Optimization on Train Operation Adjustment on Single-track Railway from Discrete Perspective
-
摘要: 针对单线铁路多等级列车共线运行调整问题, 从系统仿真角度, 构建了考虑技术作业类型及车站到发线数量等关键约束的离散系统仿真模型。为提高系统在模拟多级列车运行调整过程中的时效性, 在既有列车行进策略的基础上, 设计了能够避免调整策略在列车区间运行及在站最小作业时间内重复执行的事件转移函数。考虑到多级列车对冲突疏解造成的困难, 利用分层决策在预测越行站和会让站等方面的优势, 设计离散仿真系统的同级列车有限随机调整策略和多级列车分层随机调整策略, 以提高仿真系统在列车运行调整过程中的全局搜索能力。最后, 通过实例分析验证了离散系统仿真模型及调整策略的有效性和合理性。结果表明: (1)本文设计的调整策略可以将解的质量提高约5.77%;(2)调整策略中的事件转移函数能将系统仿真时效性提高约34.47%;(3)分层策略虽能确保高等级列车的时效性, 但需以牺牲低等级列车的时效性为代价, 损失系统时效性约45.3%。Abstract: A simulation model of discrete system is constructed from a perspective of system simulation to solve theproblem of adjusting multi-class train operation on a single-track railway , considering key constraints such as the typeof technical operation and the number of arrivals and departure tracks at each station. Based on the existing train advance strategy, an event transfer function is designed to avoid the repeated execution of the adjustment strategy duringinterval operation and the minimum stopping time of the train at the station. In this way,the system timeliness isstrengthened during the simulation of adjusting multi-class train operation.Considering the difficulties caused bymulti-class trains for conflict reliefs,a finite random strategy adjustment for same-class trains and a layered randomstrategy adjustment for multi-class trains are sequentially designed using the advantage of hierarchical decision making in predicting crossing stations and overtaking stations. It can improve the global searching ability of the discretesimulation system during adjusting train operation.Finally, the effectiveness and rationality of the simulation model ofthe discrete system,as well as the strategy adjustment,are verified through an example analysis. The results areshown as follows: ① The strategy adjustment designed in the work can improve the quality of the solution by about 5.77%.② The event transition function in the strategy adjustment can improve the timeliness of the system simulationby about 34.47%.③ Although the hierarchical strategy can ensure the timeliness of high-class trains,it needs to sacrifice the timeliness of low-class trains,losing the system's timeliness by about 45.3%
-
图 1 多级列车分层随机调整策略
Figure 1. Hierarchical random strategy adjustment of multi-class trains
图 5 同级列车调整后的列车运行图
Figure 5. Train-operation plan after adjusting the same-class trains
图 6 r=1等级列车调整过程中的离散时间步长
Figure 6. Discrete-time step during adjusting which class r= 1 trains
图 7 r∈{2, 3}等级列车调整过程中的离散时间步长
Figure 7. Discrete-time step during adjustingwhich class r ∈ {2, 3} trains
图 8 不同w2和w3取值下的目标函数值
Figure 8. Objective function values with different values of w2and w3
图 9 不同λ1和λ2取值下目标函数的平均值
Figure 9. Average value of an objective function under different values of λ1 and λ2
表 1 车站内到发线数量
Table 1. Number of arrival and departure lines in the station
车站z 1 2 3 4 5 6 7 8 9 10 到发线数量Nz 4 3 3 3 4 5 3 3 4 3 
下载: 导出CSV
表 2 列车等级及初始晚点时间
Table 2. Train rank and original time delay
列车l 列车等级 初始晚点 列车l 列车等级 初始晚点 1 2 6 25 1 -6 3 3 27 27 1 4 5 1 20 2 3 0 7 3 11 4 2 24 9 1 0 6 1 0 11 2 -8 8 2 19 13 2 7 10 2 0 15 3 -7 12 3 -6 17 3 8 14 2 25 19 1 -5 16 3 0 21 1 10 18 3 15 23 1 7 20 3 8
下载: 导出CSV
表 3 列车在各车站的技术作业类型
Table 3. Type of the technical operation of trains in each station
列车l 车站z 列车l 车站z 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 2 0 2 0 0 0 0 0 0 25 0 0 0 0 0 0 0 0 0 1 3 0 0 2 0 0 2 0 0 0 0 27 0 0 0 0 0 0 0 0 0 1 5 0 0 0 0 1 1 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 7 0 0 0 2 0 0 2 0 2 0 4 2 0 2 2 0 0 0 0 0 0 9 0 0 0 0 1 0 0 1 1 1 6 1 0 0 0 0 1 0 0 0 0 11 0 0 0 0 0 0 0 0 0 2 8 2 0 2 0 0 0 0 0 2 0 13 0 0 0 0 0 2 0 0 0 2 10 2 2 0 0 0 0 0 2 0 0 15 0 0 0 2 0 2 2 0 0 2 12 2 0 0 0 0 2 0 0 0 0 17 0 0 0 0 0 2 0 2 0 2 14 2 2 0 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0 0 0 1 16 2 2 0 0 2 0 0 0 0 0 21 0 0 0 0 0 0 0 0 0 1 18 2 0 0 0 0 0 0 0 0 0 23 0 0 0 0 0 0 0 0 0 1 20 2 0 0 0 0 0 0 0 0 0 注: 列车编号为奇数，表示该列车为下行列车，即fl=0, 反之，则为上行列车，即fl=1
下载: 导出CSV
-
[1] 李智, 张涛, 许伟, 等. 高速铁路智能CTC系统列车运行自动调整研究[J]. 交通信息与安全, 2020, 38(6): 122-128+144. https://www.cnki.com.cn/Article/CJFDTOTAL-JTJS202006017.htmLI Zhi, ZHANG Tao, XU Wei, et al. Auto-matic train rescheduling of intelligent CTC system for high-speed railway[J]. Journal of Transport Information and Safety, 2020, 38 (6): 122-128+144. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JTJS202006017.htm [2] ZHU Yongqiu, GO VERDE R M P. Railway timetable rescheduling with flexible stopping and flexible short-turning during discruption[J]. Transportation Research Part B: Methodological, 2019(123) : 149-181. http://www.onacademic.com/detail/journal_1000042281594499_99e2.html [3] CACCHIANI V, HUISMAN D, KIDD M, et al. An overview of recovery models and algorithms for real-time railway re-scheduling[J]. Transportation Research Part B : Methodological, 2014 (63): 15-37. doi: 10.1007/s00500-014-1244-6 [4] GAVONE G, D0T0DI M, EPIC0C0 N, et al. A decision making procedure for robust train rescheduling based on mixed inter linear programming and data envelopment analysis[J]. Applied Mathematical Modelling, 2017(52) : 255-273. http://www.onacademic.com/detail/journal_1000039989484410_3ffa.html [5] SOTSKOV Y N, GHOLAMI 0. Mixed graph model and algorithms for parallel-machine job-shop scheduling problems[J]. International Journal of Production Research, 2017, 55 (6): 1549-1564. doi: 10.1080/00207543.2015.1075666 [6] GHOLAMI 0, KRASEMAN J T. A heuristic approach to solving the train traffic re-scheduling problem in real time[J]. Algorithms, 2018, 11(87) : 1-4. http://www.mdpi.com/1999-4893/11/4/55 [7] D'ARIANO A, PACCIARELLI D, PRANZ-0 M. A branch and bound algorithm for scheduling trains in a railway network[J]. European Journal of Operational Research, 2007 (183): 643-657. http://www.onacademic.com/detail/journal_1000034013015710_2857.html [8] LAMORGESE L, MANNINO G. An exact decomposition approach for the real-time train dispatching problem[J]. Operations Research, 2015, 63 (1): 48-64. doi: 10.1287/opre.2014.1327 [9] YANG Lixing, ZHOU Xuesong, GAO Ziyou. Credibility-based rescheduling model in a double-track railway network : A fuzzy reliable optimization approach[J]. Omega, 2014(48) : 75-93. http://www.sciencedirect.com/science?_ob=ShoppingCartURL&_method=add&_eid=1-s2.0-S0305048313001151&originContentFamily=serial&_origin=article&_ts=1425339641&md5=6047fa01540aa674be6eb3cd360a8a4f [10] MENG Linyun, ZHOU Xuesong. Simultaneous train rerouting and rescheduling on an N-track network : A model reformulation with net-work-based cumulative flow variables[J]. Transportation Research Part B: Methodological, 2014 (67): 203-234. http://pdfs.semanticscholar.org/be84/3b6b8d6cced9789275b1cf50cd23a32d25dd.pdf [11] NIU Huimin, ZHOU Xuesong, GAO Ruhu. 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. http://www.sciencedirect.com/science/article/pii/S0191261515000478 [12] 高如虎, 牛惠民, 杨喜梅. 面向时变需求的高铁快运专列时刻表和配装方案综合优化研究[J]. 交通信息与安全, 2020, 38(4): 122-131. doi: 10.3963/j.jssn.1674-4861.2020.04.015GAO Ruhu, NIU Huimin, YANG Ximei. Coordinating train timetable and demand assignment for express delivery with high-speed railway with time-dependent-oriented demand[J]. Journal of Transport Information and Safety, 2020, 38 (4): 122-131. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2020.04.015 [13] GOVERDE R M P, HEIDERGOTT B, MERLET G. Railway timetable stability analysis using stochastic max-plus linear systems[J]. Transportation Research Part B: Methodological, 2007, 41(2): 179-201. doi: 10.1016/j.trb.2006.02.003 [14] DORFMAN M J, MEDANIC J. Scheduling trains on a railway network using a discrete event model of railway traffic[J]. Transportation Research Part B: Methodological, 2004(38): 81-98. http://www.ixueshu.com/document/4ffb078c3425e07f318947a18e7f9386.html [15] MEDANIC J, DORFMAN M J. Efficient scheduling of traffic on a railway line[J], Journal of Optimization Theory and Application, 2002, 115(3): 587-602. doi: 10.1023/A:1021255214371 [16] LI Feng, GAO Ziyou, LI Keping, et al. Efficient scheduling of railway trailic based on global information of train[J]. Transportation Research Part B: Methodological, 2008 (42): 1008-1030. http://download.xuebalib.com/xuebalib.com.23677.pdf [17] XU Xiaoming, LI Keping, YANG Lixing, et al. An efficient train scheduling algorithm on a single-track railway system[J]. Journal of Scheduling, 2019(22) : 85-105. [18] HARBERING J, RANADE A, SCHMIDT M, et al Complexity, bounds and dynamic programming algorithms for single track train scheduling[J]. Annals of Operations Research, 2017, 273(4): 1-22. http://www.zhangqiaokeyan.com/academic-journal-foreign_other_thesis/0204112823824.html [19] 张正坤, 朱昌锋. 基于统的编组站配流研究[J]. 计算机工程与应用, 2017, 53(21): 219-224. doi: 10.3778/j.issn.1002-8331.1605-0027ZHANG Zhengkun, ZHU Changfeng. Research on wagon-flow allocation for marshalling yard based on TPr/T_System[J]. Computer Engineering and Applications, 2017, 53 (21): 219-224. (in Chinese) doi: 10.3778/j.issn.1002-8331.1605-0027 [20] 徐小明. 基于离散事件的列车调度问题模型与算法研究[D]. 北京: 北京交通大学, 2016.XU Xiaoming. Research on discrete event-based models and algorithms for train scheduling problem[D]. Beijing: Beijing Jiaotong University, 2016. (in Chinese). [21] 周磊山, 秦作睿. 列车运行计划与调整的通用算法及其计算机实现[J]. 铁道学报, 1994, 16⑶: 56-65. doi: 10.3321/j.issn:1001-8360.1994.03.009ZHOU Leishan, QIN Zuorui. General algorithm and its realization on computer for the train operation adjustment sys-tem[J]. Journal of the China Railway Society, 1994, 16 (3) : 56-65. (in Chinese) doi: 10.3321/j.issn:1001-8360.1994.03.009 [22] 孟令云, 杨肇夏, 李海鹰. 单线铁路区间能力失效条件下列车运行调整模型U]. 系统工程理论与实践, 2012, 32(4): 885-894. doi: 10.3969/j.issn.1000-6788.2012.04.027MENG Lingyun, YANG Zhaoxia, LI Haiying. Train dispatching models under field capacity breakdowns on single-track railway lines[J]. System Engineering Theory and Practice, 2012, 32(4) 885-894. (in Chinese) doi: 10.3969/j.issn.1000-6788.2012.04.027 -
点击查看大图
图(9) / 表(3)
计量
- 文章访问数: 377
- HTML全文浏览量: 222
- PDF下载量: 7
- 被引次数: 0