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:Article
Entered by:
TitleA Cutting Plane Approach to Solve the Railway Traveling Salesman Problem
Bibtex cite IDRACTI-RU1-2008-85
Journal Studia Universitatis Mathematica
Year published 2008
Month March
Volume 53
Number 1
Pages 63-73
Keywords generalized traveling salesman problem,integer programming,cutting planes
We consider the Railway Traveling Salesman Problem. We show that this problem can be reduced to a variant of the generalized traveling salesman problem, defined on an undirected graph G = (V,E) with the nodes partitioned into clusters, which consists in finding a mini- mum cost cycle spanning a subset of nodes with the property that exactly two nodes are chosen from each cluster. We describe an exact exponen- tial time algorithm for the problem, as well we present two mixed integer programming models of the problem. Based on one of this models pro- posed, we present an efficient solution procedure based on a cutting plane algorithm. Extensive computational results for instances taken from the railroad company of the Netherlands Nederlandse Spoorwegen and involv- ing graphs with up to 2182 nodes and 38650 edges are reported.
Pop, Petrica
Zaroliagis, Christos
Hadjicharalambous, Georgia
a cutting plane.pdf (main file)
Publication ID855