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: | Rubino Gerardo, Robledo-Amoza Franco, Cancela Hector |
Keywords: | networks: flow |
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.