基于改进灰狼算法的通航运力匹配

杜贵和，汪 骏，凡丽明，周子林

(1. 国网通用航空有限公司，北京 102209；2. 中国民航大学电子信息与自动化学院，天津 300300)

1 引言

近年来社会用电量激增，国家电网系统面临巨大运行压力，客观、合理的通航电力巡检资源综合匹配与调度能够保障国家电网的安全、持续和平稳的运行。因此急需建立一套通航电力运力匹配系统，科学合理地统筹通航公司运力生产资源。

受限于国内通航公司较小的机队规模，目前国内通用航空领域在运力资源调度及分配方面研究成果较少。国外通航运力资源配置研究主要集中在带时间窗的航空器飞行时间分配和航空器路径维护以及机组排班管理等方面[1-3]。而在国内民航资源调度方面主要采用线性规划及智能算法开展相应研究，文献[4]建立了飞机排班问题的0-1整数模糊线性规划数学模型，但该模型解决多目标多机型调度问题能力不足。文献[5]针对多目标飞机排班问题，结合最优化理论将多目标模糊线性规划数学模型转化为一般的线性规划问题求解。非启发式算法方面，文献[6]提出了基于约束编程的动态列生成算法求解多机型排班模型，但样本数据较大时计算效率较低。启发式算法方面，文献[7]建立飞机排班一体化优化模型并采用具有自适应能力的单亲遗传算法求解，但容易陷入局部最优解。但文献中构建的模型与各类优化算法多基于国内民航公司实际运行情况，并不完全适用于本文所研究的通航领域，需要进行一定的改进。此外，从模型求解方法来看，目前主要采用线性规划法、动态列生成法及灰狼算法对所建模型进行求解，对于新型智能优化算法的研究稍显不足。而随着各学科的发展，有必要探寻更多新型有效的算法以丰富该类问题的求解途径。灰狼算法作为一种新型的群智能优化算法由Mirjalili[8-10]等人于2014年提出，相比传统智能算法需要调节的参数少，存在自适应调节的收敛因子[11-13]，能够在全局最优与局部最优之间获得较好平衡[14，15]。

相较于民用航空，通用航空产业起步较晚，信息化程度较低。由于机队规模较小，一般只有1-2架航空器，因此机组资源安排也相对简单。但是随着公司业务规模的增长及机队规模的增长，也将面临如何降低运营成本，提高生产效益的问题[16]。本文根据国内某通用航空有限公司实际运行情况，分析通航运力匹配系统现状的几个问题，依据通航公司运力资源系统运行流程，构建运力匹配模型，采用结合通航电力巡检特点的灰狼算法求解，最后收集实际运营数据进行仿真对比实验。

2 通航运力匹配模型构建

2.1 运力匹配系统运行流程及特点

在通航公司的生产任务分配过程中，首先对航空器运行状态、人员配置情况等运力信息进行运力评估，结合历史天气数据、周期性天气状况以及空管管制等外部制约因素，匹配年度巡检需求，并分解为季度、月度计划下达给各分区机组。各机组接到计划性任务后，根据现有的航空器适航状态、航检设备工作状态和人员倒休情况进行排班，分阶段完成给定的任务。整体运力匹配系统运行流程图如图1所示。

图1 运力匹配流程图

2.2 运力匹配系统的现状问题

通航公司目前通过人工排班，以机组与航空器相匹配的运力匹配方式来完成生产任务。在实际运营中，运力匹配系统会受到各种复杂的约束条件限制而产生效能低下的问题，总体上可以归结于以下几个方面：

1)生产任务飞行时长。

通航公司的各机型、同机型之间的单机日利用率参差不齐，单个生产任务所需飞行时间极差较大[17]。这说明公司航空器单机利用情况不均衡，同时也意味着航空器利用率有很大的提升空间。

2)巡线段任务重复度。

通航公司作业范围点多面广，由于受专业人员机型、作业天数、及航空器定检、排故等因素限制，公司实际运行过程中会出现任务与运力资源匹配不当的情况，单机组频繁往返基地执行不同任务，严重降低了机组的产能效率。在优化排班算法时需要考虑合理整合巡线段任务。

3)运力资源的快速响应能力。

随着近年来通航公司机队规模的扩大和专业保障人员、设备的激增，传统模式下由人工进行资源的调配和评估的工作方法对人员的专业素质和能力提出极高的要求，容错率极低，工作效率不高。

2.3 运力匹配系统建模

运力资源匹配数学模型的构建目标在于各区域分配到的机组数的确定，因此构建模型时需要综合考虑运力匹配特点与流程等因素的影响。

2.3.1 目标函数的建立

构建运力匹配系统模型本质上是考虑如何在各种约束条件下求得最优解的问题。该问题的求解目标在于使用最少运力资源完成给定任务量。目标函数如下

(1)

其中，As是系数矩阵，As的表达式为：

(2)

矩阵n维列向量分别代表机组n种作业类型任务人员配比，矩阵m维行向量分别代表机组m种工种人员配比。s代表不同区域，不同区域内运力资源分配方式不同，共有k个拟分配区域。

机组数自变量xs的表达式为：

(3)

向量中n个元素为区域s中n种作业类型的机组数。目标函数式(1)求和结果为各区域拟分配的运力资源结果总和，代表了使用最少运力完成生产任务的建模目标。

2.2.2 约束条件设定

求解目标函数主要有两个约束条件：机组人员配置所代表的强约束和任务总量所代表的弱约束。

机组成员的相对固定性，决定了最终求得的目标函数结果必须小于等于总运行作业人员的数量，是优先考虑的强约束，可列出强约束条件：

(4)

其中，Mi表示长度为m的列向量，代表通航公司m种职业人员总数。

强约束条件(4)不等式右端为通航公司各职业人员配置总数，不等式左端为拟分配的k个区域对应职业分配人数总和。

在满足生产作业的条件下，需要考虑该人员配比组合能否完成拟分配任务量，可列出弱约束条件：

(5)

其中，Ns表示长度为k的列向量，代表k个不同区域年度拟分配任务量；Bs为任务量系数矩阵，Bs的表达式为：

(6)

矩阵m维列向量代表不同区域内同一种作业类型平均年可完成里程数；矩阵k维行向量代表同一区域内m种作业类型平均年可完成里程数。

系数矩阵Bs与机组数自变量xs相乘之后，可得到由xs决定的k个不同区域可分配任务量总数。

弱约束条件(5)代表不同区域可分配任务量总数，需大于等于不同区域年度拟分配任务量。在满足强约束的条件下，弱约束条件求解过程中可能会出现无解或者解为负数的情况，即拟分配里程数总量大于可完成的年里程数，说明当前运力已无法满足实际生产任务，需要任务外包。

3 基于改进灰狼算法的运力匹配模型求解

在公司运营过程中，运力匹配系统的基本目标是在减少总运营航空器数量的同时，提升单个生产任务巡线时长，同时合并优化单个巡线段任务，减少任务重复度，达到提升单机日利用率和机组产能效率的目的。因此考虑到灰狼算法具有最优化问题求解能力的特点，适合求解本文所讨论的运力资源匹配性问题。但灰狼算法仍存在初始种群离散化程度高和后期收敛速度慢的问题。为改善这种现状，本文结合通航电力巡检特性，基于历史数据对初始种群生成方式和狼群搜索机制进行改进，提出一种适合求解通航运力匹配模型的改进灰狼算法。

3.1 基本流程

灰狼算法是以狼群狩猎行为的追踪、围猎和狩猎三个环节构建的优化算法。整个群体的适应度值自上而下分为首领狼(头狼)α、副首领狼β、普通狼δ以及底层狼ω。首领狼α的适应度值最高，负责指定狼群移动方向；β狼和δ狼适应度值依次降低，负责向α狼提供参考方向；ω狼适应度值最低，服从于α、β、δ狼，并为狼群提供稳定性。灰狼算法的基本思想是由α、β、δ狼定位猎物(最优解)，引导ω狼包围并进行狩猎(求解最优解)。

狼群包围猎物过程可表示为：

D=|C·Xp(t)-X(t)|

(7)

X(t+1)=Xp(t)-A·D

(8)

A=2a·r1-a

(9)

C=2r2

(10)

其中，D为灰狼个体与猎物的距离表达式；X(t+1)为灰狼位置更新表达式，t代表迭代次数，Xp(t)代表猎物(最优解)位置向量，X(t)代表灰狼个体位置向量，C、A为系数向量；a随着迭代次数由2线性减少至0，r1、r2为模在0至1间的随机数。

在狼群包围猎物后，通过计算适应度值最高的α、β、δ狼的位置来确定最优解的位置：

(11)

(12)

最后由α、β、δ狼共同确定狼群的位置为：

(13)

3.2 系数向量C的生成改进

在灰狼算法的早期阶段，如果出现系数向量C>1，则可能导致算法的勘测能力受到影响；而在算法的中后期，如果出现系数向量C<1，则可能导致算法出现过早收敛从而影响结果[20]。因此本文提出了一种新出的系数向量C的生成方式，使其能较大概率在算法早期保持小于1而在中后期保持大于1，以达到稳定灰狼算法的勘测能力，防止过早收敛。设定系数向量C的生成方式为

(14)

其中，tm为总迭代数，r3为[0，0.5]之间的一个随机数。

3.3 初始种群的生成改进

不同年份之间的生产任务差异较小，可以通过参考同期历史情况确定当年机组分配数量，利用历史数据改进灰狼算法初始种群，提升初始种群的整体适应度值，提升算法的收敛速度。

设定同区域历史分配及组数向量为：

(15)

得到以下初始种群改进方式：

(16)

(17)

(18)

(19)

(20)

其中，p1、p2、p3为介于0到1的原初始种群权值变量；an是均为正整数的调整参数。式(16)表示当初始种群与同期历史数据之间差的绝对值小于调整范围向量时，本次的运力资源分配过程可以借鉴同期历史数据，通过调整原初始种群优先权值，得到更符合当前运力资源分配情况的决策建议；否则表示本次的运力资源分配过程与同期历史数据相差较大，初始种群不作改进。

3.4 狼群搜索机制的改进

通航电力巡检有同区域间人员结果变化较小的特性，本文结合这一特性，对狼群搜索机制进行改进，建立“观察狼”参考机制，以解决灰狼算法后期收敛速度慢的问题：建立历史数据向量作为观察狼的坐标，狼群的狩猎方式改进为底层狼ω向α、β、δ狼与观察狼协同位置靠近，在历史数据的指导下增强算法收敛速度，式(11)、式(12)、和式(13)修改为：

(21)

(22)

(23)

所提出的改进灰狼算法将灰狼个体与猎物距离表达式扩列，引入以历史数据种群为基准的观察狼机制，狼群位置更新公式改进为由α、β、δ狼与观察狼位置加权求和所得。为不影响狼群前中期种群多样性并提高后期算法收敛速度，引入线性变化的加权因子控制四只头狼对于种群的影响能力，狩猎前期仍主要由α、β、δ狼定位猎物位置，在狩猎中期及后期观察狼引导狼群的比重逐渐上升，最终与α、β、δ狼共同定位目标，避免狼群前期受固定化的观察狼位置支配丧失种群多样性，也改善了灰狼算法后期狼群位置盲从头狼而导致的收敛过慢问题。

3.5 改进灰狼算法求解步骤

采用改进后的灰狼算法求解运力匹配模型的步骤如下：

步骤1：确定总迭代数tm，计算优先权值p1、p2、p3，调整范围向量γ、种群规模等参数的选择，同时引入历史数据；

步骤2：根据式(2)与式(3)编码规则由算法生成初始候选解群体，并根据式(14)对初始种群进行改进；

步骤3：根据目标函数式(1)以及约束条件式(4)、式(5)对当前种群中的个体适应度值进行计算，更新α、β、δ狼的个体位置，根据历史数据生成观察狼位置向量；

步骤4：根据式(21)、式(22)更新α、β、δ狼与观察狼的位置向量，根据式(23)引导狼群更新位置，更新参数α、A、C、G1、G2；

步骤5：如果狼群适应度值满足适应度值评价条件或达到最大迭代数，则算法达到预期目的并终止，转步骤6，不满足则转步骤3；

步骤6：算法结束，输出狼群群适应度值最高个体；

改进后的灰狼算法的整体求解模型流程图如图2所示。

图2 灰狼算法求解流程图

4 实例分析及评价

选取某通航公司历史运行数据和实际运行数据如表1、表2、表3。

表1 某通航公司人员配置信息

表2 各区域不同任务平均年可完成里数

表3 各区域历史人员配置

为验证本文所提出的算法的有效性，在相同实验环境条件下将改进灰狼算法与传统灰狼算法求解运力匹配模型结果进行对比，所得结果如表4。

选取某通航公司运控中心人员手工排班结果如表6，完成总任务量的前提下，人工排班所需机组总数为27个，计算时间为30min。

表4 改进灰狼算法实验最佳个体结果

表5 传统灰狼算法实验最佳个体结果

表6 人工资源调度结果

改进灰狼算法与传统灰狼算法实验结果以及人工排班数据对比结果如图3、图4、图5所示。

图3横坐标为不同区域，纵坐标为作业总里程数，图3将三种算法得到的作业总里程数作对比，可以看出三种运力资源的排班方式均可完成各区域给定总任务量。

图3 不同算法下的作业总里程数对比图

图4横坐标为不同算法结果，纵坐标为分配机组总数，图中将三种算法得到的机组数量分配总数作对比，可以看出改进灰狼算法实验结果相比传统灰狼算法下降27.2%，相比人工排班下降40.7%，节约运力资源效果显著。

图4 不同算法下的分配机组总数对比图

图5横坐标为不同区域，纵坐标为分配机组总数，将不同算法下，不同区域分配机组数量作对比，可以看出与传统灰狼算法以及人工排班实验结果相比，改进灰狼算法实验结果中各区域所需机组数量均为最少，运力资源分配效果最优。

图5 不同算法下不同区域分配机组数对比图

对不同算法计算时间作对比，可以看出采用灰狼算法相比人工排班能节约大量时间。采用改进灰狼算法相比传统灰狼算法节约2.03s，节约了27.4%的时间，提升工作效果显著。

结合实验结果及对比试验结果可以看出，改进灰狼算法求解模型的实验结果在完成给定任务量的条件下能节约更多运力资源，提高工作效率，达到预期目标。

5 结论

当前的社会条件决定着采用算法构建通航电力作业运力匹配系统是我国通航领域未来的一个重要研究方向，其理论意义和实用价值都值得深入探讨。本文基于实际生产情况以使用最少运力资源为目标构建了运力匹配系统模型，采用综合改进系数向量、初始种群、狼群搜索机制后的灰狼算法求解模型，实验结果表明使用改进后的灰狼算法求解通航运力资源匹配模型相比传统灰狼算法及人工排班方式能够节约较多运力资源和计算时间，具有一定实际应用价值。