# Vehicle Routing Problems for Drone Delivery

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Aug 2016.

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

- [Multi-Agent Coordination across Diverse Applications: A Survey](https://mlsanity.com/paper/2502.14743/) (2025)
- [Scalable Multi-Agent Reinforcement Learning through Intelligent Information Aggregation](https://mlsanity.com/paper/2211.02127/) (2022)
- [An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem](https://mlsanity.com/paper/2107.07076/) (2021)
- [A Taxonomy of Hierarchical Multi-Agent Systems: Design Patterns, Coordination Mechanisms, and Industrial Applications](https://mlsanity.com/paper/2508.12683/) (2025)
- [LLM-DaaS: LLM-driven Drone-as-a-Service Operations from Text User Requests](https://mlsanity.com/paper/2412.11672/) (2024)
- [Scalable Anytime Planning for Multi-Agent MDPs](https://mlsanity.com/paper/2101.04788/) (2021)
- [Cooperation and Fairness in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.14916/) (2024)
- [Drone-as-a-Service Composition Under Uncertainty](https://mlsanity.com/paper/2103.06513/) (2021)
- [Hallucination-Aware Generative Pretrained Transformer for Cooperative Aerial Mobility Control](https://mlsanity.com/paper/2504.10831/) (2025)
- [Dynamic Resource Management for Providing QoS in Drone Delivery Systems](https://mlsanity.com/paper/2103.04015/) (2021)
- [Data-Efficient Modeling for Precise Power Consumption Estimation of Quadrotor Operations Using Ensemble Learning](https://mlsanity.com/paper/2205.10997/) (2022)
- [A Comparative Study on Energy Consumption Models for Drones](https://mlsanity.com/paper/2206.01609/) (2022)
- [Precise Payload Delivery via Unmanned Aerial Vehicles: An Approach Using Object Detection Algorithms](https://mlsanity.com/paper/2310.06329/) (2023)
- [SmartPathfinder: Pushing the Limits of Heuristic Solutions for Vehicle Routing Problem with Drones Using Reinforcement Learning](https://mlsanity.com/paper/2404.13068/) (2024)
- [SkyRover: A Modular Simulator for Cross-Domain Pathfinding](https://mlsanity.com/paper/2502.08969/) (2025)
- [An End-to-End Learning Approach for Solving Capacitated Location-Routing Problems](https://mlsanity.com/paper/2511.02525/) (2025)
- [Exact and Heuristic Approaches to Drone Delivery Problems](https://mlsanity.com/paper/2108.01996/) (2021)
- [Bridging the Urban-Rural Connectivity Gap through Intelligent Space, Air, and Ground Networks](https://mlsanity.com/paper/2202.12683/) (2022)
- [Decision-making of Emergent Incident based on P-MADDPG](https://mlsanity.com/paper/2203.12673/) (2022)
- [Deep Reinforcement Learning for Online Routing of Unmanned Aerial Vehicles with Wireless Power Transfer](https://mlsanity.com/paper/2204.11477/) (2022)
- [Towards Autonomous and Safe Last-mile Deliveries with AI-augmented Self-driving Delivery Robots](https://mlsanity.com/paper/2305.17705/) (2023)
- [Dependency Structure Search Bayesian Optimization for Decision Making Models](https://mlsanity.com/paper/2308.00629/) (2023)
- [Coordinated Multi-Drone Last-mile Delivery: Learning Strategies for Energy-aware and Timely Operations](https://mlsanity.com/paper/2509.15830/) (2025)
- [ED3R: Energy-Aware Distributed Disaster Detection via Cooperative Agents in Robotic Systems](https://mlsanity.com/paper/2606.17739/) (2026)

## Abstract (arXiv)

Unmanned aerial vehicles, or drones, have the potential to significantly reduce the cost and time of making last-mile deliveries and responding to emergencies. Despite this potential, little work has gone into developing vehicle routing problems (VRPs) specifically for drone delivery scenarios. Existing VRPs are insufficient for planning drone deliveries: either multiple trips to the depot are not permitted, leading to solutions with excess drones, or the effect of battery and payload weight on energy consumption is not considered, leading to costly or infeasible routes. We propose two multi-trip VRPs for drone delivery that address both issues. One minimizes costs subject to a delivery time limit, while the other minimizes the overall delivery time subject to a budget constraint. We mathematically derive and experimentally validate an energy consumption model for multirotor drones, demonstrating that energy consumption varies approximately linearly with payload and battery weight. We use this approximation to derive mixed integer linear programs for our VRPs. We propose a cost function that considers our energy consumption model and drone reuse, and apply it in a simulated annealing (SA) heuristic for finding sub-optimal solutions to practical scenarios. To assist drone delivery practitioners with balancing cost and delivery time, the SA heuristic is used to show that the minimum cost has an inverse exponential relationship with the delivery time limit, and the minimum overall delivery time has an inverse exponential relationship with the budget. Numerical results confirm the importance of reusing drones and optimizing battery size in drone delivery VRPs.