1. はじめに
 本論文では,スポーツスケジューリング問題を取り扱う.このスポーツスケジューリ ング問題とは,スポーツ競技大会において,試合の組合せや試合日時,試合会場などを 決めることである.スポーツスケジューリングは,様々な制約を満たす必要があり,通 常のスケジューリング問題より難しい問題になると言われており,近年盛んに研究され ている[1].
 スポーツスケジューリング問題は,これまで熟練した担当者が数週間(あるいは,数 日間)かけて手作業でスケジューリングを行っている所がほとんどであったが,近年の 情報化技術の発達によってコンピュータを用いることによってスケジュールを求めるよ うになってきた.そのアプローチとしては,大きく分けて最適化手法などを用いた数理 計画に基づくものと制約論理などを用いた人工知能理論に基づくものがある.
 本研究では,日本バレーボールリーグ「Vリーグ」のスケジュールを作成する.そこ で,種々の制約条件を満たしながら,移動経費を最小化するというVリーグスケジュー リング問題を考察する.
 まず,このVリーグスケジューリング問題の定式化を行う.ここで定式化された問題 を正確に解くことは計算量理論から困難であるため,我々はまず,この問題を解くため の局所探索法を構成する.さらにこの局所探索法に基づいたタブー探索法を構成する. 最後に,構成した局所探索法とタブー探索法をJavaを用いてコード化し,第7回(2000 年度)のVリーグの開催期間,参加チームに適用し,スケジュールを作る.


2. Vリーグスケジューリング問題
 以下ではVリーグスケジューリング問題の定式化を行う.この際,2000年度に行われ た第7回Vリーグ大会を用いて説明する.
 第7回Vリーグ大会では男子・女子ともに10チームが参加し,総当り戦を2回,前半 ・後半に分けて行っている.ただし,試合日程に「男子または女子4チームが集結し, 1日に1会場で2試合を行う」という原則があるため,集結した4チーム(1グループ )が各週毎に割り当てられた地域に赴いて試合を行うことになる.
 制約条件としては,「各チームの移動距離の連続性」や「各チーム間・各開催ブロッ ク間の公平さを保つこと」,「各チームからの要求(どのブロックで試合をしたいか) や各開催ブロックからの要求(どのチームを招待したいか)などの要求を満たすこと」 ,「観客動員数を増加させるため,人気のあるチームが偏らないようにすること」,「 前期・後期とも少なくとも1回はホーム(本拠地のある地域)で試合を行う」などの制 約が考えられる.
 本研究では,これらの制約条件の下で,総移動費用の最小化を目的とした.


3. アルゴリズム
 Vリーグスケジューリング問題のアルゴリズムは以下のような手順となる.
ステップ1
開催期間に基づく試合日の決定とグループ化を行う.
ステップ2
局所探索法で局所最適解を求める.
ステップ3
ステップ2の解を初期解としてタブー探索法を行い改善解を求める.

4. 計算機実験とその結果
 構成した局所探索法とタブー探索法をJavaを用いてコード化し,第7回(2000年度) Vリーグ大会の開催期間,参加チームに適用し,スケジュールを作る.
 第7回Vリーグ大会で実際に用いられたスケジュールと局所探索法によって作られた ものを比較すると,実際に用いられたスケジュールはいくつかの制約条件を満たしてい ない.例えば,「チーム間の総移動量の差が大きすぎる」,「ホームでの開催試合数が 足りないチームがある」,「移動の連続性が悪いチームがある」,「人気に偏りがある 」,「開催ブロックの公平さに偏りがある」,といった点である.一方,改善解は全て の制約条件を満たしていた.さらに,実際に用いられたスケジュールの総移動費用を10 0とすると,局所探索法を用いた改善解では,総移動費用が67と低くなったスケジュー ルを得ることができた.
 このことは,本研究で作られたスケジューリングにおいては,開催ブロックの試合要 求,テレビ放送のための制約等を考慮に入れていなかったことが一つの原因であると考 えられ,このような制約が入った場合についてのスケジューリングを今後求めていく必 要があると考えられる.
 さらにこの改善解にタブー探索法を用いて解を求めたところ,局所探索法と同様に全 ての制約条件を満たしており,局所探索法によって作られたものと比べ,目的関数値が 約5%程度良い解を得ることができた.ただし,計算時間においては,局所探索法が1 〜2分程度で終了するのに対し,タブー探索法では1時間以上かかることが多く,改善 が求められる.


参考文献
[1] M.Henz: Scheduling a major college basketball conference--revisited. O perations Research, 49 (2001), 163--168.