On the Dubins Traveling Salesman Problem
Jérôme Le Ny, Éric Féron, Emilio Frazzoli · IEEE Transactions on Automatic Control · 2011
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.