An Exact Algorithm for Load-Dependent Traveling Salesman Problem for Unmanned Aerial Vehicle Package Delivery
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909020100493312 |
|---|---|
| author | Kumar, Deepak Prakash Belgaonkar, Saurabh Rathinam, Sivakumar Darbha, Swaroop Casbeer, David W. |
| author_facet | Kumar, Deepak Prakash Belgaonkar, Saurabh Rathinam, Sivakumar Darbha, Swaroop Casbeer, David W. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05507 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Exact Algorithm for Load-Dependent Traveling Salesman Problem for Unmanned Aerial Vehicle Package Delivery Kumar, Deepak Prakash Belgaonkar, Saurabh Rathinam, Sivakumar Darbha, Swaroop Casbeer, David W. Optimization and Control 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. |
| title | An Exact Algorithm for Load-Dependent Traveling Salesman Problem for Unmanned Aerial Vehicle Package Delivery |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.05507 |