基于精英蚁群算法的交通最优路径研究

doi:10.13232/j.cnki.jnju.2019.05.001

基于精英蚁群算法的交通最优路径研究

汪贵庆, 袁杰, 沈庆宏^,

南京大学电子科学与工程学院，南京，210023

Research on traffic optimal path based on elitist ant system

Wang Guiqing, Yuan Jie, Shen Qinghong^,

School of Electronic Science and Engineering，Nanjing University，Nanjing，210023，China

通讯作者: E⁃mail：qhshen@nju.edu.cn

收稿日期: 2019-03-08 网络出版日期: 2019-09-22

基金资助:

江苏省自然科学基金. BK20181256

Received: 2019-03-08 Online: 2019-09-22

摘要

随着交通规模的增大，人们对自驾出行的质量需求越来越高，而在当前的交通最优路径选择的研究中，大多只考虑静态的交通路网场景，且忽略了通过交叉口时的代价，造成计算结果和实际行驶的代价之间误差较大.针对这一问题，基于Petri网络，建立了更精确的多因素道路交叉口交通路网模型，提出了基于精英蚁群算法的交通最优路径选择算法，并对经典蚁群算法提出两个方面的改进：第一，在信息素浓度的初始化过程中加入主干道引导和行车方向的引导，以加快蚂蚁群初始的搜索速度；第二，在全局信息素浓度更新时，使用双精英蚂蚁策略，采用相互约束的方式更新两条最优路径上的信息素浓度，解决了算法过早陷入停滞的问题，且计算出多个可供选择的路径.仿真结果表明，该算法在保证收敛性的同时，将搜索到最优路径的概率提升至100%；同时，在得到最优解概率均不低于90%的前提下，该算法的收敛速度是其他算法的数倍.

关键词： 交通 ; 最优路径 ; 路网模型 ; 蚁群算法 ; 信息素 ; 精英策略

Abstract

The complexity of urban traffic road network and the China's car parc are growing at a high speed. Traffic jam now is a common problem in most citys. And the quality of people's driving trips is being seriously affected. How to plan a real⁃time and optimal driving route in a complex and variable traffic network has become a real concern for people when they travel. In most of the current research on the optimal route selection of traffic，only the static traffic road network scenario is considered，and the cost of driving through the signal intersections is neglected，which resulting in a large error between the calculation result and the actual driving cost. To solve this problem，a more accurate multi⁃factor traffic network model with road and signal intersection based on Petri nets is built，and a traffic optimal route selection algorithm based on improved elitist ant system is proposed. Improvements on the classical ant colony optimization are provided in two aspects. Firstly，the main road guiding and driving direction guiding are added in the initialization of the pheromone concentration to speed up the initial search; Secondly，a dual elitist ant strategy is utilized that the pheromone concentration on the two optimal paths is globally updated in mutually constraints way. This strategy can accelerate the convergence of the algorithm while avoiding the local optimal solution and two optimal paths can be searched to for selection. The simulation results show that the probability of finding the optimal path is increased to 100% while the convergence rate is guaranteed with the proposed algorithm. At the same time，the convergence rate of this algorithm is several times of others’ under the premise that the probability of finding the optimal solution is not less than 90%.

Keywords： traffic ; optimal path ; road network model ; ant colony optimization ; pheromone ; elitist strategy

PDF (1010KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

汪贵庆, 袁杰, 沈庆宏. 基于精英蚁群算法的交通最优路径研究. 南京大学学报（自然科学版）[J], 2019, 55(5): 709-717 doi:10.13232/j.cnki.jnju.2019.05.001

Wang Guiqing, Yuan Jie, Shen Qinghong. Research on traffic optimal path based on elitist ant system. Journal of nanjing University[J], 2019, 55(5): 709-717 doi:10.13232/j.cnki.jnju.2019.05.001

交通最短路径问题是车辆行驶路径问题的一种，是交通工程学与地理信息科学的一个重要的研究方向，其概念最早由Dantzig and Ramser^[1]于1959年提出，此后的多数研究都基于静态的交通路网.但是，随着城市的发展以及社会的变迁，我国交通路网系统变得越来越庞大、多变和复杂，车辆拥堵问题、路面质量、限速和交通管制等状态也在不断变化，人们对出行时间、行车距离和路面对车辆的损耗等方面均有显著差异化的需求，这些都使得基于传统静态交通路网模型的最优路径选择不再具有实际意义.

国外关于最短路径问题的研究开始较早，1959年图灵奖获得者Dijkstra^[2]提出用于求解SSAP问题的Dijkstra算法，1968年斯坦福研究院Hart et al^[3]首次提出了著名的启发式算法

A⁃star算法，该算法被视为是Dijkstra算法的拓展，也有更好的性能.蚁群算法（Ant Colony Optimization，ACO）最早由Dorigo^[4]于1992年提出，在计算机科学和运筹学研究中被用于概率性地求解计算问题.作为现代元启发式算法，其通过模拟现实生活中蚂蚁群在觅食过程中寻找路线的行为而工作.蚁群算法具有正反馈、鲁棒性和分布式等特点，被广泛应用于汽车路线问题^[5]、调度问题^[6]和集合问题^[7]等问题中.在最短路径问题的许多研究中，改进的蚁群算法也表现出较好的性能.郑卫国等^[8]在MMAS（Max⁃Min Ant System）的基础上根据循环中蚂蚁所选路径长度与平均值比较进行分区，对于所走路径大于平均值的蚂蚁降低其路径上的信息素浓度，相反则提高信息素浓度.吴虎发等^[9]为了解决在求解交通最短路径时蚁群算法的收敛性差和过早陷入局部最优的问题，使用方向引导以加快初始搜索速度，也降低了局部最优解的概率；同时，在全局信息素更新时设计了一个自适应因子，保证了全局搜索的正确率，实验结果也验证了算法的有效性.Liu^[10]提出运用改进的蚁群算法应用于QoS(Quality of Service)路由，研究了蚁群算法的缺陷，并从三个方面提高了蚁群算法的收敛性，使得QoS路由得到了显著优化.Cao^[11]提出了基于蚁群算法的QoS路由算法，将各种约束条件、网络负载条件和蚂蚁释放的信息素相结合，通过正确性和收敛性分析验证了该算法能有效地解决网络负载均衡问题.

但是，目前国内外大部分专家学者的研究主要集中在优化算法求解最短路径和QoS路由，很少有文献利用优化算法对现实生活中的交通车辆行驶最优路径的规划问题进行研究.

针对上述问题，本文在PTV⁃VISSIM软件中搭建了基于Petri网的多因素道路交叉口交通路网模型，使用了改进的精英蚁群算法求解交通最优路径问题，在保证收敛速度的同时，大大提升了算法搜索到最优路径的概率.本文的研究成果验证了将蚁群算法实际应用于交通最优路径问题的可行性，同时也为效率的提升提高了优化思路.

1 交通网络模型

路径问题是计算机图论中的一个重要研究点，一般在建模时都会将此类问题抽象为有向图，选择重要的节点，以此来分析节点到节点之间的路径选择.本文采用Petri网表示道路以及交叉口网络情况^[12]，并在PTV⁃VISSIM软件中搭建了有30个路口节点的城市交通网络.

1.1　道路建模

交通道路Petri网模型中，库所为路口节点，所有的路口节点的集合用P表示，则 $P_{d} (d = 1,2, \dots, n)$ 表示第d个路口；变迁为一个路口到另一个路口的路段，所有的路段集合用T表示，则 $T_{j} (j = 1,2, \dots, m)$ 表示路段j.为了便于表示和分析，用 $T_{d s}$ 和 $W (T_{d s})$ 分别表示节点d到节点s的变迁和此变迁的代价（单位：s）.在交通的实际问题中，T_ij和T_ji有着完全不一样的意义，即双向车道的交通情况通常相差悬殊，行驶的代价W(T_ij)也不同.本文基于南京仙林大学城的交通路网得到仿真数据，并对交通最优路径问题开展了研究，其交通道路Petri网模型如图1所示.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 仙林大学城交通道路Petri网模型

Fig.1 The traffic road Petri network model of Xianlin college town

1.2　交叉口建模

在研究交通最优路径问题时，尤其是市内交通，交叉口车流、信号灯等因素对整个路径规划的影响不可忽略.本文通过Petri网建立交叉口模型，且假设进入路口的所有车辆均遵照交通规则行驶.以交叉口的进口道为三车道为示例，且每个车道进入交叉口车流分为直行、左转和右转，交叉口车流示意图如图2a所示.交叉口的信号灯控制方案以常见的四相位为示例，如图2b所示.相位为0时，0,3车道的车辆右转和1,4车道的车辆直行；相位为1时，2,5车道的车辆左转；相位为2时，6,9车道的车辆右转和7,10车道的车辆直行；相位为3时，8,11车道的车辆左转.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 交叉口及信号灯相位方案抽象图

Fig.2 The abstract map of intersection and signal phase scheme

交通道路交叉口Petri网模型如图3所示.交叉口的进口道和出口道为库所集合，用P表示，则 $P_{x y} (x = n, s, w, e; y = l, c, r)$ 表示x方向道路的y进口道，而 $P_{x o}$ 则表示x方向道路的出口道（本文将出口道抽象成一条车道）；所有的交叉口转向或直行用集合T表示； $T_{x_{1} y_x_{2} o}$ 表示从进口道 $P_{x_{1} y}$ 通过交叉口行驶到出口道 $P_{x_{2} o} (x_{1}, x_{2} = n, s, w, e; y = l, c, r)$ 的转向或直行； $T_{x}$ 表示从x方向的上一个节点到该交叉口进口道入口的路段； $T_{x o}$ 表示从该交叉口x方向的出口道到下一个节点的路段； $i (P_{x y}, T_{x_{1} y_x_{2} o})$ 表示从进口道 $P_{x y}$ 经过变迁 $T_{x_{1} y_x_{2} o}$ 到达下一个路口的代价； $o (P_{x o}, T_{x_{1} y_x_{2} o})$ 表示从上一个节点经过变迁 $T_{x_{1} y_x_{2} o}$ 到达出口道 $P_{x o}$ 的代价.和道路模型一样，为了便于描述和分析，使用对应进口道到出口道转向或直行的代价用 $W (T_{x_{1} y_x_{2} o})$ 表示.

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 交通道路交叉口Petri网模型

Fig.3 The traffic road intersection Petri network model

车辆在信号交叉口，从进口道到出口的转向或直行受到信号灯的控制，即信号灯的颜色或者标志触发对应的行驶动作.例如车辆在北方向即将进入进口道，如果需要左转行驶到东方向的出口道，须进入第5进口道，即对应库所 $P_{n l}$ ，当左转绿灯亮起时，变迁 $T_{n l_e o}$ 被触发，车辆消耗一定的代价之后进入出口道 $P_{e o}$ ，随后沿着东方向驶向下一个路口节点.

上述示例及示意图均用交叉口进口道3车道及信号灯4相位控制方案，对于其他的进口道车道数和转向专用道设置方法以及不同的信号灯控制方案，此模型依然适用.

2 蚁群算法求解交通最优路径问题

2.1　交通最优路径问题

前文所述的交通路网模型中使用车辆行驶时间作为道路和交叉口转向的主权值，距离等其他因素作为辅助权值.其中，车辆在道路上的行驶时间根据车道距离和在该道路的平均行驶速度计算得到，交叉口转向的延误时间采用国际交通学经典的Webster信号交叉口延误公式计算得到^[13].在图1所示的路网中，假设车辆此时在路口 $P_{0}$ ，需要到达路口 $P_{29}$ ，则如何从 $P_{0}$ 出发找到一条路径到达 $P_{29}$ ，使得这条路径上的道路与交叉口转向的总权值在所有可能的路径中最小，这一问题称为交通最优路径问题.

2.2　蚁群算法的基本框架

蚁群算法是一种现代元启发式算法，其通过模拟蚂蚁在寻食过程中发现路径的行为解决抽象的数学问题.蚂蚁在经过的路径上留下信息素，路径越短，蚂蚁通过的时间越短，则该路径上留下的信息素越多，而蚂蚁又总是以更大的概率选择信息素更多的路径，所以会有更多的蚂蚁选择较短的路径.如此循环，蚁群寻找路径的过程就形成了一种信息素的正反馈现象，最终找到从巢穴到食物的最短路径^[14,15].

在路网模型中，有N个节点、m只蚂蚁，下面给出基本蚁群算法搜索交通最优路径的关键步骤：

（1）全局路网信息素初始化

初始化各个路段的信息素浓度，均设为：

τ_{T_{i j}} (0) = c, c 为 常 数

(1)

（2）路径选择原则

蚂蚁k（k=1,2,…,m）在当前节点i选择下一个要经过的节点j时，按照式（2）的规则进行：

j = \{\begin{matrix} a r g \underset{u ∋ a l l o w e d_{k}^{i}}{m a x} \{τ_{T_{i u}}^{α} (t) η_{T_{i u}}^{β} (t)\}, q \leq q_{0} \\ s, q > q_{0} \end{matrix}

(2)

P_{i s}^{k} (t) = \{\begin{matrix} \frac{τ_{T_{i s}}^{α} (t) η_{T_{i s}}^{β} (t)}{\sum_{u ∋ a l l o w e d_{k}^{i}} τ_{T_{i u}}^{α} (t) η_{T_{i u}}^{β} (t)}, s ∋ a l l o w e d_{k}^{i} \\ 0, s \notin a l l o w e d_{k}^{i} \end{matrix}

(3)

其中， $a l l o w e d_{k}^{i}$ 表示蚂蚁k下一步能访问的节点，即与节点i相连且蚂蚁k未经过的所有节点的集合； $τ_{T_{i j}} (t)$ 表示第t次迭代时路段 $T_{i j}$ 的信息素浓度； $η_{T_{i j}} (t)$ 表示第t次迭代时路段 $T_{i j}$ 的启发度， $η_{T_{i j}} (t) = 1 / W_{T_{i j}}$ ；α为信息启发式因子，反映信息素作用的强度，其值越大，搜索的随机性越弱，收敛越快，反之则相反；β为期望启发式因子，反映确定性因素作用的强度，其大小对搜索的随机性和收敛速度的影响和α相同；q为[0，1]间服从均匀分布的随机数； $q_{0}$ 为转移决策点， $0 < q_{0} < 1$ ,蚂蚁的状态转移采用伪随机比例规则：如果 $q \leq q_{0}$ ，蚂蚁选择当前最优路径节点；如果 $q > q_{0}$ ，按照式（3）的规则，轮盘式地搜索下一个节点.

（3）局部更新信息素浓度

蚂蚁k在完成一次搜索之后，需要根据式（4）的规则局部更新信息素浓度.

τ_{T_{i j}} (t + 1) = (1 - ρ) τ_{T_{i j}} (t) + ρ Δ τ_{T_{i j}} (t)

(4)

其中，

Δ τ_{T_{i j}} (t) = \{\begin{matrix} \frac{Q}{W_{k}}, 路 段 T_{i j} 属 于 蚂 蚁 k 选 择 的 路 径 \\ 0, 路 段 T_{i j} 属 于 蚂 蚁 k 选 择 的 路 径 \end{matrix}

(5)

ρ为局部信息素挥发因子，ρ的大小影响对蚂蚁所走路径的信息素浓度的更新程度，其值越大，算法的随机性越弱，易导致搜索快速陷入到局部最优； $Δ τ_{T_{i j}} (t)$ 为蚂蚁k完成一次搜索之后在路段 $T_{i j}$ 上的信息素释放量，若 $路段 T_{i j}$ 不在蚂蚁k选择的路径上， $Δ τ_{T_{i j}} (t)$ 为0，否则为 $\frac{Q}{W_{k}}$ ，其中Q为给定参数， $W_{k}$ 为该路径上所有道路与交叉口的权值总和.

（4）全局更新信息素浓度

当整个蚁群完成一次循环搜索后，对全局最优路径上的信息素按照式（6）进行更新:

τ_{T_{i j}} (t + 1) = τ_{T_{i j}} (t) + μ Δ τ_{T_{i j}} (t)

(6)

其中，

Δ τ_{T_{i j}} (t) = \{\begin{matrix} \frac{1}{W_{g l o b a l b e s t}}, 路 段 T_{i j} 属 于 全 局 最 优 路 径 \\ 0, 路 段 T_{i j} 属 于 全 局 最 优 路 径 \end{matrix}

(7)

μ为全局信息素更新因子，反映算法的全局搜索能力，值越大，信息素的正反馈效果越明显，搜索的随机性也越弱；值越小则收敛速度越慢，搜索的随机性增强. $Δ τ_{T_{i j}} (t)$ 为整个蚁群完成一次循环搜索之后在路段 $T_{i j}$ 上的信息素释放量，若路段 $T_{i j}$ 不在全局最优的路径上， $Δ τ_{T_{i j}} (t)$ 为0，否则为 $\frac{1}{W_{g l o b a l b e s t}}$ ，其中 $W_{g l o b a l b e s t}$ 为全局最优路径的道路与交叉口转向的权值总和.

（5）更新全局最优解

在每一次循环中，记录整个蚁群的搜索到的最优路径，并通过最优路径的权值总和，更新当前迭代位置的全局最优路径，如此反复，直至迭代结束.

3 基于精英策略的改进蚁群算法

大量研究发现，基本蚁群算法很难同时解决收敛速度慢和局部停滞这两个问题^[16]，但现在的自驾出行甚至是无人驾驶中，计算响应速度快和行驶路径质量高，两者均不可妥协，所以本文提出对信息素初始化规则和全局信息素更新策略进行优化.

3.1　信息素初始化规则优化

在交通车辆出行中，车道数多、车流速度快的主干道容易被选择，而车道数少、车流速度慢的路段则相对较少被选择，因为经验证明大多数情况下，前者的行驶时间、道路情况、意外事件等成本会更低.根据这一思路，本文提出在信息素初始化时加入主干道引导规则，即对于多车道、高车速的主干道给予更多的初始信息素浓度，引导蚂蚁从这些路径经过，从而加快算法的收敛速度.

另一方面，考虑到几何学规则，车辆在行驶过程中，行车方向越趋近于终点方向，则行驶距离越短.如图4所示，若沿着路段 $T_{i j}$ 行驶，S和E分别为出发位置和目的位置， $θ_{1}$ 、 $θ_{2}$ 分别为E和节点j相对S的方向角； $Δ θ$ 为E、j和S形成的夹角， $Δ θ$ 越小，则沿着路段 $T_{i j}$ 的行驶方向越靠近终点E，行驶距离越短，在其他条件相同的情况下，相应消耗的代价也越小.

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 行车方向引导原理图

Fig.4 Schematic diagram of driving direction guidance

方向角 $θ_{1}$ 和 $θ_{2}$ 可根据式（8）计算得到：

\begin{matrix} θ = a t a n^{- 1} \frac{s i n Δ λ c o s φ_{2}}{c o s φ_{1} s i n φ_{2} - s i n φ_{1} c o s φ_{2} c o s Δ λ} \\ - π \leq θ \leq π \end{matrix}

(8)

其中， $φ_{1}$ 和 $φ_{2}$ 分别为两个节点的纬度， $Δ λ$ 为两个节点的经度之差.

根据此原理，本文在信息素初始化时加入行车方向引导，即如果某个节点与出发位置、目的位置形成的几何夹角越小，该节点所在的道路将获得更多的初始信息素.

综合上述两个思路，将初始化信息素公式修改为：

τ_{T_{i j}} (0) = c + \frac{n}{\bar{n}} \times \frac{v}{\bar{v}} \times c + \frac{\frac{π}{2} - Δ θ}{\frac{π}{2}} c

(9)

式中第一项为固定部分；第二项为主干道引导带来的信息素增量，n, $\bar{n}$ 分别为当前路段 $T_{i j}$ 的车道数和路网平均车道数，v, $\bar{v}$ 分别为当前路段 $T_{i j}$ 的车流速度和路网平均车流速度；第三项为行车方向引导带来的信息素增量， $0 \leq Δ θ \leq π$ .

3.2　全局信息素更新策略优化

基本蚁群算法框架中，在整个蚁群一次迭代完成后，仅仅对本次迭代的最优路径进行信息素更新，而单次迭代的最优解的偶然性较大，容易造成算法过早陷入局部最优，这一全局信息素更新策略显然过于粗糙.针对这一问题，Dorigo et al^[17]使用精英策略优化算法，在显著加速收敛的同时也能保证搜索到最优解的概率.但本文经过分析发现，这一策略依然存在较大的概率提前收敛，因为经过十几次迭代之后，精英蚂蚁所选路径上的信息素浓度得到增加，如果该路径并非全局最优路径，则此后的过程中蚁群选择其他路径的概率还是很小.

针对这个问题，本文采用了双精英蚂蚁策略，并采用相互约束的方式更新两只精英蚂蚁所选路径上的信息素浓度，进一步降低过早陷入停滞的概率.同时，在新的交通路网模型中，最优路径的规划考虑的是多个因素，双精英蚂蚁策略使得算法最终能得到两个最优结果，这两个结果中各个因素的量化权值可能不同.本文仅考虑出行时间和行驶距离，亦可拓展到路面状况、过路费以及路段意外事故概率等多个因素，所以这一策略还能够满足车辆出行的差异化需求.

整个蚁群完成一次循环后，对两只精英蚂蚁搜索到的最优路径同时进行信息素更新，并且在式（7）基础上增加约束项：

∆ τ_{T_{i j}} (t)' = ∆ τ_{T_{i j}} (t) + \frac{W_{g b 2} - W_{g b 1}}{\frac{1}{2} (W_{g b 1} + W_{g b 2})} ∆ τ_{T_{i j}} (t)

(10)

即：

∆ τ_{T_{i j}} (t)' = \{\begin{matrix} \begin{array}{l} \frac{3 W_{g b 2} - W_{g b 1}}{W_{g b 1} \times W_{g b 2} + {W_{g b 2}}^{2}}, \\ 路 段 T_{i j} 属 于 全 局 最 优 路 径 1 \end{array} \\ \begin{array}{l} \frac{3 W_{g b 2} - W_{g b 1}}{W_{g b 1} \times W_{g b 2} + {W_{g b 1}}^{2}}, \\ 路 段 T_{i j} 属 于 全 局 最 优 路 径 2 \end{array} \\ \begin{array}{l} 0, \\ 路 段 T_{i j} 不 属 于 全 局 最 优 路 径 \end{array} \end{matrix}

(11)

式中， $∆ τ_{T_{i j}} (t)'$ 为优化之后整个蚁群完成一次循环搜索之后在路段 $T_{i j}$ 上的信息素释放量； $W_{g b 1}$ 和 $W_{g b 2}$ 分别为全局最优路径1和2的权值之和，且 $W_{g b 1} \leq W_{g b 2}$ .采用式（11）的方式分别增加两条全局最优路径的信息素浓度，可以使得最优路径1相较于最优路径2上的信息素浓度得到更多的增量，同时又相互约束，避免由于偶然性造成的算法过早停滞.

4 算法仿真分析

实验采用图1的交通网络来进行算法的仿真，寻找从起始点 $P_{0}$ 到终点 $P_{29}$ 的车辆行驶最优路径，与基本蚁群算法（ACO）以及精英蚁群系统（EAS）进行对比分析.蚁群算法的参数很多，如前文分析，这些参数的取值主要影响算法的随机性和先验性，本文基于相关文献^[8]及开源资料的使用参数，进行了参数实验与调试使得三种算法能够尽量保证收敛速度和求解到最优解的概率，最终选择的全部参数如表1所示，并使用相同的参数值对算法进行了仿真对比分析.

表 1 算法参数

Table 1 Algorithm parameters

参数类型	数值
信息启发式因子α	2
期望启发式因子β	2
局部信息素挥发因子ρ	0.15
全局信息素更新因子μ	50
局部信息素更新参数Q	100
转移决策点 $q_{0}$	0.02
蚂蚁数量m	24
最大迭代次数I_max	200
重复试验次数M	100
初始化信息素浓度 $τ_{T_{i j}} (0)$	0.5

新窗口打开| 下载CSV

在30节点的交通网络中，全局最优路径的总权值为968.566.仿真实验结果如表2所示，从表中对比数据可以看出，基本蚁群算法（ACO）在约14次迭代后就陷入停滞，且100次仿真实验中，仅有19次搜索到了全局最优路径；传统的精英蚁群系统（EAS）将得到全局最优解的概率大幅提升，但56%的结果依然不高，同时迭代次数也提高到了约29次；与此对比，本文的算法在约32次迭代次数的同时，得到最优解的概率达到100%，每次都可以搜索到最优路径.这说明双精英蚂蚁策略能够在提高收敛速率的同时显著避免提前陷入停滞，而在路径信息素初始化时加入主干道引导和行车方向引导能够有效地加快初始搜索速度，使得仿真中算法的平均迭代次数几乎没有增多.

表2 30节点交通网络仿真结果对比

Table 2 Simulation results on of 30⁃node traffic network

性能指标	最优解	最差解	平均解	得到最优解概率（%）	平均迭代次数
本文算法	968.566	968.566	968.566	100	32.616
ACO	968.566	1219.490	1035.640	19	13.700
EAS	968.566	1060.180	1003.038	56	29.333

新窗口打开| 下载CSV

本文算法与基本蚁群算法以及经验蚁群系统的收敛性分析对比如图5所示.100次重复实验数据证明，本文算法的初始求解结果明显优于ACO算法和EAS算法，这得益于信息素初始化的改进.在经过和EAS近乎相等的迭代次数之后，本文算法开始收敛，虽然收敛速度略慢于ACO，但是收敛值等于交通路网的最优路径的权值，即能保证得到全局最优解.

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 收敛性对比图

Fig.5 Diagram of converegence comparison

为了更直观地比较三种算法的收敛速度（表3），通过微调参数，增大ACO算法和EAS算法的搜索随机性，使得到最优解的概率大于90%.其中，ACO算法中，参数α调整为1，参数μ调整为25，参数 $q_{0}$ 调整为0.01；EAS算法中，参数β调整为1，参数μ调整为25,两种算法的最大迭代次数均调整成500次，通过收敛速度对比，明显发现在同样保证90%以上的得到最优解的概率的基础上，本文算法的收敛速度约为ACO算法的五倍，EAS算法的两倍.这一分析结果充分证明了本文算法的有效性.

表 3 三种算法的收敛速度对比

Table 3 Convergence rate comparison of three algorithms

性能指标	平均解	得到最优解概率（%）	平均迭代次数
本文算法	968.566	100	32.616
ACO	979.944	90	146.421
EAS	974.255	92	61.105

新窗口打开| 下载CSV

5 结论

本文首先介绍了当前研究交通路径问题时所采用的交通路网模型的不足，并提出了基于Petri网的多因素道路交叉口交通路网模型.从道路和信号交叉口两个部分建模，以保证研究交通路径问题时的工程可行性和结果精确性.在此模型基础上，采用了改进的精英蚁群算法求解交通最优路径问题.实验结果证明，本文的模型相较于传统的静态交通路网模型更加精确，本文的算法在加快了收敛速度的同时，大大提高了搜索结果的正确率，是一种有效的求解交通最优路径的算法.然而，蚁群算法具有高度并行性的特点，本文的算法未采用并发或分布式编程；此外，本文未验证算法对于不同规模交通网络中计算最优行驶路径的适应性.未来的工作将从这两个方面入手，进行算法的进一步优化及适应性验证.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Dantzig

G B

， Ramser

J H

The truck dispatching problem

Management Science，1959，6(1)：80-91.