基于MGP算法的舰载机回收排序调度技术

doi:10.12305/j.issn.1001-506X.2023.10.24

摘要/Abstract

摘要：

针对舰载机机群着舰回收排序调度问题，首先对航母甲板环境以及舰载机的返航回收进场模式进行了分析, 建立了基于加权等待时间的回收排序评价指标模型, 并根据舰载机回收着舰排序调度问题中的各种约束, 建立了考虑空中加油条件的舰载机回收排序调度问题模型。然后, 根据所建立的回收调度排序模型以及超启发式算法的思想, 设计了一种带强制着舰规则的遗传规划(genetic programming with mandatory landing rules, MGP)算法, 用于对着舰回收排序调度问题进行求解。进一步, 借助仿真算例验证了所建回收排序调度模型和MGP算法的有效性, 并通过与遗传算法、纯启发式算法以及普通的遗传规划算法进行对比, 验证了MGP算法的优势。最后, 基于算例仿真结果, 分析了逃逸复飞对着舰回收方案的影响。

关键词: 舰载机, 回收排序, 空中加油, 超启发算法, 遗传规划

Abstract:

Aiming at the problem of the recovery sequencing and scheduling of the carrier aircraft fleet landing, the carrier deck environment and the return recovery approach mode of the carrier aircraft are analyzed firstly, and the evaluation index model of the recovery sequencing and scheduling based on the weighted waiting time is established. According to the various constraints in the recovery sequencing and scheduling problem of the carrier aircraft, the model of the recovery sequencing and scheduling problem of the carrier aircraft considering the air refueling condition is established.Then, according to the established recycling sequencing and scheduling model and the idea of huper-heuristic algorithm, a genetic programming with mandatory landing rules (MGP) algorithm is designed to solve the ship necovery scheduling problem. Further, the effectiveness of the proposed recovery sequencing and scheduling model and MGP algorithm is verified by simulation examples, and the advantages of MGP algorithm are verified by comparison with genetic algorithm, pure heuristic algorithm and common genetic programming algorithm. Finally, based on the simulation results of an example, the influence of escape and wave off on the landing fleet recovery scheme is analyzed.

Key words: carrier aircraft, recovery sequencing, air refueling, hyper-heuristic algorithm, genetic programming

中图分类号:

V355.2

崔凯凯, 崔荣伟, 韩维, 郭放, 王毓麟, 刘洁. 基于MGP算法的舰载机回收排序调度技术[J]. 系统工程与电子技术, 2023, 45(10): 3192-3206.

Kaikai CUI, Rongwei CUI, Wei HAN, Fang GUO, Yulin WANG, Jie LIU. Carrier aircraft recovery sequencing scheduling technology based on MGP algorithm[J]. Systems Engineering and Electronics, 2023, 45(10): 3192-3206.

图/表 14

图1

表1

图2

图3

图4

图5

表2

表3

表4

图6

图7

图8

表5

表6

参考文献 31

1	ZHANG J F , ZHAO P . A new meta heuristic approach for aircraft landing problem[J]. Transactions of Nanjing University of Aeronautics and Astronautics, 2020, 37 (2): 197- 208.
2	ANDREEVA-MORI A , SUZUKI S , ITOH E . Rule derivation for arrival aircraft sequencing[J]. Aerospace Science and Technology, 2013, 30 (1): 200- 209. doi: 10.1016/j.ast.2013.08.004
3	王义平. 基于AF-PSO的飞机着陆排序算法及其FPGA实现[D]. 南京: 南京航空航天大学, 2018.
	WANG Y P. Aircraft landing sorting algorithm based on AF- PSO and FPGA implementation[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2018.
4	CAO Y , RATHINAM S , SUN D F . Greedy heuristic aided mixed integer linear programming approach for arrival scheduling[J]. Journal of Aerospace Information Systems, 2013, 10 (7): 323- 336. doi: 10.2514/1.I010030
5	ZHANG J F , ZHAO P , ZHANG Y , et al. Criteria selection and multi-objective optimization of aircraft landing problem[J]. Journal of Air Transport Management, 2020, 82, 101734. doi: 10.1016/j.jairtraman.2019.101734
6	张军峰, 郑志祥, 葛腾腾. 基于复合分派规则的进场航班排序方法[J]. 交通运输工程学报, 2017, 17 (3): 141- 150.
	ZHANG J F , ZHENG Z X , GE T T . Sequencing approach of arrival aircrafts based on composite dispatching rules[J]. Journal of Traffic and Transportation Engineering, 2017, 17 (3): 141- 150.
7	SHI W , JIANG S , LIANG X . A heuristic algorithm for solving the aircraft landing scheduling problem with a landing sequence division[J]. IEICE Trans.on Fundamentals of Electronics, Communications and Computer Sciences, 2019, E102-A (8): 966- 973. doi: 10.1587/transfun.E102.A.966
8	吴宇. 舰载机机队起降任务规划方法研究[D]. 北京: 北京航空航天大学, 2016.
	WU Y. Mission planning for a team of aircraft launching and landing on carrier[D]. Beijing: Beihang University, 2016.
9	BEASLEY E J , KRISHNAMOORTHY M , SHARAIHA M Y , et al. Scheduling aircraft landings-the static case[J]. Transportation Science, 2000, 34 (2): 180- 197. doi: 10.1287/trsc.34.2.180.12302
10	夏国清, 陈红召, 米青超. 舰载机回收作业的反馈排队模型[J]. 火力与指挥控制, 2013, 38 (5): 168-170, 173.
	XIA G Q , CHEN H Z , MI Q C . A sequencing model with feedback for embarked aircraft's recovery[J]. Fire Control & Command Control, 2013, 38 (5): 168-170, 173.
11	林华, 占明锋, 周丰. 舰载机回收任务的优化调度算法及仿真[J]. 海军工程大学学报, 2008, 20 (1): 54- 58.
	LIN H , ZHAN M F , ZHOU F . optimization schedule algorithm and simulation to recycle planes on carrier[J]. Journal of Naval University of Engineering, 2008, 20 (1): 54- 58.
12	刘玉杰, 万兵, 苏析超, 等. 基于IABC算法的舰载机着舰调度[J]. 控制与决策, 2022, 37 (7): 1810- 1818.
	LIU Y J , WAN B , SU X C , et al. Shipborne aircraft landing scheduling based on IABC algorithm[J]. Control and Decision, 2022, 37 (7): 1810- 1818.
13	张龙杰, 何凡, 刘青松. 考虑逃逸复飞队列饱和度的舰载机回收策略[J]. 火力与指挥控制, 2017, 42 (8): 15-18, 23.
	ZHANG L J , HE F , LIU Q S . Recover strategy of carrier aircraft based on saturation of waved off and bolter queue[J]. Fire Control & Command Control, 2017, 42 (8): 15-18, 23.
14	WU Y , SUN L G , QU X J . A sequencing model for a team of aircraft landing on the carrier[J]. Aerospace Science and Technology, 2016, 54 (7): 72- 87.
15	刘爱东, 桂周. 基于模拟退火的PSO算法在舰载机回收中的应用[J]. 指挥与控制仿真, 2014, 36 (5): 59- 62.
	LIU A D , GUI Z . Application of particle swarm algorithm based on simulated annealing for carrier aircraft's recovery[J]. Command Control & Simulation, 2014, 36 (5): 59- 62.
16	万兵, 韩维, 梁勇, 等. 基于指标函数的舰载机机队回收调度优化研究[J]. 系统工程与电子技术, 2021, 43 (10): 2918- 2930.
	WAN B , HAN W , LIANG Y , et al. Research on optimization of carrier-based aircraft fleet recovery scheduling based on index function[J]. Systems Engineering and Electronic Technology, 2021, 43 (10): 2918- 2930.
17	陈浩杰, 丁国富, 张剑, 等. 求解资源受限多项目调度的改进遗传规划算法[J]. 中国机械工程, 2021, 32 (10): 1213- 1221.
	CHEN H J , DING G F , ZHANG J , et al. Improved genetic programming algorithm for RCMPSP[J]. Chinese Mechanical Engineering, 2021, 32 (10): 1213- 1221.
18	COWLING P, KENDALL G, SOUBEIGA E. A hyperheuristic approach to scheduling a sales summit[C]//Proc. of the International Conference on the Practice and Theory of Automated Timetabling, 2000.
19	罗敏. 基于超启发式算法的多模具限制柔性作业车间问题研究[D]. 杭州: 浙江大学, 2021.
	LUO M. Research on hyper-heuristic for molds-constrained flexible job shop problem[D]. Hangzhou: Zhejiang University, 2021.
20	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.
21	黄子钊, 庄子龙, 滕浩, 等. 自动化码头出口箱箱位分配优化超启发式算法[J]. 计算机集成制造系统, 2022, 28 (8): 2619- 2632.
	HUANG Z Z , ZHUANG Z L , TENG H , et al. optimization of outbound container space assignment in automated container terminals based on hyper-heuristic[J]. Computer Integrated Manufacturing Systems, 2022, 28 (8): 2619- 2632.
22	OLGUN B , KOC C , ALTIPARMAK F . A hyper heuristic for the green vehicle routing problem with simultaneous pickup and delivery[J]. Computers & Industrial Engineering, 2020, 153, 107010.
23	ABDOLREZA R K , MAHBOUBEH S . A hyper-heuristic selector algorithm for cloud computing scheduling based on workflow features[J]. Opsearch, 2021, 58 (4): 852- 868.
24	BRANKE J , NGUYEN S , PICKARDT C W , et al. Automated design of production scheduling heuristics: a review[J]. IEEE Trans.on Evolutionary Computation, 2016, 20 (1): 110- 124.
25	CHEN H J , DING G F , QIN S F , et al. A hyper-heuristic based ensemble genetic programming approach for stochastic resource constrained project scheduling problem[J]. Expert Systems with Applications, 2021, 167, 114174.
26	张苏雨, 王艳, 纪志成. 基于超启发式遗传规划的动态车间调度方法[J]. 系统仿真学报, 2020, 32 (12): 2494- 2506.
	ZHANG S Y , WANG Y , JI Z C . Automatic discovery method of dynamic job shop dispatching rules based on hyper-heuristic genetic programming[J]. Journal of System Simulation, 2020, 32 (12): 2494- 2506.
27	LIN J , ZHU L , GAO K Z . A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem[J]. Expert Systems with Applications, 2019, 140, 112915.
28	SHELVIN C , QUANG H , HEMANT S , et al. On the use of genetic programming to evolve priority rules for resource constrained project scheduling problems[J]. Information Sciences, 2018, 432, 146- 163.
29	SHELVIN C , HEMANT S , TAPABRATA R . Evolving heuristics for the resource constrained project scheduling problem with dynamic resource disruptions[J]. Swarm and Evolutionary Computation, 2019, 44, 897- 912.
30	JOE C T , NHU B H . Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems[J]. Computers & Industrial Engineering, 2008, 54 (3): 453- 473.
31	杨一栋. 舰载飞机着舰引导与控制[M]. 北京: 国防工业出版社, 2007.
	YANG Y D . Guidance and control of carrier-based aircraft landing[M]. Beijing: National Defense Industry Press, 2007.

序号	前序飞机类型	后续飞机类型	尾流间隔时间要求/s
1	S	S	94
2	S	M	83
3	S	L	83
4	M	S	110
5	M	M	89
6	M	L	89
7	L	S	170
8	L	M	135
9	L	L	113

参数名称	取值/s	参数名称	取值/s
TO_safe	1 042	TO_cr	159
TO_max	11 000	T_ML	432
TO_ff	602	JT_min	900
TO_min	281	—	—

舰载机编号	着舰次序	着舰等待时间/s	安全时间裕度/s	着舰剩余油量/L
1	21	2 442	1 849	2 602
2	11	1 458	2 167	2 888
3	7	1 032	2 926	4 762
4	20	2 353	1 272	2 082
5	27	3 017	5 441	3 890
6	29	3 205	4 753	3 477
7	2	515	2 776	3 437
8	18	2 105	1 353	2 874
9	16	1 903	55	987
10	5	806	3 652	5 633
11	17	1 992	1 966	3 610
12	19	2 218	1 490	3 038
13	9	1 280	2 678	3 348
14	26	2 923	5 035	3 646
15	15	1 814	2 477	3 167
16	8	1 145	1 313	2 826
17	10	1 369	3 256	3 868
18	3	604	3 021	3 656
19	30	3 299	5 159	3 721
20	14	1 725	2 566	3 248
21	25	2 829	7 129	4 903
22	6	919	2 539	4 297
23	28	3 111	3 347	2 633
24	13	1 636	2 655	3 328
25	24	2 735	6 223	4 359
26	4	693	2 515	4 268
27	22	2 531	1 427	2 222
28	1	432	7 526	5 141
29	12	1 547	3 744	4 308
30	23	2 641	4 317	3 215

舰载机数量	调度方案求解算法	评价指标函数值/s	任务完成时间/s	空中加油架次	单次迭代计算耗时/s
15	MGP	6 154.9	1 851.2	0	0.106 0
	GP	6 163.2	1 853.5	0	0.099 1
	GA	6 178.8	1 857.5	0	0.378 8
	LFFS	6 575.8	1 867.9	0	0.002 4
	HPFS	6 805.7	1 900.0	0.033 3	0.002 6
25	MGP	14 362.0	2 829.1	0	0.145 5
	GP	14 436.8	2 827.9	0	0.127 3
	GA	14 640.5	2 861.7	0	0.300 9
	LFFS	15 364.1	2 858.9	0	0.001 7
	HPFS	17 597.6	2 952.4	0.833 3	0.001 8
35	MGP	25 866.0	3 824.9	0	0.189 2
	GP	25 975.1	3 822.6	0	0.180 1
	GA	27 202.1	3 911.6	0	0.309 2
	LFFS	27 568.9	3 846.0	0	0.001 7
	HPFS	32 476.9	3 982.9	1.400 0	0.001 8
45	MGP	40 798.2	4 790.9	0	0.297 8
	GP	41 148.7	4 793.2	0	0.269 8
	GA	48 032.6	4 874.0	1.066 7	0.350 9
	LFFS	43 298.3	4 807.1	0	0.001 8
	HPFS	69 623.3	4 993.7	6.466 7	0.002 0

再次着舰机编号	任务完成时间/s	评价指标函数值/s	再次着舰机编号	任务完成时间/s	评价指标函数值/s
25	3 393.0	19 729.0	{10, 22}	3 525.0	21 836.0
5	3 434.0	19 666.0	{22, 12}	3 593.0	21 211.0
19	3 716.0	19 597.0	{17, 30}	3 482.0	20 441.0
20	3 410.0	20 142.0	{7, 21}	3 504.0	21 040.0
28	3 439.0	21 153.0	{11, 23}	3 663.0	20 192.0
9	3 388.0	20 019.0	{20, 8}	3 545.0	20 677.0
26	3 412.0	20 781.0	{20, 4}	3 509.0	20 460.0
21	3 393.0	19 694.0	{2, 25}	3 482.0	20 363.0
29	3 388.0	20 099.0	{8, 19}	3 865.0	20 098.0
18	3 410.0	20 776.0	{12, 14}	3 552.0	20 097.0
均值	3 438.3	20 165.6	均值	3 572.0	20 641.4