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

Objective: Railway operators enhance the alignment between transportation services and passenger demand by making quarterly adjustments to the basic train timetable and daily preparation of the next-day train operation plan based on the basic timetable. 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 train space-time paths into the basic timetable while making reasonable adjustments to the original train space-time paths. Furthermore, incorporating passenger demand into the generation process of these two technical plans can evidently result in train timetables that better meet market needs.Method: 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 times, including departure times at origin stations, and dwell times at intermediate stations. An integer linear programming model was built for the integrated optimization of line planning and additional trains scheduling problems based on a space-time 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 times of original trains, whereas passenger benefits are characterized by maximizing the number of passengers transported. The coefficients of the sub-objectives were determined based on practical operations and empirical experience. Moreover, the practical constraints, including the uniqueness of the train stop pattern, train capacity, the relationship between passenger demand allocation decision variables and train stop pattern selection variables, minimum headway requirements, and the coupling of subproblems, were considered.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 trains scheduling subproblem. The algorithm iteratively solved subproblems by calling the commercial solver and a forward dynamic programming algorithm, respectively.Results: 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 obtains the optimal upper bound solution within the maximum number of iterations, with an average optimality gap value of 3.21%. Compared to the sequential solving approach, our 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 trains scheduling subproblem. Besides, the proposed algorithm is able to achieve the feasible upper bound solution within the first 200 iterations, while further iterations yielded even better upper bound solutions.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 are made to certain timings along the journey, whereas their departure from origin stations and arrival times at destination stations remain unchanged. Both findings reflects 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 remaine unserved.Conclusion: By considering passenger flow demand, integrating the additional trains 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, space-time paths of additional trains should be scheduled to maintain the arrival and departure times of higher-priority trains unchanged and minimize 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, to further enhance the feasibility of the generated train timetables.