# Efficient Large-Scale Multi-Drone Delivery Using Transit Networks

arXiv: https://arxiv.org/abs/1909.11840 · HTML: https://mlsanity.com/paper/1909.11840/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2019.

## Built on by (most cited first, 13 of 13)

- [Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance](https://mlsanity.com/paper/2105.10993/) (2021)
- [Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks](https://mlsanity.com/paper/2110.08802/) (2021)
- [Multiagent Reinforcement Learning for Autonomous Routing and Pickup Problem with Adaptation to Variable Demand](https://mlsanity.com/paper/2211.14983/) (2022)
- [Scalable Anytime Planning for Multi-Agent MDPs](https://mlsanity.com/paper/2101.04788/) (2021)
- [Leveraging Experience in Lifelong Multi-Agent Pathfinding](https://mlsanity.com/paper/2202.04382/) (2022)
- [Graph Attention Multi-Agent Fleet Autonomy for Advanced Air Mobility](https://mlsanity.com/paper/2302.07337/) (2023)
- [Dynamic Resource Management for Providing QoS in Drone Delivery Systems](https://mlsanity.com/paper/2103.04015/) (2021)
- [Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search](https://mlsanity.com/paper/2312.16106/) (2023)
- [Distributed Deep Reinforcement Learning for Intelligent Traffic Monitoring with a Team of Aerial Robots](https://mlsanity.com/paper/2107.04924/) (2021)
- [3D Radar Velocity Maps for Uncertain Dynamic Environments](https://mlsanity.com/paper/2107.11039/) (2021)
- [Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via Environment Manipulation](https://mlsanity.com/paper/2203.10540/) (2022)
- [Terraforming -- Environment Manipulation during Disruptions for Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2305.11510/) (2023)
- [UrbanHuRo: A Two-Layer Human-Robot Collaboration Framework for the Joint Optimization of Heterogeneous Urban Services](https://mlsanity.com/paper/2603.03701/) (2026)

## Abstract (arXiv)

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.