Reliable communication network design: The hybridisation of metaheuristics with the branch and bound method

Reliable communication network design (RCND) is a well-known optimisation problem to produce a network with maximum reliability. This paper addresses the minimum cost communication network design problem under the all-terminal reliability constraint. Due to the NP-hard nature of RCND, several different metaheuristic algorithms have been widely applied to solve this problem. The aim of this paper is to propose two new hybrid metaheuristic algorithms, namely, GABB and SABB, by integrating either a Genetic Algorithm (GA) with the Branch and Bound method (B&B) or Simulated Annealing (SA) with B&B. The GABB and SABB algorithms have the advantages of finding higher performance solutions produced from the GA or SA, along with the ability to repair infeasible solutions or improve solution quality by integrating the B&B method. To investigate the effectiveness of the proposed algorithms, extensive comparisons with individual application of the GA and SA (the basic forms of GABB and SABB), two different hybrid algorithms (GABB and SABB) and other two approaches (ACO_SA and STH) that give the best results in the literature for the design problems are carried out in a three-stage experimental study (ie, small-, medium-, and large-sized networks). The computational results show that hybridisation of metaheuristics with the B&B method is an effective approach to designing reliable networks and finding better solutions for existing problems in the literature.