A queueing framework for routing problems with time-dependent travel times

Tom Van Woensel*, Laoucine Kerbache, Herbert Peremans, Nico Vandaele

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)151-173
Number of pages23
JournalJournal of Mathematical Modelling and Algorithms
Volume6
Issue number1
DOIs
Publication statusPublished - Mar 2007
Externally publishedYes

Keywords

  • Dynamic travel times
  • Queueing
  • Time-dependent routing problems

Fingerprint

Dive into the research topics of 'A queueing framework for routing problems with time-dependent travel times'. Together they form a unique fingerprint.

Cite this