Algorithmic decision support for train scheduling in a large and highly utilised railway network

This thesis addresses the problem of constructing train schedules, in particular for large and highly utilised railway networks. In the thesis, a comprehensive approach from the commercial description of intended train services to a conflict-free detailed schedule for a whole day is developed. The methodology follows a divide-and-conquer strategy based on three description levels: the service intention, the macroscopic timetable, and the microscopic schedule. The levels are interfaced in such a way that planners have the possibility of intervening into the specifications on every level, and enabling a feedback loops for testing different alternative scenarios.
The starting point of the approach is the construction of an appropriate structure for describing the intended train services, including periodicity information. This partial periodic Service Intention (ppSI) contains the commercial offer that a railway company would like to tender to the customers during a day. The developed ppSI can describe commercial railway offers with partial periodic structure in a compact form and can exploit these effectively in the train scheduling process. This is done with an equivalent projection onto a single period time, resulting in an augmented periodic problem. ThlS augmented periodic timetabling problem is then solved first 9lobally on an aggregated topology with a simplified safety model (macroscoplC level), and subsequently, locally refined by considering more details of the railway infrastructure and train dynamics (microscopic level). Finally, the generated periodic conflict-free train schedule is rolled out over the complete day to create a conflict-free production plan.
The macroscopic level focuses on global interdependencies over the entire network for generating the most important properties of the timetable. A well known model for this description level is the periodic Event scheduling problem (PESP). In this thesis, an extension called Flexible Periodic Event scheduling problem (FPESP) is introduced and applied, allowing for time slots for each event instead of fixed times. Moreover, an extension of the FPESP model is proposed, the Flexbox model, which is a further generalisation of the FPESP that allows to make use of natural dependencies among events in the service intention.