The Shunt Routing Problem (SRP) is an important logistic problem at nearly every railway station. It is a subproblem of an even bigger train scheduling problem, the Train Unit Shunting Problem (TUSP). The objective of SRP is to schedule conflict-free routes between the platforms and the yards, for currently non-operational trains that have completed their current journeys and have not yet commenced the next one.
We developed a Constraint Programming (CP) model for the Shunt Routing Problem at NS. The model is intended to replace the current algorithm for constructing the initial solution for the Local Search, addressing the TUSP at NS. The model incorporates all essential feasibility requirements and produces conflict-free solutions, in contrast to its forerunner. Moreover, it can be applied to any instance and station layout.

Initially, the model exhibited an average performance of 7-8 minutes on a real-life instance at Enkhuizen station. We managed to enhance the model and reduce the computation time to less than a second. The key improvements were achieved by changing the solver search strategy, imposing additional search guidelines, or further restricting the domains of influential variables. During experimentation, an optimized second version of the model was proposed.
The evaluation undoubtedly confirmed that it outperforms the first version.

Both versions of the model, without any additional enhancements, perform exceptionally well on a second real-life instance at Amersfoort station, solving it in milliseconds. Even with a considerable number of additional routes, the performance of the second version remained reasonable, with a computation time of 18 seconds.

A final experiment revealed the remarkable performance of Gecode, achieving computation time in milliseconds with the second version of the model implemented for Enkhuizen in MiniZinc. This performance is an order of magnitude faster compared to the default performance of Google OR-Tools on Enkhuizen with the second version.