周竹萍 易富君

1.南京理工大学，交通工程系，南京 210094

2.招商局重庆交通科研设计院有限公司，重庆 404100

0 引言

动态最优路径搜索算法是智能交通系统（ITS）技术应用的关键问题之一。目前的路径诱导系统不够高效，在路径选择算法方面还不完善，缺乏实时性高、有效性强的路径搜索算法，故交通最优路径选择问题一直是各国交通领域投资研究的重点问题。

最优路径选择是指在给定的城市道路网中寻找一条从起始点到目标点之间的最优路径的问题。解决该问题的经典算法是Dijkstra 算法，是一种静态的局部最优算法[1]。该算法简单、易于实现，但也存在如下的局限性：在网络节点和路径较多的情况下，搜索效率会大大降低，有时甚至找不到最短路径，且对于路径权值随时间动态变化的动态网络，如反映路径堵塞和畅通信息的实时交通系统网络就不适用。

随着群智能技术的出现，基于群体仿生理论的蚁群算法为最短路径选择问题提供了一个新的解决方法。但是，由于蚁群算法本身的局限性，容易陷入局部最优解，且其道路信息素初始值固定，使算法收敛速度较慢[2]。近年来，我国学者提出了一系列的改进思路，如高尚、吴霜华等都考虑在蚁群算法中引入混沌理论[3-4]，黄贵玲则在原始算法中加入直线优化启发信息，赵宝江提出了一种基于自适应路径选择和动态信息素更新的蚁群算法[5]。国外的重要研究包括：Guenther Fuellerer，Yuvraj Gajpal等也在信息素局部更新中加入几种其它启发式算法以提高算法效率，Alberto V.Donati 通过改进更新规则完成了两个及多个目标的优化[6-8]等。……