离散萤火虫算法在高速列车运行调整中的应用

段少楠，戴胜华

北京交通大学 电子信息工程学院，北京 100044

1 引言

列车运行调整是铁路行车指挥工作的基础和核心[1]。列车在运行过程中，不可避免地受到各种因素的影响使列车运行偏离计划线，扰乱行车秩序，影响行车效率。我国高速铁路采用“高中速混跑”运营模式，列车采取分级调整策略[2]，并且高速铁路列车运行速度快、行车密度大，对运行调整的实时性和动态性提出了更高的要求，因此，需要采用科学的优化方法对列车运行图进行调整。

列车运行调整是一类NP完全问题，目前求解这类问题的主要方法是最优化方法和智能计算方法[3]。线性规划、非线性规划、混合整数规划、分枝定界法、拉格朗日松弛法等最优化方法都已在求解过程中得到应用[4]。但采用最优化算法解决列车运行调整问题必须对复杂模型进行简化，因此计算结果与实际有较大偏差，且计算量极为庞大。解决这一问题常用的智能计算方法有遗传算法、粒子群算法和普通启发式算法等。遗传算法虽然适用性强，计算效果较好，但是编码相对复杂，运算过程繁琐且寻优耗时多，求解速度慢。由于列车运行调整约束众多，搜索空间庞大，可行解范围狭小，粒子群算法搜索缓慢易陷入死循环，难以得到最优解[3]。普通的启发式算法虽然计算量较小，但对全局最优解的搜索能力不强，易陷入局部最优解。

萤火虫算法是模拟自然界中萤火虫的发光特性而发展起来的一种新型智能优化算法，具有较高的寻优精度和收敛速度，是一种可行有效的优化方法，为智能优化提供了新思路[5]。本文针对运行图调整问题的特点，将标准萤火虫算法进行离散化处理，通过调整列车在给定站的发车次序来对列车运行进行调整。经过计算对比，该算法可以准确、快速地得到目标函数最优解。

2 模型建立

本次研究选择双线自动闭塞高速铁路单一方向线路为研究目标。为了反映列车在区间和车站内晚点情况以及在程序设计中易于处理相关约束条件，将列车运行图的计划线用到达和出发两条线表示，并且以时间轴的形式给出，以分钟为单位，到达线和出发线可以分成1 440个点[6]。如图1所示。

2.1 变量定义

针对某一调度区段，对于列车调整模型给出如下定义：

（1）列车总列数为L。

（2）车站总数为N，则区间总数为K=N-1。

（3）Ai,k、Si,k分别为第 i(i∈{1 ,2,…,L})列车在第k(k∈{1 ,2,…,N})个车站的到达、出发时刻，则相应的定义、为原定计划时刻。

（5）列车等级优先级为 μ(i),i∈{1 ,2,…,L} ，其值越大表明列车等级越高，优先级越高，反之则优先级越低。不同等级列车对应的列车运行调整权重为w(i),i∈{1 ,2,…,L}，不同等级列车在车站的作业时间为t(i),i∈{1 ,2,…,L}。不同等级的列车在车站k与车站k+1之间的最小运行时间用表示，不同等级列车在车站k的最小作业时间用εi,k表示。

（7）定义布尔变量ψi,k表明列车通过车站的作业类型。

2.2 目标函数

对调整策略的优劣进行评价有多种标准，这是由于列车晚点情况是有差异的，运行调整策略也需要做出相应的变动[7]。本文选择按站调整的方式，以每个车站的列车发车顺序为变化量，选择列车在调整站点的下一站加权到达晚点时间最小为目标函数。

2.3 约束条件

为保障行车安全及运输效率，列车运行调整的范围要受到车站最小作业时间、最小区间运行时间、列车到达间隔、列车出发间隔等约束[8]，具体描述如下所示：

（1）越行条件：只有满足以下条件，列车 j才可以越行列车i（其中i为前车，j为后车）：

（2）列车在两站之间的运行时间，需满足列车在区间的最小运行时分，且考虑列车的起、停附加时间：

（3）若列车在车站停车，作业时间不得小于规定的在该车站的最小作业时间：

（4）所有列车发车时间不得早于固定的发车时间；

（5）在同一个车站，前后两列车的到达、出发时间间隔要满足最小到达、出发时间间隔的约束[3]。

3 离散萤火虫优化算法

3.1 标准萤火虫算法

2008年，Yang通过对萤火虫个体相互吸引和移动过程的研究，提出了一种新型群体智能优化算法，即萤火虫算法（Firefly Algorithm，FA）[9]。

萤火虫算法将搜索空间中的点模拟成自然界的萤火虫个体，将搜索和优化的过程模拟成萤火虫个体之间的吸引和移动过程，用求解问题的目标函数值来表示萤火虫当前位置的优劣，将个体的优胜劣汰过程类比为搜索和优化过程中用较好可行解取代较差可行解的迭代过程。算法涉及两个关键因素：萤火虫的发光亮度和相互吸引度。萤火虫发光亮度取决于自身所在位置的目标值，发光亮的萤火虫会吸引发光弱的萤火虫向它移动，最终大多数萤火虫会聚集在最亮的萤火虫附近。发光越亮的萤火虫对周围萤火虫的吸引度越高，若发光亮度一样，则萤火虫做随机运动。吸引度与距离成反比，即距离越大吸引度越小[10]。

算法描述如下：

首先建立萤火虫i的绝对亮度Ii和目标函数值之间的关系，一般直接用目标函数值来代表萤火虫的绝对亮度，即：

假设萤火虫i绝对亮度大于萤火虫 j，则萤火虫 j被萤火虫i吸引而向萤火虫i移动。萤火虫i对萤火虫j的吸引力βi,j为：

其中，β0为最大吸引力，通常为1；γ为光吸收系数，γ∈[0 . 01,100]；ri,j为萤火虫i到萤火虫 j的笛卡尔距离，即：

其中d为变量的维数。

由于萤火虫 j被萤火虫i吸引而向萤火虫i移动，则萤火虫 j的位置更新公式为：

其中t为迭代次数；Xi、Xj为萤火虫i和 j所处的空间位置；α为步长因子，是[0 , 1]上的常数；εj是均匀分布的随机数向量，用于加大搜索区域，避免过早陷入局部最优[11]。

3.2 算法离散化

标准萤火虫算法采用笛卡尔距离，适用于连续空间中的寻优，本文通过优化列车发车顺序来得到目标函数最优解，属于组合优化问题，因此需要对算法进行离散化处理，主要从距离计算、移动方式和扰动机制三方面进行改动。

对于每一个需要优化的站点，用总加权到站晚点时间的倒数作为萤火虫的绝对亮度，每个萤火虫表示本站所有列车的一种可能的发车顺序，如Xi=[1 , 2,3,4,5]。在离散萤火虫算法中，使用汉明距离来度量两个萤火虫序列之间的距离，即序列中相同位置元素不同的个数。例如Xi=[1 , 2,3,4,5]，Xj=[1 , 2,4,3,5]，其汉明距离为2。对于两个相互吸引的萤火虫个体，在进行移动时需要先将其相同位置元素相同的值对应保存下来，对两者元素不相同的位置，每次生成一个[0,1]区间内的随机数r，如果r＜β，则该位置取亮度高的萤火虫的元素，否则取亮度低的萤火虫的元素，其中β为萤火虫之间的吸引力。如果所选取元素和前面已选元素重复，则先将该位置留空，直到序列全部选择完毕，再将剩余未选择元素，依次分配给这些留空的位置[12]。

3.3 变邻域扰动机制

为了避免萤火虫算法陷入局部最优，需要在萤火虫移动之后加入扰动量。本文参考萤火虫算法在TSP问题中的应用，在搜索过程中采用变邻域的扰动机制，系统地改变萤火虫的邻域，从而拓展搜索范围[13]。

根据运行图调整的求解特点，文中应用了两种邻域结构：

（1）Insert邻域，在解序列中随机选取不同车次的列车x和y，其中x＜y，把列车x的发车次序插入列车y的发车次序之后，得到新的次序排列。例如Xi=[1,2,3,4,5]，随机得到x=2，y=4，则调整之后Xi=[1,3,4,2,5]。

（2）Swap邻域，在解序列中随机选择不同车次的列车x和y，互换这两次列车的发车次序。例如Xi=[1,2,3,4,5]，随机得到x=2，y=4，则调整之后Xi=[1,4,3,2,5]。

3.4 算法流程

应用离散萤火虫算法求解运行图调整问题的基本步骤如下：

步骤1按站进行查询，对比实际到站时间和计划到站时间，得到首次晚点车站k和首次晚点列车序号i。

步骤2针对该存在晚点情况的车站，初始化算法基本参数，包括萤火虫数目m、光强吸收系数γ、最大迭代次数Tmax。随机初始化每只萤火虫的初始解序列，即保持正点列车发车顺序不变，对首次晚点列车及其后所有列车的发车顺序进行随机设置。

步骤3按照约束条件（1）对每只萤火虫对应的发车次序进行重新调整，然后按照调整后的发车顺序和约束条件（3）、（4）、（5）计算所有列车在该车站的实际发车时间 Si,k,i∈{1,2,…,L}。

步骤4根据列车在车站k的实际发车时间Si,k和计划发车时间确定晚点列车，在车站k和k+1之间的区间，晚点列车按照最小区间运行时分运行，其余列车正常运行，最后按照约束条件（2）、（5）计算得到所有列车在k+1站的实际到站时间Ai,k+1,i∈{1,2,…,L}。

步骤5 根据w(i),i∈{1,2,…,L}、Ai,k+1,i∈{1,2,…,L}计算调整后的每个发车顺序对应的函数值，并按照吸引和移动原则进行移动。

步骤6对移动后的萤火虫进行变邻域搜索，选择两种邻域中的一种进行随机扰动，重复执行n次，选择目标函数值最优的位置作为萤火虫的当前位置。

步骤7对更新后的所有萤火虫的目标函数值进行排序，并与当前最优解进行比较，如果更优则更新最优解。

步骤8如果最优解满足结束条件，则跳出循环，输出本站的调整结果，对下一站点进行调整，否则跳到步骤5继续搜索。

步骤9如果调整执行到最后一个车站或者最优解为0则调整结束，否则对下一个车站继续步骤2。

4 算例分析

4.1 数据整理

为了验证离散萤火虫算法的先进性，本文选取文献[14]提供的算例，利用本文所提出的算法对文献[14]中的算例进行重新计算，将得到的结果与文献[14]提出的启发式算法进行对比。

文献[14]算例中计划运行时刻表如表1所示。针对晚点情况设定了3个参数：首次晚点发生的区间m，该区间初始晚点的列车n以及列车晚点时间s。这里的晚点时间表示的是列车在区间运行过程中的实际运行时分比计划运行时分多出的部分。本次算例，设置m=3，n=6，s=25。采用文献[14]中提到的启发式算法得到的晚点发生后的列车运行时刻表如表2所示。

该算例的已知条件如下：

有4种等级的14辆列车，对应的等级矩阵为μ(i)=[2，2，2，3，3，4，4，4，4，4，1，1，1，1]。14辆车对应权重为w(i)=[0.3，0.3，0.3，0.2，0.2，0.1，0.1，0.1，0.1，0.1，0.4，0.4，0.4，0.4]。为了便于计算，设第一个站的第一列车发车时间为0，后续时间以“min”为单位。例如，按照计划运行图，列车在5号站点计划与实际到站时间分别为：=[109，115，121，156，162，204，210，216，222，228，261，267，273，279]，Ai,5=[109，115，121，156，162，221，227，233，239，245，261，267，273，279]。各车站最小出发时间间隔=6 min；各车站最小到达时间间隔=6 min；4种等级的列车在5个区间的最小运行时间矩阵以及在6个站的最小作业时间矩阵分别为：

4.2 算例设计

列车运行图调整有按站调整和按车调整两种方式，本文以及文献[14]均是采用按站调整的方法，即重新设置经过某个车站的所有列车的到达时刻与出发时刻，通过区间的调整冗余度来降低晚点列车所受到的影响[15]。

对于每一个车站，如果所有列车进站时间及站内作业时间已知，一旦确定各个列车的发车顺序，即可知道每列车的发车时间。将发车时间和计划发车时间进行比较之后得到晚点列车车次，然后晚点的列车通过在区间的快速运行来减少或者消除晚点，最终使运行图恢复计划状态。

本次研究的目标函数是调整站点的下一站加权到达晚点时间最小。本次算例选取6个站中的某一个站，例如利用第5站的到站时间计算第5站的发车顺序然后得到第5站的发车时间和第6站的到达时间。其他站的情况类似，在文章中不再赘述。

表1 计划时刻表

表2 启发式算法调整结果

表3 启发式算法和萤火虫算法在第五站的计算结果

4.3 计算结果对比

4.3.1 启发式算法

通过表1和表2对比可得，在第5站共有5辆列车发生晚点，需要在该站点对发车顺序进行调整使得在6号站点总加权晚点时间最小。按照文献[14]中提出的启发式算法的计算结果如表3所示。

根据第5站计划发车次序和实际发车次序，可以看到为了降低晚点时间，高优先级的11、12、13、14号列车对低优先级的8、9、10号列车进行了站内越行。目标函数为6号站点的加权到达晚点时间，由实际到达时间和计划到达时间计算得到。

4.3.2 离散萤火虫算法

由于高等级的列车可以站内越行低等级的列车，因此在5号站点对列车的发车次序进行改变可以得到不同的目标函数值。利用离散萤火虫算法对解空间进行搜索可以得到最优的发车顺序。

算法参数设置：萤火虫数目m=30，最大迭代次数Tmax=20，最大吸引力β0=1，光强吸收系数γ=1，变邻域搜索中两种邻域选用概率相同，均为0.5，变邻域搜索执行次数n=4，得到计算结果如表3所示。

4.3.3 结果分析

通过表3的对比，可以看到使用离散萤火虫算法计算之后，高等级的11、12、13、14号列车只对9、10号列车进行了站内越行，而没有对晚点20 min的8号低等级列车进行越行。该算法计算得到的目标函数值优于普通启发式算法，准确找到的问题的最优解。为了验证算法的稳定性，作者还对该算例使用离散萤火虫算法进行多次计算，结果表明计算结果均可以在较少的迭代次数内达到收敛，得到该问题的最优解。

5 结束语

本文针对列车运行调整这类特殊的NP完全问题，建立对应的数学模型，通过对标准萤火虫算法进行改进，提出一种离散的萤火虫算法（DFA）对列车运行调整模型进行求解。采用Matlab编程，通过对比普通启发式算法和离散萤火虫算法的目标函数值，发现离散萤火虫算法收敛速度快、目标函数的最优解精度高，从而证明了该算法对解决列车运行调整问题具有一定优势。