Optimization algorithms for large-scale real-world instances of the frequency assignment problem Articles uri icon

authors

  • LUNA, FRANCISCO
  • ESTEBANEZ TASCON, CESAR
  • LEÓN, COROMOTO
  • CHAVES-GONZÁLEZ, JOSÉ MARÍA
  • NEBRO, ANTONIO J.
  • ALER MUR, RICARDO
  • SEGURA, CARLOS
  • VEGA RODRÍGUEZ, MIGUEL ANGEL
  • ALBA, ENRIQUE
  • VALLS FERRAN, JOSE MARIA
  • MIRANDA, GARA
  • GÓMEZ PULIDO, JUAN ANTONIO

publication date

  • May 2011

start page

  • 975

end page

  • 990

issue

  • 5

volume

  • 15

international standard serial number (ISSN)

  • 1432-7643

electronic international standard serial number (EISSN)

  • 1433-7479

abstract

  • Nowadays, mobile communications are experiencing a strong growth, being more and more indispensable. One of the key issues in the design of mobile networks is the frequency assignment problem (FAP). This problem is crucial at present and will remain important in the foreseeable future. Real-world instances of FAP typically involve very large networks, which can be handled only by heuristic methods. In the present work, we are interested in optimizing frequency assignments for problems described in a mathematical formalism that incorporates actual interference information, measured directly on the field, as is done in current GSM networks. To achieve this goal, a range of metaheuristics have been designed, adapted, and rigourously compared on two actual GSM networks modeled according to the latter formalism. To generate quickly and reliably high-quality solutions, all metaheuristics combine their global search capabilities with a local-search method specially tailored for this domain. The experiments and statistical tests show that in general, all metaheuristics are able to improve upon results published in previous studies, but two of the metaheuristics emerge as the best performers: a population-based algorithm (Scatter Search) and a trajectory based (1+1) Evolutionary Algorithm. Finally, the analysis of the frequency plans obtained offers insight about how the interference cost is reduced in the optimal plans.

keywords

  • frequency assignment problem; large-scale real-world instances; metaheuristics; optimal design; ;