The moving-target traveling salesman problem

Previous literature on the Traveling Salesman Problem (TSP) 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 intercept in minimum time a set of targets w...

Full description

Saved in:
Bibliographic Details
Published in:Journal of algorithms 2003-10, Vol.49 (1), p.153-174
Main Authors: Helvig, C.S., Robins, Gabriel, Zelikovsky, Alex
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Mathematical programming
Operational research and scientific management
Operational research. Management science
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Previous literature on the Traveling Salesman Problem (TSP) 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 intercept in minimum time a set of targets which move with constant velocities. We propose approximate and exact algorithms for several natural variants of Moving-Target TSP.
ISSN:0196-6774
1090-2678
DOI:10.1016/S0196-6774(03)00075-0