【作者】 荆长林；

【导师】 陈旭梅；

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

【摘要】 随着社会的发展与进步,城市规模在不断的扩大,交通网络越来越复杂,并且出现了大规模性、动态性等新的特征,传统最短路径搜索无法满足居民快捷出行的动态服务需求。近年来,浮动车采集技术被应用于交通管理与控制,同时积累了大量的数据,为获取路网的动态运行特征提供了基础,因此研究动态特征下的大规模路网最短路径搜索具有理论和实践意义。经典的最短路算法如Dijkstra算法、Floyd算法等多应用于静态路网的前提下,且并行化特性差,很难高效地求解动态最短路问题,因此本文的研究主题是基于分布式蚁群算法求解大规模路网下面向小汽车最短出行时间的动态最短路径搜索问题。论文首先通过对比分析,选择蚁群算法作为动态路径搜索算法,并对其基本原理、研究现状和并行计算模型进行研究综述；随后对浮动车数据获取路段平均速度方法进行研究,提出了利用多个浮动车样本的行驶时间和距离加权集成的方法获得短时的路段平均速度,作为动态路径选择的基础；其次根据大规模路网的特性,针对基本蚁群算法计算时间长、局部收敛的问题提出了单只蚂蚁路径选择优化和自适应信息素更新两种改进策略；然后在研究了分布式计算理论和蚁群算法并行化特点的基础上,设计了主从式定期交互和广播式触发交互结合的并行策略,并利用基于消息的MPI编程模型在MPICH2平台下实现了并行算法的开发；最后介绍了所开发的分布式计算实验平台和进行蚁群算法关键参数的选择,在此基础上设计多次路径搜索实验,实验结果表明该方法在运行时间和计算结果方面都具有明显的优势,具有良好的实用性。更多还原

【Abstract】 With the social development and progress, the cities are keeping expanding. Traffic networks in large cities become more and more complex and present some new features with large-scale and dynamic characteristics. Traditional shortest path search cannot meet residents’ dynamic service demand on fast travelling. In recent years, floating car technology has been applied widely in the traffic management and control area and a great deal of data are accumulated. This provides foundations for the researchers to obtain the dynamic road network features. Therefore, the research on the dynamic shortest path search has a high theoretical and practical significance. The classic shortest path search algorithms, such as Dijkstra algorithm and Floyd algorithm, are widely used in static network and difficult for parallel computing, which make them difficult to efficiently solve the dynamic shortest path problem. Therefore, this thesis has focused on using distributed ant colony algorithm to solve the dynamic shortest path search problem in large scale network to meet the car travelers’ requirement for the shortest travel time.Firstly, by comparing with other algorithms, ant colony algorithm (i.e. ACO) is selected for dynamic path search and the basic principle and researches on ACO algorithm, as well as parallel computing model are reviewed. Secondly, the research on how to aggregate section average velocity with floating car data is conducted. The travel time and distance weighted aggregation method using samples of floating car records to obtain the time-varying average section speed is proposed, which provides the basis for dynamic path search. Thirdly, according to the characteristics of large-scale network, two improvement strategies of ACO algorithm are put forward to reduce the computing time and avoid the local convergence. One is the optimization of single ant routing and the other is adaptive pheromone update strategy. Then, based on the theory of distributed computing and the characteristics of parallel ACO algorithm, a parallel program of master-slave type regular interaction method combined with radio type trigger interaction method among sub ant colonies is designed. MPI programming model is used to develop parallel ACO algorithm in MPICH2platform. Finally, the method to build the distributed computing platform is introduced and key parameters of ACO algorithm are selected. Experiments on multiple path search are conducted. The experimental results show that the developed algorithm has obvious advantages in both of running time and calculation results, which proves its high performance.更多还原