考虑高低速列车灵活混行和停站的运行图优化

田小鹏; 牛惠民; 柴和天; 韩瑛; 武硕

doi:10.19713/j.cnki.43-1423/u.T20230005

您当前的位置：

首页 >

文章列表页 >

考虑高低速列车灵活混行和停站的运行图优化

智慧交通与物流 | 更新时间：2023-12-05

- 考虑高低速列车灵活混行和停站的运行图优化
- Optimizing train timetable with flexible mixed traffic and skip-stop patterns for different speed trains
- 铁道科学与工程学报 2023年20卷第11期页码：4074-4084
- 作者机构：
  
  1.兰州交通大学交通运输学院，甘肃兰州 730070
  2.中国铁路兰州局集团有限公司运输部，甘肃兰州 730031
- 作者简介：
  
  田小鹏(1987—)，男，甘肃天水人，副教授，博士，从事运输组织优化研究；E-mail：xptian@mail.lzjtu.cn
- 基金信息：
  
  国家自然科学基金资助项目(72161023);甘肃省科技计划资助项目(22JR5RA380);甘肃省青年博士基金资助项目(2022QB-060;2021QB-54);兰州交通大学“天佑青年托举人才计划”基金资助项目
- DOI：10.19713/j.cnki.43-1423/u.T20230005
  中图分类号：
扫描看全文
田小鹏,牛惠民,柴和天等.考虑高低速列车灵活混行和停站的运行图优化[J].铁道科学与工程学报,2023,20(11):4074-4084.

TIAN Xiaopeng,NIU Huimin,CHAI Hetian,et al.Optimizing train timetable with flexible mixed traffic and skip-stop patterns for different speed trains[J].Journal of Railway Science and Engineering,2023,20(11):4074-4084.
田小鹏,牛惠民,柴和天等.考虑高低速列车灵活混行和停站的运行图优化[J].铁道科学与工程学报,2023,20(11):4074-4084. DOI： 10.19713/j.cnki.43-1423/u.T20230005.

TIAN Xiaopeng,NIU Huimin,CHAI Hetian,et al.Optimizing train timetable with flexible mixed traffic and skip-stop patterns for different speed trains[J].Journal of Railway Science and Engineering,2023,20(11):4074-4084. DOI： 10.19713/j.cnki.43-1423/u.T20230005.

摘要

为了提高不同速度列车对轨道资源的占用效率，在高速铁路列车运行图编制过程中，同步优化了高低速列车的混行数量和停站方案。通过构建分层时空网络来刻画不同速度列车运行过程，选取最小高速列车开行数量和OD停站次数来保证旅客基本的出行要求，利用单列车最大停站次数限制列车停站均衡性，建立基于时空弧变量的线性整数规划模型，实现总列车运行成本最小。在拉格朗日松弛框架下，由于所建模型耦合了不同弧变量于一起，需要松弛大量的耦合约束才能实现模型分解，使得该方法难以产生高质量的下界和原问题可行解。为此，利用变量分离技术，引入列车类型和停站方案2类0-1变量，重构优化模型；运用拉格朗日松弛方法，重构模型能够分解为时空路径子问题、列车类型子问题和停站方案子问题；在子问题求解中，构造附加约束保证列车类型指派的可行性，构建替代停站子问题加速算法求解；基于下界对偶信息，设计了两阶段启发式方法用于求解原问题可行解。以京沪高铁为背景，设置多组不同规模算例，利用上述方法进行求解，结果表明所提方法可以在合理计算时间内有效求解大规模问题，能够获得较紧致下界和近似最优解，并在求解质量上优于传统松弛分解方法，展现出良好的求解性能。

Abstract

To improve the occupancy efficiency of high-speed rail track resources, this paper considered the train timetabling problem integrating flexible mixed traffic and skip-stop patterns for different-speed trains. A layered space-time network was constructed to depict train movements. The minimum required number of high-speed trains and OD-based stops was used to ensure the primary passenger travel demand. The maximum number of single-train stops was required for balance of train stops. Thus, this paper proposed a linear integer programming model with space-time arc variables to minimize train operational costs. Using variable-splitting technique, two types of binary variables associated with train type and skip-stop patterns were separated from the arc-based variables to reformulate the model. Under the Lagrangian relaxation framework, we can decompose the reformulated model into train space-time path subproblems, train type assignment subproblem and skip-stop scheduling subproblem. Furthermore, a set of train-type selection uniqueness constraint was introduced for the train type subproblem to ensure the feasible solution generation. An alternative simplified model was constructed for the train skip-stop subproblem to speed up the subproblem solving, and a dual-solution-based two-stage heuristic method was designed to obtain feasible solutions to the primal problem. Finally, we used several numerical experiments based on Beijing-Shanghai high-speed rail line to verify the effectiveness and efficiency of the proposed approach. The results show that the proposed method can obtain a tight lower bound and a near-optimal solution in a reasonable computational time, and it is superior to the conventional Lagrangian relaxation methods in terms of solution quality.

关键词

列车运行图列车混行停站方案变量分离拉格朗日启发式

Keywords

train timetablemixed trafficskip-stop patternvariable splittingLagrangian heuristic

references

牛惠民. 轨道列车时刻表问题研究综述[J]. 交通运输系统工程与信息, 2021, 21(5): 114-124.

NIU Huimin. Literature review on rail train timetabling problems[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(5): 114-124.

CHANG Y H, YEH C H, SHEN C C. A multiobjective model for passenger train services planning: Application to Taiwan’s high-speed rail line[J]. Transportation Research Part B, 2000, 34(2): 91-106.

FREYSS M, GIESEN R, MUÑOZ J C. Continuous approximation for skip-stop operation in rail transit [J]. Transportation Research Part C: Emerging Technologies, 2013, 36: 419-433.

BURDETT R L, KOZAN E. Techniques for absolute capacity determination in railways[J]. Transportation Research Part B: Methodological, 2006, 40(8): 616-632.

郝亚秋. 不同速度等级列车混行对高速铁路通过能力影响研究[D]. 北京: 北京交通大学, 2016.

HAO Yaqiu. Study on the influence of mixed trains with different speed grades on the capacity of high-speed railway[D]. Beijing: Beijing Jiaotong University, 2016.

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

ZHOU Xuesong and ZHONG Ming. Single-track train timetabling with guaranteed optimality: Branch-and-bound algorithms with enhanced lower bounds [J]. Transportation Research Part B: Methodological, 2007, 41(3): 320-341.

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, 2015, 76: 117-135.

路超, 周磊山, 陈然. 最大通过能力下高速铁路运行图优化研究[J]. 铁道科学与工程学报, 2018, 15(11): 2749-2754.

LU Chao, ZHOU Leishan, CHEN Ran. Optimization of high-speed railway timetabling based on maximum utilization of railway capacity[J]. Journal of Railway Science and Engineering, 2018, 15(11): 2749-2754.

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

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

刘璐, 孟令云, 李新毅, 等. 考虑旅客需求的停站方案与列车运行图一体化模型与算法[J]. 铁道科学与工程学报, 2019, 16(2): 518-527.

LIU Lu, MENG Lingyun, LI Xinyi, et al. Integrated optimization of stopping pattern and train timetable for passenger demand[J]. Journal of Railway Science and Engineering, 2019, 16(2): 518-527.

YANG Lixing, QI Jianguo, LI Shukai, et al. Collaborative optimization for train scheduling and train stop planning on high-speed railways[J]. Omega, 2016, 64, 57-76.

ŞAHIN G, DIGEHSARA A, BORNDÖRFER R, et al. Multi-period line planning with resource transfers[J]. Transportation Research Part C, 2020, 119: 102726.

ZHANG Yongxiang, PENG Qiyuan, YAO Yu, et al. Solving cyclic train timetabling problem through model reformulation: extended time-space network construct and alternating direction method of multipliers methods [J]. Transportation Research Part B, 2019, 128: 344-379.

DAUZÈRE-PÉRÈS S, DE ALMEIDA D, GUYON O, et al. A Lagrangian heuristic framework for a real-life integrated planning problem of railway transportation resources[J]. Transportation Research Part B: Methodological, 2015, 74: 138-150.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

列车运行图稳定性研究综述