Travelling the entire network of the subway system in New York or the tube in London as fast as possible has become a kind of sport. In Berlin it seems to be a quite new phenomenon but the last few years some people have been trying to cover a part of the Berlin public transport network in minimal time. Most of the participants do not use mathematical optimization software to calculate a tour. In this project we develop a tool to calculate an optimal itinerary for the Berlin S-Bahn Challenge.
There are several variants for public transport challenges. The two most common ones are visiting all connections between two stations or just visiting all stations. We chose the first one as it seems to be the more natural definition of travelling the entire network. So the S-Bahn Challenge Problem can be formulated as finding a shortest tour through the Berlin public transport system obeying the following rules:
• Each S-Bahn station and each S-Bahn connection between stations in the zones A,B,C should be visited at least once.
– Each connection only has to be visited in one direction.
– If there are multiple lines between two stations, visiting one line suffices.
• Walking between stations and the use of all other public transport that follows a fixed schedule is allowed.
To take all transfer times correctly into account a time expanded network is constructed. We use that the timetable of the Berlin S-Bahn repeats itself after some time interval which makes the expanded network much smaller. Furthermore, we add some well chosen extra connections because adding all connections of the Berlin public transport system would result in a network that is too big to work with. At the end, we have a directed graph, where the arcs are partitioned into groups. The first group contains all extra connections and transfer arcs, these arcs can but need not to be used. For every connection of two stations we have one group containing all arcs that corresponds to this connections. The problem is to find a path in this directed graph visiting at least one arc of every group except of the first. In the literature this problem is known as the Generalized Directed Rural Postman Problem (GDRPP). It is a rather new problem, not many solution methods are known, and the heuristics do not perform very well.
We solve the GDRPP by transforming it into an asymmetric generalized TSP, then into an asymmetric TSP, and finally into a TSP. The final TSP can be solved using any TSP-solver, for example Concorde. Afterwards, the solution can be transformed back into a feasible tour for the S-Bahn Challenge. The fastest tour calculated this way takes 13 hours and 44 minutes (January 2015) and all transfers are feasible according to the BVG journey planner.
