Short-Term Rolling Stock Scheduling and Platform Assignment: A Branch-and-Check Method

Railway passenger demand fluctuates because of events, holidays, and individual traveler activities, making it difficult to predict several months in advance. Market-oriented railway plans feature strategies for canceling or adding train trips according to short-term forecasted passenger demand. This results in dynamic adjustments of the rolling stock schedule (RSS) and the train platforming plan (TPP) on a daily basis. The RSS defines the schedule of the train units (TUs), that is, the sequence of trips that each TU will execute and the maintenance appointments it has to undergo. The TPP defines the assignment of platforms to TUs: when two trips are executed in sequence by the same TU, a platform has to be assigned to the TU for the trip connection. Because of demand fluctuation, the RSS has to be adjusted to perform a set of trips different from those in the original plan, requiring new trip sequences and rescheduled maintenance appointments for the TUs, whereas the TPP has to be modified to guarantee the feasible assignment of the platforms to the TUs performing the newly defined trip sequences. To assist railway departments in making optimized decisions, this work studies the integrated adjustment of the RSS and TPP by proposing an integer linear programming model and an exact decomposition algorithm. The integrated model consists of two parts: (i) rolling stock scheduling with maintenance constraints, and (ii) platform assignment. The goal is to minimize the operating costs and the deviations from the original plan. The decomposition algorithm consists of a branch-and-check (B&C) method in which maintenance constraints and platform assignment are handled by dynamic cut generation, and problem-specific acceleration techniques are incorporated to reduce the search space and the computation times. The proposed B&C method is tested on real-world instances from the Chinese high-speed railway system, involving up to 981 trips, showing that optimal solutions are obtained within one hour of computation time. It is shown that the B&C method clearly outperforms solving the integrated model by a general-purpose solver even on medium-size instances. Furthermore, comparisons with different sequential methods, which firstly adjust the RSS and then compute a new TPP, highlight the benefits of the integrated framework.