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

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

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

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

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