Defesa de Dissertação Jean Carlos Campos, dia 23/04/2018, as 15:00, sala de seminários DECOM

Defesa 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:
Professor Dr. Marcone Jamilson Freitas Souza (Orientador)
Professor Dr. Alexandre Xavier Martins (Coorientador)
Professor Dr. Haroldo Gambini Santos
Professor Dr. Marco Antônio Moreira de Carvalho
Professor Dr. Mauricio Cardoso de Souza