Groupe d’études et de recherche en analyse des décisions

G-98-14

Résolution d'un problème de la capacité dans un réseau de télécommunications

La planification de l'expansion de la capacité, la plus efficace du point de vue des coûts, afin de satisfaire une croissance continue des demandes en communication à moyen et à long terme est un problème important pour les opérateurs de réseaux de télécommunications. La résolution de ce type de problème, pour un réseau comprenant plusieurs installations à équiper, consiste à déterminer, pour chaque période de l'horizon de planification, les équipements à installer parmi l'ensemble des différents types d'équipements disponinles, tout en respectant des contraintes de ressources globales. Dans ce mémoire, nous proposons un modèle mathématique dans lequel intervient la notion de variables de plan ainsi qu'une méthode de résolution pour de tels problèmes. Cette approche est basée sur la technique de décomposition de Dantzig-Wolfe (ou génération de colonnes) au sein de laquelle deux algorithmes de programmation dynamique sont utilisés afin de résoudre les sous-problèmes issus de la décomposition. Cette méthode a été testée sur plusieurs problèmes de taille réaliste et les résultats obtenus ont démontré que cette approche était très efficace. L'intérêt d'une telle formulation (avec variables de plan) et d'une telle approche de résolution réside dans le fait qu'elles permettent de résoudre rapidement et à l'optimalité (ou très près de celle-ci) des problèmes plutôt complexes tout en considérant des contraintes globales (budgets et équipements) qui sont de plus en plus incontournables dans le contexte économique actuel. Ce genre d'outil d'aide à la planification pourrait donc s'avérer des plus utiles dans le cadre des activités de planification à moyen et long terme des réseaux de télécommunications modernes.

, 103 pages