Limites para o problema do torneio com viagens

• Ano de defesa: 2019
• Autor(a) principal: Nascimento, Victor Hugo Rodrigues do
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Rio de Janeiro; Brasil; Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia; Programa de Pós-Graduação em Engenharia de Sistemas e Computação; UFRJ
• Palavras-chave em Português: Traveling tournament problem; Problema do torneio com viagens; Geração de colunas; CNPQ::ENGENHARIAS
• Link de acesso: http://hdl.handle.net/11422/13549

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.