導入事例
Gurobi + Uber
未来の都市型オンデマンド航空輸送
オンデマンド航空輸送は、日々の通勤時間を人々に取り戻し、都市交通を劇的に改善する可能性を持っています。Uber Elevateチームは、都市型航空ライドシェアリングを大規模に展開して世界の姿を変えようとしています。Uberは、都市周辺部での相乗り航空輸送システムを開発中で、2023年初就航を目指しています。現在、小型の電動垂直離着陸機（eVTOL）の機体群をダラス、ロサンジェルスおよび発表予定の国際マーケットでの就航に向け、Elevate Networkのパートナー各社と開発中です。
問題：Skyport ネットワーク設計と飛行ルート
Uberのこの未来的ベンチャー事業が成功する上で決定的に重要なのが、運用の最適化です。電動垂直離着陸機（eVTOL）の離発着は、ユニークに建設されたスカイポートと呼ばれる設備に限定されているため、飛行ルートの決定を複雑にしています。
そこで、Uberチームは、数理最適化技術を利用してネットワーク設計と飛行ルートの決定を行いました。
1. ネットワーク設計
最初に行うのがネットワーク設計で、スカイポートを配置する最適な場所を求めていきます。出発地と目的地を入力し、変形クラスタリングアルゴリズムを使ってインフラを建設すべき最も合理的な場所を決め、カスタムメイドの需要選択モデルを活用しながら、乗客数の期待値を最大化するようにスカイポートの場所を絞り込みます。
2. 飛行ルート
次は、機体の飛行ルート問題です。ネットワークが設計されて離発着場所が決まった後、乗客に航路スケジュールを提供するため、飛行ルート問題を最適化により解きます。これは機体の充電と乗客の搭乗待ちを考慮しなければならないため、従来のルート問題よりもはるかに複雑な問題になります。つまり、ネットワーク全体ですべての機体が、いつ、どこで、どのくらいの頻度で充電するかという問題を充電場所のキャパシティを超えてはならないという条件の下で、スループットを最大化し、非稼働時間を最小化するように決定するので、構造的に解くことが難しい数理モデルになります。
UberPOOLと同様、類似の出発地／目的地がある乗客を組み合わせることにより、すべての当事者にとって費用効率が高くなります。システム効率と乗客の快適さのバランスを取ることはデリケートで難しい問題であり、注意深く構築された数理モデルと最適化手法を必要とします。
この問題にはまったく新しい輸送形態に関連する不確実性があり、このサービスのためのデータ収集はきわめて複雑です。その他に考慮すべき事柄としては、選択可能な複数の移動形態の間のトレードオフに対し乗客がどのような行動を取るかがあり、これらをより複雑なネットワーク最適化モデルとして構築する必要があります。
ソリューション
Uber独自の Flux Optimizer（需要予測およびネットワーク最適化ツール）は、Uber Elevateのネットワーク設計と飛行ルート決定の問題を解くことができました。モデルのサイズは主に具体的なインスタンスにより決まりますが、整数変数の数で言えば数10万～数100万個になります。エネルギー的な実行可能性を追跡するパスベース（path-based）モデルを使うことで実行時間を改善でき、整数変数の数が10倍になっても解くことができました。
解を得るまでの実行時間は、ユーザ入力、飛行ルート数などに依存し、数秒から数時間の範囲になります。ある段階でネットワーク設計問題を解き、次の段階で乗客のマッチングとバッテリー充電を考慮した飛行ルート問題を解きます。ほとんどの時間は、経路モデルに使われるパスの生成に費やされます。
Uberチームはシンプルな ユーザインタフェースを構築し、１日の実態を詳しく調べたり、飛行日の特定部分を指定して点検ができるようにしました。これによりソリューションが適切に機能していることを確認し、独立した検討調査を行うことができるだけでなく高度に複雑であるソリューションおよび相互の影響具合も可視化できます。この柔軟な解析によりユーザは、様々な機種、バッテリー、運用上または騒音の要件、価格などを入力することができます。
なぜ Gurobi ？
私達は、私達のカスタムユースケースにも利用できるよう、中核となるGurobiの混合整数線形計画法（MILP）ソルバーをラッピングしました。これは、強力で使い易い計算処理上のいくつかのトリックに依存します。私達が航路パターンをベースとしたモデルを使い始めてからは特に、Gurobiのプリソルブ（前処理）ルーチンは、可変上限値不等式が現れる本来の定式化を厳しい定式化に変形することができ、最適化を行うのに極めて有効なものです。チームは、RINSのようなヒューリスティックスおよび評価すべき複数のソリューションをユーザに提供するソリューションプールにおいて、いくつかの成功を収めてきました。
このモデルは、かなりのカスタマイズが要求されます。例えば、モデルの制約式の部分集合に遅延制約を追加する場合は、非常に効果的であることが実証されています。コールバック手法はとても柔軟性があって使い易く、それにより、分枝限定法等のようなアルゴリズムの実装を容易にします。
期待される効果
現在はまだ基準がないため、最適化の効果を測定することは困難です。スカイポートの配置場所をできる限り正確に求めかつeVTOLの利用者数を最大化することは、収益に多大な影響を与えます。機体の効率利用、つまりは、地上待機時間を小さくすることを確実にし、適切な場所で適切な電力量の充電をすることは、このベンチャー事業の成功には不可欠です。
Uberは、より高速で、より積載量が大きい、あるいは、より長距離の飛行ができるような新しい複数の機体の仕様に影響を与える、異なった機体のコンセプトの解析を実施しました。
Uberは都市部の航空ライドシェアリングがプレミアム製品に発展し、「都市での有意義な飛行のシェアリング」のニーズに答え、低価格でのサービス提供が可能になることを期待しています。
Gurobi Optimizer 採用にあたって
私達のパートナーによる投資があまりに莫大であるために、最適化を基盤にしたリューション以外の選択肢は考えられません。そして、私の意見では、私達の要求を満たすべき製品は、 Gurobi以外にはありません。私は、会社を創業して以来 Gurobi のソフトウェアに頼ってきました。彼らの製品とチームに対して最高の敬意を捧げたいと思います。
Uber Elevate データサイエンス部長
Jon Petersen
