基于遗传算法的离场航班时刻优化

左杰俊，王 强，钟 琦，刘 懿

(1.成都佰行航空技术服务有限公司，四川 成都 610093；2.中国民用航空局第二研究所，四川 成都 610041；3.西南地区空中交通管理局，四川 成都 610202)

1 引言

航班延误是制约世界航空业发展的问题之一，目前，世界各国已采取各种措施减少航班延误。我国许多机场通过增加跑道数量和其它方法来提高容量，从而减轻航班延误。由于机场跑道是空中交通系统中最关键的单元之一，因此在一定时间内，充分利用跑道资源可以有效缓解航班延误。另外，进场和离港航班调度在减少航班延误方面也起着重要作用，因此合理的航班调度对确保航班安全，提高资源利用率，减少延误损失以及改善航班状况都有重大意义。在我国，主要采用FCFS(先到先得)原则安排进离港航班。事实表明，FCFS并不是最大程度地利用现有机场容量的最佳策略[1]。从20世纪初开始，国内外学者就进行了航班优化调度问题的研究。Dear和Sherif提出了一种在高密度终端区对飞机进行排序和调度的方法。这种方法被称为约束位置偏移(CPS)，并对其有效性进行了测试[2]。Abela等描述了解决飞机着陆时间安排问题的两种方法。他们还将此问题表述为混合整数程序(MIP)，并为其解决方案开发了分支定界算法[3]。Saraf和Slater开发了一种新的高效调度算法，该算法使用组合优化技术来找到在特定参考点上飞机的最佳到达飞机序列和最佳到达时间，前提是指定了从FCFS序列位置切换的最大数量，该算法还能够根据航空公司的偏好对飞机进行优先级排序，并在沿着飞机路线的所有扇区之间最佳地分配延误[4]。Hancerliogullari等人研究了以同时最小化飞机着陆和起飞的总加权延误为目标的多跑道混合模式下的飞机排序问题。它可以被建模为准备时间、目标时间和截止时间的并行机器调度问题[5]。与其它发达国家相比，我国空中交通流量管理的研究起步较晚。张妍考虑间隔约束建立了固定航线的进港航班排序模型[6]。侯亚伟以萧山国际机场为例利用Anylogic建立机场场面运行仿真模型，通过模拟仿真，寻找某时段航班延误的瓶颈环节，然后针对瓶颈环节对航班时刻进行优化[7]。张军峰等人将多机场终端区视为一个系统，航班计划视为与该系统相关的航班流，构建了多机场终端区进离场排序模型[8]。崔昳昕等人建立了单跑道机场进离港航班排序强化学习模型，并与先来先服务算法、蚁群算法进行比较[9]。李昂等人，以京津冀机场群为例，寻求最高航班正点率为目标，建立了机场群航班时刻优化模型[10]。

尽管学者们已经对航班排序优化方法进行了很多研究，但是它们仍然有不足之处。例如，某些模型是在理想情况下建立的，并未考虑天气、空中交通管制、机场周围环境等的实际情况。此外，大多数模型是针对单跑道或者简单的把多跑道视为独立运行的跑道，并不符合机场的实际运行情况。本文将机场场空侧视为一个系统，考虑机场实际放行能力、和管制间隔建立了离港航班时刻优化模型。通过遗传算法对模型进行求解，减少了航班延误损失。并将优化后的航班计划输入AirTop进行仿真。仿真证明文中所提方法是正确的。

2 问题描述

近年来，随着中国民航的飞速发展，场旅客运输需求显著增加，导致民航运输机场尤其是大型枢纽机场在短时间内不能满足航班流量增加的需求，随之而来的是航班延误的问题。中国民航的流量管理手段也开始从基于经验的粗放型管理策略向基于科学技术的精细化管理策略转变。因此，本文从机场运行角度出发考虑机场实际放行能力、空中交通管制间隔、航班调度难度等多种因素构建离港航班时刻优化模型，在保证安全的前提下合理安排离场航班，将总的航班延误时间降到相对最低的水平。

为防止主动延误发生，对机场历史运行数据就行分析，提取相应时间段的容量值作为容量限制，以防止安排的航班量超出机场运行保障能力造成延误。因此，本模型对连续时间区间长度为 5 分钟、15分钟、60分钟的机场时刻容量进行限制。

航空公司的期望时刻有一个最大可接受的调整幅度，因为过大的调整会影响后续航段的飞行。同时，如果对航班的调整范围过大，也会增加管制工作负荷。将优化后的航班时刻限定在某一范围之内，不但符合实际情况，也可提高模型的求解效率。

3 航班时刻优化模型

3.1 模型构建

3.1.1 符号说明

f待优化航班，∀f∈F

t0优化调整的时间片长度

ATD 实际离港时间

ETD 计划离港时间

m待优化的航班f的数量

n可用的时刻数(以5分钟为一个时刻则9：00-21：00有144个时刻)

aij航班i分配到第j个时刻时的延误时间

bij航班i分配到第j个时刻时的时刻调整量

c5机场在5分钟内的时刻容量

c15机场在15分钟内的时刻容量

c60机场在60分钟内的时刻容量

决策变量

(1)

3.1.2 目标函数

航班延误时间最小为目标，建立如下目标函数

(2)

式中i=1，2，..，m，j=1，2，..，n。考虑到实际情况，在大多数情况下，实际到达时间几乎不可能与预计时间一致，因此做出如下规定：实际起飞时间比预计起飞时间早或相等的情况视为延误时间为0，模型建立如下。

(3)

式中ATDij为航班i分配到第j个时刻时的实际离港时间，ATDij=ATD0+j×t0，比如起始离港时间ATD0为9：00航班i分配到第3个时刻则此时航班i的实际离港时间为9：15，ETDi为航班i的计划离港时间。

3.1.3 约束条件

航班时刻唯一性约束，为每一个航班分配有且仅一个时刻，式(4)中i∈(1，m)中任意整数，j=1，2，..n。

(4)

航班时刻调整范围约束，式(5)中ATDi0为优化前航班i的实际离港时刻，i∈(1，m)中任意整数，j=1，2，..n，该约束目的是避免优化后的航班因调整过大而影响后续飞行任务，特别是对联程航班意义重大。

(5)

机场容量约束，为了更好地使得航班计划符合实际运行情况，制定更加精细化的航班计划，本文将对连续时间区间长度为5分钟、15分钟以及60分钟的容量进行限制。式(6)中i∈(1，m)中任意整数，j=1，2，..n，式(7)、(8)中式中i=1，2，..，m，k∈(1，n)中任意整数。

(6)

(7)

(8)

3.2 模型求解

航班时刻优化的实质是航班排序，对不同飞机对重新组合，使得总延误时间或延误成本最小。对于数据量不大的排序问题可以使用列举法进行精确求解，也可以用数学规划法快速求解，但针对航班时刻资源配置问题，维度大，复杂性高，属于NP难题。鉴于此，本文采用遗传算法进行求解，求解过程如下图所示：

图1 遗传算法求解流程

3.3 遗传算法步骤

步骤1：确定遗传策略，包括种群数量n，选择、交叉和变异的方法。同时，确定交叉概率和变异概率，以及其它遗传参数；

步骤2：定义适应度函数f(x)；

步骤3：随机产生初始化种群P；

步骤4：计算与航班队列对应的染色体的目标函数；

步骤5：计算种群中个体的适应度值；

步骤6：在当前条件下寻找最优个体；

步骤7：判断演化代数是否达到最大遗传代数。

步骤8：采用轮盘赌选择，通过单点交叉作图法进行染色体的交叉操作；

步骤9：执行步骤4～步骤6；

步骤10：评估遗传算法的效果；

步骤11：输出最佳功能值，然后获得最优航班序列。

4 实例分析

以上海虹桥国际机场为例，首先对上海虹桥国际机场离港航班历史放行数据进行分析，分析结果如图2-图4。以每5分钟为一个时间片，分析了00：00-14：00(UTC时间)共169个时间片的离港航班量，5分钟内最大放行量为4架次，99%的时间片为超过3架次，可以认为5分钟的放行能力为3架次。详细分析方法见参考文献[11]，用同样的方法分别得到15分钟的放行能力为7架次，60分钟的放行能力为28架次。

图2 上海虹桥国际机场60分钟放行航班量

图3 上海虹桥国际机场15分钟放行航班量

图4 上海虹桥国际机场5分钟放行航班量

选取上海虹桥国际机场某日07：00-09：00共40个航班运行数据，按文中所提算法模型，设置种群规模200，最大进化代数200，变异概率0.4，优化结果如图5，在43代收敛得到最优一代种群，优化前后航班序列信息如表1所示。

表1 优化前后航班信息

图4 遗传算法求解过程

从优化前后的结果可以看出，根据文中所提算法对40条航班数据进行优化，可以减少总延误时间39%。优化前有32架次航班发生延误，平均延误24.7分钟。优化后，发生延误的航班减少为19架次，平均延误15.05分钟。

4.1 AirTop仿真验证

考虑跑道离港容量利用AirTop对文中所提算法优化后的航班计划进行仿真验证，仿真航班信息和结果见表2所示。

表2 AirTop离港仿真航班计划及结果

从上表结果可以看出，考虑跑道离港容量利用AirTop对遗传算法优化后的航班计划进行仿真，仿真得到40架次航班中延误航班数量由之前的32架次减少到23架次，总延误时间从原来的988分钟减少到668.9分钟，平均延误时间从24.7分钟减少到16.7分钟。仿真结果表明文中所提航班时刻优化模型可以有效的对航班时刻资源进行优化配置，减少航班延误时间。如果优化的数据增加，效果会更加明显，可以更大程度的提高运行效率。

5 结论

本文研究了飞机排序问题(ASP)在空中交通流量管理中的应用，以最大程度地减少总延误时间为目标。建立了基于机场实际放行能力的离场航班时刻优化模型，利用遗传算法对模型进行求解，并运用AirTop仿真验证了模型的有效性。以虹桥机场为例，优化结果表明文中所提方法可以减少离港延误39%，且能够减少延误航班数量。该方法同样可以应用于进港航班时刻优化算法的开发。