一种基于反馈调节的高速铁路列车运行调整方法

摘要

本发明公开了一种基于反馈调节的高速铁路列车运行调整方法，解决了现有技术中没有通过冲突严重性排序再依次进行冲突消解的缺陷，本发明首先获得当前时刻列车的运行状态、经过车站和区间状态；再次检测是否有冲突发生或在在将来时刻是否有潜在冲突，若否，则在将来时刻到来的时候更新数据信息，并重复该步骤，反之，则进入下一步；最后根据列车运行调整规则以最小冲突消解代价进行列车运行冲突消解，并按消解结果调整列车运行方案直至列车运行结束，反之，返回上一步。通过上述方法，本发明根据列车运行调整规则进行冲突消解，先排序再依次消解，可实现反馈调节，具有高实时性和高整体性的优点。

说明书

技术领域

本发明涉及一种高速铁路列车运行调整方法，具体来讲，是指一种以实施一 定列车运行调整方案后高速列车运行的动态性能、高速铁路运行冲突对高速列车 运行影响程度为反馈信息进行列车运行调整方案优化的列车运行调整方法。

背景技术

列车运行调整问题是一个典型的资源调度问题，国内外专家和学者致力于该 问题的研究已有近50年的历史。专家和学者先后建立了运行调整问题的数学规 划模型和基于离散事件的动态方法求解列车调整模型并利用遗传算法、协调优化 算法、分枝定界等方法对模型进行求解，构建了列车运行调整计划的专家系统， 提高运营调度系统的智能性。史峰等提出最早冲突优先方法消解列车运行图中的 冲突以实现列车运行调整，这种方法虽然能够避免冲突组合的问题，但却没有将 不同类别及严重程度的冲突区别对待，可能导致严重的冲突由于缺乏消解条件而 得不到很好的消解。

发明内容

本发明提供一种基于反馈调节的高速铁路列车运行调整方法，目的在于将冲 突的严重性从高到低进行排序，并按照该顺序消除冲突的引发原因，以免一个地 方消解了的冲突通过一定的转移和转化而以另外的形式在另一个地方又产生冲 突。

为了实现上述目的，本发明采用的技术方案如下：

一种基于反馈调节的高速铁路列车运行调整方法，包括以下步骤：

（1）获得当前时刻列车的运行状态、经过车站和区间状态；

（2）检测是否有冲突发生或在在将来时刻是否有潜在冲突，若否，则在将 来时刻到来的时候更新数据信息，并重复该步骤，反之，则进入下一步；

（3）根据列车运行调整规则进行列车运行冲突消解，并按消解结果调整列 车运行方案直至列车运行结束，反之，返回上一步。

为进一步说明冲突消解的依据，所述步骤（3）中冲突消解的方法如下：

（3a）进行列车运行冲突度量；

（3b）确定列车运行冲突消解次序；

（3c）根据单个冲突的消解策略，计算其中一个冲突消解代价；

（3d）制定该冲突的消解方案；

（3e）判断是否所有冲突的消解方案已确定，若已确定完所有冲突的消解方 案，该冲突消解过程结束，若未确定完所有冲突的消解方案，则重复步骤（3c）～ （3e）。

进一步的，所述确定列车运行冲突消解次序是根据冲突的严重度从高到低排 序。

作为多种优选，单个冲突的消解策略为平移运行线、交换运行线、变更停站 和越行中的至少一种。

在更新列车运行方案时，同时需要满足所述步骤（3）中调整列车运行调整 方案受到以下11个方面的约束：

（I）列车区间运行时间约束；

（II）列车停站时间约束；

（III）列车出发追踪间隔时间约束；

（IV）列车到达追踪间隔时间约束；

（V）需办理旅客业务车站发车时间约束；

（VI）车站到发线数约束；

（VII）动车组接续时间约束；

（VIII）旅客换乘时间约束；

（IX）跨线列车跨线时间约束；

（X）天窗时间约束；

（XI）逻辑约束。

与现有技术相比，本发明具有以下有益效果：

本发明在检测冲突并且预测将来可能发生冲突后，首先进行冲突严重性的排 序，使较为严重可能使生命财产损失较大的冲突首先做出冲突消解的动作，并反 馈至现阶段，以最小冲突消解代价提前消解冲突以便将来高速铁路列车运行出现 更大程度的列车运行秩序紊乱，提高列车运行质量。

同时本发明通过冲突判定、度量、预测、消解技术的综合运用来解决列车运 行调整问题，通过合理设计冲突消解策略降低列车运行调整问题的计算复杂度， 提高列车运行调整优化效率，具有高实时性和高整体性的优点。

附图说明

图1为本发明的流程图。

图2为本发明中冲突消解方法的流程图。

图3为仿真运行前算例阶段计划运行图。

图4为仿真情景一中列车1晚点600s调整计划图。

图5为仿真情景一中列车1晚点600s运行冲突消解代价曲线图。

图6为仿真情景二中列车1晚点1800s运行冲突消解代价曲线图。

具体实施方式

下面结合附图与实施例对本发明作进一步说明，本发明的实施方式包括但不 限于下列实施例。

实施例

列车运行冲突消解是一个对冲突列车占用运输资源的次序和时间的重新确 定问题。不同的列车运行冲突消解方案，将带来不同的列车运行调整效果，影响 行车指挥质量。因此，列车运行冲突消解方案的好坏直接影响行车指挥的效果。 列车运行冲突的消解是通过变更列车运行次序和到发时间来消除列车之间对运 输资源占用时间的重叠或使相关技术设备的运用满足列车的技术作业要求。

如图1和图2所示，本发明的实现过程如下：

（1）首先，获得当前时刻列车的运行状态、经过车站和区间状态，以方便 后续计算。

（2）检测是否有冲突发生或在在将来时刻是否有潜在冲突，若否，则在将 来时刻到来的时候更新数据信息，并重复该步骤，反之，则进入下一步；

对于检测是否有冲突或潜在冲突为现有技术故不多作说明。

（3）根据列车运行调整规则进行列车运行冲突消解，并按消解结果调整列 车运行方案直至列车运行结束，反之，返回上一步。

步骤（3）为本实施例将详细说明的步骤。

高速铁路的各类列车运行冲突中，可能发生在区间，也可能发生在车站。车 站间隔时间冲突、到发线运用冲突、动车组接续时间冲突、列车运行与旅客换乘 时间冲突、跨线列车跨线时间冲突为发生在车站的冲突，而区间冲突、行车作业 与维修作业冲突是发生在区间的冲突。车站间隔时间冲突中的发车间隔时间冲突 和到发线运用冲突的消解在冲突发生的当前车站完成，而区间冲突的消解需要在 冲突发生前的车站完成。动车组接续时间冲突、列车运行与旅客换乘时间冲突、 跨线列车跨线时间冲突是在区段终点站或特定的几个车站发生的冲突，需要在其 前方各站根据列车未来的运行可能性不断进行方案调整和修正进行消解，本实施 例将这几类冲突作为前述各类冲突消解方案可行性的评价依据，在列车运行冲突 预测时重点考虑这几类冲突发生的可能性并将其作为冲突消解方案的反馈信息。 但无论高速铁路列车运行冲突是发生在车站还是区间，列车运行冲突的消解均是 在车站完成的。

因此：

A.首先进行列车运行冲突度量，即判断所有冲突的严重程度。

B.对不同冲突进行冲突等级的度量，根据各冲突的严重程度排序。为了降 低冲突消解的复杂度，每次选择最严重的冲突进行优先消解，优先消除对列车运 行过程影响最大、危害最严重的列车运行冲突。

C.接下来依次解决每个冲突，对每个冲突制定具体的消解策略，而不同的 消解策略将导致不同的整体列车运行状态，对后续列车运行产生不同的影响。需 注意的是，冲突消策略的制定主要解决两个问题：冲突列车的运行次序和冲突列 车的时间平移量。

选取3个列车运行指标来评估列车的运行状态。

第一个指标：冲突时间消解代价

若将两列车运行特征值分别作为冲突列车时间平移的单位时间代价，则令其 与相应消解策略下所得方案的列车运行时间平移量的乘积为冲突消解时间代价 P_CT。设两列列车分别为i和j，在k站的平移量分别为ΔT_ik和ΔT_jk，两列列车在j 站的列车运行特征值分别为T_ik和T_jk，则列车i和j的冲突消解时间代价为：

$P_{\mathrm{CT}}^{\mathrm{ik}}=T_{\mathrm{ik}}\times \Delta T_{\mathrm{ik}}$

$P_{\mathrm{CT}}^{\mathrm{jk}}=T_{\mathrm{jk}}\times \Delta T_{\mathrm{jk}}$

该冲突消解方案为R_k，R_k的冲突消解时间代价为P_CT(R_k,s(k),i,j)，有：

P_CT(R_k,s(k),i,j)=T_ik×ΔT_ik+T_jk×ΔT_jk

冲突消解策略中对应冲突方案的P_CT越小，其冲突消解的效果越优，在冲突 消解时作为冲突消解方案确定的依据。

第二个指标：后效冲突

在k站消解列车i的冲突后，列车未来各类列车运行冲突可能性的总和称 为冲突消解方案的后效冲突，记为且有：

$V_{\mathrm{CT}}^{\mathrm{ik}}=\underset{j}{\overset{4}{\Sigma }}{P}_1\left(C_{\mathrm{Pj}}^i\right)+\underset{k+1}{\overset{n}{\Sigma }}\underset{r}{\overset{2}{\Sigma }}{P}_2\left(C_{\mathrm{Pr}}^{\mathrm{ik}}\right)$

式中等号右边加号前半部分为顺序运行模式工作流网的冲突预测 值，为冲突消解后列车各类冲突可能性值，包括4类冲突；为选择运行模式工作 流网的冲突预测值，为冲突消解后每一运输资源两个工作流支网冲突 的可能性值，包括车站追踪间隔时间冲突和到发线运用冲突两类，其中n为区段 终端车站序号。

第三个指标：列车运行冲突消解代价

列车i和j的冲突消解代价为：

${\hat{P}}_{\mathrm{CT}}^{\mathrm{ik}}=T_{\mathrm{ik}}\times \Delta T_{\mathrm{ik}}\times V_{\mathrm{CT}}^{\mathrm{ik}}$

${\hat{P}}_{\mathrm{CT}}^{\mathrm{jk}}=T_{\mathrm{jk}}\times \Delta T_{\mathrm{jk}}\times V_{\mathrm{CT}}^{\mathrm{jk}}$

R_j的冲突消解代价为：

$\left(\begin{array}{c}{\hat{P}}_{\mathrm{CT}}(R_k,s\left(k\right),i,j)={\hat{P}}_{\mathrm{CT}}^{\mathrm{ik}}+{\hat{P}}_{\mathrm{CT}}^{\mathrm{jk}}\\ =T_{\mathrm{ik}}\times \Delta T_{\mathrm{ik}}\left(R_k\right)\times V_{\mathrm{CT}}^{\mathrm{ik}}\left(R_k\right)+T_{\mathrm{jk}}\times \Delta T_{\mathrm{jk}}\left(R_k\right)\times V_{\mathrm{CT}}^{\mathrm{jk}}\left(R_k\right)\end{array}\right)$

为了实现列车运行效果的最优，在进行冲突消解时，总是优先选择冲突消解 代价最小的方案。欲追求所有列车冲突消解代价最小的方案，则对于某列车运行 特征值大、后效冲突大的列车，需要详细制定其列车运行计划，降低其与其他列 车的冲突，否则将对其他列车的运行产生巨大影响，为了实现此目标，则需使该 列车的平移量趋于最小，实行重点列车重点保障的列车运行调整原则。

因此在确定冲突消解次序后，对每个冲突在一定消解策略下的列车平移量， 计算列车运行特征值及该列车平移量下的后小冲突，并根据冲突消解代价确定冲 突列车的运行次序及各列车活动的实际发生时间。

本实施例中受随机干扰延误时间的影响，故提出减少冲突发生的可能性、对 消解起决定性作用的平移运行线、交换运行线、变更停站和越行以及数学规划四 种策略：

策略I：平移运行线即指当列车技术作业间隔时间小于相关作业标准而发生 列车运行冲突时，通过合理平移冲突点相关运行线，使列车技术作业时间间隔大 于等相关作业时间标准。

策略II：交换运行线即指当已经发生或即将列车运行冲突时，通过交换相关 列车运行线在站的出发顺序以消除相应的冲突。

策略III：变更停站和越行方案即指该策略是通过改变的列车的停靠站、停站 数以及待避和越行点进而达到消除列车运行冲突的目标，它是策略II的拓展。

策略IV：数学规划方法指根据一定的冲突消解和列车运行调整目标，利用数 学规划方法寻求列车运行冲突的组合优化，即将前述三种策略进行优化排列组 合，从全局角度制定最小代价的冲突消解方案。

其中单个冲突消解又涉及到多种冲突，如车站间隔时间冲突、区间冲突、到 发线运用冲突以及其他冲突。

我们依次来说明每种冲突通过不同的策略如果计算冲突消解代价。

车站间隔时间冲突又分为到达间隔时间冲突和出发间隔时间冲突。

一、对到达间隔时间冲突的冲突消解

策略I下到达间隔时间冲突消解代价为：

${\hat{P}}_{\mathrm{CT}}^1=T_{\mathrm{ik}}\times \Delta T_i^1\times V_{\mathrm{CT}}^{\mathrm{ik}}\left(1\right)+T_{\mathrm{jk}}\times \Delta T_j^1\times V_{\mathrm{CT}}^{\mathrm{jk}}\left(1\right)$

策略II下到达间隔时间冲突消解代价为：

${\hat{P}}_{\mathrm{CT}}^2=T_{\mathrm{ik}}\times \Delta T_i^2\times V_{\mathrm{CT}}^{\mathrm{ik}}\left(2\right)+T_{\mathrm{jk}}\times \Delta T_j^2\times V_{\mathrm{CT}}^{\mathrm{jk}}\left(2\right)=T_{\mathrm{jk}}\times \Delta T_i^2\times V_{\mathrm{CT}}^{\mathrm{ik}}\left(2\right)$

策略III下到达间隔时间冲突消解代价为：

${\hat{P}}_{\mathrm{CT}}^3=T_{\mathrm{ik}}\times \Delta T_i^3\times V_{\mathrm{CT}}^{\mathrm{ik}}\left(3\right)+T_{\mathrm{jk}}\times \Delta T_j^2\times V_{\mathrm{CT}}^{\mathrm{jk}}\left(3\right)=T_{\mathrm{ik}}\times \Delta T_i^2\times V_{\mathrm{CT}}^{\mathrm{ik}}\left(1\right)$

因此最终消解策略及确定消解方案的依据为使冲突消解代价最小：

${\hat{P}}_{\mathrm{CT}}^{*}=\min \{{\hat{P}}_{\mathrm{CT}}^1,{\hat{P}}_{\mathrm{CT}}^2,{\hat{P}}_{\mathrm{CT}}^3\}$

式中，i为第一辆列车，j为与第一辆列车相邻的第二辆列车，k表示第k个 站台，T表示时间，ΔT表示平移量，V表示后效冲突。

二、对出发间隔时间冲突的冲突消解

策略I下到达间隔时间冲突消解代价为：

${\hat{P}}_{\mathrm{CT}}^1=T_{\mathrm{ik}}\times \Delta T_j^1\times V_{\mathrm{CT}}^{\mathrm{jk}}\left(1\right)=T_{\mathrm{jk}}\times \Delta T_j^2\times V_{\mathrm{CT}}^{\mathrm{jk}}\left(1\right)\times (I_f-T_z)$

策略II下到达间隔时间冲突消解代价为：

${\hat{P}}_{\mathrm{CT}}^2=T_{\mathrm{ik}}\times \Delta T_i^2\times V_{\mathrm{CT}}^{\mathrm{ik}}\left(2\right)+T_{\mathrm{jk}}\times \Delta T_j^2\times V_{\mathrm{CT}}^{\mathrm{jk}}\left(2\right)=T_{\mathrm{ik}}\times \Delta T_i^2\times (I_f+T_z)$

因此最终消解策略及确定消解方案的依据为使冲突消解代价最小：

${\hat{P}}_{\mathrm{CT}}^{*}=\min \{{\hat{P}}_{\mathrm{CT}}^1,{\hat{P}}_{\mathrm{CT}}^2\}$

同理可得其他冲突消解代价。

（4）根据冲突的消解策略制定冲突的消解方案，并调整调整列车运行的数 学模型，使其为：

$\underset{i=1}{\overset{N_D}{\Sigma }}\underset{k=1}{\overset{K_D}{\Sigma }}{T}_{i,k}\times \Delta T_{i,k}\times V_{\mathrm{CT}}^{i.k}+\underset{i=1}{\overset{N_D}{\Sigma }}\underset{k=1}{\overset{K_D}{\Sigma }}{T}_{j,k}\times \Delta T_{j,k}\times V_{\mathrm{CT}}^{j.k}$

以上数值最小便为确定的冲突消解方案。

其中，T_i,k和T_j,k分别为上行和下行列车i和j分别在k站进行列车运行冲突 度量过程中的列车运行特征值。

ΔT_i,k和ΔT_j,k分别为上行和下行列车运行偏离运行计划时间，包括到站时间 偏离和离站时间偏离。

和分别为冲突消解后下行和上行列车的后效冲突，它们是列车实际 到站/离站时分的函数，是在确定了一个列车到站/离站时分后通过列车运行冲突 预测得到的未来各类冲突可能性之和。

该列车运行冲突消解方案的数学模型受到多重约束，为单目标非线性混合整 数规划模型。从模型可以看出，其自变量和约束条件的数量是非常大的，因此该 数学模型必须要同时满足所有的约束条件才能真正完成冲突消解，本实施例将要 说明约束条件的具体内容，为了后续建模方便，这里对需要用到的常量和变量予 以说明。首先对模型中涉及到的相关常量进行说明：

调整阶段内下行A类列车集合，本线速度较高的高速列车，$N_D^H=\left|T_D^H\right|,$$···,N_D^H;$

调整阶段内下行B₁类列车集合，本线速度较低的高速列车，$N_D^M=\left|T_D^M\right|,$$i=\mathrm{1,2},···,N_D^M;$

调整阶段内下行B₂类列车集合，跨线高速列车，

T_D：调整阶段内下行列车集合，有$T_D=T_D^H\cup T_D^M\cup T_D^O,N_D=\left|T_D\right|,i=\mathrm{1,2},L,N_D;$

调整阶段内上行A类列车集合，本线速度较高的高速列车，$N_U^H=\left|T_U^H\right|,$$i=\mathrm{1,2},L,N_U^H;$

调整阶段内上行B₁类列车集合，本线速度较低的高速列车，$N_U^M=\left|T_U^M\right|,$$i=\mathrm{1,2},L,N_U^M;$

调整阶段内上行B₂类列车集合，跨线高速列车，$N_U^O=\left|T_U^O\right|,$$i=\mathrm{1,2},L,N_U^O;$

T_U：调整阶段内上行列车集合，有$T_U=T_U^{H}U{T}_U^{M}U{T}_U^O,N_U=\left|T_U\right|,i=\mathrm{1,2},L,N_U;$

T：调整阶段内列车集合，因此T＝T_DUT_U，N＝|T|，N＝N_D+N_U，i＝1,2,L,N；

w_i：调整阶段内第i列列车的优先权值，满足

λ(i)：第i列列车类型，λ(i)＝1代表A类列车，λ(i)＝2代表B₁类列车， λ(i)＝3代表B₂类列车，

θ：列车类型，θ＝1代表A类列车，θ＝2代表B₁类列车，θ＝3代表B₂类列车；

S_D：下行车站集合，按下行方向对各车站依次进行编号，K_D＝|S_D|， k＝1,2,L,K_D；

B_D：下行区间集合，按下行方向对各区间依次进行编号，K_D-1＝|B_D|， kk＝1,2,L,K_D-1；

S_U：上行车站集合，按上行方向对各车站依次进行编号，K_U＝|S_U|， k＝1,2,L,K_U；

B_U：上行区间集合，按上行方向对各区间依次进行编号，K_U-1＝|B_U|， kk＝1,2,L,K_U-1；

根据列车运行计划，第i列下行列车在高速铁路上的运行径路——车 站表达方式，$G_D^i=\{{\mathrm{KD}}_1^i,{\mathrm{KD}}_2^i,L,{\mathrm{KD}}_t^{i}L,{\mathrm{KD}}_{K\left(i\right)}^i\},\forall i\in T_D,G_D^i\subseteq S_D;$和分别表示根 据列车运行计划，第i列下行列车经过的第t个和最后一个车站；

根据列车运行计划，第i列上行列车在高速铁路上的运行径路——车 站表达方式，$G_U^i=\{{\mathrm{KU}}_1^i,{\mathrm{KU}}_2^i,L,{\mathrm{KU}}_t^{i}L,{\mathrm{KU}}_{K\left(i\right)}^i\},\forall i\in T_U,G_U^i\subseteq S_U;$和分别 表示根据列列车运行计划，第i列上行列车经过的第t个和最后一个车站；

调整阶段内第i列下行列车在高速铁路上的运行径路——车站表达方 式，$J_D^i=\{{\mathrm{kd}}_1^i,{\mathrm{kd}}_2^i,L,{\mathrm{kd}}_t^{i}L,{\mathrm{kd}}_{K\left(i\right)}^i\},\forall i\in T_D,J_D^i\subseteq S_D;$和分别表示调整阶段 内第i列下行列车经过的第t个和最后一个车站；

调整阶段内第i列下行列车在高速铁路上的运行径路——区间表达方式， $V_D^i=\{{\mathrm{kkd}}_1^i,{\mathrm{kkd}}_2^i,L,{\mathrm{kkd}}_t^{i}L,{\mathrm{kkd}}_{\mathrm{KK}\left(i\right)}^i\},\forall i\in T_D,V_D^i\subseteq B_D;$和分别表示 调整阶段内第i列下行列车经过的第t个和最后一个区间；

调整阶段内第i列上行列车在高速铁路上的运行径路——车站表达方 式，$J_U^i=\{{\mathrm{ku}}_1^i,{\mathrm{ku}}_2^i,L,{\mathrm{ku}}_t^{i}L,{\mathrm{ku}}_{K\left(i\right)}^i\},\forall i\in T_U,J_U^i\subseteq S_U;$和分别表示调整阶段 内第i列上行列车经过的第t个和最后一个车站；

调整阶段内第i列上行列车在高速铁路上的运行径路——区间表达方 式，$V_U^i=\{{\mathrm{kku}}_1^i,{\mathrm{kku}}_2^i,L,{\mathrm{kku}}_t^{i}L,{\mathrm{kku}}_{\mathrm{KK}\left(i\right)}^i\},\forall i\in T_U,V_U^i\subseteq B_U;$和分别调整阶段 内表示第i列上行列车经过的第t个和最后一个区间；

第θ类下行列车在第kk个下行区间的最小纯运行时间，$\forall i\in T_D,$$\forall \mathrm{kk}\in B_D;$

第θ类上行列车在第kk个上行区间的最小纯运行时间，$\forall i\in T_U,$$\forall \mathrm{kk}\in B_U;$

第θ类下行列车在第k个下行车站的起车附加时间，

第θ类下行列车在第k个下行车站的停车附加时间，

第θ类上行列车在第k个上行车站的起车附加时间，

第θ类上行列车在第k个上行车站的停车附加时间，

第u类下行列车与第v类下行列车在第k个下行车站的出发间隔时 间，$\forall i\in T_D,\forall k\in S_D;$

第u类下行列车与第v类下行列车在第k个下行车站的到达间隔时间， $\forall i\in T_D,\forall k\in S_D;$

第u类上行

列车与第v类上行列车在第k个上行车站的出发间隔时间，

第u类上行列车与第v类上行列车在第k个上行车站的到达间隔时间， $\forall i\in T_U,\forall k\in S_U;$

第i列下行列车在其第k个下行车站最小停站时间，若第i列列车在第k 个车站始发或终点时，令其最小停站时间等于0，

第i列上行列车在其第k个上行车站最小停站时间，

第k个下行车站的到发线数，

第k个上行车站的到发线数，

第kk个下行区间的天窗开始时间，

第kk个下行区间的天窗结束时间，

第kk个上行区间的天窗开始时间，

第kk个上行区间的天窗结束时间，

第i列下行列车在第k个下行车站的计划到达时间，若第i列列车在第k 个车站始发时，令其计划到达时间等于计划出发时间，

第i列下行列车在第k个下行车站的计划出发时间，若第i列列车在 第k个车站终到时，令其计划出发时间等于计划到达时间，

第i列上行列车在第k个上行车站的计划到达时间，

第i列上行列车在第k个上行车站的计划出发时间，

0-1常量，若第i列下行列车在第k个下行车站需要办理旅客业务，取 为1，否则为0，$\forall i\in T_D,\forall k\in J_D^i;$

0-1常量，若第i列上行列车在第k个上行车站需要办理旅客业务，取 为1，否则为0，$\forall i\in T_U,\forall k\in J_U^i;$

第i列下行跨线B₂类列车在到达其高速铁路衔接站(跨线点)时可允 许最早到达时间，

第i列下行跨线B₂类列车在到达其高速铁路衔接站(跨线点)时可允 许最晚到达时间，

第i列上行跨线B₂类列车在到达其高速铁路衔接站(跨线点)时可允许 最早到达时间，

第i列上行跨线B₂类列车在到达其高速铁路衔接站(跨线点)时可允 许最晚到达时间，

第i列车与其接续列车接续时间标准；

第i列车与ii列车的旅客接续时间标准；

M：一个充分大的整数。

其次对模型中涉及到的相关变量进行说明：

第i列下行列车在第k个下行车站的实际到达时间，

第i列下行列车在第k个下行车站的实际出发时间，

第i列上行列车在第k个上行车站的实际到达时间，

第i列上行列车在第k个上行车站的实际出发时间，

0-1变量，若第i列下行列车在第j列下行列车之前进入第kk个下行 区间，其值取为0，否则为1，且i≠j，

0-1变量，若第i列上行列车在第j上行列车之前进入第kk个上行区 间，其值取为0，否则为1，且i≠j，

0-1变量，若第i列下行列车在第k个下行车站通过，取为0，否则为 1，$\forall i\in T_D,\forall k\in J_D^i;$

0-1变量，若第i列上行列车在第k个上行车站通过，取为0，否则为 1，$\forall i\in T_U,\forall k\in J_U^i;$

下面说明其具体的约束条件：

A.列车区间运行时间约束

根据列车停车或通过两邻接车站，区间运行时间需要考虑列车起停车附加时 分，即：

$X_D^{i,\mathrm{kk}+1}\ge Y_D^{i,\mathrm{kk}}+t_D^{\lambda \left(i\right),\mathrm{kk}}+{\phi }_D^{i,\mathrm{kk}}{\alpha }_D^{\lambda \left(i\right),\mathrm{kk}}+{\phi }_D^{i,\mathrm{kk}+1}{\beta }_D^{\lambda \left(i\right),\mathrm{kk}+1};\forall i\in T_D,\forall \mathrm{kk}\in V_D^i$

$X_U^{i,\mathrm{kk}+1}\ge Y_U^{i,\mathrm{kk}}+t_U^{\lambda \left(i\right),\mathrm{kk}}+{\phi }_U^{i,\mathrm{kk}}{\alpha }_U^{\lambda \left(i\right),\mathrm{kk}}+{\phi }_U^{i,\mathrm{kk}+1}{\beta }_U^{\lambda \left(i\right),\mathrm{kk}+1};\forall i\in T_U,\forall \mathrm{kk}\in V_U^i$

上式表示第i列下行列车在其运行路径上的第kk个下行区间运行时，其到达 该区间前方站的时间与从该站出发的时间间隔不得小于区间最小运行时分，如果 列车在某站通过，取相应的起停车附加时分为0；下式表示第i列上行列车在其 运行路径上的第kk个上行区间运行时，其到达该区间前方站的时间与从该站出 发的时间间隔不得小于区间最小运行时分。

B.列车停站时间约束

根据列车运行计划，各列车需要在其运行径路上部分或全部车站办理旅客业 务。对于各次列车而言，在其需要办理旅客业务的车站上，需要给予必要的停站 时间，供旅客上下车或进行必要的技术作业，即：

$Y_D^{i,k}\ge X_D^{i,k}+s_D^{i,k};\forall i\in T_D,\forall k\in J_D^i;$

$Y_U^{i,k}\ge X_U^{i,k}+s_U^{i,k};\forall i\in T_U,\forall k\in J_U^i;$

上式表示第i列下行列车在其运行路径上的第k个下行车站上的停留时间不 得小于最小停站时间，下式表示第i列上行列车在其运行路径上的第k个上行车 站上的停留时间不得小于最小停站时间。

C.列车出发追踪间隔时间约束

同向相邻列车从同一车站出发时，需满足一定的出发追踪间隔时间，即：

$Y_D^{i,k}\ge Y_D^{j,k}+p_D^{\lambda \left(j\right),\lambda \left(i\right),k}$或$Y_D^{j,k}\ge Y_D^{i,k}+p_D^{\lambda \left(i\right),\lambda \left(j\right),k};$其中

$\forall i,j\in T_D$且i≠j，$\forall k\in J_D^i\cap J_D^j;$

$Y_U^{i,k}\ge Y_U^{j,k}+p_U^{\lambda \left(j\right),\lambda \left(i\right),k}$或$Y_U^{j,k}\ge Y_U^{i,k}+p_U^{\lambda \left(i\right),\lambda \left(j\right),k};$其中

$\forall i,j\in T_U$且i≠j，$\forall k\in J_U^i\cap J_U^j.$

上式表示同向相邻第i列与第j列下行列车在其相同径路里的第k个下行车 站出发时需满足出发追踪间隔时间；下式表示同向相邻第i列与第j列上行列车 在其相同径路里的第k个上行车站出发时需满足出发追踪间隔时间；

通过引入决策变量可以将上述非线性约束转换为线性约束，即：

$Y_D^{i,\mathrm{kk}}\ge Y_D^{j,\mathrm{kk}}+p_D^{\lambda \left(j\right),\lambda \left(i\right),\mathrm{kk}}-(1-{\chi }_D^{i,j,\mathrm{kk}})\mathrm{gM},\forall i,j\in T_D$且i≠j，$\forall \mathrm{kk}\in V_D^{i}I{V}_D^j;$

$Y_D^{j,\mathrm{kk}}\ge Y_D^{i,\mathrm{kk}}+p_D^{\lambda \left(i\right),\lambda \left(j\right),\mathrm{kk}}-{\chi }_D^{i,j,\mathrm{kk}}\mathrm{gM},\forall i,j\in T_D$且i≠j,$\forall \mathrm{kk}\in V_D^{i}I{V}_D^j;$

$Y_U^{i,\mathrm{kk}}\ge Y_U^{j,\mathrm{kk}}+p_U^{\lambda \left(j\right),\lambda \left(i\right),\mathrm{kk}}-(1-{\chi }_U^{i,j,\mathrm{kk}})\mathrm{gM},\forall i,j\in T_U$且i≠j，$\forall \mathrm{kk}\in V_U^{i}I{V}_U^j;$

$Y_U^{j,\mathrm{kk}}\ge Y_U^{i,\mathrm{kk}}+p_U^{\lambda \left(i\right),\lambda \left(j\right),\mathrm{kk}}-{\chi }_U^{i,j,\mathrm{kk}}\mathrm{gM},\forall i,j\in T_U$且i≠j，$\forall \mathrm{kk}\in V_U^{i}I{V}_U^j.$

D.列车到达追踪间隔时间约束

同向相邻列车到达同一车站时，需满足一定的到达追踪间隔时间，即：

$X_D^{i,k}\ge X_D^{j,k}+q_D^{\lambda \left(j\right),\lambda \left(i\right),k}$或$X_D^{j,k}\ge X_D^{i,k}+q_D^{\lambda \left(i\right)\lambda \left(j\right),k};$其中$\forall i,j\in T_D$且i≠j,$\forall k\in J_D^{i}I{J}_D^j;$

$X_U^{i,k}\ge X_U^{j,k}+q_U^{\lambda \left(j\right),\lambda \left(i\right),k}$或$X_U^{j,k}\ge X_U^{i,k}+q_U^{\lambda \left(i\right),\lambda \left(j\right),k},$其中$\forall i,j\in T_U$且i≠j,$\forall k\in J_U^i\cap J_U^j.$

其中上式表示同向相邻第i列与第j列下行列车在到达其相同径路里的第k 个下行车站时需满足到达追踪间隔时间，下式表示同向相邻第i列与第j列上行 列车到达其相同径路里的第k个上行车站时需满足到达追踪间隔时间。

通过上述决策变量将上述非线性约束转换为线性约束，即：

$X_D^{i,\mathrm{kk}+1}\ge X_D^{j,\mathrm{kk}+1}+q_D^{\lambda \left(j\right),\lambda \left(i\right),\mathrm{kk}}-(1-{\chi }_D^{i,j,\mathrm{kk}})\mathrm{gM},\forall i,j\in T_D$且i≠j，$\forall \mathrm{kk}\in V_D^{i}I{V}_D^j;$

$X_D^{j,\mathrm{kk}+1}\ge X_D^{i,\mathrm{kk}+1}+q_D^{\lambda \left(i\right),\lambda \left(j\right),\mathrm{kk}}-{\chi }_D^{i,j,\mathrm{kk}}\mathrm{gM},\forall i,j\in T_D$且i≠j，$\forall \mathrm{kk}\in V_D^{i}I{V}_D^j;$

$X_U^{i,\mathrm{kk}+1}\ge X_U^{j,\mathrm{kk}+1}+q_U^{\lambda \left(j\right),\lambda \left(i\right),\mathrm{kk}}-(1-{\chi }_U^{i,j,\mathrm{kk}})\mathrm{gM},\forall i,j\in T_U$且i≠j，$\forall \mathrm{kk}\in V_U^{i}I{V}_U^j;$

$X_U^{j,\mathrm{kk}+1}\ge X_U^{i,\mathrm{kk}+1}+q_U^{\lambda \left(i\right),\lambda \left(j\right),\mathrm{kk}}-{\chi }_U^{i,j,\mathrm{kk}}\mathrm{gM},\forall i,j\in T_U$且i≠j，$\forall \mathrm{kk}\in V_U^{i}I{V}_U^j.$

E.需办理旅客业务车站发车时间约束

$Y_D^{i,k}\ge y_D^{i,k},\forall i\in T_D,\forall k\in J_D^i$且$c_D^{i,k}=1$

$Y_D^{i,k}\ge y_D^{i,k},\forall i\in T_D,\forall k\in J_D^i$且$c_D^{i,k}=1$

上式表示第i列下行列车在其运行调整阶段内所经某车站需办理旅客业务 时，其在该站的发车时间不得小于图定发车时间；下式表示第列上行列车在其 运行调整阶段内所经某车站需办理旅客业务时，其在该站的发车时间不得小于图 定发车时间。

F.车站到发线约束

同一时间内停留在某车站的列车数不得大于该站可利用的到发线数，即：

$\underset{i\in T_D}{\Sigma }{M}_D(i,j,k)\le F_D^k,\forall k\in J_D^{i}I{J}_D^j$

$\underset{i\in T_U}{\Sigma }{M}_U(i,j,k)\le F_U^k,\forall k\in J_U^{i}I{J}_U^j$

MD（i,j,k）表示同一时间停留在第k个下行车站的列车数(含通过列车)不得 大于其可利用的到发线数；MU(i,j,k)表示同一时间停留在第k个上行车站的列车 数(含通过列车)不得大于其可利用的到发线数。

G.列车组接续时间约束

对于两列车共用一组动车组时，为了不影响列车的正点始发，动车组担任前 一运输任务的完成时间应不晚于后一运输任务列车始发时刻减去动车组必要的 接续时间，即：

$X_D^{i,k}+T_z\le y_D^{j,k},\forall T_D,\forall i\in T_{D}U{T}_U,\mathrm{i\Xi j}$

$X_U^{i,k}+T_z\le y_U^{j,k},\forall T_U,\forall i\in T_{D}U{T}_U,i\mathrm{\Xi j}$

H.旅客换乘时间约束

为了保障旅客的旅行效率，尽量减少旅客的换乘等待时间，应保障有大量旅 客换乘的两列车之间的接续，使列车到达车站时刻不晚于换乘列车出发时刻减去 旅客必要的换乘接续时间，即：

$X_D^{i,k}+T_c\le y_D^{j,k},\forall T_D,\forall j\in T_{D}U{T}_U,i\mathrm{\Xi j}$

$X_U^{i,k}+T_c\le y_U^{j,k},\forall T_U,\forall j\in T_{D}U{T}_U,i\mathrm{\Xi j}$

I.跨线列车跨线时间约束

为了使得跨线B2类列车与衔接线列车运营有良好的接续，不产生由于列车 的晚点影响在线路之间的传播，实现路网列车运行的协调，跨线列车在到达高速 铁路衔接站(跨线点)时的时间需要满足规定的时间间隔，即：

$H_D^{i,K_{K\left(i\right)}^i}\le X_D^{i,K_{K\left(i\right)}^i}\le Q_D^{i,K_{K\left(i\right)}^i},\forall i\in T_D^O$且$K_{K\left(i\right)}^i\in J_D^i$

$H_U^{i,K_{K\left(i\right)}^i}\le X_U^{i,K_{K\left(i\right)}^i}\le Q_U^{i,K_{K\left(i\right)}^i},\forall i\in T_U^O$且$K_{K\left(i\right)}^i\in J_U^i$

上式表示第i列跨线B2类列车在到达其高速铁路衔接站时需要满足规定的 时间间隔；下式表示第i列上行跨线B2类列车在到达其高速铁路衔接站(跨线点) 时需要满足规定的时间间隔。

J.天窗时间约束

在规定天窗时间内，列车不能进行天窗运行，即：

$X_D^{i,\mathrm{kk}+1}\le L_D^{\mathrm{kk}}U{Y}_D^{i,\mathrm{kk}}\ge R_D^{\mathrm{kk}},\forall i\in T_D$且$\mathrm{kk}\in V_D^i$

$X_U^{i,\mathrm{kk}+1}\le L_U^{\mathrm{kk}}U{Y}_U^{i,\mathrm{kk}}\ge R_U^{\mathrm{kk}},\forall i\in T_U$且$\mathrm{kk}\in V_U^i$

上式表示第i列下行列车不能在第kk个下行区间的天窗时间内到达或出发， 下式表示第i列上行列车不能在第kk个上行区间的天窗时间内到达或出发。

K.逻辑约束

列车是否不停车通过车站时的到发时间关系：

$Y_D^{i,k}-X_D^{i,k}\le {\phi }_D^{i,k}\mathrm{gM},\forall i\in T_D,k\in J_D^i$

$Y_U^{i,k}-X_U^{i,k}\le {\phi }_U^{i,k}\mathrm{gM},\forall i\in T_U,k\in J_U^i$

联系之前已建立的高速铁路列车运行调整的数学规划模型与所有约束条件， 可得知该数学规划模型具有以下特点：

第一：目标函数是单列列车指标的和，不同列车的指标之间不存在耦合关系。 对于这样的优化目标，单列列车性能指标的最优与列车整体性能指标的最优等 价，采取合理的方法，对模型按列车别进行分解是可行，换句话说，这样的目标 函数结构有利于对模型进行分解，为降低模型求解难度提供了可能。

第二：列车区间运行时间和列车停站时间约束均采用不等式形式，符合运行 调整策略，使晚点列车尽量恢复正点。在列车运行调整过程中，通过利用运行图 冗余时间改变列车区间运行时间和停站时间来使晚点列车恢复正点，或缓解列车 晚点的程度是常采用的策略；区间纯运行时间和车站停站时间均采用最小值，可 充分利用计划运行图弹性，尽量恢复正常行车。

第三：通过引入0-1变量，使列车出发和到达追踪间隔时间非线性约束转换 为线性约束，尽管降低了过多的非线性约束给模型求解造成的困难，但与此同时， 过多的0-1变量加入模型，同时加大了模型求解的难度。

第四：对于具体的列车运行调整问题，有大量冗余约束条件。在具体的运行 调整阶段内，每列列车有可能只有部分运行路径在本阶段完成，由此两列列车之 间也只需要考虑相应的部分约束条件即可，从这个方面来看，尽管原模型中约束 条件很多，但具体到每一个具体的运行调整问题时，存在着大量的冗余约束条件， 优化目标只需在需要考虑的约束条件形成的可行域里实现即可。

第五：为了确定T_i,k和T_ii,k，需确定列车运行5个状态指标的值，这5个指标 中，列车等级、列车旅程完成度、列车在站停车裕度、列车区间运行裕度等4个 指标在列车运行图给定之后便可得到相应列车i和ii在站k时的取值，在一个阶 段调整计划中是一组常量。而列车正点水平指标需根据列车到站时间的正晚点情 况取值，T_i,k和T_ii,k分别是关于列车i和ii在站k的实际到达时间和的函数。

第六：冲突消解的后效冲突是在列车到站/离站时分确定后根据冲突预测方法 计算得到各列车后续运行过程中各类冲突的总和。在进行冲突预测过程中，列车 区间运行时分、停站时分、冗余时间等均在运行图确定之后即确定了。因此，冲 突消解的后效冲突和分别是关于自变量列车到发时刻的函数。其中列 车到达间隔时间冲突和到发线运用冲突是列车到站时间偏差的函数，其余冲突是 列车离站时间偏差的函数。

第七：列车运行冲突消解代价最小为目标函数，由于列车运行特征值及冲突 消解的后效冲突均是通过迭代运算得到，其取值受行车调度员调度偏好影响小， 具有较高的客观性。列车运行特征值及冲突消解的后效冲突均可通过程序化过程 求得，模型的求解关键是确定合理的列车运行计划偏离时间。

（5）判断是否所有冲突的消解方案确定，若已确定完所有冲突的消解方案， 该冲突消解过程结束，若未确定完所有冲突的消解方案，则重复步骤（3）～（5）。

在建立该高速铁路列车运行调整的数学规划模型后，需要进行求解。该模型 求解算法较多，但大部分算法不够精确，求解出的结果不甚令人满意。常规的非 线性优化方法通常是要求优化问题连续可微，一般要求初始解为可行解，且多智 能计算得到局部最优解，在全局寻优方面存在严重不足。对于列车运行调整问题 而言，列车到达、出发时刻为离散的，不具有连续可微特征，且不同运行计划的 搜索计算为组合爆炸的。以M个车站N列车的列车运行调整问题为例，需确定 的列车到发时刻数为2MN个，将列车的到发时刻作为列车运行调整的变量，则 该列车运行调整问题有2MN个变量，其计算量非常之大，且列车运行过程中的 复杂约束和运行时刻具有逻辑性强特点，因此，运用常规非线性优化技术很难构 造出简单高效的高速铁路列车运行调整实用算法。

遗传算法(Genetic Algorithm，简称GA)是基于达尔文进化论“优胜劣汰，适 者生存”的自适应随机搜索优化算法。遗传算法在求解多约束非线性规划问题方 面能够发挥其全局寻优优势，在工业技术领域广泛应用，在铁路运输组织优化领 域也得到了长足发展和应用。遗传算法的主要步骤依次为种群初始化、个体评价、 遗传操作以及终止判断，其中种群初始化是通过遗传编码实现，个体评价是通过 对种群个体目标函数值进行适应性评价得到，遗传操作包括选择、交叉和变异三 项工作，终止判断是通过设定的搜索条件对算法进行终止，输出具有最大适应度 的最优个体及其变量值作为最优解。

本发明根据高速铁路列车运行调整的特点，设计求解列车运行调整问题基于 实数编码的遗传算法(Real-coded Genetic Algorithm,RGA)。RGA使用各列车在各 站的到发时刻编码并直接进行遗传操作，无需进行特定的解码过程，降低了算法 的复杂度，尤其是对于高速铁路列车运行调整这类大规模、多变量的优化问题， 能够提高算法的效率。

我国已投入运营的京津城际高铁、武广高铁以及京沪高铁等线路的运营实践 表明：我国高速铁路运营初期的行车间隔较大，列车运行图冗余时间大，列车运 行调整弹性大，列车运行调整难度较小。但随着高速铁路客运市场的发展，高密 度、大行车量必将是我国高速铁路的发展趋势，此时高效的列车运行调整模型研 究是非常必要的。

本实施例根据我国高铁的运营实践构建一个高密度列车运行调整计划的算 例。并利用matlab7.8编写了基于列车运行冲突消解的高速铁路列车运行调整遗 传算法求解程序对含有5个车站、10列车、260km区段的阶段计划(3h)进行调整 的具体例子来说明该遗传算法的求解流程。

一、参数设置

1.确定列车运行的基本信息

车站数M=5，车站序号m=1,2…,5。

列车数N=10，列车序号m=1,2…,10。

区间数Q=4，区间序号q=1,2…,4。

已知一阶段计划的计划运行时刻表如表1所示。

表1

其中“—”表示列车为始发或终到列车。列车1和列车5为进入区段并在区 段终点站终到的列车，列车2、列车3、列车4、列车7、列车8和列车10为区 段内始发终到的列车，列车6和列车9为区段内始发在区段外终到的列车。

因此其算例阶段计划运行图如图3所示。

各列车的列车等级属性如表2所示，且设各列车在各站的列车等级不变。

表2

其中“3”表示高等级高速列车，“2”表示低等级高速列车。

根据各列车运行至各站时完成的里程数占其全程的比例，计算得到各列车在 各站的旅程完成度如表3所示。

表3

各列车运行状态指标权重：

w=[0.2220.4510.1020.0620.163]

各列车的区间运行和车站停车三角模糊数时间分别如表4和表5所示。

表4

表5

表6为各列车动车组接续时间表。

表6

列车5和列车10在站5有大量客流换乘其他列车，这两列车的换乘截止期 限分别为43980s和46680s。

跨线列车6和9在站5的允许跨线时间区间分别为[43980,45180]和 [45720,46920]。

站1和站5为始发终到站，设到发线均足够，站2～站4每站单方向均有两条 到发线。

由于高速铁路天窗开设时间为0～21600s，因此本算例不涉及列车运行与天窗 开设时间冲突的问题。

列车起停车附加时分t_q=t_t=120s，列车到达、出发最小追踪间隔时间I_min＝ 180s。

所有列车均具备利用冗余时间赶点运行的技术条件，低等级高速列车在赶点 运行时在站停留时间最短为120s，高等级高速列车在赶点运行时在站停留时间最 短为60s。

二、遗传参数设置

种群规模NIND＝60；

变异概率p_m＝0.03；

最大遗传代数MAXGEN=1500；

GGAP=0.1；

变异步长h=60s。

三、仿真情景一：列车1晚点600s到达站1

列车1和列车2在站2发生出发间隔时间冲突，同时在站3和站4均发生到 达间隔时间冲突和出发间隔时间冲突。经过对冲突进行消解并调整列车运行计划 后，得到列车运行调整计划如表7和图4所示，其列车运行冲突消解代价优化曲 线如图5所示。

表7

在列车1较短时间晚点时，仅通过改变列车1在站1的发车时刻及列车2在 站2的发车时刻，以及使列车1充分利用其在区间和车站的冗余时间赶点运行， 使用的策略有平移运行线和交换运行线两种单个冲突消解策略，消除了调整前的 冲突，对列车3至10的运行不产生影响，得到调整计划的冲突消解代价为2397， 所有列车终到总晚点时间减为180s，得到该运行结果迭代了990代，耗时86s， 在实效性方面能够满足需求。

四、仿真情景二：列车1晚点1800s到达站1

如果列车1利用冗余时间尽量减少晚点时间，则其将与列车5在站1产生出 发间隔时间冲突，与列车5在各区间均产生区间冲突，在站4与列车3产生出发 间隔时间冲突。经过对冲突进行消解并调整列车运行计划后，得到列车运行调整 计划如表8所示。

表8

并得到列车1晚点1800s列车运行冲突消解代价曲线图，如图6所示。

在列车1较长时间晚点时，列车1全程充分利用其在区间和车站的冗余时间 赶点运行，列车5晚点出发360s，列车4在站2待避列车1和列车5，列车1在 站3待避列车5，平移运行线、交换运行线和变更越行方案三种单个冲突消解策 略均使用到了，消除了调整前的冲突，对其他列车的运行不产生影响，得到调整 计划的冲突消解代价为21858，所有列车终到总晚点时间减为1380s，得到该运 行结果迭代了1006代，耗时86s。

按照上述实施例，便可很好地实现本发明。