Multi-periodic train timetabling using a period-type-based Lagrangian relaxation decomposition

- Model and solve multi-periodic train timetabling problem based on the directed graph.
- Simultaneous optimize operation periods, arrival and departure times of all period-types of trains.
- Provide a period-type-based decomposition frame by relaxing complicated constraints.
- Design an efficient solving method based on Lagrangian relaxation decomposition.

To provide passengers with strict regularity of train operation, this research is devoted to modeling and solving the multi-periodic train timetabling problem to simultaneously optimize operation periods, arrival times, and departure times of all period types of trains on a double-track rail network. Based on the construction of a weighted directed graph, a multi-path searching model, namely, a 0-1 linear programming model, is built to minimize the total travel time of all period-types of trains subject to many operational constraints, including station parking capacity and train minimum load factors. After decomposing this model by introducing some Lagrangian multipliers to relax its complicated constraints, a solution algorithm, including a multi-path simultaneous searching sub-algorithm for each period-type of train, is designed to optimize both the feasible and dual solutions, which correspond to the upper and lower bounds, respectively. Finally, the performance, convergence, sensitivity, and practicability of our method are analyzed using many instances on both a small rail network and the high-speed railway between Beijing and Shanghai in China.