Shunting of trains in succeeding yards

- A practical sequencing problem from an industrial partner is introduced.
- Three MIP formulations based on classical ideas for sequencing problems are presented and compared with each other.
- The problem at hand is shown to be NP-hard.
- Two heuristic solution algorithms are proposed.
- The MIP formulations have been tested in CPLEX and they are compared to the solution algorithms.

We consider a problem arising in international rail freight transport. At a shunting yard, inbound trains are taken apart by decoupling freight cars, which are then sent through a system of tracks and switching points to form new outbound trains. Each freight car has a designated outbound train, but each outbound train might consist of freight cars going to different final destinations. Therefore, the outbound trains will be decoupled and rearranged in succeeding shunting yards. If two freight cars with the same final destination end up in an outbound train such that a freight car with a different destination is positioned in-between, additional shunting efforts at succeeding shunting yards are involved. Especially if the succeeding shunting yard is located in a foreign country, the rail company will be charged for every shunting procedure performed by the foreign operator. Therefore, such a situation should be reduced as far as possible. To do so, we may determine the shunting sequence of inbound trains. We will show that this problem is NP-hard and various mixed integer programming models are presented and implemented in CPLEX. Further, a heuristic solution algorithm is suggested. The computation time and the quality of the results are compared to the results of the CPLEX optimizer in a computational study.