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

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

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

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

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