ALGODYN - Algorithmes pour les réseaux dynamiques

Notre objectif est d’étudier, sous un angle algorithmique, des problèmes d’optimisation centraux pour les réseaux de transport. Un tel réseau peut être représenté par un graphe temporel dont les sommets sont les points d’intérêt (villes, gares, arrêts de bus, etc.), et les arêtes, les connexions entre ces points. Les connexions peuvent apparaître et disparaître au cours du temps, ainsi les arêtes sont munies de données temporelles indiquant les moments où elles sont actives.

La thématique émergente des graphes temporels (ou dynamiques) permet de se rapprocher des problématiques du monde réel. Dans un tel graphe, les connexions ne sont pas présentes tout le temps, mais seulement à certains intervalles. Cela représente par exemple le fait que, dans un réseau de transport, certaines voies de communication peuvent être momentanément bloquées.

Considérer les graphes dynamiques permet de raffiner les résultats algorithmiques existants et de les transposer à un contexte plus réaliste.

Notre objectif est de contribuer au développement récent de l’algorithmique de ce type d’objets. Nous utiliserons les outils de l’algorithmique des graphes pour aborder ces problèmes.