| [home] - [up] |
Abstract: The prototype of a periodic timetable is the train schedule of the DB (at least in large parts). It is constructed from a given set of lines, must respect many side constraints that arise e.g. from safety conditions such as bidirectional traffic on a single track, and aims at minimizing criteria such as total passenger waiting times due to changeovers or rolling stock.
This lecture will give an introduction into the theoretical background and the available algorithmic tools for timetable generation. The main model is the periodic event scheduling problem (PESP) introduced by Serafini and Ukovich, which interprets periodic timetables as periodic potentials of a digraph. This model contains graph coloring as a special case, which illustrates the computational difficulty of periodic timetabling. Periodic potentials are closely related to the cycle space of the underlying graph, and finding a "good" basis of this space is, together with cutting planes, one of the most important techniques for reducing the feasibility domain and finding good solutions.
A second lecture by Christian Liebchen will deal with more specific algorithmic tasks and will also illustrate computational experience on real life data.
Colloquium - 16:00
Abstract: The model for periodic timetabling that gets introduced in the preceeding lecture by Rolf Möhring is the basis for this talk as well. This colloquium will point on two important special situations in periodic timetabling.
Consider the most-frequented track of the Berlin fast train network, from Lichtenberg to Friedrichsfelde Ost. During the morning's peak hours, eight trains must be scheduled within 20 minutes, and a safety distance of two an a half minutes has to be ensured. Hence, almost the complete timetable is determined, if the sequence, or ordering, of the lines is fixed. In this situation of sequencing, we did discover a powerful source for valid inequalities: a polynomial number of them suffices for explicitly cutting off exponentially many infeasible integer points. This is due to the fact that we discovered the PESP to be a generalization of the Linear Ordering Problem.
Another important point is that routing the rolling stock can only be as good as the timetable permits. Hence, one is interested in constructing timetables that allow good vehicle routings and require only few rolling stock. An exact model will be proposed, but it contains a quadratic objective function over a mixed integer programming problem. However, a simple heuristic that performs well in practice can be derived. Moreover, calculating the number of vehicles required for serving a fixed periodic timetable for an abstract period is very simple: it can be done by a greedy approach.
Parts of the results presented in the talk stem from a joint work with Leon Peeters, Rotterdam.