Shunting operations at flat yards : Retrieving freight railcars from storage tracks

In this paper, we study the railcar retrieval problem (RRT) where a specified number of certain types of railcars has to be withdrawn from the storage tracks of a flat yard. This task arises in the daily operations of yards belonging to a workshop for railcar maintenance. The objective is to minimize the total costs of shunting, i.e. minimizing the usage of shunting engines. We describe the RRT formally as a mixed-integer program and prove it to be NP-hard in the general case. In addition, we analyze several heuristics for solving the problem and provide their worst case performance guarantee. Furthermore, computational experiments are conducted that show the average performance of the introduced heuristics and compare them to the optimal solution provided by the mixedinteger program. The results show that both, the heuristics and the exact formulation come to solutions for realistically-sized instances in running times acceptable to practitioners, leading to the advice that optimization should be implemented in practice in order to save valuable resources