  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.
