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

Negin Enayaty Ahangar, Kelly M. Sullivan, Shantih M. Spanton and Yu Wang

IISE Transactions, 2024, vol. 56, issue 2, 172-185

Abstract: 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.

Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2023.2203748 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:56:y:2024:i:2:p:172-185

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2023.2203748

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().