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

Author(s):

Frank Fischer
Christoph Helmberg

Title:

Dynamic Graph Generation for Large Scale Operational Train Timetabling

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 10, 2011

Mathematics Subject Classification:

90C90	[]
90B10	[]
90B06	[]
90C35	[]
90C06	[]

Abstract:

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.

Keywords:

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

Language:

English

Publication time:

07/2011