基于GIS的大规模数据下K优路径规划算法的研究与实现

发布时间：2017-09-02 18:23

  本文关键词：基于GIS的大规模数据下K优路径规划算法的研究与实现

  更多相关文章： Kth路径 Dijkstra算法 有利度 大规模数据 地图缓冲

【摘要】：路径规划问题是地理信息系统(GIS)研究领域中的关键内容之一,最短路径的寻找更是热点问题。在数据量较大时,传统前K条最短路径算法效率较低,且不能解决某些实际需求下规划K条差异较大的路径问题。以Dijkstra算法为预处理,为有向图的节点引入有利度的概念,通过对路径结果重复度的检测以及改变有利度引起图的变化,循环使用A*算法寻找当前图中的最佳路径,从而实现了Kth条差异路径的规划。使用的A*算法时间复杂度较低,所以与同类算法相比,效率较高,得到的Kth条路径结果在满足一定重复度要求的同时长度也较为合理。同时针对大规模数据量下多次路径规划下路段拓扑路径规划系统的效率低下的问题,提出地图缓冲算法,优化了路段拓扑,提升路径规划系统总体效率。
【关键词】：Kth路径 Dijkstra算法 有利度 大规模数据 地图缓冲
【学位授予单位】：北京理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：P208;TP301.6
【目录】：

• 摘要6-7
• Abstract7-10
• 第1章 绪论10-14
• 1.1 研究背景及意义10-11
• 1.2 研究现状及趋势11-12
• 1.3 本文研究内容12-13
• 1.4 论文组织结构13
• 1.5 本章小结13-14
• 第2章 K则路径规划算法概述14-25
• 2.1 KSP问题14-15
• 2.2 理论严密KSP算法15-21
• 2.2.1 偏离路径算法15-19
• 2.2.2 候选删除边算法19-20
• 2.2.3 标号算法20-21
• 2.3 有损KSP算法21-24
• 2.3.1 改进遗传算法22
• 2.3.2 混合蛙跳算法22-23
• 2.3.3 双向搜索算法23-24
• 2.4 本章小结24-25
• 第3章 大规模数据下满足重复度要求的K优路径规划算法25-33
• 3.1 基于Dijkstra的KSP算法的优化分析25-28
• 3.2 基于Dijkstra的KOP算法28-32
• 3.2.1 问题定义28-29
• 3.2.2 KOP算法29-30
• 3.2.3 参数控制30-31
• 3.2.4 算法分析31-32
• 3.3 本章小结32-33
• 第4章 基于GIS的路段拓扑研究与优化33-43
• 4.1 基于GIS的路段拓扑33
• 4.2 限制拓扑区域的选取33-34
• 4.3 路段的分割处理34-36
• 4.4 野外区域的路段拓扑36-38
• 4.4.1 基于A*的野的区域拓扑36-37
• 4.4.2 基于A*的野的区域拓扑步骤37-38
• 4.4.3 算法分析38
• 4.5 基于拓扑信息复用的地图缓冲算法38-42
• 4.5.1 地图缓冲结构定义38-39
• 4.5.2 地图缓冲区域的确定39-40
• 4.5.3 地图缓冲替换策略40-41
• 4.5.4 地图缓冲调度算法41-42
• 4.6 本章小结42-43
• 第5章 实现设计及分析43-48
• 5.1 KOP算法对比实验43-46
• 5.1.1 KOP算法效率实验44
• 5.1.2 KOP算法数据规模实验44-45
• 5.1.3 KOP算法道路质量实验45-46
• 5.2 地图缓冲算法对比实验46-47
• 5.3 本章小结47-48
• 第6章 结论48-49
• 参考文献49-51
• 攻读学位期间发表论文与研究成果清单51-52
• 致谢52

【相似文献】

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

1 代红兵;;适合于大规模数据快速存取的文件系统设计[J];中国科学院大学学报;1993年04期

2 ;[J];;年期

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

1 徐健;陈光喜;;一种基于优化处理较大规模数据的支持向量分类机[A];第八届中国青年运筹信息管理学者大会论文集[C];2006年

中国重要报纸全文数据库 前2条

1 王丽;为大规模数据中心建设保驾护航[N];中国经营报;2005年

2 ;戴尔务实推动云计算发展[N];网络世界;2010年

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

1 金冉;面向大规模数据的聚类算法研究及应用[D];东华大学;2015年

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

1 马翠云;基于HBase的大规模数据存储解决方案的设计和实现[D];山东大学;2015年

2 周钊泽;面向大规模数据的局部在线学习[D];中山大学;2015年

3 田大鑫;基于GIS的大规模数据下K优路径规划算法的研究与实现[D];北京理工大学;2016年

4 刘伟;面向大规模数据的高效LTR调研系统设计与实现[D];南京大学;2015年

5 钱彦江;大规模数据聚类技术研究与实现[D];电子科技大学;2009年

6 张新铭;金融应用中大规模数据处理的性能优化[D];浙江大学;2007年

7 蔡偃武;面向大规模数据的在线新事件检测[D];华东理工大学;2014年

8 刘作志;应用于大规模数据的极端学习机研究[D];西北大学;2013年

，

本文编号：780157