An Exact Algorithm for Load-Dependent Traveling Salesman Problem for Unmanned Aerial Vehicle Package Delivery

David W. Casbeer; Deepak Prakash Kumar; Saurabh Belgaonkar; Sivakumar Rathinam; Swaroop Darbha

arxiv: 2605.05507 · v1 · submitted 2026-05-06 · 🧮 math.OC

An Exact Algorithm for Load-Dependent Traveling Salesman Problem for Unmanned Aerial Vehicle Package Delivery

Deepak Prakash Kumar , Saurabh Belgaonkar , Sivakumar Rathinam , Swaroop Darbha , David W. Casbeer This is my paper

Pith reviewed 2026-05-08 15:50 UTC · model grok-4.3

classification 🧮 math.OC

keywords load-dependent traveling salesman problemUAV package deliverymixed-integer linear programmingenergy dissipation modelexact algorithmvehicle routingoptimization

0 comments

The pith

A linear energy model allows exact optimization of load-dependent routes for UAV package deliveries.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper addresses the traveling salesman problem for unmanned aerial vehicles delivering packages, where the energy cost depends on the changing load as packages are dropped. It establishes an energy dissipation model that proves energy use increases linearly with both the vehicle's mass and the distance traveled. This linearity transforms the original mixed-integer nonlinear program into a solvable mixed-integer linear program through a novel relaxation. Numerical tests show that optimal solutions are found quickly for most instances involving up to 50 delivery targets, with small gaps for the rest. This approach outperforms several baseline methods and is relevant for planning efficient drone operations where energy constraints matter.

Core claim

The central discovery is an energy dissipation model proving that energy expenditure depends linearly on vehicle mass and distance traveled. Building on this, the authors formulate the load-dependent traveling salesman problem as a mixed-integer nonlinear program and relax it to a mixed-integer linear program that yields optimal routes for UAV deliveries.

What carries the argument

The energy dissipation model establishing linear dependence of energy on mass and distance, enabling the MILP relaxation of the load-dependent TSP.

If this is right

Optimal delivery sequences accounting for load changes can be computed in under a minute for up to 50 targets.
The MILP formulation provides solutions with optimality gaps below 13 percent even for harder instances within 10 minutes.
The approach outperforms three baseline formulations and another algorithm from related problems.
Routes can be planned that minimize total energy while respecting the sequence of deliveries.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the linear energy model holds in real flights, it could extend to other variable-load routing problems like ground vehicles with fuel consumption.
The relaxation's tightness suggests it may scale to larger instances with further improvements in solvers.
Integrating this with wind models or battery dynamics could provide more robust plans for actual operations.
Similar techniques might apply to urban air mobility scenarios with multiple cargo drops.

Load-bearing premise

The energy dissipation model assumes linear dependence on mass and distance under idealized conditions without external factors like wind affecting the results.

What would settle it

Comparing the model's predicted energy consumption against actual measurements from a UAV flight test with varying loads would confirm or refute the linearity assumption.

Figures

Figures reproduced from arXiv: 2605.05507 by David W. Casbeer, Deepak Prakash Kumar, Saurabh Belgaonkar, Sivakumar Rathinam, Swaroop Darbha.

**Figure 1.** Figure 1: Example tour depicting dropping off packages and the mass of the view at source ↗

**Figure 2.** Figure 2: Depiction of relation between Mi and Mj Note that (11) also eliminates subtours, as it resembles the Miller-Tucker-Zemlin subtour elimination constraints for TSP [10]. Finally, the decision variables and their bounds are: xij ∈ {0, 1}, ∀(i, j) ∈ E, Mi ∈ view at source ↗

**Figure 3.** Figure 3: Depiction of ηij and ζjk to derive their relationship Additionally, noting that the mass of the vehicle on each edge (Mi) can be bounded by 0 ≤ Mi − M ≤ M, (18) and noting that 0 ≤ xij ≤ 1, ∀(i, j) ∈ E, (19) the following inequalities can be obtained for every (i, j) ∈ E: (Mi − M) xij ≥ 0, (20) view at source ↗

**Figure 4.** Figure 4: Summary of optimality gap and computation time for an unladen view at source ↗

**Figure 5.** Figure 5: Computation time with varying unladen mass factor view at source ↗

**Figure 6.** Figure 6: Effect on unladen mass ratio on optimal path for instance MM1 view at source ↗

**Figure 8.** Figure 8: Percentage difference between LKH solution and optimal solution/best ilib view at source ↗

**Figure 7.** Figure 7: Optimal solution vs optimal TSP solution for ulysses22 with view at source ↗

**Figure 9.** Figure 9: Model of cargo drone Let I, J denote the unit vectors along X (east) and Y (north) directions of a ground Cartesian frame. Let i, j be unit vectors along the longitudinal and lateral directions of the drone. Let the coordinate pair (x, y) denote the location of the drone in the ground Cartesian frame and θ be its heading angle (relative to the wind). One may express the kinematic equations as given in (3).… view at source ↗

read the original abstract

In this article, we present a novel formulation for the load-dependent traveling salesman problem (LD-TSP), in which travel cost (or energy expended) depends on the vehicle's current load. This problem is relevant for package delivery and urban air mobility, where vehicles must transport and drop cargo at specified locations. The challenge lies in modeling the cost, which varies with both route sequence and onboard load. Our key contributions are: (i) formulating an energy dissipation model and proving energy expenditure depends linearly on vehicle mass and distance; and (ii) formulating a mixed-integer nonlinear programming formulation and providing a novel relaxation to obtain a mixed-integer linear program. Extensive numerical results show that optimal solutions for most instances with up to 50 targets are obtained within one minute. For unsolved instances within a 10-minute limit, optimality gaps are under 13%, highlighting the formulation's tightness. We further benchmark our approach against three proposed baseline formulations and another algorithm from a related problem, and demonstrate that our formulation outperforms all baselines.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a workable MILP relaxation for load-dependent drone TSP that solves most 50-target cases fast with small gaps, but the exactness claim rests on empirical results rather than a formal proof.

read the letter

The key takeaway is that this paper gives a practical MILP relaxation for the load-dependent traveling salesman problem in drone delivery, solving most 50-target instances quickly with small gaps on the rest, but it does not fully establish that the relaxation is always exact. They start with a physical energy dissipation model and prove that, under constant velocity and no external forces, the energy spent is linear in the current mass and the distance of each leg. This is useful because it turns the load-dependent cost into something that can be modeled with cumulative loads. From there they write a mixed-integer nonlinear program and relax it to a linear one. The numerical section shows the approach finds optimal solutions for the majority of test cases within a minute and keeps optimality gaps under 13 percent for the others. They also compare against three baseline formulations and one existing algorithm, where their version comes out ahead. The main limitation is that the relaxation's exactness is supported only by the computational results rather than a proof. The title calls it an exact algorithm, yet the method relies on the MILP being tight, and no theorem is mentioned that rules out cases where the linear version underestimates the true cost for certain load sequences. The instances are generated synthetically, and the model leaves out factors like wind or acceleration that would matter in actual UAV operations. These are not fatal but mean the claims should be read as works well in these tests rather than provably exact for the general problem. This is the kind of paper that would interest people working on optimization models for urban air mobility or last-mile drone logistics. A reader who wants a concrete formulation they can implement and test on similar-sized problems would get something out of it. The thinking is straightforward and the experiments are reported transparently. It is worth sending for peer review. The computational evidence is strong enough that referees can evaluate whether the relaxation holds up and whether the modeling assumptions are reasonable for the target applications.

Referee Report

2 major / 2 minor

Summary. The paper formulates the load-dependent traveling salesman problem (LD-TSP) for UAV package delivery, where energy cost depends on current load. It derives an energy dissipation model proving linearity in mass and distance under idealized conditions, presents a MINLP formulation, and introduces a novel relaxation to an MILP. Numerical tests on instances up to 50 targets show most solved to optimality within one minute, with gaps below 13% for the rest, and outperformance versus three baselines and a related algorithm.

Significance. If the relaxation is exact, the work supplies a practical exact method for a practically relevant TSP variant with load-dependent costs, directly applicable to UAV routing. The explicit linearity proof and reported empirical tightness (small gaps on unsolved instances) are strengths that could enable reliable optimization for moderate-sized delivery problems.

major comments (2)

[Formulation and relaxation (around the MINLP-to-MILP step)] The central claim of an 'exact algorithm' rests on the novel relaxation from MINLP to MILP, yet no theorem or proof is supplied establishing equivalence, validity of the bounds, or zero integrality gap. Without this, it remains possible that some MILP solutions are infeasible or suboptimal for the original nonlinear model (see skeptic note on linearization of load-dependent terms).
[Energy dissipation model] The energy model proves linearity assuming constant velocity and no external forces. The manuscript does not discuss how deviations (e.g., wind, variable speed, or acceleration) affect the claimed linearity or the resulting MILP solutions.

minor comments (2)

[Abstract] Abstract: the phrase 'highlighting the formulation's tightness' is vague; quantify what 'tight' means (e.g., average gap or worst-case bound) and reference the specific table or figure.
[Computational experiments] Numerical results: clarify the instance-generation procedure (random vs. realistic delivery locations) and whether the 10-minute limit was applied uniformly to all baselines.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each of the major comments in detail below, indicating where revisions will be made to strengthen the paper.

read point-by-point responses

Referee: The central claim of an 'exact algorithm' rests on the novel relaxation from MINLP to MILP, yet no theorem or proof is supplied establishing equivalence, validity of the bounds, or zero integrality gap. Without this, it remains possible that some MILP solutions are infeasible or suboptimal for the original nonlinear model (see skeptic note on linearization of load-dependent terms).

Authors: We clarify that the proposed MILP is a relaxation of the MINLP, obtained by linearizing the load-dependent cost function using auxiliary variables to represent the cumulative load on each arc. The linearization ensures that the objective value of the MILP is a lower bound on the MINLP, and integer solutions to the MILP correspond to feasible routes for the original problem. However, we acknowledge that a formal theorem establishing the exact equivalence or the conditions for zero integrality gap is not explicitly stated. To address this, we will add a dedicated proposition and its proof in the revised version, demonstrating the validity of the relaxation and that the MILP solutions are optimal for the MINLP when the gap is closed. The empirical results with small gaps support the tightness of the formulation. revision: yes
Referee: The energy model proves linearity assuming constant velocity and no external forces. The manuscript does not discuss how deviations (e.g., wind, variable speed, or acceleration) affect the claimed linearity or the resulting MILP solutions.

Authors: The energy dissipation model is developed under the assumptions of constant velocity and no external forces to derive the linearity in mass and distance, as detailed in the manuscript. This idealized setting is necessary for the proof and the subsequent MILP formulation. We agree that a discussion on the impact of real-world deviations would be beneficial. In the revision, we will include a new subsection or paragraph addressing how factors such as wind, variable speeds, and acceleration could affect the energy model, potentially by introducing additional terms or requiring adjustments to the coefficients in the MILP. This will clarify the scope and suggest directions for future extensions. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper formulates an energy dissipation model from physical principles, proves linearity of expenditure on mass and distance under idealized conditions (constant velocity, no external forces), and uses this to construct a linear objective in the MINLP. The MINLP is then relaxed to an MILP via a novel linearization technique. Numerical experiments report solution times and gaps on instances up to 50 targets. No quoted step reduces a claimed prediction or uniqueness result to a fitted parameter, self-definition, or load-bearing self-citation chain; the central claims rest on the stated physical model and standard relaxation methods rather than circular re-use of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the physical modeling assumption that energy use is linear in mass and distance; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Energy expenditure depends linearly on vehicle mass and distance
Stated as proven in the paper under the energy dissipation model for UAV flight.

pith-pipeline@v0.9.0 · 5495 in / 1242 out tokens · 51842 ms · 2026-05-08T15:50:21.681757+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Bluehalo inc., intense eye version 3,

BlueHalo, “Bluehalo inc., intense eye version 3,” 2021

work page 2021
[2]

A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones,

Y . Xia, W. Zeng, C. Zhang, and H. Yang, “A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones,” Transportation Research Part B: Methodological, vol. 171, pp. 80– 110, 2023. [Online]. Available: https://www.sciencedirect.com/science/ article/pii/S0191261523000383

work page 2023
[3]

Vehicle routing problems for drone delivery,

K. Dorling, J. Heinrichs, G. G. Messier, and S. Magierowski, “Vehicle routing problems for drone delivery,”IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 1, pp. 70–85, 2017

work page 2017
[4]

Drone delivery scheduling optimization considering payload-induced battery consumption rates,

M. Torabbeigi, G. J. Lim, and S. J. Kim, “Drone delivery scheduling optimization considering payload-induced battery consumption rates,” Journal of Intelligent & Robotic Systems, vol. 97, no. 3, pp. 471–487, 2020

work page 2020
[5]

Optimizing drone delivery paths from shared bases: A location-routing problem with realistic energy constraints,

M. Meskar and A. Ahmadi-Javid, “Optimizing drone delivery paths from shared bases: A location-routing problem with realistic energy constraints,”Journal of Intelligent & Robotic Systems, vol. 110, no. 4, 2024

work page 2024
[6]

Longest flight time quadcopter drones,

R. Leowins, “Longest flight time quadcopter drones,” https://www.volarious.com/blog-tethered-drone/ longest-flight-time-drones-2023-quadcopter, 2023, last accessed: Dec 6, 2025

work page 2023
[7]

A new formulation for the traveling deliveryman problem,

I. M ´endez-D´ıaz, P. Zabala, and A. Lucena, “A new formulation for the traveling deliveryman problem,”Discrete Applied Mathematics, vol. 156, no. 17, pp. 3223–3237, 2008, cologne/Twente Workshop on Graphs and Combinatorial Optimization. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0166218X08002163

work page 2008
[8]

The load- dependent vehicle routing problem and its pick-up and delivery ex- tension,

E. E. Zachariadis, C. D. Tarantilis, and C. T. Kiranoudis, “The load- dependent vehicle routing problem and its pick-up and delivery ex- tension,”Transportation Research Part B: Methodological, vol. 71, pp. 158–181, 2015

work page 2015
[9]

An exact a*- based tree search algorithm for tsp with sequence-and-load dependent risk,

H. Cha, C. Lee, C. Xie, Q.-C. Lu, J. Eun, and T. Cheong, “An exact a*- based tree search algorithm for tsp with sequence-and-load dependent risk,”IEEE Transactions on Intelligent Transportation Systems, vol. 25, no. 9, pp. 10 817–10 834, 2024

work page 2024
[10]

Integer programming formulation of traveling salesman problems,

C. E. Miller, A. W. Tucker, and R. A. Zemlin, “Integer programming formulation of traveling salesman problems,”J. ACM, vol. 7, no. 4, p. 326–329, Oct. 1960. [Online]. Available: https://doi.org/10.1145/ 321043.321046

work page arXiv 1960
[11]

D. L. Applegate, R. E. Bixby, V . Chv´atal, and W. J. Cook,The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2007

work page 2007
[12]

3-approximation algorithm for a two depot, heterogeneous traveling salesman problem,

S. Yadlapalli, S. Rathinam, and S. Darbha, “3-approximation algorithm for a two depot, heterogeneous traveling salesman problem,”Optimiza- tion Letters, vol. 6, no. 1, pp. 141–152, 2012

work page 2012
[13]

Gurobi Optimizer Reference Manual,

Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,”

work page
[14]

Available: https://www.gurobi.com

[Online]. Available: https://www.gurobi.com

work page
[15]

Lkh tsp solver,

K. Helsgaun, “Lkh tsp solver,” http://webhotel4.ruc.dk/ ∼keld/research/ LKH/, accessed Jul 2025

work page 2025
[16]

The min-max multi-depot vehicle routing problem: heuristics and computational results,

X. Wang, B. Golden, and E. Wasil, “The min-max multi-depot vehicle routing problem: heuristics and computational results,”The Journal of the Operational Research Society, vol. 66, no. 9, pp. 1430–1441, 2015. [Online]. Available: http://www.jstor.org/stable/24505453

work page arXiv 2015
[17]

Reinelt, “Tsplib,” accessed Jul 2025 1991, http://comopt.ifi

G. Reinelt, “Tsplib,” accessed Jul 2025 1991, http://comopt.ifi. uni-heidelberg.de/software/TSPLIB95/

work page 2025
[18]

TSP Test Data,

W. Cook, “TSP Test Data,” https://www.math.uwaterloo.ca/tsp/data/ index.html, accessed Jul 2009

work page 2009
[19]

Vehicle routing problems that minimize the completion time : Heuristics, worst-case analyses, and computational results,

X. Wang, “Vehicle routing problems that minimize the completion time : Heuristics, worst-case analyses, and computational results,” Ph.D. dissertation, University of Maryland, College Park, 2016

work page 2016
[20]

Symphony: Vrp test problem data sets,

COIN-OR, “Symphony: Vrp test problem data sets,” https://www. coin-or.org/SYMPHONY/branchandcut/VRP/data/index.htm, 2003, ac- cessed: 2025-12-08. APPENDIX A. Derivation of power consumption We make the following assumptions: (i) The vehicle travels at a constant speedV 0 and altitude (for UA Vs) in a steady wind, which, without loss of generality, blows e...

work page 2003

[1] [1]

Bluehalo inc., intense eye version 3,

BlueHalo, “Bluehalo inc., intense eye version 3,” 2021

work page 2021

[2] [2]

A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones,

Y . Xia, W. Zeng, C. Zhang, and H. Yang, “A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones,” Transportation Research Part B: Methodological, vol. 171, pp. 80– 110, 2023. [Online]. Available: https://www.sciencedirect.com/science/ article/pii/S0191261523000383

work page 2023

[3] [3]

Vehicle routing problems for drone delivery,

K. Dorling, J. Heinrichs, G. G. Messier, and S. Magierowski, “Vehicle routing problems for drone delivery,”IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 1, pp. 70–85, 2017

work page 2017

[4] [4]

Drone delivery scheduling optimization considering payload-induced battery consumption rates,

M. Torabbeigi, G. J. Lim, and S. J. Kim, “Drone delivery scheduling optimization considering payload-induced battery consumption rates,” Journal of Intelligent & Robotic Systems, vol. 97, no. 3, pp. 471–487, 2020

work page 2020

[5] [5]

Optimizing drone delivery paths from shared bases: A location-routing problem with realistic energy constraints,

M. Meskar and A. Ahmadi-Javid, “Optimizing drone delivery paths from shared bases: A location-routing problem with realistic energy constraints,”Journal of Intelligent & Robotic Systems, vol. 110, no. 4, 2024

work page 2024

[6] [6]

Longest flight time quadcopter drones,

R. Leowins, “Longest flight time quadcopter drones,” https://www.volarious.com/blog-tethered-drone/ longest-flight-time-drones-2023-quadcopter, 2023, last accessed: Dec 6, 2025

work page 2023

[7] [7]

A new formulation for the traveling deliveryman problem,

I. M ´endez-D´ıaz, P. Zabala, and A. Lucena, “A new formulation for the traveling deliveryman problem,”Discrete Applied Mathematics, vol. 156, no. 17, pp. 3223–3237, 2008, cologne/Twente Workshop on Graphs and Combinatorial Optimization. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0166218X08002163

work page 2008

[8] [8]

The load- dependent vehicle routing problem and its pick-up and delivery ex- tension,

E. E. Zachariadis, C. D. Tarantilis, and C. T. Kiranoudis, “The load- dependent vehicle routing problem and its pick-up and delivery ex- tension,”Transportation Research Part B: Methodological, vol. 71, pp. 158–181, 2015

work page 2015

[9] [9]

An exact a*- based tree search algorithm for tsp with sequence-and-load dependent risk,

H. Cha, C. Lee, C. Xie, Q.-C. Lu, J. Eun, and T. Cheong, “An exact a*- based tree search algorithm for tsp with sequence-and-load dependent risk,”IEEE Transactions on Intelligent Transportation Systems, vol. 25, no. 9, pp. 10 817–10 834, 2024

work page 2024

[10] [10]

Integer programming formulation of traveling salesman problems,

C. E. Miller, A. W. Tucker, and R. A. Zemlin, “Integer programming formulation of traveling salesman problems,”J. ACM, vol. 7, no. 4, p. 326–329, Oct. 1960. [Online]. Available: https://doi.org/10.1145/ 321043.321046

work page arXiv 1960

[11] [11]

D. L. Applegate, R. E. Bixby, V . Chv´atal, and W. J. Cook,The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2007

work page 2007

[12] [12]

3-approximation algorithm for a two depot, heterogeneous traveling salesman problem,

S. Yadlapalli, S. Rathinam, and S. Darbha, “3-approximation algorithm for a two depot, heterogeneous traveling salesman problem,”Optimiza- tion Letters, vol. 6, no. 1, pp. 141–152, 2012

work page 2012

[13] [13]

Gurobi Optimizer Reference Manual,

Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,”

work page

[14] [14]

Available: https://www.gurobi.com

[Online]. Available: https://www.gurobi.com

work page

[15] [15]

Lkh tsp solver,

K. Helsgaun, “Lkh tsp solver,” http://webhotel4.ruc.dk/ ∼keld/research/ LKH/, accessed Jul 2025

work page 2025

[16] [16]

The min-max multi-depot vehicle routing problem: heuristics and computational results,

X. Wang, B. Golden, and E. Wasil, “The min-max multi-depot vehicle routing problem: heuristics and computational results,”The Journal of the Operational Research Society, vol. 66, no. 9, pp. 1430–1441, 2015. [Online]. Available: http://www.jstor.org/stable/24505453

work page arXiv 2015

[17] [17]

Reinelt, “Tsplib,” accessed Jul 2025 1991, http://comopt.ifi

G. Reinelt, “Tsplib,” accessed Jul 2025 1991, http://comopt.ifi. uni-heidelberg.de/software/TSPLIB95/

work page 2025

[18] [18]

TSP Test Data,

W. Cook, “TSP Test Data,” https://www.math.uwaterloo.ca/tsp/data/ index.html, accessed Jul 2009

work page 2009

[19] [19]

Vehicle routing problems that minimize the completion time : Heuristics, worst-case analyses, and computational results,

X. Wang, “Vehicle routing problems that minimize the completion time : Heuristics, worst-case analyses, and computational results,” Ph.D. dissertation, University of Maryland, College Park, 2016

work page 2016

[20] [20]

Symphony: Vrp test problem data sets,

COIN-OR, “Symphony: Vrp test problem data sets,” https://www. coin-or.org/SYMPHONY/branchandcut/VRP/data/index.htm, 2003, ac- cessed: 2025-12-08. APPENDIX A. Derivation of power consumption We make the following assumptions: (i) The vehicle travels at a constant speedV 0 and altitude (for UA Vs) in a steady wind, which, without loss of generality, blows e...

work page 2003