交通运输网络的二叉堆索引及路径算法优化

doi:10.3969/j.issn.0255-8297.2020.06.012

应用科学学报 ›› 2020, Vol. 38 ›› Issue (6): 955-965.doi: 10.3969/j.issn.0255-8297.2020.06.012

• 信号与信息处理 • 上一篇

交通运输网络的二叉堆索引及路径算法优化

王亚¹, 任燕¹, 夏林元²

1. 遵义师范学院信息工程学院, 贵州遵义 563000;
2. 中山大学地理科学与规划学院, 广东广州 510275

收稿日期:2019-10-30 发布日期:2020-12-08
通信作者: 王亚,博士,研究方向为GIS及大数据应用.E-mail:1412560051@qq.com E-mail:1412560051@qq.com
基金资助:
国家自然科学基金（No.61562049）；贵州省教育厅“125计划”重大专项项目基金（黔教合重大专项字No.[2015]044）资助

Index of Binary Heap for Transportation Network and Optimization of Shortest Path Algorithms

WANG Ya¹, REN Yan¹, XIA Linyuan²

1. School of Information Engineering, Zunyi Normal College, Zunyi 563000, Guizhou, China;
2. School of Geography and Planning, Sun Yat-sen University, Guangzhou 510275, Guangdong, China

Received:2019-10-30 Published:2020-12-08

摘要/Abstract

摘要： 交通运输网络的最短路径分析是地理信息系统网络分析最常见的应用之一.该文在二叉堆索引结构的基础上改进了计算最短路径的Dijkstra算法和A^*算法，采用了多种优化策略提高算法的运行效率.首先，应用二叉堆索引提高了交通运输网络存储结构的读取效率；其次，通过数据类型的低精度损耗简化和运算类型的简化，提高了算法的计算效率.另外，优化了A^*算法中估计函数的计算方式，有效降低了搜索空间，提高了Dijkstra算法和A^*算法的整体计算效率.实验结果表明Dijkstra算法的改进方法可使计算速度提高7倍以上，对A^*算法的改进可使计算速度提高200倍以上.

关键词: 地理信息系统, 网络分析, 最短路径, 二叉堆, Dijkstra算法, A*算法

Abstract: Shortest path finding of transportation network is one of the commonest application scenes for geographic information system network analysis. This paper improves Dijkstra and A^* algorithms based on binary heap index. It presents several optimal strategies to improve the efficiency of both algorithms. Firstly, it uses binary heap index to improve the access efficiency of storage structure in GIS networks. Then it simplifies the data types and operation types as keeping the precision of data calculation of algorithms. Additionally, it decreases searching space effectively by optimizing the estimation function of A^* algorithm. Experimental results show that the improvement makes Dijkstra algorithm up to 7 times and A^* algorithm up to 200 times faster than before.

Key words: geographic information system (GIS), network analysis, shortest path, binary heap, Dijkstra algorithm, A^* algorithm

中图分类号:

TP301.6

王亚, 任燕, 夏林元. 交通运输网络的二叉堆索引及路径算法优化[J]. 应用科学学报, 2020, 38(6): 955-965.

WANG Ya, REN Yan, XIA Linyuan. Index of Binary Heap for Transportation Network and Optimization of Shortest Path Algorithms[J]. Journal of Applied Sciences, 2020, 38(6): 955-965.

参考文献

[1] 张波良, 张瑞昌, 关佶红. 道路网上最短路径算法综述[J]. 计算机应用与软件, 2014, 10(2):1-9. Zhang B L, Zhang R C, Guang J H. A survey on shortest path algorithm in road networks[J]. Computer Applications and Software. 2014, 10(2):1-9. (in Chinese)
[2] Cherkassky B V, Goldberg A V, Radzik T. Shortest paths algorithms theory and experimental evaluation[J]. Mathematical Programming, 1996, 73:129-174.
[3] 王树西, 吴政学. 改进的Dijkstra最短路径算法及其应用研究[J]. 计算机科学, 2012, 5(1):223-228. Wang S X, Wu Z X. Improved Dijkstra shortest path algorithm and its application[J]. Computer Science, 2012, 5(1):223-228. (in Chinese)
[4] 段莉琼, 朱建军, 王庆社, 等. 改进的最短路径搜索A^*算法的高效实现[J]. 海洋测绘, 2004, 9(1):20-22. Duan L Q, Zhu J J, Wang Q S, et al. Fast realization of the improved A^* algorithm for shortest route[J]. Hydrographic Surveying and Charting, 2004, 9(1):20-22. (in Chinese)
[5] 陆锋. 最短路径算法:分类体系与研究进展[J]. 测绘学报, 2001, 8(1):269-275. Lu F. Shortest path algorithms taxonomy and advance in research[J]. Acta Geodaetica et Cartographica Sinica, 2001, 8(1):269-275. (in Chinese)
[6] 乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报, 1999, 24(3):209-211. Yue Y, Gong J Y. An efficient implementation of shortest path algorithm based on Dijikstra algorithm[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1999, 24(3):209-211. (in Chinese)
[7] Domenico C, Simone F. Two-levels-greedy:a generalization of Dijkstra's shortest path algorithm[J]. Electronic Notes in Discrete Mathematics, 2004:81-86.
[8] Hassanzadeh R, Mahdavi-Amiri N. A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths[J]. Mathematical and Computer Modeling, 2013, 57(1/2):84-99.
[9] 闫春望, 黄玮, 王劲松. 一种并行模糊神经网络最短路径算法[J]. 计算机应用研究, 2016, 11(1):3391-3395 Yan C W, Huang W, Wang J S. Parallel fuzzy neural network shortest plan algorithm[J]. Application Research of Computers, 2016, 11(1):3391-3395. (in Chinese)
[10] Kumar P, Kumar A. Linear programming approach for solving fuzzy critical path problems with fuzzy parameters[J]. Applied Soft Computing, 2014, 21:309-319.
[11] Klunder G A, Post H N. The shortest path problem on large-scale real-road networks[J]. Networks, 2006(4):182-194.
[12] 范林林, 李翔, 张晶. 基于不同交通工具多约束条件的最短路径算法研究[J]. 测绘工程, 2016, 12(1):32-37. Fan L L, Li X, Zhang J. Research on shortest path selection based on different transportation under multiple constraints[J]. Engineering of Surveying and Mapping, 2016, 12(1):32-37. (in Chinese)
[13] Jafee J M. Algorithms for finding paths with multiple constraints[J]. Networks, 1984, 14:95-116.
[14] Wagner D, Willhalm T, Zarliagis C. Geometric containers for efficient shortest-path computation[J]. ACM Journal of Experimental Algorithmics, 2005, 10(12):1-30.
[15] Lauther U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background[J]. Geoinformation und Mobilität-von der Forschung zur Praktischen Anwendung, 2004, 22:219-230.
[16] Bazlamacci C F, Hindi K S. Minimum-weight spanning tree algorithms:a survey and empirical study[J]. Computers and Operations Research, 2001(8):767-785.
[17] 李晶, 闫军. 基于Dijkstra算法和Floyd算法的物流运输最短路径研究[J]. 科技信息, 2012, 34(1):575-576. Li J, Yan J. Shortest path finding in transportation based on Dijkstra and Floyd algorithm[J]. Science & Technology Information, 2012, 34(1):575-576. (in Chinese)
[18] 宫恩超, 李鲁群. 基于Bellman-Ford算法的动态最优路径算法设计[J]. 测绘通报, 2011, 8(1):26-28. Gong E C, Li L Q. The optimal path algorithm design based on Bellman-Ford algorithm[J]. Bulletin of Surveying and Mapping, 2011, 8(1):26-28. (in Chinese)
[19] 徐建闽, 王钰, 林培群. 大数据环境下的动态最短路径算法[J]. 华南理工大学学报(自然科学版), 2015, 10(1):1-7. Xu J M, Wang Y, Lin P Q. A dynamic shortest path algorithm for big data[J]. Journal of South China University of Technology (Natural Science Edition), 2015, 10(1):1-7. (in Chinese)
[20] Said B, Arindam D, Mohamed T, et al. Shortest path problem using Bellman algorithm under neutrosophic environment[J]. Complex & Intelligent Systems, 2019, 12:409-416.
[21] Festa P, Guerriero F, Napoletano A. An auction-based approach for the re-optimization shortest path tree problem[J]. Computational Optimization and Applications, 2019, 12:851-893.
[22] Daniele F, Paola F, Francesca G. An efficient exact approach for the constrained shortest path tour problem[J]. Optimization Methods & Software, 2019, 12:1-20.

交通运输网络的二叉堆索引及路径算法优化

Index of Binary Heap for Transportation Network and Optimization of Shortest Path Algorithms

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价

[1]	胡恩祥, 汪春雨, 潘美芹. 基于密度峰值剪枝后的最短路径聚类算法[J]. 应用科学学报, 2020, 38(5): 792-802.
[2]	张晓宁, 孔祥真, 罗传文, 刘金星. 用于样本聚类和网络分析的整合鲁棒结构化NMF模型[J]. 应用科学学报, 2020, 38(5): 825-842.
[3]	杨绍文, 闫光辉, 李雷, 张海涛. 基于活跃点的社区跟踪算法[J]. 应用科学学报, 2017, 35(5): 602-611.
[4]	李军华, 刘群芳. 基于稀疏A*算法与文化算法的无人机动态航迹规划[J]. 应用科学学报, 2017, 35(1): 128-138.
[5]	阮柏林1，王晶1，刘蕊1，余林清2. 土地利用规划综合业务信息一体化关键技术与应用[J]. 应用科学学报, 2015, 33(4): 429-437.
[6]	朱俊杰1,2，杜小平1,2，范湘涛1,2，郭华东1,2. GIS数据约束的海岸带SAR图像多尺度分割[J]. 应用科学学报, 2013, 31(1): 79-83.
[7]	解建仓, 王晓辉, 李建勋, 罗军刚. WMS下的WebGIS开发及与水环境信息服务平台集成[J]. 应用科学学报, 2006, 24(3): 265-269.