Planification et conception topologique des réseaux de télécommunication cellulaires

Ce travail traite du problème de la conception topologique des réseaux de télécommunication cellulaires. Deux types de modèles sont abordés. Un modèle classique intégrant dans un même problème la détermination des emplacements des équipements du réseau, leur connexion et la couverture des zones. Il consiste, à partir d'un ensemble de sites prédéfinis pour l'installation d'équipements, à déterminer lesquels activer et quelles paires connecter à coût minimal pour satisfaire la demande. Nous proposons une méthode de décomposition de Benders pour fournir une solution optimale. De ce modèle, on construit une autre formulation du problème. Cette dernière considère la quantité de trafic comme un flot devant être écoulé à travers le réseau depuis une source fictive. Ainsi, on obtient un modèle de flot qui consiste à déterminer les arcs à activer et la quantité de flot à y faire passer. Deux approches de relaxation sont utilisées pour résoudre ce modèle de flot. Une approche qui utilise une relaxation lagrangienne combinée avec un algorithme de sous-gradient et une autre qui utilise une technique de décomposition mixte