面向航班延误的停机位实时指派优化模型

姜 雨，胡志韬，童 楚，刘振宇，陈丽丽，张洪海

(1.南京航空航天大学民航学院，南京211106；2.航空电子无线电研究所，上海200241)

0 引 言

民航航班量的快速增长与机场资源的瓶颈使航班延误现象成为常态，对机场场面资源的正常运行造成不利影响，其中，停机位资源对延误尤为敏感.延误发生后，停机位预指派方案受到扰动，若不能及时调整方案，会使延误进一步传播和扩散.因此，面向航班延误的停机位实时指派对提升机场场面资源的运行效率，降低航空公司航班延误成本，优化旅客出行体验，具有重要的实际意义.

停机位实时指派方案是在预指派方案的基础上，针对停机位实时使用需求与原计划的偏差进行合理调整而得到的.Tang[1]以航班历史数据作为延误时间的参考，通过允许违反一些机位使用约束为航班重新指派停机位.Maharjan 等[2]在对航班延误日特性研究的基础上，构建停机位实时指派模型.Guépet 等[3]构建了停机位指派方案的混合整数规划优化模型，采用两种启发式算法对模型进行求解.近年，国内外学者在建模过程中考虑更多实际因素，在求解过程中应用智能算法，以提高求解效率[4-5].也有学者从航班延误的分布规律出发，针对旅客出行[6]，机位使用鲁棒性[7]，相邻航班之间的冲突概率[8]等，建立停机位实时指派模型.

已有研究成果考虑到航班延误对机场停机位调度的影响，但未考虑延误等级的划分.单一化的机位调整策略难以适用于所有情境，且无法体现决策的公平性.因此，本文从对航班延误等级的界定出发，在保证机坪安全运行的前提下，针对轻度航班延误状态和中/重度航班延误状态，提出一种面向航班延误的停机位实时指派多目标优化模型，为繁忙机场停机位调度提供决策依据.

1 问题与建模

1.1 问题描述

航班延误会对机场停机位资源的正常运行造成扰动.主要体现在：同一机位的前一架航空器占用超时，后续航空器无法在预定时间正常使用机位.停机位实时指派任务是在停机位预指派的基础上，对部分航班的使用机位进行空间(机位)或时间(占用时段)上的合理调整，以化解机位占用冲突.

1.2 模型假设

(1)研究时段设为2 h，指派对象为时段内的进港航空器(包括进港后又离港的航空器)；

(2)不考虑航空器拖曳，即航空器在停场过程中不可更换机位；

(3)为防止发生航空器无可用机位的情况，假设存在一个容量无限且满足各类约束的虚拟远机位.

(4)不考虑航班取消和临时更换航空器.

1.3 模型建立

首先对延误等级进行界定，设定差异化的指派目标.轻度延误状态下，为保证指派计划的一致性，减少管制等工作人员的额外负担，在化解冲突的前提下，尽可能减少对原指派计划的变动，即最小化因变更机位而增加旅客步行距离；中/重度延误状态下，需要在化解冲突的同时提升机坪运行效率.机坪运行效率可通过近机位的利用率衡量，即尽可能将航空器指派至近机位，故该目标可抽象为最小化指派至远机位的旅客数.面向航班延误的停机位实时指派模型框架如图1所示.

(1)目标函数.

(2)约束条件.

式中：A为运行航空器集合；G为所有可用机位集合；P为机坪集合；pt为P中元素，代表第t个机坪，共有l个机坪；i，j为航空器；k，m为机位；ci为航空器i执行的离港航班的旅客数量；dk,m为旅客从停机位k更换至停机位m的步行距离；si、sk分别表示航空器i和机位k的大小等级；分别为航空器i的预计开始和预计结束占用机位时间；yk、zk,m、ui,m为0-1变量，分别描述机位是否为远机位、两机位是否为相邻机位、航空器i是否被预指派至机位m；xi,k为模型的决策变量，描述航空器i是否被指派至机位k；M为一个足够大的值；Tb为最小时间间隔；vi,j表示航空器i与j发生冲突的概率，其值与两航空器间的机位占用时间间隔Ti,j有关，λ为冲突概率系数，即

式(1)针对所有航班延误状态，表示最小化机坪冲突概率，机位冲突分为同一机位的先后航空器冲突和同一时刻相邻机位的航空器冲突；式(2)针对轻度航班延误状态，表示最小化旅客变更登机口步行距离；式(3)针对中/重度航班延误状态，表示最小化指派至远机位的旅客数；式(4)为航班指派的唯一性约束，即一架航空器能且仅能被指派至一个停机位：式(5)为机位占用的唯一性约束，即同一个停机位在同一时刻只能被一架航空器占用；式(6)为类型匹配约束，即航空器的机型大小应与停机位的大小相匹配；式(7)为同一机位的占用时间间隔约束.

2 算法设计

停机位实时指派问题是大规模整数规划问题，存在多种可行性约束，求解难度较大.带精英策略的非支配排序遗传算法(NSGA-Ⅱ)在处理多目标优化问题时生成Pareto前沿，能为决策者提供良好的决策空间，因此，采用NSGA-Ⅱ进行求解.具体步骤如下.

Step 1编码.采用十进制整数编码方式，每个基因位置代表航空器被指派至的停机位编号，染色体长度等于研究时段内进港航空器数目.

Step 2初始化.依据停机位使用的约束条件，在可行范围内随机生成规模为N的初始种群，作为第一代父代种群.

Step 3初代个体适应度产生.对于生成的初始父代种群，计算每个个体在各个目标函数上的值，并依据其间是否存在支配关系对所有个体进行非支配分层与拥挤距离排序.拥挤距离计算方法为

式中：DC为解C的拥挤距离；r为问题中目标函数的个数；分别表示解(C+1)与解(C-1)在第n个目标函数On上的值.

拥挤距离可以比较各个解之间的相对优劣，拥挤距离小的解易被其他解代替，故在进行解的选择时，优先选择拥挤距离较大的解.

Step 4交叉和变异操作.采用二元锦标赛法从父代种群中选取N个个体，记为Wt，分别以概率pc、pm进行两点交叉、单点变异操作，产生N个新个体.生成新个体的过程中需要对个体按照式(4)～式(7)进行可行性检验，对于不满足约束条件的个体，随机产生新的可行方案进行替换，新个体记为Qt.

Step 5选择运算和精英策略.对合并后规模为2N的种群Rt，计算每个个体的适应度，并依据其间是否存在支配关系对所有个体进行非支配分层，从高到低记为F1、F2、F3，以此类推.在层次内部进行拥挤距离排序，如图2 所示.从第一层开始选取N个个体组成新的子代种群，记为Wt+1.

图2 NSGA-Ⅱ的选择运算和精英策略Fig.2 Selection and elitist strategy in NSGA-Ⅱ

Step 6重复Step 3～Step 5，直到达到最大迭代次数MGEN.程序终止后，处于个体分层中第一层个体，即为所求解问题的非支配解.

3 仿真验证

3.1 仿真数据

机场运行过程中国内/国际航班机位相互独立，选取其一研究即可.以北京首都机场T3航站楼的国内停机位系统为研究对象，进行仿真验证.选取停机坪P3、P4、P5，系统共85个近机位和42个远机位，如图3所示.2018年3月4日的国内航班运行数据如表1所示，停机位信息如表2所示，其中，B为近机位，R为远机位.参考该机场航班延误程度划分规则，如表3 所示，该日07:00-09:00 时段航班延误率17.8%，处于轻度航班延误状态；14:00-16:00 时段航班延误率44.9%，处于重度航班延误状态.取N=200 、MGEN=200 、pc=0.8 、pm=0.08 、λ=0.23，分别对两种状态下的停机位实时指派仿真结果进行分析.

图3 北京首都国际机场T3 航站楼停机位系统Fig.3 PEKT3 terminal gates system

表1 研究时段运行航空器数据示例Table 1 Example of operating aircraft datain study period

表2 研究时段停机位数据示例Table 2 Example of gates data in study period

表3 机场航班延误等级划分规则Table 3 Airport flight delay classification rules

3.2 轻度航班延误状态下的实时指派结果分析

07:00-09:00进港航空器共7架，仿真结果共得到8组Pareto解，如表4所示.由于受到轻度航班延误影响，预指派方案中有两处停机位(304、328)发生占用时间冲突，8组实时指派方案均将这两架航空器的使用机位调整到邻近的近机位，虽然增加了旅客步行距离，却有效避免了机位占用冲突.

机坪冲突概率及旅客更换登机口需要步行距离如图4 所示.可以发现，各组实时指派方案均互不支配，同一个停机位指派方案在两个目标上呈现相反的趋势，较小的机坪冲突概率同时意味着旅客更换登机口步行距离的增加.方案中机坪冲突概率最低降至2.4×10-4(机位占用时间平均间隔36.2 min)，旅客更换登机口总步行距离最小为111 330 m，即平均每位旅客需多步行102.9 m到达调整后的登机口.

表4 07:00-09:00 轻度航班延误状态下的停机位实时指派方案Table 4 07:00-09:00 gate assignment scheme under slight flight delays

图4 07:00-09:00 停机位实时指派方案的Pareto 解分布Fig.4 07:00-09:00 Pareto front distribution in gate reassignment scheme

3.3 重度航班延误状态下的实时指派结果分析

14:00-16:00 进港航空器共38 架.算法终止后得到4 组Pareto 解，指派方案如表5 所示.观察发现，38 架待指派航空器中，有5 架航空器的预指派方案在4 种方案中均未被改变，仅占13.2%，表明重度延误状态下的停机位实时指派策略倾向于调整大多数航空器的预设停机位，以旅客步行距离的增加换取近机位资源的高效利用，从而尽快化解航班延误.研究时段内共有6个停机位发生了不同程度的占用时间冲突，即302、309、313、314、402、520.在优化结果中，4 种方案下停机位302、313、314 及520 均没有被分配给任何航空器，避免了冲突发生，从侧面反映预指派计划缺乏鲁棒性，易受延误干扰.

表6 为停机位实时指派方案对比结果.由表6可知：预指派方案中有3 架航空器被指派至远机位，而4组方案均将它们调整至近机位，这是因为3架航空器执行的进港航班旅客人数相对较多；方案2同样有3架航空器被指派至远机位，但旅客数从528人下降至421人，减少了20.3%，体现了本文算法的有效性.在避免机位冲突的前提下，方案1中没有航空器被调整至远机位，机坪运行效率最高，同时机坪冲突概率被控制在10.7×10-5(机位占用时间平均间隔39.6 min)；方案4的机坪冲突概率最低，为4.9×10-5(机位占用时间平均间隔43 min)，安全运行水平最高，但有725名旅客被安排至远机位.停机位实时指派问题作为多目标优化问题，求解结果在目标上存在差异，决策者可根据实际需求在选择范围内做出合适的决策.

表6 14:00-16:00 停机位实时指派方案对比Table 6 14:00-16:00 contrast of gate assignment scheme

目标函数平均值变化趋势如图5 所示.由图5可知：初始条件下两目标均值都较高，随着迭代的进行，出现比较明显的下降趋势；第80 次迭代后，指派至远机位旅客数均值有小幅上升趋势，这是因为当几乎所有航班都被指派到近机位时，仅在近机位范围内调整难以使机坪冲突概率进一步下降，此时需要将少数航空器指派至远机位以减小冲突；两目标函数均值在第130 次迭代后收敛，收敛状态下，机坪冲突概率均值小于1×10-4，即机位占用时间平均间隔超过40 min.

表5 14:00-16:00 重度航班延误状态下的停机位实时指派方案(部分)Table 5 14:00-16:00 part of gate assignment scheme under severe flight delays

图5 14:00-16:00 目标函数平均值迭代曲线Fig.5 14:00-16:00 evolution of mean value of objective function

旅客更换登机口步行距离并非重度延误状态下的优化目标，相反地，为实现机坪运行的整体优化，需调整大量航空器的机位使用计划，故旅客步行距离显著增加.以方案1 为例，从机位分配公平性角度分析航空器机位变更距离的分布规律(仅针对近机位范围)，如图6(a)、(b)所示.航空器机位变更距离的均值为261.4 m，均值以下的分布较为密集，55%的航空器的机位变更距离小于200 m；均值以上的分布则较为均匀，仅有两架航空器的变更机位距离超过800 m.整体分布趋势表明，重度延误状态下的停机位实时指派方案具有较好的公平性.

图6 14:00-16:00 航空器机位变更距离的分布规律Fig.6 14:00-16:00 distribution of gate shifting distance for aircraft

4 结 论

本文研究了航班延误情境下的机场停机位实时指派问题.在对机场航班延误等级进行界定并考虑差异化指派目标的基础上，构建了面向航班延误的停机位实时指派多目标优化模型，并给出求解方法.结果表明：多目标优化中各目标不会同时达到最优，可根据实际情况选取指派方案；所提模型可成功化解延误导致的机位占用冲突，并有效优化旅客乘机体验和提升机坪运行效率.下一步研究可考虑航班取消、航空器拖曳等机坪运行过程中的实际情况，使模型更加细化.