The Parallel Drone Scheduling Traveling Salesman Problem with Collective Drones

In this paper, we study a new variant of the parallel drone scheduling traveling salesman problem that aims to increase the utilization of drones, particularly for heavy item deliveries. The system under consideration adopts a technology that combines multiple drones to form a collective drone (c-drone) capable of transporting heavier items. The innovative concept is expected to add further flexibility in vehicle assignment decisions. An especially difficult challenge to address is the collaboration among drones because it requires temporal synchronization between their delivery tours. To better model the reality, we also consider that drone power consumption is a nonlinear function of both speed and parcel weight. We first develop a two-index mixed integer linear programming (MILP) formulation from which a simple branch and cut is developed to solve small-size instances to optimality. To efficiently handle larger problem instances, we propose a ruin-and-recreate metaheuristic with problem-tailored removal and insertion operators, in which an efficient move evaluation procedure based on the topological sort is designed to deal with the complexity of the synchronization constraints. Computational experiments demonstrate the validity of the developed MILP model and the performance of the proposed metaheuristic. Sensitivity analyses based on the classification and regression tree are performed to investigate the benefits of using c-drones and the important factors affecting the efficiency of the new transportation system.