基于滚动时域优化的高速铁路车站到发线动态调整研究

任禹谋 ，张 琦，袁志明，周晓昭

（1.中国铁道科学研究院 研究生部，北京 100081；2.中国铁道科学研究院集团有限公司 通信信号研究所，北京 100081)

0 引言

随着中国城市化建设的逐步完善和经济的蓬勃发展，人们出行的需求和频率不断增加，高速铁路的竞争优势越来越突出。高速铁路车站内列车作业过程种类多样，行车密集，列车的接续关系繁杂，到发线运用合理与否直接影响列车的通过效率。铁路系统与开放式的环境交互过程中，难免受到人、天气等因素的影响，当列车发生晚点事故时，车站调度员依靠经验往往难以及时有效地调整阶段计划下发的图定到发线运用方案。因此，为尽快恢复晚点列车及连带晚点列车的正点运行，应快速高效地制定到发线动态调整方案，保证高速铁路旅客列车服务质量。

国内外学者针对到发线运用问题已经进行了大量的研究，主要分为车站作业计划编制阶段到发线分配问题和列车运行阶段到发线动态调整问题。针对到发线分配问题，吕红霞等[1]提出“时间片”的概念，通过简化到发线运用计划的二次0-1 规划模型，明显降低了问题求解的困难度；史峰等[2]考虑一端咽喉区接发车进路和到发线的关联关系，以避免到发线和进路冲突为约束构建模型，采用模拟退火算法求解；贾文峥等[3]建立一种约束规划模型来描述股道分配问题，采用约束识别、值排序以及BT 搜索方法进行求解；李涛等[4]构建满足到发线均衡使用的整数规划模型，采用模拟退火遗传算法进行求解。针对到发线动态调整问题，彭其渊等[5]从离散化的到发线时空资源描述出发，构建了到发线运用方案调整问题的线性0-1 规划模型；马驷等[6]利用道岔分组的概念建立了涵盖到发线的列车进路分配方案动态调整模型，采用软件内置的分支定界算法求解；刘伟[7]引入“虚拟列车”概念建立到发线异常条件下咽喉区利用优化模型，并采用遗传算法求解；彭其渊等[8]在考虑分段解锁的条件下建立混合整数线性规划模型解决到发线运用调整问题，设计基于分支定界的算法框架求解。

综上所述，目前针对干扰条件下到发线动态调整的研究相对较少，大部分通过调整到发线来疏解冲突，而有可能导致冲突无法疏解，从而需要调整列车的到发时刻。因此，引入滚动时域调度策略对到发线分配计划进行动态调整，建立到发线动态调整的整数规划模型，求解滚动时域时间窗内到发线分配方案，降低原问题的求解规模，得到一系列能适应外界干扰的动态调整方案。

1 高速铁路车站到发线动态调整模型构建

1.1 问题描述

铁路运输环境多变，各种随机扰动事件时有发生，不可避免地会发生计划在执行过程中偏离图定的情况，到发线分配计划也不例外。在干扰发生时，影响运输的直接结果通常是列车发生晚点，通过在列车运行图设置缓冲时间可以缓解全线的列车到发延时，但当晚点集中在某些车站时该方法并不能完全满足要求，需要车站调度配合调整，减小干扰对车站作业的影响，以免加剧列车的晚点传播。调整车站作业计划中的到发线分配方案是车站调度工作的难点之一，即通过改变列车计划占用的到发线和接发车时刻规避列车间的冲突。调整后的方案应尽量降低偏离原计划的程度，减少列车晚点的总时长，同时应充分考虑到发线占用最小安全间隔时间和咽喉区交叉冲突的影响。

高速铁路车站到发线动态调整问题本质上是按时间顺序确定列车行经车站时占用的资源，可以视为动态调度问题进行决策分析。滚动时域调度(Rolling Horizon Scheduling，RHS) 策略广泛应用于工业动态调度领域，其特点是利用沿时间线滚动进行的一系列小规模或有限时段的局部调度代替大规模或无限时段的一次全局调度[9]。RHS 是一个随时间推进的迭代过程，在每一个调度时刻更新已有信息，确定一个滚动窗口，局部调度在滚动窗口进行，其解的一部分被执行，这部分解的完成时刻就是新的调度时刻，然后重复迭代进行，直至完成全部调度任务[10]。RHS 策略可以降低大规模调度问题的求解难度，提高随机环境下生产系统的调度敏捷性和稳定性，加快调度调整的响应时间。

传统到发线调整策略是将持续时间较长的到发线分配问题作为整体对象构建模型，其缺点是对系统不确定环境的敏感性和稳定性差。利用RHS 策略可以将调度调整周期分割为若干个叠加的时间段，再针对当前时间段内的列车建模求解到发线分配方案，并保留滚动窗口内的决策，然后时间向前滚动，重复相同的策略进行优化。值得注意的是，RHS 策略中每个时间段内的列车到站时间均可根据最新的预确报信息进行实时更新，从而保证了方案的优越性。

1.2 模型构建

设某高速铁路车站到发线集合为I= {1，2，…，i，…，m}，其中i为到发线的编号，m为到发线的总数；计划时间内到达的列车集合为L= {1，2，…，l，…，n}，其中l为列车到达车站的顺序，n为到达列车的总数；同一到发线相邻作业最小安全间隔时间为Tmin。综合考虑现场实际情况和调度员工作量，当列车晚点发生时，应尽量减少列车实际到发时间与计划的偏离程度，即列车总晚点时长，避免晚点效应在路网中的传播，确定第1 个目标函数为

式中：为列车l图定到达时间，min；为列车l实际到达时间，min；为列车l图定出发时间，min；为列车l实际出发时间，min。

为了方便客运组织，需保证列车优先选择图定方案中预计停靠的到发线或同台到发线，采用到发线占用费用的方式进行表示，确定第2 个目标函数为

式中：xli为0-1 变量，xli= 1 表示列车l占用到发线i，否则xli= 0。cli为列车l占用到发线i的费用，其值越小则该选择对计划方案影响越小。当与图定到发线一致时，cli= 0；当与图定到发线同台时，cli= 1；当与图定到发线不一致且不同台时，cli= 100。

利用线性加权的方式得到优化模型的最终目标函数为

式中：λ1和λ2为2 个子目标函数的权重，且λ1≫λ2。

公式(3)保证了在列车晚点情况下，优先考虑调整到发线运用方案，再调整其到发时刻，符合车站的基本调整逻辑。从到发线运用规则和列车作业时间角度考虑，模型受到如下约束。

（1）到发线占用相容性约束。同一时间一条到发线最多可以容纳一列列车，且列车占用到发线后不得换线。

（2）到发线作业的时间间隔约束。同一到发线上先后作业的2 列列车的时间间隔需要满足最小安全间隔时间要求，即后继列车的到达时刻与前行列车的出发时刻的差值不小于最小安全间隔时间。

（3）咽喉区交叉干扰安全约束。引用时间片[1]的定义，将某一阶段的时间划分几个时间片，不同列车在同一时间片内占用咽喉区表示列车在时间上存在干扰，即进路交叉冲突，需要安排平行作业进路。

式中：为0-1 变量，= 1 表示当列车l占用到发线i时的进路与其他列车进路r发生干扰冲突，否则= 0。

（4）到发线停车时间约束。列车在到发线上的实际停车时间需要满足图定停站时间要求，否则会影响旅客乘降等作业内容。

（5）列车到发时间约束。列车l的实际到发时间均不能早于图定到发时间。

（6）正线通过约束。车站正线只接发不停站通过列车，且通过列车不能通过到发线。

式中：I正为到发线正线集合；L通为通过列车集合。

2 高速铁路车站到发线动态调整模型求解

2.1 滚动时域调整策略

到发线动态调整问题不是离线优化，而是在线进行的，因而需要充分考虑模型的求解规模和列车的实时变化。RHS 策略通过引入时域的概念将复杂的调度模型转化为多阶段决策模型，在每一个阶段的采样时刻仅利用当前列车信息进行局部优化，并随着时间滚动反复进行，以此代替原问题的全局优化，从而减少优化问题的时间，提高优化性能的敏感度。

滚动窗口技术是RHS 的核心内容，在运用RHS 进行动态调度时，应首先划分滚动窗口和预测窗口[11]。滚动窗口是局部优化区间的一段，也称为调整区域；预测窗口是整个局部优化区间，窗口内包含已知信息和短时预测信息。假设当前正在调整第k个滚动窗口的到发线分配计划，滚动窗口的起止时间为[tk，tk+ΔT]，基于当前已知的列车运行信息，预测未来b个窗口，则其预测窗口为[tk，tk+bΔT]。需要注意的是，在干扰发生后，列车会偏离图定线运行，随着时间向前滚动，列车预计到发时刻也在不停变化，实时搜集更新预测窗口内的列车信息非常重要。到发线动态调整过程示意图如图1 所示。

根据上述分析可以制定完整的到发线动态调整策略。优先对实时搜集到的到达时刻在预测窗口内的列车建立调整模型并求解，获得到发线调整的初步方案。再将调整后到发时刻落在滚动窗口内的列车按上述方案确定对应到发线，放弃时间[tk+1，tk+(b- 1) ΔT]内的优化结果。当时间推进至滚动窗口的结束时刻时，滚动窗口向前推移，新的预测窗口周期开始，根据该预测窗口时间重新确定待优化列车集合及相关时间信息，重复上述调整操作，直至全部列车按到发时刻先后分配至到发线。具体调整步骤如下。

步骤1：初始化当前时刻，确定滚动窗口、预测窗口的时间长度、当前列车占用情况以及其他参数。

步骤2：根据已知列车计划到达信息确定预测窗口时间[tk，tk+bΔT]内列车到发时刻信息。

步骤3：对步骤2 中列车建立到发线动态调整模型并设计算法求解调整结果。

步骤4：执行滚动窗口时间[tk，tk+ΔT]内到发线分配调整方案，放弃时间[tk+1，tk+(b- 1) ΔT]内的调整决策。

步骤5：判断当前预测窗口结束时间是否为全部调度任务完成时间，若判定结果为yes，则停止调度调整，否则，向前滚动一个时域，即k=k+1，tk+1=tk+bΔT，并返回步骤2。

2.2 遗传算法设计

滚动时域调整策略中步骤3 需要设计相应算法求解到发线调整结果，由于到发线调整问题是大规模组合优化问题，适合采用启发式算法求解，设计相应遗传算法流程如图2 所示。

（1）染色体编码及初始种群生成。染色体编码根据到发线编号为自然数的特点选择采用自然数编码的形式，染色体的长度定义为预测窗口时域内到站列车的数量，染色体的基因位置编号按照列车到站顺序进行排列，基因位置所对应信息则表示占用的到发线编号，每个染色体代表了一种到发线运用方案。初始种群的生成按照列车到站顺序的先后分配到发线，分配规则遵照列车的图定方案。

图1 到发线动态调整过程示意图Fig.1 Dynamic adjustment process of arrival and departure track

图2 遗传算法流程Fig.2 Process of the genetic algorithm

（2）计算适应度函数。适应度函数用于评价个体的适应度值，由于目标函数是求取极小值，结合实际问题考虑，选取目标函数的倒数作为适应度函数。

（3）遗传操作。选择操作采用精英保留策略，并以轮盘赌的方法选择父代个体；交叉操作选择单点交叉方法；变异操作采用单点变异方法。

（4）可行解修复。遗传操作过程中可能会产生违背到发线调整约束的个体，通过约束公式(4)至公式(11)进行可行性验证。对于违背约束的个体，需要随机生成新的可行解进行替换，保证种群数量。

3 算例分析

以某高速铁路车站2 h 的行车数据为例验证到发线动态调整模型和算法，研究时段的开始时间置为0 时刻，高速铁路车站站场布置示意图如图3所示。车站共有6 条到发线，2 条正线，股道IG，3G，5G，7G 接发下行列车，股道IIG，4G，6G，8G 接发上行列车。到发线运用计划图定方案如图4 所示。在该时段内共办理30 列列车到发作业，根据《车站行车工作细则》规定，该站到发线占用最小安全间隔时间Tmin为5 min。遗传算法参数设置如下：种群规模为50，交叉概率为0.9，变异概率为0.05，最大迭代次数为50。考虑到一般铁路车站阶段计划为3 ～ 4 h，动态调整范围不易超过阶段计划的时间范围，且高速铁路车站车流密集，可减小滚动窗口的时间长度来提高方案的实时性，因而滚动时域调度方法参数设置如下：预测窗口向前看时间间隔b为1，滚动窗口ΔT大小为30 min，预测窗口大小为60 min，算例中共包含3 个滚动窗口。

图3 高速铁路车站站场布置示意图Fig.3 Layout of high-speed railway station

在0 ～ 30 min 内选取2 列列车设置干扰：5 号列车晚点3 min 到达，4 号列车晚点9 min 到达。根据以上参数和条件构建模型，运用仿真软件进行求解，每个预测窗口模型时间内算法均保持收敛，程序共运行20 次，从多次求解后得到的解中选择目标函数值最小的对应方案作为最终调整方案。到发线滚动时域调整方案如图5 所示。

图4 到发线运用计划图定方案Fig.4 Arrival and departure track utilization scheme

图5 到发线滚动时域调整方案Fig.5 Arrival and departure track adjustment scheme based on rolling horizon

调整前后列车信息比较如表1 所示，其余未提及的列车到发线分配方案保持不变。通过调整前后2 个方案的对比分析可知：在0 ～ 30 min 滚动时间窗内，5 号列车到达延误，导致其发车进路与3 号列车的发车进路在排路时间上发生冲突，为疏解该冲突，3 号列车的到发时间均推迟1 min，由于上述调整列车的到达时刻都落入当前滚动窗口，则按照调整结果执行；4 号列车到达延误，导致其占用到发线发生了变化，由计划到发线4G 变更至同台到发线6G，同时为了满足相同到发线相邻列车作业时间间隔不少于5 min 的要求，8 号列车到发时刻被迫向后推迟2 min，12 号列车占用到发线由计划到发线6G 变更至同台到发线4G，4 号和8 号列车的到达时刻都落入当前滚动窗口，所以按照调整结果执行，12 号列车的到达时刻未落入当前滚动窗口，暂时放弃其调整方案。然后，时间滚入下一个滚动窗口，重新计算调整方案。

表1 调整前后列车信息比较Tab.1 Comparison of the train information before and after adjustment

根据计算结果分析，引入滚动时域优化策略的调整方案后，在第1 个预测窗口模型中列车数量由30 列减少为16 列，计算时间降幅达21.1%，在第2 个预测窗口结束后列车调整全部完成，保证了方案的实时性。同时调整后的列车晚点总时长为6 min，到发时间受干扰的正点列车为2 列，变更同台到发线的列车为2 列，在可接受的调整范围内保持了车站运输的稳定性，说明模型和调整策略合理、有效，能够解决高速铁路车站到发线动态调整的实际问题。

4 结束语

建立基于滚动时域优化的高速铁路车站到发线动态调整模型，实现到发线调整智能化，提升了高速铁路列车的安全、稳定运行，在加快列车晚点恢复的同时，减少原计划的改变，保证了一定的实时性。考虑到高速铁路网络组成复杂，单个车站的到发线调整对于列车大量晚点的吸收能力有限，还应将列车运行图和区间内多个车站作为整体对象进行研究，最大化降低列车晚点在路网中的传播影响。