On shunting over a hump

Abstract. We consider the situation of rearranging freight trains in a shunting yard with a hump and several tracks. Here, an elementary shunting operation is to push a all cars of one track over the hump. On the way back to the tracks the cars can be guided individually to an arbitrary track. The goal is to create one or several trains that have their cars in a particular order. We measure the efficiency of a shunting plan by the number of elementary shunting operations, and to a lesser extent by the total number of car movements. We find optimal shunting operations in the following situations: – The incoming trains are unsorted and the shunting yard has sufficiently many tracks but the length of the tracks is limited (capacities). – The order of the cars in a single incoming train is given, the tracks of the shunting yard are sufficiently long, but there is only a limited number of tracks. In contrast, we show that the following problems are N P-complete: – There are several incoming trains and for each the order of the cars is given, but the order in which to start shunting the trains can be chosen. – There is one train with given order of the cars, and the lengths of the tracks is limited. These results are based on expressing the shunting task as finding a suitable set of codes. The results will perhaps not solve the practical problem directly, but rather provide some first structural insights and complexity limits that can guide the search for practical algorithms.