Dealing with Perturbations of Periodic Timetables

Problem

There exist some algorithms to build entirely new timetables for a train company from scratch. These algorithms compute the departure times for the trains at every station with respect to a set of restrictions, that exist for a timetable. An example for such an algorithm is described in an article by Paolo Serafini and Walter Ukovich: A Mathematical Model for Periodic Scheduling Problems.
Our work does not concern the solution of this problem, but we assume that there exists a timetable, for that we assume to have a solution, i.e. a periodic timetable that satisfies all restrictions.
We now perturb the periodic timetable a little bit: We delayed just one departure time of one train. Our goal was to rebalance the timetable. This should be done within one period and as locally as possible, that means the number of other delayed trains should be as small as possible. Our ideas are adapted from the Serafini/Ukovich article and from a chapter written by R. T. Rockafellar.

Abstract

We assume only to have one delay in the timetable. Starting from this disturbance the delay will be propagated through the timetable using all the little scopes that should exist in a good timetable. We divide the restrictions into two classes: Strong and soft restrictions. Strong restrictions are security distances and train compositions, which means, that a train cannot leave the station until he has arrived. The soft restriction include all the restrictions according the connections a train should wait for. If such a restriction is violated then we only have unhappy passengers, but no problem with the security for other passengers.
The realization of such a delay propagation is as follows: We delay other trains, keeping all strong and as many soft restrictions as possible. The timetable can be illustrated in a directed graph: The departure times are the nodes and the restrictions are the arcs. Starting from the delayed node we compute a spanning tree of the whole graph. In this tree we only include arcs and nodes so that there are no violated restrictions. This can be achieved by propagating the delay along unsatisfied restrictions. If all the nodes are in the tree, then we insert first all the other satisfied restrictions. Violated restrictions, that are not yet in the graph, have to be dropped or we alter the departures, such that we can pick up this restriction too in our graph. The new graph (i.e. the timetable) has only satisfied restrictions; we never include bruised restrictions.

We implemented this graph data structure and the solving strategy in C++. We have results for a sample problem with about 190 nodes and 500 restrictions. As long as the delays are about 5 minutes then we could repair the timetable within one period. But if the delays are about 10 minutes then it depends heavily on the node which is delayed, whether we could balance the timetable or not within one period.