スポーツスケジューリング問題 （１９９９年２月）

宮代 隆平

卒業論文では、スポーツスケジューリング問題に取り組みました。 今回研究したのは、二重総当たりリーグ戦形式で対戦するスポーツ競技のスケジュールを決定する問題です。 スケジュール作成対象として、１９９３年のＪリーグを選びました。 理論の話はさておき、１９９３年に実際に行なわれたスケジュールを見てみましょう。

１９９３年Ｊリーグのスケジュール

↓日程＼チーム→ ： Ｋ Ｖ Ｍ Ｅ Ｊ Ｓ Ｆ Ｇ Ｎ Ｒ
−−−−−−−− −− − − − − − − − − − −
５／１５（土） ０１： Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ
５／１９（水） ０２： Ｆ Ｊ Ｇ Ｓ Ｖ Ｅ Ｋ Ｍ Ｒ Ｎ
５／２２（土） ０３： Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ
５／２６（水） ０４： Ｖ Ｋ Ｓ Ｇ Ｒ Ｍ Ｎ Ｅ Ｆ Ｊ
５／２９（土） ０５： Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ
６／２（水） ０６： Ｊ Ｅ Ｒ Ｖ Ｋ Ｎ Ｇ Ｆ Ｓ Ｍ
６／５（土） ０７： Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ
６／９（水） ０８： Ｒ Ｎ Ｅ Ｍ Ｆ Ｇ Ｊ Ｓ Ｖ Ｋ
６／１２（土） ０９： Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ
６／１６（水） １０： Ｆ Ｊ Ｇ Ｓ Ｖ Ｅ Ｋ Ｍ Ｒ Ｎ
６／１９（土） １１： Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ
６／２３（水） １２： Ｖ Ｋ Ｓ Ｇ Ｒ Ｍ Ｎ Ｅ Ｆ Ｊ
６／２６（土） １３： Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ
６／３０（水） １４： Ｊ Ｅ Ｒ Ｖ Ｋ Ｎ Ｇ Ｆ Ｓ Ｍ
７／３（土） １５： Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ
７／７（水） １６： Ｒ Ｎ Ｅ Ｍ Ｆ Ｇ Ｊ Ｓ Ｖ Ｋ
７／１０（土） １７： Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ
７／１４（水） １８： Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ

上の表が、１９９３年Ｊリーグのスケジュールです。 なお、１９９３年当時リーグ戦は年に２回行なわれていましたが、これは前半のリーグ戦です。 奇数番号の試合（１,３,…,１７試合目）は週末（土曜日）に、偶数番号の試合（２,４,…,１８試合目）は平日（水曜日）に行なわれました。 青の網掛けは、遠征する（アウェイゲーム、後述）という意味です。 つまり、１試合目にチームＶは自分の本拠地でチームＭと対戦し、２試合目にはチームＪの本拠地へ遠征して対戦します。

二重総当たりリーグ戦について簡単に説明します。 通常の総当たりリーグ戦はあるチームが他の全てのチームと１回ずつ対戦しますが、二重総当たりリーグ戦は２回対戦します。 ２回の対戦のうち、１回は自分の本拠地（ホーム）で、１回は敵の本拠地（アウェイ）で試合を行ないます。 ホームで行なう試合をホームゲーム、アウェイで行なう試合をアウェイゲームと呼びます。 一般に、どのチームもアウェイゲームよりホームゲームを好みます。

過去のスケジュールには、いくつかの問題点があります。 例えば、チームＫの９,１０,１１試合目は全てアウェイゲームです。 アウェイゲームは、チームにとって消耗が激しいため、３回以上連続するのは望ましくありません。 また、チームＭとチームＦは本拠地が同一であったため、チームＭの１６,１７,１８試合目とチームＦの８,９,１０試合目は、実質的にホームゲームの３回連続になっています。 これもアウェイゲームの３回連続と同じく望ましくありません。 また、週末だけ注目した時にアウェイゲームもしくはホームゲームが連続することも避けたい事の一つです。 週末は平日よりたくさんのお客さんが試合を見に来るので、週末に本拠地にいない期間が長く続くという状態は好ましくありません。 週末ほどではありませんが、平日だけ注目した時にも同じ事がいえます。 過去のスケジュールでは、例えばチームＫの７,９,１１,１３試合目が週末だけ注目した時にアウェイゲームが４回連続しています。 その他にも問題点はありますが、省略します。

以上のように、過去のスケジュールの問題点がわかったので、これを改善した新しいスケジュールを作成しました。 スケジュール作成には、参考文献の方法を改良して用いました。 下の表が新たに作成したスケジュールです。 計算時間は約１時間でした。 プログラムにはＣ言語を用いて、Ｗｉｎｄｏｗｓマシン上で計算しました。 スケジュール作成には整数計画問題を解く必要があるのですが、それにはＬＰ−Ｓｏｌｖｅという Public Domain Software を用いました。

新たに作成したスケジュール

↓日程＼チーム→ ： Ｋ Ｖ Ｍ Ｅ Ｊ Ｓ Ｆ Ｇ Ｎ Ｒ
−−−−−−−− −− − − − − − − − − − −
５／１５（土） ０１： Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ
５／１９（水） ０２： Ｒ Ｇ Ｓ Ｊ Ｅ Ｍ Ｎ Ｖ Ｆ Ｋ
５／２２（土） ０３： Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ
５／２６（水） ０４： Ｓ Ｊ Ｅ Ｍ Ｖ Ｋ Ｇ Ｆ Ｒ Ｎ
５／２９（土） ０５： Ｖ Ｋ Ｇ Ｒ Ｆ Ｎ Ｊ Ｍ Ｓ Ｅ
６／２（水） ０６： Ｆ Ｒ Ｊ Ｓ Ｍ Ｅ Ｋ Ｎ Ｇ Ｖ
６／５（土） ０７： Ｍ Ｆ Ｋ Ｎ Ｒ Ｇ Ｖ Ｓ Ｅ Ｊ
６／９（水） ０８： Ｊ Ｎ Ｆ Ｇ Ｋ Ｒ Ｍ Ｅ Ｖ Ｓ
６／１２（土） ０９： Ｇ Ｅ Ｒ Ｖ Ｎ Ｆ Ｓ Ｋ Ｊ Ｍ
６／１６（水） １０： Ｒ Ｇ Ｓ Ｊ Ｅ Ｍ Ｎ Ｖ Ｆ Ｋ
６／１９（土） １１： Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ
６／２３（水） １２： Ｓ Ｊ Ｅ Ｍ Ｖ Ｋ Ｇ Ｆ Ｒ Ｎ
６／２６（土） １３： Ｖ Ｋ Ｇ Ｒ Ｆ Ｎ Ｊ Ｍ Ｓ Ｅ
６／３０（水） １４： Ｆ Ｒ Ｊ Ｓ Ｍ Ｅ Ｋ Ｎ Ｇ Ｖ
７／３（土） １５： Ｍ Ｆ Ｋ Ｎ Ｒ Ｇ Ｖ Ｓ Ｅ Ｊ
７／７（水） １６： Ｊ Ｎ Ｆ Ｇ Ｋ Ｒ Ｍ Ｅ Ｖ Ｓ
７／１０（土） １７： Ｇ Ｅ Ｒ Ｖ Ｎ Ｆ Ｓ Ｋ Ｊ Ｍ
７／１４（水） １８： Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ

新たに作成したスケジュールでは、前述した問題点は全て消失しています。 （確かめてみて下さい。） その他の問題点も改善されています。

今回の研究では、参考文献のスケジュール作成方法を改良することにより、非常に短時間でスケジュールの作成が可能になりました。 作成したスケジュールの質も優れていることが確認できています。

参考文献
G. L. Nemhauser and M. A. Trick, ``Scheduling a Major College Basketball conference,'' Operations Research, 46(1998), 1-8. (LEC-97-03, The Logistics Institute, School of Industrial and Systems Engeneering, Gerogia Institute of Technology.)

松井知己, 「スポーツのスケジューリング」, オペレーションズ・リサーチ, 44(1999), 141-146.