Título: GRASP Com Algoritmos Híbridos Aplicado Ao Problema Da Árvore Geradora De Custo Mínimo Capacitada Em Níveis
Autores: Toscano, Rennan N.; Cabral, Lucídio A. F.; Souza, Marcone J. F.; Ochi, Luiz S.
Resumo: Este artigo propõe um algoritmo híbrido, baseado na metaheurística Greedy Randomized Adaptive Search (GRASP), para obter soluções melhores e reduzir o custo computacional para o problema conhecido como o Problema da Árvore Geradora de Custo Mínimo Capacitada em Níveis (PAGCMCN). Este problema, normalmente encontrado ao se projetar uma rede, consiste em determinar a melhor maneira de se conectar vários terminais a um computador central, de forma a atender suas demandas. As conexões podem envolver diferentes tipos de linhas de transmissão, onde cada tipo possui uma capacidade máxima de transmissão distinta. No algoritmo proposto, o otimizador CPLEX 12.2 é acionado, tanto na fase de construção quanto na de busca local, com vistas a uma exploração mais efetiva do espaço de busca. Os experimentos computacionais mostraram que o algoritmo proposto é bastante competitivo, superando em várias instâncias os resultados da literatura e obtendo resultados muito próximos nas demais.
Palavras-chave: Árvore geradora de custo mínimo capacitada em níveis; GRASP; Projeto de redes
Páginas: 8
Código DOI: 10.21528/CBIC2011-29.2
Artigo em pdf: st_29.2.pdf
Arquivo BibTex: st_29.2.bib