Finding optimal paths on dynamic road networks

Auteur(s): Bergeron Guyard, Alexandre
Direction de recherche: Laviolette, François
Résumé: Ce document examine différentes méthodes pour calculer des chemins optimaux sur des graphes dynamiques. Deux grandes approches sont comparées: l’approche déterministe et l’approche probabiliste. L’approche déterministe prend pour acquise une certaine connaissance préalable des changements à venir dans l’environnement. L’approche probabiliste tente de modéliser et traiter l’incertitude. Une variante dynamique de l’algorithme de Dijkstra est détaillée dans le contexte déterministe. Les paradigmes des Markov Decision Processes (MDP) et Partially Observable Markov Decision Processes sont explorés dans le cadre du problème probabiliste. Des applications et mesures sont présentées pour chaque approche. On constate une relation inverse entre la calculabilité des approches proposées et leur potentiel d’application pratique. L’approche déterministe représente une solution très efficace à une version simplifiée du problème. Les POMDP s’avèrent un moyen théorique puissant dont l’implantation est impossible pour des problèmes de grande taille. Une alternative est proposée dans ce mémoire à l’aide des MDP.
Type de document: Mémoire de maîtrise
Date de publication: 2008
Date de la mise en libre accès: 13 avril 2018
Lien permanent: http://hdl.handle.net/20.500.11794/20548
Université décernant le diplôme: Université Laval
Collection :Thèses et mémoires

Fichier(s) :
Description TailleFormat 
25830.pdfTexte1.8 MBAdobe PDFMiniature
Télécharger
Tous les documents dans CorpusUL sont protégés par la Loi sur le droit d'auteur du Canada.