Thèse Calcul d'Itinéraires Robustes dans des Réseaux Incertains H/F - 33

Établissement : Université de Bordeaux
École doctorale : Mathématiques et Informatique
Laboratoire de recherche : LaBRI - Laboratoire Bordelais de Recherche en Informatique
Direction de la thèse : Nicolas HANUSSE ORCID 0009000890827437
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-05-04T23:59:59

Actuellement, le calcul d'itinéraires est essentiellement réalisé sur des données statiques et réputées fiables : dans un réseau multimodal, les bus/trains/tram sont sensés être à l'heure et les transferts entre moyens de transport réalisables dès lors qu'une petite marge est prise en compte. En cas de perturbation sur le réseau (accidents, météo, ...), un utilisateur peut se retrouver à rater des correspondances et mettre un temps beaucoup plus long que celui qui était prévu. Il peut être préférable de proposer des itinéraires certes un peu plus longs mais plus fiables.

Les historiques des horaires réels et l'usage d'algorithmes de prédiction permettent de définir des mesures d'incertitude sur la fiabilité de points de passage a priori. Le passage à des définitions de chemins n'est pas évident. Ajouter un critère de robustesse aux critères classiques (temps de trajets, coût financier) ou de personnalisation (éviter/passer par certaines routes, effort physique), implique que les solutions envisagées doivent être multicritères. Cette vision est celle de la recherche d'un « meilleur » trajet du point de vue d'un utilisateur. Le principal challenge devient l'explosion combinatoire dû au calcul d'un front de Pareto entraînant des calculs très couteux en temps et mémoire.

Pour faire face aux incertitudes sur la connaissance spatio-temporelle du réseau, plusieurs modèles et solutions algorithmiques existent dans la littérature : le plus court chemin stochastique, le problème du voyageur canadien (faisant face à des routes bloquées par la neige qu'il découvre en cours de trajet), le reroutage en cours de trajet, l'optimisation de « pire cas ». Malheureusement, ces solutions sont souvent coûteuses ou non considérées dans le cadre multicritère.

L'objectif de cette thèse est de proposer des algorithmes de calcul de chemins multicritères qui tiennent compte d'une vision partiellement erronée du présent et du futur. D'un point de vue théorique, nous nous intéressons aux modèles de graphes temporels : (1) en essayant de caractériser, entre autres, le niveau maximal d'incertitude pour que des chemins de longueur finie puissent être calculés ; (2) à étendre leur expressivité pour des scénarios spatio-temporels plus variés (intégrant de la géométrie). Enfin, nous considérerons l'optimisation collective pour un ensemble d'agents. En effet, pour un grand nombre d'utilisateur, des congestions peuvent être créés à cause de recommandations de trajets peu diversifiés. Ce problème est parfois nommé le paradoxe de Braess : l'ajout d'une nouvelle route à un réseau routier peut, au lieu de le fluidifier, augmenter le temps de trajet total pour tous les usagers.

Thèse en laboratoire - collaboration potentielle avec Keolis et Bordeaux Métropole