PaperlayerView exact revision on arXiv

Source-linked AI summary

Vehicle Routing Problems for Drone Delivery

Kevin Dorling, Jordan Heinrichs, Geoffrey G. Messier, Sebastian Magierowski

arXiv:1608.02305v1math.OC

TL;DR

Drone-delivery VRPs have not adequately represented repeated depot trips or the effects of battery and payload weight, risking excess drones or costly and infeasible routes. The paper develops two multi-trip formulations using an experimentally validated linear energy model, MILPs, and simulated annealing for practical scenarios. Results show inverse exponential cost–time and time–budget relationships and confirm the importance of drone reuse and battery-weight optimization.

  • Problem

    Existing drone-delivery VRPs may prohibit multiple depot trips or omit battery and payload effects on energy consumption, producing excess drones or costly and infeasible routes.

  • Method

    The paper derives and experimentally validates a linear multirotor energy model, formulates cost- and time-constrained multi-trip VRPs as MILPs, and applies simulated annealing to larger scenarios.

  • Results

    Inverse exponential relationships appear between cost and delivery-time limits and between overall delivery time and budgets; battery optimization improves results by over 10%, while preventing drone reuse raises costs to approximately $113,000.

  • Takeaways & Limitations

    Drone reuse and battery-weight optimization are important considerations for planning low-cost, feasible drone-delivery routes under time or budget constraints.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper develops drone-delivery routing models that combine vehicle reuse with energy consumption dependent on battery and payload weight. It introduces cost- and time-oriented formulations supported by a linearized energy model and simulated annealing for larger instances.

  • Motivation: Drone delivery can reduce package-delivery cost and time and support emergency response over hazardous terrain.Drones may avoid road infrastructure and transport supplies such as food, water, and medicine during crises.
  • Research gap: Existing drone-routing approaches often neglect limited flight range, carrying capacity, changing payload weight, or vehicle reuse.Truck-and-drone and green-VRP formulations do not fully represent drone-specific delivery constraints or repeated depot trips.
  • Contribution: The paper develops multi-trip VRPs that model energy consumption as a function of battery and payload weight while allowing drones to be reused.The resulting models seek low-cost, feasible routes by combining multi-trip routing with weight-dependent energy modeling.
  • Energy model: Experiments show that multirotor energy consumption increases approximately linearly with battery and payload weight.The paper also reports approximately equal power consumption during hovering and constant-speed flight, simplifying the routing formulations.
  • Optimization models: The linear approximation enables MILPs for two problems: minimizing cost under a delivery-time limit or minimizing overall delivery time under a budget constraint.The models optimize drone number, routes, battery weight, payload weight, and energy consumption.
  • Solution method: Because MILPs are NP-hard for large instances, the paper derives a simulated annealing heuristic for sub-optimal solutions within limited runtime.The heuristic is used to study sensitivity to delivery-time limits and budgets and to demonstrate the importance of multiple trips and battery optimization.
  • Scope: The approach generalizes single-customer-per-route strategies by allowing constraints that limit customers per route.This addresses uncertainty about whether delivery companies intend to serve more than one customer on each route.

III. MULTIROTOR HELICOPTER ENERGY CONSUMPTION

The paper derives a multirotor power model and a linear approximation linking power consumption to battery and payload weight. This approximation supports mixed integer linear programs for optimizing drone-delivery routes, fleet size, and battery and payload decisions.

  • Energy consumption model: Drone flight time depends on vehicle weight and battery energy, so the energy model relates consumption to battery and payload weight for comparing routes.The model is used to balance battery and payload weight against available flight energy.
  • Energy consumption model: The multirotor model derives hover power by distributing total frame, battery, and payload weight across n rotors.Each rotor is assigned equal shares of the copter’s total mass and the corresponding rotor disc area is used in the power calculation.
  • Linear approximation: The approximation p(m) = αm + β represents power as a linear function of battery and payload weight, with α capturing weight-dependent power and β frame-hover power.Linear constraints are needed for compatibility with mixed integer program solvers.
  • Linear approximation: For a Hexa-B hexacopter over m = 0-3 kg, regression produced α = 46.7 W/kg and β = 26.9 W, with 3.1% mean error and a 6.3 W maximum difference.The approximation closely fits the exact model under the stated hexacopter parameters and was validated experimentally.
  • Limitations: The approximation becomes less accurate over a wider 0-10 kg weight range, where mean error rises to 12.8% and the largest difference reaches about 51 W.The paper notes that larger variation in battery and payload weight can significantly reduce approximation accuracy.
  • Drone delivery formulations: The resulting MILPs optimize drone fleet size, routes, battery weight, payload weight, and energy consumption under delivery-time or budget constraints.The formulations distinguish minimum-cost and minimum-time drone delivery objectives.

A. Assumptions

The DDP formulations assume constant-speed drone flights, single-drone fulfillment at each location, precharged replacement batteries, and one depot. Their constraints encode valid routes, reuse, demand, timing, energy, capacity, and budget.

  • Flight assumptions: Drones fly between locations at a constant speed v, while weather effects such as wind and cold temperatures are ignored.The paper notes that additional measurements would be needed to understand weather effects on speed and energy consumption.
  • Demand assumptions: Each location’s demand is assumed to be fully satisfied by one drone; higher demands can be represented by colocating multiple locations, without guaranteeing the optimal split.
  • Battery assumptions: The model assumes operators purchase enough fully charged batteries before deliveries and excludes recharging costs after batteries are swapped.This reflects the stated difficulty and cost of managing multiple battery sizes between trips.
  • Depot assumptions: The formulations use a single depot and omit multiple-depot optimization, which the paper reserves for separate work.Multiple depots could extend drone range and potentially save money.
  • Routing and reuse: Route constraints ensure each non-depot location is visited once, while reusability constraints allow returned drones to begin new routes with batteries and packages.
  • Operational constraints: Demand, timing, energy, capacity, and budget constraints track payload and battery weight, route times, consumed energy, carrying limits, and total delivery cost.Battery weight qij, payload weight yij, and consumed energy zi are explicit decision variables or modeled quantities.
  • Battery optimization: Battery constraints can be extended from exact route-specific sizing to selecting among discrete battery types with specified energy, cost, and weight.

C. Mixed Integer Linear Program Formulation

The paper formulates both drone delivery problems as MILPs with shared constraints and different objectives: minimizing delivery time or total cost. Their linear structure permits use of commercial MIP solvers despite binary decisions and non-convexity.

  • Shared formulation: Both DDPs use identical decision variables and constraints, differing only in their objective functions.
  • MT-DDP: The MT-DDP minimizes overall delivery time l, defined as the time of the last package delivery.
  • MC-DDP: The MC-DDP minimizes total cost c, including drone and energy costs.
  • Solver compatibility: Although the DDPs are non-convex because of binary variables, their objectives and constraints are linear in the decision variables, making them MILPs compatible with commercial MIP solvers.
  • Runtime consideration: Because solving the MILPs to optimality can require prohibitively long runtimes, the paper proposes simulated annealing for sub-optimal solutions under limited runtimes.

V. SIMULATED ANNEALING IMPLEMENTATION

The simulated annealing implementation addresses practical drone-delivery instances where exact MILP optimization may be too slow. It represents solutions as route strings and evaluates neighboring solutions by their constrained costs.

  • Motivation: 64? Exact MILP solutions may require prohibitively long runtimes even for scenarios with few locations.
  • Heuristic objective: The heuristic uses a cost function incorporating battery cost and weight, payload weight, and multiple trips per drone.
  • Solution representation: A solution is encoded as a one-dimensional string whose depot markers separate drone routes.The representation has the form s = [0 r1 0 r2 0 . . . rR 0].
  • Search evaluation: The SA procedure compares solution costs, using the DDP-specific objective: delivery time for MT-DDP and cost for MC-DDP.

A. The DDP Cost Function

The DDP cost function evaluates route energy, drone cost, delivery time, and constraint violations for a route-string solution. It uses route timing and scheduling procedures to account for drone reuse and the available fleet.

  • Objective selection: The cost function selects delivery time as the MT-DDP objective and total cost as the MC-DDP objective.
  • Constraint penalties: The evaluation penalizes violations of capacity, budget, and delivery-time constraints by increasing cost and overall delivery time.The penalty scale K can be adjusted to represent the actual costs of violating constraints.
  • Evaluation pipeline: Algorithm 1 computes energy cost first, then drone cost and overall delivery time, using the solution vector s and objective selector Φ.
  • Battery sizing: Discrete battery choices can replace exact battery sizing; selecting the least-cost adequate combination is formulated as a minimum knapsack problem.
  • Energy costing: Algorithm 2 traverses the route string from back to front to accumulate travel time, payload-weight exposure, and route energy cost.The energy model uses travel time and payload weight, with battery weight incorporated through the battery energy calculation.
  • Route timing: Route timing records delivery and depot-arrival times for each route, then list scheduling assigns routes to drones to minimize the maximum completion time.
  • Drone assignment: Algorithm 5 uses binary search to reduce drones for MC-DDP under its delivery-time constraint, while MT-DDP uses as many drones as allowed by its budget.

B. Simulated Annealing Algorithm

The simulated annealing heuristic searches neighboring drone-delivery solutions by applying exchange rules and accepting adjustments through the Metropolis algorithm. It provides sub-optimal solutions within limited runtimes, but does not exploit several VRP-specific features.

  • Algorithm inputs: Algorithm 6 takes initial and final temperatures, a cooling factor, and a number of adjustment rounds per cooling phase.The heating phase is omitted, and the initial temperature is supplied as an input.
  • Solution evaluation: The cost procedure evaluates drone cost and overall delivery time, using scheduling to select the number of drones for cost or time objectives.For cost minimization, it searches for the best feasible drone count under the delivery-time limit; for time minimization, it purchases as many drones as the budget permits.
  • Neighbor generation: The exchange rules generate neighboring solution vectors through swaps, relocations, and 2-opt reversals of location sequences.Each rule uses two uniformly selected indices, and the resulting candidate is evaluated with the Metropolis algorithm.
  • Limitation: The approach does not use geographical information or operation-improvement frequencies, so VRP-specific heuristics may find better solutions within the same runtime.The authors nevertheless expect the reported trends to remain broadly stable because they are attributed to area size and the number of locations rather than SA-specific behavior.

VI. RESULTS

The results validate the energy model and compare MILP with simulated annealing across small and large delivery scenarios. They show that delivery cost and time respond systematically to constraints, while drone reuse and battery-weight optimization materially affect outcomes.

  • Experimental scope: The evaluation validates the energy-consumption model and analyzes MILP and SA implementations of the delivery problems.The experiments include randomly generated scenarios with 0.25 km^2 or 1 km^2 areas, 6–8 or 125–500 delivery locations, and 50 instances per scenario.
  • Observed relationships: The MC-DDP cost has an inverse exponential relationship with the delivery time limit, while MT-DDP overall delivery time has an inverse exponential relationship with the budget.The SA results also show that changing the budget or time limit changes the number of drones while energy costs remain approximately constant.
  • Practical implications: Reusing drones for multiple trips is important for reducing costs, and optimizing battery weight reduces total cost and overall delivery time.The results identify both operational reuse and battery sizing as consequential design choices in drone-delivery VRPs.
  • Scenario assumptions: The simulations assume drones cost F = $500 and have maximum carrying capacity Q = 3 kg, including battery and payload weight.The energy model uses slope α = 0.217kW/kg and y-intercept β = 0.185 kW.
  • Scenario assumptions: The delivery model assumes constant flight speed v = 6 m/s, 60 s at each location, battery energy density ξ = 650 kJ/kg, and battery cost ǫ = 0.1 $/kJ.These assumptions parameterize travel, service, and energy costs in the simulated scenarios.

A. Hexacopter Energy Consumption Measurements

Hexacopter experiments test whether maneuver type and carried weight affect power consumption. They find approximately equal average power across tested maneuvers and an approximately linear relationship between power consumption and battery plus payload weight.

  • Experimental design: Two experiments validate the energy model by testing maneuver-related power differences and weight-related power changes.The first compares hover, level flight, and altitude changes; the second varies battery and payload weight.
  • Experimental setup: The measurements use a 3D Robotics ArduCopter Hexa-B hexacopter with six motors, an Arduino flight controller, GPS, and lithium polymer batteries.Power is calculated from current and voltage readings recorded by the aircraft’s power-management system.
  • Experimental setup: The maneuver experiment measures level flight over approximately 94 m waypoint paths at about 6 m/s, stationary hover over 40 s, and controlled altitude changes.The flight path and altitude-change profiles are represented in Fig. 4.
  • Maneuver results: Average power consumption is approximately equal during hover, level flight, and altitude adjustment.Slightly lower current during level flight may reflect translational lift, while voltage differences reflect battery charge and test order.
  • Weight results: Power consumption varies approximately linearly with battery and payload weight for both 3-cell and 4-cell batteries.The 4-cell configuration grows faster with weight because the tested propellers are less efficient at its higher motor RPM.

B. Performance of MILP and SA Implementations

The MILP formulations provide optimal benchmarks, while simulated annealing produces near-optimal solutions quickly for small instances and consistent results for larger ones. Runtime and solution quality depend on cooling-rate settings and instance structure.

  • MILP and SA comparison: SA consistently finds near-optimal MT-DDP and MC-DDP solutions for instances with 8 or fewer locations.MT-DDP solutions are at most seconds from optimal, while MC-DDP solutions are at most tens of dollars away; runtimes are under one second.
  • MILP and SA comparison: MILP runtime can grow exponentially with the number of locations, whereas SA runtime remains about 0.2-0.3 seconds per scenario.For MC-DDP, runtime rises from 75.38 s to 1116.87 s when increasing from 7 to 8 locations in one tested setting.
  • Large-instance behavior: For larger scenarios, SA results are consistent, with standard deviations generally small relative to mean delivery times and costs.Standard deviations are generally seconds for multi-minute times and usually a few hundred dollars for costs in the tens of thousands.
  • Cooling-rate sensitivity: Increasing the cooling rate from 0.9 to 0.99 improves mean results by up to 15% but increases runtime by about a factor of 10.Further increasing µ from 0.99 to 0.999 yields improvements of up to 5% with additional runtime costs, motivating µ = 0.99.
  • Method limitation: Geography-aware VRP heuristics or exact methods may find lower costs and times than this SA approach by reducing infeasible long-distance routes.The current SA does not exploit geographical information or adaptively favor operations that often improve solutions.

C. Analysis of DDP Parameters

The DDP solutions show inverse exponential trade-offs between delivery constraints and outcomes: relaxing time limits lowers cost, while increasing budgets lowers overall delivery time. Customer count has a stronger effect than area size in the tested scenarios.

  • Delivery time and cost: The MC-DDP cost c has an inverse exponential relationship with the delivery time limit T.Cost changes are larger when T is low, primarily because relaxed limits enable longer routes and greater drone reuse.
  • Budget and delivery time: The MT-DDP overall delivery time l has an inverse exponential relationship with the budget B.Adding drones produces especially large time reductions when the budget is low; limited fleets otherwise require more frequent reuse.
  • Sensitivity to location count: Higher location counts make MC-DDP costs more sensitive to T and MT-DDP delivery times more sensitive to B.More locations create more routes that can be extended or drones that can be reused as constraints are relaxed.
  • Area and location sensitivity: Changing the number of locations affects time and cost more than changing the area size.Location count changes travel distance, service time, and the number of deliveries, whereas area size primarily changes travel distance.
  • Scope boundary: The reported trends may not hold for much higher area sizes or location counts if capacity, cost, or timing constraints become unavoidable.In such cases, the SA algorithm increases solution cost when constraints are violated.

D. Effect of Drone Reuse

Allowing drones to serve multiple routes substantially reduces delivery costs by enabling fleet reuse. The comparison omits an analogous MT-DDP table because feasible solutions were unavailable below a $35,000 budget.

  • Experimental comparison: The no-reuse comparison fixes the number of drones to the number of routes, whereas the reuse-enabled formulation can reuse drones across multiple trips.The altered SA implementation removes the binary search and sets n to the number of routes.
  • Reuse benefits: Drone reuse lets the MC-DDP exceed an approximately $113,000 no-reuse cost limit without violating delivery-time constraints.With reuse, costs remain in the tens of thousands of dollars in the reported comparison.
  • Cost-model caveat: Maintenance costs are excluded, although flying fewer drones may increase maintenance costs through greater per-drone flight time.The paper argues that reducing the fleet may still be less expensive because new drones are costly while worn components may be replaced relatively inexpensively.

E. Effect of Optimizing Battery Weight

The paper models battery and payload effects on multirotor energy consumption and uses that model to optimize battery weight by route. Route-specific battery sizing and even a shared optimized battery weight can materially improve cost or delivery time.

  • Route-specific optimization: Optimizing each route’s battery weight for exactly its required energy yields 13% cost improvement over a fixed 0.3 kg battery weight in the MC-DDP.
  • Route-specific optimization: Route-specific battery optimization yields about 22% delivery-time improvement over a fixed 0.25 kg battery weight in the MT-DDP.The benefit can be smaller for small areas or low numbers of nodes.
  • Shared battery optimization: Even with identical battery weights across routes, choosing 0.3 kg instead of 0.5 kg improves MC-DDP cost by 15%.
  • Shared battery optimization: Choosing 0.25 kg instead of 0.45 kg improves MT-DDP delivery time by 80% in the reported scenario.The paper identifies battery-weight optimization and drone reuse as important considerations for drone delivery.
  • Energy model: The experimentally validated energy model approximates multirotor energy consumption as increasing linearly with battery and payload weight.The model supports MILPs that optimize routes, drone counts, battery weight, payload weight, and energy consumption.
  • Heuristic scope: The SA cost function accounts for battery and payload effects and drone reuse, but the heuristic does not exploit VRP-specific geography.A VRP-tailored heuristic could use the same cost function while reducing infeasible routes.
Loading 1608.02305v1…