基于蚁群算法的最优路径选择研究

近年来,智能交通系统(Intelligent Transportation System,ITS)越来越受到人们的重视,它在当代科学技术充分发展的背景下产生,旨在将先进的计算机技术、通信技术、数据库技术、人工智能技术等运用于交通运输中,以解决交通拥挤、保证交通安全、提高交通网络使用效率等问题。智能交通涉及到交通领域的多个方面,最优路径的选择就是其中的一个重要应用。 出行者在出行之前,感兴趣的是从起点到终点如何找到一条最优路径。传统的最优路径算法以Dijkstra算法为代表。这些算法均属于贪心算法,存在典型的局部最小问题,是一种静态的局部最优算法。当前的实际交通网络数据规模庞大,算法需要提前将整个交通数据导入才能进行路径的选择。这样显然不能反映出交通中不断变化的道路实际情况对交通路径选择的影响。蚁群算法是一种新兴的模拟仿生算法,算法具有模拟生物界群体觅食的能力,并且能够在实际的路径搜索过程中对外界的影响做出动态的响应,因而在交通最优路径选择中具有极大的可行性与适应性。 论文综合分析了当前道路交通中在路径选择方面存在的问题,介绍了路径选择算法的国内外研究现状;讨论研究了当前路径选择的几种经典的算法,分别研究了Dijkstra算法、Floyd算法以及其他几种最优路径算法。从算法的基本思想、算法过程、具体实现以及算法分析等方面探讨了算法的优缺点。在以上几种经典最优路径算法的基础上结合蚂蚁觅食行为引入新的算法—蚁群算法。并进一步研究了蚁群算法的基本原理和在交通最优路径选择中的应用与实现过程。通过系统开发实现了将蚁群算法应用于路径选择。