顾及地理实体属性信息的网络最短路径分析算法研究

发布时间：2017-08-18 21:21

  本文关键词：顾及地理实体属性信息的网络最短路径分析算法研究

  更多相关文章： 最短路径分析 层次划分 距离搜索 路径搜索

【摘要】：网络图中最短路径的计算问题在图论中是一个经典的问题,一个最实际的应用就是在道路网络中进行路径分析,如在给定的道路网中,寻找起点到目标点的最佳路径问题。在本课题研究中,假设给定的道路网中节点和边不经常改变,即在稳定的道路网中进行最短路径分析。对一般的小规模路网的路径分析问题已有较为成熟的算法,而对大规模道路网的最短路径分析问题,经典的Di jkstra算法因为计算速度非常慢,故而这种经典算法并不适用。在近几年的时间里,针对大规模路网的路径分析问题,提出了许多新的快速算法,这些算法有个共同点,就是预先计算和存储辅助数据用于加速最短路径的查询。然而,在边为非负权重的图中,这些算法通常只考虑计算源点到目标点的最短路径简单问题,而实际问题并没有那么简单,因此,在此需要扩充一下研究问题的定义,设置从源点到目标点的所需要的时间作为边的权重,充分考虑路网中节点和边的属性信息。虽然当前已有根据此提出一些新的算法,但是这些算法并不是很有效。因此研究出一种新的算法是非常有必要的。 在本文中,基于道路网节点和边实体的属性信息,对最短路径的分析提出了一种新的加速算法-HP (Hierarchy Partition)算法,这种算法包括如何对道路网的层次划分、如何在路网中构建辅助边、如何对同一层级上的节点进行排序、如何对节点进行抽样和最短路径的求解。实验数据从OpenStreetMap的镜像站点下载,在数据预处理阶段应用开源插件-ArcGIS Editor For OSM Data,安装嵌入ArcGIS中,应用此插件提供的功能对OSM原数据进行预处理,把初步处理好的数据,应用XML2RDF格式转换工具,把OSM数据转成RDF数据格式,并保存在RDF-3X数据库中。 在CH算法和TNR启发下,对路网进行层次划分和构建辅助边,结合Reach算法,对实验数据抽样,并求出近似解。在实验过程中,采用5个实验数据,数据节点从5万到2000万,把实验数据分成10个数据集作为查询数据进行实验,在实验中分别比较HP算法、CH算法、Dijkstra算法和TNR算法在距离和路径查询效率。最后对整个实验结果进行了详细的分析,得出在预处理过程HP的空间消耗稍微比CH算法差,但是比其他的2种算法消耗要低得多,而在空间复杂度和时间复杂度上都比其他3种算法优越。
【关键词】：最短路径分析 层次划分 距离搜索 路径搜索
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：P208
【目录】：

• 摘要4-5
• Abstract5-9
• 1、绪论9-15
• 1.1 课题研究背景9
• 1.2 研究现状综述9-11
• 1.3 研究内容和方法11-14
• 1.3.1 研究的内容描述11-12
• 1.3.2 研究的方法12-14
• 1.4 论文结构安排14-15
• 2、网络数据表达模型与网络数据预处理15-25
• 2.1 网络数据表达模型15-16
• 2.1.1 邻接矩阵对网络数据的表达15
• 2.1.2 邻接表对网络数据的表达15-16
• 2.2 地理数据的获取与处理16-20
• 2.2.1 OSM地理数据的获取16-17
• 2.2.2 OSM数据模型结构17-19
• 2.2.3 OSM原始数据处理19-20
• 2.3 地理数据与网络数据的转换20-21
• 2.4 大规模网络数据的表达与存储21-25
• 2.4.1 RDF数据模型简介21-23
• 2.4.2 RDF-3X数据库存储结构23
• 2.4.3 道路网数据的存储与查询23-25
• 3、基于属性信息的层次化网络构建25-30
• 3.1 基于属性信息的地理实体构建25-27
• 3.1.1 道路网的节点属性25
• 3.1.2 城市道路网级别划分25-26
• 3.1.3 道路网边的属性信息26-27
• 3.2 基于实体的重要路径发现与赋权27-30
• 3.2.1 道路网重要路径发现27-28
• 3.2.2 道路网重要路径赋权28-30
• 4、层次化网络下的最短路径算法30-46
• 4.1 Reach、TNR和CH算法30-35
• 4.1.1 Bidirectional Dijkstra算法30
• 4.1.2 Reach算法30-32
• 4.1.3 CH算法32-33
• 4.1.4 TNR算法33-35
• 4.2 层次化网络下最短路径算法35-41
• 4.2.1 层次划分36-39
• 4.2.2 辅助边构建39-41
• 4.2.3 节点级别排序的确定41
• 4.3 最短路径近似算法41-43
• 4.3.1 样本的选取42-43
• 4.3.2 近似最短路径的求解43
• 4.4 空间复杂度和时间复杂度分析43-46
• 4.4.1 空间复杂度分析44
• 4.4.2 时间复杂度分析44-46
• 5、实验46-53
• 5.1 实验数据介绍46
• 5.2 数据预处理46-48
• 5.3 距离查询效率48-50
• 5.4 路径查询效率50-51
• 5.5 空间消耗和预处理消耗51-53
• 6、总结与展望53-56
• 6.1 总结53
• 6.2 应用前景53-54
• 6.3 下一步研究计划54-56
• 致谢56-58
• 参考文献58-63
• 攻读学位期间的研究成果63

【参考文献】

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

1 宋青;汪小帆;;最短路径算法加速技术研究综述[J];电子科技大学学报;2012年02期

，

本文编号：696845