Hybrid Harmony Search Combined with Variable Neighborhood Search for the Traveling Tournament Problem

详细信息    查看全文

• 关键词：Sport scheduling ; Traveling tournament problems ; Variable neighborhood search ; Harmony search
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9875
• 期：1
• 页码：520-530
• 全文大小：475 KB
• 参考文献：1.Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6, 154–160 (1994)CrossRef MATH
  2.Biajoli, F.L., Lorena, L.A.N.: Clustering search approach for the traveling tournament problem. In: Gelbukh, A., Kuri Morales, A.F. (eds.) MICAI 2007. LNCS (LNAI), vol. 4827, pp. 83–93. Springer, Heidelberg (2007)CrossRef
  3.Biajoli, F.L., Lorena, L.A.N.: Mirrored traveling tournament problem: an evolutionary approach. In: Sichman, J.S., Coelho, H., Rezende, S.O. (eds.) IBERAMIA 2006 and SBIA 2006. LNCS (LNAI), vol. 4140, pp. 208–217. Springer, Heidelberg (2006)CrossRef
  4.Carvalho, M.A.M.D., Lorena, L.A.N.: New models for the mirrored traveling tournament problem. Comput. Ind. Eng. 63, 1089–1095 (2012)CrossRef
  5.Challenge Traveling Tournament Problems. http://​mat.​gsia.​cmu.​edu/​TOURN/​
  6.Choubey, N.S.: a novel encoding scheme for traveling tournament problem using genetic algorithm. IJCA Spec. Issue Evol. Comput. 2, 79–82 (2010)
  7.de Werra, D.: Some models of graphs for scheduling sports competitions. Discrete Appl. Math. 21, 47–65 (1988)MathSciNet CrossRef MATH
  8.Easton, K., Nemhauser, G.L., Trick, M.A.: The traveling tournament problem description and benchmarks. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 580–584. Springer, Heidelberg (2001)CrossRef
  9.Gaspero, L.D., Schaerf, A.: A composite-neighborhood tabu search approach to the traveling tournament problem. J. Heuristics 13, 189–207 (2007)CrossRef
  10.Geem, Z.W., Kim, J.H.: A new heuristic optimization algorithm: harmony search. Simulation 76, 60–68 (2001)CrossRef
  11.Guedes, A.C.B., Ribeiro, C.C.: A heuristic for minimizing weighted carry-over effects in round robin tournaments. J. Sched. 14, 655–667 (2011)MathSciNet CrossRef
  12.Gupta, D., Goel, D., Aggarwal, V.: A hybrid biogeography based heuristic for the mirrored traveling tournament problem. In: 2013 Sixth International Conference on Contemporary Computing (IC3), pp. 325–330. IEEE, Noida (2013)
  13.Hansen, P.: Mladenovi, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130, 449–467 (2001)CrossRef MATH
  14.Irnich, S.: A new branch-and-price algorithm for the traveling tournament problem. Eur. J. Oper. Res. 204, 218–228 (2010)MathSciNet CrossRef MATH
  15.Khelifa, M., Boughaci, D.: A variable neighborhood search method for solving the traveling tournaments problem. Electron. Notes Discrete Math. 47, 157–164 (2015)MathSciNet CrossRef MATH
  16.Qian, B., Wang, L., Hu, R., Huang, D.X., Wang, X.: A DE-based approach to no-wait flow-shop scheduling. Comput. Ind. Eng. 57, 787–805 (2009)CrossRef
  17.Rasmussen, R.V., Trick, M.A.: The timetable constrained distance minimization problem. Ann. Oper. Res. 171, 45–59 (2008)MathSciNet CrossRef MATH
  18.Ribeiro, C.C., Urrutia, S.: Heuristics for the mirrored traveling tournament problem. Eur. J. Oper. Res. 179, 775–787 (2007)CrossRef MATH
  19.Thielen, C., Westphal, S.: Complexity of the traveling tournament problem. Theor. Comput. Sci. 412, 345–351 (2011)MathSciNet CrossRef MATH
  20.Westphal, S., Noparlik, K.: A 5.875-approximation for the traveling tournament problem. Ann. Oper. Res. 218, 347–360 (2012)MathSciNet CrossRef MATH
  
• 作者单位：Meriem Khelifa (17)
  Dalila Boughaci (17)
  
  17. LRIA-FEI, Computer Science Department, USTHB, BP 32 El-Alia, 16111, Bab-Ezzouar, Algiers, Algeria
  
• 丛书名：Computational Collective Intelligence
• ISBN：978-3-319-45243-2
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9875

文摘

In this paper, we are interested in the mirrored version of the traveling tournament problem (mTTP) with reversed venues. We propose a new enhanced harmony search combined with a variable neighborhood search (V-HS) for mTTP. We use a largest-order-value rule to transform harmonies from real vectors to abstract schedules. We use also a variable neighborhood search (VNS) as an improvement strategy to enhance the quality of solutions and improve the intensification mechanism of harmony search. The overall method is evaluated on benchmarks and compared with other techniques for mTTP. The numerical results are encouraging and demonstrate the benefits of our approach. The proposed V-HS method succeeds in finding high quality solutions for several considered instances of mTTP.