Rolling stock shunt operation planning in urban rail transit depots with maintenance consideration

This study investigates the daily rolling stock shunt operation planning in a rail depot. Given the layout of a depot and the rolling stocks (that arrive at and depart from this depot within an operation day) with given maintenance schedule, the studied problem lies in determining: 1) the position where each rolling stock is parked, outside washed, and/or maintained, and 2) the conflict-free shunting plan of rolling stocks to move within a depot. We transform the track-circuits in the depot into different multi-layer directed graphs to illustrate the shunting processes of rolling stocks. By means of these graphs, we formulate the studied problem as a mixed integer linear programming model by considering a more general variant of four requirements that make sense in practice but are not or rarely considered in previous works and by presenting a flexible technique to model the track capacity, to reduce the additional shunting movements of rolling stocks. Besides, we design a two-stage decomposition manner to efficiently solve real-life problem instances, wherein the problem in each stage is addressed by a presented logic-based Benders decomposition algorithm enhanced by customized acceleration mechanisms. Finally, a set of realistic and real-life instances with different scales (derived from the largest depot of the Chongqing Rail Transit Line 3 in China) are investigated. Computational results demonstrate that our best algorithm solves a real-life instance to optimality in approximately 8 s that is considerably shorter than the time of rail staffs to solve this instance manually, thus our approach can provide strong automatical computer-aided decision supports. Our approach is also very efficient in optimizing another objective that is also widely used, and can provide management insights to rail staffs.