Nesta dissertação, propomos um novo método de relaxamento para resolver o problema de roteamento de dados em redes de comutação. Este problema pode ser formulado como um problema de multifluxo a critério convexo. Este algoritno resolve subproblemas de simples fluxos e pode ser implementado em paralelo. No primeiro capítulo, relembramos alguns resultados da teoria dos grafos. No segundo, apresentamos o problema de roteamento de dados, bem como sua formulação matemática. O terceiro apresenta um método primal de relaxamento. O quarto é dedicado à apresentação dos resultados computacionais e à analise destes. Na última parte, apresentamos a conclusão e perspectivas de trabalhos futuros.

In this thesis, we propose a new primal relaxation algorithm for solving the optimal routing problem M packet-switched communication networks. This problem can be formulated as a nonlinear multicommodity flow problem. This algorithm solves subproblems of single flow commodities and allow for implementation in parallel computers. In the first part, we recall the basic notions of graph theory. The second part is devoted to the optimal routing problem and his formulation as a nonlinear multicommodity flow problem. The third part deals with presentation of an original primal method for optimal routing. In the fourt part, experimental results are presented and analysed. The concluding remarks are presented in the fifth part.