Algorithms and complexity results for the single-cut routing problem in a rail yard

Rail yards are facilities that play a critical role in the freight rail transportation system. A number of essential rail yard functions require moving connected cuts of rail cars through the rail yard from one position to another. In a congested rail yard, it is therefore of interest to identify a shortest route for such a move. With this motivation, we contribute theory and algorithms for the Single-Cut Routing Problem (SCRP) in a rail yard. Two key features distinguish SCRP from a traditional shortest path problem: (i) the entity occupies space on the network; and (ii) track geometry further restricts route selection. To establish the difficulty of solving SCRP in general, we prove NP-completeness of a related problem that seeks to determine whether there is space in the rail yard network to position the entity in a given direction relative to a given anchor node. However, we then demonstrate this problem becomes polynomially solvable-and therefore, SCRP becomes polynomially solvable, too-for Bounded Cycle Length (BCL) yard networks. We formalize the resulting two-stage algorithm for BCL yard networks and validate our algorithm on a rail yard data set provided by the class I railroad CSX Transportation.

Automated summary

Rail yards are critical for freight rail transportation, and finding the shortest route for moving connected cuts of rail cars in congested yards is important. We propose theory and algorithms for the Single-Cut Routing Problem (SCRP) in rail yards, which is different from traditional shortest path problems due to space occupation and track geometry restrictions. We prove the NP-completeness of a related problem and demonstrate its polynomial solvability for Bounded Cycle Length (BCL) yard networks. We formalize a two-stage algorithm for BCL yard networks and validate it using data from CSX Transportation.