Designing cellular networks using a parallel hybrid metaheuristic on the computational grid

Cellular network design is a major issue in mobile telecommunication systems. In this paper, a model of the problem in its full practical complexity, based on multiobjective constrained combinatorial optimization, has been investigated. We adopted the Pareto approach at resolution in order to compute a set of diversified non-dominated networks, thus removing the need for the designer to rank or weight objectives a priori. We designed and implemented a “ready-to-use” platform for radio network optimization that is flexible regarding both the modeling of the problem (adding, removing, updating new antagonist objectives and constraints) and the solution methods. It extends the “white-box” ParadisEO framework for metaheuristics applied to the resolution of mono/multi-objective Combinatorial Optimization Problems requiring both the use of advanced optimization methods and the exploitation of large-scale parallel and distributed environments. Specific coding scheme and genetic and neighborhood operators have been designed and embedded. On the other side, we make use of many generic features related to advanced intensification and diversification search techniques, hybridization of metaheuristics and grid computing for the distribution of the computations. They aim at improving the quality of networks and their robustness. They also allow, to speed-up the search and obtain results in a tractable time, and so efficiently solving large instances of the problem. Using three realistic benchmarks, the computed networks and speed-ups on different parallel and/or distributed architectures show the efficiency and the scalability of hierarchical parallel hybrid models.