考虑容量不确定性的航班时刻优化模型研究

问 涛，张 颖，田 文，张晓洁

(南京航空航天大学 国家空管飞行流量管理技术重点实验室，南京 211106)

近年来我国民航运输业持续高速发展，日益增长的空中交通需求不断冲击有限的空域容量资源，为繁忙机场的正常运行带来巨大挑战.因此，如何进一步缓解拥挤和延误问题，是新形势下推动民航高质量发展的重要课题之一.一方面，我国正扩建、新建机场，加强民航基础设施建设，直接有效地增加系统容量；另一方面，可以采取流量管理策略，通过控制空中交通需求的时空分布，在中短期内改善机场容量短缺和航班延误现象[1].

航班时刻优化策略是一种战略规划阶段实施的流量管理策略，它通过科学、合理地分配航班时刻实现改善对机场容量的使用，以减少空中交通冲突，增加飞行流量，提高社会效益[2].在众多文献中， 航班时刻优化策略问题有多种说法， 包括时隙分配问题、 时隙调度问题等，它们的本质是一样的.

世界多国研究者针对航班时刻优化策略问题进行了相关研究.例如，2017年，Jacquillat等提供的优化方法在传统效率目标外，提出了如何度量时刻可靠性、公平性等其他种类的目标[3].2017年，Pellegrini等研究了机场网络在多种时刻调整量优化目标下的时隙分配[4].2018年，Zografos等提出了考虑时刻计划可接受度的双目标优化模型[5].2018年，Ribeiro等研究了基于优先级的多目标时刻分配模型及计算方法，使得优化更加贴近实际规则[6].2018年，裔田园探究了一种基于航路走向的航班时刻优化方法[7].总体上，已有成果主要集中于对确定型问题的研究，对不确定性问题的研究则相对较少.2013年，Churchill等从宏观排队系统的角度建立了容量不确定性下优化机场时刻安排水平的模型[8].2014年，Corolli等研究了不确定容量下机场网络的航班时刻优化模型[9].2014年，曾奇初步探索了单个机场的鲁棒性航班时刻优化[10].2019年，亓尧、岳仁田等研究了只考虑一个运行日的容量不确定性的航班时隙分配[11-12].

确定型航班时刻优化问题假设空域系统是理想、静态的，不受外界环境的影响，没有考虑实际每日运行过程中机场容量受天气等因素影响下的随机性，得到的航班时刻在机场实际运行时若遇到较低的容量会产生较多的航班延误.因此，有必要对不确定型航班时刻优化问题进行研究，将航班时刻的战略协调规划与实际运行可能的环境条件相互关联，得到潜在航班延误更少的时隙分配结果.

本文则在前人研究的基础上，建立了能够考虑多个机场多个运行日的容量不确定性的两阶段随机规划时隙分配模型，模型增加了对机场进离场容量的优化选择决策，弥补了既有研究将机场进场容量、离场容量和总容量孤立考虑的不足，并设计使用了样本均值近似方法对具有大量场景的大规模实例进行求解计算.

1 问题描述

在航空运输系统的实际运营中，为适应季节变化，每年要制定两次航班计划，分为冬春航季和夏秋航季，每个航季的航班时刻均要在航季开始前几个月提前协调好.由于天气这一主要不确定性因素的存在，由航班时刻协调人在航季开始前协调分配好的航班时刻在机场实际运行时往往会受到机场容量等条件的随机变化的影响而不能正常如期执行，此时需要实施地面等待等战术流量管理策略来处理发生的交通冲突.本文采用两阶段随机规划方法来考虑容量不确定性，时刻协调人根据未来机场网络运行时一系列可能的容量场景做出最佳的协调决策.

如图1所示，本文不确定性问题的优化依据包括两个阶段—协调阶段和运行阶段.第一阶段为协调阶段，协调人根据协调规则配置航班时刻；第二阶段为航班时刻在不同容量场景下的战术运行过程，航班根据机场网络容量场景施行战术流量管理.本文中机场容量指机场在单位时间能够执行的航空器架次.关于容量场景，单个机场一天的典型容量场景及其发生概率可以通过分析长期的历史容量数据得到[8]，本文假设机场之间的天气是相互独立的，暂不考虑它们之间的相关性，因此，机场网络的一个场景是各机场各运行日容量场景的一种组合[9].

图1 航班时刻协调与运行过程

两阶段随机规划是处理含有不确定性参数的优化问题的常用方法之一，通过陈列展开不确定性场景，即可以得到其等价的确定性问题.两阶段随机规划模型的一般形式和确定型等价形式可见文献[13].本文针对航班时刻分配问题建立的优化模型如下.

2 两阶段随机规划航班时刻优化模型

2.1 模型假设

本文建立的考虑容量不确定性的航班时刻优化模型为方便起见，做出如下假设：

1)以天气为主的随机因素只对机场空侧容量造成影响，带来不确定性；

2)运行阶段对交通冲突采取的战术流量管理手段均为地面等待策略；

3)暂不考虑本地机场的航班延误传播以及来自上游机场的航班延误传播.

2.2 决策变量

2.2.1 协调阶段决策变量

根据航班计划制定规则，协调后的航班时刻t必须为5 min的整数倍时间点，一个时刻t对应的是一个5 min长度的时间片，一天24 h共为288个时间片.

2.2.2 运行阶段决策变量

不同于一般的考虑不确定性的时隙分配模型，本文将进离场服务率也作为决策变量.

2.3 目标函数

本文建立的考虑容量不确定性的航班时刻优化模型的目标函数为

MinZ=CST+W·COP

(1)

其第一部分为协调阶段航班时刻调整成本CST，第二部分为权重系数W和运行阶段航班延误期望成本COP的乘积.权重系数的取值范围为W≥0，本文将其定义为对运行延误的控制程度，用来权衡协调成本和运行期望成本之间的关系.当W=0时，即等价于确定型航班时刻优化模型，航班时刻协调人不考虑不确定性带来的潜在运行延误.当W>0时，协调人开始考虑整个机场网络容量的不确定性，W取值越大，则越重视控制运行延误期望的大小，越倾向于安排更多的时刻调整以减少运行延误期望成本.其中：

(2)

(3)

式(2)表示协调成本为总航班调整时间量，其中daysf为航班f的计划运行天数，deptf为航班f申请的计划起飞时刻，arrtf为航班f申请的计划降落时刻.式(3)表示运行成本为各容量场景的总航班运行延误时间的数学期望，其中p(ω)为机场网络容量场景ω的发生概率，ck为机场k延误一个航班估计所需的时间成本.

2.4 约束条件

2.4.1 战略协调约束

1)航班时刻分配约束

保证每一个航班的起飞和降落申请都分配到时刻，即：

(4)

(5)

2)机场额定容量约束

保证机场计划的起飞、降落和总航班数量不超过对应的机场额定容量，即：

∀k∈K,r∈R,t∈T,h∈H

(6)

∀k∈K,r∈R,t∈T,h∈H

(7)

∀k∈K,r∈R,t∈T,h∈H

(8)

3)飞行时间约束

保证所有航班的计划飞行时间不变，即：

(9)

其中：lf为航班f的计划飞行时间.

4)周转时间约束

保证对于衔接航班，前一个航班的降落操作与后一个航班的起飞操作之间的时刻间隔不小于所需的最小周转时间，即：

(10)

其中：qff′为衔接航班对(f,f′)∈P的允许最小周转时间，f对应降落航班，f′对应起飞航班.

2.4.2 战术运行约束

1)运行延误定义约束

定义起飞延误、降落延误航班数量分别为超出进场和离场服务能力的航班架次，即

∀k∈K,r∈R,t∈T,h∈H

(11)

∀k∈K,r∈R,t∈T,h∈H

(12)

2)进离场服务率优化选择约束

机场运行时可达到的进场服务率和离场服务率之间存在一定的关系，即：

(13)

图2 进离场服务率优化选择原理图

机场跑道既要用于起飞，又要用于降落，研究表明，机场进离场率之间存在包络线形状的制约关系，该包络线表征了机场运行容量，其形状、大小取决于跑道配置和天气条件[14]，如图2所示.根据容量的定义，机场运行过程中，能够执行的航班量应该是在包络线范围之内，图2中圆点表示某机场假想的一些计划航班量，实线包络线表示该机场某时段假想的容量，在该容量情况下，包络线内的计划需求完全可以满足，对于包络线外的计划需求，机场实际运行时管制员会决定合适的服务率，只执行部分航班，以实现容流平衡，如图2中箭头所示.

不同于一般的考虑不确定性的时隙分配研究将进离场运行容量孤立开来列写约束，忽略了它们之间固有的关系，本文在模型中加入进离场服务率优化选择约束，使得模型能够根据容量场景ω下各时段容量包络线情况、机场总的航班计划量，优化选择每个时段最适宜的进离场率的组合，实现进离场率的动态平衡优化，更加符合机场实际运行操作.

2.5 求解计算方法

上述模型为整数线性规划模型.本文使用强大的商业数学规划求解器CPLEX求解.然而机场网络多运行日的容量场景数量一般呈指数型增加，往往使得模型的规模异常庞大，对此，本文在求解中采用一种运用统计近似的简单、快速的计算方法—样本均值近似.

样本均值近似是一种基于蒙特卡洛仿真的外部采样方法，它通过随机抽取部分容量场景，使用样本运行延误成本的算术平均作为总体运行延误成本期望的近似值，并通过多次采样缩小近似解的范围.根据文献[9]和[15]，结合本文问题，具体求解计算步骤设计如下：

1)确定采样次数M和样本大小N；

3)根据容量场景ω的发生概率按照轮盘赌规则抽取样本；

4)M组容量场景样本分别代入样本均值近似模型使用CPLEX求解，得到各组样本的目标函数值Lm；

3 算例实验

3.1 实例参数

采用我国北京首都机场(ZBAA)和广州白云机场(ZGGG)一周的预先飞行计划数据进行模拟计算.

两场所构成的机场网络如图3所示，机场网络考虑在ZBAA和ZGGG起降的航班，其中ZBAA和ZGGG考虑容量约束，外围机场假设容量为无穷大.本算例ZBAA和ZGGG的容量约束类型均选取为整点小时容量约束，战略协调阶段使用民航局颁布的协调机场容量标准作为额定总容量， 具体ZBAA为86架次/h，ZGGG为69架次/h；战术运行阶段机场进离场容量，即进离场服务率，使用后文假设的运行容量场景.

图3 机场网络示意图

以ZBAA和ZGGG为目标机场选取2018年3月5日～2018年3月11日的预先飞行计划如表1所示，共计航班申请4 502条.其他机场参数包括：选择优化的时段为各计划日的12:00～18:00；两机场的航班延误时间乘子ck粗定为5 min/架次.

表1 预先飞行计划(部分)

3.2 容量场景

由于没有机场历史运行容量数据来源可用于分析，本文采用假设的机场网络容量场景.为方便起见，假设两机场的容量场景和发生概率相同，各场景每个小时的容量也相同，且容量包络线均为如图2中间所示的三段，αb、βb为0或1，γb值具体如表2所示.7个运行日则机场网络共得到2.68亿个容量场景.

表2 机场假设容量场景

3.3 结果与分析

为了考察运行延误控制程度对时刻协调成本的影响，对前述模型采用不同的权重系数W进行计算，得到战略协调成本与战术运行期望成本之间的关系.所有算例样本均值近似初始样本大小N和N′分别定为100和500，初始采样次数M定为10，优化间隙限定为3%.最终结果如表3和图4所示.Z*下界计算用时均在1 h左右，上界计算用时均在28 min左右.

表3列出了不同权重系数下目标函数最优值的上下界和标准差，最佳近似解的两阶段成本以及最佳近似解下同W=0时相比运行期望成本优化的程度.通过表3可知，下界和上界都非常接近，表明近似结果精确度高；上下界的标准差都相对较小，说明实验选择的样本大小、数量合理，所取样本点分布均匀.

表3 求解计算结果

图4显示了战略协调成本和运行期望成本的帕累托前沿.首先，W=1和W=0时的结果一样，说明W=1时模型还不足以产生随机优化的效果，这是由于本文暂时省略了对波及延误的计算；战略协调成本为0，这是因为预先飞行计划由民航局审批后得到，本身已基本满足公布容量约束.接着，随着权重W的递增，战略协调成本在随之增加，而运行延误期望成本在不断减小，且随着运行期望成本的减小，战略协调成本增加得越快.结合表3，战略协调成本增加435 min，运行延误期望成本即减少22.61%，验证了模型能够帮助减少运行阶段预期的不确定性延误，航班时刻协调人可以根据需求和能够接受的水平对协调成本和运行期望成本做出权衡.

图4 战略协调成本与运行期望成本的帕累托前沿

4 结 论

1)本文建立了基于两阶段随机规划的航班时刻优化模型，模型能够处理考虑多个机场多个运行日的容量不确定性；

2)所建模型将进离场服务率也作为决策变量，在战术运行阶段加入了进离场率优化选择约束，更加贴近机场运行操作实际；

3)结合模型设计总结的样本均值近似方法简单快速，使得具有大量场景的实例能在有效时间内求解计算得到满意的结果；

4)结合实际数据验证了模型的有效性，同时分析了航班时刻战略协调成本与运行期望成本之间的关系，可以辅助航班时刻协调人根据能够接受的运行延误期望水平做出合适的时刻协调决策；

5)下一步可进行的研究包括：寻找可行的间接方法得出我国机场真实的典型容量场景；研究延误波及的计算从而得到更精确的运行延误期望等.