Routing trains through railway stations: Complexity issues

In this paper we consider the problem of routing trains through railway stations. This problem occurs as a subproblem in the project DONS that is currently being carried out under the supervision of Railned and Netherlands Railways. The project DONS involves the determination of the required future capacity of the Dutch railway infrastructure. In this paper we focus on the computational complexity of the problem of routing trains through railway stations. After an extensive description of the problem, we show that only a subset of the sections and routes of a railway station needs to be taken into account. Then we show that the routing problem is NP-complete as soon as each train has three routing possibilities. However, if each train has only two routing possibilities, then the problem can be solved in an amount of time that is polynomial in the number of trains. Furthermore, if the layout of the railway station is fixed, then the latter is also the case for the problem of finding an assignment of a maximum number of trains to routes that is feasible from a safety point of view. This result can be extended to the case where coupling and uncoupling of trains, certain service considerations, and a cyclic timetable have to be taken into account.