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

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.