Lagrangian Relaxation Methods for the Train Unit Shunting Problem

Abstract

Rail transport is one of the most used forms of public transport, and apart from the timetable, effective shunting operations are an important part of operational efficiency and robustness. Trains not used in the timetable are parked at shunting yards, where shunting operations take place, which take 10-50% of trains’ total transit time. Efficient planning of these operations is challenging due to relatively small yards that cannot be expanded easily, since they are located in urban areas. The management of trains outside of the timetable is an NP-hard problem known as the Train Unit Shunting Problem (TUSP). The TUSP concerns the matching, routing, and parking of arriving and departing trains. The current state-of-the-art Local Search (LS) approach is non-deterministic and struggles with the routing aspect of the TUSP. In this thesis, the TUSP is approached from a routing perspective with a deterministic algorithm. We apply Lagrangian Relaxation (LR) methods to the TUSP such that the problem can be split into per-train shortest path problems. Standard LR struggles with solving the TUSP due to symmetry in the trains and in the shunting yards. To address the symmetry, the approach is extended with Augmented Lagrangian Relaxation (ALR) and solved with the Alternating Direction Method of Multipliers (ADMM). Experimental results show that ADMM can be used to solve a somewhat simplified version of the TUSP and outperforms the LS approach on scenarios in which the arrival and departure of trains are more time restricted, i.e., smaller time windows. On larger time windows and for more trains, the LS outperforms the ADMM approach.