Use este identificador para citar ou linkar para este item:
https://repositorio.ufms.br/handle/123456789/4242
Registro completo de metadados
Campo DC | Valor | Idioma |
---|---|---|
dc.creator | CECÃ LIA LESCANO OSORIO | - |
dc.date.accessioned | 2021-12-30T02:40:36Z | - |
dc.date.available | 2021-12-30T02:40:36Z | - |
dc.date.issued | 2021 | pt_BR |
dc.identifier.uri | https://repositorio.ufms.br/handle/123456789/4242 | - |
dc.description.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. | - |
dc.language.iso | pt_BR | pt_BR |
dc.publisher | Fundação Universidade Federal de Mato Grosso do Sul | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | otimização combinatória, geração de colunas, programação linear inteira | - |
dc.title | Problema de roteamento em anéis de dois níveis | pt_BR |
dc.type | Dissertação | pt_BR |
dc.contributor.advisor1 | Edna Ayako Hoshino | - |
dc.description.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. | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.initials | UFMS | pt_BR |
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.