上海交通大学学报

上海交通大学学报 >

2025 , Vol. 59 >Issue 1: 79 - 88

DOI: https://doi.org/10.16183/j.cnki.jsjtu.2023.206

船舶海洋与建筑工程

基于网格归一化Astar算法的船舶管路布置

  • 林焰 ,
  • 张乔宇 ,
  • 楼建迪
展开
  • 1.大连理工大学 船舶工程学院, 辽宁 大连 116024
    2.宁波莱布尼茨信息技术有限公司, 浙江 宁波 315300
林焰(1963—),教授,博士生导师,从事船舶与海洋结构物数字化设计方法与软件开发研究.
张乔宇,博士生; E-mail:qiaoyuzhang@foxmail.com.

收稿日期: 2023-05-23

  修回日期: 2023-07-17

  录用日期: 2023-08-09

  网络出版日期: 2023-08-21

基金资助

国家重点实验室专项基金(S18315)

收起

Ship Pipe Layout Based on Grid Normalized Astar Algorithm

  • LIN Yan ,
  • ZHANG Qiaoyu ,
  • LOU Jiandi
Expand
  • 1. School of Naval Architecture and Ocean Engineering, Dalian University of Technology, Dalian 116024, Liaoning, China
    2. Ningbo Leibniz Information Technology Co., Ltd., Ningbo 315300, Zhejiang, China

Received date: 2023-05-23

  Revised date: 2023-07-17

  Accepted date: 2023-08-09

  Online published: 2023-08-21

Fold

摘要

为解决船舶管路布置方法中目前存在的依靠人工经验调节算法参数,权重系数的设置量级差距较大,以及求解布置方案单一的问题,提出一种网格归一化Astar (GNAstar)的布置方法.首先,采用包围盒和网格法建立数学模型.其次,通过分支管路拆分、网格标记值和父子网格搜索策略,使每一路径节点由不同目标的归一化权重值来共同决定,将传统Astar算法仅考虑长度的目标扩展成包括长度、弯头消耗和安装适用性的管路综合布置目标.最后,通过仿真案例将GNAstar算法与传统Astar算法进行对比分析,并以船舶机舱内不同管路系统为例,与文献中的蚁群算法和粒子群-Astar算法开展进一步比较.结果表明,GNAstar算法可获得有效的工程解,设计人员可通过设置不同目标的归一化权重系数来获得相应的布置方案.

关键词： 船舶管路; 布置优化; Astar算法; 网格归一化

本文引用格式

林焰 , 张乔宇 , 楼建迪 . 基于网格归一化Astar算法的船舶管路布置[J]. 上海交通大学学报, 2025 , 59(1) : 79 -88 . DOI: 10.16183/j.cnki.jsjtu.2023.206

Abstract

In order to solve the existing problems of relying on manual experience to adjust the algorithm parameters, large difference of weight coefficient, and single result in ship pipe layout, a grid normalized Astar (GNAstar) is proposed. First, the mathematical models are established using bounding box and the grid method. Then, each path node is determined by the normalized weight values of different targets using the branch pipes splitting method, grid marking values, and the parent-child grid search strategy. The cost objective of traditional Astar only considering path length is extended to the comprehensive layout objective of pipes including length, bend consumption, and installation suitability. Finally, the GNAstar proposed is compared with the traditional Astar in a simulation case, and different pipe systems in ship engine room are taken as cases to further compare with the ant colony algorithm and particle swarm-Astar. The results show that the GNAstar proposed can obtain effective engineering solutions, and designers can obtain the corresponding layout result by setting the normalized weight coefficients of different targets.

Key words： ship pipe; layout optimization; Astar algorithm; grid normalization

参考文献

[1] KIM H, RUY W, JANG B S. The development of a practical pipe auto-routing system in a shipbuilding CAD environment using network optimization[J]. International Journal of Naval Architecture and Ocean Engineering, 2013, 5: 468-477.
[2] LIN Y, BIAN X Y, DONG Z R. A discrete hybrid algorithm based on Differential Evolution and Cuckoo Search for optimizing the layout of ship pipe route[J]. Ocean Engineering, 2022, 261: 1-13.
[3] BIAN X Y, LIN Y, DONG Z R. Auto-routing methods for complex ship pipe route design[J]. Journal of Ship Production and Design, 2022, 38(2): 100-114.
[4] DONG Z, LIN Y. Ship pipe routing method based on genetic algorithm and cooperative coevolution[J]. Journal of Ship Production and Design, 2017, 33: 122-134.
[5] 董宗然, 楼偶俊, 管官. 基于改进遗传算法的船舶管路布局设计[J]. 计算机工程与应用, 2020, 56(19): 252-260.
  DONG Zongran, LOU Oujun, GUAN Guan. Ship pipe route design based on improved genetic algorithm[J]. Computer Engineering and Applications, 2020, 56(19): 252-260.
[6] SUI H, NIU W. Branch-pipe-routing approach for ships using improved genetic algorithm[J]. Frontiers of Mechanical Engineering, 2016, 11(3): 316-323.
[7] 王运龙, 王晨, 韩洋, 等. 船舶管路智能布局优化设计[J]. 上海交通大学学报, 2015, 49(4): 513-518.
  WANG Yunlong, WANG Chen, HAN Yang, et al. Intelligent layout optimization design of ship pipe[J]. Journal of Shanghai Jiao Tong University, 2015, 49(4): 513-518.
[8] DONG Z R, LIN Y. A particle swarm optimization based approach for ship pipe route design[J]. International Shipbuilding Progress, 2017, 63(1/2): 59-84.
[9] 林焰, 辛登月, 卞璇屹, 等. 改进自适应惯性权重粒子群算法及其在核动力管道布置中的应用[J]. 中国舰船研究, 2023, 18(3): 1-12.
  LIN Yan, XIN Dengyue, BIAN Xuanyi, et al. Improved particle swarm algorithm with adaptive inertia weight and its application in nuclear power pipeline layout[J]. Chinese Journal of Ship Research, 2023, 18(3): 1-12.
[10] JIANG W Y, LIN Y, CHEN M, et al. A co-evolutionary improved multi-ant colony optimization for ship multiple and branch pipe route design[J]. Ocean Engineering, 2015, 102: 63-70.
[11] DONG Z R, BIAN X Y, ZHAO S. Ship pipe route design using improved multi-objective ant colony optimization[J]. Ocean Engineering, 2022, 258(1): 1-14.
[12] 范小宁, 林焰, 纪卓尚. 多蚁群协进化的船舶多管路并行布局优化[J]. 上海交通大学学报, 2009, 43(2): 193-197.
  FAN Xiaoning, LIN Yan, JI Zhuoshang. Multi ant colony cooperative coevolution for optimization of ship multi pipe parallel routing[J]. Journal of Shanghai Jiao Tong University, 2009, 43(2): 193-197.
[13] WU L, TIAN X, WANG H Y, et al. Improved ant colony optimization algorithm and its application to solve pipe routing design[J]. Assembly Automation, 2019, 39: 45-57.
[14] 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.
[15] 林焰, 金庭宇, 杨宇超. 舰船管路布置 PG-MACO 优化方法[J]. 上海交通大学学报, 2024, 58(7): 1027-1035.
  LIN Yan, JIN Tingyu, YANG Yuchao. PG-MACO optimization method for ship pipeline layout[J]. Journal of Shanghai Jiao Tong University, 2024, 58(7): 1027-1035.
[16] JIANG W Y, LIN Y, CHEN M, et al. An ant colony optimization-genetic algorithm approach for ship pipe route design[J]. International Shipbuilding Progress, 2014, 61 (3/4): 163-183.
[17] ASMARA A. Pipe routing framework for detailed ship design[D]. Delft, The Netherlands: Delft University of Technology, 2013.
[18] DONG Z, BIAN X. Ship pipe route design using improved A* algorithm and genetic algorithm[J]. IEEE Access, 2020, 8: 153273-153296.
[19] WANG Y, WEI H, ZHANG X, et al. Optimal design of ship branch pipe route by a cooperative co-evolutionary improved particle swarm genetic algorithm[J]. Marine Technology Society Journal, 2021, 55(5): 116-128.
[20] XU J J, LIU Z F, YANG C B, et al. A pseudo-distance algorithm for collision detection of manipulators using convex-plane-polygons-based representation[J]. Robotics and Computer Integrated Manufacturing, 2020, 66: 1-19.
[21] YI K C, WANG W P, LIU Y, et al. Continuous collision detection for two moving elliptic disks[J]. IEEE Transactions on Robotics, 2006, 2(22): 213-223.
[22] HART P E, NILSSON N J, RAPHAEL B. Correction to ‘A formal basis for the heuristic determination of minimum cost paths’[J]. SIGART Newsletters, 1972, 37: 28-29.
[23] MARIEM B, MARC Z, ROBERTA C A, et al. 3D facility layout problem[J]. Journal of Intelligent Manufacturing, 2021, 32: 1065-1090.
[24] 李文博, 秦小林, 罗刚. 基于无障碍凸区域的无人机在线航迹规划[J]. 系统科学与数学, 2021, 41(6), 1493-1506.
  LI Wenbo, QIN Xiaolin, LUO Gang. Online trajectory planning of UAV based on convex obstacle-free area[J]. Journal of Systems Science and Mathematical Sciences, 2021, 41(6): 1493-1506.
Options
文章导航

/

〈 〉