﻿ 一种航母甲板作业快速调度算法
 舰船科学技术  2019, Vol. 41 Issue (10): 180-184 PDF

1. 海军航空大学，山东 烟台 265200;
2. 海军航空大学 青岛校区，山东 青岛 266041

A fast scheduling algorithm for aircraft carrier deck operation
ZHU Xing-dong1, FAN Jia-li2, WANG Zheng2, ZHAO Hong-qiang2
1. China Naval Aviation University, Yantai 265200, China;
2. Qingdao Branch of China Naval Aviation University, Qingdao 266041, China
Abstract: For aircraft carrier flight deck during operation, the challenges for time、uncertainty and dynamic were very high. In order to support handling supervisory staff making operation plan, the mathematical model for deck operation optimization scheduling was established. To solve this combination optimizing problem, a fast improved Tabu search algorithm was proposed. Some heuristic rules were used to create initial solution in the tabu search. In order to escape local minimum, a variable neighborhood method was employed for perturbation strategy. Simulation results show the effectiveness of the proposed algorithm, and with some merit of convergence speed fast and more optimal solution comparing to usual Tabu and SA algorithm.
Key words: carrier deck operation scheduling     iterative neighborhood search     heuristic rules     tabu search
0 引　言

1 舰载机再次出动保障任务调度模型 1.1 舰载机甲板作业描述

 图 1 舰载机再次出动准备作业时序 Fig. 1 The sequence diagram of carrier aircraft turnaround operations

1.2 舰载机甲板作业调度的数学模型

 $F = \min {C_{\max }}{\text{，}}$ (1)

 $\sum\limits_{k = 1}^K {{y_{i{j_i}k}}} = 1,\ \ \forall i {\text{和}}{j_i} \in {V_i} \cap \left( {{V_{nr}} \cup {V_{ra}}} \right){\text{，}}$ (2)
 $\sum\limits_{{j_i} \in {E_{{j_i}}}} {\sum\limits_{k = 1}^K {{y_{i{j_i}k}} = 1} } ,\ \ \forall i{\text{和}}{j_i} \in {V_i} \cap {V_{rs}}{\text{，}}$ (3)
 $\sum\limits_{s = k}^K {{y_{i{m_i}s}}} + \sum\limits_{s = 1}^{k + {d_{{m_i}{n_i}}} - 1} {{y_{i{n_i}s}}} \leqslant 1,\\ \ \ \ \ \ \ \ \ \forall i,j{\text{和}}\left( {{m_i},{n_i}} \right) \in {A_i}{\text{，}}$ (4)
 $\sum\limits_{i = 1}^I {{y_{ijk}}} \leqslant {N_{jk}},\ \ \forall k{\text{和}}j \in {V_{rs}} \cup {V_{ra}}{\text{，}}$ (5)
 $\sum\limits_{k = 1}^K {\left( {{y_{i{j_l}k}} + {y_{i{j_m}k}}} \right)} \leqslant 1,\ \ \forall i{\text{和}}\left( {{j_l},{j_m}} \right) \in {V_s}{\text{，}}$ (6)
 $\begin{array}{l} s{t_{i1{j_{zy}}}} \leqslant s{t_{i2{j_{zy}}}},\\ \ \ \ \ \ \ \ \ \ \forall Z{W_{i1,i2}} \in {H_s}, {X_{zwi1}} \geqslant {X_{zwi2}}\end{array} {\text{。}}$ (7)

2 求解算法

2.1 算法总体框架

2.2 基于启发式规则的初始解生成

1）对于挂弹、转运作业类受限保障资源，优先分配给甲板首区停机位上待保障的舰载机；

2）对于加油作业，按照区域，首先进入该区域停机位的舰载机优先接受加油服务；

3）对于转运作业，每一区域需要转运的舰载机，按照后进先出的顺序依次转运；

4）在满足相关约束条件的前提下，尽量避免长时间占用着舰跑道；

5）在甲板范围内，尽可能保持各类保障资源的负担均匀。

2.3 约束条件的处理

2.4 领域构造策略

3 算例仿真

 图 2 I-TB算法收敛曲线 Fig. 2 Convergence curve of I-TB algorithm

 图 3 8机再次出动准备调度时序图 Fig. 3 Turnaround operations scheduling diagram for 8 carrier aircrafts

4 结　语

 [1] 苏析超, 韩维, 等. 基于Memetic算法的舰载机舰面一站式保障调度[J]. 系统工程与电子技术, 2016, 38(38): 2303-2309. SU Xi-chao, HAN Wei, et al. Pit-stop support scheduling on deck of carrier plane based on Memetic algorithm[J]. Systems Engineering and Electronics, 2016, 38(38): 2303-2309. [2] 冯强, 等. 基于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. DOI:10.3321/j.issn:1000-6893.2009.11.017 [3] 魏昌全, 陈春良, 等. 基于任务的连续出动舰载机航空保障重调度研究[J]. 指挥控制与仿真, 2012, 34(3): 23-26, 34. WEI Chang-quan, CHEN Chun-liang, WANG Bao-ru. Rescheduling study of aircraft support of running launch aircraft on carrier based on mission[J], Command Control & Simulation 2012, 34(3): 23-26, 34. [4] 李耀宇, 朱一凡, 等. 基于逆向强化学习的舰载机甲板调度优化方案生成方法[J]. 国防科技大学学报, 2013, 35(4): 171-175. LI Yao-yu, ZHU Yi-fan, et al. Inverse reinforcement learning based optimal schedule generation approach for carrier aircraft on flight deck[J]. Journal on National University of Defense Technology, 2013, 35(4): 171-175. DOI:10.3969/j.issn.1001-2486.2013.04.030 [5] RYANA, et al. Designing an interactive local and global decision support system for aircraft carrier deck scheduling[C]// AIAA Infotech@Aerospace St. Louis, 2011. [6] 林骥鹏. 基于离散事件的舰载机出动架次计算方法研究[D]. 哈尔滨: 哈尔滨工程大学, 2011. 12. LIN Ji-peng. Research on aircraft sortie generation rate based on discrete event[D]. Harbin Engineering University master thesis, 2012. 12. [7] RAJARSHI. A queueing network based approach to distributed aircraft carrier deck scheduling[C]// AIAA Infotech@Aerospace St. Louis, 2011. [8] VERONIQUE Sels, JOSé Coelho, et al. Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem[J]. Computers & Operations Research, 2015(53): 107-117. [9] ZHOU Yang-ming, HAO Jin-kao. An iterated local search algorithm for the minimum differential dispersion problem[J]. Knowle dge-Base d Systems, 2017(125): 26-38. [10] 张超勇, 等. 基于进化禁忌算法的Job-Shop调度问题研究[J]. 华中科技大学学报, 2009, 37(8): 80-84. ZHANG Chao-yong, etal. Solving Job-Shop scheduling problem using genetic tabu algorithm[J]. Journal of Huazhong University of science and technology (Natural science edition), 2009, 37(8): 80-84. DOI:10.3321/j.issn:1671-4512.2009.08.022 [11] SLIM Belhaiza, et al. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows[J]. Computers & Operations Research, 2014(52): 269-281.