基于预计算技术的路网最短路径查询算法

论文摘要

计算公路网络中两点之间的最短路径问题,由于其在很多地图服务和商业导航系统中有着广泛的应用,最近重新引起了大家的关注。当前的加速方法主要是基于预计算技术,大致可以分为两类：基于空间一致性的最短路径加速方法和基于点重要性的最短路径加速方法,它们和经典的Dijkstra方法相比,均有显著的提高。但是这两类算法由不同的研究者提出,同时他们之间的工作并没有相互引用过,两类算法也没有在同一实验平台上进行系统的比较过,这导致用户在具体的应用条件下并不知道该如何选择合适的方法。此外,当前的算法自身在进行实验评价时还存在以下问题：有些方法仅仅在包含10万点规模的小型公路网络上测试过；有些方法在查询时只强调最短距离（而不是最短路径查询）,即只返回两点之间的最短路径的长度；还有一种方法在实验中的实现方法是错误的,将导致不正确的查询结果。为了解决以上的问题,本文对当前最具代表性的基于空间一致性的加速方法和基于点重要性的加速方法从理论和实验方面进行了详细的比较,并且在基于空间一致性方法的基础上,提出了一种新的数据结构最短路径B+树,它能够更有效的存储预先计算好的最短路径信息,完善了当前的工作。在实验中通过使用最大包含两千万点的真实公路网络,从预处理时间,空间花销和查询效率（包括最短距离和路径查询）等各个方面对两类算法进行了详细的分析比较。实验结果说明了每种算法的特性以及优缺点,根据这些可以在不同的应用情况下选择出最合适的方法。

论文目录

• 摘要
• Abstract
• 图目录
• 表目录
• 第一章 引言
• 1.1 研究背景
• 1.2 研究动机
• 1.3 本文的主要工作
• 1.4 本文的组织结构
• 第二章 基础知识
• 2.1 问题定义
• 2.2 Dijkstra算法
• 2.3 双向Dijkstra算法
• *搜索算法'>2.4 A^*搜索算法
• 第三章 基于点重要性的最短路径加速方法
• 3.1 CH方法
• 3.1.1 CH的构造
• 3.1.2 CH的查询方法
• 3.2 TNR方法
• 3.2.1 TNR的定义
• 3.2.2 TNR的查询方法
• 3.2.3 TNR的预处理方法讨论
• 3.3 其它基于点重要性的最短路径加速方法
• 3.3.1 Reach方法
• 3.3.2 高速的层次网络方法
• 第四章 基于空间一致性最短路径加速方法
• 4.1 SILC方法
• 4.2 SPB方法
• 4.2.1 SPB树定义
• 4.2.2 SPB树的构造
• 4.2.3 使用SPB树进行最短路径查询
• 4.3 PCPD方法
• 第五章 其它方法
• 5.1 基于目标的加速方法
• 5.1.1 ALT方法
• 5.1.2 Arc-Flags方法
• 5.2 组合方法
• 5.2.1 REAL方法
• *方法'>5.2.2 HH^*方法
• 5.2.3 CHASE方法
• 5.2.4 ReachFlags方法
• 第六章 实验评价
• 6.1 算法实现
• 6.2 实验设定
• 6.3 数据集和查询集
• 6.4 空间花销和预处理时间比较
• 6.5 SILC,SPB和PCPD的最短路径查询比较
• 6.6 最短距离查询效率的比较
• 6.7 最短路径查询效率的比较
• 6.8 TNR不同设定下的性能比较
• 6.9 其他查询数据集的实验比较
• 6.10 实验结果总结
• 第七章 总结与展望
• 参考文献
• 致谢
• 攻读硕士期间发表和录用论文