蚁群算法在城轨列车运行调整中的应用

王婧婧

(西南交通大学 信息科学与技术学院，成都 611756)

蚁群算法在城轨列车运行调整中的应用

王婧婧

(西南交通大学 信息科学与技术学院，成都 611756)

当城市轨道交通列车在行车过程中由于设备故障、乘客拥挤等情况发生晚点时，需要对列车时刻表进行调整，使之尽快恢复正点运行。本文以调整区段内总晚点时间最小为目标函数，提出了基于蚁群优化算法的列车调整模型，在Visual C++ 6.0编程环境下，以深圳地铁6号线为例，对模型的实用性进行了验证。

列车运行调整；蚁群算法；模型

城市轨道交通由于列车追踪间隔短、人流量大等因素，列车发生晚点情况无法避免。如果晚点列车没有及时调整，前行列车的出站晚点很有可能会造成后行列车的紧随晚点，从而导致局部列车运行秩序紊乱，无法保障区间运行效率。为了保障行车安全和提高运行效率，需要对晚点列车进行实时调整，以便尽快恢复正常运行秩序，保证列车可以按计划运行。

自从1973年B.Szpigel提出“最优列车调度”问题以来，开始了列车运行调整问题的研究[1]。许多专家学者将运筹学、专家系统、模糊决策、遗传算法、模糊神经网络等方法先后用于列车运行调整研究，并取得了相当有价值的研究成果[2～6]。这些调整方法与策略推动了该问题的研究进展，但仍存在一些问题。比如基于运筹学优化理论的调整算法实时性较差，常规解法很难求得全局最优解；基于专家系统的列车调整策略和算法只追求满意和有效，在一定程度上达不到目标函数最优；基于模糊决策的调整方法对于优先级的定义需要凭经验确定模型参数；遗传算法在搜索大规模组合优化问题解空间方面存在过早收敛以及参数优化等问题。

鉴于上述原因，本文建立了列车调整模型，并采用蚁群算法进行求解。由于蚁群算法是一种基于种群寻优的启发式搜索算法，通过蚂蚁个体间释放的信息素的堆积来寻找最短路径，具有自组织性、正反馈、分布式计算等特点[7]，符合列车运行调整模型对求解算法的要求，因此本文采用蚁群算法对时刻表数据进行寻优，并取得了较好的效果。

1 列车运行调整模型

1.1 城市轨道交通列车运行特点

城市轨道交通运营范围一般为几十千米，往返时间一般在2 h左右；站间距离较短，列车追踪间隔短，采用CBTC系统的线路安全行车间隔理论上可以达到90 s；客流量较大，在早晚高峰或者节假日期间尤其明显；运行速度一般最高为80 km/h，有些线路可以达到100 km/h甚至是120 km/h。列车运行图是运用坐标原理对列车运行时间和空间关系的图解表示，进行列车运行调整实际上是调整各车在各站的到发时刻从而解决列车与列车在车站和区间因晚点而发生的冲突关系，因此需要考虑最小区间运行时间、最小站停时间、最小追踪间隔等约束条件。

1.2 模型的构建

设某条运行线调整区段有M个车站，编号为{0，1，……，i，……，M-1}；N列同是上行或下行方向的列车，编号为{0，1，……，k，……，N-1}；调整区段内所有列车均为同一速度等级，不存在越行情况。

定义：变量XDi,k—列车k在车站i的实际到达时刻；—列车k在车站i的计划到达时刻；XFi,k—列车k在车站i的实际出发时刻；—列车k在车站i的计划出发时刻；Tsi—列车在车站i的最小停站时间；Tri—列车在相邻车站i与i+1之间运行的最小区间运行时间；Td—两追踪列车的最小追踪间隔。

1.2.1 目标函数

本文以调整后运行图与计划运行图相比，总到发晚点时间最小为目标函数，式为：

1.2.2 约束条件

列车运行调整受到区间运行时间、停站时间、相邻列车追踪间隔以及出发时间的约束，这些约束条件具体如下：

（1）最小停站时间约束。列车在车站的停站时间由开门时间、乘客上下客时间和关门时间3部分组成。其中，乘客上下客时间根据各设计年度车站的高峰小时预测客流量计算确定。列车在车站i的停站时间约束，式为：

（2）最小区间运行时间约束。任意列车k在相邻两个车站i，i+1的运行时间受到其最小区间运行时间约束，式为：

（3）列车追踪间隔约束。为保障同向列车的安全运行，两辆追踪列车需要满足追踪间隔约束，式为：

（4）出发时间约束。为保证列车按图行驶，实际列车出发时间不能小于列车计划出发时间，即列车不能提前发车，出发时间约束，式为：

2 列车运行调整算法

2.1 蚁群算法概述

1991年，M.Dorigo等人首次提出了蚁群优化算法。蚂蚁在觅食时，总能找到蚁穴与食物源之间的最短路径。研究表明，蚂蚁之间是通过一种遗留在其来往路径上的分泌物来进行通信和协调的，蚂蚁产生的分泌物称为信息素，是一种挥发性化学物质。路径上的信息素越多，蚂蚁选择该路径的可能性越大，形成了正反馈现象，使得蚁群逐渐聚集到最短的那条路径上来。

蚁群算法是通过模拟真实蚁群在觅食路径上释放信息素最终可以在蚁穴和食物源之间找到最短路径这一特征工作的。算法可以通过蚂蚁寻找食物时候的信息素原理，不断去修正原来的路线，使整个路线越来越短，即随着迭代次数的增加，所获得的路径就越接近最优路径。

2.2 蚁群优化算法的设计

本文在Visual C++ 6.0平台下编程，实现了蚁群算法用于模型的求解，算法流程图如图1所示，算法步骤为：

（1）初始化，设置蚁群算法参数；（2）输入调整区段内编号k=0的列车到达车站i=0的晚点时间，单位为秒；（3）在满足约束条件的前提下，每只蚂蚁并行地构建搜索计划时刻表上的时间点所对应的调整后时刻表的时间点的路径，搜索完所有时间点后计算目标函数值，即总晚点时间，检查每只蚂蚁的目标函数值，若目标函数值为负数，则进行调整；（4）更新信息素，比较每只蚂蚁所求得的目标函数值，得到其中最小值，作为此次迭代的最优解； （5）判断此次迭代是否结束，若结束则进行下一次迭代，否则转至步骤（3）；（6）比较每次迭代的最优解，得到其中最小值，作为算法得到的最终解，即时刻表调整后的总晚点时间；（7）判断算法是否结束，若是则输出最优结果，否则转至步骤（3）。

图1 算法流程图

3 仿真实例

本文以深圳地铁6号线为例进行分析，调整区段为从深圳北站到上屋北站一共是7个站。已知列车追踪间隔Td=240 s，停站时间和最小区间运行时间如表1所示。

表1 调整区段内最小停站时间和区间运行时间

程序中定义时刻表数据结构如下：

将计划时刻表数据按照定义的数据结构形式保存在本地，通过文件读取，并将时刻数据转换成以秒为单位的整型数据，当输入首列车晚点时间时，蚁群调整算法搜索晚点后时刻表，并计算目标函数值，即总到发晚点时间。程序中设置蚂蚁为20只，迭代次数为50，图2所示为当首列车晚点20 s时，每次迭代搜索得到的目标函数值以及目标函数值的收敛曲线。收敛曲线的横坐标为迭代次数，纵坐标为目标函数值，即总到发晚点时间。

图2 蚁群搜索过程

由图2可知，当调整区段内首列车到达第1个车站晚点20 s时，搜索得到的最佳总到发晚点时间为122 s；由收敛曲线可知，随着迭代次数的增加，目标函数值逐渐收敛，最后趋于稳定。

将搜索过程中的最优解所对应的时刻数据保存并读取，得到调整后的时刻表数据，如图3所示。

Ant Colony Optimization Algorithm applied to train operation adjustment of Urban Transit

WANG Jingjing
( School of Information Science &Technology,Southwest Jiaotong University,Chengdu 611756,China)

It is necessary to adjust the train timetable and let the train recovery on time as soon as possible when the train of Urban Transit in the process of operation is late due to equipment fault,passengers congestion,etc.Taking the minimum total delay time as the objective function,this article proposed a train adjustment model based on Ant Colony Optimization (ACO) Algorithm.Shenzhen Metro Line 6 was taken as an example to verify the practicality of the model under the Visual C++ 6.0 programming environment.

train operation adjustment;Ant Colony Optimization (ACO) Algorithm;model

U231.92∶TP39

A

1005-8451（2016）07-0001-04

2015-12-18

王婧婧，在读硕士研究生。