Sabre将机组增强设为航空公司配对优化中的显式变量

航空公司机组规划分两步进行：机组配对生成覆盖航班时刻表的匿名工作排班，然后将这些配对分配给具体机组人员。长途航班出于安全原因需要增强机组，而问题在于：一个航班需要多少名额外机长或副驾驶，取决于覆盖它的配对的特征。需求与排班选择是耦合的。大多数工具通过预先固定增强需求或限制其满足方式来打破这种耦合，因为一般性问题非常困难。

Sabre在20世纪90年代中期开发了其长途配对优化器，并走了相反的道路：优化器显式建模多种类型的机组增强流程，并同时考虑所有驾驶舱机组人员的相关职级。它使用分支定价法求解所得的大规模模型。在2015年《Interfaces》的一篇文章中，作者追溯了模型和算法二十年的演变，并将其方法与四种传统方法进行了比较，表明它解决了通用的机组增强问题，并为航空公司带来了显著的机组成本节约。

为什么有效：增强是实实在在的钱。用配对A覆盖同一航班可能需要三个额外机组位置，而配对B只需一个，因此在优化前固定需求就把成本冻结到了排班中。将需求放入目标函数中，求解器就会一次性在整个网络中购买最便宜的合法组合。节约会在投标线路中的每个配对上复合，这就是为什么航空公司为产品付费而不是调整规则。

将机组增强变为优化变量

增强需求与配对选择耦合，因此先验固定它们会在求解器运行之前就锁定机组成本。

分支定价法使扩大的模型保持可处理，因此包括增强状态在内的数百万候选配对仍然可解。

Sabre向许多长途航空公司销售了机组配对系统，因此改进在客户机队中成倍增加，而不是只在一个客户中。

二十年的渐进式模型和算法工作（1995-2015）使显式公式达到了生产级水平。

当约束实际上随解而变化时，将其保留在模型中。预先固定“已知”参数简化了数学，但锁定了求解器本可以消除的成本。

该优化器一直保留在Sabre的长途配对产品线中，直到2010年代中期，2015年的《Interfaces》论文记录了其模型和算法的演变，并将其与四种传统方法进行了基准比较。该论文将显式增强公式视为已确定的产品能力而非研究，并指出正是由于其复杂性，一般性问题在实践中长期被跳过。