An ANT Heuristic for the Frequency Assignment Problem

Vittorio Maniezzo, Dept. of Computer Science, University of Bologna, Cesena, Italy
Email: maniezzo@csr.unibo.it

Antonella Carbonaro, Dept. of Computer Science, University of Bologna, Cesena, Italy

The introduction of mobile computing and communications, such as portable phones and Personal Digital Assistants, will have a tremendous impact on everyday life over the next decades. Mobility raises a number of new research questions: for many of them discrete models and algorithms are required in order to deal with real applications. The ANT metaheuristic has proved successful in dealing with discrete optimization problems, such as travelling salesman, quadratic assignment, graph coloring and others (see http://iridia.ulb.ac.be/dorigo/ACO/ACO.html).

This paper presents its application to one of the main problem arising in mobile telecommunication, namely the frequency assignment problem (FAP, also found under the name of channel assignment problem). In order to check the computational effectiveness of the algorithm we propose, we used as a preliminary benchmark the well-known Celar data set. The Celar data consists of 11 test problems which have been made available in the framework of the European EUCLID project CALMA (Combinatorial ALgorithms for Military Applications) by the French "Centre d'Electronique de l'Armement" (Smith et al., 1995). Besides ANT, we also implemented two of the most effective heuristics so far presented for FAP: a tabu search, defined adapting (Adjakpl, Jaumard, 1997) and DSATUR, adapted from (Borndörfer et al., 1997). Preliminary computational results testify the effectiveness of the ANT approach.