Efficient Optimization of Reliable Two‐Node Connected Networks: A Biobjective Approach

This paper presents a biobjective genetic algorithm (GA) to design reliable two‐node connected telecommunication networks. Because the exact calculation of the reliability of a network is NP‐hard, network designers have been reluctant to use network reliability as a design criterion; however, it is clearly an important aspect. Herein, three methods of reliability assessment are developed: an exact reliability calculation method using factoring, an efficient Monte Carlo estimation procedure using the sequential construction technique and network reductions, and an upper bound for the all‐terminal reliability of networks with arbitrary arc reliabilities. These three methods of reliability assessment are used collectively in a biobjective GA with specialized mutation operators that perturb solutions without disturbing two‐node connectivity. Computational experiments show that the proposed approach is tractable and significantly improves upon the results found by single‐objective heuristics.