Vehicle Routing Problems for Drone Delivery
arXiv:1608.02305 · doi:10.1109/TSMC.2016.2582745
Abstract
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.
16 pages, 10 figures, 6 tables, 6 algorithms. Accepted by IEEE Transactions on Systems, Man, and Cybernetics: Systems
Cited by in corpus (48)
- Unmanned Aerial Vehicle for Internet of Everything: Opportunities and Challenges
- Autonomous Recharging and Flight Mission Planning for Battery-operated Autonomous Drones
- Efficiency Maximization for UAV-Enabled Mobile Relaying Systems with Laser Charging
- Efficient Trajectory Planning for Multiple Non-holonomic Mobile Robots via Prioritized Trajectory Optimization
- Aerial Computing: A New Computing Paradigm, Applications, and Challenges
- Drone-assisted deliveries: new formulations for the Flying Sidekick Traveling Salesman Problem
- The UMCD Dataset
- Coverage Analysis for UAV-Assisted Cellular Networks in Rural Areas
- Resilient Composition of Drone Services for Delivery
- Optimal allocation of defibrillator drones in mountainous regions
- Vehicle Routing with Drones
- Reactive Composition of UAV Delivery Services in Urban Environments
- Reinforcement Learning-Based Deadline and Battery-Aware Offloading in Smart Farm IoT-UAV Networks
- Mission Planning and Execution in Heterogeneous Teams of Aerial Robots supporting Power Line Inspection Operations
- UAVs Path Deviation Attacks: Survey and Research Challenges
- Survey on Aerial Radio Access Networks: Toward a Comprehensive 6G Access Infrastructure
- Indoor Path Planning for an Unmanned Aerial Vehicle via Curriculum Learning
- A Variable Neighborhood Search for Flying Sidekick Traveling Salesman Problem
- A Signal Temporal Logic Motion Planner for Bird Diverter Installation Tasks with Multi-Robot Aerial Systems
- Differential Flatness-based Fast Trajectory Planning for Fixed-wing Unmanned Aerial Vehicles
- Scalable Anytime Planning for Multi-Agent MDPs
- Vision-Based Distributed Formation Control of Unmanned Aerial Vehicles
- Mobile Edge Computing via a UAV-Mounted Cloudlet: Optimization of Bit Allocation and Path Planning
- Joint Ground and Aerial Package Delivery Services: A Stochastic Optimization Approach
- Response time optimization for drone-delivered automated external defibrillators
- The Multi-objective Dynamic Traveling Salesman Problem: Last Mile Delivery with Unmanned Aerial Vehicles Assistance
- Multi-objective task allocation for electric harvesting robots: a hierarchical route reconstruction approach
- Cooperation and Fairness in Multi-Agent Reinforcement Learning
- Arduino sensor integrated drone for weather indices: a prototype for pre-flight preparation
- Indoor Path Planning for Multiple Unmanned Aerial Vehicles via Curriculum Learning
- Enhancing Multirotor Drone Efficiency: Exploring Minimum Energy Consumption Rate of Forward Flight under Varying Payload
- Nonlinear Cooperative Control of Double Drone-Bar Transportation System
- Real-time UAV Complex Missions Leveraging Self-Adaptive Controller with Elastic Structure
- Terminal-Angle-Constrained Guidance based on Sliding Mode Control for UAV Soft Landing on Ground Vehicles
- Payload-Mass-Aware Trajectory Planning on Multi-User Autonomous Unmanned Aerial Vehicles
- Locating and Platforms and Scheduling a Fleet of Drones for Emergency Delivery of Perishable Items
- Multi-trip algorithm for multi-depot rural postman problem with rechargeable vehicles
- Heterogeneous Multi-robot Task Allocation for Long-Endurance Missions in Dynamic Scenarios
- Supplier Cooperation in Drone Delivery
- A Two-Stage Approach for Routing Multiple Unmanned Aerial Vehicles with Stochastic Fuel Consumption
- Control of Multi-Layer Mobile Autonomous Systems in Adversarial Environments: A Games-in-Games Approach
- Top-k Dynamic Service Composition in Skyway Networks
- Hundred Drones Land in a Minute
- Drone flight data reveal energy and greenhouse gas emissions savings for small package delivery
- WAND: Learning Robust Navigation under Complex Wind Disturbances and Dense Obstacles for Quadrotors
- Robust 3D Distributed Formation Control with Application to Quadrotors
- Exact and Heuristic Approaches to Drone Delivery Problems
- Optimal UAV Hitching on Ground Vehicles