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.