Periodic Time Tabling: Models, Algorithms, and Applications

railway company (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 time tabling. 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. We will also report on computational experience with these
approaches on real life data and discuss extensions of the model to
symmetric periodic timetables and line planning.

The lecture is based on joint work with Christian Liebchen.