基于預處理的交通網最短路徑實時查詢研究
發(fā)布時間：2019-05-12 11:42
【摘要】：最短路徑問題是圖論與算法設計中的經典問題,同時也在路徑規(guī)劃、物流規(guī)劃、GPS導航、社交網絡、基于位置的服務(LBS)等現實世界的應用中扮演著重要的角色。交通路網上最短路徑問題由最短路徑問題衍生而來,特點為交通網數據規(guī)模大(如北京市主干路網就包含了10萬個頂點與10萬條邊),計算請求頻繁且實時性要求很高,傳統(tǒng)的最短路徑算法并不能滿足計算需求。 “預處理——查詢”模型是一種交通路網上最短路徑問題的兩階段方法。在第一階段對數據進行預處理,包括獲得待使用的中間數據,以降低問題的求解難度；第二階段被稱為查詢階段,給定查詢請求的源點與目標點,每個請求須在極短時間內進行響應。兩階段的想法源自路網是靜態(tài)的,因此預處理階段可以僅執(zhí)行一次,其結果可以應對相同路網上大規(guī)模的查詢請求。 本文主要工作有： 1,基于預處理——查詢模型的幾種點到點最短路徑算法性能分析 本文針對“預處理——查詢”模型上的兩類算法——空間相干為基礎的方法和頂點重要性為基礎的方法,選出兩類方法中具有代表性的算法,就預處理時間、空間消耗、查詢效率進行分析比較。 2,針對一種基于代表元的有效最短路徑近似算法,對代表元選取策略進行研究 由于代表元的選取策略直接影響近似算法的求解精度,因此如何對路網進行區(qū)域劃分、如何在區(qū)域中分配代表元成為了算法是否高效的關鍵點。本文將結合已提出的高效劃分方案,提出一種適合最短路徑近似算法的劃分策略,并分析其與求解精度之間的聯系。 3,通過模擬真實環(huán)境下路網上的實時查詢請求,對最短路徑長度的估算策略進行研究 本文通過結合可視化的路網動態(tài)查詢演示,說明近似算法對于最短路徑中源點與目標結點的近似距離可做進一步優(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.
【學位授予單位】：中國科學技術大學
【學位級別】：碩士
【學位授予年份】：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.
【學位授予單位】：中國科學技術大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：U491
【共引文獻】
相關期刊論文 前10條
1 姚海龍;蔡懿慈;洪先龍;周強;;考慮擁擠度和性能的全芯片可控布線系統(tǒng)框架(英文)[J];半導體學報;2006年07期
2 盧新明;鄭時德;;求解路網上車流徑路的啟發(fā)式算法[J];北方交通大學學報;1993年03期
3 王海梅;周獻中;;網絡系統(tǒng)中的最短路徑分析及其應用研究[J];兵工學報;2006年03期
4 李玉擰;徐立業(yè);;不加權算術平均組對方法的改進及應用[J];北京工業(yè)大學學報;2007年12期
5 李玉擰;高凱;;一種改進的NJ方法及其應用[J];北京工業(yè)大學學報;2009年02期
6 陳艷艷;王東柱;;高可靠性應急備選路徑啟發(fā)式搜索算法[J];北京工業(yè)大學學報;2010年09期
7 彭飛,柳重堪,張其善;車輛定位與導航系統(tǒng)中的快速路徑規(guī)劃算法[J];北京航空航天大學學報;2002年01期
8 趙愛華;丁志峰;;復雜速度模型的地震交切定位方法(英文)[J];Applied Geophysics;2007年04期
9 李秉智;李智;;一種新的基于Dijkstra算法的QoS組播樹啟發(fā)式算法[J];重慶郵電學院學報(自然科學版);2006年01期
10 龔萍;吳澤忠;;基于效用值的模糊最短路問題的研究[J];成都信息工程學院學報;2010年04期
，本文編號：2475363
本文鏈接：http://www.sikaile.net/guanlilunwen/wuliuguanlilunwen/2475363.html
最近更新
教材專著
