On the dubins traveling salesman problem

Jerome Ny, Eric Feron, Emilio Frazzoli

Research output: Contribution to journalArticlepeer-review

127 Scopus citations


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
Issue number1
StatePublished - Jan 1 2012
Externally publishedYes


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

Cite this