航空器救援调度模型与算法研究∗

胡汉莉 邓 威（武汉数字工程研究所武汉430205）

航空器救援调度模型与算法研究∗

胡汉莉 邓 威
（武汉数字工程研究所武汉430205）

论文介绍了低空空域下的航空器救援调度模型及该模型的两种求解算法，并以汶川地震为背景设计算例，比较分析了两种求解算法的结果。

航空器救援；遗传算法

Class Num ber V355

1 引言

航空器救援是指使用航空技术手段和技术装备实施的一种救援，本文特指重大灾害下的低空空域的航空应急救援，其特性有受灾范围广、人员多，在事故发生后需动用大批量、多类型航空器执行长短距离任务。

航空器救援具有很高的军事意义，战场上航空救援水平的高低对作战能力的影响是很大的。航空救援水平越高，部队战斗力会越强，人员伤亡数会越低。因此，提高航空救援的水平是很有必要的。

2 航空器救援调度模型

2.1 航空器救援调度问题描述

航空器救援调度问题可描述为：在一个供求关系框架下，有若干架航空器、若干个物资配送中心和受灾点，要求合理的安排航空器的飞行路线和出行时间，在满足多种约束条件下，将物资配送中心的物资运往受灾点，并使得相应的目标函数最优化。

航空器调度问题主要包括救援物资、航空器、配送中心、受灾点、运输网络、目标函数以及约束条件等要素。

1）救援物资：包含重量和体积、要求送达时间和受灾点、是否允许分批配送等属性。

2）航空器：其属性包括航空器类型、单次最大航程、最大装载量、配送前停靠位置以及完成配送任务后的停靠位置等。

3）配送中心或出救点：救援物资集散地以及航空器运作指挥的中心枢纽，在某次配送调度任务中可有单个或多个中心点。

4）受灾点：其属性包括物资需求量、需求时间、需求次数以及物资满足率等。

5）运输网络：由顶点（受灾点、配送中心）、无向边和有向弧构成。其中边和弧的属性包括方向、权值（可表示时间、成本或距离）和交通流量限制等。

6）约束条件：满足受灾点对物资类型、规格和数量的需求以及对到达时间的约束；航空器的实际装载量不得超过最大装载量；航空器单次配送路径长度不得超过最大航程；不得在配送中心外的其他地点停靠。

7）目标函数：各个受灾点的物资满足率最高、配送总里程最短、准时性最高、时间最短等。

2.2 航空器调度模型相关概念

假定以下条件：1）调度过程中航空器满载直飞，每个架次的救援过程只针对单个受灾点；2）出救点所能提供的调度物资总量、各需求点所需的物资总量在调度周期内保持不变；3）航空器可在任一可用出救点装载物资，在受灾点投放物资或者降落卸载；4）航空器油量可满足在任一次出救点-受灾点-出救点之间的调度飞行，只能在出救点加油；5）机组调度与物资调度相互独立，可不考虑。

表1 集合常量表

表2 物资常量表

表3 时间常量表

表4 二元变量表

航空器调度模型目标函数及约束条件：

这是一个非线性整数规划模型，目标函数式（1）为使得调度周期内航空器出程飞行架次达到最大化，从而提高单位时间内的物资调运量；目标函数式（2）为当出救架次达到饱和后，使得参与救援的航空器总的调度时间最短，从而降低出救成本。

约束条件式（3）~式（14）有3种，分别为物资约束，时间约束和航空器位置约束：式（3）保证耐久类物资在调度周期（k天）开始前k'天内完成调度，同时满足受灾点对快速消耗品的需求；式（4）确保消耗性物资在耐用品调度完成后的周期内，耐用品的总需求架次可以得到保障；式（5）确保调度周期内每天消耗品连续性需求得到满足；式（6）确保每天的实际调度时间在允许的调度时间之内；式（7）和式（8）确保总的出入程飞行架次相同，且航空器只有在上一次执行了入程飞行后，方可执行本次出程飞行；式（9）和式（10）确保航空器执行出程飞行的条件得到满足；式（11）和式（12）确保航空器执行调度任务后停靠在出救点的条件得到满足；式（13）确保每架航空器在执行完当天的调度任务后停靠在一个出救点；式（14）确保所有变量均是二元变量。

3 航空器调度模型的求解算法

该模型是一类广义上的运输工具的路径规划和调度问题，属于典型的NP难问题，精确求解方法的计算量会随着问题规模的扩大呈指数型增长。本文分别采用传统遗传算法和改进的爬山遗传算法对该模型求解，并对两者的性能进行了分析比较。

3.1 基于矩阵编码的遗传算法设计

基于矩阵编码的遗传算法如图1。矩阵编码将矩阵整体看作一个遗传子代个体，不需展开成单列或者单行，从而保存了子代个体基因的完整性。矩阵编码仅改变了遗传算法的编码方式，其核心思想和求解思路并未发生变化，依然沿袭传统算法中初始种群的生成、选择、解的评判和收敛性检测步骤。

1）种群初始化。本文采用浮点数矩阵编码，一个解矩阵代表一条染色体，行代表每架航空器该周期内的调度计划，列表示各时刻航空器所在的位置。具体表达形式如下：

k为调度周期，共有k天，f1，f2…，fn为航空器集合，d和c分别为出救点与受灾点集合。随机产生m条该类型的染色体以完成种群的初始化。

2）种群可行化。所谓解的可行化即将染色体的编码向量映射为满足全部约束限制的可行解的过程，如图2。可行化操作只需判定解的时间和物资约束即可。时间约束通过引入带有各点间时间常数的矩阵，求和后与每天的作业时限比较，若小于时限要求则转入下一步，若不满足则需将每天最后一次飞行的受灾点虚拟化，以消减时间使之符合要求。物资约束须将原解矩阵分解出一个子矩阵，并统计原矩阵和新生成的子矩阵中各受灾点的出现频率，若达到频次要求则可行化操作结束，若不满足则需产生新解以维持种群数量不变，并继续执行可行化操作，直到所有解均达到可行化为止。

3）解的个体评价及适应度函数评估。衡量和评价某个染色体好坏的准则即为适应度函数，函数值越大则该染色体的性能越优越，其对应的解更接近于最优解。在本文的航空器调度模型中，根据目标函数的特征，取两目标函数的加权和作为本算法的适应度函数，其表达形式为

根据不同的算例赋予加权系数不同的取值，在此w1与w2分别取1和5000。

4）选择与复制。在本问题的求解过程中，应用适应度函数计算出当前代中的适应度平均值，然后对该代种群中所有染色体按照适应度函数值由高到低进行排序，排在榜首的个体性能最为优越，将其直接复制进入下一代种群，而其他剩余个体则采用适应度比例方法，选择进入下一代，比例Pi为

5）染色体交叉和变异操作。复制操作不会产生新的个体，交叉操作可产生新的个体，即新的航空器调度方案。具体实施过程为：按照一定的比例随机选择若干条染色体进行交叉操作，即交换解矩阵中的行或列，同理，选取某条染色体中的随机位置点进行变异，计算后的解须进行可行化操作。

6）采用指定代数的终止条件。事先设置最大遗传代数N，达到N代算法终止，将最优染色体对应的航空器调度方案输出。

3.2 爬山遗传算法设计

基本遗传算法在局部搜索能力方面暴露出的不足是为人共知的。另外，利用基本遗传算法求解一些优化问题时还会陷入过早收敛现象或停滞现象，对最终的寻优效果和计算效率产生影响。为了克服基本遗传算法的不足，通常从三方面着手：引入高级操作策略（如倒位操作）；引入群体策略（如多种群遗传算法和群体规模可变遗传算法）；将基本遗传算法与其他搜索方法相结合（如爬山算法）。

航空器调度的爬山遗传算法充分利用启发式信息，从而有效地提高遗传算法的局部搜索能力，进一步改善其解的品质和收敛速度。该算法的特点是对每一代得到的最优个体实施多次爬山操作，然后以通过爬山操作得到的个体取代原个体。算法如下：

1）解的表示方法及初始化同基本遗传算法。仅对每一代得到的最优个体利用两交换法进行爬山操作，采用固定的爬山次数，并将操作后的个体取代原个体。

2）引入罚函数思想对约束条件进行处理，对不可行解引入惩罚权重，降低该解的遗传概率。解的评价函数如下：

其中Pw为惩罚权重，M为不可行解中不可行路径数，为零时为可行解。

3）选择交叉策略及终止条件不变，提高变异概率，以消减对最优值进行爬山操作引起的单峰效应，增加种群的多样性，跳出局部最优。

3.3 算例设计与结果分析

本文以汶川地震为背景设计算例，德阳、广汉是具备航空器起降条件的城市，绵阳和成都为出救城市，都江堰、彭州、雅安、江油和汶川县为受灾城市。在调度周期5天内对两类应急物资采用3架航空器进行调度，三个出救城市均有两种物资且存储量足够。航空器在调度周期前停靠在广汉市，每天最多允许调度架次为3次，每天的调度时间为630min，装卸载时间均为20min，加油时间为40min，αc取值为2，要求在调度周期前3天完成耐用品的调度。相应的出救点与受灾点间的飞行时间以及各个受灾点两类物资的需求分别见表5和表6。

表5 出救点到受灾点所需飞行时间（m in）

表6 受灾点物资需求表

针对本问题的特性，编码遗传算法中的各类参数取值如下：种群个数为20，遗传代数为100，交叉概率Pc取0.7，变异概率Pm取0.15。w1、w2则分别取为1和5000。改进爬山遗传算法参数设置为：变异概率Pm设为0.6，Pw取值为2。图3、图4和图5分别表表目标函数值以及适应度函数值变化轨迹。

由图3可知：基本遗传算法与改进遗传算法的出救架次目标函数值有较大差异，其中前者由于进行了解的可行化操作以及第一目标函数值在适应度函数中权重较大，其变化轨迹较为平缓且总体为非递减状态，而改进的遗传算法则未对解进行可行化操作使得最初阶段由于可行解较少，引入的非可行解大多由于缺少时间限制而使得出救架次值一定程度较高，随着解的可行化程度的提高，呈现出一个先减后增的过程。

由图4可知：传统的遗传算法适应度函数中对第二目标函数值即出救时间的优化更多体现在第一目标函数值一定的情况下，且随着第一目标函数值的增加呈现出总体上升而局部减小的趋势，这与实际情况的优化过程和目标函数值的设定权重一致。而改进的遗传算法在对时间优化上差异更为明显，这也是由于非可行解的原因引起。

由图5可见：无论是采用基本还是改进的遗传算法，两者的适应度函数值都是增加的，而改进的遗传算法比基本遗传算法的适应度值变化范围大，且收敛速度更快，但存在一定小范围的波动，前者是由于对每代种群的最优解进行了爬山操作造成，而后者则是由于较大的变异概率引起。但二者均可求得最优解，其对应总的调度较次为44架次，调度时间为5285min。

根据以上计算结果可知：通过将具备更强局部搜索能力的爬山算法与传统的遗传算法相结合，构造出的低空救援航空器调度问题的爬山遗传算法，能够很大程度上弥补传统遗传算法在求解该问题过程中局部搜索能力不强收敛性弱的缺陷，也能够使得爬山算法所表现出的全局搜索能力较弱的特点隐匿起来，从而得到了更为优化的计算结果，显示出更为强大的寻优能力。

4 结语

航空器调度算法实际上是一个典型的多目标规划问题，本文提出并设计了重大灾害条件下针对各个出救点与各个受灾点的航空器调度算法，该算法能够在n2的时间复杂度内求得问题的最优解。

［1］Lucia P，Eric M F，Antonio B.Conflict resolution prob⁃lems for air traffic management systems solved withmixed integer programming［J］.IEEE Transactions on Intelli⁃gent Transportation System，2002，3（1）：3-11.

［2］Todd A，Donovan.Concept for an Integrated National Sur⁃veillance and Data Communication Infrastructure［J］. IEEE.AC paper，2005，5：1-14.

［3］James W.Rogers.Term inal Area Surveillance System［C］//InternationalRadar Conference，1995，501-504.

［4］赵勇，徐道奇，费锦荣等.基于AHP的飞行安全评估模型的研究与实现［J］.微计算机信息，2009，25（3）：84-85.

［5］Kernighan B.W.and S.Lin.An efficient heuristic proce⁃dure for partitioning graphs［J］.The Bell System Techni⁃cal Journal，1997，49：291-307.

［6］杨尚文，戴福青.基于一种免疫遗传算法的自由非冲突解脱［J］.航空计算计算，2007，37（1）：41-43.

［7］戴玲，夏学知.多Agent技术在飞行冲突解脱中的应用［J］.舰船电子工程，2008，28（3）：62-64.

［8］程丽媛，韩松臣，刘星.采用内点约束的最优冲突解脱办法［J］.交通运输工程学报，2005，5（2）：80-84.

［9］简炜，张友兵，吴阳等.基于爬山法和遗传算法的联合搜索算法［J］.湖北汽车工业学院学报.2004，18（2）：47-49.

［10］韩云祥，陈亚青.飞行冲突解决机制研究［J］.桂林航天工业高等专科学校学报，2009（3）：29-35.

［11］蔡良伟，雍正飞.求解带约束函数优化的两级自适应遗传算法［J］.系统工程与电子技术，2000，22（2）：84-86.

［12］简炜，钱积新.约束优化问题的多参量遗传算法［J］.湖北汽车工业学院学报，2003，17（4）：24-26.

Research on Arithm etic of Aircraft Rescue Scheduling M odule

HU Han li DENGW ei
（Wuhan Digital Engineering Institute，Wuhan 430205）

This papermakes research on themodule and two kinds of arithmetic of low-altitude aircraft rescue scheduling，and takesWenchuan earthquake asan examp le to compare the two kindsofarithmetic。

aircraftrescue，inheritancearithmetic

V355

10.3969/j.issn.1672-9730.2017.05.022

2016年11月7日，

2016年12月22日

胡汉莉，女，硕士，工程师，研究方向：舰载指控系统研制。邓威，男，硕士，工程师，研究方向：舰载指控系统研制。