Asymptotic Constant-Factor Approximation Algorithm for the Traveling Salesperson Problem for Dubins Vehicle
Journal Article - Open Access
University of California at Santa Barbara Santa Barbara United States
Pagination or Media Count:
This article proposes the first known algorithm that achieves a constant-factor approximation of the minimum length tour for a Dubins vehicle through n points on the plane. By Dubins vehicle, we mean a vehicle constrained to move at constant speed along paths with bounded curvature without reversing direction. For this version of the classic Traveling Salesperson Problem, our algorithm closes the gap between previously established lower and upper bounds the achievable performance is of order n23.
- Numerical Mathematics
- Surface Transportation and Equipment