蚁群算法在最优路径选择中的改进及应用

admin管理员组

文章数量:1532766

2024年5月11日发(作者：)

Technology Research

技术研究

蚁群算法在最优路径选择中的改进及应用

文／张俊豪

摘　要

：

避免交通拥堵是道路交通执法亟需解决的一个关键问题，为此，本文提出一种基于蚁群算法及实际路况的避

免拥堵最优路径选择算法。该算法首先能够从全局的角度，结合最短路径算法改变蚁群算法的启发式函数，减少蚂蚁

的盲目搜索概率；其次该算法能够结合道路交通的实时状况，改进信息素的初始分布机制，加快蚂蚁对最佳路径的选

择速度；另外该算法能够从局部和全局的双重角度改进信息素的更新机制，避免算法陷入局部最优解的困境。实验通

过与经典的蚁群算法以及迪杰斯特拉算法进行对比分析，证明该算法能够结合实际的交通路况提升改进算法的计算效

率，能够通过蚁群算法和迪杰斯特拉算法的结合对最佳路径进行不断优化，以较好的性能表现模拟出最优的行车路

线，具有针对性和创新性。

Abstract

：

Avoiding traffi c congestion is a key issue that need to be solved urgently in road traffi c law enforcement. Therefore,

an optimal route selection algorithm based on ant colony algorithm and actual road conditions to avoid traffi c congestion was

proposed. Firstly, this algorithm could change the heuristic function of ant colony algorithm from a global point of view by

combining the shortest path algorithm to reduce the blind searching probability of ants. Secondly, this algorithm could improve

the initial distribution mechanism of pheromone by combining the real-time traffic conditions to speed up the selection of

the optimal path. In addition, the algorithm could improve the updating mechanism of pheromone from both local and global

perspectives to avoid the dilemma of the local optimal solution. By comparing the classical ant colony algorithm and the

Dijkstra algorithm, the experiment proved that the algorithm could improve the computing effi ciency of the improved algorithm

by combining the actual traffi c conditions and could constantly optimize the best path by combining the ant colony algorithm

with the Dijkstra algorithm. Thus, it could simulate the optimal driving path with better performance, which was targeted and

innovative.

关键词

：

蚁群算法;实际路况;最优路径

Key words

：

ant colony optimization; actual road conditions; optimal path

0 引言

在国务院发布的《国家中长期科学和技术发展规

划纲要（2006-2020年）》中，将交通拥堵问题列为发

展现代综合交通体系亟待解决的“三大热点问题”之

一。智能交通系统作为“互联网+交通”的产物，利用

先进的科学技术对车、路、人、物进行统一的管控、调

配，成为了当下各国缓解交通拥堵的一个重要途径。

路径寻优是智能交通系统的一个核心研究内容，可以

有效的提升交通运输效率，减少事故发生频率，降低

对城市空气的污染以及提升交通警察的执法效率等。

最著名的路径规划算法是Dijkstra算法和Floyd算

法，Dijkstra算法能够在有向加权网络中计算得到某

2021.01 / 道路交通科学技术

21

技术研究

Technology Research

一节点到其他任何节点的最短路径；Floyd算法也称

查点法，该算法和Dijkstra算法相似，主要利用的是动

态规划思想，寻找加权图中多源节点的最短路径。近

些年，最优路径的研究主要集中以下几个方面：

（1）基于A*算法的路径寻优。A*算法作为一种重

要的路径寻优算法，其在诸多领域内都得到了应用。

随着科技的发展，A*算法主要运用于人工智能领域，

特别是游戏行业，在游戏中，A*算法旨在找到一条代

价（燃料、时间、距离、装备、金钱等）最小化的路径，

A*算法通过启发式函数引导自己，具体的搜索过程由

函数值来决定。A*算法也被很多的研究者引入到交通

路径寻优中，比如钱红昇提出的基于路网分层的改进

A*最优路径规划算法，该算法将时间因子加入到了启

发式函数中。

（2）基于遗传算法的路径寻优。遗传算法是借鉴

生物进化规律得到的一种随机搜索方法。遗传算法具

有并行性、全局搜索能力等诸多优点，被应用到人工

智能、信号处理以及生命医学等诸多领域，同时也被

应用到最佳路径的求解中。1975年，Holland 提出了

GA的概念和方法，GA在搜索最优路径时，存在容易

陷入过早收敛以及收敛性差等缺点。在国内，根据实

际情况，很多学者也对遗传算法进行了改进，并应用

到交通领域，比如占莉莎对免疫遗传算法中的因子进

行校正，对道路拥挤收费策略进行了良好的改善，徐

旭等人根据遗传算法对路网流量进行了分配研究等。

（3）基于模拟退火算法的路径寻优。在1953年，

N. Metropolis等人提出了模拟退火算法的思想。30

年后S. Kirkpatrick等人将该思想引入到组合优化领

域。它是基于Monte-Carlo迭代求解策略的一种随机

寻优算法。该算法是单点搜索，容易陷入盲目搜索的

困境，整体效率不是很高，另外该算法对参数具有很

强的依赖性，算法性能不是很好。在国内，模拟退火思

想也被很好的应用到交通领域，比如柴干等人基于模

拟退火算法在紧急救援服务点的优化选址方面做了深

入的研究和探索，其能够给决策者提供多种正确的选

址方案。李顺勇等人引入了冷却函数，对模拟退火算

法进行改进，建立了低碳车辆路径优化模型。

（4）基于蚁群算法的路径寻优。本文所用到的蚁

22

道路交通科学技术 / 2021.01

群算法是由Marco Dorigo博士在1992年提出，灵感

主要来源于蚂蚁集中觅食过程中所衍生出的集体交互

行为。在国内，徐向阳通过在蚁群算法中加入信息素

因子寻找最优路径。张立峰等人改进了蚁群算法中的

状态转移规则以及设计的局部搜索模块，对军事配送

中车辆调度问题进行了求解。

目前对最优路径的研究除了以上几种核心算法

外，还有人工势场法、禁忌搜索算法、神经网络算法、

粒子群算法等。这几种算法应用在进行路径的寻优过

程中，都发挥了各自的优点，但也存在着搜索效率不

高、局部最优等问题。

1 蚁群算法简介

蚂蚁在觅食过程中会展示出极其复杂的群体行

为，Marco Dorigo在其博士论文中提到，蚂蚁在觅食

过程中会根据群体行为迅速的找到一个最优路径将

食物带回，之后，经过世界各个领域内的学者对其进

行改进，蚁群算法开始应用于交通运输、大数据、医

学、国防等各个行业。

1.1 蚁群算法原理

蚂蚁在觅食过程中正常的群体行为可如图1所示，

以相同的概率选择觅食路径。

图1 没有障碍物时蚂蚁的觅食路径

当蚂蚁在觅食过程中遇到障碍物时，蚂蚁之间会

通过群体行为改变路线，并向着最优路线倾斜，如图2

所示。

图2 遭遇障碍物时蚂蚁的觅食路径

随着时间的推移，蚁群最终都能聚集到一条最合

适的路径上去，以最小的代价找到食物源。以上蚁群

展示出的群体行为是因为蚂蚁之间可以互通信息，分

享经验。蚂蚁在觅食过程中会产生一种物质以相互通

信，即信息素。蚂蚁在某条路径上经过时，会在此条路

径上遗留信息素，如果某条路径上的蚂蚁越来越多，

那么路径上的信息素就会越积越多，相反，如果某条

路径上的蚂蚁越来越少，那么路径上信息素就会越来

越少，这是因为信息素挥发的缘故。所以蚂蚁在觅食

过程中就会根据路径上的信息素选择觅食路径，它们

以更大的概率选择信息素较多的路径，这样就形成了

一个正向反馈机制，较好的路径保留下来，差的路径

被淘汰掉。

1.2 蚁群算法的数学模型

在实际的蚁群算法模型中，设定蚁群的群体行为

具有以下数字特征：

（1）设τ

ij

（t）为节点i和j之间的信息素浓度，p

k

（

i

,

j

）为第k只蚂蚁选择路线（

i

，

j

）的概率函数，即蚂蚁会

根据p

k

（

i

,

j

）选择下一个前进方向。

（2）在蚂蚁遍历所有的节点之前，定义每只蚂蚁

仅可访问未知的节点，已访问过的节点不再访问，设

禁忌表tabu存放访问过的节点。在每只蚂蚁遍历完所

有的节点后，就清空禁忌表tabu，等待下一只蚂蚁的

遍历。

（3）每只蚂蚁在遍历完所有的节点后，都会按照

一定的规则在路径上留下信息素，通过多只蚂蚁的信

息素叠加和挥发机制会形成每条路径的信息素分布

状态，其中信息素挥发机制是为了避免蚂蚁在寻优过

程中过于依赖经验，同时也避免早熟收敛。

在蚁群算法中，蚂蚁除了根据信息素选择路径之

外，还被赋予一定的自主选择权利，即通过自我判断

和信息素共同决定下一个选择，比如在

t

时刻，蚂蚁k

的概率函数可表示为：



τ

(

i

,

j

)

α

•

η

(

i

,

j

)

β

p

k

(

i

,

j

)

=







∑

τ

(

i

,

j

)

α

•

η

(

i

,

j

)

β

,

m

∈

allowed

k



j

∈

m

（1）





0,其他

式（1）中，η（

i,j

）表示蚂蚁k自主选择的期望函

Technology Research

技术研究

数，即启发式函数，α为信息启发因子，表示信息素对

蚂蚁选择路径的影响程度，α越大，蚁群之间的信息

分享机制就越重要，β为信息启发因子，β越大，蚂蚁

个体的自主选择机制就越重要，allowed

k

表示蚂蚁下

一步可以前往的节点集合。

η（

i,j

）的取值一般定义为式（2）：

（

η

(

i

,

j

)=

1

d

2）

ij

式（2）中，d

ij

表示节点

i

和

j

之间的路径长度，即d

ij

越长，表示蚂蚁选择该条路径的期望函数值就越小，

同理p

k

（

i, j

）就越小。

在一只蚂蚁遍历完所有的节点后，所有路径上的

信息素要进行更新，既要叠加又要挥发。在t时刻，把

τ

ij

（t）作如下调整：

（3）

（4）

在式（3）中，ρ为信息素的挥发系数，取值范围在

0到1之间，以此防止信息素的无限积累，避免算法早

熟收敛。式（4）中，Δτ

ij

（

t

）表示节点

i

和

j

路径上的信

息素分布，在此定义Δτ

ij

（0）=0，Δτ

k

ij

（

t

）表示第K只

蚂蚁带给

i

和

j

路径上信息素增量。

对于Δτ

k

ij

（t）的取值主要对应着三种主要模

型，分别是蚁密系统（ant-density system），蚁周

系统（antcycle system），蚁量系统（ant-quantity

system）。

在蚁密系统模型中，Δτ

k

ij

(t)的取值如式（5）所示：

∆

τ

k



Q

,

若第

k

只蚂蚁在

t

+

1

时刻经过该路径

i

j

(

t

)

=



(

i

,

j

)



0

，其他

（5）

式（5）中，Q表示第K只蚂蚁在t时刻经过路径

（

i,j

）的信息素常量。

在蚁周系统，Δτ

k

ij

（t）的取值如式（6）所示：



∆

τ

k



Q

,

若第

k

只蚂蚁在本次遍历中经过该路径

(

i

,

j

)

i

j

(

t

)

=



L

（6）



k



0

，其他

式（6）中，Q表示第K只蚂蚁在本次遍历中所产生

的信息素常量，L

k

表示蚂蚁本次遍历完所走的所有路

2021.01 / 道路交通科学技术

23

技术研究

Technology Research

径和。

在蚁量系统，Δτ

k

ij

（t）的取值如式（7）所示：



Q



,

若第

k

只蚂蚁在

t

+

1

时刻中经过该路径

(

i

,

j

)

∆

τ

i

j

(

t

)

=



d

i

j

（7）



0

，其他



k

2 基于蚁群算法以及最短路径的最优路径选择

2.1 改进信息素初始浓度分配机制

在传统的蚁群算法中，每条路径上的初始信息素

浓度分布是一样的，这是为了蚁群在觅食初始能够以

相同的概率选择觅食路径。但是在车辆的道路寻优过

程中，人们对路径的选择概率是不一样的，实际的交

通路况会严重影响最优路径的选择结果，比如交通拥

堵、红绿灯等候时间、道路维修以及车辆限号等都是

关键的道路选择因素。所以传统的信息素初始分配机

制在实际的车辆道路寻优过程中会降低对最优路径

的寻找效率，增加算法的计算时间，而且容易陷入局

部最优。

本文在进行信息素的初始分配时会考虑路径的实

际长短以及道路的拥堵状况，改变蚂蚁对初始路径的

选择概率，改善算法的计算效率。在实际的交通路况

中，造成交通拥堵的因素有很多，比如局部限速、天气

情况、道路交通事故、道路完整状况、交通信号灯的等

候时间、驾驶人因素、上下班高峰期等。根据层次分析

法，得到了常见交通拥堵因素的权值，如表1所示。

表1 常见交通拥堵因素的权值

式（7）中，Q表示第K只蚂蚁在t时刻经过路径

（i,j）的信息素常量，d

ij

表示路径（i,j）的长度。

这三种系统模型最大的区别在于信息素的更新是

否利用了全局信息。在蚁密模型和蚁量模型中，信息

素的更新是利用了局部信息，在蚁周模型中信息素的

更新是利用了全局信息。三种模型相比之下，蚁周模

型用到了全局的路径信息，不会使算法陷入局部最优

解，使用较为广泛。

1.3 蚁群算法的优缺点

蚁群算法的优点主要有三点：并行性、自组织以

及正反馈。缺点主要有两点：运行时间较长和容易陷

入局部最优。常见的改进蚁群算法有精英蚂蚁算法、

优化排序蚂蚁算法、最大最小蚂蚁算法以及最优最差

蚁群算法。

局部限速

0.056

天气情况

0.054

道路交通事故

0.098

道路完整状况

0.106

交通信号灯的

等候时间

0.356

驾驶人水平

0.022

车辆的平均行驶

速度

0.308

根据表1可发现，能够衡量交通拥堵的主要因素

有交通信号灯的等候时间以及当前车辆的平均行驶

速度，因此在进行信息素的初始分配时应着重考虑这

j表示车辆

两个因素的影响。设

i

表示当前车辆位置，

预计行驶的下一位置，交通信号灯的等候时间用E衡

量，E为某个时间段内车辆的等候时间期望，车辆在

该时段内的平均行驶速度用v表示。建立交通拥堵函

数

F

ij

（

t

）

，如式（8）表示：

堵函数值就越小，虚拟拥堵长度也就越小，相反就越

大。

将道路拥堵因素考虑在内后，信息素的初始分配

机制，可如式（9）所示：

（9）

i,j

）的信息素浓度。τ

ij

（0）表示在初始时刻路径（

M表示蚂蚁每次搜索时初始信息素浓度值，为一常

F

ij

(

t

)

=

κ

∗

v

−

1

*

E

(

time

)

（8）

F

ij

i,j

）

的拥堵函数，

（

t

）

表示在t时刻，路径（k为调

和参数。该函数能够直接反应道路的实际拥堵情况，

即行驶速度越快与交通信号灯等候时间越短，道路拥

i,j

）的长度，w

1

，w

2

表示相应的权值。数，d

ij

表示路径（

i,j

）w

1

*d

ij

与w

2

*

F

ij

（t）的和表示路径（上实际的路径长

度和虚拟拥堵长度的加权和，这能够衡量道路最原始

的通行状况，其值越大，表示该路径上的信息素初始

浓度就越小，其值越小，表示该路径上的信息素初始

24

道路交通科学技术 / 2021.01

浓度就越大。

2.2 改进选择函数

蚂蚁的概率选择函数是由路径上的信息素

浓度和启发式函数决定的，但是在传统的蚁群

算法中，启发式函数仅仅考虑了当前路径的长

度，未能从全局的角度出发衡量完整的路径长

度，容易陷入局部最优的情况，所以在本文中，

启发式函数应从局部和全局的角度出发，综合

考虑蚂蚁的概率选择函数。

设i表示当前节点位置，

j

表示车辆的下一位

置，s表示车辆的行驶终点位置，

D

js

表示采用

Dijkstra得到的节点j到终点s的最短路径。故启

发式函数η（

i, j

）如式10所示：

η

(

i

,

j

)=

Q

δ

d

ij

+

ε

Djs

（10）

式（10）中，d

ij

为路径（

i, j

）的长度，Q表示

第K只蚂蚁在本次遍历中所产生的信息素常

量。

和为相应的权值。此时，启发式函数

既能够根据局部路径d

ij

考虑局部的路径信息，

又可以根据全D

js

考虑下一选择位置

j

在全局路

径上的位置信息，这样在选择下一路径时能够

站在全局和局部的双重角度衡量路径的优良程

度，避免陷入局部最优的状况。

2.3 改进信息素更新机制

信息素的更新机制是蚁群算法的核心，在

一定程度上决定了蚁群算法的性能。在上一节

中，式（3）和式（4）表明了蚁群算法的信息素更

新机制，并对应的有三种模型系统对Δτ

k

ij

（

t

）进

行取值，三种模型系统分别从局部和全局的角

度对信息素进行了更新。但车辆的道路寻优

不同于蚁群的道路寻优，车辆的道路寻优要

考虑拥堵问题，所以在实际的运行过程中，使用

全局的信息素更新机制，往往达不到最优解，使

用局部的信息素更新机制，又容易陷入局部最

优，同时也容易陷入局部拥堵。

本文将从局部和全局的双重角度对信息素

进行更新，如图3所示：

Technology Research

技术研究

图3 路径选择图

在图3中，例如车辆需要从节点1出发到节点10，假设最

初的一条最优路径为1→2→5→7→10，车辆在到达节点2

后，发现路径2→4上的信息素浓度较低，而且启发式函数值

较小，断定为拥堵路径，故绕开，转向2→5。随着时间的推

移，车辆的增多，根据原始蚁群算法中信息素的更新方法，

各条路径上的信息素浓度会发生变化，比如在路径5→7上，

由于选择该条路径的车辆逐渐增多，该条路径上的信息素浓

度也开始不断地增加，很有可能会变成一条拥堵路段，而此

时高信息素浓度必然引来更多的车辆，按照算法流程，2→5

路径也极有可能变得拥堵。这种“正向反馈”机制渐渐变成

了“拥堵堆积”机制。鉴于此种情况，本文将交通拥堵函数

考虑进来，改变信息素的局部更新函数，增加算法的寻优效

率，本文的信息素局部更新函数如式（11）所示：

（11）

式（11）中，Δτ

k

ij

（t）

1

表示第K辆车在经过路径（

i,j

）所

残留的局部信息素数量，Q表示第K只蚂蚁在本次遍历中所

产生的信息素常量。这样局部信息素的更新将路径的长度以

及实际的交通路况考虑进来，即距离较短、畅通路径的信息

素就会增加，拥堵路径的信息素会减少，局部寻优的效率也

会增加。例如在最优路径1→2→5→7→10中，随着车辆的增

多，2→5路径上信息素也会逐步增加，同时也有可能会变得

拥堵，但经过对信息素更新机制的改进，2→5路径上信息素

的增长速度开始减缓，而路径2→4上的信息素开始逐步增

加，选择该条路径的概率也会逐步增加，进而最优路径也会

产生变化，能够达到局部最优。

在实际的交通路径选择中，连接两个地方的路径有很

多，比如在图3中节点1和10的连接路径就有很多条，上文

2021.01 / 道路交通科学技术

25

技术研究

Technology Research

中，从局部信息素更新的角度改正了可能存在的局部

拥堵造成的局部路线错误，但是没有从全局的角度考

虑所有路径的信息素分配。

比如在图3中，假设存在从源节点1到目标节点10

的最优路径1→2→5→7→10，若此时路径5→7随着

车辆的增多变得拥堵，如果根据上述局部的信息素更

新机制，车辆会转向路径5→8，当车辆达到一个饱和

的状态时，路径5→7和5→8都会变得拥堵，两条路径

上的信息素浓度也会逐步增加，随着迭代次数的增

加，而路径1→2的交通拥堵函数值也在逐步增加，但

是由于信息素更新的原则，新的路径选择会花费更多

的时间，极大的降低了算法的性能，此时更好的路径

1→3→6→7→10可能此时是一条最优的路径，但由于

信息素更新机制的原因，路径1→3不会被很多车辆快

速的选择。所以路径信息素的更新需要考虑全局信息

素的影响，避免算法陷入局部最优的状况。

设L

k

表示第k辆车本次遍历完所走的所有路径

和。全局信息素更新如式（12）所示：

∆

τ

k

i

j

(

t

)

2

=

Q

L

k

（12）

式（12）中，Δτ

k

ij

（t）

2

表示第K辆车在经过路径

（i,j）所残留的全局信息素数量。

借鉴最优最差蚁群算法，本文的信息素更新如式

（13）所示：

（13）

当路径（i,j）属于最优路径p*时，采用Δτ

k

ij

（t）

2

对

其进行奖励，反之采用Δτ

k

ij

（t）

2

对其进行惩罚，这样

本算法不仅从全局的角度更新了信息素，也从局部的

角度更新了信息素，避免算法陷入局部最优，同时也

增加算法的执行效率。

2.4 路径评价函数

对于最优路径的评价，一直以来没有严格意义上

的标准，有些学者评价最优路径偏重于路径距离，有

些学者评价最优路径偏重于时间，有些学者评价最优

路径偏重于能量的消耗等，本文将综合考量实际车辆

在路径选择中的两大影响因素：时间和距离，故引入式

（14）作为路径的评价函数。

26

道路交通科学技术 / 2021.01

（14）

在上式中，d代表实际的路线距离，v代表车辆在

没有拥堵时的平均速度，E（V）代表车辆在拥堵时的

速度期望，E（t）代表车辆在拥堵时的拥堵时间期望，

表示车辆的虚拟拥堵距离。所以f（v,t）表示的是车辆

的实际运行距离与虚拟拥堵距离的和，得到的值越

小，说明该车辆在该路径上的实际运动距离与运动时

间都能达到最佳，相反，如果得到的值越大就说明车

辆实际选择的道路路径长度偏长或者拥堵时间过久。

故本文中在所有的路径中f（v,t）值最小的那条路径为

最优路径p*。

2.5 改进信息素挥发机制

在蚁群算法中，蚂蚁所产生的信息素会挥发，在实

际的道路交通中，车辆所遗留的信息素同样也会“挥

发”，本文根据车流量T，即单位时间内道路通过该路径

的车辆数目，衡量挥发因子ρ，如式（15）所示。

（15）

3 实验及结果分析

本文在Win10 操作系统上运行 MATLAB

R2016a 软件，根据图3设置地图环境进行仿真实验，

以经典的蚁群算法和迪杰斯特拉算法为对比模型，验

证本算法的有效性。根据层次分析法以及传统的蚁群

算法要求，本算法的主要参数如表2所示。

表2 实验参数表

参数数值

M1

w

1

0.4235

w

2

0.5765

Q1

δ0.7248

ε0.2752

α2

β4

本文选定的道路为单向4车道，根据蚁群算法以

及河南省某地市发布的实际道路交通路况，当单位

路径长度上出现车辆数量大于阈值t

1

=750辆/km时，则定

义交通为极度拥堵状态，行车速度由原来的平均80km/h

降为25km/h，交通信号灯的等候时间由原来的30s上升到

300s；当单位路径长度上出现车辆数量大于阈值t

2

=600

辆/km时，则定义交通为拥堵状态，行车速度由原来的平

均80km/h降为45km/h，交通信号灯的等候时间由原来的

30s升到100s；当单位路径长度上出现车辆数量小于阈值

t

3

=100辆/km时，道路为十分流畅状态，行驶速度可保持

80km/h，交通信号灯的等候时间还是30s。

故本文采用三组综合对比实验进行分析，根据车流量分

别设定为100，600，750。

第一组实验：当车流量为100辆/km时，根据蚁群算

法以及实际路况的最优路径选择算法可知，最优路径为

1→3→5→7→9→10，实验结果如图4所示（算法设定出发

节点为1，终点为10）。

图4 基于蚁群算法以及交通路况的最优

路径选择算法仿真结果

图5 经典蚁群算法最优路径仿真结果

Technology Research

技术研究

在图4及图5、图6中，每个节点在平面图中

用二维坐标的方式进行标记，曲线反映的是算

法选择的实际路径以及实际路径长度。

根据经典蚁群算法的计算结果可知，最优

路径为1→3→6→7→10，实验结果如图5所示

（算法设定出发节点为1，终点为10）。

根据迪杰斯特拉算法的计算结果可知，最

优路径为1→3→5→7→10，实验结果如图6所

示（算法设定出发节点为1，终点为10）。

图6 迪杰斯特拉算法最优路径仿真结果

三种算法得到最优路径长度以及f（v,t）对

最优路径的评价结果如表3所示。

表3 实验结果对比

算法

路径距离

（km）

f（v,t）

基于蚁群算法以及交通路况

的最优路径选择算法

61.2473.15

经典蚁群算法41.3688.62

迪杰斯特拉算法38.9184.91

第二组实验：当车流量为600辆/km时，基

于蚁群算法以及实际路况的最优路径选择算法

可知，最优路径为1→2→5→7→9→10；基于经

典蚁群算法的最优路径选择算法可知，最优路

径为1→3→6→7→10，没有产生变化；基于迪

杰斯特拉算法的最优路径选择结果也不变，最

优路径仍为1→3→5→7→10。

2021.01 / 道路交通科学技术

27

技术研究

Technology Research

三种算法得到最优路径长度以及f（v,t）对最优路

径的评价结果如表4所示：

表4 实验结果对比

算法

路径距离

（km）

f（v,t）

基于蚁群算法以及交通路况的

最优路径选择算法

74.483.06

经典蚁群算法41.36112.44

迪杰斯特拉算法38.91129.06

第三组实验：当车流量为750辆/km时，基于蚁群

算法以及实际路况的最优路径选择算法可知，最优路

径为1→2→5→8→9→10；基于经典蚁群算法的最优

路径选择算法可知，最优路径为1→2→5→7→9→10；

基于迪杰斯特拉算法的最优路径选择结果不变，最优

路径仍为1→3→5→7→10。

三种算法得到最优路径长度以及f（v,t）对最优路

径的评价结果如表5所示：

表5 实验结果对比

算法

路径距离

（km）

f（v,t）

基于蚁群算法以及交通路况的

最优路径选择算法

81.7496.52

经典蚁群算法74.4122.58

迪杰斯特拉算法38.91135.63

根据三组实验结果进行纵向比较，可发现随着车

辆数的增加，除了迪杰斯特拉算法得到的实际最短

路径没有产生变化以外，基于经典的蚁群算法得到的

实际路径长度在车辆达到750辆/km时也有所增加，

基于蚁群算法以及实际路况的最优路径选择算法得

到的路径长度随着车辆数量的增加，最优路径的长

度也有所增加，这主要是因为该算法充分考虑了实

际的交通路况。比如第一组实验得到的最优路线为

1→3→5→7→9→10，第二组实验得到的最优路线为

1→2→5→7→9→10，这是因为算法在更新路径的信

息素时，根据全局的角度改变了信息素的更新机制，

即车辆在增加到一定数量时，路径3→5开始拥堵，根

据全局的信息素更新特点，转到了路径1→2→5；第三

组实验得到的最优路线为1→2→5→8→9→10，这是

28

道路交通科学技术 / 2021.01

因为算法在更新路径的信息素时，根据全局和局部的

双重角度改变了信息素的更新机制，即车辆在增加到

一定数量时，根据全局的信息素更新特点，路径3→5

转到了路径1→2→5，通过局部的信息素更新特点，路

径5→7转到了路径5→8。另外三种算法得到最优路

径的f（v,t）函数值也都在增加，而且迪杰斯特拉算法

的增速最快，经典蚁群算法其次，基于蚁群算法以及

交通路况的最优路径选择算法最慢。

根据三组实验结果进行横向比较，在三组实验

中，本文提出的算法得到的实际路径长度相比其他两

种算法都有所增加，这主要是因为迪杰斯特拉算法不

考虑实际的道路情况，而本文提出的算法并不是以路

径的长度作为最终的衡量目标，而且相比经典蚁群算

法路径长度也有所增加，这主要是改进了信息素的初

始分配机制以及信息素的更新机制的缘故。通过对三

种算法得到最优路径的f（v,t）函数值进行比较，可以

发现在每组实验中，本文提出的算法的f（v,t）函数值

最小，说明路径也最优。

另外通过本文算法和经典的蚁群算法进行相比

较，本文算法的收敛速度明显要优于经典的蚁群算

法，这主要是由于本文算法改变了信息素的初始分配

机制，大大增加了收敛速度。

通过对实验的分析，可知基于蚁群算法以及实际

路况的最优路径选择算法避免了迪杰斯特拉算法的

“唯距离论”，同时也避免了经典蚁群算法没有考虑交

通实际路况和收敛速度过慢的缺陷，符合实验预期。

4 小结

基于蚁群算法以及实际路况的最优路径选择算

法能够从实际路况出发，从局部和全局的角度更新信

息素，使得算法避免拥堵，重新选择路径，能够以更好

的收敛速度进行路径规划，未来应增加更多的交通因

素到信息素的更新机制中。

（张俊豪　铁道警察学院）

本文标签： 路径算法信息选择车辆