考虑冗余时间的区域铁路车站股道运用计划协同编制优化方法

高全，张英贵，陈治亚，陈曾儒，胡睿华

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

区域铁路是缓解城市群内部交通拥堵问题最强有效的绿色交通方式，股道运用是区域铁路车站作业组织的核心；区域铁路车站股道运用计划协同编制是列车运行计划编制的重要组成部分，也是提高客运服务质量的关键。相邻车站股道运用计划经由列车区间运行而产生不同程度的相互影响，当列车大面积晚点、安全事故、自然灾害等非常态事件发生时，股道运用紧张可能会导致相邻车站列车进一步晚点或站外临时停车，严重影响列车正常运行秩序，协同编制强抗干扰能力的相邻若干车站股道运用计划尤为重要。在国外，CAREY 等[1-2]采用模拟人工调度的方法，研究了大型复杂车站股道与接发车进路编制问题；LUSBY等[3-4]提出了单个车站股道与站台分配方法；PETERING 等[5]构建了基于能力、时刻表与车站作业计划的混合整数线性规划模型；CORMAN 等[6]结合禁忌搜索算法和分支定界算法，通过设计邻域结构提出了单个车站径路调整方法。在国内，彭其渊等[7-8]提出了大型客运站到发线运用调整优化方法和基于到发线运用方案的列车到达追踪间隔时间压缩方法；马驷等[9]设计了高速铁路车站列车进路分配方案的优化与调整方法；赵鹏等[10]以提高设备利用均衡性以及车站作业的抗干扰性为目标研究车站到发线与咽喉区的综合优化；张英贵等[11-12]采用排序理论，构建了单个铁路客运站股道运用窗时排序模型与算法，设计了股道与站台分配规则。目前，车站股道运用领域的研究更多关注单个车站股道运用计划编制与调整优化方面，较少涉及多站股道运用计划协同编制层面。此外，列车运行调整和时刻表是协同编制区域铁路车站股道运用计划的重要因素。聂磊等[13]提出了不同列车运行调整策略的关键技术；季学胜等[14]考虑区间封锁事件持续时间的不确定特征，分析了列车运行调整计划的鲁棒性；牛宏侠等[15]研究了高铁列车运行图车站与区间冗余时间同步优化问题；张琴等[16]提出了一种高速铁路列车运行图和到发线分配的协同编制方法；ZHANG 等[17]提出了一种面向列车晚点的时刻表、站台和进路实时调整协同优化方法；高全等[18]提出了一种兼顾调整方案波动性、抗二次干扰能力和均衡性的区域铁路车站股道运用在线融合实时调整优化方法。该方法侧重面向计划执行过程受突发事件影响所引起的股道运用实时调整优化，但无论如何调整均会不同程度的干扰车站和列车运行正常秩序，且调整时并未考虑冗余时间要素。融入冗余时间、协同编制具有强抗干扰能力的股道运用计划能从源头上有效缓解实时调整的规模和程度，编制多站股道运用计划时，合理设置分配列车在站作业、区间运行冗余时间，提高区域铁路车站股道运用计划的抗干扰能力，缓解不同车站股道运用计划的站间影响，确保车站和列车运行正常秩序，便于车站作业组织和旅客乘降。基于此，以区域铁路相邻车站股道运用计划协同编制为对象，引入冗余时间的概念，以列车运行和车站到发时刻为纽带，兼顾股道运用冗余时间分配和最大化全局抗干扰能力，提出一种考虑冗余时间的区域铁路车站股道运用计划融合编制优化方法，协同编制具有强抗干扰能力的区域铁路车站股道运用计划。

1 问题描述与分析

区域铁路车站股道运用计划协同编制优化是指在给定列车时刻表、既定线网、站场布局等情况下，考虑多个相邻车站的股道运用计划协同编制优化问题，合理编制多站股道运用计划，尽可能提高计划抗干扰能力和股道运用的均衡性。一般情况下，列车在车站内办理接发车作业时，同一时间段内最多占用某一条具体的股道，且相继占用同一股道的2列列车需满足股道占用最小时间间隔要求。因此，列车占用股道时间冲突包括起止时间错位交叉(a)，包含(b)和时间间隔不足(c)3种情形，如图1所示。

如图1所示，不妨设前行列车开始、终止占用同一股道的时刻分别为t1和t2，后行列车占用同一股道的起始和终止时刻分别为t3和t4。图1(a)和1(b)表示同一股道不能被不同列车同时占用，即t3≤t2≤t4，t1≤t3≤t4≤t2；避免股道占用冲突时，前后,2列列车占用同一股道时还必须间隔一定的最小时间间隔即t3-t2≥τ间隔，否则如图1(c)所示。上述3种冲突情况均可归纳为t3-t2＜τ间隔。同时，冗余时间的引入能增加相继占用同一股道的列车间隔和区间运行时间，缓解在非常态事件发生时出现股道占用冲突现象，但冗余时间的大幅增加亦不利于车站和区间通过能力的充分挖掘与利用，兼顾计划协同编制和冗余时间分配。考虑列车最小停站、冗余和间隔时间，股道运用计划和冗余时间分配间的关系如图1所示。

图1 股道占用时间冲突Fig. 1 Time conflicting for track utilization

如图2 所示，对比图2(a)和2(b)所示计划，后者分配给列车1 的冗余时间大于前者，在列车1 和列车2 的相同间隔时间的情况下，后者的列车1 冗余时间较大，能吸收更多的延误时间从而降低影响列车2后续占用同一股道的概率，提高计划的干扰能力；对比图2(b)和2(c)所示计划，列车1 所分配的冗余时间相同的情况下，交换列车2 与列车3所占用的股道后，列车1与其后续占用同一股道的列车时间间隔更大，更有利于对延误的吸收，股道运用计划的稳定态势和抗干扰能力会更强。

图2 股道运用计划和冗余时间分配之间的关系Fig. 2 Relationship between track utilization plan and redundant time distribution

便于描述，不妨假设：每条股道同时最多被同一列车占用；列车占用同一股道时中途不能转至其他股道；研究对象限定在旅客列车范畴，不考虑调车作业和列车等级对股道运用计划编制的影响。

2 模型构建

不妨设列车集合为I={1，2，…，i，…，n}，区域铁路车站集合为S={1，2，…，s，…，m}，车站s的股道集合为Us={1，2，…，us，…，ks}，占用车站s的股道us的列车集合为车站s的进路集合Rs，列车i占用车站s的进路为列车i在车站s的最小停站作业时间为ai，s，列车i在区间(s-1，s)的最小运行时间为bi，(s-1)，列车i与其相邻后续同向列车i+1 在区间(s-1，s)的最小间隔时间为其取值由列车i与其相邻后续同向列车i+1 的车站通过间隔时间(若有)、车站出发间隔时间、区间追踪间隔时间、车站到达追踪间隔时间之中的最大值确定；分配给列车i在车站s的站内作业冗余时间为Ai，s，在区间(s-1，s)的运行冗余时间 为Bi，(s-1)，其 理 想 目 标 值 分 别 为TAi，s和TBi，(s-1)，车站s的股道us被同一列车占用的最小间隔时间为τu，s，列车i到达和离开s站的实际时刻为用表示列车i在 车站s是否占用 股 道us，占用时

2.1 区域铁路多站股道运用冗余时间分配优化模型

冗余时间的设置可有效提高区域铁路多站股道运用计划的抗干扰能力，降低股道运用实时调整规模及程度，尽可能避免突发事件干扰或影响引起的相邻若干车站股道运用的站间影响，其实质是通过吸收部分或全部列车在站停靠和区间运行过程中因非常态受到的初始或连带延误来实现的。通过设置冗余时间理想目标值TAi，s，TBi，(s-1)以充分吸收随机干扰，在满足约束的条件下引导冗余时间分配值向理想目标值逼近，针对性设置列车在各区间和各车站的冗余时间。构建区域铁路多站股道运用冗余时间分配优化模型RTM：

其中，式(1)表示所有列车站内和区间运行冗余时间分配整体尽可能逼近理想目标值，β1和β2分别是列车站内作业和运行冗余时间权重系数，且β1+β2=1；式(2)表示冗余时间分配后所有列车的在站停留时间不低于最小停站作业时间要求；式(3)表示冗余时间分配后所有列车在区间运行时间不小于最小区间运行时间要求；式(4)和式(5)分别表示相邻的2列同向列车进出站时间间隔不少于相应的最小间隔时间要求；式(6)表示为每列列车分配的总冗余时间不超过列车最小运行时间的λ倍，λ的取值一般为0.07；式(7)和式(8)表示为每一列车站内作业冗余时间、区间运行冗余时间的非负性约束。

2.2 区域铁路车站股道运用计划融合编制优化模型

均衡股道占用时间间隔可有效避免部分股道短时间内密集接发多列列车，可最大程度地提高股道运用计划的抗干扰能力；均衡股道被列车占用次数可有效提高车站能力和资源使用效率，便于旅客乘降。以多站范围内所有占用同一股道列车之间的时间间隔标准差即抗干扰能力最强、股道占用次数均衡性最佳为目标来衡量区域铁路多站股道运用计划协同编制的效果，多站股道运用计划的抗干扰能力Z1与股道占用次数均衡性Z2分别按式(9)和式(10)确定：

采用Min-Max标准化方法对式(9)和式(10)所表示的多站股道运用计划的抗干扰能力与股道占用次数均衡性进行无量纲化处理，标准化后的无量纲函数分别记为

以最大化多站股道运用计划的抗干扰能力与均衡性为优化目标，统筹考虑列车最小停站时间、接发车最小安全间隔时间、敌对进路检查等约束，构建区域铁路车站股道运用计划融合编制优化模型TUIM：

其中，式(11)表示最大化股道运用计划抗干扰能力的同时尽可能地整体上均衡使用车站股道，α1和α2分别是抗干扰能力和股道占用均衡性权重系数，其中令α1+α2=1，α1≫α2；式(12)～(14)分别表示列车在站最小停站时间、接发车最小间隔时间约束；式(15)表示在任意车站内每列列车均有股道供其办理接发车作业，也是计划的可行性约束；式(16)表示在每列列车到达车站后仅占用一条股道；式(17)表示相继占用同一股道的2列列车需满足股道占用最小间隔时间要求；式(18)表示敌对进路检查。

2.3 考虑冗余时间的区域铁路车站股道运用计划协同编制双层规划模型

综上，以区域铁路列车运行和车站到发时刻为纽带，兼顾多站股道运用协同编制和冗余时间分配，以区域铁路车站股道运用计划融合编制优化模型TUIM 为上层模型，多站股道运用冗余时间分配优化模型RTM 为下层模型，构建考虑冗余时间的区域铁路车站股道运用计划协同编制双层规划模型TUCBM：

上层模型UTM：minf2=α1Z'1+α2Z'2

s.t.式(12)～式(18)

下层模型DTM：

3 算法设计

单个车站的股道运用计划编制优化问题是一个极其复杂的组合优化问题[12]，亦是一个NP-Hard问题[1]；区域铁路多站股道运用计划协同编制涉及多个相邻的铁路车站，制约条件繁杂，问题规模大，结合问题与算法的规约关系易知该问题也是一个NP-Hard问题，难以在较短时间内制订出最优方案；基于问题自身特征及优化多目标的客观需求，所构建的双层规划模型涉及参数及约束众多，往往会突破规划模型求解器的适用范围，为提高算法的普适性和求解的高效性，考虑提出一种启发式求解算法，即考虑冗余时间对股道运用计划协同编制的影响，优化制订多站股道运用冗余时间分配优化方案，在此基础上，以列车运行和车站到发时刻为纽带，基于模拟退火算法思想设计区域铁路多站股道运用计划协同编制启发式求解算法。

区域铁路多站股道运用冗余时间分配优化算法。

Step 1：初始化。输入列车集合I，车站集合S，列车在各站的最小停站作业时间ai，s，区间最小运行时间bi，(s-1)，列车在站作业和区间运行冗余时间分配理想目标值TAi，s和TBi，(s-1)，相邻同向列车在区间的最小间隔时间转Step 2；

Step 2：根据列车在各站的最小停站作业时间ai，s，区间最小运行时间bi，(s-1)和列车在始发站的发车时刻，计算各列车到达和离开各车站的最早可能时刻Ai，s=0，Bi，(s-1)=0，转Step 3；

Step 3：构建非常态事件随机干扰概率函数P(t)，生成各列车在各个区间与车站的随机干扰延误时间ΔAi，s与ΔBi，(s-1)，令s=2，转Step 4；

Step 4：结合n列列车在车站s-1 的出站时间，对所有n列列车重新生成列车序列，令i=1，转Step 5；

Step 5：判断列车i在区间(s-1)的干扰延误时间ΔBi，(s-1)是 否 大 于 区 间 冗 余 时 间Bi，(s-1)，若 是，则 列车i到 达 车 站s的 时 间转Step 8；否则，转Step 6；

Step 6：判断列车i在车站s-1 是否出发延误，若是，转Step 7，否则，列车i到达车站s的时间转Step 8；

Step 7：判断是否大于列车i到达车站s的最早可能时刻若是，列车i到达车站s的时间转Step 8，否则，列车i到达车站s的时间转Step 8；

Step 8：令TB判 断TBi，(s-1)是 否 大 于λbi，(s-1)，若 是，令转Step 9；否则，转Step 9；

Step 9：判断i是否等于列车总数n，若是，根据所有n列列车在车站s的到站时间，对所有n列列车重新生成列车序列，转Step 10；否则，令i=i+1，转Step 5；

Step 10：判断前后到达车站s的所以n列列车是否满足最小间隔时间，若是，令i=1，转Step 11；否则，按新列车序列依次延后不满足最小间隔时间的后续列车的到站时间，令i=1，转Step 11；

Step 11：判断列车i在车站s的干扰时间ΔAi，s是否大于车站冗余时间Ai，s，若是，则列车i离开车站s的 时 间转Step 14；否 则，转Step 12；

Step 12：判断列车i在车站s是否到达晚点，若是，转Step 13，否则，列车i离开车站s的时间转Step 14；

Step 13：判断是否大于列车i离开车站s的最早可能时刻若是，列车i离开车站s的时 间转Step 14，否 则，列 车i离开车站s的时间转Step 14；

Step 14：令判 断TAi，s是 否 大于λai，s，若 是，令转Step 15；否则，转Step 15；

Step 15：判断i是否等于列车总数n，若是，根据所有n列列车在车站s的出站时间，对所有n列列车重新生成列车序列，转Step 16；否则，令i=i+1，转Step 11；

Step 16：判断前后离开车站s的所以n列列车是否满足最小列车间隔时间，若不满足，则按新列车序列依次延后不满足最小列车间隔时间的后续列车的出站时间；更新车站s的列车到发时刻，转Step 17；

Step 17：判断s是否等于车站总数m，若是，输出列车在各站的初始实际到发时刻、冗余时间分配结果Ai，sBi，(s-1)和f1，算法结束；否则，令s=s+1，转Step 4。

一般地，列车在区间、车站内受到的随机干扰服从晚点均值的负指数分布[15]，冗余时间分配优化算法Step 3 中的列车干扰延误时间为t的非常态事件随机干扰概率函数按式(19)确定取值：

其中，为某列列车在某区间或某车站受非常态时间影响的平均干扰延误时间的倒数。不妨设多站股道运用初始解矩阵的三维矩阵An×s×2，第1维度n表示列车，第2 维度s表示车站，第3 维度表示列车占用的股道编号；邻域解矩阵A'n×s×2由当前解矩阵变换得到：由随机生成器来选中当前解矩阵An×s×2特定车站的单列或多列列车，在满足进路占用约束的情况下，变更选中列车所占用的股道信息进而获得新解。采取Metropolis 接受准则来确定是否接受新生成的邻域解作为当前解，邻域解向当前解转换的概率：

其中，t为温度。区域铁路多站股道运用计划融合编制优化算法如下。

Step 1：输入由区域铁路多站股道运用冗余时间分配优化算法的计算结果，设置初始温度T0，迭代次数L1，L2，冷却速率c，温度阈值e；令T=T0，r1=1，r2=1，转Step 2；

Step 2：基于文献[12]的股道分配规则，生成股道运用初始计划，构造多站股道运用初始解矩阵An×s×2，根据式(11)计算初始目标函数f2(An×s×2)，转Step 3；

Step 3：判断r2是否等于L2，若是，则不重新改变列车实际到发时刻、当前L2下无法求得可行的多站股道运用计划，需局部调整产生冲突的列车在站实际到发时刻，并令r2=1，转Step 5；否则，转Step 4；

Step 4：采用文献[11]的解改进优化策略，变换当前解矩阵的若干股道占用信息，同时对列车敌对进路进行检查，产生新的解矩阵A'n×s×2，转Step 5；

Step 5：结合模型约束条件判断新解A'n×s×2是否可行，若可行，计算新解目标函数f2(A'n×s×2)，转Step 6；否则，r2=r2+1，返回Step 3；

Step 6：判断f2(An×s×2)-f2(A'n×s×2)是否大于0，若是，则接受新解，转Step 7；否则按Metropolis 准则以一定概率(按式(20)确定取值)接受新解，转Step 7；

Step 7：判断r1是否等于设定迭代次数L1，若是，转Step 8；否则，令r1=r1+1，转Step 4；

Step 8：令T=c*T，判断T-e是否小于0，若是，输出最终解及目标函数值；否则，转Step 4。

4 算例分析

以某区域铁路线路和某日列车运行数据为背景验证所提模型与算法的有效性。某区域铁路包括4 个车站、3 个区间，车站及区间关系示意图参见文献[18]，运行列车82 列；以车站1 发车时间为初始时间，考虑车站2，3，4 和区间(1-2)，(2-3)，(3-4)的冗余时间配置，协同编制该区域铁路车站股道运用计划(参数取值为β1=β2=0.5，α1=0.999 9，采用Matlab 编程，基于所构建的考虑冗余时间的区域铁路车站股道运用计划协同编制优化方法进行求解。该区域铁路部分列车在站作业及区间运行区间冗余时间配置优化、股道运用计划协同编制结果如表1所示。

表1 冗余时间配置和多站股道运用计划(部分)Table 1 Redundant time configuration and multi-station utilization plans (Part)

如表1所示，列车区间运行时间调整空间相对灵活，站内作业时间的设置刚性较强，主要是由于列车在站停靠时间普遍较短造成的，编制单个车站股道运用计划的同时需兼顾相邻车站股道运用和列车运行的影响。全部列车在不同区间、车站的冗余时间分配情况分别如图3～4所示。

如图3～4 所示，列车在区间1，2，3 运行时间的平均冗余时间分别为68.63，141.19和64.73 s，冗余时间的设置跟区间长度呈反比关系，可以有效增强多站股道运用计划抗干扰能力；车站1，2，3的平均冗余时间分别为1.14，3.38和1.42 s，站内冗余时间的设置对股道运用计划抗干扰能力的提升没有显著作用。协同编制区域铁路多站股道运用计划时，必须充分考虑列车在区间运行及冗余时间配置。

图3 区间运行冗余时间分配结果Fig. 3 Distribution results for train running redundant time in railway sections

为进一步验证多站股道运用计划的抗干扰能力和所提多站股道运用冗余时间分配优化方法的优劣，对比冗余时间传统平均分配和比例分配方法，以列车晚点为例进行分析。便于对比，特选取列车总到发晚点时间、总出发晚点时间、到站晚点列车数、股道运用计划波动系数为评价指标(相同工况及参数取值)，基于不同冗余时间分配方法的多站股道运用计划评价指标对比分析如表2所示。

图4 在站作业冗余时间分配结果Fig. 4 Distribution results for operations redundant time in railway stations

如表2所示，对比传统的平均分配和比例分配方法，基于本文所提出的冗余时间分配方法，制订的多站股道运用计划的列车总到发晚点时间、总出发晚点时间、到站晚点列车数、股道运用计划波动系数均有不同程度的降低，各站股道运用计划的鲁棒性和抗干扰能力效果更佳，如基于本文方法的车站3 总到达晚点时间比基于平均分配、比例分配方法的总到达晚点时间分别降低了69.28%和71.40%，基于本文方法的车站3 的到站晚点列车数比基于平均分配、比例分配方法的到站晚点列车数分别降低了60.94%和63.13%；基于本文方法的车站4的股道运用计划波动系数比基于平均分配、比例分配方法的股道运用计划波动系数分别降低了50%和20%；所构建的区域铁路多站股道运用冗余时间分配优化模及其求解算法在提高各个区域铁路车站股道运用计划抗干扰能力方面的效果显著。对比车站2，3和4，虽然后续车站股道运用计划波动趋势逐步变大，但是列车总到发晚点时间、总出发晚点时间、到站晚点列车数下降明显，表明不同车站股道运用计划存在不同程度的相互影响，列车晚点等突发事件影响会向后传播，并随着列车往后运行这种影响会逐步被消化和吸收，这是由于列车在站和区间运行过程中均设置了冗余时间，冗余时间的引入能有效降低突发晚点对后续车站股道运用计划的影响，切实提高了计划的抗干扰能力；适当变更车站股道运用计划有利于降低线路级相邻车站股道运用的站间影响，缓解非常态突发事件对全局股道运用计划的影响。

表2 基于不同冗余时间分配方法的股道运用计划评价指标对比分析Table 2 Indexes analysis for track utilization plan with different redundant time allocation methods

综上，所提方法能统筹考虑区域铁路多站股道运用计划协同编制要素，合理制订线路级区域铁路多站股道运用计划，并通过Matlab 程序对不同工况和站线组合进行了多次模拟仿真验算，均能在10 min 内制订出抗干扰能力强和均衡性好的多站股道运用计划，能够为区域铁路车站股道运用计划协同编制提供强有力支撑。

5 结论

1) 以区域铁路列车运行和车站到发时刻为纽带，构建了考虑冗余时间的区域铁路车站股道运用计划协同编制双层规划模型，设计了区域铁路多站股道运用冗余时间分配优化方法，提出一种兼顾抗干扰能力和均衡性的线路级区域铁路车站股道运用计划协同编制优化方法。

2) 所提方法能合理编制出具有强抗干扰能力的区域铁路相邻若干车站的股道运用计划，能有效缓解相邻车站股道运用计划的站间影响，并逐步降低非常态突发事件对后续车站股道运用计划的影响程度。

3) 融入不同种类列车和共网运行特征等因素，兼顾冗余时间配置和列车节能运行目标，提出路网级区域铁路车站股道运用计划协同编制优化方法是笔者亟待开展的下一步研究工作。