Network Design Optimisation Using Two Population-Based Search Strategies

In the pursuit of cost-effective services, the telecommunication industry faces increasing and intense competition, with tight constraints on budgets. The automation and optimisation of network design becomes crucial to minimise the overall cost of service deployment. BT NetDesign is a tool developed by British Telecom (BT) to reduce the capital expenditure of designing a fibre network, using a single-point heuristic search algorithm. Although NetDesign facilitates different exploration and exploitation moves on a single-point search, the utilisation of these moves in the context of a population, enabling the possibility of interaction between multiple individuals in the population, is a potential alternative. To investigate the performance of population-based search algorithms for network design optimisation, this study utilises two population-based search strategies, namely genetic algorithms (GA) and memetic algorithms (MA). These strategies are rigorously evaluated on network instances of different sizes. Experimental results show that GA and MA cannot reach high quality solutions for large networks compared to an existing Simulated Annealing-based hyper-heuristic approach.