Simultaneous scheduling of railway maintenance and trains : Modelling and solving train interactions close to a maintenance operation

Abstract: Rail transport plays a key role in the mobility of passengers and goods. It is expected to grow the decarbonization of society. In that context, it is important to use the railway network efficiently, and jointly planning trains and network maintenance allows for better use of resources. This master thesis focuses on the integration of regular maintenance slots in a timetable while minimizing the impact on rail traffic and maintenance costs. The problem has been modeled as a mixed-integer linear programming formulation. First, we study the modeling of the interactions between trains, and we focus on the possible conflicts due to maintenance slots. Two approaches are compared: an aggregated one and a detailed one close to maintenance slots. We analyze the computation time and the quality of the solution on a real-life timetable with different maintenance scenarios. The results show while the aggregated approach is useful for finding reasonable slots, the detailed one is necessary to achieve high quality solutions with minimal traffic impact. In the second step, we reduce the computation time by using construction heuristics. We use a greedy algorithm to find realistic maintenance slots combined with a train-fixing heuristic. Our experiments have shown that theses heuristics reduces significantly the computation time (with more than 50% on the considered test instances) for solutions of equivalent quality. Limitations of the model and improvements are discussed.