An approximation algorithm for the curvature-constrained traveling salesman problem

Jerome Le Ny, Eric Feron

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

31 Scopus citations

Abstract

We present an approximation algorithm for the Traveling Salesman Problem when the vehicle is constrained to move forward along paths with bounded curvature (Dubins' vehicle). A deterministic algorithm returns in time O(n3) a tour within (( 1 + max { 8π ρ / Dmin , 14 /3 o} log n ) of the optimum tour, where n is the number of points to visit, ρ is the minimum turning radius and Dmin is the minimum Euclidean distance between any two points. A randomized version returns a tour with an expected approximation ratio of (( 1 + 13.58 Dmin ρ ) log n ) . This very simple algorithm reduces the Traveling Salesman Problem for Dubins' vehicle to an Asymmetric Traveling Salesman Problem on a directed graph.
Original languageEnglish (US)
Title of host publication43rd Annual Allerton Conference on Communication, Control and Computing 2005
PublisherUniversity of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
Pages620-629
Number of pages10
ISBN (Print)9781604234916
StatePublished - Jan 1 2005
Externally publishedYes

Fingerprint

Dive into the research topics of 'An approximation algorithm for the curvature-constrained traveling salesman problem'. Together they form a unique fingerprint.

Cite this