Uma abordagem para o problema da árvore geradora mínima com restrição de diâmetro via metaheurística BRKGA

Abstract

Este trabalho explora abordagens para resolver o problema da Árvore Geradora Mínima com Restrição de Diâmetro (AGMRD), um importante problema de otimização combinatória em teoria dos grafos, que pode ser aplicado a diversos problemas como redes de transporte, abastecimento e energias, além de redes de computadores e internet das coisas (IoT). A proposta do trabalho envolve o desenvolvimento de heurísticas construtivas que, integradas à metaheurística BRKGA (Biased Random-Key Genetic Algorithm), visam gerar soluções de alta qualidade de forma eficiente. Para atingir os objetivos, foram desenvolvidas três heurísticas construtivas. A primeira inicia a construção da solução através de um backbone central, composto por D − 1 vértices. A segunda heurística organiza os vértices em níveis, aproximadamente D/2, a terceira a partir de caminhos mínimos que se conectam ao centro da árvore. Em todas as heurísticas a árvore geradora é criada sem a necessidade de verificação de diâmetro durante sua construção. As heurísticas foram integradas ao framework BRKGA, que começa com uma população inicial gerada aleatoriamente, onde cada indivíduo representa solução viável para o problema. Além das heurísticas construtivas, o trabalho inclui a aplicação de uma heurística de busca local VND (variable neighborhood descent) para refinar as soluções obtidas. Esta busca local é baseada em propriedades e teoremas de grafos, incluindo movimentos como trocas de nós folhas, caracterizando a vizinhança N1 e melhorias entre nós pai e filho no tipo N2. Os algoritmos foram testados em instâncias conhecidas da literatura, com tamanhos variando de 50 a 500 vértices. Os resultados mostraram que as heurísticas propostas, combinadas com o BRKGA, foram capazes de produzir soluções próximas ao ótimo global de maneira consistente.