快速路径寻优的GIS网络数据结构设计及算法研究

论文摘要

随着GIS在物流决策中的广泛应用,在大量物流优化模型中,要求GIS系统能够快速求解复杂道路网络中的最短路问题。本文根据GIS网络中结点度数小、多等级干道、道路的车辆通行限制等特点,针对单源点最短路问题,通过对GIS道路网络的重新构建,设计了一种层次数据结构,并以Dijkstra算法为基础算法设计了一种双向搜索算法,可较大幅度地降低在每次优化计算中的重复计算量。首先,在GIS网络的层次数据结构构建部分,采用两阶段法选出GIS网络的主干道,构成主干道网络。其中,应用Dijkstra算法对每个点生成一个树型图,采用一些规则在树型图中沿着从树叶向树根的方向分辨出主干道,进一步对由主干道构成的网络进行压缩处理后,再次应用两阶段法确定出主干道网络;如此重复多次,便可构建出多级干道网络。在构建过程中,本文考虑了GIS道路网络中存在行车吨位限制的情形。其次,在Dijkstra算法为基础算法的双向搜索算法设计部分,给出一系列搜索规则,包括:从出发点和目的点双向搜索时低级干道网络进入高级干道网络的限制规则;同级干道网络入口点领域内搜索规则;以及双向搜索过程中出现相遇时的中断规则。可以证明,基于这些规则的双向搜索算法为最优算法。

论文目录

• 中文摘要
• ABSTRACT
• 1 引言
• 1.1 研究背景
• 1.2 研究意义
• 1.3 研究内容
• 2 GIS拓扑网络结构
• 2.1 GIS概述
• 2.2 GIS道路网络特征
• 2.3 GIS拓扑网络结构
• 2.4 GIS最短路查询功能
• 3 算法综述
• 3.1 最优化算法
• 3.1.1 标号方法
• 3.1.2 BF和BFP算法
• 3.1.3 Dijkstra算法和DIKB算法
• 3.1.4 DIKBM、DIKBA、DIKBD算法
• <sub>Q算法'>3.1.5 PAPE、TWO_<sub>Q算法
• 3.1.6 Threshold算法
• 3.1.7 Topological Ordering算法
• 3.2 启发式算法
• 4 GIS网络的层次数据结构
• 4.1 干道网络的构建
• 4.1.1 干道判别准则
• 4.1.2 干道判别的两阶段方法
• 4.2 干道网络的压缩
• 4.3 GIS网络的多级干道网络
• 4.4 GIS网络的层次数据结构
• 5 基于GIS多级干道网络的最短路算法
• 5.1 双向搜索算法原理
• 5.2 双向搜索算法的约束规则
• 5.3 双向算法搜索的中止规则
• 5.4 基于GIS多级干道网络的最短路算法
• 6 总结
• 参考文献
• 致谢
• 附录