高速铁路列车运行图新增列车 运行线优化方法研究

毛万华，陈亚茹

（1.中国铁路兰州局集团有限公司 调度所，甘肃 兰州 730000；2.中国铁道科学研究院集团有限公司 电子计算技术研究所，北京 100081）

0 引言

列车运行图是用以表示列车在区间运行及在车站到发或通过时刻的技术文件，是全路组织列车运行的基础[1]。在实际运营过程中，由于突发事件或节假日客流激增，都需要组织临时加开列车，新增列车运行线可以应用于日常计划编制及列车运行图调整过程中。在新增列车运行线时，需要综合考虑原始列车及新增列车对运行图性能的影响，应在对原始列车影响程度最小的情况下，尽可能从需要新增的列车运行线备选集中加入更多的运行线，以满足客流出行需求。

目前，关于列车运行图新增列车运行线的调整问题研究相对较多。Burdett等[2]提出三阶段加线过程，通过固定或适当移动已铺画的列车运行线实现加线。Tan等[3]将列车加线问题分解为2个子问题，分别是列车重排序问题和列车顺序固定情况下的插线问题，并利用分支定界算法，设计迭代重排序策略求解。徐涵等[4]在周期列车运行图加线过程中，考虑灵活接续约束，实现列车接续与列车运行图的协同优化。江峰等[5]基于时空网络构建模型，考虑列车始发时刻和初始利润，目标函数为运行线总利润最大，设计基于拉格朗日松弛的启发式算法求解，进一步提高算法求解效率。刘敏[6]针对部分客运专线增开本线列车及调整列车开行方案，实现运力资源与需求的合理匹配，进一步优化运输资源配置。王锴楷等[7]考虑货物列车在集结或者编组过程中因外在因素导致部分列车延误，结合运到期限、停站时间限制等约束条件，建立了针对货物列车延迟情况下的列车运行图加线模型，以中欧班列西通道郑州—阿拉山口为例，验证模型的有效性。张小炳等[8]考虑货物运到期限，建立0-1整数规划模型，并设计了模拟退火算法求解。

总体而言，既有文献对列车运行图加线问题的研究主要是基于周期列车运行图。对于非周期列车运行图的调整主要考虑针对加线列车确定的情况，但由于线路通过能力的限制，在新增列车运行线较多的情况下，难以全部实现加线成功。研究针对部分线路列车客座率普遍较高的情况，建立列车运行图新增列车运行线模型，基于提供的新增列车运行线备选集，在尽可能减少对原始列车运行图调整的原则下，以合适的目标函数为导向，优先选择恰当的新增列车运行线组合。

1 高速铁路列车运行图新增列车运行线模型构建

1.1 问题描述

随着高速铁路路网规模的不断扩大，我国高速铁路已经从快速建设阶段向高效运营阶段过渡，为旅客提供更加优质的服务是铁路部门提供运输产品的目标。高速铁路更是以其安全、舒适、便捷的特点，成为广大旅客出行选择的主要交通方式之一。近年来旅客出行需求不断增长，部分高速铁路线路能力紧张，其列车客座率普遍较高，为满足高峰时段或特殊时期旅客快速增长的出行需求，亟需开展新增列车运行线时列车运行图调整问题的研究。通过合理组织加开列车的方式，在充分利用线路剩余通过能力的同时，尽可能多地为旅客提供出行服务。新增列车运行线时，涉及到列车运行图调整问题。主要包含2类列车，一类是原始列车，一类是新增列车。在加入新的列车运行线时，需要满足一定的原则：①保持原有开行列车的开行方案不变，适当调整部分列车在其途经站的到发时间；②新增列车运行线时，需要满足规定的时间窗范围，提高旅客服务的满意度，尽可能减少对原有列车旅行速度的影响。

1.2 事件－活动图

为了更加形象地表示列车运行图中各个元素之间的关联关系，研究利用事件－活动图构建列车运行图新增列车运行线模型。

定义事件－活动图G= （V，A）。点集合V表示事件的集合，具体包括列车在车站的出发或到达事件，即V=Vdep∪Varr，Vdep表示出发事件集合，Varr表示到达事件集合。弧集合A表示活动的集合，任一活动弧可由2个列车事件表示。主要考虑3类活动弧，分别是运行弧（Arun）、停站弧（Adwell）和安全弧（Asafe）。运行弧Arun⊂Vdep×Varr，表示的是一列车在相邻2个车站，由前一车站的出发事件指向后一车站的到达事件；停站弧Adwell⊂Varr×Vdep，表示的是一列车在同一车站的到达事件指向在该车站的出发事件。若到达事件与出发事件发生时间相同，则表示该列车在车站不停车直接通过；安全弧Asafe⊂Aarr×Aarr∪Adep×Adep，表示的是不同列车在同一车站到达和出发事件之间的连接，要满足安全作业时间标准。事件－活动图如图1所示。

1.3 线性规划模型

式中：yi为0-1决策变量，表示列车t（i）状态，对于需要新增列车运行线而言，一共有加线成功或加线失败2种状态。其值为1时，表示该列车被选中加线，否则表示该列车无法加入。对于原始列车而言，默认其状态为加线成功；runemin为运行弧的区间最小运行时分；M表示一个无穷大的正整数；xi，xj表示事件i，j在新时刻表中发生的时间i∈V；V表示列车事件集合；runemax为运行弧的区间最大运行时分；e表示由事件i、事件j构成的活动弧；wi为0-1变量，取值为1时，表示停站方案中，列车t（i）在车站s（i）停车，取值为0时，表示停站方案中，列车t（i）在车站s（i）不停车直接通过；dwemin表示停站弧的最小停站时间；dwemax表示停站弧的最大停站时间；λij为0-1决策变量，其值为1，表示事件i比事件j先发生，否则表示事件j比事件i先发生；he表示任意2个连续事件发生的最小安全间隔时间；zij表示0-1决策变量，其值为1，表示列车t（i）和列车t（j）同时加线成功，即yi=yj= 1；否则，表示至少有1列车加线失败；μ（i）和μ（j）分别表示事件i和事件j发生的下一个事件；twimin和twimax分别表示事件i的最早发生时间和最晚发生时间；V ini表示原始列车事件集合，V ini⊂V；θi表示事件i相对于原图最大的调整程度；πi表示事件i在原时刻表中发生的时刻，i∈V ini；T ini表示原始列车集合。

公式 ⑴ 为模型的目标函数，表示成功加入的列车运行线数量最多。保证在线路能力允许范围内，尽可能多地加入新的列车运行线，以满足旅客出行需求；公式 ⑵ 为区间运行时分约束，runemin和runemax为考虑起动和停车附加时分的区间最小运行时分和区间最大运行时分。当该列车运行线保留或加线成功，即当yi= 1时，需严格满足区间运行时分约束；否则该式恒成立，为无效不等式；公式 ⑶ 为列车停站时分约束，表示列车在车站的停站时间要满足一定的作业时间要求，即位于最大停站时间dwemax和最小停站时间dwemin之间，同时考虑列车运行线状态；公式 ⑷ 和公式 ⑸ 为车站追踪间隔时间约束，表示2列车在同一车站到达、出发或通过时，需要满足的作业时间间隔，其中he为安全间隔时间约束；公式 ⑹ 对非线性约束zij=yi·yj进一步进行了线性化处理，便于后续模型求解。公式 ⑺ 为区间防越行约束，表示任意2列车在区间上一车站的先后顺序与在下一车站的先后顺序要保持一致，即区间不能发生越行；公式 ⑻ 为列车合理始发时间窗约束，表示列车的发车时间要位于合理始发时间下限twimin和上限twimax之间，若twimin=twimax表示列车出发时间为固定时间点；公式 ⑼ 表示原始列车的允许调整时间范围，其中θi为事件i相对于原图最大调整程度；公式 ⑽ 表示原始列车运行线必须保留；公式 ⑾ 为决策变量之间的耦合关系约束；公式 ⑿ 为变量取值约束。

2 案例分析

2.1 数据准备

（1）车站线路数据：选取京沪高速铁路（北京南—上海虹桥）北京南—徐州东区段下行单方向列车运行图铺画为例，涉及到北京南、廊坊、天津南、沧州西、德州东、济南西、泰安、曲阜东、滕州东、枣庄、徐州东共11个车站。

（2）原始列车运行图：考虑始发时间范围为3 h，共包含30列车，并将时间范围限制在6 : 00—9 : 00，原始列车运行图信息如图2所示。

（3）新增列车运行线备选集：考虑客流波动性，设计加入8条列车运行线，并将运行线的停站方案、列车始发、终到时间范围作为模型的输入。允许新增列车运行线信息如表1所示。

由表1可知，新增列车运行线备选集中一共包含8列车，为了尽可能提高旅客出行满意度，规定新增运行线的始发时间不得早于最早始发时间，终到时间不得晚于最晚到达时间。

表1 新增列车运行线信息Tab.1 Information of newly-added train paths

2.2 结果验证

设计一组案例，具体参数设置情况为：允许新增列车运行线数量为8，设置原始列车允许调整时间为5 min，列车停站时间范围为2 ～ 15 min，基于以上参数取值，以新增列车运行线数量最多为目标函数，求解得到新增列车运行线示意图如图3所示，红色标注的线为成功新增的列车运行线。根据模型求解结果发现，成功新增列车运行线信息如表2所示。

表2 成功新增列车运行线信息Tab.2 Information of successfully newly-added train paths

分析求解结果可以发现，当允许新增列车运行线数量较多时，线路剩余通过能力不足以组织全部列车开行，此时模型会按照一定的求解规则选择合适的列车运行线开行。将新增列车运行线前后的列车运行图各项指标进行对比，指标统计分析如表3所示。

表3 指标统计分析Tab.3 Statistical analysis of indicators

综合分析新增列车运行线前后列车运行图各项指标，可以发现，由于新增列车运行线导致线路能力紧张，影响原始列车运行图的性能，比如降低旅行速度、增加停站时间等。同时新增列车的平均旅行速度为177 km/h，与原始列车的平均旅行速度261 km/h相比，其旅行速度也相对较低。这是由于在新增列车运行线时，需要保证对原有列车到发时刻的调整程度尽可能小，这就导致了新增列车运行线需要以牺牲自身旅行速度为代价减少对原有列车运行图的干扰。新增列车运行线后，原始列车的旅行速度由261 km/h下降到209 km/h，这也是受新增列车运行线影响，原有列车的到发时刻调整、停站时间增加导致的。另外，原始列车总调整时间为6 958 min。总调整时间是指原始列车在其途经站到发时刻变化的绝对值之和。由于在案例求解时，设置原始列车始发时间窗调整范围为5 min以内，导致列车在其后续途经站的变化时刻可能会出现累加的情况，从而导致列车全程总调整时间进一步增加。原始列车始发时间变化分布如图4所示，原始列车终到时间变化分布如图5所示。

观察图4数据，可以发现原始列车始发时间调整范围为5 min的列车数量占列车总数的一半以上，其次是调整范围为4 min的列车数量。而原始列车终到时间变化范围主要集中在10 ～ 20 min范围内（不包括10 min，但包括20 min），位于该区间的列车数量约占列车总数的1/3，其次是变化范围为10 min以内（包括10 min）的列车数量。原始列车允许调整时间的参数设置会影响新增列车运行线的难度，从而影响最终成功新增的列车运行线数量。目前模型在求解过程中，只约束了原始列车在其始发站的发车调整时间范围，若是严格限制所有列车在其各个途经站的到发调整时间范围，则模型容易出现无解的情况。

实际列车运行图在调整过程中，需要考虑新增列车运行线的动车组运用及到发线股道运用等众多问题，极大地增加了新增列车运行线的难度。并且由于新增列车运行线备选集中的列车途经车站不同，列车所面向的服务客流不一样，不同列车运行线的优先级也会有所不同，后续可以为新增列车设置不同的优先级，确保高等级列车优先选中加线。同样地，选择不同的目标函数，也会影响模型求解的方向，从而影响新增列车运行线的最终选择。若目标函数选择新增列车服务客流数量最多，模型会倾向于选择为客流较大的OD提供服务的列车；若目标函数选择列车总走行距离最长，则模型会倾向于选择长途旅客列车优先加线。因此，在实际列车运行图调整过程中，需要综合考虑各方面因素，并根据铁路运营部门的需求，选择恰当的目标函数，为实际决策提供辅助支撑功能。

3 结束语

研究通过构建高速铁路列车运行图新增列车运行线模型，在已知新增列车运行线备选集的基础上，以成功新增列车运行线数量最多为目标函数，在充分利用线路剩余通过能力的基础上，尽可能多地加入新的列车运行线。模型实现了新增列车运行线的自主选择，可根据实际需求设置不同的目标函数，从而在线路能力允许范围内，决策最合适的新增列车运行线组合。通过实例结果证明，该模型可以应用于列车运行图的调整或日计划编制阶段，为铁路运营部门提供辅助决策支撑。该模型未考虑动车组运用和股道分配问题，后续需要进一步细化模型约束。