Weekly rolling stock planning in Chinese high-speed rail networks

In high-speed rail networks, train units are scheduled to periodically meet all maintenance requirements while at the same time continuing to serve all scheduled passenger trips. Motivated by the trip demand variances on the days of every week in China, this paper studies a weekly rolling stock planning (W-RSP) problem that aims to optimize the rotation plan for the train units on each day of a week, so as to minimize their operating cost, including any (un)coupling costs and maintenance costs. We model the W-RSP on a newly developed rotation network by adopting particular nodes and arcs to address the (un)coupling operations of train units, and then propose an integer linear programming formulation for the problem. To solve this formulation, we develop a customized branch-and-price algorithm, which relies on a reduced linear programming relaxation for computing the lower bound, embeds a diving algorithm for computing the upper bound, and integrates advanced branching rules for effective explorations of the solution space. Computational results validate the effectiveness and efficiency of the proposed solution algorithm, which is able to solve large instances with up to 5034 trips to near-optimality.