Abstract
The Traveling Tournament Problem (TTP) is a combinatorial problem that combines features from the traveling salesman problem and the tournament scheduling problem. We propose a family of tabu search solvers for the solution of TTP that make use of complex combination of many neighborhood structures. The different neighborhoods have been thoroughly analyzed and experimentally compared. We evaluate the solvers on three sets of publicly available benchmarks and we show a comparison of their outcomes with previous results presented in the literature. The results show that our algorithm is competitive with those in the literature.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahuja, R.K., J.B. Orin, and D. Sharma. (2000). “Very Large Scale Neighborhood Search.” International Transactions in Operations Research 7, 301–317.
Anagnostopoulos, A., L. Michel, P. Van Hentenryck, and Y. Vergados. (2005). “A Simulated Annealing Approach to the Traveling Tournament Problem.” Journal of Scheduling 9(2), 177–193.
Araùjo, A., V. Rebello, C. Ribeiro, and S. Urrutia. (2005). “A Grid Implementation of a GRASP”-ILS Heuristic for the Mirrored Traveling Tournament Problem (Extended Abstract). In Proceedings of the 6th Metaheuristics International Conference (MIC2005), Vienna, Austria, pp. 70–76.
Birattari, M. (2004). The Problem of Tuning Metaheuristics as Seen from a Machine Learning Perspective. Ph.D. thesis, Université Libre de Bruxelles, Brussels, Belgium.
Birattari, M. (2005). The RACE Pacakge. http://cran.r-project.org/doc/packages/race.pdf.
Conover, W. (1999). Practical Nonparametric Statistics 3rd edn. John Wiley & Sons, New York, NY, USA.
de Werra, D. (1981). “Scheduling in Sports.” In P. Hansen (ed.), Studies on Graphs and Discrete Programming, North Holland, Amsterdam, the Netherlands, pp. 381–395.
Di Gaspero, L. and A. Schaerf. (2003). “ EasyLocal++”: An Object-Oriented Framework for Flexible Design of Local Search Algorithms.” Software—Practice & Experience 33(8), 733–765.
Dinitz, J.H., D.K. Garnick, and B.D. McKay. (1994). “There are 526,915,620 Nonisomorphic One-factorizations of K 12”. Journal of Combinatorial Design 2, 273–285.
Easton, K., G. Nemhauser, and M. Trick. (2001). “The Traveling Tournament Problem Description and Benchmarks.” In Proceedings of the 7th International Conference on the Principles and Practice of Constraint Programming (CP-99), Springer-Verlag, Berlin, Germany, vol. 2239 of Lecture Notes in Computer Science, pp. 580–589.
Easton, K., G. Nemhauser, and M. Trick. (2003). “Solving the Traveling Tournament Problem: A Combined Integer Programming and Constraint Programming Approach.” Practice and Theory of Automated Timetabling IV (PATAT-2002), Springer-Verlag, Berlin, Germany, vol. 2740 of Lecture Notes in Computer Science, pp. 100–109.
Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer Academic Publishers, Norwell, MA, USA.
Hansen, P. and N. Mladenovié. (1999). “An Introduction to Variable Neighbourhood Search.” In S. Voß, S. Martello, I. Osman, and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Norwell, MA, USA, pp. 433–458.
Henz, M. (2001). “Scheduling a Major College Basketball Conference—Revisited.” Operations Research 49(1), 163–168.
Jünger, M., O. Reinelt, and G. Rinaldi. (1995). “The Traveling Salesman Problem.” In M. Ball, T. Magnanti, C. Monma, and G. Nemhauser (eds.), Handbooks in Operations Research and Management Science, North-Holland, Amsterdam, the Netherlands, chapter 7, pp. 225–330.
Langford, G. (2005). “Personal Communication.”
Lim, A., B. Rodrigues, and X. Zhang. (2005). “A Simulated Annealing and Hill-Climbing Algorithm for the Traveling Tournament Problem.” European Journal of Operations Research (to appear).
Lindner, C.C., E. Mendelsohn, and A. Rosa. (1976). “On the Number of 1-Factorizations of the Complete Graph.” Journal of Combinatorial Theory Series B 20, 265–282.
Lourenço, H.R., O. Martin, and T. Stützle. (2002). “Applying Iterated Local Search to the Permutation flow Shop Problem.” In F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics, Kluwer Academic Publishers, Norwell, MA, USA, pp. 321–353.
Mendelsohn, E. and A. Rosa. (1985). “One-Factorizations of the Complete Graph—a Survey.” Journal of Graph Theory 9, 43–65.
R Development Core Team. (2005). R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. http://www.R-project.org, ISBN 3-900051-07-0.
Rasmussen, R. and M. Trick. (2005). “A Benders Approach for the Constrained Minimum Break Problems.” European Journal of Operations Research To appear.
Ribeiro, C.C. and S. Urrutia. (2004). “Heuristics for the Mirrored Traveling Tournament Problem.” In E. Burke and M.A. Trick (eds.), Proceedings of the 5th International Conference on Practice and Theory of Automated Timetabling (PATAT-2004), pp. 323–342.
Schaerf, A. (1999). “Scheduling Sport Tournaments using Constraint Logic Programming.” CONSTRAINTS 4(1), 43–65.
Trick, M. (2005). “Challenge Traveling Tournament Instances, web page.” URL: http://mat.gsia.cmu.edu/TOURN/. Viewed: November 25, 2005, Updated: October 13, 2005.
Urrutia, S. and C.C. Ribeiro. (2005). “Mazimizing Breaks and Bounding Solutions to the Mirrored Traveling Tournament Problem.” Discrete Applied Mathematics154(13), 1932–1938
Wallis, W.D., A.P. Street, and J.S. Wallis. (1972). Combinatorics: Room Squares, Sum-Free Sets, Hadamard Matrices. Number 292 in Lecture Notes in Mathematics, Springer-Verlag, Berlin, Germany.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gaspero, L.D., Schaerf, A. A composite-neighborhood tabu search approach to the traveling tournament problem. J Heuristics 13, 189–207 (2007). https://doi.org/10.1007/s10732-006-9007-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-006-9007-x