Evaluating simple metaheuristics for the generalized steiner problem

Abstract

This article presents the empirical evaluation of several simple metaheuristics applied to solve the Generalized Steiner Problem (GSP). This problem models the design of high-reliability communication networks, demanding a variable number of independent paths linking each pair of terminal nodes. GSP solutions are built using intermediate nodes for guaranteeing path redundancy, while trying to minimize the design total cost. The GSP is a NP-hard problem, and few algorithms have been proposed to solve it. In this work, we present the resolution of several GSP instances whose optimal solutions are known, using metaheuristic techniques. The comparative analysis shows promising results for some of the studied techniques