基于蚁群算法的智能交通行车最优路径研究

（陕西铁路工程职业技术学院，陕西渭南市，714000）杨钰浩

随着我国城镇化建设的不断发展，城市居民汽车保有量的逐年提升[1]。城市交通拥堵问题日益严重，基于大数据资源和计算机技术的智能算法则是解决这一问题的有效手段之一，尤其是在传感器技术和无线通信技术快速发展的大背景下，交通数据资源将会有更加充分的保障，将智能算法应用于交通行车最优路径的搜索已经成为未来一段时间内必然的发展趋势[2]。

1 蚁群算法概述

蚁群算法是一种模拟蚂蚁集体觅食行为的拟进化算法，单个蚂蚁在行走的过程中会残留一种可供同类识别的标记物质，用以指导下一次觅食的行走路径，标记物质越多，则说明该路径上蚂蚁的数量越多或路径越长[3]。由于蚂蚁在选择行走路径时会倾向于标记物质较多的方向，在大量个体的共同选择下最终会出现一条标记物质最多且长度最短的行走路线，出现最优解收敛[4]。

2 单个蚂蚁路径搜索

当蚂蚁在城市路网中行走时会遇到大量联通性较差的节点，在蚂蚁走入“死胡同”后，则需要将该蚂蚁走过的路线设置为“0”，阻止其他蚂蚁选择此路线。

图1 蚂蚁行走路线

假设有一只蚂蚁采用1-2-3-6-5的线路从节点1走到节点5，它会发现2-5的路线存在大量的标记物质，因此它以后会直接从节点2走向节点5，并删减2-3、2-6、6-5这三个路段，长此以往，这三个路线的标记物质将越来越少，则其他蚂蚁在选择路径时，可以根据标记物质减少量来对所选路径的正确率进行加权，提醒其他蚂蚁不会选择联通“死胡同”的路径。加权后的蚂蚁由节i点到节点j路径选择概率计算方法如下：

上式将节点i至节点j路段上的标记物质量记为τi,j；将节点i与节点j距离的倒数记为ηij；将期望程度记为β；将标记物质量记为α；将不在蚂蚁轨迹表中且与i节点相连接的路段记为allowedk；将路径被删减的次数记为ci,j；在蚂蚁再次选择该路段而未进行删减的情况下，则将该属性值减1，使标记物质的诱导作用得到恢复。

在此基础上，还需要对单个蚂蚁的最长行驶距离加以限定，在行驶距离过长的情况下将所在位置设置为起点并重新选择路径。本次研究将蚁群个体量设置为30并进行最短距离的路径搜索，经过200次迭代后，路径长度平均值为89.56km，完成搜索所需时间4.7s，收敛速度较快。

3 标记物质更新

蚁群算法本质上是一种搜索算法，并通过解空间参数化概率分布模型进行数据，其中的“解空间参数化概率”在本次研究中实际指的是标记物质，该数值与最优解收敛的质量和速度有着直接的关系，蚂蚁在每完成一轮路径搜索工作后都会更新一次标记物质量。本次研究从将每个路段中标记物质的量设定在[τmin,τmax]之间。首先，基于初始标记物质量τ0对标记物质的最大值τmax和最小值τmin进行计算。为了避免模型收敛至同一条路径并维持足够的变异性，本次研究通过多次实验决定取τmin=0.005×τmax=τ0×0.2。在此基础上基于τ0实施一次随机路径搜索，根据蚁群最大的迭代次数NC和每次路径搜索的结果确定标记物质释放总量Qi。具体的实现策略为假设蚁群算法在迭代了μ·NC次后可以收敛，假定收敛后状态下标记物质量为τmax，则能够对标记物质的投放总量进行计算，计算方法为：

上式将最大迭代次数记为μ·NC；将期望收敛的迭代数与最大迭代次数的比值记为μ，该数值需要根据实际需求和实验结果进行调整。设整个路网中存在m条较优路径，对各路段标记物质的增量进行计算，计算方法为

在基于公式（3）的数据处理过程中，随着迭代次数的增加，较优路径选取数量m也会逐渐减少。在标记物质量不断更新的过程中，标记物质会根据解的优秀程序在多条路径上实现有差异的分布，既具有寻找最优解的能力，也能够有效规避局部收敛问题。

4 路径行程时间

动态路网下的行程时间可基于浮动车数据进行计算而得出，利用路段长度和路段平均速度得出单个路段的行程时间，每个路段行程时间之和即为路径行程时间。设车辆在T0时刻到达某路段，车辆到达后的第一次更新时刻为T1，路段的平均速度更新间隔为t，路段长度为L，T0至T1时段路段的平均速度为speed0。在Lpeed0·(T1-T0)的情况下，车辆在该路段的行程时间Total=L/speed0；在L＞speed0·(T1-T0)的情况下，代表路段的平均速度在车辆未到达路段终点时就已经出现了变化，设车辆在该路段行驶了n-1个完整的平均速度采集时段t后，在未到达第n个t时段时离开了该路段。该状况下可根据以下方法计算车辆在该路段总的行程时间。

5 蚁群算法的具体流程

本次研究利用动态平均速度下的行程时间和蚁群算法来获取动态路网下的最短路径，具体流程如下：①初始化全局参数，具体包括每个路段中的全局标记物质τ0、节点编号、路段编号等，最大迭代次数循环次数NC，迭代系数C为1，蚂蚁的数量为N，删减次数设置为0，初始较优解的选取数量为m，全局禁忌路径搜索起点为Nstart，全局禁忌路径搜索终点为Nend，并计算标记物质的最大值τmax和标记物质的最小值τmin；②初始化N只蚂蚁，令C=C+1，将每只蚁的轨迹表置为空值，将蚂蚁的起点记为Nstart，将蚂蚁的终点记为Nend；③每只蚂蚁均采用公式（1）的方法选择行驶路径，在搜索新路径之前，每一只蚂蚁都会分析是否可以对行驶轨迹进行优化，将删减路段的删减属性值加1，并在完成优化后向下一节点行进。在选择路段的删减属性值大于0的情况下，则将该路段的删减属性值减1，在蚂蚁无法根据指定规则前进或下一节点为空的情况下，则需要将当前的节点删除，并将该路段的标记物质设置为0；④反复实施第三步操作，使蚂蚁全部到达节点Nend，基于动态路网的平均速度和蚂蚁的行驶轨迹对路段的行程时间进行计算，并根据公式2对标记物质的释放总量进行计算；⑤基于标记物质的释放总量来选择m条较优路径，在此基础上对较优路径的路段信息素的增量进行计算，对全部路段的τi,j(t)进行更新。在τi,j(t)＜τmin的情况下，令τi,j(t)=τmin，在τi,j(t)＞τmax的情况下，令τi,j(t)=τmax，并将每次迭代的最优解看作为局部最优解；⑥重复进行第二步至第五步的操作，直至迭代系数C等于NC；⑦在完成每一次迭代后都会出现一个局部最优解，在完成所有迭代后筛选出全部最优解，进而确定全局最短路径，在此基础上计算出行程时间、行驶距离并输出其轨迹。

6 结语

本次研究通过蚁群算法对交通路网最优路径的搜索方法进行了详细的介绍。在未来的研究工作中，还需要通过并行策略对蚁群算法进行优化，将其应用于更大规模的路网分析，进一步降低计算时间。