Single-stage shunting minimizing weighted departure times

• We introduce a practical problem arising at shunting yards.
• An analysis of the problem concerning complexity and optimality criteria is presented.
• Exact and heuristic algorithms are proposed.
• We evaluate the performance of the algorithms and a MIP formulation in numerical tests.

In a traditional rail-freight hump yard, a huge number of freight cars are perpetually shunted to form outbound trains. In order to transport each car to its destination, the inbound trains are decoupled and disassembled into individual cars, which are then moved to one of the several classification tracks where they are reassembled to form new outbound trains. Motivated by the situation at Munich shunting yard, we consider a traditional single-stage shunting problem, where freight cars form new, single-destination trains with an arbitrary freight car order. There might be multiple trains to one destination so that the assignment of freight cars to outbound trains is determined by the sequence of inbound trains to be processed. Each freight car has a priority value and the objective is to minimize the weighted sum of priority values of outbound trains multiplied by the time units that have elapsed until departure. First, we elaborate a MIP formulation and then we provide a lower bound and develop precedence relations. Furthermore, we present heuristic procedures as well as a branch and bound approach. The paper concludes with computational results comparing the proposed algorithms with CPLEX.