On the Dubins Traveling Salesman Problem

Jérôme Le Ny, Éric Féron, Emilio Frazzoli

IEEE Transactions on Automatic Control · 2011 · 157 citations · 25 references

Concepts

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.

References

25