Abstract
The Traveling Tournament Problem with Predefined Venues (TTPPV) is a single round robin variant of the Traveling Tournament Problem, in which the venue of each game to be played is known beforehand. We propose an Iterated Local Search (ILS) heuristic for solving real-size instances of the TTPPV, based on two types of moves. Initial solutions are derived from an edge coloring algorithm applied to complete graphs. We showed that canonical edge colorings should not be used as initial solutions in some situations. Instead, the use of Vizing’s edge coloring method lead to considerably better results. We also establish that the solution space defined by some commonly used neighborhoods in the sport scheduling literature is not connected in the case of single round robin tournaments, which explains the hardness of finding high quality solutions to some problem instances. Computational results show that the new ILS heuristic performs much better than heuristics based on integer programming and that it improves the best known solutions for benchmark instances.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anagnostopoulos, A., Michel, L., Hentenryck, P. V., & Vergados, Y. (2006). A simulated annealing approach to the traveling tournament problem. Journal of Scheduling, 9, 177–193.
de Werra, D. (1981). Scheduling in sports. In P. Hansen (Ed.), Annals of discrete mathematics : Vol. 11. Studies on graphs and discrete programming (pp. 381–395). Amsterdam: North Holland.
Durán, G., Noronha, T. F., Ribeiro, C. C., Souyris, S., & Weintraub, A. (2007). Branch-and-cut for a real-life highly constrained soccer tournament scheduling problem. In E. Burke & H. Rudová (Eds.), Lecture notes in computer science : Vol. 3867. Practice and theory of automated timetabling VI (pp. 174–186). Berlin: Springer.
Easton, K., Nemhauser, G., & Trick, M. (2001). The traveling tournament problem: description and benchmarks. In T. Walsh (Ed.), Lecture notes in computer science : Vol. 2239. Principles and practice of constraint programming (pp. 580–584). Berlin: Springer.
Gaspero, L., & Schaerf, A. (2007). A composite-neighborhood tabu search approach to the traveling tournament problem. Journal of Heuristics, 13, 189–207.
Kendall, G., Knust, S., Ribeiro, C. C., & Urrutia, S. (2010). Scheduling in sports: an annotated bibliography. Computers and Operations Research, 37, 1–19.
Knust, S. (2010). Scheduling non-professional table-tennis leagues. European Journal of Operational Research, 200, 358–367.
Lourenço, H. R., Martin, O. C., & Stutzle, T. (2003). Iterated local search. In F. Glover & G. Kochenberger (Eds.), Handbook of metaheuristics (pp. 321–353). Berlin: Springer.
Melo, R. A., Urrutia, S., & Ribeiro, C. C. (2009). The traveling tournament problem with predefined venues. Journal of Scheduling, 12, 607–622.
Nemhauser, G., & Trick, M. (1998). Scheduling a major college basketball conference. Operations Research, 46, 1–8.
Rasmussen, R., & Trick, M. (2006). The timetable constrained distance minimization problem. In J. Beck & B. Smith (Eds.), Lecture notes in computer science : Vol. 3990. Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 167–181). Berlin: Springer.
Rasmussen, R., & Trick, M. (2008). Round robin scheduling—a survey. European Journal of Operational Research, 188, 617–636.
Régin, J. (2001). Minimization of the number of breaks in sports scheduling problems using constraint programming. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 57, 115–130.
Ribeiro, C. C., & Urrutia, S. (2007a). Heuristics for the mirrored traveling tournament problem. European Journal of Operational Research, 179, 775–787.
Ribeiro, C. C., & Urrutia, S. (2007b). Scheduling the Brazilian soccer championship. In E. Burke & H. Rudová (Eds.), Lecture notes in computer science : Vol. 3867. Practice and theory of automated timetabling VI (pp. 149–159). Berlin: Springer.
Trick, M. (2000). A schedule-then-break approach to sports timetabling. In E. Burke & W. Erben (Eds.), Lecture notes in computer science : Vol. 2079. PATAT (pp. 242–253). Berlin: Springer.
Trick, M. (2009). Challenge traveling tournament instances. Online reference at http://mat.gsia.cmu.edu/TOURN/, last visited on August 19, 2009.
Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. Metody Discret Analiz, 3, 25–30 (in Russian).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Costa, F.N., Urrutia, S. & Ribeiro, C.C. An ILS heuristic for the traveling tournament problem with predefined venues. Ann Oper Res 194, 137–150 (2012). https://doi.org/10.1007/s10479-010-0719-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-010-0719-9