Meta-heurísticas para o Problema da Árvore Geradora com Rotulação Mínima e Restrições Orçamentárias

- 326153
Trabalho completo (Oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O Problema da Árvore Geradora com Rotulação Mínima e Restrições Orçamentárias é um problema de conectividade em grafos com arestas rotuladas, cujo objetivo é encontrar uma árvore geradora minimizando o número de rótulos utilizados, respeitando limites sobre a quantidade máxima de arestas permitidas por rótulo. Para sua resolução, foram propostos dois métodos heurísticos baseados nas meta-heurísticas GRASP e BRKGA, além de uma formulação baseada em cortes com um algoritmo de branch-and-cut, utilizada para validar os métodos heurísticos. Os experimentos computacionais demonstraram que o método baseado em GRASP encontrou a solução ótima em todas as instâncias nas quais a formulação convergiu dentro do tempo limite. Também obteve resultados melhores e com desempenho superior ao método baseado em BRKGA.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Instituto Federal da Paraíba
Eixo Temático
  • 12. MH – Metaheurísticas
Palavras-chave
Grafos com arestas rotuladas
Árvores geradoras
GRASP
BRKGA