Solving the traveling tournament problem by packing three-vertex paths

Management Science

Keywords

Traveling tournament problems, Vertex path

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Published

Standard

Solving the traveling tournament problem by packing three-vertex paths. / Goerigk, Marc; Kawarabayashi, Ken Ichi; Hoshino, Richard et al.
Proceedings of the National Conference on Artificial Intelligence. Vol. 3 AI Access Foundation, 2014. p. 2271-2277.

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Harvard

Goerigk, M, Kawarabayashi, KI, Hoshino, R & Westphal, S 2014, Solving the traveling tournament problem by packing three-vertex paths. in Proceedings of the National Conference on Artificial Intelligence. vol. 3, AI Access Foundation, pp. 2271-2277, 28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014, Quebec City, Canada, 27/07/14.

APA

Goerigk, M., Kawarabayashi, K. I., Hoshino, R., & Westphal, S. (2014). Solving the traveling tournament problem by packing three-vertex paths. In Proceedings of the National Conference on Artificial Intelligence (Vol. 3, pp. 2271-2277). AI Access Foundation.

Vancouver

Goerigk M, Kawarabayashi KI, Hoshino R, Westphal S. Solving the traveling tournament problem by packing three-vertex paths. In Proceedings of the National Conference on Artificial Intelligence. Vol. 3. AI Access Foundation. 2014. p. 2271-2277

Author

Goerigk, Marc ; Kawarabayashi, Ken Ichi ; Hoshino, Richard et al. / Solving the traveling tournament problem by packing three-vertex paths. Proceedings of the National Conference on Artificial Intelligence. Vol. 3 AI Access Foundation, 2014. pp. 2271-2277

Bibtex

@inproceedings{0f0bf5bfd5d944efa750208b7e7d72cc,

title = "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 threegame road trips match up with the underlying graph's minimum-weight P3-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.",

keywords = "Traveling tournament problems, Vertex path",

author = "Marc Goerigk and Kawarabayashi, {Ken Ichi} and Richard Hoshino and Stephan Westphal",

year = "2014",

language = "English",

isbn = "9781577356790",

volume = "3",

pages = "2271--2277",

booktitle = "Proceedings of the National Conference on Artificial Intelligence",

publisher = "AI Access Foundation",

address = "United States",

note = "28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014 ; Conference date: 27-07-2014 Through 31-07-2014",

}

RIS

TY - GEN

T1 - Solving the traveling tournament problem by packing three-vertex paths

AU - Goerigk, Marc

AU - Kawarabayashi, Ken Ichi

AU - Hoshino, Richard

AU - Westphal, Stephan

PY - 2014

Y1 - 2014

N2 - 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 threegame road trips match up with the underlying graph's minimum-weight P3-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.

AB - 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 threegame road trips match up with the underlying graph's minimum-weight P3-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.

KW - Traveling tournament problems

KW - Vertex path

M3 - Conference contribution/Paper

AN - SCOPUS:84908191785

SN - 9781577356790

VL - 3

SP - 2271

EP - 2277

BT - Proceedings of the National Conference on Artificial Intelligence

PB - AI Access Foundation

T2 - 28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014

Y2 - 27 July 2014 through 31 July 2014

ER -

Research

Keywords