Resolving Infeasibilities in Railway Timetabling Instances

One of the key assumptions of timetabling algorithms is that a solution exists that meets the pre-specified constraints, like driving times, transfer constraints and headway constraints. If this assumption is satisfied, in most cases a timetable can be found rapidly. Nowadays, railways are being used more intensively, which leads to a higher utilization of the network. Due to this increased utilisation, capacity conflicts occur, so that no feasible solution to the timetabling models can be found, without making subtle but non-trivial changes to the initial input. Resolving these conflicts is essential for railway companies with high utilization of infrastructure. In this paper, we consider infeasible timetabling instances together with a list of allowed modifications of the constraints. We iteratively identify local conflicts in these instances and resolve them by adapting some of the constraints, until there are no more conflicts. The adaptations of the constraints are changes in the right-hand sides that we try to make as small as possible but that resolve the infeasibility. We empirically show that our method can be improved by enriching the initial minimal conflicts found with more constraints. In order to keep the problems tractable, an iterative procedure is used to find solutions to subproblems corresponding to conflicts in the complete timetabling instance. In a case study on instances from the Dutch railway network, we show that these instances can be made feasible within a few minutes.