Solving the Steiner Two-Node-Survivable Network Problem. Issue 2 (15th January 2010)

• Record Type: Journal Article
• Authors: Robledo-Amoza, Franco; Cancela, Hector; Rubino, Gerardo
• Is Part Of: International journal of logistics systems and management. Volume 6:Issue 2(2010)
• Page Start: 218
• Page End: 234
• Publication Date: 2010-01-15
• Subjects: metaheuristics -- topological design -- Steiner two-node-survivable network problem -- STNSNP -- optical fibre networks -- disjoint-paths -- distinguished nodes -- greedy randomised adaptive search procedure -- GRASP -- low-cost topologies -- heuristics -- heterogeneous topologies -- local-optimal solutions -- survivability -- logistics systems -- logistics management -- R&amp -- amp -- D -- research and development; Business logistics -- Periodicals; 658.5005
• Languages: English
• ISSNs: 1742-7967

Abstract

In the design of optical fibre networks, a commonly applied requirement is to ensure the existence of at least two node-disjoint-paths between pairs of distinguished nodes. The problem of finding a topology verifying this restriction is known as the Steiner Two-Node-Survivable Network Problem (denoted by STNSNP), an NP-hard problem. This paper introduces a Greedy Randomised Adaptive Search Procedure (GRASP) for designing low-cost topologies for the STNSNP model. The heuristic was tested over a large problem set containing heterogeneous topologies with different characteristics, including instances with hundreds of nodes. The numerical results were highly satisfactory, accomplishing in all cases good quality local-optimal solutions.