Easy Cases of Deadlock Detection in Train Scheduling

• 成果类型: Article
• 署名作者: Dal Sasso, Veronica; Lamorgese, Leonardo; Mannino, Carlo; Tancredi, Antonio; Ventura, Paolo
• 署名单位: SINTEF; University of Oslo; Consiglio Nazionale delle Ricerche (CNR)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2283
• 发表日期: 2022
• 关键词: Railways; deadlocks; train scheduling

摘要

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.