基于两阶段算法的运行图与天窗协同优化

徐长安; 倪少权; 陈钉均

doi:10.3969/j.issn.0258-2724.20180577

基于两阶段算法的运行图与天窗协同优化

doi: 10.3969/j.issn.0258-2724.20180577

徐长安^1,2,,
倪少权^1,2,3,
陈钉均^1,2,3, ,

基金项目: 国家重点研发计划（2017YFB1200702，2016YFC0802208）；国家自然科学基金（61703351）；四川省科技创新（苗子工程）培育项目（2017015）；四川省科技计划项目（2017ZR0149，2017RZ0007）

详细信息

作者简介:
徐长安（1991—），男，博士研究生，研究方向为铁路运输组织优化，E-mail：xu_chang_an@163.com

通讯作者:
陈钉均（1982—），男，副教授，博士，研究方向为铁路运输组织优化与系统工程，E-mail：chen-dingjun@163.com

中图分类号: U292.41
计量
- 文章访问数: 759
- HTML全文浏览量: 342
- PDF下载量: 29
- 被引次数: 17
出版历程
- 收稿日期: 2018-07-09
- 修回日期: 2018-12-14
- 网络出版日期: 2018-12-19
- 刊出日期: 2020-08-01

Collaborative Optimization for Timetable and Maintenance Window Based on Two-Stage Algorithm

XU Chang’an^{1,2
,},
NI Shaoquan^1,2,3,
CHEN Dingjun^{1,2,3
, ,}

摘要

摘要: 列车运行图铺画与天窗设置存在相互影响，相互制约的耦合关系，为了达到优化列车运行图结构，合理配置铁路运力资源的目的，在分析天窗与列车运行动态影响关系的基础上，以天窗设置对列车运行线铺画影响最小为目标，建立了列车运行图与天窗协同优化的混合整数规划模型. 考虑问题复杂性,设计了包含初步优化和综合优化的两阶段求解算法. 初步优化阶段采用基于专家经验的启发式算法得到列车运行图的大体框架，综合优化阶段利用禁忌搜索算法获取全局最优解. 最后以宝成线（阳平关—成都）为例进行有效性验算. 结果表明，相较于人机交互编制所得运行图，优化得出的运行图中所有客货列车在途经车站的总停留时间降低了6.19%，共减少1 355 min，其中旅客列车和货物列车在站停留时间分别降低了3.08%和7.40%，减少总时间分别为189 min和1 166 min.
- 铁路运输 /
- 列车运行图 /
- 天窗 /
- 协同优化 /
- 两阶段算法 /
- 禁忌搜索
Abstract: There is mutual coupling between train timetable generation and maintenance window setting. To achieve the purpose of optimizing the train timetable structure and reasonably configuring the railway transportation capacity. According to the dynamic analysis of train timetable generation and maintenance window setting, the minimum impact of maintenance windows setting on train timetable planning is used as the objective function, and a mixed integer programming (MIP) model is built to realize the collaborative optimization of train timetable and maintenance window. To solve this complex problem, a two-stage solving algorithm including preliminary optimization and comprehensive optimization is designed. In the preliminary optimization stage, a heuristic algorithm based on experts’ experience is used to obtain the general framework of the train timetable. In the comprehensive optimization stage, the tabu search algorithm is used to obtain the global optimal solution. Finally, a case study based on Baoji−Chengdu railway line (Yangpingguan−Chengdu section) was conducted to verify the model. The results show that compared with the timetable compiled by human-computer interaction, the proposed method can effectively reduce the total residence time of all passenger and freight trains at stations by 6.19%, a total reduction of 1 355 min, of which the passenger trains and freight trains station residence time are decreased by 3.08% and 7.40%, with the total reduction time of 189 min and 1 166 min, respectively.
- railroad transportation /
- timetable /
- maintenance window /
- collaborative optimization /
- two-phase algorithm /
- tabu search

HTML全文

图 1 天窗与列车运行图协同优化示意

Figure 1. Collaborative optimization for timetable and maintenance window

下载: 全尺寸图片幻灯片

图 2 天窗前后安全间隔

Figure 2. Safety interval before and after maintenance window

下载: 全尺寸图片幻灯片

图 3 两阶段求解算法流程

Figure 3. Flowchart of two-phase algorithm

下载: 全尺寸图片幻灯片

图 4 算法收敛

Figure 4. Algorithm convergence

下载: 全尺寸图片幻灯片

表 1 优化图与实际图在站停留时间对比

Table 1. Residence time comparison of optimized and planned timetables min

方案旅客列车货物列车所有列车

实际图 6 130 15 762 21 892
优化图 5 941 14 596 20 537

下载: 导出CSV

参考文献(13)

史峰,黎新华,秦进,等. 单线列车运行图铺划的时间循环迭代优化方法[J]. 铁道学报,2005,27(1): 1-5. doi: 10.3321/j.issn:1001-8360.2005.01.001

SHI Feng, LI Xinhua, QIN Jin, et al. Time-cycle iterative optimization method for single-line train timetable planning[J]. Journal of the China Railway Society, 2005, 27(1): 1-5. doi: 10.3321/j.issn:1001-8360.2005.01.001

徐长安,倪少权,陈钉均,等. 天窗设置理论与优化技术研究综述[J]. 交通运输工程与信息学报,2017,15(4): 24-31. doi: 10.3969/j.issn.1672-4747.2017.04.004

XU Changan, NI Shaoquan, CHEN Dingjun, et al. Survey of optimization theory and method of maintenance window arrangement in the train timetable[J]. Journal of Transportation Engineering and Information, 2017, 15(4): 24-31. doi: 10.3969/j.issn.1672-4747.2017.04.004

FORSGREN M, ARONSSON M, GESTRELIUS S. Maintaining tracks and traffic flow at the same time[J]. Journal of Rail Transport Planning & Management, 2013, 3(3): 111-123.

ALBRECHT A R, PANTON D M, LEE D H. Rescheduling rail networks with maintenance disruptions using problem space search[J]. Computers and Operations Research, 2013, 40(3): 703-712. doi: 10.1016/j.cor.2010.09.001

LIDEN T, JOBORN M. An optimization model for integrated planning of railway traffic and network maintenance[J]. Transportation Research Part C:Emerging Technologies, 2017, 74: 327-347. doi: 10.1016/j.trc.2016.11.016

AKEN S V, BESINOVIC N, GOVERDE R M P. Designing alternative railway timetables under infrastructure maintenance possessions[J]. Transportation Research Part B:Methodological, 2017, 98: 224-238. doi: 10.1016/j.trb.2016.12.019

赵丽珍,赵映莲,杨岳勤,等. 高速铁路综合维修“天窗”开设形式与行车组织协调问题的研究[J]. 中国铁道科学,2002,23(2): 127-131. doi: 10.3321/j.issn:1001-4632.2002.02.021

ZHAO Lizhen, ZHAO Yinglian, YANG Yueqin, et al. Study on the coordination of the opening form and the organization of trains in the comprehensive maintenance of high-speed railway[J]. China Railway Science, 2002, 23(2): 127-131. doi: 10.3321/j.issn:1001-4632.2002.02.021

聂磊,胡必松,付慧伶,等. 客运专线夜间行车与天窗的相互影响分析[J]. 交通运输系统工程与信息,2010,10(5): 66-72. doi: 10.3969/j.issn.1009-6744.2010.05.009

NIE Lei, HU Bisong, FU Huizhen, et al. Analysis of interaction between night driving and skylight in passenger dedicated line[J]. Journal of Transportation Systems Engineering and Information, 2010, 10(5): 66-72. doi: 10.3969/j.issn.1009-6744.2010.05.009

杨奎,彭其渊,鲁工圆,等. 高速铁路天窗设置与夜间列车运行协调优化技术[J]. 铁道学报,2015(4): 1-7. doi: 10.3969/j.issn.1001-8360.2015.04.001

YANG Kui, PENG Qiyuan, LU Gongyuan, et al. Coordination optimization technology of skylight setting and night train operation in high speed railway[J]. Journal of the China Railway Society, 2015(4): 1-7. doi: 10.3969/j.issn.1001-8360.2015.04.001

张强锋,吕红霞,杨宇翔. 基于三角模糊数的高铁天窗施工实施效果评价[J]. 西南交通大学学报,2018,53(4): 798-805. doi: 10.3969/j.issn.0258-2724.2018.04.018

ZHANG Qiangfeng, LÜ Hongxia, YANG Yuxiang. Effect evaluation of high-speed railway skylight construction based on triangular fuzzy number[J]. Journal of Southwest Jiaotong University, 2018, 53(4): 798-805. doi: 10.3969/j.issn.0258-2724.2018.04.018

兰泽康,何世伟,黎浩东,等. 考虑维修天窗和到发线数量的复线铁路列车运行图优化[J]. 北京交通大学学报,2018,42(3): 30-36.

LAN Zekang, HE Shiwei, LI Haodong, et al. Optimization for double-track railway train timetabling considering the maintenance skylight and the number of arrival-departure tracks[J]. Journal of Beijing Jiaotong University, 2018, 42(3): 30-36.

倪少权. 中国铁路列车运行图编制系统研究[D]. 成都: 西南交通大学, 2013

董守清,王进勇,闫海峰. 双线铁路列车运行调整的禁忌搜索算法[J]. 中国铁道科学,2005,26(4): 114-119. doi: 10.3321/j.issn:1001-4632.2005.04.024

DONG Shouqing, WANG Jinyong, YAN Haifeng. Tabu search algorithm for train operation adjustment of two-line railway[J]. China Railway Science, 2005, 26(4): 114-119. doi: 10.3321/j.issn:1001-4632.2005.04.024

施引文献

期刊类型引用(7)

1.	邢春阳，蓝天，高德钊，陈磊，赵敏敏. 基于客流量分析的增开地铁列车运行图局部调整模型设计. 自动化与仪器仪表. 2024(03): 110-113+118 . 百度学术
2.	石贇，牟海波，黄志鹏，董文青，柴获. 考虑跨线列车的运行图与天窗一体化模型与算法. 铁道科学与工程学报. 2024(05): 1761-1773 . 百度学术
3.	刘磊，田志强，靳欣妮，李津铭. 高原地区客货共线铁路综合维修天窗设置研究. 铁道技术标准(中英文). 2024(05): 45-52 . 百度学术
4.	杨皓男，倪少权，潘金山，吕苗苗，邓洪波，陈钉均. 铁路天窗方案与列车运行图协同优化研究综述. 铁道运输与经济. 2024(11): 71-81+174 . 百度学术
5.	刘俊琦，张则强，龚举华，张裕. 受约束的过道布置问题建模及优化方法. 西南交通大学学报. 2022(06): 1376-1385 . 本站查看
6.	徐长安，李晟东，李斯涵，倪少权. 高铁夕发朝至列车开行与天窗设置协同优化. 西南交通大学学报. 2021(04): 744-754 . 本站查看
7.	李彪，王立文，邢志伟，王思博，罗谦. 飞机地面除冰资源协同控制. 上海交通大学学报. 2021(11): 1362-1370 . 百度学术