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

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

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