株式会社オクトーバー・スカイ October Sky Co., Ltd.loading
  1. HOME
  2. 導入事例
  3. 米国 ナショナルフットボール・リーグ

導入事例

米国 ナショナルフットボール・リーグ

地域
海外
分野
その他
製品
Gurobi Optimizer

はじめに

技術は、過去数十年間に格段の進歩を遂げ、以前は解決できなかった問題が今や数秒足らずで解決できるまでになりました。当然ながらこれほどの進歩の結果としてより大規模で複雑な問題に取り組めるようになったのです。その最たる例が、米国のナショナルフットボール・リーグ(NFL)です。4人の担当者が、10週間かけて17週間にわたるシーズンの256試合のスケジュールを組みます。決定することが少ないわりには、時間は十分にあるように見受けられるかもしれません。ところが実際にやってみると、考えられるスケジュールの数はゆうに数百京にも上ります。想像してみてください。これは、1の後にゼロが19個も並ぶ数です。

データサイエンティストがこの膨大な数の選択肢の中から適切なスケジュールを選び出すとなったら、何年もかかることでしょう。この問題をさらに難しくしているのが、追加される多くの制約条件です。たとえば、NYジェッツとNYジャイアンツなど、チームの本拠地が同じチームは同じ日時にプレーしない、どのチームも遠征試合が1週間内で連続3試合を超えてはならない、シーズン最後の数週間に地域対戦試合を可能なかぎり集中させてシーズンの終盤を盛り上げる等々の制約条件を考慮しなければなりません。

木製ボードからコンピュータへ

10年ほど前までは、6フィート四方の木製のボードの横17列をシーズン17週分と見做し、総チーム数と同じ数の32を縦列として格子上に区切り、これを壁に掛けて、どのチームとどのチームが、いつ、どこで対戦するか書き込んでスケジュールを組んでいました。その際の最初の目標は、実現可能なスケジュールを見つけることであり、この作業にプランニングに充てることができる時間の90%を費やし、残りの時間は、特定のチームまたはネットワークのスケジュールのどちらかを改善するための調整に充てていまいた。

木製ボードからコンピュータに切り替わり最適化のパワーが増すと、状況は劇的に変化しました。スケジュールを組むこと自体、ほんの2~3年前とは比べものにならないほど複雑化してはいるのですが、作業の焦点はスケジュール作成からスケジュール分析へとシフトしたのです。以前は、プランニングをするチームが直面する問いは単に「このスケジュールでいけるか?」ということでしたが、現在は実現可能な最善のスケジュールを見つけることが重要になっています。

科学としての芸術

この変化が重要であるのは、素晴らしいスケジュールを組むことは、科学であると同時に芸術でもあるからです。例えば、スケジューリング・プロセスの一つの目標は、視聴者を最大限に確保できるTV放映時間帯に好カードを組むことですが、これは、そう簡単にできることではありません。1週間内での各チームの連続アウェイゲーム数の上限など、数々の制約条件を満たしたスケジュールであることを保証しながら、対戦カードの主観的評価が必要となるためです。さらに、フリーエージェントなどを含む様々な要因によって、スケジューリング・プロセス中に主観的評価が大幅に変化することもあります。

芸術的要素は、スケジューリング・プロセスの中心です。プランナーたちは現在、システムから与えられたどのスケジュールも評価でき、そのスケジュールで何を変更したいかを見分けられ、また、それがスケジュール全体にどう影響するかも確認することができます。変更後のスケジュールが良くなっていれば、それが新しいリーダーになり、そうでなければ捨てられます。ほんの8年ほど前まで、プランナーが見ることができるスケジュールは、全部で5件くらいだったかもしれませんが、それが2014年のレギュラーシーズンのスケジューリングでは、Gurobiを使うことによって、1000もの実現可能なスケジュールを検討することができました。

線形計画から並列最適化へ

TNFLのスケジューリングにおける課題の複雑さは、この数年間で急激に増大しました。困難さの急激な増大に対処する戦略上重要な部分を占めているのは、コンピュータ・ハードウェアの大幅な増設です。NFLは24コアボックス1つでスタートしましたが、最近では16コア、40コア、さらに大きなサーバがずらりと並んだ部屋に移っています。

新しいテクノロジーを採用する際にしばしば起こるのですが、従来の戦略を適用しても、そのすべての利点を活かしきることはできません。そこでOptimal Planning Solutions社は、Gurobiの開発チームと協力し、並列処理を有効活用するためのアプローチを再考しました。その結果NFLは、2014年に初めて新しいアプローチを採用することができたのです。並列化アプローチの重要な利点は、一つの問題をいくつかのより小さい副問題に分割することに基づきます。副問題は問題解決のための資源プールに展開され、すべての資源は情報を共有でき、協調的な探索効果を作り出します。このアプローチによってNFLは、次のようなことが可能になりました。

  • 少数の既知解の狭い近傍を探索する方法に比べて、解空間全体からサンプリングすることで、実質的に解の質が向上しました。
  • 複数のマルチコアの問題解決をするボックスから、より小さく安価なハードウェア構成またはクラウドベースのテクノロジーに移行する選択肢も含め、将来のハードウェア構成により柔軟に対応できるようになりました。

将来の展望

2014年、NFLのスケジューリング問題は、750コア超のネットワーク上で解決されました。今後も難しい要件が継続して追加されていくためこの数字は確実に増え続け、クラウド環境に移行する可能性もあります。最適化ツールの強化と結びついた問題の複雑さが増していくなか、NFLのような経験豊富なエンドユーザとOptimal Planningのようなコンサルティング会社、そしてGurobiのようなソルバーの開発に専念している開発者集団の強固なパートナーシップは、よりいっそう重要性を増していくでしょう。

Gurobiのチームに切り替え協力できたことは、とても良い経験でした。GurobiのソルバーはNFLの高い期待に応えるもので、そのサポート体制も素晴らしいものでした。
– Michael North, Sr. Director, NFL

Gurobiのチームは、最高のパートナーでした。開発スタッフもサポートスタッフも、対応が迅速です。彼らのアイデアのおかげで、素晴らしい結果を出すことができました。
– Rick Stone, President,Optimal Planning Solutions

対象製品

Pickup導入事例

  • 最適化コンサルティング
  • 評価版ライセンス
  • 採用情報
  • お問合せ
PAGE TOP
Menu