IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v339y2024i1d10.1007_s10479-023-05418-y.html
   My bibliography  Save this article

Collaborative truck multi-drone delivery system considering drone scheduling and en route operations

Author

Listed:
  • Teena Thomas

    (Indian Institute of Technology Madras
    Manipal Academy of Higher Education)

  • Sharan Srinivas

    (University of Missouri
    University of Missouri)

  • Chandrasekharan Rajendran

    (Indian Institute of Technology Madras)

Abstract

The integration of drones into the conventional truck delivery system has gained substantial attention in the business and academic communities. Most existing works restrict the launch and recovery of unmanned aerial vehicles (UAVs) to customer locations (or nodes) in the delivery network. Nevertheless, emerging technological advances can allow drones to autonomously launch/land from a moving vehicle. In addition, majority of the current literature assumes multiple UAVs to be deployed and/or recovered simultaneously, thereby ignoring the associated scheduling decisions, which are essential to ensure safe, collision-free operations. This research introduces the single truck multi-drone routing and scheduling problem with en route operations for last-mile parcel delivery. A mixed integer linear programming (MILP) model is developed to minimize the delivery completion time. In addition, a variant is introduced to minimize the total delivery cost. Since the problem under consideration is NP-hard, a relax-and-fix with re-couple-refine-and-optimize (RF-RRO) heuristic approach is proposed, where the associated decisions (truck routing and drone scheduling) are decomposed into two stages and solved sequentially. Besides, a deep learning-based clustering procedure is developed to establish an initial solution and accelerate the convergence speed of the RF-RRO heuristic. Notably, the proposed approach is extended to solve a multi-truck multi-drone variant using a deep learning-based cluster-first route-second heuristic. Our numerical results show that the proposed MILP model is able to solve problem instances with up to 20 customers optimally in a reasonable time. The proposed RF-RRO heuristic can achieve optimal (or near-optimal) solutions for small instances and is computationally efficient for large cases. Extensive experimental analysis shows 30% average savings in delivery completion time, and an average drone utilization of 62% if en route drone operations are considered. In addition, numerical results provide insights on the impact of heterogeneous drone fleet and customer density.

Suggested Citation

  • Teena Thomas & Sharan Srinivas & Chandrasekharan Rajendran, 2024. "Collaborative truck multi-drone delivery system considering drone scheduling and en route operations," Annals of Operations Research, Springer, vol. 339(1), pages 693-739, August.
    • Handle: RePEc:spr:annopr:v:339:y:2024:i:1:d:10.1007_s10479-023-05418-y
    DOI: 10.1007/s10479-023-05418-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-023-05418-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-023-05418-y?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. Mauro Dell’Amico & Roberto Montemanni & Stefano Novellani, 2020. "Matheuristic algorithms for the parallel drone scheduling traveling salesman problem," Annals of Operations Research, Springer, vol. 289(2), pages 211-226, June.
    2. Tiniç, Gizem Ozbaygin & Karasan, Oya E. & Kara, Bahar Y. & Campbell, James F. & Ozel, Aysu, 2023. "Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 81-123.
    3. 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.
    4. Chowdhury, Sudipta & Emelogu, Adindu & Marufuzzaman, Mohammad & Nurre, Sarah G. & Bian, Linkan, 2017. "Drones for disaster response and relief operations: A continuous approximation model," International Journal of Production Economics, Elsevier, vol. 188(C), pages 167-184.
    5. Taha Benarbia & Kyandoghere Kyamakya, 2021. "A Literature Review of Drone-Based Package Delivery Logistics Systems and Their Implementation Feasibility," Sustainability, MDPI, vol. 14(1), pages 1-15, December.
    6. Techane Bosona, 2020. "Urban Freight Last Mile Logistics—Challenges and Opportunities to Improve Sustainability: A Literature Review," Sustainability, MDPI, vol. 12(21), pages 1-20, October.
    7. Wang, Zheng & Sheu, Jiuh-Biing, 2019. "Vehicle routing problem with drones," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 350-364.
    8. Arshad Ali & Yuvraj Gajpal & Tarek Y. Elmekkawy, 2021. "Distributed permutation flowshop scheduling problem with total completion time objective," OPSEARCH, Springer;Operational Research Society of India, vol. 58(2), pages 425-447, June.
    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. Zhu, Waiming & Hu, Xiaoxuan & Pei, Jun & Pardalos, Panos M., 2024. "Minimizing the total travel distance for the locker-based drone delivery: A branch-and-cut-based method," Transportation Research Part B: Methodological, Elsevier, vol. 184(C).
    2. Cheng, Chun & Adulyasak, Yossiri & Rousseau, Louis-Martin, 2020. "Drone routing with energy function: Formulation and exact algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 364-387.
    3. Yang Xia & Wenjia Zeng & Xinjie Xing & Yuanzhu Zhan & Kim Hua Tan & Ajay Kumar, 2023. "Joint optimisation of drone routing and battery wear for sustainable supply chain development: a mixed-integer programming model based on blockchain-enabled fleet sharing," Annals of Operations Research, Springer, vol. 327(1), pages 89-127, August.
    4. Tiniç, Gizem Ozbaygin & Karasan, Oya E. & Kara, Bahar Y. & Campbell, James F. & Ozel, Aysu, 2023. "Exact solution approaches for the minimum total cost traveling salesman problem with multiple drones," Transportation Research Part B: Methodological, Elsevier, vol. 168(C), pages 81-123.
    5. Zhang, Guowei & Zhu, Ning & Ma, Shoufeng & Xia, Jun, 2021. "Humanitarian relief network assessment using collaborative truck-and-drone system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    6. Giuseppe Aiello & Rosalinda Inguanta & Giusj D’Angelo & Mario Venticinque, 2021. "Energy Consumption Model of Aerial Urban Logistic Infrastructures," Energies, MDPI, vol. 14(18), pages 1-19, September.
    7. Salama, Mohamed R. & Srinivas, Sharan, 2022. "Collaborative truck multi-drone routing and scheduling problem: Package delivery with flexible launch and recovery sites," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    8. 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.
    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. Pei, Zhi & Dai, Xu & Yuan, Yilun & Du, Rui & Liu, Changchun, 2021. "Managing price and fleet size for courier service with shared drones," Omega, Elsevier, vol. 104(C).
    11. Ren, Xuan & Froger, Aurélien & Jabali, Ola & Liang, Gongqian, 2024. "A competitive heuristic algorithm for vehicle routing problems with drones," European Journal of Operational Research, Elsevier, vol. 318(2), pages 469-485.
    12. Tengkuo Zhu & Stephen D. Boyles & Avinash Unnikrishnan, 2024. "Battery Electric Vehicle Traveling Salesman Problem with Drone," Networks and Spatial Economics, Springer, vol. 24(1), pages 49-97, March.
    13. Vincent F. Yu & Shih-Wei Lin & Panca Jodiawan & Yu-Chi Lai, 2023. "Solving the Flying Sidekick Traveling Salesman Problem by a Simulated Annealing Heuristic," Mathematics, MDPI, vol. 11(20), pages 1-21, October.
    14. Yu, Shaohua & Puchinger, Jakob & Sun, Shudong, 2024. "Electric van-based robot deliveries with en-route charging," European Journal of Operational Research, Elsevier, vol. 317(3), pages 806-826.
    15. Lixin Shen & Jie Sun & Dong Yang, 2024. "Research on Path Optimization for Collaborative UAVs and Mothership Monitoring of Air Pollution from Port Vessels," Sustainability, MDPI, vol. 16(12), pages 1-33, June.
    16. 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.
    17. 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).
    18. Kloster, Konstantin & Moeini, Mahdi & Vigo, Daniele & Wendt, Oliver, 2023. "The multiple traveling salesman problem in presence of drone- and robot-supported packet stations," European Journal of Operational Research, Elsevier, vol. 305(2), pages 630-643.
    19. Shi, Yong & Yang, Junhao & Han, Qian & Song, Hao & Guo, Haixiang, 2024. "Optimal decision-making of post-disaster emergency material scheduling based on helicopter–truck–drone collaboration," Omega, Elsevier, vol. 127(C).
    20. Jeong, Ho Young & Song, Byung Duk & Lee, Seokcheon, 2019. "Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones," International Journal of Production Economics, Elsevier, vol. 214(C), pages 220-233.

    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:spr:annopr:v:339:y:2024:i:1:d:10.1007_s10479-023-05418-y. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.