Algorithmes de recherche d'itinéraires en transport multimodal

Ce travail de thèse s est intéressé au transport urbain de passagers dans un contexte d offre de transport multimodale consistant en la coexistence de plusieurs modes de transport. Dans la pratique, un problème de transport multimodal nécessite la prise en compte de plusieurs objectifs et de contraintes spécifiques liées aux modes ou à la séquence de modes utilisés. De telles contraintes sont appelées contraintes de viabilité.Cette thèse CIFRE s est déroulée en collaboration avec la société MobiGIS, spécialisée dans le conseil et le développement d applications autour des Systèmes d Information Géographiques.Le problème étudié dans cette thèse est celui de la recherche d itinéraires viables multimodaux point à point bi-objectif pour lequel il s agit à la fois de minimiser le temps de trajet et le nombre de changements de mode. Compte tenu notamment des objectifs considérés, ce problème est de complexité polynomiale.Sur la base d une modélisation multi-couches des réseaux de transport multimodaux et d une modélisation par un automate à états finis des contraintes de viabilité nous avons proposé différents algorithmes de résolution de ce problème basés sur le principe de fixation et extension de labels. Nous avons également proposé une règle de dominance basée sur les états de l automate de viabilité et permettant d élaguer le nombre de labels explorés par nos algorithmes. Des adaptations en bidirectionnel ou en utilisant le principe de la recherche A_ ont également été proposées.Les algorithmes proposés ont été évalués sur une partie du réseau de transport de la ville de Toulouse et les expérimentations ont mis en évidence l intérêt de la règle de dominance basée sur les états ainsi que de l approche bidirectionnelle développée.Un prototype logiciel implémentant différentes fonctionnalités des algorithmes de plus courts chemins a été développé. Il permet notamment de réaliser des calculs d itinéraires point à point, des calculs d accessibilité ou des calculs de distancierThis thesis focuses on urban passenger multimodal transportation. In practice, a multimodal transportation problem requires taking into account several objectives and specific constraints related to modes or sequence of used modes. Such constraints are called viability constraints. This work has been carried out in collaboration with MobiGIS, a company specialized in consulting and development of applications around Geographical Information Systems.The problem studied in this thesis is the bi-objective multimodal viable point-to-point shortest path, aiming at minimizing the total travel time and the total number of mode changes. Given the considered objectives, this problem is polynomial.On the basis of a multi-layered graph model of the multimodal transportation networks, and of a finite state automaton model of the viability constraints, we propose various algorithms for solving this problem, based on the principle of label setting and extension.We also proposed a new dominance rule based on the states of the automaton to reduce the number of labels explored by our algorithms. Bidirectional and A* variants are also proposed.The algorithms are evaluated the transportation network of the city of Toulouse and experiments demonstrate the interest of the proposed dominance rules and bidirectional approach. A prototype software implementing different features of the shortest path algorithms has been developed. It notably enables calculations of point-to-point routes, accessibility and origin-destination matricesTOULOUSE-INSA-Bib. electronique (315559905) / SudocSudocFranceF