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

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

Authors: Woensel, Tom Van; Kerbache, Laoucine; Peremans, Herbert; Vandaele, Nico

Journal of Mathematical Modelling and Algorithms - 2007 Volume 6, Pages 151-173

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.

https://doi.org/10.1007/s10852-006-9054-1

Cite as:

@article{Woensel_2006,
	doi = {10.1007/s10852-006-9054-1},
	url = {https://doi.org/10.1007%2Fs10852-006-9054-1},
	year = 2006,
	month = {nov},
	publisher = {Springer Science and Business Media {LLC}},
	volume = {6},
	number = {1},
	pages = {151--173},
	author = {Tom Van Woensel and Laoucine Kerbache and Herbert Peremans and Nico Vandaele},
	title = {A Queueing Framework for Routing Problems with Time-dependent Travel Times},
	journal = {Journal of Mathematical Modelling and Algorithms}
}



    Leave a Reply

    Your email address will not be published. Required fields are marked *

    x
    This site uses cookies to make navigation simple and efficient. By continuing you declare that you want to automatically accept the privacy policy. More. Close