基于蚁群算法的实时最优路径算法

张水舰

摘要：在实时交通网络中的路径寻优问题是ITS的关键问题之一。在该文中，构建了实时交通网络模型；并基于交通网络的特点，提出了一种实时最优路径蚁群算法。仿真实验表明，文中提出的算法能为出行车辆找到有效的实时最优路径。此算法的运用对改善拥堵的交通状况有一定的积极意义。

关键词：实时最优路径；蚁群算法；实时交通网络

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2017）30-0178-03

Real-time Optimal Path Algorithm Based on Ant Colony Algorithm

ZHANG Shui-jian

（Huzhou Vocational and Technical College， Huzhou 313000， China）

Abstract： The optimal path problem in real-time traffic networks is one of the key problems of ITS. In this paper， the real-time traffic network model was constructed. A real-time optimal path algorithm was proposed Based on the improved ant colony algorithm taking account of the traffic network characteristics. The results of simulation experiment show that the proposed algorithm can find an effective real-time optimal path for the travel vehicle. The application of this algorithm in intelligent transportation system may be significant to relieving the congestion situation in traffic network.

Key words： Real-time optimal path； Ant colony algorithm； Real-time traffic network

1 概述

在交通网络中给出行者找到最优出行路线，不仅能使出行者快捷地到達目的地，宏观上还能起到调节交通流，提高整个交通系统的效率，从而缓解交通拥堵的作用。在实际交通网络中，交通网络上的交通状况往往会随着时间发生变化，比如在上下班高峰期某些路段比平时拥堵。城市交通网络的规模越来越大的，最优路径问题面临新的挑战。对于复杂的实时网络，传统算法已不能满足要求[1] [2]。而智能算法模型简单，对目标函数的约束少，实践证明在一些结构复杂的优化问题中表现出优良的性能，可以运用智能算法来求解实时路径寻优问题[3-5 ]。

2 实时最优路径模型

2.1 实时路网模型

可用网络模型[G：{V，E，Wet}]来表示一个实时交通网络，其中，[V]为路网节点的集合，

[V=1，2，…，n|n为节点编号]；E为路段的集合，[E∈V×V=ei，j|i≠j， i，j∈V]；[Wet]表示路段[e]在时刻[t]的阻抗函数，以行程时间表示。交通网络上的路段在不同的时间段交通状况可能会发生变化，路段上的行程时间也会随之发生变化，称此类交通网络为实时交通网络。

4 仿真实验分析

我们对以上所述算法进行了仿真实验，以某一交通网络作为实验对象，选定某一时间段为研究时间区域（7：00AM-8：00AM），对研究时间区域进行离散化处理，以5分钟为时间间隔，于是一个小时的时间区域可离散为12个时间段，每5分钟更新一次交通信息，通过此方式模拟交通信息发布平台更新实时交通信息，如模拟某路段发生交通堵塞，并给出堵塞可能持续的时间，如果已规划好了的最短路径正好经过该路段上，则更新该路段上的信息素，并触发诱导算法重新规划路径。

以地理信息系统软件ArcGIS10.2为平台的电子地图数据库为基础，C#作为开发工具编程实现此算法。选取算法参数为： 蚁群数量[pop_size] =30，初始信息素量[τc=10]，每次迭代蚂蚁留在路径上的信息量[Q=100]，信息量残留系统[ρ=0.8]，参数[α=1]，参数[β]=2。在实验交通网络上随机选取了三组起终点，模拟交通状况发生变化的情况下进行实时路径求解实验，每组计算了三次，计算结果如表1所示。实验结果显示本文提出算法有良好的收敛性和有很高的效率，比基本蚁群算法的求解性能有明显的改善。

5 结论

交通网络上的交通状况是会随时间发生变化，传统最优路径算法不能适应交通网络的实时性。在交通网络经常发生拥堵的情况下研究实时最优路径问题具有十分重要的现实意义。本文分析研究了交通网络的空间分布特性以及交通路状的实时性，对蚁群算法适用于优化问题的特点进行了分析，并根据交通网络的特性提出了一种实时最优路径蚁群算法。为了评估所提出的算法的性能，文中给出了一个实验来测试新算法，测试结果表明文中所提出的算法具有良好的收敛性和运行效率，说明新算法切实可行。

参考文献：

[1] Dijkstra E W. A note on two problems in connection with graphs[J]. Numerische Mathematik， 1959， 1（1）：269-271.endprint

[2] Bellman E. On a routing problem[J]. Quarterly of Applied Mathematics， 1958，16（1）：87-90.

[3] 潘曉萌， 李冰. 蚁群算法优化和路径规划问题的应用研究[J]. 科技通报， 2016， 32（6）：99-103.

[4] 郭胜国， 邢丹丹. 一种改进蚁群算法在机器人路径规划中的应用[J]. 科技通报， 2015， 31（12）：91-93.

[5] Fouad A， Boukhetala D， Boudjema F， Zenger K， Gao X Z. A novel global Harmony Search method Based on Ant Colony Optimisation algorithm[J]. Journal of Experimental & Theoretical Artificial Intelligence， 2016， 28（1-2）：215-238.

[6] Colorni A， Dorigo M， Maniezzo V， Trubian M. Ant system for job-shop scheduling[J]. Belgian Journal of Operations Research， Statistics and Computer Science， 1994， 34（1）：39-53.

[7] Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B （Cybernetics）， 1996， 26（1）：29-41.

[8] Dorigo M， Birattari M， Stutzle T. Ant colony optimization[J]. IEEE computational intelligence magazine， 2006， 1（4）：28-39.endprint