Solving the steiner two-node-survivable network problem

In the design of metropolitan optical fiber networks, a commonly applied requirement is to ensure the existence of at least two node-disjoint-paths between pairs of distinguished nodes of the network In this way, when a failure occur in some component of the network (link or node), the network will remain in operational state, i.e. the resulting network is connected The problem of finding a network topology verifying this restriction is known as the Steiner two-node-survivable network problem (denoted by STNSNP) which is NP-Hard. In this work, we introduce a heuristic based on the GRASP (Greedy Randomized Adaptive Search Procedure) methodology for designing low-cost topologies for the STNSNP model. The heuristic was tested over a large testing problem set containing heterogeneous topologies with different characteristics, including instances with hundreds of nodes. The numerical results were highly promising, accomplishing in all cases good quality local-optimal solutions.