On the discretized Dubins Traveling Salesman Problem

This research deals with a variation of the Traveling Salesman Problem in which the cost of a tour, during which a kinematically constrained vehicle visits a set of targets, has to be minimized. We are motivated by situations that include motion planning for unmanned aerial, marine, and ground vehicles, just to name a few possible application outlets. We discretize the original continuous problem and explicitly formulate it as an integer optimization problem. Then we develop a performance bound as a function of the discretization level and the number of targets. The inclusion of a discretization level provides an opportunity to achieve tighter bounds, compared to what has been reported in the literature. We perform a numerical study that quantifies the performance of the suggested approach. The suggested linkage between discretization level, number of targets, and performance may guide discretization-level choices for the solution of motion planning problems. Specifically, theoretical and numerical results indicate that, in many instances, discretization may be set at a low level to strike a balance between computational time and the length of a tour.