ある最適化問題 スポーツスケジューリング スポーツスケジューリングとは? 生成方法 プログラムと問題点 2001年2月7日(水) 12月8日発表分資料 2001年2月7日(水) 5497039 5497044 加倉田 稔 木本 公康
スポーツスケジューリングとは?
概要と我々の構想 ゲームの面白さ 視聴率の向上 経費の削減 対戦の組み合わせ 試合会場 チーム間の公平性 2重総当たり戦は考えない TV放映のスケジュール 視聴率の向上 チームの移動 経費の削減 この条件をもとにスケジュールを作る事は困難である。
生成方法 slotとB Patternのランク 探索の構造 整数計画法 予備知識
予備知識 同一チームが1日に2試合以上行わないとする 各試合日で全てのチームが試合を行う slot 各チームのスケジュールは配列で表現する 試合の日程 例:slot0=1日目 slot1=2日目 各チームのスケジュールは配列で表現する Pattern : 長さがslotで、H・A(・B)からなる配列。 H A B H ホームゲーム A アウェイゲーム B 休日(チーム数が奇数の場合のみ使用)
slotとB(1日休日) チーム数(n)が偶数 slotの数と1つのチームが行う試合数が等しい 1 2 3 n n-1 B slot=n 奇数 偶数
探索の構造 STEP1 : 全ての組み合わせのPatternを生成し、 使用可能なものを選ぶ。 探索手順 STEP1 : 全ての組み合わせのPatternを生成し、 使用可能なものを選ぶ。 STEP2 : Patternの集合の中からチーム数と 等しい数だけ選ぶ。 その集合を Pattern Set と呼ぶ。 STEP3 : Pattern Setに試合を割り当てる。 これを Time Table と呼ぶ。
H H H H H H H H H H H A H A A A A A A A A A A A P STEP1 Pattern STEP2 Pattern Set H H H ・・・ H H H ・・ ・・ H H H ・・・ H H A ・・・ pCn個 H A A ・・・ A A A A A A ・・・ A A A slot (slot-1) 偶:2 奇:2 ×slot ・・・ 5チームなら5個のpatternしかないと思う人がいるかもしれないが、それは×。 まず、全てのpatternの組み合わせを生成し、使用可能なものをPの集合とする。 それからチーム数分抜き取る(pattern set)。このときに初めてpatternに仮チーム名が書き加えられる。 P STEP3 Time Table p個 ・・ ・・・
STEP1 Pattern生成の条件 Patternの長さがslot。 チーム間の公平性より、H・Aの数を下記に示す。 Hの数 Aの数 Bの数 n:偶数 slot=n-1 slot/2 n:奇数 slot=n 1 Patternの中に、3連続H・Aがない。 上記の条件に合っていても「あまり好ましくない」状態がある。 それらに値を与え、ランクをつける。
「あまり好ましくない」状態を値にする 試合日程 状態 悪さ 全ての日程内の4連戦 HBHH,HHBH 1 最初、最後以外の3連戦 AAB,ABA,BAA 2 最初の2試合 AA 3 2試合 AB,BA 4 3試合 AAB,ABA,BAA 5 最後の2試合 AA 6 2試合 AB,BA 7 3試合 AAB,ABA,BAA 8
STEP2 Pattern Setの生成 P ・・・ H A B 使用可能なPatternの集合(P)からチーム数分選ぶ。 ・あるPattern set内に同じPatternが存在しない。 各slotのH・Aの数が等しい。 チーム数が奇数の場合、各slotにBが1つある。 P slot4 slot3 slot2 slot1 slot0 1 2 3 4 5 H A B ・・・
整数計画法とは? 制約文 目的関数 3x + 2y ≦ 7 5x + 6y ≦ 13 x ≧ 0 y ≧ 0 x + y 線形計画問題に「変数は整数値しかとらない」という制約(整数制約)を加えたもの x+y=k (2 , 0.5)
整数計画法によるPattern Set生成 P:Patternの集合 T:slotの集合 X i :Pattern i をPattern Setに加えるとき1、それ以外0 h i k :Pattern i がslot kでHのとき1、それ以外0 a i k :Pattern i がslot kでAのとき1、それ以外0 b i :Pattern iの悪さ値 目的関数<Patternの悪さの合計> Min : Σ{i Є P} b i X i 制約文 <slot k のH・Aの数> Σ{i Є P} h i k X i = n/2 for all k∈T Σ{i Є P} a i k Xi = n/2 for all k∈T <Patternの数> Σ{i Є P} X i = n for all i ∈ P
STEP3 Time Tableの生成 5 4 3 2 1 H A B 3 2 4 5 B 1 H・Aの組み合わせで1試合を割り当てる。 Pattern Set に全てのチームが他のチームと1回試合を行うように試合を割り当てる。 各slotで全てのチームが試合を行う。(Bは除く) slot4 slot3 slot2 slot1 slot0 5 4 3 2 1 H A B 3 2 4 5 B 1 A H
整数計画法によるTime Tableの生成 X i j k :slot k でPattern i がPattern j と試合をする とき1、それ以外0 S :Pattern Set内のPatternの集合 F :(i, j, k)の集合 T :slotの集合 目的関数 <Time Tableの試合数> Max : Σ{(i,j,k)ЄF} X i j k 制約文 <Time Table 内でi と jの試合が一回のみ> Σ{k : (i,j,k)ЄF} X i j k = 1 for all i,j∈S , i≠j <slot k で全てのチームが1回試合を行う> Σ{j : (i,j,k)ЄF} X i j k ≦ 1 for all i∈S , k∈T
プログラムと問題点 実験結果 計算量 問題点 課題と可能性
プログラム 整数計画法のプログラム 世の中には整数計画法のエンジンなどが存在するが、 今回はPattern Set , Time Tableにそれぞれ対応した プログラムを作成した。 プログラムの計算量 n:チーム数 n 2 Ο(n ×2 )
実験結果 Pattern Pattern Set Time Table 5 24 76 48 6 10 1 8 7 86 スペック:CPU733MHz メモリー128MHz Pattern Pattern Set Time Table 5 24 76 48 6 10 1 8 7 86 83812(36分) 536836(77秒) 138 82688(14秒) 9 270 X 61 283440(14時間)
問題点 スポーツの種類・放送・チームの現状などにより制約が変化する。 チーム数が多くなると計算が膨大になる。 最良のスケジュールがいくつもでる可能性がある。 現状のスポーツスケジュール問題の最終決定は人の手作業になってしまうのか?
今後の我々の課題と可能性 課題 ・ PatternによってはPattern Set・Time Table が大量にできる。又は1個もできない場合の可能性がある。 可能性 ・ プログラムの効率化 ・ ある種のスポーツに特化したプログラムの作成
STAFF ower .Kimoto .Kakurata esume rogram M ● K P P ● K M R ● K M oint .Kimoto .Kakurata esume rogram .C Special Thanks ● TEAM Knot M ● K P P ● K M R ● K M P ● M K Presented by TEAM SPORTS