Optimisation de l'intégrale de Choquet pour le calcul de plus courts chemins multi-objectifs préférés

Dans cette thèse nous nous intéressons à la prise en compte des préférences du décideur pour le calcul des plus courts chemins multi-objectif. Les préférences du décideur sont modélisées a priori par une fonction d utilité basée sur une intégrale de Choquet. Plutôt que de calculer l ensemble des solutions efficaces puis de sélectionner une solution optimale selon cette fonction d utilité, nous cherchons à directement construire une solution efficace optimale au regard des préférences. Le travail réalisé développe une règle de coupe, propose une relation de dominance et valide ces propositions sur un problème de routage multi-objectif rencontré dans les réseaux informatiques. La règle de coupe permet de réduire l espace de recherche en calculant une somme pondérée bornant la fonction d utilité. Plusieurs méthodes pour le calcul d une telle somme pondérée sont proposées, analysées et comparées. Nous définissons une nouvelle relation de dominance capable de prendre en compte la fonction d utilité et raffinant la relation de dominance de Pareto. Des conditions suffisantes de cette dominance sont proposées, elles permettent de réduire le nombre de solutions calculées et les temps de calcul par rapport aux méthodes existantes. Nous montrons que les préférences d un administrateur réseau, dans le cadre du routage multi-objectif au niveau IP, peuvent être modélisées à l aide d une fonction d utilité basée sur l intégrale de Choquet. Les résultats précédents sont appliqués pour la résolution de ce problème.The purpose of this thesis is to handle decision maker preferences for computing multi-objective shortest paths. Decision maker preferences are modeled a priori with a utility function based on a Choquet integral. Instead of computing the set of efficient solutions and choosing afterward an optimal solution according to the utility function, we aim to directly compute an efficient optimal solution satisfying decision maker preferences. In this thesis we develop a pruning rule, propose a dominance relation and valid these propositions in a multi-objective routing problem for computer networks. The pruning rule allows to reduce the search space by computing a weighted sum that bounds the utility function. Several methods for computing such weighted sum are proposed, analyzed and compared. We define a new dominance relation that considers the utility function and refines Pareto dominance. Sufficient conditions for this dominance are proposed, they allow to reduce the number of solutions computed and computing time compared to existing methods. We highlight that network administrator preferences, for multi-objectif routing in IP network, can be modeled with a utility function based on the Choquet integral. Previous results are applied for solving this problem.NANTES-BU Sciences (441092104) / SudocSudocFranceF