ROUTING TRAINS THROUGH RAILWAY STATIONS - COMPLEXITY ISSUES

In this paper we consider the problem of routing trains through railwa y stations. This problem occurs as a subproblem in the project DONS th at 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 t his paper we focus on the computational complexity of the problem of r outing 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 tha t the routing problem is NP-complete as soon as each train has three r outing possibilities. However, if each train has only two routing poss ibilities, 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 pr oblem 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 exte nded to the case where coupling and uncoupling of trains, certain serv ice considerations, and a cyclic timetable have to be taken into accou nt. (C) 1997 Elsevier Science B.V.