Solving the Steiner Two-Node-Survivable Network Problem

Solving the Steiner Two-Node-Survivable Network Problem

0.00 Avg rating0 Votes
Article ID: iaor2010314
Volume: 6
Issue: 2
Start Page Number: 218
End Page Number: 234
Publication Date: Jan 2010
Journal: International Journal of Logistics Systems and Management
Authors: , ,
Keywords: networks: flow
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.

Reviews

Required fields are marked *. Your email address will not be published.