Collaborative Optimization of Demand-oriented Train
Timetabling and Stop Planning for Intercity Railways

doi:10.16097/j.cnki.1009-6744.2023.02.021

Abstract

Abstract: To collaboratively optimize train timetables and stop plans for intercity railways, this paper used the hourdependent origin-destination passenger demand as the input. Considering variable train running times on segments, the paper developed a bi- objective linear integer programming model including train safe operation constraints and passenger demand loading constraints, and the construction of the objective functions depending on two aspects of train operation efficiency and passenger travel quality. Combining the characteristics of the proposed model, the bi-objective optimization model was transformed into a single-objective model by using the ε-constraint method, and then a branchand-cut algorithm was designed based on two sets of valid inequalities. Several different-sized numerical experiments on Guangzhou- Zhuhai intercity railway were conducted to assess the effectiveness of the proposed approach. The results show that the proposed approach can efficiently solve the real-life problems, and the obtained train timetables can highly match the dynamic passenger demand distributions. Specifically, compared with the non-peak periods, the peak periods account for 70% of the train lines and 69% of the train stops. For medium-scale and large-scale problems that cannot be solved directly using GUROBI, the proposed method can obtain satisfactory feasible solutions within an acceptable computational time, showing good solution performance.

Key words: railway transportation, train timetable, skip-stop pattern, passenger demand, ε-constraint method, branchand-cut approach

摘要： 为了同步优化城际铁路列车时刻表和停站方案，本文引入小时OD客流作为需求输入，考虑可变区间运行时间条件，耦合列车安全运行和需求合理加载约束，从列车运行效率和旅客出行质量两方面构建双目标线性整数规划模型。结合模型特点，采用ε-约束法将其转化为单目标优化模型，并依据问题特征构造两组有效不等式，设计分支切割算法求解转化后的单目标模型。为验证所提方法的可行性和有效性，设置以广州南—珠海城际铁路为背景的多组算例进行案例研究。计算结果表明：所提方法能够有效求解实际案例，其列车服务方案可以高度匹配旅客需求时空分布，相较于平峰时段，高峰时段分布了近70%的列车运行线，以及69%的列车停站；对于直接使用GUROBI无法求解的中大规模问题，所提方法能够在合理计算时间内获得满意可行解，展现出良好的求解性能。

关键词: 铁路运输, 列车时刻表, 停站方案, 旅客需求, ε-约束法, 分支切割

CLC Number:

U292.4

TIAN Xiao-peng, NIU Hui-min, HAN Ying. Collaborative Optimization of Demand-oriented Train Timetabling and Stop Planning for Intercity Railways[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(2): 197-207.

田小鹏, 牛惠民, 韩瑛. 面向需求的城际列车时刻表与停站方案同步优化[J]. 交通运输系统工程与信息, 2023, 23(2): 197-207.

Add to citation manager EndNote|Ris|BibTeX

URL: http://www.tseit.org.cn/EN/10.16097/j.cnki.1009-6744.2023.02.021

http://www.tseit.org.cn/EN/Y2023/V23/I2/197

References

[1] 牛惠民. 轨道列车时刻表问题研究综述[J]. 交通运输系统工程与信息, 2021, 21(5): 114-124. [NIU H M. Literature review on rail train timetabling problems[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(5): 114-124.]

[2] 秦进, 谭宇超, 张威, 等. 基于时空网络的城际高速铁路列车开行方案优化方法[J]. 铁道学报, 2020, 42(2): 1-10. [QIN J, TAN Y C, ZHANG W, et al. Train planning optimization for intercity railway based on space-time network[J]. Journal of the China Railway Society, 2020, 42(2): 1-10.]

[3] CAPRARA A, FISCHETTI M, TOTH P. Modeling and solving the train timetabling problem[J]. Operations Research, 2002, 50(5): 851-861.

[4] SCHÖEBEL A. An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation[J]. Transportation Research Part C: Emerging Technologies, 2017, 74: 348-365.

[5] NIU H M, ZHOU X S, GAO R H. Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints[J]. Transportation Research Part B: Methodological, 2015, 76: 117-135.

[6] BAI Y, HU Q Y, Ho T K, et al. Timetable optimization for metro lines connecting to intercity railway stations to minimize passenger waiting time[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(1): 79- 90.

[7] YANG L X, QI J G, LI S K, et al. Collaborative optimization for train scheduling and train stop planning on high-speed railways[J]. Omega, 2016, 64: 57-76.

[8] JIANG F, CACCHIANI V, TOTH P. Train timetabling by skip-stop planning in highly congested lines[J]. Transportation Research Part B: Methodological, 2017, 104: 149-174.

[9] MENG L Y, ZHOU X S. An integrated train service plan optimization model with variable demand: A team-based scheduling approach with dual cost information in a layered network[J]. Transportation Research Part B: Methodological, 2019, 125: 1-28.

[10] TIAN X P, NIU H M. Optimization of demand-oriented train timetables under overtaking operations: A surrogate-dual-variable column generation for eliminating indivisibility[J]. Transportation Research Part B: Methodological, 2020, 142: 143-173.

[11] 张春田, 戚建国, 杨凯, 等. 基于两阶段分布鲁棒优化的列车停站方案与时刻表协同研究[J/OL]. 控制与决策, (2022-04-19) [2022-11-23]. https: //doi. org/ 10. 13195/j. kzyjc. 2021. 2058. [ZHANG C T, QI J G, YANG K, et al. Two-stage distributionally robust optimization for integrated train stop planning and timetabling[J/OL]. Control and Decision, (2022-04-19) [2022-11-23]. https: //doi. org/10. 13195/j. kzyjc. 2021. 2058. ]

[12] 张旭, 陈秉智, 孟璐. 基于多目标的丹大城际停站方案优化研究[J]. 铁道学报, 2018, 40(8): 9-18. [ZHANG X, CHEN B Z, MENG L. Optimization study of DandongDalian intercity railway stop schedule plan based on multi-targets[J]. Journal of the China Railway Society, 2018, 40(8): 9-18.]

[13] 彭宏勤, 朱郁俊. 基于客流动态分配的城际列车开行方案[J]. 交通运输系统工程与信息, 2013, 13(1): 111- 117. [PENG H Q, ZHU Y J. Intercity train operation schemes based on passenger flow dynamic assignment [J]. Journal of Transportation Systems Engineering and Information Technology, 2013, 13(1): 111-117.]

[14] BARRENA E, CANCA D, COELHO L C, et al. Exact formulations and algorithm for the train timetabling problem with dynamic demand[J]. Computers & Industrial Engineering, 2014, 44: 66-74.

[15] 李得伟, 丁世顺, 张琦, 等. 基于客流需求的城际列车时刻表模型改进研究[J]. 交通运输系统工程与信息, 2017, 17(3): 157-164. [LI D W, DING S S, ZHANG Q, et al. Improved dynamic demand oriented timetabling model for intercity railway[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(3): 157-164.]

[16] 闫璐, 张琦, 丁舒忻, 等. 基于双目标优化的高速铁路列车运行调整[J]. 中国铁道科学, 2022, 43(2): 161- 171. [YAN L, ZHANG Q, DING S X, et al. High-speed railway train operation adjustment based on bi-objective optimization[J]. China Railway Science, 2022, 43(2): 161-171.]

Collaborative Optimization of Demand-oriented Train Timetabling and Stop Planning for Intercity Railways

面向需求的城际列车时刻表与停站方案同步优化

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	PENG Hong-qin, ZHANG Guo-wu. Strategies for High-quality Development of Air and High-speed Rail Transportation Under Goal of Carbon Peaking and Carbon Neutrality [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(3): 1-5.
[2]	HOU Tao, TANG Li, NIU Hong-xia. Data-driven Speed Compound Control of High-speed Train [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(3): 145-152.
[3]	TAI Guo-xuan, HUANG You-neng, LI Chun-chi, WANG Xi. An Optimization Method of Train Scheduling for Urban Rapid Rail Transit Based on Flexible Train Composition Mode [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(3): 195-203.
[4]	JIANG Zheng, WANG Rui, DU Hai-bin, YU Jian, CHEN Xue. Electro-pneumatic Brake for Heavy Haul Locomotive During Automatic Driving at Long Downgrade Segment [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(3): 311-318.
[5]	PAN Han-chuan, LU Jun-bo, HU Hua, LIU Zhi-gang, SHA Yue. Collaborative Optimization of Urban Rail Timetable and Flow Control Under Mixed Passenger and Freight Transportation [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(2): 187-196.
[6]	TONG Rui-yong, MAO Bao-hua, DU Peng, WEI Run-bin, HUANG Jun-sheng. Comprehensive Optimization of Operation Planning and Pricing of Backhaul for Heavy-haul Railways Transportation [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(2): 217-224.
[7]	XU Ling, XU Tong, JIANG Wen-hui, XIAO Hua, ZHANG Xiang-hong. Pricing and Subsidizing Mechanism of China Railway Express Considering Shipper's Preference [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(1): 2-9.
[8]	FENG Jia, LI Guo-wei, FU Yi-long, PENG Cheng, WU Yu-hui. Integrated Rolling Stock Scheduling and Maintenance Scheduling Optimization of Urban Rail Transit Lines Based on Shared Train Depot [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(1): 131-140.
[9]	XU He-ying, LV Hong-xia, LV Miao-miao, WANG Meng. Optimization of Empty Car Distribution in Loading End of Heavy Haul Railway [J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(1): 141-151.
[10]	FENG Fen-ling, CAI Ming-xu, JIA Jun-jie. Key Node Identification of China Railway Express Transportation Network Based on Multi-layer Complex Network [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(6): 191-200.
[11]	ZHANG Hai, LV Miao-miao, NI Shao-quan. Train Timetable Optimization Model for Full-length and Short-turn Routings with Irregular Departure Intervals [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(6): 224-233.
[12]	WANG Zhi-mei, YAO Shang-jun, CUI Zan-yang. Joint Optimization of Car Routing and Train Formation Plan Based on Transfer of Freight Flow from Road to Railway [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(5): 19-25.
[13]	SUN Hui-jun, DAI Pei-ling, GUO Xin. Train Timetable Collaborative Optimization Model Considering Transfer Heterogeneity for Urban Rail Transit System [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(5): 125-134.
[14]	YAN Zhen-ying, WANG Yu, HAN Bao-ming, LI Xiao-juan. Joint Optimization of Ticket Price and Ticket Time Window for High-speed Railway Based on Preference Order Choice [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(5): 164-173.
[15]	CHEN Xing-han, ZHOU Pei-yu, LANG Mao-xiang, YU Xue-qiao, LI Shi-qi . High-speed Railway Express Cargo Flow Allocation and Operation Organization Optimization Under Varying Demand [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(5): 174-186.