Item Details

Moving-Target TSP and Related Problems

Helvig, C; Robins, Gabriel; Zelikovsky, Alex
Format
Report
Author
Helvig, C
Robins, Gabriel
Zelikovsky, Alex
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.
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1998
Published Date
1998
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online