顧及地理實體屬性信息的網(wǎng)絡最短路徑分析算法研究.pdf

1、網(wǎng)絡圖中最短路徑的計算問題在圖論中是一個經(jīng)典的問題,一個最實際的應用就是在道路網(wǎng)絡中進行路徑分析,如在給定的道路網(wǎng)中,尋找起點到目標點的最佳路徑問題。在本課題研究中,假設給定的道路網(wǎng)中節(jié)點和邊不經(jīng)常改變,即在穩(wěn)定的道路網(wǎng)中進行最短路徑分析。對一般的小規(guī)模路網(wǎng)的路徑分析問題已有較為成熟的算法,而對大規(guī)模道路網(wǎng)的最短路徑分析問題,經(jīng)典的Dijkstra算法因為計算速度非常慢,故而這種經(jīng)典算法并不適用。在近幾年的時間里,針對大規(guī)模路網(wǎng)的路徑分

2、析問題,提出了許多新的快速算法,這些算法有個共同點,就是預先計算和存儲輔助數(shù)據(jù)用于加速最短路徑的查詢。然而,在邊為非負權重的圖中,這些算法通常只考慮計算源點到目標點的最短路徑簡單問題,而實際問題并沒有那么簡單,因此,在此需要擴充一下研究問題的定義,設置從源點到目標點的所需要的時間作為邊的權重,充分考慮路網(wǎng)中節(jié)點和邊的屬性信息。雖然當前已有根據(jù)此提出一些新的算法,但是這些算法并不是很有效。因此研究出一種新的算法是非常有必要的。
　　

3、在本文中,基于道路網(wǎng)節(jié)點和邊實體的屬性信息,對最短路徑的分析提出了一種新的加速算法-HP(Hierarchy Partition)算法,這種算法包括如何對道路網(wǎng)的層次劃分、如何在路網(wǎng)中構建輔助邊、如何對同一層級上的節(jié)點進行排序、如何對節(jié)點進行抽樣和最短路徑的求解。實驗數(shù)據(jù)從OpenStreetMap的鏡像站點下載,在數(shù)據(jù)預處理階段應用開源插件-ArcGISEditorForOSMData,安裝嵌入ArcGIS中,應用此插件提供的功能對

4、OSM原數(shù)據(jù)進行預處理,把初步處理好的數(shù)據(jù),應用 XML2RDF格式轉換工具,把 OSM數(shù)據(jù)轉成 RDF數(shù)據(jù)格式,并保存在RDF-3X數(shù)據(jù)庫中。
　　在 CH算法和 TNR啟發(fā)下,對路網(wǎng)進行層次劃分和構建輔助邊,結合 Reach算法,對實驗數(shù)據(jù)抽樣,并求出近似解。在實驗過程中,采用5個實驗數(shù)據(jù),數(shù)據(jù)節(jié)點從5萬到2000萬,把實驗數(shù)據(jù)分成10個數(shù)據(jù)集作為查詢數(shù)據(jù)進行實驗,在實驗中分別比較HP算法、CH算法、Dijkstra算法和TN