k-Shortest routing of trains on shunting yards

We consider the problem of designing algorithmic support for k-best routing decisions in train shunting scheduling. A study at the Netherlands Railways revealed that planners like to interact with the solution process of finding suitable routes. Two types of interaction were required: the possibility of assigning specific tracks to a route and of preventing the assignment of specific tracks to a route. The paper develops insights in the structure of the cost matrix in this k-best optimization problem. These dominance results are used in a two stage k-shortest path algorithm to support this task of the shunting planners. The solution approach determines the optimal sequence of the tracks that manually have been added to the route and determines the k shortest paths in this network. The approach is implemented in a prototype of a support system for shunting planners. The required calculation times for practical instances of the problem with varying numbers of alternative solutions (k a parts per thousand currency sign 8) and intermediate tracks (m a parts per thousand currency sign 5) are between 0.1 and 1.4 s. These calculation times are acceptable to provide adequate support to the planners of these shunting yards.