IDEAS home Printed from https://ideas.repec.org/p/hal/journl/hal-00465130.html
   My bibliography  Save this paper

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

Author

Listed:
  • Tom van Woensel
  • 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])

  • Nico Vandaele

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.

Suggested Citation

  • Tom van Woensel & Laoucine Kerbache & Herbert Peremans & Nico Vandaele, 2007. "A Queueing Framework for Routing Problems with Time-dependent Travel Times," Post-Print hal-00465130, HAL.
    • Handle: RePEc:hal:journl:hal-00465130
    DOI: 10.1007/s10852-006-9054-1
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    2. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2018. "The stochastic vehicle routing problem, a literature review, part I: models," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 193-221, September.
    3. LECLUYSE, C. & VAN WOENSEL, Tom & PEREMANS, Herbert, 2007. "Vehicle routing with stochastic time-dependent travel times," Working Papers 2007018, University of Antwerp, Faculty of Business and Economics.
    4. Anke Stieber & Armin Fügenschuh, 2022. "Dealing with time in the multiple traveling salespersons problem with moving targets," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(3), pages 991-1017, September.
    5. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    6. Anastasios D. Vareias & Panagiotis P. Repoussis & Panagiotis P. Repoussi, 2019. "Assessing Customer Service Reliability in Route Planning with Self-Imposed Time Windows and Stochastic Travel Times," Service Science, INFORMS, vol. 53(1), pages 256-281, February.
    7. Elgesem, Aurora Smith & Skogen, Eline Sophie & Wang, Xin & Fagerholt, Kjetil, 2018. "A traveling salesman problem with pickups and deliveries and stochastic travel times: An application from chemical shipping," European Journal of Operational Research, Elsevier, vol. 269(3), pages 844-859.
    8. Andrés Gómez & Ricardo Mariño & Raha Akhavan-Tabatabaei & Andrés L. Medaglia & Jorge E. Mendoza, 2016. "On Modeling Stochastic Travel and Service Times in Vehicle Routing," Transportation Science, INFORMS, vol. 50(2), pages 627-641, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:journl:hal-00465130. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.