A branch-and-price algorithm for multi-day rolling stock circulation planning under enhanced operational conditions in Chinese high-speed railway network

This study investigates a rolling stock circulation planning problem under enhanced operational conditions, including the consideration of multi-day maintenance periods, the feasibility of coupling and decoupling operations, and the arrangement of deadhead movements. A tailored branch-and-price algorithm and a decomposition structure with observable upper and lower bounds are proposed to solve this problem. First, the problem is formulated into a path-based generation model for single-day routes and an assignment model to obtain multi-day circulation plans satisfying maintenance constraints. Then, regarding the feasibility of coupling and decoupling operations, circulation type variables with set covering constraints are introduced, and tailored type-and-state-based branching rules are designed to explore the solution space within the branch-and-price framework effectively. Next, to improve computational efficiency, additional relaxation techniques based on the deadhead movements in the network are designed. Lastly, extensive experiments are conducted on large-scale instances with up to 785 trips and 66 stations, which demonstrate the effectiveness of the proposed decomposition structure, additional relaxation techniques, and branching rules in both solution quality and performance. Comparisons under different maintenance rules and coupling/decoupling modes further validate the practical significance of the problem under enhanced operational conditions considered in this study.