期刊文献+

地标导向的启发式路径规划算法 被引量:2

Landmark-oriented heuristic routing algorithm in traffic network
下载PDF
导出
摘要 为提高大规模交通网络路径规划算法的查询效率,以A*算法为基础,提出一种地标导向的启发式算法。在预处理中将重要的顶点和边选为地标,在点对点寻径时使用地标作为启发式函数的启发参数,并进行分段计算。实验结果表明,此算法在处理长距离的路径规划问题时有较高的查询效率和更合理的计算结果。 To improve the query efficiency of road routing algorithm in large-scale traffic network,a landmark-oriented algorithm based on A* algorithm was proposed.Select the most important vertexes and edges as landmarks during preprocessing,choose appropriate landmarks as the reference parameters and calculate in sections in point-to-point routing.The experimental results indicate that it has higher query efficiency and more reasonable results in long-distance road routing.
作者 孟珂 张春艳
出处 《计算机应用》 CSCD 北大核心 2012年第4期1053-1055,共3页 journal of Computer Applications
关键词 路径规划 地标 预处理 层次缩减算法 三角启发算法 path-planning landmark preprocessing Contraction Hierarchies(CH) algorithm A* Landmarks Triangle(ALT) algorithm
  • 相关文献

参考文献12

  • 1DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959(1):269-271.
  • 2GOLDBERG A V,KAPLAN H,WERNECK R F.Reach for A*:Efficient point-to-point shortest path algorithms[C]//Proceedingsof 7th International Workshop on Algorithm Engineeringand Experiments.Miami:SIAM,2006:129-143.
  • 3GOLDBERG A V,KAPLAN H,WERNECK R F.Better landmarks within reach[C]//WEA'07:Proceedings of the 6th International Conference onExperimental Algorithms.Berlin:Springer-Verlag,2007:38-51.
  • 4GEISBERGER R,SANDERS P,SCHULTES D,et al.Contraction hierarchies:faster and simplerhierarchical routing in road networks[C]//WEA'08:Proceedings of the 7th InternationalConference on Experimental Algorithms.Berlin:Springer-Verlag,2008:319-333.
  • 5KHLER E,MHRING R H,SCHILLING H.Fast point-to-point shortest path computations witharc-flags[C]//The Shortest Path Problem:NinthDIMACS Implementation Challenge.Piscataway:IEEE,2009:41-72.
  • 6LAUTHER U.An extremely fast,exact algorithm for finding shortestpaths in static networks with geographical background[EB/OL].[2011-07-02].http://gi-days.de/archive/2004/downloads/gi-tage2004/vortraege/lauther.pdf.
  • 7BAUER R,DELLING D.SHARC:Fast and robust unidirectionalrouting[J].ACM Journal of Experimental Algorithmics,2009,14(12):12-26.
  • 8DELLING D.Time-dependent SHARC-routing[J].Algorithmica,2009,60(7):60-94.
  • 9GOLDBERG A V,HARRELSON C.Computing the shortest path:A*search meets graph theory,#MSR-TR-2004-24[R].USA:Mi-crosoft Research,2004.
  • 10BAST H,FUNKE S,SANDERS P,et al.Fast routing in road networkswith transit nodes[J].Science,2007,316(5824):566-593.

同被引文献20

  • 1林澜,闫春钢,蒋昌俊,周向东.动态网络最短路问题的复杂性与近似算法[J].计算机学报,2007,30(4):608-614. 被引量:17
  • 2Dijkstra E. A Note on Two Problems in Connexion with Graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.
  • 3Delling D, Hoffmann R, Kandyba M, et al. Chapter 9. Case Studies[J]. Algorithm Engineering, 2010:389-445.
  • 4Dantzig GB. On the Shortest Route through A Network[J]. Management Science,1960, 6(2): 187-190.
  • 5Hart PE, Nilsson NJ, Raphael B. A Formal Basis for the Heuristic Determination of Minimnm Cost Paths[J]. Systems Science and Cybernetics, IEEE Transactions on, 1968, 4(2): 100-107.
  • 6Gutman R. Reach-based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks[C]. The 6th Workshop on Algorithm Engineering and Experiments, 2004.
  • 7Goldberg AV, Werneck RF. Computing Point-to-point Shortest Paths from External Memory[C]. SIAM Workshop on Algorithms Engineering and Experimentation, Vancouver, Canada, 2005.
  • 8Mohring RH, Schilling H, Sch ii tz B, et al Partitioning Graphs to Speedup Dijkstra's Algorithm[J]. Journal of Experimental Algorithmics, 2007.
  • 9Delling D, Sanders P, Schultes D, et al. Highway Hierarchies Star[C]. The 9th DIMACS Implementation Challenge, 2006.
  • 10Goldherg A, Kaplan H, Werneck R. Better Landmarks within Reach[J]. Experimental Algorithms,2007:38-51.

引证文献2

二级引证文献1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部