スポ⊥ツスケジューリング一夫解決問題を中心に−
宮代 隆平，松井 知己…ll‖‖‖‖‖‖＝‖‖‖＝＝‖‖‖‖‖‖‖＝‖‖＝‖‖＝‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖…………………………………ll‖‖‖‖‖‖‖＝‖‖＝＝‖州l…………Il……………l……l…………‖＝州‖川＝‖＝‖‖川Ill川州I…………I

effect値最小化問題を紹介する ．最後に節2．6で，ス

1．はじめにポーツスケジューリングの研究に用いられている手法ごとに概観を述べる．なお，本稿で述べるスケジ「アメリカ大リーグの2005年スケジュールは，カーネギーメロン大学のトリック教授のグルー70が作成しルの形式は，すべてリーグ戦形式である．，トーナメンたものを採用することになった．」

ト形式の実用スケジューリング手法に関しては，Ro−

最近の読売新聞［23］で，このニュースをご覧になっkoszによる文献［19］を参照されたい．

た方も多いと思う．ここでトリック教授というのは，2002年にINFORMSの会長だったMichaelTrickの2．スポーツスケジューリングの近年の展開ことを指している．このように欧米では，ORの研究者がスポーツ競技のスケジュール作成を行うことが増

2．1用語の定義えてきている．アメリカ大リーグ以外にも，ここ数年

本稿では，次のような総当たりリーグ戦のスケジュ

ではブラジルのプロサッカーリーグ（Ribeiro，ーリングについて考える：Urrutia［18］），アメT）カ西海岸大学対抗バスケットボ

・チーム数は偶数（以下，乃とする）．

ール（Nemhムu草er，Trick［16］），ドイツのプロサッカ

・各チ⊥ムは他の乃Tlチームと1回ずつ対戦を行ーリーグ（Bartsch，Drexl，Kr6ger［2］）など，大規模なスポーツ競技団体を含む様々な実例がある．OR

監＝・すべてのチームが1日（あるいは1週間など）・にの手法を用いキプロスボーッ競技のスケジュール作成

1回試合を行い，乃−1日でリーグ戦が終了する．の波は，やがて日本にも上陸することだろう．

プロスポーツ競技における総当たりリーグ戦では，スポーツ競技における対戦順序，競技施設の割当を各チームが本拠地を持っており，各試合はどこかのチどをうまく決定し，質の良いスケジュールを作成するームの本拠地で開催されることが多い．節2．2〜2．4

分野は，スポーツスケジューリングと呼ばれている．

では，次の条件の下で総当たりリーグ戦が行われると● スポーツスケジューリングの研究は，1970年代頃かする：

ら散発的に行われていたが，ここ数年で特に研究が活・各チームはそれぞれ相異なる本拠地を持つ．
リング

発化してきた．本稿では，スポーーソスケジューの最近の研究に関して，いくつかの未解決問題を中心に紹介する（スポーツスケジューリングに関しては，文献［7，10〜12］などを参照のこと）．まず節2．1にお・各試合は，対戦する2チーキのどちらかの本拠地で行われる．
図1は，上記の条件を満たすスケジュ丁ルの一例である．スケジュールのそれぞれの行は各チームに対応いて，基本的な用語を定義し，以降の節2．2〜2．5でそれぞれ移動距離最小化問題，ブレーク数最小化問題，

Home−Away Table許容性判定問題，Carry−0Ver
みやしろ りゅうへい
東京農工大学大学院共生科学技術研究部〒184−8588小金井市中町2−24−16
まつい 之もみ東京大学大学院情報理工学系研究科〒113−8656文京区本郷7−3−1
2005年2月号チーム 1日目 2日目■ 3日目 4日目 5日冒
13 ◎5・＠62＠563＠154◎6 ■ 1 ＠2＠62

呈 ・＠14◎呈45 ＠352 ＠3 ◎主 ◎464 2

36主 ◎5

図1チーム数6のスケジュール© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（51）119

し，行内の数字は日ごとの対戦相手を表している．図かの種類がある）．TTPの問題例は適度に抽象化さ1のスケジュールでは，チーム1は1日目にチーム3れており他のスポーツスケジューリングにも容易に適と対戦し，以降チーム4，5，6，2の順序で試合を行用できること，また，問題の数値データ，現在までのっていく．各試合の前にある＠の記号は，その試合が最良の上界と下界の記録（表1）が公開されているこ対戦相手の本拠地で行われることを示している．つまとから，この間題に対する研究が一気に広まった．

り，チーム1はチーム4と2日目に試■合を行うが，ここれまでTTPの上界の記録は，ほとんどメタ・ヒの試合はチーム4の本拠地で行われる．逆に＠がついューリステイクスを用いた研究により更新されてきた．ていない試合は，自チームの本拠地で行われる．それぞれのチームにとっての本拠地をホーム，それに対し特に，Anagnostopoulos，Michel，Van Hentenryck，Vergados［1］によるシミュレーテッド・アニーリングて他チームの本拠地をアウェイと呼ぶ．また各チームを用いた手法は，従来得られていた上界値の記録を大にとって，ホームでの試合をホームゲーム，アウェイ幅に更新した．現在までのTTPの暫定最良解の大部での試合をアウェイゲームと呼ぶ．

分が彼らによって発見されたものである．

一方，TTPの下界値の更新は進んでいない．TTP

2．2 移動距離最小化問題
前節で述べた，「各チームがそれぞれ異なる本拠地は巡回セールスマン問題とよく似た構造を持つが，同を持ち，各試合は対戦するチームのどちらかの本拠地程度の規模の巡回セールスマン問題と比較して最適解で行う」というリーグ戦の形式は，野球，サッカーなを求めるのが極めて困難であどをはじめとするプロのスポーツ競技で広く用いられいて最適解が求められているのは，チーム数（わずている．このとき，リーグ戦のスケジュールをうまくか）8以下の問題例に限られている．この結果は，作成することにより各チームの移動距離の総和を最小Easton，Nemhauser，Trick［4］の強力なグループによ化する問題が移動距離最小化問題である．国土が広大って，TTPを整数計画問題として定式化し，20台のな国では，移動距離を減少させることによる移軌コス計算機上で並列分枝限定法を5日間走らせることによトの削減効果は非常に大きくなる．最近では，り得られたものであるから，生半可な結果ではない．

Ribeiro，Urrutia［18］が，メタ・ヒューリステイクス

このことからも，TTPがいかに難しいか感じていたを用いてブラジルのプロサッカーリーグ（2003年，だけると思う，チーム数10以上のインスタンスに関24チーム）の移動距離最小化をはかり，費用にしてして，これまでの手法を用いたのでは現実的な時間内約270万ドルの削減に成功した．彼らの作成したスケに最通性を証明するのは難しく，研究に何らかのブレジュールの総移動距離は55万kmだったが，同時にークスルーが必要だと考えられる．

スケジュール委員会が手作業で作成したスケジュール

2．3 ブレーク数最小化問題の移動距離は約150万kmだったと報告されている．

図1のスケジュールは，各チームがそれぞれの日に移動距離最小化問題は，対象とするそれぞれのスポおいて「どのチームと」「どちらの本拠地で」対戦すーツ競技によって条件が異なるが，現在ではベンチマるか，という情報から成り立っている．本節では，あークとしてTraveling Tournament Problem（以らかじめ「どのチームと対戦するか」が決められてい下，TTP）がよく知られている．TTPのベンチマーる場合について考える．図2のような，試合開催場所

クデータは，TrickによるWebペpジ［22］に公開さの割当が決定されていないスケジュールが与えられたれている（与えられる制約条件により，問題にいくつ場合，スケジュールを完成させるたりには各試合の開催場所（ホーム／アウェイ）を割り当てる必要がある．

表1TTPの下界／上界鱒（NLinstances［22］）チーム

チーム数 下界 上界 ギャップ
48276

23916 23916

0839479 39479

01057500 59583

1416‥≦

2083

3765

182797 189766
248852 267194 18342

3456225643131562446

1253523

14664

23

1

506

12 107483 111248●120（52）8276

・1日目 2日目 3日目 4日自 5日目

6969

図2 チーム数6のスケジュール（開催場所の割当無し）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

さて，ホーム／アウェイを決定する際に，何を基準状況を考える．実際のスケジューリング現場では，試にしたらよいだろうか．スポーツスケジューリングの合開催場所の確保の観点などから，各試合がホーム／分野では，チーム′がd−1日目とd日日に連続してアウェイのどちらで行われるかが前もって決められてホームゲームを行う，あるいは連続してアウェイゲーいる場合も多い．図3はHome−Away Table（以下，ムを行うとき，チームオはd日日にブレークを持つ，HAT）と呼ばれる 表で，各試合がと呼ばれる．例えば図1のスケジュールでは，ブレーウェイのどちらで行われるかを指定している（Hがクが六つある（図1中の下線部がブレークに対応）．

ホーム，Aがアウェイに対応）．

ブレークの多いスケジュHATが制約条件として与えられた場合，スケジュ保たれない，各本拠地での試合開催間隔がばらばらにール作成者はそれに従いスケジュールを作成していくなる，などの問題点があり，多くのスポーツ競技にお（図3から作成できるスケジュールのうちの一つが，いて望ましくないスケジュールとされている．

図1である）．．・しかし，任意のHATからスケジュー

ブレーク数最小化問題とは，試合開催瘍所の指定がルが作成できるわけではなく，HATによってはそれ無いスケジュールが与えられたとき，ブレークができが不可能なことがある．スケジュールを作成できるるだけ少なくなるように各試合にホーム／アウェイをHAT−の必要条件として，割り当てる問題である．例えば，図2のスケジュール・それぞれの目について，HとAの数が同数（試合開催場所の吉山当無し）が与えられたとき，図1

・HとAのパターンが全く同じチームが存在しなのようにホーム／アウェイを割り当てればブレーク数しヽは6となるが，ブレーク数が4となる割当も存在し，というものがあるが，この条件を満たすHATがすべそれが最適解となる．てスケジュールを生成可能というわけではない．図4

ブレーク数最小化問題は，スポー、ソスケジューリン
グの中でも比較的新しい問題である．この間題に対しは，上記の条件を満たしているがスケジュールの生成ができないHATの÷例である．ては，1998年にR6gin［i7］が制約論理法を用いてチ与えられたHATがスケジュールを生成できるか否ーム数20までのインスタンスを，2000年にはTrickか（HATの許容性）Lを判定する問題が，Home−［21］が整数計画法を用いた定式化を行いチーム数22

AwayTable許容性判定問題である．この間題は，既までのインスタンスを解いている．2003年にはElf，に1980年のdeWerraの論文［3］において，未解決問

Junger，Rinaldi［5］かグラフ上のMAXCUTを求め題として提起されている．また，Nemhauser，Trickる問題として定式化を行い，専用の分枝限定法を実装［16］の論文においても注目するべき問題として触れらしてチーム数26までのインスタンスを現実的な時間れており，スポーツスケジュ「リングの大きな未解決で解いた．宮代・松井［15］は，ブレーク数最小化問題

をMAX RES CUTおよびMAX2SATとして定式

チーム 1日目 2日目 3日目 4日目 5日目
HA

2AH3A

H4A

H

5H

A

6FA

化し，Goemans，Williamson［6］のSDP緩和を用いた近似解法を適用して，大規模なインスタンス（−40チーム）に対しても高速に質の良いスケジュールを生成できることを実証した．
ブレーク数最小化問題の計算複雑度はNP一困難と予想されているが，まだ解決はされていない．一方，

HAH

塑AHHA皇A皇A室HH

旦A

図3 チーム数6のHome−AwayTable

Elfら［5］は，「ブレーク数最小イヒ問題において，ブレーク数がリーグ戦のチーム数未満となるような解が存

チーム 1日目 2日目 3日日 4日．目 5日目在するか否かは多項式時間で判羞可能」という予想を提出していたが，これは宮代・松井［14］・によって肯定的に解決された．

23 H
4H
HA 皇

AHAA

5AH

本節では，ブレーク数最小化問題とは逆に，条件と6AHして各試合のホーム／アウェイのみが先に固定された
2005年2月号

旦H

2・4 Home−AAA

皇H

A旦AAA

H
H

皇H

H

宣

図4 スケジュール生成不可能なHAT■© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（53）121

問題の一つである．しかし，これまでこの間題に対すは相対的に有利になると考えられる．次では，このよる多項式時間アルゴリズム，NP−完全性の証明，許うな観点のもとでチーム間の公平性を評価する尺度を

容HAT（スケジュールを生成できるHAT）の良い紹介する．

特徴付けのいずれも得られていない．ただし，各チーリーグ戦のスケジュールにおいて，d日日にチームムがブレークをたかだか1個しか持たないような才対チーム々の試合があり，d十1日目（乃日日は1HATに関しては，強力な必要条件が得られている［9，日目とする）にチームノ対チーム

13］．現状ではHAT許容性判定問題は整数計画法

るとき，．「チームiがチームjにcarry−OVereffect［16］や制約論理法［8］を用いて解かれることが多いが，（以下，COe）を与える」と定義する．与えられたス

これらの方法ではチーム数が多くなると計算時間が増

ケジュールに対して，Cむをチームブがチームノへ大する．

coeを与えた回数とし，これによって定まる行列C＝

2．5 Carry−OverEffect値最小化問題（cむ）をそのスケジュールに対応するcoe行列と呼ぶ．

節2．2−2．5では，リーグ戦の各試合は対戦する2

定義より，COe行列はチーム数乃のスケジュールに対チームのどちらかの本拠地で行われるとしてきたが，して各行，各列の和が乃−1，対角要素が0の非負整本節では試合開催場所の概念が無いスケジュールの作数行列となる．スケジュールに対応するcoe行列C成を扱う．

＝（cび）に対して，∑i，ノ（cぴ2）をそのスケジュールのCOe値と呼ぶ．明らかに，COe値はcoe行列の非対角ラグビーやアメリカンフットボールなどのハードなスポーツのスケジュール作成を考えよう．いま，リー要素がすべて1になるとき下界値乃（乃−1）を達成す

グ戦に参加している乃チームのうちチーム2は非常る．に強く，チーム2と対戦したチームには疲労が残り，あるスケジュールから定まるcoe行列の非対角要

その次の試合に影響が残ると想定する．そのような場素がすべて1になるとき，そのスケジュールをbaト合，図5と図6ではどちらが良いスケジュールだろう

ancedスケジュールという．balancedスケジュールか？ 図5のスケジュールでは，チーム1が行う7試

は，各チームが受け取るcoeの発生源が偏っていな合のうち実に5試合で，「対戦相手の，直前の対戦相い，という意味で最適なスケジュールである．図6の手がチーム2」になっている．したがって，チーム1

スケジュールはbalancedスケジネールであり，COe値は乃（乃−1）＝56となる．それに対して図5のスケジュールのcoe値は140となり，図6のスケジュー

チーム 1日自 2日目 3日8 4日日 5日目 6日目 7日自183456234532

1 684554677681

77652
728325842673814771ルと比較して不公平なことが分かる．

2831636815442ールを求める問題である．Russell［20］は，チーム数nがn＝2m（m≧2）の場合，balancedスケジュールの作成方法を与えた．また同じ論文の中で，チーム数
31coe値最小化問題は，COe値を最小にするスケジュ

5乃＝♪椚＋1（♪は奇素数）の場合に対する発見的解法を提案していた．
しかし近年の研究で，この発見的解法はチーム数6

図5 coe値140のスケジュール

表2 coe値最小化問題の記録
チーム 1日目 2日日 3日目 4日日 5日日 6日目 7日目
625483852
7622

1673768836631841234472527て13587468553126416

図6 balancedスケジュール（coe値56）18122（54）11415381247105846

1

チーム数乃 m（和一1）暫定最良解© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

参考1212 balanced

30605656 balanced

90

122

132

188

182

260

240

240 balanced

306

428

380

520

最適

オペレーションズ・リサーチ

20

の場合最適解を与えるが，チーム数10，12の場合にースが多くなってしまっている．

はそうでないことが示された．Russellの発見的解法

3．おわりにでは，チーム数10，12の場合に得られるスケジュー

本稿では，スポーツスケジュー

ルのcoe値はそれぞれ138，196だったが，チーム数リングにおける最近10の場合122（論文［21］），チーム数12の場合にはの研究を，四つの問題を中心にして紹介した．紙面の188（論文［8］）のスケジュールが最近発見されている

都合上，グラフ理論∴組合せ理論を用いた研究はほと（表2）．これらの結果は制約論痙法をべ「スにした実んど紹介できなかったのが残念である／また，現実問験で得られたものであり，これ以上のチーム数に対し題のモデル化と解法の詳細もお伝えできなかったが，ては計算が難しい．また，いまのところcoe値の最本文中で引用した以外にも，スポーツスケジューリン小化を行う効率的なアルゴリズムは知られておらず，

グの適用先はアメフト，野球，バスケットボール，チ

チーム数10，12の場合の新しい結果が最適解かどうェス，・クか分かっていない．また，チーム数が2のベキ乗でなス，卓球など，非常に多岐にわたっている．

い場合にはbalahcedスケジュールが存在しないだろ

現時点でのスポーツスケジューリングは，計算機の普及と高速化，および各種解法の発達により現実問題うと予想されているが，この間題も未解決である．
2．6 研究手法の概観への適用が進んでいる．その一方で，スポーツ興行のスポ⊥ッスケジューリングの研究を大ま▲かに分類す

巨大化にも対応できるさらに高速なアルゴリズムの開ると，制約論理法を用いた研究，メタ・ヒューリステ発など，取り組むべき課題は多数残っている．将来，イクスを用いたもの，整数計画などの数理計画法に基日本のスポーツ産業界においてORの手法によるスケづくもの，彩色問題に代表されるグラフ理論，実験計

ジュー画法などのデザイン理論・組合せ理論を用しポーツスケジューリングが当たり前になるだろうか？ 今後のスリングの発展が楽しみである．

分けられる．本節では，スポーツスケジューリングに参考文献おけるそれぞれの手法の特徴を簡単に述べる．

［1］A．Anagnostopoulos，LMichel，P．VanHentenryck，

制約論理法は一般に，制約条件が厳しい問題に対しand Y．Vergados：て許容解を見つけるという目的に適している．また，

AISimulated annealing approach

tothetravelingtournamentproblem，非常に多様な形の制約条件を扱えるのが特徴である．

inProceedings

Ofthe5thInternationalWorkshop onIntegration of

ただし，目的関数を最小化あるいは最大化する問題は，

AI and OR Techniques in Constraint Programming

規模が大きくなると計算時間が急激に増加する傾向がfor CombinatorialOptimization Problems，2003

ある．

（avaihlbleathttp：／／www．cs．brown．edu／people／pvh／）．

スポーツスケジューリングの実用現場では，問題に［2］T．Bartsch，A．Drexl，and S．Kr6ger：与えられた制約条件に急に変更があった場合など，何the professionalsoccerleagues of Austria and Ger−

度も問題を解きなおすことが多い．これらのことから，

many，

高速にスケジュールを生成できるメタ・ヒューリステ

Scheduling

Computers＆OperatioりSResearch，tOappear・［3］D．de Werra： Geography，gameS and graphs，DiscreteAppliedMathematics，2，pp．327−337，1980．

イクスは実用的に好まれてし1るようである．

［4］K．East占n，G．L．Nemhauser，and M．A．Trick：

整数計画法に代表される，各種の数理計画法によるアプローチは，最小化（最大化）問題に対する最適性

Solving the travtling tournament broblem：a COm−の保証を行うことができる．また，問題を適切にモデ

binedinteger programmlng and constraint program−mingapproach，

ル化できれば非常に強力なツールとなる．ただし，問TimetablingIV，LectureNotesinComputerScience，

題の規模によっては現実的な時間で最適解を得るのオゞ

2740，Springer，Berlin，Pp．100−109，2003．

難しいこともある．

［5］M．Elf，M．Junger，and G．Rinaldi＝

グラフ理論やデザイン理論，組合せ痙論を用いた研breaks by m云ximizing cuts， Operations Research

究は，1980年代に複数行われたが，現在ではあまり新しい成果は出てし？ない．また，現実のスケジュー

ング問題では複雑な制約条件が存在し，これらの理論

PracticeandTheory ofAutomatedLetters，31，pp．343−349，2003．
リ［6］M．X．Goemans and D．P．Williamson：

Improved

approximation algorithms for maximurn Cut and的に美しい結果をそのまま適用することができないケ
2005年2月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（55）123

grammingbased approachesto thebreakminimiza−

Satis負ability problems using semide負nite program−ming，

JournaloftheACM，42，pp．1115−1145，1995． tion problem， Computers＆Operations Research，tO［7］J．L．Gross andJ．Yellen（eds．）： Handbook ofgraph theory， CRC Press，Boca Raton，pp．462−470，
2004．

［8］M．Henz，T．Miiller，and S．Thiel：

Schedulinga

major college basketballconference，Operations

Globalcon− Research，46，pp．1−8，1998．

Straintsforroundrobintournamentscheduling，

Eur− ［17］J．−C．Regin： Minimization of the number ofOpeanJournalof OperationalResearch，153，pp．92−

breaksinsportsschedulingproblemsusingconstraint

101，2004．

programming，［9］柏原賢二：「総当りゲームと1−factorization」，2003年

Constraint Programming and Large

Scale Discrete Optimization，DIMACS Seriesin Dis−crete Mathematics and TheoreticalComputer Sci−

応用数学合同研究集会報告集，pp．21−24，2003．

ence，57，American MathematicalSociety，Provi−［10］J・Y−T・Leung（ed・）： ：Handbook of scheduling：algorithms，mOdels，and performance analysis，dence，pp．115−130，2001．

CHAPMAN＆HALL／CRC，Boca Raton，pp．52−1−52−［18］C．C．Ribeiro and S．Urrutia： OR on the ball：applicationsin sports scheduling and management，

19，2004．

OR／MSToday，31，pp．50−54，2004．

［11］松井知己：「スポーツのスケジューlノング」，オペレー［19］F．M．Rokosz：Procedures for Structuring andションズ・リサーチ，44，pp．14卜146，1999．

SchedulingSportsTournaments（3rdEdition），Char−［12］宮代隆平，松井知己：「1993年Jリーグの再スケジューリング」，オペレーションズ・リサーチ，45，pp．8ト83，

lesCThomasPublisher，Illinois，2000．

［20］K．G．Russell： Balancing carry−0Ver effectsin

2000．

［13］R．Miyashiro，H．Iwasaki，andT．Matsui：Char−round robin tournaments，

acterizingfeasiblepatternsetswithaminimumnum−
ber of breaks， Practice and Theory of AutomatedBiometrika，67，pp．127−

131，1980．

［21］M．A．Trick： Aschedule−then−breakapproachto

TimetablingIV，LectureNotesinComputerScience，

SpOrtS timetabling，

2740，Springer，Berlin，pp．78L99，2003．

Automated TimetablingIII，Lecture Notesin Com−

［14］R．MiyashiroandT．Matsui：

Apolynomial−timealgorithm tofind an equitable home−aWay aSSlgn−
ment， Operations Research Letters，33，pp．235−241，［15］R．Miyashiro and T．Matsui： Semide丘nite pro−

124（56）

in：Practice and Theory ofputerScience，2079，Springer，Berlin，pp．242「253，2001．
［22］M．A．Trick：

Challenge traveling tournament

instances， WebPage，Since1999（http：／／mat．tepper．
cmu．edu／TOURN／）．

2005．

− −− Jappear．

［16］G．L．NemhauserandM．A．Trick：［23］読売新聞，朝刊スポーツ面，2004年11月9日．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ