IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v177y2023ics1366554523002144.html
   My bibliography  Save this article

A branch-and-regret algorithm for the same-day delivery problem

Author

Listed:
  • Côté, Jean-François
  • Alves de Queiroz, Thiago
  • Gallesi, Francesco
  • Iori, Manuel

Abstract

We study a dynamic vehicle routing problem where stochastic customers request urgent deliveries characterized by restricted time windows. The aim is to use a fleet of vehicles to maximize the number of served requests and minimize the traveled distance. The problem is known in the literature as the same-day delivery problem, and it is of high importance because it models a number of real-world applications, including the delivery of online purchases. We solve the same-day delivery problem by proposing a novel branch-and-regret algorithm in which sampled scenarios are used to anticipate future events and an adaptive large neighborhood search is iteratively invoked to optimize routing plans. The branch-and-regret is equipped with four innovation elements: a new way to model the subproblem, a new policy to generate scenarios, new consensus functions, and a new branching scheme Extensive computational experiments on a large variety of instances prove the outstanding performance of the branch-and-regret, also in comparison with recent literature, in terms of served requests, traveled distance, and computational effort.

Suggested Citation

  • Côté, Jean-François & Alves de Queiroz, Thiago & Gallesi, Francesco & Iori, Manuel, 2023. "A branch-and-regret algorithm for the same-day delivery problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    • Handle: RePEc:eee:transe:v:177:y:2023:i:c:s1366554523002144
    DOI: 10.1016/j.tre.2023.103226
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554523002144
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2023.103226?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. Michel Gendreau & François Guertin & Jean-Yves Potvin & Éric Taillard, 1999. "Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching," Transportation Science, INFORMS, vol. 33(4), pages 381-390, November.
    2. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    3. 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.
    4. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    5. Liu, Dan & Yan, Pengyu & Pu, Ziyuan & Wang, Yinhai & Kaisar, Evangelos I., 2021. "Hybrid artificial immune algorithm for optimizing a Van-Robot E-grocery delivery system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    6. Ulrike Ritzinger & Jakob Puchinger & Richard F. Hartl, 2016. "A survey on dynamic and stochastic vehicle routing problems," International Journal of Production Research, Taylor & Francis Journals, vol. 54(1), pages 215-231, January.
    7. Stacy A. Voccia & Ann Melissa Campbell & Barrett W. Thomas, 2019. "The Same-Day Delivery Problem for Online Purchases," Service Science, INFORMS, vol. 53(1), pages 167-184, February.
    8. Alan S. Minkoff, 1993. "A Markov Decision Model and Decomposition Heuristic for Dynamic Vehicle Dispatching," Operations Research, INFORMS, vol. 41(1), pages 77-90, February.
    9. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2016. "The Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates," Transportation Science, INFORMS, vol. 50(2), pages 676-693, May.
    10. Rosario Paradiso & Roberto Roberti & Demetrio Laganá & Wout Dullaert, 2020. "An Exact Solution Framework for Multitrip Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 68(1), pages 180-198, January.
    11. Potvin, Jean-Yves & Rousseau, Jean-Marc, 1993. "A parallel route building algorithm for the vehicle routing and scheduling problem with time windows," European Journal of Operational Research, Elsevier, vol. 66(3), pages 331-340, May.
    12. Marlin W. Ulmer & Barrett W. Thomas & Dirk C. Mattfeld, 2019. "Preemptive depot returns for dynamic same-day delivery," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(4), pages 327-361, December.
    13. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2018. "Vehicle routing problems with multiple trips," Annals of Operations Research, Springer, vol. 271(1), pages 127-159, December.
    14. Willem Klein Haneveld & Maarten van der Vlerk, 1999. "Stochastic integer programming:General models and algorithms," Annals of Operations Research, Springer, vol. 85(0), pages 39-57, January.
    15. Bruno P. Bruck & Manuel Iori, 2017. "Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries," Operations Research, INFORMS, vol. 65(6), pages 1597-1614, December.
    16. Mitrovic-Minic, Snezana & Laporte, Gilbert, 2004. "Waiting strategies for the dynamic pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(7), pages 635-655, August.
    17. Marlin W. Ulmer, 2020. "Dynamic Pricing and Routing for Same-Day Delivery," Transportation Science, INFORMS, vol. 54(4), pages 1016-1033, July.
    18. Iman Dayarian & Martin Savelsbergh & John-Paul Clarke, 2020. "Same-Day Delivery with Drone Resupply," Transportation Science, INFORMS, vol. 54(1), pages 229-249, January.
    19. Naccache, Salma & Côté, Jean-François & Coelho, Leandro C., 2018. "The multi-pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 269(1), pages 353-362.
    20. Azi, Nabila & Gendreau, Michel & Potvin, Jean-Yves, 2010. "An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles," European Journal of Operational Research, Elsevier, vol. 202(3), pages 756-763, May.
    21. Archetti, C. & Feillet, D. & Mor, A. & Speranza, M.G., 2020. "Dynamic traveling salesman problem with stochastic release dates," European Journal of Operational Research, Elsevier, vol. 280(3), pages 832-844.
    22. Ghiani, Gianpaolo & Manni, Emanuele & Quaranta, Antonella & Triki, Chefi, 2009. "Anticipatory algorithms for same-day courier dispatching," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 45(1), pages 96-106, January.
    23. Lars M. Hvattum & Arne Løkketangen & Gilbert Laporte, 2006. "Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic," Transportation Science, INFORMS, vol. 40(4), pages 421-438, November.
    24. Marlin W. Ulmer & Barrett W. Thomas & Ann Melissa Campbell & Nicholas Woyak, 2021. "The Restaurant Meal Delivery Problem: Dynamic Pickup and Delivery with Deadlines and Random Ready Times," Transportation Science, INFORMS, vol. 55(1), pages 75-100, 1-2.
    25. Nabila Azi & Michel Gendreau & Jean-Yves Potvin, 2012. "A dynamic vehicle routing problem with multiple delivery routes," Annals of Operations Research, Springer, vol. 199(1), pages 103-112, October.
    26. Aristide Mingozzi & Roberto Roberti & Paolo Toth, 2013. "An Exact Algorithm for the Multitrip Vehicle Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 193-207, May.
    27. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2020. "Adaptive large neighborhood search for the time-dependent profitable pickup and delivery problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 138(C).
    28. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    29. Aziez, Imadeddine & Côté, Jean-François & Coelho, Leandro C., 2020. "Exact algorithms for the multi-pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 284(3), pages 906-919.
    30. Ulmer, Marlin W. & Thomas, Barrett W., 2020. "Meso-parametric value function approximation for dynamic customer acceptances in delivery routing," European Journal of Operational Research, Elsevier, vol. 285(1), pages 183-195.
    31. Klapp, Mathias A. & Erera, Alan L. & Toriello, Alejandro, 2020. "Request acceptance in same-day delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    32. Cattaruzza, Diego & Absi, Nabil & Feillet, Dominique & Vidal, Thibaut, 2014. "A memetic algorithm for the Multi Trip Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 833-848.
    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. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    2. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    3. Zhang, Jian & Luo, Kelin & Florio, Alexandre M. & Van Woensel, Tom, 2023. "Solving large-scale dynamic vehicle routing problems with stochastic requests," European Journal of Operational Research, Elsevier, vol. 306(2), pages 596-614.
    4. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    5. Marlin W. Ulmer & Alan Erera & Martin Savelsbergh, 2022. "Dynamic service area sizing in urban delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 763-793, September.
    6. Ritzinger, Ulrike & Puchinger, Jakob & Rudloff, Christian & Hartl, Richard F., 2022. "Comparison of anticipatory algorithms for a dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 301(2), pages 591-608.
    7. Banerjee, Dipayan & Erera, Alan L. & Stroh, Alexander M. & Toriello, Alejandro, 2023. "Who has access to e-commerce and when? Time-varying service regions in same-day delivery," Transportation Research Part B: Methodological, Elsevier, vol. 170(C), pages 148-168.
    8. Chen, Xinwei & Ulmer, Marlin W. & Thomas, Barrett W., 2022. "Deep Q-learning for same-day delivery with vehicles and drones," European Journal of Operational Research, Elsevier, vol. 298(3), pages 939-952.
    9. Klein, Vienna & Steinhardt, Claudius, 2023. "Dynamic demand management and online tour planning for same-day delivery," European Journal of Operational Research, Elsevier, vol. 307(2), pages 860-886.
    10. Chen, Xinwei & Wang, Tong & Thomas, Barrett W. & Ulmer, Marlin W., 2023. "Same-day delivery with fair customer service," European Journal of Operational Research, Elsevier, vol. 308(2), pages 738-751.
    11. Marlin W. Ulmer & Barrett W. Thomas & Ann Melissa Campbell & Nicholas Woyak, 2021. "The Restaurant Meal Delivery Problem: Dynamic Pickup and Delivery with Deadlines and Random Ready Times," Transportation Science, INFORMS, vol. 55(1), pages 75-100, 1-2.
    12. Klapp, Mathias A. & Erera, Alan L. & Toriello, Alejandro, 2018. "The Dynamic Dispatch Waves Problem for same-day delivery," European Journal of Operational Research, Elsevier, vol. 271(2), pages 519-534.
    13. He, Dongdong & Ceder, Avishai (Avi) & Zhang, Wenyi & Guan, Wei & Qi, Geqi, 2023. "Optimization of a rural bus service integrated with e-commerce deliveries guided by a new sustainable policy in China," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    14. Klapp, Mathias A. & Erera, Alan L. & Toriello, Alejandro, 2020. "Request acceptance in same-day delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    15. Aziez, Imadeddine & Côté, Jean-François & Coelho, Leandro C., 2022. "Fleet sizing and routing of healthcare automated guided vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 161(C).
    16. Nikola Mardešić & Tomislav Erdelić & Tonči Carić & Marko Đurasević, 2023. "Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment," Mathematics, MDPI, vol. 12(1), pages 1-44, December.
    17. Liu, Zeyu & Li, Xueping & Khojandi, Anahita, 2022. "The flying sidekick traveling salesman problem with stochastic travel time: A reinforcement learning approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    18. Pan, Binbin & Zhang, Zhenzhen & Lim, Andrew, 2021. "Multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 291(1), pages 218-231.
    19. Marlin W. Ulmer & Barrett W. Thomas & Dirk C. Mattfeld, 2019. "Preemptive depot returns for dynamic same-day delivery," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(4), pages 327-361, December.
    20. Ulmer, Marlin W. & Soeffker, Ninja & Mattfeld, Dirk C., 2018. "Value function approximation for dynamic multi-period vehicle routing," European Journal of Operational Research, Elsevier, vol. 269(3), pages 883-899.

    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:transe:v:177:y:2023:i:c:s1366554523002144. 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/wps/find/journaldescription.cws_home/600244/description#description .

    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.