区域铁路车站股道运用在线融合实时调整优化方法

高全，张英贵，陈治亚，陈曾儒

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

区域轨道交通包括高速、普速、城际、市郊、地铁和轻轨等多种轨道交通方式，地铁和轻轨等城市轨道交通系统与其他轨道交通方式的运营管理机制不同，将高速、普速、城际和市郊铁路统称为区域铁路。车站是铁路服务的窗口，股道运用是区域铁路车站作业组织的核心，不同车站股道运用经由列车运行导致相互影响、相互制约，高效制订多站股道运用在线融合调整方案是区域铁路列车运行实时调整的重要内容，是提升客运服务质量的关键。区域铁路车站股道运用在线融合调整涉及列车时刻表、股道运用2个层面。在列车时刻表层面，BARRENA 等[1]研究了面向动态需求环境下的列车时刻表设计和优化问题；HASSANNAYEBI等[2-3]采用拉格朗日松弛算法和交替方向乘子法对时刻表问题进行了分解；廖正文等[4]提出了基于累计变量的列车时刻表整数规划模型并设计了拉格朗日松弛算法求解；高如虎等[5]提出了一种新增列车条件下灵活的列车时刻表优化算法。在股道运用层面，CAREY 等[6-7]采用模拟人工调度的方法，研究了大型复杂车站股道与接发车进路编制问题；吕红霞等[8-11]通过构建混合整数规划模型研究了客运站到发线运用计划、旅客列车过站径路、车站列车进路分配方案和股道分配优化方法；ZENG 等[12]提出了基于规则的启发式算法。一些学者对二者协同编制及调整进行了研究。张琴等[13]基于时空网络提出了协同编制多线路列车运行图和多车站到发线分配方案的方法；张英贵等[14-15]初步探讨了车站股道运用协同调整优化方法。纵观研究现状，既有研究大多考虑单站股道运用编制与调整问题，较少考虑多站股道运用实时调整层面，尤其是考虑时刻表调整的区域铁路多站股道运用在线融合调整研究亟待加强。基于此，统筹考虑区域铁路多个车站股道运用实时协同调整优化问题，兼顾列车时刻表调整及其抗二次干扰能力、计划的波动性和股道运用的均衡性，提出区域铁路车站股道运用在线融合实时调整优化方法，以期高效制订多站股道运用在线融合调整方案。

1 模型构建

区域铁路车站股道运用在线融合调整优化是指在给定列车时刻表、股道运用计划和既定线网、站场布局等情况下，考虑多个相邻车站的股道运用计划实时调整优化问题，高效编制多站股道运用在线融合调整方案，追求列车时刻表和股道运用计划波动性最小，尽可能提高调整后列车时刻表的抗二次干扰能力和股道运用在线融合方案的均衡性。为便于描述，不妨假设：每条股道同一时段内最多被同一列车占用；列车占用同一股道时中途不能转至其他股道；研究对象限定在旅客列车范畴，不考虑调车作业和列车等级对股道运用的影响。

1.1 上层模型：列车时刻表动态调整模型

调整后列车时刻表的波动性越小，正点率越高，旅客满意程度越高，其波动性由列车总早晚点率和车站到发时刻总偏离程度共同确定，列车在区域铁路多个车站的总到达和出发早晚点率、车站到发时刻总偏离程度分别按式(1)和(2)确定取值(ti′s，a=tis，a，=1；ti′s，a≠tis，a，=0；t′is，d=tis，d，=1；t′is，d≠tis，d，=0)；

在特定时间段内固定数量列车运行时，所有相邻列车在车站到发时刻相对均衡不会引起个别相邻列车在极短时间内密集到发车站；调整后的列车在极短时间内密集到发时，更易受突发事件影响，调整后的时刻表抗二次干扰能力相对较弱。兼顾调整前后列车时刻表的稳定性和波动性，以调整列车为基准，采用被调整列车与其相邻前后两列列车到发时间间隔均衡来衡量调整后列车时刻表的抗二次干扰能力，抗二次干扰能力评估函数如式(3)所示：

采用Min-Max 标准化方法对式(1)～(3)所表示的列车时刻表总晚点率、总偏离程度和抗二次干扰能力进行无量纲化处理，标准化后的无量纲函数分别记为，和。

以最小化调整后列车时刻表的波动性、最大化其抗二次干扰能力(负的最小)为优化目标，统筹考虑列车最小停站时间、接发车最小安全间隔时间等约束，构建区域铁路车站股道运用在线融合调整双层规划模型的上层模型即列车时刻表动态调整模型UTM：

其中，式(4)表示采用线性加权的方式对UTM 的多目标函数进行求和，γ1，γ2和γ3分别表示列车总早晚点率、车站到发时刻总偏离程度、列车时刻表抗二次干扰能力的权重；式(5)、式(6)和式(7)分别表示任一列车在任一车站的经停时间必须满足其最小停站时间要求、相同方向相邻列车进入同一车站的时间间隔必须满足其同向接车最小安全间隔时间要求、相邻列车离开车站进入同一区间的时间间隔必须满足其同向发车最小安全间隔时间要求；式(8)表示列车实际出发时刻不早于图定出发时刻；式(9)表示列车在下一车站的实际到达时刻即为列车在本站的实际出发时刻和列车在两站之间的区间运行时间之和。

1.2 下层模型：多站股道运用在线实时调整优化模型

一般情况下，车站股道按方案固定使用，股道占用变更可能会导致其占用的站台发生变化，不利于旅客乘降；调整时应尽量避免股道占用变更，便于旅客乘降，提高旅客满意程度。区域铁路车站股道运用在线融合调整过程中可能会变更部分列车占用的股道和接发车进路，整体波动性采用调整前后列车占用股道和进路情况来衡量，具体按式(10)确定：

以全部车站的所有列车占用同一股道的时间间隔标准差之和衡量多站股道运用在线实时调整优化的整体均衡性，多站股道运用在线实时调整方案的均衡性评估函数如(11)所示：

采用Min-Max 标准化方法对式(10)和(11)所表示的多站股道运用在线实时调整方案的波动性和均衡性进行无量纲化处理，标准化后的无量纲函数分别记为，。

以多站股道运用的整体波动性最小和均衡性最大(负的最小)为优化目标，统筹考虑股道占用最小安全时间间隔、接发车作业进路编制等约束，构建区域铁路车站股道运用在线融合调整双层规划模型的下层模型即多站股道运用在线实时调整优化模型DTM：

其中，式(12)表示采用线性加权的方式对DTM 的多目标函数进行求和，ε1，ε2分别表示多站股道运用调整方案的整体波动性和均衡性的权重；式(13)表示列车相继占用同一车站同一股道的时间间隔必须满足其占用的最小安全时间间隔要求；式(14)和式(15)表示所有列车在任一车站实际占用股道的唯一性约束；式(16)和式(17)表示所有列车在任一车站实际占用接车进路的唯一性约束；式(18)和式(19)表示所有列车在任一车站实际占用发车进路的唯一性约束；式(20)～(23)是指敌对进路占用安全性约束即任一列车不能同时占用同一接车或发车进路，分别表示接车、发车、接发车、发接车占用进路的唯一性约束。

1.3 区域铁路车站股道运用在线融合调整双层规划模型

综上，以调整后的列车is在车站s的实际到发时刻t′is，a，t′is，d为融合因子，以列车时刻表动态调整模型UTM 为上层模型，以多站股道运用在线实时调整优化模型DTM 为下层模型，构建区域铁路交通车站股道运用在线融合调整双层规划模型DPTM：

2 算法设计

区域铁路车站股道运用在线融合调整方案的制订涉及多个相邻的铁路车站，制约条件繁杂、问题规模大，尤其是单个车站股道运用优化问题是一个极其复杂的组合优化问题，难以在较短时间内制订出最优调整方案。考虑区域铁路突发事件的影响，优先制订列车时刻表调整方案，以列车在站实际到发时刻为纽带，基于模拟退火思想协同编制多站股道运用在线实时调整方案，融合新时刻表的多站股道运用在线调整的正反馈作用、多站股道运用对时刻表调整的负反馈作用，设计区域铁路多站股道运用在线融合调整启发式求解算法。便于算法描述，不妨记某站的初始股道占用解矩阵为An×2(矩阵行数为在车站经停列车总数，首列为列车编号，第2列为当前列车在此车站停靠的股道编号)。

多站股道运用在线融合调整启发式算法步骤如下。

Step 1：初始化。输入区域铁路车站集合S，经由车站s的列车集合Is，车站s的接发车股道集合Us，接(发)进路及轨道电路集合，既定方案的列车时刻表TT的图定到(发)时刻tis，a(tis，d)，车站、区间列车运行参数，和列车晚点信息；按既定方案确定调整前列车在各站的股道、接车、发车占用信息xis，us，ois，ras，ois，rds；t′is，a=tis，a；t′is，d=tis，d，x′is，us=0，o′is，ras=0，o′is，rds=0；设定内循环迭代次数计数器l，内循环迭代次数L，求解计数器ξ，求解迭代次数N，初始温度t0，温度下降速率α，当前温度tr，外循环终止温度te，令s=1，转Step 2；

Step 2：结合列车图定和实际到发时刻，判定列车在车站s是否偏离既定时刻表，早晚点的列车集合为Ds(Ds⊂Is)，早晚点列车为dis(dis∈Ds)，早晚点列车总数为k，列车dis早晚点到达车站s的时间为t′dis，a，转Step 3；

Step 3：将所有晚点列车从原列车时刻表TT中扣除，将剩余列车按离开车站s的时间排序，生成过渡列车时刻表TT1，令dis=1，转Step 4；

Step 4：判断列车dis的发站时间t′dis，d是否与过渡列车时刻表TT1中的列车的发站时间的时间间隔满足，若不满足，则转Step 5，否则，令t′dis，d=t′dis，a+，转Step 7；

Step 5：将列车dis与其相邻的后续列车is交换出站秩序，判断此时在过渡列车时刻表TT1 中与列车dis前 后 相 邻 的2 列 列 车 是 否 满 足t′is+1，d-tis，d＞，若是，确定当前列车秩序为列车dis的出站秩序，转Step 6，否则，转Step 7；

Step 6：将列车dis依次与后续列车is+1,is+2,…交换进站秩序，直至寻求出满足出站时间间隔的列车秩序，若交换后所有结果均不满足出站时间间隔要求，则在过渡列车时刻表TT1中的列车中从与列车dis最临近的列车开始将其出站时间往后推移，直至寻求出满足出站时间间隔的列车秩序，转Step 7；

Step 7：计算使||t-tis+1，d| -|t-tis-1，d||达到最小的t值，令t′dis，d=t，转Step 8；

Step 8：将列车dis纳入过渡列车时刻表TT1，转Step 9；

Step 9：令dis=dis+1，判断是否满足dis=k+1，若是，转Step 10，否则，转Step 4；

Step 10：加载过渡列车时刻表TT1，由既定方案生成初始股道占用解矩阵，令tr=t0，内循环迭代次数计数器l=0，求解计数器ξ=0，转Step 11；

Step 11：判断初始股道占用解矩阵是否满足如下条件：1) 股道占用最小时间间隔τus；2) 列车占用股道的唯一性约束；3) 列车占用接发车进路

Step 12：随机交换初始股道占用解矩阵中第的唯一性约束；4) 接发车进路冲突检查。若满足，则 令 当 前 解Ak×2=A0k×2，转Step 13；否 则，转Step 12；i，j行第2 列的股道编号，重新生成初始股道占用解矩阵，并令ξ=ξ+1，判断ξ是否等于求解迭代次数N，若是，以冲突量最少的占用解为标准，将产生股道占用时间冲突的列车中的较后秩序列车的到达时间后移，并将此部分列车编入列车集合Ds，转Step 2；否则，转Step 11；

Step 13：在所有股道编号集合Us范围内随机变换2 个当前股道占用解矩阵Ak×2的第k行的股道编号，产生当前股道占用解的邻域股道占用解矩阵A′k×2，转Step 14；

Step 14：判断邻域股道占用解矩阵A′k×2是否满足如下条件：1) 最小停站时间；2) 同向接发车最小安全间隔时间，；3) 列车实际出发时刻不早于图定出发时刻；4) 股道占用最小时间间隔τus；5) 列车占用股道的唯一性约束；6) 列车占用接发车进路的唯一性约束；7) 接发车进路冲突检查。若满足，确定决策变量t′is，a，t′is，d，x′is，us，o′is，ras，o′is，rds和接发车进路占用起止时间取值，转Step 15，否则，转Step 13；

Step 15：计算当前股道占用解的目标函数值Z(Ak×2)与邻域股道占用解的目标函数值Z(A′k×2)，若Z(A′k×2)＜Z(Ak×2)，则接受Z(A′k×2)作为新的当前股道占用解矩阵Ak×2，否则根据Metropolis 准则接受Z(A′k×2)，转Step 16；

Step 16：令l=l+1，判断是否达到内循环迭代次数L，若是，转Step 17，否则，转Step 13；

Step 17：降温，令tr=α×tr，判断tr是否小于te，若是，记录当前股道占用解矩阵Ak×2，转Step 18，否则，转Step 13；

Step 18：令s=s+1，判断是否满足s=j+1，若不满足，则令t′dis，a=t′dis-1，d+tiss，s+1，转Step 2；否则，输出各站股道、接发车占用及时刻表调整结果及目标函数值，算法结束。

3 算例分析

某区段包括4个高铁车站，站间关系及车站拓扑结构示意图如图1 所示；某日6:00～12:00 内共有上行列车25 列。受突发事件影响，编号为ID7，ID8 和ID9 的列车在车站1 发生初始延误，晚点时间分别为60，74 和69 min；不妨设车站同向接车和发车最小安全间隔时间均为3 min、占用同一股道的最小安全间隔时间为5 mim，考虑调度员对在线融合实时调整目标的决策偏好程度和客观需要，上层模型目标函数权值取值分别为0.45，0.45 和0.10，下层模型目标函数权值取值分别为0.90 和0.10。基于所提出的在线融合实时调整优化方法，采用Matlab 软件编程，制订多站股道运用在线融合调整方案，如表1所示。

如表1 所示，表中到发时刻均为实际到发时刻，实际到发时刻相等说明列车在该站经由正线通过，ID7，ID8，ID9 的晚点引起了ID19，ID20和ID21 列车晚点，引起方案改变；ID8 按既定计划经由1G 于9:00 通过车站1，但受初始延误的影响，按其最终调整方案该列车将于10:25 经由3G离开车站1，时刻表的波动和调整正反馈于车站的股道运用结果；便于直观说明股道运用对时刻表的负反馈效用，表2给出了部分列车的在线融合临时调整方案。

表1 多站股道运用在线融合调整方案(部分)Table 1 Multi-station track utilization online integrated adjustment plan (in part)

如表2 所示，带括号的到发时刻为临时参数，未带括号的为最终结果。以ID9和ID17占用车站2的3 G 为例进行说明：列车ID9 在车站2 的实际到发时刻为10:56，11:37，停靠股道3 G，列车ID9和ID17会先后占用3 G，不满足股道占用最小安全时间间隔要求，且车站2下行方向非正线的接发车股道只有3 G，无论如何调整难以获得可行股道运用方案。此时，可通过调整列车ID9 在车站2 的实际到站时刻即晚点至10:59 满足约束，说明站内无可行股道占用时可通过调整时刻表获得在线融合调整方案，调整时二者呈现强关联关系。

表2 多站股道运用在线融合临时调整方案(部分)Table 2 Multi-station track utilization online integrated temporary adjustment plan (in part)

综上，论文所提方法能统筹考虑区域铁路多站股道运用协同编制和时刻表调整要素，高效制订合理的区域铁路多站股道运用在线融合调整方案，并通过Matlab 程序对不同晚点情况进行多次仿真验算，均能在30 s内制订出波动性最小、抗二次干扰能力最强和均衡性最好的方案的同时，满足多站股道运用在线融合实时调整的强时效性要求；所提方法能够为区域铁路列车运行实时调整和多站股道运用应急协同编制提供决策支持。

4 结论

1) 以区域铁路列车运行和车站实际到发时刻为纽带，融合区域铁路多站股道运用协同编制和列车时刻表调整优化，提出了一种兼顾调整方案波动性、抗二次干扰能力和均衡性的区域铁路车站股道运用在线融合实时调整优化方法。

2) 所提方法能在极短时间内制订出合理的多站股道运用在线融合调整方案，能够满足区域铁路列车运行实时调整的强时效性要求。

3) 区域铁路列车存在区间反向行车或占用股道情形，统筹考虑区间反向行车、站内线路灵活使用和列车等级等因素，完善并验证方法的有效性和合理性是作者正在研究的问题。