Recent Advances in Periodic Railway Timetable Optimization

The timetable is the heart of a public transportation system. It does not only communicate the service to customers, but also has a large impact on the outcome of subsequent cost-sensitive planning steps, e.g., vehicle and crew scheduling. Moreover, it is often necessary to modify timetables to different extents due to planned construction sites, so that timetabling is a frequent and fundamental planning task. Many public transportation networks are operated in a periodic manner. It is therefore of interest to design and to optimize periodic timetables. The main mathematical model for this purpose is the Periodic Event Scheduling Problem (PESP). We will present several recent successes in periodic timetabling:

* Geometric Methods:  We will outline tropical neighborhood search, a local heuristic based on the geometric properties of the space of feasible timetables, which proved to be valuable for PESP benchmark instances. Moreover, we will demonstrate a connection between Benders decomposition for PESP and the zonotope generated by feasible cycle offsets.

* Cutting Planes: Good dual bounds for PESP are notoriously hard to obtain. We investigate the split/MIR closure of the cycle-based MIP formulation of PESP, and show that it is given by so-called flip inequalities. We further discuss how split cuts can be separated in theory and practice, and that the split closure is stable with respect to reformulating the MIP.

* Turn-Sensitive Infrastructure-Aware PESP: Although PESP is quite versatile, it has a limited capability of modeling safety distances, so that conflict-free timetables cannot be guaranteed. This can be resolved easily when dwelling times are rather short, but fails when trains occupy parts of the infrastructure for comparably long times, e.g., when turning. We show how to integrate conflict-freeness into PESP, and showcase this by means of a real-world application for construction sites on the S-Bahn Berlin network.

About Niels Lindner

Niels Lindner is a visiting professor at the Institute of Mathematics at Freie Universität Berlin and the head of MobilityLab in the Department Network Optimization at Zuse Institute Berlin. His research interests lie in discrete optimization and its intersections with algebra and geometry. In particular, he actively works on mathematical optimization for public transport, including timetabling, railway track allocation, passenger routing, network design, line and fare planning, vehicle and crew scheduling.