Solving the Railway Traveling Salesman Problem via a Transformation into the Classical Traveling Salesman Problem

The Railway Traveling Salesman Problem (RTSP) is a practical extension of the classical traveling salesman problem considering a railway network and train schedules. We are given a salesman who has to visit a number of cities to carry out some business. He starts and ends at a specified home city, and the required time for the overall journey, including waiting times, shall be minimized. In this paper, we present two transformation schemes to reformulate the RTSP as either a classical asymmetric or symmetric Traveling Salesman Problem (TSP). Using these transformations, established algorithms for solving the TSP can be used to attack the RTSP as well. Tests using the branch-and-cut TSP solver from the Concorde library show that this transformation is efficient and, thus, is highly competitive compared to so far existing approaches for solving the RTSP directly.