基于預(yù)處理的交通網(wǎng)最短路徑實時查詢研究
發(fā)布時間：2019-05-12 11:42
【摘要】：最短路徑問題是圖論與算法設(shè)計中的經(jīng)典問題,同時也在路徑規(guī)劃、物流規(guī)劃、GPS導(dǎo)航、社交網(wǎng)絡(luò)、基于位置的服務(wù)(LBS)等現(xiàn)實世界的應(yīng)用中扮演著重要的角色。交通路網(wǎng)上最短路徑問題由最短路徑問題衍生而來,特點為交通網(wǎng)數(shù)據(jù)規(guī)模大(如北京市主干路網(wǎng)就包含了10萬個頂點與10萬條邊),計算請求頻繁且實時性要求很高,傳統(tǒng)的最短路徑算法并不能滿足計算需求。 “預(yù)處理——查詢”模型是一種交通路網(wǎng)上最短路徑問題的兩階段方法。在第一階段對數(shù)據(jù)進行預(yù)處理,包括獲得待使用的中間數(shù)據(jù),以降低問題的求解難度；第二階段被稱為查詢階段,給定查詢請求的源點與目標(biāo)點,每個請求須在極短時間內(nèi)進行響應(yīng)。兩階段的想法源自路網(wǎng)是靜態(tài)的,因此預(yù)處理階段可以僅執(zhí)行一次,其結(jié)果可以應(yīng)對相同路網(wǎng)上大規(guī)模的查詢請求。 本文主要工作有： 1,基于預(yù)處理——查詢模型的幾種點到點最短路徑算法性能分析 本文針對“預(yù)處理——查詢”模型上的兩類算法——空間相干為基礎(chǔ)的方法和頂點重要性為基礎(chǔ)的方法,選出兩類方法中具有代表性的算法,就預(yù)處理時間、空間消耗、查詢效率進行分析比較。 2,針對一種基于代表元的有效最短路徑近似算法,對代表元選取策略進行研究 由于代表元的選取策略直接影響近似算法的求解精度,因此如何對路網(wǎng)進行區(qū)域劃分、如何在區(qū)域中分配代表元成為了算法是否高效的關(guān)鍵點。本文將結(jié)合已提出的高效劃分方案,提出一種適合最短路徑近似算法的劃分策略,并分析其與求解精度之間的聯(lián)系。 3,通過模擬真實環(huán)境下路網(wǎng)上的實時查詢請求,對最短路徑長度的估算策略進行研究 本文通過結(jié)合可視化的路網(wǎng)動態(tài)查詢演示,說明近似算法對于最短路徑中源點與目標(biāo)結(jié)點的近似距離可做進一步優(yōu)化,并提出一種基于代表元的兩點間距離估算策略,對估算誤差進行分析。
[Abstract]:The shortest path problem is a classical problem in graph theory and algorithm design. It also plays an important role in the real world applications such as path planning, logistics planning, GPS navigation, social network, location-based service (LBS) and so on. The shortest path problem on the traffic network is derived from the shortest path problem. It is characterized by the large scale of traffic network data (for example, the Beijing backbone network contains 100000 vertices and 100000 edges). The computation request is frequent and the real-time requirement is very high. The traditional shortest path algorithm can not meet the computing requirements. Preprocessing query model is a two-stage method for the shortest path problem on traffic network. In the first stage, the data is preprocessed, including obtaining the intermediate data to be used in order to reduce the difficulty of solving the problem. The second stage is called the query stage. Given the source and target points of the query request, each request must be responded to in a very short period of time. The idea of two stages originates from the fact that the road network is static, so the preprocessing phase can be executed only once, and the result can deal with large-scale query requests on the same road network. The main work of this paper is as follows: 1, Performance Analysis of several Point-to-Point shortest path algorithms based on pre-processing-query Model this paper focuses on the spatial coherence-based method and vertex importance-based method for two kinds of algorithms on the "pre-processing-query" model. The representative algorithms of the two methods are selected, and the preprocessing time, space consumption and query efficiency are analyzed and compared. 2. Aiming at an effective shortest path approximation algorithm based on representative element, this paper studies the selection strategy of representative element, because the selection strategy of representative element directly affects the accuracy of the approximate algorithm, so how to divide the region of the road network is carried out. How to allocate representative elements in the region becomes the key point of whether the algorithm is efficient or not. In this paper, combined with the proposed efficient partition scheme, a partition strategy suitable for the shortest path approximation algorithm is proposed, and the relationship between it and the accuracy of the solution is analyzed. 3. By simulating the real-time query request on the road network, the estimation strategy of the shortest path length is studied in this paper by combining the visual dynamic query demonstration of the road network. It is shown that the approximate distance between the source point and the target node in the shortest path can be further optimized by the approximate algorithm, and a distance estimation strategy between the two points based on the representative element is proposed, and the estimation error is analyzed.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：U491
本文編號：2475363
[Abstract]:The shortest path problem is a classical problem in graph theory and algorithm design. It also plays an important role in the real world applications such as path planning, logistics planning, GPS navigation, social network, location-based service (LBS) and so on. The shortest path problem on the traffic network is derived from the shortest path problem. It is characterized by the large scale of traffic network data (for example, the Beijing backbone network contains 100000 vertices and 100000 edges). The computation request is frequent and the real-time requirement is very high. The traditional shortest path algorithm can not meet the computing requirements. Preprocessing query model is a two-stage method for the shortest path problem on traffic network. In the first stage, the data is preprocessed, including obtaining the intermediate data to be used in order to reduce the difficulty of solving the problem. The second stage is called the query stage. Given the source and target points of the query request, each request must be responded to in a very short period of time. The idea of two stages originates from the fact that the road network is static, so the preprocessing phase can be executed only once, and the result can deal with large-scale query requests on the same road network. The main work of this paper is as follows: 1, Performance Analysis of several Point-to-Point shortest path algorithms based on pre-processing-query Model this paper focuses on the spatial coherence-based method and vertex importance-based method for two kinds of algorithms on the "pre-processing-query" model. The representative algorithms of the two methods are selected, and the preprocessing time, space consumption and query efficiency are analyzed and compared. 2. Aiming at an effective shortest path approximation algorithm based on representative element, this paper studies the selection strategy of representative element, because the selection strategy of representative element directly affects the accuracy of the approximate algorithm, so how to divide the region of the road network is carried out. How to allocate representative elements in the region becomes the key point of whether the algorithm is efficient or not. In this paper, combined with the proposed efficient partition scheme, a partition strategy suitable for the shortest path approximation algorithm is proposed, and the relationship between it and the accuracy of the solution is analyzed. 3. By simulating the real-time query request on the road network, the estimation strategy of the shortest path length is studied in this paper by combining the visual dynamic query demonstration of the road network. It is shown that the approximate distance between the source point and the target node in the shortest path can be further optimized by the approximate algorithm, and a distance estimation strategy between the two points based on the representative element is proposed, and the estimation error is analyzed.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：U491
【共引文獻】
相關(guān)期刊論文 前10條
1 姚海龍;蔡懿慈;洪先龍;周強;;考慮擁擠度和性能的全芯片可控布線系統(tǒng)框架(英文)[J];半導(dǎo)體學(xué)報;2006年07期
2 盧新明;鄭時德;;求解路網(wǎng)上車流徑路的啟發(fā)式算法[J];北方交通大學(xué)學(xué)報;1993年03期
3 王海梅;周獻中;;網(wǎng)絡(luò)系統(tǒng)中的最短路徑分析及其應(yīng)用研究[J];兵工學(xué)報;2006年03期
4 李玉擰;徐立業(yè);;不加權(quán)算術(shù)平均組對方法的改進及應(yīng)用[J];北京工業(yè)大學(xué)學(xué)報;2007年12期
5 李玉擰;高凱;;一種改進的NJ方法及其應(yīng)用[J];北京工業(yè)大學(xué)學(xué)報;2009年02期
6 陳艷艷;王東柱;;高可靠性應(yīng)急備選路徑啟發(fā)式搜索算法[J];北京工業(yè)大學(xué)學(xué)報;2010年09期
7 彭飛,柳重堪,張其善;車輛定位與導(dǎo)航系統(tǒng)中的快速路徑規(guī)劃算法[J];北京航空航天大學(xué)學(xué)報;2002年01期
8 趙愛華;丁志峰;;復(fù)雜速度模型的地震交切定位方法(英文)[J];Applied Geophysics;2007年04期
9 李秉智;李智;;一種新的基于Dijkstra算法的QoS組播樹啟發(fā)式算法[J];重慶郵電學(xué)院學(xué)報(自然科學(xué)版);2006年01期
10 龔萍;吳澤忠;;基于效用值的模糊最短路問題的研究[J];成都信息工程學(xué)院學(xué)報;2010年04期
，本文編號：2475363
本文鏈接：http://sikaile.net/guanlilunwen/wuliuguanlilunwen/2475363.html
最近更新
教材專著
