Formulações para problemas de agendamento de competições esportivas.

Abstract

Encontrar um calendário para competições esportivas é uma tarefa de grande importância econômica, pois as diversas viagens realizadas pelas equipes geram altos gastos de transporte e desgaste dos atletas. O Traveling Tournament Problem (TTP) é um problema de otimização combinatória da classe dos NP-difíceis que visa encontrar o melhor calendário para competições esportivas reduzindo a distância total viajada pelas equipes. Neste trabalho propõe-se uma formulação para minimizar os custos levando-se em conta as variações do TTP para problemas Double Round Robin, Double Round Robin Unrestricted e Double Round Robin Mirrored. O modelo é baseado em conjuntos independentes de grafos de conflitos. Para avaliar as formulações foram utilizados dados de problemas reais bem conhecidos da literatura obtidos no Challenge Traveling Tournament Instances. Através dos experimentos computacionais pôde-se observar que métodos exatos são capazes de solucionar apenas instâncias do problema com poucos times. Para quatro times a solução ótima é encontrada em poucos segundos, para seis e oito times soluções sub-ótimas podem ser encontradas em uma hora,e para dez ou mais times solução alguma é encontrada em uma hora. Assim,concluiu-se que métodos exatos ainda não são eficientes o suficiente para solucionar a maioria das instâncias desse problema.