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. |