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

摘要

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