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

An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots

Author

Listed:
  • Chen, Cheng
  • Demir, Emrah
  • Huang, Yuan

Abstract

Considering autonomous delivery robots in urban logistics has attracted a great deal of attention in recent years. In the meantime, new technology has led to new operational challenges, such as the routing and scheduling of vehicles and delivery robots together that are currently outside the logistics service providers’ capability. In this paper, a vehicle routing problem with time windows and delivery robots (VRPTWDR) as a variant of the classical VRP is studied. The investigated problem is concerned with the routing of a set of delivery vans equipped with a number of self-driving parcel delivery robots. To tackle the VRPTWDR, an Adaptive Large Neighborhood Search heuristic algorithm is developed. Experiments show the performance and effectiveness of the algorithm for solving the VRPTWDR, and provide insights on the use of self-driving parcel delivery robots as an alternative last mile service.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:294:y:2021:i:3:p:1164-1180
    DOI: 10.1016/j.ejor.2021.02.027
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172100120X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.02.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. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    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. 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.
    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. Huber, Sandra & Geiger, Martin Josef, 2017. "Order matters – A Variable Neighborhood Search for the Swap-Body Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 263(2), pages 419-445.
    7. John Gunnar Carlsson & Siyuan Song, 2018. "Coordinated Logistics with a Truck and a Drone," Management Science, INFORMS, vol. 64(9), pages 4052-4069, September.
    8. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2012. "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 346-359.
    9. Chiang, Wen-Chyuan & Li, Yuyu & Shang, Jennifer & Urban, Timothy L., 2019. "Impact of drone delivery on sustainability and cost: Realizing the UAV potential through vehicle routing optimization," Applied Energy, Elsevier, vol. 242(C), pages 1164-1175.
    10. 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).
    11. Wang, Zheng & Sheu, Jiuh-Biing, 2019. "Vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 350-364.
    12. Roberto Baldacci & Sandra Ulrich Ngueveu & Roberto Wolfler Calvo, 2017. "The Vehicle Routing Problem with Transhipment Facilities," Transportation Science, INFORMS, vol. 51(2), pages 592-606, May.
    13. 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.
    14. Sze, Jeeu Fong & Salhi, Said & Wassan, Niaz, 2017. "The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search," Transportation Research Part B: Methodological, Elsevier, vol. 101(C), pages 162-184.
    15. Simoni, Michele D. & Kutanoglu, Erhan & Claudel, Christian G., 2020. "Optimization and analysis of a robot-assisted last mile delivery system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    16. 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.
    17. Franceschetti, Anna & Demir, Emrah & Honhon, Dorothée & Van Woensel, Tom & Laporte, Gilbert & Stobbe, Mark, 2017. "A metaheuristic for the time-dependent pollution-routing problem," European Journal of Operational Research, Elsevier, vol. 259(3), pages 972-991.
    18. Stefan Poikonen & Bruce Golden, 2020. "The Mothership and Drone Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 249-262, April.
    19. 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lin, Na & Akkerman, Renzo & Kanellopoulos, Argyris & Hu, Xiangpei & Wang, Xuping & Ruan, Junhu, 2023. "Vehicle routing with heterogeneous service types: Optimizing post-harvest preprocessing operations for fruits and vegetables in short food supply chains," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    2. 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.
    3. 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.
    4. 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.
    5. Kallestad, Jakob & Hasibi, Ramin & Hemmati, Ahmad & Sörensen, Kenneth, 2023. "A general deep reinforcement learning hyperheuristic framework for solving combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 309(1), pages 446-468.
    6. Tao Dai & Xiangqi Fan, 2021. "Multi-Stove Scheduling for Sustainable On-Demand Food Delivery," Sustainability, MDPI, vol. 13(23), pages 1-13, November.
    7. Heimfarth, Andreas & Ostermeier, Manuel & Hübner, Alexander, 2022. "A mixed truck and robot delivery approach for the daily supply of customers," European Journal of Operational Research, Elsevier, vol. 303(1), pages 401-421.
    8. 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.
    9. Wang, Mengtong & Zhang, Canrong & Bell, Michael G.H. & Miao, Lixin, 2022. "A branch-and-price algorithm for location-routing problems with pick-up stations in the last-mile distribution system," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1258-1276.
    10. 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.
    11. Zhang, Ruijuan & Dai, Ying & Yang, Fei & Ma, Zujun, 2024. "A cooperative vehicle routing problem with delivery options for simultaneous pickup and delivery services in rural areas," Socio-Economic Planning Sciences, Elsevier, vol. 93(C).
    12. Ji, Bin & Zhang, Zheng & Yu, Samson S. & Zhou, Saiqi & Wu, Guohua, 2023. "Modelling and heuristically solving many-to-many heterogeneous vehicle routing problem with cross-docking and two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1219-1235.
    13. Huang, Baobin & Tang, Lixin & Baldacci, Roberto & Wang, Gongshu & Sun, Defeng, 2023. "A metaheuristic algorithm for a locomotive routing problem arising in the steel industry," European Journal of Operational Research, Elsevier, vol. 308(1), pages 385-399.
    14. Srinivas, Sharan & Ramachandiran, Surya & Rajendran, Suchithra, 2022. "Autonomous robot-driven deliveries: A review of recent developments and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    15. 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.
    16. 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. 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.
    2. 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).
    3. 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).
    4. 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.
    5. 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.
    6. 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.
    7. Srinivas, Sharan & Ramachandiran, Surya & Rajendran, Suchithra, 2022. "Autonomous robot-driven deliveries: A review of recent developments and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    8. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    9. 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.
    10. 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.
    11. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    12. Büyüközkan, Gülçin & Ilıcak, Öykü, 2022. "Smart urban logistics: Literature review and future directions," Socio-Economic Planning Sciences, Elsevier, vol. 81(C).
    13. 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.
    14. 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.
    15. Amine Masmoudi, M. & Mancini, Simona & Baldacci, Roberto & Kuo, Yong-Hong, 2022. "Vehicle routing problems with drones equipped with multi-package payload compartments," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    16. Henriette Koch & Andreas Bortfeldt & Gerhard Wäscher, 2018. "A hybrid algorithm for the vehicle routing problem with backhauls, time windows and three-dimensional loading constraints," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1029-1075, October.
    17. 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.
    18. 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.
    19. Yin, Yunqiang & Li, Dongwei & Wang, Dujuan & Ignatius, Joshua & Cheng, T.C.E. & Wang, Sutong, 2023. "A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1125-1144.
    20. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.

    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:294:y:2021:i:3:p:1164-1180. 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.