基于遗传算法的进离场流量动态分配方法研究*

张晋武

（中国人民解放军91977部队 北京 100036）

1 引言

近年来，我国经济由高速增长阶段转向高质量发展阶段，航空运输业持续快速增长，有限的飞行空域内流量压力逐渐增大。直到2020年受到新冠疫情的影响，国内外航空运输市场遭受打击，总周转量同比下降39.5%，其中中部地区2020年1月-12月中部地区民航货邮吞吐量达到137.18 万吨，仍保持10.0%的正增长［1］；主要航空公司共执行航班241.92万班次，而由于流量控制造成的航班延误比例达到11.21%，在造成经济损失的同时，也带来了一定的安全隐患。

在民航空中交通管制领域，科学合理的规划机场进离场流量分配［2］是众多国内外学者关注的研究方向，进离场流量动态分配作为流量管理的有效手段之一，通过研究进场与离场流量之间的相关性，在不超出机场容量最大限制的前提下，实现航班进离场需求的二次分配，从而促使机场容量与进离场流量间的协调均衡，提高机场资源利用率。

通过相关文献查阅，国外研究人员［3］对民用航空机场中的进离场容量曲线开展优化研究，采用数据统计常用的R 软件与分位回归理论相结合的方式模拟进离场容量变化曲线，基于此，为机场进离场流量调度分配提供解决方案。

国内学者何沛南［4］针对成都机场容量资源评估需要及流量分配中的问题，进行了机场容量与流量分配协同优化的供需平衡策略研究；杨尚文［5］等针对现有的民航机场容量仿真模拟模型中不确定性强、鲁棒性差的问题，进一步优化参数，降低不同仿真场景下延误等特情事件对进离场流量造成的扰动影响。

总结分析国内外现有的研究成果，针对民航机场进离场流量分配策略问题，仅仅考虑了进场流量与离场流量之间存在的相互影响关系，但并未将该相关性因子在模型中量化体现，对多仿真场景下的机场容量动态调配方法缺乏深入研究［6］，现行的流量分配策略难以达到相关管理部门对空中交通流量管制要求［7］。

2 流量动态分配模型研究

传统流量分配模型采用RBS 算法与Compression 算法相结合，对进场、离场时间切片完成相关数据清洗、数据预处理等步骤，实现进离场流量的队列排序［8］。但该传统算法模型并未考虑机场容量不同场景以及特情事件造成的不确定性因素，因此提出的动态流量分配策略并未达到最优。

为解决在机场容量不确定条件下，地面等待和空中等待之间的均衡性问题，本节通过构建流量动态分配模型，将不确定性用容量情景树模型［9］量化表示，计算以航班预计总延误成本为目标函数的最小解。

将目标场景中进离场流量对应的时间序列分割成τ个离散时间切片，并定义τ+1为单独的时间切片，在τ+1 时间切片中定义机场容量无限大，并用Γ 定义同类相等的离散时间切片总集合。

在流量动态分配模型中，定义机场因流量分配不适造成的最小延误成本为目标函数，其中延误成本由地面等待成本与空中等待成本两部分组成。

上式中：F定义为所研究的进离场时间段内该航班f集合，f∈F；Fd定义为在目标机场离场的该航班f集合；Fa定义为在目标机场进

场的该航班f集合；S定义为目标机场容量情景s集合，ps定义为机场容量情景s发生的概率，s∈S；定义为该航班f在地面等待单位时间的延误成本；定义为该航班f在空中等待单位时间的延误成本；df定义为该航班f的预计离场时间；af定义为航班f的计划进场时间。

决策变量如下所示：

约束条件为

本文中构建目标机场进离场流量动态分配模型计算不同时间段、不同情景下的最优抵达进场航班数量以及最优目标机场进离场流量动态分配策略，步骤依次如下所示。

步骤1：选择初始参数，预设初始时刻和阶段，即t=1、ξ=1。

步骤2：通过历史数据统计，将目标机场对各航班进离场需求和总容量信息以情景树形式筛选，选取运筹学理论算法将选择不同的分支变量和不确定性因素进行分支，求解不同时间切片内在第ξ阶段内的预计最优抵达目标机场的航班数量，同时预估对不同时间切片内在第ξ+1 阶段内累计抵达机场航班数量。

步骤3：通过决策分析中的情景树方法对不同航程班次以及目标机场进离场总容量的进行数据分析，计算在t 时间切片内的最优进离场流量动态分配策略，t=t+1。

步骤4：当计算过程中t=τ时，算法流程跳转至步骤6，否则流程转至步骤5。

步骤5：当目标机场进离场容量场景发生变化，定义ξ=ξ+1，并同步更新目标机场对各航班进离场需求和总容量情景树信息，流程跳转至步骤2；相反，各时间切片在t时间内，直至第ξ+1 阶段记录抵达目标机场航班数量保持不变，流程跳转至步骤3。

但流量动态分配模型需要耗费长时间来求解流量和容量匹配机制，实际运行决策中，更是涉及大规模的数据量，为保证模型求解的时效性，因此选用遗传算法进行优化。

3 基于遗传算法的模型优化

遗传算法［10］是基于自然群体遗传进化机制的启发式算法，通过模拟生物进化论中自然选择和自然遗传过程中的选择，交叉，突变的基因现象，提供了一种求解组合改进的基础泛用模型方法［11］。本文充分利用遗传算法GA在解决动态组合问题方面的优势［12］，调整流量动态分配模型中的决策变量，优化实际场景中进离场流量与机场容量间的匹配机制，根据已有的机场容量情景模型与进离场空域信息，计算航班进场与离场时间片的最优解，为机场管理提供动态分配方案。

3.1 初始编码

在机场进离场流量的动态随机调配决策方案中，定义决策变量为在不同机场容量场景下各航班的进离场时间序列，通过二进制编码方法对时间切片进行预处理。染色体单体集合定义为o(s,f,t)，染色体单体编码形式如图1所示。其中q定义为机场在情景s下的总容量，m为机场进离场网络需求中进场与离场的航班总数f，n为整个过程所需时间量总和。集合o(s,f,t)定义为当机场容量处于情景s条件下航班总数f在时间切片t内的进离场平衡状态。而当o(s,f,t)=1 时，则说明在机场容量情景s条件下，当前航班在时间切片t内进场或离场，当o(s,f,t)=0 时，则表示在机场容量情景s条件下，当前航班不在该时间切片t内进场或离场。在分配策略中o(s,f,t)的值由系统随机生成，同时满足机场容量曲线、容量情景、连续航班三个必要约束条件。

3.2 遗传算子

1）选择

根据适应度函数计算公式求解种群中各染色体单体的适应度值，利用最优适应度选择排序方法，将各染色单体按照适应度评估结果依次进行排序；通过比对预设的种群淘汰率，筛选适应度符合条件的染色单体，最后复制同比例适应度高的染色单体替换淘汰个体，以保证整个迭代过程中种群大小不变。

2）交叉

根据交叉率将父代染色体中的部分染色单体按照一定概率随机交换基因生成新的子染色体，本文采用单点交叉方法实现交叉操作。交叉过程示意图如图2所示，在规定时间切片t内，随机选择某一行位置进行交叉（如图中加粗黑线的位置所示），将交叉点前后的父染色体1上侧部分与父染色体2上侧部分o(s,f,t)进行交叉对调，生成两个新的子染色单体。

图2 交叉过程示意图

3）变异

变异操作是通过遗传算法中染色体单体交叉之后的子代个体，按照一定概率值不定性随机改变某单体的基因值。在不同机场进离场流量动态随机调配方案中，采用任意将其中两行进行交换的形式，从而生成新的子代个体，变异的过程示意图如图3所示。变异产生的新子代个体校正处理方式与交叉过程保持一致。

图3 变异过程示意图

整个变异过程是针对单体中的基因序列上的某个或某类基因值。定义单体变异概率pm=B/(M2·λ1)，上式中参数B是变异过程中每代发生变异的基因数，M2是每代中整个群体的单体数目，·λ1是参与变异过程中的单体基因串长度。

4 实例及分析

选取国内上海虹桥国际机场ZSSS 中八点整至十二点整时间段的目标机场进离场航班动态数据为实验数据，进行仿真验证。机场ZSSS 的航班需求初始值214架航班，包括进场飞机数量105架，离场飞机数量109架。

在开展仿真实验前，预设相关模型参数，设置种群初始数量为120，最大迭代数量为240，变异因素为0.1，交叉因子为0.9，淘汰率为0.2；目标机场周转时间每个时间片设置为15min。

通过多次的仿真模拟发现，214 架航班调度，遗传算法优化过程往往在120 代左右完成收敛过程，与传统分配模型相比，提高了整体收敛速率。如图4所示。

图4 遗传算法进化过程

经优化求解得到各容量场景下对给定机场流量变化网络的进离场流量调配改进组合方案，最小预计总延误成本为1260.9 个单位成本。从图5、图6 中可以看出分别为目标机场ZSSS 在九点整阴雨转晴容量场景1与十一点整阴雨转晴容量场景2下的进离场流量动态分配策略。

图5 容量场景1下进离场流量分配方案

为验证基于遗传算法的进离场流量动态分配方案的均衡性，将八点至十二点分成四组，通过比对分配方案进离场航班数与该情景下的机场容量曲线关系，如下图所示。可以看出在容量情景1 下的动态分配点均处于容量曲线区域内部。

图7 八点至九点进离场流量分配方案

图8 九点至十点进离场流量分配方案

5 结语

面向民航空中交通流量科学管制技术发展，本文通过研究进离场流量与机场容量的协调匹配机制，提出了一种基于遗传算法的进离场流量动态分配研究方法。

考虑不同情景下机场容量的不确定性，并以情景树模型进行量化，通过计算地面等待成本与空中等待成本的最小值。得到进离场流量动态分配的最优方案。通过上海虹桥机场的实例数据，验证了方法在不同机场容量情景下仍能保持较好的均衡性，同时也可为空管部门今后的最佳优化决策提供参考。