基于改进蚁群算法的最短路径问题研究

《自动化技术与应用》２００９年第２８卷第６期

控制理论与应用

Control Theory and Applications

基于改进蚁群算法的最短路径问题研究*

张学敏,张 航

（中南大学 信息科学与工程学院,湖南 长沙 410075）

摘 要:最短路径问题是智能交通:交通网络分析中的一个重要问题。文章分析了基本蚁群算法在求解交通网络两点之间最短路径时

所出现的问题,并针对这些问题,在方向引导及信息素更新等方面对算法进行了改进。实验证明,改进后的方法较基本蚁群算法能准确快速地找到交通路网中两点间的最短路径,是切实可行的。

关键词:智能交通;最短路径;蚁群算法

中图分类号:TP301.6 文献标识码:A 文章编号:1003-7241(2009)06-0004-04

Research An Improved Ant Colony Algorithm of the

Optimal Routing Problem

ZHANG Xue-min, ZHANG Hang

( School of Information Science and Engineering, Central South University, Changsha 410075 China )

Abstract: Search for the shortest path in transportation network is one of the most important problem of ITS. This paper analyzes

the basic ant colony algorithm and presents an improved algorithm on the heuristic direction information and renewal ofpheromone. The results of the experimentation proved that the improved algorithm could find the shortest path moreaccurately and quickly than the basic algorithm, and it’s feasible.

Key words: intelligent transport system(ITS); shortest path; ant colony algorithm

1 引言

最短路径问题是智能交通中交通网络分析中的一个重要问题,也是一个研究热点。它是资源分配、路线设计及分析等优化问题的基础,具有重要理论意义和实际应用价值。有许多研究者曾对最短路径算法进行了大量的研究,并取得了很大的进展,提出了很多解决这类问题的方法。其中传统的算法有,Dijkstra算法、A*算法及其改进算法等等;还有近几十年来,通过模拟或揭示某些自然现象而产生了一些新颖的启发式智能算法,如遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法等。

城市道路网中的交叉路口,连接两节点之间的边表示道路路线,并将路线的长度、通行时间、路况等属性表示为该边的权值,那么就可以把道路网络抽象为一个带权有向图。

给定一个带权有向图G为二元组G=(V,{E}),其中V是包含n个节点的集合,E是包含h条边(弧段)的集合,<i, j>是E中从节点i至j的边,wij是边<i,j>的非负权值。设S,T 分别为V中的起始节点和目标节点,则最优路径问题就是指在带权有向图G中,寻找从指定起始节点到目标节点的一条具有最小权值总和的路径。

2 交通最短路径问题描述

城市道路网有道路路线、交叉路口等物理属性,同时也具有路线长度、通行时间、路况等各种其它逻辑属性。用节点来表示

3 蚁群算法的基本原理及存在的问题

蚁群算法就是受蚂蚁觅食行为的启发,以人工蚂蚁模拟真实蚂蚁行为来求解组合优化问题的方法。在20世纪90年代初期,由意大利学者Dorigo Macro等首先提出[1] 。其原理在于[5],蚂

＊基金项目：湖南省科学技术与科技计划（编号２００６ＧＫ３１３０）；湖南省自然科学基金奖资助项目（编号０５ＪＪ３０１２１）收稿日期：２００８－１１－１０

T蚁在所经过的路径上留下一种称为信息素的挥发性分泌物,在觅食过程中蚂蚁能够感知这种物质的存在及其强度,并以此来指导