Moving Trains like Pebbles

Abstract

The Train Unit Shunting Problem concerns the parking of trains outside their scheduled use on so-called shunting yards. This is an NP-hard problem, and the current algorithm used by the Netherlands Railways cannot detect whether an instance is infeasible. So, infeasible instances can cause needlessly long computation times. Therefore, this paper fills the gap by providing novel approaches to determine the feasibility. For this, the Pebble Motion problem is considered which moves pebbles from their starting node to their goal node in the graph, such that no two pebbles occupy a node at the same time. A variant of the Pebble Motion problem is proposed to model the Train Unit Shunting Problem, where train units are represented by pebbles and the arrival and departure of train unit combinations are also included. This paper specifically looks at dead-end track shunting yards, as they can be abstractly represented by trees, such that trains arrive and depart at the root node. Furthermore, trains cannot be reallocated between arrival and departure in the tree, since reallocation in practice is a very costly process as moves need to be performed by a small set of drivers. The conditions for realizing the departure order of trains are studied, and an efficient method to (partially) determine the feasibility of problem instances is given, which can find the minimal number of tracks required to park the trains. Furthermore, a special case with tracks of length two is shown to be polynomially solvable, while another subset of problem instances with tracks of length six or more is demonstrated to be NP-complete.