Novas heurísticas para o problema de geração de escalas de jogos para torneios esportivos - Fabrício Lacerda Biajoli (2007)
O Traveling Tournament Problem (TTP), ou Problema de Gera¸cao de Escala de Jogos para Torneios Esportivos, ´e um problema de otimiza¸cao que trata algumas caracter´ýsticas de torneios esportivos, tendo como objetivo a minimiza¸cao das distancias percorridas pelos times no decorrer da competi¸cao. O presente trabalho apresenta o uso de novas t´ecnicas heur´ýsticas h´ýbridas para a resolu¸cao da versao espelhada do TTP, utilizando um algoritmo evolutivo, chamado Evolutionary Clustering Search (ECS), bem como uma adapta¸cao deste, chamado Clustering Search (*CS), onde a metaheur´ýstica Variable Neighborhood Search (VNS), ser´a utilizada como alternativa ao algoritmo evolutivo empregado no ECS. Apresenta-se ainda, uma modelagem in´edita para o m´etodo evolutivo utilizado atrav´es de uma codifica¸cao gen´etica compacta associada a um algoritmo de expansao de c´odigo que tem por objetivo decodificar cromossomos em escalas de jogos. A valida¸cao dos resultados foi realizada em instancias existentes na literatura e em problemas reais (Campeonato Brasileiro de Futebol). Quando poss´ývel, os resultados apresentados foram comparados com os de outros m´etodos j´a utilizados na literatura.