基于定序优化的高速铁路网络列车运行图优化

周文梁，屈林影，史峰，邓连波

(中南大学 交通运输工程学院，湖南 长沙 410075)

在我国高速铁路网络化运营背景下，构建高速铁路网络化运输组织优化方法迫切需要，特别是网络列车运行图的铺划，由于需要在叉点站衔接多个线路方向，使本来难度很大的列车运行图铺划方法变得更为复杂。目前，针对网络列车运行图铺划方法的研究仍然较少。马建军等[1]将铁路路网表示为分层节点图，将列车运行图表示为时间序列，基于离散事件方法计算列车到发时间；彭其渊等[2−3]通过不断向子路网增加区段，使运行图铺划范围不断扩大，最终获得整个路网运行图；同时通过在列车运行图时空局域内设置和滚动窗口，每次优化窗口中运行线来动态地完成网络运行图铺划；Dorfman等[4]将各种列车优先策略融合到列车离散事件仿真框架中来解决路网列车运行图铺划问题；王涛等[5]采用分层多级优化分枝定界算法，针对列车调度问题给出了一种基于替代图的列车运行图修正及优化方法；Eva等[6]进一步引用了ANLS算法对旅客等待时间进行优化；文超等[7]给出了在运行图铺化过程中单个列车化解冲突的方法；白紫熙等[8]在给定列车车站到发顺序的基础上，进一步采用原始对偶算法优化列车车站到发时间；史峰[9]基于分层铺化的思想确定速度优先级，给出相同径路的运行图编制；而周文梁等[10]通过设计高铁线路列车运行图的有向图表示形式，以此结合文献[8]和[9]方法优化列车到发作业顺序以及到发时刻；Kaspi等[11]采用交叉熵算法对列车运行图和开行方案进行综合优化，而ZHOU等[12]基于拉格朗日松弛分解方法协同优化列车车站径路与车站到发时刻。本文在文献[10]研究方法的基础上，通过在车站对各衔接区间的接发列车作业进行组合约束，以列车旅行时间最少为目标，建立高铁网络运行图优化模型；通过扩展高铁网络松弛运行图的有向图表示形式，建立网络松弛运行图的定序优化线性规划模型，在网络松弛运行图中以平移作业组、交换作业顺序、变更停站方案等方法优化网络运行图。

1　网络运行图优化模型与求解思想

高速铁路网络由客运站和各相邻客运站间的线路区间组成，记为N=(S,E)，其中S为客运站集，为区间集。每个客运站至少衔接一个区间(或方向)，车站 sk衔接的区间集为

描述网络运行图最关键的环节在于描述作业间隔时间时必须考虑作业的衔接区间。对于车站sk的2个衔接区间，不同列车分别经过区间e1和e2并同在车站sk作业时，作业之间需要满足如下时间间隔：

以上各项作业时间间隔查定值与车站布局和列车过站径路等因素有关。一些作业对之间因为有足够的安全保障，可以不作时间间隔约束。

设高速铁路网络 N = ( S,E)上开行旅客列车集为Ω。对于列车i∈Ω，记oi为始发站，di为终到站，分别表示其经由的区间序列与车站序列，为始发时间域分别为列车i在区的启动附加时间、纯运行时间和停止附加时间；列车i在车站的最少停站时间；列车i在车站的停站标志，若列车i在车站sk停车，则列车i从车站sk经区间开往车站的出发、到达作业时刻分别记为另记区间 e的维修天窗为

以列车旅行时间最少为优化目标，结合线路运行图优化模型[10]和网络运行图中作业间隔的衔接区间属性，建立高速铁路网络列车运行图优化模型如下：

以上模型中目标函数式(1)为最小化列车旅行时间，其中符号Θ表示两整数关于运营周期T的模运算；式(2)~(5)分别为不同时出发时间间隔、不同时到达时间间隔、不同时发到时间间隔以及不同时到发时间间隔约束，式(6)和(7)分别为列车区间运行时间、车站停留时间约束，式(8)为列车始发时间约束，式(9)为区间天窗时间约束，式(10)与(11)为变量取值约束。

模型式(1)~(11)是一个大规模优化问题，本文借助于文献[10]求解思想设计求解算法。首先在忽略各列车车站作业间隔约束关系下，根据列车始发时间分布和列车区间运行时间等确定初始网络松弛运行图，然后在保持其它作业之间的顺序关系的条件下，按一定冲突选择策略逐步选择化解列车作业冲突，直至所有冲突全部化解为止，获得完整的高铁网络运行图。

2　网络松弛运行图的有向图表示形式

线路松弛运行图的多平行四边形表示形式的构造可通过将一端边界上冲突相关的运行线在另一端添加该运行线的副本(与原运行线段相差一个时间周期T的运行线段)以准确反映列车作业之间的位置关系。对于网络松弛运行图，需通过判断增加必要的运行线副本来保持叉点站各衔接方向运行线的位置关系，形成网络松弛运行图的扩展多平行四边形。衔接4个方向的网络松弛运行图的多平行四边形如图 1 所示，其中，BDD′B′和 CEE′C′分别表示相交在车站中心线AA′的2个平面，4个衔接方向的运行图铺划在这4个半平面上，其中，列车1与2经由站均为车站E，A与C，而列车3与4经由站分别为车站D，A与B。此外，以虚线表示的列车1与3运行线作为平行四边形表示形式的右边界，与其对应的左边界构成一个周期，如1 d1 440 min。

图1　网络松弛运行图的多平行四边形表示形式Fig. 1　Multi-parallelogram of relaxed train diagram on rail network

记各列车在车站的到发作业为点集Vz，各列车的始发时间域上下限时间为点集Vs，各区间两端车站相应的天窗起始、终止时间为点集Vw，获得点集V=Vz∪Vs∪Vw；将车站所有存在作业间隔时间限制的相邻定序列车作业间(冲突运行线段的相关作业除外)沿时间增加方向作弧得相邻作业弧集 Ap，将各区间运行线段两端作业沿时间增加方向作弧的区间运行弧集Ay，将各列车在同一车站的到达作业至发车作业间作弧得停站弧集At，将各列车始发作业至其始发时间域上限时间、列车始发时间域下限时间至其始发作业间作弧得始发时间域弧集As，将列车运行图中各区间两端车站相应的天窗时间与其紧前或紧后列车作业间沿时间增加方向作弧得天窗弧集Aw，将一段边界线上列车作业与另一端边界线上对应作业沿时间增加方向作弧得周期约束弧集Az，获得弧集，由此便得网络松弛运行图的有向图表示形式 G = ( V,A)。图 1中多平行四边形运行图对应的有向图如图 2所示(图中包含区间运行弧、停站弧、作业时间间隔弧及周期约束弧)，其中，区间弧对应于列车区间运行，如区间弧(1,2)与(3,4)分别对应于列车1在两区间的运行；停站弧对应于列车车站停车过程，如停站弧(2,3)与(6,7)分别对应于列车1与3在车站A的停车过程，若列车不停车，则将其权值设为0即可；作业间隔弧对应于列车作业之间的间隔，如间隔弧(1,9)与(2,6)分别对应于同径路列车1和2进入区间间隔与不同径路列车1和3离开区间间隔；而周期弧为边界约束，如周期弧(1,17)保证了同一列车在相邻周期的时间间隔正好为周期长度。值得说明的是，在网络状态下不同运行径路列车在叉点站存在作业时间间隔要求，如图2中间隔弧(2,6)与(3,7)描述的正是列车1与3从不同区间进入车站A的时间间隔要求，以及它们离开车站A进入不同区间的时间间隔要求。

图2　网络松弛运行图的有向图表示形式Fig. 2　Digraph of relaxed train diagram on rail network

将列车车站作业时间、列车始发时间域上下限值以及天窗起始、终止时间作为图G中相应点v上的加权 t(v)，同时将每条弧(u,v)尾节点加权与首节点加权的差值定义为该弧上的加权w(u,v)=t(v)−t(u)，确定所有有向弧(u,v)上加权的下限w0(u,v)，便得到网络松弛列车运行图的加权有向图G。

3　网络松弛运行图的定序优化线性规划模型

网络松弛运行图的定序优化指在忽略所有冲突的相关作业之间的顺序关系、保持与冲突外不相关作业之间的顺序关系的条件下，使得列车旅行时间最小化。记Uk为网络松弛运行图的扩展有向图中左端边界线上车站Ssk∈的边界作业集。对于xik∈ Uk或 yik∈ Uk，记 xi′k或 yi′k为其相应右端边界线上作业，根据各类有向弧加权函数约束，建立网络松弛运行图的定序优化线性规划模型如下：

其中：约束式(28)表示列车停站变量与列车车站到发时刻之间一致性约束，即当列车在车站停留，即=1时，列车停留时间至少大于1 min；否则列车停留时间为0。

4　基于定序优化的网络运行图铺划方法

基于定序优化的网络运行图铺划方法是在铺划松弛网络运行图的基础上，每次选择一定数量冲突进行化解；在化解冲突时，先确定其相关作业顺序，然后构造当前松弛运行图的有向图，在此有向图中，保持非冲突作业之间的关系，利用作业平移的方法化解冲突，如此反复，直至获得不存在冲突的网络运行图。若平移作业仍无法完全满足最小作业时间间隔，可进一步结合交换列车作业顺序、变更停站方案或扩大列车始发时间域等优化手段。

4.1　化解冲突及化解方案的选择

根据冲突发生位置将松弛运行图中冲突分为区间冲突和车站冲突。对于区间冲突，可通过让速度等级高的列车在前方或后方车站越行速度等级低列车而化解；对于车站冲突，只需让速度等级高的列车在该车站越行速度等级低列车化解。故冲突化解均需使得冲突运行线平移一定时间距离而满足最小作业间隔时间要求。通常冲突化解平移时间之和越少，所带动平移的运行线数量越少，这既对运行图质量影响较小，也容易实现冲突化解。因此，对于区间冲突应优先选择化解平移时间之和最少越行站进行化解。

每次化解冲突的选择，可简单从松弛运行图中随机选择一定数量冲突，或者根据冲突化解时平移时间以概率方式选择一定数量冲突，这两种方法易操作，但运行图优化质量不明显。为了提高运行图优化质量，这里设计两种冲突选择原则：冲突化解平移时间总和最小原则和冲突化解平移时间差距最大原则。

1) 平移时间总和最小原则

采用平移时间总和最小原则选择数量为λ的化解冲突集C满足：

2) 平移时间差距最大原则采用平移时间差距最大原则选择数量为λ的化解冲突集C满足：

4.2　松弛运行图的定序优化方法

根据当前化解冲突及其化解方案确定当前所有化解冲突作业之间的时间先后顺序后，进而基于有向图调整其作业时间使得其满足最小作业时间间隔要求。可采用的方法主要有平移列车作业、交换列车作业顺序、变更停站方案和调整列车始发时间域等关键技术。文献[10]详细介绍了区段列车运行图铺划过程中这些关键技术的实现方法。由于网络运行图铺划与区段运行图铺划主要区别在于同时考虑了叉点站对各衔接区间的接发(或通过)作业之间的时间间隔约束，而有向图构造已经完全反映了作业之间的先后关系，因此，文献[10]中关于这些关键技术的实现方法同样适应于网络运行图铺划，因篇幅有限，不再叙述。只是在化解冲突作业平移时，不仅带动一条线路上相关作业平移，也带动所有衔接线路上的相关作业一起平移。

5　网络运行图铺划算例

由13个客运站和20个复线线路区间组成的高铁网络如图3所示(图中标记了以km为单位的路段里程)。在该网络上铺划两种速度等级列车，其中高速度等级列车191对、低速度等级列车158对。高、低速等级列车在各区间的启停附加时分均设为 1分，在各区间的技术速度分别为 320 km/h和 250 km/h。在此基础上，结合区间里程便可计算出2种速度列车在区间的纯运行时间，进一步结合列车区间前后车站停车情况与启停附加时分便可获得其区间运行时分。车站不同衔接方向列车的不同时出发、不同时到达、不同时发到及不同时到发时间间隔为3 min。

图3　高速铁路网络结构示意图Fig. 3　Structure schematic of an example rail network

利用基于定序优化的网络运行图铺划方法求解网络上的列车运行图，下面仅以车站S6衔接的4个区间S4-S6-S5,S3-S6-S8在12:00-18:00时间段内的运行图展示如图4和图5所示。图中很容易看出列车先后通过S4-S6和S6-S5，S3-S6和S6-S8的衔接关系，篇幅所限，列车先后通过其它线路的衔接关系并未画出来，读者可以通过组合这两个图看出它们的衔接关系，如列车Z147先通过区间S4-S6，再通过区间S6-S8。

1) 冲突选择策略对算法优化效率与质量比较

首先随机产生165个运行图铺划实例，分别采用随机策略、最小平移时间策略和最大平移差距策略选择化解冲突优化列车运行图，确定算法计算时间与其列车总旅行时间，统计各策略使得列车总旅行时间、计算时间以及两者为3种策略中最小值的次数以及所占比例如表1所示。由于各冲突选择策略下计算的列车总旅行时间或计算时间可能相等，所以表中各策略次数之和大于铺划实例数 165，百分率之和也不等于1。

图4　区段S4-S6-S5的列车运行图Fig. 4　Train diagram of section S4-S6-S5

图5　区段S3-S6-S8的列车运行图Fig. 5　Train diagram of section S3-S6-S8

表1　在运行实例数165条件下3种冲突选择策略效果比较Table 1　Compare of three conflict-selection strategies used for 165 instances

由表1数据可知：3种冲突选择策略中，最小平移时间策略使列车总旅行时间最小的次数达到84次，占到实例总数的51%；而计算时间最小的次数达到103次，占到实例总数的62%，而使得两者均最小的次数达到63次，占到实例总数的38%。由此可见，相比随机策略和最大平移差距策略，采用最小平移时间策略选择化解冲突能够以最大概率花费较较少的计算时间而获得列车总旅行时间较小的列车运行图。

图6　计算时间随一次同时化解冲突数的变化关系图Fig. 6　Change relation of computing time with the number of disposed conflicts

图7　列车平均延误时间随一次同时化解冲突数的变化关系图Fig. 7　Change relation of average train delay time with the number of disposed conflicts

2) 一次同时化解冲突数量对算法优化效率与质量的影响

分别采用随机策略、最小平移时间策略和最大平移差距策略，依次选择一次同时化解冲突数为 1至 50优化网络运行图，确定各冲突选择策略下计算时间与其列车平均延误时间(列车旅行时间与技术时间之差)随一次同时选择化解冲突数的变化曲线关系分别如图6和图7所示。

由图5和图6可知：每次选择化解冲突的数量对运行图铺划时间和列车平均延误时间的影响不是很明显。这是因为作业冲突化解过程中，冲突作业之间的定序工作量很少，而大部分工作量是调整两作业间隔时间使之满足最小作业间隔时间，所以若将多个冲突进行一次定序，所节约的计算时间相比调整列车作业间隔所花的时间是非常小的。

6　结论

1) 建立了以列车旅行时间最少为目标的网络运行图优化模型，同时考虑了车站上各衔接方向列车到发或通过作业之间约束关系，确保了列车运行图的整体优化质量。

2) 设计基于定序优化的网络列车运行图铺划方法，在铺划初始网络松弛运行图的基础上，通过最小平移时间策略和最大平移差距策略等各种冲突化解策略能够有效地化解网络松弛运行图中冲突，获得完整的网络运行图。

3) 算例分析表明，定序优化冲突化解策略的方法能提高运行图铺化速率并获得较优的列车运行图。而如何进一步将车站到发线、进路等约束考虑到模型和算法中，是有待扩展的重要研究内容。

参考文献：

[1] 马建军, 周磊山, 胡思继. 计算机编制网状线路列车运行图系统研究[J]. 铁道学报, 2000, 22(1): 7−11.MA Jianjun, ZHOU Leishan, HU Siji. Research on train working diagram system of railway netted lines worked out with computer[J]. Journal of the China Railway Society, 2000, 22(1): 7−11.

[2] 彭其渊, 朱松年. 网络列车运行图的数学模型及算法研究[J]. 铁道学报, 2001, 23(1): 1−8.PENG Qiyuan, ZHU Songnian. Study on a general optimization model and its solution for railway network train diagram[J]. Journal of the China Railway Society,2001, 23(1): 1−8.

[3] 彭其渊, 王宝杰, 周党瑞. 基于实用的一种网络列车运行图计算方法[J]. 西南交通大学学报, 1999, 34(5):588−593.PENG Qiyuan, WANG Baojie, ZHOU Dangrui. A practical algorithm for making train diagram of railway network[J]. Journal of Southwest Jiaotong University,1999, 34(5): 588−593.

[4] Dorfman M J, Medanic J. Scheduling trains on a railway network using a discrete event model of railway traffic[J].Transportation Research Part B, 2004(38): 81−98.

[5] 王涛, 张琦, 赵宏涛, 等. 基于替代图的列车运行调整计划编制及优化方法[J]. 中国铁道科学, 2013, 34(5):126−133.WANG Tao, ZHANG Qi, ZHAO Hongtao. A method for generation and optimization of train operation adjustment plan based on alternative graph[J]. China Railway Science, 2013, 34(5): 126−133.

[6] Eva Barrena, David Canca. Single-line rail rapid transit timetabling under dynamic passenger demand[J].Transportation Research Part B, 2014(70): 134−150.

[7] 文超, 彭其渊, 陈芋宏. 高速铁路单个列车运行冲突消解研究[J]. 铁路技术与工程, 2013, 13(10): 2741−2747.WEN Chao, PENG Qiyuan, CHEN Yuhong. Train operation adjustment based on conflict resolution for high-speed rail[J]. Science Technology and Engineering,2013, 13(10): 2741−2747.

[8] 白紫熙, 邵静静. 相同径路的高速列车运行图编制方法[J]. 中国铁道科学, 2015, 36(6): 135−140.BAI Zixi, SHAO Jingjing. Drawing method for working diagram of high speed train with same path[J]. China Railway Science, 2015, 36(6): 135−140.

[9] 史峰. 定序单线列车运行图的原始－对偶算法[J]. 铁道学报, 1996, 18(1): 8−20.SHI Feng. A primal-dual algorithm for making train diagram fixed order on single-track rail lines [J]. Journal of the China Railway Society, 1996, 18(1): 8−20.

[10] 周文梁, 史峰, 陈彦. 基于定序优化的客运专线列车运行图铺划方法[J]. 铁道学报, 2010, 32(1): 1−7.ZHOU Wenliang, SHI Feng, CHEN Yan. A method for drawing train diagram of dedicated passenger line based on fixed order optimization[J]. Journal of The China Railway Society, 2010, 32(1): 1−7.

[11] Kaspi M, Raviv T. Service-oriented line planning and timetabling for passenger trains[J]. Transport Science,2013, 47(3): 295−311.

[12] ZHOU Wenliang, TENG Hualiang. Simultaneous passenger train routing and timetabling using an efficient train-based Lagrangian relaxation decomposition[J].Transportation Research Part B, 2016(11): 409−439.