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

万兵; 韩维; 苏析超; 刘洁

doi:10.13700/j.bh.1001-5965.2020.0674

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

doi: 10.13700/j.bh.1001-5965.2020.0674

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

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

基金项目:

国家自然科学基金 61903374

航空科学基金 2016ZA01008

详细信息

通讯作者:
苏析超, E-mail: suxich@126.com

中图分类号: V221⁺.3; TB553
计量
- 文章访问数: 430
- HTML全文浏览量: 200
- PDF下载量: 47
- 被引次数: 0
出版历程
- 收稿日期: 2020-12-02
- 录用日期: 2021-03-12
- 网络出版日期: 2022-05-20

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

WAN Bing¹,
HAN Wei¹,
SU Xichao^{1
, ,},
LIU Jie²

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

Funds:

National Natural Science Foundation of China 61903374

Aeronautical Science Foundation of China 2016ZA01008

More Information

Corresponding author: SU Xichao, E-mail: suxich@126.com

摘要

摘要:
甲板作业调度研究是提升航母战斗力的关键技术，而其具有时间、空间与资源受限的复杂约束调度问题已被证实为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.
- carrier-based aircraft /
- sortie and departure /
- cross entropy-operations profile fitting (CE-PF) algorithm /
- scheduling /
- optimization

HTML全文

图 1 舰载机出动作业流程

Figure 1. Flowchart of departure and operation of carrier-based aircraft

下载: 全尺寸图片幻灯片

图 2 作业剖面示意图

Figure 2. Sketch map of operation profile

下载: 全尺寸图片幻灯片

图 3 基于CE-PF算法求解离场调度的结构流程

Figure 3. Flowchart for solving departure scheduling based on CE-PF algorithm

下载: 全尺寸图片幻灯片

图 4 某型航母甲板概况

Figure 4. Overview of aircraft carrier deck

下载: 全尺寸图片幻灯片

图 5 8架飞机出动调度甘特图

Figure 5. Gantt chart of departure scheduling of 8 aircraft

下载: 全尺寸图片幻灯片

图 6 8架飞机的滑行路径

Figure 6. Taxiing trajectory of 8 aircraft

下载: 全尺寸图片幻灯片

图 7 12架飞机出动调度甘特图

Figure 7. Gantt chart of departure scheduling of 12 aircraft

下载: 全尺寸图片幻灯片

图 8 16架飞机出动调度甘特图

Figure 8. Gantt chart of departure scheduling of 16 aircraft

下载: 全尺寸图片幻灯片

图 9 50次仿真优化计算结果的散布值

Figure 9. Scatter of 50 simulation optimization results

下载: 全尺寸图片幻灯片

图 10 允许滑行交叠作业下不同出动规模的调度甘特图

Figure 10. Gantt chart of scheduling with different departure scales under taxiing overlap operation

下载: 全尺寸图片幻灯片

图 11 出动16架飞机时各起飞位调度甘特图

Figure 11. Gantt chart of take-off position scheduling for 16 aircraft

下载: 全尺寸图片幻灯片

图 12 弹射模式下16架飞机出动甘特图

Figure 12. Gantt chart of 16 aircraft in ejection mode

下载: 全尺寸图片幻灯片

表 1 仿真实验中出动飞机情况

Table 1. Departure aircraft in simulation

停机位	飞机编号
停机位	8架出动	12架出动	16架出动
A0
A1
A2		1	1
A3	1		2
A4		2	3
A5	2	3	4
A6		4	5
A7	3		6
A8		5	7
A9	4	6	8
A10	5	7	9
A11			10
A12	6	8	11
A13			12
B1	7	9	13
B2		10	14
B3	8	11	15
B4		12	16

下载: 导出CSV

表 2 空间约束变化对离场调度方案的影响

Table 2. Impact of spatial constraint changes on departure scheduling scheme

阻塞式(本文)		无阻塞情况			滑行作业交叠情况
出动规模/架	最优值/s	最优值/s	Gap值/s	gap相对值	最优值/s	减少量/s	提升率
8	372	349	23	0.07	320	52	0.14
12	538	481	57	0.12	429	109	0.20
16	691	622	69	0.11	537	154	0.22

下载: 导出CSV

表 3 不同出动规模下调度算法性能比较

Table 3. Performance comparison of scheduling algorithms under different departure scales

算法	出动规模/架	平均算法时间/s	出动完成时间/s
算法	出动规模/架	平均算法时间/s	Best	Avg.	Worst	Std.
	8	0.93	372	374.6	378	1.729
CE-PF	12	1.14	538	540.15	542	1.089
	16	1.28	691	695.9	701	3.28
	8	10.38	376	382.75	390	4.18
DL-GA	12	12.63	545	557.6	559	6.17
	16	16.82	695	714.4	736	14.6
	8	3.84	372	385.9	396	7.37
DE-CE	12	5.95	546	557.5	576	9.63
	16	8.28	697	716.8	730	9.68

下载: 导出CSV

参考文献(24)

[1]	屈也频, 金惠明, 何肇雄. 航母舰载机装备体系及指标论证方法[J]. 航空学报, 2018, 39(5): 108-119. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201805010.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201805010.htm
[2]	谢君, 廖松, 石章松. 航母作战部署中的舰载机出动规划模型[J]. 系统工程与电子技术, 2020, 42(1): 128-132. https://www.cnki.com.cn/Article/CJFDTOTAL-XTYD202001017.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-XTYD202001017.htm
[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. doi: 10.1016/j.cja.2020.06.020
[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. doi: 10.1016/j.ifacol.2016.07.810
[10]	郑茂, 黄胜, 王超. 优先网络排队的舰载机出动回收能力研究[J]. 北京理工大学学报, 2013, 33(10): 1051-1055. doi: 10.3969/j.issn.1001-0645.2013.10.011 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). doi: 10.3969/j.issn.1001-0645.2013.10.011
[11]	司维超, 韩维, 史玮韦. 基于PSO算法的舰载机舰面布放调度方法研究[J]. 航空学报, 2012, 33(11): 2048-2056. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201211013.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201211013.htm
[12]	苏析超, 韩维, 萧卫, 等. 基于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(in Chinese). doi: 10.3969/j.issn.1001-506X.2016.10.12
[13]	杨放青, 王超, 姜滨, 等. 舰载机出动回收调度策略生成方法[J]. 北京理工大学学报, 2018, 38(10): 1030-1036. https://www.cnki.com.cn/Article/CJFDTOTAL-BJLG201810007.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-BJLG201810007.htm
[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. doi: 10.1016/j.jairtraman.2019.101734
[15]	苏析超, 韩维, 张勇, 等. 考虑人机匹配模式的舰载机甲板机务勤务保障调度方法[J]. 航空学报, 2018, 39(12): 222314. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201812020.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201812020.htm
[16]	SU X C, HAN W, WU Y, et al. 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. doi: 10.1109/ACCESS.2018.2846769
[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. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201701004.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201701004.htm
[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. https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201607001.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC201607001.htm
[24]	张智, 林圣琳, 朱齐丹, 等. 考虑运动学约束的不规则目标遗传避碰规划算法[J]. 航空学报, 2015, 36(4): 1348-1358. https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201504035.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-HKXB201504035.htm