Calcul de plus courts chemins multicritères et problèmes géométriques connexes

Abstract

Cette thèse s'intéresse au calcul de plus courts chemins multicritères approché. Dans un contexte multicritère, le calcul des ensembles de Pareto, c'est-à-dire de toutes les solutions optimales, est souvent prohibitif. De nombreuses approches consistent à n'en calculer que des sous-ensembles. Certaines offrent des temps de calcul raisonnables mais aucune garantie quant à la représentabilité, c'est-à-dire la distribution du sous-ensemble calculé dans l'ensemble de Pareto complet. D'autres méthodes garantissent une certaine représentabilité et des complexités intéressantes, mais elles sont généralement inutilisables en pratique. Un autre problème est que ces deux approches ne garantissent généralement pas que la sortie est réellement un sous-ensemble de l'ensemble de Pareto : elle peut donc contenir des chemins non optimaux.Tout d'abord, nous proposons deux optimisations de méthodes exactes classiques : MC DIJKSTRA 2D pour le cas bicritère et BUCKET pour toute dimension. Ensuite, nous proposons des algorithmes d'approximation avec des garanties théoriques intéressantes. Plusieurs d'entre eux, SECTOR, SSECTOR et QSSECTOR, fonctionnent en dimension quelconque et leur complexité en fonction de la taille de la sortie est intéressante. Cette dernière étant incomparable à la taille de l'ensemble de Pareto, nous proposons une optimisation 2D, FRAME, qui garantit que la sortie n'est constituée que de chemins optimaux. Nous déduisons que la complexité de FRAME est inférieure ou égale à celle du meilleur algorithme de calcul exact connu. Afin d'évaluer la capacité d'élagage de FRAME, nous menons une étude expérimentale. Cette étude montre que notre algorithme est intéressant lorsque la taille des ensembles de Pareto est grande.Afin d'améliorer nos algorithmes d'approximation en 3D, nous étudions les Thêta-graphes. Nous proposons des algorithmes efficaces pour la maintenance dynamique de ces graphes. Ensuite, nous étudions une requête de proximité, utilisant un Thêta-graphe pour trouver les plus proches voisins dans une direction donnée. Enfin, nous détaillons comment appliquer nos algorithmes de Thêta-graphes pour le calcul de plus court chemins tricritères.