On the discretized Dubins Traveling Salesman Problem. (1st February 2017)

• Record Type: Journal Article
• Authors: Cohen, Izack; Epstein, Chen; Shima, Tal
• Is Part Of: IISE transactions. Volume 49:Number 2(2017)
• Page Start: 238
• Page End: 254
• Publication Date: 2017-02-01
• Subjects: Traveling Salesman Problem -- Dubins vehicle -- motion planning; Industrial engineering -- Periodicals; Systems engineering -- Periodicals; Industrial engineering; Systems engineering; Electronic journals; Periodicals; 670.285
• DOI: 10.1080/0740817X.2016.1217101
• Languages: English
• ISSNs: 2472-5854

Abstract

ABSTRACT: 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.