Optimizing Train Timetable Under Oversaturated Demand Conditions: A Variable-Splitting Lagrangian Approach for Big-$M$ Constraints

This study aims to optimize train timetables with hour-dependent origin-destination passenger demand for an oversaturated high-speed rail corridor, where some passengers may be delayed to the next hour. By introducing arc-based binary variables and assignment-based integer variables in the elaborated space-time network, we formulate the problem under consideration as an integer linear programming model with the objective of minimizing passenger travel time. To transform nonlinear demand loading constraints, multiple sets of big- $M$ constraints linking different types of variables are established equivalently. While relaxing these big- $M$ constraints under the standard Lagrangian decomposition framework, a thorny issue is that the lower bounds are often not ideal due to the existence of big- $M$ values. To tackle this important and common computational challenge, a novel approach is employed to split the arc-based variables into train skip-stopping and departing variables. Furthermore, a series of valid constraints are proposed to augment the decomposed assignment subproblem. With the help of Lagrangian dual information, a dynamic programming heuristic is also developed to generate feasible solutions to the primal problem. Finally, several numerical experiments are conducted to assess the efficiency and effectiveness of the proposed approach. The results show that compared with traditional solution approaches, the proposed approach can obtain satisfactory solutions in acceptable computation times for all the instances, in which the optimality gaps are less than 5% and the travel time is reduced by 17.28% on average.