<--目次へ

はじめに

試合スケジュールの作成【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