层次化网络优化算法设计与实现

Design and Implementation of Optimization Algorithm in Hierarchical Network

随着道路交通网络地图数据越来越复杂和庞大,为了最短路径搜索加速,通常按等级对道路交通网络地图进行层次化划分。针对层次化交通网络地图中"死节点"问题,设计并实现了一种优化算法以改善上层网络连通性,并通过真实交通网络数据对该算法进行了性能评估。评估数据表明,增加少量链路至上层网络后,上层网络搜索性能显著改善。

With the more complicated and huger map data of the road traffic networks, and to ac-celerate searching the shortest path, the road traffic network map is hierarchically divided accord-ing to the road rank. Aimed at the ＂dead-end＂ node problem in the hierarchical traffic network map, an optimization algorithm is designed and realized to improve the connectivity of the upper layer networks. Then, its performance is evaluated with the actual traffic network data. The e-valuation data show that the searching performance in the upper layer networks is obviously en-hanced after extracting small amount of links to the upper layer network.