交通网络最短路径标号算法的实现与效率分析

Implementation and Evaluation of the Shortest Path Labeling Algorithms in Transportation Networks

标号算法是交通网络最短路径算法族中应用最广泛的算法,其中以各种D ijkstra算法为核心的标号设定算法是各种商用G IS平台网络分析算法的首选。然而,同样隶属于标号算法的标号改正算法在交通网络路径分析中却罕有应用。为了将标号改正算法应用于交通网络路径分析,首先讨论了标号算法的基本结构;然后分析了标号设定算法和标号改正算法的实现过程、复杂度、运行特点和适用性,进而选择了标号设定和标号改正算法中公认的几种优秀算法———基于逼近桶结构和改进四叉堆的D ijkstra算法(D IKBA与D IKQH)以及Pallottino算法(TWO-Q),并结合交通网络邻接链表结构予以实现;最后采用城市交通网络数据,对几种算法的实际运行效率进行了对比试验,试验结果表明,标号改正算法和标号设定算法优点各异;由于交通网络路径算法的应用越来越强调动态性和网络适用性,而且标号改正算法较之标号设定算法具有更大的适用范围,因此其在交通网络路径分析中具有极大的应用潜力。

Labeling algorithms have got broad applications for shortest path finding in transportation networks, among which various fine-tunned Dijkstra＇ s algorithms well known as typical label setting algorithms have been selected by many GIS related software for network analysis. However, label correcting algorithms, the other group in label algorithms family, are rarely used yet in GIS network analysis. After detailed discussion on the structures of labeling algorithms, in this paper, the implementation, complexity and applicability of labeling setting and label correcting algorithms are analyzed. Then three best-known fastest label algorithms, i, e. , Dijkstra algorithm implemented with approximate buckets（DIKBA） , Dijkstra＇ s algorithm based on quad-heap priority queue（ DIKQH ） and Pallottino algorithm（ TWO_Q） , were used tocarry out practical evaluation on three real urban road networks. The results showed that for one-to-one shortest path calculation, DIKQH and DIKBA greatly outperformed than TWO-Q algorithm, and DIKQH exhibited the best running efficiency. For one-to-all shortest path calculation, however, TWO-Q algorithm runs a little faster than DIKQH and DIKBA on the selected real road networks. The author argued that more attention should be paid on TWO-Q algorithm for its efficiency and applicability.