Optimization methods for the Train Unit Shunting Problem

We consider the Train Unit Shunting Problem, an important planning problem for passenger railway operators. This problem entails assigning train units from shunting yards to scheduled train services in such a way that the resulting operations are without conflicts. The problem arises at every shunting yard in the railway network and involves matching train units to arriving and departing train services as well as assigning the selected matchings to appropriate shunting yard tracks. We present an extensive comparison benchmark of multiple solution approaches for this problem, some of which are novel. In particular, we develop a constraint programming formulation, a column generation approach, and a randomized greedy heuristic. We compare and benchmark these approaches with two existing methods, a mixed integer linear program and a two-stage heuristic. The benchmark contains multiple real-life instances provided by the Danish State Railways (DSB) and Netherlands Railways (NS). The results highlight the strengths and weaknesses of the considered approaches.