大规模道路网最短路径算法的研究

《大规模道路网最短路径算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ＴＰ３０－１分类号：单位代码：１０６３６密级：公开学号：２０１５１３９１００１、汾Ｗ却範七摩专业学位硕士论文＾／ｒＢＢｓｆｅｉｊＶ＼（３／中文论文题目：大规模道路网最短路径算法的研究英文论文题目：ＲｅｓｅａｒｃｈｏｎｔｈｅＳｈｏｒｔｅｓｔＰａｔｈＡｌｇｏｒｉｔｈｍｆｏｒ－ＬａｒｇｅｓｃａｌｅＲｏａｄＮｅｔｗｏｒｋ论文作者：王鹏霞指导教师：李晓宁张昭专业学位类别：工程硕士专业领域：计算机技术论文形式：技术研究所在学院：计算机科学学院论文提交日期：２０１８年０６月１５日论文答辩日期：２０１８年０５月２

2、７日大规模道路网最短路径算法的研究计算机技术专业研究生王鹏霞指导教师李晓宁张昭摘要随着人口往城市的快速迁移，全球道路网的规模在不断地扩大，高效、快速的从庞大的道路网数据中计算两点之间的最短路径，成为了学术界和工业界众多研发人员的研究课题。经过多年的研究，学者们已经提出了诸多相关算法，例如Dijkstra算法、CH算法(ConstructionHierarchiesAlgorithm)、Arc-Flag算法、HighwayHierarchies算法，以及一些结合智能算法的最短路径算法。但是如何通过减少数据搜索空间，从而达到有效降低查询时间这一问题仍然未能得到良好的解决。本文针

3、对从大规模道路网数据中查询两点之间最短路径存在时间消耗较大的问题，分析研究了实际道路之间的限制关系，提出了一种基于节点度的大规模道路网数据划分方法，在此基础上，给出有效可行的解决方案，同时也保证了算法的性能。论文的主要工作如下：(1)提出了一种基于节点度的道路划分算法，以解决划分道路网数据时容易将节点分布密集的区域划分在不同的子网内的问题。首先，该算法根据实际道路之间的限制关系处理并存储道路网数据；其次，设置划分后的子网内最大节点数量，然后利用Kd-tree划分道路网数据，并标记划分后的子网的最大节点度；最后，比较子网内的最大节点的度与边界节点的度，若边界节点的度与最大节点的度

4、相等，则说明该边界节点位于节点分布密集的区域，进行相邻节点的合并。实验结果表明，该算法在一定程度上提高了划分后的子网的独立性。(2)优化了基于划分的最短路径查询算法的查询效率，以解决大规模道路网中查询最短路径时空间消耗巨大，以及起始节点和目标节点相距较近时查询效率低的问题。首先，根据道路的特性将道路网数据分层划分；其次，设定子网内节点数量为层次收缩最短路径算法能够处理的最大节点数量，并使用基于节点度的道路划分算法划分道路网数据；然后，获取道路网数据划分后的边界节点集合并建立边界节点最短路径查询表；最III后，通过判断输入的起始节点和目标节点是否属于同一子网，选择不同的最短路径搜

5、索策略。若两节点在同一子网内，则根据子网内的节点的重要性双向搜索最短路径。(3)针对本文提出的最短路径查询算法，使用了大量的实验进行验证。实验结果表明，与经典的基于道路网划分的最短路径算法相比，本文算法减少了空间消耗，同时缩短了查询时间。(4)基于C#和OpenStreetMap，开发了最短路径查询的动态链接库，实现了建立有转向限制的道路网数据库和道路网数据的划分功能，并对最短路径查询功能进行封装，通过调用示例证明动态链接库的可靠性。关键词：大规模道路网最短路径问题KDTREE划分动态链接库IVResearchontheShortestPathAlgorithmforLarge

6、-scaleRoadNetworkMajor:ComputerTechnologyGraduateStudent:WangPengxiaSupervisor:LiXiaoning,ZhangzhaoAbstract:Alongwiththerapidhumanmigrationtourbanareas,globalroadnetworkisconstantlyexpanding,makingthefastandhighlyefficientcalculationoftheshortestpathbetweentwonodesinthevastnetworkofroadsbeco

7、mearesearchtopicformanyresearchersanddevelopersinacademiaandindustry.Afteryearsofstudy,scholarspresentednumerousrelevantalgorithmssuchasDijkstraalgorithm,CHalgorithm(ConstructionHierarchiesAlgorithm),Arc-Flagalgorithm,HighwayHierarchiesalgorithmasw