Dithebe, Keletso2021-04-262021-04-262020Dithebe, Keletso Kenneth. (2020). A comparative study of different Meta-Heuristic methods for scheduling the CAF champions league, University of the Witwatersrand, https://hdl.handle.net/10539/31008https://hdl.handle.net/10539/31008A thesis submitted in fulfilment of the requirements for the degree of Masters of Science, Faculty of Science, School of Computer Science and Applied Mathematics, University of the Witwatersrand, 2020The Confederation of African Football (CAF) Champions League, is an annual continental football tournament organised by CAF. The CAF Champions League has the capacity to feature 68 African teams, but on average only 57 teams participate in this league. Some of the reasons for teams and their affiliated football associations not participating, include excessive travel costs. In this dissertation, we highlight and tackle two problems which arise when generating fixtures for the CAF Champions League. These include the scheduling of football matches such that the total distance travelled by teams and match officials is minimized. These problems can be formulated as constrained optimization problems, where the constraints are dictated by the Confederation of African Football and other relevant stakeholders. We carry out a comparative study of the performance of three meta-heuristic methods, to solve the constrained problem. The methods under consideration are the Genetic Algorithm, Tabu search and Simulated Annealing. We then compare the results of the best performing meta-heuristic with that of existing CAF Champions League schedulesOnline resource (xi, 114 leaves)enHeuristic programmingCombinatorial optimization.Thesis