Solution Approaches to the Train Timetabling Problem


Thomas Schlechte, Zuse Institute Berlin

Title Solution Approaches to the Train Timetabling Problem
When 05.03.2008, 15.00 Uhr
Where Lecture Room Informatik 7
Abstract This talk focuses on the optimization models, algorithmic approaches and features implemented in TS-OPT – a Train Schedule Optimizer developed at Zuse Institute Berlin.

The train scheduling problem, also known as the train timetabling problem (TTP), addresses one of the main decisions of a railway network operator and provider: to determine, for a given set of train request routes, a conflict free train timetable of maximum utility or profit.

The problem is a prime example for a combinatorial optimization problem. Complex interactions between trains on tracks and inside stations let the solution space become opaque and gigantic. Sophisticated approaches are needed to handle the complex railway system and identify the crucial decision to make.

The talk is organized as follows, first we describe a macroscopic railway world, defining headway conflicts, station capacities w.r.t. the definition of aggregated standard train types. Second input of the problem is a set of train requests w.r.t. the macroscopic infrastructure. Each train request specifies time windows for arrival and departure stations, obligatory stops, desired traveltimes etc.; leading to a standardized formulation of the train timetabling problem. Then we recall several linear and integer programming formulations of TTP from the literature and present some details on the used and developed algorithms implemented in TS-OPT.

Finally, we present some computational studies on several macroscopic real-world data sets, which are provided by the data library TTPLib, to show the possibilities, features and limitations of TS-OPT.

Slides download