机场群共用航路点的航班排序模型及算法*

王莉莉 林雍雅

（中国民航大学空中交通管理学院 天津300300）

0 引言

“十三五”期间，我国民航大力推进世界级机场群建设，全力打造以京津冀为代表的四大世界级机场群，实现机场群与城市群联动，为国家发展助力。世界级机场群的建设标志着我国民航逐渐发展进入以机场群为核心的区域化和一体化的发展阶段。据民航局统计数据显示，机场群的旅客吞吐量在逐年递增，但其吞吐量的增长也意味着会带来一系列的问题。因此，针对机场群的研究具有重要意义。

机场群运行耦合复杂，主要由于机场群基本上都处于同一终端区空域内，各机场间相互影响，共享部分空域资源，这些因素均会导致运行效率低下，进而导致空域拥堵和航班延误等现象频发，甚至会从某种程度上威胁到航空安全。

机场群系统内各机场间距离近，会导致多个机场起飞的航班目的地机场同方向时都过同1个航路点，即共用航路点。目前各机场往往单独进行航班时刻管理，这样就会造成共用航路点的拥堵。共用航路点是1个关键节点，能发挥承上启下的作用。通过一线单位调研了解到对机场群共用航路点的交通流进行优化调配能够大大减少运行拥堵和航班延误。

国内外学者从不同的角度对航班排序问题开展了大量的研究，主要研究对象是单机场。近年，对单机场航班排序的研究，Faye[1]考虑了跑道运行模式，研究多跑道航班进场排序问题。Salehipour[2]研究了进场航班排序问题，提出了启发式算法解决该问题。崔昳昕等[3]提出了进离港航班排序强化学习模型。张兆宁等[4]考虑了航班运行类别，建立适用于相关运行模式下多种跑道构型的多跑道机场航班优化排序模型，采用基于改进动态规划方法的滚动时间窗启发式算法。刘继新等[5]研究了不同空中交通密度下进场航班动态协同排序问题，设计了精英保留的遗传算法和带精英策略的快速非支配排序遗传算法。邱梦雅等[6]基于跑道限制、管制运行规则和终端区延误消耗限制等因素，建立了结合调度的航班排序优化模型，采用了先到先服务和局部队列优化。

随着机场群的发展，对机场群航班排序的研究也逐渐被国内外学者探讨与研究。Saraf等[7]设计了先到先服务、独立运行排序和繁忙机场优先3种进场航班排序算法，并进行了对比分析。Wieland等[8]研究了多机场航班排序问题，将其转化成单机场的航班排序问题，互相协作进而解决多机场航班排序问题。Capps等[9]综合考虑了航班汇聚点和跑道限制，基于多机场运行提出了离场航班调度方案。黄吉波[10]对比分析了几种终端区航班排序方法，建立了基于跑道分配的多机场终端区进离场航班协同排序模型和基于延误分配的进离场航班协同排序模型，设计了珠三角终端区航班排序系统。王莉莉等[11]着重考虑了交接点容量限制，建立了以最小化延误时间为目标的终端区多机场协同决策进离场航班排序模型。陆嘉旻[12]对现有的多机场终端区进场航班排序方法进行了总结与分析。张军峰等[13]提出了终端区“外围航班流”，综合考虑尾流间隔、移交间隔、放行间隔等多种间隔约束限制，建立了多机场终端区进离场航班优化排序模型。王湛等[14]提出了基于按时刻表分配公布顺序的离散化优化模型，重点分析各航空公司之间的公平性，制定了以调度延误、调度公平和调度航班架次三者均最优的多目标优化模型，并将模糊自修正多目标粒子群算法应用于模型进行求解计算。胡京[15]建立了多机场地面等待策略，并考虑恶劣天气下航路扇区容量骤增情况，结合改航策略改进了模型。黄吉波[16]基于管制运行规则和延误限制等因素，构建了基于延误分配的多机场终端区航班排序模型。张建学[17]构建了多机场终端区进场航班排序决策系统。

对航路点航班排序的相关研究，张颖等[18]基于航路流量间隔限制策略和航路排序策略，建立了解决2种策略一体化决策的二层目标规划模型，设计了基于NSGA-II多目标遗传算法进行求解。赵嶷飞等[19]基于汇聚航路的特点建立了汇聚航路航班排序模型，提出了多路编码算法解决航路航班排序问题。杜实等[20]引入了交通波模型，构建了以延误成本最小化为目标的基于交通波模型的交叉点航班排序模型。

纵观以上研究，现有的航班排序研究重点是针对单机场的，对于机场群各机场间协同效应考虑的仍较少；多机场航班排序主要侧重于多机场终端区航班的进离场排序或地面等待排序问题，而较少考虑航路阶段的航班排序问题；目前航班排序研究中针对航路点的研究普遍仍只是将其容量限制作为约束条件考虑，且研究对象大多是终端区的，现有研究中也有解决航路或航路交叉点的航班排序问题，但大多是单独针对其空域资源的考虑，并没有从机场群的角度出发。笔者提出机场群的共用航路点的概念，以机场群的共用航路点为研究对象进行流量管理的优化研究，能更好地从机场群的协同的角度研究航路点航班排序的问题，为整个系统资源的利用提供帮助。

为提高机场群整体运行效率，本文针对机场群公共资源-共用航路点进行交通流优化研究。针对机场群的共用航路点的运行特征，根据机场流量特性引入惩罚因子以总延误时间成本最小为优化目标建立机场群共用航路点的航班优化排序模型，提出1种新的TW-PSO组合优化算法对模型进行求解。仿真结果表明，所提出的优化排序模型和算法具有可行性和有效性。

1 模型建立

1.1 问题描述

机场群与单机场的差异之处主要在于其运行的耦合性与复杂性，机场群中各机场间运行相关性强，在分配时空资源时无法独立考虑，而需从整体运行的角度进行考量。共用航路点是机场群空域中共用的资源，其对机场群整个系统有一定影响，与终端区和其他空域都紧密相连，提升共用航路点的运行效率是增强机场群系统全局资源的关键。因此，本文研究机场群过共用航路点的航班排序问题，已知从各机场起飞的航班的计划过点时刻，对共用航路点的交通流进行有效的优化调配，得到合理的过点顺序和过点时刻。

1.2 模型假设

1）已知从各机场起飞航班的基本信息以及计划过点时刻等航班计划信息。

2）只考虑从机场群系统中的机场起飞单方向通过共用航路点的航班，且不考虑高度层的变化。

3）每架航班只能分配1个过点时刻。

4）共用航路点或机场附近无恶劣天气、无军航活动等特殊情况影响。

1.3 优化排序模型

1.3.1 建模思路

基于机场群与单机场的差异性，本模型的构建从协同角度综合考虑机场群的情况，选取机场群中的关键节点——共用航路点为研究对象，在提出共用航路点概念的基础上，对共用航路点的运行特征进行分析，进而实现对其交通流的优化，旨在构建机场群共用航路点的航班优化排序模型来对从各机场汇聚到共用航路点的航班进行排序和优化时刻，在确保安全的前提下，尽可能地减少整个机场群系统内的航班延误问题。

结合实际情况从机场群共用航路点的角度研究模型的目标函数和约束条件。机场群共用航路点的航班排序的目的是调度航班使整个机场群的资源更好的服务空中交通需求，减少航班延误，因此模型的目标是最小化所有过共用航路点的航班的总延误时间成本。为符合机场群的实际情况，通过一线单位调研了解，机场群中各机场的流量存在差异性，考虑到流量大的机场应赋予更高的重要度，故通过引入惩罚因子的方式来避免流量大的机场航班延误过多造成同时段内大面积航班受影响，并会波及机场群内其他机场的情况。基于实际运行考虑，构建共用航路点的时刻占用唯一性、安全间隔限制、时间窗、共用航路点以及所在扇区容量限制的约束条件。根据既定的目标函数，结合约束条件，建立机场群共用航路点的航班优化排序模型，从而实现机场群过共用航路点航班的排序，在确保安全的前提下，减小延误时间成本，避免空域拥堵与航班延误。

1.3.2 变量定义

变量定义的总结见表1，据此描述模型的目标函数和约束条件。

表1 变量定义Tab.1 Variable definitions

1.3.3 目标函数

为了避免各机场航班不要提前和延误过多，引入了惩罚因子α和β。α为飞机提前过共用航路点的惩罚因子，β为飞机延迟过共用航路点的惩罚因子，鼓励飞机提前，惩罚飞机延误。延误时间成本即延误时间乘以惩罚因子，以过共用航路点的航班的总延误时间成本最小为目标函数。机场群共用航路点的航班优化排序模型的目标函数见式（1）。

1.3.4 约束条件

机场群共用航路点的航班优化排序模型的约束条件见式（2）~（6）。

1）唯一性约束，即确保每架航班只分配到1个过点时刻。

2）安全间隔限制约束，即过共用航路点的相邻2个航班，需满足以下安全间隔限制。

3）时间窗约束，即实际过点时刻存在最大可接受的调整幅度，将时刻控制在时间窗范围内，就是在最早过共用航路点的时刻PTfai和最晚过共用航路点的时刻DTfai之间。

式中：最早过共用航路点的时刻PTfai与飞机的机型性能、起飞机场到共用航路点的距离等因素有关；最晚过共用航路点的时刻DTfai与飞机燃油量等因素有关。因此，PTfai和DTfai的取值可以根据实际情况进行设置。

4）共用航路点容量限制约束，即从各机场起飞通过共用航路点的总航班数量不超过共用航路点的最大容量限制。

5）扇区容量限制约束，即从各机场起飞通过共用航路点的总航班数量不超过共用航路点所在扇区的最大容量限制。

2 算法设计

2.1 算法原理

滑动时间窗算法的优点在于不需要对队列中所有飞机进行一次性排序，可以有效减小计算量，加快计算速度，但由于是依次移动时间窗，随机性较差；粒子群优化算法（particle swarm optimization，PSO）具有随机性和并行性，适合解决优化问题，但如果航班数量过大，迭代就会越复杂。笔者提出将滑动时间窗算法和粒子群优化算法有机结合形成1种TW-PSO（time window-particle swarm optimization）组合优化算法，上述2种算法均是从1个子集合入手解决问题，这种方式不需要对航班全序列中每个个体进行一次性排序。2种算法的有机结合可以将该优点发挥到最大价值。同时该算法既具有滑动时间窗算法适用于大量航班序列排序和快速性的特点，又具有粒子群优化算法的随机性、并行性和高效的特点。

TW-PSO算法是1种组合优化算法，即基于滑动时间窗算法得到的初次优化后的结果，作为二次优化的初始序列，对初次优化后的序列采用粒子群优化算法进行二次优化，通过双重优化后得到的最终结果即为TW-PSO组合优化算法的结果。

2.2 算法流程

采用滑动时间窗算法对机场群内从各机场起飞预计通过共用航路点的航班进行初次排序，对每个时间窗内航班排序并以某一步长向后移进行排序；以初次优化后得到的航班序列作为初始计划过点时刻，采用粒子群优化算法对该优化后的序列进行二次优化，以总延误时间成本最小作为目标函数来确定适应度值用来判断是否最优，不断更新最终得到双重优化后的最优位置及对应的最优适应度值，即航班序列和实际过点时刻。步骤如下。

步骤1。采用滑动时间窗算法进行初次优化。对初始时间窗内n=5架航班序列进行排序，优化后的窗内前s架航班即为最终队列的前s架航班。

步骤2。将时间窗以步长s=2向后移动，将新加入窗体内的s架航班加上上1架窗体内未被分离出的n-s架航班，重新构成包含n架航班的新时间窗。以此类推，不断构造新时间窗，分别对每个时间窗内航班进行排序，直到窗体右边界移动到最后1架航班为止，最终得到初次优化结果。

步骤3。采用粒子群优化算法进行二次优化。首先初始化粒子种群，设定搜索空间为m=20，种群大小为n=20，将步骤2得到的初次优化序列作为初始粒子种群，随机生成种群初始位置xi=(xi1，xi2，…，xim)和初始速度vi=(vi1，vi2，…，vim)，设定自我学习因子c1=2和群体学习因子c2=2，自身最优适应度值gbesti=(pi1，pi2，…，pim)，种群最优适应度值zbest=(pz1，pz2，…，pzm)；

步骤4。通过式（7）~（8）更新位置和速度，由总延误时间成本最小化的目标函数构造的适应度值函数计算出每次迭代各粒子的适应度值。

步骤5。比较各粒子当前的适应度值和粒子自身最优适应度值、种群最优适应度值。不断迭代，更新粒子和种群的最优位置和最优适应度值。以此类推，直到达到最大迭代次数，得到二次优化后的最终结果，算法结束。

3 算例仿真与分析

3.1 算例仿真

为验证所提出的机场群共用航路点的航班排序模型和组合优化算法的合理性和可行性，以京津冀机场群中的北京首都国际机场、北京大兴国际机场、天津滨海国际机场和石家庄正定国际机场为研究对象，选取从这4个机场起飞的预计在09：00—09：45和14：00—14：45时间段内通过共用航路点大王庄的航班进行仿真排序优化，得到过共用航路点的顺序以及实际过点时刻，选择总延误时间成本最小作为目标进行对比分析。通过数据统计选取2个较高峰时段09：00—09：45和14：00—14：45，09：00—09：45属于高峰时段，共20架航班；14：00—14：45属于较高峰时段，共15架航班。

本次算例仿真主要包括从北京首都国际机场（B）、北京大兴国际机场（D）、天津滨海国际机场（T）和石家庄正定国际机场（S）起飞的航班。共用航路点和扇区每10 min时间段内最大容量限制均为7架，航路中雷达管制下安全间隔是10 km，转换成时间取Si，i+1=2 min。最早过共用航路点的时刻PTfai和最晚过共用航路点的时刻DTfai在此是根据实际情况初步设置，也可以基于飞机的机型性能、起飞机场到共用航路点的距离、燃油量等因素进行设置。惩罚因子在此是根据机场流量设置，还可以根据飞机机型的不同而设置。在Matlab R2019a的环境下编写仿真程序，将所提出的组合优化算法结果同先到先服务（FCFS）算法、滑动时间窗算法和粒子群优化算法所得结果进行对比分析。4种算法的优化结果见表2。

表2 算法优化结果对比Tab.2 Comparison of the results of optimized algorithms

3.2 结果分析

14：00—14：45较高峰时段内15架航班的优化结果表明：采用TW-PSO组合优化算法比FCFS算法得到的航班总延误时间成本减少了76 min；比滑动时间窗算法减少了68 min；比粒子群优化算法减少了75 min。由于09：00—09：45高峰时段相比于较高峰时段的研究更具实际意义，故对高峰时段的优化结果展开详细分析。

根据结果绘制出延误时间成本累积折线图，见图1。通过总延误时间成本的对比，结果分析如下。

图1 延误时间成本累积折线图Fig.1 Cumulative line chart of the delay time cost

从研究对象和模型角度分析。针对机场群的共用航路点的运行特征，构建的模型能有效降低航班的延误时间成本，具有现实意义。根据机场流量的差异性，设置不同的惩罚因子研究延误时间成本更符合京津冀机场群实际运行情况。

从算法角度分析。与传统的先到先服务（FCFS）算法相比：采用FCFS算法，航班总延误时间成本为266 min；采用TW-PSO组合优化算法，航班总延误时间成本为50 min，减少了216 min，大大降低了延误时间成本。与TW-PSO组合优化算法的2种基础算法相比：采用滑动时间窗算法，航班总延误时间成本为262 min；采用粒子群优化算法，航班总延误时间成本为211 min；采用TW-PSO组合优化算法，航班总延误时间成本为50 min。由对比结果可知，与滑动时间窗算法相比，采用组合优化算法延误时间成本减少了212 min；与粒子群优化算法相比，采用组合优化算法延误时间成本减少了161 min。根据组合优化算法的排序结果可以看出，该算法得到的序列调整度比粒子群优化算法调整度小很多，说明该组合优化算法在滑动时间窗算法的基础上，充分发挥了滑动时间窗算法的优势，使调整幅度尽量较小的前提下仍实现了总延误时间成本的降低，说明2种算法实现了互补，使得组合优化算法结果更优，具有可行性。

由图1可以明显看出：TW-PSO组合优化算法曲线位于其他3种优化算法曲线的下方，证明组合优化算法得到的总延误时间成本最小，优化效果最佳。粒子群优化算法相较于其他3种算法，上下波动尤其明显，组合优化算法在一定程度上改进了粒子群优化算法的不稳定性。滑动时间窗算法和粒子群优化算法虽然总延误时间成本相较于FCFS算法的低，但最初的延误时间成本都高于FCFS算法。TW-PSO组合优化算法就很好地解决了这个问题，延误时间成本始终低于FCFS算法的延误时间成本。因此，从结果可以清晰看出提出的组合优化算法的合理性。

根据迭代过程的对比，粒子群优化算法得到的优化结果需要迭代500次，TW-PSO组合优化算法只需要迭代50次即可得到较优值，结果更稳定且优化效果更好。

统计15 min的航班通行量，统计结果见图2。由统计图可知，优化后的通行量折线图比优化前更趋于平稳，模型和算法在缓解航班延误的同时，使得空域容流匹配。

图2 通行量统计图Fig.2 Statistics of traffic volume

综上所述，本文以机场群的共用航路点为研究对象是具有实际应用价值的，所提出的共用航路点的航班优化排序模型通过惩罚因子的方式研究是具有现实客观意义的，TW-PSO组合优化算法具有合理性和可行性，优化效果有很大程度的提高，能对共用航路点的交通流进行有效的优化调配，有利于缓解航班延误问题，满足空域管理的需求，并改善机场群的协同运行效率。

4 结束语

本文以机场群的共用航路点为研究对象，给出了共用航路点的概念，提出了对共用航路点的交通流进行优化。研究了机场群共用航路点的航班优化排序问题，综合考虑了多元约束条件，考虑到实际情况鼓励提前的航班，惩罚延误的航班，根据机场流量的差异性采用惩罚因子的方式以总延误时间成本最小化为目标，构建了机场群共用航路点的航班优化排序模型，提出了新的结合滑动时间窗算法和粒子群优化算法的TW-PSO组合优化算法进行求解。对京津冀机场群过共用航路点的航班进行优化排序，将TW-PSO组合优化算法的优化结果分别与传统的FCFS算法、滑动时间窗算法、粒子群优化算法的优化结果对比。分析结果表明：本文所提出的TW-PSO组合优化算法的优化效果最佳，总延误时间成本明显降低，所提出的优化排序模型和算法具有可行性和有效性。对共用航路点的交通流进行优化调配，减少拥堵现象的发生，能为空中交通管制工作提供理论支撑，有助于机场群的协同运行管理和空域优化管理。后续可以将终端区进离场航班排序与共用航路点航班排序综合考虑，从整体性角度研究机场群空域协同优化问题；同时可以继续针对共用航路点的流量管理问题进行深入研究。