We study the problem of finding the minimum length curvature constrained closed path through a set of regions in the plane. This problem is referred to as the Dubins Traveling Salesperson Problem with Neighborhoods (DTSPN). Two algorithms are presented that transform this infinite dimensional combinatorial optimization problem into a finite dimensional asymmetric TSP by sampling and applying the appropriate transformations, thus allowing the use of existing approximation algorithms. We show for the case of disjoint regions, the first algorithm needs only to sample each region once to produce a tour within a factor of the length of the optimal tour that is independent of the number of regions. We present a second algorithm that performs no worse than the best existing algorithm and can perform significantly better when the regions overlap.
Algorithms for the traveling salesman problem with neighborhoods involving a Dubins vehicle
ACC, American Control Conference, 2011 ; 1704-1709
2011
6 Seiten, 23 Quellen
Conference paper
English
Dubins orienteering problem with neighborhoods
IEEE | 2017
|On the Discretized Dubins Travelling Salesman Problem
British Library Conference Proceedings | 2014
|Genetic algorithms for the traveling salesman problem
TIBKAT | 1993
|British Library Conference Proceedings | 2012
|