基于CE-PF算法的舰载机离场调度优化问题

doi:10.13700/j.bh.1001-5965.2020.0674

北京航空航天大学学报 ›› 2022, Vol. 48 ›› Issue (5): 771-785.doi: 10.13700/j.bh.1001-5965.2020.0674

基于CE-PF算法的舰载机离场调度优化问题

万兵¹, 韩维¹, 苏析超¹, 刘洁²

1. 海军航空大学, 烟台 264001;
2. 军事科学院战争研究院, 北京 100850

收稿日期:2020-12-02 发布日期:2022-05-30
通讯作者: 苏析超 E-mail:suxich@126.com
基金资助:
国家自然科学基金(61903374)；航空科学基金(2016ZA01008)

Carrier-based aircraft departure scheduling optimization based on CE-PF algorithm

WAN Bing¹, HAN Wei¹, SU Xichao¹, LIU Jie²

1. Naval Aviation University, Yantai 264001, China;
2. War Research Institute, Academy of Military Sciences, Beijing 100850, China

Received:2020-12-02 Published:2022-05-30
Supported by:
National Natural Science Foundation of China (61903374);Aeronautical Science Foundation of China (2016ZA01008)

摘要/Abstract

摘要： 甲板作业调度研究是提升航母战斗力的关键技术，而其具有时间、空间与资源受限的复杂约束调度问题已被证实为NP-hard。根据舰载机出动离场调度优化问题的特点，将其抽象为零缓存区混合流水车间调度模型，建立包含飞机避碰等约束的混合整数规划模型。提出一种交叉熵与作业剖面匹配(CE-PF)算法用于问题求解，并给出了算法流程架构。交叉熵算法通过高斯采样完成启发式规则下的工件分组，作业剖面匹配算法完成分组工件的任务排序、作业编排及约束检查等调度设计，Gap逼近算法进行目标值评估、精英种群选择、抽样参数更新及收敛判定。通过算例仿真，验证了CE-PF算法求解离场调度优化问题的有效性；灵敏度分析表明起飞模式和空间约束对出动效能影响较大。

关键词: 舰载机, 出动离场, 交叉熵与作业剖面匹配(CE-PF)算法, 调度, 优化

Abstract: Carrier-deck operation scheduling is a key technology to improve the combat effectiveness of aircraft carriers, and the optimization scheduling problem of complex constraints with time, space and resource constraints has been proved to be NP-hard. We study the optimization problem of carrier-based aircraft sortie and departure scheduling, which is abstracted as a zero-buffer hybrid flow shop scheduling model. A mixed integer programming model including aircraft collision avoidance and other constraints is established. Then, a cross entropy-operation profile fitting (CE-PF) optimization intelligent algorithm is proposed to solve the mathematical model. The flowchart of solving algorithm is given. The jobs grouped by heuristic rules are accomplished by the cross-entropy algorithm through Gaussian sampling, the scheduling design of task sorting, operations permutation and constraint checking in the grouped jobs is completed by the operation profile fitting algorithm, and the gap approximation algorithm is used to perform the target value evaluation, elite population selection, sampling parameters update and optimal convergence decision. The simulation results show that the CE-PF algorithm can solve the departure scheduling problem efficiently. The sensitivity analysis shows that the take-off mode and space constraints have a great influence on aircraft sortie efficiency.

Key words: carrier-based aircraft, sortie and departure, cross entropy-operations profile fitting (CE-PF) algorithm, scheduling, optimization

中图分类号:

万兵, 韩维, 苏析超, 刘洁. 基于CE-PF算法的舰载机离场调度优化问题[J]. 北京航空航天大学学报, 2022, 48(5): 771-785.

WAN Bing, HAN Wei, SU Xichao, LIU Jie. Carrier-based aircraft departure scheduling optimization based on CE-PF algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(5): 771-785.

参考文献

[1] 屈也频, 金惠明,何肇雄.航母舰载机装备体系及指标论证方法[J].航空学报,2018,39(5):108-119.QU Y P,JIN H M,HE Z X.Carrier-based aircraft equipment system-of-systems and index demonstration method[J].Acta Aeronuatica et Astronautica Sinica,2018,39(5):108-119(in Chinese).
[2] 谢君, 廖松,石章松.航母作战部署中的舰载机出动规划模型[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(in Chinese).
[3] 姜龙光. 国外航母航空保障系统[M].北京:国防工业出版社,2016:1-35.JIANG L G.Foreign aircraft carrier aviation support system[M].Beijing:National Defense Industry Press,2016:1-35(in Chinese).
[4] WANG X W,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.
[5] RYAN J C,CUMMINGS M L,ROY N,et al.Designing an interactive local and global decision support system for aircraft carrier deck scheduling:AIAA-2011-1516[R].Reston:AIAA，2011.
[6] MICHINI B,HOW J P.A human-interactive course of action planner for aircraft carrier deck operations[C]//Proceedings of AIAA Information Technology.Reston:AIAA,2011:1515.
[7] DASTIDAR R G,FRAZZOLI E.A queueing network based approach to distributed aircraft carrier deck scheduling[C]//Proceedings of AIAA Information Technology.Reston:AIAA,2011:1514.
[8] RYAN J C.Evaluating safety protocols for manned unmanned environments through agent based simulation[D].Cambridge:Massachusetts Institute of Technology,2014:35-65.
[9] QI C,WANG D.Dynamic aircraft carrier flight deck task planning based on HTN[J].IFAC-PapersOnLine,2016,49(12):1608-1613.
[10] 郑茂, 黄胜,王超.优先网络排队的舰载机出动回收能力研究[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(in Chinese).
[11] 司维超,韩维,史玮韦．基于PSO算法的舰载机舰面布放调度方法研究[J].航空学报,2012,33(11):2048-2056.SI W C,HAN W,SHI W W.Research on deck-disposed scheduling method of carrier planes based on PSO algorithm[J].Acta Aeronautica et Astronautica Sinica,2012,33(11):2048-2056(in Chinese).
[12] 苏析超, 韩维,萧卫,等.基于Memetic算法的舰载机舰面一站式保障调度[J].系统工程与电子技术,2016,38(10):2303-2309.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(in Chinese).
[13] 杨放青, 王超，姜滨，等.舰载机出动回收调度策略生成方法[J].北京理工大学学报,2018,38(10):1030-1036.YANG F Q,WANG C,JIANG B， el 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(in Chinese).
[14] 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.
[15] 苏析超, 韩维,张勇,等.考虑人机匹配模式的舰载机甲板机务勤务保障调度方法[J].航空学报,2018,39(12):222314.SU X C，HAN W，ZHANG Y,et al.Scheduling method 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).
[16] SU X C,HAN W,WU Y,et a1.A proactive robust scheduling method for aircraft carrier flight deck operations with stochastic durations[J].Complexity,2018,2018:6932985.
[17] 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.
[18] JIANG T,SU X,HAN W.Optimization of support scheduling on deck of carrier aircraft based on improved differential evolution algorithm[C]//Proceedings of the 3rd IEEE International Conference on Control Science and Systems Engineering.Piscataway:IEEE Press,2017:136-140.
[19] ASHIS G B,NICHOLAS R.Efficiently solving repeated integer linear programming problems by learning solutions of similar linear programming problems using boosting trees:MIT-CSAIL-TR-2015-001[R].Cambridge:Massachusetts Institute of Technology,2015:12-35.
[20] 刘翱,刘克.舰载机保障作业调度问题研究进展[J].系统工程理论与实践,2017,37(1):49-60.LIU A,LIU K．Advances in carrier-based aircraft deck operation scheduling[J].Systems Engineering-Theory and Practice,2017,37(1):49-60(in Chinese).
[21] PINEDO M L.Scheduling theory,algorithms,and systems[M].5th ed.Berlin:Springer,2016:150-165.
[22] CABO M,POSSANI E.Considerations on applying cross entropy methods to the vehicle routing problem[J].International Journal of Combinatorial Optimization Problems and Informatics,2015,6(3):22-33.
[23] 王桂荣，李歧强，丁然,等.加工时间不确定的炼钢连铸生产调度串级交叉熵算法[J].控制与决策,2016,31(7):1153-1160.WANG G R,LI Q Q,DING R,et al.Cascade cross entropy algorithm for steelmaking-continuous casting production scheduling with uncertain processing time[J].Control and Decision,2016,31(7):1153-1160(in Chinese).
[24] 张智, 林圣琳,朱齐丹,等.考虑运动学约束的不规则目标遗传避碰规划算法[J].航空学报,2015,36(4):1348-1358.ZHANG Z,LIN S L,ZHU Q D,et al.Genetic collision avoidance planning algorithm for irregular shaped object with kinematics constraint[J].Acta Aeronautica et Astronautica Sinica,2015,36(4):1348-1358(in Chinese).

基于CE-PF算法的舰载机离场调度优化问题

Carrier-based aircraft departure scheduling optimization based on CE-PF algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张彩萍, 李峰, 张琳静, 王宇斌, 贾新羽, 张维戈. 基于正负极动力学特性的锂离子电池优化充电方法[J]. 北京航空航天大学学报, 2022, 48(5): 725-735.
[2]	李鑫滨, 郭力争, 韩松. 一种分布式异构多AUV任务分配鲁棒拍卖算法[J]. 北京航空航天大学学报, 2022, 48(5): 736-746.
[3]	缪柯强, 王曦, 朱美印. 基于LMI的过渡态主控回路闭环控制律优化设计[J]. 北京航空航天大学学报, 2022, 48(5): 841-854.
[4]	王辉, 何天宇, 都显琛, 王春洁. 单元构架式抛物面天线张紧绳索多层设计方法[J]. 北京航空航天大学学报, 2022, 48(4): 657-664.
[5]	王宁, 李哲, 梁晓龙, 侯岳奇, 吴傲. 基于搜索意图交互的无人机集群协同搜索算法[J]. 北京航空航天大学学报, 2022, 48(3): 454-463.
[6]	郝靖伟, 潘丽敏, 李蕊, 杨鹏, 罗森林. Android恶意软件检测低冗余特征选择方法[J]. 北京航空航天大学学报, 2022, 48(2): 225-232.
[7]	宋超, 周铸, 李伟斌, 罗骁. 旋翼翼型高维多目标气动优化设计[J]. 北京航空航天大学学报, 2022, 48(1): 95-105.
[8]	王璟贤, 师鹏, 陈致钧, 赵勇, 白玉铸. 非合作目标安全走廊设计及飞越逼近轨迹优化[J]. 北京航空航天大学学报, 2021, 47(9): 1832-1840.
[9]	侯煦, 邢玉明, 郝兆龙, 王仕淞, 侯天睿. 高碳醇/膨胀石墨复合相变热沉多目标优化[J]. 北京航空航天大学学报, 2021, 47(9): 1866-1873.
[10]	牛得清, 伍友利, 徐洋, 吴鑫, 张丹旭, 杨鹏飞. 红外空空导弹抗干扰效能评估建模[J]. 北京航空航天大学学报, 2021, 47(9): 1874-1883.
[11]	霍继伟, 刘泽, 王亚东, 袁伟, 王成飞. 优化Landweber迭代快速电磁层析成像图像重建算法[J]. 北京航空航天大学学报, 2021, 47(8): 1571-1579.
[12]	李旭阳, 万志强, 王晓喆, 杨璐嘉, 杨超. 考虑多巡航工况的大型飞机气动弹性优化[J]. 北京航空航天大学学报, 2021, 47(8): 1628-1637.
[13]	邱明, 严勇杰, 孙蕊, 张文宇. 基于帝国竞争优化的双目标综合决策选星算法[J]. 北京航空航天大学学报, 2021, 47(8): 1646-1655.
[14]	任毅如, 向剑辉, 何杰, 宁克焱, 杨玲玲. 基于导重法的自重载荷下悬臂梁结构拓扑优化[J]. 北京航空航天大学学报, 2021, 47(7): 1338-1344.
[15]	汤安迪, 韩统, 徐登武, 谢磊. 混沌多精英鲸鱼优化算法[J]. 北京航空航天大学学报, 2021, 47(7): 1481-1494.