IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v50y2016i2p627-641.html
   My bibliography  Save this article

On Modeling Stochastic Travel and Service Times in Vehicle Routing

Author

Listed:
  • Andrés Gómez

    (Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia)

  • Ricardo Mariño

    (Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia)

  • Raha Akhavan-Tabatabaei

    (Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia)

  • Andrés L. Medaglia

    (Centro para la Optimización y Probabilidad Aplicada (COPA), Departamento de Ingeniería Industrial, Universidad de los Andes, Bogotá, Colombia)

  • Jorge E. Mendoza

    (Université Catholique de l’Ouest, LARIS (EA7315), 49008 Angers, France; and Université François-Rabelais de Tours, CNRS, LI (EA6300), OC (ERL CNRS 6305), 37200 Tours, France)

Abstract

Vehicle routing problems with stochastic travel and service times (VRPSTT) consist of designing transportation routes of minimal expected cost over a network where travel and service times are represented by random variables. Most of the existing approaches for VRPSTT are conceived to exploit the properties of the distributions assumed for the random variables. Therefore, these methods are tied to a given family of distributions and subject to strong modeling assumptions. We propose an alternative way to model travel and service times in VRPSTT without making many assumptions regarding such distributions. To illustrate our approach, we embed it into a state-of-the-art routing engine and use it to conduct experiments on instances with different travel and service time distributions.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:50:y:2016:i:2:p:627-641
    DOI: 10.1287/trsc.2015.0601
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.2015.0601
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2015.0601?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    2. Li, Xiangyong & Tian, Peng & Leung, Stephen C.H., 2010. "Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm," International Journal of Production Economics, Elsevier, vol. 125(1), pages 137-145, May.
    3. 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.
    4. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    5. Taş, D. & Gendreau, M. & Dellaert, N. & van Woensel, T. & de Kok, A.G., 2014. "Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach," European Journal of Operational Research, Elsevier, vol. 236(3), pages 789-799.
    6. Gilbert Laporte, 2007. "What you should know about the vehicle routing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(8), pages 811-819, December.
    7. Figliozzi, Miguel Andres, 2010. "The impacts of congestion on commercial vehicle tour characteristics and costs," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(4), pages 496-506, July.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Bock, Stefan, 2020. "Optimally solving a versatile Traveling Salesman Problem on tree networks with soft due dates and multiple congestion scenarios," European Journal of Operational Research, Elsevier, vol. 283(3), pages 863-882.
    2. Ramon Faganello Fachini & Vinícius Amaral Armentano & Franklina Maria Bragion Toledo, 2022. "A Granular Local Search Matheuristic for a Heterogeneous Fleet Vehicle Routing Problem with Stochastic Travel Times," Networks and Spatial Economics, Springer, vol. 22(1), pages 33-64, March.
    3. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    4. Groß, Patrick-Oliver & Ehmke, Jan Fabian & Mattfeld, Dirk Christian, 2020. "Interval travel times for robust synchronization in city logistics vehicle routing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    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. Irawan, Chandra Ade & Eskandarpour, Majid & Ouelhadj, Djamila & Jones, Dylan, 2021. "Simulation-based optimisation for stochastic maintenance routing in an offshore wind farm," European Journal of Operational Research, Elsevier, vol. 289(3), pages 912-926.
    7. Rafael Dawid & David McMillan & Matthew Revie, 2018. "Decision Support Tool for Offshore Wind Farm Vessel Routing under Uncertainty," Energies, MDPI, vol. 11(9), pages 1-17, August.
    8. 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.
    9. Saif Eddin Jabari & Nikolaos M. Freris & Deepthi Mary Dilip, 2020. "Sparse Travel Time Estimation from Streaming Data," Transportation Science, INFORMS, vol. 54(1), pages 1-20, January.
    10. David Corredor-Montenegro & Nicolás Cabrera & Raha Akhavan-Tabatabaei & Andrés L. Medaglia, 2021. "On the shortest $$\alpha$$ α -reliable path problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 287-318, April.
    11. 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.
    12. Chandra Ade Irawan & Majid Eskandarpour & Djamila Ouelhadj & Dylan Jones, 2019. "Simulation-based optimisation for stochastic maintenance routing in an offshore wind farm," Post-Print hal-02509382, HAL.
    13. 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.
    14. Alexandra Anderluh & Rune Larsen & Vera C. Hemmelmayr & Pamela C. Nolz, 2020. "Impact of travel time uncertainties on the solution cost of a two-echelon vehicle routing problem with synchronization," Flexible Services and Manufacturing Journal, Springer, vol. 32(4), pages 806-828, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    2. Hossein Hashemi Doulabi & Gilles Pesant & Louis-Martin Rousseau, 2020. "Vehicle Routing Problems with Synchronized Visits and Stochastic Travel and Service Times: Applications in Healthcare," Transportation Science, INFORMS, vol. 54(4), pages 1053-1072, July.
    3. 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.
    4. Liu, Bingbing & Guo, Xiaolong & Yu, Yugang & Zhou, Qiang, 2019. "Minimizing the total completion time of an urban delivery problem with uncertain assembly time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 132(C), pages 163-182.
    5. Ehmke, Jan Fabian & Campbell, Ann Melissa & Urban, Timothy L., 2015. "Ensuring service levels in routing problems with time windows and stochastic travel times," European Journal of Operational Research, Elsevier, vol. 240(2), pages 539-550.
    6. Biao Yuan & Ran Liu & Zhibin Jiang, 2015. "A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements," International Journal of Production Research, Taylor & Francis Journals, vol. 53(24), pages 7450-7464, December.
    7. Mojtaba Rajabi-Bahaabadi & Afshin Shariat-Mohaymany & Mohsen Babaei & Daniele Vigo, 2021. "Reliable vehicle routing problem in stochastic networks with correlated travel times," Operational Research, Springer, vol. 21(1), pages 299-330, March.
    8. 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.
    9. 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.
    10. F. Errico & G. Desaulniers & M. Gendreau & W. Rei & L.-M. Rousseau, 2018. "The vehicle routing problem with hard time windows and stochastic service times," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 223-251, September.
    11. Mathias A. Klapp & Alan L. Erera & Alejandro Toriello, 2018. "The One-Dimensional Dynamic Dispatch Waves Problem," Transportation Science, INFORMS, vol. 52(2), pages 402-415, March.
    12. Hongtao Lei & Gilbert Laporte & Bo Guo, 2012. "A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 20(1), pages 99-118, April.
    13. Yan, Shangyao & Lin, Jenn-Rong & Lai, Chun-Wei, 2013. "The planning and real-time adjustment of courier routing and scheduling under stochastic travel times and demands," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 53(C), pages 34-48.
    14. Errico, F. & Desaulniers, G. & Gendreau, M. & Rei, W. & Rousseau, L.-M., 2016. "A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times," European Journal of Operational Research, Elsevier, vol. 249(1), pages 55-66.
    15. Huang, Kuancheng & Wu, Kun-Feng & Ardiansyah, Muhammad Nashir, 2019. "A stochastic dairy transportation problem considering collection and delivery phases," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 129(C), pages 325-338.
    16. 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.
    17. Junlong Zhang & William Lam & Bi Chen, 2013. "A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service," Networks and Spatial Economics, Springer, vol. 13(4), pages 471-496, December.
    18. Avraham, Edison & Raviv, Tal, 2020. "The data-driven time-dependent traveling salesperson problem," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 25-40.
    19. Mohammed Bazirha & Abdeslam Kadrani & Rachid Benmansour, 2023. "Stochastic home health care routing and scheduling problem with multiple synchronized services," Annals of Operations Research, Springer, vol. 320(2), pages 573-601, January.
    20. Chen, Lu & Gendreau, Michel & Hà, Minh Hoàng & Langevin, André, 2016. "A robust optimization approach for the road network daily maintenance routing problem with uncertain service time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 40-51.

    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:inm:ortrsc:v:50:y:2016:i:2:p:627-641. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.