Efficient Large-Scale Multi-Drone Delivery Using Transit Networks
This addresses efficient large-scale drone delivery for logistics companies, though it is incremental as it builds on existing multi-agent pathfinding and task allocation methods.
The paper tackles the problem of controlling a large fleet of drones for package delivery by leveraging public transit networks to conserve energy, achieving solutions within seconds for up to 200 drones and 5000 packages, with drones extending their range by up to 360% using transit.
We consider the problem of controlling a large fleet of drones to deliver packages simultaneously across broad urban areas. To conserve energy, drones hop between public transit vehicles (e.g., buses and trams). We design a comprehensive algorithmic framework that strives to minimize the maximum time to complete any delivery. We address the multifaceted complexity of the problem through a two-layer approach. First, the upper layer assigns drones to package delivery sequences with a near-optimal polynomial-time task allocation algorithm. Then, the lower layer executes the allocation by periodically routing the fleet over the transit network while employing efficient bounded-suboptimal multi-agent pathfinding techniques tailored to our setting. Experiments demonstrate the efficiency of our approach on settings with up to $200$ drones, $5000$ packages, and transit networks with up to $8000$ stops in San Francisco and Washington DC. Our results show that the framework computes solutions typically within a few seconds on commodity hardware, and that drones travel up to $360 \%$ of their flight range with public transit.