Um modelo reforçado e heurísticas relax-and-fix e VNS para o Problema da Árvore Geradora Mínima Capacitada em Níveis.

Abstract

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 formulação reforçada 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), consiste em adicionar dois novos conjuntos de restrições à formulação considerada a mais e ciente da literatura. A motivação para a utilização do modelo MBC2 está em ele fornecer um limite inferior de qualidade, esperando assim convergir mais rapidamente à solução ótima. Experimentos computacionais mostraram que a formulação reforçada proposta, quando comparada ao modelo da literatura, melhora a qualidade da relaxação linear, fornecendo 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 ele ser capaz de proporcionar um limite inferior de qualidade. Essa formulação reforçada é 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.