人员搭配规则是国内航空公司机组人员派遣问题中最复杂的一项,为优化机组排班质量,提高人员满意度,保障飞行安全,针对国内机组搭配特点,创建考虑机组人员派遣公平性的指派模型,设计基于变邻域搜索算法和模拟退火算法的混合启发式算法,以某航司客舱机组派遣月计划为例进行数据验证,结果表明,该算法在较短的时间内得到更优的解决方案,满足人员排班的现实业务要求,为解决考虑复杂人员搭配规则的机组人员派遣问题提供有效的方法,从而促进智能化机组排班产品在中国航空公司的落地。

Crew combination rules are the most complicated rules in crew rostering problem of Chinese airlines. In order to optimize the quality of crew rostering, improve aircrew satisfaction and ensure flight safety, and according to the characteristics of domestic crew allocation, this paper analyses crew complementation requirement in domestic airlines, proposes a crew assignment model which incorporates complicated crew combination rules with the objective to minimize the fairness factors. A hybrid variable neighbor search and simulated annealing meta-heuristic algorithm was designed to solve the model. The algorithm was verified in a case study. Taking a monthly rostering plan of an airline company as an example, the results show that the algorithm obtains a better solution in a short time, meets the actual business requirements of crew rostering,and provides an effective method to solve the problem of crew rostering problem with crew combination rules, so as to facilitate the implementation of crew scheduling optimizer in Chinese airlines.

机组人员派遣优化 ； 人员搭配规则 ； 指派模型 ； 变邻域搜索算法

crew rostering problem ； crew augmentation rule ； assignment model ； variable neighbor search algorithm

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

机组人员派遣问题(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 机组人员搭配方案表

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

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

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

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

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

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

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

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

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

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

步骤2:基于Si构造Nk (Si)得到新解Sn,并计算新目标值Zn。

步骤3:若Zn