基于城市路网的最短路径算法研究与应用

发布时间：2018-05-09 12:32

本文选题：Dijkstra算法 + 矩形搜索算法　；参考：《中北大学》2017年硕士论文

【摘要】：现如今,城市规模扩大,汽车数量增多,交通拥堵问题成我国亟需解决的重要问题之一。解决城市路网交通拥堵问题的关键技术在于最短路径的研究。因此,基于城市路网的最短路径算法研究具有重要意义。本课题重点研究了求解城市路网最短路径的Dijkstra算法以及求解K最短路径的Yen算法,主要工作如下:(1)在存储城市路网图方面,邻接矩阵存储稀疏图时,存在数据冗余度大的问题,本文提出用邻接表数据结构存储城市路网图,降低Dijkstra算法的空间复杂度。(2)在搜索范围优化方面,Dijkstra算法存在搜索范围广、遍历节点多,耗时长的问题,本文对椭圆搜索算法、矩形搜索算法优化Dijkstra算法的问题进行深入的分析,结合路网特征给出两种算法的具体搜索范围和面积公式。并通过实验对比分析,证明了采用矩形算法优化Dijkstra算法的可行性和高效性。(3)针对Yen算法在求解K最短路径计算比较复杂,时间复杂度高的问题,对Yen算法做了改进。通过引入估价函数,求解最短路径时只选取估价值最小的节点作为最终的偏离节点,降低了算法的复杂度。并通过实验,从算法寻路时间、算法所求的路径长度及寻路过程中产生的候选路径数目方面对比分析了两种算法,验证了算法的有效性。(4)基于unity3d和3ds Max,利用了模型优化技术设计实现了虚拟城市路网寻路系统,将矩形搜索算法和基于启发式搜索改进的Yen算法应用到虚拟城市路网寻路系统中,并验证了本文所提观点在具体应用中的高效性和可行性,达到了预期的寻路效果。
[Abstract]:Nowadays, with the expansion of the city scale and the increase of the number of cars, the problem of traffic congestion has become one of the most important problems that need to be solved in our country. The research of shortest path is the key technology to solve the problem of traffic congestion in urban road network. Therefore, it is of great significance to study the shortest path algorithm based on urban road network. This paper focuses on the Dijkstra algorithm for solving the shortest path of urban road network and the Yen algorithm for solving the shortest path of urban road network. The main work is as follows: in the storage of urban road network map, the problem of data redundancy exists when the adjacent matrix is used to store sparse map. In this paper, we put forward the problem of storing urban road map using adjacent table data structure to reduce the space complexity of Dijkstra algorithm. In the aspect of searching range optimization, Dijkstra algorithm has the problems of wide search scope, many traversing nodes and long time consuming. In this paper, elliptical search algorithm is discussed. The problem of optimizing Dijkstra algorithm by rectangular search algorithm is analyzed deeply, and the specific search range and area formula of the two algorithms are given according to the road network features. The feasibility and high efficiency of using rectangle algorithm to optimize Dijkstra algorithm are proved by comparing experiments. Aiming at the problem of complex computation and high time complexity of Yen algorithm for solving K shortest path, the Yen algorithm is improved. By introducing the evaluation function, only the node with the smallest estimated value is selected as the final deviation node when solving the shortest path, and the complexity of the algorithm is reduced. Through experiments, the two algorithms are compared and analyzed in terms of the searching time, the path length and the number of candidate paths generated in the route finding process. The validity of the algorithm is verified. Based on unity3d and 3ds Maxs, the virtual city road network routing system is designed and implemented by using model optimization technology. The rectangular search algorithm and the improved Yen algorithm based on heuristic search are applied to the virtual city road finding system. The efficiency and feasibility of this paper are verified, and the expected route finding effect is achieved.
【学位授予单位】：中北大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：U491;TP301.6

【参考文献】