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

This article focuses on the detection and management of deadlocks in railway networks, where trains block each other’s movements, causing costly delays. It introduces two novel pure 0,1 integer linear programming formulations—BD_Vall for rapid deadlock detection and BDM_Vall for deadlock management including safe place assignment, which determines optimal locations to hold trains to resolve deadlocks. The models are based on a path-and-cycle formulation of train movements and incorporate routing and scheduling decisions, with constraints ensuring feasibility and avoidance of cyclic conflicts. Implemented within an advanced traffic management system (A-TMS) developed in cooperation with Union Pacific, these formulations outperform previous approaches such as the tick formulation, demonstrating significant computational efficiency on realistic instances derived from the Union Pacific network. The paper also discusses algorithmic strategies like delayed row generation to handle large constraint sets and heuristic identification of “bubbles” (subnetworks with trains at risk of deadlock) to maintain real-time applicability.