Langues : English français
Accueil > Manifestations > Thèses et HDR > Thèses > Hugo Fouchal

Hugo Fouchal

Directeur de thèse

X. Gandibleux
F. Lehuédé

Résumé

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-objectifs. 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 internet.
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.

Mots-clés : optimisation combinatoire multi-objectif ; plus courts chemins ; préférences ; intégrale de Choquet ; algorithme d’étiquetage.

Abstract :

The purpose of this thesis is to handle decision maker preferences in order to compute 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 that 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.

Keywords : multi-objective combinatorial optimisation ; shortest paths ; preferences ; Choquet integral ; labeling algorithm.

Dernière modification : lundi 17 octobre 2011