Minimizing delays in a shunting yard

作者：Jaehn Florian^*; Rieder Johannes; Wiehl Andreas

来源：OR-Spektrum, 2015, 37(2): 407-429.

DOI：10.1007/s00291-015-0391-1

• Railway systems
• Shunting yard
• Branch and bound
• Tabu search

We consider an operational process at shunting yards, where freight cars are disassembled and reassembled via a system of tracks and switches to form outbound trains with no restriction on the order of the freight cars. Given are due dates for each outbound train and priority values for its freight cars. Furthermore, the composition and the processing time of each inbound train is part of the input. An outbound train is defined by a set of freight cars taken from one or many inbound trains. In this context, we try to minimize the weighted tardiness of all outbound trains by determining the optimal humping sequence of inbound trains. We show that this problem is NP-hard and we present a simple mixed integer problem formulation. Besides two heuristic approaches and an implementation in CPLEX, the main focus of our single stage shunting problem to minimize weighted tardiness (SSSWT) is on developing an exact branch and bound procedure. Therefore, we present powerful precedence constraints and priority rules to reduce the solution space. Further, we compare the runtime and accuracy of the proposed algorithms with the results of CPLEX optimizer in a computational study.

• 出版日期2015-3