スポーツスケジューリング問題 ~1993年Jリーグの再スケジューリング~ 文教大学 情報学部 経営情報学科 「シミュレーション」 2000年11月24日 東京大学 宮代 隆平 発表の概要 1993年Jリーグのスケジュールを 数理的手法を用いて改善 スポーツスケジューリング問題とは？ 1993年Jリーグのスケジュールと，その問題点 数理的手法によるスケジュールの改善過程＆結果 2 スポーツスケジューリング問題とは？ スポーツ競技（サッカー，バスケ，相撲，…）の “質の良い” スケジュールを作成する問題 → “良い（悪い）” スケジュールとは？ ・ 大相撲で，12日目に優勝力士が決まってしまう → 残りは消化取組になり，観客動員数減少 ・ ダイエー対巨人の日本シリーズ（7回戦） ただし，1～3戦が福岡，4～7戦が東京 → 不公平 3 スケジュール改善の例Ⅰ 5チームの総当りリーグ戦 チームＡ，Ｂが優勝候補とすると…（＊は休み） １ Ａ：Ｂ Ｂ：Ａ Ｃ：Ｅ Ｄ：＊ Ｅ：Ｃ ２ ＊ Ｃ Ｂ Ｅ Ｄ ３ Ｃ Ｄ Ａ Ｂ ＊ ４ Ｄ Ｅ ＊ Ａ Ｂ ５ Ｅ ＊ Ｄ Ｃ Ａ ⇒ １ Ａ：Ｅ Ｂ：Ｄ Ｃ：＊ Ｄ：Ｂ Ｅ：Ａ ２ Ｄ ＊ Ｅ Ａ Ｃ ３ ＊ Ｃ Ｂ Ｅ Ｄ ４ Ｃ Ｅ Ａ ＊ Ｂ ５ Ｂ Ａ Ｄ Ｃ ＊ 4 スケジュールに求められる要素 スケジュールを決定する時考慮すべき条件 試合の日時，競技場が使用可能か， 移動距離，本拠地 or 遠征，天気， ＴＶ放映，観客の満足度，チーム間の公平性， 各チームの強さ，… 最終目的は？ 費用削減，人気向上，興行収入増加，視聴率ｕｐ，… 5 スポーツスケジューリングの現状 現在，スポーツスケジューリングは ほとんど手作業で行われているのが現状 10チームの総当りリーグ戦の場合， 最低限の見積もりとして 9！（≒36万）通り以上のスケジュールが存在する → スケジューリングは適当でも良い？ 6 スポーツスケジューリングの重要性 ・ 移動距離減少をはかった問題では 手作業によるスケジュールと比較して5～30％減少 ・ ある種のスポーツではスケジュールが試合結果に 大きな影響を与える → 悪いスケジュールでは競技自体の人気も下落 ・ 現在はＴＶ中継の時代（放映料，視聴率） 7 スケジュール改善の例Ⅱ 5チームによる総当りリーグ戦 ただし，コートが一つしかない → 特定のチームが連続して試合することを避ける １２３４５６７８９10 １２３４５６７８９10 ＡＡＥＣＥＥＢＥＤＤ ⇒ ＣＢＡＢＡＢＤＡＣＡ ＢＣＤＤＡＣＣＢＢＡ ＤＥＣＤＥＣＥＢＥＤ 連戦が消失！ → 実は簡単？？ 8 スポーツスケジューリングの難しさ １２３４５６７８９ Ａ：Ｊ Ｆ Ｇ Ｃ Ｈ Ｂ Ｅ Ｂ：Ｉ Ｇ Ｄ Ｆ Ｅ Ａ Ｃ 10チームのリーグ戦 Ｃ：Ｈ Ｄ Ｅ Ａ Ｆ Ｇ Ｂ 6日目まで作成済み Ｄ：Ｇ Ｃ Ｂ Ｊ Ｉ Ｅ 7日目にＡ - Ｅ，Ｂ - Ｃの Ｅ：Ｆ Ｊ Ｃ Ｈ Ｂ Ｄ Ａ 対戦を組みたい Ｆ：Ｅ Ａ Ｉ Ｂ Ｃ Ｈ Ｇ：Ｄ Ｂ Ａ Ｉ Ｊ Ｃ Ｈ：Ｃ Ｉ Ｊ Ｅ Ａ Ｆ Ｉ：Ｂ Ｈ Ｆ Ｇ Ｄ Ｊ Ｊ：Ａ Ｅ Ｈ Ｄ Ｇ Ｉ 9 スポーツスケジューリングの難しさ １２３４５６７８９ Ａ：Ｊ Ｆ Ｇ Ｃ Ｈ Ｂ Ｅ Ｂ：Ｉ Ｇ Ｄ Ｆ Ｅ Ａ Ｃ 10チームのリーグ戦 Ｃ：Ｈ Ｄ Ｅ Ａ Ｆ Ｇ Ｂ 6日目まで作成済み Ｄ：Ｇ Ｃ Ｂ Ｊ Ｉ Ｅ Ｆ 7日目にＡ - Ｅ，Ｂ - Ｃの Ｅ：Ｆ Ｊ Ｃ Ｈ Ｂ Ｄ Ａ 対戦を組みたい Ｆ：Ｅ Ａ Ｉ Ｂ Ｃ Ｈ Ｄ Ｇ：Ｄ Ｂ Ａ Ｉ Ｊ Ｃ Ｈ：Ｃ Ｉ Ｊ Ｅ Ａ Ｆ Ｉ：Ｂ Ｈ Ｆ Ｇ Ｄ Ｊ Ｊ：Ａ Ｅ Ｈ Ｄ Ｇ Ｉ 10 スポーツスケジューリングの難しさ １２３４５６７８９ Ａ：Ｊ Ｆ Ｇ Ｃ Ｈ Ｂ Ｅ Ｂ：Ｉ Ｇ Ｄ Ｆ Ｅ Ａ Ｃ 10チームのリーグ戦 Ｃ：Ｈ Ｄ Ｅ Ａ Ｆ Ｇ Ｂ 6日目まで作成済み Ｄ：Ｇ Ｃ Ｂ Ｊ Ｉ Ｅ Ｆ 7日目にＡ - Ｅ，Ｂ - Ｃの Ｅ：Ｆ Ｊ Ｃ Ｈ Ｂ Ｄ Ａ 対戦を組みたい Ｆ：Ｅ Ａ Ｉ Ｂ Ｃ Ｈ Ｄ Ｇ：Ｄ Ｂ Ａ Ｉ Ｊ Ｃ Ｈ Ｈ：Ｃ Ｉ Ｊ Ｅ Ａ Ｆ Ｇ Ｉ：Ｂ Ｈ Ｆ Ｇ Ｄ Ｊ Ｊ：Ａ Ｅ Ｈ Ｄ Ｇ Ｉ 11 スポーツスケジューリングの難しさ １２３４５６７８９ Ａ：Ｊ Ｆ Ｇ Ｃ Ｈ Ｂ Ｅ Ｂ：Ｉ Ｇ Ｄ Ｆ Ｅ Ａ Ｃ 10チームのリーグ戦 Ｃ：Ｈ Ｄ Ｅ Ａ Ｆ Ｇ Ｂ 6日目まで作成済み Ｄ：Ｇ Ｃ Ｂ Ｊ Ｉ Ｅ Ｆ 7日目にＡ - Ｅ，Ｂ - Ｃの Ｅ：Ｆ Ｊ Ｃ Ｈ Ｂ Ｄ Ａ 対戦を組みたい Ｆ：Ｅ Ａ Ｉ Ｂ Ｃ Ｈ Ｄ Ｇ：Ｄ Ｂ Ａ Ｉ Ｊ Ｃ Ｈ Ｈ：Ｃ Ｉ Ｊ Ｅ Ａ Ｆ Ｇ Ｉ：Ｂ Ｈ Ｆ Ｇ Ｄ Ｊ Ｊ ← 既に対戦済！ Ｊ：Ａ Ｅ Ｈ Ｄ Ｇ Ｉ Ｉ 12 スポーツスケジューリングの難しさ １２３４５６７８９ Ａ：Ｊ Ｆ Ｇ Ｃ Ｈ Ｂ Ｅ Ｂ：Ｉ Ｇ Ｄ Ｆ Ｅ Ａ ↓ 7日目にＡ - Ｅの対戦 Ｃ：Ｈ Ｄ Ｅ Ａ Ｆ Ｇ Ｉ ↓ Ｄ：Ｇ Ｃ Ｂ Ｊ Ｉ Ｅ Ｃの相手は Ｉ のみ Ｅ：Ｆ Ｊ Ｃ Ｈ Ｂ Ｄ （Ｂ ｰ Ｃは不可能） Ｆ：Ｅ Ａ Ｉ Ｂ Ｃ Ｈ Ｇ：Ｄ Ｂ Ａ Ｉ Ｊ Ｃ 人間の目で判断するのは Ｈ：Ｃ Ｉ Ｊ Ｅ Ａ Ｆ 非常に難しい！ Ｉ：Ｂ Ｈ Ｆ Ｇ Ｄ Ｊ Ｊ：Ａ Ｅ Ｈ Ｄ Ｇ Ｉ 13 手作業での問題点 手作業では… ・ 全てのスケジュールを考慮するのは無理！ ・ 本当に最適？公平？ ・ この条件下でスケジュールが作成可能？ ・ 作成時間，各方面との調整，…（Jリーグは半年程 度） ・ 予定していた日に競技場が使えなくなった！ → 数理的手法の必要性 14 数理的手法の必要性 数理的手法を用いれば… ・ 制約を満たすスケジュールが短時間で作成可能 ・ 公平性，最適性が明らか ・ 最適化問題としてモデル化することにより， 条件の変化にも容易に対応可能 → 1993年Jリーグのスケジュールへ 15 1993年Jリーグの概略 Jリーグ開幕の年，サッカーブーム 10チームによる二重総当りリーグ戦 （後述） 第1節は土曜日，以降水曜日，土曜日，…（全18節） 5月15日（土）～7月14日（水） チーム略号 Ｋ：鹿島アントラーズ，Ｖ：ヴェルディ川崎， Ｍ：横浜マリノス，Ｅ：清水エスパルス，Ｊ：ジェフ市原， Ｓ：サンフレッチェ広島，Ｆ：横浜フリューゲルス，Ｇ：ガンバ大阪， Ｎ：名古屋グランパス， Ｒ：浦和レッズ 16 1993年Jリーグのスケジュール ① ２ ③ ４ ⑤ ６ ⑦ ８ ⑨ 10 ⑪ 12 ⑬ 14 ⑮ 16 ⑰ 18 Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ Ｆ Ｊ Ｇ Ｓ Ｖ Ｅ Ｋ Ｍ Ｒ Ｎ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ Ｖ Ｋ Ｓ Ｇ Ｒ Ｍ Ｎ Ｅ Ｆ Ｊ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ Ｊ Ｅ Ｒ Ｖ Ｋ Ｎ Ｇ Ｆ Ｓ Ｍ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ Ｒ Ｎ Ｅ Ｍ Ｆ Ｇ Ｊ Ｓ Ｖ Ｋ Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ Ｆ Ｊ Ｇ Ｓ Ｖ Ｅ Ｋ Ｍ Ｒ Ｎ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ Ｖ Ｋ Ｓ Ｇ Ｒ Ｍ Ｎ Ｅ Ｆ Ｊ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ Ｊ Ｅ Ｒ Ｖ Ｋ Ｎ Ｇ Ｆ Ｓ Ｍ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ Ｒ Ｎ Ｅ Ｍ Ｆ Ｇ Ｊ Ｓ Ｖ Ｋ Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ 17 二重総当りリーグ戦 あるチームが，他のチームとそれぞれ２回ずつ， １回は自分の本拠地で，１回は相手の本拠地に遠征して 試合を行う総当りリーグ戦の形式 Ａ： Ｂ： Ｃ： Ｄ： １ Ｂ Ａ Ｄ Ｃ ２ Ｄ Ｃ Ｂ Ａ ３ Ｃ Ｄ Ａ Ｂ ４ Ｃ Ｄ Ａ Ｂ ５ Ｄ Ｃ Ｂ Ａ ６ Ｂ ← ＡがＢの本拠地に遠征 Ａ ← Ｂは本拠地から動かず Ｄ Ａと試合 Ｃ 一般に，遠征は不利！ 18 ミラーリング 二重総当りリーグ戦のスケジューリングは， 場所付き（一重）総当りリーグ戦のスケジュールを作成し， 対戦場所を入れ換えたスケジュールを後半に接続すればできる （対戦間隔も開く） １ ２ ３ １ ２ ３ ｜ ４ ５ ６ Ａ：Ｂ Ｂ：Ａ Ｃ：Ｄ Ｄ：Ｃ Ｃ Ｄ Ａ Ｂ Ｄ Ａ：Ｂ Ｃ Ｃ ⇒ Ｂ：Ａ Ｄ Ｂ Ｃ：Ｄ Ａ Ａ Ｄ：Ｃ Ｂ Ｄ Ｃ Ｂ Ａ ｜ ｜ ｜ ｜ Ｂ Ａ Ｄ Ｃ Ｃ Ｄ Ａ Ｂ Ｄ Ｃ Ｂ Ａ 19 1993年スケジュールのミラーリング １９９３年Jリーグのスケジュールにおいて， ミラーリングの対応関係は （1，11），（2，10），（3，18），（4，12），（5，13）， （6，14），（7，15），（8，16），（9，17） → 理由は不明だが，最小対戦間隔は 十分に開いている（中7節） 20 1993年Jリーグのスケジュール ① ２ ③ ４ ⑤ ６ ⑦ ８ ⑨ 10 ⑪ 12 ⑬ 14 ⑮ 16 ⑰ 18 Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ Ｆ Ｊ Ｇ Ｓ Ｖ Ｅ Ｋ Ｍ Ｒ Ｎ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ Ｖ Ｋ Ｓ Ｇ Ｒ Ｍ Ｎ Ｅ Ｆ Ｊ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ Ｊ Ｅ Ｒ Ｖ Ｋ Ｎ Ｇ Ｆ Ｓ Ｍ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ Ｒ Ｎ Ｅ Ｍ Ｆ Ｇ Ｊ Ｓ Ｖ Ｋ Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ Ｆ Ｊ Ｇ Ｓ Ｖ Ｅ Ｋ Ｍ Ｒ Ｎ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ Ｖ Ｋ Ｓ Ｇ Ｒ Ｍ Ｎ Ｅ Ｆ Ｊ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ Ｊ Ｅ Ｒ Ｖ Ｋ Ｎ Ｇ Ｆ Ｓ Ｍ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ Ｒ Ｎ Ｅ Ｍ Ｆ Ｇ Ｊ Ｓ Ｖ Ｋ Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ 21 1993年スケジュールの分析 本拠地での試合をｈ（ホーム） 遠征先での試合をａ（アウェイ）と表記 10チームの二重総当りリーグ戦ではｈ，ａが9回ずつ ・ 各チームとも土曜日に4または5個のｈ （土曜日は観客動員数が水曜日の1.3倍） ・ 各チームとも前半（第1～9節）までに4または5個のｈ → この二点に関しては公平 22 1993年スケジュールの問題点 一般にａの連続は嫌われる → スケジュール中，チームＫの第9，10，11節のみ ａが3連続！（他チームにはない） 公平性？ また，土曜日のスケジュールのみを抜き出すと… → 観客にとって親切でない！ 23 1993年Jリーグのスケジュール ① ２ ③ ４ ⑤ ６ ⑦ ８ ⑨ 10 ⑪ 12 ⑬ 14 ⑮ 16 ⑰ 18 Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ Ｆ Ｊ Ｇ Ｓ Ｖ Ｅ Ｋ Ｍ Ｒ Ｎ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ Ｖ Ｋ Ｓ Ｇ Ｒ Ｍ Ｎ Ｅ Ｆ Ｊ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ Ｊ Ｅ Ｒ Ｖ Ｋ Ｎ Ｇ Ｆ Ｓ Ｍ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ Ｒ Ｎ Ｅ Ｍ Ｆ Ｇ Ｊ Ｓ Ｖ Ｋ Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ Ｆ Ｊ Ｇ Ｓ Ｖ Ｅ Ｋ Ｍ Ｒ Ｎ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ Ｖ Ｋ Ｓ Ｇ Ｒ Ｍ Ｎ Ｅ Ｆ Ｊ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ Ｊ Ｅ Ｒ Ｖ Ｋ Ｎ Ｇ Ｆ Ｓ Ｍ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ Ｒ Ｎ Ｅ Ｍ Ｆ Ｇ Ｊ Ｓ Ｖ Ｋ Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ 24 土曜日だけ着目すると… ① Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ ③ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ ⑤ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ ⑦ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ ⑨ Ｓ Ｇ Ｆ Ｒ Ｎ Ｋ Ｍ Ｖ Ｊ Ｅ ⑪ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ ⑬ Ｇ Ｒ Ｊ Ｎ Ｍ Ｆ Ｓ Ｋ Ｅ Ｖ ⑮ Ｍ Ｆ Ｋ Ｊ Ｅ Ｒ Ｖ Ｎ Ｇ Ｓ ⑰ Ｓ ← チームＫの場合， Ｇ 本拠地での土曜の試合は， Ｆ ⑤の次は⑮． Ｒ ⑤は 5 月 29 日で， Ｎ ⑮は 7 月 3 日． Ｋ 一ヶ月以上も間が開く！ Ｍ 水曜日だけ見ても同様． Ｖ Ｊ Ｅ 25 1993年スケジュールの問題点 ・ チームＫのみ，3連続ａがある ・ 土曜日（水曜日）のみを考えると， いくつかのチームに関して 本拠地での試合間隔が開きすぎ ・ 他にも様々な問題点 （本拠地が同一のＭとＦを考慮していない，…） → 数理的手法を用いて改善を試みる！ 26 全列挙法 全列挙して，最適なスケジュールを選択？ → 10チームの二重総当りリーグ戦 最低限のスケジュール総数は18！（≒6400兆） 1秒間に1億個のスケジュールが作れる 仮想計算機で 2年 ただ計算機を用いてもダメ！ → 当時論文で提案されていた方法を改良して使用 27 数理的手法の参考文献 参考文献 G. L. Nemhauser and M. A. Trick, “Scheduling a Major College Basketball Conference,” Operations Research, 46(1998), 1‐8. 実際に，米の大学バスケ対抗戦（9チーム）の スケジューリングを行った論文 → 数理的手法の説明 28 スケジュール スケジュール：最終的に求めたいもの １ ２ ３ １ ２ ３ Ａ：Ｂ Ｃ Ｄ Ａ：Ｂ Ｃ Ｄ Ｂ：Ａ Ｄ Ｃ Ｂ：Ａ Ｄ Ｃ Ｃ：Ｄ Ａ Ｂ Ｃ：Ｄ Ａ Ｂ Ｄ：Ｃ Ｂ Ａ， Ｄ：Ｃ Ｂ Ａ，… 29 パターンセット パターンセット：場所の情報のみがある表 任意の日に関して，ａとｈは等しい個数必要 １ ２ ３ １ ２ ３ １ ２ ３ Ａ：Ｂ Ｃ Ｄ Ｂ：Ａ Ｄ Ｃ ⇒ ａ ｈ ａ ＝ ｈ ａ ｈ Ｃ：Ｄ Ａ Ｂ ｈ ａ ａ Ｄ：Ｃ Ｂ Ａ ａ ｈ ｈ 30 パターン パターンセットの横一行だけを取り出した文字列 ａａａ，ａａｈ，ａｈａ，ａｈｈ，ｈａａ，ｈａｈ，ｈｈａ，ｈｈｈ それぞれのチームはこの文字列通り移動する パターン → パターンセット → スケジュール → 最適解 ↑ ↑ ↑ 制約条件 制約条件 制約条件 31 スケジュール作成までの流れ パターン － ｈｈａ，ａａｈ，ｈａａ，ａｈｈ ↓ パターンセット → スケジュール → 最終スケジュール ｈｈａ Ａ：ＢＣＤ Ａ：ＤＣＢ ａａｈ Ｂ：ＡＤＣ Ｂ：ＣＤＡ ｈａａ Ｃ：ＤＡＢ Ｃ：ＢＡＤ ａｈｈ Ｄ：ＣＢＡ，Ｄ：ＡＢＣ 32 パターンセット → スケジュール 一般に，1つのパターンセットからは… ・ 多数のスケジュールが生成される ・ スケジュールが全く生成できない → 不可能な例 １ ２ ３ ４ ５ （6チーム） ａ ｈ ｈ ａ ｈ ａ ｈ ａ ａ ｈ 与えられたパターンセットに， ａ ｈ ａ ｈ ｈ 各チームを割り当てることが可 能？ ｈ ａ ａ ｈ ａ （＝スケジュールを生成） ｈ ａ ｈ ｈ ａ → 整数計画問題として定式化 ｈ ａ ｈ ａ ａ 33 整数計画問題としての定式化 １２３ α：ｈ ａ ｈ x 2= 1 ： α→γが2日目に対戦する β：ｈ ａ ａ x 2= 0 ： α→γが2日目に対戦しない γ：ａ ｈ ｈ 対戦可能な変数のみを定義 δ：ａ ｈ ａ 全ての変数は0 - 1整数変数 基本的な制約条件 x 1 x 2 x 3 1 （βとγが必ず1回対戦） x 3 x 3 1 （αは3日目に必ず1試合行う） 34 整数計画問題の例 x121+x141+x321+x341+x212+x242+x312+x342+x213+x233+x413+x433=6, x121+x212+x213=1, x312=1, x141+x413=1, x321+x233=1, x242=1, x341+x342+x433=1, １２３ x121+x141=1, x212+x312=1, x213+x413=1, １：ａ ｈ ｈ x121+x321=1, x212+x242=1, x213+x233=1, ２：ｈ ａ ａ x321+x341=1, x312+x342=1, x233+x433=1, ３：ａ ａ ｈ x141+x341=1, x242+x342=1, x413+x433=1, ４：ｈ ｈ ａ ∀x∈｛0, 1｝. （x の添え字はａ，ｈ，日の順） 35 整数計画問題について 定式化した整数計画問題（今回の場合，225変数）は ソフトウェアに解かせる 問題に解がある ＝ パターンセットにチーム割当可能 問題が不能 ＝ パターンセットにチーム割当不可能 制約条件が少ないと時間がかかり，また多数の解 制約条件が多すぎると矛盾することが多い 36 スケジュールの作成 元のスケジュールより良いものを作りたい！ 問題点の復習 ・ チームＫのみ，3連続ａがある ・ 土曜日を考えると，いくつかのチームに関し 本拠地での試合間隔が開きすぎ ・ 他にも様々な問題点 （本拠地が同一のＭとＦを考慮していない，…） 37 前提条件 ・ 元のスケジュールより劣ったものは作らない（目標） ・ （変則的な）ミラーリングは同じとする ・ 開幕戦（第1節）と最終戦（第18節，第3節に対応）は 元のスケジュールと全く同じにする → スケジュール作成の実験開始 38 パターン生成 1993年はチーム数が10→ パターンの長さは9 ａａａａａａａａａ，ａａａａａａａａｈ，…，ｈｈｈｈｈｈｈｈｈ（512個） ・ 3連続ａ，3連続ｈはだめ ・ 土曜日には4または5個のｈ ・ 前半戦に4または5個のｈ ・ 土曜（水曜）だけ注目したとき，3連続ａ（ｈ）はだめ → 24個のパターンが残った 39 24個の許容パターン ａａｈｈａａｈｈａ， ａａｈｈａｈｈａａ， ａｈａａｈａａｈｈ， ａｈａａｈａｈｈａ， ａｈａａｈｈａａｈ， ａｈａａｈｈａｈａ， ａｈａａｈａｈｈａ， ａｈａａｈｈａａｈ， ａｈａａｈｈａｈａ， ａｈａｈｈａｈｈａ， ａｈａｈｈａａｈａ， ａｈａｈｈａａｈｈ， ｈａａｈａａｈｈａ， ｈａａｈａｈｈａｈ， ｈａｈａａｈａａｈ， ｈａｈａａｈｈａａ， ｈａｈａａｈｈａｈ， ｈａｈｈａａｈａａ， ｈａｈｈａａｈａｈ， ｈａｈｈａａｈｈａ， ｈａｈｈａｈａａｈ， ｈａｈｈａｈｈａａ， ｈｈａａｈａａｈｈ， ｈｈａａｈｈａａｈ 40 パターンからパターンセットへ 24個のパターンを10個組み合わせて， パターンセットを作る → 24Ｃ10≒200万 その中で，任意の日についてａとｈが等しい必要有り ａａｈ ａｈｈ → 200万個中，1382個が合格 ｈａｈ （計算時間5分） ｈｈａ ↑対戦不可能！ 41 思考錯誤 パターンセット1382個は候補が多すぎる！ 「第1,2節，第17,18節にａａを禁止」 （旧スケジュールは合計2チーム） パターンセットがただ1個に！！ しかし，スケジュール割当て不可能であった… → （やり直し） 42 パターンセットを減らす パターンセット1382個のうち， 実際に（1つ以上の）スケジュールを生成できるもの？ 整数計画問題に定式化して判定（1382問） → 208個が合格（計算時間約30分） 1つのパターンセットからは， 多数のスケジュールが生成可能．（まだまだ多い） 43 条件の適用 「第1,2節，第17,18節のａａをできるだけ避ける」 （旧スケジュールは合計2チーム） この条件を適用すると…，パターンセットが7個に！ 参考文献ではこの段階で17個 → 24時間 計算時間の見積り 24＊10＊7／17 ＝ 100時間 まだパターンセットが多い！（ここでしばらく挫折） 44 新たな制約条件の導入 チームＭとチームＦは本拠地が同一 ☆同時にホームゲームは戦えない！ 正反対のパターンが必要 （例） チームＭ：ａｈａａｈｈａａｈ チームＦ：ｈａｈｈａａｈｈａ → さらに，ＭとＦが対戦する日を考える 45 Ｍ－Ｆ条件の導入 チームＭ：ａｈａａｈｈａａｈ チームＦ：ｈａｈｈａａｈｈａ チームＭ，Ｆが上のパターンである時， ＭとＦが戦えるのは？（本拠地は同一） → 本拠地が3連続しないことを考えると チームＭ：ａｈａａｈｈａＦｈ 対戦可能なのは チームＦ：ｈａｈｈａａｈＭａ ← ここだけ！ 46 パターンセットの決定 ・ Ｍ－Ｆ条件 ・ 第1節と第18節を旧スケジュールと同一にする 以上の条件を考慮した結果， パターンセットは（運良く）1個に！ さらに，いくつかの試合が固定された → ここまでの状況 47 ここまで得られた条件 ① ２ ③ ４ ⑤ ６ ⑦ ８ ⑨ 10 ⑪ 12 ⑬ 14 ⑮ 16 ⑰ 18 Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ R,J: S,G: Ｆ：Ｅ S,G: Ｎ：Ｋ R,J: Ｅ Ｓ Ｎ Ｋ Ｒ Ｍ Ｆ Ｍ Ｎ Ｍ Ｖ Ｆ Ｅ Ｋ Ｆ Ｍ Ｅ Ｓ Ｎ Ｋ Ｒ Ｍ 48 さらなる工夫 前頁のパターンセットを整数計画問題として， 全ての解（＝スケジュール）を求めると… → 時間がかかりすぎていつ終わるか不明 チームＲ，Ｊ，Ｓ，Ｇの割り当ては4通り → 割り当てたスケジュールを解く！ （子問題に分割） 49 子問題の一例 ① ２ ③ ４ ⑤ ６ ⑦ ８ ⑨ 10 ⑪ 12 ⑬ 14 ⑮ 16 ⑰ 18 Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ Ｆ Ｍ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ Ｆ Ｍ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ 50 子問題に分割して解く チームＲ，Ｊ，Ｓ，Ｇを割り当て， 4つの整数計画問題に分割して解くと… → 問題Ⅰ 問題Ⅱ 問題Ⅲ 問題Ⅳ 合計 18個 6分 22個 7分 14個 2分 18個 4分 72個 20分 分割しないと，同じ72個を 得るのに56時間を要した！ 51 最終スケジュールの選択 得られた72個のスケジュール中， 少数のスケジュールを選択したい！ → 強豪チームとの連続対戦に注目 旧スケジュールでは8箇所 ただ1個のスケジュールが，8箇所未満（7）であった！ → スケジュールの紹介 52 新たに提案するスケジュール ① ２ ③ ４ ⑤ ６ ⑦ ８ ⑨ 10 ⑪ 12 ⑬ 14 ⑮ 16 ⑰ 18 Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ Ｒ Ｇ Ｓ Ｊ Ｅ Ｍ Ｎ Ｖ Ｆ Ｋ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ Ｓ Ｊ Ｅ Ｍ Ｖ Ｋ Ｇ Ｆ Ｒ Ｎ Ｖ Ｋ Ｇ Ｒ Ｆ Ｎ Ｊ Ｍ Ｓ Ｅ Ｆ Ｒ Ｊ Ｓ Ｍ Ｅ Ｋ Ｎ Ｇ Ｖ Ｍ Ｆ Ｋ Ｎ Ｒ Ｇ Ｖ Ｓ Ｅ Ｊ Ｊ Ｎ Ｆ Ｇ Ｋ Ｒ Ｍ Ｅ Ｖ Ｓ Ｇ Ｅ Ｒ Ｖ Ｎ Ｆ Ｓ Ｋ Ｊ Ｍ Ｒ Ｇ Ｓ Ｊ Ｅ Ｍ Ｎ Ｖ Ｆ Ｋ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ Ｓ Ｊ Ｅ Ｍ Ｖ Ｋ Ｇ Ｆ Ｒ Ｎ Ｖ Ｋ Ｇ Ｒ Ｆ Ｎ Ｊ Ｍ Ｓ Ｅ Ｆ Ｒ Ｊ Ｓ Ｍ Ｅ Ｋ Ｎ Ｇ Ｖ Ｍ Ｆ Ｋ Ｎ Ｒ Ｇ Ｖ Ｓ Ｅ Ｊ Ｊ Ｎ Ｆ Ｇ Ｋ Ｒ Ｍ Ｅ Ｖ Ｓ Ｇ Ｅ Ｒ Ｖ Ｎ Ｆ Ｓ Ｋ Ｊ Ｍ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ 53 新スケジュール（土曜日のみ） ① Ｋ：Ｎ Ｖ：Ｍ Ｍ：Ｖ Ｅ：Ｆ Ｊ：Ｓ Ｓ：Ｊ Ｆ：Ｅ Ｇ：Ｒ Ｎ：Ｋ Ｒ：Ｇ ③ Ｅ Ｓ Ｎ Ｋ Ｇ Ｖ Ｒ Ｊ Ｍ Ｆ ⑤ Ｖ Ｋ Ｇ Ｒ Ｆ Ｎ Ｊ Ｍ Ｓ Ｅ ⑦ Ｍ Ｆ Ｋ Ｎ Ｒ Ｇ Ｖ Ｓ Ｅ Ｊ ⑨ Ｇ Ｅ Ｒ Ｖ Ｎ Ｆ Ｓ Ｋ Ｊ Ｍ ⑪ Ｎ Ｍ Ｖ Ｆ Ｓ Ｊ Ｅ Ｒ Ｋ Ｇ ⑬ Ｖ Ｋ Ｇ Ｒ Ｆ Ｎ Ｊ Ｍ Ｓ Ｅ ⑮ Ｍ Ｆ Ｋ Ｎ Ｒ Ｇ Ｖ Ｓ Ｅ Ｊ ⑰ Ｇ 土曜日だけ見たときでも， Ｅ 遠征試合の連続を Ｒ 最大２回までに抑えている． Ｖ Ｎ Ｆ Ｓ Ｋ Ｊ Ｍ 54 スケジュールの比較 評価項目 ３連続アウェイ ３連続ホーム 土曜日３連続以上のａ 水曜日３連続以上のａ チームＭＦが同時にｈ 第1,2節，第17,18節にａａ 旧 １ ０（２） ５（４） ５ １ ２ 新 ０ ０ ０ ０ ０ ２ ほぼ全ての項目で，旧スケジュールより優れている！ 55 スケジュール計算過程 全パターン → パターン → パターンセット 512個 24個 （5分） 1382個 → スケジュール生成可能ＰＳ → 選択されたＰＳ （30分） 208個 7個 → 1個 最終ＰＳ → スケジュール → 最終スケジュール 1個 （20分） 72個 1個 56 問題点 ・ 現在はもっとチーム数が多い（16チーム） → 制約条件によっては可能 ・ 第1節と第18節を同じにすることの妥当性 → ＴＶ中継，企業秘密… ・ 解法全体として，場当たり的（Ｍ－Ｆ条件など） → 一般的なアルゴリズムの必要性 57 まとめ スポーツスケジューリング問題について概説し， 問題の重要性，数理的取り扱いの必要性を示した． 1993年Jリーグのスケジュールの問題点を指摘し， 数理的手法による再スケジューリングを行った． 提案する新スケジュールは，旧スケジュールにおける 問題点が全て改善されている． 58 参考文献 Webページ http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/sportsscheduling.html 日本語の解説記事 松井知己, 「スポーツのスケジューリング」, オペレーションズリサーチ，44 (1999), 141－146. 宮代隆平, 松井知己, 「1993年Jリーグの再スケジューリング」, オペレーションズ・リサーチ, 45 (2000), 81－83. お問い合わせは [email protected] まで 59
© Copyright 2024 ExpyDoc
