Modèles de résolution approchée et efficace pour les problèmes des réseaux de transport et de télécommunication

This thesis focuses on solving combinatorial optimization problems NP-hard using approximate solving methods. Two practical application areas are targeted here, firstly the general problem of vehicule routing network with a variant specifically with planning tours with a vehicle team, on the other hand the multicast session management problem on a telecommunications network, addressed by the broader perspective of clustering in a bipartite graph. Both applications are obviously of interest both from the fundamental point of view for the resolution methods that must always progress facing new challenges, from the point of view of potential industrial benefits. The resolution of such problems usually has two phases: initially it comes to define one or more mathematical models to compare possibly to choose the most effective according to the available resolution tools; secondly it is possible to use a generic resolution paradigm, such as a linear programming solver, or specialize an algorithm by including specific heuristics and knowledge to optimize its performance. This thesis is in this second approach. This is often necessary when the problems addressed become complex and / or large and that we need to be designing more efficient algorithmsCette thèse s’intéresse à la résolution de problèmes d’optimisation combinatoires NP-difficiles en utilisant des méthodes de résolution approchées. Deux domaines d’application sont ciblés ici, d’une part la problématique générale du réseau de transport avec une variante portant plus précisément sur la planification des tournées avec une équipe de véhicules, d’autre part le problème de gestion de sessions en mode multicast dans un réseau de télécommunication, abordé ici du point de vue plus général du partitionnement dans un graphe biparti. Ces deux applications sont évidemment d’intérêt, tant du point de vue fondamental pour les méthodes de résolution qui doivent toujours progresser face à de nouveaux challenges, que du point de vue des retombées industrielles potentielles. La résolution de tels problèmes comporte généralement deux phases : dans un premier temps il s’agit de définir un ou plusieurs modèles mathématiques, de les comparer éventuellement pour choisir le plus efficace en fonction des outils de résolution disponibles; dans un deuxième temps il est possible d’utiliser un paradigme de résolution générique, comme par exemple un solveur de programmation linéaire, ou bien de spécialiser un algorithme en y incluant des heuristiques et connaissances spécifiques, afin d’optimiser sa performance. C’est dans cette deuxième démarche que se situe cette thèse, démarche souvent nécessaire lorsque les problèmes abordés deviennent complexes et/ou de grande taille et que l’on souhaite concevoir des algorithmes plus efficace