Moving-Target TSP and Related ProblemsReport
Previous literature on the Traveling Salesman Problem (TSP) implicitly assumed that the sites to be visited are stationary. Motivated by practical applications, we introduce a time-dependent generalization of TSP which we call Moving-Target TSP, where a pursuer must inter- cept a set of targets which move with constant velocities in a minimum amount of time. We propose approximate and exact algorithms for sev- eral natural variants of Moving-Target TSP. Our implementation of the exact algorithm of One-Dimensional TSP is available on the Web.
All rights reserved (no additional license for public reuse)
Helvig, C, Gabriel Robins, and Alex Zelikovsky. "Moving-Target TSP and Related Problems." University of Virginia Dept. of Computer Science Tech Report (1998).
University of Virginia, Department of Computer Science