基于Hadoop的GIS网络最短路径算法研究

摘要

最短路径分析作为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平台兼容，在空间可视化表达上具有一定的优势，效率也得到了较好的提高。

目录

声明

第一章 绪论

1.1 论文研究背景与意义

1.2 国内外研究现状

1.3 主要研究内容

1.4 论文组织结构

第二章 Hadoop平台与GIS相关技术

2.1 分布式文件系统HDFS

2.2 MapReduce编程模型

2.3 分布式数据库HBASE

2.4 GIS相关技术

2.5 本章小结

第三章 基于Hadoop的GIS网络最短路径算法分析与设计

3.1 Dijkstra与并行广度优先的最短路径算法介绍

3.2 Hadoop下GIS网络最短路径算法的问题分析

3.3 Hadoop下GIS网络最短路径算法的设计

3.4 本章小结

第四章 基于Hadoop的GIS网络最短路径算法实现

4.1 Hadoop下GIS网络最短路径算法实现

4.2 Hadoop集群搭建及实验结果对比分析

4.3 基于ArcGIS API for JavaScript 的结果展示

4.4 本章小结

第五章 总结与展望

5.1 论文总结

5.2 未来展望

参考文献

附录

附录A NodeHbase类部分代码

致谢