Solving the Traveling Tournament Problem by Packing Three-Vertex Paths

Authors

  • Marc Goerigk University of Kaiserslautern
  • Richard Hoshino Quest University Canada
  • Ken-ichi Kawarabayashi National Institute of Informatics
  • Stephan Westphal University of Gottingen

DOI:

https://doi.org/10.1609/aaai.v28i1.9031

Keywords:

traveling tournament problem, heuristic search, graph theory, scheduling theory

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.

AAAI 2014 Proceedings Cover

Downloads

Published

2014-06-21

How to Cite

Goerigk, M., Hoshino, R., Kawarabayashi, K.- ichi, & Westphal, S. (2014). Solving the Traveling Tournament Problem by Packing Three-Vertex Paths. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.9031

Issue

Vol. 28 No. 1 (2014): Twenty-Eighth AAAI Conference on Artificial Intelligence

Section

Main Track: Planning and Scheduling