Utilisation de GRASP et des Algorithmes Génétiques pour la conception de réseaux IP/MPLS résistants et à coût réduit

The main objective of this thesis is to find good quality solutions for rep- resentative instances of the problem of designing a resilient and low cost IP/MPLS network, to be deployed over an existing optical transport network. This research is motivated by two complementary real-world application cases, which comprise the most important commercial and academic networks of Uruguay.To achieve this goal, we performed an exhaustive analysis of existing models and technologies. From all of them we took elements that were contrasted with the par- ticular requirements of our counterparts. We highlight among these requirements, the need of getting solutions transparently implementable over a heterogeneous net- work environment, which limit us to use widely standardized features of related technologies. We decided to create new models more suitable to fit these needs.These models are intrinsically hard to solve (NP-Hard). Thus we developed meta- heuristics to find solutions to these real-world instances. Evolutionary Algorithms and Greedy Randomized Adaptive Search Procedures obtained the best results.As it usually happens, prospective real-world problems are surrounded by uncer- tainty. Therefore, we have worked closely with our counterparts to reduce the fuzzi- ness upon data to a set of representative cases. They were combined with different strategies of design to get to scenarios, which were translated into representative instances of these problems.Finally, the algorithms were fed with this information, and from their outcome we derived our results and conclusions.L'objectif principal de cette thèse est de trouver des solutions de bonne qualité à des instances représentatives du problème de la conception d'un réseau IP/MPLS qui soit résistant et de faible coût, déployé sur une infrastructure de transport optique existante. Ces travaux ont été motivés par deux cas réels, concernant les plus grands réseaux commercial et académique d'Uruguay. Ce type de problème étant NP difficile, nous avons développé des méta-heuristiques pour trouver des solutions, basées dans les méthodologies GRASP et GA, combinées avec une analyse détaillée des incertitudes associées avec les problèmes. Ces travaux ont ainsi permis de traiter efficacement les deux familles de problèmes réels de grande taille