IEEE Transactions on Automatic Control · 2011 · 157 citations · 25 references
ComputingComputer ScienceMathematicsAlgorithmsOptimizationTransportationApproximation AlgorithmsCombinatorial OptimizationHeuristic OptimizationHeuristic SearchNumerical AlgorithmsTransportation ProblemsLower BoundsTraveling Salesman ApproximationTraveling Salesman ProblemTraveling Salesperson ProblemTraveling Salesperson Problem Approximation
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.
25
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
Reducibility Among Combinatorial Problems
Kichard Rarp · 2012 · 1.4K citations