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

doi:10.3976/j.issn.1002-4026.2018.02.011

山东科学 ›› 2018, Vol. 31 ›› Issue (2): 64-71.doi: 10.3976/j.issn.1002-4026.2018.02.011

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

陆文琦，谷远利，李萌，王硕，张源

北京交通大学城市交通复杂系统理论与技术教育部重点实验室，北京 100044

收稿日期:2017-06-14 出版日期:2018-04-20 发布日期:2018-04-20
作者简介:陆文琦（1993—），男，硕士研究生，研究方向为交通运输规划与管理。E-mail：16120863@bjtu.edu.cn
基金资助:
国家重点基础研究发展计划（973计划）(2012CB725403)；北京市科技计划项目(Z121100000312101)

An algorithm for point to point shortest paths based on preprocessing

LU Wen-qi, GU Yuan-li, LI Meng, WANG Shuo, ZHANG Yuan

MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing 100044, China

Received:2017-06-14 Online:2018-04-20 Published:2018-04-20

摘要/Abstract

摘要：

基于经典的Dijkstra算法，研究采用预处理的点到点最短路径算法。通过引入双向Dijkstra和基于reach的预处理方法形成新的RE算法，并利用C++编程设计算法程序，将新算法应用于交通工程领域。利用EFSS数据结构搭建考虑交叉口和路段延误的交通网络，检验新算法的适用性和效率，结果发现RE算法与Dijkstra算法相比，搜索速度有大幅提升且能保证路径查询的正确性，RE算法在大规模网络上优势更为显著，查询时间约为Dijkstra算法的10%。

关键词: 双向Dijkstra算法, RE算法, 路径优化, 基于reach的剪枝方法

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

中图分类号:

U116.2

陆文琦，谷远利，李萌，王硕，张源. 基于预处理的点到点最短路径计算方法[J]. 山东科学, 2018, 31(2): 64-71.

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.

参考文献

［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.

[1]	邵文, 贾顺平, 曹文娟. 基于混合车型的灵活型接驳公交路径协同优化研究[J]. 山东科学, 2019, 32(4): 64-73.
[2]	陈胜波，刘永平，何世伟，黎浩东. 整车物流双层轿运车车辆装载与路径整合优化研究[J]. 山东科学, 2017, 30(3): 73-81.

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

An algorithm for point to point shortest paths based on preprocessing

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

Metrics

本文评价

推荐阅读 0