Etude de capacité du réseau, simulation numérique

 

Auteur : Adrien Garrigues, Wenger Marin

Tuteur : Abdelkader Lahmadi

 

Etude de capacité du réseau

 

L’algorithme de routage

 

Introduction

Lorsque le projet UrbanLoop est né, aucun des membres du projet n’était certain que cette solution technique serait viable et réaliste. Il s’est donc avéré nécessaire de réaliser des calculs énergétique, des mesures de flux et la création d’une maquette numérique afin de se convaincre que l’on travaillait sur un projet concret et crédible pour l’extérieur. La maquette numérique utiliserait l’analyse des flux réalisé afin de modéliser le fonctionnement de l’UrbanLoop tout en pouvant modifier certaines caractéristiques afin de déterminer au mieux leur optimum. Grâce à celle-ci nous pouvons obtenir des données chiffrées et explicite sur les capacités que pourrait supporter le réseau et ses éventuels point d’engorgement.

 

Problématique

 

            Afin de développer cet algorithme de routage, nous devons trouver un moyen de guider de manière individuelle chaque capsule dans le réseau UrbanLoop tout en évitant les collisions aux intersections pour assurer un trajet en toute quiétude. Plus précisément, une capsule qui part d’un point A cherche à rejoindre un point B avec la meilleure efficacité temporelle, pour cela, il faut trouver le chemin de parcours dans les tubes qui optimise ce paramètre. De plus, un autre aspect de ce problème et pas des moindres, est l’aspect sécurité du réseau. Les capsules sont vouées à se déplacer à grande vitesse dans les tubes et avec un minimum de distance entre elles afin de fluidifier le réseau. Chaque intersection devient donc une place à haut risque : il est nécessaire de calculer de manière très précise chaque horaire de passage d’une capsule à une intersection et ce pour l’ensemble du réseau en assurant la cohérence avec les trajets de toute les capsules en action simultanément sur le réseau.

 

Hypothèse de fonctionnement

 

            Il se précise que l’algorithme sera extrêmement complexe, cependant au vu des contraintes temporelle et technique, nous devons faire quelques hypothèses simplificatrices :

-    La route pour aller d’un point A à un point B sera à chaque fois la même. Celle-ci ne sera donc pas considérée comme dépendante des flux en temps réel du réseau, d’un possible problème à une station, ...

- La position de chaque capsule est connue à tout instant sans incertitude.

- Les parties du réseau sont standardisées : les portions d’accélérations, de décélérations et celles parallèles aux stations sont toutes de même longueur dans le réseau, seule change la longueur de la dernière portion où la voie d’accélération rejoint la boucle pour rendre compte de la géographie réelle du réseau.

- L’étude sera faite de façon discrète : nous divisons le temps en morceaux de 0.1 seconde.

- Les capsules PMR sont considérés comme 2 capsules normales (perte d’optimalité).

 

Principe de fonctionnement

 

            Dans un premier temps il faut représenter le réseau, on divise donc les boucles en autant de portions qu’elles contiennent de stations, puis on subdivise chacune de ces portions en 4 en distinguant la voie parallèle à la station (1), la voie de décélération (2), la voie d’accélération (3) et le dernier morceau (4).  

Schéma

Nous divisons de la même manière les intersections entre les boucles.

Par la suite nous modélisons les capsules : chaque capsule renferme en elle ses informations de numéro d’identification, de station de départ, station d’arrivée, position actuelle dans le réseau, position dans la portion de réseau, de vitesse et de routage.

Il nous reste à assurer le routage des flux de capsules en toute sécurité maintenant que le réseau et les capsules sont modélisés.

Dans un premier temps, on assure le routage des capsules en remplissant un tableau à double entrée avec la liste des stations comme entrées. Chaque case représente donc la correspondance d’une station à une autre sur l’intégralité du réseau. On remplit ces cases grâce à l’algorithme de Dijkstra qui donne le chemin optimal d’une station à une autre. Une fois ceci terminé, on dispose donc d’un tableau qui contient le routage unique d’une station à une autre pour tout le réseau.

Par la suite nous devons assurer la sécurité du réseau et donc éviter les collisions aux différentes interface. Pour cela nous réalisons donc un deuxième tableau à double entrée avec la liste des interfaces et les temps équitablement répartis avec un pas de 0.1 seconde sur toute la durée de fonctionnement. Quand une capsule part, elle calcule ses temps de passage aux différents interfaces du réseau qu’elle doit emprunter, cela correspond à des cases du tableau : ci celles-ci sont libre alors la capsule les réserve et part, sinon elle décale son horaire de départ jusqu’à ce que toutes les cases qui sont nécessaires à son trajet soient libre.

Grâce à tout ces outils, nous pouvons pleinement simuler une instance du réseau et la tester avec différents flux de capsules puis en tirer des conclusions sur sa capacité maximale, ses durées de trajet, son temps d’attentes aux gares, ...

 

Analyse et conclusion

 

            Différentes études menées sur le réseau numérique ont apaisé nos craintes quant à la viabilité du projet. L’algorithme représentant un fonctionnement simplifié de l’UrbanLoop mais toutefois proche de la réalité nous as permis d’apprécier bon nombre de réglage différents en termes de vitesse de capsules, longueur des portions d’accélération/décélération, flux maximaux, temps d’embarcation/débarcation, ...

            Quelques chiffres majeurs qui ressortent de cet étude :

- Il faut moins d’une seconde à une capsule pour trouver une opportunité de départ dans plus de 98% des cas.

- A une vitesse de 80 km/h, il peut circuler environ 3900 capsules en simultané dans le réseau sans engorgements.

- Il peut y avoir 100 000 trajets par jour soit le double des besoins actuels du réseau.

- Le temps de trajet moyen est d’environ 4 minutes et moins de 6 minutes suffisent pour presque tous les trajets.

 

 

L’interface graphique

Interface Graphique

Introduction

 

            L’objectif de l’interface graphique visuelle a été de mettre en évidence le déplacement des capsules le long des boucles, afin de visualiser leurs trajets effectués, et de mettre en application directe l’algorithme de routage mis au point. Cet affichage permet donc de juger efficacement et rapidement de la validité des solutions misent en œuvre, et donc de valider la crédibilité du projet.

 

Hypothèse de fonctionnement

 

            Le déplacement des capsules sera faîtes selon une discrétisation de temps, partant sur une base de 0.1 seconde. La création des capsules nécessitera les données suivantes venant de l’algorithme de routage : la gare de départ, la gare d’arrivée, et la liste des intersections qu’il faut prendre afin d’effectuer le chemin optimal.  La vitesse est constante dans la boucle principale. Les boucles, les stations et les intersections sont déterminées de façon fixe.

 

Problématique

 

            L’interface graphique devra être codée dans un langage tel que le rendu final soit le plus en adéquation possible avec les attentes des utilisateurs. Ce langage devra être également en cohérence avec celui utilisé pour l’algorithme de routage. Un moyen fiable pour tracer les chemins des boucles sur un fond de carte, tel que ces chemins soient bien superposés avec les voies présentent sur la carte devra être mis au point. Ces tracés de boucles seront bien mis en évidence, afin de visualiser rapidement la position des tubes de l’Urbanloop sur le réseau. Des stations doivent être incrustées le long du circuit, et les capsules passeront le long de ces stations. La vitesse des capsules devra être implémentée pour que la distance parcourue à chaque discrétisation de temps le long d’une boucle soit constante. Les capsules suivent le trajet qui est déterminé par l’algorithme de routage, afin d’atteindre leurs destinations. Le déplacement des points représentant les capsules sera visible en temps réel sur la carte. Un compteur de collision dans un but préventif, afin de vérifier la validité de la solution devra être implémenté. Enfin, des services tel que des zooms différents, ou un déplacement sur la carte seront implémentés, pour une expérience par l’utilisateur amélioré.

 

Solutions techniques principales

 

            Le langage utilisé sera le python, car c’est un langage haut niveau, simple d’accès et accessible à diverses modifications pour des personnes tierces. Ce langage possède aussi un système d’interface graphique développé qui permettra des fonctionnalités avancées pour l’interface avec le module Tkinter. Les cartes en fond d’écran seront téléchargées et placées automatiquement à partir de l’API Google Static Map. Afin de tracer les boucles, un service d’édition de trace GPS en ligne sera utilisé, afin de créer un fichier GPX contenant les longitudes et latitudes des points formant la boucle. Puis ces fichiers GPX seront lus, et à l’aide d’une projection de Mercator sur la carte en fond, et un réajustement des coordonnées pour correspondre à la fenêtre, la boucle sera tracée en adéquation avec la carte en arrière-plan. Des listes de coordonnées constituant les boucles seront créer, afin de ne calculer les coordonnées des chemins qu’une seule fois, et de faire transiter les capsules le long de ces traces, à l’aide de ces listes. Le positionnement des stations et des intersections avec leurs caractéristiques, sera facilement mise en place à l’aide d’interfaces graphiques tierces, afin de créer des fichiers CSV fixe, qui seront lu dans le programme principal. Chaque intersection sera examinée à chaque discrétisation de temps, afin de vérifier qu’elle est utilisée par une seule capsule. Dans le cas contraire, une collision sera notifiée. A chaque itération de temps dt, une récupération des capsules à créer à partir de l’algorithme de routage sera faîtes, et elles seront mise en circulation à cette itération, en utilisant les données nécessaires à leurs créations.

 

Principe de fonctionnement

 

            Pour mettre en place l’interface graphique, il faut tout d’abord mettre en place la trace des boucles sur une carte à l’aide d’un service en ligne. Le site web http://momolinux.free.fr/  permet de créer les points GPS caractérisant le chemin de la boucle. En effet à l’aide de clic de la souris, l’on place des points, qui se relient entre eux en suivant des routes existantes, ou en ligne droite suivant ce que l’on a choisis. Il ne faut pas fermer la boucle, cet aspect est géré dans le programme par la suite. Il faut par la suite exporter cette trace en fichier GPX, qui sera lu par notre programme, mais également en fichier JSON, pour pouvoir réimporter la trace sur le site, et pouvoir la modifier facilement. Ces fichiers seront lus dans le programme python Creation_Boucles. Pour qu’ils soient lus, il faut entrer les noms des fichiers GPX dans la liste Liste_Nom_Boucles du programme.

            

Schéma Creation_Boucle

            Ce programme a pour but de stocker des objets Boucle dans une liste, afin de les utiliser dans la suite du programme. La méthode de projection de Mercator a pour objectif de projeté les longitudes et latitudes en mètre sur Terre, puis on utilise la résolution en mètre par pixel, dépendant du zoom de la carte, pour retrouver les coordonnées en pixel dans la fenêtre. La méthode creation_coords lis les longitudes et latitudes, et crée deux listes : Chemix et Cheminy contenant les coordonnées de la fenêtre de la trace de la boucle. Cependant, les points sont situés à des distances variables. La méthode creation_chemin a ainsi pour objectif de recréer des listes Cheminx et Cheminy tel que tous les points soient équidistants d’une distance précision  déterminée dans la fenêtre d'initialisation. Finalement la méthode creation_boucle crée les objets boucles avec les informations calculées précédemment.

 

 

            Il faut ensuite télécharger les images avec le programme Creation_Images :

Schéma Creation_Images

            Ce programme lis les boucles dans les fichiers GPX, et regarde les dimensions de la fenêtre, pour savoir combien d’images, et quelles images il faut charger depuis l'ordinateur. Si l'image est inexistante dans l'ordinateur, elle est alors téléchargé. Ce procédé est géré par la méthode creation_image. Les images sont téléchargées à partir d’un service de Google, fonctionnant par l’intermédiaire d’un lien http, contenant les informations de zoom, de latitude_centre et longitude_centre de l’image. Ces longitudes et latitudes centrées sont déterminées par la méthode determination_LongLat_centre.

 

 

            Il faut ensuite créer les listes contenant tous les objets qui seront utilisés, ainsi que les variables indispensables au fonctionnement de l’application, ceci est géré par Creation_BDD.

Schéma Creation_BDD

            Ce programme crée les intersections et les gares à partir des fichiers csv, en lisant le numéro de ces objets, les boucles concernées par ces objets, et les coordonnés GPS en longitude et latitude de ces objets. Une méthode trouver_iteration, permet alors de positionner précisément sur la ou les boucles concernées, les objets, à partir des coordonnées GPS qui ont été lus. Une interface utilisateur permet également la rentrée simple et intuitive de variables élémentaire, comme le nombre de capsules maximum dans le système, leurs tailles d’affichage ou bien encore leurs vitesses. Toutes ces informations sont par la suite utilisées pour créer les objets, puis ces derniers sont stockés dans des listes pour être utilisés par la suite.

 

 

            Tous ces programmes sont appelés par un programme principal intitulé Capsules(Principal), qui gère les objets capsules, leurs déplacements, le placement des images, l’affichage de tous les objets, ainsi que des fonctionnalités comme pouvoir naviguer sur la carte.

Schéma Capsules

 

 

 

            D’autres programmes intitulés Creation_Intersections et Créations_Gares sont des interfaces graphiques ayant pour but de créer facilement de nouvelles gares et intersections, puis de placer les informations importantes de ces objets dans les fichiers Gares.csv et  Intersections.csv. Ces fichiers seront lus pour le programme principal. La méthode de création est simple, il suffit de cliquer avec le bouton droit ou gauche de la souris, le plus proche possible de ce que l’on vise, le programme se chargera de trouver la position exacte pour vous. Puis en cliquant sur le bouton Finis, les fichier csv sont créés.

 

Analyse et conclusion

 

            L’interface graphique est donc clair, et permet la visualisation rapide et simple du déplacement des capsules au cours du temps. Elle gère différents paramètres, et peut être modifié simplement par l’utilisateur si les informations sur lesquels se basent l’interface viennent à changer. Elle est colorée, et permet différentes fonctionnalités qui rendent l’expérience utilisateur plus agréable, comme la navigation sur la carte. Mais c’est aussi un formidable outil pour mettre en pratique l’algorithme de routage, et effectuer la visualisation crédible de la simulation numérique. Les indicateurs de collisions nous assurent également de la sécurité du système mis en œuvre. A ce titre, cette interface remplis parfaitement son rôle, et est un outil parfait pour la réalisation de notre projet.