基于数字孪生的改进A*HNSA算法在船舶分段吊运任务的应用

doi:10.16183/j.cnki.jsjtu.2025.353

上海交通大学学报 ›› 2026, Vol. 60 ›› Issue (8): 1266-1278.doi: 10.16183/j.cnki.jsjtu.2025.353

基于数字孪生的改进A^*HNSA算法在船舶分段吊运任务的应用

齐麟龙¹, 刘立全², 王喆¹, 张子绅¹, 朱颖³, 夏唐斌¹^,⁴()

¹ 上海交通大学机械与动力工程学院, 上海 200240
² 清峦福兴工业科技集团有限公司, 山东枣庄 277500
³ 上海交通大学航空航天学院, 上海 200240
⁴ 特殊环境数字制造装备技术创新中心, 四川绵阳 621900

收稿日期:2025-10-22 修回日期:2025-12-18 接受日期:2026-01-15 出版日期:2026-08-28 发布日期:2026-09-02
通讯作者: 夏唐斌,教授,博士生导师,电话(Tel.):021-34208589;E-mail:xtbxtb@sjtu.edu.cn.
作者简介:齐麟龙(2001—),硕士生,从事数字孪生、运筹优化算法、船舶智能制造研究.
基金资助:
国家自然科学基金(72571173);国家自然科学基金(72301169)

Application of Digital Twin-Based Improved A^*HNSA Algorithm to Ship Block Hoisting Tasks

QI Linlong¹, LIU Liquan², WANG Zhe¹, ZHANG Zishen¹, ZHU Ying³, XIA Tangbin¹^,⁴()

¹ School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
² Qingluan Fuxing Industrial Technology Co., Ltd., Zaozhuang 277500, Shandong, China
³ School of Aeronautics and Astronautics, Shanghai Jiao Tong University, Shanghai 200240, China
⁴ Special Environment Digital Manufacturing Equipment Technology Invitation Center, Mianyang 621900, Sichuan, China

Received:2025-10-22 Revised:2025-12-18 Accepted:2026-01-15 Online:2026-08-28 Published:2026-09-02

摘要/Abstract

摘要：

船舶分段堆场调度是船舶建造中的关键环节.针对堆场吊运作业效率偏低的问题,本文构建面向分段堆场的数字孪生系统与高保真虚拟仿真环境,提出改进的A^*HNSA两阶段优化方法,在数字孪生驱动下联合优化吊运次序与龙门吊路径.基于上海某船厂的真实调度数据,根据调度分段的数量,设置小型、中型、大型3类算例,并与已有方法对比.结果显示,与已有方法相比,该方法在3类算例中总运输距离分别降低3.51%、5.33%、6.79%,总调度时间分别降低3.82%、5.35%、7.07%,显著降低了龙门吊运输成本,提升了求解效率,且满足分段堆场数字孪生系统的在线响应要求.

关键词: 数字孪生, 船舶分段堆场调度, 路径规划, A^*算法, 模拟退火算法

Abstract:

Block yard scheduling is a crucial link in ship construction. To address the issue of low efficiency in yard hoisting operations, this paper constructs a digital twin system and a high-fidelity virtual simulation environment for block yards, and proposes an improved two-stage optimization method named A^*HNSA. Driven by the digital twin, this method jointly optimizes the hoisting sequence and the gantry crane path planning. Based on the real scheduling data from a shipyard in Shanghai, three types of test cases (small, medium, and large) are established according to the number of scheduling blocks, and comparisons are made with existing methods. The results show that, compared with existing methods in the three types of test cases, the proposed method reduces the total transportation distance by 3.51%, 5.33%, and 6.79% respectively, and shortens the total scheduling time by 3.82%, 5.35%, and 7.07% respectively. It significantly reduces the transportation cost of gantry cranes, improves the solution efficiency, and meets the online response requirements of the block yard digital twin system.

Key words: digital twin, ship block yard scheduling, path planning, A^* algorithm, simulated annealing (SA) algorithm

中图分类号:

TP391
U673

齐麟龙, 刘立全, 王喆, 张子绅, 朱颖, 夏唐斌. 基于数字孪生的改进A^*HNSA算法在船舶分段吊运任务的应用[J]. 上海交通大学学报, 2026, 60(8): 1266-1278.

QI Linlong, LIU Liquan, WANG Zhe, ZHANG Zishen, ZHU Ying, XIA Tangbin. Application of Digital Twin-Based Improved A^*HNSA Algorithm to Ship Block Hoisting Tasks[J]. Journal of Shanghai Jiao Tong University, 2026, 60(8): 1266-1278.

图/表 19

图1

图2

表1

图3

图4

图5

表2

图6

图7

图8

图9

图10

图11

表3

表4

表5

图12

表6

表7

参考文献 25

[1]	WIEGMANS B, WITTE P. Efficiency of inland waterway container terminals: Stochastic frontier and data envelopment analysis to analyze the capacity design- and throughput efficiency[J]. Transportation Research Part A: Policy and Practice, 2017, 106: 12-21. doi: 10.1016/j.tra.2017.09.007 URL
[2]	LEE B K, KIM K H. Comparison and evaluation of various cycle-time models for yard cranes in container terminals[J]. International Journal of Production Economics, 2010, 126(2): 350-360. doi: 10.1016/j.ijpe.2010.04.015 URL
[3]	NARASIMHAN A, PALEKAR U S. Analysis and algorithms for the transtainer routing problem in container port operations[J]. Transportation Science, 2002, 36(1): 63-78. doi: 10.1287/trsc.36.1.63.576 URL
[4]	卢治兵, 王爱民, 唐承统. 面向曲面分段建造的双龙门吊车协同调度技术[J]. 计算机集成制造系统, 2016, 22(9): 2153-2164.
	LU Zhibing, WANG Aimin, TANG Chengtong. Double yard cane scheduling for curved block in shipbuilding[J]. Computer Integrated Manufacturing Systems, 2016, 22(9): 2153-2164.
[5]	LU H J, WANG S. A study on multi-ASC scheduling method of automated container terminals based on graph theory[J]. Computers & Industrial Engineering, 2019, 129: 404-416. doi: 10.1016/j.cie.2019.01.050 URL
[6]	李钊. 船舶分段建造多车间协同调度方法[D]. 上海: 上海交通大学, 2022.
	LI Zhao. Method of multi-factory collaborative scheduling for ship block construction plan[D]. Shanghai: Shanghai Jiao Tong University, 2022.
[7]	WANG H T, RUIZ R, VILLA F, et al. Iterated greedy for the yard crane scheduling problem with input/output assignment[J]. European Journal of Operational Research, 2025, 327(1): 84-94. doi: 10.1016/j.ejor.2025.04.052 URL
[8]	TAN R Z, WANG P X, TAO J H, et al. The bay-based quay crane scheduling problem considering time-varying handling capacities in automated container terminals[J]. Transportation Research Part E: Logistics and Transportation Review, 2025, 201: 104254. doi: 10.1016/j.tre.2025.104254 URL
[9]	TANG G L, LI M X, FANG Z, et al. Efficiency and energy consumption of the automated container yard with twin rail-mounted gantry cranes considering crane scheduling strategies and handshake area designs[J]. Simulation Modelling Practice and Theory, 2024, 135: 102981. doi: 10.1016/j.simpat.2024.102981 URL
[10]	LIU W Q, ZHU X N, WANG L, et al. Flexible yard crane scheduling for mixed railway and road container operations in sea-rail intermodal ports with the sharing storage yard[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 190: 103714. doi: 10.1016/j.tre.2024.103714 URL
[11]	王兴志, 翟海保, 严亚勤, 等. 基于数字孪生和深度学习的新一代调控系统预调度方法[J]. 上海交通大学学报, 2021, 55(Sup.2): 37-41. doi: 10.16183/j.cnki.jsjtu.2021.S2.006
	WANG Xingzhi, ZHAI Haibao, YAN Yaqin, et al. Pre-dispatching method of new generation dispatching and control system based on digital twin and deep learning[J]. Journal of Shanghai Jiao Tong University, 2021, 55(Sup.2): 37-41.
[12]	SOORI M, AREZOO B, DASTRES R. Digital twin for smart manufacturing, A review[J]. Sustainable Manufacturing and Service Economics, 2023, 2: 100017. doi: 10.1016/j.smse.2023.100017 URL
[13]	XIA T B, SUN H, DING Y T, et al. Digital twin-based real-time energy optimization method for production line considering fault disturbances[J]. Journal of Intelligent Manufacturing, 2025, 36(1): 569-593. doi: 10.1007/s10845-023-02219-9
[14]	陶飞, 张辰源, 戚庆林, 等. 数字孪生成熟度模型[J]. 计算机集成制造系统, 2022, 28(5): 1267-1281.
	TAO Fei, ZHANG Chenyuan, QI Qinglin, et al. Digital twin maturity model[J]. Computer Integrated Manufacturing Systems, 2022, 28(5): 1267-1281.
[15]	LENG B H, GAO S, XIA T B, et al. Digital twin monitoring and simulation integrated platform for reconfigurable manufacturing systems[J]. Advanced Engineering Informatics, 2023, 58: 102141. doi: 10.1016/j.aei.2023.102141 URL
[16]	JIA W J, WANG W, ZHANG Z Z. From simple digital twin to complex digital twin Part I: A novel modeling method for multi-scale and multi-scenario digital twin[J]. Advanced Engineering Informatics, 2022, 53: 101706. doi: 10.1016/j.aei.2022.101706 URL
[17]	ZHANG X W, CHEN D Y. Shipbuilding 4.0: A systematic literature review[J]. Applied Sciences, 2024, 14(14): 6363. doi: 10.3390/app14146363 URL
[18]	LIU Y C, REN H L. Rapid acquisition method for structural strength evaluation stresses of the ship digital twin model[J]. Ocean Engineering, 2023, 285: 115323. doi: 10.1016/j.oceaneng.2023.115323 URL
[19]	刘震. 基于数字孪生的船用起重机吊臂制造过程状态监控方法研究[D]. 上海: 上海海事大学, 2023.
	LIU Zhen. Research on condition monitoring method of marine crane boom manufacturing process based on digital twin[D]. Shanghai: Shanghai Maritime University, 2023.
[20]	MAURO F, KANA A A. Digital twin for ship life-cycle: A critical systematic review[J]. Ocean Engineering, 2023, 269: 113479. doi: 10.1016/j.oceaneng.2022.113479 URL
[21]	JEON J, THEOTOKATOS G. A framework to assure the trustworthiness of physical model-based digital twins for marine engines[J]. Journal of Marine Science and Engineering, 2024, 12(4): 595. doi: 10.3390/jmse12040595 URL
[22]	沈慧, 刘世民, 许敏俊, 等. 面向加工领域的数字孪生模型自适应迁移方法[J]. 上海交通大学学报, 2022, 56(1): 70-80. doi: 10.16183/j.cnki.jsjtu.2021.167
	SHEN Hui, LIU Shimin, XU Minjun, et al. Adaptive transferring method of digital twin model for machining domain[J]. Journal of Shanghai Jiao Tong University, 2022, 56(1): 70-80.
[23]	贺益雄, 代永刚, 赵兴亚, 等. 河口深槽可航宽度变化水域航行决策方法[J]. 上海交通大学学报, 2025, 59(4): 489-502. doi: 10.16183/j.cnki.jsjtu.2023.356
	HE Yixiong, DAI Yonggang, ZHAO Xingya, et al. Navigation decision-making method in estuary deep trough with varying width of navigable waters[J]. Journal of Shanghai Jiao Tong University, 2025, 59(4): 489-502.
[24]	LI W F, FAN H X, CAI L, et al. Digital twin-driven proactive-reactive scheduling framework for port multi-equipment under a complex uncertain environment[J]. Simulation Modelling Practice and Theory, 2024, 136: 103011. doi: 10.1016/j.simpat.2024.103011 URL
[25]	韩冬阳, 夏唐斌, 范宜静, 等. 智能制造系统的数字孪生正向监测与反向控制方法[J]. 计算机集成制造系统, 2024, 30(10): 3419-3430.
	HAN Dongyang, XIA Tangbin, FAN Yijing, et al. Digital twin forward monitoring and reverse control method for intelligent manufacturing systems[J]. Computer Integrated Manufacturing Systems, 2024, 30(10): 3419-3430.

符号	定义
B	待调度分段的集合,B={b₁, b₂, …, b_n}
C	龙门吊集合,C={c₁, c₂}
d	龙门吊之间的安全距离
t_F_i	龙门吊完成吊运任务i的时间
M_L	吊运进口任务集合
M_U	吊运出口任务集合
P_e_i	吊运任务i的终点坐标,P_e_i=(x_e_i, y_e_i)
P_s_i	吊运任务i的起点坐标,P_s_i=(x_s_i, y_s_i)
S_l_i, S_e_i	吊运任务i的负载距离和空载距离
t_s_i	吊运任务i的计划开始时间
T_t	总完工时间
v_ll, v_el	龙门吊纵向移动的负载速度和空载速度
${\mathrm{\alpha }}_{\mathrm{i}\mathrm{i}\text{'}}^{\mathrm{c}}$	如果吊运任务i'和吊运任务i由同一龙门吊处理,且任务i'在任务i之后,则${\mathrm{\alpha }}_{\mathrm{i}\mathrm{i}\text{'}}^{\mathrm{c}}$=1,否则${\mathrm{\alpha }}_{\mathrm{i}\mathrm{i}\text{'}}^{\mathrm{c}}$=0;c为龙门吊索引
${\mathrm{\beta }}_{\mathrm{i}}^{\mathrm{c}}$	如果吊运任务i被分配给龙门吊,则${\mathrm{\beta }}_{\mathrm{i}}^{\mathrm{c}}$=1,否则${\mathrm{\beta }}_{\mathrm{i}}^{\mathrm{c}}$=0
γ_ii'	如果任务i在任务i'开始之前完成,则γ_ii'=1,否则γ_ii'=0

类别	符号	含义
状态	Q₁	待机状态
	Q₂	空载移动状态
	Q₃	抓取分段状态
	Q₄	负载移动状态
	Q₅	释放分段状态
行为	δ₁	启动龙门吊
	δ₂,δ₃	接收并移动到任务开始坐标点
	δ₄,δ₅	抓取分段,吊钩上升
	δ₆,δ₇	接收并移动到任务结束坐标点
	δ₈,δ₉	吊钩下降,释放分段
	δ₁₀	设备关闭
	δ₁₁	检修重启

参数	取值	参数	取值
T₀	100	α_min	0.90
T_max	500	q	0.90
α_max	0.99	ε	2

分段ID	起点和终点坐标/m	路径长度/m	拐点数	途径坐标/m
B005	(0.00, 10.50),(72.50, 59.62)	108.12	3	(0.00, 20.50), (45.50, 20.50), (45.50, 59.62)
B009	(0.00, 48.00),(120.70, 18.85)	144.35	2	(0.00, 30.50), (120.70, 30.50)
B015	(300.00, 95.00),(250.00, 15.77)	129.23	1	(250.00, 95.00)
B018	(300.00, 17.00),(204.45, 12.40)	122.31	3	(269.50, 17.00), (269.50, 1.32), (204.45, 1.32)

分段数量	算法	空载距离/m	负载距离/m	总移动距离/m	作业时间/s	算法运行时间/min
23	仅优先规则^[4]	5 816.71	6 641.27	12 457.98	7 335.87	1.34
	Bi-RRT+DPSO^[6]	4 813.77	6 242.87	11 056.64	6 568.80	6.07
	DT-A^*HNSA	4 766.70	5 901.78	10 668.48	6 317.87	2.01
65	仅优先规则^[4]	17 359.25	19 352.45	36 711.70	21 581.26	3.46
	Bi-RRT+DPSO^[6]	14 362.15	17 964.26	32 326.41	19 157.25	15.86
	DT-A^*HNSA	13 573.51	17 022.78	30 596.29	18 135.28	5.84
128	仅优先规则^[4]	30 899.02	34 829.73	65 728.75	38 669.33	9.26
	Bi-RRT+DPSO^[6]	26 062.36	32 335.21	58 397.57	34 587.99	39.24
	DT-A^*HNSA	24 024.21	30 244.68	54 268.89	32 175.23	17.23

基于数字孪生的改进A^*HNSA算法在船舶分段吊运任务的应用

Application of Digital Twin-Based Improved A^*HNSA Algorithm to Ship Block Hoisting Tasks

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 19

参考文献 25

相关文章 15

编辑推荐

Metrics

本文评价

分段数量	龙门吊1移动距离/m	龙门吊2移动距离/m	总移动距离/m	负载率
23	4 867.07	5 801.41	10 668.48	1.19
65	14 324.56	16 271.73	30 596.29	1.13
128	28 693.56	25 575.33	54 268.89	1.12

分段数量	算法	算法运行时间/min
23	A^*-SA	5.68
	DT-A^*HNSA	2.01
65	A^*-SA	16.67
	DT-A^*HNSA	5.84
128	A^*-SA	42.56
	DT-A^*HNSA	17.23

[1]	温晓健, 严哲, 胡佐治, 袁轶, 鲍劲松, 张丹. 一种生成式船舶薄板产线数字孪生建模方法[J]. 上海交通大学学报, 2026, 60(8): 1279-1289.
[2]	卞文超, 温晓健, 王新厚, 鲍劲松. 基于大语言模型的数字孪生模型语义重构方法[J]. 上海交通大学学报, 2026, 60(8): 1290-1298.
[3]	. 基于区域约束模块的类车多智能体路径规划方法[J]. J Shanghai Jiaotong Univ Sci, 2026, 31(4): 1003-1013.
[4]	. RSG-P：一种基于路径场景图的快速全局路径规划方法[J]. J Shanghai Jiaotong Univ Sci, 2026, 31(4): 881-897.
[5]	. 基于代价地图 A*引导强化学习路径规划方法的复杂环境导航[J]. J Shanghai Jiaotong Univ Sci, 2026, 31(4): 819-827.
[6]	唐爱盼, 徐隽骁, 凌爱军, 等. 海上设施数字孪生系统测试、评估、验证与确认（TEVV）技术研究[J]. 海洋工程装备与技术, 2026, 13(1): 123-128.
[7]	贺益雄, 代永刚, 赵兴亚, 于德清, 黄立文. 河口深槽可航宽度变化水域航行决策方法[J]. 上海交通大学学报, 2025, 59(4): 489-502.
[8]	. 血管介入手术路径规划及三维视觉导航[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(3): 472-481.
[9]	张思霈, 徐天洋, 康传华, 慈慧鹏, 刘瑞. 数字平行战场：理论综述与发展展望[J]. 空天防御, 2025, 8(3): 29-39.
[10]	王刚, 杨科, 权文, 郭相科, 赵小茹. 基于数字孪生的防空反导数智平行战场构建方法研究[J]. 空天防御, 2025, 8(3): 1-13.
[11]	董德金, 王常成, 蔡云泽. 基于改进多目标进化算法的栅格地图路径规划[J]. 上海交通大学学报, 2025, 59(10): 1558-1567.
[12]	李龙跃, 王文豪, 皮雳, 贾忠慧, 赵慧珍. 防空反导作战模拟推演分析方法综述[J]. 空天防御, 2025, 8(1): 48-53.
[13]	何通, 韦亚利, 卢青, 毕千. 无人机群协同侦察多点目标路径规划与控制[J]. 空天防御, 2025, 8(1): 31-40.
[14]	白文超, 班明飞, 宋梦, 夏世威, 李知艺, 宋文龙. 电动汽车-无人机联合救援系统协调调度模型[J]. 上海交通大学学报, 2024, 58(9): 1443-1453.
[15]	张菁菁1, 赵金城1, 2, 3, 宋振森1, 2, 3, 段立平1, 2, 3. 海洋平台人员疏散试验与仿真模拟研究[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(5): 747-758.

基于数字孪生的改进A*HNSA算法在船舶分段吊运任务的应用

Application of Digital Twin-Based Improved A*HNSA Algorithm to Ship Block Hoisting Tasks

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 19

参考文献 25

相关文章 15

编辑推荐

Metrics

本文评价

基于数字孪生的改进A^*HNSA算法在船舶分段吊运任务的应用

Application of Digital Twin-Based Improved A^*HNSA Algorithm to Ship Block Hoisting Tasks