Uma abordagem evolutiva para o mirrored traveling tournament proble

Disponível somente no TrabalhosFeitos
  • Páginas : 17 (4080 palavras )
  • Download(s) : 0
  • Publicado : 26 de janeiro de 2013
Ler documento completo
Amostra do texto
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 aversã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 NogueiraLorena LAC/INPE lorena@lac.inpe.br
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 dessanatureza 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. Ageraçã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). Nestetrabalho é proposta a aplicação conjunta de técnicas evolutivas e busca local na resolução da versão espelhada do TTP, conhecida como Mirrored Traveling Tournament Problem (mTTP) (Ribeiro & Urrutia, 2004). Este trabalho está organizado em 6 seções, sendo esta a primeira. A seção 2 apresenta a descrição do problema abordado. Na seção 3 é apresentada a metodologia adotada, com as estruturas devizinhança e o algoritmo proposto. Os resultados computacionais serão apresentados na seção 4. E por último, nas seções 5 e 6, serão apresentadas as conclusões a respeito do trabalho desenvolvido e a referências bibliográficas pesquisadas, respectivamente.

1. Introdução
O escalonamento de jogos, ou programação de jogos, vem se tornando nos últimos anos uma das classes mais importantes de problemascombinatórios. Isto porque as ligas esportivas profissionais representam uma das maiores atividades econômicas ao redor do mundo e para muitas delas (tais como futebol, futsal, voleibol, basquetebol, etc), onde os jogos são disputados dois a dois e realizados em vários locais ao longo de um determinado período de tempo, há a necessidade de se fazer um escalonamento desses jogos. Além da necessidadede se escalonar estes jogos alguns fatores fortalecem a aplicação de técnicas de otimização em problemas desta natureza, tais como: times e ligas não querem perder seus investimentos em jogadores e estrutura em conseqüência de escalonamentos mal feitos ou mal organizados; as ligas esportivas representam significantes fontes de renda das redes de rádio e televisão mundial; as escalas interferemdiretamente no desempenho dos times participantes da competição; entre vários outros fatores. Do lado dos estudiosos da Pesquisa Operacional o principal atrativo é que as ligas esportivas geram problemas de otimização extremamente desafiadores. O problema de geração de escalas para torneios esportivos é conhecido na literatura como Traveling

2. O problema abordado
O Traveling Tournament...
tracking img