地标导向的启发式路径规划算法

doi:10.3724/SP.J.1087.2012.01053

计算机应用 ›› 2012, Vol. 32 ›› Issue (04): 1053-1055.DOI: 10.3724/SP.J.1087.2012.01053

地标导向的启发式路径规划算法

孟珂,张春艳

中国矿业大学计算机科学与技术学院,江苏徐州 221008

收稿日期:2011-09-07 修回日期:2011-11-13 发布日期:2012-04-20 出版日期:2012-04-01
通讯作者: 孟珂
作者简介:孟珂(1987-),男,江苏徐州人,硕士研究生,CCF会员,主要研究方向：GIS、路径规划;
张春艳(1985-),女,江苏徐州人,硕士研究生,主要研究方向：云计算、蚁群算法。

Landmark-oriented heuristic routing algorithm in traffic network

MENG Ke,ZHANG Chun-yan

School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221008, China

Received:2011-09-07 Revised:2011-11-13 Online:2012-04-20 Published:2012-04-01
Contact: MENG Ke

摘要/Abstract

摘要： 为提高大规模交通网络路径规划算法的查询效率，以A*算法为基础，提出一种地标导向的启发式算法。在预处理中将重要的顶点和边选为地标，在点对点寻径时使用地标作为启发式函数的启发参数，并进行分段计算。实验结果表明，此算法在处理长距离的路径规划问题时有较高的查询效率和更合理的计算结果。

关键词: 路径规划, 地标, 预处理, 层次缩减算法, 三角启发算法

Abstract: 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.

Key words: path-planning, landmark, preprocessing, Contraction Hierarchies (CH) algorithm, A* Landmarks Triangle (ALT) algorithm

孟珂张春艳. 地标导向的启发式路径规划算法[J]. 计算机应用, 2012, 32(04): 1053-1055.

MENG Ke ZHANG Chun-yan. Landmark-oriented heuristic routing algorithm in traffic network[J]. Journal of Computer Applications, 2012, 32(04): 1053-1055.

参考文献

［1］ DIJKSTRA E W. A note on two problems in connexion with graphs ［J］. Numerische Mathematik, 1959(1):269-271. ［2］ GOLDBERG A V, KAPLAN H, WERNECK R F. Reach for A*: Efficient point-to-point shortest path algorithms ［C］// Proceedings of 7th International Workshop on Algorithm Engineering and Experiments. Miami: SIAM, 2006:129-143. ［3］ GOLDBERG A V, KAPLAN H, WERNECK R F. Better landmarks within reach［C］// WEA07: Proceedings of the 6th International Conference on Experimental Algorithms. Berlin: Springer-Verlag,2007:38-51. ［4］ GEISBERGER R, SANDERS P, SCHULTES D, et al. Contraction hierarchies: faster and simpler hierarchical routing in road networks［C］// WEA08: Proceedings of the 7th International Conference on Experimental Algorithms. Berlin: Springer-Verlag,2008:319-333. ［5］ KHLER E, MHRING R H, SCHILLING H. Fast point-to-point shortest path computations with arc-flags［C］// The Shortest Path Problem: Ninth DIMACS Implementation Challenge. Piscataway: IEEE, 2009:41-72. ［6］ LAUTHER U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background［EB/OL］.[2011-07-02].http://gi-days.de/archive/2004/downloads/gitage2004/vortraege/lauther.pdf. ［7］ BAUER R, DELLING D. SHARC: Fast and robust unidirectional routing ［J］. ACM Journal of Experimental Algorithmics, 2009, 14(12):12-26. ［8］ DELLING D. Time-dependent SHARC-routing ［J］. Algorithmica, 2009, 60(7): 60-94. ［9］ GOLDBERG A V, HARRELSON C. Computing the shortest path: A* search meets graph theory, #MSR-TR-2004-24 ［R］.USA: Microsoft Research, 2004. ［10］ BAST H, FUNKE S, SANDERS P, et al. Fast routing in road networks with transit nodes ［J］. Science, 2007,316(5824):566-593. ［11］ HILGER M. Accelerating point-to-point shortest path computations in large scale networks［R］. Berlin: Technische University, 2007. ［12］ SANDERS P, SCHULTES D. Highway hierarchies hasten exact shortest path queries［EB/OL］.[2011-06-06].http://algo2.iti.kit.edu/schultes/hwy/esaHwyHierarchies.pdf.

[1]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[3]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[4]	王家亮, 李树华, 张海涛. 基于贝叶斯估计与区域划分遍历的四轴飞行器避障路径规划算法[J]. 计算机应用, 2021, 41(2): 384-389.
[5]	李伟, 金世俊. 基于人工势场法和启发式采样的最优路径收敛方法[J]. 计算机应用, 2021, 41(10): 2912-2918.
[6]	刘思嘉, 童向荣. 基于强化学习的城市交通路径规划[J]. 计算机应用, 2021, 41(1): 185-190.
[7]	祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2021-2027.
[8]	徐晓强, 秦品乐, 曾建朝. 基于改进粒子群优化算法的牙齿正畸路径规划方法[J]. 计算机应用, 2020, 40(7): 1938-1943.
[9]	韩雨涝, 房鼎益. 联合无线充电与数据收集的移动充电装置多目标路径规划算法[J]. 计算机应用, 2020, 40(6): 1745-1750.
[10]	徐小强, 王明勇, 冒燕. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2020, 40(12): 3508-3512.
[11]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[12]	刘昂, 蒋近, 徐克锋. 改进蚁群和鸽群算法的机器人路径规划[J]. 计算机应用, 2020, 40(11): 3366-3372.
[13]	梅伟, 赵云涛, 毛雪松, 李维刚. 基于离散灰狼算法的喷涂机器人路径规划方法[J]. 计算机应用, 2020, 40(11): 3379-3384.
[14]	潘春霞, 杨秋辉, 谭武坤, 邓惠心, 伍佳. 软件缺陷预测中的数据预处理方法[J]. 计算机应用, 2020, 40(11): 3273-3279.
[15]	童心赤, 张华军, 郭航. 多方向无人水面艇路径规划算法[J]. 计算机应用, 2020, 40(11): 3373-3378.

地标导向的启发式路径规划算法

Landmark-oriented heuristic routing algorithm in traffic network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics