Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2603.00328 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917300551024640 |
|---|---|
| author | Lee, Jae Hyeok Hwang, Taekang Kwon, Changhyun |
| author_facet | Lee, Jae Hyeok Hwang, Taekang Kwon, Changhyun |
| contents | The asymptotic behavior of the optimal TSP tour length is well known from the classical Beardwood--Halton--Hammersley theorem. We extend this result to the Traveling Salesman Problem with Drone (TSPD), a cooperative routing problem in which a truck and a drone jointly serve customers. Using a subadditive Euclidean functional framework, we establish the existence of an almost sure limit for the optimal TSPD makespan scaled by the square root of the problem size. We derive explicit upper and lower bounds for the speed-scaled Euclidean TSPD model: upper bounds are obtained via structured ring-based tour constructions and Monte Carlo evaluation, while lower bounds are derived from a parametric approach and known bounds on the Euclidean TSP constant. Computational results illustrate how tight the bounds are. We also derive and discuss lower bounds for the Rectilinear--Euclidean mixed TSPD model, in which truck travel is measured by the rectilinear distance and drone travel by the Euclidean distance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_00328 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Asymptotic Bounds for the Traveling Salesman Problem with Drone Lee, Jae Hyeok Hwang, Taekang Kwon, Changhyun Optimization and Control Discrete Mathematics The asymptotic behavior of the optimal TSP tour length is well known from the classical Beardwood--Halton--Hammersley theorem. We extend this result to the Traveling Salesman Problem with Drone (TSPD), a cooperative routing problem in which a truck and a drone jointly serve customers. Using a subadditive Euclidean functional framework, we establish the existence of an almost sure limit for the optimal TSPD makespan scaled by the square root of the problem size. We derive explicit upper and lower bounds for the speed-scaled Euclidean TSPD model: upper bounds are obtained via structured ring-based tour constructions and Monte Carlo evaluation, while lower bounds are derived from a parametric approach and known bounds on the Euclidean TSP constant. Computational results illustrate how tight the bounds are. We also derive and discuss lower bounds for the Rectilinear--Euclidean mixed TSPD model, in which truck travel is measured by the rectilinear distance and drone travel by the Euclidean distance. |
| title | Asymptotic Bounds for the Traveling Salesman Problem with Drone |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2603.00328 |