Abordagens baseadas em coloração de arestas para problemas de programação de tabelas esportivas

Abstract

Sport scheduling is a trending research topic in operations research. Local search heuristics are among the most effective methods to construct schedules. Prior studies have noted the existance of non-connectivity in neighborhoods used in local search heuristics for single round-robin tournament scheduling. This non-connectivity affects the performance of local search heuristics. It is well-known that graphs are useful tools for modeling relevant parts of reality. A contribution from this thesis is the modeling of the existing neighborhood structures in edge coloring terms. This thesis presents empirical and theoretical evidences relating the nonconnectivity of the neighborhood structures with the perfect riffle shuffle permutations of a deck of playing cards (faro shuffle). It is proved that, when the faro shuffle permutation has an (n 2)-cycle, the neighborhood is not connected and it does not allow the search to escape from schedules isomorphic to the initial one. A new constructive method based on the faro shuffle of playing cards (faro method) is presented. The faro method is used in the analysis of neighborhood connectivity of one of the existing neighborhood structures. This thesis introduces a novel neighborhood structure for single round-robin sport scheduling problems. The neighborhood structure is described in edge coloring terms and its correctness is proven. We show that the new neighborhood structure increases the connectivity of the solution space and evaluate its performance using the Traveling Tournament Problem with Predefined Venues and the Weighted Carry-Over Effects Value Minimization Problem as case studies.