0 引言

随着航空市场规模不断扩大,航空公司高效管理各项资源的压力与日俱增,如何在复杂多变的环境下,进行有效的资源调配,降低运营管理成本,成为航空公司亟待解决的问题。近15年来,机组排班自动化软件的供应商均为国外厂商,这些产品考虑通用的业务规则,不适用于对国内航空公司机组排班的业务场景。对此,本文考虑国内航司复杂的人员搭配业务要求,从业务和模型算法角度提出解决方案,有助于智能化机组排班产品在中国航空公司的落地。

1 机组人员派遣方案

机组人员派遣问题(Crew Rostering Problem,简称CRP)是航空调度优化领域的经典问题,派遣结果直接影响航空公司的机组人员满意度和机组服务水平^[1]。按照求解算法分类,已有研究主要分为基于精确算法和基于启发式算法两类。基于精确算法的研究主要包括运用列生成算法^[2]、拉格朗日松弛^[3]或双层规划^[4]等分解算法求解;基于启发式算法的研究主要是对传统的遗传算法、模拟退火、局部搜索等算法进行针对性地改进^[5-10]。

机组人员派遣问题需要根据《大型飞机公共航空运输承运人运行合格审定规则》第121条P章规定的和航空公司特有的机组排班规则,确定机组人员具体执行飞行、置位、备份、训练等任务的方案。以飞行任务为例,机组人员从出发机场到目的机场执行一次起降的过程为一次飞行任务,即航段粒度任务。为了简化问题的求解难度,通常不直接为机组人员指派航段粒度的任务,而是首先进行任务环优化,将航段粒度的任务聚合为任务环粒度的任务,即从基地机场出发回到基地机场结束的多个航段任务,再进行机组人员任务环任务派遣。在机组人员派遣问题中,人员搭配规则可以理解为机组各成员间的组合规则,可细分为:机组人员级别、性别、年龄、语言、资质等搭配规则。国内外航司在该规则的业务要求和解决方案上存在显著区别。

国外航司通常只对各个级别的人员数量存在要求,如:一般情况下,执行波音737机型飞行任务的飞行机组成员最低配置为2人,包括机长(Captain,简称CAP)级别1人,副驾驶(First Officer,简称FO)级别1人。

国内航司对每个飞行任务上的人员数量要求多样,表现为:每一个飞行任务存在一个可行的级别搭配方案集合,该集合中同时存在需要2名或3名飞行机组成员的方案,在此基础上,对各机组人员的子级别之间的搭配方案进行限制,通过需求梳理,将为所有可行搭配方案表示出来,作为法规检查时的规则,举例见表1。

在表1的案例中,CAP细分为C15、C14、···、C1共15个子级别,级别依次由高到低。FO分为F5、F4、···、F1共5个子级别,级别依次由高到低。每一行代表一种可能的搭配方案。

2 模型和算法设计

2.1 一般的机组人员派遣问题解决方案

在机组人员派遣问题中,航空公司主要关注任务环的完成情况和机组人员之间工作、休息等指标的公平性。机组人员派遣问题本质上属于考虑任务时空约束的指派问题。对于一般机组派遣问题而言,任务所需要的机组人数固定,级别搭配要求明确,该类问题可以直接通过基于时空网络的集合覆盖模型刻画,采取基于列生成或拉格朗日松弛等分解策略求解。

该方案不能解决国内机组排班业务的特殊搭配规则。主要原因有:(1)需求覆盖约束无法创建:集合覆盖模型中的任务需求覆盖约束的右手项表示任务需要被覆盖的次数。但是,任务所需机组人数的不固定导致该约束的右手项不明确,此时需要增加成倍的辅助决策变量和约束辅助建模,从而导致模型求解困难。(2)机组搭配规则难以刻画:列生成或拉格朗日松弛等分解算法的求解策略是将原问题分解为限制主问题和最短时空路径子问题,主问题主要刻画问题的各类约束(如:任务需求覆盖约束),子问题主要限制时空路径所消耗的资源(如:机组成员张三的连续工作和休息规则),主问题子问题间不断迭代直至收敛,进而通过收敛信息设计最优可行解求解算法。但是,机组搭配规则的引入导致各子问题之间强耦合,因此需要在主问题中增加不可行搭配的约束,但由于不可行搭配情况过多甚至无法全枚举出所有方案,导致该求解策略很难求解带有搭配规则的机组人员派遣问题。

2.2 考虑复杂人员搭配规则的机组人员派遣模型

根据国内航司机组人员搭配规则,建立机组人员派遣问题模型。定义为所有需要考虑公平性的指标集合,公平性通常指同一级别下各机组人员之间的指标公平,为所有机组人员的集合,为机组人员所有的级别集合,为所有任务环的集合,表示级别的所有机组人员集合,为级别需要满足公平性的第k类指标的标准差。

其中, $q_{km}^0$为机组人员第类指标的初始值。$\overline{q_{kr}^0}$为级别r人员第k类指标初始值的均值。q_kp为任务环p的第k类指标值。x_mp为决策变量,若人员m执行任务环p,其值为1;否则为0。公平性指标,包括每个机组人员分配的飞行时间均衡,休息时间均衡,过夜次数均衡,特殊航班(如红眼航班,国际航班)数量均衡等。

定义决策变量x_mpt,当人员m在第t天执行任务环p,其值为1,否则为0。决策变量y_pt表示第t天任务环p缺少的人员。对每个任务环p∈P, $D_p^A$表示A类资质人员的需求数, $D_p^B$表示B类资质人员的需求数, $D_p^C$表示C类资质人员的需求数。M_A表示具有A类资质的人员,M_B表示具有B类资质的人员,M_C表示具有C类资质的人员,A类资质为普通等级资质,C类资质为最高等级资质,当资源不足时,C类资质的人员可以降级(Downgrading)执行A类和B类资质任务。L为最长工作天数,T表示规划周期。建立如下整数规划模型:

目标函数为最小化总成本(公式(2)),包括人员任务匹配成本和公平性成本,w ₁代表任务完成情况的权重,w ₂代表公平性的权重,w ₂应远大于w ₁。公式(3)为每个任务环上机组人员数量最低约束,公式(4)表示一个人员只能执行一个排班计划。公式(5)表示决策变量之间的关系,公式(6)表示第t天每个机组人员每天只能在一个任务环上。公式(7)表示在互斥集$M_{S_n}$的人员,不能同时执行任务p,该互斥集通过机组人员搭配方案划分得出。公式(8)表示连续飞行天数不能超过最大限制,公式(9)表示决策变量约束。

2.3 算法设计

针对上述模型,设计基于变邻域搜索算法和模拟退火算法(VNS-SA)的混合算法求解该问题,首先给出算法流程图,然后阐述初始解生成和邻域构造两个阶段的邻域搜索启发式策略。变邻域搜索算法(Variable Neighborhood Search,简称VNS)是一种改进型的局部搜索算法。在搜索过程中不断改变邻域结构集来拓展搜索范围,从一个邻域的局部最优解跳到另一个局部最优解,在集中性和疏散性之间达到很好的平衡,直至收敛到一个可接受的近似最优解。模拟退火算法(Simulated Annealing,简称SA)从某一较高初温出发,随着温度不断降低,和温度相关的概率突变机制会保证跳出局部最优区域从而搜索更优的解,保证了发现全局最优解的可能性。

本文将VNS和SA结合保证最终解的质量。对于一个问题P,假设当前解表示为Sⁱ,当前解目标值为Zⁱ,全局最优解表示为S^*,全局解目标值为Z^*,基于Sⁱ使用第k种邻域结构所构造的邻域表示为N_k (Sⁱ),算法流程图见图1,算法步骤如下:

步骤1:令k=1,调用初始解算法生成问题P的初始解S⁰,计算初始解目标值Z⁰,令Sⁱ=S⁰,S^*=Sⁱ, Zⁱ=Z⁰, Z^*=Z0。

步骤2:基于Sⁱ构造N_k (Sⁱ)得到新解Sⁿ,并计算新目标值Zⁿ。

步骤3:若$Z^n<Z^{*}$,则令$S^i=S^n,S^{*}=S^n,Z^i=Z^n,Z^{*}=Z^n,k=0$;否则,若$Z^n<Z^i$,则令$S^i=S^n,Z^i=Z^n$;否则,调用模拟退火算法,若接受,则令$S^i=S^n,Z^i=Z^n$。

步骤4:判断算法是否停止,若是,则算法结束,输出S^*和Z^*;否则,k=k + 1,进入步骤2。

2.3.1 初始解生成

本文分别对任务环、机组成员以及任务环和机组成员的匹配进行分值评估,根据分值来进行指派,生成初始解。

假设P表示任务环集合,M表示机组成员集合,Q_P表示任务环优先队列,Q_M表示机组成员优先队列,邻域N_k (Sⁱ)规定的最大总机组人数限制为U。

步骤1:将所有任务环P加入Q_P,按任务环重要性分值调整Q_P。

步骤2:若Q_P为空,则算法停止。

步骤3:弹出队首元素$Q_p^0$。

步骤4:将所有机组成员加入Q_M,计算所有机组成员$Q_p^0$和的匹配度分值,更新Q_M。

步骤5:若Q_M为空,转到步骤2。

步骤6:从Q_M中弹出队首$Q_M^0$。

步骤7:检查是否可以将$Q_M^0$指派给$Q_p^0$,这里需要特殊检查机组人员的搭配规则。若是,指派;否则,转入步骤5。

步骤8:判断$Q_p^0$所需组员是否被排满。若是,转入步骤2;否则,转入步骤5。

2.3.2 邻域构造

VNS的目的是在搜索过程中系统地更改当前解的邻域集,以扩大搜索范围并找到更好的解。在实际业务中,主要关注任务的覆盖率和机组人员的工作均衡性指标,受实际业务启发,本文设计了三种邻域结构用来构建新解。

1) Move

选择两个机组人员,从两人的航段列表时间中划定一个时间窗口,将其中一人在该时间窗口内的航段移动到另一个机组人员身上,如图2所示。

如图2所示,原有的解中,Crew2的任务数量较多,Crew1的任务则较少且分布较为稀疏。经过Move构造得到的新解中,Crew1的任务量得到增加,两个人的任务分配更加均衡。同时,Move还扩大了Crew2的可分配时间窗,有利于提升覆盖率。这种邻域结构在初期搜索过程效果最佳,因为此时期公平性指标提升空间较大。

2) Swap

选择两个机组人员,从两人的航段列表时间中划定一个时间窗口,将两个机组人员在该时间窗口内的航段进行交换,如图3所示。对于两个机组人员Crew1和Crew2,前者的任务量较少,而后者的任务量相对较多,在经过Swap之后,两人的任务量相对来说变得更加均衡,从而提升机组人员整体的任务量均衡性指标。

3) Rebuild

选择两个机组人员,将两个机组人员航段进行打散,然后重组为两个新的航段序列并分配给机组人员,如图4所示。

一般的邻域搜索仅仅是对原有的解进行微调,对于大规模的实际问题来说,由于存在大量的约束条件,找到一个可行解十分不易,要想从一个已有的可行解经过微调,跳转至另一个可行解的可能性也不高,这就造成邻域搜索的成功率较低,且更容易陷入局部最优。因此,Rebuild操作考虑对已有的解进行较大程度的破坏,可以提供更大的可操作空间来搜索另一个可行解,为别的邻域构造方法提供更大的可能性,从而跳出局部最优。

如图4所示,对于给定的两个机组人员Crew1和Crew2,任务可交换和移动的空间不大,如果采用Move和Swap方法,成功率较低。此时,如果采用Rebuild,对二者的任务打散重排,可以增大获得可行解的概率。

3 案例

以经过脱敏处理后的某国内航空公司和某国际航空公司实际运营数据为例,对本文建立的考虑复杂人员搭配规则的机组人员排班优化模型和设计的求解算法进行验证和分析。实验硬件环境为AMD Ryzen 7 4800H 2.9GHz,16GB的个人计算机。航段时空网络创建、任务生成、任务时空网络创建及变邻域搜索算法,均基于Visual Studio 2017开发平台C++语言编程实现。

算例实验测试了国内航空公司和国际航空公司两种场景,其中国内航司数据包括5 951个任务环,国际航司数据包括541个任务环,计划周期均为31天。任务环计划数据如表2所示。人员搭配规则集合如表3所示。

国内航司针对某些特定搭配情形,要求在连续7天的工作中存在一个连续时长的休息期,根据不同搭配情形,相应连续时长的休息期如表4所示。

国内航司针对不同的级别与搭配情形,要求相应的飞时或执勤期不得超过给定的上限,详细信息如表5所示。

算法配置参数设置如表6所示。

分别针对国内航司和国际航司的情形进行测试,测试结果如表7和表8所示。其中表7为国内航司优化结果,求解时间为332s;表8为国际航司优化结果,求解时间为65s。

本文提出的优化方法可以在较短的时间内求解考虑复杂人员搭配规则的机组人员排班问题。由表7可以看出,算法在考虑复杂人员搭配规则情况下,能给出飞时全覆盖的高质量求解方案,表明该算法具有较高的特殊场景应用能力。从表8可以看出,即使不考虑复杂人员搭配规则,算法也能求解出飞时全覆盖的解,表明算法具有较高的推广性。另一方面,结合表7和表8的对比结果可以发现,在考虑复杂人员搭配规则情况下,求解结果的均衡性指标有一定的下降,但相对来说差距并不大,针对性地提升均衡性指标可以作为未来进一步研究的方向。

4 结论

本文针对考虑复杂人员搭配规则的机组人员派遣优化问题进行研究,分析了国外厂商解决方案不适用于国内航司的根本原因,创建了考虑机组人员派遣公平性的指派模型,基于人员搭配规则的特点,设计了基于变邻域搜索算法和模拟退火算法的混合启发式算法,并用实际数据验证了该策略的效果,为考虑复杂人员搭配规则的机组人员派遣优化问题提出了一个有效的解决方案。

参考文献