ALNS com Simulated Annealing e Shortest Path Heuristic para o Problema da Árvore de Steiner Clusterizada - Guimarães e Silva, João Guilherme; Ribeiro, Alexandre (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2026.22127, 2026)
Este trabalho aborda o Problema da Árvore de Steiner Clusterizada (CluSteiner), em que os terminais são particionados em clusters e as árvores locais de clusters distintos devem ser disjuntas em vértices. Propõe-se uma meta-heurística de Adaptive Large Neighborhood Search (ALNS) com aceitação por Simulated Annealing (SA) e procedimentos de reparo guiados por caminhos mínimos. A abordagem combina operadores de destruição e reconstrução com verificação explícita de viabilidade para preservar a restrição de disjunção. Os resultados computacionais em instâncias não euclidianas indicam melhorias frente a métodos de referência.