基于预处理的点到点最短路径计算方法

doi:10.3976/j.issn.1002-4026.2018.02.011

Abstract

Abstract:

Based on the classical Dijkstra algorithm, an algorithm for point to point shortest paths based on preprocessing was studied. The bidirectional Dijkstra algorithm and the reachbased preprocessing method were introduced to establish the new RE algorithm in this paper. The program of the new algorithm was compiled with C++ and the new algorithm was applied to traffic engineering field. Traffic networks considering delay on roads and intersections were constructed by using EFSS data structure to test the applicability and efficiency of RE algorithm. The results reveal that compared with the original Dijkstra algorithm, the RE algorithm has a significant increase in the search speed and can ensure the correctness of path query. On largescale networks, the new RE algorithm shows great advantages and its query time is approximately 10% of the Dijkstra algorithm.

Key words: reach-based pruning method, route optimization, RE algorithm, bidirectional Dijkstra algorithm

CLC Number:

U116.2

LU Wen-qi, GU Yuan-li, LI Meng, WANG Shuo, ZHANG Yuan. An algorithm for point to point shortest paths based on preprocessing[J].SHANDONG SCIENCE, 2018, 31(2): 64-71.

References

［1］DIJKSTRA E W. A note on two problems in connection with graphs [J]. Numerical Mathematics, 1959, 1(1)：269271.
［2］HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on System Science and Cybernetics, 1968, 4(2):100107.
［3］DORAN J E. An approach to automatic problemsolving [EB/OL].[20170302].https://aitopics.org/search? view=&filters=&sort=score+desc&q=An+approach+to+automatic+problem+solving+.
［4］付强. 基于预处理的交通网最短路径实时查询研究[D]. 合肥：中国科学技术大学,2015.
［5］PEARL J. Heuristics: Intelligent search strategies for computer problem solving[M]. MA, US： AddisonWesley Pub. Co., Inc., 1984.
［6］GOLDBERG A V, HARRELSON C. Computing the shortest path: A search meets graph theory [M]// Proceedings of the sixteenth annual ACMSIAM symposium on discrete algorithms. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2005:156165.
［7］GOLDBERG A V, KAPLAN H, WERNECK R F. Reach for A*: efficient pointtopoint shortest path algorithms [EB/OL]. [20170312]. http://epubs.siam.org/doi/abs/10.1137/1.9781611972863.13.
［8］SANDERS P, SCHULTES D. Highway hierarchies hasten exact shortest path queries [EB/OL]. [20170304].https://link.springer.com/chapter/10.1007/11561071_51.
［9］GEISBERGER R, SANDERS P, SCHULTES D, et al. Contraction hierarchies: Faster and simpler hierarchical routing in road networks[C]// International Workshop on Experimental Algorithms. Provincetown, MA, USA: [s.n.], 2008: 319333．
［10］SCHULTES D, SANDERS P. Dynamic highwaynode routing[M]// Proceedings of 6th International Workshop on Experimental Algorithms. Berlin: Springer, 2007: 6679.
［11］BAST H,FUNKE S,MATIJEVIC D,et al.In transit to constant time shortest path queries in road networks[EB/OL].[20170312].http://dx.doi.org/10.1137/1.9781611972870.5.
［12］ZILIASKOPOULOS A K,MAHMASSANI H S. Time dependent shortest path algorithm for real time intelligent vehicle highway system applications [J]. Transportation Research Board，1993(1408)：94100．
［13］ZILIASKOPOULOS A K,MAHMASSANI H S. A note on least time path computation considering delays and prohibitions for intersection movements [J]. Transportation Research Part B Methodological, 1996, 30(5):359367.
［14］GUTMAN R J. Reachbased routing: A new approach to shortest path algorithms optimized for road networks[C]// Proceedings of the Sixth Workshop on Algorithm Engineering & Experiments & the First Workshop on Analytic Algorithmics & Combinatorics. New Orleans, LA, USA: [s.n.], 2004: 100111.
［15］杜牧青,程琳.考虑交叉口转向延误的最短路径拍卖算法[J]. 西南交通大学学报,2010,45(2):249254.

An algorithm for point to point shortest paths based on preprocessing

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Metrics

Comments

Recommended 0