Item Details

Print View

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
2012-10-29
Published
University of Virginia, Department of Computer Science, 1998
Published Date
1998
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online