论文部分内容阅读
最短路径分析作为GIS中最重要的空间分析功能之一,已经广泛地应用于路径导航、管网优化设计、交通疏导等方面。随着交通路网、管道网络等设施的规模逐年扩大,由这些现实设施抽象出来的空间网络数据的规模也逐渐趋向于海量化。如何使大规模空间网络得到快速处理是GIS中最短路径算法所要面对的一个巨大挑战。单机环境下GIS平台的最短路径分析处理大规模网络数据会出现计算效率较低的情况,有时甚至会造成GIS软件运行崩溃。云计算平台Hadoop在处理大数据方面,具有运算效率高和应用成熟、稳定的优势。为此,本文对基于Hadoop的GIS网络最短路径算法进行了研究。(一)本文研究了GIS网络矢量数据在HBase中的存储与管理。根据GIS网络的数据结构进行解析,并通过适当的HBase表结构设计,解决了GIS网络在Hadoop下的存储问题,为GIS网络在Hadoop云平台中进行最短路径并行计算创造了前提条件。并且通过设计相关HBase表,实现了动态权重的赋值问题,使得最短路径算法能够延伸为最优路径算法。(二)本文设计了基于MapReduce的邻接表结构生成算法。该算法的设计结合了邻接表结构的特点与MapReduce的运行原理,在Hadoop平台下能有效地解决大规模GIS网络的邻接表结构生成问题。通过该算法过程得到的邻接表数据结构给本文最短路径算法提供了数据结构保障。(三)本文提出了基于Hadoop的GIS网络最短路径并行算法(H_PGNSP)。该算法流程除了上文所述的计算过程外,还包括改进的最短路径算法计算过程。改进的算法以Lin J提出的广度优先最短路径并行算法(PBFS_SP)为思想基础,进行改进设计。通过搭建Had oop云平台,将改进的算法与PBFS_SP算法和Dijkstra算法进行了实验对比分析。实验表明改进算法在网络规模达到一定程度时相较Dijkstra算法计算效率得到了较大的提高,在大规模的网络下,三个算法中改进算法计算效率最高。(四)最后,在模拟的应急场景下,将本文算法H_PGNSP用于救援路径的制定。算法计算结果通过GIS技术能与相关GIS平台无缝结合,且易于实现最短路径的空间可视化。研究结果表明,与单机GIS平台相比,本文算法可解决求解大规模网络最短路径的效率问题。而且相较于其他并行最短路径算法,本文算法能与相关GIS平台兼容,在空间可视化表达上具有一定的优势,效率也得到了较好的提高。