Title: Solving the Steiner Two-Node-Survivable Network Problem

Authors: Franco Robledo-Amoza, Hector Cancela, Gerardo Rubino

Addresses: Facultad de Ingenieria, Departamento de Investigacion Operativa, Instituto de Computacion, Universidad de la Republica, Uruguay. ' Facultad de Ingenieria, Departamento de Investigacion Operativa, Instituto de Computacion, Universidad de la Republica, Uruguay. ' IRISA, INRIA/Rennes, Campus de Beaulieu, 35042 Rennes Cedex, France

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.

Keywords: 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&D; research and development.

DOI: 10.1504/IJLSM.2010.030962

International Journal of Logistics Systems and Management, 2010 Vol.6 No.2, pp.218 - 234

Published online: 14 Jan 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article