基于交通拥堵指数的蚁群改进算法研究

李枭　赵文君

摘要：随着城市道路规模的不断扩大，在车辆路线优化问题上，大部分学者只考虑距离或者费用等单目标，往往忽略了实际交通道路情况。提出了一种基于实际道路交通情况的路线优化改进蚁群算法，首先根据实际交通道路生成交通网络图，然后在信息素初始化时根据各路段的交通拥堵指数加入对应的交通拥堵权重；其次在信息挥发系数中加入车流量系数；最后在转移概率中加入道路畅通强度加强蚂蚁的选择。Matlab模拟实验证明，带交通拥堵指数优化后的蚁群算法能更好地符合实际道路情况，解决车辆路线优化问题。

关键词：车辆路线优化；交通拥堵指数；蚁群算法；Matlab

DOIDOI：10.11907/rjdk.172899

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2018）003007404

英文摘要Abstract：In view of the advancement of new urbanization in China and the continuous expansion of urban road scale， most scholars have only considered the single target of distance or cost， and often neglected the actual traffic road. Ant colony optimization algorithm for route optimization based on actual road traffic. First， according to the traffic congestion index， the traffic congestion weight is added when the pheromone is initialized. Secondly， the traffic flow coefficient is added to the information volatility coefficient. Finally， the road smoothing strength is added to the transformation probability. The simulation results show that the ant colony algorithm with traffic congestion index can be used to solve the problem of vehicle route optimization.

英文關键词Key Words：optimization of vehicle routes； traffic jam index； ant colony algorithm； Matlab

0引言

我国新型城镇化进程加快，城市交通道路变得越来越拥堵，城市居民出行、公交调度、物流转运成为大问题，发展智慧交通已经成为解决交通拥挤的必要措施。本文在求解销售员问题（Traveling Salesman Problem，TSP）、邮政员问题（Chinese Postman Problem，CPP）、车辆路线问题（Vehicle Routing Problem，VRP）等NP难题的背景下，研究一种基于现实交通道路的多目标优化车辆路线问题。车辆路线问题（VRP）最早由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗时最少等目的[1]。

目前常用的最优路径求解方法有BellmanFord算法、Dijkstra算法、A*算法及蚁群算法（ACO）、遗传算法（GA）、禁忌搜索算法（TS）、粒子群算法（PSO）、模拟退火算法（SA）、人工神经网络（ANN）等启发算法。

最近几年来，蚁群算法的研究取得了很多成果。夏小云、周育人[2]回顾了蚁群优化算法的收敛性分析、时间复杂度分析与近似性能分析等理论研究进展，分析了其理论研究对象从简单的拟布尔函数转为组合优化问题以及实际应用问题。何小锋、马良[3]针对蚁群算法求解VRPTW问题时易于陷入局部最优和收敛速度满的问题，提出了一种VRPTW的量子蚁群算法。文献[4]中提出“最大最小蚁群系统”MMAS（MaxMin Ant System），将信息素浓度控制在一定范围内变化，并对信息素浓度设置了上下限。文献[5]提出了一种将蚁群算法选择策略参数设置为迭代次数的分段函数蚁群算法。文献[6]提出带奖惩的蚁群算法，对较优解路径信息素浓度进行奖励，较差解路径信息素浓度给予惩罚，然而这两种算法的参数设置都根据经验确定，难以准确引导信息素的更新。文献[7]讨论了参数设置对蚁群算法性能的影响，但未提出有效的参数选择机制。文献[8]提出增加初始信息素浓度方向性，并在全局更新中引入动态因子的新颖算法，但其对方向引导和动态因子的选用仍需进一步优化。在对传统车辆路径求解搜索时间过长、求解质量不高或得不到最优解等情况下，文献[9]在一般物流配送路径问题处理方法和数学模型的基础上，提出了在限量车辆路径问题（Capacitated Vehicle Routing Problem，CVRP）中用改进的蚁群算法优化求解物流的配送路径。

在这些研究的基础上，本文根据城市道路拥堵情况，把交通拥堵指数运用到蚁群算法中，提出了一种基于交通拥堵指数的蚁群改进算法，该算法对信息素的初始化设置、信息素挥发系数的设置和蚂蚁转移概率的计算进行了改进，在符合实际道路的情况下，提高了最优路径的搜索效率。

1蚁群算法简述

蚁群算法（Ant Colony Algorithm，ACA）最早由意大利学者Marco.Dorigo于1991年在博士论文中提出，该算法模拟了自然界中蚂蚁的觅食行为[10]。蚂蚁在寻找食物源时会在其经过的路径上释放一种叫信息素的外激素，并能感知其他伙伴释放的信息素。因此信息素浓度的高低就可以近似表征为路径的远近，信息素浓度越高，表示对应的路径距离越短。一般情况下蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素， 以增强该条路径上的信息素浓度，这样就形成一个正反馈。随着时间的推进，较短路径上的信息素逐渐积累增多，选择该路径的蚂蚁个数也越来越多，最终蚂蚁能够找到一条从巢穴到食物源的最佳路径，即距离最短。同时生物学家发现，路径上的信息素浓度会随着时间的推移而逐渐衰减。蚂蚁觅食过程如图1所示。

目前，蚁群算法广泛应用于多种求组合最优化问题，例如车辆调度、通讯网络中路由、容量平衡、图着色、工件排序问题等。

1.1蚁群算法优缺点

蚁群算法作为一种仿生进化算法具有一些优点：①每只蚂蚁在搜索过程中彼此独立，相互通过信息素的释放改变周围的环境，并且个体间能通过环境中的信息素进行间接地通讯；②搜寻过程受正反馈的作用，不断收敛，最终逼近于最优解；③具有分布并行计算的能力，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率；④启发式的概率搜索方式，不容易陷入局部最优，易于寻找到全局最优解；⑤鲁棒性较好，不会因为个别蚂蚁搜索的路径差影响整个搜索结果。

蚁群算法的缺点：①算法的搜索时间较长。当处理的问题规模较大时，要在短时间内从大量的解中寻找出最优解是比较难的。在搜索初期，各个路径上的信息素浓度差不多一致，通过信息素的反馈，再到各个路径上的信息素有明显差别，这个过程需要较长时间；②易于陷入局部最优。在算法中影响蚂蚁的转移主要是由各个路径上的信息素浓度和城市间距离两个因素决定，致使蚂蚁趋于信息素浓度强的路径。

1.2蚁群算法基本步骤

步骤1：初始化参数

在计算之前为每只蚂蚁建立禁忌列表，并对相关的参数进行初始化，如设蚂蚁数量m、信息启发因子α、期望启发因子β、信息素挥发因子ρ、信息素释放总量Q、最大迭代次数iter_max、当前迭代次数iter等参数。

步骤2：构建解空间

将每个蚂蚁随机分布在不同的起点，对每个蚂蚁k（k=1，2，…，m）计算其下一个待访问的城市，直到所有蚂蚁访问完所有城市。

步骤3：更新信息素

计算每个蚂蚁经过的路径长度：Lk（k=1，2，…，m）

并記录当前迭代次数中的最优解。同时，对个城市连接路径上的信息素浓度进行更新。其中信息素的更新M.Dorigo给出了3种不同的模型，分别为蚂蚁循环系统（ant_cycle system）、蚂蚁数量系统（ant_quantity system）、蚂蚁密度系统（ant_density system）。它们的区别在于信息素变化的公式不同。

在蚂蚁循环系统中：

Δτkij（t）=QLk若蚂蚁k在该次循环中经过的边（i，j）

0否则

在蚂蚁数量系统中：

Δτkij（t）=Qdij若蚂蚁k在时刻t和t+1之间经过的边（i，j）0否则

在蚂蚁密度系统中：

Δτkij（t）=Q若蚂蚁k在时刻t和t+1之间经过的边（i，j）

0否则

这3种模型中前种利用的是全局信息，而后两种利用的是局部信息。

步骤4：判断是否终止

若iter< iter_max，则令iter=iter+1，清空蚂蚁经过路径的记录表，并返回步骤2；否则，终止计算，输出最优解。

2带交通拥堵指数的改进蚁群算法

2.1信息素浓度初始化

在经典蚁群算法中，大部分学者把初始信息素浓度设置为一个固定相同的值，这样容易使蚂蚁在开始搜索时产生大量的无关搜索路径，使得初始搜索时间偏长，这对信息素浓度的局部更新产生了误导，阻碍最优路径的搜索。本文基于实际交通道路情况的连通图（见图2、图3），在信息素浓度初始时根据道路交通拥堵情况加入交通拥堵权重（见表1），将初始化信息素公式修改为式（1）：

τij=Qdij·ω（1）

ω=0.090>TCI>2

0.072>TCI>4

0.054>TCI>6

0.036>TCI>8

0.018>TCI>10

其中，dij为相邻两节点间的距离；Q为每次搜索分配的总信息素，是一个给定的常量；ω为交通拥堵指数权重。交通路线越拥堵，初始信息素的浓度越低，这对初始搜索产生了较为合理的方向引导，加快了搜索速度。

2.2转移策略选择

在一般蚁群算法中，蚂蚁k在节点i寻找下一节点j的转移概率为式（2）：

2.3信息素挥发系数

基本蚁群算法的信息挥发系数ρ是一个不变的常量，鉴于实际道路交通车流量情况，不同道路的车流量不同，不能满足信息素及时更新的要求，故将信息素挥发系数改进为：ρ+ω，其中，ω为车流量系数：

ω=1车流量2

3结论与分析

实验采用图2中所示的道路进行算法的分析与仿真，搜索在符合实际道路情况下从某一节点出发，经过全部节点返回到起点的最短路径。本文改进的算法与经典蚁群算法（ACS）、MMAS算法进行对比分析。主要实验参数如表2所示。

通过用Matlab实验分析，得出结果如图4经典蚁群算法（ACS）、图5 MMAS算法、图6基于交通拥堵指数的蚁群改进算法的路径轨迹图。

以上结果与图2实际交通道路图进行对比分析，采用经典蚁群算法（ACS）的结果与实际道路有许多不符合的地方，如1011、39；MMAS算法同样存在不符合实际道路的情况，如611、39；采用基于交通拥堵指数的蚁群改进算法能够很好地按照实际道路进行路线规划。

4结语

本文针对车辆路线优化问题上往往忽略实际交通道路的情况，利用Matlab模拟实验证明带交通拥堵指数优化后的蚁群算法能够很好地按照实际道路进行路线规划，其中加入了交通拥堵权重、车流量系数以及道路畅通强度。未来可以考虑人流量、城市布局以及交通红绿灯等待时间等因素对路线优化的影响。

参考文献参考文献：

[1]PAOLO TOTH， DANIELE VIGO. He vehicle routing problem[M].Society for Industrial and Applied Mathematics Philadephia，2002.

[2]夏小云，周育人.蚁群优化算法的理论研究进展[J].智能系统学报，2016，11（1）：2736.

[3]何小锋，马良.带时间窗车辆路径问题的量子蚁群算法[J].系统工程理论与实践，2013，33（5）：12561261.

[4]STUTZLE，HOES.Maxmin ant system[J].Future Generation Computer System Journal，2000，16（8）：889914.

[5]畢军，付梦印.一种改进的蚁群算法求解最短路径问题[J].计算机工程与应用，2003，39（3）：107109.

[6]郑卫国，田其冲，张磊.基于信息素强度的改进蚁群算法[J].计算机仿真，2010（7）：191193.

[7]ZAKZOUK A A A ，ZAHER H M ，ELDEEN R A Z.An ant colony optimization approach for solving shortest path problem with fuzzy constraints[C]. 2010 The 7th International Conference on Informatics and Systems， INFOS，2010：18.

[8]吴虎发，李学俊，章玉龙.改进的蚁群算法求解最短路径问题[J].计算机仿真，2012，29（8）：215218.

[9]袁文涛，孙红.CVRP物流配送路径优化及应用研究[J].软件导刊，2016，11（15）：140143.

[10]COLORNI A， DORIGO M， MNAIEZZO V. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems，Man and Cybernetics，1996，26（1）：2941.

责任编辑（责任编辑：何丽）