Train scheduling in a compensation zone

Stefan Ravizza, Term project, Autumn 2007

Supervisors: Gabrio Caimi, Martin Fuchsberger

A compensation zone is the region connecting two main station areas and consists of one line with a simple track topology, usually one or two parallel tracks with some small stations and few switches. As this zone has small traffic density, time reserves in the running time of trains can be introduced to increase timetable stability without creating capacity bottlenecks. This leads to a large variety of speed profiles for the train to connect the two main stations.

An extension of the method called Resource Tree Conflict Graph (RTCG) is developed. RTCG is an exact method for conflict-free train scheduling, tough it is not designed to deal with different speed profiles. In this work an algorithm for generating a set of feasible speed profiles is produced, and each profile is attributed a measure of quality. The method is basically a tree search: at each place where speed change is allowed it tests different possibilities retaining those which lead to a feasible speed profile. The RTCG model was then augmented with this speed profile generator and the constructed MIP is solved with a commercial solver in order to optimize the quality of the assigned speed profiles in the conflict-free solution.

Computational results for a line in central Switzerland are presented. The method works well for small instances up to 15 km, tough it is not adequate for larger instances, as size and computation times grow exponentially.