基于Dijkstra算法的货运索道路径规划方法

doi:10.6040/j.issn.1672-3961.0.2022.187

摘要/Abstract

摘要： 为解决路径规划算法缺失、路径规划周期长、劳动强度大等货运索道路径规划难题,基于Dijkstra算法对索道路径规划问题进行了环境建模,并结合地形曲线、索道架设限制条件、路径规划目标函数等提出货运索道路径规划的邻接矩阵构建方法;结合货运索道的路径规划特点,对Dijkstra算法的搜索方向进行优化,有效降低了路径搜索的计算量。提出基于Dijkstra算法的货运索道路径规划方法。对十万个二维地形曲线进行路径搜索,本研究算法搜索出的符合索道架设要求的路径数量比已有算法(地形搜索法、干涉点搜索法和地形自适应法3种)搜索出的符合索道架设要求的路径数量提高了17.9%,且能够根据目标函数规划出最优路径,大幅度减少货运索道路径规划工作的时间和工作量,有效地降低索道架设和运输的成本。

关键词: 货运索道, 最优路径, 路径规划, Dijkstra算法, 环境建模

中图分类号:

TM754

张飞凯,黄永忠,李连茂,秦剑,刘晨. 基于Dijkstra算法的货运索道路径规划方法[J]. 山东大学学报 (工学版), 2022, 52(6): 176-182.

ZHANG Feikai, HUANG Yongzhong, LI Lianmao, QIN Jian, LIU Chen. Planning method of freight ropeway path based on Dijkstra algorithm[J]. Journal of Shandong University(Engineering Science), 2022, 52(6): 176-182.

参考文献

[1] SZLOSAREK R, YAN C, KRGER M, et al. Energy efficiency of ropeways: a model-based analysis[J]. Public Transport, 2019, 11(3): 617-635.
[2] 李靖. 货运索道自动化关键技术研究与应用[D]. 成都: 西南交通大学, 2014. LI Jing. Research and application of key technology of freight ropeway automation[D]. Chengdu: Southwest Jiaotong University, 2014.
[3] 李攀, 李志斌, 谢芳毅, 等. 三维GIS辅助山区输电线路货运索道选线系统设计[J]. 数字技术与应用, 2016,(5): 173-174. LI Pan, LI Zhibin, XIE Fangyi, et al. Design of freight ropeway selection system for mountain power transmission line assisted by 3D GIS[J]. Digital Technology and Application, 2016,(5): 173-174.
[4] 秦剑, 张飞凯, 江明, 等. 基于地形搜索的输电线路货运索道支架设置方法及系统: 202110537673.0[P]. 2021-09-14.
[5] 秦剑, 张飞凯, 江明, 等. 基于干涉点搜索输电线路货运索道支架设置方法及系统: 202110537471.6[P]. 2021-09-03.
[6] 秦剑, 张飞凯, 江明, 等. 一种基于地形自适应构建输电线路货运索道的方法及系统: 202110537644.4[P]. 2021-09-17.
[7] 秦剑, 张飞凯, 江明, 等. 一种输电线路施工物料运输路径规划方法及系统: 202110537738.1[P]. 2021-09-14.
[8] KAVRAKI L E, SVESTKA P, LATOMBE J C, et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation, 1996, 12(4): 566-580.
[9] 郑秀敏, 顾大鹏, 刘相术. 基于栅格法-模拟退火法的机器人路径规划[J]. 微计算机信息, 2007, 23(5): 247-248. ZHENG Xiumin, GU Dapeng, LIU Xiangshu. Robot path planning based on grid method with simulated annealing[J]. Science and Technology & Innovation, 2007, 23(5): 247-248.
[10] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1): 269-271.
[11] 熊壬浩, 刘羽. A*算法的改进及并行化[J]. 计算机应用, 2015(7): 45-50. XIONG Renhao, LIU Yu. Improvement and parall-elization of A* algorithm [J]. Journal of Computer Applications, 2015(7): 45-50.
[12] HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost path[J]. IEEE Transportations on Systems Science and Cybernetics, 1965, 4(2):100-107.
[13] KHATIB O. Real-time obstacle avoidance for mani-pulators and mobile robots[C] // Proceedings of 1985 IEEE International Conference on Robotics and Automation. St. Louis, USA:IEEE, 1985.
[14] 袁曾任. 人工神经元网络及其应用[M]. 北京: 清华大学出版社, 1999. YUAN Zengren. Artificial neural network and its application[M]. Beijing: Tsinghua University Press, 1999.
[15] ORESKI S, ORESKI D, ORESKI G. Hybrid system with genetic algorithm and artificial neural networks and its application to retail credit risk assessment[J]. Expert Systems with Applications, 2012, 39(16): 12605-12617.
[16] STUTZLE T, HOOS H. Max-min ant system and local search for the traveling salesman problem[C] // Proceedings of 1997 IEEE International Conference on Evolutionary Computation(ICEC '97). Indianapolis, USA:IEEE, 2002.
[17] 王璇. 遗传算法的改进及其应用研究[D]. 北京: 华北电力大学(北京), 2010. WANG Xuan. Research on improvement and application of genetic algorithm[D]. Beijing: North China Electric Power University(Beijing), 2010.
[18] BEED R S, SARKAR S, ROY A, et al. A hybrid multi-objective carpool route optimization technique using genetic algorithm and A* algorithm[J]. Computer Research and Modeling, 2021, 13(1): 67-85.
[19] HE Z, ZHAO L. The comparison of four UAV path planning algorithms based on geometry search algorithm[C] // 2017 9th International Conference on Intelligent Human-Machine Systems and Cybernetics(IHMSC). Hangzhou, China:IEEE, 2017.
[20] 薛峰会, 周瑞涛. 利用Dijkstra与A*算法实现船舶导航算路[J]. 舰船科学技术, 2017, 39(6): 81-83. XUE Fenghui, ZHOU Ruitao. Using Dijkstra and A* algorithm to implement ship navigation arithmetic[J]. Ship Science and Technology, 2017, 39(6): 81-83.
[21] SZCZEPANSKI R, TARCZEWSKI T. Global path planning for mobile robot based on artificial bee colony and Dijkstra's algorithms[C] // IEEE 19th International Power Electronics and Motion Control Conference(PEMC). Gliwice, Poland:IEEE, 2021.
[22] 向敏, 陈诚. 基于改进Dijkstra算法的配用电通信网流量调度策略[J]. 计算机应用, 2018, 38(6):1715-1720. XIANG Min, CHEN Cheng. Traffic scheduling strategy based on improved Dijkstra algorithm for power distribution and utilization communication network [J]. Journal of Computer Applications, 2018, 38(6): 1715-1720.
[23] 江渝, 叶泓炜, 张青松, 等. 能源互联网中基于Dijkstra算法的分布式电能路由策略的实现[J]. 电网技术, 2017, 41(7): 2071-2078. JIANG Yu, YE Hongwei, ZHANG Qingsong, et al. Implementation of distributed power routing strategy based on Dijkstra algorithm in energy internet[J]. Implementation of Distributed Power Routing Strategy Based on Dijkstra Algorithm in Energy Internet, 2017, 41(7): 2071-2078.
[24] 乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现[J]. 武汉测绘科技大学学报, 1999, 24(3): 209-212. LE Yang, GONG Jianya. An efficient implementation of shortest path algorithm based on Dijkstra algorithm[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1999, 24(3): 209-212.
[25] 叶颖诗, 魏福义, 蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65. YE Yingshi, WEI Fuyi, CAI Xianzi. Research on fast Dijkstra algorithm based on parallel computing[J]. Computer Engineering and Applications, 2020, 56(6): 58-65.
[26] ZHOU Y, HUANG N. Airport AGV path optimization model based on ant colony algorithm to optimize Dijkstra algorithm in urban systems[J]. Sustainable Computing: Informatics and Systems, 2022, 35: 100716.
[27] AKRAM M, HABIB A, ALCANTUD J C R. An optimization study based on Dijkstra algorithm for a network with trapezoidal picture fuzzy numbers[J]. Neural Computing Application, 2021, 33:1329-1342.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed