民机机队航班指派与维修调度联合优化策略

丁雨童,郭晋之,邢雪琪,郑美妹,夏唐斌+,奚立峰

(1.上海交通大学 机械与动力工程学院,上海 200240;2.中国商飞上海飞机客户服务公司 运行支持技术研究所,上海 200241)

0 引言

民航工业的迅速发展给航司机队维修调度带来了巨大挑战[1]。作为飞机适航性保证,维修活动要求飞机在维修基地较长时间停场产生的维修机会中,执行覆盖飞机部件循环往复维修需求的大量维修任务。维修成本可达航司运营总成本的30%[2-4],因此机队维修调度需在满足飞机适航性的前提下,优化机队飞机各项维修任务的执行时间与地点方案,以降低维修成本,提升航司收益[5]。

目前,航司维修调度主要遵循独立于飞行路径规划的定检模式,在最大定检间隔约束下,自上而下地首先确定各飞机的定检日程,然后进行定检中的维修任务分配[6],现有研究相应聚焦于定检方案的优化。首先,定检日期与地点的决策往往以维修资源可用性与最大维修间隔为依据,在航班运营规划前优先确定飞机在维修基地的停场日程。DENG等[7]考虑机位与人工时等资源可用度及航空淡旺季运维需求差异,面向机队的单一维修基地定检日期进行决策优化。将定检决策问题抽象为马尔可夫决策过程,基于动态规划方法贯序输出定检方案。在此基础上,文献[8-9]进一步考虑天气条件、突发故障等不确定性干扰,建立鲁棒优化模型,最大限度减少已有定检方案的变动。为解决定检决策过程中的维数灾难问题,ANDRADE等[10]提出一种基于强化学习的优化框架,在保障飞机利用率的前提下显著提升求解速度。在定检日程决策的基础上,多属性、大规模的机队维修任务被分配于定检活动中形成最终的维修调度方案。LI等[11]针对单架飞机设计了基于属性相似度权重的维修任务聚类方法,通过将相似度高的维修任务组合执行,有效降低定检规划复杂度。WITTEMAN等[12]基于定检日程输入,将机队的维修任务分配问题抽象为装箱问题,并设计了基于任务优先级的启发式算法输出维修任务分配方案。ZHANG等[13]针对资源受限且高度不确定维修环境下的舰载机队维修任务分配问题提出了完全与部分重调度算法,以提高维修计划抗干扰能力。此外,定检的具体执行还需与维修人员、工具、备件等要素匹配[14],QIN等[15]根据给定维修计划进行多技能维修人员的调配优化以降低维修成本。

以上文献针对定检维修的关键环节,考虑维修资源、不确定扰动等因素进行了较全面的研究。然而,机队维修方案的实施需要飞行路径规划支撑,使飞机能够在维修执行日期抵达预定维修基地。因此,部分学者针对融合预定定检方案或间隔约束的机队飞行路径规划与航班指派问题进行研究[16-17]。LIANG等[18]将定期抵达维修基地的约束纳入机队飞机飞行路径规划中,获得满足适航性的飞行路径方案。MAHER等[19]针对短期维修资源不确定情况下的航班指派问题,提出一种灵活的前瞻调度方法,在保障次日维修需求前提下隐式地满足后续两天的维修需要,最大限度降低失修风险。此外,CUI等[20]针对飞机延误概率对考虑维修约束的飞行路径影响建立了鲁棒优化模型,在满足维修间隔约束前提下降低了飞机延误成本。

综上,定检模式下机队维修调度问题已得到广泛研究,但相关文献大多局限于维修方案制定的单一环节,与机队运营与维修调度实践仍存在差距。首先,飞机抵达维修基地仅产生维修机会,而维修任务的分配则是维修调度最终方案[21]。每架飞机都有大量维修任务,由于维修历史差异,飞机个体维修需求存在较大区别。机队维修需在飞机个体大规模维修任务分配层面进行调度,而仅关注群体普遍定检间隔的停场决策忽略了飞机维修个性化需求。此外,由于维修活动只在维修基地进行对航班指派全局规划的限制,及飞机个体维修方案执行对适航性的影响,局限于单一维修基地的维修任务分配易导致维修计划与航班运营冲突。航班指派与维修调度需进行协同规划,仅以定检间隔为约束的飞行路径难以实现飞行路径与维修调度方案的全局优化考虑。最后,维修基地有限的维修资源由多架飞机共享,维修机位、人工时等差异化的资源能否匹配飞机个体维修需求,也将很大程度影响维修基地选择与维修任务分配决策[22-25]。

规划粗放的定检模式易导致过度维修、飞机利用率低、维修与飞行路径冲突等问题,其经济性较低[26-27]。因此,国内外航司已开始探索利用飞机日常夜间维修基地停场执行维修任务,形成维修任务日常执行(Maintenance Task Daily Execution,MTDE)模式。该模式能够突破定检局限,大幅减少飞机日间维修停场时间,正逐步应用于实践,但也为维修调度优化提出更高要求。在上述建模难点的基础上,航班指派方案不局限于与定检方案匹配,而需主动为每架飞机提供充足维修机会,进一步提升了问题复杂度。因此,有必要针对MTDE模式开展机队航班指派与维修调度联合优化,以弥补定检模式下维修调度经济性的不足。

本研究面向MTDE模式下机队维修调度的优化目标,综合考虑飞机个体维修任务层面维修需求和机队整体航班运营与维修资源共享约束,围绕联合调度方案经济性提升,提出一种新的航班指派与维修调度联合优化策略(Collaborative Optimization Policy of Tail Assignment and Maintenance Scheduling,COPTAMS)。为应对耦合飞行路径与维修方案建模难点,借助飞行路径中涵盖的维修机会的交互枢纽作用,通过引入维修机会节点定义,创新改进了常用于航班指派问题的连接网络模型框架以统筹考虑航班分配与维修调度,并将问题抽象为多商品网络流问题建立了整数规划模型。针对大规模模型的求解困难,将问题进行分解并建立了高效的两阶段求解方法,基于满足运营约束且提供充足维修机会的航班指派方案生成,依据维修任务剩余可用间隔对维修任务在维修机会中进行合理分配,相较航司人工排程现状,在较短时间内获得经济性显著提升的航班指派与维修调度方案。COPTAMS能够改善航班运营与维修计划的脱节,支持航司在MTDE模式的调度实践,有效降低机队运维成本。

1 问题描述

本文面向一支执飞国内航线的机队,开展航班指派与维修调度的联合优化,该机队事先将被分配规划期内需执飞的日间航班任务。航班运营保证所有航班均指派给机队中的飞机,且同一飞机连续执飞的航班序列满足时间与路径的连续性。由于机龄、燃油消耗等运行特征的差异,同一航班指派给不同飞机的成本有所区别。飞机需通过执行大量维修任务确保适航性要求。各项任务在相应维修间隔约束下循环往复执行,每次执行将会消耗对应维修成本。飞机维修活动受限于飞行路径规划,只有在飞机抵达维修基地停场产生的维修机会中,维修任务才得以在基地资源承载能力内进行分配。故机队航班指派与维修调度联合优化方案需在满足航班全覆盖与执飞连续性的运营约束、飞机适航性要求与维修资源承载限制的维修约束前提下,为每架飞机指派航班任务,并提供机队所有维修任务在维修基地的分配执行计划。本文主要符号说明如表1所示。

表1 主要符号说明表

传统定检维修模式规划复杂度低,但整体方案经济性较差。首先,飞机长时间日间停场维修需支付场地费用且无法执飞航班,飞机利用率及运营收益由此下降;而维修任务只能局限分配到固定的定检日程中,易导致维修任务过度提前执行,增加长期维修成本;同时,定检方案制定独立于飞机路径,易导致航班指派与维修调度冲突,出现成本高昂的航班取消或空载飞行状况。而MTDE模式的应用能够改善定检模式的不足,通过航班指派方案为飞机提供日常夜间停场的维修机会,维修任务分配灵活且飞机利用率显著提升。

COPTAMS旨在优化MTDE模式下联合调度方案的经济性指标,包括航班指派成本与维修成本。航班指派成本即所有航班由相应飞机执飞的成本之和。为对维修方案经济性进行长远考量,维修成本包括维修提前成本与维修额外执行成本。规划期内维修任务实际执行总成本为所有任务各自执行次数与对应成本乘积的总和,从长远看,经济性较高的维修方案应在适航性要求下,尽量减少过度提前维修。不同维修任务分配方案可能对应相同执行次数,因此应用维修提前成本dc将维修提前程度纳入优化模型中。对于飞机a的维修任务m,其实际执行日期越接近下一执行期限,维修提前程度越低,在第d(d∈D)天执行对应的维修提前成本dcamd计算如下:

(1)

而当维修任务已达执行期限且基地剩余人工时无法满足其执行需求时,需通过维修资源与人员调配付出额外成本执行任务以保证适航性。

2 改进连接网络模型框架及联合优化模型建立

2.1 改进连接网络模型

航班指派与维修调度联合优化的关键在于突破协同考虑飞行路径与维修调度障碍并进行统筹规划。由于维修任务仅能在维修基地执行,飞行路径中涵盖的维修机会即成为了二者间交互枢纽。本节通过引入维修机会节点,创新改进了常用于航班指派问题的连接网络(Connection Network,CN)模型框架,实现了航班指派与维修调度在同一框架中的统筹规划。

CN框架是由航班节点V与连接弧E构成的有向网络G(E,V)。航班节点代表待执飞的航班任务,其节点属性包括航班的起落时间、起落机场;节点间的连接弧则代表两个航班能否由同一飞机连续执飞的判断:假设航班节点i,j被一条弧连接且弧由i指向j,则航班i,j必须满足:航班i的降落机场与航班j的起飞机场相同,航班i的降落时间早于航班j的起飞时间且二者之间留有基本航前准备时间。此外,网络中还包括源(Source)和汇(Sink)两个虚拟节点,表示所有飞机的起点和终点。基于CN框架,航班指派方案将CN中所有航班节点分配给各架飞机,每架飞机分配的节点由弧顺序连接,形成由源到汇的可行路径。相较航班指派问题其他模型框架,CN以较少元素进行问题完整表示,进而减小问题规模,因此采用CN作为模型构建的基础框架。

然而,CN框架仅含航班元素,在指派航班时忽略了适航性要求,故需要对CN进行调整。基于CN框架应用于航班指派的思想,通过在网络结构中将维修活动纳入考虑,即可实现机队的航班指派与维修调度的联合规划。根据飞机的维修活动仅能在维修基地进行的约束,飞机在执飞目的机场为维修基地的航班后,便拥有能够在当前维修基地进行当日过夜维修决策的机会,即维修机会。将飞机各个维修任务在维修机会是否执行进行决策,即可形成最终的维修调度方案。因此,维修机会作为飞行路径与维修方案的关键交互枢纽,本文将其抽象为维修机会节点并纳入CN网络结构中,形成了改进连接网络(Modified Connection Network,MCN)模型。一个维修机会节点表示一个维修基地在当天夜晚为各飞机提供的过夜维修机会,其属性包括所在机场、维修起止时间、维修机位数、可用人工时。类似地,其与航班节点的连接代表二者能否由同一飞机连续执行的判断:若航班节点i与维修机会节点j连接且由i指向j,则i,j应满足:i的降落机场与j所在的机场相同,且i的降落时间不晚于j的维修开始时间;若由j指向i,则i的起飞机场与j所在的机场相同,且i的起飞时间不早于j的维修终止时间。

下面通过示例展示CN与MCN的应用及区别。考虑表2航班时间表及维修机会信息,涉及两天往返A、B两机场的航班,B为维修基地。其中:a+,a-,a分别为航班起降机场、维修机会所在机场,t+,t-分别为航班起飞或维修开始时间、航班降落或维修结束时间,D1,D2分别表示第一、二天,航前准备时间为30 min。

表2 航班时间表与维修机会信息示例

图1 CN与MCN框架示例

2.2 整数规划模型建立

基于MCN框架,建立COPTAMS整数规划模型如下:

(2)

(3)

∀j∈N/{sink,source};

(4)

i=source,i′=sink;

(5)

(6)

(7)

(8)

∀a∈A,∀i∈N,∀j∈B;

(9)

∀a∈A,∀m∈M,∀d∈D;

(10)

xaij∈{0,1},∀a∈A,∀i,j∈N;

(11)

yami∈{0,1},

∀a∈A,∀i∈B,∀m∈M。

(12)

该模型的决策变量包括xaij与yami,辅助变量包括eamd及dcamd,其余均为模型的输入参数。目标函数(2)表示最小化联合调度方案的经济性指标。约束(3)为航班覆盖约束,即每个航班均需指派给机队中的一架飞机。约束(4)～约束(6)为MCN网络流平衡约束,其中约束(4)表示网络中除源和汇所有节点的出入流量相等;约束(5)表示离开源与进入汇的流量相等;约束(6)表示每架飞机须从源节点出发,且各飞机首个执飞航班从其初始机场起飞。约束(7)～约束(10)为维修调度约束,其中约束(7)与约束(8)表示维修机位与可用人工时限制;约束(9)表示维修任务只能在飞机到达维修机会节点时进行;约束(10)定义中间变量eamd。约束(11)与约束(12)为决策变量取值范围。通过在小规模问题上的精确求解,验证了模型的有效性与可靠性。

3 联合调度方案两阶段求解方法

2.2节建立了机队航班指派与维修调度的联合优化模型,而由于模型同时涵盖航班指派与维修任务执行决策变量,模型规模过大,直接使用Gurobi等商业求解器耗时过长,难以满足实践需求。为在可接受时间内得到质量较高的调度方案,本节基于对原问题的分解,设计了COPTAMS两阶段求解方法,具体如下。

3.1 阶段一:维修机会导向的航班指派优化

借助维修机会在航班指派与维修调度的交互枢纽作用,首先考虑飞机个体维修需求,生成满足运营约束且包含充足维修机会的航班指派方案,以进行后续维修任务层面分配。为此,第一阶段求解建立维修机会导向的航班指派优化模型如下。

(13)

s.t.

式(3)～式(7),

∀k∈K,∀d∈D;

(14)

xaij∈{0,1},∀a∈A,∀i,j∈N。

(15)

该模型的决策变量为xaij,不包含辅助变量,其余均为模型的输入参数。航班指派成本(13)为优化目标,航班运营、网络流平衡、维修机位约束(3)～约束(7)得到保留,其余维修约束被调整为维修机会分配需求约束(14):对于任一飞机任一类型的维修任务,将该类任务维修间隔最小值设为时间窗长度,飞机须在时间窗内至少一次经过具备该类任务维修能力的维修基地,通过时间窗在规划期内的滚动,保证了飞机个体维修任务要求,航班指派方案能使其拥有对应维修能力的充足维修机会。约束(15)为决策变量取值范围。该模型仅包括节点分配(包括航班与维修机会节点)决策变量xaij,在模型简化基础上保证了基本维修需求,求解速度显著提升。

3.2 阶段二:维修任务分配高效启发式算法

基于第一阶段的航班指派与维修机会方案,第二阶段综合考虑飞机个体维修任务执行状态与维修资源共享机制,将维修任务在各维修机会进行择优分配与状态更新交互,求解经济性较优的维修调度方案。

首先,满足维修间隔且维修提前成本最低的方案应将维修任务在其期限日期执行。由于维修机会日期、维修资源限制,维修任务大多无法恰好分配在期限日期,而使任务分配尽可能接近期限日期则能降低维修提前成本。因此,在每个维修机会,通过判断各维修任务的剩余可用间隔,其中在当前维修机会已到期、即将在下一维修机会前到期的维修任务优先执行,若人工时消耗完毕则调配额外维修资源;对于剩余维修任务,计算其剩余可用间隔并据此由小到大排序,设置剩余间隔阈值,大于该阈值的任务无需在当前维修机会过早执行,将其从备选执行序列中剔除;若维修基地仍有可用人工时,则顺次执行排序后的维修任务,直至人工时使用完毕。随后更新各任务执行状态,计算下一执行期限,在后续维修机会重复上述判断步骤直至规划期结束。上述方法的机理保证了飞机适航性要求,同时任务剩余间隔得到了充分利用,缓解了过度维修,有效降低长期维修成本。

3.3 算法评价

第一阶段应用Gurobi求解器进行成本最优的航班指派方案精确求解,因此针对本阶段的算法评价以模型规模为标准。由于模型规模可以由决策变量与约束的数目衡量[28],相较于2.2节建立的机队航班指派与维修调度的联合优化模型(决策变量数目为|A|×CO+|A|×|M|×|B|,约束数目为|F|+|A|×[|N|×(1+|B|)+|M|×|D|+1]+|B|×(|K|+1)),该模型仅包括节点分配(包括航班与维修机会节点)决策变量xaij(数目为|A|×CO),且约束数目减少为|F|+|A|×(|N|+|K|×|D|+1)+|B|。由于机队飞机数目|A|较少发生变动,机队航班指派与维修调度联合优化的问题规模变化主要来自于规划期时长|D|、航班任务数|F|及维修任务数|M|。而在维修实践中,每架飞机维修任务可达百余项,对于问题规模影响最为显著。本阶段模型保留的决策变量xaij数目远小于yami数目,同时维修相关约束数量大幅降低,因此在处理大规模问题时将不受维修任务数目增长影响,实现成本最优的航班指派方案快速生成。

在第二阶段,算法执行时间仅随着输入的总维修任务数与规划期天数变化而线性变化,其时间复杂度可表示为O(n)。机队维修调度问题本身具有大规模特性,而本阶段所提方法即使面对规划期长、机队规模大、维修任务数量多的维修任务分配问题,也能够实现较快的求解速度,满足机队维修调度实践需求。

3.4 航班指派与维修调度联合优化求解步骤

综合上述求解过程,COPTAMS求解步骤如下所示:

步骤1获取航班时间表、维修基地信息、机队维修任务、飞机初始位置等参数,构建MCN框架,建立维修机会导向的航班指派优化模型。

步骤2对模型精确求解,得到规划期内机队航班指派方案及维修机会,即各飞机在MCN中的节点路径。

步骤3从规划期第一天开始,寻找当日MCN中飞机经过的维修机会节点。若当日所有维修机会节点均无飞机经过,则直接进入次日继续寻找。

步骤4从当日首个维修机会节点开始,获取抵达该节点飞机的维修任务信息,计算各任务剩余可用间隔及执行期限,按剩余可用间隔由少到多顺序排列。进一步获取该节点各飞机下一维修机会节点日期,判断各项任务执行期限是否在规划期内,若不在规划期内则停止对该任务的决策;若在规划期内且早于所属飞机的下一维修机会节点日期,则将该任务于当前维修机会节点执行,消耗相应人工时。

步骤5根据剩余间隔阈值进行任务剔除,对剔除并排序后的任务,从首个任务开始,判断当前维修机会节点的剩余可用人工时能否执行此任务。若是,则安排该任务在当前维修节点执行;否则不执行该任务,进行下一任务的判断,直至所有任务判断完毕;转步骤4进行下一维修节点的任务分配决策过程,直至当日所有维修节点决策完毕。

步骤6获取当日所有执行的维修任务进行状态更新,转步骤3搜索次日维修机会节点,直至规划期内所有维修节点搜索完毕。COPTAMS求解步骤示意如图2所示。

图2 COPTAMS示意图

4 实例分析

为验证本研究提出的COPTAMS方法,选取一组国内某航司10架客机组成的机队实例进行分析,各实例信息及成本相关参数如表3和表4所示。各实例在问题规模、航班任务、维修起始状态、规划时长、维修基地方面均有所差异,全面验证优化方法应用性能。本章所有实例分析计算均使用MATLAB R2020b以及Gurobi 9.1.2进行,PC处理器为Intel(R) Core(TM) i7-10510U CPU @ 1.80 GHz,内存大小为4 GB。

表3 机队运营实例信息

表4 成本相关参数设置

表5 实例求解结果

由表5可知,大部分实例求解时间均值与极大值均在10 min内,实例3、12的航班任务与维修基地数据较复杂,但仍可在30 min内生成联合调度方案。而与本研究合作的航司维修调度部门目前仍采用人工定检排程的方式,进行相同规模机队15天内航班指派与维修任务规划耗时约2 h,而若规划时长进一步扩大至30天需耗费超过3 h。此外,为验证本研究所提维修任务分配方法的竞争性,基于阶段一的最优节点分配方案,选取文献[12]中提出的相关算法进行效果比较如表6所示。该文献研究机队在单一维修基地、固定维修间隔下的维修任务分配问题,依据装箱问题基础求解思想“worst-fit”,仅据任务间隔计算各任务分配优先级,构建启发式求解算法进行维修任务在维修活动中的分配。在联合优化场景下,本研究中维修任务分配方法能够全面考虑后续维修机会间隔灵活变动及任务执行状态更新,具有更优的维修经济性表现。故COPTAMS方法可高效得到机队飞机的航班与维修计划,满足机队调度需求。

表6 维修任务分配算法成本对比

而为验证MTDE模式相较传统定检模式的经济性优势,将定检模式的航班指派与维修调度同样应用于本章的实例进行总成本对比。在定检模式下,机队各架飞机每间隔vkmin天需要抵达具有k类维修任务能力的维修基地进行日间停场维修。根据航司实际情况,运营人需为日间停场支付停场费用以及飞机利用率降低的惩罚成本。每次定检执行维修任务决策依据仅为维修间隔要求,即下次定检之前到期的维修任务均在当前定检执行,其他任务则不执行。各实例计算得到的优化航班指派成本obj1、维修成本obj2以及维修调度原因导致航班取消的数量q如表7所示,表中定检模式下的obj1包括了航班取消的收入损失,obj2包括了日间停场维修场地费用。总成本TC柱状图如图3所示。

图3 两种维修模式的总成本对比图

表7 两种维修模式的成本对比

由表7和图3可知,MTDE模式下航班指派成本、维修调度相关成本均优于定检模式:

(1)航班指派方面 定检模式需要飞机在指定日期抵达维修基地的约束破坏了航班指派全局最优性,且机队中多架飞机同时定检会导致部分航班无法执飞而产生高昂的航班取消惩罚成本;MTDE模式避免了飞机的日间维修停场,机队运营部门能够灵活调配飞机执飞航班,使所有航班均被覆盖,因此相较定检模式,在航班指派成本上具有优势,平均节省2%航班指派成本。

(2)维修调度方面 固定的定检日程局限了维修任务分配方案,且分配决策依据仅为适航性要求,易导致过度维修,同时日间停场也需为占用维修机位而支出费用;而MTDE模式下,综合考虑飞机路径及维修需求能灵活安排维修机会以分配维修任务,在保证适航性前提下兼顾维修经济性指标,从而得到成本更低的维修调度方案,同时避免日间停场费用支出,平均节省51%维修成本。

从总成本的视角看,由于在航班指派与维修调度进行了联合优化,MTDE模式相较定检模式平均节省了11%总成本。综上,面对MTDE模式下机队维修调度优化需求,COPTAMS能够高效输出航班指派与维修调度联合优化方案,帮助航司改善传统定检模式运营与维修计划脱节、调度效率与灵活性差、飞机利用率低、停场时间长等难题,显著提升经济性指标。

5 结束语

本研究面向MTDE模式下机队维修调度经济性优化需求,综合考虑维修任务层面的飞机个体维修需要及机队整体航班运营与维修资源分配,提出了机队航班指派与维修调度联合优化方法。通过引入维修机会创新提出MCN框架以进行统筹规划,以联合优化方案经济性指标为优化目标,全面考虑航班覆盖、执飞连续性、飞机适航性、维修资源限制、网络流平衡等约束,建立了问题的整数规划模型。首先通过维修机会导向的航班指派优化,在保证飞机充足维修机会的前提下得到航班指派成本最优的节点分配方案;随后构建维修任务分配启发式算法,通过对任务剩余可用间隔的排序筛选进行任务择优分配,在保证飞机适航性前提下有效降低长期维修成本。

航司机队实例分析结果验证了COPTAMS方法能够高效得到总成本优化的调度方案,帮助解决航司人工进行定检调度效率与经济性不足的难题。未来工作可将更复杂的机队运营与维修场景纳入优化框架中,如跨日长途航班指派、飞机长期入库拆解大修需求、维修基地人工时资源变动等。