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

Tom van Woensel, Laoucine Kerbache (), Herbert Peremans () and Nico Vandaele
Additional contact information
Laoucine Kerbache: GREGH - Groupement de Recherche et d'Etudes en Gestion à HEC - HEC Paris - Ecole des Hautes Etudes Commerciales - CNRS - Centre National de la Recherche Scientifique
Herbert Peremans: APL - Active Perception Lab - Universiteit Antwerpen - Universiteit Antwerpen = University of Antwerpen [Antwerpen]

Post-Print from HAL

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.

Keywords: time-dependent routing problems; queueing; dynamic travel times (search for similar items in EconPapers)
Date: 2007-03-01
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Published in Journal of Mathematical Modelling and Algorithms, 2007, Vol.6,n°1, pp.1-173. ⟨10.1007/s10852-006-9054-1⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-00465130

DOI: 10.1007/s10852-006-9054-1

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().