A comparison of local search algorithms for radio link frequency assignment problems

Abstract

The frequency assignment problem, known to be NPcomplete, is to find an assignment of radio frequencies to a set of transmitters in a region. The interference level between the frequencies assigned to different communication links has to be acceptable, since otherwise communication will be distorted. Consequently, constraints are defined on pairs of links that limit the choice of frequencies for these pairs. Usually, a fixed number of frequency channels are available with which to make an assignment. The aim is to produce an assignment which minimizes the number of constraint violations. This paper compares the results obtained from using simulated annealing, genetic algorithms and tabu search for determining such an assignment. We report on our computational experiments in terms of the quality of the solutions obtained for realistic, computer-generated problem instances.