原文传递
路网中标签约束最短路径查询算法研究
| 论文题名： | 路网中标签约束最短路径查询算法研究 |
| 关键词： | 城市路网;标签约束;最短路径;查询算法 |
| 摘要： | 随着现代科学技术的不断进步，基于位置的服务已经与我们的日常生活形成了密不可分的关系。路径规划是基于位置服务中最重要的功能之一，它对资源分配，行车路线规划，交通拥堵的缓解有着重要的作用。给定一个起始节点，目标节点，寻找一条最小代价的路径被称为最短路径查询。不同于传统的最短路径查询算法，标签约束最短路径查询在用户指定的道路类型的条件下找到一条最短路径。但是，现有的关于标签约束最短路径查询的算法较少，而且存在的一定的不足，不能够在大型路网数据集中进行高效的查询。基于上述所存在的问题，本文提出了标签约束最短路径的查询算法，并在现实生活中选取了六个不同城市路网的真实数据集，执行了大量的实验，最终证明了本文所提出的算法的高效性。具体地，本文的主要贡献包括如下几个部分： (1)提出了一个基于网格的索引GBPI，根据划分的网格对部分节点之间的路径进行存储，同时对网格中的标签类型进行划分，使得查找过程中可以快速判断节点之间是否可以根据指定的标签到达。 (2)提出了一个基础的标签约束最短路径查询算法BLCSP(BasicLabelConstrainedShortestPathQuery)。算法以给定的起始点为中心，在约束条件下不断的对外进行拓展。在拓展的过程中，计算当前节点到目的节点的直线距离，从而给算法规定了一个拓展的方向，避免访问部分无关节点，加速查询效率。 (3)在BLCSP算法的基础上提出了改进的标签约束最短路径查询算法ILCSP(ImprovedLabelConstrainedShortestPathQuery)。该方法主要包括格间约束最短路径查找和标签约束最短路径调整两个过程。首先，根据GBPI索引找到一条从起始节点到目标节点的满足网格间约束的最短路径，这条路径由网格内部不考虑约束的最短路径和网格间的标签约束路径组成。之后在调整过程中，对网格内部不符合给定标签类型的路径进行微调，得到算法最终所需的精确路径。 (4)进行了详细的对比实验，证明了本文提出的两个算法的高效性，相比于当前最优的算法EDP，基础算法BLCSP和提高算法ILCSP在六个真实数据集中的查询时间分别比EDP加快了12％~17%和20%~22%。 |
| 作者： | 要佳敏 |
| 专业： | 计算机技术 |
| 导师： | 王习特 |
| 授予学位： | 硕士 |
| 授予学位单位： | 大连海事大学 |
| 学位年度： | 2022 |
检索历史
应用推荐
