Ce manuscrit présente des travaux effectués sur l'optimisation des réseaux d'accès télécoms. Il s'agit de la partie du réseau qui agrège le trafic des clients se trouvant dans une même zone géographique, avant de le transmettre vers le coeur du réseau. C'est un réseau hiérarchique avec à son sommet un concentrateur central et à sa base les clients, et qui présentent un ou plusieurs niveaux de concentrateur intermédiaires. Nous nous intéressons ici à deux applications : l'optimisation de l'accès du réseau téléphonique commuté sur un territoire vierge, et l'optimisation du déploiement d'un réseau d'accès en fibre optique en présence d'une infrastructure existante. Pour la première application, nous proposons d'améliorer les méthodes de résolution existantes et proposons de nouvelles méthodes afin d'avoir des solutions de qualité pour différents types d'instances.Pour le réseau d'accès optique, le problème consiste à raccorder les clients au concentrateur central à travers deux ou trois niveaux de coupleurs optiques. Le but de l'optimisation et de minimiser le coût de déploiement global. Nous proposons de nouveaux modèles pour les problématiques de localisation des coupleurs et de choix du câblage. Quelques tests sont présentés montrant qu'il est possible d'obtenir des solutions de qualité sur des instances réelles pour le problème de localisation de coupleurs.

We are pleased to welcome readers to this issue of the Journal of Applied Operational Research (JAOR), Volume 4, Number 3. The journal reports on developments in all aspects of operational research, including the latest advances and applications. It is a primarily goal of the journal to focus on and publish practical case studies which illustrate real-life applications.

These proceedings gather contributions presented at the 3rd International Conference on Applied Operational Research (ICAOR 2011) in Istanbul, Turkey, August 24-26, 2011, published in the series Lecture Notes in Management Science (LNMS). The conference covers all aspects of Operational Research and Management Science (OR/MS) with a particular emphasis on applications.

OPTIMISER UN RESEAU REVIENT EN GENERAL A LE CONSTRUIRE OU A LE METTRE A NIVEAU AFIN DE RENDRE CERTAINS SERVICES AVEC DES QUALITES DONNEES, TOUT EN MINIMISANT LES COUTS (INSTALLATION, GESTION ETC.) OU (ET) EN MAXIMISANT LES REVENUS GENERES. LA CONTINUITE DU SERVICE ET LA CAPACITE DU RESEAU A FAIRE FACE AUX PANNES POUVANT AFFECTER SES ENTITES, SONT DES PROPRIETES ESSENTIELLES POUR UN GRAND OPERATEUR. LA THESE PRESENTEE DANS CE DOCUMENT A DONC POUR CADRE LE MONDE DES TELECOMMUNICATIONS, SES RESEAUX ET LEURS OPTIMISATION. ELLE A POUR OBJECTIF D'ILLUSTRER CE QUE LA THEORIE DES GRAPHES, LES PROBABILITES ELEMENTAIRES ET LA RECHERCHE OPERATIONNELLE PEUVENT APPORTER AUX PROBLEMES D'OPTIMISATION ET DE SECURISATION DES RESEAUX DE TELECOMMUNICATIONS. EN FAISANT ABSTRACTION DE LA GRANDE COMPLEXITE DES RESEAUX DE TELECOMMUNICATION, ON PEUT RESUMER L'OPTIMISATION DE RESEAUX SECURISES EN TROIS POINTS INTERDEPENDANTS : LA DETERMINATION DE LA TOPOLOGIE DU RESEAU, LE DIMENSIONNEMENT DE SES RESSOURCES ET LE ROUTAGE DES DEMANDES DE TRAFIC. POUR ETUDIER CES TROIS POINTS, NOUS AVONS TOUT D'ABORD ETE AMENES A REALISER UN TRAVAIL PORTANT SUR LES GRAPHES QUI A PERMIS DE DEMONTRER PLUSIEURS NOUVEAUX RESULTATS THEORIQUES AYANT DES APPLICATIONS IMMEDIATES POUR LA MODELISATION DES TOPOLOGIES DES RESEAUX SECURISES. ENSUITE, NOUS NOUS SOMMES INTERESSES A PLUSIEURS PROBLEMES DE DIMENSIONNEMENT EN FONCTION DES ALGORITHMES DE ROUTAGE ET DES RESEAUX ETUDIES (IP, ATM ETC.). PLUSIEURS PROBLEMES D'OPTIMISATION ONT AINSI ETE RESOLUS PARTIELLEMENT OU COMPLETEMENT DANS CETTE THESE.

Les réseaux de communication devenant de plus en plus présents dans nos activités quotidiennes, l'interruption ou une une dégradation significative des services fournis par le réseau deviennent de moins en moins tolérables. Une conception robuste des réseaux de communication, anticipant les pannes éventuelles d'équipements ou les variations du trafic, devient donc de plus en plus nécessaire. Cette thèse traite de plusieurs problèmes de conception et de planification robustes. Nous étudions tout d'abord le problème de la conception et du dimensionnement d'une topologie de communication résiliente et proposons un modèle de conception intégrant les coûts et contraintes des équipements ainsi que de nombreuses contraintes opérationnelles (nœuds potentiels, capacités modulaires, délais de communication). Un algorithme exact et deux approximations sont proposés pour résoudre ce problème. Les résultats numériques montrent que des économies substantielles peuvent être effectuées en intégrant les coûts d'équipements dans la phase amont de la conception. Les variations sur les volumes de trafic sont devenus un des problèmes majeurs auxquels sont confrontés les opérateurs. Il devient ainsi nécessaire d'intégrer explicitement l'incertitude sur la demande en trafic dans les problèmes de planification. Nous étudions deux problèmes d'optimisation robuste du routage : (1) le problème de conception des VPN dans le cadre du modèle hose et (2) le problème d'optimisation des métriques de routage IGP avec incertitude sur la demande. Nous formulons des modèles mathématiques de chacun de ces problèmes et proposons des heuristiques basées sur des techniques de recherche locale pour les résoudre.

Dans cette thèse, nous nous intéressons aux problèmes d’optimisation dans les réseaux de télécommunication. Un premier objectif consiste à identifier les problèmes spécifiques aux réseaux optiques et satellitaires, et à présenter des contributions pour l’optimisation des ressources de ces réseaux. Le second objectif est de présenter une contribution logicielle pour la conception et l’optimisation de réseaux. La première partie débute par la présentation des réseaux optiques WDM. Nous abordons ensuite les modèles pour les réseaux optiques et satellitaires et proposons des méthodes algorithmiques nouvelles pour optimiser l’allocation des ressources de ces réseaux. Nous traitons ainsi le problème du routage, du groupage et de la protection des réseaux WDM successivement dans trois chapitres puis nous nous intéressons à un algorithme dédié à l’allocation de fréquences dans les réseaux satellitaires. Enfin, pour chaque problème, nous présentons des résultats expérimentaux sur des instances de réseaux réels. Le deuxième partie de cette thèse présente les développements logiciels qui ont été entrepris. Le premier chapitre présente le logiciel Porto dédié à la résolution d problèmes de routage, groupage et protection dans des réseaux optiques utilisant trois niveaux de brassage. Dans un second chapitre, nous présentons le logiciel Mascopt, une bibliothèque d’optimisation pour le domaine des graphes et des réseaux qui a servi notamment à réaliser les expérimentations présentées dans la première partie.

Les problèmes étudiés dans cette thèse sont motivés par des questions issues de l'optimisation des réseaux de télécommunication. Nous avons abordé ces problèmes sous deux angles principaux. D'une part nous avons étudié leurs propriétés de complexité et d'inapproximabilité. D'autre part nous avons dans certains cas proposé des algorithmes exacts ou d'approximation ou encore des méthodes heuristiques que nous avons pu comparer à des formulations en programme linéaires mixtes sur des instances particulières. Nous nous intéressons aussi bien aux réseaux de coeur qu'aux réseaux d'accès. Dans le premier chapitre, nous présentons brièvement les réseaux d'accès ainsi que les réseaux multiniveaux de type IP/WDM et l'architecture MPLS que nous considérons pour les réseaux de coeur. Ces réseaux sont composés d'un niveau physique sur lequel est routé un niveau virtuel. A leur tour les requêtes des utilisateurs sont routées sur le niveau virtuel. Nous abordons également la tolérance aux pannes dans les réseaux multiniveaux qui motive deux problèmes que nous avons étudiés. Le second chapitre est consacré à la conception de réseaux virtuels. Dans un premier temps nous modélisons un problème prenant en compte la tolérance aux pannes, puis nous en étudions un sous-problème, le groupage. Notre objectif est de minimiser le nombre de liens virtuels, ou tubes, à installer pour router un ensemble de requêtes quelconque lorsque le niveau physique est un chemin orienté. Le troisième chapitre traite des groupes de risque (SRRG) induits par l'empilement de niveaux au sein d'un réseau multiniveaux. Grâce à une modélisation par des graphes colorés, nous étudions la connexité et la vulnérabilité aux pannes de ces réseaux. L'objet du *quatrième chapitre* est le problème du placement d'instruments de mesure du trafic dans le réseau d'accès d'un opérateur. Nous considérons aussi bien les mesures passives qu'actives. La surveillance du trafic possède de nombreuses applications, en particulier la détection de pannes et l'évaluation des performances d'un réseau.