Methods for Designing Communications Networks with Certain Two-Connected Survivability Constraints

In this paper, we consider the problem of designing a minimum cost communication network subject to certain two-connected survivability constraints. This problem was motivated by work at Bellcore on planning fiber optic communications networks. We introduce heuristics for constructing initial feasible networks, and local improvement heuristics for reducing the cost of existing network designs while preserving a feasible network. This approach is shown to be effective on data from both real-world fiber optic communications network problems and randomly generated problems.