考虑客流需求的高速铁路列车运行图加线模型与算法

赵天胤; 张永祥; 王蔚; 彭其渊; 郭经纬

doi:10.3969/j.issn.0258-2724.20240637

考虑客流需求的高速铁路列车运行图加线模型与算法

doi: 10.3969/j.issn.0258-2724.20240637

赵天胤^{1, 2,},
张永祥^{1, 2},
王蔚^{1, 2, ,},
彭其渊^{1, 2},
郭经纬³

1.
西南交通大学交通运输与物流学院，四川成都 611756
2.
西南交通大学综合运输智能化国家地方联合工程实验室，四川成都 611756
3.
澳门城市大学商学院，澳门 999078

基金项目: 国家重点研发计划（2022YFB4300502）；国家自然科学基金项目（72201218）；四川省科技计划（2025YFHZ0125，2023NSFSC0901）

详细信息

作者简介:
赵天胤（1997—），男，博士研究生，研究方向为运输组织优化理论与方法，E-mail：zhaotianyin@my.swjtu.edu.cn

通讯作者:
王蔚（1982—），男，副研究员，博士，研究方向为轨道交通运输组织仿真及优化，E-mail：ww@swjtu.edu.cn

中图分类号: U292.62
计量
- 文章访问数: 151
- HTML全文浏览量: 52
- PDF下载量: 24
- 被引次数: 0
出版历程
- 收稿日期: 2024-12-02
- 修回日期: 2025-01-24
- 网络出版日期: 2025-03-29
- 刊出日期: 2025-02-26

Optimization Model and Algorithm of Additional Trains Scheduling in High-Speed Railway Timetables Considering Passenger Demand

ZHAO Tianyin^{1, 2
,},
ZHANG Yongxiang^{1, 2},
WANG Wei^{1, 2
, ,},
PENG Qiyuan^{1, 2},
GUO Jingwei³

1.
School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 611756, China
2.
National United Engineering Laboratory of Integrated and Intelligent Transportation, Southwest Jiaotong University, Chengdu 611756, China
3.
Faculty of Business, City University of Macau, Macau 999078, China

摘要

摘要:
在既有列车运行图中插入新增列车运行线是铁路运输企业编制每季度列车运行图和日计划中列车运行计划所常采用的方法. 然而，传统基于人工的编制手段效率低且难以保证列车运行图编制质量. 对此，本文以降低铁路运营和调度成本以及运输尽可能多的旅客等为优化目标，基于离散时空网络构建综合优化列车开行方案和新增列车运行线的整数线性规划模型；针对模型特点，设计基于拉格朗日松弛的启发式求解算法，将原问题分解为列车开行方案优化子问题和一组为单列列车搜索费用最小的时空路径子问题；最后，以京沪高速铁路为算例，验证模型的正确性和算法可行性. 研究结果表明：所提方法能快速自动生成新增列车运行线后的列车运行图，且求得的上界解质量相比顺序求解方法平均提升了4.58%.
- 新增列车运行线 /
- 列车开行方案 /
- 拉格朗日松弛 /
- 客流需求 /
- 离散时空网络
Abstract: Objective
Railway operators enhance the alignment between transportation services and passenger demand by making quarterly adjustments to the basic train timetable and preparing next-day train operation plans based on it. However, the structural complexity of the basic timetable significantly complicates the generation of these two technical plans. To address this challenge within the framework of manually generated transport plans, railway operators commonly insert additional spatio-temporal train paths into the basic timetable while making reasonable adjustments to the original paths. Furthermore, incorporating passenger demand into the generation of these two technical plans can evidently result in train timetables that better meet market needs.
Methods
To effectively utilize the remaining capacity of the basic timetable, two adjustment measures were applied to trains in the original train timetable: flexible adjustment of train stop patterns and time, including departure time at origin stations, and dwell time at intermediate stations. An integer linear programming model was developed for the integrated optimization of line planning and additional train scheduling problems based on a spatio-temporal network modeling framework. The objective function was formulated from the perspective of balancing the interests of both railway operators and passengers. The benefits of railway operators were represented by the total travel time of all trains and penalties imposed for adjusting stop patterns, as well as departure and dwell time of original trains, whereas passenger benefits were reflected in maximizing the number of passengers transported. The coefficients of the sub-objectives were determined based on practical operations and empirical experience. Moreover, practical constraints were considered, including the uniqueness of train stop patterns, train capacity, the relationship between passenger demand allocation decision variables and train stop pattern selection variables, minimum headway requirements, and the coupling of subproblems. Given the characteristics of the model, a Lagrangian relaxation-based heuristic algorithm was designed. By dualizing the headway requirements and coupling constraints into the objective function through Lagrangian multipliers, the original problem was decomposed into two independent subproblems: a line planning subproblem and an additional train scheduling subproblem. The algorithm iteratively solved subproblems by calling the commercial solver and a forward dynamic programming algorithm, respectively.
Results
To evaluate the effectiveness of the proposed model and algorithm, a set of numerical experiments based on the Beijing–Shanghai high-speed railway corridor was conducted. Moreover, the same scenarios were also solved using a sequential solving approach commonly employed in practical operations, where the line planning problem was optimized first, followed by the generation of the train timetable. The efficiency of the proposed algorithm was more comprehensively evaluated by comparing the solution results of the two methods.In all scenarios, the proposed algorithm successfully obtained the optimal upper bound solution within the maximum number of iterations, with an average optimality gap of 3.21%. Compared to the sequential solving approach, the proposed model and algorithm improve the quality of the upper bound solutions by an average of 4.58%. This improvement is attributed to the fact that the sequential solving approach prioritizes higher-quality solutions in the line planning subproblem, which, in turn, leads to a more significant deterioration in the solution quality of the additional train scheduling subproblem. Besides, the proposed algorithm is able to achieve a feasible upper bound solution within the first 200 iterations, while further iterations can yield even better results.The optimized train timetable shows that approximately 5% of the original trains undergo time adjustments exceeding 10 minutes throughout their entire journey. Moreover, for around 10% of the original trains, significant adjustments have been made to certain timings along the journey, whereas their departure from origin stations and arrival time at destination stations remain unchanged. Both findings reflect the structural complexity of the timetable and its inherent robustness. Passenger demand allocation results indicate that over 10% of the trains have seat occupancy rates below capacity across three or more segments. However, compared to short-distance passengers, a larger proportion of long-distance passengers remains unserved.
Conclusion
By considering passenger flow demand, integrating the additional train scheduling with the line planning can generate train timetables that provide higher overall system efficiency. To reduce the difficulty of basic timetable adjustments and train operation plan generation, spatio-temporal paths of additional trains should be scheduled in a way that maintains the arrival and departure time of higher-priority trains and minimizes changes to the overtaking relationships among trains. Additionally, to lower operational costs for railway operators and better meet passenger travel needs, priority should be given to accommodating long-distance passenger travel demand in daily operations. In future research, more practical factors should be incorporated into the modeling process, such as more detailed and accurate representations of the interests of railway operators and passengers, as well as time-varying passenger demand. Besides, the problem-solving framework should integrate other operational aspects, such as platform track allocation and rolling stock circulation plan, so as to further enhance the feasibility of the generated train timetables.
- additional trains scheduling /
- line planning /
- Lagrangian relaxation /
- passenger demand /
- discretized spatio-temporal network

HTML全文

为适应不断变化的运输需求，铁路运输企业每季度会对既有列车运行图进行调整，并且每日基于既有列车运行图编制次日列车运行计划. 然而，随着高速铁路建设的不断推进，我国高铁网络化运营特征日益凸显. 其中，大量跨线列车的开行，使得繁忙干线的列车运行图结构复杂、难以调整^[1]. 因此，铁路运输企业通常采用在既有列车运行图中插入新增列车运行线的方法来降低调整图编制难度和减少日常调度成本. 此外，旅客作为高速铁路的主要服务对象，在编制新增列车运行线时统筹考虑旅客需求有利于提升旅客服务水平和优化资源综合利用，对于铁路运输企业进一步提高市场竞争力尤为关键.

新增列车运行线编制问题虽尚未引起广泛关注，但受到了部分专家学者的持续研究，且已经积累不少有价值的理论成果. 受实际生产中常用的运输调度方式启发，早期针对这一领域的研究多集中于在既有客运列车运行图中插入货物列车运行线. 文献[2]面向单线铁路提出了以新增列车平均旅行时间最小为目标的优化模型. 文献[3]首次分析了新增列车运行线编制问题的本质，将其视为具有时间窗约束的混合车间调度问题，并基于析取图构建优化模型. 文献[4]开发了基于动态约束生成方法的拉格朗日算法，求解区域路网层面的新增列车运行线编制问题. 文献[5]在考虑运行线路、旅行时间、线路定价和能效对列车路径选择影响的基础上，通过计算可以插入的货物列车运行线数量来评估铁路网络的运能. 文献[6]研究了高速铁路开行货物列车并为其铺画鲁棒运行线的问题，设计了一种整数Benders分解方法进行求解. 由于客运列车的优先级高于货运列车的，在这些研究中，既有图是不可调整的.

多数针对新增客运列车运行线的研究都对既有列车运行线进行调整，通常在目标函数中以最小化调整量的方式对调整幅度加以限制. 基于文献[4]的研究，文献[7]在允许既有列车改变停站的条件下改进优化模型，并采用拉格朗日算法求解. 文献[8]为灵活调整接续方案条件下混合周期和非周期模式的运行图插入新增列车运行线问题，建立以既有运行图调整和无法满足的接续方案数量最少为目标的数学模型. 文献[9]基于时间-车站-股道三维时空扩展网络，研究考虑到发线运用计划的新增列车运行线编制问题. 文献[10]构建以所有列车总旅行时间最短和提供运能与客流需求差最小为目标的0-1整数规划模型. 文献[11]为新增列车设置了柔性发车时间窗，并利用交替方向乘子法高效求解所提模型. 文献[12]基于事件活动图构建了以成功插入的新增列车运行线数量最多为目标的优化模型. 文献[13]聚焦多式联运背景下，开行新增列车以应对其他运输方式中断产生的突发大客流问题，建立以尽可能满足客流需求和调度成本最低为目标的优化模型. 文献[14]研究新增列车运行线和动车组接续方案一体化编制问题，设计滚动时域算法以提高模型求解效率. 文献[15]基于利用现有空闲车底、另购专用车底和利用外局车底3种运输组织模式，考虑高铁枢纽内新增环线公交化列车的问题. 在这些文献中，仅文献[10,13]考虑了客流需求对求解新增列车运行线问题的影响，但这2篇文献均简化了对客流的刻画，并未直接将客流需求分配到具体列车.

新增列车运行线编制问题可以看作一个特定条件下的时刻表编制问题. 因此，近年来列车开行方案和列车时刻表综合优化问题的研究成果能为本文提供理论参考. 文献[16]仅考虑了铁路运输企业相关利益，基于时空状态网络构造以最小化列车总旅行时间为目标的优化模型，并以不同特征的客流数据验证模型可行性. 文献[17]则仅考虑了旅客相关利益，利用鲁棒随机规划模型求解不确定客流条件下的列车时刻表编制问题. 而文献[18]则以车站服务间隔均衡性来刻画旅客利益，以此构建优化模型，并基于遗传算法的原理设计了综合优化算法. 文献[19]以单位时间内提供的运力里程表征运营方利益，以平均等待时间为指标表征旅客利益，为该综合问题的求解提出多层次优化算法. 文献[20]则聚焦地铁首班车时刻表协同编制，以最大化能源节省和最小化旅客旅行时间为目标构建了优化模型；然而，由于列车时刻表的编制过程中不需要对既有列车运行线进行调整，因此，目标函数中并未考虑这一因素.

本文聚焦新增列车运行线编制问题，在考虑客流需求的基础上，研究列车开行方案和新增列车运行线综合优化问题，以期提升我国高铁每季度列车运行图和日计划中列车开行计划等技术文件的编制质量和效率，为相关技术决策提供参考依据. 创新点体现为：1）为获得整体质量更高的列车时刻表，允许既有列车灵活调整运行时刻和停站方案；2）建立客流决策变量和列车开行方案选择变量耦合约束，基于客流优化既有列车停站模式的选择及新增列车开行方案的决策，并实现客流需求分配到具体列车；3）利用拉格朗日松弛技术设计启发式算法，以实现大规模实际问题的高效求解；4）通过与模拟生产现场中使用的顺序求解方法进行对比，验证所设计算法的优越性.

1. 问题描述

新增列车运行线编制问题的核心在于将需要开行但尚未纳入既有列车运行图的额外列车，在既有图的剩余空间中合理铺画运行线. 然而，由于安全间隔等因素的限制，仅依赖既有图剩余空间可能难以找到可行的新运行线，或仅能生成质量较低的新运行线. 因此，需要通过调整既有列车运行线，在既有图中整合出更多空间，以满足新增列车运行线的编制需求. 此时，若将新增列车视为一种“干扰”，既有列车运行线的调整与列车实时调整问题的研究内容存在一定相似性^[3].

列车开行方案是编制列车运行线的重要依据. 在调整既有列车及编制新增列车的开行方案时，由于既有列车可能仍有空闲运能，且旅客在出行时不区分所乘列车是否为新增列车. 相较于固定既有列车开行方案，依据新增客流决策新增列车的开行方案，将所有客流作为整体进行优化显然更为合理，更有利于提升系统整体效益. 此外，若将列车开行方案和新增列车运行线分阶段编制，可能导致优化后的开行方案无法找到可行的列车运行图. 因此，将列车开行方案与新增列车运行线相结合进行综合优化编制，显得尤为必要.

本文以单条双线高速铁路中单方向的列车及其对应客流需求为研究对象. 图1（a）、（b）为08 ：00—08 ：50间上行方向的既有列车运行图和优化列车运行图（其线路由3个区段和4个车站组成）. 列车的最大载客量为5人，区间的通通运行时分为5 min. 图中的条形图表示客流分配信息. 例如，列车G106在车站A处的2个条形图分别表示该列车上搭载了1名从车站A到车站D的旅客，以及4名从车站A到车站B的旅客.

图 1 在既有列车运行图中编制新增列车运行线示例

Figure 1. Illustration of scheduling additional trains into an original train timetable

下载: 全尺寸图片幻灯片

本文基于确定的备选新增列车集合，通过客流需求和铁路运营、调整成本来决定开行的新增列车数量和方案，而非提前给定. 具体而言，在图1所示的案例中，为满足变化后的客流需求，现计划在备选新增列车集合中选择合适的新增列车开行. 备选新增列车集合共有2列列车：一列为仅有1种备选停站方案的直达列车G112；另一列为有3种备选停站方案的普通列车G110. 3种备选停站方案分别为仅停靠车站B，仅停靠车站C和停靠车站B、C. 两列车的始发时间窗均为08 ：00—08 ：15.

在固定既有列车运行线条件下，图2（a）虚线代表的运行线反映了既有图余量能力：可容纳一列直达列车或一列仅停靠车站B的列车，而这未必能满足新增客流的需求. 因此，本文考虑2种调整既有列车的策略. 策略1：灵活调整停站. 停站模式是影响列车间到发顺序的关键因素. 在图1（a）所示的既有图中，列车G106在车站B的停靠导致后续列车若要以最小追踪间隔从车站A始发，则必须在车站B停靠；否则，两列车之间的发车间隔将不得不增加，导致运行图能力的浪费. 若将列车G106的停站调整为车站C或途中不停站，追踪发车的后续列车将能够在不增加列车G106旅行时间的前提下有更多停站模式的选择. 考虑到列车运行图结构要求、不同起讫点（OD）对间客流差异等实际因素影响，为避免出现不合理的停站模式，本文为既有列车提前设置备选停站方案. 策略2：调整运行时刻. 策略1的实施必然带来运行时刻调整. 如图2（b）所示，仅调整运行时刻同样能为新增列车运行线提供新的方案. 将除列车G106之外的其他列车运行时间统一推迟4 min，则可以在更早的时间插入1条停靠车站B的列车运行线. 同时实施2种策略可能导致既有列车间的到发顺序、越行车站发生变化，这些在本文中是允许的. 除此之外，取消既有列车开行、调整列车运行区间等调整策略不予考虑.

图 2 不同调整策略条件下的新增列车运行线方案

Figure 2. Additional train scheduling results based on different adjustment measures

下载: 全尺寸图片幻灯片

新增客流需求优化后的列车运行图如图1（b）所示. 调整后的运行图中，列车G110为新增列车，列车G104新增了车站B的停靠，列车G106则将原先的车站B停靠调整为车站C. 与既有图相比，在规定时间段内，调整图新增了一列列车，车站B、C的列车停靠次数均增加了一次. 在既有列车平均旅行时间增加1.00 min、所有列车平均旅行时间增加0.85 min的情况下，实现了额外运送10名旅客的目标.

2. 模型建立

在高速铁路列车运行图中，以客流需求为基础编制新增列车运行线涉及到列车开行方案优化和新增列车运行线编制2个理论问题. 利用列车运行图自身固有的时空特性，本文基于时空网络构建优化模型.

2.1 建模假设

根据生产现场实际，为进一步简化问题，做如下合理性假设：

假设1　新增列车的运行区间、始发时间窗和备选停站方案等列车要素为提前给定.

假设2　仅考虑车站到发线数量的限制，而不具体为列车安排其占用的到发线.

假设3　不考虑动车组车底数量对开行新增列车的影响，以及忽略动车组交路计划对列车运行时间的限制.

假设4　不允许旅客在中间站换乘，即旅客只能从出发站乘坐一次列车直接抵达目的地.

2.2 模型符号说明

定义集合如下： $K$ 为列车集合， $k、\hat k$ 为列车索引； ${K_{\mathrm{o}}}、{K_{\mathrm{a}}}$ 分别为既有列车和新增列车集合； $S$ 为车站集合， $i、\hat i、j、\hat j$ 为车站索引； $G、{G_k}$ 分别为区间和列车 $k$ 经过的区间集合，而 $（i,\hat i）$ 为区间索引； $L、{L_k}$ 分别为停站方案和列车 $k$ 备选停站方案集合； $T、\hat T$ 为时空网络中离散时间集合， $t、\hat t$ 为时间索引； $V、（i,t）$ 分别为时空网络中的节点集合与索引； $E、{E_k}$ 分别为时空网络中的弧集合和时空网络中列车 $k$ 相关的弧集合， $(i,j,t,\hat t)$ 为弧的索引； $\phi (j,\hat j,t)$ 为不兼容弧集合.

定义参数如下： ${o_k}、{d_k}$ 分别为列车 $k$ 的始发站和终到站； $o_{{\mathrm{dep}},k}、d_{{\mathrm{arr}},k}$ 分别为列车k在既有图中的始发时间和终到时间； ${s_{{\text{dep}},k}}$ 、 ${e_{{\text{arr}},k}}$ 分别为列车在始发站始发时间窗的开始和结束时间； ${h_{\mathrm{a}}}、{h_{\mathrm{d}}}$ 分别为两车间的到达间隔和出发间隔时间； ${h_{\min }}、{h_{\max }}$ 分别为列车在中间站最小和最大停站时间； ${h_{{\mathrm{acc}}}}、{h_{{\mathrm{dec}}}}$ 分别为列车启动和停车附加时分； ${c_k}(i,\hat i,t,\hat t)$ 为列车 $k$ 占用弧 $(i,\hat i,t,\hat t)$ 的成本； ${F_k}$ 为列车 $k$ 的最大定员数； ${L_{{\mathrm{dis}},i}}$ 为车站 $i$ 的中心里程距离； ${P_{ij}}$ 为车站 $i$ 到车站 $j$ 的客流需求； $\bar \theta _i^{(k)}、\theta _i^{(l)}$ 均为0-1指示参数，取值为1时分别表示既有列车 $k$ 和开行方案 $l$ 在车站 $i$ 停靠； $M$ 为一个取值足够大的数.

定义变量如下： $x_k^{(l)}$ 为0-1决策变量，若列车 $k$ 选择停站方案 $l$ 则为1，否则为0； $p_{ij}^{(k)}$ 为整数变量，表示乘坐列车 $k$ 由车站 $i$ 到车站 $j$ 的旅客人数； ${y_k}(i,\hat i,t,\hat t,l)$ 为0-1决策变量，若选择停站方案 $l$ 的列车 $k$ 占用弧 $(i,\hat i,t,\hat t)$ 则为1，否则为0.

2.3 目标函数

在各类资源有限且不足、运输市场供不应求的背景下，铁路运输企业与旅客的利益存在一定冲突. 为实现铁路运输企业成本最小化和旅客利益最大化之间的平衡，本文构建一个多目标优化模型.

铁路运输企业成本由两部分组成：既有列车的运营和调整成本以及新增列车的运营成本. 其中，既有和新增列车的运营成本可以由列车的旅行时间刻画，旅行时间越小，铁路运输企业的运营成本越低. 而为保持列车运行图结构的稳定，并尽量避免对包括动车组交路计划在内的其他运输计划产生影响，铁路运输企业希望尽可能减少对既有列车的调整，即最小化调整成本. 本文对既有列车采取2种策略，针对策略1，最小化停站改变数量为目标Z₁，如式（1）所示.

${{\textit{Z}}_1} = {\eta _1}\sum\limits_{k \in {K_{\mathrm{o}}}} {\sum\limits_{i \in S} {\sum\limits_{l \in {L_k}} {\left| {\left. {\bar \theta _i^{(k)} - \theta _i^{(l)}} \right|} \right.x_k^{(l)}} } },$

(1)

式中： ${\eta _1}$ 为惩罚系数.

针对策略2，调整既有列车的运行时刻和相关运营成本的旅行时间均与列车运行时刻相关，本文利用占用时空弧的费用计算这2项成本. 各类时空弧的费用计算式见. 表中， ${\beta _1}$ 和 ${\beta _2}$ 分别为既有列车和新增列车的权重.

表 1 时空弧费用

Table 1. Spatio-temporal arc costs

列车种类	弧类型	弧费用
既有列车	始发弧	${\beta _1} (\hat t - t + \| {t - o_{{\mathrm{dep}},k}} \|)$
	运行弧	${\beta _1} (\hat t - t)$
	终到弧	${\beta _1} (\hat t - t + \| {\hat t - o_{{\mathrm{arr}},k}} \|)$
新增列车	所有弧	${\beta _2} (\hat t - t)$

下载: 导出CSV

| 显示表格

对于既有列车运行时刻调整，本文仅计算在始发站和终到站产生的运行时刻偏差惩罚. 一方面，运行过程中产生的时刻偏差与停站调整高度相关，而式（1）已对这一调整施加惩罚；另一方面，离开始发站和抵达终到站的时刻不仅直接影响动车组交路计划，还与跨线列车进入或离开其他线路的时刻密切相关. 由此，最小化列车总旅行时间与既有列车运行时刻的调整幅度可以统一转化为占用时空弧费用的最小化，即优化目标Z₂，如式（2）所示.

${{\textit{Z}}_2} = \sum\limits_{k \in K} {\sum\limits_{l \in {L_k}} {\sum\limits_{(i,\hat i,t,\hat t) \in {E_k}} {{c_k}(i,\hat i,t,\hat t){y_k}(i,\hat i,t,\hat t,l)} } } .$

(2)

从旅客角度出发，铁路运输企业应提供足够的运能来尽可能满足更多旅客的出行需求. 因此，本文选用未被运输的旅客人数表征旅客利益，最小化未被运输的旅客人数，即优化目标Z₃，如式（3）所示.

${{\textit{Z}}_3} = {\eta _2}\sum\limits_{i \in S\backslash \left\{ {\left| S \right|} \right\}} {\sum\limits_{j > i} {({P_{ij}} - \sum\limits_{k \in K} {p_{ij}^{(k)}} )} },$

(3)

式中： ${\eta _2}$ 为惩罚系数.

在对既有列车调整施加惩罚的同时，模型还通过惩罚系数 ${\eta _1}$ 和 ${\eta _2}$ 将所有子目标转化为同一量级的费用^[21]. 上述3个子目标构成了模型的总目标Z，如式（4）所示.

$\mathrm{min}\;{\textit{Z}}=\alpha ({{\textit{Z}}}_{1} + {{\textit{Z}}}_{2}) + (1-\alpha ){{\textit{Z}}}_{3},$

(4)

式中： $\alpha$ 为权重系数，用于平衡铁路运输企业和旅客利益在优化目标中的占比.

2.4 约束条件

1）开行方案唯一性约束

每列列车只能选择唯一的开行方案. 对既有列车，由于本文不允许取消既有列车开行，所有既有列车必须选择一个开行方案. 而备选新增列车集合中的列车是否开行，则通过模型优化计算确定. 若新增列车开行，则同样必须选择唯一的开行方案；若不开行，则无需选择任何开行方案. 如式（5）、（6）所示.

$\sum\limits_{l \in {L_k}} {x_k^{(l)} = 1,\quad\forall k \in {K_{\mathrm{o}}}},$

(5)

$\sum\limits_{l \in {L_k}} {x_k^{(l)} \leqslant 1,\quad\forall k \in {K_{\mathrm{a}}}}.$

(6)

2）列车载客量约束

在列车运行过程中，任意断面位置的车上旅客人数不能超过规定的列车最大定员人数，如式（7）所示.

$\sum\limits_{\hat i \in S,\hat i \leqslant i} {\sum\limits_{j \in S,j > i} {p_{\hat ij}^{(k)}} \leqslant {F_k},\quad\forall k \in K} ,\; \forall i \in S\backslash \left\{ {\left| S \right|} \right\}.$

(7)

3）客流和开行方案耦合约束

仅当列车 $k$ 均停靠车站 $i$ 和车站 $j$ 时，由 $i$ 到 $j$ 的旅客才能被分配到列车 $k$ ，如式（8）所示.

$p_{ij}^{(k)} \leqslant M\sum\limits_{l \in {L_k}} {x_k^{(l)}} \theta _i^{(l)}\theta _j^{(l)},\quad\forall k \in K,\forall i,j \in S,i < j.$

(8)

4）流量守恒约束

对于任意列车 $k$ ，仅能在时空网络中选择唯一一条连接其始发站和终到站的完整时空路径，如式（9）所示.

$\begin{gathered} \sum\limits_{i,t:(i,\hat i,t,\hat t) \in {E_k}} {{y_k}(i,\hat i,t,\hat t,l)} - \sum\limits_{i,t:(i,\hat i,t,\hat t) \in {E_k}} {{y_k}(\hat i,i,\hat t,t,l)} = \\ \left\{ \begin{array}{ll} 1,\quad \hat i = {o_k},\hat t = {s_{{\text{dep}}k}},\forall k \in K,\forall l \in {L_k}, \\ - 1, \quad \hat i = {d_k},\hat t = T,\forall k \in K,\forall l \in {L_k}, \\ 0, \quad \forall k \in K,\forall l \in {L_k}. \\ \end{array} \right. \\ \end{gathered}$

(9)

5）安全间隔约束

每条时空弧对应一个不兼容弧集，该弧集由所有与该时空弧不满足安全间隔要求的弧组成. 在任意不兼容弧集 $\phi (j,\hat j,t)$ 中，最多仅允许其中的一条时空弧被占用，如式（10）所示.

$\sum\limits_{k \in K} {\sum\limits_{l \in {L_k}} {\sum\limits_{(i,\hat i,t,\hat t) \in \phi (j,\hat j,t)} {{y_k}(i,\hat i,t,\hat t,l)} \leqslant 1,\quad \forall (j,\hat j) \in G,t \in T} }.$

(10)

6）子问题耦合约束

当开行方案 $l$ 的列车 $k$ 开行时，才能为其在时空网络中搜索一条完整的时空路径. 而备选新增列车集合或停站方案集合中没有被选择的新增列车或开行方案将使用虚拟弧直接连接其始发站和终到站，如式（11）所示.

$\sum\limits_{t,\hat t:(i,\hat i,t,\hat t) \in {E_k}} {{y_k}(i,\hat i,t,\hat t,l)} = x_k^{(l)},\quad \forall k \in K,l \in {L_k},(i,\hat i) \in {G_k}.$

(11)

7）变量取值约束（式（12）～（14））

$x_k^{(l)} \in \left\{ {0,1} \right\},\quad \forall k \in K,l \in {L_k},$

(12)

$p_{ij}^{(k)} \geqslant 0,\quad\forall k \in K,\forall i,j \in S,i < j,$

(13)

${y_k}(i,\hat i,t,\hat t,l) \in \left\{ {0,1} \right\},\quad\forall k \in K,(i,\hat i,t,\hat t) \in {E_k},l \in {L_k}.$

(14)

3. 基于拉格朗日松弛的求解算法

3.1 拉格朗日松弛及问题分解

拉格朗日松弛技术的关键在于确定模型中的难约束，并利用拉格朗日乘子将其添加至目标函数. 上述模型中，第5组约束涉及不同列车间的相互制约关系，而第6组约束涉及2个子问题之间的耦合，是典型的难约束，故引入2个拉格朗日乘子 ${\mu _{j,\hat j,t}}$ 和 ${\lambda _{i,\hat i,k,l}}$ ，并将2组约束松弛到目标函数中，得到原问题的松弛模型 ${{\textit{Z}}_{{\mathrm{LR}}}}$ ，其目标函数如式（15）所示.

$\left\{\begin{aligned} &\min \;{{\textit{Z}}_{{\mathrm{LR}}}} = {\textit{Z}} + \\ &\quad\sum\limits_{k \in K} {\sum\limits_{l \in {L_k}} {\sum\limits_{(i,\hat i) \in {G_k}} {{\lambda _{i,\hat i,k,l}}\Biggr( {\sum\limits_{i,t:(i,\hat i,t,\hat t) \in {E_k}} {{y_k}(i,\hat i,t,\hat t,l)} - x_k^{(l)}} \Biggr)} } } + \\ &\quad\sum\limits_{(j,\hat j) \in G} {\sum\limits_{t \in T} {{\mu _{j,\hat j,t}}\Biggr( {\sum\limits_{k \in K} {\sum\limits_{l \in {L_k}} {\sum\limits_{(i,\hat i,t,\hat t) \in \phi (j,\hat j,t)} {{y_k}(i,\hat i,t,\hat t,l)} } } - 1} \Biggr)} } ,\\ &{\text{s.t. 式（5）～（9）、\;（12）～（14），}}\\ &\quad\;\;\;{\lambda }_{i,\hat{i},k,l}\in R\text{，}\text{ }\forall k\in K,l\in {L}_{k},(i,\hat{i})\in {G}_{k},\\ &\quad\;\;\;{\mu _{j,\hat j,t}} \geqslant 0,\quad\forall (j,\hat j) \in G,t \in T. \end{aligned}\right.$

(15)

2个拉格朗日乘子在算法中利用次梯度方法更新，计算式如式（16）、（17）所示，其中， ${\sigma ^{(n)}}$ 为拉格朗日乘子更新步长， $n$ 为当前迭代次数.

$\begin{split} &\mu _{j,\hat j,t}^{(n + 1)} = \max \Biggr\{ 0, \Biggr.{\sigma ^{(n)}}\Biggr( {\sum\limits_{k \in K} {\sum\limits_{l \in {L_k}} {\sum\limits_{(i,\hat i,t,\hat t) \in \phi (j,\hat j,t)} {{y_k}(i,\hat i,t,\hat t,l)} } } - 1} \Biggr)+\Biggr.\\ &\quad \mu _{j,\hat j,t}^{(n)}\Biggr\}, \quad \forall (j,\hat j) \in G,t \in T , \end{split}$

(16)

$\begin{split} &{\lambda }_{i,\hat{i},k,l}^{(n + 1)}=\mathrm{max}\Biggr\{0,{\sigma }^{(n)}\Biggr({\displaystyle \sum _{i,t:(i,\hat{i},t,\hat{t})\in {E}_{k}}{y}_{k}(i,\hat{i},t,\hat{t},l)}-{x}_{k}^{(l)}\Biggr)+ \\ &\quad{\lambda }_{i,\hat{i},k,l}^{(n)} \Biggr\},\quad \forall k\in K,l\in {L}_{k},(i,\hat{i})\in {G}_{k}. \end{split}$

(17)

由于子问题耦合约束被松弛，原问题被分解为列车开行方案优化子问题和新增列车运行线编制子问题. 其中，列车开行方案优化子问题 ${{\textit{Z}}_{{\text{LRL}}}}$ 仅与变量 $x_k^{(l)}$ 和 $p_{ij}^{(k)}$ 相关，如式（18）所示.

$\left\{\begin{aligned} & \min\; {{\textit{Z}}_{{\text{LRL}}}} = \Biggr(\alpha {\eta _1}\sum\limits_{k \in {K_{\mathrm{o}}}} {\sum\limits_{i \in S} {\left| {\left. {\bar \theta _i^{(k)} - \theta _i^{(l)}} \right|} \right.} } -\\ &\quad \sum\limits_{k \in K} {\sum\limits_{(i,\hat i) \in {G_k}} {{\lambda _{i,\hat i,k,l}}} \Biggr)\sum\limits_{l \in {L_k}} {x_k^{(l)}} }- \\ &\quad (1 - \alpha ){\eta _2}\sum\limits_{k \in K} {\sum\limits_{i \in S\backslash \left\{ {\left| S \right|} \right\}} {\sum\limits_{j > i} {p_{ij}^{(k)}} } } + \\ &\quad(1 - \alpha ){\eta _2}\sum\limits_{i \in S\backslash \left\{ {\left| S \right|} \right\}} {\sum\limits_{j > i} {{P_{ij}}}, } \\ &\quad{\text{s.t. 式（5）～（8）、\;（12）、（13）、\;（16）.}} \end{aligned}\right.$

(18)

而新增列车运行线编制子问题 ${{\textit{Z}}_{{\text{LRA}}}}$ 仅与变量 ${y_k}(i,\hat i,t,\hat t)$ 相关，如式（19）所示.

$\left\{ \begin{aligned} &\min\; {{\textit{Z}}_{{\text{LRA}}}} = \Biggr({\alpha _1}{c_k}(i,\hat i,t,\hat t) + \sum\limits_{(j,\hat j) \in G} \sum\limits_{t \in T:(i,\hat i,t,\hat t) \in \phi (j,\hat j,t)} {{\mu _{j,\hat j,t}}} + \\ &\quad \sum\limits_{(i,\hat i) \in {G_k}} {{\lambda _{i,\hat i,k,l}}}\Biggr) \sum\limits_{k \in K} {\sum\limits_{l \in {L_k}} {\sum\limits_{i,t:(i,\hat i,t,\hat t) \in {E_k}} {{y_k}(i,\hat i,t,\hat t,l)} } }- \\ &\quad \sum\limits_{(j,\hat j) \in G} {\sum\limits_{t \in T} {{\mu _{j,\hat j,t}}} } , \\ &\quad{\text{s.t. 式（9）、\;（14）、\;（16）、（17）.}} \end{aligned}\right.$

(19)

安全间隔约束的松弛进一步将新增列车运行线编制子问题分解为一组单列车搜索费用最小的时空路径子问题.

3.2 基于拉格朗日松弛的求解算法框架

步骤1　初始化. 将迭代次数、最大迭代次数、上界解值、下界解值、拉格朗日乘子和步长设置为初始值.

步骤2　求解列车开行方案子问题. 利用商业求解器Gurobi求解列车开行方案子问题.

步骤3　生成下界方案. 利用前向动态规划算法求解新增列车运行线编制子问题，结合步骤2求得的解计算下界解，并更新最优下界解值 ${ L _{\mathrm{B}}^*}$ .

步骤4　生成上界方案. 先基于下界方案中各列车的拉格朗日利润值对决策开行的列车进行重新排序. 按照新的列车排序，再次利用前向动态规划算法逐列车搜索费用最小路径. 结合步骤2求得的解计算上界解，并更新最优上界解值 ${ U_{\mathrm{B}}^*}$ .

步骤5　更新拉格朗日乘子（式（18）、（19））和步长（ $\sigma^{(n)}=1/(n+1)$ ）.

步骤6　评估解得质量并判断终止条件. 依据上下界间隙 $e_{{\mathrm{gap}}} = (| {U_{\mathrm{B}}^* - L_{\mathrm{B}}^*} |)/\left| {L_{\mathrm{B}}^*} \right| \times 100{\text{%}}$ 计算最优间隙. 判断当前迭代次数是否已经达到设置的最大迭代次数. 若达到，则算法终止，输出结果；否则，返回步骤2.

4. 算例分析

以京沪高速铁路为研究对象，此线路共设有23个车站，其车站名称、车站中心里程及2种标尺下的站间通通时分等详细信息见图3. 研究的规划时段为06：00—15：00，既有运行图中开行下行列车75列，备选新增列车8列. 京沪高速铁路衔接十余条高铁线路，开行了大量跨线列车. 鉴于本文研究对象为单条高速铁路线路，跨线列车仅考虑其在京沪高速铁路上对应的运行区间和运行线. 例如，原哈尔滨西至青岛北的列车在算例中视为运行区间为天津南至济南西的列车. 本算例中涉及的列车运行区间共有19种，其具体分布情况如图3所示. 其中，运行区间由实线表示的列车为长途列车. 以始发时间窗长度为60 min、客流需求为135615人、最大备选停站方案数量为3个，以及备选新增列车运行区间组合方式以长途列车为主的场景作为对照组，依次对上述4个参数进行调整，生成其他实验场景.

图 3 京沪高速铁路详细信息及开行的列车运行区间

Figure 3. Detailed information and train operation sections of Beijing–Shanghai High-Speed Railway

下载: 全尺寸图片幻灯片

实验所需的参数设置如下：到达和出发间隔分别为3、4 min，最小和最大停站时间分别为2、20 min，启动和停车附加时分分别为2、3 min，模型中的参数 $M$ 为5000，最大迭代次数为600次. 在调研基础上，结合现场生产实际和经验，确定目标函数中的各系数值. 目标函数中的权重系数设置如下： $\alpha$ 、 ${\beta _1}$ 和 ${\beta _2}$ 均为0.5. 惩罚系数设置如下： ${\eta _1}$ 、 ${\eta _2}$ 分别为100、1. 本文所提出的算法在 Visual Studio 2013 平台上实现，算法运行环境为 1 台 CPU Intel（R） Core（TM） i5-12600K 3. 7 GHz，32 GB 内存的个人计算机.

为更全面验证所设计算法的可行性及求解效率，本文将其与模拟生产现场中使用的顺序求解方法进行比较. 传统方法的流程是先求解列车开行方案优化子问题，将其结果作为输入求解新增列车运行线编制子问题. 本文针对所有场景分别应用本文设计的基于拉格朗日松弛的求解算法和顺序求解方法进行求解. 表2 详细列出2种方法所得上、下界解的目标函数值、计算时间以及上、下界解的间隔 e_gap. 表中，“Impr”表示基于拉格朗日松弛的求解算法上界质量相对于顺序求解方法上界质量的提升幅度.

表 2 各场景求解结果及求解质量指标

Table 2. Solution results and solution quality metrics for each scenario

对照参数	场景编号	参数设置	顺序求解方法				基于拉格朗日松弛的求解算法
对照参数	场景编号	参数设置	下界解值	上界解值	计算时间/s	e_gap/%	下界解值	上界解值	计算时间/s	e_gap/%	Impr/%
始发时间窗长度	1		7706.15	7976.93	678	3.51	7336.65	7532.89	1174	2.67	5.89
	2	40 min	7705.63	8037.93	678	4.31	7335.56	7664.90	1219	4.49	4.87
	3	50 min	7706.35	7975.68	775	3.49	7336.60	7612.91	1069	3.77	4.77
客流需求	4	115270 人	5633.86	5806.79	614	3.07	5262.99	5491.79	1016	4.35	5.74
客流需求	5	155958 人	9952.70	10142.33	603	1.91	9571.84	9902.13	2534	3.45	2.43
备选停站方案数量	6	短途	7868.33	8054.41	619	1.96	7473.63	7732.41	777	3.46	4.16
备选停站方案数量	7	均匀	7617.67	7834.25	568	2.84	7256.33	7436.75	1520	2.49	5.35
运行区间	8	2 个	9076.02	9254.05	591	2.36	8707.45	8857.30	1190	1.72	4.48
运行区间	9	4 个	8603.21	8741.14	813	2.76	8232.49	8439.19	869	2.51	3.58

下载: 导出CSV

| 显示表格

在 600 次迭代中，本文设计算法均成功求得上、下界解. 对于所有场景，其 $e_{\mathrm{gap}}$ 值范围为 1.72%～4.48%，平均 Gap 值为 3.21%. 相比之下，尽管顺序求解方法同样能够得到上、下界解，但其上界解的质量明显较差. 本文设计算法上界解的质量较顺序求解方法提升了 2.42%～5.89%，平均提升幅度达到 4.58%. 解的质量提升主要是因为顺序求解方法在列车开行方案子问题中获得的更优解，反而导致新增列车运行线编制子问题的解质量显著下降，从而使整体上界解质量较差.

图4为本文设计算法在求解场景9时的收敛曲线. 在第128次迭代时，算法首次找到可行上界解，第129次迭代时，找到最优下界解，第460次迭代时，找到最优上界解. 该收敛特征具有代表性，即在求解过程中，算法基本可以在200次迭代以内找到一个可行的上界解，随后的迭代次数多用于搜索更优的上界解. 求解场景1生成的列车运行图见图5. 图5中，实线代表优化后运行线未被调整或调整幅度没有超过10 min的既有列车，虚线代表调整幅度超过10 min的既有列车，点划线代表新增列车. 运行线的粗细代表列车不同的上座率，线条由细到粗表示上座率由低到高.

图 4 求解场景9时算法迭代过程收敛曲线

Figure 4. Convergence curves of algorithm’s iterative process for solving Scenario 9

下载: 全尺寸图片幻灯片

从图5所示的运行图中可以看出，仅有3%的既有列车全程运行时刻出现大幅度调整，而9%的列车尽管在途中运行时刻的调整超过了10 min，但其始发或终到时间并未发生变化. 前者反映出既有图结构复杂的特点，列车间的到发顺序发生改变可能导致少数列车的运行时刻完全偏离既有运行线；而后者表明既有运行图具有一定的鲁棒性，其冗余时刻可以通过与原本空闲时间的整合，在调整既有列车运行线和编制新增列车运行线时提供更多的可用空间. 对于铁路运输企业而言，在调整既有列车运行线时应保证标杆列车运行线不变，并在调整其余既有列车停站时要尽可能不改变越行车站，从而避免列车到发顺序的变化.

由图5中运行线线宽可知，有10.6%的列车在3个及以上区间的上座率较低. 然而，在未被运输的旅客中长途客流需求占比更高，这显然不利于铁路运输企业的利益. 因此，从铁路运输企业的利益出发，应优先保证长途旅客出行的需求，而这与当前铁路运输企业采取的营销策略是一致的.

图 5 求解场景1生成的列车运行图

Figure 5. Train timetable generated for Scenario 1

下载: 全尺寸图片幻灯片

5. 结　论

本文在考虑调整既有列车运行时刻和停站模式2种策略的基础上，建立了列车开行方案与新增列车运行线综合优化模型和算法，以京沪高速铁路为案例进行分析. 结果表明：

1）在结构复杂、能力紧张的既有图中编制新增列车运行线时，允许对既有列车的运行时刻和停站模式进行合理调整是必要的；为不对其他运输计划产生明显影响，应固定标杆列车运行线，并尽可能不改变其他既有列车被越行的车站.

2）在运能无法满足全部需求的情况下，铁路运输企业应优先保证长途旅客的出行需求，以提高有限资源的利用率.

3）通过实验例证，本文提出基于拉格朗日松弛的启发式算法求解平均最优间隙值为3.21%；相较于模拟生产现场中使用的先确定列车开行方案再编制新增列车运行线的顺序求解方法，本文所提出算法的上界解质量提升了4.58%.

图 1 在既有列车运行图中编制新增列车运行线示例

Figure 1. Illustration of scheduling additional trains into an original train timetable

下载: 全尺寸图片幻灯片

图 2 不同调整策略条件下的新增列车运行线方案

Figure 2. Additional train scheduling results based on different adjustment measures

下载: 全尺寸图片幻灯片

图 3 京沪高速铁路详细信息及开行的列车运行区间

Figure 3. Detailed information and train operation sections of Beijing–Shanghai High-Speed Railway

下载: 全尺寸图片幻灯片

图 4 求解场景9时算法迭代过程收敛曲线

Figure 4. Convergence curves of algorithm’s iterative process for solving Scenario 9

下载: 全尺寸图片幻灯片

图 5 求解场景1生成的列车运行图

Figure 5. Train timetable generated for Scenario 1

下载: 全尺寸图片幻灯片

表 1 时空弧费用

Table 1. Spatio-temporal arc costs

列车种类	弧类型	弧费用
既有列车	始发弧	${\beta _1} (\hat t - t + \| {t - o_{{\mathrm{dep}},k}} \|)$
	运行弧	${\beta _1} (\hat t - t)$
	终到弧	${\beta _1} (\hat t - t + \| {\hat t - o_{{\mathrm{arr}},k}} \|)$
新增列车	所有弧	${\beta _2} (\hat t - t)$

下载: 导出CSV

表 2 各场景求解结果及求解质量指标

Table 2. Solution results and solution quality metrics for each scenario

对照参数	场景编号	参数设置	顺序求解方法				基于拉格朗日松弛的求解算法
对照参数	场景编号	参数设置	下界解值	上界解值	计算时间/s	e_gap/%	下界解值	上界解值	计算时间/s	e_gap/%	Impr/%
始发时间窗长度	1		7706.15	7976.93	678	3.51	7336.65	7532.89	1174	2.67	5.89
	2	40 min	7705.63	8037.93	678	4.31	7335.56	7664.90	1219	4.49	4.87
	3	50 min	7706.35	7975.68	775	3.49	7336.60	7612.91	1069	3.77	4.77
客流需求	4	115270 人	5633.86	5806.79	614	3.07	5262.99	5491.79	1016	4.35	5.74
客流需求	5	155958 人	9952.70	10142.33	603	1.91	9571.84	9902.13	2534	3.45	2.43
备选停站方案数量	6	短途	7868.33	8054.41	619	1.96	7473.63	7732.41	777	3.46	4.16
备选停站方案数量	7	均匀	7617.67	7834.25	568	2.84	7256.33	7436.75	1520	2.49	5.35
运行区间	8	2 个	9076.02	9254.05	591	2.36	8707.45	8857.30	1190	1.72	4.48
运行区间	9	4 个	8603.21	8741.14	813	2.76	8232.49	8439.19	869	2.51	3.58

下载: 导出CSV

参考文献(21)

[1]	鲁工圆,胡留洋,彭慧,等. 基于预发车的高速铁路列车出发追踪间隔时间压缩方法[J]. 西南交通大学学报,2024,59(6): 1368-1377. doi: 10.3969/j.issn.0258-2724.20220064 LU Gongyuan, HU Liuyang, PENG Hui, et al. Method for compressing departure tracking interval of high-speed trains based on pre-departure strategy[J]. Journal of Southwest Jiaotong University, 2024, 59(6): 1368-1377. doi: 10.3969/j.issn.0258-2724.20220064
[2]	INGOLOTTI L, BARBER F, TORMOS P, et al. An efficient method to schedule new trains on a heavily loaded railway network[C]//Advances in Artificial Intelligence–IBERAMIA 2004. Berlin: Springer, 2004:164-173.
[3]	BURDETT R L, KOZAN E. Techniques for inserting additional trains into existing timetables[J]. Transportation Research Part B: Methodological, 2009, 43(8/9): 821-836.
[4]	CACCHIANI V, CAPRARA A, TOTH P. Scheduling extra freight trains on railway networks[J]. Transportation Research Part B: Methodological, 2010, 44(2): 215-231. doi: 10.1016/j.trb.2009.07.007
[5]	MEIRICH C, NIEßEN N. Calculating the maximal number of additional freight trains in a railway network[J]. Journal of Rail Transport Planning & Management, 2016, 6(3): 200-217.
[6]	LI S D, ZUO D J, LI W Q, et al. Freight train line planning for large-scale high-speed rail network: an integer Benders decomposition-based branch-and-cut algorithm[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 192: 103750. 1-103750.28. doi: 10.1016/j.tre.2024.103750
[7]	JIANG F, CACCHIANI V, TOTH P. Train timetabling by skip-stop planning in highly congested lines[J]. Transportation Research Part B: Methodological, 2017, 104(10): 149-174. doi: 10.1016/j.trb.2017.06.018
[8]	徐涵,聂磊,谭宇燕. 基于灵活接续的周期性列车运行图加线模型[J]. 铁道科学与工程学报,2018,15(9): 2439-2447. XU Han, NIE Lei, TAN Yuyan. The adding train paths model on cyclic timetable based on flexible connection[J]. Journal of Railway Science and Engineering, 2018, 15(9): 2439-2447.
[9]	高如虎,牛惠民,江雨星. 基于多维网络的增开列车条件下高速铁路列车运行图调整[J]. 铁道学报,2020,42(5): 1-8. GAO Ruhu, NIU Huimin, JIANG Yuxing. Train timetable rescheduling based on a time-station-track multi-dimensional network under condition of running extra trains for high-speed railway[J]. Journal of the China Railway Society, 2020, 42(5): 1-8.
[10]	LIU Y T, CAO C X. A multi-objective train operational plan optimization approach for adding additional trains on a high-speed railway corridor in peak periods[J]. Applied Sciences, 2020, 10(16): 5554.1-555.29. doi: 10.3390/app10165554
[11]	高如虎,牛惠民. 基于 ADMM 方法的新增列车条件下灵活的列车时刻表优化算法研究[J]. 铁道学报,2021,43(2): 21-29. doi: 10.3969/j.issn.1001-8360.2021.02.003 GAO Ruhu, NIU Huimin. Study on additional train timetable algorithm in flexible manner based on ADMM approach[J]. Journal of the China Railway Society, 2021, 43(2): 21-29. doi: 10.3969/j.issn.1001-8360.2021.02.003
[12]	毛万华,陈亚茹. 高速铁路列车运行图新增列车运行线优化方法研究[J]. 铁道运输与经济,2021,43(11): 1-6,26. MAO Wanhua, CHEN Yaru. Research on optimization method of newly-added train paths based on train running diagram of high speed railways[J]. Railway Transport and Economy, 2021, 43(11): 1-6,26.
[13]	ZHAO J D, LI H Y, MENG L Y, et al. An optimization method of high-speed railway rescheduling to meet unexpected large passenger flow[J]. Journal of Advanced Transportation, 2022, 2022: 5964010.1-5964010.16.
[14]	曲云腾,姚向明,赵鹏,等. 考虑动车组接续的区域城际网运行图加线模型[J]. 铁道学报,2024,46(1): 13-21. doi: 10.3969/j.issn.1001-8360.2024.01.002 QU Yunteng, YAO Xiangming, ZHAO Peng, et al. Model for inserting additional trains into existing timetable for intercity railway network considering EMU connections[J]. Journal of the China Railway Society, 2024, 46(1): 13-21. doi: 10.3969/j.issn.1001-8360.2024.01.002
[15]	赵日鑫,何世伟,张杰,等. 高铁枢纽环线公交化列车新增运行线优化方法[J]. 北京交通大学学报,2025,49(1): 28-37. ZHAO Rixin, HE Shiwei, ZHANG Jie, et al. Optimization method of adding extra train paths for mass transit type in high-speed railway hub loop[J]. Journal of Beijing Jiaotong University,2025,49(1): 28-37.
[16]	刘璐,孟令云,李新毅,等. 考虑旅客需求的停站方案与列车运行图一体化模型与算法[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.
[17]	HASSANNAYEBI E, ZEGORDI S H, AMIN-NASERI M, et al. Demand-oriented timetable design for urban rail transit under stochastic demand[J]. Journal of Industrial and Systems Engineering, 2016, 9(3): 28-56.
[18]	赵子洪. 面向服务间隔时间的列车运行图优化方法研究[J]. 铁道运输与经济,2019,41(7): 33-39. ZHAO Zihong. A research on train diagram optimization method oriented to service interval time[J]. Railway Transport and Economy, 2019, 41(7): 33-39.
[19]	ALBRECHT T. Automated timetable design for demand-oriented service on suburban railways[J]. Public Transport, 2009, 1(1): 5-20.
[20]	FENG J J, LI X, SHI J G, et al. Joint optimization of metro train timetable and stopping plan for the first service period: an integrated energy-efficient and time-saving model[J/OL]. International Journal of Transportation Science and Technology. (2024-10-06)[2024-12-10]. https://api.semanticscholar.org/CorpusID:273492667.
[21]	李冰,任泽强,轩华. 考虑多编组站转场作业的铁路枢纽车流组织优化[J]. 西南交通大学学报,2023,58(3): 489-498,545. LI Bing, REN Zeqiang, XUAN Hua. Optimization of wagon flow assignment with transship work for multiple marshaling stations at railroad terminals[J]. Journal of Southwest Jiaotong University, 2023, 58(3): 489-498,545.

施引文献

附加材料(0)

访问统计

点击查看大图

图(5) / 表(2)

计量

文章访问数: 151
HTML全文浏览量: 52
PDF下载量: 24
被引次数: 0

1. 问题描述
2. 模型建立
2.1 建模假设
2.2 模型符号说明
2.3 目标函数
2.4 约束条件
3. 基于拉格朗日松弛的求解算法
3.1 拉格朗日松弛及问题分解
3.2 基于拉格朗日松弛的求解算法框架
4. 算例分析
5. 结　论

考虑客流需求的高速铁路列车运行图加线模型与算法

doi: 10.3969/j.issn.0258-2724.20240637

作者简介: 赵天胤（1997—），男，博士研究生，研究方向为运输组织优化理论与方法，E-mail：zhaotianyin@my.swjtu.edu.cn

通讯作者: 王蔚（1982—），男，副研究员，博士，研究方向为轨道交通运输组织仿真及优化，E-mail：ww@swjtu.edu.cn

计量

出版历程