An exact approach to the flat shunting problem with a focus on car movement cost optimization

Flat shunting is a classical railway yard operation that aims to rearrange a given sequence of railcars into a desired sequence by using a shunting engine and a set of shunting tracks. The operation considered in this study is a one-end push–pull process, which is particularly relevant when an initial classification or drop-off process cannot directly form the target outbound order. Compared to train timetabling or routing problems, this microscopic operational task is difficult to handle both practically and theoretically, as the shunting tracks have a strict first-in-last-out (FILO) requirement (i.e., cars can be coupled or decoupled only from one end of a track). Focusing on the multi-stage flat shunting problem, we develop a mixed-integer linear programming (MILP) model to optimize the number of engine actions, as the mesoscopic cost, and the number of car movements, as the microscopic cost, during pull-back and assignment operations. The proposed model is solved using a standard optimization solver and a customized branch-and-bound algorithm. A sequencing state measure is proposed to quantitatively evaluate the deviation of a car distribution in a yard from the desired final car sequence, leading to an effective heuristic rule that significantly improves branching efficiency. The proposed approach saves more than 99% of the computation time compared with the basic branch-and-bound algorithm. Through numerical experiments with several benchmarks, we found that optimizing generalized car movement costs can further improve the quality of shunting schedules even when the number of pull-back engine actions is already optimal.