【作者】 陈艳；

【导师】 何春明；

【作者基本信息】 北京交通大学 ， 智能交通工程， 2007， 硕士

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

【Abstract】 In recent years, Intelligent Transportation System (ITS) has been paid more and more attention. It was given birth to in the background of contemporary science and technology fully developed which seeks to introduce advanced computer technology, communication technology, database technology and Artificial Intelligence to transportation so as to solve the traffic congestion, ensure the safety and improve the efficiency of traffic network. ITS involves many aspects of traffic field. And in these aspects, one important application is the choosing of the optimal path.Before starting off, people are interested in how to find an optimal path from the start point to end point. The traditional optimal algorithms were represented by Dijkstra algorithm. These are all greedy which are static local optimal algorithm and have typical local optimization problem. At present, the scale of real traffic data is huge. And it should be loaded in advance of algorithm carried out into the path chosen. Obviously, this cannot reflect the actual continuous situation of traffic on path chosen. Ant Colony Algorithm is a new bionic simulation algorithm. It has the capability in simulating colony cooperation and finding a shortest path from nest to food, which could respond dynamically to external affection in the routing search process. So it has infinite feasibility and flexibility in the optimal path chosen of traffic.This paper analyzed the problems in traffic path chosen generally, presented the researching status of algorithm in and out of China, discussed and researched the traditional algorithm of optimal path chosen, which contained Dijkstra Algorithm, Floyd Algorithm and others. And the algorithm’s advantages and disadvantages were discussed from basic idea, algorithm process, idiographic implement and algorithm analysis. Combined these several traditional optimal path algorithms and ant foraging behavior, a new algorithm was introduced, that was Ant Colony Algorithm (ACA). And then further researched the ACA’s basic principles and the application and implementation process of traffic optimal path chosen.更多还原