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

An exact method for a last-mile delivery routing problem with multiple deliverymen

Author

Listed:
  • Senna, Fernando
  • Coelho, Leandro C.
  • Morabito, Reinaldo
  • Munari, Pedro

Abstract

The demand for efficient last-mile delivery systems in large cities creates an opportunity to develop innovative logistics schemes. In this paper, we study a problem in which each vehicle may travel with more than one deliveryman to serve multiple customers with a single stop of the vehicle, increasing the delivery efficiency. We extend the vehicle routing problem with time windows and multiple deliverymen by explicitly considering the deliveryman routes. We introduce the problem, formally define it with a formulation, propose valid inequalities, and develop a tailored branch-and-Benders-cut (BBC) algorithm to solve it. The BBC is capable of solving 89% of the instances to proven optimality in reasonable times, many of them of realistic sizes. Additionally, we show the benefits of evaluating the deliveryman routes considering a cost minimization perspective, and discuss relevant solutions for urban logistics problems that can help decrease congestion and emissions.

Suggested Citation

  • Senna, Fernando & Coelho, Leandro C. & Morabito, Reinaldo & Munari, Pedro, 2024. "An exact method for a last-mile delivery routing problem with multiple deliverymen," European Journal of Operational Research, Elsevier, vol. 317(2), pages 550-562.
    • Handle: RePEc:eee:ejores:v:317:y:2024:i:2:p:550-562
    DOI: 10.1016/j.ejor.2024.04.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724002662
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.04.007?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. Bayliss, Christopher & Bektaş, Tolga & Tjon-Soei-Len, Vernon & Rohner, Remo, 2023. "Designing a multi-modal and variable-echelon delivery system for last-mile logistics," European Journal of Operational Research, Elsevier, vol. 307(2), pages 645-662.
    2. Antonio Martinez-Sykora & Fraser McLeod & Carlos Lamas-Fernandez & Tolga Bektaş & Tom Cherrett & Julian Allen, 2020. "Optimised solutions to the last-mile delivery problem in London using a combination of walking and driving," Annals of Operations Research, Springer, vol. 295(2), pages 645-693, December.
    3. Moreno, Alfredo & Munari, Pedro & Alem, Douglas, 2019. "A branch-and-Benders-cut algorithm for the Crew Scheduling and Routing Problem in road restoration," European Journal of Operational Research, Elsevier, vol. 275(1), pages 16-34.
    4. Reed, Sara & Campbell, Ann Melissa & Thomas, Barrett W., 2024. "Does parking matter? The impact of parking time on last-mile delivery optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 181(C).
    5. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    6. Nils Boysen & Stefan Fedtke & Stefan Schwerdfeger, 2021. "Last-mile delivery concepts: a survey from an operational research perspective," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 1-58, March.
    7. Ostermeier, Manuel & Heimfarth, Andreas & Hübner, Alexander, 2023. "The multi-vehicle truck-and-robot routing problem for last-mile delivery," European Journal of Operational Research, Elsevier, vol. 310(2), pages 680-697.
    8. Ouyang, Zhiyuan & Leung, Eric K.H. & Huang, George Q., 2023. "Community logistics and dynamic community partitioning: A new approach for solving e-commerce last mile delivery," European Journal of Operational Research, Elsevier, vol. 307(1), pages 140-156.
    9. Le Colleter, Théo & Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2023. "Small and large neighborhood search for the park-and-loop routing problem with parking selection," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1233-1248.
    10. Li, Hongqi & Chen, Jun & Wang, Feilong & Bai, Ming, 2021. "Ground-vehicle and unmanned-aerial-vehicle routing problems from two-echelon scheme perspective: A review," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1078-1095.
    11. Pedro Munari & Reinaldo Morabito, 2018. "A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(3), pages 437-464, October.
    12. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    13. Alfandari, Laurent & Ljubić, Ivana & De Melo da Silva, Marcos, 2022. "A tailored Benders decomposition approach for last-mile delivery with autonomous robots," European Journal of Operational Research, Elsevier, vol. 299(2), pages 510-525.
    14. Gerald Senarclens de Grancy & Marc Reimann, 2015. "Evaluating two new heuristics for constructing customer clusters in a VRPTW with multiple service workers," 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. 23(2), pages 479-500, June.
    15. 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.
    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. Le Colleter, Théo & Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2023. "Small and large neighborhood search for the park-and-loop routing problem with parking selection," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1233-1248.
    2. Zang, Xiaoning & Jiang, Li & Liang, Changyong & Fang, Xiang, 2023. "Coordinated home and locker deliveries: An exact approach for the urban delivery problem with conflicting time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    3. Reed, Sara & Campbell, Ann Melissa & Thomas, Barrett W., 2024. "Does parking matter? The impact of parking time on last-mile delivery optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 181(C).
    4. Ostermeier, Manuel & Heimfarth, Andreas & Hübner, Alexander, 2023. "The multi-vehicle truck-and-robot routing problem for last-mile delivery," European Journal of Operational Research, Elsevier, vol. 310(2), pages 680-697.
    5. Gómez-Marín, Cristian Giovanny & Comi, Antonio & Serna-Urán, Conrado Augusto & Zapata-Cortés, Julián Andrés, 2024. "Fostering collaboration and coordination in urban delivery: a multi-agent microsimulation model," Research in Transportation Economics, Elsevier, vol. 103(C).
    6. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2016. "The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm," European Journal of Operational Research, Elsevier, vol. 248(1), pages 33-51.
    7. Christian Brandstätter, 2021. "A metaheuristic algorithm and structured analysis for the Line-haul Feeder Vehicle Routing Problem with Time Windows," 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. 29(1), pages 247-289, March.
    8. Neves-Moreira, Fábio & Almada-Lobo, Bernardo & Guimarães, Luís & Amorim, Pedro, 2022. "The multi-product inventory-routing problem with pickups and deliveries: Mitigating fluctuating demand via rolling horizon heuristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    9. Li, Hongqi & Wang, Feilong & Zhan, Zhuopeng, 2024. "Drone routing problem with swarm synchronization," European Journal of Operational Research, Elsevier, vol. 314(2), pages 477-495.
    10. Zhou, Hang & Qin, Hu & Cheng, Chun & Rousseau, Louis-Martin, 2023. "An exact algorithm for the two-echelon vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 124-150.
    11. Bock, Stefan, 2024. "Vehicle routing for connected service areas - a versatile approach covering single, hierarchical, and bi-criteria objectives," European Journal of Operational Research, Elsevier, vol. 313(3), pages 905-925.
    12. Yi Li & Min Liu & Dandan Jiang, 2022. "Application of Unmanned Aerial Vehicles in Logistics: A Literature Review," Sustainability, MDPI, vol. 14(21), pages 1-18, November.
    13. Jonathan De La Vega & Pedro Munari & Reinaldo Morabito, 2019. "Robust optimization for the vehicle routing problem with multiple deliverymen," 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. 27(4), pages 905-936, December.
    14. Fragkogios, Antonios & Qiu, Yuzhuo & Saharidis, Georgios K.D. & Pardalos, Panos M., 2024. "An accelerated benders decomposition algorithm for the solution of the multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 317(2), pages 500-514.
    15. Giménez-Palacios, Iván & Parreño, Francisco & Álvarez-Valdés, Ramón & Paquay, Célia & Oliveira, Beatriz Brito & Carravilla, Maria Antónia & Oliveira, José Fernando, 2022. "First-mile logistics parcel pickup: Vehicle routing with packing constraints under disruption," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    16. Zhang, Qihuan & Wang, Ziteng & Huang, Min & Yu, Yang & Fang, Shu-Cherng, 2022. "Heterogeneous multi-depot collaborative vehicle routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 160(C), pages 1-20.
    17. Liu, Dan & Kaisar, Evangelos I. & Yang, Yang & Yan, Pengyu, 2022. "Physical Internet-enabled E-grocery delivery Network:A load-dependent two-echelon vehicle routing problem with mixed vehicles," International Journal of Production Economics, Elsevier, vol. 254(C).
    18. Muriel, Juan E. & Zhang, Lele & Fransoo, Jan C. & Villegas, Juan G., 2024. "A reinforcement learning framework for improving parking decisions in last-mile delivery," Other publications TiSEM b3811dad-50fa-486b-8255-3, Tilburg University, School of Economics and Management.
    19. 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.
    20. 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.

    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:317:y:2024:i:2:p:550-562. 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.