Use este identificador para citar o ir al link de este elemento:
http://hdl.handle.net/1843/ESBF-A27MKE
Tipo: | Tese de Doutorado |
Título: | Abordagens baseadas em coloração de arestas para problemas de programação de tabelas esportivas |
Autor(es): | Tiago de Oliveira Januario |
primer Tutor: | Sebastián Alberto Urrutia |
primer miembro del tribunal : | Antonio Alfredo Ferreira Loureiro |
Segundo miembro del tribunal: | Jayme Luiz Szwarcfiter |
Tercer miembro del tribunal: | Jose Elias Claudio Arroyo |
Cuarto miembro del tribunal: | Mauricio Cardoso de Souza |
Quinto miembro del tribunal: | Thiago Ferreira de Noronha |
Resumen: | O planejamento de tabelas esportivas é um tema que vem ganhando espaço na área de pesquisa operacional. Métodos de buscas locais estão entre as técnicas mais eficazes para a construção de tabelas de jogos. Estudos prévios apontam a existência de nãoconectividade nas estruturas de vizinhanças utilizadas na programação de torneios com rodadas simples. Tal característica afeta o desempenho de buscas locais que fazem uso dessas vizinhanças. É sabido que grafos são importantes ferramentas matemáticas usadas na modelagem problemas reais. Uma contribuição desta tese é justamente a modelagem das estruturas de vizinhanças para o problema de programação de tabelas esportivas por meio de coloração de arestas. Esta tese apresenta evidências empíricas e teóricas que relacionam a conectividade de estruturas de vizinhanças com a técnica de embaralhamento perfeito de cartas. Prova-se que, quando a permutação em um embaralhamento possui uma órbita permutacional de tamanho (n 2), uma determinada vizinhança analisada é desconexa, assim as buscas locais baseadas em tal vizinhança não são capazes de obter tabelas de jogos que não sejam isomórficas à tabela inicial. Um novo método construtivo baseado na técnica de embaralhamento perfeito de cartas é apresentado. O método proposto é usado na análise de conectividade de uma das vizinhança estudadas. Por fim, uma nova estrutura de vizinhança para o problema de programação de tabelas esportivas em torneios com rodadas é proposta. Essa estrutura de vizinhança é descrita em termos de coloração de arestas e a sua corretude é provada. Mostramos que a nova estrutura de vizinhança aumenta a conectividade do espaço de soluções. O seu desempenho é avaliado usando o Problema de Torneio com Viagens com Estádios Predefinidos e o Weighted Carry-Over Effects Value Minimization Problem como estudos de caso. |
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. |
Asunto: | Teoria dos grafos Computação |
Idioma: | Inglês |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Institución: | UFMG |
Tipo de acceso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/ESBF-A27MKE |
Fecha del documento: | 12-ago-2015 |
Aparece en las colecciones: | Teses de Doutorado |
archivos asociados a este elemento:
archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
tiago_de_oliveira_januario.pdf | 2.89 MB | Adobe PDF | Visualizar/Abrir |
Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.