原文传递
基于社区发现的动态路径规划问题研究
| 论文题名： | 基于社区发现的动态路径规划问题研究 |
| 关键词： | 车辆导航;路径规划;社区发现;分层搜索 |
| 摘要： | 近年来，国内经济的迅速发展带来了交通需求的日益增长，交通拥堵已经成为大中城市交通的普遍现象，这影响了人们出行的安全与效率。车辆导航系统在此背景下变得越来越重要，车辆导航系统可以通过提供给出行者有效的路径规划方案来解决道路的拥堵状况。车辆导航系统核心的功能是在短时间内给出一条最优或近似最优的出行路径，这对路径规划算法的实时性和准确性提出了很高的要求。 由于交通网络规模庞大，传统的路径规划算法不能很好地应用于车辆导航中。目前对导航领域路径规划算法的研究都会结合分层技术，通过分治与划分，把网络划分为多个子网从而降低搜索空间的范围使传统算法能够很好的应用。社区发现能够发现网络中的社区结构，将联系紧密的节点组成一个社区，联系稀疏的节点组成不同社区，从而形成层次化的结构。本文基于社区发现思想研究了对交通路网分层的策略和基于分层路网下的动态路径规划算法，主要研究内容和结果如下： 以通行时间为相似性标准对路网进行分层，抽象出基于社区发现的多层交通路网模型。在此模型的基础上提出了一个分层路径搜索策略，在该策略中优先对稀疏的高层路网进行搜索，将高层搜索的结果作为低层的搜索范围，根据多层路网模型由高到低逐层减小搜索范围，使实际路网的搜索区域被限定在一个很小的范围中。而且该策略中每一层是独立搜索的，在实现的时候可以根据需要进行不同的调整。将该策略进行算法实现并应用到福州市交通路网进行实验仿真，结果表明，该策略不仅降低了搜索范围，提高了搜索效率，同时提高了大区域搜索时的精准度。 将本文提出的分层路径搜索策略应用到不同交通场景进行实验仿真，如道路施工、交通事故等，对路网分层结构进行动态局部调整并进行重新规划。实验表明本文提出的策略能够使车辆有效地规避道路施工、交通事故等路段。 在基于社区发现的分层搜索策略的基础上，针对动态环境下车辆行驶一段时间后路况变化而导致车辆在行驶过程需要经常重新规划路径的问题，引入历史统计数据因素，对动态实时路况进行分析。对蚁群算法进行改进并应用到本文提出的分层搜索策略的第一层路径搜索中，仿真实验表明改进后的蚁群算法提高了路径的搜索精准度。 |
| 作者： | 王晨 |
| 专业： | 计算机技术 |
| 导师： | 潘正祥 |
| 授予学位： | 硕士 |
| 授予学位单位： | 哈尔滨工业大学 |
| 学位年度： | 2016 |
| 正文语种： | 中文 |
检索历史
应用推荐
