Vehicle routing with stochastic time-dependent travel times. (English) Zbl 1188.90032

Summary: Assigning and scheduling vehicle routes in a stochastic time-dependent environment is a crucial management problem. The assumption that in a real-life environment everything goes according to an a priori determined static schedule is unrealistic. Our methodology builds on earlier work in which the traffic congestion is captured in an analytical way using queueing theory. The congestion is then applied to the \(VRP\) problem. In this paper, we introduce the variability in traffic flows into the model. This allows for an evaluation of the routes based on the uncertainty involved. Different experiments show that the risk taking behavior of the planner can be taken into account during optimization. As more weight is given to the variability component, the resulting optimal route will take a slightly longer travel time, but will be more reliable. We propose a powerful objective function that is easily implemented and that captures the trade-off between the average travel time and its variance. The evaluation of the solution is done in terms of the 95th-percentile of the travel time distribution (assumed to be lognormal), which reflects well the quality of the solution in this stochastic time-dependent environment.


90B06 Transportation, logistics and supply chain management
90B15 Stochastic network models in operations research


Full Text: DOI Link


[1] Augerat P, Belenguer JM, Benavent E, Corber A, Naddef D (1998) Separating capacity constraints in the CVRP using tabu search. Eur J Oper Res 106: 546–557 · Zbl 0991.90028 · doi:10.1016/S0377-2217(97)00290-7
[2] Beaulieu NC, Xie Q (2004) An optimal lognormal approximation to lognormal sum distributions. IEEE Trans Vehicular Technol 53(2): 479–489 · doi:10.1109/TVT.2004.823494
[3] Berry DS, Belmont DM (1951) Distribution of vehicle speeds and travel times. In: Proceedings of 2nd Berkeley symposium on mathematical and statistical probabability, pp 589–602
[4] Best MJ, Grauer RR (1991) Sensitivity analysis for mean-variance portfolio problems. Manage Sci 37(8): 980–989 · Zbl 0729.90857 · doi:10.1287/mnsc.37.8.980
[5] Chen C, van Zwet E, Varaiya P, Skabardonis A (2003) Travel time reliability as a measure of service. Technical report, Transporation Research Board
[6] DfT (2000) Transport 2010: the 10 year plan. Technical report, DETR, July
[7] DfT (2003) Delivering better transport–progress report. Technical report
[8] Donati AV, Montemanni R, Casagrande N, Rizzoli AE, Gambardella LM (2003) Time dependent vehicle routing problem with a multi ant colony system. Technical Report IDSIA 2-03, International IDSIA, 2003 · Zbl 1146.90328
[9] Finkel AM (1990) A simple formula for calculating the mass density of a lognormally-distributed characteristic: Applications to risk analysis. Risk Anal 10(2): 291–301 · doi:10.1111/j.1539-6924.1990.tb01050.x
[10] Fu L, Rilett LR (1998) Expected shortest path in dynamic and stochastic traffic networks. Transp Res Record 32(7): 499–516
[11] Gao S, Chabini I (2002) The best routing policy problem in stochastic time-dependent networks. Transp Res Record 1783: 188–196 · doi:10.3141/1783-23
[12] Gao S, Chabini I (2006) Optimal routing policy problem in stochastic time-dependent networks. Transp Res B 40: 93–122 · doi:10.1016/j.trb.2005.02.001
[13] Gendreau M, Hertz A, Laporte G (1994) A tabu search heuristic for the vehicle routing problem. Manage Sci 40(10): 1276–1290 · Zbl 0822.90053 · doi:10.1287/mnsc.40.10.1276
[14] Gendreau M, Laporte G, Séguin R (1996) A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Oper Res 44(3): 469–477 · Zbl 0864.90043 · doi:10.1287/opre.44.3.469
[15] Gendreau M, Laporte G, Séguin R (1996b) Stochastic vehicle routing. Eur J Oper Res 88(1): 3–12 · Zbl 0913.90094 · doi:10.1016/0377-2217(95)00050-X
[16] Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comp Oper Res 13(5): 533–549 · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[17] Grauer RR, Hakansson NH (1993) On the use of mean–variance and quadratic approximations in implementing dynamic investment strategies: a comparison of returns and investment policies. Manage Sci 39(7): 856–871 · doi:10.1287/mnsc.39.7.856
[18] Haghani A, Jung S (2005) A dynamic vehicle routing problem with time-dependent travel times. Comp Oper Res 32: 2959–2986 · Zbl 1071.90011 · doi:10.1016/j.cor.2004.04.013
[19] Hall RW (1986) The fastest path through a network with random time-dependent travel times. Transp Sci 20(3): 182–188 · doi:10.1287/trsc.20.3.182
[20] He RR, Kornhauser AL, Ran B (2005) Essentially best routes in dynamic and stochastic transportation network. Int J Vehicle Inf Commun Syst 1(1–2): 1–14 · doi:10.1504/IJVICS.2005.007582
[21] Heidemann D (1996) A queueing theory approach to speed-flow-density relationships. In: Proceedings of the 13th international symposium on transportation and traffic theory, Lyon, France, 1996. Transporation and traffic theory
[22] Hertz A, Laporte G, Mittaz M (2000) A tabu search heuristic for the capacitated arc routing problem. Oper Res 48(1): 129–135 · Zbl 1106.90384 · doi:10.1287/opre.
[23] Ichoua S, Gendreau M, Potvin J-Y (2003) Vehicle dispatching with time-dependent travel times. Eur J Oper Res 144: 379–396 · Zbl 1012.90003 · doi:10.1016/S0377-2217(02)00147-9
[24] Kharoufeh JP, Gautam N (2004) Deriving link travel-time distributions via stochastic speed processes. Transp Sci 38(1): 97–106 · doi:10.1287/trsc.1030.0048
[25] Kwon J, Coifman B, Bickel P (2000) Day-to-day travel time trends and travel-time prediction from loop-detector data. Transp Res Record 1717: 120–129 · doi:10.3141/1717-15
[26] Laporte G (1992) The vehicle routing problem: An overview of exact and approximate algorithms. Eur J Oper Res 59(3): 345–358 · Zbl 0761.90034 · doi:10.1016/0377-2217(92)90192-C
[27] Laporte G, Louveaux F, Mercure H (1992) The vehicle routing problem with stochastic travel times. Transp Sci 26(3): 161–170 · Zbl 0761.90035 · doi:10.1287/trsc.26.3.161
[28] Malandraki C, Daskin MS (1992) Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transp Sci 26(3): 185–200 · Zbl 0758.90029 · doi:10.1287/trsc.26.3.185
[29] Mulvey JM, Vanderbei RJ, Zenios SA (1995) Robust optimization of large-scale systems. Oper Res 43(2): 264–281 · Zbl 0832.90084 · doi:10.1287/opre.43.2.264
[30] Osman IH (1991) Metastrategy Simulated Annealing and Tabu Search Algorithms for Combinatorial Optimization Problems. PhD Thesis, Imperial College London, The Management School
[31] Osman IH (1993) Vehicle routing and scheduling: Applications, algorithms and developments. In: Proceeding of the international conference on industrial logistics, Rennes
[32] Pirlot M (1996) General local search methods. Eur J Oper Res 92: 493–511 · Zbl 0914.90227 · doi:10.1016/0377-2217(96)00007-0
[33] Rockwell Software Inc. (2005) Arena user’s guide. Rockwell Software Inc., USA
[34] Taniguchi E, Thompson RG, Yamada T, Van Duin R (2001) City logistics: network modelling and intelligent transport systems. Pergamon, New York
[35] Van Woensel T, Vandaele N (2006) Empirical validation of a queueing approach to uninterrupted traffic flows. A Quart J Oper Res 4(1): 59–72 · Zbl 1124.60079
[36] Van Woensel T, Creten R, Vandaele N (2001) Managing the environmental externalities of traffic logistics: the issue of emissions. POMS J Spec Issue Environ Manage Oper 10(2)
[37] Van Woensel T, Kerbache L, Peremans H, Vandaele N (2008) Vehicle routing with dynamic travel times: A queueing approach. EJOR 186(3): 990–1007 · Zbl 1146.90426 · doi:10.1016/j.ejor.2007.03.012
[38] Vandaele N, Van Woensel T, Verbruggen A (2000) A queueing based traffic flow model. Transp Res D 5(2): 121–135 · doi:10.1016/S1361-9209(99)00028-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.