Skip to Main content Skip to Navigation
Journal articles

A Queueing Framework for Routing Problems with Time-dependent Travel Times

Abstract : Assigning and scheduling vehicle routes in a dynamic environment is a crucial management problem. Despite numerous publications dealing with efficient scheduling methods for vehicle routing, very few addressed the inherent stochastic and dynamic nature of travel times. In this paper, a vehicle routing problem with time-dependent travel times due to potential traffic congestion is considered. The approach developed introduces the traffic congestion component based on queueing theory. This is an innovative modelling scheme to capture the stochastic behavior of travel times as it generates an analytical expression for the expected travel times as well as for the variance of the travel times. Routing solutions that perform well in the face of the extra complications due to congestion are developed. These more realistic solutions have the potential to reduce real operating costs for a broad range of industries which daily face routing problems. A number of datasets are used to illustrate the appropriateness of the novel approach. Moreover it is shown that static (or time-independent) solutions are often infeasible within a congested traffic environment which is generally the case on European road networks. Finally, the effect of travel time variability (obtained via the queueing approach) is quantified for the different datasets.
Complete list of metadatas

https://hal-hec.archives-ouvertes.fr/hal-00465130
Contributor : Antoine Haldemann <>
Submitted on : Friday, March 19, 2010 - 10:06:47 AM
Last modification on : Thursday, January 11, 2018 - 6:19:31 AM

Links full text

Identifiers

Collections

Citation

Tom van Woensel, Laoucine Kerbache, Herbert Peremans, Nico Vandaele. A Queueing Framework for Routing Problems with Time-dependent Travel Times. Journal of Mathematical Modelling and Algorithms, Springer Verlag, 2007, Vol.6,n°1, pp.1-173. ⟨10.1007/s10852-006-9054-1⟩. ⟨hal-00465130⟩

Share

Metrics

Record views

310