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

Teena Thomas (), Sharan Srinivas () and Chandrasekharan Rajendran ()
Additional contact information
Teena Thomas: Indian Institute of Technology Madras
Sharan Srinivas: University of Missouri
Chandrasekharan Rajendran: Indian Institute of Technology Madras

Annals of Operations Research, 2024, vol. 339, issue 1, No 26, 693-739

Abstract: 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.

Keywords: Drone delivery; Last-mile logistics; Decomposition; Heuristics; En route operations; Deep learning (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-023-05418-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:339:y:2024:i:1:d:10.1007_s10479-023-05418-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-023-05418-y

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().