Come fly with me: Scheduling point-to-point transports with collective drones

Drone usage for transportation tasks has inspired a vast body of operations research literature. Due to the small payloads of current-generation drones, most predecessors treat drone-based transportation in a one-to-many distribution context where a single fulfillment center distributes lightweight, small-sized goods to many customer households. Recent technological progress, however, advocates a coupling of multiple smaller drones to collective drones, cooperating in the aerial transport of bulky and heavier loads over longer distances. Collective drones, thus, open up the application of drones for point-to-point transportation services. Against this backdrop, we consider the following scheduling problem: Given a set of jobs, each representing a point-to-point transport with a given origin, destination, flight time, and weight, as well as a heterogeneous fleet of drones with varying lifting capacity, we seek a schedule, where the sum of lifting capacities of the drones assigned to each job meets the weight requirement, drones have enough time to move between subsequent jobs, and the makespan is minimum. We formulate the resulting collective drone scheduling problem, provide an in-depth analysis of computational complexity, and introduce suitable solution methods based on decomposition. Our computational study explores the performance of these solution methods and investigates managerial issues such as the impact of different drone fleet compositions.