Timetable Optimization for High-Speed Rail with Multiple Operating Periods: Solving Method Based on a Framework of Lagrangian Relaxation Decomposition

By aiming to provide high-speed rail (HSR) passengers with travel convenience in the regularity of train operation, this research is devoted to optimizing a novel type of multiperiod train timetable in which trains operating with the same stop stations, speeds, and headways are classified into one period type. Moreover, trains with different period types have various operating periods on the HSR system. First, the authors propose an optimization model with the aim of minimizing the total travel times of all trains and then further reformulate the model on the basis of a weighted digraph. Through the period type–based decomposition to the reformulated model with Lagrangian relaxation, a solving algorithm that includes a multiflow shortest-path searching algorithm is designed for optimizing the multiperiod train timetable and obtaining a lower bound of the objective to evaluate its quality. Numerical examples illustrate that the solving algorithm has a good convergence and can obtain a satisfactory feasible solution with a small gap between the upper and lower bounds of the objective values.