Efficient Large-Scale Multi-Drone Delivery Using Transit Networks

Shushman Choudhury, Kiril Solovey, Mykel J. Kochenderfer, Marco Pavone

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.

Overview of the drone-transit delivery system, showing depots, transit rides, and transfers.

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).

Illustration of boarding and capacity conflict resolution within the transit network.

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

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.
BibTeX
@article{choudhury2020efficient,
  author = {Shushman Choudhury and Kiril Solovey and Mykel J. Kochenderfer and Marco Pavone},
  title = {{Efficient Large-Scale Multi-Drone Delivery Using Transit Networks}},
  journal = {J. Artif. Intell. Res.},
  year = {2020},
  doi = {10.1109/icra40945.2020.9197313},
}
Figure