Dans ce mémoire nous avons, en premier lieu, identifié et présenté deux méthodes de calcul de l'ensemble de Pareto.Ces méthodes ne demandent qu'un logiciel élémentaire de programmation linéaire. En second lieu nous avons analysé une problématique issue du domaine de la fonderie. Nous avons présenté un problème de base de mélange classique. Ensuite nous avons considéré un problème bicritère de correction d'un prémélange et calculé son ensemble de Pareto. En troisième lieu nous avons constaté qu'il était possible de présenter une formulation unifiée des deux problèmes précédents sous forme d'un second problème bicritère. Cette unification fait intervenir une transformation géométrique. Finalement nous avons terminé ce mémoire par une étude sommaire de cette transformation géométrique mettant en évidence les cônes de préférence associés aux ensembles de Pareto de ces différents problèmes.

In the first part of the thesis, we address the optimization of multimedia applications such as videoconferences or multi-player games in which user-dependent information has to be sent from the users to a core node to be chosen, and then global information has to be multicast back from the core node to all users. For a given communication network, this optimization seeks a core node under two potentially competing criteria, one being the sum of the distances to a set of user terminals, the other being the cost of connecting this core node and the terminals with a multicast (or Steiner) tree. We first consider the problem of minimizing a weighted sum of the two criteria and propose a heuristic which rapidly computes a solution guaranteed to be within a few percent of the optimum. Then we characterize the worst-case trade-offs between approximation ratios for the two criteria. To state our result informally, we show that there always exists a core location for which each criterion is close to its minimum value (if we were to disregard the other criterion). In the second part, we focus on the protection of multimedia streaming applications against packet losses. Because of real-time constraints, error recovery is often achieved by Forward Error Correction (FEC) techniques which consist of partitioning the packet stream into blocks of consecutive packets and adding redundant data packets to each block. If the number of packets lost within a block is at most the number of redundant packets added, the receiver is able to recover the original data packets. Otherwise some data is irrecoverably lost. In communication networks, FEC techniques are typically impaired by the fact that packet losses are not evenly distributed among blocks but rather occur in long bursts of consecutive losses. However it has been observed that splitting the transmission of a FEC block onto several paths typically decreases the probability of an irrecoverable loss. Whereas current approaches rely on an exact computation of the probability and are consequently restricted to very small network instances, we propose to approximate this probability by measuring the impact of the chosen routing on the peakedness of the received packet stream. The peakedness of a stream may be seen as a measure of how packets are spread over time within the stream. Numerical experiments are presented and show that our method yields good approximations of the probability of irrecoverable loss./La première partie de cette thèse concerne l'optimisation d'applications multimédias, telles que des vidéoconférences ou des jeux en groupes, pour lesquels l'information propre à chaque utilisateur doit être envoyée vers un noeud central à sélectionner. L'information globale est ensuite diffusée en retour de ce noeud central vers chacun des utilisateurs. Pour un réseau de communication donné, cette optimisation consiste à choisir le noeud central selon deux critères potentiellement concurrents, le premier étant la somme des distances vers les utilisateurs, le second étant le coût de connecter ce noeud central et les utilisateurs avec un arbre multicast (ou arbre de Steiner). Nous considérons tout d'abord le problème de la minimisation d'une somme pondérée des deux critères et proposons une heuristique qui calcule rapidement une solution garantie d'être éloignée de l'optimum d'au plus quelques pour cent. Ensuite nous caractérisons les pires cas du compromis existant entre les rapports d'approximation pour les deux critères. De façon informelle, notre résultat peut se formuler comme suit : nous montrons qu'il est toujours possible de sélectionner le noeud central de telle sorte que chaque critère soit proche de sa valeur minimum (obtenue sans considérer l'autre critère). Dans la seconde partie, nous nous concentrons sur la protection des applications de diffusion multimédia (streaming) contre les pertes de paquets. A cause de contraintes temps réel, la récupération des erreurs pour ces applications est typiquement réalisée par des techniques de corrections d'erreurs dites "en avant" (Forward Error Correction ou FEC) qui consistent à partitionner le flux de paquets en blocs de paquets consécutifs et à ajouter des paquets de données redondantes à chacun de ces blocs. Si le nombre de paquets perdus au sein d'un bloc est inférieur ou égal au nombre de paquets ajoutés, le récepteur est capable de récupérer les paquets de données originaux. Dans le cas contraire, des données sont perdues de façon irrécupérable. Dans les réseaux de communication, l'efficacité des techniques FEC est typiquement dégradée par le fait que les pertes de paquets ne sont pas distribuées uniformément parmi les blocs de paquets mais apparaissent plutôt groupées par en rafales de pertes consécutives. Cependant il a été récemment observé que répartir la transmission d'un bloc FEC sur plusieurs chemins permet généralement de diminuer la probabilité de perte irrécupérable. Alors que les approches existantes se basent sur un calcul exact de cette probabilité et se limitent donc à des réseaux de très petite taille, nous proposons d'en calculer une approximation en mesurant l'impact du routage choisi sur la "peakedness" du flux de paquets. La peakedness d'un flux peut être vue comme un mesure de la répartition temporelle des paquets au sein de ce flux. Des résultats numériques sont présentés et montrent que notre méthode permet de calculer une bonne approximation de la probabilité de perte irrécupérable..

Mes travaux de recherche ont pour sujet unificateur : les déplacements et les réseaux de transport ; et ils ont été traités par une approche unique, la modélisation physico-économique à caractère mathématique et algorithmique.<br />Une telle modélisation comporte quatre aspects : un contenu sémantique, à caractère physique ou économique ; une formulation mathématique ; un solveur technique ; un aspect empirique (métrologie, statistique, économétrie).<br />Les disciplines mises en œuvre sont variées : théorie des réseaux, optimisation, informatique algorithmique, probabilités et statistiques, et aussi économie, socio-économie et physique du trafic. Mes contributions théoriques concernent la théorie des réseaux, l'économie du transport et la physique du trafic.<br />Mes travaux se répartissent en quatre thèmes :<br />A. La mesure et la modélisation du trafic. Au niveau local d'une route, j'ai analysé la relation entre flux et vitesse en mettant en cohérence l'analyse désagrégée, probabiliste au niveau du mobile individuel ; et l'analyse macroscopique en termes de flux et de distribution statistique des temps.<br />B. La modélisation des réseaux et des cheminements. L'équilibre entre offre de transport et demande de déplacement conjugue une dimension spatiale - topologique, une dimension temporelle, et une dimension comportementale - économique. Les enjeux de modélisation concernent : la représentation de l'offre et la demande ; la formulation et les propriétés d'existence – unicité – stabilité ; les algorithmes. Je me suis intéressé à la diversité des comportements ; et à la modélisation fine de l'offre et à la dimension temporelle.<br />C. L'analyse socio-économique des déplacements. Je me suis intéressé à l'usage de divers moyens de transport et à la prospection de leur clientèle potentielle ; au choix d'horaire de déplacement ; aux caractéristiques à la fois économiques et dynamiques de la congestion.<br />D. La distribution spatiale des déplacements et des activités. Je me suis intéressé d'une part à l'observation des flux par relation origine-destination (O-D) et à l'inférence statistique des matrices O-D ; et d'autre part, à la justification microéconomique des déplacements en raison de la localisation et de l'utilité des activités.