Multi-Neighborhood simulated annealing for the minimum interference frequency assignment problem

Abstract

We consider the Minimum Interference Frequency Assignment Problem and we propose a novel Simulated Annealing approach that makes use of a portfolio of different neighborhoods, specifically designed for this problem.We undertake at once the two versions of the problem proposed by Correia (2001) and by Montemanni et al. (2001), respectively, and the corresponding benchmark instances. With the aim of determining the best configuration of the solver for the specific version of the problem we perform a comprehensive and statistically-principled tuning procedure.Even tough a totally precise comparison is not possible, the experimental analysis show that we outperform all previous results on most instances for the first version of the problem, and we are at the same level of the best ones for the second version.As a byproduct of this research, we designed a new robust file format for instances and solutions, and a data repository for validating and maintaining the available solutions.

Keywords

• Frequency assignment
• Neighborhood search
• Simulated annealing
• Parameter tuning