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

Document Type

Journal Article

Publication Date


Subject Area

place - asia, mode - rail, operations - scheduling, operations - capacity, operations - performance, planning - methods


Train timetabling, Multiple periods, Directed graph, 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.


Permission to publish the abstract has been given by Elsevier, copyright remains with them.


Transportation Research Part B Home Page: