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