Optimizing Computer Networks Communication with the Band Collocation Problem: A Variable Neighborhood Search Approach

Abstract

The Band Collocation Problem appears in the context of problems for optimizing telecommunication networks with the aim of solving some concerns related to the original Bandpass Problem and to present a more realistic approximation to be solved. This problem is interesting to optimize the cost of networks with several devices connected, such as networks with several embedded systems transmitting information among them. Despite the real-world applications of this problem, it has been mostly ignored from a heuristic point of view, with the Simulated Annealing algorithm being the best method found in the literature. In this work, three Variable Neighborhood Search (VNS) variants are presented, as well as three neighborhood structures and a novel optimization based on Least Recently Used cache, which allows the algorithm to perform an efficient evaluation of the objective function. The extensive experimental results section shows the superiority of the proposal with respect to the best previous method found in the state-of-the-art, emerging VNS as the most competitive method to deal with the Band Collocation Problem.