| Cellular wireless network operators set aside an important part of their budget to acquire, install and maintain equipments like radio interfaces, controllers and switches. Considering the cost of a cellular wireless infrastructure, network planning and optimization are important issues for those operators in order to remain competitive.; In this thesis, we first propose a constraint programming model for the design problem of cellular wireless communication networks. It consists of selecting the location of the base station controllers (BSC) and mobile service switching centers (MSC), selecting their types, designing the network topology and selecting the link types, and considering the location of base transceiver stations (BTS). The objective is to find the minimum cost network. Since this problem is NP-hard, it is unlikely that real-size instances of the problem can be solved to optimality within a reasonable amount of time. As a result, we propose a heuristic to find a good solution of the model. This heuristic is based on a local search heuristic combined with constraint programming techniques.; In order to assess the performance of the proposed heuristic, we compare it with a tabu search algorithm proposed by Chamberland and Pierre (2002) and with a lower bound obtained by solving a relaxed version of the model. The heuristic was tested with the same set of randomly generated instances as Chamberland and Pierre (2002). The solutions found with our approach are near the lower bound and improve by more than 2% the best solution found so far. |
