修士論文審査資料

巡回トーナメント問題の発見的解法
指導教員 松井 知己 助教授
数理情報学専攻数理第五研究室 藤原 伸友
平成 18 年 2 月 8 日

1 概要

出力

本論文では各チームの本拠地間の距離が 1 であるような巡回トーナメント問題に対して，最適値の下界を評価し，許容解の構成法を 2 つ提案する．1 つ目はポリゴン法を改訂した構成法で，質の良い許容界を非常に高速に構成することができる．2 つ目は整数計画法を用いた構成法で，チーム数が 22，28, 34, 40, 46 の場合には最適解を構成できる．

チームの本拠地間の距離行列 D.
以下の制約条件を満たす 2 重総当りリーグ戦のスケジュールで，各チームの移動距離の総和が最小のもの．
1 (No repeat) 同じ対戦相手と連続する節で対戦してはならない．
2 (At most) 4 節以上ホームゲームまたはアウェイゲームが連続してはならない．

TTP の許容解であるスケジュールを許容スケジュールと呼ぶ．我々は Urrutia, Ribeiro[3] により提案された各チームの本拠地間の距離が 1 であるような巡回トーナメント問
題 (CTTP) を扱う．TTP の制約を満たすスケジュール Yの移動距離を w(Y ) と表す．CTTP において，w(Y ) は移動回数と等しくなる．
スケジュールが与えられたとき，チーム t がスロット s−1と s においてホーム (アウェイ) ゲームを連続して行うとき，チーム t はスロット s にブレークを持つという．スケジュール Y のブレーク数を，各チームのブレーク数の総和と定義し b(Y ) と表す．2 重総当りリーグ戦のスケジュール
Y の移動回数とブレーク数の間には，2 問題の定義
本稿では以下の条件でリーグ戦が行われるとする:• チーム数は偶数 (以下 n) である．
• 各チームは異なる本拠地 (ホーム) をもつ．
• 各試合は対戦する 2 チームのどちらかの本拠地で行われる．
• 対戦相手の本拠地での試合が連続するときは，対戦相手の本拠地に直接移動する．
• 各チームは自チームの本拠地からリーグ戦を開始し，終了したら自チームの本拠地に戻る．

w(Y ) = 2n(n − 1) −次のようなリーグ戦の形式を 1 重総当りリーグ戦という:• 各チームは他の n − 1 チームと 1 回ずつ対戦する．
• 全てのチームが 1 節に 1 回対戦し，n − 1 節でリーグ戦(1)という関係があることが容易に導ける．
従って，CTTP はブレーク数を最大にするような許容解を見つける問題と本質的に等価である．以後ブレーク数最大化についての議論を行う．

は終了する．
次のようなリーグ戦の形式を 2 重総当りリーグ戦という:3 ブレーク数の上界• 各チームは他の n − 1 チームと 2 回ずつ対戦する．
• 各チーム対はそれぞれの本拠地で 1 回ずつ対戦する．
• 全てのチームが 1 節に 1 回対戦し，2(n − 1) 節でリー

補題 1 任意の許容スケジュールのブレーク数は以下で定められる UB(n) 以下である．

2(n ≡ 0 (mod 3) のとき),
 (4/3)n − 2n
UB(n) =(4/3)n(n − 1) − (n − 2) (n ≡ 1 (mod 3) のとき),
(4/3)n(n − 2)(n ≡ 2 (mod 3) のとき).

グ戦は終了する．
距離行列 D とは，行と列がチームの集合でインデックスされ，t 行 t0 の要素 d(t, t0 ) はチーム t と t0 の本拠地間の距離を表し，d(t, t) = 0 である行列である．2 重総当りリーグ戦のスケジュールが与えられたとき，チーム t の移動距離とは，スケジュールに従って対戦相手の本拠地を巡回したときの経路の長さである．スケジュールの移動距離とは各チームの移動距離の総和である．巡回トーナメント問題とは Easton, Nemhauser, Trick [1] により提唱された問題で次のように記述される．

略証: n ≡ 1 (mod 3) の場合について考える．スロットの数は 2(n − 1) ≡ 0 (mod 3) である. 明らかに各チームは高々 (2/3)2(n − 1) = (4/3)(n − 1) 個のブレークしか持ち得ない．また，高々 2 チームしか (4/3)(n − 1) 個のブレークをもつことはできないことが容易に示せる．従って任意の許容スケジュールのブレーク数は，

2(4/3)(n−1)+(n−2)(4/3)(n − 1) − 1 = (4/3)(n−1)−(n−2)

問題 1 巡回トーナメント問題
入力b(Y )
2以下である．

n ∈ {0, 2} (mod 3) の場合についても同様にして示すこと

チームの集合 T = {1, 2, . . . , n}, (n は偶数) と各ができる．

1

ムアウェイを反転したスケジュールを X 0 とする．X 0 は 2
チームが 2(n − 1) − 1 個のブレークを持ち，残りの n − 2
チームが 2(n − 1) − 2 個のブレークを持ち，全てのチームが s > 1, s ≡ 1 (mod 3) なるスロット s にブレークを持つスケジュールである．この X 0 から構成法 2 を用いて 2 重総当りリーグ戦 Y 0 を構成する．Y が許容スケジュールであり，b(Y ) = (4/3)n(n − 1) − (n − 2) ことは容易に確認できる．
n ∈ {0, 2} の場合についても同様に示すことができる．
構成法 2 において，定理 3 の許容スケジュールを構成することができる．

4 ポリゴン法を用いた構成法
1 重総当りリーグ戦のスケジュールから 2 重総当りリーグ戦のスケジュールを次のように構成する．
構成法 1n ≡ 1 (mod 3) の場合

1. 1 重総当りリーグ戦のスケジュール X を構成する．
2. 各 i ∈ {1, 2, . . . , (n − 1)/3} に対して，X の部分スケ
ジュール Xi が，スロット (3i − 2, 3i − 1, 3i) からなるように X を分割する．
3. Xi のホームアウェイを反転させた部分スケジュールをX とし，Xi とX i を以下のように接続して 2 重総当りリーグ戦のスケジュール Y を構成する．

6 結果
提案手法の結果を表 1 にまとめる．

Y = (X1 , X 1 , X 2 , X2 , X3 , X 3 , . . . , X (n−1)/3 , X(n−1)/3 ).

表1定理 2 許容スケジュール Y で，

 UB(n) − ((2/3)n − 2) (n ≡ 0 (mod 3)),b(Y ) =UB(n) − (2/3)(n − 1) (n ≡ 1 (mod 3)),UB(n) − (5/3)(n − 2) (n ≡ 2 (mod 3)),n

移動回数
最良解 LB(n) 定理 2 定理 3

ブレーク数

UB(n) 定理 2 定理 3
306
296
306
396
386
380
480
450
462
596
582
596
720
706
698
832
792
808
982
964
982
1140
1122 1112
1280
1230 1250
1464
1442 1464
1656
1634 1622
1824
1764 1788
2042
2016 2042
2268
2242 2228
2464
2394 2422
2716
2686 2716

16327
327
332 *327
18
418
414
419
426
20
521
520
535
529
22
632
626
633 *626
24
757
744
751
755
26
—884
904
896
28— 1021 1030 *1021
30— 1170 1179 1184
32— 1344 1369 1359
34— 1512 1523 *1512
36— 1692 1703 1709
38— 1900 1930 1918
40— 2099 2112 *2099
42— 2310 2323 2330
44— 2552 2587 2573
46— 2782 2797 *2782
n: チーム数．
known:[2] に公開されている最良解の値, 2006 年 2 月現在.
*: 下界 LB(n) を達成した解．

であるものが存在する．
構成法 1 において，1 重総当りリーグ戦 X をポリゴン法を改訂した方法をもちいて構成することで，定理 2 の許容スケジュールを構成することができる．

5 整数計画法を用いた構成法
1 重総当りリーグ戦のスケジュールから 2 重総当りリーグ戦のスケジュールを次のように構成する．
構成法 2

チーム数 16 ≤ n ≤ 46 の問題に対する結果.

n ≡ 1 (mod 3) の場合

1. 1 重総当りリーグ戦のスケジュール X を構成する．
2. 各 i ∈ {1, 2, . . . , (n − 1)/3} に対して，X の部分スケ
ジュール Xi が，スロット (3i − 2, 3i − 1, 3i) からなるように X を分割する．
3. Xi のホームアウェイを反転させた部分スケジュールをX とし，Xi とX i を以下のように接続して 2 重総当りリーグ戦のスケジュール Y を構成する．
Y = (X1 , X 1 , X2 , X 2 , X3 , X 3 , . . . , , X(n−1)/3 , X (n−1)/3 ).

参考文献

n ∈ {0, 2} の場合もほぼ同様の手続きにより構成する．

[1] K. Easton, G. L. Nemhauser and M. A. Trick:
The traveling tournament problem: description andbenchmarks, Lecture Notes in Computer Science,2239 (2001), Springer, 580–585.
[2] M. Trick: Challenge traveling tournament problem, Web Page. http://mat.gsia.cmu.edu/TOURN/,2006.
[3] S. Urrutia and C. C. Ribeiro: Maximizing breaks
and bounding solutions to the mirrored traveling
tournament problem, Discrete Applied Mathematics(to appear).

定理 3 チーム数 n が 16 ≤ n ≤ 46 の許容スケジュール Yで， UB(n) − (n − 2) (n ≡ 0 (mod 3)),b(Y ) =UB(n)(n ≡ 1 (mod 3)),UB(n) − (n − 2) (n ≡ 2 (mod 3)),であるものが存在する．
略証:n ≡ 1 (mod 3) の場合を示す．X を (B1) b(X) =n − 2，(B2) スロット s ∈ {3, 5, 0} (mod 6) にちょうど 2チームがブレークをもつような 1 重総当りリーグ戦のスケジュールとする．n ∈ {16, 22, 28, 34, 40, 46} のとき，整数計画法を解くことにより，(B1), (B2) を満たすスケジュールが存在することを確認した．X の偶数スロットのホー2