机组资源是航空公司最为珍贵的生产资源之一，奠定了机组排班在航空运营管理中的重要地位。但同时，这也是个普遍认为难以解决的问题。一方面航空公司通常需要制定月度排班计划，可能

　　相信仔细阅读过上一期推文的小伙伴们一定对机组排班的主角——机组人员有了更多的认识和了解，尚未读过的小伙伴们也千万不要错过哦！点击下方链接回顾上期内容：

　　在开始前，为了让本期推文不至沦为“天书”，我们先来认识一下机组排班问题中涉及的一些专业术语是什么意思吧！

　　指机组成员根据公司的要求为完成指派的飞行任务，作为乘员乘坐飞机或地面交通工具，但不包括其往返当地适宜的住宿场所的交通。

　　指机组成员接受公司安排的飞行任务（包括飞行、调机或转场等）后，从为完成该次任务而到指定地点报到时刻的开始，到飞机在最后一次飞行后发动机关车且机组成员没有再次移动飞机的意向为止的时间段。一个飞行值勤期还可能包括机组成员在某一航段前或航段之间，代表合格证持有人执行的任务但没有必要休息期的情况（如置位、主备份、飞机或培训发生在某一航段前或航段之间，但没有安排必要的休息期）。在一个值勤期内，如机组成员能在适宜的住宿场所得到休息，该休息时间可以不计入该飞行值勤期的值勤时间。

　　指机组成员按照公司的要求执行的所有任务，包括但不限于飞行值勤、置位、备份（包括主备份和备份）和培训等。

　　机组资源是航空公司最为珍贵的生产资源之一，奠定了机组排班在航空运营管理中的重要地位。但同时，这也是个普遍认为难以解决的问题。一方面航空公司通常需要制定月度排班计划，可能会涉及成千上万条航段；另一方面，出于保障飞行安全和机组人员权益的目的，机组排班还必须满足许多复杂的工作规则，主要可以划分为四类：

　　机场资质类规则，即排班时必须根据特殊机场人员资质数量的限制，考虑在过夜环人员资质的影响，如：在疫情期间各地机场防疫规定不同，在过夜连线中考虑，前后两天过夜的地点是否有前一天旅居史不可入住的限制，在安排组环时就要避免在同一个航班环中。

　　飞行值勤期/值勤/休息时间类规则，可以进一步细分为机组人员在一个飞行值勤期内飞行时长和值勤时长的上限，一段时期内累积飞行时长和飞行值勤时长的上限及各阶段休息时长的最低要求三部分，下面我们仅对飞行机组的时间类规则进行简单举例说明。

　　任意 7 个连续日历日内飞行值勤期不超过 60 小时；任一日历月，飞行时间不超过100小时，飞行值勤期不超过210小时。

　　在前一个飞行值勤期结束后至下一个飞行值勤期开始前，必须获得至少连续10个小时的休息期；在执行飞行任务或主备份前的144小时内，必须安排至少连续48小时的休息期。

　　具体细节大家可以翻阅《大型飞机公共航空运输承运人运行合格审定规则》第五版（CCAR-121R5）中关于机组排班的要求。

　　为降低求解难度，排班员通常会将机组排班按先后阶段拆分为两个子问题：组环问题（Crew Pairing Problem）和指派问题（Crew Rostering Problem）。前者构造一组能够涵盖所有飞行航段且符合规定的航班环集合，后者则将构造的航班环分别指派给各机组人员，生成个人排班计划。根据两个子问题的求解内容及时间跨度，各项工作规则自然也就被分到两个阵营中。

　　值得一提的是，机组人员的飞行小时费及产生的机组额外费用（外站过夜补贴、搭车或搭机的费用等）基本都取决于航班环的生成过程，因此组环的首要目的是最小化运营过程中产生的机组成本；除此之外，决定排班计划质量的部分指标也需要排班员在组环时充分考虑，如：日均飞行/值勤时间、飞行/值勤日数量、排班计划的稳定度、鲁棒性等。

　　而在指派过程中，排班员则不仅要保证各机组人员有资格且有空余时间来执行安排的航班环，更多地还要从机组人员工作满意度的角度出发，考虑分配的公平性及他们工作的舒适度、疲劳情况等。

　　接下来我们就将一一为大家揭秘排班员在实际解决组环问题时的业务考虑因素、对组环方案的评价指标及建模求解的方法。

　　机组人员经常会遇到执行完飞行任务，无法返回基地，只能选择外站过夜的情况，航空公司自然会在这些需要过夜的机场为他们安排酒店等休息场所。但是，不同站点的休息场所的等级可能不同，对应着不同的花费，机组人员从站点去往休息场所的通勤时间也不尽相同。排班员需要权衡过夜成本，过夜次数，甚至休息环境设施等级等方面选择合适的过夜机场。

　　在实际运作中，经常会出现某个地方的机组人数不够的情况，需要将机组人员通过坐车或者搭机的方式送过去执飞航班，或者是机组人员由于航班延误等原因，在外站无法执行原本安排的下一趟航班时，也需要让机组人员通过坐车或搭机的方式回到基地，这类操作均属于置位。虽然置位有时必不可少，但机组人员大都唯恐避之不及，而且航空公司还可能因此少赚几张机票钱。所以排班员需要合理地安排置位，在满足航班环覆盖所有航段的前提下尽量减少置位的次数。

　　机组人员在飞机到达目的地后，有时需要赶往另一架飞机去执行下一个飞行任务，这可比一直执行同一架飞机的航段麻烦多了。而且机组人员执行相邻两航段的最短过站时间也与是否换机有关——不换机时所需的过站时间较短。因此排班员的工作也会与飞机路径规划相结合，灵活调整两航段之间是否换机，此举既能够提高机组人员的满意度，还能增加可行航班环的数量，从而进一步优化机组成本。

　　如图所示，当前序4号航段发生延误（4-4*），后续5号航段就只能在机组人员赶来前翘首以盼了，等着等着很有可能也就发生了延误（5-5*）。

　　因此，排班员要考虑历史航班的延误情况，适当调整航班之间的过站时间。比如说，考虑到4号航段可能发生延误，排班员在组环时就为其预留充足的过站时间，而安排计划起飞时间较晚的f号航段作为其后续航段。

　　这样可以提高机组排班计划的鲁棒性，从而在不正常航班出现时，控制其影响范围。然而，空余时间过长也会导致机组利用效率降低，增加航司成本，因此，排班员需要在提高鲁棒性和控制成本之间进行权衡。

　　在上述例子中，如果仍按原定计划，有没有什么方法能够在4号航段发生延误时，而不影响5号航段的计划起飞时间呢？

　　如图所示，5号航段原定由机组1执行，同时存在满足以下要求的另一个机组：在5号航段计划起飞时刻之前已经做好飞行准备，与机组1 同属一个基地且当前执行的航班环的结束日期相同，即图中的机组2。

　　那么在监测到4号航段发生延误时，机组1和机组2就能够通过交换后续飞行任务，确保后续航段仍然可按计划起飞时间运行。除此之外，还能够保证交换之后两个机组实际执飞的航班环不会违背组环的工作规则。

　　一般称机组2为机组1的可拆班机组，这是由Shebalov和Klabjan首次提出的概念。有时，可拆班机组的数量也会被用来衡量一个机组排班计划的鲁棒性，这就需要排班员进一步考虑了。

　　当然，机组排班不能只考虑经济成本，安全才是民航的重中之重。从上世纪80年代起，由于科技的突飞猛进，现代飞机设计日臻完善，机械故障大幅减少，人的因素成为飞行事故的最主要原因。机组人员的工作始终需要集中的注意力、高度的警觉和迅速反应能力，但是长时间的高强度工作、工作时间没有规律、跨时区飞行、休息状况不佳等情况，却会引起疲劳，进而影响其思考、推理和决断能力。

　　其实《CCAR-121R5》中的时间类规则已经实现了一部分疲劳控制。但是，这还远远不够，已经有部分航司对排班提出了更多的要求，以期进一步缓解机组人员的工作疲劳，例如：降低早晚班的数量，提高排班计划的规律性和稳定度等。这些要求都需要排班员在组环过程中充分考虑，从而在一定程度上缓解机组人员的疲劳情况，降低事故发生可能性，提高航班安全性。

　　一份合理的组环方案首先必须满足机组人员的工作规则，并做到100%覆盖计划期内所有航班。除此之外，还可以从以下列举的一些指标的表现对其进行评价。不同航司对各指标的偏向可能有所差异；另外，考虑当月航班量和占位的影响，淡旺季时的偏向也略有不同，旺季时偏向于提高航班环的日均飞行时长，提升机组资源的利用率；而淡季时，则会希望让更多的机组人员出勤来平均分配航班。

　　组环问题的首要目的就是为航司缩减成本，这里包括飞行小时费、过夜费用、置位费用等各部分机组在实际工作中产生的费用。

　　机组利用率可以通过所有航班环的总飞行时间与总值勤时间的比值、日均飞行/值勤时间等具体衡量，计算值越高，意味着机组利用率越高，也越能反映出机组资源得到了更加合理恰当的配置安排。

　　机组成本中的过夜费用与外站过夜的天数直接相关，而且过夜机场的个数同样需要控制，在满足排班需求的前提下，较少的过夜机场便于管理，在出现航班延误等情况时也更容易调整机组人员。

　　过长的外站连续休息时间会占用机组人员的值勤日，降低机组人员利用率。通常航空公司与机组人员都不喜欢过长的外站连续休息时间，对于航空公司而言，无法为公司带来收益，造成飞行实力的浪费；对于机组人员而言，无法挣取飞行小时费，造成可工作时间的浪费。

　　组环方案应该符合生物节律，可以使用生物钟曲线对机组人员的疲劳值进行测试，避免出现机组过度疲劳的情况，保证飞行安全。

　　组环方案在模拟场景中表现出来的鲁棒性越高，可以在一定程度上说明其在实际应用时，抵抗航班不确定扰动的能力越强。

　　在一个值勤日内，当由同一个机组连续执行的两个航段衔接时间较长时，会安排机组人员去住宿场所休息一段时间后，再次进场工作，这种操作称为二次进退场。这样虽然能让机组人员在航段间隙获得更好的休息条件，但是却意味着在值勤日中间，需要完成签退、乘通工具在机场和休息场所之间来回，再签到一系列流程，机组人员的实际体验并不美好，尤其是当真正剩余的在休息场所休息的时间并不长时，更是得不偿失。

　　当基地机场超过一个时，偶尔会出现机组人员签到和退场机场不同的情况，例如上海基地的机组人员在虹桥机场签到，完成工作后在浦东机场退场。这类情况会导致机组人员通勤时间变长，也应该尽量减少。

　　由于工作性质及规则不同，飞行员和乘务员的排班问题往往被分开解决。另外，不同于乘务员通常可以在多种机型的飞机上工作，大多数飞行员只能驾驶一种机型的飞机，因此在对飞行员进行排班时，排班员还可以按照机型进一步缩小问题的规模。

　　各类别机组人员的组环问题的求解思路大致相同。国内外已有的研究大多选择建立集合分割模型（Set-Partitioning Model）或多商品网络流模型（Multi-commodity Network Flow Model）以刻画组环问题。这里我们仅展示基础的集合分割模型。

　　由于每一个决策变量都对应一个符合要求的航班环，一个最直接的想法就是枚举出所有符合组环规则的航班环后，对上述整数规划模型进行强解，从而得到最优的组环方案。

　　但是机组排班是一个大规模问题，可行航班环的数量更是会随着航段数量的增长而呈现指数级增长，假设每个航段后续有三个航段备选，一天有四个航段，连续四天的航班环的数量就达到千万级别（3^16）；而当有四个备选航段时，这样的航班环数量甚至可达到十亿级别（4^16）。

　　因此，即使按机型等要求将航段集合划分为若干个子集分别求解，想要枚举出所有可行的航班环也近乎痴人说梦，为此我们需要借助算法来控制变量规模，提高求解速度。

　　通常，可以取消对变量的整数约束，将原整数规划问题松弛为线性规划问题后，采用列生成框架求得最优解。正是这一步的线性松弛，虽然原问题属于整数问。