Large-Scale, Passenger Oriented, Cyclic Railway Timetabling and Station Platforming and Routing

Abstract

The two topics of this thesis are macroscopic railway timetabling and station
platforming and routing. These problems are challenges that are faced by all
railway infrastructure companies. This thesis was carried out in cooperation
with Infrabel, the Belgian railway infrastructure manager.

(1) Macroscopic Cyclic Timetabling of Entire Countries

In the macroscopic Train Timetabling Problem (TTP), the goal is to obtain,
for each train and for each station it visits, an arrival and a departure time.
Sufficient time should be provided for trains to ride from one station to the
next. In stations, trains that stop should be allowed a minimal stop time, so
that passengers can board, transfer or leave. Of course trains cannot collide
on the same track and should even be separated by typically 3 minutes for
safety reasons. No commercial software tools exist yet that automatically

solve this problem. Over the last decennia, research at universities has led
to automatically constructed ’draft’ timetables for the Netherlands, but these

timetables still lack robustness against small recurrent delays. A timetable for
the 37 trains of the Berlin underground was also constructed automatically,
but also lacks robustness. For Belgium, about 200 hourly trains have to be
planned, but Infrabel additionally requires that the timetable implies minimal
passenger travel time in practice. This implies it will be robust. This was a new
modelling and computational challenge. This time, which has to be minimised,
includes journey time and small recurrent delays. In our latest paper, we also
include excess journey time, which is the sum of waiting time at departure and
at arrival.

We are able to generate a timetable for all 196 hourly Belgian passenger trains
from the 2013 timetable in a computation time of about 2 hours. Assuming
common delays, the reduction of expected passenger time is 3.8% and the
average missed transfer probability goes down from more than 10% in the
original timetable to less than 3% in our timetable. Additionally, we also
optimised the Danish timetable with 88 trains in about one hour, with a
reduction of 2.9% of expected passenger time and reduced percentages for the
probability of missing a transfer that are similar to the Belgian case.

(2) Station Train Platforming and Routing

For the problem of station platforming and routing, the arrival and departure
times of trains are considered as given by the timetable. The sequential planning
of the timetable and then station platforming and routing corresponds to the
process currently used at Infrabel and almost all other railway companies. The
challenge is then, to assign, per station, a platform track to each train such that
no two trains are using the same infrastructure element at any time. This Train
Platforming Problem (TPP) has been intensively studied and solved during
the last decennia. Computation times are of the order of seconds per station.
However, realisation of these automated methods at railway companies or into
commercial tools for the railway industry has been limited. We solve this by
developing and integrating a platforming tool at Infrabel.

This tool produces a picture showing the current - manually made - platforming
plan and indicates any conflict between any train pairs in the station area.

We then generate an assignment without conflicts, of as many trains to platforms
as possible. Sometimes, not all trains can be assigned to platform tracks andonly a partial solution is given. This means that in practice, some trains cannot
be assigned or otherwise the arrival and/or departure times have to be adapted
manually. In the last case the macroscopic timetable also will have to be changed
again. We also produce a picture of our optimised assignment which consistently
shows that indeed, in our solution, there is no single conflict left. We are able
to automatically generate train to platforming assignments for all 530 Belgian
stations in only 10 minutes of optimisation time for all 530 models together.

Both our macroscopic timetabling tool and platforming and routing tool are
integrated and useable at Infrabel.