Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Frank Fischer, Christoph Helmberg: Dynamic Graph Generation for Large Scale Operational Train Timetabling

Frank Fischer, Christoph Helmberg: Dynamic Graph Generation for Large Scale Operational Train Timetabling

Frank Fischer
Christoph Helmberg
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.

time-expanded networks, column generation, Lagrangian relaxation, large scale
Publication time:


  • Hilfe für Lena

    Tochter von ehemaliger TU-Mitarbeiterin benötigt Stammzellenspende – Typisierungsaktion am 21. April 2018 im Büroland Chemnitz für Personen zwischen dem 18. und 40. Lebensjahr …

  • Grenzenlose Leichtbau-Forschung

    Sachsens Ministerpräsident Michael Kretschmer: „Bundesexzellenzcluster MERGE der TU Chemnitz setzt mit zweiter Brücken-Konferenz wichtiges Statement für grenzübergreifende Wissenschaftsvernetzung." …