スポーツスケジューリング — 未解決問題を中心に —^{宮代隆平, 松井知己}

1 はじめに

「アメリカ大リーグの 2005 年スケジュールは，カーネギーメロン大学のトリック教授のグループが作成したものを採用することになった．」

最近の読売新聞 [23] で，このニュースをご覧になった方も多いと思う．ここでトリック教授というのは， 2002 年に INFORMS の会長だった Michael Trick のことを指している．このように欧米では， OR の研究者がスポーツ競技のスケジュール作成を行うことが増えてきている．アメリカ大リーグ以外にも，ここ数年ではブラジルのプロサッカーリーグ (Ribeiro, Urrutia [18]), アメリカ西海岸大学対抗バスケットボール (Nemhauser, Trick [16]), ドイツのプロサッカーリーグ (Bartsch, Drexl, Kröger [2]) など，大規模なスポーツ競技団体を含むさまざまな実例がある． OR の手法を用いたプロスポーツ競技のスケジュール作成の波は，やがて日本にも上陸することだろう．

スポーツ競技における対戦順序，競技施設の割当などをうまく決定し，質の良いスケジュールを作成する分野は，スポーツスケジューリングと呼ばれている．スポーツスケジューリングの研究は， 1970 年代ころから散発的に行われていたが，ここ数年で特に研究が活発化してきた．本稿では，スポーツスケジューリングの最近の研究に関して，いくつかの未解決問題を中心に紹介する．（スポーツスケジューリングに関しては，文献 [7,10–12] などを参照のこと．）まず 2.1 節において，基本的な用語を定義し，以下 2.2–2.5 節でそれぞれ移動距離最小化問題，ブレーク数最小化問題， Home-Away Table 許容性判定問題， carry-over effect 値最小化問題を紹介する．最後に 2.6 節で，スポーツスケジューリングの研究に用いられている手法ごとに概観を述べる．なお，本稿で述べるスケジュールの形式は，全てリーグ戦形式である．トーナメント形式の実用スケジューリング手法に関しては， Rokosz による文献 [19] を参照されたい．

2 スポーツスケジューリングの近年の展開

2.1 用語の定義

本稿では，次のような総当りリーグ戦のスケジューリングについて考える：

チーム 1 日目 2 日目 3 日目 4 日目 5 日目 1  3  @4  5  @6  2 2  @5  6  \underline{4}  \underline{3}  @1 3  @1  5  @6  @\underline{2}  4 4  @6  1  @2  5  @3 5  2  @3  @\underline{1}  @\underline{4}  6 6  4  @2  3  \underline{1}  @5_{図 1 チーム数 6 のスケジュール} ; • チーム数は偶数（以下 n とする）； ; • 各チームは他の n − 1 チームと 1 回ずつ対戦を ; 行う； ; • 全てのチームが 1 日（あるいは 1 週間など）に 1 ; 回試合を行い， n − 1 日でリーグ戦が終了する． ; プロスポーツ競技における総当りリーグ戦では，各 ; チームが本拠地を持っており，各試合はどこかのチーム ; の本拠地で開催されることが多い．以下， 2.2–2.4 節で ; は，次の条件の下で総当りリーグ戦が行われるとする： ; • 各チームはそれぞれ相異なる本拠地を持つ； ; • 各試合は，対戦する 2 チームのどちらかの本拠地 ; で行われる． ; 図 1 は，上記の条件を満たすスケジュールの一例であ ; る．スケジュールのそれぞれの行は各チームに対応し， ; 行内の数字は日ごとの対戦相手を表している．図 1 のス ; ケジュールでは，チーム 1 は 1 日目にチーム 3 と対戦 ; し，以下チーム 4, 5, 6, 2 の順序で試合を行っていく． ; 各試合の前にある@の記号は，その試合が対戦相手の本 ; 拠地で行われることを示している．つまり，チーム 1 は ; チーム 4 と 2 日目に試合を行うが，この試合はチーム 4 ; の本拠地で行われる．逆に@がついていない試合は，自 ; チームの本拠地で行われる．それぞれのチームにとって ; の本拠地をホーム，それに対して他チームの本拠地をア ; ウェイと呼ぶ．また各チームにとって，ホームでの試合 ; をホームゲーム，アウェイでの試合をアウェイゲームと ; 呼ぶ． ; 2.2 移動距離最小化問題 ; 前節で述べた，「各チームがそれぞれ異なる本拠地を ; 持ち，各試合は対戦するチームのどちらかの本拠地で行 ; う」というリーグ戦の形式は，野球，サッカーなどをは

表 1 TTP の下界／上界値 (NL instances [22])

チーム数下界上界ギャップ
4  8276  8276  0
6  23916 23916  0
8  39479 39479  0
10  57500 59583  2083
12  107483 111248  3765
14  182797 189766  6969
16  248852 267194  18342

じめとするプロのスポーツ競技で広く用いられている．このとき，リーグ戦のスケジュールをうまく作成することにより各チームの移動距離の総和を最小化する問題が移動距離最小化問題である．国土が広大な国では，移動距離を減少させることによる移動コストの削減効果は非常に大きくなる．最近では， Ribeiro, Urrutia [18] が，メタ・ヒューリスティクスを用いてブラジルのプロサッカーリーグ（2003 年， 24 チーム）の移動距離最小化をはかり，費用にして約 270 万ドルの削減に成功した．彼らの作成したスケジュールの総移動距離は 55 万 km だったが，同時にスケジュール委員会が手作業で作成したスケジュールの移動距離は約 150 万 km だったと報告されている．

移動距離最小化問題は，対象とするそれぞれのスポーツ競技によって条件が異なるが，現在ではベンチマークとして “Traveling Tournament Problem” （以下 TTP）がよく知られている． TTP のベンチマークデータは， Trick による Web ページ [22] に公開されている．（与えられる制約条件により，問題にいくつかの種類がある．） TTP の問題例は適度に抽象化されており他のスポーツスケジューリングにも容易に適用できること，また，問題の数値データ，現在までの最良の上界と下界の記録（表 1）が公開されていることから，この問題に対する研究が一気に広まった．

これまで TTP の上界の記録は，ほとんどメタ・ヒューリスティクスを用いた研究により更新されてきた．特に， Anagnostopoulos, Michel, Van Hentenryck, Vergados [1] によるシミュレーテッド・アニーリングを用いた手法は，従来得られていた上界値の記録を大幅に更新した．現在も TTP の最良暫定解の大部分が彼らによって発見されたものである．

一方， TTP の下界値の更新は進んでいない． TTP は巡回セールスマン問題とよく似た構造を持つが，同程度の規模の巡回セールスマン問題と比較して最適解を求めるのが極めて困難である．例えば，現時点におい

チーム 1 日目 2 日目 3 日目 4 日目 5 日目 1  3  4  5  6  2 2  5  6  4  3  1 3  1  5  6  2  4 4  6  1  2  5  3 5  2  3  1  4  6 6  4  2  3  1  5^{図 2 チーム数 6 のスケジュール（開催場所の割当無し）}

て最適解が求められているのは，チーム数（たった！） 8 以下の問題例に限られている．この結果は， Easton, Nemhauser, Trick [4] の強力なグループによって， TTP を整数計画問題として定式化し， 20 台の計算機上で並列分枝限定法を 5 日間走らせることにより得られたものであるから，生半可な結果ではない．これだけからも， TTP がいかに難しいか感じていただけると思う．チーム数 10 以上のインスタンスに関して，これまでの手法を用いたのでは現実的な時間内に最適性を証明するのは難しく，研究に何らかのブレークスルーが必要だと考えられる． 2.3 ブレーク数最小化問題

図 1 のスケジュールは，各チームがそれぞれの日において「どのチームと」「どちらの本拠地で」対戦するか，という情報から成り立っている．本節では，あらかじめ「どのチームと対戦するか」が決められている場合について考える．図 2 のような，試合開催場所の割当が決定されていないスケジュールが与えられた場合，スケジュールを完成させるためには各試合の開催場所（ホーム／アウェイ）を割り当てる必要がある．

さて，ホーム／アウェイを決定する際に，何を基準にしたらよいだろうか．スポーツスケジューリングの分野では，チーム t が d − 1 日目と d 日目に連続してホームゲームを行う，あるいは連続してアウェイゲームを行うとき，チーム t は d 日目にブレークを持つ，と呼ばれる．例えば図 1 のスケジュールでは，ブレークが 6 つある．（図 1 中の下線部がブレークに対応．）ブレークの多いスケジュールは，チーム間の公平性が保たれない，各本拠地での試合開催間隔がばらばらになる，などの問題点があり，多くのスポーツ競技において望ましくないスケジュールとされている．

ブレーク数最小化問題とは，試合開催場所の指定が無いスケジュールが与えられたとき，ブレークができるだけ少なくなるように各試合にホーム／アウェイを割り当てる問題である．例えば，図 2 のスケジュール（試合開催場所の割当て無し）が与えられたとき，図 1 のようにホーム／アウェイを割り当てればブレーク数は 6 となる

チーム 1 日目 2 日目 3 日目 4 日目 5 日目
1  H  A  H  A  H
2  A  H  \underline{H}  \underline{H}  A
3  A  H  A  \underline{A}  H
4  A  H  A  H  A
5  H  A  \underline{A}  \underline{A}  H
6  H  A  H  \underline{H}  A

図 3 チーム数 6 の Home-Away Table

が，ブレーク数が 4 となる割当も存在し，それが最適解となる．

ブレーク数最小化問題は，スポーツスケジューリングの中でも比較的新しい問題である．この問題に対しては， 1998 年に Régin [17] が制約論理法を用いてチーム数 20 までのインスタンスを， 2000 年には Trick [21] が整数計画法を用いた定式化を行いチーム数 22 までのインスタンスを解いている． 2003 年には Elf, Jünger, Rinaldi [5] がグラフ上の MAX CUT を求める問題として定式化を行い，専用の分枝限定法を実装してチーム数 26 までのインスタンスを現実的な時間で解いた．宮代・松井 [15] は，ブレーク数最小化問題を MAX RES CUT および MAX 2SAT として定式化し， Goemans, Williamson [6] の SDP 緩和を用いた近似解法を適用して，大規模なインスタンス（〜40 チーム）に対しても高速に質の良いスケジュールが生成できることを実証した．

ブレーク数最小化問題の計算複雑度は NP-困難と予想されているが，まだ解決はされていない．一方， Elf ら [5] は，「ブレーク数最小化問題において，ブレーク数がリーグ戦のチーム数未満となるような解が存在するか否かは多項式時間で判定可能」という予想を提出していたが，これは宮代・松井 [14] によって肯定的に解決された． 2.4 Home-Away Table 許容性判定問題

本節では，ブレーク数最小化問題とは逆に，条件として各試合のホーム／アウェイのみが先に固定された状況を考える．実際のスケジューリング現場では，試合開催場所の確保の観点などから，各試合がホーム／アウェイのどちらで行われるかが前もって決められている場合も多い．図 3 は Home-Away Table （以下 HAT）と呼ばれる表で，各試合がホームもしくはアウェイのどちらで行われるかを指定している．（H がホーム， A がアウェイに対応．）

HAT が制約条件として与えられた場合，スケジュール作成者はそれに従いスケジュールを作成していく．（図 3 から作成できるスケジュールのうちのひとつが，

チーム 1 日目 2 日目 3 日目 4 日目 5 日目
1  H  A  \underline{A}  H  A
2  H  A  H  \underline{H}  A
3  H  A  H  A  \underline{A}
4  A  H  \underline{H}  A  H
5  A  H  A  \underline{A}  H
6  A  H  A  H  \underline{H}

図 4 スケジュール生成不可能な HAT

図 1 である．）しかし，任意の HAT からスケジュールが作成できるわけではなく， HAT によってはそれが不可能なことがある．スケジュールを作成できる HAT の必要条件として，

• それぞれの日について， H と A の数が同数

• H と A のパターンが全く同じチームが存在しない

というものがあるが，この条件を満たす HAT が全てスケジュールを生成可能というわけではない．図 4 は，上記の条件を満たしているがスケジュールの生成ができない HAT の一例である．

与えられた HAT がスケジュールを生成できるか否か（HAT の許容性）を判定する問題が， Home-Away Table 許容性判定問題である．この問題は，既に 1980 年の de Werra の論文 [3] において，未解決問題として提起されている．また， Nemhauser, Trick [16] の論文においても注目するべき問題として触れられており，スポーツスケジューリングの大きな未解決問題の一つである．しかし，これまでこの問題に対する多項式時間アルゴリズム， NP-完全性の証明，許容 HAT （スケジュールを生成できる HAT）の特徴付けのいずれも得られていない．ただし，各チームがブレークを高々 1 個しか持たないような HAT に関しては，強力な必要条件が得られている [9, 13]．現状では HAT 許容性判定問題は整数計画法 [16] や制約論理法 [8] を用いて解かれることが多いが，これらの方法ではチーム数が多くなると計算時間が増大する． 2.5 Carry-Over Effect 値最小化問題

2.2–2.5 節では，リーグ戦の各試合は対戦する 2 チームのどちらかの本拠地で行われるとしてきたが，本節では試合開催場所の概念が無いスケジュールの作成を扱う．

ラグビーやアメリカンフットボールなどのハードなスポーツのスケジュール作成を考えよう．いま，リーグ戦に参加している n チームのうちチーム 2 は非常に強く，チーム 2 と対戦したチームには疲労が残り，その次の試

チーム 1 日目 2 日目 3 日目 4 日目 5 日目 6 日目 7 日目 1  8  3  4  5  6  7  2 2  3  4  5  6  7  8  1 3  2  1  6  8  5  4  7 4  5  2  1  7  8  3  6 5  4  7  2  1  3  6  8 6  7  8  3  2  1  5  4 7  6  5  8  4  2  1  3 8  1  6  7  3  4  2  5 図 5 coe 値 140 のスケジュール
チーム 1 日目 2 日目 3 日目 4 日目 5 日目 6 日目 7 日目
1  4  5  6  7  8  2  3
2  5  4  8  3  6  1  7
3  8  6  5  2  4  7  1
4  1  2  7  6  3  5  8
5  2  1  3  8  7  4  6
6  7  3  1  4  2  8  5
7  6  8  4  1  5  3  2
8  3  7  2  5  1  6  4

図 6 balanced スケジュール (coe 値 56)

合に影響が残ると想定する．そのような場合，図 5 と図 6 ではどちらが良いスケジュールだろうか？図 5 のスケジュールでは，チーム 1 が行う 7 試合のうち実に 5 試合で，「対戦相手の，直前の対戦相手がチーム 2」になっている．したがって，チーム 1 は相対的に有利になると考えられる．以下では，このような観点のもとでチーム間の公平性を評価する尺度を紹介する．

リーグ戦のスケジュールにおいて， d 日目にチーム i 対チーム k の試合があり， d + 1 日目（n 日目は 1 日目とする）にチーム j 対チーム k の試合が行われるとき，「チーム i がチーム j に carry-over effect （以下 coe）を与える」と定義する．与えられたスケジュールに対して， c_{ij} をチーム i がチーム j へ coe を与えた回数とし，これによって定まる行列 C = (c_{ij}) をそのスケジュールに対応する coe 行列と呼ぶ．定義より， coe 行列はチーム数 n のスケジュールに対して各行，各列の和が n − 1, 対角要素が 0 の非負整数行列となる．スケジュールに対応する coe 行列 C = (c_{ij}) に対して， ∑_{i,j}(c_{ij}^{2}) をそのスケジュールの coe 値と呼ぶ．明らかに， coe 値は coe 行列の非対角要素が全て 1 になるとき最小値 n(n − 1) をとる．

あるスケジュールから定まる coe 行列の非対角要素が全て 1 になるとき，そのスケジュールを balanced スケジュールという． balanced スケジュールは，各チームが受け取る coe の発生源が偏っていない，という意味

表 2 coe 値最小化問題の記録

チーム数 n n(n − 1) 暫定最良解参考
4  12  12 balanced
6  30  60  最適
8  56  56 balanced
10  90  122
12  132  188
14  182  260
16  240  240 balanced
18  306  428
20  380  520

で最適なスケジュールである．図 6 のスケジュールは balanced スケジュールであり， coe 値は n(n − 1) = 56 となる．それに対して図 5 のスケジュールの coe 値は 140 となり，図 6 のスケジュールと比較して不公平なことがわかる．

coe 値最小化問題は， coe 値を最小にするスケジュールを求める問題である． Russell [20] は，チーム数 n が n = 2^{m} (m ≥ 2) の場合， balanced スケジュールの作成方法を与えた．また同じ論文の中で，チーム数 n = p^{m} + 1 (p は奇素数) の場合に対する発見的解法を提案していた．

しかし近年の研究で，この発見的解法はチーム数 6 の場合最適解を与えるが，チーム数 10, 12 の場合にはそうでないことが示された． Russell の発見的解法では，チーム数 10, 12 の場合に得られるスケジュールの coe 値はそれぞれ 138, 196 だったが，チーム数 10 の場合 122 （論文 [21]） , チーム数 12 の場合には 188 （論文 [8]）のスケジュールが最近発見されている（表 2）．これらの結果は制約論理法をベースにした実験で得られたものであり，これ以上のチーム数に対しては計算が難しい．また，いまのところ coe 値の最小化を行う効率的なアルゴリズムは知られておらず，チーム数 10, 12 の場合の新しい結果が最適解かどうかわかっていない．また，チーム数が 2 のベキ乗でない場合には balanced スケジュールが存在しないだろうと予想されているが，この問題も未解決である． 2.6 研究手法の概観

スポーツスケジューリングの研究を大まかに分類すると，制約論理法を用いた研究，メタ・ヒューリスティクスを用いたもの，整数計画などの数理計画法に基づくもの，彩色問題に代表されるグラフ理論，実験計画法などのデザイン理論・組合せ理論を用いたものに分けられる．以下，スポーツスケジューリングにおけるそれぞれの手法の特徴を簡単に述べる．

制約論理法は一般に，制約条件が厳しい問題に対して許容解を見つけるという目的に適している．また，非常に多様な形の制約条件を扱えるのが特徴である．ただし，目的関数を最小化あるいは最大化する問題は，規模が大きくなると計算時間が急激に増加する傾向がある．

スポーツスケジューリングの実用現場では，問題に与えられた制約条件に急に変更があった場合など，何度も問題を解きなおすことが多い．これらのことから，高速にスケジュールを生成できるメタ・ヒューリスティクスは実用的に好まれているようである．

整数計画法に代表される，各種の数理計画法によるアプローチは，最小化（最大化）問題に対する最適性の保証を行うことができる．また，問題を適切にモデル化できれば非常に強力なツールとなる．ただし，問題の規模によっては現実的な時間で最適解を得るのが難しいこともある．

グラフ理論やデザイン理論，組合せ理論を用いた研究は， 1980 年代に複数行われたが，現在ではあまり新しい成果は出ていない．また，現実のスケジューリング問題では複雑な制約条件が存在し，これらの理論的に美しい結果をそのまま適用することができないケースが多くなってしまっている．

3 おわりに

本稿では，スポーツスケジューリングにおける最近の研究を， 4 つの問題を中心にして紹介した．紙面の都合上，グラフ理論，組合せ理論を用いた研究はほとんど紹介できなかったのが残念である．また，現実問題のモデル化と解法の詳細もお伝えできなかったが，本文中で引用した以外にも，スポーツスケジューリングの適用先はアメフト，野球，バスケットボール，チェス，クリケット，アイスホッケー，サッカー，テニス，卓球など，非常に多岐にわたっている．

現時点でのスポーツスケジューリングは，計算機の普及と高速化，および各種解法の発達により現実問題への適用が進んでいる．その一方で，スポーツ興行の巨大化にも対応できるさらに高速なアルゴリズムの開発など，取り組むべき課題は多数残っている．将来，日本のスポーツ産業界において OR の手法によるスケジューリングが当たり前になるだろうか？今後のスポーツスケジューリングの発展が楽しみである．

参考文献

[1] A. Anagnostopoulos, L. Michel, P. Van Hentenryck, and Y. Vergados, “A simulated annealing approach to the traveling tournament problem,” in: Proceedings of the 5th International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2003 (available at http://www.cs. brown.edu/people/pvh/).

[2] T. Bartsch, A. Drexl, and S. Kröger, “Scheduling the professional soccer leagues of Austria and Germany,” Computers & Operations Research, to appear.

[3] D. de Werra, “Geography, games and graphs,” Discrete Applied Mathematics, 2 (1980), pp. 327–337.

[4] K. Easton, G. L. Nemhauser, and M. A. Trick, “Solving the traveling tournament problem: a combined integer programming and constraint programming approach,” Practice and Theory of Automated Timetabling IV, Lecture Notes in Computer Science, 2740 (2003), Springer, Berlin, pp. 100–109.

[5] M. Elf, M. Jünger, and G. Rinaldi, “Minimizing breaks by maximizing cuts,” Operations Research Letters, 31(2003), pp. 343–349.

[6] M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journal of the ACM, 42 (1995), pp. 1115–1145.

[7] J. L. Gross and J. Yellen (eds.), “Handbook of graph theory,” 2004, CRC Press, Boca Raton, pp. 462–470.

[8] M. Henz, T. Müller, and S. Thiel, “Global constraints for round robin tournament scheduling,” European Journal of Operational Research, 153 (2004), pp. 92–101.

[9] 柏原賢二，「総当りゲームと 1-factorization」， 2003 年応用数学合同研究集会報告集， pp. 21–24.

[10] J. Y-T. Leung (ed.), “Handbook of scheduling: algorithms, models, and performance analysis,” 2004, CHAPMAN & HALL/CRC, Boca Raton, pp. 52-1– 52-19.

[11] 松井知己，「スポーツのスケジューリング」，オペレーションズ・リサーチ， 44 (1999), pp. 141–146.

[12] 宮代隆平，松井知己，「1993 年 J リーグの再スケジューリング」，オペレーションズ・リサーチ， 45 (2000), pp. 81– 83.

[13] R. Miyashiro, H. Iwasaki, and T. Matsui, “Characterizing feasible pattern sets with a minimum number of breaks,” Practice and Theory of Automated Timetabling IV, Lecture Notes in Computer Science, 2740 (2003), Springer, Berlin, pp. 78–99.

[14] R. Miyashiro and T. Matsui, “A polynomial-time algorithm to find an equitable home-away assignment,” Operations Research Letters, 33 (2005), pp. 235–241.

[15] R. Miyashiro and T. Matsui, “Semidefinite programming based approaches to the break minimization problem,” Computers & Operations Research, to appear.

[16] G. L. Nemhauser and M. A. Trick, “Scheduling a major college basketball conference,” Operations Re-

search, 46 (1998), pp. 1–8.

[17] J. -C. Régin, “Minimization of the number of breaks in sports scheduling problems using constraint programming,” Constraint Programming and Large Scale Discrete Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 57 (2001), American Mathematical Society, Providence, pp. 115–130.

[18] C. C. Ribeiro and S. Urrutia, “OR on the ball: applications in sports scheduling and management,” OR/MS Today, 31 (2004), pp. 50–54.

[19] F. M. Rokosz, Procedures for Structuring and Scheduling Sports Tournaments (3rd Edition), Charles C Thomas Publisher, Illinois, 2000.

[20] K. G. Russell, “Balancing carry-over effects in round robin tournaments,” Biometrika, 67 (1980), pp. 127– 131.

[21] M. A. Trick, “A schedule-then-break approach to sports timetabling,” in: Practice and Theory of Automated Timetabling III, Lecture Notes in Computer Science, 2079 (2001), Springer, Berlin, pp. 242–253.

[22] M. A. Trick, “Challenge traveling tournament instances,” Web Page, since 1999 (http://mat.tepper. cmu.edu/TOURN/).

[23] 読売新聞，朝刊スポーツ面， 2004 年 11 月 9 日．