Afficher la notice abrégée

dc.contributor.advisorHanusse, Nicolas
dc.contributor.advisorIlcinkas, David
dc.contributor.authorLENTZ, Antonin
dc.contributor.otherHanusse, Nicolas
dc.contributor.otherIlcinkas, David
dc.contributor.otherBose, Prosenjit
dc.contributor.otherViennot, Laurent
dc.contributor.otherBonichon, Nicolas
dc.contributor.otherCoudert, David
dc.date2021-07-05
dc.date.accessioned2021-09-16T14:30:32Z
dc.date.available2021-09-16T14:30:32Z
dc.identifier.urihttp://www.theses.fr/2021BORD0179/abes
dc.identifier.uri
dc.identifier.urihttps://tel.archives-ouvertes.fr/tel-03346036
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/112220
dc.identifier.nnt2021BORD0179
dc.description.abstractCette 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.
dc.description.abstractEnThis thesis focuses on the computation of approximate multicriteria shortest paths. In a multicriteria context, computing the Pareto sets, i.e. all the optimal solutions, is often prohibitive. Many approaches consist in computing only a subset. Some offer reasonable computation times but no guarantee about the representability, i.e. the distribution of the subset output among the whole Pareto set. Others methods guarantee a certain representability and interesting complexities but these are generally unpractical. Another issue is that, strictly speaking, both these approaches usually do not guarantee that the output is really a subset of the Pareto set, i.e. they might output non optimal paths.First, we propose two optimizations of classical exact methods: MC DIJKSTRA 2D for the bicriteria case and BUCKET for higher dimension cases. Then, we propose approximation algorithms with interesting theoretical guarantees. Several of those, SECTOR, SSECTOR and QSSECTOR, work in any dimension and their output sensitive complexity is interesting. The latter being incomparable to the Pareto set size, we propose a 2D optimization, FRAME, which guarantees that the output is only constituted by optimal paths. We deduce that FRAME's complexity is lower or equal to the best known exact computation algorithm. In order to evaluate the pruning capability of FRAME, we conduct an experimental study. This study shows that our algorithm is interesting when the Pareto set sizes are large.In order to accelerate our approximation algorithms in 3D, we study Theta-graphs. We propose efficient algorithms for the dynamic maintenance of these graphs. Then, we study a proximity oriented query, using a Theta-graph to find nearest neighbors in a given direction. Finally, we detail how to apply our Theta-graph algorithms for tricriteria shortest path computation.
dc.language.isofr
dc.subjectAlgorithmique des graphes
dc.subjectMulticritères
dc.subjectStructures de données
dc.subjectThêta-Graphes
dc.subjectApproximation
dc.subject.enGraphs algorithms
dc.subject.enMulticriteria
dc.subject.enData structures
dc.subject.enTheta-Graphs
dc.subject.enApproximation
dc.titleCalcul de plus courts chemins multicritères et problèmes géométriques connexes
dc.title.enMulticriteria shortest paths and related geometric problems
dc.typeThèses de doctorat
dc.contributor.jurypresidentCohen, Johanne
bordeaux.hal.laboratoriesLaboratoire bordelais de recherche en informatique
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.type.institutionBordeaux
bordeaux.thesis.disciplineInformatique
bordeaux.ecole.doctoraleÉcole doctorale de mathématiques et informatique
star.origin.linkhttps://www.theses.fr/2021BORD0179
dc.contributor.rapporteurBose, Prosenjit
dc.contributor.rapporteurViennot, Laurent
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Calcul%20de%20plus%20courts%20chemins%20multicrit%C3%A8res%20et%20probl%C3%A8mes%20g%C3%A9om%C3%A9triques%20connexes&rft.atitle=Calcul%20de%20plus%20courts%20chemins%20multicrit%C3%A8res%20et%20probl%C3%A8mes%20g%C3%A9om%C3%A9triques%20connexes&rft.au=LENTZ,%20Antonin&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée