基于延误分级的航班过站松弛时间优化研究＊

朱星辉 戚彦龙 吴薇薇 高 强

（南京航空航天大学民航学院 南京 210016）

0 引 言

航班延误问题，Rexing等［1－3］运用设置时间窗的方法，优化了航班离港时刻，为航班延误调整提供了一定的灵活性．Paul［4］等把影响航班衔接和延误波及因素分为可控因素和随机因素，指出针对不同机场、不同飞机应有不同的航班地面操作缓冲时间以及空中飞行缓冲时间，用以补偿随机变化因素带来的时间损失．Shervin等［5］考虑了飞机和飞行机组两个因素在延误树中的影响，提出了利用调整松弛时间来减少延误的传播，不过没有给出调整松弛时间的具体方法．Shervin等［6］指出延误向下游航班的传播加剧了延误的发生和影响程度，并且通过对计划过程中的松弛时间进行重新分配，不改变原来飞机路线和机组计划的决策，最小程度地修改航班计划，来减少延误波及的影响．曹卫东等［7］利用贝叶斯推理建立了单机场和多机场过站时间贝叶斯模型，分析了前航延误时间和机型类型对航班过站时间调整的影响，以及发生首发延误时多机场间过站时间调整量的相互影响和对末航班到达延误的影响，认为发生前航延误时调整航班的机场过站时间可以有效减少延误向下游机场的波及．牟德一等［8］提出了基于延误概率的鲁棒性飞机排班问题，但只考虑单机型情况，而且没有限制飞机架次，计算结果飞机利用率明显偏低．郑晓洋［9］从航班取消可行性、取消原则、取消策略的选择三个方面对航班取消策略进行了探讨，并提出基于延误波及的航班取消延误成本模型，对航班延误波及时的航班取消策略选择具有一定的指导意义．丁建立等［10］在基于免疫进化算法的基础上对过站时间进行了优化，但其对离港时间调整区间采用了统一阈值．以上文献从飞机路线、机组排班以及一体化模型等不同角度对航班衔接的过站松弛时间进行了定性和定量方面的研究．不过对过站时间的调整没有针对性的考虑每个航班的延误程度．本文基于每个航班延误风险分级，在原有飞机路线和机组任务不变情况下调整过站松弛时间，使延误波及范围减小，提高航班正点率及旅客的满意度；即根据每个航班的延误级别，设置相应的过站松弛时间调整区间，使调整更具有针对性．

1 航班延误波及和过站松弛时间研究

1．1 航班延误波及分析

航空公司为了优化资源利用，保障飞机平均日利用率，在航班计划中往往安排1架飞机在1d连续执行多次航班．这些航班组成了一个航班联线，相邻的连续航班之间有一定的过站时间，包括地面服务时间和松弛时间．由于航班之间存在时间衔接关系，当上游航班由于某种原因产生延误，在空中飞行时间不变的情况下，则延误必然会波及到下游航班．上游航班延误时，调整下游航班的过站时间可以有效的减少延误的传播．因此在实际操作中航空公司常通过调整飞机的过站时间来减小延误的波及，图1为连续航班i，j的离港、到达和延误图．其中Slack为过站松弛时间；PCT为计划过站时间；MCT为最小过站时间；PDT为计划离港时间；ADT为实际离港时间；PAT为计划到达时间；AAT为实际到达时间；PD为波及延误；IDD为独立离港延误；IAD为独立抵达延误；TDD为总的离港延误；TAD为总的抵达延误．且存在以下数量关系PCTij＝PDTj－PATi；Slackij＝PCTij－MCT；PDij＝Max（TADi－Slackij，0）．

图1 连续航班i，j的离港、到达和延误图

1．2 基于航班延误风险分级的过站松弛时间优化模型

为进行航班过站松弛时间优化调整，做如下基本假设（或建模基础）．

1）保持原机组和飞机路线、航班联线不变．

2）保持原航班联线中总过站时间不变（航班时刻调整时，不出现红眼航班）．

3）航班时刻（时隙资源）不能大幅度修改，不影响航班市场需求．

4）航班轮档时间不变．

根据文献［11］，航班延误风险分为5个等级，即正常延误，轻度延误，中度延误，重度延误和超长延误．设G表示航班延误风险分级集合，有g∈G．模型涉及到的其他参数及变量如下：F为航班集合；Tg为航班延误风险级别g对应的过站松弛时间调整阀值，相应调整区间为［0，Tg］；Tig为航班i（i∈F）延误风险级别为g对应的过站松弛时间调整区间，其中Tig∈Tg；A为衔接航班的集合（如i－j）；S为航班联线的集合，s∈S（通常指1架飞机执行的一个航班任务串）；As为航班联线s中航班衔接的集合；W 为始发航班延误时间集合，w∈W；Fo为所有航班联线集合S中首航班的航班集合；Fl为所有航班联线集合S中末航班的航班集合；pws为航班联线s中，始发航班离港延误w分钟发生的概率，s∈S，w∈W；PATi为原计划中，航班i的计划到达时刻，i∈F；PDij为原计划中，从航班i到后续航班j的波及延误，（i，j）∈As，s∈S；PDwij为原计划中，给出w 后，从航班i到后续航班j的波及延误，（i，j）∈As，s∈S，w∈W；TADwi为原计划中，给出w后，航班i的抵达延误，i∈F，w∈W；IADwi为原计划中，给出w后，航班i的独立抵达延误，i∈F，w∈W；Slackij为原计划中，航班衔接（i，j）的松弛时间，（i，j）∈As，s∈S；pdwij为新计划中，给出 w 后，从航班i到后续航班j的波及延误，（i，j）∈As，s∈S；iadwi为新计划中，给出w后，航班i的独立抵达延误；Slack′ij为调整过站时间后航班衔接（i，j）的松弛时间；tadwi为给出了延误w 以后，航班i的抵达延误；xi为航班i的离港时间变化量，按民航局规定，国内航班离港时刻不能提前，因此xi只能大于等于0，即i∈F，0≤xi≤Tig．

以调整过站松弛时间前后延误波及时间之差为目标函数建立模型，实现优化调整效果最大化，即：

1）新的松弛时间满足：

式中：xj－xi为松弛时间的变化量．式（3）保证每个航班联线中过站时间的总和不变．

2）在航班实际运行当中，同1架飞机执行的任意航班衔接（i，j）∈A，航班i到j的波及延误为：

PDwij＝ max（TADwi－slackij，0） （4）

3）对于任意航班j，如果j是航班联线的始发航班，航班j的独立抵达延误＝航班j的抵达延误，即若j∈Fo，则iadwj＝tadwj；否则的话，iadwj＝tadwj－pdwij（独立抵达延误＝航班j的抵达延误－航班j的波及延误）．即

4）对于任意航班联线∀（i，j）∈As，调整后的波及延误应满足：

同时，对任意航班j的抵达延误满足

5）对过站松弛时间的调整应满足：

为了使首末航班的离港时间变化不大，令T＝5，即满足否则，

为了保证末航班调整之后不为红眼航班，且根据假设4），对于末航班应该满足式（12）：

6）另外，有非负约束条件：

2 实例验证

选取国内某航空公司每天的180条航班联线数据，每个航班联线包括4～8个航节，见表1．其中Stringnumber为航班联线编号，Stringdata第一维为相应的航班联线编号，第二维为航节序号；如果航班联线小于8个航节，则通过设置虚拟航班进行补充，如航班联线Stringnumber［2］实际只有7个航节，则Stringdata［2，8］为虚拟航班．过站松弛时间调整阀值Tg既要保证离港时间调整幅度不能太大，又要保持机组和飞机路线、航班联线不变，因此，根据实际情况和历史数据的聚类分析，取Tg＝｛5，10，15，15，15｝．

表1 某航空公司一天执行的180条航班联线

运用ILOG OPL优化软件求解，目标函数值z＝10 008min，即通过航班衔接松弛时间的调整，使总延误波及减少了10 008min．通过计算，原始波及延误TotalPD＝32 697min，波及延误减少了30．6%，调整效果非常明显．

部分数据见表2．其中pdij是航班i对j的波及延误，xi是航班离港时间的调整量，pdij和xi的单位均为分钟．

表2 运行结果的相关数据

3 结束语

航班延误给航空公司成本、乘客出行及航空运输生产等带来很大的负面影响，其中波及延误的影响更为突出，而过站松弛时间在减缓延误波及中起到关键的作用．本文基于航班延误分级，在保持原有飞机路线和机组任务，以及总的过站时间不变的基础上，对航班过站时间进行优化．研究结果表明，基于航班延误风险分级的过站时间调整，针对不同延误级别设置不同的调整区间，小范围的改变离港时间，有效地减少了延误波及现象；基于航班延误风险分级的过站松弛时间优化为提高航班计划抗干扰能力，制定更具鲁棒性的航班计划提供了理论支持．不过，此模型没有具体考虑调整过站松弛时间后对经济成本的影响，仅是从航班延误时间上考虑了过站时间的重新分配，这也是下一步研究的内容．

［1］REXING B，BARNHART C，KNIKER T．Airline fleet assignment with time windows［J］．Transportation Science，2000：34（1）：1－20．

［2］LAN S，CLARKE J P，BARNHART C．Planning for robust airline operations：Optimizing aircraft routings and flight departure times to minimize passenger disruptions［J］．Transportantion Science，2006，40（1）：15－28．

［3］曹 嵩，孙富春，胡来红，等．基于分布算法的离港航班排序优化［J］．清华大学学报：自然科学版，2012，52（1）：66－71．

［4］PAUL T R，LISA A S，LEONARD A W．Flight connections and their impacts on delay propagation［J］．Digital Avionics Systems Conference，2003，5（1）：1－9．

［5］SHERVIN A，AMY C，YIHAN G，et al．Analysis of the potential for delay propagation in passenger airline networks［J］．Journal of Air Transport Management，2008，14（5）：221－236．

［6］SHERVIN A，AMY C，LAPP M．Decreasing airline delay propagation by re－allocating scheduled slack［J］．IIE Transactions，2010，42（7）：478－489．

［7］曹卫东，林翔宇．基于贝叶斯网络的机场过站时间分析［J］．航空计算技术，2010，40（5）：5－9．

［8］牟德一，张宗贤．基于航班延误概率的鲁棒性飞机排班模型［J］．中国民航大学学报，2010，28（6）：35－39．

［9］郑晓洋．航班延误波及问题中的航班取消策略探讨［D］．济南：山东大学，2011．

［10］丁建立，李华峰．基于免疫进化算法的航班过站时间优化模型［J］．计算机工程与设计，2012，33（9）：3637－3640．

［11］戚彦龙，王 琨，朱星辉，等．基于离差最大化原理的航班延误风险分级研究［J］．武汉理工大学学报：交通科学与工程版，2014，38（1）：162－166．