Solving the train scheduling problem in a main station area via a resource constrained space/time integer multicommodity flow

Abstract

This master thesis addresses the problem of generating conflict-free train schedules in main station areas (typically considered the capacity bottlenecks in rail networks). Two trains are in conflict if they use the same topology resource element within a certain safety time span. A typical model for this problem is the conflict graph, where each possible time/space itinerary for one train corresponds to a vertex and an edge connects two vertices if they are in conflict or belongs to the same train. Thus, a conflict free schedule corresponds to an independent set of maximum cardinality in the conflict graph.

This work proposes here an alternative model based on an integer multicommodity flow formulation that incorporates the railway topology, as well as passing times and speed profiles of the trains. The resulting integer program is then solved with a commercial solver.
Notice, that the standard LP relaxation of the conflict graph formulation is usually weak. In contrast, by considering all trains simultaneously (instead of just two) for each resource, we algorithmically generate substantially stronger constraints. Tests with data from Berne (Switzerland) show that with this model it is possible to find feasible solutions within seconds even for cases in which the conflict graph approach fails.

Literature

• Solving the train scheduling problem in a main station area via a resource constrained space-time integer multi-commodity flow G. Caimi, M. Fuchsberger, F. Chudak 2006/2007