
The Automatic Frequency Planning Problem



Description:
In GSM (Global System for Mobile Communications) networks the basic communication structure includes
a set of base stations (BTS or Base Transceiver Station) located at several sites. Each BTS may have installed either
an omnidirectional antenna or several directional antennae called sectors (Figure 1). Devices which allow
the transmission of radio signals are usually calles transceivers (TRX). Typically, each TRX has to be assigned with a frequency which carry the radio signal.
In general, the number of BTSs and, consequently, the number of TRXs needed to
cover large areas, is much higher than the total number of available frequencies.
Efficiently reusing these frequencies is, therefore, essential.
Reusing generally provokes a reduction in the network performance due to interferences between TRXs. Two basic kinds of interferences
are considered in the frequency planning: cochannel interferences, produced by TRXs using the
same frequency, and adjacent channel, when TRXs operate with adjacent frequencies.
Therefore, the problem relies in assigning the limited spectrum of frequencies available to all TRXs of the GSM network in order to maximize its performance, or,
what is the same, minimize interferences. The input data include the network topology as well as the potential interferences between each pair of TRXs.
Complexity
NPhard (generalization of graph colouring).

Figure 1: GSM network




New Results 2016:
Denver Results:
Date 
Score 
Reference 
2007 
88345 
LUNA07 
2008 
86908 
LUNA08a 
2008 
84234.5 
CHAV08a 
2008 
83991.8 
LUNA08b 
2011 
83815.7 
CHAV11 
2011 
83725.6 
SEGR11 
2013 
83340 
SEGU13 
2015 
83280 
SEGR14 
2016 
82994.9 
SEGR16 
Seattle Results:
Date 
Score 
Reference 
2009 
18123 
MAXI09 
2010 
654.5 
SEGU10 
2011 
564 
SEGR11 
2011 
456 
CHAV11 
2016 
349.3 
SEGR16 
Resources:
Download source code here
Download instances here



Basic Articles on the AFP Problem:
[SEGR16] Carlos Segura ; Arturo Hernandez ; Francisco Luna ; Enrique Alba. Improving Diversity in Evolutionary Algorithms: New Best Solutions for Frequency Assignment in IEEE Transactions on Evolutionary Computation , vol.PP, no.99, pp.11, 2016. Doi: 10.1109/TEVC.2016.2641477
[ALB2008] E. Alba, F. Luna, A.J. Nebro (2008), Applying Evolutionary Algorithms to Solve the
Automatic Frequency Planning in GSM Networks, Handbook of Applied Algorithms
[LUN2007a] Francisco Luna, Christian Blum, Enrique Alba, Antonio J. Nebro: ACO vs EAs for solving a realworld frequency assignment problem in GSM networks. GECCO 2007: 94101
[LUN2007b] Francisco Luna, Enrique Alba, Antonio J. Nebro, Salvador Pedraza: Evolutionary Algorithms for RealWorld Instances of the Automatic Frequency Planning Problem in GSM Networks. EvoCOP 2007: 108120
Click here to get the bibliography in txt format.



Last Updated: 30/06/06
For any question or suggestion, click here to contact with us.


