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 and only 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.status: publishe