基于社区发现的动态路径规划问题研究

发布时间：2017-09-07 06:22

  本文关键词：基于社区发现的动态路径规划问题研究

  更多相关文章： 车辆导航 动态路径规划 社区发现 分层搜索

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

• 摘要4-5
• ABSTRACT5-9
• 第1章 绪论9-17
• 1.1 课题背景及研究意义9-10
• 1.2 国内外研究现状10-15
• 1.2.1 车辆导航系统10-12
• 1.2.2 路径规划算法12-15
• 1.3 论文主要内容及安排15-17
• 第2章 路径规划算法17-25
• 2.1 经典算法及基本加速技术17-18
• 2.1.1 经典最短路径算法17
• 2.1.2 基本加速技术17-18
• 2.2 基于目标引导的加速技术18-22
• 2.2.1 基于剪枝思想的目标引导技术18-19
• 2.2.2 基于A~*算法的目标引导技术19-21
• 2.2.3 基于子目标的目标引导技术21-22
• 2.3 基于分层技术的加速算法22-24
• 2.3.1 基于道路等级的分层方法22-23
• 2.3.2 基于节点缩减的分层方法23-24
• 2.3.3 基于图分割的分层方法24
• 2.4 本章小结24-25
• 第3章 基于社区发现的分层路径规划算法25-39
• 3.1 时间依赖的路网模型25-27
• 3.2 基于社区发现的路网分层方法27-31
• 3.2.1 社区发现27-28
• 3.2.2 路网分层28-30
• 3.2.3 动态环境下的分层路网局部调整30-31
• 3.3 基于社区发现的分层路径规划算法31-34
• 3.4 基于分层搜索的改进蚁群算法34-38
• 3.4.1 蚁群算法数学模型35-36
• 3.4.2 期望启发函数的改进36
• 3.4.3 信息素更新规则的改进36-37
• 3.4.4 参数的改进37-38
• 3.5 本章小结38-39
• 第4章 实验结果与分析39-51
• 4.1 实验环境39-41
• 4.2 路网分层结果41-42
• 4.3 分层路径规划算法的性能测试42-45
• 4.4 不同场景下的路径规划算法的仿真45-47
• 4.4.1 道路施工场景46-47
• 4.4.2 交通事故场景47
• 4.5 动态环境下算法的性能测试47-50
• 4.5.1 目标引导技术存在的问题48-49
• 4.5.2 改进的蚁群算法的实验与分析49-50
• 4.6 本章小结50-51
• 结论51-53
• 参考文献53-58
• 攻读硕士学位期间发表的论文及其它成果58-60
• 致谢60

【相似文献】

中国期刊全文数据库 前10条

1 杨正磊;宋建社;吴永定;郭军;;多约束条件下战场导航路径规划问题研究[J];系统仿真学报;2011年06期

2 艾海舟,张钹;基于拓扑的路径规划问题的图形解法[J];机器人;1990年05期

3 陈刚,沈林成;复杂环境下路径规划问题的遗传路径规划方法[J];机器人;2001年01期

4 普措才仁;;一种新的编码方法解决路径规划问题[J];工业仪表与自动化装置;2011年01期

5 鲁子卉;;基于Memetic算法的电子AGV路径规划[J];四川兵工学报;2013年02期

6 黄建华,方毅,黄樟灿,吴方才;基于演化计算的广义路径规划问题[J];武汉理工大学学报(信息与管理工程版);2001年02期

7 李晋航;黄刚;贾艳;;多模糊信息条件下的物料配送路径规划问题研究[J];机械工程学报;2011年01期

8 杨丽英;吴成东;韩建达;聂义勇;;多目标追逐问题的一种混合整数线性规划解[J];机械工程学报;2008年10期

9 李梅娟;陈雪波;张梅凤;;基于群集智能算法的路径规划问题[J];清华大学学报(自然科学版);2007年S2期

10 欧微;李志凌;;基于混沌优化算法的车辆路径规划问题研究[J];科学技术与工程;2010年29期

中国重要会议论文全文数据库 前1条

1 王旭;张江;崔平远;;一种基于蚁群算法求解路径规划问题的新方法[A];2003年中国智能自动化会议论文集（下册）[C];2003年

中国博士学位论文全文数据库 前2条

1 张兴;信使机制UAV/UGV多点动态集结的协同规划方法研究[D];北京理工大学;2015年

2 王沛栋;改进蚁群算法及在路径规划问题的应用研究[D];中国海洋大学;2012年

中国硕士学位论文全文数据库 前10条

1 王晨;基于社区发现的动态路径规划问题研究[D];哈尔滨工业大学;2016年

2 袁斌;带访问限制的需求时变的移动设施路径规划问题研究[D];清华大学;2014年

3 赵再兴;基于改进和声搜索算法的车辆路径规划问题[D];沈阳大学;2011年

4 王星;基于蚁群算法的图书物流车辆路径规划问题研究[D];武汉理工大学;2011年

5 吴颖;双层车库车辆调度辅助决策支持系统[D];华中科技大学;2011年

6 玉坤;蚁群算法在路径规划问题中的应用研究[D];北京工业大学;2012年

7 弓晨;三维曲面上路径规划问题的研究[D];中国地质大学;2006年

8 周晴红;智能Avatar在IVE中行走运动控制及其路径规划问题的研究[D];浙江师范大学;2006年

9 冯超;基于以太网和TCP/IP的IEC60870-5-104协议的性能分析[D];上海交通大学;2007年

10 马乐;VMI环境下库存运输联合优化问题的研究[D];重庆大学;2008年

，

本文编号：807912