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.