T.K. Satish Kumar, Marcello Cirillo and Sven Koenig
On the Traveling Salesman Problem with Simple Temporal Constraints
Proc. of the 10th Symposium on Abstraction, Reformulation, and Approximation (SARA 2013)
Abstract: Many real-world applications require the successful combination of spatial and temporal reasoning. In this paper, we study the general framework of the Traveling Salesman Problem with Simple Temporal Constraints. Representationally, this framework subsumes the Traveling Salesman Problem, Simple Temporal Problems, as well as many of the frameworks described in the literature. We analyze the theoretical properties of the combined problem providing strong inapproximability results for the general problem, and positive results for some special cases.
Download:
Paper: [PDF (200kB)].
@INPROCEEDINGS{Kumar_etal:SARA:2013,
  AUTHOR = {Kumar, T.K. Satish and Cirillo, Marcello and Koenig, Sven},
  TITLE = {On the Traveling Salesman Problem with Simple Temporal Constraints},
  BOOKTITLE = {Proceedings of the 10th Symposium on Abstraction, Reformulation, and Approximation (SARA 2013)},
  YEAR = {2013},
  ADRESS = {Leavenworth, Washington, USA},
  PAGES = {}
}