はじめに
試合スケジュールの作成【GLPK】の続きです。
各チームが1日に1試合する場合には前掲のプログラムで割り当てができますが、1日に2試合する場合に試合間隔を調整する機能を追加しました。
最適化の条件
- 16チームでリーグ戦のスケジュールを作成する。
- 全チーム1回ずつの対戦を1節(8試合)とし、2コート使える時には1日で2節分の試合をする。
- 各チームの1戦目と2戦目の試合の間隔の差をなるべく偏らないようにする。
- 1戦目と2戦目は違うコートで行う。
- 1〜7日目は1日で2節、最後の8日目は残りの1節分を割り当てる。
このような簡単な条件で作ったものを以下に書いておきます。
以下のプログラムは、基本的な動作を示すもので、実際にはなかなか結果が出てませんでした。
改良版を後日追加しておきます。
下に、改良版で出てきた結果を書いておきます。結果が必要でしたら参考にしてください。
game_schedule03.mod
# version 0.3
# リーグ戦のスケジュールを作成する
param nTeams integer; # チーム数を読み込む
set Date; # 日付を読みこむ 日付は1からの連番
param nSections{Date} integer; # 日別の節数を読み込む
set FixGameSchedule dimen 3; # 強制的に試合を設定を読み込む
set AvoidGameSchedule dimen 3; # 避ける試合を設定を読み込む
set FixMatch2 := {(s,g,t1) in FixGameSchedule, (s,g,t2) in FixGameSchedule: t1<t2}; # 対戦相手が決まっている試合
set FixMatch1 := FixGameSchedule symdiff (setof{(s,g,t1,t2) in FixMatch2}(s,g,t1) union setof{(s,g,t1,t2) in FixMatch2}(s,g,t2)); # 対戦の一方が決まっている試合
param startSectionID{d in Date} := if d==1 then 1 else startSectionID[d-1]+nSections[d-1]; # 日別の開始節番号
set Team := 1..nTeams; # チーム番号
param nGamesInSection := floor(nTeams / 2); # 節あたりの試合数
param nCourts{d in Date} := nSections[d]; # 使用するコート数 ここでは節数を同じ
set Section := 1..sum{d in Date}nSections[d]; # 節番号
set GameIndex := {s in Section, g in 1..nGamesInSection}; # 節内の試合番号
# 試合スケジュール、日付, 節, 試合番号, その日の試合時刻番号, コート番号
set GameSchedule := {d in Date, (s, g) in GameIndex,
{if nCourts[d]>=2 then ((g+1) div nCourts[d])+(s-startSectionID[d])*ceil(nGamesInSection/nCourts[d]) else g}, {((g+1) mod nCourts[d]) +1}:
(d<card(Date) and s>=startSectionID[d] and s<startSectionID[d+1]) or (d=card(Date) and s>=startSectionID[d])};
set Match := {i in Team, j in Team : i<j}; # 対戦組み合わせ
set MatchIndex := {GameIndex, Match};
# 同じ日に2節ある場合の節番号ペア
set ContinuousSectionPair := setof{s in Section, d in Date: nSections[d]>=2 and s==startSectionID[d]}(s,s+1);
## (1)
# 試合を割り振る変数、試合がある場合は1,無ければ0
var assignGame{(s,g,t1,t2) in MatchIndex} binary;
# スケジュールが決まっている試合の処理
s.t. fix_game{(s,g,t) in FixGameSchedule}: sum{(t1,t2) in Match: t1==t or t2==t}assignGame[s,g,t1,t2]==1;
# 試合を避ける時間の処理
s.t. avoid_game{(s,g,t) in AvoidGameSchedule}: sum{(t1,t2) in Match: t1==t or t2==t}assignGame[s,g,t1,t2]==0;
## (2)
# 同じ試合番号に1つだけの試合
s.t. oneGame{(s,g) in GameIndex}: sum{(s,g,t1,t2) in MatchIndex}assignGame[s,g,t1,t2]==1;
# リーグ戦なので同じ対戦相手には当たらない
s.t. onceMatch{(t1,t2) in Match}: sum{(s,g,t1,t2) in MatchIndex}assignGame[s,g,t1,t2]<=1;
# 1節で1回試合に出場
s.t. onceGame{s in Section, t in Team}: sum{(s,g,t1,t2) in MatchIndex: t1==t or t2==t}assignGame[s,g,t1,t2]==1;
# ゲームの間隔を求める変数
var game_interval{ContinuousSectionPair, Team} integer, >=1, <=nGamesInSection-1;
# 同じ日に2節ある場合の試合は違うのコートで
s.t. diffCourt{(s1,s2) in ContinuousSectionPair, t in Team, c in 1..2}: sum{(s,g,t1,t2) in MatchIndex, (d,s,g,gd,c) in GameSchedule: (t1==t or t2==t) and (s==s1 or s==s2)}assignGame[s,g,t1,t2]==1;
# 同じ日に2節ある場合の試合の間隔を求める
s.t. calcInterval{(s1,s2) in ContinuousSectionPair, t in Team}: sum{(d,s,g,gd,c) in GameSchedule, (s,g,t1,t2) in MatchIndex: (t1==t or t2==t) and s==s2}assignGame[s,g,t1,t2]*gd-sum{(d,s,g,gd,c) in GameSchedule, (s,g,t1,t2) in MatchIndex: (t1==t or t2==t) and s==s1}assignGame[s,g,t1,t2]*gd==game_interval[s1,s2,t];
# 試合間隔の最小値と最大値の差を最小に
var max_interval integer, >=1, <=nGamesInSection-1;
var min_interval integer, >=1, <=nGamesInSection-1;
s.t. max_game_interval{(s1,s2) in ContinuousSectionPair, t in Team}: game_interval[s1,s2,t]<=max_interval;
s.t. min_game_interval{(s1,s2) in ContinuousSectionPair, t in Team}: game_interval[s1,s2,t]>=min_interval;
minimize minimize_interval: max_interval-min_interval;
solve;
# 出力
printf "試合スケジュール\n";
for{d in Date, s in Section: exists{(d,s,g,gd,c) in GameSchedule}(d,s,g,gd,c) in GameSchedule}{
printf "%d日目 第%d節\n", d, s;
printf "試合順 コート番号 (節の試合番号) 対戦チーム\n";
printf{(s,g,t1,t2) in MatchIndex, (d,s,g,gd,c) in GameSchedule: assignGame[s,g,t1,t2]==1} " %d %d (%d) %d - %d\n", gd, c, g, t1, t2;
}
printf "\nチームごとの試合順(節の試合番号)\n";
printf " ";
printf{s in Section} "%4d節", s;
printf "\n";
for{t in Team}{
printf "%4d", t;
printf{s in Section, (s,g,t1,t2) in MatchIndex, (d,s,g,gd,c) in GameSchedule: assignGame[s,g,t1,t2]==1 and (t==t1 or t==t2)} "%3d(%d)",gd, g;
printf "\n";
}
printf "\n同じ日に2節開催時の試合間隔 最小 %d 最大 %d\n", min{(s1,s2) in ContinuousSectionPair, t in Team}game_interval[s1,s2,t], max{(s1,s2) in ContinuousSectionPair, t in Team}game_interval[s1,s2,t];
printf "チームごとの試合間隔\n";
for{t in Team}{
printf "%5d :", t;
printf{(s1,s2) in ContinuousSectionPair} "%5d" ,game_interval[s1,s2,t];
printf " : 平均 %3.1f\n", sum{(s1,s2) in ContinuousSectionPair}game_interval[s1,s2,t]/card(ContinuousSectionPair);
}
printf "\nFixGameSchedule用出力\n";
printf{(s,g,t1,t2) in MatchIndex, (d,s,g,gd,c) in GameSchedule: assignGame[s,g,t1,t2]==1} "(%d, %d, *) %d %d\n", s, g, t1, t2;
data;
# チーム数
param nTeams := 16;
# 日付とその日の節数
param : Date : nSections :=
1 2
2 2
3 2
4 2
5 2
6 2
7 2
8 1
;
# 試合をする節番号,試合番号,チーム番号(,チーム番号)
set FixGameSchedule :=
(1, 1, *) 1 2
(1, 2, *) 3 4
(1, 3, *) 5 6
(1, 4, *) 7 8
(1, 5, *) 9 10
(1, 6, *) 11 12
(1, 7, *) 13 14
(1, 8, *) 15 16
;
# 試合を避ける節番号,試合番号,チーム番号
set AvoidGameSchedule :=
;
end;
得られた結果
result.txt
試合スケジュール
1日目 第1節
試合順 コート番号 (節の試合番号) 対戦チーム
1 1 (1) 1 - 2
1 2 (2) 3 - 4
2 1 (3) 5 - 6
2 2 (4) 7 - 8
3 1 (5) 9 - 10
3 2 (6) 11 - 12
4 1 (7) 13 - 14
4 2 (8) 15 - 16
1日目 第2節
試合順 コート番号 (節の試合番号) 対戦チーム
5 1 (1) 3 - 7
5 2 (2) 1 - 6
6 1 (3) 4 - 12
6 2 (4) 2 - 10
7 1 (5) 8 - 15
7 2 (6) 5 - 14
8 1 (7) 11 - 16
8 2 (8) 9 - 13
2日目 第3節
試合順 コート番号 (節の試合番号) 対戦チーム
1 1 (1) 8 - 12
1 2 (2) 7 - 15
2 1 (3) 2 - 9
2 2 (4) 4 - 11
3 1 (5) 6 - 16
3 2 (6) 1 - 14
4 1 (7) 3 - 13
4 2 (8) 5 - 10
2日目 第4節
試合順 コート番号 (節の試合番号) 対戦チーム
5 1 (1) 11 - 15
5 2 (2) 2 - 8
6 1 (3) 7 - 14
6 2 (4) 9 - 12
7 1 (5) 4 - 5
7 2 (6) 3 - 6
8 1 (7) 1 - 10
8 2 (8) 13 - 16
3日目 第5節
試合順 コート番号 (節の試合番号) 対戦チーム
1 1 (1) 1 - 13
1 2 (2) 4 - 7
2 1 (3) 10 - 11
2 2 (4) 6 - 8
3 1 (5) 12 - 15
3 2 (6) 2 - 5
4 1 (7) 14 - 16
4 2 (8) 3 - 9
3日目 第6節
試合順 コート番号 (節の試合番号) 対戦チーム
5 1 (1) 4 - 6
5 2 (2) 1 - 11
6 1 (3) 2 - 7
6 2 (4) 13 - 15
7 1 (5) 8 - 9
7 2 (6) 10 - 14
8 1 (7) 3 - 5
8 2 (8) 12 - 16
4日目 第7節
試合順 コート番号 (節の試合番号) 対戦チーム
1 1 (1) 5 - 11
1 2 (2) 6 - 10
2 1 (3) 9 - 16
2 2 (4) 4 - 15
3 1 (5) 3 - 14
3 2 (6) 8 - 13
4 1 (7) 2 - 12
4 2 (8) 1 - 7
4日目 第8節
試合順 コート番号 (節の試合番号) 対戦チーム
5 1 (1) 6 - 15
5 2 (2) 9 - 11
6 1 (3) 8 - 10
6 2 (4) 5 - 16
7 1 (5) 1 - 4
7 2 (6) 2 - 3
8 1 (7) 7 - 13
8 2 (8) 12 - 14
5日目 第9節
試合順 コート番号 (節の試合番号) 対戦チーム
1 1 (1) 8 - 16
1 2 (2) 2 - 15
2 1 (3) 4 - 13
2 2 (4) 6 - 14
3 1 (5) 10 - 12
3 2 (6) 5 - 7
4 1 (7) 3 - 11
4 2 (8) 1 - 9
5日目 第10節
試合順 コート番号 (節の試合番号) 対戦チーム
5 1 (1) 14 - 15
5 2 (2) 4 - 8
6 1 (3) 2 - 6
6 2 (4) 10 - 16
7 1 (5) 1 - 5
7 2 (6) 11 - 13
8 1 (7) 7 - 9
8 2 (8) 3 - 12
6日目 第11節
試合順 コート番号 (節の試合番号) 対戦チーム
1 1 (1) 2 - 16
1 2 (2) 11 - 14
2 1 (3) 6 - 13
2 2 (4) 5 - 8
3 1 (5) 1 - 3
3 2 (6) 4 - 9
4 1 (7) 7 - 12
4 2 (8) 10 - 15
6日目 第12節
試合順 コート番号 (節の試合番号) 対戦チーム
5 1 (1) 8 - 11
5 2 (2) 2 - 13
6 1 (3) 9 - 14
6 2 (4) 3 - 16
7 1 (5) 5 - 15
7 2 (6) 6 - 7
8 1 (7) 4 - 10
8 2 (8) 1 - 12
7日目 第13節
試合順 コート番号 (節の試合番号) 対戦チーム
1 1 (1) 5 - 9
1 2 (2) 3 - 15
2 1 (3) 12 - 13
2 2 (4) 1 - 16
3 1 (5) 6 - 11
3 2 (6) 8 - 14
4 1 (7) 7 - 10
4 2 (8) 2 - 4
7日目 第14節
試合順 コート番号 (節の試合番号) 対戦チーム
5 1 (1) 1 - 15
5 2 (2) 5 - 12
6 1 (3) 3 - 8
6 2 (4) 6 - 9
7 1 (5) 4 - 16
7 2 (6) 10 - 13
8 1 (7) 2 - 14
8 2 (8) 7 - 11
8日目 第15節
試合順 コート番号 (節の試合番号) 対戦チーム
1 1 (1) 4 - 14
2 1 (2) 2 - 11
3 1 (3) 3 - 10
4 1 (4) 7 - 16
5 1 (5) 9 - 15
6 1 (6) 5 - 13
7 1 (7) 6 - 12
8 1 (8) 1 - 8