1
スポーツスケジューリング問題
公平なリーグ戦スケジュールについて
ｖer. 1.0
東京大学 宮代隆平
東京大学 松井知己
卒論に! 1993とは？
2
1993年のＪリーグ前半戦のスケジュール
1993年のＪリーグ前半戦
1 2 3 4 5 6 7 8 9101112131415161718
K: N F E V G J M R S F N V G J M R S E
V: M J S K R E F N G J M K R E F N G S
M: V G N S J R K E F G V S J R K E F N
E: F S K G N V J M R S F G N V J M R K
J: S V G R M K E F N V S R M K E F N G
S: J E V M F N R G K E J M F N R G K V
F: E K R N S G V J M K E N S G V J M R
G: R M J E K F N S V M R E K F N S V J
N: K R M F E S G V J R K F E S G V J M
R: G N F J V M S K E N G J V M S K E F
読み方
3
1993年Ｊリーグ
1993年：Jリーグ開幕(前半戦)
10チーム２重総当たりリーグ戦
K:鹿島アントラーズ（予想５位）
V:ヴェルディ川崎（予想２位）
M:横浜マリノス（予想１位）
E:清水エスパルス（予想３位）
J:ジェフユナイテッド市原
S:サンフレッチェ広島
F:横浜フリューゲルス
G:ガンバ大阪
N:名古屋グランパスエイト（予想４位）
R:浦和レッドダイヤモンズ
2重総当り戦とは？
4
1993年のＪリーグ前半戦のスケジュール
２重総当りリーグ戦
1 2 3 4 5 6 7 8
K: N F E V G J M R
V: M J S K R E F N
M: V G N S J R K E
E: F S K G N V J M
J: S V G R M K E F
S: J E V M F N R G
F: E K R N S G V J
G: R M J E K F N S
N: K R M F E S G V
R: G N F J V M S K
9101112131415161718
S F N V G J M R S E
G J M K R E F N G S
F G V S J R K E F N
R S F G N V J M R K
N V S R M K E F N G
K E J M F N R G K V
M K E N S G V J M R
V M R E K F N S V J
J R K F E S G V J M
E N G J V M S K E F
読み方
5
2重総当りリーグ戦
チーム数2N（チーム数は偶数）
各チーム対は, 双方のホームグラウンドで1回ずつ
（計2回）戦う．
各試合日に N 試合を平行して行う.
２(２N －１）試合日ですべての試合が終了する．
４チームのスケジュール
1
A:C
B:D
C:A
D:B
2
D
C
B
A
3
B
A
D
C
4
D
C
B
A
5
B
A
D
C
6
C
D
A
B
BとDは第１試合日を
Bの本拠地で戦う．
6
スケジュールの見方
計10チーム
各日に５試合行い,18試合日で2重総当りリーグ戦を行う.
各チーム対は,双方のホームグラウンドで１回ずつ戦う.
RとGは第１試合日をRの本拠地で戦う．奇数試合日は週末．
K:
V:
M:
E:
J:
S:
F:
G:
N:
R:
1
N
M
V
F
S
J
E
R
K
G
2
F
J
G
S
V
E
K
M
R
N
3
E
S
N
K
G
V
R
J
M
F
4
V
K
S
G
R
M
N
E
F
J
5
G
R
J
N
M
F
S
K
E
V
6
J
E
R
V
K
N
G
F
S
M
7
M
F
K
J
E
R
V
N
G
S
8
R
N
E
M
F
G
J
S
V
K
9101112131415161718
S F N V G J M R S E
G J M K R E F N G S
F G V S J R K E F N
R S F G N V J M R K
N V S R M K E F N G
K E J M F N R G K V
M K E N S G V J M R
V M R E K F N S V J
J R K F E S G V J M
E N G J V M S K E F
ミラーリング
7
ミラーリング
1
A:C
B:D
C:A
D:B
2
D
C
B
A
3
B
A
D
C
4
D
C
B
A
5
B
A
D
C
6
C
D
A
B
前半2N -1試合を作れば，後半2N -1試合は，
前半のスケジュールの試合場を交代した
ものを付ければ良い．
8
1993年前半戦スケジュールのミラーリング
K:
V:
M:
E:
J:
S:
F:
G:
N:
R:
1
N
M
V
F
S
J
E
R
K
G
2
F
J
G
S
V
E
K
M
R
N
3
E
S
N
K
G
V
R
J
M
F
4
V
K
S
G
R
M
N
E
F
J
5
G
R
J
N
M
F
S
K
E
V
6
J
E
R
V
K
N
G
F
S
M
7
M
F
K
J
E
R
V
N
G
S
8
R
N
E
M
F
G
J
S
V
K
9101112131415161718
S F N V G J M R S E
G J M K R E F N G S
F G V S J R K E F N
R S F G N V J M R K
N V S R M K E F N G
K E J M F N R G K V
M K E N S G V J M R
V M R E K F N S V J
J R K F E S G V J M
E N G J V M S K E F
イタリアセリエAのミラーリングは，平行移動．
問題点
9
2001年のＪリーグ前半戦のスケジュール（１重総当たり戦）
16TEAMS
磐田 :
市原 :
名古屋:
浦和 :
C大阪 :
札幌 :
福岡 :
G大阪 :
横浜FM:
神戸 :
F東京 :
東京V :
柏
:
清水 :
鹿島 :
広島 :
1 2 3 4 5 6 7 8 9 101112131415
市広FT鹿CO名浦GO清札柏福横TV神
磐名柏福横FT鹿広TV神GO清札浦CO
浦市横FT鹿磐CO神GO清札柏福広TV
名CO福横FT鹿磐TV神GO清札柏市広
札浦鹿GO磐清名福広横TVFT神柏市
CO柏広TV神GO清FT鹿磐名浦市福横
GO清浦市広TV神CO横FT鹿磐名札柏
福横神CO清札柏磐名浦市広TVFT鹿
神GO名浦市広TV柏福COFT鹿磐清札
横FTGO清札柏福名浦市広TVCO鹿磐
TV神磐名浦市広札柏福横CO鹿GO清
FT鹿清札柏福横浦市広CO神GO磐名
清札市広TV神GO横FT鹿磐名浦CO福
柏福TV神GOCO札鹿磐名浦市広横FT
広TVCO磐名浦市清札柏福横FT神GO
鹿磐札柏福横FT市COTV神GO清名浦
読み方
10
総当りリーグ戦とグラフ
各チームを頂点とする完全グラフ．
各枝は試合に対応する．
各試合日には，全てのチームが１試合を戦う．
各試合日の試合は，グラフ上の完全マッチング．
F
F
A
E
A
E
B
D
B
D
C
C
11
総当り戦とマッチング
F
F
A
B
E
D
B
A５
E
A
B
D
B
C
E
A
D
B
１
C
C
F
F
A
F
２
C
F
E
A
D
B
ミラーリング
３
E
D
C
１２３４５ ６７８９10
A：B C D E F B C D E F
B：A D F C E A D F C E
C：F A E B D F A E B D
D：E B A F C E B A F C
E：D F C A B D F C A B
F：C E B D A C E B D A
E
４
C
D
12
うまく行かない例
F
F
A
E
B
D
残った試合は
C
F
F
A
B
E
１
D
C
A
B
２
C
E
A
D
B
A
E
B
D
F
３
C
E
D
C
１２３４５
A：B D C
B：A F E
C：F E A
後2日では終わらない
D：E A F
E：D C B
F：C B D
13
円盤の回転
以下のような円盤を回して，試合を決める．
A
A
B E
E
F
D
B E
D
A
B
E
F
F
C
A
B E F
A
C
D
１２３４５
A：F C E B D
B：E F D A C
C：D A F E B
D：C E B F A
E：B D A C F
F：A B C D E
C
D
C
F
D
B
C
12チームの場合
このまま回転を続ける‥‥.
実際のスケジュールは？
14
総当りリーグ戦の作り方
ホームゲーム･アウェイゲームを決める．
A
A
B E
E
F
D
B E
D
A
B
E
F
F
C
A
B E F
A
C
１２３４５
A：F C E B D
B：E F D A C
C：D A F E B
D：C E B F A
E：B D A C F
F：A B C D E
D
C
D
アウェイ
ゲームチーム
C
D
F
B
C
ホーム
ゲームチーム
実際のスケジュールは？
15
2重総当りリーグ戦の簡単な作り方（円盤＋ミラーリング）
６チーム(A,B,...,F)の例（試合数は 10）
アウェイ
ゲームチーム
A
A
B E
E
F
D
A
E
D
D
C
D
D
A
B E
B E
C
B E
D
C
A
F
F
C
A
C
D
F
B
F
F
C
B E
A
B E F
B E
A
F
D
A
F
C
ホーム
ゲームチーム
D
A
C
ミラーリング
B E
B
F
C
D
C
実際のスケジュールは？
16
2重総当りリーグ戦の簡単な作り方（対戦表）
（ミラーリング）
１２３４５６７８９10
A：F C E B D F C E B D
B：E F D A C E F D A C
C：D A F E B D A F E B
D：C E B F A C E B F A
E：B D A C F B D A C F
F：A B C D E A B C D E
白（ホームゲーム）や 黄(アウェイゲー
ム）
が連続しないのが好ましい．
17
1993年のＪリーグ前半戦のスケジュールの問題点
例：3連続アウェイゲームがある．
1 2 3 4 5 6 7 8 9101112131415161718
K: N F E V G J M R S F N V G J M R S E
V: M J S K R E F N G J M K R E F N G S
M: V G N S J R K E F G V S J R K E F N
E: F S K G N V J M R S F G N V J M R K
J: S V G R M K E F N V S R M K E F N G
S: J E V M F N R G K E J M F N R G K V
F: E K R N S G V J M K E N S G V J M R
G: R M J E K F N S V M R E K F N S V J
N: K R M F E S G V J R K F E S G V J M
R: G N F J V M S K E N G J V M S K E F
K:鹿島アントラーズ
M:横浜マリノス
本）
J:ジェフユナイテッド市原
F:横浜フリューゲルス（熊
望ましい
18
Home-Away Table (HAT)
Home-Away Table (HAT)
試合の開催地の情報のみを表したもの
１
１：３
２：４
３：１
４：２
２
２
１
４
３
３
４
３
２
１
スケジュール
１
１：Ａ
２：Ａ
３：Ｈ
４：Ｈ
２
Ａ
Ｈ
Ａ
Ｈ
３
Ｈ
Ａ
Ｈ
Ａ
Ａ:アウェイゲーム
Ｈ:ホームゲーム
HA-パターン:
HAT の各行
対応する HAT
HAT の性質を探る
19
1993年のＪリーグ前半戦のスケジュール(HAT）
K:
V:
M:
E:
J:
S:
F:
G:
N:
R:
1
H
H
A
A
A
H
H
H
A
A
2
H
A
H
H
H
A
A
A
A
H
3
A
A
A
H
A
H
H
H
H
A
4
A
H
A
A
H
H
A
H
H
A
5
H
A
H
H
A
A
H
A
A
H
6
H
A
A
H
A
A
H
A
H
H
7
A
H
H
A
H
H
A
H
A
A
8
H
A
A
H
A
A
H
H
H
A
9101112131415161718
A A A H A A H A H H
H H A A H H A H A H
H A H H A H A H A H
A A H H A A H A H A
H A H A H H A H A H
H H A A H H A H A A
A H A H A A H A H A
A H A A H H A A H A
A H H A H A H A H A
H A H H A A H H A H
望ましい
20
Basic Properties of HAT
HAT は以下の性質を満たす
（１）各スロットにおいて,
(# of Ａ) = (# of Ｈ)
１ ２ ３
１：Ａ Ａ Ｈ
２：Ａ Ｈ Ｈ
３：Ｈ Ａ Ｈ
４：Ｈ Ｈ Ａ
（２）HA パターンが
同じ行は存在しない
１：ＡＨＨＡＨ → この２チームは
２：ＡＨＨＡＨ
対戦できない
21
Infeasible HAT
前述の2つの性質を満たすHATは
対応するスケジュールがあるか? → NO
１
１：Ａ
２：Ａ
３：Ａ
４：Ｈ
５：Ｈ
６：Ｈ
２
Ｈ
Ｈ
Ｈ
Ａ
Ａ
Ａ
不能 HAT
３
Ｈ
Ａ
Ａ
Ａ
Ｈ
Ｈ
４
Ａ
Ａ
Ｈ
Ｈ
Ｈ
Ａ
５
Ｈ 1-2, 2-3, 3-1 の戦いは
Ｈ
スロット 3か 4
Ｈ
Ａ → このHATに
Ａ
対応する
Ａ
スケジュールは
存在しない
22
Undesired HAT
下記のHATは対応するスケジュールが存在する
１２３４５
１２３４５
１：Ａ Ａ Ａ Ａ Ａ
１：６ ２ ４ ５ ３
２：Ａ Ｈ Ａ Ｈ Ａ
２：３ １ ６ ４ ５
３：Ｈ Ｈ Ａ Ａ Ｈ → ３：２ ４ ５ ６ １
４：Ｈ Ａ Ｈ Ａ Ａ
４：５ ３ １ ２ ６
５：Ａ Ａ Ｈ Ｈ Ｈ
５：４ ６ ３ １ ２
６：Ｈ Ｈ Ｈ Ｈ Ｈ
６：１ ５ ２ ３ ４
許容 HAT
しかしながら，上記のスケジュールは良いものではな
い. (連続するアウェイゲームは好まれない)
23
Definition of Breaks
ブレーク：連続する Ａ または Ｈ (以下では下線で表
示)
１２３４５
１：Ａ Ａ Ａ Ａ Ａ
２：Ａ Ｈ Ａ Ｈ Ａ
３：Ｈ Ｈ Ａ Ａ Ｈ
４：Ｈ Ａ Ｈ Ａ Ａ
５：Ａ Ａ Ｈ Ｈ Ｈ
６：Ｈ Ｈ Ｈ Ｈ Ｈ →14
１２３４５
１：Ａ Ｈ Ｈ Ａ Ａ
２：Ｈ Ｈ Ｈ Ａ Ｈ
３：Ａ Ｈ Ａ Ｈ Ａ
４：Ｈ Ａ Ａ Ｈ Ｈ
５：Ａ Ａ Ｈ Ａ Ｈ
６：Ｈ Ａ Ａ Ｈ Ａ → 8
HATの公平性をブレークの数で測る.
(ブレーク数が少ない方が良い)
24
1993年のＪリーグ前半戦のスケジュール(ブレーク数）
1
H
H
A
A
A
H
H
H
A
A
2 3 4 5 6 7 8 9101112131415161718
K: H A A H H A H A A A H A A H A H H
V: A A H A A H A H H A A H H A H A H
M: H A A H A H A H A H H A H A H A H
E: H H A H H A H A A H H A A H A H A
J: H A H A A H A H A H A H H A H A H
S: A H H A A H A H H A A H H A H A A
F: A H A H H A H A H A H A A H A H A
G: A H H A A H H A H A A H H A A H A
N: A H H A H A H A H H A H A H A H A
R: H A A H H A A H A H H A A H H A H
2 2 6 0 8 0 2 0 4 2 6 0 8 0 2 0 2
週２試合のため，週日と週末がある.
7
5
2
5
2
6
2
6
3
6
43
望ましい
25
2001年のＪリーグ前半戦のスケジュール
磐田 :
市原 :
名古屋:
浦和 :
C大阪 :
札幌 :
福岡 :
G大阪 :
横浜FM:
神戸 :
F東京 :
東京V :
柏
:
清水 :
鹿島 :
広島 :
H
A
H
A
H
A
H
A
H
A
H
A
H
A
H
A
0
A H
H H
A H
H H
A H
H A
A A
H A
A A
H H
A A
H H
A A
H A
A A
H H
010
A
A
A
A
A
H
H
H
H
A
H
A
H
H
H
A
0
H
H
H
H
A
A
A
H
A
H
A
H
A
A
A
H
2
H
A
A
A
H
H
H
A
H
A
H
A
H
A
H
A
2
A
H
H
H
A
A
A
H
A
H
A
H
A
H
A
H
0
H
H
H
H
H
A
A
A
H
A
H
A
A
A
H
A
6
A
A
A
A
A
H
H
H
A
H
A
H
H
H
A
H
0
H
H
H
H
H
A
A
A
A
A
H
A
A
A
H
H
2
A
A
A
A
A
H
H
H
H
H
A
H
H
H
A
A
0
H
H
H
H
H
A
A
A
A
A
A
H
A
A
H
H
2
A
A
A
A
A
H
H
H
H
H
H
A
H
H
A
A
0
H
H
H
A
H
A
H
A
H
A
H
A
A
A
H
A
6
A 1
H 3
A 1
A 4
A 1
H 1
A 3
H 1
A 3
H 1
A 3
H 3
H 2
H 1
A 1
H 3
2 32
読み方
26
Equitable HAT
ブレーク数の意味で最も良いHATは？
(ブレーク数が少ない方が良い.)
ブレーク最小 HAT [de Werra’80]
補題：ブレーク数の最小値 ≧ チーム数－2
証明：ブレークの無いHA-パターンは２つ
AHAHAHAHAHAHA
HAHAHAHAHAHAH
許容HATの行は互い異なるHAパターンを持つ．
2チームはブレークを持たない.
他のチームは１つ以上のブレークを持つ.
27
2001年のＪリーグ前半戦のスケジュール
磐田 :
市原 :
名古屋:
浦和 :
C大阪 :
札幌 :
福岡 :
G大阪 :
横浜FM:
神戸 :
F東京 :
東京V :
柏
:
清水 :
鹿島 :
広島 :
H
A
H
A
H
A
H
A
H
A
H
A
H
A
H
A
0
A H
H H
A H
H H
A H
H A
A A
H A
A A
H H
A A
H H
A A
H A
A A
H H
010
A
A
A
A
A
H
H
H
H
A
H
A
H
H
H
A
0
H
H
H
H
A
A
A
H
A
H
A
H
A
A
A
H
2
H
A
A
A
H
H
H
A
H
A
H
A
H
A
H
A
2
A
H
H
H
A
A
A
H
A
H
A
H
A
H
A
H
0
H
H
H
H
H
A
A
A
H
A
H
A
A
A
H
A
6
A
A
A
A
A
H
H
H
A
H
A
H
H
H
A
H
0
H
H
H
H
H
A
A
A
A
A
H
A
A
A
H
H
2
A
A
A
A
A
H
H
H
H
H
A
H
H
H
A
A
0
H
H
H
H
H
A
A
A
A
A
A
H
A
A
H
H
2
A
A
A
A
A
H
H
H
H
H
H
A
H
H
A
A
0
H
H
H
A
H
A
H
A
H
A
H
A
A
A
H
A
6
A 1
H 3
A 1
A 4
A 1
H 1
A 3
H 1
A 3
H 1
A 3
H 3
H 2
H 1
A 1
H 3
2 32
読み方
28
2001年のＪリーグ後半戦のスケジュール
磐田 :
市原 :
名古屋:
浦和 :
C大阪 :
札幌 :
福岡 :
G大阪 :
横浜FM:
神戸 :
F東京 :
東京V :
柏
:
清水 :
鹿島 :
広島 :
H
H
H
H
H
A
A
A
H
A
H
A
A
A
H
A
0
A
A
A
A
A
H
H
H
A
H
A
H
H
H
A
H
0
H
A
H
H
H
A
H
A
H
A
H
A
A
A
H
A
2
A
H
A
A
A
H
A
H
A
H
A
H
H
H
A
H
0
H
A
A
A
H
H
H
A
H
A
H
A
H
A
H
A
4
A
H
H
H
A
A
A
H
A
H
A
H
A
H
A
H
0
A
A
A
A
H
H
H
A
H
A
H
A
H
H
H
A
2
H
H
H
H
H
A
A
A
A
H
A
H
A
A
A
H
2
A A
A A
A A
A A
A A
H H
H H
H H
H H
A H
H A
A H
H H
H H
H A
A A
012
H
H
H
H
H
A
A
A
A
A
H
A
A
A
H
H
0
A
A
A
A
A
H
H
H
H
H
H
A
H
H
A
A
2
H
H
H
H
H
A
A
A
A
A
A
H
A
A
H
H
0
H
A
H
A
H
A
H
A
H
A
H
A
H
A
H
A
8
A 3
H 2
A 3
H 2
A 3
H 3
A 2
H 3
A 1
H 1
A 1
H 1
A 2
H 3
A 1
H 1
0 32
読み方
29
セリエＡ2000/2001シーズン（２重総当たり戦）
Atlanta
:
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina :
Roma
:
Udinese
:
Verona
:
Vicenza
:
HAAHAHAHAHAHHAHAH
HAHAHHAHAHAHAAHAH
AHAHAHHAHAHAHAHAH
AHHAHAHAAHAHAHAHA
AHAHHAHAAHAHAHAHA
AHAHAHHAHAHAAHAHA
AHAHAHAHAHAAHHAHA
AHAHHAHAHAHAHAHAH
AHAHAAHAHAHAHHAHA
HAHAHAAHAHAHHAHAH
HAHAHAHAHAHHAAHAH
HAAHAHAHHAHAHAHAH
HAHAAHAHHAHAHAHAH
HAHAHAAHAHAHAHAHA
HAHAAHAHAHAHAHAHA
HAHAHAHAHAHHAHAHA
AHHAHAHAHAHAAHAHA
AHHAHAHAHAHAAHAHA
AHHAHAHAHAHAAHAHA
AHAHAAHAHAHAHHAHA
HAHAHAAHAHAHAHAHA
HAAHAHAHHAHAHAHAH
HAHAAHAHHAHAHAHAH
HAHAHAAHAHAHHAHAH
HAHAHAHAHAHHAAHAH
HAHAAHAHAHAHAHAHA
HAHAHHAHAHAHAAHAH
AHAHAHHAHAHAAHAHA
AHAHAHAHAHAAHHAHA
AHHAHAHAAHAHAHAHA
AHAHHAHAAHAHAHAHA
AHAHAHHAHAHAHAHAH
AHAHHAHAHAHAHAHAH
AHAHAHAHAHAAHAHAH
HAAHAHAHAHAHHAHAH
HAAHAHAHAHAHHAHAH
30
セリエＡ2000/2001シーズン（２重総当たり戦）
Atlanta
:
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina :
Roma
:
Udinese
:
Verona
:
Vicenza
:
HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA
HAHAHHAHAHAHAAHAHAHAHAAHAHAHAHHAHA
AHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHAHA
AHHAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAH
AHAHHAHAAHAHAHAHAHAHAAHAHHAHAHAHAH
AHAHAHHAHAHAAHAHAHAHAHAAHAHAHHAHAH
AHAHAHAHAHAAHHAHAHAHAHAHAHAHHAAHAH
AHAHHAHAHAHAHAHAHHAHAAHAHAHAHAHAHA
AHAHAAHAHAHAHHAHAHAHAHHAHAHAHAAHAH
HAHAHAAHAHAHHAHAHAHAHAHHAHAHAAHAHA
HAHAHAHAHAHHAAHAHAHAHAHAHAHAAHHAHA
HAAHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHA
HAHAAHAHHAHAHAHAHAHAHHAHAAHAHAHAHA
HAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAHAH
HAHAAHAHAHAHAHAHAAHAHHAHAHAHAHAHAH
HAHAHAHAHAHHAHAHAAHAHAHAHAHAAHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
31
セリエＡ2000/2001シーズン（ホームゲーム）
Atlanta
:
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina :
Roma
:
Udinese
:
Verona
:
Vicenza
:
H H H H H HH H H HH H H H H H H
H H HH H H H H H H H H H H HH H
H H HH H H H H HH H H H H H H H
HH H H H H H H H H H HH H H H H
H HH H H H H H H H H HH H H H H
H H HH H H H H H H H H H HH H H
H H H H H HH H H H H H H HH H H
H HH H H H H H HH H H H H H H H
H H H H H HH H H H HH H H H H H
H H H H H HH H H H H HH H H H H
H H H H H HH H H H H H H H HH H
H H H HH H H H H HH H H H H H H
H H H HH H H H H H HH H H H H H
H H H H H H H H H H HH H H H H H
H H H H H H H H H HH H H H H H H
H H H H H HH H H H H H H H H H H
HH H H H H H H H H H H H HH H H
HH H H H H H H H H H H H HH H H
030212020022200020202120200132000
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
2
2
33
32
セリエＡ2000/2001シーズン（アウェイゲーム）
Atlanta
:
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina :
Roma
:
Udinese
:
Verona
:
Vicenza
:
AA A A A A A A A A A A A AA A A
A A A A A AA A A A AA A A A A A
A A A A A A A A A A AA A A A A A
A A A AA A A A A AA A A A A A A
A A A AA A A A A A AA A A A A A
A A A A A AA A A A A AA A A A A
A A A A A AA A A A A A A A AA A
A A A A A A A A A AA A A A A A A
A A AA A A A A A A A A A A AA A
A A AA A A A A A A A A A AA A A
A A A A A AA A A A A A A AA A A
AA A A A A A A A A A AA A A A A
A AA A A A A A A A A AA A A A A
A A AA A A A A AA A A A A A A A
A AA A A A A A AA A A A A A A A
A A A A A A A AA A A A A AA A A
A A A A A AA A A AA A A A A A A
A A A A A AA A A AA A A A A A A
020212020013200030302120200222000
2
2
1
2
2
2
2
1
2
2
2
2
2
2
2
2
2
2
34
33
セリエＡ2000/2001シーズン （ブレーク数）
Atlanta
:
Bari
:
Bologna
:
Brescia
:
Fiorentina:
Inter
:
Juventus :
Lazio
:
Lecce
:
Milan
:
Napoli
:
Parma
:
Perugia
:
Reggina :
Roma
:
Udinese
:
Verona
:
Vicenza
:
HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA
HAHAHHAHAHAHAAHAHAHAHAAHAHAHAHHAHA
AHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHAHA
AHHAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAH
AHAHHAHAAHAHAHAHAHAHAAHAHHAHAHAHAH
AHAHAHHAHAHAAHAHAHAHAHAAHAHAHHAHAH
AHAHAHAHAHAAHHAHAHAHAHAHAHAHHAAHAH
AHAHHAHAHAHAHAHAHHAHAAHAHAHAHAHAHA
AHAHAAHAHAHAHHAHAHAHAHHAHAHAHAAHAH
HAHAHAAHAHAHHAHAHAHAHAHHAHAHAAHAHA
HAHAHAHAHAHHAAHAHAHAHAHAHAHAAHHAHA
HAAHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHA
HAHAAHAHHAHAHAHAHAHAHHAHAAHAHAHAHA
HAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAHAH
HAHAAHAHAHAHAHAHAAHAHHAHAHAHAHAHAH
HAHAHAHAHAHHAHAHAAHAHAHAHAHAAHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH
050424040035400050504240400354000
4
4
3
4
4
4
4
3
4
4
4
4
4
3
3
3
4
4
67
34
Equitable HAT
ブレーク最小 HAT [de Werra’80]
１２３４５
ブレーク数最小値=(チーム数－2) A：F C E B D
B：E F D A C
2チームはブレークを持たない
C：D A F E B
他のチームは
D：C E B F A
ちょうど１つのブレークを持つ
E：B D A C F
F：A B C D E
A
A
B E
E
F
D
B E
D
A
B
E
F
F
C
A
B E F
A
C
D
C
D
C
D
F
B
C
ブレーク最小HATは公平さの観点からは好ましくない．
35
Equitable HAT
均等 HAT [de Werra’80]
各チームが丁度1つのブレークを持つ
(総ブレーク数 = 2N)
A
E
D
B E
F
C
A
B E
F
D
C
１２３４５
A：F C E B D
B：E F D A C
C：D A F E B
D：C E B F A
E：B D A C F
F：A B C D E
A
A
A
BE F B E F B
F
D C
D
C
D
１２３４５１
A：F C E B D F
B：E F D A C E
C：D A F E B D
D：C E B F A C
E：B D A C F B
F：A B C D E A
均等HATの性質について探る！
(ブレーク最小HATとほぼ同じ!？）
C
36
補完パターン
均等HATの各行（HA-パターン）は下記のよう
にブレークが1つあるもの．
HAHAHAHAHHAHAHA ：HA-パターン
AHAHAHAHAAHAHAH ：補完パターン
補題：均等許容HATがあるHA-パターンを含む
ならば，その補完パターンも含む．
証明： （背理法）
s
あるパターン： ‥‥‥‥AHAAHA‥‥‥‥‥
‥‥‥‥HAHAHA‥‥AA ‥
‥‥‥‥HAHAHA ‥ HH‥‥
‥‥AA‥AHAHAH‥‥‥‥‥
sスロットとs+1スロットのHとAの数が異なる．矛盾.
37
Example of Equitable HAT
１２３４５
１：Ａ Ａ Ｈ Ａ Ｈ
２：Ａ Ｈ Ｈ Ａ Ｈ
３：Ａ Ｈ Ａ Ｈ Ｈ
４：Ｈ Ｈ Ａ Ｈ Ａ
５：Ｈ Ａ Ａ Ｈ Ａ
６：Ｈ Ａ Ｈ Ａ Ａ
１２３４５
１：Ａ Ａ Ｈ Ａ Ｈ
２：Ａ Ｈ Ｈ Ａ Ｈ
３：Ａ Ｈ Ａ Ａ Ｈ
４：Ｈ Ｈ Ａ Ｈ Ａ
５：Ｈ Ａ Ａ Ｈ Ａ
６：Ｈ Ａ Ｈ Ｈ Ａ
均等HATは（補完パターンを含んでいて
も）許容HATであるとは限らない.
38
Opening and Closing Condition
HA-パターン…
ＡＡ または ＨＨ で始まるならば
HA-パターン は 開幕条件を満たさない と言う.
ＡＡ または ＨＨで終わるならば
HA-パターン は 閉幕条件を満たさない と言う.
上記のような HA-パターン は，閉開幕におけ
る観客の動員数に悪影響を与える．
ミラーリングを施した後，３連続 Ａ または Ｈ
が出現する．
39
Consideration of Mirroring
均等 HAT が以下の HA-パターン を含むなら
(ＡＡ…), (ＨＨ…), (…ＡＡ), (…ＨＨ),
ミラーリングをして得られる HAT は
3 連続の Ａ(または Ｈ) を持つ.
ＡＡＨ…ＡＨ → ＡＡＨ…Ａ Ｈ∥ＨＨ Ａ…ＨＡ,
ＨＨＡ…ＨＡ → ＨＨＡ…Ｈ Ａ∥ＡＡ Ｈ…ＡＨ,
ＡＨＡ…ＨＨ → ＡＨＡ… ＨＨ∥Ｈ ＡＨ…ＡＡ,
ＨＡＨ…ＡＡ → ＨＡＨ… ＡＡ∥Ａ ＨＡ…ＨＨ,
ミラーリング後
40
The Number of Candidates for Feasible HAT
今迄の条件をすべて満たす HAT はいくつあるの
か？
(1)各日のHとAの数が同じ. (2)同じ行が無い.
(3)均等HAT. (4)補完パターンを含む.
(5)開閉幕条件を満たす.
#teams #HAT
6
0
8
1
#HAT:条件(1)～(5)を満たす
10
6
HAT の数
12
28
許容HATとは限らない
14 120
16 495
→ このうち許容HATはいくつ？
18 2002
20 8008
41
Checking Feasibility of HAT
今迄の条件をすべて満たす HAT はいくつあるのか？
与えられた HATが許容HATであるかを判定す
る問題を, 整数計画問題に定式化する.
この問題はN2(2N－1) 個の0-1 変数を持つ.
IP が許容解を持つ ⇔ HAT は許容HATである
42
スケジュールを作る 0-1 整数計画法
HAT
1
B:A
A:H
C:A
D:H
2
A
H
H
A
3
H
A
A
H
4
H
A
H
A
5
H
A
A
H
6
A このHATに対応する，
H
スケジュールを求めよう．
H
A (ミラーリング)
1 （ AとBが１日目に戦う），
｛
ｘAB1 ＝
0 （ AとBが１日目に戦わない）.
ｘAB1 , ｘAB2 , ｘAB3 , ｘAC1 , ｘAC2 , ｘAC3 ,
ｘAD1 ,ｘAD2 , ｘAD3 , ｘBC1 , ｘBC2 , ｘBC3 ,
ｘBD1 ,ｘBD2 , ｘBD3 , ｘCD1 , ｘCD2 ,ｘCD3 .
43
0-1 整数計画問題
ｘAB1+ｘAB2+ｘAB3 =1, （AとBはどこかで戦う）
ｘAC1+ｘAC2+ｘAC3 =1, （AとCはどこかで戦う）
ｘAD1+ｘAD2+ｘAD3 =1, （AとDはどこかで戦う）
‥‥
ｘCD1+ｘCD2+ｘCD3 =1, （CとDはどこかで戦う）
ｘAB1+ｘAC1+ｘAD1 =1, （１日目Aは誰かと戦う）
ｘAB1+ｘBC1+ｘBD1 =1, （１日目Bは誰かと戦う）
ｘAC1+ｘBC1+ｘCD1 =1, （１日目Cは誰かと戦う）
‥‥
ｘAD3+ｘBD3+ｘCD3 =1, （３日目Dは誰かと戦う）
ｘAC2=ｘAC3=ｘAD1=ｘBC1=ｘBD2=ｘBD3= 0,
}
}
4C2=6本
4×3=12本
残りの変数（１２個）は，0または1を取る.
スケジュールを全部見つける=上記を満たすもの全て見つける
0-1整数計画法 ：0-1変数12個，等式18本.
44
The Number of Candidates for Feasible HAT
#teams #cand.(#vars.)
6
0 (45)
#cand.: 開閉幕条件を満たす
8
1 (112)
均等HATの数
10
6 (225) (許容HATの候補数)
12
28 (396)
14 120 (637) #vars. : 対応する整数計画問題
16 495 (960)
の0-1変数の数
18 2002 (1377) (チーム数 2N , 変数 N2(2N－
1))
20 8008 (1900)
すべてのIPを解くのは非現実的!
45
Triple Break Constraints
与えられた HAT に，スロットs, s+1, s+2 にブ
レークが在る3行の HA-パターン があるなら
ば，
ＡＨＡ ＡＨ ＡＨ
ＡＨＡ ＨＨ ＡＨ
ＡＨＡ ＨＡ ＡＨ
与えられた HAT は不能!
与えられた HAT が上記のような
3つの HA-パターン を含んでいるかのチェックは
IPを解くより容易である.
３連続ブレーク条件
46
Applying Triple Break Constraints
#teams #cand. #tri.
6
0
0
8
1
0
10
6
0
12
28
1
14 120
4
16 495
15
18 2002
50
20 8008 161
#cand.: 許容HATの候補数
#tri.: 許容HATの新たな候補数
for feasible HAT
(3連続ブレーク条件を適用)
許容HATの候補数は非常に減る.
(上記の3連続ブレーク条件のチェックは1分以下)
47
The Number of Feasible HAT
#teams #triple (#vars.) #feasible
6
0 (45)
0
8
0 (112)
0
CPU: Pentium II
10
0 (225)
0
400 MHz,
12
1 (396)
0
OS: Windows 98,
14
4 (637)
0
RAM: 128MB,
16
15 (960)
1
IP Solver:
18
50 (1377)
0
ILOG OPL Studio 3.0
20
161 (1900)
4
CPLEX
総計算時間 : 3.5 時間
48
Results of Experiment
許容HATの数は 非常に少ない.
チーム数 ∈{6, 8, 10, 12, 14, 18}については,
許容 HATは存在しない
(チーム数 = 16) → 1 HAT
(チーム数 = 20) → 4 HAT
現実的な計算時間 (3.5 時間)
49
Unique Feasible HAT (16 teams)
１ ２ ３ ４ ５ ６ ７ ８ ９ 10 11 12 13 14 15
１：Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ
２：Ａ Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ
３：Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ
４：Ａ Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ
５：Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ Ｈ
６：Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ
７：Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ Ｈ
８：Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ
９：Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ
10：Ｈ Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ
11：Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ
12：Ｈ Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ
13：Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ Ａ
14：Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ
15：Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ Ａ
16：Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ
50
Conclusion & Future Work
結論
現実的なチーム数 (20以下) においては，設定
した性質を満たす許容HATは非常に少ない．
HATすべての許容性をチェックする問題は，適
切な制約を導入することにより，現実的な計
算時間で可能となる．
今後の研究
一般のHATに対する算法の設計 (均等とは限
らないHAT)
どんなスケジュールが欲しいのか？
51
スポーツスケジューリングの研究を発展させるために
ホームページの公開 ： 簡略ページ ・ 詳細ページ
研究発表 統計研, 南山大学, 文教大学, 東京大学, 班会議
関連記事の雑誌掲載
サーベイ： 松井知己, 「スポーツのスケジューリング」,
オペレーションズリサーチ，44 (1999), 141－146.
入門編： 宮代隆平, 松井知己,
「1993年Jリーグの再スケジューリング」,
オペレーションズ・リサーチ, 45 (2000), 81－83.
関連研究（者）の交流
東大, 筑波大, 東京理科大, 中央大, 東海大
応用から実務へ？ どんな目的関数？モデル化
52
おわり
53
1993年のＪリーグ前半戦のスケジュール
２重総当りリーグ戦（原本）
1 2 3 4 5 6 7 8 9101112131415161718
K: N F E V G J M R S F N V G J M R S E
V: M J S K R E F N G J M K R E F N G S
M: V G N S J R K E F G V S J R K E F N
E: F S K G N V J M R S F G N V J M R K
J: S V G R M K E F N V S R M K E F N G
S: J E V M F N R G K E J M F N R G K V
F: E K R N S G V J M K E N S G V J M R
G: R M J E K F N S V M R E K F N S V J
N: K R M F E S G V J R K F E S G V J M
R: G N F J V M S K E N G J V M S K E F
54
今後の課題
手作業の部分は，問題例依存の性質を用いている．
1993年を選んだのは10チームと少なかったから．
今回の方法では16チームは無理！
1999年：２リーグ制
Ｊ1：16ﾁｰﾑ．試合は週末のみ．(1重)総当り戦．
Ｊ２：10ﾁｰﾑ．試合は週末のみ．４重総当り戦．
入っていない因子：
TV放映．グラウンド使用可能日．チーム移動費
用？
消化試合を減らす（好カードを後に残す）．
Nemhauser and Trick の open problem
与えられたｈａテーブルに対応するタイムテーブルはある
か？
NP-complete?
© Copyright 2024 ExpyDoc
