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 language | English (US) |
|---|---|
| Title of host publication | 43rd Annual Allerton Conference on Communication, Control and Computing 2005 |
| Publisher | University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering |
| Pages | 620-629 |
| Number of pages | 10 |
| ISBN (Print) | 9781604234916 |
| State | Published - Jan 1 2005 |
| Externally published | Yes |