Vehicle routing with dynamic travel times: a queueing approach. (English) Zbl 1146.90426

Summary: Transportation is an important component of supply chain competitiveness since it plays a major role in the inbound, inter-facility, and outbound logistics. In this context, assigning and scheduling vehicle routes is a crucial management problem. In this paper, a vehicle routing problem with dynamic travel times due to potential traffic congestion is considered. The approach developed introduces mainly the traffic congestion component based on queueing theory. This is an innovative modeling scheme to capture travel times. The queueing approach is compared with other approaches and its potential benefits are described and quantified. Moreover, the optimization of the starting times of a route at the distribution center is evaluated. Finally, the trade-off between solution quality and calculation time is discussed. Numerous test instances are used, both to illustrate the appropriateness of the approach as well as to show that time-independent solutions are often unrealistic within a congested traffic environment, which is usually the case on European road networks.


90B35 Deterministic scheduling theory in operations research
90B22 Queues and service in operations research
90C35 Programming involving graphs or networks


Full Text: DOI


[1] Aarts, E.H.L.; Lenstra, J.K., Local search in combinatorial optimization, (1997), Wiley
[2] Akçelik, R., Travel time functions for transport planning purposes: davidson’s function, its time-dependent form and an alternative travel time function, Australian road research, 21, 3, 49-59, (1991)
[3] Akçelik, R., Relating flow, density, speed and travel time models for uninterrupted and interrupted traffic, Traffic eengineering and control, 37, 9, 511-516, (1996)
[4] Augerat, P.; Belenguer, J.M.; Benavent, E.; Corber, A.; Naddef, D., Separating capacity constraints in the CVRP using tabu search, European journal of operations research, 106, 546-557, (1998) · Zbl 0991.90028
[5] Bertsimas, D.; Van Ryzin, G., A stochastic and dynamic vehicle routing problem in the Euclidian plane, Operations research, 39, 601-615, (1991) · Zbl 0736.90027
[6] Bertsimas, D.; Van Ryzin, G., Stochastic and dynamic vehicle routing problems in the Euclidean plane with multiple capacitated vehicles, Operations research, 41, 60-76, (1993) · Zbl 0776.90018
[7] Bertsimas, D.; Van Ryzin, G., Stochastic and dynamic vehicle routing with general demand and interarrival time distributions, Applied probability, 25, 947-978, (1993) · Zbl 0784.60016
[8] Bertsimas, D.J.; Simchi-Levi, D., A new generation of vehicle routing research: robust algorithms, addressing uncertainty, Operations research, 44, 2, 286-304, (1996), March-April · Zbl 0855.90053
[9] Transportation Research Board, Traffic flow theory: A state-of-the-art report. Technical report, Transporation Research Board, 1996.
[10] Brown, G.G.; Ellis, C.J.; Lenn, G.; Graves, W.; Ronen, D., Real time, wide area dispatch of mobile tank trucks, Interfaces, 17, 107-120, (1987)
[11] Coyle, J.J.; Bardi, E.J.; Langley, J.J., The management of business logistics, (1996), West Publishing
[12] Daganzo, C.F., Fundamentals of transportation and traffic operations, (1997), Elsevier Science
[13] Davidson, K.B., The theoretical basis of a flow-travel time relationship for use in transportation planning, Australian road research, 8, 1, 32-35, (1978)
[14] Fleischmann, B.; Gietz, M.; Gnutzmann, S., Time-varying travel times in vehicle routing, Transportation science, 38, 2, 160-173, (2004)
[15] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Management science, 40, 10, 1276-1290, (1994) · Zbl 0822.90053
[16] Gendreau, M.; Laporte, G.; Séguin, R., A tabu search heuristic for the vehicle routing problem with stochastic demands and customers, Operations research, 44, 3, (1996) · Zbl 0864.90043
[17] Glover, F., Tabu search, part, ORSA journal of computing, 190-206, (1989) · Zbl 0753.90054
[18] Glover, F., Tabu search, part II, ORSA journal of computing, 4-32, (1990) · Zbl 0771.90084
[19] B.D. Greenshields, A study of traffic capacity, in: Highway Research Board Proceedings 14 (1935) 448-477.
[20] D. Heidemann, A queueing theory approach to speed-flow-density relationships, in: Proceedings of the 13th International Symposium on Transportation and Traffic Theory, Lyon, France, Transporation and traffic theory, 1996.
[21] Hertz, A.; Laporte, G.; Mittaz, M., A tabu search heuristic for the capacitated arc routing problem, Operations research, 48, 1, 129-135, (2000) · Zbl 1106.90384
[22] Hill, A.V.; Benton, W.C., Modeling intra-city time-dependent travel speeds for vehicle scheduling problems, European journal of operational research, 43, 4, 343-351, (1992) · Zbl 0825.90358
[23] Ichoua, S.; Gendreau, M.; Potvin, J.-Y., Vehicle dispatching with time-dependent travel times, European journal of operational research, 144, 379-396, (2003) · Zbl 1012.90003
[24] Jain, R.; MacGregor Smith, J., Modeling vehicular traffic flow using M/G/C/C state dependent queueing models, Transportation science, 31, 324-336, (1997) · Zbl 0920.90064
[25] J.F.C. Kingman, The single server queue in heavy traffic, in: Proceedings of the Cambridge Philosophical Society, vol. 57, 1964, p. 902-904. · Zbl 0114.11703
[26] W. Kraemer and M. Lagenbach-Belz. Approximate formulae for the delay in the queueing system GI/GI/1, in: Congressbook of the Eight International Teletraffic Congress, pages 235-1/8, Melbourne, 1976.
[27] Lambrecht, M.R.; Ivens, P.L.; Vandaele, N.J., ACLIPS: A capacity and lead time integrated procedure for scheduling, Management science, 44, 11, 1548-1561, (1998), Part 1 of 2, November · Zbl 0989.90524
[28] Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms, European journal of operational research, 59, 3, 345-358, (1992) · Zbl 0761.90034
[29] C. Lecluyse, T. van Woensel, H. Peremans, Stochastic vehicle routing with random time dependent travel times, submitted for publication. · Zbl 1188.90032
[30] Malandraki, C.; Daskin, M.S., Time dependent vehicle routing problems: formulations, properties and heuristic algorithms, Transportation science, 26, 3, 185-200, (1992) · Zbl 0758.90029
[31] Malandraki, C.; Dial, R.B., A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem, European journal of operational research, 90, 45-55, (1996) · Zbl 0916.90262
[32] Pirlot, M., General local search methods, European journal of operational research, 92, 493-511, (1996) · Zbl 0914.90227
[33] Shen, Y.; Potvin, J.-Y., A computer assistant for vehicle dispatching with learning capabilities, Annals of operations research, 61, 189-211, (1995) · Zbl 0839.90039
[34] Taniguchi, E.; Thompson, R.G.; Yamada, T.; Van Duin, R., City logistics: network modelling and intelligent transport systems, (2001), Pergamon
[35] Vandaele, N.; Van Woensel, T.; Verbruggen, A., A queueing based traffic flow model, Transportation research D, 5, 2, 121-135, (2000), February
[36] Whitt, W., The queueing network analyzer, The Bell system technical journal, 62, 9, 2779-2815, (1983)
[37] Whitt, W., Approximations for the GI/G/m queue, Production and operations management, 2, 2, 114-161, (1993)
[38] T. Van Woensel, Modelling Uninterrupted Traffic Flows, a Queueing Approach. Ph.D. Dissertation, University of Antwerp, Belgium, 2003. · Zbl 1124.60079
[39] T. Van Woensel, R. Creten, N. Vandaele, Managing the environmental externalities of traffic logistics: The issue of emissions, POMS journal, Special issue on Environmental Management and Operations 10 (2) (2001).
[40] Van Woensel, T.; Vandaele, N., Empirical validation of a queueing approach to uninterrupted traffic flows, 4OR, A quarterly journal of operations research, 4, 1, 59-72, (2006) · Zbl 1124.60079
[41] Van Woensel, T.; Wuyts, B.; Vandaele, N., Validating state-dependent queueing models for uninterrupted traffic flows using simulation, 4OR, A quarterly journal of operations research, 4, 2, 159-174, (2006) · Zbl 1112.60072
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.