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

doi:10.3969/j.issn.0255-8297.2020.06.012

Abstract

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

CLC Number:

TP301.6

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

Comments

[1]	HU Enxiang, WANG Chunyu, PAN Meiqin. Clustering by Pruning Paths Based on Shortest Paths from Density Peaks [J]. Journal of Applied Sciences, 2020, 38(5): 792-802.
[2]	ZHANG Xiaoning, KONG Xiangzhen, LUO Chuanwen, LIU Jinxing. Integrated Robust Structured NMF Model for Sample Clustering and Network Analysis [J]. Journal of Applied Sciences, 2020, 38(5): 825-842.
[3]	YANG Shao-wen, YAN Guang-hui, LI Lei, ZHANG Hai-tao. Community Tracking Algorithm Based on Active Points [J]. Journal of Applied Sciences, 2017, 35(5): 602-611.
[4]	ZHU Jun-jie1,2, DU Xiao-ping1,2, FAN Xiang-tao1,2, GUO Hua-dong1,2. GIS-Constrained Multi-scale Coastal SAR Image Segmentation [J]. Journal of Applied Sciences, 2013, 31(1): 79-83.