Journal of Shanghai Jiao Tong University

Journal of Shanghai Jiaotong University >

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

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

Naval Architecture, Ocean and Civil Engineering

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

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

Cite this article

LIN Yan , ZHANG Qiaoyu , LOU Jiandi . Ship Pipe Layout Based on Grid Normalized Astar Algorithm[J]. Journal of Shanghai Jiaotong University, 2025 , 59(1) : 79 -88 . DOI: 10.16183/j.cnki.jsjtu.2023.206

References

[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
Outlines

/

〈 〉