基于分块路径缓存的在线路径搜索算法

摘要

为建立一个高效的互联网在线地图服务路径搜索引擎,提出一种基于分块路径缓存的最短路径算法.对路网重采样得到路网密集度图像,提出路网分块算法ISODATA.根据路网子块构建路径缓存设计缓存路径索引算法,提出基于子块缓存路径与节点间动态路径结合的双向路径搜索算法.实验结果表明,该算法可将城市级在线路径搜索时间控制在0.2 s 以内,降低网络地图服务路径计算服务器负荷.