波多野　卓磨
2014/6/18 (水), 15:30-17:30
東京大学 工学部6号館 235号室

　プロスポーツの試合日程について, 参加チームの総移動距離を最小化することを目指す巡回トーナメント問題は, 2010年にNP完全問題であることが証明された. 文献[1]では, 巡回トーナメント問題を発展させ, グラフ上の最短路問題に帰着させることで, 最適な試合日程を高速に得る手法が提案されている. 提案手法を日本プロ野球のリーグ戦に適用し, さらに文献[2]で行われた交流戦試合日程の最適化結果と組み合わせることで, 総移動距離を25%削減することができた.
　本発表では, 文献[1]と文献[2]で行われた, 日本プロ野球の通常日程と交流戦日程の最適化手法を紹介する. さらに, 文献[3]で行われた, 週末の試合数を考慮した最適化手法を紹介する.

参考文献
[1] Hoshino, R. and Kawarabayashi, K. The multi-round balanced traveling tournament problem. ICAPS, 2011, pp106-113 .
[2] Hoshino, R. and Kawarabayashi, K. The distance-optimal inter-league schedule for japanese pro baseball. COPLAS, 2011, pp 71–78.
[3] Hoshino, R. and Kawarabayashi, K. Balancing the traveling tournament problem for weekday and weekend games. In Twenty-Fifth IAAI Conference, 2013.