TABU SEARCH FOR FREQUENCY ASSIGNMENT IN MOBILE RADIO NETWORKS

The main goal of the Frequency Assignment Problem in mobile radio netw orks consists of assigning a limited number of frequencies to each rad io cell in a cellular network while minimizing electromagnetic interfe rence due to the reuse of frequencies. This problem, known to be NP-ha rd, is of great importance in practice since better solutions will all ow a telecommunications operator to manage larger cellular networks. T his paper presents a new Tabu Search algorithm for this application. T he algorithm is tested on realistic and large problem instances and co mpared with other methods based on simulated annealing, constraint pro gramming and graph coloring algorithms. Empirical evidence shows that the Tabu algorithm is very competitive by giving the best solutions to the tested instances.