Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation

Frank Fischer, Christoph Helmberg, Jürgen JanßEn & Boris Krostitz
The train timetabling problem considered is to find conflict free routes for a set of trains in a given railway network so that cer- tain time window conditions are satisfied. We deal with the very large scale problem of constructing such timetables for the German railway network. A number of restrictions on different train types like freight trains or passenger trains have to be observed, e.g., sequence dependent headway times, station capacities, and stopping times....