スポーツスケジューリング問題 公平なリーグ戦スケジュールについて ｖer. 1.0

Presentation on theme: "スポーツスケジューリング問題 公平なリーグ戦スケジュールについて ｖer. 1.0"— Presentation transcript:

1 スポーツスケジューリング問題 公平なリーグ戦スケジュールについて ｖer. 1.0
東京大学 宮代隆平 東京大学 松井知己 卒論に! 1993とは？

2 K: N F E V G J M R S F N V G J M R S E
1993年のＪリーグ前半戦のスケジュール 1993年のＪリーグ前半戦 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年：Jリーグ開幕(前半戦) 10チーム２重総当たりリーグ戦 K:鹿島アントラーズ（予想５位） V:ヴェルディ川崎（予想２位）
1993年Ｊリーグ 1993年：Jリーグ開幕(前半戦) 10チーム２重総当たりリーグ戦 K:鹿島アントラーズ（予想５位） V:ヴェルディ川崎（予想２位） M:横浜マリノス（予想１位） E:清水エスパルス（予想３位） J:ジェフユナイテッド市原 S:サンフレッチェ広島 F:横浜フリューゲルス G:ガンバ大阪 N:名古屋グランパスエイト（予想４位） R:浦和レッドダイヤモンズ 2重総当り戦とは？

4 K: N F E V G J M R S F N V G J M R S E
1993年のＪリーグ前半戦のスケジュール ２重総当りリーグ戦 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 読み方

5 A:C D B D B C B:D C A C A D C:A B D B D A D:B A C A C B 1 2 3 4 5 6
2重総当りリーグ戦 チーム数2N（チーム数は偶数） 各チーム対は, 双方のホームグラウンドで1回ずつ（計2回）戦う． 各試合日に N 試合を平行して行う. ２(２N －１）試合日ですべての試合が終了する． ４チームのスケジュール A:C D B D B C B:D C A C A D C:A B D B D A D:B A C A C B BとDは第１試合日を Bの本拠地で戦う．

6 K: N F E V G J M R S F N V G J M R S E
スケジュールの見方 計10チーム 各日に５試合行い,18試合日で2重総当りリーグ戦を行う. 各チーム対は,双方のホームグラウンドで１回ずつ戦う. RとGは第１試合日をRの本拠地で戦う．奇数試合日は週末． 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 ミラーリング

7 1 2 3 4 5 6 A:C D B D B C B:D C A C A D C:A B D B D A D:B A C A C B
ミラーリング A:C D B D B C B:D C A C A D C:A B D B D A D:B A C A C B 前半2N -1試合を作れば，後半2N -1試合は， 前半のスケジュールの試合場を交代した ものを付ければ良い．

8 K: N F E V G J M R S F N V G J M R S E
1993年前半戦スケジュールのミラーリング 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 イタリアセリエAのミラーリングは，平行移動． 問題点

9 2001年のＪリーグ前半戦のスケジュール（１重総当たり戦）
16TEAMS 磐田 : 市広FT鹿CO名浦GO清札柏福横TV神 市原 : 磐名柏福横FT鹿広TV神GO清札浦CO 名古屋: 浦市横FT鹿磐CO神GO清札柏福広TV 浦和 : 名CO福横FT鹿磐TV神GO清札柏市広 C大阪 : 札浦鹿GO磐清名福広横TVFT神柏市 札幌 : CO柏広TV神GO清FT鹿磐名浦市福横 福岡 : GO清浦市広TV神CO横FT鹿磐名札柏 G大阪 : 福横神CO清札柏磐名浦市広TVFT鹿 横浜FM: 神GO名浦市広TV柏福COFT鹿磐清札 神戸 : 横FTGO清札柏福名浦市広TVCO鹿磐 F東京 : TV神磐名浦市広札柏福横CO鹿GO清 東京V : FT鹿清札柏福横浦市広CO神GO磐名 柏 : 清札市広TV神GO横FT鹿磐名浦CO福 清水 : 柏福TV神GOCO札鹿磐名浦市広横FT 鹿島 : 広TVCO磐名浦市清札柏福横FT神GO 広島 : 鹿磐札柏福横FT市COTV神GO清名浦 読み方

10 各試合日には，全てのチームが１試合を戦う． 各試合日の試合は，グラフ上の完全マッチング．
総当りリーグ戦とグラフ 各チームを頂点とする完全グラフ． 各枝は試合に対応する． 各試合日には，全てのチームが１試合を戦う． 各試合日の試合は，グラフ上の完全マッチング． E D C B A F F A E B D C

11 B C D E F A：B C D E F A D F C E B：A D F C E F A E B D C：F A E B D
総当り戦とマッチング E D C B A F E D C B A F E D C B A F １ ２ ３ ４ ５ E D C B A F E D C B A F E D C B A F ミラーリング ６７８９10 B C D E F A D F C E F A E B D E B A F C D F C A B C E B D A １２３４５ A：B C D E F B：A D F C E C：F A E B D D：E B A F C E：D F C A B F：C E B D A

12 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 E D C B A F
うまく行かない例 E D C B A F E D C B A F 残った試合は E D C B A F １ ２ ３ １２３４５ 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：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
円盤の回転 以下のような円盤を回して，試合を決める． A B C D E F １２３４５ 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 12チームの場合 このまま回転を続ける‥‥. 実際のスケジュールは？

14 １２３４５ １２３４５ A：F C E B D A：F C E B D B：E F D A C B：E F D A C
総当りリーグ戦の作り方 ホームゲーム･アウェイゲームを決める． A B C D E F １２３４５ 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：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 実際のスケジュールは？

15 2重総当りリーグ戦の簡単な作り方（円盤＋ミラーリング）
６チーム(A,B,...,F)の例（試合数は 10） アウェイ ゲームチーム ホーム ゲームチーム ミラーリング A B C D E F 実際のスケジュールは？

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連続アウェイゲームがある． 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:鹿島アントラーズ J:ジェフユナイテッド市原 M:横浜マリノス F:横浜フリューゲルス（熊本） 望ましい

18 Home-Away Table (HAT) １ ２ ３ １ ２ ３ １：３ ２ ４ １：Ａ Ａ Ｈ Ａ:アウェイゲーム
試合の開催地の情報のみを表したもの １ ２ ３ １ ２ ３ １：３ ２ ４ １：Ａ Ａ Ｈ Ａ:アウェイゲーム ２：４ １ ３ ２：Ａ Ｈ Ａ Ｈ:ホームゲーム ３：１ ４ ２ ３：Ｈ Ａ Ｈ HA-パターン: ４：２ ３ １ ４：Ｈ Ｈ Ａ HAT の各行 スケジュール 対応する HAT HAT の性質を探る Home-away table, in short HAT, has not information of venue but stadium assignment. This HAT is correspond to this schedule. Also, we say this HAT can generates this schedule. In a HAT, capital red A represents away-game, capital black H represents home-game. Home-away pattern, in short HA-pattern is each row of HAT. In this HAT, we say team1 has HA-pattern “AAH”. Today, I talk about properties of HAT.

19 1993年のＪリーグ前半戦のスケジュール(HAT）
K: H H A A H H A H A A A H A A H A H H V: H A A H A A H A H H A A H H A H A H M: A H A A H A H A H A H H A H A H A H E: A H H A H H A H A A H H A A H A H A J: A H A H A A H A H A H A H H A H A H S: H A H H A A H A H H A A H H A H A A F: H A H A H H A H A H A H A A H A H A G: H A H H A A H H A H A A H H A A H A N: A A H H A H A H A H H A H A H A H A R: A H A A H H A A H A H H A A H H A H 望ましい

20 Basic Properties of HAT
（１）各スロットにおいて, １：Ａ Ａ Ｈ (# of Ａ) = (# of Ｈ) ２：Ａ Ｈ Ｈ ３：Ｈ Ａ Ｈ ４：Ｈ Ｈ Ａ （２）HA パターンが 同じ行は存在しない １：ＡＨＨＡＨ → この２チームは ２：ＡＨＨＡＨ 対戦できない At first, HATs must satisfy following two condition. On each slot, number of A equal to number of H. If number of A is different from number of H on particular slot, the HAT can’t generate schedule. In this HAT, 3 H and 1 A on slot3, therefore this HAT is inefficient. And every team has a different HA-pattern comparing with that of all other teams at least one slot. If team1 and team2 have completely same HA-pattern, they can’t play each other.

21 前述の2つの性質を満たすHATは 対応するスケジュールがあるか? → NO １ ２ ３ ４ ５
Infeasible HAT 前述の2つの性質を満たすHATは 対応するスケジュールがあるか? → NO １ ２ ３ ４ ５ １：Ａ Ｈ Ｈ Ａ Ｈ , 2-3, 3-1 の戦いは ２：Ａ Ｈ Ａ Ａ Ｈ スロット 3か 4 ３：Ａ Ｈ Ａ Ｈ Ｈ ４：Ｈ Ａ Ａ Ｈ Ａ → このHATに ５：Ｈ Ａ Ｈ Ｈ Ａ 対応する ６：Ｈ Ａ Ｈ Ａ Ａ スケジュールは 存在しない 不能 HAT When a given HAT can generate schedule, we say the HAT is feasible. There are infeasible HATs which meets previous two conditions. In this HAT, number of H and number of A is equal on ever slot, and each team has a different HA-pattern. However, this HAT can’t generate schedule, that is infeasible. Team1, team2 and team3 have to play 3 games 1vs2, 2vs3, 3vs1 for finishing a tournament. And HA-patterns of three team is same character on slot 1,2 and 5, thus they must play each other on slot 3 and 4. But this is impossible, so this HAT is infeasible.

22 下記のHATは対応するスケジュールが存在する １ ２ ３ ４ ５ １ ２ ３ ４ ５ １：Ａ Ａ Ａ Ａ Ａ １：６ ２ ４ ５ ３
Undesired HAT 下記のHATは対応するスケジュールが存在する １ ２ ３ ４ ５ １ ２ ３ ４ ５ １：Ａ Ａ Ａ Ａ Ａ １：６ ２ ４ ５ ３ ２：Ａ Ｈ Ａ Ｈ Ａ ２：３ １ ６ ４ ５ ３：Ｈ Ｈ Ａ Ａ Ｈ → ３：２ ４ ５ ６ １ ４：Ｈ Ａ Ｈ Ａ Ａ ４：５ ３ １ ２ ６ ５：Ａ Ａ Ｈ Ｈ Ｈ ５：４ ６ ３ １ ２ ６：Ｈ Ｈ Ｈ Ｈ Ｈ ６：１ ５ ２ ３ ４ 許容 HAT しかしながら，上記のスケジュールは良いものではない. (連続するアウェイゲームは好まれない)

23 ブレーク：連続する Ａ または Ｈ (以下では下線で表示) １ ２ ３ ４ ５ １ ２ ３ ４ ５
Definition of Breaks ブレーク：連続する Ａ または Ｈ (以下では下線で表示) １ ２ ３ ４ ５ １ ２ ３ ４ ５ １：Ａ Ａ Ａ Ａ Ａ １：Ａ Ｈ Ｈ Ａ Ａ ２：Ａ Ｈ Ａ Ｈ Ａ ２：Ｈ Ｈ Ｈ Ａ Ｈ ３：Ｈ Ｈ Ａ Ａ Ｈ ３：Ａ Ｈ Ａ Ｈ Ａ ４：Ｈ Ａ Ｈ Ａ Ａ ４：Ｈ Ａ Ａ Ｈ Ｈ ５：Ａ Ａ Ｈ Ｈ Ｈ ５：Ａ Ａ Ｈ Ａ Ｈ ６：Ｈ Ｈ Ｈ Ｈ Ｈ →14 ６：Ｈ Ａ Ａ Ｈ Ａ → 8 HATの公平性をブレークの数で測る. (ブレーク数が少ない方が良い)

24 1993年のＪリーグ前半戦のスケジュール(ブレーク数）
K: H H A A H H A H A A A H A A H A H H 7 V: H A A H A A H A H H A A H H A H A H 5 M: A H A A H A H A H A H H A H A H A H 2 E: A H H A H H A H A A H H A A H A H A 5 J: A H A H A A H A H A H A H H A H A H 2 S: H A H H A A H A H H A A H H A H A A 6 F: H A H A H H A H A H A H A A H A H A 2 G: H A H H A A H H A H A A H H A A H A 6 N: A A H H A H A H A H H A H A H A H A 3 R: A H A A H H A A H A H H A A H H A H 6 週２試合のため，週日と週末がある. 望ましい

25 横浜FM: H A A H A H A H A A H A H H A 3
2001年のＪリーグ前半戦のスケジュール 磐田 : H A H A H H A H A H A H A H A 1 市原 : A H H A H A H H A H A H A H H 3 名古屋: H A H A H A H H A H A H A H A 1 浦和 : A H H A H A H H A H A H A A A 4 C大阪 : H A H A A H A H A H A H A H A 1 札幌 : A H A H A H A A H A H A H A H 1 福岡 : H A A H A H A A H A H A H H A 3 G大阪 : A H A H H A H A H A H A H A H 1 横浜FM: H A A H A H A H A A H A H H A 3 神戸 : A H H A H A H A H A H A H A H 1 F東京 : H A A H A H A H A H A A H H A 3 東京V : A H H A H A H A H A H H A A H 3 柏 : H A A H A H A A H A H A H A H 2 清水 : A H A H A A H A H A H A H A H 1 鹿島 : H A A H A H A H A H A H A H A 1 広島 : A H H A H A H A H H A H A A H 3 読み方

26 許容HATの行は互い異なるHAパターンを持つ． 2チームはブレークを持たない. 他のチームは１つ以上のブレークを持つ.
Equitable HAT ブレーク数の意味で最も良いHATは？ (ブレーク数が少ない方が良い.) ブレーク最小 HAT [de Werra’80] 補題：ブレーク数の最小値 ≧ チーム数－2 証明：ブレークの無いHA-パターンは２つ AHAHAHAHAHAHA HAHAHAHAHAHAH 許容HATの行は互い異なるHAパターンを持つ． 2チームはブレークを持たない. 他のチームは１つ以上のブレークを持つ. In prevous slide, we saw undesired HAT because of unequality among particular teams. What is optimal HAT in terms of equality? As we have seen, HAT consist of small number of breaks is better. It is already known two kinds of HAT with small number of breaks. One, minimizing breaks HAT. Two team have no breaks, and other team have exactly one break. But in this HAT, there is two team which has no breaks. So we prefer equitable HAT rather than minimizing breaks HAT. In equitable HAT, all teams have exactly one break.

27 横浜FM: H A A H A H A H A A H A H H A 3
2001年のＪリーグ前半戦のスケジュール 磐田 : H A H A H H A H A H A H A H A 1 市原 : A H H A H A H H A H A H A H H 3 名古屋: H A H A H A H H A H A H A H A 1 浦和 : A H H A H A H H A H A H A A A 4 C大阪 : H A H A A H A H A H A H A H A 1 札幌 : A H A H A H A A H A H A H A H 1 福岡 : H A A H A H A A H A H A H H A 3 G大阪 : A H A H H A H A H A H A H A H 1 横浜FM: H A A H A H A H A A H A H H A 3 神戸 : A H H A H A H A H A H A H A H 1 F東京 : H A A H A H A H A H A A H H A 3 東京V : A H H A H A H A H A H H A A H 3 柏 : H A A H A H A A H A H A H A H 2 清水 : A H A H A A H A H A H A H A H 1 鹿島 : H A A H A H A H A H A H A H A 1 広島 : A H H A H A H A H H A H A A H 3 読み方

28 横浜FM: H A H A H A H A H H A H A H A 1
2001年のＪリーグ後半戦のスケジュール 磐田 : H A H A H A A H A A H A H H A 3 市原 : H A A H A H A H A A H A H A H 2 名古屋: H A H A A H A H A A H A H H A 3 浦和 : H A H A A H A H A A H A H A H 2 C大阪 : H A H A H A H H A A H A H H A 3 札幌 : A H A H H A H A H H A H A A H 3 福岡 : A H H A H A H A H H A H A H A 2 G大阪 : A H A H A H A A H H A H A A H 3 横浜FM: H A H A H A H A H H A H A H A 1 神戸 : A H A H A H A H A H A H A A H 1 F東京 : H A H A H A H A H A H H A H A 1 東京V : A H A H A H A H A H A A H A H 1 柏 : A H A H H A H A H H A H A H A 2 清水 : A H A H A H H A H H A H A A H 3 鹿島 : H A H A H A H A H A H A H H A 1 広島 : A H A H A H A H A A H A H A H 1 読み方

29 Atlanta : HAAHAHAHAHAHHAHAH AHHAHAHAHAHAAHAHA
セリエＡ2000/2001シーズン（２重総当たり戦） Atlanta : HAAHAHAHAHAHHAHAH AHHAHAHAHAHAAHAHA Bari : HAHAHHAHAHAHAAHAH AHAHAAHAHAHAHHAHA Bologna : AHAHAHHAHAHAHAHAH HAHAHAAHAHAHAHAHA Brescia : AHHAHAHAAHAHAHAHA HAAHAHAHHAHAHAHAH Fiorentina: AHAHHAHAAHAHAHAHA HAHAAHAHHAHAHAHAH Inter : AHAHAHHAHAHAAHAHA HAHAHAAHAHAHHAHAH Juventus : AHAHAHAHAHAAHHAHA HAHAHAHAHAHHAAHAH Lazio : AHAHHAHAHAHAHAHAH HAHAAHAHAHAHAHAHA Lecce : AHAHAAHAHAHAHHAHA HAHAHHAHAHAHAAHAH Milan : HAHAHAAHAHAHHAHAH AHAHAHHAHAHAAHAHA Napoli : HAHAHAHAHAHHAAHAH AHAHAHAHAHAAHHAHA Parma : HAAHAHAHHAHAHAHAH AHHAHAHAAHAHAHAHA Perugia : HAHAAHAHHAHAHAHAH AHAHHAHAAHAHAHAHA Reggina : HAHAHAAHAHAHAHAHA AHAHAHHAHAHAHAHAH Roma : HAHAAHAHAHAHAHAHA AHAHHAHAHAHAHAHAH Udinese : HAHAHAHAHAHHAHAHA AHAHAHAHAHAAHAHAH Verona : AHHAHAHAHAHAAHAHA HAAHAHAHAHAHHAHAH Vicenza : AHHAHAHAHAHAAHAHA HAAHAHAHAHAHHAHAH

30 Atlanta : HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA
セリエＡ2000/2001シーズン（２重総当たり戦） Atlanta : HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA Bari : HAHAHHAHAHAHAAHAHAHAHAAHAHAHAHHAHA Bologna : AHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHAHA Brescia : AHHAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAH Fiorentina: AHAHHAHAAHAHAHAHAHAHAAHAHHAHAHAHAH Inter : AHAHAHHAHAHAAHAHAHAHAHAAHAHAHHAHAH Juventus : AHAHAHAHAHAAHHAHAHAHAHAHAHAHHAAHAH Lazio : AHAHHAHAHAHAHAHAHHAHAAHAHAHAHAHAHA Lecce : AHAHAAHAHAHAHHAHAHAHAHHAHAHAHAAHAH Milan : HAHAHAAHAHAHHAHAHAHAHAHHAHAHAAHAHA Napoli : HAHAHAHAHAHHAAHAHAHAHAHAHAHAAHHAHA Parma : HAAHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHA Perugia : HAHAAHAHHAHAHAHAHAHAHHAHAAHAHAHAHA Reggina : HAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAHAH Roma : HAHAAHAHAHAHAHAHAAHAHHAHAHAHAHAHAH Udinese : HAHAHAHAHAHHAHAHAAHAHAHAHAHAAHAHAH Verona : AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH Vicenza : AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH

31 Atlanta : H H H H H HH H H HH H H H H H H 2
セリエＡ2000/2001シーズン（ホームゲーム） Atlanta : H H H H H HH H H HH H H H H H H 2 Bari : H H HH H H H H H H H H H H HH H 2 Bologna : H H HH H H H H HH H H H H H H H 2 Brescia : HH H H H H H H H H H HH H H H H 2 Fiorentina: H HH H H H H H H H H HH H H H H 2 Inter : H H HH H H H H H H H H H HH H H 2 Juventus : H H H H H HH H H H H H H HH H H 2 Lazio : H HH H H H H H HH H H H H H H H 2 Lecce : H H H H H HH H H H HH H H H H H 2 Milan : H H H H H HH H H H H HH H H H H 2 Napoli : H H H H H HH H H H H H H H HH H 2 Parma : H H H HH H H H H HH H H H H H H 2 Perugia : H H H HH H H H H H HH H H H H H 2 Reggina : H H H H H H H H H H HH H H H H H 1 Roma : H H H H H H H H H HH H H H H H H 1 Udinese : H H H H H HH H H H H H H H H H H 1 Verona : HH H H H H H H H H H H H HH H H 2 Vicenza : HH H H H H H H H H H H H HH H H 2

32 Atlanta : AA A A A A A A A A A A A AA A A 2
セリエＡ2000/2001シーズン（アウェイゲーム） Atlanta : AA A A A A A A A A A A A AA A A 2 Bari : A A A A A AA A A A AA A A A A A 2 Bologna : A A A A A A A A A A AA A A A A A 1 Brescia : A A A AA A A A A AA A A A A A A 2 Fiorentina: A A A AA A A A A A AA A A A A A 2 Inter : A A A A A AA A A A A AA A A A A 2 Juventus : A A A A A AA A A A A A A A AA A 2 Lazio : A A A A A A A A A AA A A A A A A 1 Lecce : A A AA A A A A A A A A A A AA A 2 Milan : A A AA A A A A A A A A A AA A A 2 Napoli : A A A A A AA A A A A A A AA A A 2 Parma : AA A A A A A A A A A AA A A A A 2 Perugia : A AA A A A A A A A A AA A A A A 2 Reggina : A A AA A A A A AA A A A A A A A 2 Roma : A AA A A A A A AA A A A A A A A 2 Udinese : A A A A A A A AA A A A A AA A A 2 Verona : A A A A A AA A A AA A A A A A A 2 Vicenza : A A A A A AA A A AA A A A A A A 2

33 Atlanta : HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA 4
セリエＡ2000/2001シーズン （ブレーク数） Atlanta : HAAHAHAHAHAHHAHAHAHHAHAHAHAHAAHAHA 4 Bari : HAHAHHAHAHAHAAHAHAHAHAAHAHAHAHHAHA 4 Bologna : AHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHAHA 3 Brescia : AHHAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAH 4 Fiorentina: AHAHHAHAAHAHAHAHAHAHAAHAHHAHAHAHAH 4 Inter : AHAHAHHAHAHAAHAHAHAHAHAAHAHAHHAHAH 4 Juventus : AHAHAHAHAHAAHHAHAHAHAHAHAHAHHAAHAH 4 Lazio : AHAHHAHAHAHAHAHAHHAHAAHAHAHAHAHAHA 3 Lecce : AHAHAAHAHAHAHHAHAHAHAHHAHAHAHAAHAH 4 Milan : HAHAHAAHAHAHHAHAHAHAHAHHAHAHAAHAHA 4 Napoli : HAHAHAHAHAHHAAHAHAHAHAHAHAHAAHHAHA 4 Parma : HAAHAHAHHAHAHAHAHAHHAHAHAAHAHAHAHA 4 Perugia : HAHAAHAHHAHAHAHAHAHAHHAHAAHAHAHAHA 4 Reggina : HAHAHAAHAHAHAHAHAAHAHAHHAHAHAHAHAH 3 Roma : HAHAAHAHAHAHAHAHAAHAHHAHAHAHAHAHAH 3 Udinese : HAHAHAHAHAHHAHAHAAHAHAHAHAHAAHAHAH 3 Verona : AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH 4 Vicenza : AHHAHAHAHAHAAHAHAHAAHAHAHAHAHHAHAH 4

34 ブレーク最小HATは公平さの観点からは好ましくない．
Equitable HAT ブレーク最小 HAT [de Werra’80] ブレーク数最小値=(チーム数－2) 2チームはブレークを持たない 他のチームは ちょうど１つのブレークを持つ １２３４５ 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 B C D E F In prevous slide, we saw undesired HAT because of unequality among particular teams. What is optimal HAT in terms of equality? As we have seen, HAT consist of small number of breaks is better. It is already known two kinds of HAT with small number of breaks. One, minimizing breaks HAT. Two team have no breaks, and other team have exactly one break. But in this HAT, there is two team which has no breaks. So we prefer equitable HAT rather than minimizing breaks HAT. In equitable HAT, all teams have exactly one break. ブレーク最小HATは公平さの観点からは好ましくない．

35 均等 HAT [de Werra’80] 各チームが丁度1つのブレークを持つ １２３４５ A：F C E B D B：E F D A C
Equitable HAT 均等 HAT [de Werra’80] 各チームが丁度1つのブレークを持つ (総ブレーク数 = 2N) A B C D E F １２３４５ 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：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 In prevous slide, we saw undesired HAT because of unequality among particular teams. What is optimal HAT in terms of equality? As we have seen, HAT consist of small number of breaks is better. It is already known two kinds of HAT with small number of breaks. One, minimizing breaks HAT. Two team have no breaks, and other team have exactly one break. But in this HAT, there is two team which has no breaks. So we prefer equitable HAT rather than minimizing breaks HAT. In equitable HAT, all teams have exactly one break. 均等HATの性質について探る！ (ブレーク最小HATとほぼ同じ!？）

36 均等HATの各行（HA-パターン）は下記のようにブレークが1つあるもの．
補完パターン 均等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であるとは限らない. This is an example of equitable HAT. Please note equitable HATs aren’t always feasible. There are infeasible equitable HAT. Our goal is to determine how many are there feasible and equitable HATs .

38 Opening and Closing Condition
HA-パターン… ＡＡ または ＨＨ で始まるならば HA-パターン は 開幕条件を満たさない と言う. ＡＡ または ＨＨで終わるならば HA-パターン は 閉幕条件を満たさない と言う. 上記のような HA-パターン は，閉開幕における観客の動員数に悪影響を与える． ミラーリングを施した後，３連続 Ａ または Ｈ が出現する． We required HAT also meets other constraints for holding equality among all teams. If a team has HA-pattern its slot1 and 2 is both ‘A’ or both ‘H’, like AAHAHAH, HHAHAHA, we say such HA-pattern violates opening condition. Similarly, if HA-pattern which has final slot and previous are same character, we say such HA-pattern violates closing condition. We show aspect of these two condition in next slide.

39 Consideration of Mirroring
均等 HAT が以下の HA-パターン を含むなら (ＡＡ…), (ＨＨ…), (…ＡＡ), (…ＨＨ), ミラーリングをして得られる HAT は 3 連続の Ａ(または Ｈ) を持つ. ＡＡＨ…ＡＨ → ＡＡＨ…Ａ Ｈ∥ＨＨ Ａ…ＨＡ, ＨＨＡ…ＨＡ → ＨＨＡ…Ｈ Ａ∥ＡＡ Ｈ…ＡＨ, ＡＨＡ…ＨＨ → ＡＨＡ… ＨＨ∥Ｈ ＡＨ…ＡＡ, ＨＡＨ…ＡＡ → ＨＡＨ… ＡＡ∥Ａ ＨＡ…ＨＨ, ミラーリング後 We assume DRR by mirroring, thus HA-pattern violating opening or closing condition causes 3 consecutive A or H after mirroring. This HA-pattern violates opening condition, and opening two A become two H, then 3 consecutive H is occurred.

40 The Number of Candidates for Feasible HAT
(5)開閉幕条件を満たす. #teams #HAT #HAT:条件(1)～(5)を満たす HAT の数 許容HATとは限らない → このうち許容HATはいくつ？ This table shows a number of candidates of feasible HAT. This table is easily obtained with simple consideration, described in our abstract. Ideally, we are able to check feasibility of any HAT by solving IP. But the case of 20 teams, we have to solve 8008[eight thousands and eight] IP problem, and each IP has 1900[one thousand and nine hundreds]. Solving all IP naively is too time consuming.

41 Checking Feasibility of HAT
与えられた HATが許容HATであるかを判定する問題を, 整数計画問題に定式化する. この問題はN2(2N－1) 個の0-1 変数を持つ. IP が許容解を持つ ⇔ HAT は許容HATである Now, we state three conditions required for desireble HAT. Equitable HAT, opening and closing condition. To check feasibility of given HATs, we formulize the problem as IP with 2N(2N-1) 0-1 variables. If the IP has feasible solutions, given HAT is feasible. Otherwise, given HAT is infeasible.

42 1 （ AとBが１日目に戦う）， ｘAB1 ＝｛ ｘAB1 , ｘAB2 , ｘAB3 , ｘAC1 , ｘAC2 , ｘAC3 ,
スケジュールを作る 0-1 整数計画法 HAT B:A A H H H A このHATに対応する， A:H H A A A H スケジュールを求めよう． C:A H A H A H D:H A H A 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 } } 4C2=6本 ‥‥ ｘAB1+ｘAB2+ｘAB3 =1, （AとBはどこかで戦う）
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, 残りの変数（１２個）は，0または1を取る. スケジュールを全部見つける=上記を満たすもの全て見つける 0-1整数計画法 ：0-1変数12個，等式18本. 4C2=6本 } 4×3=12本

44 The Number of Candidates for Feasible HAT
#teams #cand.(#vars.) (45) #cand.: 開閉幕条件を満たす (112) 均等HATの数 (225) (許容HATの候補数) (396) (637) #vars. : 対応する整数計画問題 (960) の0-1変数の数 (1377) (チーム数 2N , 変数 N2(2N－1)) (1900) すべてのIPを解くのは非現実的! This table shows a number of candidates of feasible HAT. This table is easily obtained with simple consideration, described in our abstract. Ideally, we are able to check feasibility of any HAT by solving IP. But the case of 20 teams, we have to solve 8008[eight thousands and eight] IP problem, and each IP has 1900[one thousand and nine hundreds]. Solving all IP naively is too time consuming.

45 Triple Break Constraints
与えられた HAT に，スロットs, s+1, s+2 にブレークが在る3行の HA-パターン があるならば， ＡＨＡ ＡＨ ＡＨ ＡＨＡ ＨＨ ＡＨ ＡＨＡ ＨＡ ＡＨ 与えられた HAT は不能! 与えられた HAT が上記のような 3つの HA-パターン を含んでいるかのチェックは IPを解くより容易である. ３連続ブレーク条件 Now we state triple break condition. If a given HAT have such HA pattern, breaks occur on slot s, s+1, s+2, then it is easy to show the HAT must be infeasible. Checking whether given HATs contain such breaks or not is much easier than solving IPs.

46 Applying Triple Break Constraints
#teams #cand. #tri. #cand.: 許容HATの候補数 #tri.: 許容HATの新たな候補数 for feasible HAT (3連続ブレーク条件を適用) 許容HATの候補数は非常に減る. (上記の3連続ブレーク条件のチェックは1分以下) After applying triple break condition, a number of candidates of feasible HAT is wildly reduced. For 18 teams, 2002 to 50, for 20 teams 8008[eight thousand eight] to 161, and so on. Checking this takes under 1 minute for enumeration.

47 The Number of Feasible HAT
#teams #triple (#vars.) #feasible (45) (112) CPU: Pentium II (225) MHz, (396) OS: Windows 98, (637) RAM: 128MB, (960) IP Solver: (1377) ILOG OPL Studio 3.0 (1900) CPLEX 総計算時間 : 3.5 時間 After applying triple break condition, we have to solve moderate number of IP problems. We use ILOG OPL Studio version3.0 as IP solver, on Pentium 400MHz PC with 128MB main memory. All computation are done in 3.5 hours.

48 許容HATの数は 非常に少ない. チーム数 ∈{6, 8, 10, 12, 14, 18}については, 許容 HATは存在しない
Results of Experiment 許容HATの数は 非常に少ない. チーム数 ∈{6, 8, 10, 12, 14, 18}については, 許容 HATは存在しない (チーム数 = 16) → 1 HAT (チーム数 = 20) → 4 HAT 現実的な計算時間 (3.5 時間) Experiments shows a number of desired feasible HAT is very SMALL. There is only one feasible HAT of 16 teams, four feasible HAT of 20 teams. When teams for 6,8,10,12,14,18, there is no feasible HAT satisfying all required constraints.

49 Unique Feasible HAT (16 teams)
１ ２ ３ ４ ５ ６ ７ ８ ９ １：Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ ２：Ａ Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ ３：Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ ４：Ａ Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ ５：Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ Ｈ ６：Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ ７：Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ Ｈ ８：Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ ９：Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ 10：Ｈ Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ 11：Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ 12：Ｈ Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ 13：Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ Ｈ Ａ Ｈ Ａ 14：Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ Ａ Ｈ Ａ 15：Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ａ Ｈ Ａ 16：Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ａ Ｈ Ｈ Ａ This is an unique feasible HAT of 16 teams, meeting all condition.

50 Conclusion & Future Work
結論 現実的なチーム数 (20以下) においては，設定した性質を満たす許容HATは非常に少ない． HATすべての許容性をチェックする問題は，適切な制約を導入することにより，現実的な計算時間で可能となる． 今後の研究 一般のHATに対する算法の設計 (均等とは限らないHAT) どんなスケジュールが欲しいのか？ Our conclusion is; There are few desired HATs for a pratcical number of teams, up to 20. Checking feasibility of HATs takes an acceptable computational time under adequate constraints. Future work is finding better algorithm for general HAT. This is end of my talk. Any question or comment, please.

51 スポーツスケジューリングの研究を発展させるために
ホームページの公開 ： 簡略ページ ・ 詳細ページ 研究発表 統計研, 南山大学, 文教大学, 東京大学, 班会議 関連記事の雑誌掲載 サーベイ： 松井知己, 「スポーツのスケジューリング」, オペレーションズリサーチ，44 (1999), 141－146. 入門編： 宮代隆平, 松井知己, 「1993年Jリーグの再スケジューリング」, オペレーションズ・リサーチ, 45 (2000), 81－83. 関連研究（者）の交流 東大, 筑波大, 東京理科大, 中央大, 東海大 応用から実務へ？ どんな目的関数？モデル化

52 おわり

53 K: N F E V G J M R S F N V G J M R S E
1993年のＪリーグ前半戦のスケジュール ２重総当りリーグ戦（原本） 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チームは無理！
今後の課題 手作業の部分は，問題例依存の性質を用いている． 1993年を選んだのは10チームと少なかったから． 今回の方法では16チームは無理！ 1999年：２リーグ制 Ｊ1：16ﾁｰﾑ．試合は週末のみ．(1重)総当り戦． Ｊ２：10ﾁｰﾑ．試合は週末のみ．４重総当り戦． 入っていない因子： TV放映．グラウンド使用可能日．チーム移動費用？ 消化試合を減らす（好カードを後に残す）． Nemhauser and Trick の open problem 与えられたｈａテーブルに対応するタイムテーブルはあるか？ NP-complete?