Integrated line planning and train timetabling through price-based cross-resolution feedback mechanism

Railway line planning and train timetabling are two key planning steps that determine the operating cost and passenger service quality of a railway operator under the infrastructure capacity limitations. Traditionally, the line planning and train timetabling problems are solved sequentially at the strategic and tactical level, respectively. In this study, by introducing two types of binary decision variables, we first propose a unified integer linear programming (ILP) model for the integrated optimization of line planning and train timetabling. The line planning problem is modeled using ILP to satisfy passenger demand, whereas the cyclic train timetabling problem is formulated as a multi-commodity network flow model with a side track capacity constraint. The two types of binary decision variables are coupled by a cross-resolution consistency constraint, which ensures the conformity of the line planning and train timetabling decisions. Furthermore, a dual decomposition mechanism based on the Alternating Direction Method of Multipliers (ADMM) is developed to dualize the cross-resolution consistency and track capacity constraints, such that the original ILP model is decomposed into a line planning sub-problem and a set of train-specific sub-problems. After the linearization of the quadratic penalty terms in the ADMM, each sub-problem contains the Lagrangian relaxation price information based on the cross-resolution consistency constraint. Moreover, the primal and dual solutions are obtained by iteratively and efficiently solving the line planning sub-problem using a commercial solver, and each train-specific sub-problem through a tailored forward dynamic programming algorithm. Furthermore, a real-life case study is conducted based on the Beijing–Shanghai high-speed railway corridor to verify the efficiency and effectiveness of the proposed model and algorithm. The results of the numerical experiments demonstrate that the ADMM can achieve significantly smaller optimality gaps than Lagrangian relaxation, and the integrated optimization approach can improve the objective value by 5.78% on average compared with the sequential optimization approach.