TY - GEN

T1 - The curvature-constrained traveling salesman problem for high point densities

AU - Le Ny, Jerome

AU - Frazzoli, Emilio

AU - Feron, Eric

N1 - Generated from Scopus record by KAUST IRTS on 2021-02-18

PY - 2007/12/1

Y1 - 2007/12/1

N2 - 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.

AB - 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.

UR - http://ieeexplore.ieee.org/document/4434503/

UR - http://www.scopus.com/inward/record.url?scp=62749141190&partnerID=8YFLogxK

U2 - 10.1109/CDC.2007.4434503

DO - 10.1109/CDC.2007.4434503

M3 - Conference contribution

SN - 1424414989

SP - 5985

EP - 5990

BT - Proceedings of the IEEE Conference on Decision and Control

ER -