Deadlock Detection on a Railway Line

In the context of rail transportation deadlocks occur when the placement of two or more trains prevents each train from moving forward. Recovering from deadlocks requires complicated train movements and causes huge delays; therefore detecting and avoiding deadlocks are important activities in railway management, especially for single-track railway lines. In this work we study the problem of early detection of deadlocks on a railway line: given a line layout and an initial placement of trains on the line, the problem consists in determining whether it is possible to move each train towards the line endpoint that they are facing or if, vice versa, any possible sequence of train movements will eventually create a deadlock. We first provide necessary and sufficient conditions for the existence of a solution for some special cases. Then we propose a combinatorial and exact algorithm for the general case. Although our algorithm runs in polynomial time in some meaningful special cases, the existence of a polynomial algorithm for the general case of this problem is still an open question