Optimizing train timetable with flexible mixed traffic and skip-stop patterns for different speed trains

To improve the occupancy efficiency of high-speed rail track resources, this paper considered the train timetabling problem integrating flexible mixed traffic and skip-stop patterns for different-speed trains. A layered space-time network was constructed to depict train movements. The minimum required number of high-speed trains and OD-based stops was used to ensure the primary passenger travel demand. The maximum number of single-train stops was required for balance of train stops. Thus, this paper proposed a linear integer programming model with space-time arc variables to minimize train operational costs. Using variable-splitting technique, two types of binary variables associated with train type and skip-stop patterns were separated from the arc-based variables to reformulate the model. Under the Lagrangian relaxation framework, we can decompose the reformulated model into train space-time path subproblems, train type assignment subproblem and skip-stop scheduling subproblem. Furthermore, a set of train-type selection uniqueness constraint was introduced for the train type subproblem to ensure the feasible solution generation. An alternative simplified model was constructed for the train skip-stop subproblem to speed up the subproblem solving, and a dual-solution-based two-stage heuristic method was designed to obtain feasible solutions to the primal problem. Finally, we used several numerical experiments based on Beijing-Shanghai high-speed rail line to verify the effectiveness and efficiency of the proposed approach. The results show that the proposed method can obtain a tight lower bound and a near-optimal solution in a reasonable computational time, and it is superior to the conventional Lagrangian relaxation methods in terms of solution quality. © 2023, Central South University Press. All rights reserved.