基于GRASP算法的甲板航空保障作业流程优化

宋璟毓，萧 卫，贾建龙，赵振宇

（1.中国船舶工业系统工程研究院，北京100094；2.海丰通航科技有限公司，北京100070；3.92950部队，辽宁葫芦岛125100）

航母等大型载机水面舰艇区别于其他常规舰艇的一大显著特征在于，其所配置的广阔甲板可作为提供舰载机起飞、着舰以及各项保障作业的平台，从而拓展了母舰的三维立体作战能力。然而，由于甲板空间狭小，各型舰载机的甲板航空保障作业也面临着诸多挑战：一是安全风险较大，航空保障作业过程涉及的“油电气液”等安全风险源较陆地机场更为集中；二是参与保障的资源繁多，协同性较强。其中，较为突出的是保障人员和保障设备的协同保障组织管理难度较大；三是保障作业过程约束复杂。对此，须综合考虑甲板航空保障作业的特殊环境。基于模型驱动的方法设计面向效能的航空保障作业流程，可以实现机群安全、协调、高效地进行甲板出动回收作业，从而提升机群的出动架次率和作战能力。

美军航母经过几十年的实践经验，归纳总结了NATOPS标准化作业手册，提出了甲板航空保障流程的总体流程和作业规范，但该框架无法面向任务进行流程优化[1]。苏析超等[2]针对多机机务保障流程中保障组分配问题，提出了基于改进混合差分进化算法的调度方法；进一步针对一站式保障模式下多资源协同调度问题，设计了一类Memetic优化算法[3]。文献[4]针对甲板航空保障作业的串并行混合特性，构建了拓展柔性作业车间调度模型进行优化求解。文献[5]在以上基础上，考虑了单机机组模式、大机组模式和一体化联合保障模式等不同保障模式对调度管理的影响，并验证了一体化联合保障模式的优越性。Ryan等[6]建立了舰载机作业的混合整数线性规划模型，并将基于线性规划的方法和基于人工经验的调度规则进行了对比分析。Qi等[7]针对大规模调度中存在操作规程和经验知识表示难、复杂约束处理难且规划耗时等问题，提出了基于层次任务网络的甲板航空保障任务规划方法。此外，针对保障过程中的时间不确定性，文献[8-9]分别从随机不确定和区间不确定两类描述形式进行度量；而针对保障过程中的随机故障等较大扰动，文献[10-11]分别采用滚动时域规划和完全重规划的方法进行干扰管理。

在调度优化算法设计方面，相关研究成果涵盖了遗传算法[5]、差分进化算法[12-13]、Memetic算法[3]、粒子群算法[14]、禁忌搜索算法[15]、遗传和声混合算法[16]等。以上算法主要以基于种群的智能优化算法为主。该模式相对于面向单解的局部搜索算法，由于种群个体间的相互作用，难以在程序上实现并行运算，时效性较差，因而也限制了其在工程实践中的应用。

以上研究主要针对甲板航空保障调度问题开展，而航空保障作业优化具体包括工序路径的选择、资源的分配以及时序的规划3个层面，调度仅是流程优化中的一部分。本文基于单解的贪婪随机自适应搜索算法（Greedy Randomized Adaptive Search Procedure，GRASP），对甲板航空保障作业流程进行优化研究，为舰载机智能保障的工程实践提供理论和方法支撑。

1 甲板航空保障作业流程优化建模

甲板航空保障作业流程优化问题（Aviation Support Operation Processes Optimization on Deck，ASOPOD）可以描述为：给定Nf架待保障的舰载机，机群集合表示为I={1,2,…,Nf}，各舰载机按时刻Zi入场至指定停机位并开展保障作业，各舰载机i的保障工序集为Ji，对应机群的保障工序集为J，单机保障作业流程并非固定的网络流结构[5]，局部工序之间由于存在安全性或空间的限制而不能并行作业，且相互间的前后顺序未定，即定义Vi表示i机不能同步作业的工序对集合；其余工序则按照既定的保障工艺顺序进行作业，即定义i机j道工序Oij当且仅当其前序工序集Pij保障结束后方可开始，其工时为dij。各工序的保障还需相应的保障人员、保障设备和供给类资源，分别定义保障人员、保障设备和供给量资源类别集合为Kp、Ke和Kw。ASOPOD的目标即为在满足甲板航空保障作业的各项约束前提下，通过优化各工序的作业流程、时序计划和资源分配，使得机群高效快速地完成甲板保障作业任务，即最小化保障完工时间Cmax。

1）Sij为工序Oij的保障开始时间；

2）Eij为工序Oij的保障完成时间；

基于以上所述，建立ASOPOD的数学模型如下。

选取调度优化目标为最小化机群保障完工时间：

约束模型包括：

式（2）为入场保障时间约束，即飞机需入场系留后方可开展各项保障作业；式（3）为具有紧前紧后顺序约束的时序关系；式（4）为分配至相同保障资源的作业优先级关系，即占用相同人员或设备下，优先级高的工序先进行保障；式（5）为不可并行作业的工序时序约束；式（6）为保障设备对应保障工序的覆盖范围约束；式（7）为供给类资源的供给能力约束，即任意时刻可供保障的飞机数量有限；式（8）、（9）分别确保保障人员和设备的分配量与工序对资源需求量一致。

2 基于GRASP算法的流程优化方法

本文采用基于单解的GRASP算法对调度优化模型进行求解。该算法是一类多步启动的迭代优化算法，每一次迭代循环包括2个核心步骤：一是在构造阶段生成可行的初始解；二是在邻域搜索阶段对初始解进行局部扰动寻优，并采用贪婪选择保留最优解。

应用至本文问题中，采用工序列表编码形式，GRASP算法的迭代过程如表1所示。

表1 GRASP算法结构Tab.1 Structure of GRASP algorithm

算法包含一组精英集EliteSet，用于保留搜索过程所获得的相异的最优解集；在构造初始解阶段，一个新的解将从精英集中通过一定机制BuildActList（*）进行组合生成；其次，在邻域搜索阶段，通过搜索机制LocalSearch（*）进行邻域扰动并改进新解；最后，通过串行调度机制[3]将编码转换为具体的调度方案，如果新解的目标函数优于精英集中的最劣解，则用该解进行替换并更新精英集，假设精英解集的规模为Ne，并维持不变。

首先，在构造初始解阶段，构造过程如表2所示，从前至后依次选择工序构造完整的长度为No的工序列表。定义每个调度阶段的EligibleSet为满足紧前工序约束的可调度工序集合，精英解复制链长为nit，其选取范围为[nit_min，nit_max]。

表2 初始解构造阶段Tab.2 Stage of initial solution construction

在每一步选取工序过程中，当链长nit为0时，则由函数SelectSolution（*）选取一个参考对象reference用于指导工序的选择，其可以是某个优选规则或工序列表解，本算法中的优先规则选取完全随机规则random和基于后悔值偏好的随机采样RBRS。若reference为工序列表解，则随机选取复制链长nit按照EligibleSet在工序列表解中位置进行选取工序；否则，当reference为优选规则时，则根据对应规则从Eligible-Set中选取工序，最终输出完整的工序列表。

具体函数SelectSolution（*）的实现过程如表3所示，其中，pRandom、pRBRS分别为选中随机规则和RBRS规则的概率，通常取较小的数值，用于对所选择的精英解进行小范围的随机扰动，以增强搜索的多样性。

其次，在邻域搜索阶段，主要对所构造的解进行进一步地局部优化，为增强搜索的高效性，选择双向对齐（Double Justification，DJ）[17]进行局部调整，可保证更新解不劣于初始解。

具体执行过程如下：首先，根据初始解的工序列表按正向串行调度机制进行时序调度和资源分配[3]；其次，根据各工序的完工时间，按照越大越优先的规则，采用反向串行调度，按流程逆向从后向前排程；依此顺序，不断进行正向和逆向的交替调度，使得时间得到最大程度的压缩，直到正向调度方案没有提升，并输出最优改进解。

表3 参考对象选择函数Tab.3 Selection function for reference

3 机群保障流程优化案例仿真

舰载机的甲板航空保障项目一般包括充气、加油、通电检查、外观机务检查、弹药挂载、惯导对准等项目，具体的通用化单机航空保障作业流程如图1所示，共包含19道工序。其中，可变因素包括15号工序，其可位于3号工序前、16/17并行工序前或18号工序之后，且15、3、5、7和12号工序任意两者之间均不能同步作业，因而其作业顺序可变。1和19号工序分别为虚拟开始和虚拟结束工序，无实质内容。其余工序右侧的Kpk和Kek分别表示该工序对第k类保障人员和设备存在需求，且需求量均为1，供给类资源与保障设备存在一一对应关系，即第k类设备存在需求时对应需要第k类供给量资源的保障。

仿真案例：选择某典型航空保障任务A，需要出动12架舰载机并执行飞行前的航空保障作业。各飞机对应各项保障工序的作业工时以及各飞机的入场系留完成时间如表4所示，其中1和19号虚工序无工时意义。

甲板航空保障资源配置方面，考虑保障设备均为固定类资源站，各类站点对应舰载机的覆盖关系如表5所示。供给性资源可同时保障舰载机数量分别为[6，5，2，4，2]，4类保障人员配置数量分别为[5，5，8，10]。

图1 通用化的单机航空保障作业流程Fig.1 General support process flow chart of single aircraft

表4 航空保障作业工序工时Tab.4 Durations of aviation support operation

表5 保障设备对应舰载机覆盖关系Tab.5 Coverage relationship between equipment and aircraft

采用Matlab 2017对基于GRASP算法的甲板航空保障作业流程优化方法进行编程实现，其中GRASP算法的相关参数设置为：复制链长的下界和上界分别为nit_min=1，nit_max=30，规则选择概率pRandom=0.05，pRBRS=0.95。最大流程优化生成评价次数取NSmax=10 000。

为了进一步体现改进GRASP算法的性能，选取该类问题抽象得资源受限项目调度问题的改进粒子群算法IPSO[18]，多模态遗传算法MMGA[19]和混合分布估计算法HEDA[20]作为对比，其各自算法的参数设置参见文献[8]。分别在同等条件下，对各算法独立运行10次，所得计算结果如表6所示。

表6 算法对比结果Tab.6 Contrast results of algorithms

本文的GRASP算法在多次运算中均稳定收敛至最优值65，其寻优性能最佳，且算法鲁棒性最好。相比其他算法性能排序为：HEDA＞IPSO＞MMGA。其中，HEDA和IPSO算法均应用了双向对齐机制，寻优性能优于MMGA。GRASP算法在初始解构造阶段中就通过规则和精英解复制链长的机制有效地实现了开发和探索的融合，并进一步引入双向对齐机制，从而更有效地提升解的质量，具备更高的寻优性能，也更适用于求解甲板航空保障作业流程优化问题。

图2、3分别为由GRASP算法求解得到的最优保障流程下保障人员及设备工序分配和时序方案。

图2 保障人员工序分配及时序图Fig.2 Schedule and operation allocation of support personnel

图3 保障设备工序分配及时序图Fig.3 Schedule and operation allocation of support equipment

4 结论

甲板航空保障作业流程优化是关系到航母舰载机作战力和保障力生成与生长的核心枢纽，属于保障领域的一类特殊运筹优化问题。在分析甲板航空保障作业流程优化内涵的基础上，以保障作业完工时间最小化为优化目标，考虑了甲板作业过程中所涉及的各类约束情况，构建了甲板航空保障作业流程优化的数学模型，并设计了相适应的GRASP算法。通过典型保障任务的仿真案例分析，验证了GRASP算法在求解该类问题的全局搜索能力和鲁棒性，并通过甘特图的形式展示作业流程的具体执行计划，并可检验模型的有效性。下一步，可以考虑研究算法在动态不确定环境下并行高效调度决策中的应用，以提升动态调度的时效性。