航季航班计划飞机连线自动衔接模型

黄国辉

(厦门航空有限公司，福建厦门361000)

近年来，中国民航运输业呈现快速发展趋势，根据《2020年民航行业发展统计公报》[1]，截至2020年底，中国大陆已有64家运输航空公司、3 903架运营飞机、5 581条执飞定期航班航线.对于各家航空公司而言，飞机是重资产、航权时刻是关键资源，企业核心目标是在飞机投入最小化的情况下，高效利用航权时刻资源，编排出最优的航线网络，最终实现经营利润最大化.因此，制定合理的航班计划对提升航空公司市场竞争力有着重要作用.航季航班计划编制是一项非常复杂而繁重的工作，操作难点在于飞机机型指派和飞机连线衔接[2-4].目前，国内大部分航空公司还是借助人工来完成这两项业务，操作效率和编排质量都较低.行业主流的航班编排系统基本都被欧美公司垄断，国内航空公司不得不高额采购引进这些系统，不仅维护成本极高，而且无法根据国内航空公司的实际业务优化系统功能，存在较大的应用局限性.Zhou[5]整理综述了机型指派(FAP)、飞机路径(ARP)和机组排班(CSP)等航空公司计划和调度问题的解决方法，并指出航班调度仍是当前主要难题.都业富[6]在航班串优化的研究中提出航班衔接是评价航线调度优化效果的重要因素.肖东喜等[7]认为飞机连线问题是航班环构建的实际体现，飞机连线的自动衔接有助于降低航空公司构建航班环的难度，进而提高航线计划的效率.于焯等[8]引入等图的概念，构造航线调配状态图，将飞机航线调配问题等价为等图的路径査找问题.孙宏[9]用二部图来描述航节衔接问题，并通过Ford Fulkerson算法进行求解.然而，当前研究主要用于解决单枢纽(或基地)航线网络的航班衔接问题，无法完全满足多枢纽、固定连线等复杂的实际需求.加权二部图算法是在二部图的基础上，给边赋予权重，以实现不同优先级别的目标实现[10]，张绍阳等[11]利用加权二部图最优匹配算法研究了中文段落相似度的匹配查重问题，但该算法还比较少应用于解决航线优化问题.

综合考虑机型指派、飞机路线问题，朱星辉等[12]建立了基于列生成算法的一体化飞机排班模型.但该模型是基于以天为单位的航班计划(即每天的航班计划都相同)，飞机数量和航班数量均较少.而在实际应用场景，国内中大型航空公司机队数量达数百架，每周航班数量高达数千个，如果用一体化模型求解，建模和求解的复杂性将倍增，求解效率根本无法满足航季航班计划编制过程中快速模拟的需求.如Ahmed等[13]基于美国联合航空公司的航班网络，考虑航班计划鲁棒性，建立了综合机型指派、连线衔接、机组排班等一体化的模型，该案例解决了超过200架飞机的航班排班问题，但需要数小时的求解时间；
Sanchez等[14]利用启发式算法建立了考虑飞机维修计划的一体化飞机排班模型，该模型求解529架飞机的排班问题也需要2 h.结合相关领域的前沿算法，寻找有效的解决方案仍是目前亟待解决的一个重要难题.

由于国内民航市场规模大、变化速度快，且政府监管频率较高，意味着航班优化调整的效率对航空公司而言极为重要.因此，本文以使用飞机数量最小化和收益贡献最大化为目标，采取两阶段方式解决机型指派和连线衔接的问题.首先，利用时空网络图完成机型指派，明确最少的使用飞机数量，为飞机连线衔接确定机型基础.其次，采用加权二部图算法来解决航线衔接问题，根据连线衔接的目的不同，设计不同的衔接权重，求解满足要求的衔接方案.为了与加权二部图算法作对比，本文在第二阶段加入二部图、先进先出、后进先出等连线衔接算法，并通过横向、纵向对比不同算法的可行性与适用性.

1.1 问题描述

在国内民航运输业，每年分为两个航季，即夏航季(每年3月的最后一个星期日至10月的最后一个星期日的前一天)和冬航季(每年10月的最后一个星期日开始到第二年3月的最后一个星期日的前一天).每次换季都要重新制定航班计划，包括航班日期、航线、航班号、起降时刻、机型、连线编号等要素.其中：1) 航班日期是指每个航班在第一个起飞机场的起飞日期；
2) 航线是指航空公司开展经营活动所运营的航班路线，比如，广州-上海、厦门-舟山-北京；
3) 航班号是一天中区分不同航班的唯一标识，比如，南航广州-上海CZ3533；
4) 起降时刻是指航班在起点机场、终点机场和经停机场的起飞及降落时刻；
5) 机型指用于执飞该航班的飞机型号，比如波音B787、空客A321；
6) 连线编号是指每架飞机执飞任务的编号，即同一架飞机执飞不同的航班，这些航班均属于同一个连线编号，比如有3架A321飞机，那么这3架飞机连线编号为A321_01、A321_02、A321_03.

通常情况下，新航季航班计划编制是在前一个同航季航班计划的基础上(比如2021年冬航季是基于2020年冬航季)，根据航空公司的机队规划、航权、时刻等资源情况和市场预期效益进行优化调整.因此，新航季会有部分航班是延续前一个同航季的航班计划，但多数航班会根据市场和资源争取情况做调整.这里的航季航班计划是以周为单位制定，即只要编制出一周的航班计划，再将其复制到后续周期，就可以形成整个航季的航班计划.

在航班计划编制过程中，第一步是机型指派.主要是满足运行约束的前提条件下分配机型，使航班收益贡献最大化.即考虑两个因素：1) 运行限制.不同型号的飞机具有不同的飞行性能(如航程、最大起飞重量、发动机推力等)，不同性能的飞机决定了该机型可以执飞的航班.比如：B737、A320等短航程机型就不能执飞国内到洛杉矶等长航程的洲际航线.2) 预期效益.不同机型的运营成本存在差异，不同座舱布局的飞机载客能力也不同，同一架飞机执飞不同航班产生的收益贡献也不同，故航班计划编排也要综合考虑预期效益.这里的收益贡献是指航空公司从事经营活动所获得的税后收入减去使用某种机型执飞的变动成本，是衡量航班盈利能力的重要指标.

第二步是连线衔接.在确定每个航班的执飞机型后，两个航班能实现衔接的前提是满足以下两条规则：1) 同机场，即前序航班的落地机场要与后续航班的起飞机场相同.2) 满足最小过站时间，即前序航班降落与后续航班起飞之间在机场的停留时间要满足最小过站时间标准.除了最基本的衔接原则外，航空公司在编制航班计划时，也会根据实际业务需求增加航班衔接要求，常见的有3类：1) 保留原始衔接.航季航班计划编排并不是完全从零开始，有部分航班计划是延续上一个同航季的航班计划，这些航班保留了部分衔接信息甚至机组排班信息.2) 保留往返衔接.往返航班衔接是指从出发地到达目的地，然后再从目的地返回出发地的两个航班之间的衔接.这不仅利于机组排班，还可以减少机组在外站的过夜费用，对航空公司控制成本有重要意义.3) 紧凑衔接.航季航班计划会尽可能用最少的飞机数量编排最多的航班，使整个航班计划的飞机利用率最高.在此过程中，航空公司通常会将较短过站时间的两个航班优先衔接，使得编排的航班计划更为紧凑，可以集中利用空档运力，有利于增加航班执飞量，提高飞机利用率.如图1所示，假设最小过站时间为60 min，航班A、C的落地机场与航班B、D的起飞机场相同，图1(a)中航班A与航班B的衔接过站时间为3 h，航班C与航班D的衔接过站时间为4 h，这两个过站时间均较短，新增航班比较困难；
但是，航班C与航班B的衔接时间最短且满足最小过站时间，如图1(b)，如果优先将航班C与航班B衔接，过站时间为1 h，剩余的航班A与航班D的衔接过站时间长达6 h，在这6 h的空余运力中新增航班就相对容易.

图1 紧凑衔接航班计划示意图Fig.1Diagram of a tightly connected flight plan

A航空公司之前也是通过引进国外某系统来完成航季航班编排，但该系统只能在人工确定机型的前提下进行连线衔接操作，无法自动分配机型，自动化程度不高.为进一步提高航班计划编排效率，确保航班收益最大化，经过长期的业务总结和技术研究，A公司已探索出满足国内航司航季航班编排的解决方案.首先运用机型指派模型，在飞机数量最小化前提下确定每个航班执飞机型，使整体收益贡献最大化；
然后运用先进先出、后进先出、二部图、加权二部图等算法完成连线衔接.基于上述思路，本文列出以下假设条件：

1) 航季航班计划是以周为单位，不同自然周的航班计划均相同.因此，只需某个自然周的航班计划进行连线自动衔接，其余周期的航班计划重复衔接即可.

2) 航季航班计划的飞机连线不涉及具体机号，只需根据具体型号的飞机数量给出对应数量的飞机连线即可.

3) 所有运行约束都只考虑机型维度的运行约束，不考虑机号维度的运行约束.

4) 每个航班用不同机型执飞所产生的收益贡献为已知，贡献大小仅与机型有关，与航班衔接无关.本文使用的预计贡献是利用神经网络模型根据历史经营情况以及未来航班的销售情况进行预计，文中不作详述.

1.2 航班机型指派模型

机型指派模型以时空网络为基础.在时空网络中，横轴代表时间，纵轴代表机场，网络由若干航班组成，能够体现航班起飞、降落的时刻与机场.图2所示为一周的时空网络图，xd,f,k等箭头表示第d天用k机型执飞f航班，yd,a,k等节点表示第d天凌晨3:00时在A机场k机型的过夜数量(由于每天的航班计划中，最迟降落的航班时刻可能超过24:00，故本文选取凌晨3:00作为过夜飞机数的统计节点).机型指派模型最核心的思想是当航班起飞时必须有一架飞机可供使用，例如：对于机型k，当x1,4,k准备起飞时，机场B初始的飞机有y1,b,k架，进港的飞机有x1,5,k、x1,2,k、x1,3,k，离港的飞机有x1,1,k、x1,6,k.因此，要使x1,4,k有k机型可用，就必须满足y1,b,k+x1,5,k+x1,2,k+x1,3,k-x1,1,k-x1,6,k大于等于1.此外，为了航班计划的衔接能够循环延续，每个机场最终的机型数量分布要与该机场最初的机型数量分布一致，即需要图中y8,a,1=y1,a,1.

图2 时空网络图Fig.2Time-space network

1.2.1 参数设置

模型参数和变量设置如表1和2所示.

表1 模型参数

表2 模型变量说明

1.2.2 目标函数

对于航季航班分配机型通常考虑两个目标：一是将现有航班用最少的飞机数编排；
二是使航线网络收益贡献最大化.根据以上两个目标可以得出目标函数(1)和(2)：

(1)

(2)

对于多目标决策，主要思路是将多目标降维成一系列单一目标进行优化，常见的有抢占式优化和加权优化.抢占式优化需要根据目标的重要性多次建立模型，而加权优化只需建立一次模型，通过设置加权系数的正负性保证加权目标函数最大化或最小化一致，其中系数绝对值大小体现目标的重要性，这样就能减少建模次数，提高优化效率.在实际业务中，要优先保证以最小的飞机数排下所有航班，然后再调整机型增加贡献.因此，本文采取加权优化，可以列出目标函数(3)，加权目标是求最大化的问题，所以β的系数为负.经过测试，当设α=1，β=-10 000时，求解的最小飞机数、最大贡献与抢占式优化的结果一致.

(3)

1.2.3 约束条件

飞机连线的衔接要求覆盖每个航班且每个航班只能被指派1种机型执飞，如式(4)：

(4)

每个航班在起飞前必须有1架飞机可供使用，即如果xd,f,k=1，则对于d天在fj航班的起飞机场的初始飞机数加上在fj航班起飞前进港的飞机数再减去在fj航班起飞前离港的飞机数后，在fj航班离港时至少有一架k机型的飞机可供其使用，如式(5)：

(5)

在每个机场，每天的初始飞机数加上该机场的所有进港飞机数再减去该机场的所有出港飞机数要等于该机场的最终的飞机数，如式(6)：

(6)

这里：∀k∈K,∀a∈A,∀d∈D且d≠8.

机队平衡约束，在优化周期内，每个机场的初始机队分布要与最终的机队分布一致，如式(7)：

y1,a,k-y8,a,k=0,∀k∈K,∀a∈A.

(7)

机队规模约束，即每种机型在优化周期的初始机队数量应在用户设定的上下限之间，如式(8)和(9)：

(8)

(9)

每个机场对不同机型的保障能力不同，因此还需对每个机场每种机型允许过夜的飞机数量进行约束，如式(10)：

(10)

这里：∀d∈D,∀k∈K,∀a∈A.

1.3 连线自动衔接优化

通过航班机型指派模型，只能确定在使用最少飞机数的前提下每个航班的执飞机型，并且能使总体贡献最大化，但是机型指派模型并不能确定航班与航班间是如何衔接的.飞机连线的衔接本质是在每个机场为进港航班找到后续的出港航班，如图3所示两条飞机连线，实际上可以拆分成在杭州、广州、海口、沈阳和兰州机场的进港航班和出港航班的衔接.基于机场衔接思路，飞机连线的衔接算法主要有以下3种方法：先进先出、后进先出、加权二部图最佳完美匹配算法.

图3 飞机连线衔接本质示意图Fig.3Aircraft routing schematic diagram

1.3.1 先进先出和后进先出算法

图4 先进先出和后进先出算法Fig.4FIFO & LIFO algorithms

先进先出和后进先出算法如图4所示.假设最小过站时间为60 min，先进先出算法(图4(a))主要是在每个机场内，先进港的航班优先与满足最小过站时间标准的先出港航班衔接；
后进先出(图4(b))算法主要是在每个机场内，将后进港的航班优先与满足最小过站时间标准的先出港航班衔接.图4中，08:10为第一个出港航班，无前序航班；
12:00为最后一个进港航班，则无后续航班.先进先出的优点在于求解速度最快，飞机的过站时间分布较为均衡，过站时间相对较充足；
后进先出的优点在于飞机的过站时间分布较为极端，可以集中体现飞机的空余运力.尤其在市场旺季区间，使用后进先出法可以快速发现空余运力，有利于旺季增加航班量，提高飞机利用率.

1.3.2 加权二部图最佳完美匹配算法

每个机场的航班衔接实际上可以看作是一张二部图的指派问题，即将机场的每个进港航班指派给该机场的每个出港航班，根据衔接目的不同可以对二部图的边(衔接)进行赋权，得到一张加权二部图，再通过KM(Kuhn-Munkres)算法求得二部图的最佳完美匹配，即可得到满足要求的衔接方案.

连线衔接通常考虑保留原始衔接、往返衔接、紧凑型衔接3个因素.本文分别对原始衔接、往返衔接、紧凑衔接按0～100的不同得分赋值，其中：如果衔接为往返衔接(原始衔接)，往返衔接(原始衔接)得分即为100分，反之0分；
对于紧凑衔接得分，采用指数函数y=100·ax(0

1.3.3 指派飞机连线编号

在每个机场都建立好衔接之后，需要将每个航班赋值机型连线编号.首先建立3个集合：初始航班集合P、前序-后续航班集合PF、终止航班集合F.对于先进先出、后进先出算法，如果未匹配航班属于降落航班集合，说明该航班无后续航班衔接，属于终止航班集合F；
相反，如果未匹配航班属于起飞航班集合，说明该航班无前序航班衔接，属于初始航班集合P.对于加权二部图求解的结果，边权为-104的匹配在业务上是不合法的，在这些不合法的匹配中，将起飞的航班归入初始航班集合，将落地的航班归入终止航班集合.其次，遍历初始航班集合P中的每个航班，通过该初始航班在前序-后续航班集合PF中不断寻找后续航班，直到后续航班为终止航班，说明这些航班属于同一条飞机连线，为其编号，以形成完整的连线衔接方案.具体的连线衔接流程如图5所示.

2.1 评价指标

使用不同算法和同一算法不同参数求得的连线衔接方案会有差异.本文结合航空公司实际业务，从飞机日利用率、往返航班衔接占比、原始衔接占比、空档运力情况、过站时间裕度等指标，对比不同连线衔接方案的差异.

1) 飞机日利用率

飞机日利用率是从时间维度衡量飞机使用情况的重要指标，计算如式(11)所示.日利用率高说明在同等规模的机队下，能够充分利用主要固定资产，执飞更多的航班，为航空公司带来更高收益.

(11)

2) 往返航班衔接占比

衡量往返航班衔接占比高低的指标，如式(12)所示.

往返航班衔接占比=

(12)

3) 原始衔接航班占比

衡量原始衔接占比高低的指标，如式(13)所示.

100%.

(13)

4) 空档运力数量和时长

如前所述，空档运力是指每天6:00—24:00时期间，连续6 h及以上没有任何航班执行计划的飞机数和时长.例如，图1(a)中的空档数量和时长均为0，图1(b)中的空档数量为1，空档时长为6 h.

图5 飞机连线衔接及编号流程图Fig.5Aircraft routing flow chart

5) 过站时间裕度分布

过站时间裕度是指飞机实际过站时间与局方要求最小过站时间之差.过站时间裕度越小，说明航班衔接得越紧凑，有利于腾出空档运力，但应对前序航班延误情况的能力有限.过站时间裕度越大，说明航班衔接越宽松，不利于发现空档运力，但能够较好地应对前序航班延误的情况，整个航班计划的稳定性更好.本文中过站时间裕度不计过夜衔接的时间裕度.

2.2 实验结果

本文选取A航空公司每周共3 876个航班进行实证分析.在这些航班中，1 317个航班延续了上个同航季的航班计划，占总航班的34.0%；
1 028个航班的衔接属于往返航班衔接，占总航班的26.5%；
其余航班均未指派机型且均未确定衔接情况.航班计划共涉及4个主要基地、79个机场.

机型配置方面，本文应用cplex对机型配置模型进行求解，计算时间为16.3 s(cpu：i5-4570，主频：3.0 GHz，内存：8 GB)；
连线衔接方面，本文用Python程序求解，其中先进先出、后进先出算法求解时间不到1 s，加权二部图的求解约3 s，实现了大规模航班飞机连线的快速模拟(表3).对比从国外引进的现有系统，虽在机型确定的前提下连线衔接仅需5 s，但还要考虑机型调整的时间，采用人工，则需要1～4 h，若采用本文机型配置结果，还要增加人工录入时间.对比引言中提到的一体化模型需要数小时的求解时间，分阶段的模式在求解效率上具有明显的优势，均在20 s以内.

通过第一阶段机型指派模型结果(表4)可以得出，使用最少的飞机数为160架，飞机日利用率为8.40 h，贡献22 602.8万元，比现有系统编排结果增加收益贡献232.8万元/周，相当于1个航季可以增加收益贡献7 200万元.

为对比加权二部图不同参数的效果，本文制定了3个方案，如表5所示.方案一侧重往返衔接(简称“往返”)，方案二侧重保留原始衔接(简称“原始”)，方案三侧重紧凑衔接(简称“紧凑”).

在第一阶段机型指派的结果上，分别运用先进先出、后进先出、二部图、加权二部图等算法进行连线衔接.从往返航班衔接占比(图6)可以看出加权二部图往返方案的占比最高，达82.0%，较初始航班计划提高55.5个百分点，符合最初侧重往返衔接的得分设置.从原始衔接航班占比(图7)可以看出现有系统的占比最高，为33.7%，基本上保留了初始航班衔接的信息，其次为加权二部图原始方案，占比31.7%，仅比现有系统少2个百分点.从空档运力和时间(图8、表6)可以看出后进先出和加权二部图紧凑方案腾出的空档运力最多，空档运力数量达115个，比现有系统多4个，最高空档时间达883 h，比现有系统多10%.从过站时间裕度分布(图10)可以看出，后进先出和加权二部图紧凑方案在0～5 min衔接裕度上数量最多，其余时间段均为最少，也可以说明这两种算法倾向于紧凑型的衔接，而先进先出算法在20 min以上衔接裕度数量上均为第一，说明该算法倾向于较为宽松的衔接.对于二部图算法，在各个指标上均不突出，实际上二部图的结果只是求得一个可行解，并不能像加权二部图一样可以满足不同的需求倾向.

表3 机型指派模型和连线衔接算法运行时间

表4 机型指派模型运行结果

表5 衔接算法中加权二部图算法得分权重设置

图6 各衔接算法对往返航班衔接占比的影响Fig.6The impacts on proportion of round-trip flights among different aircraft routing algorithms

图7 各衔接算法对原始衔接航班占比的影响Fig.7The impacts on proportion of initial flights among different aircraft routing algorithms

图8 各衔接算法对空档运力数量的影响Fig.8The impacts on unused aircraft numbers among different aircraft routing algorithms

图9 各衔接算法空档运力时间的影响Fig.9The impacts on unused aircraft flight times among different aircraft routing algorithms

图10 各衔接算法对过站时间裕度分布的影响Fig.10The impact of transit time distribution among different aircraft routing algorithms

航季航班编排关系到航空公司飞机利用率和整体经营效益.本文以使用飞机数量最小化和收益贡献最大化为目标，通过运用机型指派模型，确定了新航季中每个航班的执飞机型，再运用先进先出、后进先出、二部图、加权二部图等算法，根据不同业务需求，求解满足条件的连线衔接方案，实现航季航班编排的完整规划.研究结果表明：

1) 先进先出算法倾向于宽松的衔接条件，在运力充足的情况下，采用此方法可以增加过站时间裕度，在发生航班延误时，能提高整个航班计划的稳定性.

2) 后进先出和加权二部图紧凑方案算法在腾挪空档运力方面效果显著，在运力较为紧张时，可以通过紧凑型的衔接，发现空档运力，有利于增加航班，提高飞机利用率.

3) 加权二部图可以通过对不同需求设置差异化权重，实现往返航班衔接、保留原始航班衔接、腾挪空档运力等方面的特定需求.特别是尽量做到往返航班衔接，并保留原始航班的衔接，更有利于机组排班等业务工作.

总结本文的研究创新点，主要有两个方面：

1) 本文提出的模型更侧重于航空公司的实际运营需要.采用现有系统编排航季航班，编排效率低、效果不理想；
使用一体化模型求解，运行时间较长，较适用于航班计划相对固定的国际航线编排，但国内民航市场的航班计划每天都可能发生变动，对连线衔接的求解效率要求很高，如果采取一体化模型，求解效率将无法满足实际需要.本文采用两阶段模型，可以快速求解满足需求的连线衔接方案，20 s以内就能完成每周3 800班左右的航班编排.

2) 本文创造性将机型配置模型和加权二部图算法结合应用.目前，二部图在连线衔接上主要用于解决单枢纽(或基地)航线网络的航班衔接问题，无法完全满足多枢纽航线网络的衔接，以及寻找运力空档、往返衔接等不同衔接目标的复杂实际业务需求.本文运用加权二部图，针对衔接目标不同进行差异赋权，在每个机场建立一张加权二部图，再通过KM算法求得二部图的最佳完美匹配，生成针对多枢纽航线网络不同衔接需求的衔接方案，对比现有系统，航班编排收益贡献可以提高232.7万元/周，改善效果明显.

本文以一个自然周的航班计划作为研究样本，通过重复单周的航班衔接方案，扩展至整个航季的航班计划，可以适用于航季航班计划的连线衔接优化.但到了航季中段，不同周期的航班计划可能存在差异，需要编排的航班周期就会大于1周(比如暑运).面对这种情况，算法上计算量和计算时间就会有所增加，后续可以考虑启发式算法等更加高效的优化算法，应用于优化长周期的航班计划.

猜你喜欢指派连线机型快乐连线快乐语文(2021年27期)2021-11-24快乐连线快乐语文(2021年11期)2021-07-20航站楼旅客行李提取转盘的指派优化分析物流科技(2021年1期)2021-07-05国内主流机型客舱声品质表现分析民用飞机设计与研究(2020年4期)2021-01-21快乐连线快乐语文(2020年36期)2021-01-14基于动态规划的指派问题网络方法及其应用怀化学院学报(2020年5期)2020-12-05不可小觑的4K机型，着重亮丽的色彩还原 光峰A300家庭影院技术(2019年11期)2019-12-09快乐连线快乐语文(2019年12期)2019-06-12渐趋成熟的旗舰机型 艾洛维V10家庭影院技术(2019年1期)2019-01-21特殊指派问题之求解算法对比分析电脑知识与技术(2017年17期)2017-07-14

推荐访问:衔接 连线 航班