Abstract
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 within a few seconds (up to 2 minutes at most) on commodity hardware, and that drones travel up to 450% of their flight range with public transit.
Introduction
While drones offer a promising solution for "last-mile" delivery, they suffer from two major bottlenecks: limited flight range and low carrying capacity. Previous research has explored drone-truck tandems, but these solutions often fail to scale in dense urban environments or for large fleets.
This research addresses the "Multi-Drone Delivery using Transit Networks" problem, where drones "hitchhike" on public transit vehicles like buses and trams to overcome battery limitations. This creates a complex coordination challenge involving task allocation (which drone delivers what), pathfinding through time-dependent transit schedules, and conflict resolution (managing bus capacity and avoiding collisions).
System Architecture
To maintain computational tractability at scale, the authors propose a two-layer hierarchical framework that decouples the high-level assignment from the low-level routing.
Upper Layer: Delivery Sequence Allocation
The upper layer utilizes the MergeSplitTours algorithm. It first solves a "Minimal Connecting Tours" (MCT) problem to link packages to depots, then merges these into a single tour which is split into individual paths for each drone. To account for transit availability without exhaustive searching, this layer uses a surrogate cost estimate based on precomputed travel times between Voronoi regions of the city.
Lower Layer: Multi-Agent Path Finding (MAPF-TN)
The lower layer executes the assigned tasks by planning specific routes. The authors adapted Enhanced Conflict-Based Search (ECBS) for transit networks. Key innovations include:
- Focal-MCSP: A search routine handling battery/flight distance constraints alongside time.
- Trip Metagraph: A precomputed graph where nodes represent entire bus trips, allowing the heuristic to identify transit shortcuts quickly.
- Capacity Constraints: The solver explicitly ensures drones do not exceed the physical carrying capacity of any transit vehicle.
Experimental Evaluation
The framework was tested using real-world GTFS transit data from San Francisco (SFMTA, ~4,200 stops) and Washington DC (WMATA, ~7,600 stops). Simulations involved up to 200 drones and 5,000 packages.
Key Results
- Range Extension: Drones reached destinations up to 450% further than their standalone flight range by utilizing transit.
- Scalability: The system handled 5,000 packages in roughly 18 minutes, while real-time routing for 200 drones took less than 10 seconds.
- Efficiency: The "Replan-1" strategy—replanning only for the drone that just finished a task—proved nearly as effective as full-fleet replanning but with significantly lower computational overhead.
Discussion and Future Work
Public transit acts as a "mobile energy-saving platform," allowing drones to bypass the energy density limits of current batteries. By decoupling task allocation from pathfinding, the framework avoids the "curse of dimensionality" typical in multi-agent routing.
However, several areas for future improvement remain. The current model assumes deterministic transit schedules, whereas real-world delays would require stochastic modeling. Additionally, the current battery model is abstracted, and the system operates on batch requests rather than a continuous stream. Future work will also need to address the social and environmental impacts, such as noise pollution, of large-scale urban drone operations.
Summary updated