PPGCC - Programa de Pós-graduação em Ciência da Computação

URI permanente desta comunidadehttp://www.hml.repositorio.ufop.br/handle/123456789/596

Navegar

Filtros

20181

Configurações

Autor: search.filters.author.Campos, Jean Carlos TiburcioAssunto: search.filters.subject.Otimização combinatória

Resultados da Pesquisa

Agora exibindo 1 - 1 de 1
  • Nenhuma Miniatura Disponível
    Item
    Um modelo reforçado e heurísticas relax-and-fix e VNS para o Problema da Árvore Geradora Mínima Capacitada em Níveis.
    (2018) Campos, Jean Carlos Tiburcio; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Souza, Marcone Jamilson Freitas; Martins, Alexandre Xavier; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Souza, Maurício Cardoso de
    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.