On the dubins traveling salesman problem

Jerome Ny, Eric Feron, Emilio Frazzoli

Research output: Contribution to journalArticlepeer-review

103 Scopus citations

Abstract

We study the traveling salesman problem for a Dubins vehicle. We prove that this problem is NP-hard, and provide lower bounds on the approximation ratio achievable by some recently proposed heuristics. We also describe new algorithms for this problem based on heading discretization, and evaluate their performance numerically. © 2006 IEEE.
Original languageEnglish (US)
Pages (from-to)265-270
Number of pages6
JournalIEEE Transactions on Automatic Control
Volume57
Issue number1
DOIs
StatePublished - Jan 1 2012
Externally publishedYes

Fingerprint

Dive into the research topics of 'On the dubins traveling salesman problem'. Together they form a unique fingerprint.

Cite this