On Tightly Bounding the Dubins Traveling Salesman's Optimum Academic Article uri icon

abstract

  • 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. This problem requires finding a curvature constrained shortest path for a vehicle visiting a set of target locations. Currently, there is no algorithm that can find an optimal solution to the DTSP. In addition, relaxing the motion constraints and solving the resulting Euclidean traveling salesman problem (ETSP) provide the only lower bound available for the DTSP. 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 paper addresses this fundamental issue and presents the first systematic procedure for developing tight lower bounds for the DTSP.

published proceedings

  • JOURNAL OF DYNAMIC SYSTEMS MEASUREMENT AND CONTROL-TRANSACTIONS OF THE ASME

altmetric score

  • 4

author list (cited authors)

  • Manyam, S. G., & Rathinam, S.

citation count

  • 18

complete list of authors

  • Manyam, Satyanarayana G||Rathinam, Sivakumar

publication date

  • July 2018