并行K最短路径搜索算法研究

发布时间：2019-01-12 14:25

【摘要】：最短路径搜索不仅在城市交通路网规划和人工智能等领域被广泛应用,而且是现阶段智能交通行业研究的焦点。城市的发展使得城市规模不断扩大,城市路网变得越来越复杂,路网节点数目也迅速增加,从时间代价和计算量等多方面因素考虑,传统串行算法无法达到期望的求解结果。因此,伴随着并行技术发展,并行算法出现能够有效减少最短路径搜索时间,方便我们在大规模路网中求解最短路径。一般求解最短路径的算法存在一些问题,例如,采用Dijkstra算法在大规模城市交通路网中搜索最短路径,面对用户并发的出行请求,容易造成交通拥堵,降低了城市交通的运行效率。K最短路径(K Shortest Paths,KSP)算法是路径搜索算法的另一个应用形式,区别于其他算法的是它可以搜索出路网中两点间的最短路径集合,能够尽可能的满足出行者的需求。实际中,路网规模越复杂,KSP算法需要计算的数据量就越大,占用计算机存储空间也就越多。文中提到的KSP算法具有O(n2+n+m)的时间复杂度,程序执行消耗时间较长,导致算法效率和实时性不高。本文从最短路径问题入手,结合城市路网交通流状况,分析了城市交通网络中最短路径算法发展现状,重点描述了KSP算法。针对传统算法存在的问题,本文提出将KSP算法并行化的思想来搜索最短路径。首先,分析城市道路网络的拓扑结构,根据路网的网络结构特点,确定网络分解的基本要求、网络划分方法以及交通网络分割算法。其次,本文以方格式路网模型为基础进行研究,按照网络分割原则划分网络,选择路径的源点和终点,运用并行K最短路径(Parallel K Shortest Paths,PKSP)算法搜索路径,能够得到一个最短路径集合。最后,对PKSP算法的指标体系进行了评估,运用PKSP算法既降低了搜索路径的时间,提高了算法的搜索效率,又能获得较好的加速比。同时,将PKSP算法在城市路网交通流分配方面做了应用,结果证明:在大规模路网中,如果同时出现多个出行请求,PKSP算法能够搜索出多条符合K最短路径集合选择要求的最短路径,扩大了路段交通流的分布范围,降低了发生交通堵塞的频率。
[Abstract]:Shortest path search is not only widely used in urban traffic network planning and artificial intelligence, but also the focus of intelligent transportation industry. With the development of the city, the urban network becomes more and more complex, and the number of nodes in the network increases rapidly. Considering the time cost and computational cost, the traditional serial algorithm can not achieve the desired results. Therefore, with the development of parallel technology, parallel algorithms can effectively reduce the shortest path search time and facilitate us to solve the shortest path in large-scale road network. There are some problems in the algorithm of solving the shortest path. For example, the Dijkstra algorithm is used to search the shortest path in the large-scale urban traffic network, and it is easy to cause traffic congestion in the face of concurrent travel requests. K shortest path (K Shortest Paths,KSP algorithm is another application form of path search algorithm, which is different from other algorithms in that it can search the shortest path set between two points in the outlet network. To be able to meet the needs of travelers as much as possible. In practice, the more complex the network scale, the larger the amount of data needed to be computed by the KSP algorithm, and the more computer storage space is occupied. The KSP algorithm mentioned in this paper has the time complexity of O (N2 n m) and the long time of program execution, which leads to the low efficiency and real-time performance of the algorithm. Starting with the shortest path problem and combining the traffic flow situation of urban road network, this paper analyzes the development of shortest path algorithm in urban transportation network, and describes the KSP algorithm emphatically. Aiming at the problems of traditional algorithms, this paper proposes the idea of parallelizing the KSP algorithm to search the shortest path. Firstly, the topological structure of urban road network is analyzed. According to the characteristics of network structure, the basic requirements of network decomposition, network partition method and traffic network segmentation algorithm are determined. Secondly, based on the square format road network model, this paper divides the network according to the principle of network segmentation, selects the source point and the end point of the path, and uses the parallel K shortest path (Parallel K Shortest Paths,PKSP algorithm to search the path. A set of shortest paths can be obtained. Finally, the index system of PKSP algorithm is evaluated. Using PKSP algorithm can not only reduce the time of searching path, but also improve the search efficiency and get better speedup. At the same time, the PKSP algorithm is applied to the traffic flow allocation of urban road network. The results show that in the large-scale road network, if there are multiple travel requests at the same time, The PKSP algorithm can search for multiple shortest paths which meet the selection requirements of K shortest path set, enlarge the distribution range of traffic flow, and reduce the frequency of traffic jam.
【学位授予单位】：长安大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U495;TP18

【参考文献】