带有一致性规范约束的航空机组排班问题研究

马弘沈倪朱靖夏佳楠

(1.浙江大学 工程师学院,浙江 杭州 310015;2.浙江大学 管理学院,浙江 杭州 310058)

0 引言

航空运输业在国民生产和生活中扮演着越来越重要的角色。与此同时,经济全球化和激烈的航空运输市场竞争也对航空公司的运营与调度提出了更高的要求。航空运输业具有服务密集型产业的特征,机组人员是航空公司最重要的航空资源之一,是其潜在竞争优势的来源[1],会对公司绩效产生直接的影响[2]。近年来飞行事故调查结果显示,人为错误因素诱发的飞行事故比例高达70%。其中机组成员的不良状态如精神疲劳、协调缺失等是引起人为错误的重要因素[3]。由此,我们看到的确有必要在机组人员排班过程中充分考虑并协调各环节中能够影响到机组人员身心健康的因素,如休息时间、环境变化等,并积极采取措施减少此类消极因素的影响。

在机组人员排班调度中,传统机组排班是根据已确定的航段来生成固定周期内从某一基地出发并且能够返回基地的机组排班的集合,排班需要满足民航局发布的民航运输飞行人员飞行时间、值勤时间和休息时间的规定;同时确保这些机组排班能覆盖所有计划的航段,不应使任何需要值勤的航段未分配给机组人员,即令排班计划满足合法性和可行性的约束。但值得注意的是,即便是满足并符合上述两个约束的排班计划在航空公司的航班与飞行规划实践中仍存在较多可改进之处,这说明目前该领域仍尚未被充分研究。近期仍有不少学者通过在传统的机组排班问题基础上中添加有针对性的相关约束,以达到针对性地提升排班调度的质量的目标。例如Quesnel等[4]将机组轮换问题(crew rostering problem)中的工作语言约束引入到机组配对问题中,研究表明在计算复杂度略微提升的前提下,能使违反语言约束的排班比率减少百分之九十。Quesnel等[5]的研究中亦加入了旨在将工作时间平均分配给全体员工的特殊约束。

在正常执行任务状态下,保障机组人员有充足的休息、维持其良好的工作状态是保障航空运行安全和效率的重要方面。为加强排班计划对机组人员良好工作状态的保障,我们将车辆路径规划问题中的一致性标准引入到航空领域,提出了机组排班问题中新的一致性约束。包含一致性的车辆路径规划问题最早由Groër等[6]提出,是指固定线路上的顾客在固定时间区域内被相同的司机服务,从而获得提升客户满意、提升公司收益等优势。经过调研,我们发现在民用航空机组排班背景下的一致性,则强调机组人员的值勤期路径应呈现一定的规律性,以此来增强机组对新值勤期的适应程度,提升人员调度计划质量,进而达到保障飞行安全和提高运营稳定性的目的。

本文对该一致性标准的定义具体表现在人员的值勤班次一致性和过夜城市一致性两方面。一方面,因为航空作业的特殊性,机组人员经常需要倒班,如在夜间工作和日间工作班次之间转换,这极易引起睡眠紊乱以致疲劳驾驶等问题[7]。而规律性的作息对于机组人员保持精力充沛非常重要,因此应尽可能保证机组人员在值勤期内工作时间的一致性,将其在一个周期内的换班次数控制在一定区间内[8]。这将更有助于保障机组人员身心健康,提升工作满意度和促进航空公司运行的效率与安全性。另一个方面,过夜城市一致性要求将机组人员在一个周期内除基地(居住地点)外的过夜城市数量限制在一定范围内。长时间的旅途奔波易使机组人员精神和体力疲劳,熟悉的环境有助于缩短机组人员的环境适应过程以帮助其更好地休息,从而能够促进其疲劳恢复,保证后续航空作业的安全性[9]。同时,对过夜城市数量的控制能帮助提升航空公司的管理效率,公司可与相对较少数量的相关酒店达成合作,以较为优惠的价格预定客房和接送车辆,并更加集中地实施人员管理和调度,减少人员的不确定性。

本文在传统机组排班模型中引入了考虑机组人员身心健康的一致性考量,在此基础上分别构建了考虑值勤班次一致性和过夜城市一致性的机组排班模型。根据新模型的特点,我们提出了求解该模型的启发式列生成算法,采用了两种形式分别构建了相应的子问题,并通过改进的动态规划算法对子问题求解产生新列。我们通过对一航空公司的真实数据的求解分析,将结果和市面上先进的商业求解器的结果进行比较验证了算法的效率和有效性,并深入分析比较两种约束形式求解子问题的优劣,以及探寻我们所提出的一致性约束在机组排班问题中的可行性和实用价值。

1 机组人员排班问题的相关研究回顾

1.1 值勤计划问题相关研究

生成值勤计划是航空公司机组人员排班研究的重要方面。值勤计划问题是指将航空公司飞行计划中的航段按照一定规则生成每个机组人员的工作计划,并最终达到最小化运营成本或者最小化机组人员数量等优化目标的问题[10]。由于生成值勤计划问题具有需要满足的规则繁多、可能的解集规模庞大、解决方案成本中薪资等部分与工作时长非线性相关等特点[2],该问题一直是热门研究问题。

学者一般将集合划分模型或集合覆盖模型作为生成机组人员值勤计划的基本数学模型[11-12]。集合划分模型生成机组人员可行的排班计划的集合,并使得每个飞行航段至少被覆盖一次,并使总成本最小。集合覆盖约束所允许的飞机航段被超过一次覆盖则可解释为有机组人员作为乘客搭乘了这些航段(deadhead)[12]。Arabeyre等[13]在其综述文章中讨论了可行的排班计划集合的生成、缩减和优化的各种方法。Kolner[14]、Fearnley[15]用子集减少方法缩减集合规模,并成功运用在了联合航空公司和加拿大航空公司的调度系统中。Barnhart[10]、Desrosiers等[16]则为解决大规模的0-1整数规划问题提供了相关的数学方法,为解决航空公司机组调度问题提供了借鉴。Desrosiers等[17]使用嵌入在分支定界算法中的列生成算法生成了值勤计划的可行解,提高了求解的效率。此外,一些研究者也将启发式算法与排班问题的求解过程相结合。Gershkoff[18]从启发式解法产生的一组初始解开始,再利用整数规划方式不断改善初始解。Thomas 和Proksch[19]将模拟退火与特定问题的局部改进启发式相结合,在提高解决方案的质量的同时减少了算法运行时间。Bader等[20]利用遗传算法来求解大规模的机组排班问题,并将分支定界法与遗传算法相结合,有效提升了遗传算法中寻找最优解的收敛速度。Crawford等[21]分析了蚁群优化算法对解决机组人员调度问题的性能,并将蚁群算法与列生成算法相结合,较好地解决了Beasley's OR-Library 中的测试实例。Saddoune等[22]打破了规划过程的顺序性限制,构建了一个集成值勤期生成和机组人员排班问题的模型,并开发了组合的列生成与动态约束聚合方法求解的算法,实现了一体化排班。该模型使得北美一家主要航空公司的座舱机组总数减少约5.5%。

同时除了成本最小化目标外,也有研究关注到排班稳定性与运营成本效益问题。Ehrgott 和Ryan[23]对延长机组人员值勤期之间空闲时间的成本效益进行了研究,在增强鲁棒性的目标下使得调度计划成本最小。Yen 和Bridge[24]通过减少机组人员在工作期间更换飞机的次数,减少了因换机时间不足而导致的不确定性。赵正佳[25]制定了满足机组休息时间约束并使机组在异地停留时间最短的调度计划,该计划能以较少的机组完成航段飞行任务。他们的实践经验表明,人力成本的小幅增加可以带来可观的运营稳定性收益。Tam等[26]考虑到了一个机组内人员的延迟对排班问题的影响,他们发现由最低成本目标求出的排班结果对航段延迟几乎没有缓冲时间,所以机组人员在飞行延迟后进行的拆分会导致延迟在不同排班计划上的传播,影响排班计划的鲁棒性,因此,Tam等[26]在原有模型计算成本最小化目标的基础上增加了最大化单位机组数量的目标。他们对新西兰航空国内航线的数值测试表明,增加此目标大大提高了单位机组的配备水平,而成本却没有大幅增加。

1.2 一致性标准相关研究

Groër等[6]首次在车辆路径规划问题中引入一致性标准,构建了包含一致性标准的车辆路径规划问题(con-VRP),具体提出的路径一致性标准规定了司机在固定的n条路线上工作;时间一致性标准规定了司机在大致相同的时间区间服务顾客;间隔一致性标准规定了客户被服务的最大和最小间隔时间。Coelho等[27]认为在路径规划中加入一致性标准将有助于建立起一种使司机和顾客双方都受益的纽带。这些规定将使司机更加熟悉分配给他们的客户和地点,从而更容易与客户建立发展更加紧密良好的关系,培养与顾客之间的熟悉程度,进而获得更多的配送需求,提高公司收益,这是在仅仅基于成本考虑车辆路径规划问题时所没有的特点和优势。近年来有关车辆路径规划问题的一致性研究层出不穷。Coelho等[27]在库存路径规划问题(IRP)解决方案中引入了反映通用服务质量水平的六个一致性标准并建立了相关模型。Nowak等[28]在周期车辆路径问题(PVRP)中加入顾客一致性标准(司机服务相同的一组顾客)并构建了平衡人力成本和出行距离目标的模型,为管理决策提供了借鉴。Luo等[29]研究了带有时间一致性标准和运输容量一致性标准的多期车辆路径选择问题(MVRPTW-LVQ),分析了在不同需求波动水平下提升服务一致性水平对运营成本的影响。

综合以上航班值勤计划相关问题和一致性的车辆路径规划问题的文献回顾可知,在目前航空公司运营调度问题研究中,研究者所增加的约束大多是以降低规划成本以及增加运营稳定性等为目标,而较少从机组人员的中长期身心健康与工作、休息状态角度出发考虑。但机组排班计划的主体是机组人员,他们的身心健康对航空公司的运营质量和生产效率方面有着至关重要的影响,如乘务员在与客户的互动中展现出的饱满的精神状态对于提高顾客满意度有着积极影响[2];而身心疲劳则会使得飞行员注意力下降、反应动作迟钝、严重影响他们的判断力和决策力,从而对飞行安全带来隐患[30]。最后,机组人员的身心健康还会对其工作满意度产生较大影响。由于不同的排班计划涉及的飞行时间、区域、工作强度等都不同,机组人员对不同的排班计划偏好也不同,如一些排班计划内的值勤期在日间飞行与夜间飞行之间不断轮换,这对飞行员作息调整产生了极大的挑战,飞行员一般不愿意执行该类任务,而一些带有国际航段的排班计划则被认为是好差事,因为飞行员能够有较长的带薪休假以及高额飞行津贴[31]。一致性标准作为提升车辆路径规划相关问题求解质量的有效手段,可以帮助提升配送服务水平、顾客满意度、提升订单成交概率和增加配送需求。因此,为使航空排班计划更好地符合机组人员、航空公司、顾客三者的利益,我们尝试在制定排班计划的过程中,将一致性约束引入机组人员排班模型中,使得机组排班计划不仅能够关注成本与效率,而且在平衡机组人员技能素质、身体状况、身心负荷等条件下,减少影响机组人员身心健康的消极因素,进而给出更加均衡一致、科学合理的排班执勤计划。

2 机组人员排班问题介绍

2.1 值勤计划相关概念

(1)航段:是指飞机从起飞到下一个着陆之间的飞行。

如上表1 所示,每一个航段包括①航段编号:该航段的序号,用来唯一确定这一航段。②飞机编号:该航段被指派的飞机的编号。③起飞机场和降落机场:说明该航段的出发地点和降落地点。④三字码:国际航空运输协会(IATA)所制定的代表不同机场的特定编码。⑤日差:起飞时间和降落时间日期的差值,日差为0 时说明该航段在起飞当天就结束,反之则说明该航段一直延续到下一天。⑥起飞时间和落地时间:说明该航段的从机场起飞的时间和降落的时间,以北京时间计。

表1 航段示例Table 1 Example of legs

(2)飞行值勤期(tour of duty):是指在某一天中,机组成员从为完成该次任务到达指定地点报到时刻开始,到飞机在最后一次飞行后发动机关闭且机组成员没有再次移动飞机的意向为止的时间段。

上表2 所示是某个编号为1 的值勤期中的具体航段。每个值勤期的第一个航段被称为值勤期开始航段,最后一个航段被称为值勤期结束航段。该值勤期的开始时间由报到时间决定,而每一个值勤期的报到时间根据规定为开始航段起飞前1.5 h,计算为7 月4 日10:35。该值勤期的结束时间由结束航段的结束时间决定,即7 月4 日21:05。值勤期的开始时间、结束时间、所包含的航段等要素构成了值勤期的基本要素。

表2 飞行值勤期示例Table 2 Tour of duty

(3)值勤时间:是指机组成员按照要求执行所分配的任务的时间,这些任务包括但不限于飞行值勤、置位航班和培训等。值勤时间由值勤期的结束和开始时间的差值得到。表2 中的值勤时间是21:05 与10:35 的差值为9.5 小时。

(4)置位航班(deadhead):是指机组成员为完成指派的飞行任务,作为乘客乘坐飞机或地面交通工具,但不包括其往返当地的住宿场所的交通。置位航班属于值勤,该时间不能作为休息时间。

(5)飞行时间:是指机组成员在一个值勤期内从飞机起飞到下一个着陆之间的飞行时间的累加。表2 中飞行时间是航段324,331,338 三段飞行时间的累加,其总和为5.17 小时。

(6)休息期:两个值勤期之间的间隔,是指从机组成员到达过夜城市起,到为执行下一次任务离开过夜城市的连续时间段。在该段时间内,航空公司不得为机组成员安排任何工作。

(7)过夜城市:是指机组人员在休息期所处的城市。在该地有可以控制温度、降低噪音、条件良好的场所(如宾馆等),该场所能够控制光线亮度,使机组成员可以在床位上以平躺或接近平躺姿势睡觉或休息。

(8)机组排班计划(line of work):是指机组人员在较长时间跨度内(一周或一个月等)的工作计划。它是由多个值勤期和休息期构成的连续的活动计划。

2.2 值勤计划相关规则

在实际值勤过程中,一个机组由飞行机组和乘务机组所构成,不同类型的机组人员所适用的规则不同。由于飞行机组的责任更大,值勤计划安排过程中对飞行机组成员的要求和约束也更多,在不失一般性的前提下,本文讨论的值勤计划以飞行机组成员的执勤计划为例,而在后续的应用中可推广至所有机组成员。飞行机组人员值勤计划的规则由中国民航局《大型飞机公共航空运输承运人运行合格审定规则》中的重要规则以及华东地区某民营航空公司的相关补充规则构成[32]。

(1)每个飞行值勤期内的值勤时间约束与飞行机组成员报到时间和航段任务数量有关,详见下表3。如某个飞行机组成员在0:00 至4:59 之间的时间报到,执行小于4 个航段的航段任务,则其最大的飞行值勤期不超过12 小时。

表3 飞行机组最大飞行值勤期限制Table 3 Maximum flight duty limitations for a flight crew

(2)每个飞行值勤期内的飞行时间约束与飞行机组成员报到时间有关,详见下表4。如某个飞行机组成员在0:00 至4:59 之间的时间报到,则其最大的飞行时间不超过8 小时。

表4 飞行机组最大飞行时间限制Table 4 Maximum flight time limitations for a flight crew

(3)单个飞行值勤期后休息期不少于10 小时。

(4)若飞行机组成员执飞值勤期的第一个航段,或飞行机组成员在值勤期内从一架飞机换到另一架飞机,则飞行机组成员的报到时间是起飞前1.5 小时,若飞行机组成员的下一个飞行航段在值勤期内的同一架飞机上,则不需要提前报到。

(5)排班计划任意连续7 天飞行值勤内有一个至少连续24 小时的休息期,且起飞基地和降落基地应相等。

机组人员排班整体而言需要解决两阶段问题,生成值勤计划和值勤计划分配。生成值勤计划是指航空公司根据已确定的航段来生成固定周期内从某一基地出发并且能够返回基地的排班计划的集合,这些排班计划要包含预设的所有航段;值勤计划分配是指将生成的排班计划具体地分配给每一个特定的机组人员的方法。常见的分配方法有资历优先竞标法和公平任务分配法。本文研究机组排班问题中关键的第一阶段的值勤计划生成问题,因为该问题包含大量复杂约束,并且与一致性规范直接相关。而对于第二阶段的值勤计划分配问题,与本研究的主要贡献点一致性规范并不密切相关,故不做赘述,相关方法可直接参考 Ernst[33]、Butchers[34]等人的研究。

生成航空公司排班计划是一个复杂的计划制定过程,航空公司航线计划和基地分布以及民航局的规定等都会直接影响模型的构建。本文将在分析和总结现有机组人员排班模型的基础上,构建包含一致性标准的机组人员排班模型并设计相应的求解算法,研究一致性标准的加入对排班计划的影响,以改善现有机组排班相关研究中优化目标不够全面的弊端,保障机组人员规律作息和身心健康,同时促进航空公司的运营安全与人员工作效率。

3 问题模型

3.1 基本模型

机组排班问题可以被等价地建模为一个集合覆盖模型,我们用J表示所有符合规则的排班计划(列)的集合,对于每一条排班计划j∈J,设aij为0-1 变量表示第j条排班计划中是否包含i航段。使用二元变量xj表示是否选择排班计划j,假设总成本与每个排班计划线性相关,并令cj表示每个计划的单位成本,则具体模型如下所示。

模型的目标函数是最小化排班计划的成本,式(1b)为航段覆盖约束,表示所有预设的航段都会被选中的排班计划组合至少覆盖一次;式(1c)表示xj为0-1 变量。

为了使问题清晰简洁,在不影响对一致性约束探究的前提下,我们将模型中的排班计划的成本cj设为1,即我们认为使用的飞行机组数越少,排班计划的总成本越少。上述模型目标函数(1a)简化为(1d)。

上述模型包含指数数量级的列,每列都描述了一个机组排班计划。求解中遇到的困难主要在于求解所有排班计划的集合,因为它是一个NP-Hard 问题,当求解所有满足约束的排班计划时,即使只有100 个航段的值勤计划,也有可能生成上万条可行的排班计划,而对于有上千个航段的值勤计划,排班计划的数量可达数十亿条[2]。由于存在太多的可行排班计划(列),直接求解上述模型十分困难,与传统研究类似,本文也将采用列生成方法(详见4.1 节)对模型进行求解。其主要思想是先构造一个规模较小的主问题(仅包含少量初始列)和一个用于寻找新排班计划的子问题。主问题为松弛的集合覆盖问题,求解主问题的同时,为子问题提供对偶价值(dual price);子问题为主问题提供改进的排班任务。通过循环迭代,主问题增加新变量,逐渐逼近原问题的最优解,当满足一定收敛准则时即完成模型求解。

3.2 子问题

3.2.1 子问题基本模型

子问题基本模型的目的是生成满足规范标准的排班计划(列)。我们首先给出以下参数与变量:

参数:

·i、j:代表航段,i,j∈I,I为所有航段的集合;

·t:代表值勤期的时间周期,t∈T,T为日期集合;

·πi:为来自受限主问题的对偶解;

·h(i):表示i航段的前导航段的集合;

·b(i):表示i航段的后继航段的集合;

·fti:表示航段i的飞行时间;

·tdepi:表示航段i的起飞时刻;

·tarii:表示航段i的降落时刻;

·Fti:表示t日以航段i为起始航段的最大飞行时间;

·Dti:表示t日以航段i为起始航段的最长值勤时间;

·Scityi:表示航段i的出发城市的编号;

·Ecityi:表示航段i的降落城市的编号;

·M:表示一个极大的数;

变量:

·xit:0-1 变量,表示t日i航段是否与j航段连接的决策变量;

·yijt:0-1 变量,表示t日i航班是否与t +1日j航班连接的决策变量;

·sit:0-1 变量,表示该排班计划(列)是否由t日的i航段开始;

·eit:0-1 变量,表示该排班计划(列)是否由t日的i航段结束;

·maxht:表示t日机组的最大飞行时间;

·maxdht:表示t日机组最长值勤时间;

·maxth: 表示飞机组一个排班计划内的最大值勤时间;

·nft:表示t日机组执行的航段数量;

子问题表示为以下0～1 混合整数规划模型:

子问题根据主问题求出的航段对偶价值,计算满足约束且具有最小降低成本的排班计划(列)。式(2a)对应相应列的差额降低成本(reduced cost)。式(2b)-(2d)是生成列的基础约束。式(2b)表示该排班计划(列)有且仅有一个出发航段,式(2c)表示该排班计划(列)有且仅有一个结束航段。式(2d)是流量平衡约束,若航段为该列的出发航段,那么其必有一个后继航段或其为结束航段;若航段为中间航段,那么其必有一个前导航段和一个后继航段;若航段为该列的结束航段,那么其必有一个前导航段或其为出发航段。式(2e)表示该排班计划(列)的出发城市和降落城市相同。最大飞行时间同当日飞行员报到时间(即第一个值勤航段出发前半小时)有关,总飞行时间不得超过民航总局以及航空公司的要求限制,式(2f-1)识别出某日第一个值勤航段,并根据此航段的报到时间计算出最大飞行时间。式(2f-2)表示某日最大飞行时间(maxht) 的约束,即每一值勤期内各航段的总飞行时间不得超过民航总局以及航空公司的要求限制。约束(2g-1)-(2g-3)给出了值勤时间相关约束。该约束与飞行员当日报到时间和该值勤期执行的航段数量有关,通常执行越多航段,最长值勤时间越低。式(2g-1)识别出某日第一个值勤航段,并根据此航段的报到时间和执行的航段数量(nft),计算了最长的值勤时间。由表三可知以4 个航段为界限,每增加一个航段值勤时间减少一个小时,故在计算时可由基础值勤时间减去航段数量与4 的差值获得此时的值勤时间,而式(2g-2)则给出了值勤期执行的航段数量的计算。式(2g-3)表示某日最长值勤时间(maxdht) 的约束,当日值勤时间由当日执飞的结束航段的降落时间减去起始航段的起飞时间得到。式(2h)表示结束时间和开始时间的差值不得超过一个排班计划内的最大值勤时间,使排班计划满足在7 个值勤期至少需要有连续24 小时的休息期约束。

3.2.2 纳入一致性标准的模型

(1) 班次一致性约束

增加班次一致性是为了保证机组人员作息的规律性,为此需要将其在一个周期内的班次交替次数限制在一定范围内。为更合理地划分时间段,本文参考了中华人民共和国铁道部有关发车时间的班次划分规则,每六个小时划分为一个班次,值勤班次区间分别为00:00 至05:59、06:00 至11:59、12:00 至17:59 以及18:00 至23:59,共计四班。

表5 值勤班次时间表Table 5 Schedule of duty

若相邻两天内所属的值勤班次不同时,我们就认为该机组人员进行了一次班次交替。但当相邻的两天中有一天为休息日时,由于机组人员的休息时间达到了24 小时,有足够的时间来调整自己的作息规律,则不被认为进行了班次交替。为实现班次一致性,需要在求解子问题时加入新的约束。这里我们设计了两组不同的约束形式,在后续的数值实验中对分别带有这两组约束的模型进行求解检验并观察其效果。

第一种约束形式如下所示:

参数:

Lt:表示预设的最大班次交替次数;

t:代表值勤期的时间周期,t∈T,T为日期集合;

sfi:表示航段i的出发时刻所属的值勤班次;

变量:

at:0-1 变量,表示第t日与第t+1 日之间是否有班次交替;

bt:取值为[0,4]的整数变量,表示第t个值勤期的班次,休息日的值勤班次记为0;

ct:0-1 变量,表示第t+1 个值勤期的班次与第t个值勤期的值勤班次差值是否为0;

yt:取值为[0,4]的整数变量,表示第t+1 个值勤期的班次与第t个值勤期的班次差值的绝对值;

dt:0-1 变量,计算yt所用到的中间变量;

式(2i)表示一周之内班次交替的数量不超过最大交替次数。式(2j)和(2k)表示某日与其后一日若有一日为休息日时,则当日与后一日没有班次交替,即bt或bt+1等于0 时,at=0。式(2l)表示第t日与第t+1 日值勤班次的差值为0,即班次相同时,没有进行班次交替。式(2m)计算了第t个值勤期的班次值,由当日的起始航段所属的班次决定。式(2n)表示当两天都不为休息日(当日存在执飞航段)且班次差值不为0(班次值不同即ct=1) 时,第t日与第t +1 日之间有班次交替,此时at=1。式(2o)表示当yt=0(两日班次的值相等) 时,ct=0,表示两日班次值不存在差值;当yt≠0时,ct=1,表示存在差值。式(2p)～(2r)是将yt=| bt+1-bt|转化为线性不等式的表示。

第二种约束形式如下所示:

变量:

ξi: 0-1 变量,是用来限制at取值的中间变量

β: 0-1 变量,是将绝对值约束转换为线性表达式的中间变量

式(2i)表示一周之内班次交替的数量不超过最大交替次数。第二种约束中的式(2i)-(2k)含义与第一种约束形式中的式(2i)-(2k)相同。式(2l)-(2m)表示将at≤转化为线性表达式,其含义为第t日与第t +1 日值勤班次的差值为0 时,没有进行班次交替。式(2n)表示第t个值勤期的班次的值的计算方式,由当日的起始航段所属的班次决定。式(2o)-(2r)表示当bt和bt+1之间有差值且不存在休息日(即bt≠0且bt+1≠0) 时,at取值为0,否则存在班次交替,即at取值为1。

(2) 过夜城市一致性约束

过夜城市是机组人员在休息期时所处的地点,为了使机组人员休息时能尽量处于熟悉的环境中,需要将机组人员在一个周期内除基地外的过夜城市的数量限制在一定区间内。我们只统计值勤期内不同的休息点的数量,且基地不作为过夜城市纳入计算。为了实现过夜城市一致性,需要在求解子问题时加入以下约束:

参数:

c:代表城市,c∈C,C为所有的城市的集合;

c(i):表示所有降落城市为c的航段的集合;

Lc:表示预设的最大过夜城市数量;

变量:

cityc:0-1 变量,表示城市c是否为过夜城市。

式(2s)表示总过夜城市数量不能超过预设的最大过夜城市数量限制;式(2t)～(2v)表示通过实际降落地点情况来计算出过夜城市数量。如果城市c是过夜城市,那么必须有在这个城市降落的航段和第二天在这个城市起飞的航段,并且城市c不能是基地。式(2t)表示对于城市c而言,如果降落地点为该城市的所有航段i,都不存在跨天的后续航段,则城市c不是过夜城市,即cityc=0。式(2u)表示对于城市c而言,如果降落地点为该城市的航段i中,有跨天的后续航段(航段i是当日的结束航段),且城市c不是基地,那么城市c是该排班计划(列) 的一个过夜城市,即cityc=1。式(2v)表示当城市c为基地时,该城市也不能算作过夜城市。

4 模型求解算法

精确算法求解排班任务可采用经典的列生成算法框架,求解非常耗时,即使使用流行的数学规划商用求解器(如IBM ILOG CPLEX),针对大规模的应用问题,也无法有效求解。本文在排班计划中新添加了一致性规范约束,使得问题求解变得更为困难。为提高求解速度和效率,我们针对列生成算法框架中的子问题,设计了一个基于动态规划的考虑一致性标准的寻找优质排班计划的启发式算法。虽然它不能像精确算法那样保证最优,但通过对比验证,该算法收敛精度高,并且能保证较好的求解质量。

4.1 列生成算法

列生成算法是一种算法框架,适用于求解一类每个决策方案对应整体规划模型中约束矩阵的一列的组合优化问题。接下来,本文简要讨论列生成算法(算法1)的总体框架。算法1 首先生成一些初始可行的排班计划(列)来构造受限主问题(restricted master problem),(第1 行)。然后在列生成过程中解决受限主问题(RMP)的线性规划松弛问题(第3行)。求解受限主问题后,将主问题的对偶值传递给子问题修正路径参数并进行求解(第4 行),子问题的目标是生成新的排班计划环,如果我们能找到降低成本为负的排班计划(列)(第5 行),将迭代地把这些列添加到受限主问题(RMP)中(第7 行),这些排班计划可能会改善当前受限主问题的解。如果满足收敛条件(即列的降低成本非负),则求解过程停止,循环跳出(第9 行)。最后我们求解受限主问题(RMP),如果此时解均为整数,则求解结束获得最优解(第11 行)。否则我们添加变量整数约束(第12 行)再次求解。

列生成算法的求解速度和质量主要取决于子问题生成新排班计划(列)的速度和质量。如果在模型求解初期或在每次迭代能够生成大量高质量的排班计划,这将提高原问题的求解速度和质量。本文聚焦于迭代求解子问题时的排班计划质量,因此在获得初始解时暂不考虑解的质量,只保证解中包含的排班计划满足其生成规则并能覆盖到所有预设航段即可。因此可多次调用3.2 节中求解子问题的模型,将目标函数设定为一个常数,每次添加针对某一未覆盖航段的约束以确保其被初始排班计划覆盖,多次求解后即可获得一组覆盖所有航段的排班计划集合,也就是我们的初始解。初始解的求解过程如下图1 所示。

图1 初始解求解流程Figure 1 Finding the initial solution

为了减少子问题的求解次数,提高候选排班计划的数量,提高求解速度和收敛精度,我们允许主问题加入子问题新生成所有有效列,而不仅仅是最优的列,同时在一定次数迭代次数后,对主问题的列进行一个筛选操作,以保证主问题模型的高效和精简。

4.2 基于动态规划的启发式算法

由于航段数目过大且同时需要考虑一致性约束,使用分支定界的精确算法求解子问题这样的MIP 问题求解时间过长,因此我们设计了针对子问题的基于动态规划的启发式算法求解,以兼顾生成列的速度和有效性。

我们可以把航班的前后依赖关系抽象作是一个有向无环图(directed acyclic graph,DAG),那么所有的排班计划都是该有向无环图上的一条路径。再将每趟航班所需的飞行与值勤时间看作资源,那么3.2 节中的子问题其实可以看作是在满足时间资源约束条件下,寻找有向图中的最长路径问题[35]。因此,机组排班的子问题原则上可以用最长路径算法求解,但是我们的排班问题附加有一致性约束条件。由于一致性标准的路径依赖性,在最长路搜索过程中还要同时计算航班的班次交替次数和过夜城市数量,进一步增加了算法实现的复杂性。因此我们设计了一种新的基于动态规划的启发式算法来求解子问题获取新的排班计划,不但保证了一定的求解质量且大大提高了求解速度和效率,使得整个排班问题可以在一定时间内求解完成。具体来说就是在受限主问题求解后,将其对偶值传递给子问题,更新有向图每个点的权值,再利用下述的动态规划算法求得一条新的最长路径,当无法生成一条权值为正的路径时停止。

4.2.1 动态规划基本步骤

我们首先介绍无一致性约束的子问题动态规划算法如下,我们按照单个值勤期t划分子问题的阶段,将其转化为多阶段决策问题,在每个阶段中我们需要决定多个航段如何顺序排列组成这一值勤期的飞行任务。问题中的指标函数就是当前阶段所包含的所有航段修正后的成本系数的加和,我们定义指标函数F(c,t,d,i) 为城市c出发的排班计划在第t日的d时刻完成了航段i任务时的最长路径长度,给出状态转移方程为:

动态规划问题求解的关键在于正确地写出基本的递推关系式和恰当的边界条件,选取恰当的状态变量。对于本问题而言,如需要精确求解那么状态中的时刻d需要包括单个值勤期的总耗费时间、该值勤期的飞行时间以及航段i的落地时间。因此如果直接使用上述状态转移方程求解将具有极大的时间复杂度和空间复杂度,无法在可接受时间范围内实现。因此我们再次考量到每段航班的耗时在1 至3 小时左右,单个值勤期执飞的航班数目一般在3 至7 个左右的特点,由此引入了一个新的变量p来描述时刻状态,p表示该值勤期的执飞任务次序,取值为[0,P]。这样在确保解的一定的质量同时大大降低了时间和空间复杂度,能够快速高效地进行求解。此时新的指标函数F(c,t,p,i)为城市c出发的排班计划在第t日的第p个任务为航段i时的最长路径长度,新的状态转移方程为:

该动态规划算法的步骤如下

4.2.2 纳入一致性标准的模型

(1) 班次一致性

纳入班次一致性的动态规划算法在定义指标函数时需要多加入一维变量s,取值为[0,S],表示当前更换班次的次数,则此时的指标函数F(c,t,p,s,i) 为城市c出发的排班计划在第t日的第p个任务为航段i且当前换班次数为s时的最长路径长度,状态转移方程为:

与上述基础步骤相比,在每一阶段更新指标函数时,如果航段i,j属于同一个值勤期(t相同),那么此时航段i的换班次数与航段j相同,如果航段i,j不属于同一个值勤期(t不同),此时需要比较航班i,j所属值勤期的始发航段的班次是否相同,若相同则两者的换班次数相同否则航班i的换班次数为航段j的换班次数加一,其余步骤和算法2.1 一致。

(2) 过夜城市一致性

纳入过夜城市一致性的动态规划算法在定义指标函数时需要多加入一维变量r表示当前过夜城市的数量,则此时的指标函数F(c,t,p,r,i) 为城市c出发的排班计划在第t日的第p个任务为航段i且当前过夜城市数量为r时的最长路径长度,状态转移方程为:

由于每个值勤期之间航段的起始城市与降落城市相同,所以仍旧可以在每一值勤期起始位置更新过夜城市的数量,但与换班次数相比,过夜城市一致性统计的是除基地外的不同城市种类而非每一值勤期之间的城市更换,此时我们将过夜城市数量的可行值r的取值范围设为大于Lc(预设最大过夜城市数量)的值Lr(可取Lc至T之间的任一数值),然后在处理时分两步走,首先在每一阶段同4.2.2.1 更新指标函数,如果航段i,j属于同一个值勤期(t相同),那么此时航段i的过夜城市数量与航段j相同,如果航段i,j不属于同一个值勤期(t不同),此时需要比较航班i,j所属值勤期的始发航段的过夜城市是否相同,若相同则两者的过夜城市数量相同否则航班i的过夜城市数量为航段j的加一。然后我们在找到的排班计划中检查实际过夜城市种类数,如果小于预设值我们将其纳入最后结果,如果不符合则舍去。同时我们参考了自适应领域搜索中参数的更新方法在实验中根据主问题的目标值不断调整Lr的数值以获得更快的收敛速度和更优质的解。

5 数值实验

5.1 实验环境

因为考虑了新的一致性约束,本文研究的问题与模型和过往研究中的机组排班问题存在着较大不同之处。因此本文提出的算法和结果不能通过计算实验和现有文献中的算法结果直接进行比较。于是,我们选择与商业求解器(IBM ILOG CPLEX)的求解情况做详细的对比。实验包括了模型是否含有一致性约束的两种不同情况。实验数据来自华东地区某大型民营航空公司2019 年7 月国内短途飞行航线数据,其中共包含有39 架飞机的航线,每条航线代表了一架飞机在一周内飞行的路线。39 条航线中共包含1420 个航段。本实验将通过求解1420 个航段的排班计划来检验模型和算法对实际问题的求解能力,并分别观察加入一致性约束后机组人员数量的增长情况。数值实验在配置了2.8 GHz 主频的英特尔至强四核处理器、16 GB 内存的CentOS Linux 7 的工作站上进行。我们采用Java 1.8 与IBM ILOG 提供的混合整数规划商用求解器CPLEX 12.6.1进行编程实现。

5.2 实验结果与分析

首先我们给出班次交替次数和过夜城市地点的排班计划示例。如表6 所示的排班计划,可以看到该机组人员此周的工作共有五个班次,分别属于第2,2,1,2,4 班次,根据3.3.2.2 中的规则,第二班(周二)与第三班(周三)之间发生一次交替,第四班(周六)与第五班(周日)之间发生一次交替,而第三班(周三)与第四班(周六)之间虽隶属班次不同但其中有一个两天的休息期,因此不计入工作时间的交替,所以这条排班计划一共有2 次班次交替。且这五个班次的过夜城市分别为杭州,西安,乌鲁木齐,杭州和银川,由于乌鲁木齐为基地城市且杭州作为过夜城市重复出现了两次,所以此排班计划中的过夜城市数量记做3。

表6 增加班次与过夜城市列的排班计划示例Table 6 Example of a work line

首先用不包含一致性约束的模型求解排班计划,对比用CPLEX 和动态规划启发式算法求解得出的结果,可以看到CPLEX 求得至少需259 列排班计划才能覆盖所有航段,而启发式算法求出只需要126 列排班计划。统计启发式排班计划中班次交替与过夜城市数量如下表7 所示。

表7 基础模型班次交替与过夜城市情况Table 7 Statistics of shift alternation and overnight city for the basic model

由上表7 可知84.13%的排班计划交替次数不超过2次,这些机组人员在一周的工作时间内只要调整两次及以下的作息,但可以看到仍有大约15.87%的机组人员在一周内要调整3 次到4 次作息时间,这对作息规律的影响是非常大的。所以本文决定将班次一致性的范围限制在[0,2]的区间内。同时仅有26.19%的排班计划过夜城市个数不超过2个,有大量的机组人员在一周内要在3 个及以上甚至5 个不同的城市度过休息期,这将非常不利于机组人员适应环境以获得更好的休息。所以本文将过夜城市数量限制在[0,2]的区间内。基础模型的安排存在非常多不合理之处,所以有必要在班次特别是外出过夜城市中加入限制。

此时我们利用CPLEX 与启发式算法分别求解问题。下表8,9,10 所示是两者在分别求解基本模型、纳入班次一致性约束模型和纳入过夜城市一致性约束模型的结果。

从表8 可以看出我们的启发式算法新生成的列的数量远远多于直接使用CPLEX 获得的列的数量,启发式算法在求解次数更多的情况下,所用的时间不到使用CPLEX 直接求解模型耗时的百分之一,同时最优值也从CPLEX 求得的259 下降到了126,效果有显著提升。可见启发式算法在效率和可行性上都有保证,不仅能大大节约时间,而且能获得高质量的求解结果。

表8 基本模型求解情况Table 8 Results of the basic model

上表9 和10 分别展示了分别加入班次和过夜城市一致性约束的求解情况。表9 展示了纳入班次一致性后两种不同建模形式下的CPLEX 与启发式的求解结果。在相近时间内(约72 小时)第二种建模形式略优于第一种,其最优排班计划数量分别为335 与354。相较于基础模型求得的259 我们可以看出加入班次一致性后CPLEX 求解速度大大下降,这又进一步证明了CPLEX 在此等规模下求解是不合适的,而提出的启发式算法在600 秒内获得最优解为130,解的质量有了显著提升。通过表10 中我们可以看到CPLEX在求解过夜城市一致性时也表现不佳,在近72 小时内求得最优解为375,而启发式求得的解为135,故而我们在下文对启发式的结果进行进一步分析。

表9 纳入班次一致性的模型求解情况Table 9 Results of the model with shift consistency

表10 纳入过夜城市一致性的模型求解情况Table 10 Results of the model with overnight city consistency

从表11 中可明确看出加入班次与过夜城市一致性约束的两种模型生成的最优解中的总排班计划数量与基础模型相比并未有显著增加,班次一致性加入后仅需增加4 条新排班计划即可覆盖预设航段,过夜城市一致性加入后仅需增加9 条新排班计划,比之基础模型分别增加了3.175%和7.143%。

表11 三组模型求解情况对比Table 11 Comparison of solutions for three models

增加班次一致性条件后,平均每个航班计划飞行时间和值勤时间都没有太大变化,我们对具体解分析后发现排班计划数的增加是源于置位航班使用的增加。相对地,增加过夜城市一致性条件后,平均飞行时间和值勤时间都有3～4 个小时的减少,可以明显看出由于要求过夜城市一致后,排班计划路线发生了调整,排班计划数量增加,致使平均飞行时间和值勤时间略有下降。

上述三个模型的求解结果不仅对模型中一致性约束设定的正确性进行了验证,也展示了加入一致性约束前后所需排班方案的变化情况,从机组人员数量这一方面来看,增加一致性约束后机组人员数量均有所上升,在一定程度上说明增加排班计划的一致性是以增加人力成本为代价的,但其所需付出的代价是在可接受范围之内的,同时虽然三个模型的日均飞行小时与值勤小时均不相同,有所起伏,但是变化幅度很小,结果较为稳定,这说明了纳入班次与过夜城市一致性后并未使得飞行时限和工作时间有较大的波动。此外我们统计了两组一致性约束加入后班次与过夜城市情况(见表12,13)。

表12 增加班次一致性约束班次与过夜城市情况Table 12 Results of shift consistency and overnight cities consistency

由表12 统计我们可以看出纳入班次一致性的模型求得的排班计划很好地将班次交替数量限制在了[0,2]的区间内。班次交替次数在0 次,1 次与2 次间的占比分别为8.462%,23.846%和67.692%,基本都在合理的区间范围内。与基本模型结果相比,过夜城市数量比例的分布没有太大的变化,仍旧集中在2 至4 之间。从表13 可知模型在纳入过夜城市一致性后所求得的排班计划也很好地将过夜城市数量限制在了[0,2]的区间内,过夜城市数量在1 个和2 个的比例分别为22.963%和77.037%。而与基本模型结果相比,班次交替次数比例的分布也没有太大的变化,集中在1 至3次之间。

表13 增加过夜城市一致性约束班次与过夜城市情况Table 13 Results of shift consistency and overnight cities consistency

另外,在敏感度分析方面,我们调整了允许班次交替数量的区间,将其上限控制在0 次、1 次和2 次分别进行试验得到下表14 结果,从表中我们可以看出,当班次交替数量上限为0,也就是不允许机组人员有换班时,为执行整个航段计划我们共需要151 人,与基础模型相比增加了19.84%。可见,严格的班次轮替要求会导致人力成本大大增加,同时因为人员的增加,平均飞行小时数,值勤小时数和工作天数下降幅度较大,从而造成了人力资源的浪费。当班次交替数量上限为1 时,我们需要137 人,与基本模型相比增加了8.73%,而平均飞行小时数,值勤小时数和工作天数则是略有下降。当班次交替数量上限为2 时,我们需要130 人,与基本模型相比所需人数增加了3.18%,平均飞行小时数下降了0.46 小时每人,值勤小时数增加了0.11 小时每人,工作天数则是略有下降,下降幅度为0.02 天每人。由此可见,虽然更严格的班次交替数量会提升机组人员的工作体验和工作效率,但是过于严格的要求可能会导致排班本身的安排不够紧凑,从而导致人力资源的浪费,管理者需要就具体情况对进行权衡。

表14 不同换班次数下模型求解情况对比Table 14 Comparison of solution with different shift times

同时我们也对班次区间调整后的班次与过夜城市情况进行统计,结果如下图所示。我们可以看到当班次交替上限分别为0,1,2 时,班次交替次数均在约束区间内,三者过夜城市数量都较为集中在3 个,所占比例均达40%以上。我们关注到也有20%左右的排班计划需要在多于4 个城市驻足,过夜数量多这一点需要在后期引起重视,我们也初步探求了将过夜城市限制在0 至1 个排班计划数量的变化,结果显示为减少过夜城市数量,排班计划数量会大幅上涨,这极易导致高人力成本,所以上述两点都启示我们在安排值勤时需要更多地关注到过夜的具体地点和数量,比如我们建议可以和某些经常出现的城市达成较为长期的合作以降低运营成本等。同时在后期的排班研究中我们可以更加关注过夜城市选择对排班计划的影响机理。总结来说,从上述结果我们可以得到以下管理启示,纳入一致性标准的模型所求得的排班计划与基础模型解得的排班计划在飞行与值勤时长的表现上相差不大,新模型在保留了原有计划的效率与收益的同时,又满足了我们提出的新的班次与过夜城市的约束,使得排班方案既合理有效,又能够考虑到机组人员的精神状态与身心健康,这启示我们在实际的运用中,航空公司可以在可接受的人力成本的增幅下,将一致性更多的纳入考量,提升机组人员的满意度和工作效率,进一步提高综合竞争能力。

表15 不同换班次数下模型求解情况对比Table 15 Results of overnight cities consistency with different shift times

6 结束语

6.1 研究总结

本文针对现有的机组人员排班问题研究中大多关注成本最小化和运营稳定性目标、并没有将机组人员身心健康的关注纳入系统考虑范围这一问题,将新的一致性规范约束引入机组排班问题这一领域。我们在排班计划中增加班次一致性和过夜城市一致性标准,有利于保障机组人员身心健康与航空公司运营的稳定性,为航空公司制定更加安全合理的排班计划提供了理论参考。

本文构建了基于真实排班计划规则并包含一致性标准的模型,并基于列生成的求解算法,针对性的提出了一个启发式的动态规划求解生成列。在此基础上使用真实航段数据验证了模型的正确性以及算法的求解效率,并对比分析了设定两个一致性约束前后所需机组人员数量的变化情况,证明了该模型和算法能够有效求解真实情况下规模较大的机组人员排班问题,这将有助于航空公司结合实际情况,更好地将一致性约束运用到实际的排班计划过程中,统筹考虑排班计划的成本与质量,提升管理和服务水平。但研究也存在一些局限性,有待进一步改进。本文模型中只考虑了使机组人员数量最小化的优化目标,即使用最少的排班计划数量来覆盖所有的航段,而未考虑每条排班计划的具体成本。在航空公司的实践中,需要根据每一条排班计划的航段数量、飞行地点、过夜地点数量等计算飞行津贴、任务津贴、旅馆费用等的费用作为排班计划的成本,因而加入一致性约束前后每条排班计划的成本会发生不同的改变。因此,本文中求得的最小化目标与航空公司真实的成本最小化目标之间有一定的差距。此外,本研究在使用列生成算法求解排班问题的子问题时为了加快求解算法的速度设置了求解器的最大的求解时间以及最大求解次数,因而最终选择出的排班计划会与理论上的最优解选择的排班计划不同。本文虽然通过多次尝试设定了这两个参数的值,但是最大求解时间与最大求解次数的设置对最终结果的影响以及如何取得求解速度和求解性能之间的平衡点还有待进一步研究。

6.2 未来展望

机组排班问题是航空公司运营调度重要问题之一,影响机组人员排班计划生成的因素有很多,如民航与航空公司的规定、人力成本、基地数量、飞机航线、上一周期排班计划等,本研究只考虑了其中一部分因素。因此,在未来的研究中可以引入其他因素综合考虑更全面的排班模型,以生成更完善的排班计划。其次,本研究中只考虑了一致性规范中的班次和过夜城市对机组排班问题的影响,我们建议未来的研究中可以探讨其他方面的一致性约束,例如机组与客机机型的一致性、机组内成员的一致性(例如正副机长的一致优先配对)等的加入对排班计划的影响,从多方面提高排班计划的质量。最后,可将一致性与排班计划研究的其他方向相结合,例如将一致性约束与机组排班计划鲁棒性的研究相结合,分析对比增加了一致性约束求解得到的排班计划是否比原来的排班计划在遇到延误或其他突发事故时的运营更具有稳定性等。