Frequency assignment for cellular mobile systems using a hybrid Tabu search with an adaptive constraint satisfaction technique

摘要

This paper presents a new algorithm for solving the frequency assignment problem in cellular mobile systems. The proposed algorithm is based on a Taboo search starting with a sequential local search method. Instead of using a minimum number of frequencies and reusing them a maximum number of times, our algorithm assembles to maximum the frequencies while avoiding deadlock. This algorithm introduces a powerful sequential local search method to start with an initial solution respecting all constraints, and minimizing the costs of employment. This initial solution is used to construct a global solution by permutation of all frequencies of a constraint link in its frequency domain in order to obtain the smallest maximum frequency used and the overall cost of such a solution. The algorithm reduces both the search space, the order of variables and values and avoids cycles through by the use of a temporary Taboo list. Our approach has been tested on standard benchmark problems called Philadelphia benchmarks of frequency assignment problem. The results obtained are equivalent to those of current methods. Moreover, our approach shows more efficiency in terms of flexibility and autonomy.