Covering Tours with Turn Cost: Variants, Approximation and Practical Solution
Fekete and Krupke
Abstract: For a given set P of points in the plane, the Angular-Metric Traveling Salesman Problem (AM-TSP) asks for a tour on P that minimizes the total turn along the tour. While there exists a PTAS for the Euclidean TSP, for the AM-TSP only a O(log n) approximation algorithm is known. We introduce a number of generalizations and provide approximation algorithms whose performance depend on the angular resolution. We also develop exact methods for computing provably optimal solutions, and present an array of experimental results.
This paper is based on chapter 5 of my master’s thesis Algorithmic methods for complex dynamic sweeping problems. Please check there for further material.
- The runtime dependency is polynomial and not as written linear on $\omega$.
Mosquito drone and corresponding images by Aaron Becker and his team in Houston.