留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

离散视角下单线铁路列车运行调整优化

张正坤 朱昌锋 马文虎

张正坤, 朱昌锋, 马文虎. 离散视角下单线铁路列车运行调整优化[J]. 交通信息与安全, 2021, 39(4): 108-116. doi: 10.3963/j.jssn.1674-4861.2021.04.014
引用本文: 张正坤, 朱昌锋, 马文虎. 离散视角下单线铁路列车运行调整优化[J]. 交通信息与安全, 2021, 39(4): 108-116. doi: 10.3963/j.jssn.1674-4861.2021.04.014
ZHANG Zhengkun, ZHU Changfeng, MA Wenhu. Optimization on Train Operation Adjustment on Single-track Railway from Discrete Perspective[J]. Journal of Transport Information and Safety, 2021, 39(4): 108-116. doi: 10.3963/j.jssn.1674-4861.2021.04.014
Citation: ZHANG Zhengkun, ZHU Changfeng, MA Wenhu. Optimization on Train Operation Adjustment on Single-track Railway from Discrete Perspective[J]. Journal of Transport Information and Safety, 2021, 39(4): 108-116. doi: 10.3963/j.jssn.1674-4861.2021.04.014

离散视角下单线铁路列车运行调整优化

doi: 10.3963/j.jssn.1674-4861.2021.04.014
基金项目: 

教育部人文社科规划基金项目 18YJAZH148

详细信息
    作者简介:

    张正坤(1989—), 博士研究生.研究方向: 交通运输优化理论与方法. E-mail : zzklzjtu@163.com

    通讯作者:

    朱昌锋(1972—), 博士, 教授.研究方向: 轨道交通运输组织.E-mail : cfzhu003@163.com

  • 中图分类号: U292.4

Optimization on Train Operation Adjustment on Single-track Railway from Discrete Perspective

  • 摘要: 针对单线铁路多等级列车共线运行调整问题, 从系统仿真角度, 构建了考虑技术作业类型及车站到发线数量等关键约束的离散系统仿真模型。为提高系统在模拟多级列车运行调整过程中的时效性, 在既有列车行进策略的基础上, 设计了能够避免调整策略在列车区间运行及在站最小作业时间内重复执行的事件转移函数。考虑到多级列车对冲突疏解造成的困难, 利用分层决策在预测越行站和会让站等方面的优势, 设计离散仿真系统的同级列车有限随机调整策略和多级列车分层随机调整策略, 以提高仿真系统在列车运行调整过程中的全局搜索能力。最后, 通过实例分析验证了离散系统仿真模型及调整策略的有效性和合理性。结果表明: (1)本文设计的调整策略可以将解的质量提高约5.77%;(2)调整策略中的事件转移函数能将系统仿真时效性提高约34.47%;(3)分层策略虽能确保高等级列车的时效性, 但需以牺牲低等级列车的时效性为代价, 损失系统时效性约45.3%。

     

  • 图  1  多级列车分层随机调整策略

    Figure  1.  Hierarchical random strategy adjustment of multi-class trains

    图  2  原始列车运行图

    Figure  2.  Plan of original train operation

    图  3  调整过程收敛图

    Figure  3.  Convergency of the adjustment process

    图  4  多级列车调整后的列车运行图

    Figure  4.  Train-operation plan after adjusting 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  不同w2w3取值下的目标函数值

    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.htm

    LI 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.015

    GAO 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-0027

    ZHANG 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.009

    ZHOU 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.027

    MENG 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)
计量
  • 文章访问数:  379
  • HTML全文浏览量:  222
  • PDF下载量:  7
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-11-29

目录

    /

    返回文章
    返回