Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/288666 
Authors: 
Year of Publication: 
2020
Citation: 
[Journal:] Journal of Heuristics [ISSN:] 1572-9397 [Volume:] 26 [Issue:] 4 [Publisher:] Springer US [Place:] New York, NY [Year:] 2020 [Pages:] 503-530
Publisher: 
Springer US, New York, NY
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.
Subjects: 
Dubins traveling salesman problem
Curvature-constrained traveling salesman problem
Dubins vehicle
Heuristic methods
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.