基于边际-人工蜂群算法的舰载机机群出动保障人员配置-调度联合优化方法

苏析超，伍恒，崔荣伟，张勇

（1.海军航空大学，烟台264001； 2.海军研究院，北京100191）

舰载机机群出动保障是全周期出动回收作业的关键阶段，作为衡量出动回收能力的核心指标，保障效率的发挥不仅与航母航空保障系统的指挥调度和协调控制水平密切相关［1］，同时受限于以保障人员为主体的各类保障资源的规模和能力［2］。相对于陆基机场，甲板空间狭小、安全态势复杂，传统的固定机组制人员利用率较低，人数需求随着机群规模增加而线性递增，无法满足舰载航空保障“减员增效”的要求；另外，当前国内外航母舰载机调度仍处在以人工经验为主的水平，在大规模机群保障条件下难以确保最优调度性能。因此，基于一体化联合保障模式和智能调度技术，开展面向出动任务的保障人员配置和资源分配调度联合优化，是高强度、快节奏作战训练条件下舰载机指挥管理信息化和智能化的迫切需求和发展趋势。

由于舰载机出动保障作业内涵开放性不足，约束限制多，研究难度大，当前国内外针对出动保障调度和人员配置的研究成果尚不充分。在出动保障调度方面，Ryan等［3］基于所开发的甲板作业规划决策系统（Deck operations Course of Action Planner，DCAP）［4］，对比了专家经验和基于整数线性规划的自动决策方法的优劣。文献［5］面向一站式保障调度问题，构建了舰载机舰面机务勤务保障的资源受限项目调度模型；文献［6］则借鉴柔性车间调度问题，对舰载机甲板作业进行建模优化分析。文献［7-8］以甲板空间约束为出发点，分别研究了考虑停机位空间约束的保障组调度和考虑调运/作业空间约束的舰载机作业调度。文献［9］基于分布式路径规划方法，解决了出动阶段的协同调度问题。文献［10］进一步考虑了作业时间的不确定性，构建了前摄式舰面保障调度优化模型。以上研究不断朝着约束的复杂化、模型的精细化和目标的多样化发展。

在舰载机保障人员配置优化方面，Ross［2］基于多主体（Multi-agent）仿真技术，研究了保障人员配置数量与舰载机出动效率的影响关系；文献［11］在多主体架构基础上，内嵌合同网协议，提出了面向舰载机故障维修的保障人员配置和任务分配模型。崔博［12］提出了舰载机保障人员技能分配优化方法，并采用递增遍历算法确定保障组人数。郭小威等［13］针对工时不确定下的航空弹药保障作业，以基于蒙特卡罗的PERT网络仿真为效能评估核心，外层以遗传算法为优化框架，对保障人员配置方案进行优化。针对资源配置的方法研究［14］在装备保障领域可以归纳为经验比例公式［15］、数学规划［16］、基于排队模型的优化方法［17］和基于蒙特卡罗仿真的优化方法［18］等；按照资源配置主体，又区分为人员设备等可更新资源和不可修备件等消耗性资源。其中，边际优化算法作为一种高效实用的方法，在备件配置优化领域得到了广泛应用［19］。

综上所述，现有研究主要存在2个方面不足：①舰载机出动保障调度优化和保障人员配置优化的研究相对独立，缺乏联合优化的机制；②当前调度模型的研究较少考虑资源转移过程，更没有细化至保障工位之间转移，难以实现精细化保障需求。据此，本文立足舰载机出动任务需求，在一体化联合保障模式下，构建舰载机机群出动保障的人员配置和调度的联合优化模型，并提出基于边际-人工蜂群（Artificial Bee Colony，ABC）算法的两层优化决策架构进行模型求解，以实现舰载机机群出动保障的人员配置和调度决策的集成，减少决策环节，进一步促进舰载航空保障的“减员增效”。

1 问题描述

舰载机机群出动保障人员配置与调度联合优化问题（Integrated Staffing and Scheduling Problem for Aircraft Sortie Support，ISSP-ASS）的目标是确定各专业保障人员数量及各类人员设备的分配计划保障时序，以满足出动时间的要求。与传统的固定机组制不同，一体化联合保障模式下各专业保障人员可在各架同机型舰载机之间转移保障，因此可最大程度地提升保障人员利用率。该模式主要应用于美军舰载机保障，对人员配置和管理调度提出了更高要求。在给定保障人员配置方案下，保障资源的调度则受限于出动保障流程约束、出动时限约束、保障人员约束、保障设备约束、工位空间约束和资源供给能力约束等条件。

传统任务规划模式下，保障人员配置和保障作业调度两者为先后序决策，即一般先根据保障任务量，基于经验进行人力资源的配置，或直接指派在位的所有员额，再根据人力资源进行保障方案的规划调度。然而保障人员的配置直接影响到调度性能，独立的分步决策可能导致调度方案无法满足指标要求。因此，需要将2项决策任务进行统筹考虑和建模。

图1 单机出动保障作业流程图Fig.1 Support operation flowchart for single-aircraft sortie

每一架飞机均有各自的入场时间Mi，表示第i架飞机调运至停机位pi，并系留完毕，这也是单机保障的最早可开始时刻。令Oij表示第i架飞机的第j道工序，该工序当且仅当其前序工序集Pij均保障完毕后方可开始作业，保障所需工时为dij，保障所属工位表示为Wij。假设机群出动保障满足“一站式”条件［5］，即各舰载机在任一停机位均可满足所有资源的保障，可原位保障所有工序。每项工序可能涉及至多4类资源需求：保障人员、保障设备、工位空间和供给类资源，其各自种类集合分别定义为Kp、Ke、Ks和Kw。

图2 保障人员和设备转移保障示意图Fig.2 Schematic diagram of support personnel and equipment transfer

2 ISSP-ASS模型

2.1 决策变量和优化目标建立

ISSP-ASS模型需优化生成舰载机机群出动保障人员的数量配置、各保障人员设备的工序分配及作业时序等具体保障方案，因此模型的决策变量定义为

对2个优化目标按照字典序进行排序，即优先确保保障人员数量最小化，其次优化人员负载均衡性，实际运算中可采用加权的形式进行组合。

2.2 数学模型建立

3 联合优化方法设计

针对第2节ISSP-ASS优化问题，最直接的求解思路是采用集成式优化方法，即将保障人员配置和保障作业调度作为一体化并列的决策对象，并同步开展迭代优化。该方法的优势在于：算法设计简单，只需采用一种优化算法对配置和调度进行统一的编码、解码和循环搜索迭代。然而，人员配置和作业调度2部分的决策变量存在一定递阶关联性，即最优调度方案取决于人员的配置。如果同步对2部分决策变量进行扰动搜索，一方面2部分决策变量组合的搜索空间浩大，难以收敛至较优解区域，寻优的鲁棒性难以保证；另一方面，搜索缺乏导向性，容易形成无效搜索，如针对局部最优解，如果对2部分决策变量同步进行扰动寻优，则可能完全破坏原解的结构，无法在当前人员配置下进一步局部优化调度方案。

为有效利用保障人员配置和调度方案的递阶关联关系，提升寻优的针对性和搜索效率，可采用两层决策机制进行求解。在两层规划模型中，上下层均包含完整的目标和约束模型，下层模型依据上层模型的优化参数来引导自身目标优化，上层则依赖下层的优化反馈来优化自身目标。应用至本文问题，构建两层决策模型的概念图如图3所示。

图3 求解ISSP-ASS的两层决策模型概念图Fig.3 Concept of bi-level decision model for ISSP-ASS

上层模型负责各专业保障人员的配置决策。对此，采用边际优化算法进行求解，该算法操作简单，搜索精度高，且最大优势在于迭代过程不丢失最优解，在求解资源配置这类问题相对一般启发式算法更具优势。下层模型负责舰载机机群出动保障调度优化，以缩短保障完工时间，本文设计了一类改进人工蜂群算法进行求解。在每一步迭代过程中，在上层将各类专业保障人员分别增加单位数量后，调用下层调度优化模型计算边际效益的增量，下层则根据所增加的保障人员配置，基于改进的人工蜂群算法求解最优调度方案，并将机群保障完工时间和保障人员负载方差和反馈至上层配置模型，由上层模型选取边际效益最优的人员增加方案，通过不断迭代直至满足机群完工时间的时限要求。基于边际-人工蜂群算法的舰载机机群出动保障人员配置-调度联合优化流程如图4所示。

图4 边际-人工蜂群算法流程Fig.4 Marginal-ABC algorithm flowchart

3.1 上层保障人员配置优化

保障人员的数量配置直接影响了机群保障完工时间，当保障人员数量较少时，保障完工时限约束（4）未必得到满足，因此上层决策的目标是在保证达到保障完工时限的要求前提下，优化目标函数（3），因此，上层保障人员配置优化模型可抽象为

式中：（Xp，Xe，Y）表示机群保障调度分配决策方案。

采用边际优化算法，可将该优化问题转化为：依据各专业保障人员数量的边际效益增量大小，选取专业类别进行逐项增加的方式，使得机群完工时间不断迭代压缩至完工期限内。因此，可将第g次迭代过程中第k（k∈Kp）类专业保障人员的边际效益增量定义为

在统一的调度优化算法和较高的优化鲁棒性条件下，机群保障调度完工时间是关于保障人员配置数量的递减函数，考虑到α为极小值，第二目标项对优化目标函数值的影响较小，因此可将目标函数近似看做凸函数，即满足边际优化需假设目标函数为凸的前提条件。

基于边际优化算法的上层保障人员配置优化基本步骤如下：

式中：第k（k∈Kp）类专业保障人员的初始配置数量与配置强度、所保障工序的工作量成正比，与出动保障时限成反比。其中保障人员配置强度R为变量，随着R增加，各专业保障人员数量按比例递增。由于保障调度的复杂性，式（17）所得初始保障人员配置的比例未必是最优比例，因此R的赋值不宜过大以免超出最优保障配置解。

3.2 下层保障调度配置优化

下层决策以上层保障人员配置作为输入，求解以机群出动保障完工时间和负载方差和最小化为目标的保障工序任务分配及保障时序方案。因此，下层保障调度优化模型可概括为

该问题可抽象为考虑转移时间的资源约束下多项目调度问题（Resource-Constrained Multi-Project Scheduling Problem with Transfer Times，RCMPSPTT）［20］。由于RCMPSPTT的NP-hard特性，精确算法难以求解其中大规模调度问题，而以人工蜂群［21］算法为代表的元启发式算法则可实现求解效率和求解精度之间的权衡，并在调度领域中得到了广泛应用。采用该算法求解本文调度问题的考虑在于：①算法控制参数少，易于操作；②采蜜蜂和观察蜂的搜索机制较好地实现全局和局部搜索的协调；③侦察蜂机制可有效避免陷入局部极值，更适用于ISSP-ASS这类多峰优化问题的求解。

经典的人工蜂群算法的搜索策略仅针对一维的局部搜索，搜索能力有限，对于大规模调度这类多维优化问题会出现收敛速度较慢的现象。对此，本文在基本人工蜂群算法架构之上，引入差分进化的交叉变异策略以提升蜂群的搜索效率，并将项目调度中的面向个体解的双向对齐局部搜索［22］转换为面向种群的双向对齐，进一步提升种群的优化性能。本文改进的双向人工蜂群算法流程如图4所示，具体执行步骤如下：

步骤1 接收上层决策中的舰载机机群出动保障任务、保障人员配置等资源状态及相关信息；设置蜜源数目NS，蜜源停留最大限制搜索次数NL，初始化随机生成NS个蜜源。

步骤2 执行基于左向调度的人工蜂群搜索，按以下子步骤进行：

步骤2.1 采蜜蜂按式（21）和式（22）搜索生成新的蜜源，基于左向调度求解其适应度，并贪婪选择较优蜜源。

步骤2.2 观察蜂根据蜜源花蜜量信息，基于轮盘赌概率选择一个蜜源，并按式（23）和式（22）搜索生成新的蜜源，同理基于左向调度求解其适应度，并贪婪选择较优蜜源。

步骤2.3 若蜜源停留次数超过NL，则放弃该蜜源，同时该处的采蜜蜂转变侦察蜂，随机搜索新蜜源。

步骤3 判断是否达到最大评价次数，若是，则终止迭代，并输出最优的舰载机机群出动保障的人员、设备分配方案和保障时序计划；若未达到迭代终止条件，则转入步骤4继续迭代优化。

步骤4 执行基于右向调度的人工蜂群搜索，具体搜索子步骤与步骤2相同，其中差别在于生成的新蜜源采用右向调度进行适应度的评价。转入步骤2继续迭代优化。

步骤5 判断最优解对应的调度方式，若为右向调度，则保持资源分配固定，对右向调度解左移生成左向最优调度方案。

3.2.1 蜜源编码形式

种群中每个蜜源个体对应一个调度解，一方面为了利用人工蜂群算法求解连续优化问题的优势，另一方面为了实现编码与解空间的一对一映射，以精简搜索空间，同时是为了便于基于种群的双向对齐调度。本文设计了基于保障工序开始和结束时间向量的拓展优先序编码。

该编码为两层结构，第1行是保障工序开始时间向量，作为用于生成左向调度时的优先序列表，取值越小则调度优先级越高；第2行是保障工序结束时间向量，作为用于生成右向调度时的优先序列表，取值越大则调度优先级越高。在每次解码的调度方案生成后，将新的时序方案修正原编码。

3.2.2 解码调度过程

本节以左向调度为例，右向调度过程为左向调度的逆方向过程。采用串行调度生成机制，定义已完成调度工序集Sg，可调度工序集Dg，解码调度过程是从Dg中按工序优先级选取工序，并安排在满足各项约束的最早可开工时刻，分配人员、设备资源，并加入集合Sg这一循环迭代过程。将时间离散化，取间隔为Δt=0.1，解码调度具体执行步骤如下：

步骤6 为工序分配资源，从满足工位转移时序约束的保障人员集合中，选择负载Bkl最小所对应的保障人员；从满足工位转移时序约束的保障设备集合中，根据MTRCA规则［5］，选择覆盖范围内剩余工序作业时间最少的保障设备进行分配，更新所分配保障人员和设备的保障作业状态，令Sg=Sg∪（i*，j*），转入步骤2执行下一个工序调度。

步骤7 输出保障时序计划和保障人员、设备的工序分配方案，根据式（18）计算目标函数值。

基于解码调度结果，机群保障完工时间越短，保障人员负载方差和越小，则蜜源的花蜜量（适应度）越大，因此算法的花蜜量可表示为

3.2.3 蜜源位置更新策略

在进行蜜源位置更新时，分为左向调度阶段和右向调度阶段。在左向调度时，取各蜜源位置的保障工序开始时间向量构成的种群xL作为更新对象；反之在右向调度时，取保障工序结束时间向量构成的种群xR作为更新对象。以下以左向调度阶段为例，右向调度阶段的蜜源更新操作与之相同。

当蜜源停留次数达到限制NL后，则放弃该蜜源，并由侦察蜂随机产生一个新的蜜源，从而防止蜜源个体陷入局部极值，并增强种群多样性。

3.2.4 面向种群的双向对齐机制

面向种群的双向对齐机制将进化过程分为了左向调度阶段和右向调度阶段，2类调度机制可有助于彼此时序的微调优化以进一步压缩工期。通过引入该机制，使得算法在2个方面得到改进：

1）经典的双向对齐技术针对个体调度方案进行，并将消耗更多额外的计算量，因此往往仅针对部分较优个体实施；而面向种群的双向对齐则将该机制融入到人工蜂群的进化过程，节省计算量的同时也将应用范围拓展到整个群体。

2）通过种群的交替双向迭代，可增强蜜源位置（基因）的多样性，有助于克服由于单一方向调度导致的早熟及陷入局部极值的问题。

4 算例仿真与分析

4.1 出动案例构建

表1中，各项保障工序对保障人员和设备的需求单位均为1。保障人员专业种类按特设、航电、军械和机械依次编号1～4；保障设备种类按加油站、电源站、充氧站、充氮站、液压站、挂弹设备和惯导对准装置依次编号1～7；工位空间仅列出存在限制的座舱空间，仅可容纳一人进行保障作业；供给性资源种类对应设备种类进行编号，且供给限制为［Lw1，Lw2，Lw3，Lw4，Lw5］=［5，8，2，4，6］。

表1 保障工序对保障资源需求Table 1 Support resource demand of support operations

4类作战任务对应的保障工序工时如表2所示。保障人员和保障设备在各机工位间转移时间规模较大，篇幅原因不在文中列出。

甲板上各类保障设备的可覆盖保障飞机集合如表3所示。表3中，1～5类保障设备均为固定设备站，除表3中所示，挂弹设备为移动保障设备，可覆盖全甲板保障，配置12组，惯导对准设备较充足，不会对保障造成约束，因此本文案例可忽略。

表2 各出动任务下保障工序工时Table 2 Support operation durations of different sortie missions

表3 保障设备与舰载机保障覆盖关系Table 3 Reachability r elation between carrier-based aircr aft and support equipments

经过多次实验对比择优，双向人工蜂群算法参数选取为：蜜源数目NS=30，蜜源停留最大限制搜索次数NL=15，迭代终止条件设置为调度最大评价次数6 000。为克服调度优化的随机性，对每个保障人员配置方案进行n次调度优化，并取其目标值均值作为输出，本文设置n=5。

4.2 运算结果分析

基于MATLAB 2017编程运算，可得基于边际-人工蜂群算法求解舰载机机群出动保障人员配置-调度联合优化的目标值收敛曲线如图5和图6所示。其中，机群出动保障完工时间呈现单调递减趋势，最终收敛至Cmax=53.5 min；而保障人员负载方差和则为波动趋势，最终输出结果为L=25.2。在外层迭代过程中，以机群出动保障完工时间作为第一优先目标，因此每次迭代所选择专业增加保障人员虽然能确保缩短保障完工时间，然而可能会对该专业保障均衡性带来不确定的影响，而随着人员数量的增加，该波动趋缓。

最终优化所得人员配置方案为［4，4，8，9］，迭代过程如图7所示。由于机械专业和军械专业的保障任务相对繁重，所需保障人员明显多于特设专业和航电专业的保障人员，这也与实际保障状况相吻合。

图5 机群出动保障完工时间随外层迭代次数收敛Fig.5 Convergence curve of aircraft fleet sortie support completion time with the increase of external iterations times

图6 保障人员负载方差和随外层迭代次数变化Fig.6 Variation trend of support personnel load variance sum with the increase of external iterations times

图7 保障人员配置迭代过程Fig.7 Iteration trends of support personnel configuration

相对于固定机组制的保障模式，一体化联合保障模式下对保障人员的需求明显减少，在固定机组制下一般配置各专业保障人员共8人，本文保障模式下可减少需求39人。此外，为确定本文所提出初始配置模型的鲁棒性，进一步选取特设专业的人数为2和3，分别在这2种配置强度下确定初始保障人员配置，通过边际-人工蜂群优化算法所得结果均与本次结果相同，最终配置方案均为［4，4，8，9］，因此该初始配置方法在一定范围内具备寻优的鲁棒性，且可显著减少迭代次数，提升优化效率。

图8 保障人员调度甘特图Fig.8 Gantt chart of support personnel scheduling

图9 保障设备调度甘特图Fig.9 Gantt chart of support equipment scheduling

4.3 算法分析

表4 算法对比结果Table 4 Comparison of different algorithms min

5 结束语

本文针对舰载机机群出动保障人员配置及调度联合优化问题，系统分析了保障过程的流程、资源工位转移和出动时限约束情况，构建了相应的数学模型；提出了基于边际-人工蜂群算法的两层优化决策架构，其中上层决策模型基于边际优化算法对保障人员配置方案进行迭代改进，下层决策模型基于改进的双向人工蜂群算法，结合上层确定的人员配置方案，对舰载机机群出动保障任务进行调度优化。针对上层保障人员配置，提出了基于人员配置强度的初始配置方法以缩短迭代次数；针对下层调度优化，引入差分进化的交叉变异策略及面向种群的双向对齐机制。典型出动保障案例仿真结果表明，所提出的边际-人工蜂群两层优化算法可有效解决舰载机机群出动保障人员配置及调度联合优化问题，且无论是上层的保障人员初始配置方法，还是下层的保障调度优化算法，针对优化结果均具有较强的鲁棒性，所生成的保障资源分配方案和时序方案可满足模型的各项约束，为甲板保障作业资源配置和调度提供一套新的联合决策方法，对提升舰载机机群甲板作业的保障效率和资源利用率，促进航空保障“减员增效”均具有一定理论指导意义和工程应用价值。结合甲板作业的不确定性，拓展保障资源的决策优化范围，开展不确定环境下舰载机保障的前摄-反应式资源配置及动态调度研究是下一步的研究方向。