Defesa de Dissertação Jean Carlos Campos, dia 23/04/2018, as 15:00, sala de seminários DECOMDefesa de Dissertação Jean Carlos Campos, dia 23/04/2018, as 15:00, sala de seminários DECOM Título: Um novo modelo e uma heurística relax-and-fix, baseada em VNS, para o Problema da Árvore Geradora Mínima Capacitada em Níveis Resumo: Este trabalho tem seu foco no Problema da Árvore Geradora Mínima Capacitada em Níveis (PAGMCN). Ele consiste em encontrar uma árvore geradora de custo mínimo, tal que o fluxo a ser transferido de um nó central aos demais nós seja limitado pela capacidade das arestas. Para resolvê-lo, propomos neste trabalho uma nova formulação de programação matemática e um algoritmo híbrido, combinando as heurísticas relax-and-fix e Variable Neighborhood Search (VNS), juntamente com um modelo matemático. A formulação matemática proposta, chamada "Modelo Baseado na Capacidade das Facilidades 2" (MBC2), é baseada na formulação considerada a mais eficiente da literatura. A motivação para a utilização do modelo MBC2 está em fornecer um limite inferior de qualidade, esperando assim convergir mais rapidamente à solução ótima. Experimentos computacionais mostraram que a formulação proposta, quando comparado ao modelo da literatura, melhora a qualidade da relaxação linear, fornecendo assim um limite inferior melhor e justificando a sua utilização. Para o desenvolvimento do algoritmo híbrido, foi utilizado o modelo MBC2 proposto neste trabalho, em razão de ser capaz de proporcionar um limite inferior de qualidade. A formulação é usada com a heurística relax-and-fix para fornecer uma solução inicial para o VNS. Resultados mostram que o VNS melhora a solução inicial e gera soluções com gaps relativamente pequenos nas instâncias usadas para teste. Banca: |
Departamento de Computação | ICEB | Universidade Federal de Ouro Preto
Campus Universitário Morro do Cruzeiro | CEP 35400-000 | Ouro Preto - MG, Brasil
Telefone: +55 31 3559-1692 | decom@ufop.edu.br