Limites para o Problema do Torneio com Viagens
Autores
|
6712 |
3006,539
|
|
|
6713 |
3006,539
|
Informações:
Publicações do PESC
O problema do torneio com viagens (TTP, do inglês Traveling Tournament Problem) é um importante problema da área de agendamento esportivo. Dados n times e as distâncias entre os estádios dos times, o TTP consiste em encontrar um torneio com 2(n-1) rodadas onde cada time deve jogar n-1 rodadas em casa e deve viajar nas outras n-1 rodadas para enfrentar cada um de seus rivais. A distância percorrida por todos os times deve ser mínima. Este trabalho consiste na implementação de um algoritmo de geração de colunas para o TTP e como contribuições originais dois algoritmos de pricing são propostos. Estes algoritmos são adaptados do problema de roteamento de veículos capacitado (CVRP). Duas técnicas de estabilização para a geração de colunas também foram implementadas: uma baseada na ideia de box de estabilidade e a outra utiliza combinações convexas das soluções duais obtidas. Por fim, uma heurística de pricing e uma metaheurística ILS (Iterated Local Search - Busca Local Iterada) foram propostas. Os novos algoritmos de pricing propostos permitiram a execução da geração de colunas para as instâncias do problema com tamanho de até n = 24 times. Os limites inferiores encontrados eram mais fracos em comparação com os conhecidos, porém foram obtidos de forma mais rápida.
The traveling tournament problem (TTP) is a important problem in sports scheduling. Given n teams and the distances between the team's venues, the TTP consists in finding a tournament with 2(n - 1) rounds where each team must play n - 1 rounds at his home venue and must travel to each of its rivals venues in the other n - 1 rounds. The distance traveled by all teams must be minimum. This work consists on a column generation algorithm to the TTP and as original contributions two pricing algorithms are proposed. These algorithms are adapted from the capacitated vehicle routing problem (CVRP). Two stabilization techniques for column generation were also implemented: one based on the idea of stability box and the other uses convex combinations of the obtained dual solutions. Finally, a pricing heuristic and an ILS metaheuristic were proposed. The new pricing algorithms proposed allowed running the column generation for instances with size up to n = 24 teams. The lower bounds found were weaker compared to those previously known, but were obtained more quickly.