舰载机出动离场调度优化算法

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

摘要/Abstract

摘要：

出动离场调度是舰载机起降作业中关键一环, 可抽象为NP(non-deterministic pdynoial)难问题的混合车间调度问题。首先，在传统数学规划模型基础上, 引入逻辑约束及间隔变量, 建立了约束规划模型。然后，通过调度分解技术构建多机调度转化为单机调度的启发式规则, 并提出了单机约束引导启发式搜索与约束规划二分法迭代算法, 给出了问题的求解流程。算例仿真表明, 约束规划可有效解决不同规模下的离场调度, 并快速收敛到阈值内; 在中小规模出动时, 所提算法效率比传统智能方法提升约2个数量级, 具有较强实时规划能力, 但随着实验规模增大算法收敛时间呈线性变化趋势, 而在本文研究范围内仍优于传统智能算法, 具有良好实用价值。最后，用起飞位数量对出动效率进行灵敏度分析, 发现C2起飞位对出动效能贡献最大。

关键词: 舰载机, 出动离场, 约束规划, 二分法迭代, 约束引导

Abstract:

Sortie departure scheduling is a key part of the take-off and landing operations of carrier-based aircraft, which can be abstracted as an non-deterministic polynomial(NP)-hard hybrid job-shop scheduling problem. Firstly, based on the traditional mathematical programming model, logical constraints and interval variables are introduced to establish a constraint programming model. Then, the heuristic rules for transforming multi-machine scheduling into single-machine scheduling are constructed through scheduling decomposition technology, and the single-machine constraint-guided heuristic search and constraint programming dichotomy iterative algorithm is proposed. The simulation results show that the constrained programming could effectively solve the problem of departure scheduling under different scales and converge to the threshold quickly. The efficiency of the proposed algorithm in small and medium scale is about two orders of magnitude higher than that of the traditional intelligent method, and it has strong real-time planning capabilities. However, as the scale increases, the convergence time changes linearly, and it is still better than traditional methods in the scope of this article. Finally, the sensitivity analysis of the sortie efficiency based on the number of available take-off positions shows that the C2 take-off position contributes the most to the dispatch efficiency.

Key words: carrier-based aircraft, sortie departure, constrained programming, dichotomy iteration, constraint guidance

中图分类号:

V355.2

万兵, 韩维, 梁勇, 郭放. 舰载机出动离场调度优化算法[J]. 系统工程与电子技术, 2021, 43(12): 3624-3634.

Bing WAN, Wei HAN, Yong LIANG, Fang GUO. Optimization algorithm of carrier-based aircraft sortie departure scheduling[J]. Systems Engineering and Electronics, 2021, 43(12): 3624-3634.

图/表 12

图1

图2

图3

图4

图5

图6

图7

表1

图8

表2

图9

图10

参考文献 20

1	韩维, 王庆官. 航母与舰载机概论[M]. 烟台: 海军航空工程学院出版社, 2009: 37- 41.
	HAN W , WANG Q G . Conspectus of aircraft carrier and carrier aircraft[M]. Yantai: Naval Aeronautical and Astronautical University Press, 2009: 37- 41.
2	姜龙光. 国外航母航空保障系统[M]. 北京: 国防工业出版社, 2016.
	JIANG L G . Foreign aircraft carrier aviation support system[M]. Beijing: National Defense Industry Press, 2016.
3	RYAN J C, CUMMINGS M L, ROY N, et al. Designing an interactive local and global decision support system for aircraft carrier deck scheduling[C]//Proc. of the AIAA Infotech@ Aerospace Conference, 2011.
4	RYAN J C. Evaluating safety protocols for manned unmanned environments through agent based simulation[D]. Massachusetts: Massachusetts Institute of Technology, 2014.
5	司维超, 韩维, 史玮玮. 基于HPSO算法和GA的舰载机甲板布放方法比较[J]. 系统工程与电子技术, 2013, 35 (2): 338- 344. doi: 10.3969/j.issn.1001-506X.2013.02.17
	SI W C , HAN W , SHI W W . Comparison of deck-disposed methods for shipboard aircraft based on HPSO and GA[J]. Systems Engineering and Electronic, 2013, 35 (2): 338- 344. doi: 10.3969/j.issn.1001-506X.2013.02.17
6	LIU J , HAN W , ZHANG Y , et al. Design of an online nonlinear optimal tracking control method for unmanned ground systems[J]. IEEE Access, 2018, 6, 33251- 33260. doi: 10.1109/ACCESS.2018.2846769
7	苏析超, 韩维, 张勇, 等. 考虑人机匹配模式的舰载机甲板机务勤务保障调度算法[J]. 航空学报, 2018, 39 (12): 222314.
	SU X C , HAN W , ZHANG Y , et al. Scheduling algorithm for maintenace and service support of carrier-based aircraft on flight deck with different man-aircraft matching patterns[J]. Acta Aeronautica Sinica, 2018, 39 (12): 222314.
8	苏析超, 韩维, 萧卫, 等. 基于Memetic算法的舰载机舰面一站式保障调度[J]. 系统工程与电子技术, 2016, 38 (10): 2303- 2309. doi: 10.3969/j.issn.1001-506X.2016.10.12
	SU X C , HAN W , XIAO W , et al. Pit-stop support scheduling on deck of carrier plane based on Memetic algorithm[J]. Systems Engineering and Electronics, 2016, 38 (10): 2303- 2309. doi: 10.3969/j.issn.1001-506X.2016.10.12
9	WU Y , QU X J . Obstacle avoidance and path planning for carrier aircraft launching[J]. Chinese Journal of Aeronautics, 2015, 28 (3): 695- 703. doi: 10.1016/j.cja.2015.03.001
10	张智, 林圣琳, 朱齐丹, 等. 考虑运动学约束的不规则目标遗传避碰规划算法[J]. 航空学报, 2015, 36 (4): 1348- 1358.
	ZHANG Z , LIN S L , ZHU Q D , et al. Genetic collision avoi-dance planning algorithm for irregular shaped object with kinematics constraint[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36 (4): 1348- 1358.
11	ASHIS G B, NICHOLAS R. Efficiently solving repeated integer linear programming problems by learning solutions of similar linear programming problems using boosting trees[R]. Massachusetts: Massachusetts Institute of Technology, 2015: 1-48.
12	ACHTERBERG T , BIXBY R E , GU Z , et al. Presolve reductions in mixed integer programming[J]. Informs Journal on Computing, 2020, 32 (2): 473- 506. doi: 10.1287/ijoc.2018.0857
13	PINEDO M L . Scheduling theory, algorithms, and systems[M]. 5th ed New York: Springer, 2016.
14	HOOKER J N . Integrated methods for optimization[M]. 2nd ed London: Springer, 2012.
15	谢君, 廖松, 石章松. 航母作战部署中的舰载机出动规划模型[J]. 系统工程与电子技术, 2020, 42 (1): 128- 132.
	XIE J , LIAO S , SHI Z S . Programming model of flight sortie for an aircraft carrier in transit[J]. Systems Engineering and Electronics, 2020, 42 (1): 128- 132.
16	杨放青, 王超, 姜滨, 等. 舰载机出动回收调度策略生成方法[J]. 北京理工大学学报, 2018, 38 (10): 1030- 1036.
	YANG F Q , WANG C , JIANG B , et al. A method of policy automated generation for carrier aircraft sortie and recovery scheduling[J]. Transactions of Beijing Institute of Technology, 2018, 38 (10): 1030- 1036.
17	郑茂, 黄胜, 王超. 优先网络排队的舰载机出动回收能力研究[J]. 北京理工大学学报, 2013, 33 (10): 1051- 1055.
	ZHENG M , HUANG S , WANG C . Research on aircraft sortie generation rate with the use of HOL closed queueing network model[J]. Transactions of Beijing Institute of Technology, 2013, 33 (10): 1051- 1055.
18	LABORIE P , ROGERIE J , SHAW P , et al. IBM ILOG CP optimizer for scheduling[J]. Constraints, 2018, 23 (2): 210- 250.
19	SU X C , HAN W , WU Y , et al. A robust scheduling optimization method for flight deck operations of aircraft carrier with ternary interval durations[J]. IEEE Access, 2018, 6, 69918- 69936.
20	WANG X , LIU J , SU X C , et al. A review on carrier aircraft dispatch path planning and control on deck[J]. Chinese Journal of Aeronautics, 2020, 33 (12): 3039- 3057.

出动规模/架	可行解数	决策变量	约束条件	收敛时间/s	终止/s	最优目标值	平均出动时间/s
8	17	122	118	0.1	0.97	348	43.50
12	14	178	170	0.33	0.85	463	39.42
18	13	262	248	0.44	0.91	638	35.44

算法	出动规模/架	最小收敛时间/s	算法平均时间/s	最佳目标/s	平均最佳目标/s
本文	8	0.10	0.88	348	348.00
	12	0.24	0.89	463	465.46
	18	0.36	0.93	638	639.74
PSO	8	5.82	14.22	348	349.24
	12	10.02	23.09	463	464.18
	18	12.98	36.74	646	647.92
DE	8	10.94	26.93	348	349.94
	12	10.27	39.38	468	468.43
	18	12.18	56.37	644	647.59
DPGA	8	10.45	59.86	348	350.12
	12	13.56	80.56	473	474.62
	18	24.68	120.26	649	650.38

[1]	张勇, 李常久, 苏析超, 崔荣伟. 基于HTLBO算法的舰载机机群机库维修任务调度[J]. 系统工程与电子技术, 2022, 44(9): 2858-2868.
[2]	邓嘉宁, 吴宇, 许舒婷, 苟进展. 基于模糊贝叶斯-ANP舰载机出动回收综合评估[J]. 系统工程与电子技术, 2022, 44(11): 3423-3432.
[3]	韩维, 崔凯凯, 刘洁, 王昕炜, 张勇. 基于自校正MPC的舰载机着舰控制技术[J]. 系统工程与电子技术, 2022, 44(1): 250-261.
[4]	曾斌, 陈媛媛, 李厚朴. 考虑保障装备可用度的舰载机作业调度优化[J]. 系统工程与电子技术, 2021, 43(7): 1856-1865.
[5]	崔荣伟, 韩维, 苏析超, 王立国, 刘玉杰. 舰载机甲板机务勤务保障作业调度与资源配置集成优化[J]. 系统工程与电子技术, 2021, 43(7): 1884-1893.
[6]	万兵, 韩维, 梁勇, 苏析超. 基于指标函数的舰载机机队回收调度优化研究[J]. 系统工程与电子技术, 2021, 43(10): 2918-2930.
[7]	岳奎志, 赵建忠, 程亮亮, 郁大照. 舰载机着舰航线侧方计时建模与分析[J]. 系统工程与电子技术, 2020, 42(6): 1332-1337.
[8]	袁培龙, 韩维, 苏析超, 高少辉. 不确定环境下舰载机保障预反应式动态调度优化[J]. 系统工程与电子技术, 2019, 41(6): 1265-1277.
[9]	吴文海, 汪节, 高丽, 张杨, 郭晓峰. MAGIC CARPET着舰技术分析[J]. 系统工程与电子技术, 2018, 40(9): 2079-2091.
[10]	吴文海, 张杨, 胡云安, 张源原. 舰载机着舰非线性反演控制方法研究进展[J]. 系统工程与电子技术, 2018, 40(7): 1578-1587.
[11]	张杨, 吴文海, 胡云安, 高丽. 舰载机着舰纵向非仿射模型控制器设计[J]. 系统工程与电子技术, 2018, 40(3): 635-642.
[12]	夏国清, 栾添添, 孙明晓, 仲伟东, 刘彦文. 基于主成分约简和突变级数的舰载机出动能力综合评估方法[J]. 系统工程与电子技术, 2018, 40(2): 330-337.
[13]	韩清华, 潘明海, 龙伟军. 基于机会约束规划的机会阵雷达功率资源管理算法[J]. 系统工程与电子技术, 2017, 39(3): 506-513.
[14]	杨启舶, 田瑾, 刘芳. #br# 基于Bayes判别方法的舰载机着舰安全分析[J]. 系统工程与电子技术, 2016, 38(9): 2208-2214.
[15]	苏析超, 韩维, 萧卫, 蒋婷婷. 基于Memetic算法的舰载机舰面一站式保障调度[J]. 系统工程与电子技术, 2016, 38(10): 2303-2309.