Train timetable and stopping plan generation based on cross-line passenger flow in high-speed railway network

Considering the real scenario in China, in order to decrease passenger transfer, cross-line trains are scheduled extensively for the large number of cross-line passenger flow. Therefore, in this paper, we propose a more practical approach aiming to schedule more trains within a limit time horizon by both main-line train and cross-line train scheduling optimization (train timetable and stopping plan optimization). We find that the train scheduling and passenger assignment problems are multi-commodity flow problems. The trains (as the users) share the railway capacities (as the resource) in a high-speed railway network, and the passengers (as the users) share the train carrying capacities (as the resource). Thus, based on this, we formulate two space–time networks—train and passenger space–time networks—to present the train operation and the passenger flow, respectively. In addition, we regard train disturbances in different directions as different train headways at cross-line stations to optimize train scheduling practically. Sequentially, a mixed-integer linear programing model with headway and coupling constraints is formulated. To solve the model efficiently for a large-scale application, we decompose the problem into two space–time path-searching sub-problems based on the passenger and train space–time networks by the Lagrangian relaxation and alternating direction method of multipliers decomposition methods. Finally, we adopt the Taiyuan–Dezhou and Zhengzhou–Beijing high-speed railway networks in a practical experiment, and an experiment without cross-line operation is designed to test the effect of cross-line operation. The results show the proposed approach can obtain a no-conflict timetable and all the passenger demand can be satisfied, meanwhile, the capacity can improve 20.7% when the cross-line operation is not considered.