The curvature-constrained traveling salesman problem for high point densities

Jerome Le Ny, Emilio Frazzoli, Eric Feron

Research output: Chapter in Book/Report/Conference proceedingConference contribution

37 Scopus citations

Abstract

We consider algorithms for the curvature-constrained traveling salesman problem, when the nonholonomic constraint is described by Dubins' model. We indicate a proof of the NP-hardness of this problem. In the case of low point densities, i.e., when the Euclidean distances between the points are larger than the turning radius of the vehicle, various heuristics based on the Euclidean Traveling salesman problem are expected to perform well. In this paper we do not put a constraint on the minimum Euclidean distance. We show that any algorithm that computes a tour for the Dubins' vehicle following an ordering of points optimal for the Euclidean TSP cannot have an approximation ratio better than Ω(n), where n is the number of points. We then propose an algorithm that is not based on the Euclidean solution and seems to behave differently. For this algorithm, we obtain an approximation guarantee of O (min{(1 + Ω) log n, (1 + Ω)2}), where ρ is the minimum turning radius, and e is the minimum Euclidean distance between any two points. ©2007 IEEE.
Original languageEnglish (US)
Title of host publicationProceedings of the IEEE Conference on Decision and Control
Pages5985-5990
Number of pages6
DOIs
StatePublished - Dec 1 2007
Externally publishedYes

Fingerprint

Dive into the research topics of 'The curvature-constrained traveling salesman problem for high point densities'. Together they form a unique fingerprint.

Cite this