An Efficient Simulated Annealing Approach to the Travelling Tournament Problem
Affiliation(s)
Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran. Faculty of department of Industrial Engineering, Sharif University of Technology, Tehran, Iran. Department of Computer Engineering, Sharif University of Technology, Tehran, Iran.
Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran. Faculty of department of Industrial Engineering, Sharif University of Technology, Tehran, Iran. Department of Computer Engineering, Sharif University of Technology, Tehran, Iran.
ABSTRACT
Scheduling sports leagues has drawn significant attention to itself in recent years, as it involves considerable revenue as well as challenging combinatorial optimization problems. A particular class of these problems is the Traveling Tournament Problem (TTP) which focuses on minimizing the total traveling distance for teams. In this paper, an efficient simulated annealing approach is presented for TTP which applies two simultaneous and disparate models for the problem in order to search the solutions space more effectively. Also, a computationally efficient modified greedy scheme is proposed for constructing a favorable initial solution for the simulated annealing algorithm. Our computational experiments, carried out on standard instances, demonstrate that this approach competes with previous offered methods in quality of found solutions and their computational time.
Scheduling sports leagues has drawn significant attention to itself in recent years, as it involves considerable revenue as well as challenging combinatorial optimization problems. A particular class of these problems is the Traveling Tournament Problem (TTP) which focuses on minimizing the total traveling distance for teams. In this paper, an efficient simulated annealing approach is presented for TTP which applies two simultaneous and disparate models for the problem in order to search the solutions space more effectively. Also, a computationally efficient modified greedy scheme is proposed for constructing a favorable initial solution for the simulated annealing algorithm. Our computational experiments, carried out on standard instances, demonstrate that this approach competes with previous offered methods in quality of found solutions and their computational time.
KEYWORDS
Travelling Tournament Problem; Simulated Annealing; Graph Coloring; Combinatorial Optimization
Travelling Tournament Problem; Simulated Annealing; Graph Coloring; Combinatorial Optimization
Cite this paper
S. Nourollahi, K. Eshghi and H. Razaghi, "An Efficient Simulated Annealing Approach to the Travelling Tournament Problem," American Journal of Operations Research, Vol. 2 No. 3, 2012, pp. 391-398. doi: 10.4236/ajor.2012.23047.
S. Nourollahi, K. Eshghi and H. Razaghi, "An Efficient Simulated Annealing Approach to the Travelling Tournament Problem," American Journal of Operations Research, Vol. 2 No. 3, 2012, pp. 391-398. doi: 10.4236/ajor.2012.23047.
References
[1] A. K. Easton, G. Nemhauser and M. Trick, “The Traveling Tournament Problem: Description and Benchmarks,” Lecture Notes in Computer Science, Vol. 2239, 2001, pp. 580-585. doi:10.1007/3-540-45578-7_43 [2] J. C. Bean and J. R. Birge, “Reducing Travelling Costs and Player Fatigue in the National Basketball Association,” Interfaces, Vol. 10, No. 3, 1980, pp. 98-102. doi:10.1287/inte.10.3.98 [3] A. Anagnostopoulos, L. Michel, P. Van Hentenryck and Y. Vergados, “A Simulated Annealing Approach to the Traveling Tournament Problem,” International Workshop on Integration of AI and OR Techniques, Montreal, 2003. [4] J. A. M. Schreuder, “Constructing Timetables for Sport Competitions,” Mathematical Programming Study, Vol. 13, 1980, pp. 58-67. doi:10.1007/BFb0120907 [5] D. de Werra, “Scheduling in Sports,” Studies on Graphs and Discrete Programming, 1981, pp. 381-395. [6] D. de Werra, “Some Models of Graphs for Scheduling Sports Competitions,” Discrete Applied Mathematics, Vol. 21, No. 1, 1988, pp. 47-65. doi:10.1016/0166-218X(88)90033-9 [7] R. T. Campbell and D. S. Chen, “A Minimum Distance Basketball Scheduling Problem,” Management Science in Sports, Studies in the Management Sciences, Vol. 4, 1976, pp. 15-26. [8] D. Costa, “An Evolutionary Tabu Search Algorithm and the NHL Scheduling Problem,” Information Systems and Operational Research, Vol. 33, 1995, pp. 161-178. [9] M. B. Wright, “Scheduling Fixtures for Basketball New Zealand,” Computers & Operations Research, Vol. 33, No. 7, 2006, pp. 1875-1893. doi:10.1016/j.cor.2004.09.024 [10] T. Benoist, F. Laburthe and B. Rottembourg, “Lagrange Relaxation and Constraint Programming Collaborative Schemes for Traveling Tournament Problems,” International Workshop on Integration of AI and OR Techniques, Ashford, Kent, 2001. [11] K. Easton, G. Nemhauser and M. Trick, “Solving the Traveling Tournament Problem: A Combined Integer Programming and Constraint Programming Approach,” Lecture Notes in Computer Science, Vol. 2740, 2003, pp. 100-109. doi:10.1007/978-3-540-45157-0_6 [12] J. H. Lee, Y. H. Lee and Y. H. Lee, “Mathematical Modeling and Tabu Search Heuristic for the Traveling Tournament Problem,” Lecture Notes in Computer Science, Vol. 3982, 2006, pp. 875-884. doi:10.1007/11751595_92 [13] K. K. H. Cheung, “Solving Mirrored Traveling Tournament Problem Benchmark Instances with Eight Teams,” Discrete Optimization, Vol. 5, No. 1, 2008, pp. 138-143. doi:10.1016/j.disopt.2007.11.003 [14] N. Fujiwara, S. Imahori, T. Matsui and R. Miyashiro, “Constructive Algorithms for the Constant Distance Traveling Tournament Problem,” The International Series of Conferences on the Practice and Theory of Automated Timetabling, 2006, pp. 402-405. [15] L. D. Gaspero and A. Schaerf, “A Composite-Neighbor- hood Tabu Search Approach to the Traveling Tournament Problem,” Heuristics, Vol. 13, No. 2, 2007, pp. 189-207. doi:10.1007/s10732-006-9007-x [16] S. Urrutia and C. C. Ribeiro, “Maximizing Breaks and Bounding Solutions to the Mirrored Traveling Tournament Problem,” Discrete Applied Mathematics, Vol. 154, No. 13, 2006, pp. 1932-1938. doi:10.1016/j.dam.2006.03.030 [17] M. A. Trick, “Michael Trick’s Guide to Sports Scheduling”. http://mat.gsia.cmu.edu/TOURN/ [18] D. T. Connelly, “General Purpose Simulated Annealing,” Journal of Operations Research, Vol. 43, 1992, pp. 495- 505. [19] R. Lewis and J. Thompson, “On the Application of Graph Coloring Techniques in Round-Robin Sports Scheduling,” Computers and Operations Research, Vol. 38, No. 1, 2011, pp. 190-204. doi:10.1016/j.cor.2010.04.012 [20] J. Kennedy and R. C. Eberhart, “A Discrete Binary Version of the Particle Swarm Algorithm,” World Multiconference on Systemics, Cybernetics and Informatics, Piscatawary, 1997, pp. 4104-4109. [21] A. Lim, B. Rodrigues and X. Zhang, “A Simulated Annealing and Hill-Climbing Algorithm for the Traveling Tournament Problem,” European Journal of Operational Research, Vol. 174, 2006, pp. 1459-1478. doi:10.1016/j.ejor.2005.02.065 [22] M. B. Wright, “Scheduling Fixtures for Basketball New Zealand,” Computers & Operations Research, Vol. 33, No. 7, 2006, pp. 1875-1893. doi:10.1016/j.cor.2004.09.024
[1] A. K. Easton, G. Nemhauser and M. Trick, “The Traveling Tournament Problem: Description and Benchmarks,” Lecture Notes in Computer Science, Vol. 2239, 2001, pp. 580-585. doi:10.1007/3-540-45578-7_43 [2] J. C. Bean and J. R. Birge, “Reducing Travelling Costs and Player Fatigue in the National Basketball Association,” Interfaces, Vol. 10, No. 3, 1980, pp. 98-102. doi:10.1287/inte.10.3.98 [3] A. Anagnostopoulos, L. Michel, P. Van Hentenryck and Y. Vergados, “A Simulated Annealing Approach to the Traveling Tournament Problem,” International Workshop on Integration of AI and OR Techniques, Montreal, 2003. [4] J. A. M. Schreuder, “Constructing Timetables for Sport Competitions,” Mathematical Programming Study, Vol. 13, 1980, pp. 58-67. doi:10.1007/BFb0120907 [5] D. de Werra, “Scheduling in Sports,” Studies on Graphs and Discrete Programming, 1981, pp. 381-395. [6] D. de Werra, “Some Models of Graphs for Scheduling Sports Competitions,” Discrete Applied Mathematics, Vol. 21, No. 1, 1988, pp. 47-65. doi:10.1016/0166-218X(88)90033-9 [7] R. T. Campbell and D. S. Chen, “A Minimum Distance Basketball Scheduling Problem,” Management Science in Sports, Studies in the Management Sciences, Vol. 4, 1976, pp. 15-26. [8] D. Costa, “An Evolutionary Tabu Search Algorithm and the NHL Scheduling Problem,” Information Systems and Operational Research, Vol. 33, 1995, pp. 161-178. [9] M. B. Wright, “Scheduling Fixtures for Basketball New Zealand,” Computers & Operations Research, Vol. 33, No. 7, 2006, pp. 1875-1893. doi:10.1016/j.cor.2004.09.024 [10] T. Benoist, F. Laburthe and B. Rottembourg, “Lagrange Relaxation and Constraint Programming Collaborative Schemes for Traveling Tournament Problems,” International Workshop on Integration of AI and OR Techniques, Ashford, Kent, 2001. [11] K. Easton, G. Nemhauser and M. Trick, “Solving the Traveling Tournament Problem: A Combined Integer Programming and Constraint Programming Approach,” Lecture Notes in Computer Science, Vol. 2740, 2003, pp. 100-109. doi:10.1007/978-3-540-45157-0_6 [12] J. H. Lee, Y. H. Lee and Y. H. Lee, “Mathematical Modeling and Tabu Search Heuristic for the Traveling Tournament Problem,” Lecture Notes in Computer Science, Vol. 3982, 2006, pp. 875-884. doi:10.1007/11751595_92 [13] K. K. H. Cheung, “Solving Mirrored Traveling Tournament Problem Benchmark Instances with Eight Teams,” Discrete Optimization, Vol. 5, No. 1, 2008, pp. 138-143. doi:10.1016/j.disopt.2007.11.003 [14] N. Fujiwara, S. Imahori, T. Matsui and R. Miyashiro, “Constructive Algorithms for the Constant Distance Traveling Tournament Problem,” The International Series of Conferences on the Practice and Theory of Automated Timetabling, 2006, pp. 402-405. [15] L. D. Gaspero and A. Schaerf, “A Composite-Neighbor- hood Tabu Search Approach to the Traveling Tournament Problem,” Heuristics, Vol. 13, No. 2, 2007, pp. 189-207. doi:10.1007/s10732-006-9007-x [16] S. Urrutia and C. C. Ribeiro, “Maximizing Breaks and Bounding Solutions to the Mirrored Traveling Tournament Problem,” Discrete Applied Mathematics, Vol. 154, No. 13, 2006, pp. 1932-1938. doi:10.1016/j.dam.2006.03.030 [17] M. A. Trick, “Michael Trick’s Guide to Sports Scheduling”. http://mat.gsia.cmu.edu/TOURN/ [18] D. T. Connelly, “General Purpose Simulated Annealing,” Journal of Operations Research, Vol. 43, 1992, pp. 495- 505. [19] R. Lewis and J. Thompson, “On the Application of Graph Coloring Techniques in Round-Robin Sports Scheduling,” Computers and Operations Research, Vol. 38, No. 1, 2011, pp. 190-204. doi:10.1016/j.cor.2010.04.012 [20] J. Kennedy and R. C. Eberhart, “A Discrete Binary Version of the Particle Swarm Algorithm,” World Multiconference on Systemics, Cybernetics and Informatics, Piscatawary, 1997, pp. 4104-4109. [21] A. Lim, B. Rodrigues and X. Zhang, “A Simulated Annealing and Hill-Climbing Algorithm for the Traveling Tournament Problem,” European Journal of Operational Research, Vol. 174, 2006, pp. 1459-1478. doi:10.1016/j.ejor.2005.02.065 [22] M. B. Wright, “Scheduling Fixtures for Basketball New Zealand,” Computers & Operations Research, Vol. 33, No. 7, 2006, pp. 1875-1893. doi:10.1016/j.cor.2004.09.024