원문정보
초록
영어
The design of a communication network where the connectivity between nodes must be kept even after failure of some links can be modeled as a Generalized Steiner Problem. It consists of computing the minimal cost subnetwork of a given feasible network where certain pairs of nodes must satisfy a number of disjoint connectivity requirements and is known to be an NP-Complete problem. This paper introduces an heuristic based on the combinatorial optimization metaheuristic “Greedy Randomized Adaptive Search Procedure” (GRASP) to solve the edge-survivable version of the problem, where nodes are perfect but links can fail. The algorithm is tested with a set of heterogeneous network topologies and connectivity requirements obtaining promising results; in all cases with known optimal cost, optimal or near-optimal solutions are found.
목차
1. Introduction
2. Definitions and Formalization
3. A GRASP Heuristic
3.1. Construction Phase Algorithm
3.2. Local Search Phase Algorithm
3.3. The Bundled GRASP Algorithm
4. Performance Tests
4.1. Test Set Description
4.2. Numerical Results
5. Conclusions
Appendix