# A Novel Dynamic Programming Approach to the Train Marshalling Problem

arXiv: https://arxiv.org/abs/1903.08364 · HTML: https://mlsanity.com/paper/1903.08364/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2019.

## Built on by (most cited first, 3 of 3)

- [A Novel Hybrid Heuristic-Reinforcement Learning Optimization Approach for a Class of Railcar Shunting Problems](https://mlsanity.com/paper/2603.05579/) (2026)
- [Reconfiguring Shortest Paths in Graphs](https://mlsanity.com/paper/2112.07499/) (2021)
- [Optimization of the Railcar Assignment Problem Using Zone-based Double Deep Reinforcement Learning](https://mlsanity.com/paper/2608.18442/) (2026)

## Abstract (arXiv)

Train marshalling is the process of reordering the railcars of a train in such a way that the railcars with the same destination appear consecutively in the final, reassembled train. The process takes place in the shunting yard by means of a number of classification tracks. In the Train Marshalling Problem (TMP), the objective is to perform this rearrangement of the railcars with the use of as few classification tracks as possible. The problem has been shown to be NP-hard, and several exact and approximation algorithms have been developed for it. In this paper, we propose a novel exact dynamic programming (DP) algorithm for the TMP. The worst-case time complexity of this algorithm (which is exponential in the number of destinations and linear in the number of railcars) is lower than that of the best presently available algorithm for the problem, which is an inclusion-exclusion-based DP algorithm. In practice, the proposed algorithm can provide a substantially improved performance compared to its inclusion-exclusion-based counterpart, as demonstrated by the experimental results.