Abstract: We consider the Railway TravelingSalesmanProblem. We
show that this problem can be reduced to a variant of the generalized
travelingsalesmanproblem, 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.
Abstract: We consider the Railway TravelingSalesmanProblem (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 $\mathcal{NP}$ -hard problem. Although it is related to the Generalized Asymmetric TravelingSalesmanProblem, 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.
Abstract: In this work, we introduce the notion of time to some well-known combinatorial optimization problems. In particular, we study problems defined on temporal graphs. A temporal graph D=(V,A) may be viewed as a time-sequence G_1,G_2,...,G_l of static graphs over the same (static) set of nodes V. Each G_t = D(t) = (V,A(t)) is called the instance of D at time t and l is called the lifetime of D. Our main focus is on analogues of travelingsalesmanproblems in temporal graphs. A sequence of time-labeled edges (e.g. a tour) is called temporal if its labels are strictly increasing. We begin by considering the problem of exploring the nodes of a temporal graph as soon as possible. In contrast to the positive results known for the static case, we prove that, it cannot be approximated within cn, for some constant c > 0, in general temporal graphs and within (2 − \varepsilon), for every constant \varepsilon > 0, in the special case in which D(t) is connected for all 1 <= t <= l, both unless P = NP. We then study the temporal analogue of TSP(1,2), abbreviated TTSP(1,2), where, for all 1 <= t <= l, D(t) is a complete weighted graph with edge-costs from {1,2} and the cost of an edge may vary from instance to instance. The goal is to find a minimum cost temporal TSP tour. We give several polynomial-time approximation algorithms for TTSP(1,2). Our best approximation is (1.7 + \varepsilon) for the generic TTSP(1,2) and (13/8 + \varepsilon) for its interesting special case in which the lifetime of the temporal graph is restricted to n. In the way, we also introduce temporal versions of Maximum Matching, Path Packing, Max-TSP, and Minimum Cycle Cover, for which we obtain polynomial-time approximation algorithms and hardness results.
