Optimization Model and Algorithm of Additional Trains Scheduling in High-Speed Railway Timetables Considering Passenger Demand
-
摘要:
在既有列车运行图中插入新增列车运行线是铁路运输企业编制每季度列车运行图和日计划中列车运行计划所常采用的方法. 然而,传统基于人工的编制手段效率低且难以保证列车运行图编制质量. 对此,本文以降低铁路运营和调度成本以及运输尽可能多的旅客等为优化目标,基于离散时空网络构建综合优化列车开行方案和新增列车运行线的整数线性规划模型;针对模型特点,设计基于拉格朗日松弛的启发式求解算法,将原问题分解为列车开行方案优化子问题和一组为单列列车搜索费用最小的时空路径子问题;最后,以京沪高速铁路为算例,验证模型的正确性和算法可行性. 研究结果表明:所提方法能快速自动生成新增列车运行线后的列车运行图,且求得的上界解质量相比顺序求解方法平均提升了4.58%.
Abstract:Objective 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.
Methods 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.
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 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.
Conclusion 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.
-
表 1 时空弧费用
Table 1. Spatio-temporal arc costs
列车种类 弧类型 弧费用 既有列车 始发弧 $ {\beta _1} (\hat t - t + | {t - o_{{\mathrm{dep}},k}} |) $ 运行弧 $ {\beta _1} (\hat t - t) $ 终到弧 $ {\beta _1} (\hat t - t + | {\hat t - o_{{\mathrm{arr}},k}} |) $ 新增列车 所有弧 $ {\beta _2} (\hat t - t) $ 表 2 各场景求解结果及求解质量指标
Table 2. Solution results and solution quality metrics for each scenario
对照参数 场景编号 参数设置 顺序求解方法 基于拉格朗日松弛的求解算法 下界解值 上界解值 计算时间/s egap/% 下界解值 上界解值 计算时间/s egap/% Impr/% 始发时间
窗长度1 7706.15 7976.93 678 3.51 7336.65 7532.89 1174 2.67 5.89 2 40 min 7705.63 8037.93 678 4.31 7335.56 7664.90 1219 4.49 4.87 3 50 min 7706.35 7975.68 775 3.49 7336.60 7612.91 1069 3.77 4.77 客流需求 4 115270 人5633.86 5806.79 614 3.07 5262.99 5491.79 1016 4.35 5.74 5 155958 人9952.70 10142.33 603 1.91 9571.84 9902.13 2534 3.45 2.43 备选停站
方案数量6 短途 7868.33 8054.41 619 1.96 7473.63 7732.41 777 3.46 4.16 7 均匀 7617.67 7834.25 568 2.84 7256.33 7436.75 1520 2.49 5.35 运行区间 8 2 个 9076.02 9254.05 591 2.36 8707.45 8857.30 1190 1.72 4.48 9 4 个 8603.21 8741.14 813 2.76 8232.49 8439.19 869 2.51 3.58 -
[1] 鲁工圆,胡留洋,彭慧,等. 基于预发车的高速铁路列车出发追踪间隔时间压缩方法[J]. 西南交通大学学报,2024,59(6): 1368-1377. doi: 10.3969/j.issn.0258-2724.20220064LU Gongyuan, HU Liuyang, PENG Hui, et al. Method for compressing departure tracking interval of high-speed trains based on pre-departure strategy[J]. Journal of Southwest Jiaotong University, 2024, 59(6): 1368-1377. doi: 10.3969/j.issn.0258-2724.20220064 [2] INGOLOTTI L, BARBER F, TORMOS P, et al. An efficient method to schedule new trains on a heavily loaded railway network[C]//Advances in Artificial Intelligence–IBERAMIA 2004. Berlin: Springer, 2004:164-173. [3] BURDETT R L, KOZAN E. Techniques for inserting additional trains into existing timetables[J]. Transportation Research Part B: Methodological, 2009, 43(8/9): 821-836. [4] CACCHIANI V, CAPRARA A, TOTH P. Scheduling extra freight trains on railway networks[J]. Transportation Research Part B: Methodological, 2010, 44(2): 215-231. doi: 10.1016/j.trb.2009.07.007 [5] MEIRICH C, NIEßEN N. Calculating the maximal number of additional freight trains in a railway network[J]. Journal of Rail Transport Planning & Management, 2016, 6(3): 200-217. [6] LI S D, ZUO D J, LI W Q, et al. Freight train line planning for large-scale high-speed rail network: an integer Benders decomposition-based branch-and-cut algorithm[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 192: 103750. 1-103750.28. doi: 10.1016/j.tre.2024.103750 [7] JIANG F, CACCHIANI V, TOTH P. Train timetabling by skip-stop planning in highly congested lines[J]. Transportation Research Part B: Methodological, 2017, 104(10): 149-174. doi: 10.1016/j.trb.2017.06.018 [8] 徐涵,聂磊,谭宇燕. 基于灵活接续的周期性列车运行图加线模型[J]. 铁道科学与工程学报,2018,15(9): 2439-2447.XU Han, NIE Lei, TAN Yuyan. The adding train paths model on cyclic timetable based on flexible connection[J]. Journal of Railway Science and Engineering, 2018, 15(9): 2439-2447. [9] 高如虎,牛惠民,江雨星. 基于多维网络的增开列车条件下高速铁路列车运行图调整[J]. 铁道学报,2020,42(5): 1-8.GAO Ruhu, NIU Huimin, JIANG Yuxing. Train timetable rescheduling based on a time-station-track multi-dimensional network under condition of running extra trains for high-speed railway[J]. Journal of the China Railway Society, 2020, 42(5): 1-8. [10] LIU Y T, CAO C X. A multi-objective train operational plan optimization approach for adding additional trains on a high-speed railway corridor in peak periods[J]. Applied Sciences, 2020, 10(16): 5554.1-555.29. doi: 10.3390/app10165554 [11] 高如虎,牛惠民. 基于 ADMM 方法的新增列车条件下灵活的列车时刻表优化算法研究[J]. 铁道学报,2021,43(2): 21-29. doi: 10.3969/j.issn.1001-8360.2021.02.003GAO Ruhu, NIU Huimin. Study on additional train timetable algorithm in flexible manner based on ADMM approach[J]. Journal of the China Railway Society, 2021, 43(2): 21-29. doi: 10.3969/j.issn.1001-8360.2021.02.003 [12] 毛万华,陈亚茹. 高速铁路列车运行图新增列车运行线优化方法研究[J]. 铁道运输与经济,2021,43(11): 1-6,26.MAO Wanhua, CHEN Yaru. Research on optimization method of newly-added train paths based on train running diagram of high speed railways[J]. Railway Transport and Economy, 2021, 43(11): 1-6,26. [13] ZHAO J D, LI H Y, MENG L Y, et al. An optimization method of high-speed railway rescheduling to meet unexpected large passenger flow[J]. Journal of Advanced Transportation, 2022, 2022: 5964010.1-5964010.16. [14] 曲云腾,姚向明,赵鹏,等. 考虑动车组接续的区域城际网运行图加线模型[J]. 铁道学报,2024,46(1): 13-21. doi: 10.3969/j.issn.1001-8360.2024.01.002QU Yunteng, YAO Xiangming, ZHAO Peng, et al. Model for inserting additional trains into existing timetable for intercity railway network considering EMU connections[J]. Journal of the China Railway Society, 2024, 46(1): 13-21. doi: 10.3969/j.issn.1001-8360.2024.01.002 [15] 赵日鑫,何世伟,张杰,等. 高铁枢纽环线公交化列车新增运行线优化方法[J]. 北京交通大学学报,2025,49(1): 28-37.ZHAO Rixin, HE Shiwei, ZHANG Jie, et al. Optimization method of adding extra train paths for mass transit type in high-speed railway hub loop[J]. Journal of Beijing Jiaotong University,2025,49(1): 28-37. [16] 刘璐,孟令云,李新毅,等. 考虑旅客需求的停站方案与列车运行图一体化模型与算法[J]. 铁道科学与工程学报,2019,16(2): 518-527.LIU Lu, MENG Lingyun, LI Xinyi, et al. Integrated optimization of stopping pattern and train timetable for passenger demand[J]. Journal of Railway Science and Engineering, 2019, 16(2): 518-527. [17] HASSANNAYEBI E, ZEGORDI S H, AMIN-NASERI M, et al. Demand-oriented timetable design for urban rail transit under stochastic demand[J]. Journal of Industrial and Systems Engineering, 2016, 9(3): 28-56. [18] 赵子洪. 面向服务间隔时间的列车运行图优化方法研究[J]. 铁道运输与经济,2019,41(7): 33-39.ZHAO Zihong. A research on train diagram optimization method oriented to service interval time[J]. Railway Transport and Economy, 2019, 41(7): 33-39. [19] ALBRECHT T. Automated timetable design for demand-oriented service on suburban railways[J]. Public Transport, 2009, 1(1): 5-20. [20] FENG J J, LI X, SHI J G, et al. Joint optimization of metro train timetable and stopping plan for the first service period: an integrated energy-efficient and time-saving model[J/OL]. International Journal of Transportation Science and Technology. (2024-10-06)[2024-12-10]. https://api.semanticscholar.org/CorpusID:273492667. [21] 李冰,任泽强,轩华. 考虑多编组站转场作业的铁路枢纽车流组织优化[J]. 西南交通大学学报,2023,58(3): 489-498,545.LI Bing, REN Zeqiang, XUAN Hua. Optimization of wagon flow assignment with transship work for multiple marshaling stations at railroad terminals[J]. Journal of Southwest Jiaotong University, 2023, 58(3): 489-498,545. -