Décomposition d'un réseau de transport urbain de grande taille.

Overview & Synopsis

Dans ce rapport de recherche, nous nous intéressons à la décomposition de réseaux urbains de grande taille en sous réseaux de taille limitée. Nous cherchons à minimiser les connexions entre sous réseaux. En d'autres termes, nous cherchons à minimiser le nombre de noeuds situés à la frontière entre sous réseaux. Ce travail s'intègre dans une démarche qui a pour but de fournir aux conducteurs de véhicules automobiles un support qui leur permet de trouver le chemin le plus rapide entre deux localisations données. Deux algorithmes notés RP-1 et RP-2 sont présentés dans ce qui suit. Dans chacun de ces algorithmes, chaque noeud constitue initialement un sous réseau. Dans le premier algorithme, deux sous réseaux sont agrégés à chaque pas. Les deux sous réseaux choisis sont ceux qui conduisent au sous réseau de densité minimale. La densité d'un sous réseau est le quotient du nombre de noeuds situés sur la frontière par le nombre de noeuds du sous réseau. Dans le second algorithme, nous choisissons le sous réseau de densité maximale et nous lui agrégeons le sous réseau densité maximale qui lui est connecté. Nous poursuivons le processus jusqu'à atteindre la taille maximale acceptée, puis nous recommençons le processus jusqu'à épuisement des noeuds. Dans le second algorithme, l'intensité est définie comme le rapport entre le nombre de connexions entre les sous réseaux et le nombre de noeuds dans le sous réseau agrégé. Ces deux algorithmes sont ensuite comparés, puis appliqués à un vaste réseau de la Ville de Paris.