基于路网分层的多级搜索算法的研究与实现

论文摘要

近年来,智能交通系统(ITS)、车载GPS定位系统、城市交通诱导系统等相关地理信息系统(GIS)技术的广泛应用对电子地图搜索服务提出了更高的要求。因此,对电子地图搜索及其相关领域的研究已变得炙手可热。本文研究了电子地图搜索服务中的一个核心议题:最短路径问题求解。拥有海量数据是GIS系统的一个显著特点,合理地提取、组织、分析和处理电子地图数据是提高寻径效率的关键。传统最短路径问题的研究更多地注重算法的改进和优化,或者是基于少量地图数据的寻径系统的实现;本文则侧重于海量数据下的寻径及其性能优化,提出基于路网分层的多级搜索算法,实现了全美国的Door2Door(门牌号到门牌号)寻径系统。其主要研究工作如下:1.提出基于路网分层的多级搜索算法,并比较几种传统寻径算法的优劣,选择了适合GIS中大数据量寻径的A~*算法作为其通用最短寻径算法;2.将分层思想引入路网数据组织,从地图数据中提取出需要的数据通过分层、合并、简化等方式组织成特定的道路数据文件,并建立路网数据库;3.通过实验得出了适用于全美寻径系统的A~*算法的估价函数的加权模型;以此为基础提出了基于海量数据下的各种寻径策略,并讨论其具体实现的细节问题;4.讨论寻径中的必备工具——RTree模块,研究TIGER数据和Shape文件的组织格式;5.基于前面的研究实现了一个实用高效的寻径系统。全文主要对GIS寻径问题中海量数据的处理进行了较为深入的探索并提出相应的算法,并且初步实现了全美国的Door2Door寻径系统,证明了理论研究的价值和可行性。目前国内关于大数据量下的最短路径问题的研究还比较薄弱,实用性的资料较少,因此本文的研究有较大的理论意义,而且本文已经初步实现了一个寻径系统,因此有着更大的现实意义。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 GIS中最短路径问题的研究现状
• 1.2.1 最短路径算法
• 1.2.2 寻径策略和数据组织
• 1.3 研究内容及意义
• 1.3.1 研究内容
• 1.3.2 研究意义
• 1.4 本论文的章节安排
• 第二章 基于路网分层的多级搜索算法
• 2.1 算法的提出
• 2.1.1 算法提出的背景
• 2.1.2 分层与多级搜索思想的引入
• 2.1.3 基于路网分层的多级搜索算法的提出
• 2.2 MSA-HR的特点
• 2.3 MSA-HR的最短路径通用算法
• 2.3.1 传统最短路径算法及性能分析
• 2.3.2 通用最短路径算法的选择及改进
• 2.4 小结
• 第三章 基于分层思想的路网数据组织
• 3.1 路网分层策略
• 3.1.1 路网数据分层
• 3.1.2 数据分层存在的问题
• 3.1.3 道路的简化
• 3.2 路网数据的组织
• 3.2.1 数据源——TIGER数据
• 3.2.2 中间数据格式——Shape文件
• 3.3 道路数据文件的生成
• 3.3.1 道路数据文件的作用
• 3.3.2 道路数据路段结构
• 3.3.3 道路数据文件的生成
• 3.4 全美道路网数据库的建立
• 3.4.1 道路网数据提取策略
• 3.4.2 全美道路网数据库的设计
• 3.5 小结
• 第四章 MSA-HR的寻径策略分析
• 4.1 估价函数的加权模型
• 4.2 “三段寻径”分析
• 4.3 基于MSA-HR的寻径策略
• 4.3.1 County内寻径
• 4.3.2 State内寻径
• 4.3.3 USA内寻径
• 4.4 小结
• 第五章 系统实现
• 5.1 必要工具——RTree模块
• 5.1.1 空间索引
• 5.1.2 R树
• 5.1.3 R树索引的建立
• 5.1.4 R树索引在本文中的应用
• 5.2 系统需求分析
• 5.3 程序的主要结构及核心代码
• 5.3.1 系统类图
• 5.3.2 核心代码
• 5.4 性能分析
• 5.4.1 最短路径搜索算法性能对比
• 5.4.2 MSA-HR和平面算法性能对比
• 5.4.3 不同分层方式寻径结果对比
• 5.4.4 与Google寻径结果对比
• 5.5 小结
• 第六章 总结与展望
• 致谢
• 参考文献
• 攻硕期间取得的研究成果