Use este identificador para citar ou linkar para este item:
https://repositorio.ufms.br/handle/123456789/4242
Tipo: | Dissertação |
Título: | Problema de roteamento em anéis de dois níveis |
Autor(es): | CECÃ LIA LESCANO OSORIO |
Primeiro orientador: | Edna Ayako Hoshino |
Resumo: | Nesta dissertação de mestrado estudamos o problema do roteamento em anéis de dois níveis, que consiste em, dado um grafo e custos associados às arestas, projetar uma rede hierárquica em dois níveis em que ambos os níveis são anéis. Apresentamos um modelo em programação linear inteira para o problema e propomos um algoritmo exato branch-and-price para resolvê-lo. Uma vez que o modelo proposto faz uso de um número exponencial de variáveis, utilizamos o método da geração de colunas para resolver a relaxação linear do modelo. Propomos também uma relaxação para a geração de colunas e heurísticas para melhorar o desempenho do algoritmo proposto. |
Abstract: | In this dissertation, we study the ring/ring problem, which consists in, given a graph and costs associated to its edges, designing a hierarchical network in two levels, with both levels being rings. We present an integer linear programming model for the problem and propose an exact branch-and-price algorithm to solve it. Since the proposed model uses an exponential number of variables, we use the column generation method to solve the linear relaxation. We also propose a relaxation for the column generation and heuristics to improve the performance of the proposed algorithm. |
Palavras-chave: | otimização combinatória, geração de colunas, programação linear inteira |
País: | Brasil |
Editor: | Fundação Universidade Federal de Mato Grosso do Sul |
Sigla da Instituição: | UFMS |
Tipo de acesso: | Acesso Aberto |
URI: | https://repositorio.ufms.br/handle/123456789/4242 |
Data do documento: | 2021 |
Aparece nas coleções: | Programa de Pós-graduação em Ciência da Computação |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
RRP_Disserta__o-Final.pdf | 478,53 kB | Adobe PDF | ![]() Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.