Solving the Traveling Tournament Problem by Packing Three-Vertex Paths
Abstract
The Traveling Tournament Problem (TTP) is a complex problem in sports scheduling whose solution is a schedule of home and away games meeting specific feasibility requirements, while minimizing the total distance traveled by all the teams. A recently-developed "hybrid" algorithm, combining local search and integer programming, has resulted in best-known solutions for many TTP instances. In this paper, we tackle the TTP from a graph-theoretic perspective, by generating a new "canonical" schedule in which each team's three-game road trips match up with the underlying graph's minimum-weight P_3-packing. By using this new schedule as the initial input for the hybrid algorithm, we develop tournament schedules for five benchmark TTP instances that beat all previously-known solutions.
Cite
Text
Goerigk et al. "Solving the Traveling Tournament Problem by Packing Three-Vertex Paths." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.9031Markdown
[Goerigk et al. "Solving the Traveling Tournament Problem by Packing Three-Vertex Paths." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/goerigk2014aaai-solving/) doi:10.1609/AAAI.V28I1.9031BibTeX
@inproceedings{goerigk2014aaai-solving,
title = {{Solving the Traveling Tournament Problem by Packing Three-Vertex Paths}},
author = {Goerigk, Marc and Hoshino, Richard and Kawarabayashi, Ken-ichi and Westphal, Stephan},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2014},
pages = {2271-2277},
doi = {10.1609/AAAI.V28I1.9031},
url = {https://mlanthology.org/aaai/2014/goerigk2014aaai-solving/}
}