Optimization of Railway Freight Shunting

Railway freight shunting is the process of forming departing trains from arriving freight trains. The process is continuously performed at rail yards. The shunting procedure is complex and rail yards constitute bottlenecks in the rail freight network, often causing delays to individual shipments. One of the problems is that planning for the allocation of tracks at rail yards is difficult, given that the planner has limited resources (tracks, shunting engines, etc.) and needs to foresee the consequences of committed actions for the current inbound trains. The required schedules highly depend on the particular infrastructure of the rail yard, on the configuration of inbound and outbound trains, and on the business objectives. Thus, new optimization tools as active decision support for the dispatchers are closely tailored to the actual processes. Due to its practical relevance, a broad range of variants has been discussed and solved by the scientific community in recent years. For selected relevant variants, we describe their fruitful relation to scientific research topics such as graph coloring, sequence partitioning, and scheduling, we discuss their computational complexity and approximability, and we outline efficient optimization procedures. In particular, we consider a set of models and algorithms which are applicable in practice, and discuss their application to the shunting yards in Ludwigshafen, Germany and in Hallsberg, Sweden. We also discuss similarities and differences between the different approaches and outline the need for future research.