考虑冲突评分的高速铁路列车运行冲突消解研究

Research on Conflict Resolution of High Speed Railway Train Operation Considering Conflict Scoring

摘要

为研究高速铁路列车运行冲突消解问题，提出一种基于列车运行冲突严重性评分的冲突消解方法；首先，基于列车运行数据，提取列车运行冲突信息，建立列车运行冲突评分准则，评估冲突的严重性，提出冲突消解代价计算方法。基于冲突严重性以及消解代价构建以冲突消解代价最小化为优化目标的混合整数规划模型；针对模型特点，设计大邻域搜索(LNS)、遗传算法(GA)和变邻域搜索算法(VNS)对模型进行求解。基于武广高速铁路真实干扰案例验证，结果表明，LNS算法在求解效率和计算结果方面具有显著优势，能够在较短时间内获得高质量的冲突消解方案；与既有的以总延误时间最小化为优化目标相比，提出的模型冲突消解代价降低了5.69%，晚点时间方差降低了8.32%，晚点频次减少了9次。提出的方法能够更为精准地衡量不同冲突的严重性，优先消解影响较大的冲突，从而有效提升铁路运行的稳定性与调度效率。

Abstract

To research the problem of high speed railway train operation conflict resolution, this paper proposed a conflict resolution method based on train operation conflict severity scoring. First, based on train operation data, train operation conflict information was extracted; train operation conflict scoring criteria were established to evaluate the severity of the conflicts, and a conflict resolution cost calculation method was proposed. Based on conflict severity and resolution cost, a mixed-integer programming model was constructed with the optimization objective of minimizing the conflict resolution cost. According to model characteristics, large neighborhood search (LNS), genetic algorithm (GA), and variable neighborhood search algorithm (VNS) were designed to solve the model. Based on validation using real disturbance cases of the Wuhan-Guangzhou High Speed Railway, the results show that the LNS algorithm has significant advantages in solution efficiency and calculation results and can obtain high-quality conflict resolution schemes within a short time. Compared with the existing optimization objective of minimizing total delay time, the conflict resolution cost of the proposed model is reduced by 5.69%; the delay time variance is reduced by 8.32%, and the number of delays is reduced by nine. The proposed method can more accurately measure the severity of different conflicts, prioritize the resolution of conflicts with great impact, and thereby effectively improve the stability and dispatching efficiency of railway operation.

Graphical abstract

关键词

列车运行 / 冲突评分 / 冲突消解 / 冲突消解代价 / 冲突消解方案

Key words

Train Operation / Conflict Scoring / Conflict Resolution / Conflict Resolution Cost / Conflict Resolution Scheme

0　引言

铁路行车实时应急调度指挥的核心任务是选择合理的策略消解列车运行冲突，确定列车运行时间及顺序，从而提升铁路运输效率。列车运行冲突消解的本质是对运输资源占用的全局优化过程，其目标是通过调整列车运行顺序和到发时间使列车满足技术作业要求。不同的列车运行冲突消解方案的效果存在显著差异，冲突消解方案的优劣直接影响铁路行车的运行质量及系统稳定性。

在列车运行冲突消解问题上，国内外学者已开展了大量研究工作，提出了多种理论方法与优化模型；数学优化方法是最常用的方法之一，主要包括整数线性规划模型、混合整数线性规划模型、非线性整数规划模型，并广泛应用分支定界、拉格朗日松弛优化算法、遗传算法等进行求解。文超等^[1-2]对列车运行过程中常见的7类冲突的判定方法进行了深入研究，并在研究单个列车运行冲突消解的基础上，提出了包括平移运行线、交换运行线、变更停站和越行方案在内的4种主要冲突消解策略，并结合数学规划方法对到达间隔冲突、出发冲突以及到发线运用冲突等典型冲突的消解进行了深入探索。部分学者基于轨道区段锁闭时间理论对资源占用冲突即列车运行冲突进行描述^[3-4]。林枫等^[5]提出不同高速铁路车站的冲突判定条件及检测步骤。洪鑫等^[6]基于时空网络提出了多种类的列车运行冲突的判定方法，并基于滚动时域和深度优先搜索方法，提出了列车运行冲突检测步骤。冯丽萍等^[7]基于模糊时间知识推理算法提出冲突判定时间条件。郭竞文^[8]则考虑了冲突的动态性特征，建立了以最小化列车总延误时间为优化目标的列车运行调整优化模型。此外，在全局冲突优化领域，张俊等^[9]提出了一种双目标规划模型，以延误传播最小化和列车均衡调整为优化目标，综合运用了帕累托最优和纳什均衡的方法对冲突消解问题进行求解。Domino等^[10]探讨了如何利用量子退火解决单线铁路上的列车调度冲突问题，并提出了一种二次无约束二进制优化(QUBO)模型。Meloni等^[11]提出一种新的方法，用于评估列车运行冲突产生的延误的风险，并以此开发了一个基于图的模型，对列车运行冲突消解方案的实时风险进行评估。Corman等^[12]提出了一种以最小化列车延误时间和错过接驳为双目标的列车冲突消解方法，并设计了2种基于替代图模型的启发式算法，对荷兰复杂且高密度铁路网络的实际运行情况进行了验证计算。Zhao等^[13]对铁路运营中可能发生的冲突进行了分类和定义，并提出了一种列车冲突预测与协同解决方法。Dündar等^[14]提出了一种基于遗传算法的冲突消解方法，并根据调度员的实时操作和算法的精确度对方法进行了评价。Samà等^[15-16]在实时冲突消解研究中，将列车路线选择问题建模为整数线性规划问题，并基于蚁群行为启发算法对模型进行求解。此外，Bettinelli等^[17]基于时空网络设计了一种列车迭代贪婪调度的启发式算法，在时空网络上快速求解实时冲突问题，为复杂场景下的列车运行冲突提供了有效解决方案。Binder等^[18]创新性地将乘客满意度、运营成本和未中断时间表的偏差3个目标进行整合，并建立一个整数线性规划模型。Wang等^[19]基于模型预测控制(MPC)，通过最小化新旧时刻表的差异为优化目标，建立冲突消解模型，并采用分支定界算法求解。

综上所述，现有研究多以最小化列车延误时间为优化目标消解冲突。然而，在冲突消解过程中，不同类型冲突的严重程度和对列车运行计划的影响并不相同，冲突消解时，不同冲突之间的代价差异显著，仅以降低列车延误为优化目标的消解策略在实际应用中存在一定局限性。因此，考虑列车运行冲突的严重程度，以评分度量不同冲突严重程度，并定义冲突消解代价，以此为优化目标对冲突进行消解，以期提高冲突消解方案的科学性和应用效果。

1　问题描述

列车运行冲突本质上是不同列车对运输资源占用时间的冲突。列车运行冲突示意图如图1所示，列车i计划占用运输资源的时间段为[a，c]，列车j计划占用时间段为[c，e]；但由于突发情况，列车i发生晚点，实际占用时间段变为[b，d]，与列车j的占用时间发生重叠；列车i与列车j在时间段[c，d]占用同一运输资源发生的冲突即为列车运行冲突。

列车运行冲突主要表现为列车运行过程中无法满足既定的技术要求。多冲突示意图如图2所示。列车i由于突发状况在车站2发生较大程度的晚点，其到达时间超过了列车j在该区间的资源占用时间，从而导致区间冲突。同时，列车i与列车n之间的间隔时间未满足最小技术间隔要求，因此又发生了车站间隔时间冲突。在列车j与列车n的冲突处理中，列车n出现了晚点，进而与列车m之间也发生了车站间隔时间冲突。为了解决这些冲突，列车j，n，m均进行了相应的晚点调整，最终形成了实际运行线。从计划图中可以看出，这3组列车的冲突类型不同，且处于不同的运行状态；其中，列车n与列车i及列车m都存在车站间隔时间冲突。对于这2个冲突，可以参考实际运行线中所采用的处理方案，即按照冲突发生的时间顺序，逐步进行冲突的消解。然而，在实际冲突消解过程中，若列车m所面临的冲突影响明显大于列车i，则应优先考虑减轻列车m与列车n之间冲突的影响，尽量减少列车m的晚点时间，甚至在条件允许的情况下，确保列车m按计划正常运行。相应地，可以适当延长列车n的晚点时间。这种冲突消解策略虽然可能导致整体晚点时间的增加，特别是列车n的晚点时间被延长，但通过保障列车m的正常运行，可以有效降低因处理列车n与列车m之间冲突而带来的综合成本。与第1种处理方案相比，尽管总晚点时间略有增加，但受影响的列车数量减少，且综合成本更低。为选择最优的冲突消解方案，需要综合考虑各类冲突的严重程度及其消解的优先级。

因此，如何科学地评估不同冲突的影响程度和合理确定冲突列车的优先级别，是提高冲突消解方案质量的关键。其关键就在于确定不同冲突的严重程度，即度量列车运行冲突严重性；以往对列车运行冲突的分级多采用静态分级方法，即根据冲突可能造成的影响进行定性的分级；然而，静态分级存在一定局限性，特别是在冲突刚发生时，其实际影响往往尚未显现，因此难以依据实际后果进行准确评估。为此，有必要引入动态分级机制，即在冲突发生的同时，通过定量方法对冲突进行评估，可通过确定各列车的运行状态参数(如晚点时间、列车等级、列车区间冗余时间等)，以此来确定各冲突的严重程度。

为了准确描述动态分级的方法，确定冲突中各列车的运行状态，引入了“列车运行冲突评分”的概念以及“列车运行冲突消解代价”的概念；前者指通过定量方法对各列车的运行状态进行评估，计算相关评分，并将各项指标整合为一个可供比较的综合数值；后者指在定量确定各列车的运行状态参数后，冲突消解时产生的时间偏移。通过引入以上2个概念，可以更加精确地判断冲突的严重程度及优先级，从而为复杂条件下的大规模列车冲突消解提供更加科学和高效的解决方案。

模型中采用的参数符号说明如表1所示，其他相关参数与变量将在建模过程中予以解释。

定义列车运行冲突评分：不同冲突中列车运行状态不同，导致列车运行冲突严重程度不同，列车运行冲突评分是对冲突严重程度的定量评估。列车运行冲突评分越高，严重程度就越大，相同程度的晚点所产生的代价也就越高，消解优先级就越大；在生成冲突消解方案时，需要对多个列车运行冲突进行评分，为列车运行冲突消解提供依据。

定义列车运行冲突消解代价：将列车运行冲突评分视为冲突列车晚点的单位时间成本，则列车运行冲突消解后的总时间成本即为总晚点时间与列车运行冲突的评分的乘积。该乘积即为列车运行冲突消解代价。最终生成的冲突消解方案的冲突消解代价越小，冲突消解的效果越好。

2　列车运行冲突消解模型

2.1　列车运行冲突消解思路

以冲突评分为基础，确定冲突消解代价计算方法，建立以消解代价为目标函数的整数规划模型，并以实际运行数据进行有效性验证。列车运行冲突消解路线如图3所示。

关键步骤实现如下。

（1）列车运行冲突提取。基于列车运行数据和冲突判定条件，判断是否发生冲突，以此作为冲突评分的决策属性。

（2）冲突评分指标及权重确定。依据列车运行调整基本原则以及过往对于列车运行指标的研究，确定列车运行冲突评分体系。

（3）冲突消解模型建立。在对冲突进行消解时主要解决冲突列车的2个问题：①冲突列车的消解次序；②冲突列车的时间平移量；基于(2)中所确定的各列车的冲突评分确定冲突列车的消解优先级，以最小化总冲突消解代价为优化目标，考虑多种约束条件，建立整数规划模型消解冲突，并生成最终的列车运行方案。

2.2　列车运行冲突判定

模型所研究的列车运行冲突主要包括3类：车站时间间隔冲突、区间冲突和到发线运用冲突，本节将对这3类冲突进行定义，并给出具体的判定依据。

车站时间间隔冲突：当同向行驶的前行列车i和后行列车j，在车站k的到达或出发间隔时间不满足最小间隔时间标准时，即视为发生车站时间间隔冲突。

其判定依据为两列车在车站的计划间隔时间与最小间隔时间的关系，若小于则发生车站时间间隔冲突，反之则不发生；以M表示是否发生车站时间间隔冲突，M为0-1变量，若发生冲突，则M为1，反之为0，则冲突判定条件为

(1)

式中：t_{i,j,k}为列车i与列车j在车站k的计划间隔时间，s；t_{\mathrm{m}\mathrm{i}\mathrm{n}}为计划最小间隔时间，s；t_w^{i,k}，t_w^{j,k}分别为列车i与列车j在车站k的晚点时间，s。

区间冲突：当两同向行驶的前行列车i和后行列车j，在区间(k，k+1)运行时，由于后行列车j速度大于前行列车i，按计划运行时后行列车会提前到达车站k+1，就会发生区间冲突。

区间冲突的判定依据为两列车在区间(k，k+1)的运行线是否发生交叉，可以通过计算两列车在车站k的出发时间之差与在车站k+1的到达时间之差，两者相乘，若小于0则发生区间冲突，反之则不发生该类冲突，以N表示是否发生区间冲突，N为0-1变量，发生冲突，则N为1，反之为0，其判断条件为

(2)

到发线运用冲突：指车站k在容纳列车时，列车数超过其最大到发线数量时，即视为发生到发线运用冲突。

到发线运用冲突的判定依据为车站容纳列车数量与最大到发线数量的关系，若大于则发生到发线运用冲突，反之则不发生该类冲突，以Z表示是否发生到发线运用冲突，Z为0-1变量，发生冲突，则Z为1，反之为0，其判断公式为

Z=\left\{\begin{array}{l}\mathrm{0}{n}_t^k\le S_D^k\\ \mathrm{1}{n}_t^k>S_D^k\end{array}\right.(3)

式中：n_t^k为在车站k所容纳的列车数量。

2.3　列车运行冲突评分确定

为了评估冲突严重程度，首先需要明确各列车的运行状态。列车的运行状态是多个运行指标的综合体现。在确定了用于表征列车运行状态的各项指标及其对应数值后，需要分析各指标对冲突严重程度的影响，并计算各指标的权重，最终将各指标值与相应权重进行整合，得出列车运行冲突评分。因此，列车运行冲突评分的确定是一个基于列车运行指标的评估问题，其具体步骤如下。①确定列车运行指标的含义以及评分范围。②利用熵权法确定各列车运行指标的权重。③计算出冲突所涉及列车的冲突评分。

列车运行冲突评分的目的在于确定冲突消解优先级，并据此对冲突列车进行运行调整。在列车运行调整中，遵循以下原则。①高等级列车优于低等级列车调整。②同等级列车晚点让正点，晚点程度小的列车优先运行。③区间列车运行与最小运行时间相差较小的列车优先调整。

车站时间间隔冲突示意图如图4所示，基于上述原则，结合图4阐述如何选择指标。

当列车i发生晚点后，若列车j按计划准时到达车站k，则可能与列车i发生冲突。是否构成车站时间间隔冲突需依据两列车在该车站的实际间隔时间与最小安全间隔时间之间的关系进行判断。具体而言，两列车的实际间隔时间可根据其计划间隔时间以及各自的晚点时间计算得出：前行列车的晚点越严重，实际间隔时间越短，从而冲突越严重；相反，在晚点情况已定的前提下，若两列车的计划间隔时间越大，则发生冲突的可能性越小，冲突的严重程度也越低。

因此，列车的晚点程度、计划间隔时间可作为反映列车运行状态的重要指标。此外，列车在区间运行过程中的冗余时间能够有效反映其运行速度状态，同样可以作为衡量运行状态的指标之一。综上，选取列车晚点程度、计划间隔时间与区间运行冗余时间3项指标来描述列车的运行状态，并参考文献^[20]中对于这3项指标评分方法，结合本实验所使用的数据进行相应修正与调整。

列车运行冲突评分指标及其相应定义如下。

（1）列车相对晚点。列车相对晚点表示两列车的晚点情况的相对关系，以P₁表示，其数值范围为

P_{\mathrm{1}}=\left\{\begin{array}{l}\mathrm{0}\mathrm{列车}i\mathrm{正点}，\mathrm{列车}j\mathrm{晚点}\\ \mathrm{1}\mathrm{列车}i\mathrm{晚点}，\mathrm{列车}j\mathrm{正点}\\ \mathrm{2}\mathrm{列车}i\mathrm{晚点}\mathrm{小于}\mathrm{列车}j\\ \mathrm{3}\mathrm{列车}i\mathrm{晚点}\mathrm{等于}\mathrm{列车}j\\ \mathrm{4}\mathrm{列车}i\mathrm{晚点}\mathrm{大于}\mathrm{列车}j\end{array}\right.(4)

（2）列车相对优先度。列车相对优先度表示冲突列车之间的计划间隔时间，列车之间的计划间隔时间与车站间隔时间冲突是否发生息息相关，因此采用列车i与列车j的图定间隔时间与最小间隔时间的差值S_i，j 作为依据，以P₂表示，其数值范围为

(5)

（3）列车运行相对冗余时间。列车从某站出发到下一站的图定运行时间与该区间的最小运行时间的差值，这个差值就是列车运行冗余时间；相对冗余时间即表示两列车的运行冗余时间的相对关系，以P₃表示，其数值范围为

P_{\mathrm{3}}=\left(\begin{array}{l}\mathrm{0}\mathrm{列车}i\mathrm{和列}\mathrm{车}j\mathrm{冗余}\mathrm{时间}\mathrm{相同}\\ \mathrm{1}\mathrm{列车}i\mathrm{冗余}\mathrm{时间}\mathrm{小于}\mathrm{列车}j\\ \mathrm{2}\mathrm{列车}i\mathrm{冗余}\mathrm{时间}\mathrm{大于}\mathrm{列车}j\end{array}\right.(6)

在确定各指标及其数值范围后，需要确定各指标在列车运行冲突评分构成中的权重，利用熵权法确定各指标的权重。熵权法的基本思想是：信息熵越大，说明该指标对评价结果的影响越小，权重越小；反之，熵越小，影响越大，权重越大。因此，采用熵权法首先需要确定各指标以及评价结果的信息熵，具体步骤如下。

①确定决策属性(A)：是否发生冲突的信息熵\mathrm{。}

E_{\mathrm{c}}(A)=-\left(\frac{m_{\mathrm{1}}}{m}\times \mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}{m}_{\mathrm{1}}+\frac{m_{\mathrm{2}}}{m}\times \mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}{m}_{\mathrm{2}}\right)(7)

式中：A为决策属性，是否发生冲突，发生冲突为1，没发生为0；m₁为A=1的数量；m₂为A=0的数量；m为m₁和m₂的总和。

②对各指标的信息熵进行计算。首先根据各指标的取值个数进行划分，然后在每个指标的各个取值点上计算对应的信息熵，其计算方法同决策属性的计算方法。在求出每个指标的每个分值处的信息熵后，需要以此整合出该指标的信息熵，以列车相对优先度为例，该指标存在0，1，2这3种情况，因此，该指标的信息熵为

E_{\mathrm{c}}(R)=E_{\mathrm{0}}\times p_{\mathrm{0}}+E_{\mathrm{1}}\times p_{\mathrm{1}}+E_{\mathrm{2}}\times p_{\mathrm{2}}(8)

式中：E₀，E₁，E₂为分值为0，1，2时的信息熵；p₀，p₁，p₂为分值为0，1，2的概率，不同分值的数量与总和的比值即表示其概率。

③通过决策属性和不同指标的信息熵，即可得出不同指标重要程度。

sig(R,A)=E_c(A)-E_c(R)(9)

④通过比对各指标的重要程度，并以比值的形式表示各指标的权重。列车运行冲突评分值为3项指标的加权和，通过比较该数值大小即可确定冲突的严重程度。

2.4　列车运行冲突消解模型

冲突消解时，可以采用越行和改变停站方案，调整列车运行到发时间等策略。在本模型中，考虑到旅客列车需要停站完成上下旅客的作业，不改变列车是否停站，但可在保证最小停站时间的基础上改变停站时间，通过调整列车在车站的到发时刻消解冲突。

根据列车运行冲突消解代价定义，将冲突评分作为冲突列车晚点的单位时间成本，则冲突列车的时间平移量与冲突列车的冲突评分的乘积为冲突列车的消解时间代价。

列车i与列车j发生冲突时，列车i与列车j在车站k的时间平移量(或称晚点时间)分别为ΔT_i，k 和ΔT_j，k，列车i与列车j的列车运行冲突评分为E_i，k 和E_j，k，则两列车的运行冲突消解代价可表示为

P_{i,k}=E_{i,k}^{}\times \mathrm{\Delta }{T}_{i,k}^{}(10)

P_{j,k}=E_{j,k}^{}\times \mathrm{\Delta }{T}_{j,k}^{}(11)

式中：ΔT_i，k 为列车i在车站k的总时间偏移量，列车j同理。包括到站时间晚点与出发晚点。

\mathrm{\Delta }{T}_{i,k}=\mathrm{\Delta }{T}_{i,k}^D+\mathrm{\Delta }{T}_{i,k}^C(12)

但式(12)未考虑冲突消解后产生的影响；拟考虑列车初始晚点情况以及采取策略后列车晚点变化情况，以此作为列车消解后的影响评估，将冲突列车的影响评估作为乘子分别乘以该列车的冲突消解时间代价，以此作为最终的冲突消解代价。

P_{i,k}=E_{i,k}^{}\times \mathrm{\Delta }{T}_{i,k}^C\times V_{i,k}(13)

其中，V_i，k 是采取策略进行消解时的影响评估，列车运行冲突的判定主要考虑了前一列车晚点与后一列车图定计划间隔时间之间的关系。因此，在影响评估时，应综合考虑前后两列车的总晚点变化情况，包括到达晚点和出发晚点。同时，还需评估采取策略后，列车晚点是否对运营造成过大影响。综合以上因素，评估时应使用两列车的晚点时间以及采取策略前后两列车的相对晚点变化情况，即

V_{i,k}=t_w^{i,j,k}+t_g^{i,j,k}+T_w^{i,j,k}+T_g^{i,j,k}(14)

式中：t_w^{i,j,k}为列车i与列车j在车站k的晚点时间之和；t_g^{i,j,k}为列车i与列车j在车站k的晚点时间之差的绝对值；T_w^{i,j,k}为列车i，j在车站k偏移后的两列车晚点时间之和；T_g^{i,j,k}为列车i，j在车站k偏移后的两列车晚点时间之差的绝对值。

冲突消解方案的冲突消解代价越小，冲突消解的效果越好，因此，冲突消解模型以冲突消解代价最小化为优化目标，考虑列车运行、车站等相关约束，实现列车运行冲突消解。

（1）目标函数。通过最小化冲突消解代价来确定消解方案，不仅能够解决冲突列车的2个主要问题，还能实现消解后的影响评估。本模型以冲突消解代价最小化为优化目标。

\mathrm{m}\mathrm{i}\mathrm{n}Z={\displaystyle \sum _{k=\mathrm{1}}^m}{\displaystyle \sum _{i=\mathrm{1}}^n}{P}_{i,k}(15)

式中：m,n分别代表车站总数量和列车总数量。

（2）约束条件。

①列车到达间隔时间约束。两同向列车到达同一车站时，其到达时间需要满足相应的到达间隔时间，即

T_D^{i,k}-T_D^{j,k}\ge T_{D,\mathrm{m}\mathrm{i}\mathrm{n}}^{i,j,k}\mathrm{o}\mathrm{r}{T}_D^{j,k}-T_D^{i,k}\ge T_{D,\mathrm{m}\mathrm{i}\mathrm{n}}^{i,j,k}(16)

式(16)表示同向运行的列车i与列车j到达车站k的时间间隔需满足最小到达间隔时间。

列车i与列车j的到达先后顺序需要进行判断，因此引入0-1变量X_k^{i,j}，其表示列车i与列车j在车站k的到达顺序，若列车i先到达，则其值为1，反之为0，以此将上述非线性约束转化为线性约束。

T_D^{i,k}-T_D^{j,k}\ge T_{D,\mathrm{m}\mathrm{i}\mathrm{n}}^{i,j,k}-X_k^{i,j}\times M(17)

T_D^{j,k}-T_D^{i,k}\ge T_{D,\mathrm{m}\mathrm{i}\mathrm{n}}^{i,j,k}-(\mathrm{1}-X_k^{i,j})\times M(18)

式中：M为充分大的正数。

②列车出发间隔时间约束。两同向列车从同一车站出发时，其出发时间需要满足相应的出发间隔时间，即

T_C^{i,k}-T_C^{j,k}\ge T_{C,\mathrm{m}\mathrm{i}\mathrm{n}}^{i,j,k}\mathrm{o}\mathrm{r}{T}_C^{j,k}-T_C^{i,k}\ge T_{C,\mathrm{m}\mathrm{i}\mathrm{n}}^{i,j,k}(19)

式(19)表示同向运行的列车i与列车j在车站k出发的时间间隔需满足最小出发间隔时间。

列车i与列车j的出发先后顺序需要进行判断，引入0-1变量Y_k^{i,j}，其表示列车i与列车j在车站k的出发顺序，若列车i先出发，则其值为1，反之为0，以此将上述非线性约束转化为线性约束。

T_C^{i,k}-T_C^{j,k}\ge T_{C,\mathrm{m}\mathrm{i}\mathrm{n}}^{i,j,k}-Y_k^{i,j}\times M(20)

T_C^{j,k}-T_C^{i,k}\ge T_{C,\mathrm{m}\mathrm{i}\mathrm{n}}^{i,j,k}-(\mathrm{1}-Y_k^{i,j})\times M(21)

③列车区间运行时间约束。列车在区间运行时需要考虑其在区间运行的最小运行时间，同时也需要考虑列车起停附加时分。

T_D^{i,k+\mathrm{1}}-T_C^{i,k}\ge T_{\mathrm{m}\mathrm{i}\mathrm{n}}^{k,k+\mathrm{1}}+T_Q^k\times {\theta }^{i,k}+T_T^{k+\mathrm{1}}\times {\theta }^{i,k+\mathrm{1}}(22)

式中：{\theta }_{}^{i,k}为0-1变量，若列车i在车站k通过，则为0，否则为1。

式(22)表示列车i从车站k出发到达车站k+1的时间间隔不应该小于该区间最小运行时间，如果列车i在车站k直接通过，则相应的起停附加时分取为0。

④列车停站时间约束。列车在车站停车时，需要给予必要的停车时间，供列车办理相应的旅客业务，即

T_C^{i,k}-T_D^{i,k}\ge {\theta }^{i,k}\times t_{\mathrm{m}\mathrm{i}\mathrm{n}}^{i,k}(23)

式(23)表示列车i在车站k的停留时间不得小于最小停站时间，如果列车i直接通过该车站，则最小停站时间为0。

⑤天窗时间约束。在规定的天窗时间里，列车不能运行，即

T_D^{i,k+\mathrm{1}}\le B_{tc}^{k,k+\mathrm{1}}(24)

T_C^{i,k+\mathrm{1}}\ge E_{tc}^{k,k+\mathrm{1}}(25)

式(24)—(25)表示列车不能在区间天窗时间内到达或者出发。

⑥逻辑约束。列车是否不停车通过车站的时间关系。

T_C^{i,k}-T_D^{i,k}\le {\theta }^{i,k}\cdot N(26)

\mathrm{\Delta }{T}_{i,k}^D\ge \mathrm{0}\bigcup \mathrm{\Delta }{T}_{i,k}^C\ge \mathrm{0}(27)

\mathrm{\Delta }{T}_{i,k}^D=T_D^{i,k}-t_D^{i,k}(28)

\mathrm{\Delta }{T}_{i,k}^C=T_C^{i,k}-t_C^{i,k}(29)

式中：N为一个充分大的正数。

式(27)表示列车i在车站k的晚点时间不得小于0，式(28)和(29)表示晚点时间与计划和实际到发时间的关系。

⑦到发线数冲突。同一时间内停留在车站的列车数不得大于该站可利用到发线数。

\sum M_D^{i,j,k}\le S_D^k(30)

M_D^{i,j,k}=\left\{\begin{array}{l}{\mathrm{1}}_{}{}_{}{}_{}{}_{}\mathrm{i}\mathrm{f}\left[T_D^{i,k},T_C^{i,k}\right]\bigcap \left[T_D^{j,k},T_C^{j,k}\right]\ne \mathrm{\varnothing }\\ {\mathrm{0}}_{}{}_{}{}_{}{}_{}\mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}\end{array}\right.(31)

3　求解算法设计

提出的冲突消解模型是具有多约束的单目标非线性混合整数规划模型，以m个车站n个列车为例，需确定的列车在各车站的到发时刻数量为2mn个，以各列车在各车站的到达晚点和出发晚点时间为变量，则该模型中总共有2mn个变量，其计算量较大，常规的求解方法包括遗传算法(Genetic Algorithm，GA)、邻域搜索算法(Large Neighborhood Search，LNS)、变邻域搜索算法(Variable Neighborhood Search，VNS)。

相较于GA算法，LNS算法在大规模解空间中具有更强的局部搜索能力、更高的灵活性、更快的收敛速度和更低的计算复杂度；与VNS算法相比，LNS的搜索能力更强，且其破坏和修复过程更具灵活性和扩展性，能更有效提升全局解质量，尤其在解空间较大时，LNS表现优于VNS。鉴于冲突消解的时效性要求，LNS算法相较于GA和VNS更为高效，适用于本问题的求解。

LNS算法通过破坏当前解的一部分，并通过修复操作使解重新可行，从而探索更优的解。算法包括2个步骤：首先，消解冲突以生成初始可行解；其次，在初始可行解的基础上，以冲突消解代价最小化为优化目标，进一步生成更优解。

根据冲突产生的时间顺序逐步消解得到初始可行解，因此设置了区域间隔冲突节点、到发间隔冲突节点、停站间隔冲突节点，对冲突节点进行破坏，并在破坏后在给定范围内随机生成初始可行解。

在得到初始可行解后，基于LNS算法设置破坏算子和修复算子进行优化求解。

（1）破坏算子。①冲突评分算子：以列车运行冲突评分为基础构建模型，评分越高在破坏时优先级就越高，因此设置该破坏算子，选择冲突评分较高的列车到达晚点和出发晚点变量进行破坏。②消解代价算子：在每一轮破坏时优先选择消解代价最高的列车进行破坏。③随机破坏：为防止在破坏时过早陷入局部最优，通过随机选取进行破坏。

（2）修复算子。基于多项技术要求，设置基于最小到发间隔时间、最小停站时间、最小区间运行时间的修复算子，并在修复时取最大值以保证修复后解依然满足约束。

算法路线如图5所示。

4　案例分析

4.1　列车运行冲突评分

经过对列车运行数据进行预处理(包括去重、剔除错误数据等操作)，得到完整的列车运行数据。基于冲突判定条件，提取了存在冲突的记录，并根据评分规则对以往的列车运行数据进行了评分。最终，从381 076条列车运行数据中，共发现了58 861次冲突。

各指标的信息熵如表2所示。

各指标的重要程度为

\begin{array}{l}sig(P_{\mathrm{1}},A)=E_c(A)-E_c(P_{\mathrm{1}})=\mathrm{0.312}\mathrm{4}\\ sig(P_{\mathrm{2}},A)=E_c(A)-E_c(P_{\mathrm{2}})=\mathrm{0.516}\mathrm{2}\\ sig(P_{\mathrm{3}},A)=E_c(A)-E_c(P_{\mathrm{3}})=\mathrm{0.321}\mathrm{7}\end{array}

各指标的重要程度按顺序排序：P₂>P₃>P₁；对冲突程度影响最大的是列车间的计划间隔时间，其次是运行冗余与晚点情况，在消解时应着重考虑计划间隔时间较小的列车间产生的冲突。

依据指标的重要程度，得出各指标权重如图6所示。

列车运行冲突评分为

P=P_{\mathrm{1}}{R}_{P_{\mathrm{1}}}+P_{\mathrm{2}}{R}_{P_{\mathrm{2}}}+P_{\mathrm{3}}{R}_{P_{\mathrm{3}}}(31)

式中：R_{P_{\mathrm{1}}}，R_{P_{\mathrm{2}}}，R_{P_{\mathrm{3}}}为各指标权重。

4.2　案例描述及参数设置

本案例使用2017—2018年武广高速铁路(武汉—广州南)的真实线路数据和时刻表数据。为了方便描述，将车站与列车分别用数字编号，共11个车站及29列车。此外，研究中设计了2种不同程度的晚点情况，用于进行冲突消解的研究。车站数：M=1，2，…，11。列车数：N=1，2，…，29。29列车在11个车站的计划运行图如图7所示。

各车站之间的区间最小运行时间如表3所示。

各车站到发线数量如表4所示。

起停附加时分，最小停站时间，天窗开始、结束时间相关时间技术要求如表5所示。

由于天窗开设时间为0~21 600 s，因此案例中不涉及列车运行与天窗时间约束冲突的问题。

4.3　实验设置

案例中设置600 s晚点造成的冲突及1 800 s晚点造成的冲突2种情景，2种情景下冲突数量不同，通过设置的算法消解冲突并使冲突消解代价尽可能最小。

情景1：列车1在车站5晚点到达600 s。列车1在车站5晚点到达600 s，并且在后续车站继续维持晚点600 s到达与出发。由于列车1的晚点，列车2在后续车站均发生冲突，列车3仅在车站10和车站11发生冲突，情景1冲突运行图如图8所示。

情景2：列车1在车站5晚点1 800 s到达。列车1在车站5发生较大程度晚点，并且在后续区间运行中保持计划速度不变，在后续车站晚点1 800 s。由于列车1的晚点，列车2、列车3、列车4、列车5均发生冲突，情景2冲突运行图如图9所示。

4.4　列车运行冲突消解结果分析

2种情景下的调整运行图如图10所示，情景1中冲突消解后得到的调整运行图如图10a所示，情景2中冲突消解后得到的调整运行图如图10b所示。

在情景1中，列车1发生较短时间的晚点，导致列车2在多个后续车站与其发生冲突，列车3仅在车站10和车站11存在冲突。通过调整列车2和列车3在相应车站的到达与出发时刻，能够有效消解冲突，且对其他列车的运行秩序未造成影响。情景1列车晚点如表6所示。

在情景2中，列车1出现较大幅度的晚点，冲突涉及列车2—5，且影响逐步传导至后续列车，导致列车6—9也需调整运行时刻。最终，各列车在多个车站均出现不同程度的晚点，情景2列车晚点如表7所示。

为验证所提出基于冲突消解代价最小化的优化模型的有效性，与传统以列车总晚点时间最小化为目标的模型进行了对比分析。比较维度包括总消解代价、列车总晚点时间、晚点时间方差以及晚点频次，不同优化目标指标对比如表8所示。

从结果来看，虽然模型的总晚点时间比传统模型多出840 s，但总消解代价降低了5.69%，说明通过适度增加某些列车的晚点，可以显著降低整体冲突消解成本。同时，模型的晚点时间方差降低了8.32%，表明各列车的晚点分布更加均衡、波动更小，有助于提升列车运行的稳定性。此外，在晚点频次方面(定义为晚点超过4 min的列车数量)，模型共发生46次，较传统方法的55次减少了9次，显示出其在更广范围内有效降低了晚点事件的发生频率。这些优势主要得益于模型在冲突消解过程中引入了冲突评分机制，能够根据冲突严重程度合理分配各列车的晚点幅度。特别是针对评分较高的关键冲突列车(如列车2与列车5)，该方法显著降低了它们的总晚点时间，较传统模型减少了3 784 s，从而在保障整体运行效率的同时，有效控制了冲突消解代价。

综上所述，提出的基于冲突消解代价优化的列车运行冲突消解模型，在降低总消解代价、平衡列车晚点分布、减少晚点频次等方面均表现出显著优势，具有良好的工程应用价值与推广前景。

4.5　冲突消解算法评估

情景1与情景2采用不同算法下的收敛曲线如图11所示。图11a为情景1算法收敛曲线，图11b为情景2算法收敛曲线，不同算法求解结果如表9所示。

在情景1与情景2中，均采用3种算法进行求解并进行对比。每种算法都设置收敛条件，因此各算法的最大迭代次数不同。

情景1中，LNS与VNS算法的最终目标函数值明显优于GA算法；此外，LNS算法求解所用时间是3种算法中最短的，最终结果相较于VNS算法提升8.9%，显示出LNS算法的明显优势。因此，在该情景中，LNS算法的求解结果是最优的。

情景2中，LNS与VNS算法的最终目标函数值也明显优于GA算法。LNS算法与VNS算法的结果相差仅为1.7%，但LNS算法的求解时间远低于VNS算法。从图11b的收敛曲线可以看出，LNS算法在该情景下收敛速度更快，且最终得到的目标函数值更优。因此，在该情景中，LNS算法的求解结果是最优的。

5　结束语

针对高速铁路列车运行冲突问题，基于列车运行数据提出了冲突判定条件及评分准则，并进一步运用历史数据确定各评分指标的重要程度的权重。在此基础上，构建了以最小化冲突消解代价为优化目标的冲突消解数学模型，与传统的以总延误时间最小为优化目标的模型相比，在降低总消解代价、减小晚点方差和减少晚点频次方面均表现出优越性。同时设计了一种基于大邻域搜索算法的求解方法。研究结果表明，该方法在应对小规模及大规模列车冲突时，能够在5 min内有效生成质量较高的冲突消解方案，显著降低列车运行冲突的消解代价，直至算法收敛，相较于GA和VNS算法，求解结果和求解时间都有明显提高。在未来的实际应用中，可在本研究基础上进一步拓展，引入更为细致的冲突消解策略选择机制。具体而言，可在冲突评分的基础上，结合不同类型冲突的特性，选取最匹配的冲突消解策略，从而提升解的合理性与实际可操作性。同时，可在现有模型基础上引入双目标优化框架，不仅最小化冲突消解代价，同时兼顾列车运行效率与公平性，通过模型线性化等手段提升求解效率与适用范围。此外，针对铁路现场调度指挥工作，本模型可支撑实现“冲突识别—评分评估—策略选择—方案生成”一体化操作，快速响应列车运行中出现的各类冲突情形，显著减轻调度员负担，提升铁路系统的智能化水平与运行可靠性。

参考文献

[1] 文　超，彭其渊，陈芋宏. 高速铁路单个列车运行冲突消解研究[J]. 科学技术与工程，2013，13(10)：2741-2747.

[2] 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.

[3] 文　超，彭其渊，陈芋宏. 高速铁路列车运行冲突判定及其实现[J]. 西南交通大学学报，2012，47(5)：867-873.

[4] WEN Chao， PENG Qiyuan， CHEN Yuhong. Judgment of Train Operation Conflict and Its Implementation for High Speed Railway[J]. Journal of Southwest Jiaotong University，2012，47(5)：867-873.

[5] 郭竞文，孟令云，冉　锋，等. 列车间不确定性资源请求冲突的预测方法[J]. 铁道运输与经济，2014，36(7)：34-39.

[6] GUO Jingwen， MENG Lingyun， RAN Feng，et al. Forecast Method of Uncertainty Resource Requiring Conflict between Trains[J]. Railway Transport and Economy，2014，36(7)：34-39.

[7] 黄　悦，潘晓军，李民进，等. 基于轨道区段锁闭时间的城轨列车运行图冲突检测研究[J]. 铁道运输与经济，2018，40(12)：104-111.

[8] HUANG Yue， PAN Xiaojun， LI Minjin，et al. A Timetable Conflict Detection Based on Blocking-Time Theory for Urban Rail Transit Systems[J]. Railway Transport and Economy，2018，40(12)：104-111.

[9] 林　枫，郭一唯，杨　晓，等. 基于高速铁路车站分类的到发线运用冲突识别方法研究[J]. 铁道运输与经济，2024，46(12)：137-144.

[10] LIN Feng， GUO Yiwei， YANG Xiao，et al. Conflict Identification Method for Arrival-Departure Tracks Based on High Speed Railway Station Classification[J]. Railway Transport and Economy，2024，46(12)：137-144.

[11] 洪　鑫，孔庆玮，陈亚茹，等. 列车运行计划冲突判定与检测方法研究[J]. 交通运输工程与信息学报，2023，21(3)：145-160.

[12] HONG Xin， KONG Qingwei， CHEN Yaru，et al. Conflict Judgement and Detection Method for Train Operation Plans[J]. Journal of Transportation Engineering and Information，2023，21(3)：145-160.

[13] 冯丽萍，张立东，高　佳. 基于模糊时间知识推理的到发线运用冲突预测[J]. 铁道运输与经济，2022，44(4)：91-98.

[14] FENG Liping， ZHANG Lidong， GAO Jia. Arrival-Departure Track Conflict Prediction Based on Fuzzy Temporal Knowledge Reasoning[J]. Railway Transport and Economy，2022，44(4)：91-98.

[15] 郭竞文. 考虑冲突不确定性的高速铁路列车运行调整优化模型[D]. 北京：北京交通大学，2016.

[16] 张　俊，叶玉玲. 基于全局冲突解析的高速铁路时刻表调整模型[J]. 铁道学报，2023，45(2)：1-12.

[17] ZHANG Jun， YE Yuling. Timetable Rescheduling Model of High Speed Railway Based on Global Conflict Resolution[J]. Journal of the China Railway Society，2023，45(2)：1-12.

[18] DOMINO K， KONIORCZYK M， KRAWIEC K，et al. Quantum Annealing in the NISQ Era：Railway Conflict Management[J]. Entropy，2023，25(2)：191.

[19] MELONI C， PRANZO M， SAMÀ M. Risk of Delay Evaluation in Real-Time Train Scheduling with Uncertain Dwell Times[J]. Transportation Research Part E：Logistics and Transportation Review，2021，152：102366.

[20] CORMAN F， D’ARIANO A， PACCIARELLI D，et al. Bi-Objective Conflict Detection and Resolution in Railway Traffic Management[J]. Transportation Research Part C：Emerging Technologies，2012，20(1)：79-94.

[21] ZHAO X N， ZHANG Y. Research on Railway Traffic Conflict Management Method in Onboard-Centered Train Control System[J]. IOP Conference Series：Earth and Environmental Science，2020，587(1)：012020.

[22] DÜNDAR S， ŞAHIN İ. Train Re-Scheduling with Genetic Algorithms and Artificial Neural Networks for Single-Track Railways[J]. Transportation Research Part C：Emerging Technologies，2013，27：1-15.

[23] SAMÀ M， PELLEGRINI P， D’ARIANO A，et al. Ant Colony Optimization for the Real-Time Train Routing Selection Problem[J]. Transportation Research Part B：Methodological，2016，85：89-108.

[24] SAMÀ M， PELLEGRINI P， D’ARIANO A，et al. On the Tactical and Operational Train Routing Selection Problem[J]. Transportation Research Part C：Emerging Technologies，2017，76：1-15.

[25] BETTINELLI A， SANTINI A， VIGO D. A Real-Time Conflict Solution Algorithm for the Train Rescheduling Problem[J]. Transportation Research Part B：Methodological，2017，106：237-265.

[26] BINDER S， MAKNOON Y， BIERLAIRE M. The Multi-Objective Railway Timetable Rescheduling Problem[J]. Transportation Research Part C：Emerging Technologies，2017，78：78-94.

[27] WANG Z H， ZHOU Y H， LIU D. Models and Algorithms of Conflict Detection and Scheduling Optimization for High Speed Train Operations Based on MPC[J]. Journal of Control Science and Engineering，2018，2018：3473175.

[28] 王明慧. 粗糙集理论在铁路行车调度指挥系统中应用的研究[J]. 中国铁道科学，2004，25(4)：103-107.

[29] WANG Minghui. Study on the Application of Rough Set in Railway Dispatching System[J]. China Railway Science，2004，25(4)：103-107.

基金资助

国家重点研发计划项目(2022YFB4300502)

国家自然科学基金项目(72301221)