A 0,1 Linear Programming Approach to Deadlock Detection and Management in Railways

In railway systems, a deadlock occurs when trains accidentally occupy positions that prevent each other from moving forward. Although deadlocks are rare events, they do occur from time to time, requiring costly recourse actions and generating significant knock-on delays. In this paper, we present a noncompact 0,1 linear programming formulation and a methodology for discovering (possibly future) deadlocks and the subsequent implementation of optimal recovery measures. The approach is implemented in a tool to dispatch trains in real time developed in cooperation with Union Pacific (UP) and currently in operations on the entire UP network. Funding: This work was partially funded by Europe’s Rail, Flagship Project MOTIONAL [Action Horizon JU Innovation, Project 101101973]. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the Europe’s Rail Joint Undertaking. Neither the European Union nor the granting authority can be held responsible for them. The project “FP1-MOTIONAL” is supported by the Europe’s Rail Joint Undertaking and its members. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2024.0521 .