飛行機の運行ルートを最適化し二酸化炭素の排出を削減(2/2)

１．飛行機の運行ルートを最適化し二酸化炭素の排出を削減(2/2)まとめ

・機体割当問題はノードとアーク(円弧)の集合によって特徴づけられる有向グラフと見なせる
・ネットワーク内のフローバランスを維持しながらフローコストの合計を最小化する問題
・航空機スケジュールの最適化で年間350万スイスフランと6500トンのCO2排出量の削減を見込む

２．機体割当問題の最適化

以下、ai.googleblog.comより「Optimizing Airline Tail Assignments for Cleaner Skies」の意訳です。元記事は2022年3月9日、Emily Mastenさんによる投稿です。

アイキャッチ画像のクレジットはPhoto by Yoshi Sugimoto on Unsplash

機体割当問題の数学的モデル

この問題は、基本的にノードとアーク(円弧)の集合によって特徴づけられる有向グラフであり、特定の目的に関連する制約が追加されています。

ノードには商品の供給と需要があり、アークにはフロー容量とフロー単位あたりのコストがあります。目標は、ネットワーク内のフローバランスを維持しながら、各商品のフローコストの合計を最小化するように、すべてのアークのフローを決定することです。

フローネットワークを使うことにしたのは、それが文献上この問題をモデル化する最も一般的な方法であり、フローネットワークの商品、アーク、ノードが現実の問題における機体、運行区間、エアポートに単純に一対一で対応しているためです。この場合、ネットワークのアークはフライトスケジュールの各区間に対応し、個々の機体はネットワークに沿って「流れる」商品の実体の1つです。ネットワーク上の各区間と機体のペアには関連する割り当てコストがあり、このモデルの目的は、これらの割り当てコストが最小になるように有効な区間と機体のペアを選ぶことです。

機体割当問題の簡単な例
このスケジュールには4つの飛行区間があり、それらの区間に割り当て可能な4つの機体があります。それぞれの機体と区間の組には、関連する運用コストがあります。例えば、区間1に対して、機体1を割り当てるには50ドルかかりますが、機体2を割り当てるろ100ドルかかります。コストを最小にする最適解は、機体4を区間3と2に、機体1を区間1と4に割り当てることです。

標準的なネットワークフロー制約の他に、このモデルでは航空会社特有の制約も考慮し、ルフトハンザグループの航空会社に合わせた解を提供します。

たとえば、航空機のターンアラウンドタイム(連続する2つのフライトの間に航空機が地上で過ごす時間)は航空会社固有のもので、さまざまな理由で変化する可能性があります。

例えば、ある航空会社のハブ空港でケータリングが積まれたり、へき地の空港ではターンアラウンドタイムが短縮されたり、ビジネス客よりも乗降に時間がかかる休暇客が多い路線では、ターンアラウンドタイムが長くなる可能性があります。また、航空機の整備やクリーニングが必要な場合は、空港の整備拠点で毎晩点検を行う必要があります。さらに、各航空会社には独自のメンテナンススケジュールがあり、航空機の燃費を維持するため、数日おきに定期的なメンテナンスチェックを受けなければならないこともあります。

結果速報と次のステップ

SWISS International Air Linesは、当社の問題解決プログラムを使ってヨーロッパにおける航空機のスケジュールを最適化した結果、年間350万スイスフラン以上の節約と6500トンのCO2排出量の削減を見込んでいます。このモデルがルフトハンザグループの他の航空会社に展開され、交通量がCOVID導入前のレベルに戻ったときには、この節約効果がさらに大きくなると期待しています。今後の課題としては、このモデルがより多くのデータセットで使用できるようにすること、最適化システムに乗務員と乗客の割り当てを追加して乗客と乗務員の両方のフライトスケジュールを改善することなどがあります。

独自のネットワークフローモデルの実験に興味がある方は、この投稿で紹介した問題解決プログラムと同様の最適化ソリューションを構築するために使用できる、私達のオープンソースソフトウェアスイート、OR-Toolsをチェックしてみてください。詳細については、OR-Toolsの関連ドキュメントを参照してください。

謝辞

Jon Orwant に感謝します。このブログの記事に幅広く協力し、Alejandra Estanislao とともに Lufthansa および SWISS とのパートナーシップを確立してくれたことに感謝します。オペレーションズリサーチチームとSWISS International Air Linesの皆さん、彼らの努力と貢献なしにはこの仕事は成り立ちませんでした。