Optimal routing and scheduling in railway marshalling station yards: An improved MILP model and a branch-and-Benders-cut algorithm

Managing train and engine traffic in the receiving/departure yard of a busy marshalling station is both critical and challenging for yard dispatchers due to the complex operational procedures and extensive shunting operations. To address this management challenge, this study investigates the train and engine routing and scheduling problem (TERSP) at railway marshalling stations, which entails simultaneously assigning routes and scheduling start times for both train and shunting operations in a receiving/departure yard, ensuring that the operations can be executed as closely as possible to the planned schedule without conflicts. We represent the yard infrastructure with microscopic granularity and formulate the TERSP as a mixed integer linear programming model to minimize the total weighted time deviation of operations from the given schedules. In comparison to previous studies on the TERSP, this model further incorporates practical requirements on train arrival-departure orders and railcar rolling processes. Moreover, the concept of key sections is introduced to formulate improved resource-based section occupation constraints, which are more aggregated and compact than traditional route-based constraints. To efficiently solve practical-size problems, we develop an exact branch-and-Benders-cut algorithm, in which problem specific upper- and lower-bound acceleration strategies are customized to facilitate the convergence of the algorithm. A set of real-world instances from a large marshalling station in China is employed to validate the effectiveness and efficiency of the proposed approaches. Computational results demonstrate that our model outperforms the benchmark model in both model construction and solution phases. Our algorithm can find (near-)optimal solutions within a short time (e.g., 30 or 60 s), showing superior performance over the conventional Benders decomposition approach and the built-in branch-and-cut method in CPLEX in terms of solution quality and computational efficiency.