基于多目标融合及改进遗传算法的终端区进场协同排序

向征， 袁博轩， 刘玥琳

(中国民用航空飞行学院空中交通管理学院， 广汉 618307)

随着国民经济水平的快速提高，民航业的发展速度越来越快。然而，空中交通的繁荣，交通流量的增长，让本不富足的空域容量更加雪上加霜，空中交通流量过大导致航空器安全性降低、运行效率下降、公司效益下降。因此，这不仅使航班运行的安全性降低，延误率增高，也给国内民航业带来了严重的经济损失。

为了缓解矛盾、降低延误、提高效率，针对航班的不同飞行阶段，业界在航路建设与利用、机场建设与利用等方面采取了多种手段努力解决问题。这些举措，对于提高航班运行效率产生了显著作用。但相比终端管制区域来说并不简单，终端区是一个航空器降落的必经之地也是流量较大航路较复杂的区域，所以为了能够提升航空器效率和空域使用率，终端区的规划就显得尤为重要。多机场终端区程序繁杂，线路复杂，运行效率低下，很容易造成航班延误。更为关键的是，终端区内各机场间有很强的关联性，某一机场的航班延误极易影响其他机场航班，直接降低空中交通运行效率并可能导致安全隐患。虽然终端区运行效率的重要性日渐凸显，但目前针对这类问题的方法研究还太过于缺乏。

国外在20世纪60年代末就对进场航班排序问题开始进行研究，到目前为止已经取得了丰硕的成果。早期Dear[1]提出先到先服务是低效的，采用全新的约束位置转换算法消除了以最小延迟为目标模型的一些不良特性，并得出该方法是实用，高效和极为灵活的，为后续的研究发展奠定的良好的基础。1978年，Psaraftis[2]针对飞机排序问题的3个方面提出了动态规划算法，考虑到了两个目标：如何尽快降落所有计划到达飞机，或者如何最小化乘客的总等待时间。1995年，Abela等[3]提出了一种在高密度航站区对飞机进行排序和调度的方法，并利用位置约束转移算法进行了检验，并对其有效性进行了测试，在先到先得的跑道策略中，特别是在高峰时段，潜在的容量得到提升。2013年，Awasthi等[4]对美国国家航天局所使用的顺序排序模型进行了全面的优化，在先前结果的基础上研究出了更为可靠的进场排序的模型。2017年，Hong等[5]主要针对管制员负荷的问题，通过蒙特卡洛分析法结合整数规划的思想对航空器进场排序进行了优化。2018年，Meriem等[6]在对空域交通线路的建模中提出了一种新的混合整数规划公式，其中将主要问题分解为3个子问题即航段和跑道上飞机进近和着陆的调度排序问题，最后利用CPLEX数学优化技术进行了求解，结果表明了该方法的有效性。2019年，Zhang等[7]受航空器着陆和单机调度问题相似之处的启发提出一种准则选择法通过最大总飞行时间和单航班的最大飞行时间为目标函数构建多目标模型，利用一组基准实例对所提出的模型和方法的性能进行了评估。2020年，Abdelaziz等[8]提出一种基于迭代局部搜索和模拟退火算法(simulated annealing algorithm，SAA)混合算法的航空器着陆问题的解决方法，主要是在目标时间范围内找到一个可行的飞机调度方案，利用两种算法的优势结合13个大型实例来对解决方案的有效性和广泛性进行了评估，结果表明迭代模拟退火算法比其他先进的方法表现得更好。

国内对进场航班排序方法的研究开始的比较晚，但也取得了丰硕的科研成果。1999年，荀海波等[9]对各类常见的基于时间的排序算法进行了分析对比，针对机场终端区航空器的进场次序提出了规划算法。2004年，张兆宁等[10]通过对流量中的战术管理进行分析后发现，动态管理航空器的起降是尤为关键的，于是在动态航空器起降管理的基础上加入了滑动窗口机制，结果表明该方法可行且有效。2010年，杨晶妹[11]提出滚动时域的策略来解决排序问题，结合时间提前量法建立了进场航空器排序的问题，利用遗传算法对该问题进行了优化计算求解。2015年，高伟等[12]利用模糊评判法和粗糙理论，建立了一套综合评定体系，利用该体系中的各项指标来对航空器进行相应的排序。2017年，张军峰等[13]为解决终端区现状问题，通过归一化的思想将终端区看作一个整体来进行思考，优先解决局部最优问题，最后利用模拟退火算法对其进行了求解，实验证明这种方式的求解有效地提高了终端区的运行效率。2019年，戴喜妹等[14]为深入研究解决多目标模型问题，利用帝国竞争算法对航空器进场排序与调度进行了优化。同年，黄吉波[15]针对管制员指挥过程中的可执行性建立了基于延误分配的多机场航班排序模型，并利用相应的算法进行了求解。2020年，张兆宁等[16]针对机场跑道实际情况以及可供起降飞机的类型进行分析，并整理出各项因素对航空器排序以及延误航班的影响，为后续解决约束相关性打下了良好的基础。2021年，夏正洪等[17]对比传统雷达管制与程序管制特点与有效性利用雷达模拟机对航空器排序进行了研究与分析。

随着空中交通流量以及需求的不断增长，对空域容量以及流量的研究重点要从单一跑道逐渐向多跑道、单一机场逐渐向多机场这样大型的交通流量区域过渡。求解算法上也要不断地创新，目前包括利用滑动窗口算法增加局部搜索最优、解决多目标的非支配排序遗传算法Ⅱ(non-dominated sorting genetic algorithm Ⅱ，NSGA-Ⅱ)和带有精英改进遗传算法等[18]。较之前相比效率大幅度提高，但还有如下许多不足之处。

(1)大部分的研究都是对单一机场、单一跑道进行考虑，没有充分考虑到多方面的耦合关系，比如机场与机场之间，机场与航空公司之间，多跑道与单跑道之间的关系[19]。

(2)优化目标过于单一，大多数是以最小延误时间为目标进行优化，忽略了多目标的情况，比如跑道容量最大，顾客满意度最高，公共资源公平使用率最高[20]。

(3)进场排序考虑的方面太少，针对天气因素、地形因素、跑道因素以及相关机场之间的构型问题分配问题、管制员的指挥方式问题考虑地欠缺。

现针对当今航空事业的发展现状，大型机场以及大型机场群的现实需求，以终端区内部范围为界限，航空器在终端区内运行情况为对象，研究多机场终端区进场航空器协同排序的问题。通过分析终端区的空域结构和运行特征，综合考虑多方的公平以及利益需求，为航空器分配最优的进场顺序，以适应和缓解日益剧增的空域流量。

1 多机场系统定义及运行主要问题与空域结构的分析

1.1 多机场系统定义及运行主要问题

研究对象为多机场终端区，首先要对终端区给予明确定义。根据《中华人民共和国飞行基本规则》中《民用航空使用空域办法》有关规定，终端区即终端管制区，指的是在单个机场下或机场较多航路航线较多的范围附近建立的管制汇合区称作终端进近管制区，需要区分的是在单个机场的条件下称为进近管制区，多个机场的条件下称为终端管制区，且这些机场的进离场航班运行具有极强相关性的系统，如表1所示。

表1 多机场系统运行相关因素

根据多机场系统定义及对多机场系统运行相关因素的分析表明：多机场系统运行中最突出的问题是多个机场共同竞争使用同一受限的资源。通过对国内相关研究文献分析总结，提炼出多机场系统中运行相关性问题，通过对运行主要问题的分析不难看出，多机场运行矛盾主要集中在空域资源的使用上，多机场系统运行相关性在空域交互方面表现为如下5种形式，如表2所示。

表2 多机场系统空域交互分类

1.2 空域结构的分析

终端区是多机场管制区一个最为关键的部分，航空器的起飞和降落、飞行姿态的转变、速度的提升和降低等都是在终端管制区内完成的。因此终端管制区的划设合理性至关重要。

终端区内的结构比较复杂，分析其结构就要从以下几个元素着手：终端区进场离场走廊口点、进场离场航线、起始进近点和航线、中间进近进近点和航线、最后进近进近点和航线、复飞点和航线、复飞区和等待区。典型终端区空域结构如图1所示。

IAF(initial approach fix)为起始进近定位点；IF(intermediate fix)为中间定位点；FAF(final approach fix)为最后进近定位点；红色曲线分别表示A、B两机场航空器的进场航线，蓝色曲线分别表示A、B两机场航空器的离场航线

多机场终端区空域结构图如图2所示，整个圆柱体表示机场周围的管制空域，交叉点表示进场航路与离场航路的交叉点。

图2 多机场终端区空域结构图

协同排序的主要因素是“协同”两字，主要涉及多目标之间的协同，主要包含机场与机场之间的相关性，各个机场之间多跑道的相关性，降落在各个机场各个跑道航空器之间的相关性。当前中国的空域结构较为复杂，多机场终端区协同主要有以下特点。

(1)航路航线复杂管制效率低。航空器从航线进入终端区前就要进行管制移交，在这一系列的过程中航空器要经过平飞、下降、降速等过程，都要通过管制员的指令来完成，航空器根据这些指令进行飞机的安全飞行，在繁忙的终端区中进离场航线交错，进离场航班较多这就会造成管制员指挥不过来的现象，管制的效率会大大降低，稍有不慎会造成严重的后果。

(2)多机场以及空域构型复杂。多机场终端区中航空器进入终端区后会飞往各自不同的机场，机场的程序、跑道、运行方式各有不同，各航空器需要满足各机场不同的条件，加上空域结构复杂航线也时常交错，进入终端区后限制区和危险区时常存在使得空域环境更为复杂，更加不利于对航空器进行管理。

(3)各场场面容量存在差异导致空域资源分配不均。航空器进入终端区后会按照顺序飞往不同的目的地机场，大流量机场和小流量机场航空器的起降次数肯定会存在明显的差异。按照实际情况来说，会安排大流量机场的飞机优先排序，导致小流量机场的飞机处于等待状态。这种方式存在很强的不合理性，也会导致空域资源的不公平分配，提高航班延误率。

(4)地面保障系统复杂。由上述可知，在多机场终端区中会存在着不同等级的机场，各机场的地面保障系统也会存在差异。如航空器飞行中在相同条件下雷达管制间隔一定比目视飞行间隔要小，这样也更能提高航空器的效率，如果某机场的雷达服务设备故障，航空器就会从雷达间隔转为目视飞行间隔，增加了航空器之间的间隔，因此也会降低航空器的运行效率。

2 多机场终端区进场航空器协同排序模型建立

2.1 进场航空器协同排序模型参数介绍

建立多机场终端区进场航空器协同排序模型，需给出一些符号定义和参数变量，如表3所示。

表3 参数变量和符号定义

为建立模型还需定义3个决策变量，变量表达式如下。

(1)

式(1)中：Xi,j为航空器进入走廊口定位点，并且按预定进近航路飞行，当该变量为1时表明航空器i进入进近航道j，反之为0。

(2)

式(2)中：Yi,j为航空器进入入场定位点，并且按预定航线进入所对应的入场定位点，当该变量为1时表明航空器i进入入场定位点j，反之为0。

(3)

式(3)中：Zi,j为航空器按计划航路飞行到跑到口后，按飞机预计跑道降落，当该变量为1时表明航空器i进入跑道入口点j，反之为0。

2.2 进场航空器协同排序模型目标函数

在求解多目标的基础上对模型进行建立，根据对多机场系统运行主要问题和空域结构的分析，将从3个方面来建立目标函数。

从机场方面，应尽量减小所有航班延误时间损失，表达式为

(4)

从管制员负荷方面，应尽量减小管制员负荷，预计到达时间最大差值在20%，表达式为

(5)

从资源平衡方面，应尽量减小各机场之间的平均延误时间，表达式为

(6)

2.3 进场航空器协同排序模型约束条件

航空器只能降落在飞行计划中对应的一个机场，即

(7)

式(7)为1时，航空器i的目的机场为j，反之为0，可以确保式(7)的变量针对的是多机场。

航空器在进入终端区走廊口点后，进近航路是固定的，航路的终点只对应一个，最后进近定位点也只能对应一个机场，即

(8)

式(8)为1时，航空器i通过进近航路的目的机场为j，反之为0。

航空器在进入终端区走廊口点后，进近航路是固定的，进近航路只能对应一个入场定位点与一个跑道入口点，即

(9)

式(9)为1时，进近航路i服务入场定位点j与跑道入口点z，反之为0。

民航对尾流间隔有明确的定义，不同的尾流间隔会产生不同的进场次序与时间，为确保时间利用率最高，航空器的类型只属于一种，即

(10)

航空器在进入终端区走廊口点后，进近航路是固定的，航空器只能选择符合要求的航路，不同型号降落器跑道限制约束，即

(11)

航空器i的延误时间可以用航空器i结束滑跑的时间减去航空器i预计着陆的时间来计算，即

∀i∈F, Tfi=|Tdi-TCi|

(12)

绝对值的意义在于行业的特殊性，航空器提前到不一定会提高效率以及降低管制负荷，也有可能会增加管制负荷。

航空器i实际到达的时间，相当于结束滑跑的时间可以使用航空器进入终端区走廊口点之后的计划飞行路线时间加上航空器通过最后进近定位点到跑道头的时间加上滑跑时间来计算，即

∀i∈F, Tdi=Tni+TRi+TMi

(13)

航空器是否延误，延误的严重性是通过针对实际到达时间以及预计到达时间之差来做比较得到的，即

∀i∈F,Ki=|Tsi-THi|>To

(14)

为确保使得终端区内所有管制机场的平均延误时间最低，换句话说总体延误时间最低，空间利用率最大，用飞机场航空器平均延误时间来表示，即

(15)

为确保每个连续降落的航空器在同一航路有足够的尾流间隔，通过转换前后两架航空器进入进近航道的时间之差来表示，即

∀i∈F,j∈F,i≠j,

(16)

进场定位点尾随间隔以及管制移交间隔为

∀i∈F,j∈F,i≠j,

(17)

相同跑道入口点行驶间隔为

∀i∈F,j∈F,i≠j,

(18)

降落器进场时间约束为

∀i∈F, TAi≤Tni≤TBi

(19)

为了搜索能力更佳，更好地对该位置进行局部搜索，所以添加了滑动窗口的概念以及位置互换约束，即

(20)

3 算例仿真

3.1 算法过程

以成都终端区为例，将收集到的成都双流国际机场与天成都天府国际机场某时间段的航班时刻表代入多排序模型中，采用结合模拟退火的NSGA-Ⅱ算法对数据进行仿真，对得出的结果进行分析和对比。

NSGA-Ⅱ算法能够高效地遍历整个空间内的种群，有很强的全局搜索能力，但是针对航空器排序运用了时间窗口约束，该算法在局部搜索的能力较弱。模拟退火算法相比于遗传算法有很强的局部搜索能力，但是要求解一个需要全局搜索的最优解，该算法的效率较低，过程较为复杂，因此在NSGA-Ⅱ算法的框架下引入模拟退火算法，利用两种算法的优势相结合来对进场航空器排序模型进行求解。算法过程如下。

步骤1根据航空器及航空器选择的航道以及跑道随机产生染色体，并生成父代的染色体群nC。

步骤2按照所建立的约束条件和父代筛选情况，过滤掉不符合各项约束条件的个体，将剩下的个体重新组成新的种群nC1。

步骤3将新生成种群nC1中的值代入多机场终端区排序模型中，计算出所对应的延误时间、管制员负荷以及资源公平度，对其进行快速非支配排序后形成新种群nC2。

步骤4利用锦标赛法对新生成种群nC2该种群进行选择、交叉、变异等操作，将生成的新种群与初始种群nC1进行合并，再次进行快速非支配排序生成新种群nC3，然后通过精英策略对该种群继续进行筛选得到新种群nC4。

步骤5如果迭代次数到达上限，则将得到的解取出作为模拟退火算法的初始解；如果迭代次数没有达到上限，则继续按步骤3继续迭代。

步骤6将NSGA-Ⅱ算法中最终的解取出作为初始值代入模拟退火算法的步骤1中进行计算。

步骤7在初始温度下利用蒙特卡洛过程对初始值进行扰动选择抽样，形成新的解集。

步骤8模拟退火算法随着迭代次数的增加温度逐渐降低，当温度或迭代次数降到最低时，将模拟退火算法产生的解集与NSGA-Ⅱ算法产生的种群进行合并，如果没有继续迭代循环。

步骤9将模拟退火算法产生的解集与NSGA-Ⅱ算法产生后的种群进行合并，形成新的种群nC5返回步骤3继续搜索计算。

步骤10重复以上循环，将NSGA-Ⅱ算法的解集与模拟退火算法产生的解集一次次的合并对比，直到整个大循环结束。

改进的NSGA-Ⅱ算法流程图如图3所示。

图3 改进NSGA-Ⅱ算法流程图

3.2 基于成都终端区排序算例

成都终端管制区主要由成都双流国际机场和成都天府国际国际机场构成，该终端区内一共有5个进离场走廊口点，由图4可知，顺时针顺序分别为AKDIK、EKOKA、IGNAK、CZH和CDX。在该终端区内有多条进离场航线交错，空域结构极其复杂。

图4 成都终端区结构图

通过对该终端区航班时刻表的收集，在14：00—16：00区间内，共有30架次航班进入该终端区，航班信息如表4所示。

表4 航班信息

经过对成都终端区14:00—16:00时间段30架航空器数据的分析，再利用NSGA-Ⅱ和NSGA-Ⅱ加模拟退火算法代入所建立的模型中得出优化后的延误时间目标图、管制员负荷目标图以及不同机场延误平滑指数图，可以明显地看出，对于NSGA-Ⅱ和NSGA-Ⅱ加模拟退火算法，随着迭代次数不断地增加，三组目标函数得到的解集有明显的提高。如图5～图7所示。

图5 延误时间优化图

图6 管制员负荷优化图

图7 不同机场延误平滑指数优化图

根据熵权法，综合3个目标函数的影响，将3个目标函数最优解按照优先比例进行权重分配，得到最终的三维最优解集，根据pareto所有解集中最前沿的解集得到一档最优权重解集作为综合最优解集，如图8所示。

图8 三目标综合影响分析优化图

针对30架航空器利用结合模拟退火的NSGA-Ⅱ算法进行求解，由表5可知，利用结合模拟退火的NSGA-Ⅱ算法后航空器总延误时间为5 690 s，较利用先到先服务调度算法求解出来的时间提高了55.2%，较利用NSGA-Ⅱ算法求解出来的时间提高了28.1%。

表5 结合模拟退火的NSGA-Ⅱ算法下进场航班数据

可以看到利用了结合模拟退火的NSGA-Ⅱ算法后整个系统又在原先的基础上更加优化了一些，因为加入了模拟退火算法的机制结合滑动窗口后，更容易进行局部搜索使得数据更加的精准。显然利用全局搜索能力较强的NSGA-Ⅱ算法和局部搜索能力较强的模拟退火算法能够使航空器排序效率更有效的提升。

4 结论与展望

(1)结合实际机场终端区需求，从终端区定义范围、空域结构、运行特征以及终端区运行的影响因素等多维度综合分析了多机场终端区流量会趋于饱和的原因，提出能够提高终端区运行效率的措施，可为空中交通管理人员提供科学的管制方法。

(2)根据对终端区的分析建立了时间资源模型和空间资源模型，分析了终端区内主要的几个关键流量点以及关键时间点。依据航空器进近方式以及跑道的运行方式建立了全新的以延误时间最小、管制员负荷最小以及平衡空域资源为目标的多目标进场排序模型。但由于目前天府机场流量较小，因此未来需要在大流量终端区进行实验验证方法的有效性。

(3)分析了具有较强全局搜索能力的NSGA-Ⅱ算法和具有较强局部搜索能力的模拟退火算法。将模拟退火算法应用于NSGA-Ⅱ算法的框架下提出结合模拟退火的NSGA-Ⅱ算法。该算法不仅具有遗传算法较强全局搜索的能力，还利用模拟退火算法增加了种群的搜索宽度。但求解多目标问题的算法需要在此研究的基础上进一步探索，找到收敛更快、解更为精确的优化算法，提升了整体解决的效率以及精确性。