情報処理学会 第84回全国大会 会期:2022年3月3日~5日 情報処理学会 第84回全国大会 会期:2022年3月3日~5日

7M-03
巡回トーナメント問題に対する3種類の近傍解生成法の性能比較
○市川槙人,藤田実沙(中京大)
巡回トーナメント問題は,スポーツスケジューリング問題の一つであり,本拠地をもつチームのリーグ戦において,各種の制約条件を満たしつつ,全チームの移動距離の総和を最小にする試合スケジュールを作成する問題である.本研究では,巡回トーナメント問題に対する発見的解法において重要な役割を果たす,近傍解生成法について検討した.具体的には,3種類の近傍解生成法と,それらを組合わせた近傍解生成法をベンチマーク問題に適用し,解探索性能の違いを調査した.調査の結果,単体ではSwapRounds,組合せではSwapRoundsとSwapHomesを交互に行う手法が高い解探索性能を示すことが明らかになった.