On the discretized Dubins Traveling Salesman Problem

Izack Cohen, Chen Epstein and Tal Shima

IISE Transactions, 2017, vol. 49, issue 2, 238-254

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.

Date: 2017
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/0740817X.2016.1217101 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:49:y:2017:i:2:p:238-254

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/0740817X.2016.1217101

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().