The STUDIA UNIVERSITATIS BABEŞ-BOLYAI issue article summary

The summary of the selected article appears at the bottom of the page. In order to get back to the contents of the issue this article belongs to you have to access the link from the title. In order to see all the articles of the archive which have as author/co-author one of the authors mentioned below, you have to access the link from the author's name.

  
       
         
    STUDIA MATHEMATICA - Issue no. 1 / 2008  
         
  Article:   A CUTTING PLANE APPROACH TO SOLVE THE RAILWAY TRAVELING SALESMAN PROBLEM.

Authors:  PETRICĂ C. POP, CHRISTOS D. ZAROLIAGIS, GEORGIA HADJICHARALAMBOUS. 		 
       
         
  Abstract:   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 minimum cost cycle spanning a subset of nodes with the property that exactly two nodes are chosen from each cluster. We describe an exact exponential time algorithm for the problem, as well we present two mixed integer programming models of the problem. Based on one of this models proposed, 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 involving graphs with up to 2182 nodes and 38650 edges are reported.  
         
     
         
         
      Back to previous page