スポーツスケジューリング

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

Download Report