Accession Number:

AD1005734

Title:

Asymptotic Constant-Factor Approximation Algorithm for the Traveling Salesperson Problem for Dubins Vehicle

Descriptive Note:

Journal Article - Open Access

Corporate Author:

University of California at Santa Barbara Santa Barbara United States

Report Date:

2006-03-02

Pagination or Media Count:

6.0

Abstract:

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.

Subject Categories:

  • Numerical Mathematics
  • Surface Transportation and Equipment

Distribution Statement:

APPROVED FOR PUBLIC RELEASE