A REDUCED SPACE COMBINED WITH TABU SEARCH FOR SOLVING THE CHANNEL ALLOCATION PROBLEM

Abstract

With the rapid growth of mobile communications, solving the channel assignment problem has now become a new challenge in research. In this paper, we present an efficient technique for solving the Channel Assignment Problem (CAP). We first map a given CAP, P, to a smaller subset P of cells of the network, which actually reduces the search space. This reduction is done using a multi-colouring method. Then the tabu search algorithm is applied to solve the new problem P . This method reduces the computing time drastically. The latter is then used to solve the original problem by using a modified forced assignment with rearrangement (FAR) operation. The proposed method has been tested on well known benchmark problems. Optimal solutions have been obtained with zero blocked calls for all the cases with improved computation time. Furthermore, there are many unused frequencies which can be used for changes in demands