Skip to main content
Top

2018 | OriginalPaper | Chapter

Evolutionary Harmony Search Algorithm for Sport Scheduling Problem

Authors : Meriem Khelifa, Dalila Boughaci, Esma Aïmeur

Published in: Transactions on Computational Collective Intelligence XXX

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, an original enhanced harmony search algorithm (HS-TTP) is proposed for the well-known NP-hard traveling tournament problem (TTP) in sports scheduling. TTP is concerned with finding a tournament schedule that minimizes the total distances traveled by the teams. TTP is well-known, and an important problem within the collective sports communities since a poor optimization in TTP can cause heavy losses in the budget of managing the league’s competition. In order to apply HS to TTP, we use a largest-order-value rule to transform harmonies from real vectors to abstract schedules. We introduce a new heuristic for rearranging the scheduled rounds which give us a significant enhancement in the quality of the solutions. Further, we use a local search as a subroutine in HS to improve its intensification mechanism. The overall method (HS-TTP) is evaluated on publicly available standard benchmarks and compared with the state-of-the-art techniques. Our approach succeeds in finding optimal solutions for several instances. For the other instances, the general deviation from optimality is equal to 4.45%. HS-TTP is able to produce high-quality results compared to existing methods.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
2.
go back to reference Anagnostopoulos, A., Michel, L., Hentenryck, P.V., Vergados, Y.: A simulated annealing approach to the traveling tournament problem. J. Sched. 9(2), 177–193 (2006)CrossRef Anagnostopoulos, A., Michel, L., Hentenryck, P.V., Vergados, Y.: A simulated annealing approach to the traveling tournament problem. J. Sched. 9(2), 177–193 (2006)CrossRef
3.
4.
go back to reference Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6(2), 154–160 (1994)CrossRef Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6(2), 154–160 (1994)CrossRef
6.
go back to reference Cáceres, L.P., Riff, M.C.: AISTTP: an artificial immune algorithm to solve traveling tournament problems. Int. J. Comput. Intell. Appl. 11(01), 1250008 (2012)CrossRef Cáceres, L.P., Riff, M.C.: AISTTP: an artificial immune algorithm to solve traveling tournament problems. Int. J. Comput. Intell. Appl. 11(01), 1250008 (2012)CrossRef
7.
go back to reference de Carvalho, M.A.M., Lorena, L.A.N.: New models for the mirrored traveling tournament problem. Comput. Ind. Eng. 63(4), 1089–1095 (2012)CrossRef de Carvalho, M.A.M., Lorena, L.A.N.: New models for the mirrored traveling tournament problem. Comput. Ind. Eng. 63(4), 1089–1095 (2012)CrossRef
8.
go back to reference Chen, P.C., Kendall, G., Berghe, G.V.: An ant based hyper-heuristic for the travelling tournament problem. In: IEEE Symposium on Computational Intelligence in Scheduling, SCIS 2007, pp. 19–26. IEEE (2007) Chen, P.C., Kendall, G., Berghe, G.V.: An ant based hyper-heuristic for the travelling tournament problem. In: IEEE Symposium on Computational Intelligence in Scheduling, SCIS 2007, pp. 19–26. IEEE (2007)
9.
go back to reference Choubey, N.S.: A novel encoding scheme for traveling tournament problem using genetic algorithm. IJCA 2(7), 79–82 (2010). Special Issue on Evolutionary ComputationCrossRef Choubey, N.S.: A novel encoding scheme for traveling tournament problem using genetic algorithm. IJCA 2(7), 79–82 (2010). Special Issue on Evolutionary ComputationCrossRef
10.
go back to reference Costa, F.N., Urrutia, S., Ribeiro, C.C.: An ils heuristic for the traveling tournament problem with predefined venues. Ann. Oper. Res. 194(1), 137–150 (2012)MathSciNetCrossRef Costa, F.N., Urrutia, S., Ribeiro, C.C.: An ils heuristic for the traveling tournament problem with predefined venues. Ann. Oper. Res. 194(1), 137–150 (2012)MathSciNetCrossRef
11.
go back to reference Di Gaspero, L., Schaerf, A.: A composite-neighborhood tabu search approach to the traveling tournament problem. J. Heuristics 13(2), 189–207 (2007)CrossRef Di Gaspero, L., Schaerf, A.: A composite-neighborhood tabu search approach to the traveling tournament problem. J. Heuristics 13(2), 189–207 (2007)CrossRef
13.
go back to reference Gao, K.Z., Suganthan, P.N., Pan, Q.K., Chua, T.J., Cai, T.X., Chong, C.S.: Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives. J. Intell. Manuf. 27(2), 363–374 (2016)CrossRef Gao, K.Z., Suganthan, P.N., Pan, Q.K., Chua, T.J., Cai, T.X., Chong, C.S.: Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives. J. Intell. Manuf. 27(2), 363–374 (2016)CrossRef
16.
go back to reference Geem, Z.W., Kim, J.H., Loganathan, G.: A new heuristic optimization algorithm: harmony search. Simulation 76(2), 60–68 (2001)CrossRef Geem, Z.W., Kim, J.H., Loganathan, G.: A new heuristic optimization algorithm: harmony search. Simulation 76(2), 60–68 (2001)CrossRef
17.
go back to reference Geem, Z.W., Yoon, Y.: Harmony search optimization of renewable energy charging with energy storage system. Int. J. Electr. Power Energy Syst. 86, 120–126 (2017)CrossRef Geem, Z.W., Yoon, Y.: Harmony search optimization of renewable energy charging with energy storage system. Int. J. Electr. Power Energy Syst. 86, 120–126 (2017)CrossRef
19.
go back to reference Hansen, P., Mladenović, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130(3), 449–467 (2001)MathSciNetCrossRef Hansen, P., Mladenović, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130(3), 449–467 (2001)MathSciNetCrossRef
20.
go back to reference Imahori, S., Matsui, T., Miyashiro, R.: A 2.75-approximation algorithm for the unconstrained traveling tournament problem. Ann. Oper. Res. 218(1), 237–247 (2014)MathSciNetCrossRef Imahori, S., Matsui, T., Miyashiro, R.: A 2.75-approximation algorithm for the unconstrained traveling tournament problem. Ann. Oper. Res. 218(1), 237–247 (2014)MathSciNetCrossRef
21.
go back to reference Irnich, S.: A new branch-and-price algorithm for the traveling tournament problem. Eur. J. Oper. Res. 204(2), 218–228 (2010)MathSciNetCrossRef Irnich, S.: A new branch-and-price algorithm for the traveling tournament problem. Eur. J. Oper. Res. 204(2), 218–228 (2010)MathSciNetCrossRef
22.
go back to reference Januario, T., Urrutia, S., Ribeiro, C.C., De Werra, D.: Edge coloring: a natural model for sports scheduling. Eur. J. Oper. Res. 254(1), 1–8 (2016)MathSciNetCrossRef Januario, T., Urrutia, S., Ribeiro, C.C., De Werra, D.: Edge coloring: a natural model for sports scheduling. Eur. J. Oper. Res. 254(1), 1–8 (2016)MathSciNetCrossRef
23.
go back to reference Kendall, G., Knust, S., Ribeiro, C.C., Urrutia, S.: Scheduling in sports: an annotated bibliography. Comput. Oper. Res. 37(1), 1–19 (2010)MathSciNetCrossRef Kendall, G., Knust, S., Ribeiro, C.C., Urrutia, S.: Scheduling in sports: an annotated bibliography. Comput. Oper. Res. 37(1), 1–19 (2010)MathSciNetCrossRef
24.
go back to reference Khelifa, M., Boughaci, D.: A variable neighborhood search method for solving the traveling tournaments problem. Electron. Notes Discret. Math. 47, 157–164 (2015)MathSciNetCrossRef Khelifa, M., Boughaci, D.: A variable neighborhood search method for solving the traveling tournaments problem. Electron. Notes Discret. Math. 47, 157–164 (2015)MathSciNetCrossRef
25.
26.
go back to reference Laporte, G.: The traveling salesman problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2), 231–247 (1992)MathSciNetCrossRef Laporte, G.: The traveling salesman problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res. 59(2), 231–247 (1992)MathSciNetCrossRef
27.
go back to reference Lim, A., Rodrigues, B., Zhang, X.: A simulated annealing and hill-climbing algorithm for the traveling tournament problem. Eur. J. Oper. Res. 174(3), 1459–1478 (2006)MathSciNetCrossRef Lim, A., Rodrigues, B., Zhang, X.: A simulated annealing and hill-climbing algorithm for the traveling tournament problem. Eur. J. Oper. Res. 174(3), 1459–1478 (2006)MathSciNetCrossRef
28.
go back to reference Mahdavi, M., Fesanghary, M., Damangir, E.: An improved harmony search algorithm for solving optimization problems. Appl. Math. Comput. 188(2), 1567–1579 (2007)MathSciNetMATH Mahdavi, M., Fesanghary, M., Damangir, E.: An improved harmony search algorithm for solving optimization problems. Appl. Math. Comput. 188(2), 1567–1579 (2007)MathSciNetMATH
29.
go back to reference Marković, D., Petrović, G., Ćojbašić, Ž., Marinković, D.: A comparative analysis of metaheuristic maintenance optimization of refuse collection vehicles using the Taguchi experimental design. Trans. FAMENA 36(4), 25–38 (2013) Marković, D., Petrović, G., Ćojbašić, Ž., Marinković, D.: A comparative analysis of metaheuristic maintenance optimization of refuse collection vehicles using the Taguchi experimental design. Trans. FAMENA 36(4), 25–38 (2013)
31.
go back to reference Qian, B., Wang, L., Hu, R., Huang, D., Wang, X.: A DE-based approach to no-wait flow-shop scheduling. Comput. Ind. Eng. 57(3), 787–805 (2009)CrossRef Qian, B., Wang, L., Hu, R., Huang, D., Wang, X.: A DE-based approach to no-wait flow-shop scheduling. Comput. Ind. Eng. 57(3), 787–805 (2009)CrossRef
32.
go back to reference Rasmussen, R.V., Trick, M.A.: The timetable constrained distance minimization problem. Ann. Oper. Res. 171(1), 45 (2009)MathSciNetCrossRef Rasmussen, R.V., Trick, M.A.: The timetable constrained distance minimization problem. Ann. Oper. Res. 171(1), 45 (2009)MathSciNetCrossRef
33.
go back to reference Ribeiro, C.C., Urrutia, S.: Heuristics for the mirrored traveling tournament problem. Eur. J. Oper. Res. 179(3), 775–787 (2007)CrossRef Ribeiro, C.C., Urrutia, S.: Heuristics for the mirrored traveling tournament problem. Eur. J. Oper. Res. 179(3), 775–787 (2007)CrossRef
35.
go back to reference Saka, M.: Optimum design of steel sway frames to BS5950 using harmony search algorithm. J. Constr. Steel Res. 65(1), 36–43 (2009)CrossRef Saka, M.: Optimum design of steel sway frames to BS5950 using harmony search algorithm. J. Constr. Steel Res. 65(1), 36–43 (2009)CrossRef
36.
go back to reference Sivasubramani, S., Swarup, K.: Multi-objective harmony search algorithm for optimal power flow problem. Int. J. Electr. Power Energy Syst. 33(3), 745–752 (2011)CrossRef Sivasubramani, S., Swarup, K.: Multi-objective harmony search algorithm for optimal power flow problem. Int. J. Electr. Power Energy Syst. 33(3), 745–752 (2011)CrossRef
37.
go back to reference Thielen, C., Westphal, S.: Complexity of the traveling tournament problem. Theor. Comput. Sci. 412(4–5), 345–351 (2011)MathSciNetCrossRef Thielen, C., Westphal, S.: Complexity of the traveling tournament problem. Theor. Comput. Sci. 412(4–5), 345–351 (2011)MathSciNetCrossRef
38.
go back to reference Uthus, D.C., Riddle, P.J., Guesgen, H.W.: An ant colony optimization approach to the traveling tournament problem. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 81–88. ACM (2009) Uthus, D.C., Riddle, P.J., Guesgen, H.W.: An ant colony optimization approach to the traveling tournament problem. In: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, pp. 81–88. ACM (2009)
39.
go back to reference Van Hentenryck, P., Vergados, Y.: Population-based simulated annealing for traveling tournaments. In: Proceedings of the National Conference on Artificial Intelligence, vol. 22, p. 267. MIT Press, Cambridge, London (1999). AAAI Press, Menlo Park (2007) Van Hentenryck, P., Vergados, Y.: Population-based simulated annealing for traveling tournaments. In: Proceedings of the National Conference on Artificial Intelligence, vol. 22, p. 267. MIT Press, Cambridge, London (1999). AAAI Press, Menlo Park (2007)
40.
go back to reference Wang, C.M., Huang, Y.F.: Self-adaptive harmony search algorithm for optimization. Expert. Syst. Appl. 37(4), 2826–2837 (2010)CrossRef Wang, C.M., Huang, Y.F.: Self-adaptive harmony search algorithm for optimization. Expert. Syst. Appl. 37(4), 2826–2837 (2010)CrossRef
41.
go back to reference Wang, L., Pan, Q.K., Tasgetiren, M.F.: Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms. Expert. Syst. Appl. 37(12), 7929–7936 (2010)CrossRef Wang, L., Pan, Q.K., Tasgetiren, M.F.: Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms. Expert. Syst. Appl. 37(12), 7929–7936 (2010)CrossRef
42.
43.
go back to reference Westphal, S., Noparlik, K.: A 5.875-approximation for the traveling tournament problem. Ann. Oper. Res. 218(1), 347–360 (2014)MathSciNetCrossRef Westphal, S., Noparlik, K.: A 5.875-approximation for the traveling tournament problem. Ann. Oper. Res. 218(1), 347–360 (2014)MathSciNetCrossRef
44.
go back to reference Weyland, D.: A rigorous analysis of the harmony search algorithm: how the research community can be. In: Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends: Advancements and Trends, p. 72 (2012) Weyland, D.: A rigorous analysis of the harmony search algorithm: how the research community can be. In: Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends: Advancements and Trends, p. 72 (2012)
Metadata
Title
Evolutionary Harmony Search Algorithm for Sport Scheduling Problem
Authors
Meriem Khelifa
Dalila Boughaci
Esma Aïmeur
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-99810-7_5

Premium Partner