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 typically within a few seconds on commodity hardware, and that drones travel up to 360% of their flight range with public transit.
Introduction
The rapid growth of e-commerce has led to increased urban traffic congestion from delivery vehicles. Drones offer an agile alternative but are limited by battery life and carrying capacity. This paper presents a framework that enables drones to "piggyback" on public transit networks, effectively using buses and trams as a "moving sidewalk" to extend their operational reach.
Integrating flexible drone flight with fixed transit schedules creates a complex optimization problem. Managing hundreds of agents and thousands of tasks while respecting time-dependent schedules and energy constraints is NP-hard, necessitating a scalable, decoupled approach.
Methodology
The proposed framework utilizes a two-layer architecture to manage the scale and complexity of urban delivery.
Upper Layer: Task Allocation
The upper layer determines which drone delivers each package and the sequence of deliveries. The MergeSplitTours algorithm treats this as a variant of the Traveling Salesman Problem. It first groups packages and depots into tours and then splits them into individual drone paths. This approach is provably near-optimal and runs in polynomial time.
Lower Layer: Route Planning and Conflict Resolution
The lower layer executes the assigned tasks by routing drones through the transit network using Enhanced Conflict-Based Search (ECBS). A specialized low-level search, Focal-MCSP, minimizes travel time while adhering to battery limits.
Crucially, the system resolves "social" conflicts that arise when multiple drones interact with the same transit vehicle. These include boarding conflicts (simultaneous boarding) and capacity conflicts (exceeding vehicle limits).
Experimental Results
The framework was evaluated using real-world GTFS data from San Francisco (SFMTA) and Washington DC (WMATA), involving up to 200 drones and 5,000 packages.
- Range Extension: Drones achieved a range extension of 3.6x to 4.5x their standard flight range by utilizing transit.
- Scalability: Solutions for city-wide scenarios were typically computed in seconds. Even the largest cases in Washington DC were resolved in approximately two minutes.
- Efficiency: The use of surrogate travel time estimates in the allocation layer proved essential for generating feasible routes that the lower layer could successfully plan.
Conclusion
This research demonstrates a scalable solution for large-scale drone delivery by leveraging existing transit infrastructure. By decoupling task allocation from pathfinding and implementing efficient conflict resolution, the framework overcomes the range limitations of current drone technology. Future work will address transit schedule uncertainty and optimize depot placement to further enhance system performance.
Summary updated