Pantheon Institutional repository
Collect, preserve and disseminate digital academic production in all areas of knowledge.
Comprise the assets of the repository, in addition to theses and dissertations at UFRJ, scientific articles, electronic books, book chapters and papers presented at events for teachers, researchers, administrative staff and students of master's and doctoral degrees.
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11422/13549| Type: | Dissertação |
| Title: | Limites para o problema do torneio com viagens |
| Other Titles: | Bounds for the traveling tournament problem |
| Author(s)/Inventor(s): | Nascimento, Victor Hugo Rodrigues do |
| Advisor: | Simonetti, Luidi Gelabert |
| Abstract: | 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. |
| Abstract: | 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. |
| Keywords: | Traveling tournament problem Problema do torneio com viagens Geração de colunas |
| Subject CNPq: | CNPQ::ENGENHARIAS |
| Program: | Programa de Pós-Graduação em Engenharia de Sistemas e Computação |
| Production unit: | Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia |
| Publisher: | Universidade Federal do Rio de Janeiro |
| Issue Date: | Mar-2019 |
| Publisher country: | Brasil |
| Language: | por |
| Right access: | Acesso Aberto |
| Appears in Collections: | Engenharia de Sistemas e Computação |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| VictorHugoRodriguesDoNascimento.pdf | 404.79 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.