The Tick Formulation for deadlock detection and avoidance in railways traffic control. (March 2021) - Sasso, Veronica Dal; Lamorgese, Leonardo; Mannino, Carlo; Onofri, Andrea; Ventura, Paolo
Abstract: Wrong dispatching decisions may lead to deadlocks, where trains reciprocally block resources necessary to reach their destinations. It is crucial to develop tools to detect such potential deadlocks on time, in order to reverse the decisions previously taken by dispatchers or to take recovery actions. In this paper we present a new 0, 1 linear formulation for detecting deadlocks and optimally park the involved trains to reduce congestion around the affected area. We discuss computational results on some realistic randomly generated instances to show the validity of the approach, as well as its limits. Graphical abstract: Image 1 Highlights: Deadlock detection is crucial: deadlocks are costly to be resolved. Tick formulation can detect deadlocks and anticipate if a move causes a deadlock. Safe Places Assignment is an extra feature to enforce low levels of congestion.