セイバーは航空会社のペアリング最適化において乗務員の増強を明示的な変数とした

航空会社の乗務員計画は2つのステップで行われる。まず乗務員ペアリングによって、飛行スケジュールをカバーする匿名の勤務スケジュールを生成し、次にそのペアリングを個々の乗務員に割り当てる。長距離路線では安全上の理由から増強乗務員が必要となるが、ここに落とし穴がある。あるフライトに必要な追加の機長や副操縦士の数は、それをカバーするペアリングの特性に依存する。要件とスケジュールの選択は連動しているのだ。ほとんどのツールは、増強要件を事前に固定したり、その充足方法を制限したりすることでこの連動を断ち切っている。一般的な問題は非常に難しいからだ。

セイバーは1990年代半ばに長距離ペアリング最適化ツールを開発し、逆の道を選んだ。最適化ツールは多くの種類の乗務員増強プロセスを明示的にモデル化し、すべてのコックピット乗務員の関連する階級を同時に考慮する。それは分枝価格法（branch and price）を用いて、結果として生じる大規模モデルを解く。2015年のInterfaces誌の論文で、著者らは20年にわたるモデルとアルゴリズムの進化をたどり、彼らのアプローチを4つの従来手法と比較し、それが一般的な乗務員増強問題を解き、航空会社に大幅な乗務員コスト削減をもたらすことを示した。

なぜ機能するのか。増強は実際のコストである。同じフライトをペアリングAでカバーすると追加の乗務員配置が3つ必要になる一方、ペアリングBでは1つで済むかもしれない。したがって、最適化の前に要件を固定すると、コストがスケジュールに凍結されてしまう。要件を目的関数の内側に置けば、ソルバーはネットワーク全体にわたって最も安価な法的組み合わせを一度に選び取る。節約は bid line 内のすべてのペアリングにわたって複合的に積み重なる。だからこそ航空会社は単なるルールの微調整ではなく、この製品に対価を支払ったのだ。

乗務員の増強を最適化変数とした

増強要件はペアリングの選択と連動しているため、事前に固定するとソルバーが実行される前に乗務員コストが固定されてしまう。

分枝価格法によって拡大されたモデルが扱いやすい状態に保たれるため、増強状態を含む数百万の候補ペアリングが解ける状態に保たれる。

セイバーは乗務員ペアリングシステムを多くの長距離航空会社に販売したため、改善は1社ではなく顧客の機材全体にわたって倍増した。

20年にわたるモデルとアルゴリズムの漸進的な取り組み（1995年～2015年）が、明示的な定式化を実用レベルにしたのである。

制約が実際に解によって変化する場合、それをモデルの内側に残すべきである。「既知の」パラメータを事前に固定すると数学は単純になるが、ソルバーが取り除いたはずのコストを固定してしまう。

この最適化ツールは2010年代半ばまでセイバーの長距離ペアリング製品ラインに残り、2015年のInterfaces誌の論文はそのモデルとアルゴリズムの進化を記録し、4つの従来手法と比較評価している。論文は明示的な増強の定式化を研究ではなく確立された製品能力として位置づけ、一般的な問題が長らく実務で回避されてきたのはまさにその複雑さのためであったと指摘している。