基于蒙特卡洛树搜索的舰载机保障作业调度方法

doi:10.7527/S1000-6893.2025.32444

Abstract

Abstract:

The key to improving the takeoff efficiency of carrier-based aircraft is to develop an efficient deck support operation scheduling plan for carrier aircraft. To improve the aircraft group support ability， the aircraft carrier deck support operation scheduling algorithm is studied. Firstly， according to the task requirements and various constraints of the carrier-based aircraft deck support scheduling problem， a constraint satisfaction model is established to minimize the completion time of cluster support， and the computational complexity analysis of the scheduling problem shows that it is an NP-hard problem. The algorithm draws on the exploration and exploitation balance mechanism of Monte Carlo Tree Search （MCTS）， combines heuristic simulation strategy and scheduling scheme generation method to evaluate the search path， and uses the MCTS to record the evaluation results to guide the subsequent search direction. Finally， to verify the performance of the proposed algorithm， a random activity network generator is used to construct test cases and conduct simulation experiments. The simulation results show that compared with the current advanced algorithms， the proposed algorithm improves the solution quality and efficiency.

Key words: carrier-based aircraft, deck support operation, scheduling algorithm, scheduling scheme generation, Monte Carlo Tree Search (MCTS)

CLC Number:

V271.4⁺92

Jian PENG, Guanglei ZHU, Qingshun WU, Yafei LI, Shuo HE, Yuanyuan JIN, Mingliang XU. Scheduling method for carrier-based aircraft support operations based on Monte Carlo tree search[J]. Acta Aeronautica et Astronautica Sinica, 2026, 47(6): 332444.

Figures/Tables 15

Fig.1

Table 1

Variable definition

变量	定义	变量	定义
$I$	待保障的舰载机集合	$T$	完成所有保障作业的时间上限
$J i$	舰载机 $i$ 的保障作业集合	$r j k p$	开展保障作业 $j$ 所需要的 $k$ 类型保障人员数量
$J$	所有保障作业集合， $J = ∪ i ∈ I J i$	$r j k e$	开展保障作业 $j$ 所需要的 $k$ 类型保障设备数量
$A t$	$t$ 时刻所有处于执行状态的所有保障作业集合	$λ k l i$	如果类型为 $k$ 的保障设备 $l$ 可以为舰载机 $i$ 提供保障服务，那么 $λ k l i = 1$ ，否则 $λ k l i = 0$
$P j$	保障作业 $j$ 的紧前作业集合	$L k w$	类型为 $k$ 的供给性资源可以同时支持保障设备的最大数量
$K p$	保障人员类型集合	$r j k w$	如果保障作业 $j$ 对 $k$ 类型供给性资源有需求，那么 $r j k w = 1$ ，否则 $r j k w = 0$
$L k p$	类型为 $k$ 的保障人员集合， $k ∈ K p$	$r j k s$	如果保障作业 $j$ 对 $k$ 类型工位空间有需求，那么 $r j k s = 1$ ，否则 $r j k s = 0$
$K u e$	独占式保障设备类型集合	$Δ P i j k$	类型为 $k$ 的保障人员从保障作业 $i$ 转移至保障作业 $j$ 所需时间
$K s e$	共享式保障设备类型集合	$Δ E e g k$	类型为 $k$ 的保障设备从舰载机 $e$ 转移至舰载机 $g$ 所需时间
$K e$	保障设备类型集合， $K e = K u e ⋃ K s e$	$x j t$	如果保障作业 $j$ 于时刻 $t$ 完工，那么 $x j t = 1$ ，否则 $x j t = 0$
$L k e$	类型为 $k$ 的保障设备集合	$F j$	保障作业 $j$ 的完工时间， $F j = ∑ t ∈ 0, T t x j t$
$K w$	供给类资源类型集合	$X j k l p$	如果类型为 $k$ 的保障人员 $l$ 被分配给保障作业 $j$ ，那么 $X j k l p = 1$ ，否则 $X j k l p = 0$
$K s$	工位空间集合	$Z i j k l p$	如果类型为 $k$ 的保障人员完成保障作业 $i$ 后转移至保障作业 $j$ ，那么 $Z i j k l p = 1$ ，否则 $Z i j k l p = 0$
$s 0, e 0$	2个虚拟作业	$X j k l e$	如果类型为 $k$ 的保障设备 $l$ 被分配给保障作业 $j$ ，那么 $X j k l e = 1$ ，否则 $X j k l e = 0$
$d j$	保障作业 $j$ 的工期	$Z i j k l e$	如果类型为 $k$ 的保障设备 $l$ 完成保障作业 $i$ 后从其工位转移至保障作业 $j$ 的工位开展作业，那么 $Z i j k l e = 1$ ，否则 $Z i j k l e = 0$
$B j$	保障作业 $j$ 所属舰载机

Table 1

Fig.2

Fig.3

Fig.4

Table 2

Job priority rules

作业优先规则	优先值	最大/最小值优先
minLFT	LFT	最小值优先
minLST	LST	最小值优先
minSLK	$L S T - E S T$	最小值优先

Table 2

Table 3

Resource allocation rules

作业优先规则	优先值	最大/最小值优先
minTT	$Δ P i j k$ 或 $Δ E i j k$	最小值优先
maxFT	$F i$ 或 $F i k a$	最大值优先
minRR	$v i k$ 或 $w i k$	最小值优先
maxRR	$v i k$ 或 $w i k$	最大值优先

Table 3

Fig.5

Table 4

Fig.6

Table 5

Table 6

Parameter settings of comparison algorithms

算法	参数设置
ISSA	种群规模=30，每次迭代后都进行交叉和变异操作
DPFGSA	各种群粒子数量=30， $G 0 = 100$
GA-TPCO	初始种群规模=200，变异概率=0.05
HEDA	种群规模=250，选择个体数量=5，学习速率=0.05，接受率=0.5，下降速度=0.8
A2C	训练回合数=4 000，batch_size=128，学习率=0.001

Table 6

Fig.7

Table 7

Table 8

References 30

[1]	邓嘉宁，李海旭，安强林，等. 基于指标关联的舰载机出动架次率预测方法［J］. 系统工程与电子技术， 2023， 45（11）： 3507-3515.
	DENG J N， LI H X， AN Q L， et al. Prediction method of carrier aircraft’s sortie rate based on index correlation［J］. Systems Engineering and Electronics， 2023， 45（11）： 3507-3515 （in Chinese）.
[2]	金钊，金璐，张博闻，等. 舰载机弹药保障作业调度的形式化建模与验证［J］. 软件学报， 2024， 35（9）： 4100-4122.
	JIN Z， JIN L， ZHANG B W， et al. Formal modeling and verification of carrier-borne aircraft ammunition support operation scheduling［J］. Journal of Software， 2024， 35（9）： 4100-4122 （in Chinese）.
[3]	MICHINI B， HOW J. A human-interactive course of action planner for aircraft carrier deck operations［C］∥Proceedings of AIAA Information Technology. Reston： AIAA， 2011.
[4]	RYAN J， CUMMINGS M， ROY N， et al. Designing an interactive local and global decision support system for aircraft carrier deck scheduling［C］∥Proceedings of AIAA Information Technology. Reston： AIAA， 2011.
[5]	RYAN J C， BANERJEE A G， CUMMINGS M L， et al. Comparing the performance of expert user heuristics and an integer linear program in aircraft carrier deck operations［J］. IEEE Transactions on Cybernetics， 2014， 44（6）： 761-773.
[6]	GHOSH DASTIDAR R， FRAZZOLI E. A queueing network based approach to distributed aircraft carrier deck scheduling［C］∥Proceedings of AIAA Information Technology. Reston： AIAA， 2011.
[7]	冯强，曾声奎，康锐. 基于MAS的舰载机动态调度模型［J］. 航空学报， 2009， 30（11）： 2119-2125.
	FENG Q， ZENG S K， KANG R. A MAS-based model for dynamic scheduling of carrier aircraft［J］. Acta Aeronautica et Astronautica Sinica， 2009， 30（11）： 2119-2125 （in Chinese）.
[8]	高东博，石章松，王旋. 基于人员分配的舰载机出动调运指挥模型［J］. 火力与指挥控制， 2023， 48（1）： 105-109.
	GAO D B， SHI Z S， WANG X. Dispatch and command model of shipboard aircraft based on personnel allocation［J］. Fire Control & Command Control， 2023， 48（1）： 105-109 （in Chinese）.
[9]	李耀宇，朱一凡，杨峰，等. 基于逆向强化学习的舰载机甲板调度优化方案生成方法［J］. 国防科技大学学报， 2013， 35（4）： 171-175.
	LI Y Y， ZHU Y F， YANG F， et al. Inverse reinforcement learning based optimal schedule generation approach for carrier aircraft on flight deck［J］. Journal of National University of Defense Technology， 2013， 35（4）： 171-175 （in Chinese）.
[10]	万兵，韩维，梁勇，等. 舰载机出动离场调度优化算法［J］. 系统工程与电子技术， 2021， 43（12）： 3624-3634.
	WAN B， HAN W， LIANG Y， et al. Optimization algorithm of carrier-based aircraft sortie departure scheduling［J］. Systems Engineering and Electronics， 2021， 43（12）： 3624-3634 （in Chinese）.
[11]	苏析超，韩维，张勇，等. 考虑人机匹配模式的舰载机甲板机务勤务保障调度算法［J］. 航空学报， 2018， 39（12）： 222314.
	SU X C， HAN W， ZHANG Y， et al. Scheduling algorithm for maintenance and service support of carrier-based aircraft on flight deck with different man-aircraft matching patterns［J］. Acta Aeronautica et Astronautica Sinica， 2018， 39（12）： 222314 （in Chinese）.
[12]	谭大力，王云飞，于连飞，等. 基于整数线性规划方法的舰载机航空保障资源优化调度［J］. 中国舰船研究， 2019， 14（5）： 145-151.
	TAN D L， WANG Y F， YU L F， et al. Optimal scheduling of aviation support resources for carrier based aircrafts based on integer linear programming［J］. Chinese Journal of Ship Research， 2019， 14（5）： 145-151 （in Chinese）.
[13]	魏昌全，陈春良，王保乳. 分波出动舰载机航空保障调度研究［J］. 控制工程， 2012， 19（S1）： 108-110， 115.
	WEI C Q， CHEN C L， WANG B R. Research on aviation support scheduling of carrier-based aircraft with separate waves［J］. Control Engineering of China， 2012， 19（S1）： 108-110， 115 （in Chinese）.
[14]	李经，孙哲，李梦龙，等. 舰载机保障作业调度决策研究［J］. 舰船电子工程， 2018， 38（12）： 165-168， 184.
	LI J， SUN Z， LI M L， et al. Research on carrier-based aircraft deck operation scheduling［J］. Ship Electronic Engineering， 2018， 38（12）： 165-168， 184 （in Chinese）.
[15]	于连飞，朱承，张维明，等. 保障时间不确定情况下的舰载机航保资源调度［J］. 火力与指挥控制， 2018， 43（2）： 12-16， 20.
	YU L F， ZHU C， ZHANG W M， et al. Research on scheduling of aviation supporting resource based on uncertain supporting time［J］. Fire Control & Command Control， 2018， 43（2）： 12-16， 20 （in Chinese）.
[16]	SU X C， CUI R W， LI C J， et al. A heuristic solution framework for the resource-constrained multi-aircraft scheduling problem with transfer of resources and aircraft［J］. Expert Systems with Applications， 2023， 228： 120430.
[17]	CUI R W， HAN W， SU X C， et al. A multi-objective hyper heuristic framework for integrated optimization of carrier-based aircraft flight deck operations scheduling and resource configuration［J］. Aerospace Science and Technology， 2020， 107： 106346.
[18]	韩维，崔荣伟，苏析超，等. 基于双种群模糊引力搜索算法的舰载机甲板作业调度［J］. 控制与决策， 2021， 36（11）： 2751-2759.
	HAN W， CUI R W， SU X C， et al. Flight deck operations scheduling based on dual population fuzzy gravitational search algorithm［J］. Control and Decision， 2021， 36（11）： 2751-2759 （in Chinese）.
[19]	范加利，黄葵，朱兴动，等. 基于禁忌算法的舰载机甲板作业动态调度优化算法［J］. 系统工程与电子技术， 2023， 45（10）： 3172-3182.
	FAN J L， HUANG K， ZHU X D， et al. Carrier aircraft deck operations dynamic scheduling optimization algorithm based on the tabu algorithm［J］. Systems Engineering and Electronics， 2023， 45（10）： 3172-3182 （in Chinese）.
[20]	王文鹏，邹刚，张玎，等. 基于自适应遗传算法的舰载机保障调度［J］. 兵工自动化， 2021， 40（1）： 37-42.
	WANG W P， ZOU G， ZHANG D， et al. Support scheduling of carrier-based aircraft based on adaptive genetic algorithm［J］. Ordnance Industry Automation， 2021， 40（1）： 37-42 （in Chinese）.
[21]	刘翱. 变邻域搜索分布估计算法求解舰载机保障作业调度问题［J］. 系统科学与数学， 2024， 44（2）： 391-407.
	LIU A. On the carrier-based aircraft deck operation scheduling problem solved by variable neighborhood search-based estimation of distribution algorithm［J］. Journal of Systems Science and Mathematical Sciences， 2024， 44（2）： 391-407 （in Chinese）.
[22]	黄珈其，郭宏伟，杨帅，等. 航空保障作业两阶段动态调度方法研究［J/OL］. 北京航空航天大学学报， 2024： 1-13. （2024-08-30）. .
	HUANG J Q， GUO H W， YANG S， et al. Research on two-stage dynamic scheduling method of aviation support operation［J/OL］. China Industrial Economics， 2024： 1-13. （2024-08-30）. （in Chinese）.
[23]	邓建辉，田程程，王岩磊，等. 基于改进樽海鞘算法的舰载机舰面保障作业流程优化方法［J］. 中国舰船研究， 2024， 19（S2）： 1-10.
	DENG J H， TIAN C C， WANG Y L， et al. Optimization method of carrier-based aircraft surface support operation process based on improved sea sheath algorithm［J］. Chinese Journal of Ship Research， 2024， 19（S2）： 1-10 （in Chinese）.
[24]	刘珏，王能建，罗旭，等. 采用改进遗传算法的舰载机保障调度方法［J］. 国防科技大学学报， 2020， 42（2）： 194-205.
	LIU J， WANG N J， LUO X， et al. Deck operation scheduling method of carrier-based aircraft based on improved genetic algorithm［J］. Journal of National University of Defense Technology， 2020， 42（2）： 194-205 （in Chinese）.
[25]	李亚飞，高磊，蒿宏杰，等. 舰载机保障作业人机协同决策方法［J］. 中国科学：信息科学， 2023， 53（12）： 2493-2510.
	LI Y F， GAO L， HAO H J， et al. Human-machine collaborative decision-making for carrier aircraft support operations［J］. Scientia Sinica （Informationis）， 2023， 53（12）： 2493-2510 （in Chinese）.
[26]	穆琳，吴家仁，刘东，等. 基于虚拟现实的舰面保障流程优化仿真研究［J］. 航空工程进展， 2025， 16（6）： 61-70.
	MU L， WU J R， LIU D， et al. Simulation research on optimization of ship surface support process based on virtual reality［J］. China Industrial Economics， 2025， 16（6）： 61-70 （in Chinese）.
[27]	刘广，王华，林友芳，等. 舰载机保障作业自适应批量匹配决策方法［J］. 航空学报， 2025， 46（1）： 330615.
	LIU G， WANG H， LIN Y F， et al. Adaptive batch matching decision method for carrier-based aircraft support operations［J］. Acta Aeronautica et Astronautica Sinica， 2025， 46（1）： 330615 （in Chinese）.
[28]	DEMEULEMEESTER E， DODIN B， HERROELEN W. A random activity network generator［J］. Operations Research， 1993， 41（5）： 972-980.
[29]	KADRI R L， BOCTOR F F. An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times： The single mode case［J］. European Journal of Operational Research， 2018， 265（2）： 454-462.
[30]	WANG L， FANG C. A hybrid estimation of distribution algorithm for solving the resource-constrained project scheduling problem［J］. Expert Systems with Applications， 2012， 39（3）： 2451-2460.

保障阵位	可覆盖该阵位的保障设备编号
保障阵位	加油	电源	充氧	充电	液压
1	［1］	［1］	［1］	［1］	［1］
2	［1］	［2］	［1］	［1］	［1， 2］
3	［1， 2］	［3］	［1］	［1］	［1， 2］
4	［2］	［4］	［1， 2］	［1， 2］	［2， 3］
5	［2］	［5］	［2］	［2］	［3］
6	［3］	［6］	［2］	［2］	［3］
7	［3， 4］	［7］	［2， 3］	［2， 3］	［4］
8	［4］	［8］	［3］	［3］	［4］
9	［4， 5］	［9］	［3， 4］	［3， 4］	［4， 5］
10	［5］	［10］	［4］	［4］	［5］
11	［5］	［11］	［4］	［4］	［5］
12	［6］	［12］	［5］	［5］	［6］
13	［6， 7］	［13］	［5， 6］	［5， 6］	［6］
14	［7］	［14］	［6］	［6］	［6， 7］
15	［7-8］	［15］	［6， 7］	［6， 7］	［7］
16	［8］	［16］	［7］	［7］	［7］

舰载机数	完工时间/min
舰载机数	α=0.1	α=0.3	α=0.5	α=0.7	α=0.9
平均	69.74	69.64	69.69	69.71	69.58
4	67.10	67.15	67.30	67.30	67.00
6	68.80	68.35	68.65	68.80	68.70
8	69.15	69.25	69.30	69.35	69.05
12	70.35	70.40	70.30	70.30	70.15
16	73.30	73.05	72.90	72.80	73.00

测试案例	完工时间/min
测试案例	DPFGSA	GA-TPCO	HEDA	ISSA	A2C	MCTS
平均	74.1	72.5	71.5	73.6	74.4	69.7
I4PS3.5	61.8	61.0	57.4	61.4	62.1	60.0
I6PS3.5	64.2	63.3	61.7	63.4	64.5	62.7
I8PS3.5	67.0	65.3	64.7	67.1	68.0	63.9
I12PS3.5	67.9	66.3	66.3	68.1	68.5	65.4
I16PS3.5	70.8	69.4	68.6	71.8	71.1	68.4
I4PS1.8	81.4	78.5	77.7	80.6	81.3	74.6
I6PS1.8	81.6	79.5	78.1	79.4	81.4	74.6
I8PS1.8	81.4	78.2	79.3	80.6	81.5	74.7
I12PS1.8	80.6	81.4	79.1	80.8	81.8	75.2
I16PS1.8	83.8	82.3	82.1	82.7	84.1	77.4

测试案例	耗时/s
测试案例	DPFGSA	GA-TPCO	HEDA	ISSA	A2C	MCTS
平均	302	255	333	309	0.7	120
I4PS3.5	61	56	66	61	0.4	38
I6PS3.5	142	125	156	142	0.5	70
I8PS3.5	204	166	214	189	0.6	93
I12PS3.5	375	314	428	382	0.8	137
I16PS3.5	594	497	711	610	1.1	214
I4PS1.8	63	52	70	66	0.4	38
I6PS1.8	132	97	144	134	0.5	61
I8PS1.8	240	182	260	246	0.6	96
I12PS1.8	458	393	528	494	0.8	170
I16PS1.8	747	667	748	767	1.2	283

Scheduling method for carrier-based aircraft support operations based on Monte Carlo tree search

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 30

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Yizhe LUO, Hui ZHANG, Xinde YU, Zhao JIN, Shuo FENG, Yucheng SHI, Mingling XU. Hierarchical dynamic scheduling for multi-wave carrier-based aircraft ammunition support missions [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(18): 331945-331945.
[2]	Xiaochen LYU, Jingping SHI, Yongxi LYU, Gengnong LI. Flow angle reconstruction algorithm for MAGIC CARPET landing with sensor failure [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 531159-531159.
[3]	Fang GUO, Wei HAN, Yujie LIU, Jie LIU, Xichao SU, Liangliang CHENG. Scheduling for maintenance and service support of carrier-based aircraft based on variable operation process [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 531195-531195.
[4]	Yu LI, Tongwen CHEN, Zhigang WANG, Chiyung WEN, Xiaoxiong LIU. Incremental control of direct lift landing based on predefined-time theory [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 531163-531163.
[5]	Wei CHEN, Lulu LI, Dong CHEN, Shaohui ZHANG, Yafei LI, Ke WANG, Yuanyuan JIN, Mingliang XU. Multi-aircraft cooperative decision-making methods driven by differentiated support demands for carrier-based aircraft [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 531274-531274.
[6]	Xudong CHEN, Qiqi CHEN, Yizhe LUO, Jiabao WANG, Mingliang XU. Dynamic parallel scheduling of heterogeneous carrier-based aircraft deck support operations [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 531329-531329.
[7]	Zheng WANG, Hua WANG, Keke CUI, Chaochao LI, Junnan LIU, Mingliang XU. Locally guided reinforcement learning for autonomous dispatching of carrier-based aircraft [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 531333-531333.
[8]	Xinze XU, Guanxin HONG, Liang DU, Gang LIU. Manual approach and landing model of carrier-based aircraft in complex environments [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 531802-531802.
[9]	Jiaxing WANG, Hao CHEN, Zheng SHAO, Yang ZHANG. Direct lift landing control method based on flight path angle command [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 532162-532162.
[10]	Zhibing ZHANG, Ziyang ZHEN. Research progress on guidance and control of fixed-wing manned and unmanned carrier-based aircraft landing [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(13): 532336-532336.
[11]	Guang LIU, Hua WANG, Youfang LIN, Shuo HE, Yafei LI, Mingliang XU. Adaptive batch matching decision method for carrier-based aircraft support operations [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(1): 330615-330615.
[12]	Dapeng ZHOU, Xiaolei QU. Knowledge-based intelligent pigeon-inspired optimization of carrier-based aircraft landing control [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(S1): 730801-730801.
[13]	FU Jiawei, YU Jialong, LIU Chao, WANG Muguo, WANG Zizi. Key technologies of aerodynamics design of stealth carrier-based aircraft [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(8): 525804-525804.
[14]	WANG Xiao, CHENG Jianhui, SHEN Tianrong, XU Baocheng, MENG Xuan. Numerical simulation research of influence of wake flow field on inlet temperature field of carrier-based aircraft [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(8): 525795-525795.
[15]	CHEN Yueliang, CHEN Liang, BIAN Guixue, YANG Xiangning, GUAN Yu, ZHANG Yong, HE Gang. Corrosion protection control and calendar life design of advanced carrier-based aircraft [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(8): 525786-525786.