A Weighting Local Search for the Network Topology Design Problem  
Author Taishin Nakamura

 
Co-Author(s) Koji Shingyochi

 
Abstract Network topology design plays a crucial role in the efficacy, reliability, and cost-effectiveness of communication networks. The network topology design with minimum cost subject to a reliability constraint (NTD-CR) problem aims to find a network that minimizes total costs while satisfying all-terminal reliability constraints. This study aims to solve the NTD-CR problem using a weighting local search (WLS) algorithm that combines a weighting function with a dynamic penalty coefficient update strategy to efficiently explore the solution space. The WLS algorithm seeks to strike a balance between exploration and exploitation, thereby improving its overall performance. Numerical experiments demonstrate that the WLS algorithm outperforms the simulated annealing algorithm, which is comparable to the efficient hybridized algorithm for small networks, in terms of performance. For small instances, the algorithm can obtain exact solutions in several cases, whereas for moderate-sized instances, it tends to achieve better solutions compared with the simulated annealing algorithm. The WLS algorithm can be combined with various optimization algorithms to address complex and largescale network design problems, offering the potential for improved performance, cost-efficiency, reliability, and sustainability in real-world networks.

 
Keywords Network topology design, Weighting Local Search, Optimization, All-terminal reliability
   
    Article #:  RQD28-265
 

Proceedings of 28th ISSAT International Conference on Reliability & Quality in Design
August 3-5, 2023