Le problème du voyageur canadien
Time: 14:30 -- Location: LRI, 455
Résumé : Le problème du voyageur canadien (PSPACE-complet), en anglais Canadian Traveller Problem (CTP), est un problème d'optimisation généralisant le problème du plus court chemin entre deux noeuds d'un graphe pondéré et non orienté. Un voyageur part d'un noeud s et son objectif est d'arriver à t en parcourant la distance la plus faible possible. Cependant, il se peut que le voyageur, lorsqu'il arrive sur le noeud u d'une arète e=(u,v), découvre que e est "bloquée" et ne peut être traversée (présence de neige sur le réseau routier,...). Seront présentés les différents concepts associés à ce problème, les principaux résultats de la littérature, nos contributions ainsi que les questions qui restent ouvertes à l'issue de ces recherches.
Summary: The Canadian Traveller Problem, which is a PSPACE-complete optimisation problem, generalizes the Shortest Path Problem which consists in finding the shortest path between two nodes in a weighted undirected graph. A traveller starts his walk at node s and his objective is to reach target t with minimum distance. However, the traveller may discover that some edges are blocked when arriving at one of their endpoints (as when a driver discovers that the road is blocked because of snow...). We introduce main results for this problem, our contributions and eventually give some questions that remain unsolved.