加权路网分层的最优路径计算

An optimal path algorithm based on weighted hierarchical road network

为了弥补传统分层算法在平面最短路径计算中对出行者出行习惯考虑不充分的缺陷,该文提出了一种分层算法的优化策略,即加权路网分层:首先运用层次分析法计算选定的道路属性的权值,对道路属性权值进行组合相加,进而确定道路权值,然后根据确定的分层阈值对路网进行分层,最后运用双向A*算法进行试验,并与传统的分层路网计算结果进行比较。实验结果表明,加权分层策略充分考虑了出行者的出行习惯,能够适用于路径导航中的最优路径计算,具有可行性与实用性。

In order to make up the defects of the traditional hierarchical algorithm on inadequate consideration of the travelers＇ habits in the computation of planar shortest path algorithm,an optimization strategy named weighted hierarchical road network based on the traditional hierarchical algorithm was proposed in the paper.In this strategy,an analytic hierarchy process was firstly utilized to calculate the weights of each selected road property,based on the combination of which the weight of a road was also determined accordingly.Subsequently the hierarchical threshold was used to stratify the road network.At last,a two-way A Star algorithm was used to obtain the final shortest path.Compared with the traditional method,the weighted hierarchical strategy could significantly consider the travelers＇ travel habits,and be applicable for the optimal path algorithm in the path navigation with feasibility and practicability.