Ship pipe layout optimization based on BPA-star algorithm

Expand
  • (Marine Engineering College, Dalian Maritime University, Dalian 116026, China)

Online published: 2026-07-13

Abstract

Ship pipeline path planning is susceptible to problems such as local optima and path redundancy. To solve these issues, this paper adopted the blocked-path pruning A* algorithm (BPA-star) to study pipeline layout optimization. After establishing the geometric model of the pipeline working space, the algorithm was improved by integrating pruning segmentation and blocked-path iteration techniques. This method not only avoids the local optimum trap of traditional search algorithms and expands the global search range, but also eliminates redundant routes and unnecessary turning points, thereby effectively improving the quality of pipeline planning. The results show that for single-pipeline cases, the BPA-star algorithm achieves optimal values in terms of path length, number of turns and energy cost. For multi-pipeline cases, it produces a more compact layout that fits the hull structure well. Compared with the conventional A* algorithm, the proposed method delivers better pipeline connection performance, along with superior economic efficiency and adaptability. Without the directional guidance of extension segments, the energy value of pipelines planned by the algorithm decreases by 45.68%, and the installation adaptation length increases by 400%. With the directional guidance of extension segments adopted, the number of pipeline turns decreases by 8.64%, and the installation adaptation length increases by 54.64%. The findings can provide guidance for ship pipeline layout design and have practical application value for improving pipeline design and construction efficiency.

Cite this article

LIAO Zhenxiang, FU Jingguo, JI Yulong . Ship pipe layout optimization based on BPA-star algorithm[J]. Journal of Dalian Maritime University, 2026 , 52(2) : 22 -34 . DOI: 10.16411/j.cnki.issn1006-7736.2026.02.003

References

[1]PARK J H, STORCH R L. Pipe-routing algorithm development: case study of a ship engine room design[J]. Expert Systems with Applications, 2002, 23(3): 299-309.
[2]崔康,雷洪涛,黄奇奇,等.船舶管路辅助布置系统设计与开发[J].机械设计与研究,2021,37(5):186-189.CUI K, LEI H T, HUANG Q Q, et al. Design and development of an auxiliary ship pipeline layout system[J]. Machine Design & Research, 2021, 37(5): 186-189.(in Chinese)
[3]熊勇,张加,余嘉俊,等.船舶三维管路智能布局优化算法[J].计算机应用,2020,40(7):2164-2170.XIONG Y, ZHANG J, YU J J, et al. Intelligent layout optimization algorithm for 3D ship piping[J]. Journal of Computer Applications, 2020, 40(7): 2164-2170. (in Chinese)
[4]高惠兴,六机部第十一研究所船舶管路集成系统课题组.船舶管路程序系统PCPS—1[J].造船技术,1979(1):7-19.doi:CNKI:SUN:ZCJS.0.1979-01-001.GAO H X, PCPS-1 Research Group, No. 11 Institute, Sixth Ministry of Machine Building. Ship piping integrated system PCPS—1[J]. Marine Technology, 1979 (1): 7-19. doi:CNKI:SUN:ZCJS.0.1979-01-001. (in Chinese)
[5]董宗然, 林焰. 船舶布管系统的结构设计及自动化算法[J]. 计算机集成制造系统,2016,22(3):714-727.DONG Z R, LIN Y. Structural design and automation algorithms for ship piping layout systems[J]. Computer Integrated Manufacturing Systems, 2016, 22(3): 714-727. (in Chinese)
[6]GUNAWAN, HAMADA K, KUNIHIROK, et al. Automated pipe routing optimization for ship machinery using Dijkstra’s algorithm and genetic algorithm[J]. Journal of Marine Science and Application, 2022, 21(2): 170-178.
[7]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.
[8]MIN J G, RUY W S, PARKC S. Faster pipe auto-routing using improved jump point search[J]. International Journal of Naval Architecture and Ocean Engineering, 2020,12:596-604.
[9]杨智尧,张洪硕,林焰. 基于EPA-star算法的船舶管路协同布局优化研究[J].中国舰船研究,2024,19(6):161-172.YANG Z Y, ZHANG H S, LIN Y. Collaborative layout optimization of ship pipelines based on EPA-star algorithm[J]. Chinese Journal of Ship Research, 2024, 19(6):161-172. (in Chinese)
[10]林焰,张乔宇,楼建迪.基于网格归一化A-star算法的船舶管路布置[J].上海交通大学学报,2025,59(1):79-88. LIN Y, ZHANG Q Y, LOU J D. Ship pipe routing based on grid-normalized A-star algorithm[J]. Journal of Shanghai Jiao Tong University, 2025, 59(1): 79-88. (in Chinese)
[11]HONG Z, SUN P F, TONG X H, et al. Global pipe optimization for ship engine room[J]. Journal of Marine Science and Engineering, 2024, 12(11): 1803.
[12]DONG Z R, BIAN X Y. Ship pipe route design using improved A* algorithm and genetic algorithm[J]. IEEE Access,2020,8:153273-153296.
[13]DONG Z R, BIAN X Y, ZHAO S. Ship pipe route design using improved multi-objective ant colony optimization [J]. Ocean Engineering, 2022,258:111789.
[14]赵自奕.基于改进粒子群算法的核电管路自动化布置优化方法研究[J].自动化技术与应用, 2025, 44(8): 165-168.ZHAO Z Y. Research on automated layout optimization method for nuclear power pipelines based on improved particle swarm optimization [J]. Techniques of Automation and Applications,2025,44(8): 165-168. (in Chinese)
[15]吴忧,洪梅,黄海平,等.一种基于改进栅格法的无人机巡逻路径规划方法: CN202211594784.6[P].2025-10-01.
WU Y, HONG M, HUANG H P, et al. A UAV patrol path planning method based on improved grid method: CN202211594784.6[P]. 2025-10-01. (in Chinese)

[16]范业鹏,张凌峰,迟玉森,等.一种基于网格与包围盒的碰撞检测方法: CN202011519586.4[P]. 2025-10-01.

FAN Y P, ZHANG L F, CHI Y S, et al. A collision detection method based on grid and bounding box:CN202011519586.4[P]. 2025-10-01. (in Chinese)

[17]刘永涛,晁兴雨,朱屹晨,等.融合改进A*和DWA算法的无人车路径规划研究[J/OL].汽车技术,2025(12):19-28[2025-10-18]. https://doi.org/10.19620/j.cnki.1000-3703.20250502.LIU Y T, CHAO X Y, ZHU Y C, et al. Research on path planning for unmanned vehicles integrating improved A* and DWA algorithms[J/OL]. Automobile Technology,2025(12):19-28[2025-10-18].https://doi.org/10.19620/j.cnki.1000-3703. 20250502. (in Chinese)
 [18]卞璇屹.船舶管路布局优化辅助设计方法研究[D].大连:大连理工大学,2023.doi:10.26991/d.cnki.gdllu.2023.000139. BIAN X Y. Research on auxiliary design method for ship pipe routing layout optimization[D]. Dalian:Dalian University of Technology, 2023. doi:10. 26991/d.cnki. gdllu. 2023.000139. (in Chinese)
[19]ASMARA A. Pipe routing framework for detailed ship design[D]. Delft: Delft University of Technology, 2013.
[20]李喆,吴君,王顺森,等.采用A星遗传算法的船舶管路智能布置[J].西安交通大学学报,2023,57(6):172-180.LI Z, WU J, WANG S S, et al. Intelligent ship pipe routing using A star-genetic algorithm[J]. Journal of Xi’an Jiaotong University, 2023, 57(6): 172-180. (in Chinese)

Outlines

/