【摘要】：最短路徑搜索不僅在城市交通路網(wǎng)規(guī)劃和人工智能等領(lǐng)域被廣泛應(yīng)用,而且是現(xiàn)階段智能交通行業(yè)研究的焦點(diǎn)。城市的發(fā)展使得城市規(guī)模不斷擴(kuò)大,城市路網(wǎng)變得越來越復(fù)雜,路網(wǎng)節(jié)點(diǎn)數(shù)目也迅速增加,從時(shí)間代價(jià)和計(jì)算量等多方面因素考慮,傳統(tǒng)串行算法無法達(dá)到期望的求解結(jié)果。因此,伴隨著并行技術(shù)發(fā)展,并行算法出現(xiàn)能夠有效減少最短路徑搜索時(shí)間,方便我們?cè)诖笠?guī)模路網(wǎng)中求解最短路徑。一般求解最短路徑的算法存在一些問題,例如,采用Dijkstra算法在大規(guī)模城市交通路網(wǎng)中搜索最短路徑,面對(duì)用戶并發(fā)的出行請(qǐng)求,容易造成交通擁堵,降低了城市交通的運(yùn)行效率。K最短路徑(K Shortest Paths,KSP)算法是路徑搜索算法的另一個(gè)應(yīng)用形式,區(qū)別于其他算法的是它可以搜索出路網(wǎng)中兩點(diǎn)間的最短路徑集合,能夠盡可能的滿足出行者的需求。實(shí)際中,路網(wǎng)規(guī)模越復(fù)雜,KSP算法需要計(jì)算的數(shù)據(jù)量就越大,占用計(jì)算機(jī)存儲(chǔ)空間也就越多。文中提到的KSP算法具有O(n2+n+m)的時(shí)間復(fù)雜度,程序執(zhí)行消耗時(shí)間較長,導(dǎo)致算法效率和實(shí)時(shí)性不高。本文從最短路徑問題入手,結(jié)合城市路網(wǎng)交通流狀況,分析了城市交通網(wǎng)絡(luò)中最短路徑算法發(fā)展現(xiàn)狀,重點(diǎn)描述了KSP算法。針對(duì)傳統(tǒng)算法存在的問題,本文提出將KSP算法并行化的思想來搜索最短路徑。首先,分析城市道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),根據(jù)路網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn),確定網(wǎng)絡(luò)分解的基本要求、網(wǎng)絡(luò)劃分方法以及交通網(wǎng)絡(luò)分割算法。其次,本文以方格式路網(wǎng)模型為基礎(chǔ)進(jìn)行研究,按照網(wǎng)絡(luò)分割原則劃分網(wǎng)絡(luò),選擇路徑的源點(diǎn)和終點(diǎn),運(yùn)用并行K最短路徑(Parallel K Shortest Paths,PKSP)算法搜索路徑,能夠得到一個(gè)最短路徑集合。最后,對(duì)PKSP算法的指標(biāo)體系進(jìn)行了評(píng)估,運(yùn)用PKSP算法既降低了搜索路徑的時(shí)間,提高了算法的搜索效率,又能獲得較好的加速比。同時(shí),將PKSP算法在城市路網(wǎng)交通流分配方面做了應(yīng)用,結(jié)果證明:在大規(guī)模路網(wǎng)中,如果同時(shí)出現(xiàn)多個(gè)出行請(qǐng)求,PKSP算法能夠搜索出多條符合K最短路徑集合選擇要求的最短路徑,擴(kuò)大了路段交通流的分布范圍,降低了發(fā)生交通堵塞的頻率。
[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.
【學(xué)位授予單位】：長安大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：U495;TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 宮恩超;李魯群;;基于Bellman-Ford算法的動(dòng)態(tài)最優(yōu)路徑算法設(shè)計(jì)[J];測(cè)繪通報(bào);2011年08期

2 王志龍;;Floyd-Warshall算法在現(xiàn)實(shí)生活中的應(yīng)用及算法思想引申[J];計(jì)算機(jī)光盤軟件與應(yīng)用;2012年09期

3 朱參世;;一種Warshall和Floyd算法的優(yōu)化方法研究[J];計(jì)算機(jī)與現(xiàn)代化;2010年04期

4 徐濤;丁曉璐;李建伏;;K最短路徑算法綜述[J];計(jì)算機(jī)工程與設(shè)計(jì);2013年11期

5 陳潔;陸鋒;;一種基于雙端隊(duì)列的交通網(wǎng)絡(luò)最短路徑Pallottino優(yōu)化算法[J];中國圖象圖形學(xué)報(bào);2006年03期

6 段宗濤;李瑩;鄭西彬;康軍;程豪;;基于Hadoop平臺(tái)的實(shí)時(shí)多路徑交通流分配算法[J];中國公路學(xué)報(bào);2014年09期

，

本文編號(hào)：2407880