Easy Cases of Deadlock Detection in Train Scheduling

Abstract

In a railway network, a deadlock occurs when two or more trains are preventing each other from moving forward by each occupying the tracks required by the other. Deadlocks are rare but pernicious events in railroad operations, and, in most cases, they are caused by human errors and involve only two extra-long trains missing their last potential meet location. In “Easy Cases of Deadlock Detection in Train Scheduling,” V. Dal Sasso, L. Lamorgese C. Mannino, A. Tancredi, and P. Ventura prove that the identification of two-train deadlocks can be performed in polynomial time. Moreover, they also present a pseudo-polynomial but efficient oracle that allows real-time early detection and prevention of any (potential) two-train deadlock in the Union Pacific (a U.S. class 1 rail company) railroad network. A deadlock prevention module based on the work in this paper will be put in place at Union Pacific to prevent all deadlocks of this kind.