To main content

Easy Cases of Deadlock Detection in Train Scheduling

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.
Read the publication

Category

Academic article

Language

English

Author(s)

  • Veronica Dal Sasso
  • Leonardo Lamorgese
  • Carlo Mannino
  • Antonio Tancredi
  • Paolo Ventura

Affiliation

  • SINTEF Digital / Mathematics and Cybernetics
  • Italy
  • National Research Council
  • University of Oslo

Year

2022

Published in

Operations Research

ISSN

0030-364X

Volume

70

Issue

4

Page(s)

2101 - 2118

View this publication at Norwegian Research Information Repository