|
Abstract : |
This paper presents Tabu FAP, a Tabu Search procedure tailored to a real world application: the Frequency Assignment Problem (FAP) in mobile radio networks engineering. The main goal of the FAP consists in assigning frequencies to each radio cell in a cellular radio network while minimizing electro-magnetic interference due to the re-use of frequencies by adjacent cells. This problem is of great importance both in practice and in theory. In practice, solving this problem efficiently will allow the telecommunications operator to manage larger cellular networks. In theory, the simplification of the FAP is reduced to the graph coloring problem which is known to be NP-complete. Experiments of Tabu FAP on real size FAP instances (up to 300 cells, 30,000 constraints with 30 frequencies) give good results. Comparative studies using the same FAP instances show that Tabu FAP outperforms largely constraint programming (CP) and graph coloring algorithms (GCA) and is comparable to simulated annealing (SA)., |
