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

doi:10.16183/j.cnki.jsjtu.2023.206

摘要/Abstract

摘要：

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

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

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

中图分类号:

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

LIN Yan, ZHANG Qiaoyu, LOU Jiandi. Ship Pipe Layout Based on Grid Normalized Astar Algorithm[J]. Journal of Shanghai Jiao Tong University, 2025, 59(1): 79-88.

图/表 15

图1

图2

图3

图4

图5

图6

表1

表2

图7

表3

图8

表4

表5

图9

图10

参考文献 24

[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. doi: 10.3778/j.issn.1002-8331.1906-0251
	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. doi: 10.3778/j.issn.1002-8331.1906-0251
[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. doi: 10.1007/s11465-016-0384-z
[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. doi: 10.16183/j.cnki.jsjtu.2022.508
	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. doi: 10.12341/jssms20355

编辑推荐 0

Metrics

阅读次数

全文

158

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	9	97	0	52

来源	本网站	其他网站

次数	51	107
比例	32%	68%

摘要

375

最新录用	在线预览	正式出版

110	0	265

来源	本网站	其他网站

次数	88	287
比例	23%	77%

设备编号	x范围	y范围	z范围
I	(20, 29)	(0, 3)	(0, 26)
II	(25, 27)	(44, 49)	(0, 8)
III	(0, 8)	(10, 15)	(0, 10)
IV	(0, 8)	(30, 34)	(0, 10)
V	(20, 30)	(20, 30)	(0, 18)
VI	(41, 49)	(20, 28)	(0, 20)

管路编号	类型	连接设备	接口坐标
1	分支	I	(24, 2, 26)
		II	(26, 46, 8)
		III	(2, 12, 10)
		IV	(5, 32, 10)
2	并行	III	(6, 12, 10)
		VI	(45, 23, 20)
3	并行	IV	(6, 32, 10)
		VI	(45, 25, 20)
4	独立	I	(29, 1, 20)
		VI	(45, 20, 16)

q	L/B/I
q	传统Astar算法	GNAstar算法
1	135/6/0	137/6/30
2	60/3/25	60/3/49
3	56/3/25	56/3/49
4	39/4/0	39/2/20
总计	289/16/50	291/14/148

管道系统	q	类型	连接设备	坐标/mm	直径/mm
脱硫系统	1	分支	循环水质监测器洗涤塔	(580, 3 220, 2 320)	300
				(610, 3 400, 3 180)
				(610, 3 400, 3 130)
				(610, 3 400, 3 080)
	2	并行	水处理器	(170, 3 420, 2 770)	220
	2	并行	污水储存箱	(220, 3 355, 2 600)	220
	3	并行	水处理器	(170, 3 460, 2 770)	220
	3	并行	废气处理器	(480, 3 300, 2 770)	220
	4	分支	废气处理器	(360, 3 570, 2 800)	100
			水泵1	(440, 3 548, 2 557)
			水泵2	(440, 3 448, 2 557)
	5	分支	板式冷却器	(603, 3 297, 2 537)	100
			水泵1	(448, 3 448, 2 537)
			水泵2	(448, 3 548, 2 537)
	6	并行	板式冷却器	(620, 3 297, 2 587)	100
	6	并行	循环水质监测器	(670, 3 220, 2 320)	100
	7	并行	板式冷却器	(600, 3 297, 2 587)	100
	7	并行	水箱	(245, 3 240, 2 300)	100
	8	独立	洗涤塔	(650, 3 400, 2 980)	100
	8	独立	板式冷却器	(620, 3 297, 2 537)	100
燃油系统	1	分支	主机	(1 030, 2 200, 2 320)	600
			燃油泵1	(1 170, 2 270, 2 330)
			燃油泵2	(1 170, 2 130, 2 330)
	2	独立	燃油日用柜1	(1 330, 2 270, 2 330)	600
	2	独立	燃油泵1	(1 210, 2 270, 2 330)	600
	3	独立	燃油日用柜2	(1 330, 2 130, 2 330)	600
	3	独立	燃油泵2	(1 210, 2 130, 2 330)	600
	4	分支	分油机1	(1 385, 2 430, 2 320)	480
			分油机2	(1 410, 2 430, 2 320)
			燃油沉淀柜	(1 400, 2 530, 2 330)
	5	并行	燃油沉淀柜	(1 400, 2 530, 2 330)	480
	5	并行	分油机3	(1 475, 2 430, 2 320)	480
	6	分支	分油机1	(1 370, 2 390, 2 320)	480
			分油机2	(1 430, 2 390, 2 320)
			燃油日用柜1	(1 460, 2 265, 2 330)
	7	并行	燃油日用柜2	(1 460, 2 130, 2 330)	480
	7	并行	分油机3	(1 490, 2 390, 2 320)	480

管路系统	q	L/B/I
管路系统	q	蚁群	粒子群-Astar	GNAstar-I	GNAstar-II
脱硫系统	1	1 490/4/860	1 130/3/1 040	1 130/3/1 040	1 190/5/1 100
	2	278/4/101	278/4/176	278/4/101	278/4/176
	3	470/2/0	500/4/455	500/3/180	500/5/460
	4	494/2/0	494/2/0	494/4/67	494/4/67
	5	700/3/356	700/3/356	700/3/356	700/3/356
	6	638/4/364	638/3/134	616/3/443	698/5/546
	7	432/4/329	432/4/316	445/4/345	445/4/345
	8	464/4/434	464/4/434	464/4/434	486/4/462
总计		4 966/27/2 444	4 636/27/2 911	4 627/28/2 966	4 791/34/3 512
燃油系统	1	286/4/117	276/4/158	276/4/158	294/6/234
	2	120/0/0	120/0/0	148/4/100	148/4/100
	3	120/0/0	120/0/0	148/4/100	148/4/100
	4	200/4/85	173/4/150	173/4/150	190/6/150
	5	310/4/85	310/4/85	310/4/270	310/4/270
	6	321/3/117	321/4/117	298/5/270	333/5/272
	7	190/4/85	190/4/75	202/5/164	202/5/164
总计		1 547/19/489	1 510/20/585	1 555/30/1 212	1 625/34/1 290