Solving the train marshalling problem by inclusion–exclusion

In the Train Marshalling Problem (TMP) the cars of a train having different destinations have to be reordered in such a way that all the cars with the same destination appear consecutively. To this aim the cars are first shunted on k auxiliary rails, then the sequences of cars present on the different rails are reconnected one after the other to form a new train. The TMP is the problem of minimizing the number k of auxiliary rails needed to obtain a train with the required property. The TMP is an NP-hard problem. Here we present an exact dynamic programming algorithm for the TMP based on the inclusion–exclusion principle. The algorithm has polynomial space complexity and time complexity that is polynomial in the number of cars, exponential in the number of destinations. This shows that the TMP is fixed parameter tractable with the number of destinations as parameter.