Optimise switching in flat rail yards: integer linear models and a greedy randomised adaptive search procedure

This paper investigates the problem of switching wagons in flat rail yards to form both an outbound train and additional blocks. We present a new encoding scheme for the studied problem in both stub-yards and through-yards, and formulate the studied problem as mixed integer linear models. Then, we reformulate our problem into a shortest-path problem in a huge hierarchical directed graph. To solve practical-size problem instances, we customise a greedy randomised adaptive search procedure, wherein a greedy randomised algorithm computes an initial solution quickly, which is further improved by a large neighbourhood search heuristic. Finally, we demonstrate the effectiveness and efficiency of our methods by solving a set of instances. Computational results reveal that our method is capable of computing good solutions for practical-size instances within a reasonable computation time. We also provide decision suggestions to support decision-making of rail staff by comprehensively analysing the features of our solutions.