Artículos de revistas
Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints
Fecha
2008Registro en:
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, v.190, n.1, p.68-78, 2008
0377-2217
10.1016/j.ejor.2007.06.012
Autor
COSTA, Alysson M.
CORDEAU, Jean-Francois
LAPORTE, Gilbert
Institución
Resumen
This article describes and compares three heuristics for a variant of the Steiner tree problem with revenues, which includes budget and hop constraints. First, a greedy method which obtains good approximations in short computational times is proposed. This initial solution is then improved by means of a destroy-and-repair method or a tabu search algorithm. Computational results compare the three methods in terms of accuracy and speed. (C) 2007 Elsevier B.V. All rights reserved.