ÉTUDE DE LA QUALITÉ D’UN RÉSEAU DU POINT DE VUE DE L’ACCESSIBILITÉ

RESPONSABLES : Paul Dorbec (GREYC), Géraldine Del Mondo (LITIS)

PERSONNE(S) IMPLIQUÉE(S) : Pierrick Tranouez (LITIS)

AXE(S) ET ACTION(S) TRANSVERSE(S) CONCERNÉ(S) : Systèmes Complexes, Algorithmique et Combinatoire, Graphes et applications

MOTS CLÉS : théorie des graphes ; graphe spatial ; métrologie des graphes ; gestion des risques

SUJET ET OBJECTIFS : Le sujet de ce stage s'inscrit dans la suite des projets ANR ESCAPE et RIN ESCAPE SG qui ont pour objectif de produire des outils de modélisation et de simulation informatique permettant de représenter et d’explorer différents scénarios d’évacuation dans le cadre de la gestion des risques naturels et technologiques pour concevoir les plans les plus appropriés. Concrètement l’idée est d’avoir à sa disposition un outil pour simuler une catastrophe (e.g. tsunami, explosion d’une usine chimique) et étudier ses conséquences sur l’environnement urbain. L’analyse de ces conséquences permet d’adapter les infrastructures et les plans d’évacuation prévus dans le cadre de la gestion des risques pour les villes concernées. Les projets se basent sur une simulation multi-agent et prévoient de développer des librairies à destination des catastrophes de types tsunami, rupture de digue et accident industriel avec entre autres des données issues des villes de Rouen et d’Hanoï au Vietnam.

Dans le cadre de ce stage, on s’intéresse uniquement à l’analyse de la structure du graphe représentant l’espace dans lequel les agents se déplacent (un nœud représente une intersection et un arc un tronçon entre deux intersections du réseau). L’objectif est de déterminer les parties qui pourraient être à l’origine d’une dégradation de l’accessibilité dans le réseau (i.e. parties vulnérables). En effet, un des points critique dans le cadre d’une évacuation est la capacité du réseau routier à être résistant aux détériorations liées à l’impact de l’aléa (e.g. problèmes de congestion), autrement dit, sa capacité à maintenir une accessibilité pour tous les points du réseau.

Dans ce contexte, un premier stage de Master a été réalisé permettant d’établir un état de l’art autour d’opérateurs permettant de distinguer les parties vulnérables de ce graphe. Cependant, l’application des opérateurs a révélé que les graphes basés sur des données réelles nécessitaient d’être « nettoyés » afin que ces opérateurs puissent révéler des résultats utilisables. Il en ressort qu’un travail préliminaire fondamental sur des graphes générés aléatoirement pourrait grandement aider à caractériser les biais rencontrés dans les graphes réels et à les corriger. Ce travail fondamental est l’objet de ce nouveau stage dans lequel on s’attachera aussi à mener une réflexion sur la complexité des algorithmes développés.