基于Hadoop的GIS網(wǎng)絡(luò)最短路徑算法研究.pdf

1、最短路徑分析作為GIS中最重要的空間分析功能之一，已經(jīng)廣泛地應用于路徑導航、管網(wǎng)優(yōu)化設(shè)計、交通疏導等方面。隨著交通路網(wǎng)、管道網(wǎng)絡(luò)等設(shè)施的規(guī)模逐年擴大，由這些現(xiàn)實設(shè)施抽象出來的空間網(wǎng)絡(luò)數(shù)據(jù)的規(guī)模也逐漸趨向于海量化。如何使大規(guī)?？臻g網(wǎng)絡(luò)得到快速處理是GIS中最短路徑算法所要面對的一個巨大挑戰(zhàn)。單機環(huán)境下GIS平臺的最短路徑分析處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)會出現(xiàn)計算效率較低的情況，有時甚至會造成GIS軟件運行崩潰。云計算平臺 Hadoop在處理大數(shù)據(jù)方

2、面，具有運算效率高和應用成熟、穩(wěn)定的優(yōu)勢。為此，本文對基于Hadoop的GIS網(wǎng)絡(luò)最短路徑算法進行了研究。
　?。ㄒ唬┍疚难芯苛薌IS網(wǎng)絡(luò)矢量數(shù)據(jù)在HBase中的存儲與管理。根據(jù)GIS網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)進行解析，并通過適當?shù)腍Base表結(jié)構(gòu)設(shè)計，解決了GIS網(wǎng)絡(luò)在Hadoop下的存儲問題，為GIS網(wǎng)絡(luò)在Hadoop云平臺中進行最短路徑并行計算創(chuàng)造了前提條件。并且通過設(shè)計相關(guān)HBase表，實現(xiàn)了動態(tài)權(quán)重的賦值問題，使得最短路徑算法能夠延

3、伸為最優(yōu)路徑算法。
　?。ǘ┍疚脑O(shè)計了基于MapReduce的鄰接表結(jié)構(gòu)生成算法。該算法的設(shè)計結(jié)合了鄰接表結(jié)構(gòu)的特點與MapReduce的運行原理，在Hadoop平臺下能有效地解決大規(guī)模GIS網(wǎng)絡(luò)的鄰接表結(jié)構(gòu)生成問題。通過該算法過程得到的鄰接表數(shù)據(jù)結(jié)構(gòu)給本文最短路徑算法提供了數(shù)據(jù)結(jié)構(gòu)保障。
　?。ㄈ┍疚奶岢隽嘶?Hadoop的 GIS網(wǎng)絡(luò)最短路徑并行算法（H_PGNSP）。該算法流程除了上文所述的計算過程外，還包括改進

4、的最短路徑算法計算過程。改進的算法以 Lin J提出的廣度優(yōu)先最短路徑并行算法（PBFS_SP）為思想基礎(chǔ)，進行改進設(shè)計。通過搭建 Had oop云平臺，將改進的算法與PBFS_SP算法和Dijkstra算法進行了實驗對比分析。實驗表明改進算法在網(wǎng)絡(luò)規(guī)模達到一定程度時相較 Dijkstra算法計算效率得到了較大的提高，在大規(guī)模的網(wǎng)絡(luò)下，三個算法中改進算法計算效率最高。
　　（四）最后，在模擬的應急場景下，將本文算法 H_PGNSP