Detalhes dos Anais Veja o resumo do trabalho

Publicado no Encontro de Saberes 2017

Evento: II Mostra da Pós-Graduação

Área: CIÊNCIAS EXATAS E DA TERRA

Subárea: Ciência da Computação

Órgão de Fomento: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

Título
Novos modelos e uma heurística relax and fix, baseada em VNS, para o Problema da Árvore Geradora Mínima Capacitada em Níveis
Autores
JEAN CARLOS TIBÚRCIO CAMPOS (Autor)
Marcone Jamilson Freitas Souza (Orientador)
Alexandre Xavier Martins (Co-Orientador)
Resumo
Este trabalho tem seu foco no Problema da Árvore Geradora Mínima Capacitada em Níveis (PAGMCN), conhecido na literatura inglesa como Multi-level Capacitated Minimum Spanning Tree (MLCMST) Problem. 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. O PAGMCN tem aplicações em sistemas logísticos e de telecomunicações. Por ser um problema da classe NP-difícil, ele é normalmente resolvido por meio de técnicas heurísticas. Neste trabalho, propõe-se um algoritmo híbrido, combinando o método Variable Neighborhood Search (VNS) e uma formulação de programação matemática da literatura, acrescida de duas novas restrições, para resolvê-lo. Essa formulação, nomeada MBC2, é baseada na capacidade dos arcos e é usada para fornecer uma solução inicial ao VNS. Cinco estruturas de vizinhança, baseadas em realocações de nós e sub-árvores, foram desenvolvidas para explorar o espaço de busca. Para testar o algoritmo desenvolvido, foram utilizados problemas teste da literatura envolvendo de 21 a 151 nós. Pelos experimentos computacionais realizados, observou-se que a nova formulação melhora a qualidade da relaxação linear e que o algoritmo VNS é capaz de melhorar a solução inicial e gerar soluções com gaps relativamente pequenos em todos os conjuntos de problemas teste.
Voltar Visualizar PDF