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

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

3. アルゴリズム
　Ｖリーグスケジューリング問題のアルゴリズムは以下のような手順となる．

ステップ１: 開催期間に基づく試合日の決定とグループ化を行う．
ステップ２: 局所探索法で局所最適解を求める．
ステップ３: ステップ２の解を初期解としてタブー探索法を行い改善解を求める．

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

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