research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleThe Railway Traveling Salesman Problem
Bibtex cite IDRACTI-RU1-2007-120
Booktitle Algorithmic Methods for Railway Optimization
Series Lecture Notes in Computer Science
Year published 2007
Volume 4359
Pages 264-275
Publisher Springer-Verlag
Note Also in ATMOS 2004
We consider the Railway Traveling Salesman Problem (RTSP) in which a salesman using the railway network wishes to visit a certain number of cities to carry out his/her business, starting and ending at the same city, and having as goal to minimize the overall time of the journey. RTSP is an $\mathcalNP$ -hard problem. Although it is related to the Generalized Asymmetric Traveling Salesman Problem, in this paper we follow a direct approach and present a modelling of RTSP as an integer linear program based on the directed graph resulted from the timetable information. Since this graph can be very large, we also show how to reduce its size without sacrificing correctness. Finally, we conduct an experimental study with real-world and synthetic data that demonstrates the superiority of the size reduction approach.
Hadjicharalambous, Georgia
Pop, Petrica
Pyrga, Evangelia
Tsaggouris, George
Zaroliagis, Christos
fulltext3.pdf (main file)
Publication ID107