The Traveling Salesman Problem with Drones: The Benefits of Retraversing the Arcs

Nicola Morandi (), Roel Leus (), Jannik Matuschke () and Hande Yaman ()
Additional contact information
Nicola Morandi: Research Centre for Operations Research and Statistics, KU Leuven, 3000 Leuven, Belgium
Roel Leus: Research Centre for Operations Research and Statistics, KU Leuven, 3000 Leuven, Belgium
Jannik Matuschke: Research Centre for Operations Management, KU Leuven, 3000 Leuven, Belgium
Hande Yaman: Research Centre for Operations Research and Statistics, KU Leuven, 3000 Leuven, Belgium

Transportation Science, 2023, vol. 57, issue 5, 1340-1358

Abstract: In the traveling salesman problem with drones (TSP-mD), a truck and multiple drones cooperate to serve customers in the minimum amount of time. The drones are launched and retrieved by the truck at customer locations, and each of their flights must not consume more energy than allowed by their batteries. Most problem settings in the literature restrict the feasible truck routes to cycles (i.e., closed paths), which never visit a node more than once. Revisiting a node, however, may lower the time required to serve all the customers. Additionally, we observe that optimal solutions for the TSP-mD may retraverse arcs (i.e., optimal truck routes may contain the same arcs multiple times). We refer to such solutions as arc retraversing and include them in our solution space by modeling the truck route as a closed walk. We describe Euclidean instances where all the optimal solutions are arc retraversing. The necessity of arc retraversals does not seem to have been investigated in previous studies, and those that allow node revisits seem to assume that there always exists an optimal solution without arc retraversals. We prove that under certain conditions, which are commonly met in the literature, this assumption is correct. When these conditions are not met, however, excluding arc-retraversing solutions might result in an increase of the optimal value; we identify cases where a priori and a posteriori upper bounds hold on such increase. Finally, we prove that there is no polynomial-time heuristic that can approximate the metric TSP-mD within a constant factor, unless P = NP . We identify a (nonconstant) approximation factor explicitly when the truck can visit all the nodes.

Keywords: drone-aided routing; TSP with drone; arc retraversing; approximability; synchronization (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.0230 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:57:y:2023:i:5:p:1340-1358

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().