New heuristic algorithms for the Dubins traveling salesman problem

Luitpold Babel ()
Additional contact information
Luitpold Babel: Universität der Bundeswehr, München

Journal of Heuristics, 2020, vol. 26, issue 4, No 3, 503-530

Abstract: Abstract The problem of finding a shortest curvature-constrained closed path through a set of targets in the plane is known as Dubins traveling salesman problem (DTSP). Applications of the DTSP include motion planning for kinematically constrained mobile robots and unmanned fixed-wing aerial vehicles. The difficulty of the DTSP is to simultaneously find an order of the targets and suitable headings (orientation angles) of the vehicle when passing the targets. Since the DTSP is known to be NP-hard there is a need for heuristic algorithms providing good quality solutions in reasonable time. Inspired by standard methods for the TSP we present a collection of such heuristics adapted to the DTSP. The algorithms are based on a technique that optimizes the headings of the targets of an open or closed subtour with given order. This is done by discretizing the headings, constructing an auxiliary network and computing a shortest path in the network. The first algorithm for the DTSP uses the order of the targets obtained from the solution of the Euclidean TSP. A second class of algorithms extends an open subtour by successively adding a new target and closes the tour if all targets have been added. A third class of algorithms starts with a closed subtour consisting of few targets and successively inserts a new target into the tour. The individual algorithms differ by the number of headings to be optimized in each iteration. Extensive simulation results show that the proposed methods are competitive with state-of-the-art methods for the DTSP concerning performance and superior concerning running time, which makes them applicable also to large-scale scenarios.

Keywords: Dubins traveling salesman problem; Curvature-constrained traveling salesman problem; Dubins vehicle; Heuristic methods (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-020-09440-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joheur:v:26:y:2020:i:4:d:10.1007_s10732-020-09440-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-020-09440-2

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().