Uma abordagem evolutiva para o mirrored traveling tournament proble

Anais do V WORCAP, INPE, São José dos Campos, 26 e 27 de Outubro de 2005.

Uma Abordagem Evolutiva para o Mirrored Traveling Tournament Problem
Resumo
O Traveling Tournament Problem é um problema de otimização que abstrai algumas características de torneios esportivos, tendo como objetivo a minimização das distâncias percorridas pelos times no decorrer do torneio. Este trabalho aborda a versão espelhada do TTP, conhecida como Mirrored Traveling Tournament Problem (mTTP). Para tal propõe-se o uso conjunto das técnicas Algoritmos Genéticos e Simulated Annealing. A validação dos resultados será feita a partir de instâncias disponíveis na literatura. Palavras-chave: mirrored traveling tournament problem, sports timetabling, algoritmo genético, simulated annealing.

Luiz Antônio Nogueira Lorena LAC/INPE [e-mail]
Tournament Problem (Trick et al., 2001). Basicamente a tarefa de gerar uma escala de jogos consiste em fazer com que todo time participante da competição confronte no mínimo uma vez todos os outros (condição que varia entre as competições) e que todos os times joguem em todas as rodadas com oponentes diferentes (seja em sua sede ou fora dela). Problemas dessa natureza contêm em geral muitas restrições conflitantes que devem ser satisfeitas e diferentes objetivos a cumprir, como a minimização dos deslocamentos dos times durante o campeonato, realização de apenas uma partida por time e por dia, realização de determinados jogos em estádios e em datas pré-estabelecidas, número mínimo de partidas consecutivas realizadas na sede do time e fora dela, etc. A geração de escalonamentos satisfatórios, respeitando essas condições e objetivos, é um problema muito difícil de ser resolvido. A dificuldade de solução desse problema é atribuída ao grande número de possibilidades a serem analisadas. Para exemplificar a magnitude do espaço de soluções, para uma competição com 20 participantes há 2,9062 × 10130 combinações possíveis (Concílio & Zuben, 2002). Neste