In:
Operations Research, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 70, No. 4 ( 2022-07), p. 2101-2118
Abstract:
A deadlock occurs when two or more trains are preventing each other from moving forward by occupying the required tracks. Deadlocks are rare but pernicious events in railroad operations and, in most cases, are caused by human errors. Recovering is a time-consuming and costly operation, producing large delays and often requiring crew rescheduling and complex switching moves. In practice, most deadlocks involve only two long trains missing their last potential meet location. In this paper, we prove that, for any network configuration, the identification of two-train deadlocks can be performed in polynomial time. This is the first exact polynomial algorithm for such a practically relevant combinatorial problem. We also develop 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.
Type of Medium:
Online Resource
ISSN:
0030-364X
,
1526-5463
DOI:
10.1287/opre.2022.2283
Language:
English
Publisher:
Institute for Operations Research and the Management Sciences (INFORMS)
Publication Date:
2022
detail.hit.zdb_id:
2019440-7
detail.hit.zdb_id:
123389-0
SSG:
3,2
Permalink
