Optimization Model and Algorithm of Additional Trains Scheduling in High-Speed Railway Timetables Considering Passenger Demand

Railway operators enhance the alignment between transportation services and passenger demand by making quarterly adjustments to the basic train timetable and preparing next-day train operation plans based on it. However, the structural complexity of the basic timetable significantly complicates the generation of these two technical plans. To address this challenge within the framework of manually generated transport plans, railway operators commonly insert additional spatio-temporal train paths into the basic timetable while making reasonable adjustments to the original paths. Furthermore, incorporating passenger demand into the generation of these two technical plans can evidently result in train timetables that better meet market needs.

To effectively utilize the remaining capacity of the basic timetable, two adjustment measures were applied to trains in the original train timetable: flexible adjustment of train stop patterns and time, including departure time at origin stations, and dwell time at intermediate stations. An integer linear programming model was developed for the integrated optimization of line planning and additional train scheduling problems based on a spatio-temporal network modeling framework. The objective function was formulated from the perspective of balancing the interests of both railway operators and passengers. The benefits of railway operators were represented by the total travel time of all trains and penalties imposed for adjusting stop patterns, as well as departure and dwell time of original trains, whereas passenger benefits were reflected in maximizing the number of passengers transported. The coefficients of the sub-objectives were determined based on practical operations and empirical experience. Moreover, practical constraints were considered, including the uniqueness of train stop patterns, train capacity, the relationship between passenger demand allocation decision variables and train stop pattern selection variables, minimum headway requirements, and the coupling of subproblems. Given the characteristics of the model, a Lagrangian relaxation-based heuristic algorithm was designed. By dualizing the headway requirements and coupling constraints into the objective function through Lagrangian multipliers, the original problem was decomposed into two independent subproblems: a line planning subproblem and an additional train scheduling subproblem. The algorithm iteratively solved subproblems by calling the commercial solver and a forward dynamic programming algorithm, respectively.

To evaluate the effectiveness of the proposed model and algorithm, a set of numerical experiments based on the Beijing–Shanghai high-speed railway corridor was conducted. Moreover, the same scenarios were also solved using a sequential solving approach commonly employed in practical operations, where the line planning problem was optimized first, followed by the generation of the train timetable. The efficiency of the proposed algorithm was more comprehensively evaluated by comparing the solution results of the two methods.In all scenarios, the proposed algorithm successfully obtained the optimal upper bound solution within the maximum number of iterations, with an average optimality gap of 3.21%. Compared to the sequential solving approach, the proposed model and algorithm improve the quality of the upper bound solutions by an average of 4.58%. This improvement is attributed to the fact that the sequential solving approach prioritizes higher-quality solutions in the line planning subproblem, which, in turn, leads to a more significant deterioration in the solution quality of the additional train scheduling subproblem. Besides, the proposed algorithm is able to achieve a feasible upper bound solution within the first 200 iterations, while further iterations can yield even better results.The optimized train timetable shows that approximately 5% of the original trains undergo time adjustments exceeding 10 minutes throughout their entire journey. Moreover, for around 10% of the original trains, significant adjustments have been made to certain timings along the journey, whereas their departure from origin stations and arrival time at destination stations remain unchanged. Both findings reflect the structural complexity of the timetable and its inherent robustness. Passenger demand allocation results indicate that over 10% of the trains have seat occupancy rates below capacity across three or more segments. However, compared to short-distance passengers, a larger proportion of long-distance passengers remains unserved.

By considering passenger flow demand, integrating the additional train scheduling with the line planning can generate train timetables that provide higher overall system efficiency. To reduce the difficulty of basic timetable adjustments and train operation plan generation, spatio-temporal paths of additional trains should be scheduled in a way that maintains the arrival and departure time of higher-priority trains and minimizes changes to the overtaking relationships among trains. Additionally, to lower operational costs for railway operators and better meet passenger travel needs, priority should be given to accommodating long-distance passenger travel demand in daily operations. In future research, more practical factors should be incorporated into the modeling process, such as more detailed and accurate representations of the interests of railway operators and passengers, as well as time-varying passenger demand. Besides, the problem-solving framework should integrate other operational aspects, such as platform track allocation and rolling stock circulation plan, so as to further enhance the feasibility of the generated train timetables.