Sequence-based Selection Hyper-heuristics for Real-World Fibre Network Design Optimisation

In light of increased demand for streaming services, the need for more cost-effective network services is pressing. The telecommunication industry is facing tight budgets and severe competition. Therefore, reducing the cost of designing a fibre network via automation and optimisation has become critical. In order to automate and optimise network designs, British Telecom (BT) have developed a network design software, BT NetDesign, which includes a number of heuristics to search the design space of networks using a simulated annealing (SA) search strategy. Although NetDesign's current SA-based method is able to provide exploration and exploitation via different move heuristics, it cannot consistently reach the near-global optimum as the search space grows exponentially with the size of the network. To deal with larger networks, this study implements sequence-based hyper-heuristics utilising a hidden Markov model (HMM) with different acceptance strategies. The proposed methods have been rigorously analysed and compared using real-world network instances of different sizes. Results showed that HMM with a longer learning period and threshold acceptance strategy has promising ability to reach high quality solutions for large real-world problem instances.