Abstract FR:

Dans ce travail nous nous intéressons au problème de routage et expansion de capacités. On suppose qu'il existe déjà un réseau avec des capacités installées dans chacune des lignes de communication. Il s'agit alors de définir conjointement les lignes de communication les plus adéquates à effectuer l'expansion de capacités et l'acheminement des flots sur le réseau étendu afin de minimiser les coûts totaux d'investissement et de routage. Nous abordons le problème par un modèle continu dont l'innovation se trouve dans une fonction de coût sur les arcs qui combine une composante reliée au coût d'investrissement en expansion de capacité et une composante reliée au coût de routage. La fonction objective ainsi définie génère un problème de multiflots avec des coûts non convexes et non différentiables. Le coeur de la présente thèse est le développement de conditions d'optimalité locale du modèle étudié en s'appuyant sur la répartition des flots sur les arcs du réseau. Plus précisément, les propriétés des fonctions de coût sur les arcs nous permettent d'aboutir à une condition nécessaire et suffisante d'optimalité locale basée sur la non-existence de cycles de coût négatif. Cette condition nous fournit les bases théoriques pour le développement d'un algorithme d'annulation de cycles (AC) pour l'optimisation locale du problème de routage et expansion des capacités. Nous démontrons, en généralisant des résultats développés originalement pour le problème de flot de coût minimal à coûts convexes, que l'algorithme d'annulation de cycles converge linéairement vers un optimum local. On compare ensuite cet algorithme avec une approche classique basée sur une alternance d'affectation des flots et capacités (CA_FA) qui, d'ailleurs, n'assure pas la convergence vers un optimum local du problème. Nous présentons des résultats numériques sur des réseaux réels de grandes tailles. Les algorithmes AC et CA_FA arrivent à réduire significativement les écarts par rapport à la borne inférieure donnée par une approximation convexe de la fonction objecif. On constate que l'algorithme AC est plus robuste que CA_FA dans un sens où il est capable de mieux traiter différents types de configurations particulières exhibant des dimansions proches des cas réels