Optimisation models for train timetabling and marshalling yard planning

Railways provide high capacity, safe and energy efficient transportation of goods and passengers. However, railway transportation also suffers from intrinsic restrictions and the effectiveness and efficiency of the transportation depend on the railway actors’ ability to solve a set of hard and interconnected planning problems. As the digitalisation of rail-way planning advance, compute-intensive decision support tools could be implemented to support the planners’ work. Two support functions that would be useful are automatic generation of new plans and optimisation of existing plans. In this thesis, mathematical models are developed and analysed for optimisation of (1) train timetables and (2) marshalling yard plans. The aim is to investigate the feasibility and potential of using mixed integer linear programming (MILP) models to solve these two planning problems. To this aim, requirements and planning goals are identified and modelled as mathematical constraints and objective functions. The resulting mathematical models are then tested on realistic problem instances, and the execution times and optimised plans are analysed to determine if the mathematical models could be useful in practice. The thesis contributes with an analysis of the definition of ”good” in a railway timetable setting from the perspective of an infrastructure manager, a novel mathematical model for timetable planning, an optimisation-based heuristic for decreasing execution times and last but not least an analysis of the potential of using optimisation to enable a new type of annual capacity allocation. For marshalling yard planning, the thesis contributes with an analysis of three different mathematical models for planning one of the sub-yards of a marshalling yard, and with an extended, more comprehensive, mathematical model that can be used to plan two sub-yards. Further, a heuristic is developed for the more comprehensive problem, and the effects of optimising two sub-yards rather than one are analysed. The overall conclusion is that MILP models can contribute to improved railway planning. By using MILP optimisation, more effective plans can be made faster. However, more research is needed to reach the full potential of mathematical optimisation for railway planning problems, in particular when it comes to user experience and user interaction, but also to further decrease the execution times and extend the problem scope that can be handled. This thesis consists of two parts. The first part introduces and summarises the research. It provides background knowledge on the two planning problems as well as on mathematical optimisation, and also present the research framework and some overall conclusions and suggestions for future work. The second part of the thesis consists of five appended papers, three on train timetabling and two on marshalling yard planning