Moving-Target TSP and Related Problems

Report
Authors:Helvig, C, Department of Computer ScienceUniversity of Virginia Robins, Gabriel, Department of Computer ScienceUniversity of Virginia Zelikovsky, Alex, Department of Computer ScienceUniversity of Virginia
Abstract:

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.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Helvig, C, Gabriel Robins, and Alex Zelikovsky. "Moving-Target TSP and Related Problems." University of Virginia Dept. of Computer Science Tech Report (1998).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1998