Network Design Optimisation
Lead Research Organisation:
Queen Mary University of London
Department Name: School of Engineering & Materials Scienc
Abstract
The project will investigate applications for network design, e.g. a town's fibre network. The goal of the project is to explore software solutions to find optimal solutions to a graph problem described in a human readable declarative constraint language. It has two parts.
Design a declarative language for representing constraints on a graph, and the costs of the graph.
Implement a heuristic search engine which combines heuristic search techniques with constraint satisfaction methods to limit the search space. It is expected that the students will work in close collaboration with other researchers, both in QMUL, the University of Leicester and BT University Research.
Design a declarative language for representing constraints on a graph, and the costs of the graph.
Implement a heuristic search engine which combines heuristic search techniques with constraint satisfaction methods to limit the search space. It is expected that the students will work in close collaboration with other researchers, both in QMUL, the University of Leicester and BT University Research.
People |
ORCID iD |
| Jun Chen (Primary Supervisor) | |
| Anil Arpaci (Student) |
Publications
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/S513696/1 | 01/10/2018 | 30/09/2023 | |||
| 2363919 | Studentship | EP/S513696/1 | 02/12/2019 | 30/09/2023 | Anil Arpaci |
| Description | Network planning and optimisation is crucial to reduce the overall cost of network deployment, e.g., a town's fibre network. In order to help network designers to generate optimal network designs, the goal of the project includes the implementation of a heuristic search engine that can traverse in the search space to find better network designs. As a collaborator, British Telecom (BT) shared their current network design software, BT NetDesign, which uses a stochastic search method to find the best solution for the given network design problem. BT NetDesign is based on a single-point selection hyper-heuristic (HH) framework, which is a general-purpose search method. In the BT's HH algorithm, an incumbent solution is modified by atomic move operator (heuristic), which is selected randomly. BT NetDesign provides several move heuristics to find better (low cost) network designs. In the scope of the implementation of heuristic search engine, sequence-based selection feature has been added to improve the current framework. The sequence-based selection feature allows HH algorithm to combine moves to mitigate the possibility of slow progression or getting stuck at local optima. There are many studies in the literature that combine move heuristics to improve the performance of the search algorithm. So, one of combining moves algorithm has been chosen and implemented in the BT NetDesign. Experiments showed that new combining moves algorithm has not improved BT's algorithm in the average performance when using with random selection. In order to increase the effectiveness of move combinations, learning algorithm has been implemented on the move selection process. The results of experiments showed that the learning algorithm with combining moves has improved BT's algorithm, as the learning algorithm can generate move combinations that are more capable of leading the search algorithm to find better solutions. When we applied our algorithm on network design optimisation problem in two different real-world instances, new algorithm was able to reach higher quality solutions than BT's algorithm. In the first network instance, the average cost is improved by £50.34 with the narrowest variance. In the second network instance, new algorithm ended up with the narrowest variance that is statistically significant (95% confidence level), and the average cost is improved by £61.69. These results show that the new algorithm has less variance, finding higher quality solutions on a more consistent basis. Detailed results can be found in the publication. This research contributes to our understanding of move combinations in search methods, which increases the harmony between moves to maximise the efficiency of the search. Moreover, the result opened up new research areas in our heuristic engine implementation goal. Different learning algorithms can be employed in move heuristic selection and their performance and internal dynamics can be rigorously analysed for network design optimisation problem with various network instances. |
| Exploitation Route | It may help companies in many different industries to design their operation network, ranging from retailers' supply chains to water or energy providers' physical networks. The new heuristic search framework can be utilised to find better network designs. |
| Sectors | Digital/Communication/Information Technologies (including Software) |