IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v21y2021i1d10.1007_s12351-019-00452-w.html
   My bibliography  Save this article

Reliable vehicle routing problem in stochastic networks with correlated travel times

Author

Listed:
  • Mojtaba Rajabi-Bahaabadi

    (Iran University of Science and Technology)

  • Afshin Shariat-Mohaymany

    (Iran University of Science and Technology)

  • Mohsen Babaei

    (Bu-Ali Sina University)

  • Daniele Vigo

    (University of Bologna)

Abstract

This study is motivated by the fact that travel times on road networks are correlated. However, all existing studies on the vehicle routing problem share a common simplifying assumption that arc travel times are independently distributed. In this paper, we address a variant of the vehicle routing problem with soft time windows in which travel times are treated as correlated random variables. To this end, correlations among arc travel times are modeled by a variance–covariance matrix. We use a mathematical model in which penalties are incurred for early and late arrival at each customer (violation of time window constraints). A Max–Min ant colony system is hybridized with a tabu search algorithm to solve the model. Results show that ignorance of correlations among arc travel times can significantly lead to inefficient solutions to the vehicle routing problem in stochastic networks. We also conduct an exploratory analysis of real travel time data. The results of the analysis demonstrate that travel times are significantly correlated and the shifted log-normal distribution is an appropriate candidate for modeling travel time uncertainty.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:operea:v:21:y:2021:i:1:d:10.1007_s12351-019-00452-w
    DOI: 10.1007/s12351-019-00452-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-019-00452-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s12351-019-00452-w?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Lam, William H.K. & Shao, Hu & Sumalee, Agachai, 2008. "Modeling impacts of adverse weather conditions on a road network with uncertainties in demand and supply," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 890-910, December.
    2. Ramezani, Mohsen & Geroliminis, Nikolas, 2012. "On the estimation of arterial route travel time distribution with Markov chains," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1576-1590.
    3. Patrick Jaillet & Jin Qi & Melvyn Sim, 2016. "Routing Optimization Under Uncertainty," Operations Research, INFORMS, vol. 64(1), pages 186-200, February.
    4. Jenelius, Erik & Koutsopoulos, Haris N., 2013. "Travel time estimation for urban road networks using low frequency probe vehicle data," Transportation Research Part B: Methodological, Elsevier, vol. 53(C), pages 64-81.
    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. Éric Taillard & Philippe Badeau & Michel Gendreau & François Guertin & Jean-Yves Potvin, 1997. "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows," Transportation Science, INFORMS, vol. 31(2), pages 170-186, May.
    7. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    8. Naoki Ando & Eiichi Taniguchi, 2006. "Travel Time Reliability in Vehicle Routing and Scheduling with Time Windows," Networks and Spatial Economics, Springer, vol. 6(3), pages 293-311, September.
    9. David B. Brown & Melvyn Sim, 2009. "Satisficing Measures for Analysis of Risky Positions," Management Science, INFORMS, vol. 55(1), pages 71-84, January.
    10. Jiang, J. & Ng, K.M. & Teo, K.M., 2016. "Satisficing measure approach for vehicle routing problem with time windows under uncertaintyAuthor-Name: Nguyen, V.A," European Journal of Operational Research, Elsevier, vol. 248(2), pages 404-414.
    11. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    12. 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.
    13. Christophe Duhamel & Jean-Yves Potvin & Jean-Marc Rousseau, 1997. "A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows," Transportation Science, INFORMS, vol. 31(1), pages 49-59, February.
    14. Westgate, Bradford S. & Woodard, Dawn B. & Matteson, David S. & Henderson, Shane G., 2016. "Large-network travel time distribution estimation for ambulances," European Journal of Operational Research, Elsevier, vol. 252(1), pages 322-333.
    15. Yossiri Adulyasak & Patrick Jaillet, 2016. "Models and Algorithms for Stochastic and Robust Vehicle Routing with Deadlines," Transportation Science, INFORMS, vol. 50(2), pages 608-626, May.
    16. 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.
    17. R A Russell & T L Urban, 2008. "Vehicle routing with soft time windows and Erlang travel times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1220-1228, September.
    18. 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.
    19. Tao Cheng & James Haworth & Jiaqiu Wang, 2012. "Spatio-temporal autocorrelation of road network data," Journal of Geographical Systems, Springer, vol. 14(4), pages 389-413, October.
    20. 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.
    21. Lau, Hoong Chuin & Sim, Melvyn & Teo, Kwong Meng, 2003. "Vehicle routing problem with time windows and a limited number of vehicles," European Journal of Operational Research, Elsevier, vol. 148(3), pages 559-569, August.
    22. Michel Gendreau & Ola Jabali & Walter Rei, 2016. "50th Anniversary Invited Article—Future Research Directions in Stochastic Vehicle Routing," Transportation Science, INFORMS, vol. 50(4), pages 1163-1173, November.
    23. Tomáš Režnar & Jan Martinovič & Kateřina Slaninová & Ekaterina Grakova & Vít Vondrák, 2017. "Probabilistic time-dependent vehicle routing problem," 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. 25(3), pages 545-560, September.
    24. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. 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.
    3. 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.
    4. Yu Zhang & Zhenzhen Zhang & Andrew Lim & Melvyn Sim, 2021. "Robust Data-Driven Vehicle Routing with Time Windows," Operations Research, INFORMS, vol. 69(2), pages 469-485, March.
    5. 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.
    6. Maaike Hoogeboom & Yossiri Adulyasak & Wout Dullaert & Patrick Jaillet, 2021. "The Robust Vehicle Routing Problem with Time Window Assignments," Transportation Science, INFORMS, vol. 55(2), pages 395-413, March.
    7. 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.
    8. Jiang, J. & Ng, K.M. & Teo, K.M., 2016. "Satisficing measure approach for vehicle routing problem with time windows under uncertaintyAuthor-Name: Nguyen, V.A," European Journal of Operational Research, Elsevier, vol. 248(2), pages 404-414.
    9. 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.
    10. Alexandre M. Florio & Richard F. Hartl & Stefan Minner & Juan-José Salazar-González, 2021. "A Branch-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands and Probabilistic Duration Constraints," Transportation Science, INFORMS, vol. 55(1), pages 122-138, 1-2.
    11. 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.
    12. 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.
    13. 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).
    14. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    15. R A Russell & T L Urban, 2008. "Vehicle routing with soft time windows and Erlang travel times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(9), pages 1220-1228, September.
    16. 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.
    17. Sana Jawarneh & Salwani Abdullah, 2015. "Sequential Insertion Heuristic with Adaptive Bee Colony Optimisation Algorithm for Vehicle Routing Problem with Time Windows," PLOS ONE, Public Library of Science, vol. 10(7), pages 1-23, July.
    18. Maria João Santos & Pedro Amorim & Alexandra Marques & Ana Carvalho & Ana Póvoa, 2020. "The vehicle routing problem with backhauls towards a sustainability perspective: a review," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 358-401, July.
    19. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    20. Shi, Yong & Boudouh, Toufik & Grunder, Olivier, 2019. "A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 52-95.

    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:spr:operea:v:21:y:2021:i:1:d:10.1007_s12351-019-00452-w. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.