Trafikverket faces an increasing number of possessions for maintenance works on their railway lines. During these possessions, railway traffic has to be rescheduled or even rerouted. Similar situations occur during large disturbances. These closures generate much work for planners. To simplify this planning process, we aim to automate the rerouting of freight trains and long-distance passenger trains in Sweden. That problem reduces to finding new train paths for a set of trains. We assume that the existing timetable cannot be modified and that robustness requirements are fixed constraints. 

To develop an algorithm for obtaining these train paths, we split up our problem into two smaller problems. Here, we consider the problem of finding multiple feasible train paths for a specific train. Later, we will use this procedure to develop an algorithm that can insert multiple trains to a timetable by picking conflict-free candidate paths with low cost. While literature on rerouting multiple trains is scarce, the problem of obtaining one train path has been covered in earlier work. To ensure that our procedure is applicable in practice, we pay attention to several details. For example, we avoid conflicts between train paths around stations, which includes forbidding simultaneous arrivals at stations on single-track lines when appropriate. Another example on single-track lines is the small number of blocks. Often, only one block separates two stations, but on longer segments, there could be a few. We make sure to derive realistic headway parameters in these cases. Lastly, we use methods that can also be applied efficiently on larger railway networks.