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

Van-based robot hybrid pickup and delivery routing problem

Author

Listed:
  • Yu, Shaohua
  • Puchinger, Jakob
  • Sun, Shudong

Abstract

We present a two-echelon van-based robot last-mile pickup and delivery system in urban settings. Robots can visit areas with van access restrictions, such as pedestrianized areas or university campuses. The van stops at parking nodes to drop off and/or pick up its robot, and to replenish its robot and/or swap its robot’s battery if needed. Five van/robot pickup and delivery cases are considered, according to the roles the van/robot plays in the process of pickup/delivery and whether the van transports its robot.

Suggested Citation

  • Yu, Shaohua & Puchinger, Jakob & Sun, Shudong, 2022. "Van-based robot hybrid pickup and delivery routing problem," European Journal of Operational Research, Elsevier, vol. 298(3), pages 894-914.
    • Handle: RePEc:eee:ejores:v:298:y:2022:i:3:p:894-914
    DOI: 10.1016/j.ejor.2021.06.009
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721005154
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.06.009?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. Dumas, Yvan & Desrosiers, Jacques & Soumis, Francois, 1991. "The pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 54(1), pages 7-22, September.
    2. Boysen, Nils & Schwerdfeger, Stefan & Weidinger, Felix, 2018. "Scheduling last-mile deliveries with truck-based autonomous robots," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1085-1099.
    3. Yu, Shaohua & Puchinger, Jakob & Sun, Shudong, 2020. "Two-echelon urban deliveries using autonomous vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    4. Michael Drexl, 2012. "Synchronization in Vehicle Routing---A Survey of VRPs with Multiple Synchronization Constraints," Transportation Science, INFORMS, vol. 46(3), pages 297-316, August.
    5. 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.
    6. John Gunnar Carlsson & Siyuan Song, 2018. "Coordinated Logistics with a Truck and a Drone," Management Science, INFORMS, vol. 64(9), pages 4052-4069, September.
    7. Moshref-Javadi, Mohammad & Lee, Seokcheon & Winkenbach, Matthias, 2020. "Design and evaluation of a multi-trip delivery model with truck and drones," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    8. Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2020. "Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 26-62.
    9. Seyed Mostafa Mirhedayatian & Teodor Gabriel Crainic & Mario Guajardo & Stein W. Wallace, 2021. "A two-echelon location-routing problem with synchronisation," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 72(1), pages 145-160, January.
    10. 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.
    11. Boysen, Nils & Schwerdfeger, Stefan & Weidinger, Felix, 2018. "Scheduling last-mile deliveries with truck-based autonomous robots," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 126189, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    12. Stefan Poikonen & Bruce Golden & Edward A. Wasil, 2019. "A Branch-and-Bound Approach to the Traveling Salesman Problem with a Drone," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 335-346, April.
    13. Wang, Zheng & Sheu, Jiuh-Biing, 2019. "Vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 350-364.
    14. Anderluh, Alexandra & Nolz, Pamela C. & Hemmelmayr, Vera C. & Crainic, Teodor Gabriel, 2021. "Multi-objective optimization of a two-echelon vehicle routing problem with vehicle synchronization and ‘grey zone’ customers arising in urban logistics," European Journal of Operational Research, Elsevier, vol. 289(3), pages 940-958.
    15. 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.
    16. David Pisinger & Stefan Ropke, 2019. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, edition 3, chapter 0, pages 99-127, Springer.
    17. Kitjacharoenchai, Patchara & Min, Byung-Cheol & Lee, Seokcheon, 2020. "Two echelon vehicle routing problem with drones in last mile delivery," International Journal of Production Economics, Elsevier, vol. 225(C).
    18. Perboli, Guido & Brotcorne, Luce & Bruni, Maria Elena & Rosano, Mariangela, 2021. "A new model for Last-Mile Delivery and Satellite Depots management: The impact of the on-demand economy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    19. Iman Dayarian & Martin Savelsbergh & John-Paul Clarke, 2020. "Same-Day Delivery with Drone Resupply," Transportation Science, INFORMS, vol. 54(1), pages 229-249, January.
    20. Liu, Tian & Luo, Zhixing & Qin, Hu & Lim, Andrew, 2018. "A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints," European Journal of Operational Research, Elsevier, vol. 266(2), pages 487-497.
    21. Nico Dellaert & Fardin Dashty Saridarq & Tom Van Woensel & Teodor Gabriel Crainic, 2019. "Branch-and-Price–Based Algorithms for the Two-Echelon Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 53(2), pages 463-479, March.
    22. Roberto Roberti & Mario Ruthmair, 2021. "Exact Methods for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 55(2), pages 315-335, March.
    23. Jie, Wanchen & Yang, Jun & Zhang, Min & Huang, Yongxi, 2019. "The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology," European Journal of Operational Research, Elsevier, vol. 272(3), pages 879-904.
    24. Darvish, Maryam & Archetti, Claudia & Coelho, Leandro C. & Speranza, M. Grazia, 2019. "Flexible two-echelon location routing problem," European Journal of Operational Research, Elsevier, vol. 277(3), pages 1124-1136.
    25. Niels Agatz & Paul Bouman & Marie Schmidt, 2018. "Optimization Approaches for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 52(4), pages 965-981, August.
    26. Guido Perboli & Roberto Tadei & Daniele Vigo, 2011. "The Two-Echelon Capacitated Vehicle Routing Problem: Models and Math-Based Heuristics," Transportation Science, INFORMS, vol. 45(3), pages 364-380, August.
    27. Sun, Wei & Yu, Yang & Wang, Junwei, 2019. "Heterogeneous vehicle pickup and delivery problems: Formulation and exact solution," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 181-202.
    28. Mühlbauer, Ferdinand & Fontaine, Pirmin, 2021. "A parallelised large neighbourhood search heuristic for the asymmetric two-echelon vehicle routing problem with swap containers for cargo-bicycles," European Journal of Operational Research, Elsevier, vol. 289(2), pages 742-757.
    29. Chen, Cheng & Demir, Emrah & Huang, Yuan, 2021. "An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1164-1180.
    30. Stefan Poikonen & Bruce Golden, 2020. "The Mothership and Drone Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 249-262, April.
    31. M. W. P. Savelsbergh & M. Sol, 1995. "The General Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 29(1), pages 17-29, 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. 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.
    2. 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.
    3. Mengyuan Gou & Haiyan Yu, 2023. "Online Delivery Problem for Hybrid Truck–Drone System with Independent and Truck-Carried Drones," Sustainability, MDPI, vol. 15(2), pages 1-15, January.
    4. Yang, Tiannuo & Chu, Zhongzhu & Wang, Bailin, 2023. "Feasibility on the integration of passenger and freight transportation in rural areas: A service mode and an optimization model," Socio-Economic Planning Sciences, Elsevier, vol. 88(C).
    5. Meng, Shanshan & Chen, Yanru & Li, Dong, 2024. "The multi-visit drone-assisted pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 314(2), pages 685-702.
    6. Arslan, A.M. & Agatz, N.A.H. & Srour, F.J., 2023. "Model Formulations for Pickup and Delivery Problems in Designated Driver Services," ERIM Report Series Research in Management ERS-2023-004-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    7. Themistoklis Stamadianos & Nikolaos A. Kyriakakis & Magdalene Marinaki & Yannis Marinakis, 2023. "Routing Problems with Electric and Autonomous Vehicles: Review and Potential for Future Research," SN Operations Research Forum, Springer, vol. 4(2), pages 1-34, June.

    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. 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.
    2. Sluijk, Natasja & Florio, Alexandre M. & Kinable, Joris & Dellaert, Nico & Van Woensel, Tom, 2023. "Two-echelon vehicle routing problems: A literature review," European Journal of Operational Research, Elsevier, vol. 304(3), pages 865-886.
    3. 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.
    4. Jiang, Jie & Dai, Ying & Yang, Fei & Ma, Zujun, 2024. "A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services," European Journal of Operational Research, Elsevier, vol. 312(1), pages 125-137.
    5. Zhao, Lei & Bi, Xinhua & Li, Gendao & Dong, Zhaohui & Xiao, Ni & Zhao, Anni, 2022. "Robust traveling salesman problem with multiple drones: Parcel delivery under uncertain navigation environments," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    6. Madani, Batool & Ndiaye, Malick & Salhi, Said, 2024. "Hybrid truck-drone delivery system with multi-visits and multi-launch and retrieval locations: Mathematical model and adaptive variable neighborhood search with neighborhood categorization," European Journal of Operational Research, Elsevier, vol. 316(1), pages 100-125.
    7. Chen, Cheng & Demir, Emrah & Huang, Yuan, 2021. "An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots," European Journal of Operational Research, Elsevier, vol. 294(3), pages 1164-1180.
    8. Rave, Alexander & Fontaine, Pirmin & Kuhn, Heinrich, 2023. "Drone location and vehicle fleet planning with trucks and aerial drones," European Journal of Operational Research, Elsevier, vol. 308(1), pages 113-130.
    9. 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.
    10. Soares, Ricardo & Marques, Alexandra & Amorim, Pedro & Parragh, Sophie N., 2024. "Synchronisation in vehicle routing: Classification schema, modelling framework and literature review," European Journal of Operational Research, Elsevier, vol. 313(3), pages 817-840.
    11. Li, Hongqi & Wang, Haotian & Chen, Jun & Bai, Ming, 2020. "Two-echelon vehicle routing problem with time windows and mobile satellites," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 179-201.
    12. Chen, Cheng & Demir, Emrah & Huang, Yuan & Qiu, Rongzu, 2021. "The adoption of self-driving delivery robots in last mile logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 146(C).
    13. Themistoklis Stamadianos & Nikolaos A. Kyriakakis & Magdalene Marinaki & Yannis Marinakis, 2023. "Routing Problems with Electric and Autonomous Vehicles: Review and Potential for Future Research," SN Operations Research Forum, Springer, vol. 4(2), pages 1-34, June.
    14. 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).
    15. 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).
    16. 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.
    17. Meng, Shanshan & Guo, Xiuping & Li, Dong & Liu, Guoquan, 2023. "The multi-visit drone routing problem for pickup and delivery services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 169(C).
    18. Nguyen, Minh Anh & Dang, Giang Thi-Huong & Hà, Minh Hoàng & Pham, Minh-Trien, 2022. "The min-cost parallel drone scheduling vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 299(3), pages 910-930.
    19. 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).
    20. Peng, Xiaoshuai & Zhang, Lele & Thompson, Russell G. & Wang, Kangzhou, 2023. "A three-phase heuristic for last-mile delivery with spatial-temporal consolidation and delivery options," International Journal of Production Economics, Elsevier, vol. 266(C).

    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:298:y:2022:i:3:p:894-914. 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.