ALNS com Simulated Annealing e Shortest Path Heuristic para o Problema da Árvore de Steiner Clusterizada
Resumo
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.Referências
Ben-Ameur, W. (2004). Computing the initial temperature of simulated annealing. Computational Optimization and Applications, 29:369–385.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
Hakimi, S. L. (1971). An algorithmic approach to the steiner problem in graphs. Networks, 1(2):113–133.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680.
Kou, L., Markowsky, G., and Berman, L. (1981). A fast algorithm for steiner trees. Acta Informatica, 15(2):141–145.
Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1):48–50.
Long, N. B., Anh, D. T., Ban, H., and Binh, H. T. T. (2024). An online transfer learning based multifactorial evolutionary algorithm for solving the clustered Steiner tree problem. Knowledge-Based Systems, 296:111870.
Pisinger, D. and Ropke, S. (2010). Large neighborhood search. In Gendreau, M. and Potvin, J., editors, Handbook of Metaheuristics, volume 146 of International Series in Operations Research & Management Science, pages 399–419. Springer.
Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6):1389–1401.
Ropke, S. and Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4):455–472.
Takahashi, H. and Matsuyama, A. (1980). An approximate solution for the steiner problem in graphs. Mathematica Japonica, 24:573–577.
Wu, B. Y. and Lin, C. (2015). On the clustered Steiner tree problem. Journal of Combinatorial Optimization, 30(2):370–386.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
Hakimi, S. L. (1971). An algorithmic approach to the steiner problem in graphs. Networks, 1(2):113–133.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680.
Kou, L., Markowsky, G., and Berman, L. (1981). A fast algorithm for steiner trees. Acta Informatica, 15(2):141–145.
Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1):48–50.
Long, N. B., Anh, D. T., Ban, H., and Binh, H. T. T. (2024). An online transfer learning based multifactorial evolutionary algorithm for solving the clustered Steiner tree problem. Knowledge-Based Systems, 296:111870.
Pisinger, D. and Ropke, S. (2010). Large neighborhood search. In Gendreau, M. and Potvin, J., editors, Handbook of Metaheuristics, volume 146 of International Series in Operations Research & Management Science, pages 399–419. Springer.
Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6):1389–1401.
Ropke, S. and Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4):455–472.
Takahashi, H. and Matsuyama, A. (1980). An approximate solution for the steiner problem in graphs. Mathematica Japonica, 24:573–577.
Wu, B. Y. and Lin, C. (2015). On the clustered Steiner tree problem. Journal of Combinatorial Optimization, 30(2):370–386.
Publicado
19/07/2026
Como Citar
GUIMARÃES E SILVA, João Guilherme; RIBEIRO, Alexandre.
ALNS com Simulated Annealing e Shortest Path Heuristic para o Problema da Árvore de Steiner Clusterizada. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 26-30.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.22127.
