基于路网压缩策略的改进Highway

Improved Highway Hierarchical Algorithm Based on Contracted Network Strategy

摘要:

针对Highway Hierarchical算法中存在的路网压缩成环问题、预处理数据存储问题和完整最短路计算问题，采用无环压缩策略、分层存储策略和局部最短路存储策略，对算法进行了改进.广东省路网测试结果表明，改进后的算法在时间效率上约是原算法的5倍，在空间效率上约是原算法的4倍.

Abstract:

In the pretreatment process, Highway Hierarchical(HH) algorithm faces such problems as the compressing of network into a ring road, the storage way of pretreatment data and a complete calculation of the optimal route. Non cycle compressing, tiered storage and local shortest path storage are introduced to improve the efficiency of the algorithm. The test of the road network of Guangdong Province of China shows that with the improved HH algorithm, the computational efficiency increases by 5 times, and the search space reduces by 4 times.