Planification du réseau d'accès pour l'amélioration de la rentabilité de l'infrastructure d'un réseau FTTN

Étant donné l'offre de nouveaux services de réseau comme la télévision haute définition sur le protocole IP (Internet Protocol), de nouvelles architectures et technologies devraient être planifiées et introduites dans le réseau d'accès afin d'améliorer le taux d'accès. La meilleure solution est d'étendre le réseau de fibre jusqu'à l'abonné. Cependant, celle-ci est très coûteuse et ne peut être largement déployée de nos jours. Une alternative intéressante est la technologie FTTN (Fiber-to-the-node) qui réduit la portion de réseau utilisant le cuivre. Dans ce mémoire, on commence par présenter un modèle de programmation mathématique de réseau d'accès dans le but d'améliorer la rentabilité de l'infrastructure d'un réseau FTTN. Ce modèle consiste à trouver le nombre et la localisation des noeuds, et sélectionner les chemins qui seront utilisés d'un noeud à chaque point de demande. Le problème a des contraintes qui limitent la capacité des noeuds et la distance entre chaque point de demande et le noeud qui le dessert. Le but est de minimiser la somme du coût des paires de cuivre à installer et du coût d'installation des noeuds. Par la suite, la complexité du problème est analysée. Nous montrons que des instances du problème de grande taille ne peuvent être résolues de manière exacte dans un temps raisonnable, car le problème est NP-difficile. Nous proposons donc une heuristique basée sur la recherche taboue dans le but de trouver de bonnes solutions dans un temps raisonnable. Les résultats obtenus en utilisant l'heuristique taboue proposée sont comparés avec une borne inférieure obtenue en relâchant des contraintes du modèle mathématique. Celle-ci est calculée en utilisant le résolveur commercial CPLEX qui utilise l'algorithme d'évaluation et séparation. Des tests effectués avec des exemplaires du problème générés de façon aléatoire montrent que l'heuristique proposée donne des résultats satisfaisants. En effet, la moyenne des écarts est de 0,34 et le temps d'exécution est raisonnable.