On Tightly Bounding the Dubins Traveling Salesman's Optimum
This work provides a crucial tool for improving solution quality in surveillance applications, though it is incremental as it focuses on bounding rather than solving the problem directly.
The paper tackles the lack of tight lower bounds for the Dubins Traveling Salesman Problem (DTSP), presenting the first systematic procedure to develop such bounds, which addresses a fundamental gap in existing methods that rely on relaxed Euclidean TSP solutions.
The Dubins Traveling Salesman Problem (DTSP) has generated significant interest over the last decade due to its occurrence in several civil and military surveillance applications. Currently, there is no algorithm that can find an optimal solution to the problem. In addition, relaxing the motion constraints and solving the resulting Euclidean TSP (ETSP) provides the only lower bound available for the problem. However, in many problem instances, the lower bound computed by solving the ETSP is far below the cost of the feasible solutions obtained by some well-known algorithms for the DTSP. This article addresses this fundamental issue and presents the first systematic procedure for developing tight lower bounds for the DTSP.