高铁站列车和调车作业计划一体化编制方法

交通运输系统工程与信息 ›› 2021, Vol. 21 ›› Issue (3): 176-186.

高铁站列车和调车作业计划一体化编制方法

钟明轩，乐逸祥^*，周磊山

北京交通大学，交通运输学院，北京 100044

收稿日期:2021-01-15 修回日期:2021-04-02 出版日期:2021-06-25 发布日期:2021-06-25
作者简介:钟明轩(1994- )，男，甘肃嘉峪关人，博士生。
基金资助:
国家自然科学基金高铁联合基金/High-speed Rail Joint Fund of National Natural Science Foundation of China (U1834211，U1934216)；中国铁路北京局集团有限公司2020重大项目/Research Project of China Railway Beijing Group Co. Ltd.(2020AY01)。

Scheduling Method for Integrated Plan of Train Operation and Shunting Operation in High-speed Railway Station

ZHONG Ming-xuan, YUE Yi-xiang^* , ZHOU Lei-shan

School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

Received:2021-01-15 Revised:2021-04-02 Online:2021-06-25 Published:2021-06-25

摘要/Abstract

摘要：

复杂高铁站作业计划的编制质量是影响整个路网运输能效发挥的重要因素，为快速编制高质量车站作业计划，分析了各类列车在车站列车和调车作业，构建列车作业链，并描述车站作业计划优化问题的本质，结合车站布局和轨道电路分布，构建基于微观层面的车站作业计划优化模型；针对实际问题变量巨大，约束条件复杂的特点，将模型转换为对偶形式，在不需要初始解的情况下，通过拉格朗日松弛算法求解，并通过基于对称性破缺规则的分支定界法快速对松弛问题的解可行化，获得可行车站作业计划。以北京南站为例测试模型和算法，计算时间不超过 20 min，对偶间隙不超过10%,计算结果无冲突，表明该方法能够实现复杂高铁站高质量列车作业计划的快速求解，具有实际应用意义。

关键词: 铁路运输, 车站作业计划编制, 拉格朗日松弛, 高速铁路车站, 作业优化

Abstract:

The quality of train operation plan for complex high-speed railway station is an important factor affecting the transportation efficiency of the high- speed railway network. To generate high- quality station operation plans in short time, this paper analyzes the train operation and shunting operation of all types of trains in the station, and establishes the train operation chain. Based on these, the essence of station operation planning optimization problem has been described, which can be taken as a resource optimization problem. Then, considering the station layout and track circuit distribution, the study proposes a microscopic optimization model to create station operation plans. In view of the large number of variables and the complex constraints in the problem, the model is transformed into dual form and then solved by the Lagrange relaxation algorithm without initial feasible solution. A branch and bound method based on symmetry breaking rule is used to make the solution of Lagrange relaxation problem feasible. The case study uses Beijing South Railway Station to test the proposed model and algorithm. The calculation time in the case study is within 20 minutes, the results are feasible and the dual gaps are less than 10%. The results show that this method can generate high-quality train operation plan for complex high-speed railway stations effectively and has good potentials for practical applications.

Key words: railway transportation, station operation plan scheduling, lagrange relaxation, high- speed railway station, operation optimization

中图分类号:

U292.12

钟明轩，乐逸祥，周磊山. 高铁站列车和调车作业计划一体化编制方法[J]. 交通运输系统工程与信息, 2021, 21(3): 176-186.

ZHONG Ming-xuan, YUE Yi-xiang,ZHOU Lei-shan. Scheduling Method for Integrated Plan of Train Operation and Shunting Operation in High-speed Railway Station[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(3): 176-186.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract30258.shtml

http://www.tseit.org.cn/CN/Y2021/V21/I3/176

参考文献

[1] CHAKROBORTY P, VIKRAM D. Optimum assignment of trains to platforms under partial schedule compliance [J]. Transportation Research, Part B, 2008, 42(2): 0-184.

[2] CAPRARA A, GALLI L, TOTH P. Solution of the train platforming problem[J]. Transportation Science, 2011, 45 (2): 246-257.

[3] QI J G, YANG L X, GAO Y, et al. Integrated multi-track station layout design and train scheduling models on railway corridors[J]. Transportation Research Part C: Emerging Technologies, 2016, 69: 91-119.

[4] 彭其渊, 宁佳, 鲁工圆. 大型高铁客运站到发线运用调整模型及算法 [J]. 铁道学报, 2019, 41(1): 16- 25. [PENG Q Y, NING J, LU G Y. Model and algorithm for train platform scheme rescheduling at large high-speed railway station[J]. Journal of the China Railway Society, 2019, 41(1): 16-25.]

[5] LIU S Q, ERHAN K. Scheduling trains as a blocking parallel-machine job shop scheduling problem[J]. Computers and Operations Research, 2009, 36(10): 2840-2852.

[6] 白紫熙, 周磊山, 王劲, 等. 基于拉格朗日的高速铁路车站作业优化[J]. 交通运输系统工程与信息, 2014, 14 (4): 120-125. [BAI Z X, ZHOU L S, WANG J, et al. A Lagrangian relaxation model for high-speed railway station operation optimization[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(4): 120-125.]

[7] ARMSTRONG J, PRESTON J, POTTS C, et al. Addressing nodal constraints on the capacity of railways [J]. Proceedings of the Institution of Mechanical Engineers, Part F: Journal of Rail and Rapid Transit, 2017, 231(5): 637-646.

[8] LAMORGESE L, MANNINO C. An exact decomposition approach for the real-time train dispatching problem[J]. Operations Research, 2015, 63(1): 48-64.

[9] SAMA M, PELLEGRINI P, D' ARIANO A, et al. Ant colony optimization for the real-time train routing selection problem[J]. Transportation Research Part B: Methodological, 2016, 85: 89-108.

[10] 郭彬, 周磊山, 唐金金, 等. 高速铁路大站作业计划鲁棒性链式优化研究[J]. 铁道学报, 2017，39(7): 14-21. [GUO B, ZHOU L S, TANG J J, et al. Study on robustness improvement of high-speed railway station operation plan based on operational chain optimization [J]. Journal of the China Railway Society, 2017, 39(7): 14-21.]

[11] KUMAR R , SEN G, KAR S, et al. Station dispatching problem for a large terminal: A constraint programming approach[J]. Interfaces, 2018, 48(6): 510-528.

[12] LEE Y S, CHEN C Y. A heuristic for the train pathing and timetabling problem[J]. Transportation Research Part B: Methodological, 2009, 43(8/9): 837-851.

[13] 苗建瑞, 于勇, 孟令云, 等. 面向稳定性的高速铁路车站作业计划优化方法[J]. 交通运输系统工程与信息, 2012, 12(3): 115-121. [MIAO J R, YU Y, MENG L Y, et al. Stability- oriented optimization of train platforming problem on high speed railway[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(3): 115-121.]

[14] BURGGRAEVE S, VANSTEENWEGEN P. Robust routing and timetabling in complex railway stations[J]. Transportation Research Part B: Methodological, 2017, 101: 228-244.

[1]	耿庆桥, 贾元华, 陈军团. 基于变权可拓物元的铁路“走出去”公私合营项目风险决策[J]. 交通运输系统工程与信息, 2022, 22(2): 64-71.
[2]	戚建国, 周厚盛, 杨立兴, 周亚茹, 张春田. 灵活编组条件下轨道交通客货协同运输方案优化[J]. 交通运输系统工程与信息, 2022, 22(2): 197-205.
[3]	张晓明, 徐芳, 江文辉, 蒋朝哲. 考虑资金约束的中欧班列运价与运量决策分析[J]. 交通运输系统工程与信息, 2022, 22(1): 30-36.
[4]	张春田, 戚建国, 杨立兴, 高原, 高自友. 基于不确定旅客需求的高速铁路鲁棒列车开行方案研究[J]. 交通运输系统工程与信息, 2022, 22(1): 115-123.
[5]	周勇, 张杰, 钟祾充, 李文锋, 王国栋. 铁路集装箱中心站多轨道吊柔性协同调度优化[J]. 交通运输系统工程与信息, 2022, 22(1): 133-141.
[6]	牛惠民. 轨道列车时刻表问题研究综述[J]. 交通运输系统工程与信息, 2021, 21(5): 114-124.
[7]	胡臣杰, 张军. 基于时空等待特征系数的大型活动出行规划研究[J]. 交通运输系统工程与信息, 2021, 21(4): 148-155.
[8]	刘葛辉, 陈绍宽, 刘爽, 金华, 王丹阳. 资源约束下城市轨道交通基础设施维修任务安排优化模型[J]. 交通运输系统工程与信息, 2021, 21(3): 163-169.
[9]	徐智勇. 铁路电分相布设及纵断面协同优化研究[J]. 交通运输系统工程与信息, 2021, 21(3): 170-175.
[10]	吕敏, 帅斌, 周照玉, 张士行, 左静, 李林卿. 考虑边境站延误风险的中欧班列运输路径决策[J]. 交通运输系统工程与信息, 2021, 21(3): 254-259.
[11]	张蒙蒙, 许茂增. 考虑政府补贴决策的中欧班列竞合关系研究[J]. 交通运输系统工程与信息, 2021, 21(2): 16-21.
[12]	李岸隽，王典，彭其渊. 基于个体出行链的区域城际铁路规划方法研究[J]. 交通运输系统工程与信息, 2021, 21(2): 30-36.
[13]	刘晓伟，晏启鹏，倪少权，吕苗苗，吕红霞. 考虑空车调配协调的货物列车开行方案优化研究[J]. 交通运输系统工程与信息, 2021, 21(2): 180-188.
[14]	杨森炎，宁连举，商攀. 基于时空状态网络的电动物流车辆路径优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 196-204.
[15]	李晓娟，石佳娜，李得伟，闫振英. 考虑定制化列车的运行图与能力协同优化方法[J]. 交通运输系统工程与信息, 2021, 21(1): 95-100.