基于BPA-star算法的船舶管路布局优化

廖振翔, 付景国, 纪玉龙

大连海事大学学报 ›› 2026, Vol. 52 ›› Issue (2) : 22-34.

PDF(15301 KB)
PDF(15301 KB)
大连海事大学学报 ›› 2026, Vol. 52 ›› Issue (2) : 22-34. DOI: 10.16411/j.cnki.issn1006-7736.2026.02.003

基于BPA-star算法的船舶管路布局优化

  • 廖振翔,付景国,纪玉龙*
作者信息 +

Ship pipe layout optimization based on BPA-star algorithm

  • LIAO Zhenxiang, FU Jingguo, JI Yulong*
Author information +
文章历史 +

摘要

船舶管路路径规划易出现局部最优、路径冗余等问题。为此,本文采用堵路剪枝 A*算法(BPA-star)开展管路布局优化研究。在完成管路作业空间几何建模的前提下,融合分段剪枝技术与堵路迭代方法对算法进行改良,既克服了传统搜索算法易陷入局部最优的弊端,扩大了全局搜索区间,又去除了管路路径中的冗余线路与多余转折点,有效提升了管路规划质量。结果表明,单管路案例中,BPA-star 算法在路径长度、拐角数与能量值等方面均得到最优值;多管路案例中,其管路布局更紧凑,贴合船体结构,管路衔接效果优于基础A*算法,经济性与适配性更突出。未引入延伸段方向引导时,算法规划管路的能量值降低 45.68%,安装适配长度增加 400%;引入延伸段方向引导后,管路拐角数减少 8.64%,安装适配长度增加 54.64%。研究成果可为船舶管路布局设计提供参考,对提升管路设计与施工效率具有实际应用价值。

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.

关键词

船舶管路 / 布局寻优 / BPA-star算法 / 分段剪枝技术

Key words

ship pipeline / layout optimization / BPA-star algorithm / pruning segmentation technique 

引用本文

导出引用
廖振翔, 付景国, 纪玉龙. 基于BPA-star算法的船舶管路布局优化[J]. 大连海事大学学报. 2026, 52(2): 22-34 https://doi.org/10.16411/j.cnki.issn1006-7736.2026.02.003
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 https://doi.org/10.16411/j.cnki.issn1006-7736.2026.02.003
中图分类号: U664.8   

参考文献

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

基金

国家重点研发计划项目(2023YFB4301700)

PDF(15301 KB)

Accesses

Citation

Detail

段落导航
相关文章

/