Ship Pipe Layout Based on Grid Normalized Astar Algorithm

doi:10.16183/j.cnki.jsjtu.2023.206

Abstract

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

CLC Number:

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.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Tab.1

Tab.2

Fig.7

Tab.3

Fig.8

Tab.4

Tab.5

Fig.9

Fig.10

References 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

设备编号	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