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.
https://doi.org/10.1016/S0196-6774(03)00075-0Cite as:
@article{Helvig_2003,
doi = {10.1016/s0196-6774(03)00075-0},
url = {https://doi.org/10.1016%2Fs0196-6774%2803%2900075-0},
year = 2003,
month = {oct},
publisher = {Elsevier {BV}},
volume = {49},
number = {1},
pages = {153--174},
author = {C.S. Helvig and Gabriel Robins and Alex Zelikovsky},
title = {The moving-target traveling salesman problem},
journal = {Journal of Algorithms}
}