著者

住川 裕岳 宮代 隆平 中森 眞理雄

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.64, pp.5-8, 2007-06-25

参考文献数

9

---

本研究では、スポーツスケジューリング問題の一種である巡回トーナメント問題を扱う。巡回トーナメント問題とは、ホーム&アウェイ形式の二重総当りリーグ戦を行うスポーツにおいて、各チームの移動距離の総和を最小化した試合日程を構築する問題である。この問題では、巡回セールスマン問題の難しさに加え、あるチームの対戦順序が他チームの対戦順序に影響を与えており、問題の難易度を増している。これまでの研究により、巡回トーナメント問題に対してはシミュレーテッド・アニーリングが有効であることが示されていたが、本研究ではタブーサーチを用いて最適化を行った。計算機実験の結果、既存のアルゴリズムによる結果に匹敵する質の良い解が得られた。The traveling tournament problem is a well known benchmark problem in sports scheduling. This problem has both an optimization aspect like the traveling salesman problem and a feasibility aspect as in many scheduling/timetabling problems. Since the traveling tournament problem was established, a number of researchers have tackled the problem with various optimization techniques. Recent researches indicated that simulated annealing algorithms are effective for the traveling tournament problem, and few results by tabu search are reported so far. In this manuscript, we propose a tabu search algorithm for the traveling tournament problem. Our computational experiments show that the proposed algorithm generates good solutions, which are competitive with solutions by simulated annealing algorithms.