船舶与海洋工程

基于改进A*算法的管路初始路径优化

展开
  • (1.大连海事大学 船舶与海洋工程学院,辽宁 大连 116026;2.中国船舶重工集团应急预警与救援装备股份有限公司,武汉   430200 ) 
蒋勤文(1997 — ),男,硕士生,研究方向:机械工程;度红望*(1984 — ),男,博士,副教授,博士生导师, E-mail:jqw@dlmu.edu.cn
度红望*(1984 — ),男,博士,副教授,博士生导师, E-mail:jqw@dlmu.edu.cn

收稿日期: 2022-12-27

  修回日期: 2023-02-23

  录用日期: 2023-02-23

  网络出版日期: 2023-03-01

基金资助

国家自然科学基金资助项目(52075065);中央高校基本科研业务费专项资金资助项目(3132022340;3132019352)

Pipeline initial path optimization  based on improved A* algorithm 

Expand
  • (1. School of Naval Architecture and Ocean Engineering, Dalian Maritime University, Dalian 116026, China;2. China Harzone Industry CORP., LTD., Wuhan 430200 , China)

Received date: 2022-12-27

  Revised date: 2023-02-23

  Accepted date: 2023-02-23

  Online published: 2023-03-01

摘要

针对管路布局的效率和精度问题,提出一种基于改进A*算法的管路初始路径计算方法。考虑管路实际布局问题,获取管路的布局平面图。利用MATLAB的图像处理模块完成布局环境特征提取,利用栅格法完成布局空间预处理。基于A*算法对其搜索方向进行拓展,去除冗余节点并优化路径长度。考虑管路的弯曲约束,构建弯折数和弯曲半径的启发函数筛选路径关键节点,得到一条满足弯折约束和经济性约束的管路初始路径,以减少路径后处理的工作量。相比文献[13-14],本文算法计算的路径长度减少了3.3%,求解效率提高了28.98%,路径弯折节点减少了14.3%,提高了布局效率。实际布局场景测试表明,相比原A*算法,改进算法的路径长度同比减少了6.54%,效率同比提高了42.59%。

本文引用格式

蒋勤文, 度红望, 聂勇, 熊伟 . 基于改进A*算法的管路初始路径优化[J]. 大连海事大学学报, 2023 , 49(2) : 141 -147 . DOI: 10.16411/j.cnki.issn1006-7736.2023.02.015

Abstract

Aiming at the efficiency and precision problem of pipeline layout, a pipeline initial path calculation method based on improved A* algorithm was proposed. Considering the actual pipeline layout, the product plan was obtained for modeling the pipeline layout space. MATLAB image processing module was used to complete the feature extraction of the layout environment, and the grid method was used to complete the layout space preprocessing. Based on A* algorithm, the search direction was expanded to remove redundant nodes and optimize the path length. Considering the bending constraints of the pipeline, the heuristic function for the number of bends and bending radius was constructed to filter the key nodes of the path, and a pipeline initial path satisfying the bending constraints and economic constraints was obtained to reduce the workload of path post-processing. Compared with other algorithms in literature [13-14], the algorithm proposed in this paper reduces path length by 3.3%, improves solving efficiency by 28.98%, reduces path bending nodes by 14.3%, and improves layout efficiency. The actual layout scenario testing shows that compared to the original A* algorithm, the improved algorithm reduces the path length by 6.54% and improves efficiency by 42.59%.

参考文献

[1]HAYTHAM M D, HUSSEIN H, KASSEM G. Modular approach for optimal pipeline layout[J]. Journal of Petroleum Science and Engineering, 2021, 197:107934.
[2]王发麟,郭宇,查珊珊.复杂机电产品线缆虚实融合装配体系构建及其关键技术[J].图学学报,2018,39(1):75-84.
WANG F L, GUO Y, ZHA S S. Assembly system construction and its key techniques of cable harness under virtual and real scene fusion for complex mechatronic products[J]. Journal of Graphics, 2018,39(1):75-84. (in Chinese)
[3]NEUMAIER M, KRANEMANN S, KAZMEIER B, et al. Fully automated piping in an Airbus A320 landing gear bay using graph-based design languages[J]. IOP Conference Series: Materials Science and Engineering, 2022, 1226(1):012026.
[4]KIMURA H. Automatic piping arrangement design considering piping supports and curved surfaces of building blocks[C]//International Conference on Computer Applications in Shipbuilding, 2017: 26-28.
[5]DONG Z R, BIAN X Y. Ship pipe route design using improved A* algorithm and genetic algorithm[J]. IEEE Access, 2020, 8: 153273-153296.
[6]NGUYEN H, KIM D J, GAO J. 3D piping route design including branch and elbow using improvements for dijkstras algorithm[C]// 2016 International Conference on Artificial Intelligence: Technologies and Applications, 2016: 309-312.
[7]徐联杰,刘检华,何永熹,等.一种基于改进快速搜索随机树算法的管路自动布局方法[J].图学学报,2016,37(1):1-10.
XU L J, LIU J H, HE Y X, et al. A method for pipe auto layout based improved RRT algorithm[J]. Journal of Graphics,2016,37(1):1-10. (in Chinese)
[8]张禹,公健,唐滋阳,等.基于改进多目标人工蜂群算法的航空发动机管路智能布局方法[J].机械工程学报,2022,58(4):277-284.
ZHANG Y, GONG J, TANG Z Y, et al. Method for intelligent aeroengine pipeline layout based on improved multi-objective artificial bee colony algorithm [J]. Journal of Mechanical Engineering,2022,58(4):277-284. (in Chinese)
[9]KIM S, CHOI T, KIM S, et al. Sequential graph-based routing algorithm for electrical harnesses, tubes, and hoses in a commercial vehicle [J]. Journal of Intelligent Manufacturing, 2021,32(4):917-933.
[10]WANG Y L, YU Y Y, LI K, et al. A human-computer cooperation improved ant colony optimization for ship pipe route design[J]. Ocean Engineering, 2018, 150: 12-20.
[11]CANNAV A, BARDELLA C, SEMERARO L, et al.  An automatic 3D scene generation pipeline based on a single 2D image[C]//International Conference on Augmented Reality, Virtual Reality and Computer Graphics, 2021:109-117. 
[12]周广芬,李鹏,杨久义.利用MATLAB图像处理工具箱进行图形数字化的研究[J].河北科技大学学报,2005,26(4):309-311+321.
ZHOU G F,LI P, YANG J Y. Study of using the image processing toolbox of MATLAB to digitize graph [J]. Journal of Hebei University of Science and Technology,2005,26(4):309-311+321. (in Chinese)
[13]姜康,马世纪.基于改进A*算法的线缆路径规划方法[J].中国机械工程,2019,30(6):699-708.
JIANG K, MA S J. A cable path planning method based on improved A* algorithm [J]. China Mechanical Engineering,2019,30(6):699-708. (in Chinese)
[14]张成,凌有铸,陈孟元. 改进蚁群算法求解移动机器人路径规划[J].电子测量与仪器学报,2016,30(11):1758-1764.
ZHANG C, LING Y Z, CHEN M Y. Path planning of mobile robot based on an improved ant colony algorithm [J]. Journal of Electronic Measurement and Instrumentation, 2016, 30 (11): 1758-1764. (in Chinese)
[15]崔金龙,李元奎,索基源,等. 基于改进A*算法的船舶航向航速协同优化方法[J]. 大连海事大学学报,2022, 48(4): 29-37. 
CUI J L,LI Y K,SUO J Y,et al. Collaborative optimization method of ship course and speed based on improved A* algorithm[J]. Journal of Dalian Maritime University, 2022, 48(4): 29-37. (in Chinese)
[16]王军,朱芍颐,王冠卓,等.气象不确定下的船舶避台路径优化[J]. 大连海事大学学报, 2021, 47(2): 56-62. 
WANG J, ZHU S Y, WANG G Z, et al. Route optimization of ship avoiding typhoon under meteorological uncertainty[J]. Journal of Dalian Maritime University, 2021, 47(2): 56-62. (in Chinese)
文章导航

/