IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v249y2016i1p55-66.html
   My bibliography  Save this article

A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times

Author

Listed:
  • Errico, F.
  • Desaulniers, G.
  • Gendreau, M.
  • Rei, W.
  • Rousseau, L.-M.

Abstract

The vehicle routing problem with hard time windows and stochastic service times (VRPTW-ST) introduced by Errico et al. (2013) in the form of a chance-constrained model mainly differs from other vehicle routing problems with stochastic service or travel times considered in the literature by the presence of hard time windows. This makes the problem extremely challenging. In this paper, we model the VRPTW-ST as a two-stage stochastic program and define two recourse policies to recover operations feasibility when the first stage plan turns out to be infeasible. We formulate the VRPTW-ST as a set partitioning problem and solve it by exact branch-cut-and-price algorithms. Specifically, we developed efficient labeling algorithms by suitably choosing label components, determining extension functions, and developing lower and upper bounds on partial route reduced cost to be used in the column generation step. Results on benchmark data show that our methods are able to solve instances with up to 50 customers for both recourse policies.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:249:y:2016:i:1:p:55-66
    DOI: 10.1016/j.ejor.2015.07.027
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715006608
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.07.027?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. 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. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    3. Dimitris J. Bertsimas, 1992. "A Vehicle Routing Problem with Stochastic Demand," Operations Research, INFORMS, vol. 40(3), pages 574-585, June.
    4. 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.
    5. Ilgaz Sungur & Yingtao Ren & Fernando Ordóñez & Maged Dessouky & Hongsheng Zhong, 2010. "A Model and Algorithm for the Courier Delivery Problem with Uncertainty," Transportation Science, INFORMS, vol. 44(2), pages 193-205, May.
    6. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    7. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    8. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    9. Guy Desaulniers & François Lessard & Ahmed Hadjar, 2008. "Tabu Search, Partial Elementarity, and Generalized k -Path Inequalities for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 42(3), pages 387-404, August.
    10. Michel Gendreau & Gilbert Laporte & René Séguin, 1995. "An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers," Transportation Science, INFORMS, vol. 29(2), pages 143-155, May.
    11. C Lee & K Lee & S Park, 2012. "Robust vehicle routing problem with deadlines and travel time/demand uncertainty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 63(9), pages 1294-1306, September.
    12. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    13. 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.
    14. Mads Jepsen & Bjørn Petersen & Simon Spoorendonk & David Pisinger, 2008. "Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows," Operations Research, INFORMS, vol. 56(2), pages 497-511, April.
    15. Chang, Tsung-Sheng & Wan, Yat-wah & OOI, Wei Tsang, 2009. "A stochastic dynamic traveling salesman problem with hard time windows," European Journal of Operational Research, Elsevier, vol. 198(3), pages 748-759, November.
    16. 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.
    17. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    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. Wang, Yang & Bi, Mengyu & Lai, Jianhui & Wang, Chenxi & Chen, Yanyan & Holguín-Veras, José, 2024. "Recourse strategy for the routing problem of mobile parcel lockers with time windows under uncertain demands," European Journal of Operational Research, Elsevier, vol. 316(3), pages 942-957.
    2. 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.
    3. 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.
    4. Federica Bomboi & Christoph Buchheim & Jonas Pruente, 2022. "On the stochastic vehicle routing problem with time windows, correlated travel times, and time dependency," 4OR, Springer, vol. 20(2), pages 217-239, June.
    5. Borzou Rostami & Guy Desaulniers & Fausto Errico & Andrea Lodi, 2021. "Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times," Operations Research, INFORMS, vol. 69(2), pages 436-455, March.
    6. Jin Qin & Yong Ye & Bi-rong Cheng & Xiaobo Zhao & Linling Ni, 2017. "The Emergency Vehicle Routing Problem with Uncertain Demand under Sustainability Environments," Sustainability, MDPI, vol. 9(2), pages 1-24, February.
    7. Yang, Meng & Ni, Yaodong & Song, Qinyu, 2022. "Optimizing driver consistency in the vehicle routing problem under uncertain environment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    8. 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.
    9. Guodong Yu & Yu Yang, 2019. "Dynamic routing with real-time traffic information," Operational Research, Springer, vol. 19(4), pages 1033-1058, December.
    10. Pedro Munari & Alfredo Moreno & Jonathan De La Vega & Douglas Alem & Jacek Gondzio & Reinaldo Morabito, 2019. "The Robust Vehicle Routing Problem with Time Windows: Compact Formulation and Branch-Price-and-Cut Method," Transportation Science, INFORMS, vol. 53(4), pages 1043-1066, July.
    11. Zhaoxia Guo & Stein W. Wallace & Michal Kaut, 2019. "Vehicle Routing with Space- and Time-Correlated Stochastic Travel Times: Evaluating the Objective Function," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 654-670, October.
    12. Andreas Hagn & Rainer Kolisch & Giacomo Dall'Olio & Stefan Weltge, 2024. "A Branch-Price-Cut-And-Switch Approach for Optimizing Team Formation and Routing for Airport Baggage Handling Tasks with Stochastic Travel Times," Papers 2405.20912, arXiv.org.
    13. Zhang, Bo & Li, Hui & Li, Shengguo & Peng, Jin, 2018. "Sustainable multi-depot emergency facilities location-routing problem with uncertain information," Applied Mathematics and Computation, Elsevier, vol. 333(C), pages 506-520.
    14. 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.
    15. Dalmeijer, K. & Spliet, R. & Wagelmans, A.P.M., 2019. "Dynamic Time Window Adjustment," Econometric Institute Research Papers EI2019-22, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    16. Hongwen Han & Luxian Chen & Sitong Fang & Yang Liu, 2023. "The Routing Problem for Electric Truck with Partial Nonlinear Charging and Battery Swapping," Sustainability, MDPI, vol. 15(18), pages 1-29, September.
    17. Reusken, Meike & Laporte, Gilbert & Rohmer, Sonja U.K. & Cruijssen, Frans, 2024. "Vehicle routing with stochastic demand, service and waiting times — The case of food bank collection problems," European Journal of Operational Research, Elsevier, vol. 317(1), pages 111-127.
    18. 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.
    19. Zhou, Qing & Benlic, Una & Wu, Qinghua & Hao, Jin-Kao, 2019. "Heuristic search to the capacitated clustering problem," European Journal of Operational Research, Elsevier, vol. 273(2), pages 464-487.
    20. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    21. Chengji Liang & Yue Zhang & Liang Dong, 2022. "A Three Stage Optimal Scheduling Algorithm for AGV Route Planning Considering Collision Avoidance under Speed Control Strategy," Mathematics, MDPI, vol. 11(1), pages 1-18, December.
    22. 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.
    23. Edgar Gutierrez-Franco & Christopher Mejia-Argueta & Luis Rabelo, 2021. "Data-Driven Methodology to Support Long-Lasting Logistics and Decision Making for Urban Last-Mile Operations," Sustainability, MDPI, vol. 13(11), pages 1-33, June.
    24. 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.

    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. 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.
    2. Borzou Rostami & Guy Desaulniers & Fausto Errico & Andrea Lodi, 2021. "Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times," Operations Research, INFORMS, vol. 69(2), pages 436-455, March.
    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. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2018. "Branch-and-Price-and-Cut for the Truck-and-Trailer Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 52(5), pages 1174-1190, October.
    5. 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).
    6. 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.
    7. Pedro Munari & Alfredo Moreno & Jonathan De La Vega & Douglas Alem & Jacek Gondzio & Reinaldo Morabito, 2019. "The Robust Vehicle Routing Problem with Time Windows: Compact Formulation and Branch-Price-and-Cut Method," Transportation Science, INFORMS, vol. 53(4), pages 1043-1066, July.
    8. Tilk, Christian & Rothenbächer, Ann-Kathrin & Gschwind, Timo & Irnich, Stefan, 2017. "Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster," European Journal of Operational Research, Elsevier, vol. 261(2), pages 530-539.
    9. Yiming Liu & Yang Yu & Yu Zhang & Roberto Baldacci & Jiafu Tang & Xinggang Luo & Wei Sun, 2023. "Branch-Cut-and-Price for the Time-Dependent Green Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 14-30, January.
    10. Jinil Han & Chungmok Lee & Sungsoo Park, 2014. "A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times," Transportation Science, INFORMS, vol. 48(3), pages 373-390, August.
    11. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    12. Ann-Kathrin Rothenbächer & Michael Drexl & Stefan Irnich, 2016. "Branch-and-Price-and-Cut for the Truck-andTrailer Routing Problem with Time Windows," Working Papers 1617, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    13. Qie He & Stefan Irnich & Yongjia Song, 2019. "Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs," Transportation Science, INFORMS, vol. 53(5), pages 1409-1426, September.
    14. Gschwind, Timo & Bianchessi, Nicola & Irnich, Stefan, 2019. "Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 91-104.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    20. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.

    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:eee:ejores:v:249:y:2016:i:1:p:55-66. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.