Frank Fischer, Christoph Helmberg: Dynamic Graph Generation for Large Scale Operational Train Timetabling
- Dynamic Graph Generation for Large Scale Operational Train Timetabling
- Electronic source:
- Preprint series:
- Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 10, 2011
- Mathematics Subject Classification:
90C90  90B10  90B06  90C35  90C06 
The aim of operational train timetabling is to find a conflict free
timetable for a set of passenger and freight trains with predefined
stopping time windows along given routes in an infrastructure
network so that station capacities and train dependent running and
headway times are observed. Typical models for this problem are
based on time-discretized networks for the train routes coupled by
conflict constraints. They grow very fast for large scale
instances and quickly lead to intractable models.
Motivated by the observation that relaxations mostly use a narrow corridor inside such networks, we develop a general dynamic graph generation framework in order to control this size even for infinite time horizons. It can be applied to time-discretized networks modelling the routing of objects through capacity restricted handling stations with the property that early paths in the network are preferred. Without sacrificing any information compared to the full model, it includes a few additional time steps on top of the latest arcs currently in use. This ``frontier'' of the graphs can be extended automatically as required by solution processes such as column-generation or Lagrangian relaxation. The corresponding algorithm is efficiently implementable and linear in the arcs of the non-time-expanded network with a factor depending on the basic time offsets of these arcs. We give some bounds on the required additional size in important special cases.
With this dynamic graph generation technique we are able to solve relaxations of large scale real-world train timetabling problems of the German railway network of Deutsche Bahn. By enhancing the informativeness of the relaxation by convex load-balancing functions that distribute the train load on single tracks, it forms the basis of a dynamic rolling horizon approach to finding integer solutions of good quality.
- Publication time: