Offset optimization of a time discretization approach for train scheduling in station areas

Stefan Wörner, Term project, Spring 2009

Supervisor: Gabrio Caimi, Marco Laumanns

Keywords:
Train scheduling problem, Time discretization, Station area, Offset optimization

Abstract

The goal of the present thesis is to simplify the generation of conflict-free train schedules in station areas. In the underlying setup a standard time discretization approach is used. However, the possibility of introducing offsets to enlarge the space of feasible schedules was not discussed so far and is the topic of this work. Therefore, the considered trains are grouped according to their origin/destination and speed profile. A discrete set of periodic enter/exit times is assigned to each train group. The periodicity is fixed throughout the station area. However, the offsets of the discretization can be chosen independently for each train group. A model is provided which allows the evaluation of particular offsets. In addition, it is shown that the problem of finding optimal offsets cannot be solved for real scenarios in general. Therefore, a two step heuristic approach is developed. The complete approach is tested with real data for the station area of Lucerne and the results are validated by practitioners of Swiss Federal Railways (SBB).