Heurística GRASP para o Problema da Floresta de Steiner

Neste trabalho, foi proposta uma heur´ıstica construtiva para resolver o Problema da
Floresta de Steiner (SFP). Experimentos computacionais em instˆancias conhecidas da literatura in-
dicaram que os resultados produzidos pela nossa heur´ıstica construtiva superaram `aqueles obtidos
pelo algoritmo primal-dual estado-da-arte proposto por Agrawal et al. [1995] e implementado por
Ghalami e Grosu [2022]. Adicionalmente, propusemos uma nova heur´ıstica chamada GRASP-SFP,
que aplica a metaheur´ıstica GRASP para resolver o SFP. Experimentos computacionais adicionais
mostraram que o GRASP-SFP, mais especificamente a sua fase de busca local, melhorou significa-
tivamente os resultados obtidos pelo nosso algoritmo construtivo proposto.