Introduction : un calcul des itinéraires très rapide

Je viens enfin de mettre en ligne la recherche d'itinéraire optimisée sur laquelle j'ai  travaillé cet été (je vous rassure, je n'ai pas fait que ça loin de là). Les itinéraires sont maintenant utilisables même quand le réseau est très dense comme dans Paris : avant plusieurs dizaines de secondes de calcul n'y suffisaient parfois pas, depuis la mise à jour le calcul dure rarement plus de 100ms.

Cette mise à jour est l'occasion de faire le point sur les technologies utilisées.

L'Open Data et le format GTFS

La vague de l'Open Data, c'est à dire les données gratuitement partagées par les entreprises et les administrations, a poussé certaines régies de transport à mettre à disposition l'ensemble de leurs données sour le format GTFS.

Le format GTFS, pour General Transit Feed Specification, est un format proposé  par Google pour décrire un réseau de transport : arrêts, circuits, horaires, etc..

Ma démarche est de regrouper dans la même base, les données de  plusieurs régies de transport, afin de proposer des itinéraires de transports en commun qui les prennnt tous en compte. Pour le moment, j'ai intégré les données de :

• Transilien
• TER
• Intercité
• RATP (bus et métros)

C'est une base de départ ; j'ai vu que plusieurs grandes villes françaises ont mis à disposition leurs données de transports en commun, que j'intégrerais bientôt.

Ca fait déjà une base de 33000 arrêts techniquement parlant, représentant environ 6000 stations réelles, et plus de 14 millions de couples arrêt/horaire.

La base de données avec Mysql

 Le format GTFS suit la logique des bases de données relationnelles. Ayant l'habitude d'utiliser Mysql (souhaitant bientôt passer à son clone MariaDB, mais c'est une autre histoire), j'ai décidé de rentrer ces données dans une base construite à cet effet, et suivant de près le format GTFS.

Une fois les données rentrées, des scripts SQL corrigent quand même certains défauts de format des données, par exemple la colonne stop_sequence qui part des fois de 0 et des fois de 1, et la colonne direction_id qui n'est utilisée par personne (alors qu'on en a besoin).

L'utilisation de la base de données est parfaitement adaptée aux besoins pour afficher les gares par recherche et géolocalisation, trouver les prochains départs d'une gare et les trajets. Après avoir travaillé les requêtes et indexé les tables, l'affichage de n'importe quelle donnée est suffisamment rapide, et on est peu limité par la taille des données, la base actuelle faisant 1,6G sur le disque ; on  peut donc prévoir d'en ajouter et d'accumuler la provenance des données.

HTML5, Javascript et NodeJS

Comme mon but était de construire un site internet qui soit aussi une application pour smartphones et tablettes, le choix de la technologie HTML5 et Javascript était évident. L'affichage n'est plus proposé par le serveur mais totalement mis en forme par des scripts côté client ; la logique MVC (Modèle-Vue-Contrôleur)  est facilement respectée et après le chargement de scripts au démarrage, seules les données sont transmises du serveur au client.

Du point de vue de la mise en forme, un design adaptatif est mis en place (responsive design) ce qui veut dire que la mise en forme varie en fonction de la taille de l'écran. Le logiciel s'adapte ainsi aux ordinateurs, smartphones et tablettes. Comme j'ai recherché la clarté et la simplicité dès le début, le site est particulièrement adapté aux smartphones.

Côté client, j'utilise la librairie Jquery pour manipuler plus facilement l'affichage sur le navigateur.

Côté serveur, le choix de NodeJs me permet d'utiliser le même language de programmation que côté client. Le caractère asychrone de NodeJS le rend particulièrement efficace pour traiter et renvoyer les données demandées. Pour le moment, NodeJS est caché derrière un proxy avec le serveur Web Apache qui s'occupe des autres sites sur ce serveur.

La limite du système pour le calcul des itinéraires

 Le système mis en place pour afficher les gares et les prochains départs fonctionnant à merveille, je me suis lancé dans le calcul d'itinéraires. Ce projet très technique m'intéressait et je vous voulais savoir si je pourrais tout seul proposer un calcul assez rapide sur l'ensemble des données regroupement plusieurs réseaux de transport.

J'ai fait une première tentative en juin dernier d'Algorithme de Dijkstra amélioré en Algorithme A*, en utilisant une heuristique basée sur la distance à vol d'oiseaux avec la destination, avec NodeJS en javascript et en appelant les données sous Mysql. Cette recherche d'itinéraire fonctionnait correctement sur le réseau Intercité et TER en province, mais le temps de calcul était catastrophiquement long sur Paris, à cause de la densité et de la proximité des stations de bus et de métro (résultat trouvé en plusieurs dizaines de secondes dans le meilleurs de cas). Le fait que la recherche soit dépendante du temps m'empêchait d'utiliser d'autres améliorations comme une recherche bi-directionnelle.

Je me suis alors efforcé de trouver un meilleur algorithme afin de réduire la quantité de calcul. C'est évidemment encore plus important que de rechercher un langage et un accès aux données plus rapides. Après avoir lu plusieurs papiers en français et en anglais sur le sujet, j'ai décidé de réécrire le calcul en plusieurs étapes :

• Algorithme Dijkstra bidirectionnel et amélioré sur une version simplifiée et non dépendante du temps du réseau,
• Algorithme de Dijkstra en utilisant le résultat de la recherche précédente comme base limitative et comme heuristique.

Il sera intéressant de faire un article détaillé sur l'algorithme que j'ai construit, mais pour en revenir aux technologies, le côté asynchrone de NodeJS si utile pour le côté serveur commençait à m'ennuyer pour l'écriture des algorithmes ; et pour ces raisons ainsi que pour des raisons de rapidité j'ai décidé de passer à un langage compilé.

C++ comme module NodeJS

Le langage C++ permet d'éviter les questions ennuyeuses de gestion de la mémoire du C avec des objets, des tableaux dynamiques (vector) et des index clé-valeur (map) , tout en étant très rapide puisque compilé. J'ai donc écrit l'algorithme dans ce langage, en allant encore chercher les données dans la base Mysql.

Après avoir réalisé les algorithmes en C++ et testé dans un programme de test, je les ai interfacé comme module NodeJS asynchrone. Ainsi, j'utilise ces fonctions comme si c'étaient des objets NodeJS, directement à partir du Jabascript.

Là, miracle, le calcul des itinéraires commencait à être viable ; un trajet de banlieue à banlieue en passant par Paris avec deux correspondances se trouvant souvent en une seconde environ, contre plusieurs dizaines auparavant. Mais les trajets non triviaux à l'intérieur de Paris restaient catastrophiquement longs à trouver.

La recherche dans une base de données est très adaptée pour sortir des données et les afficher, mais pour des calculs qui nécessitent plusieurs milliers de requêtes compliquées en série ce n'est pas assez efficace. On ne gagne presque rien en mettant toutes les tables en mémoire vive.

Comme dernière étape, j'ai donc décidé de charger toutes les données en mémoire vive au lancement du serveur. Cette méthode comporte des défauts : temps de démarrage dû au chargement (environ 3 minutes actuellement), taille des données prises en compte qui dépend de la mémoire vive qu'on a. Mais une fois le serveur lancé, les données se référençant par pointeur les unes aux autres, la recherche est enfin très rapide comme vous pouvez le tester vous même : moins de 100ms dans la plupart des recherches.

Récapitulation et conclusion

Pour la recherche d'itinéraires, nous avons réussi deux changements d'échelle dans les temps de calcul, à chaque étape divisés par 100 :

• Amélioration de l'algorithme en utilisant un réseau très simplifié et non dépendant du temps (moins de noeuds et moins d'arêtes entre les noeuds) comme première étape de calcul,
• Chargement des données en mémoire vive et utilisation du langage C++ pour les calculs .

Une petit diagramme pour récapituler tout ça pour finir ; cliquez dessus pour l'agrandir de façon lisible !

La gestion des itinéraires arrive en bêta !

Le logiciel trouve rapidement les itinéraires s'ils ne sont pas trop complexes.

L'algorithme utilisé est Dijkstra amélioré ou Algorithme A*. Il demande à être amélioré, mais fonctionne déjà pour la plupart des cas.

L'itinéraire utilise jusqu'à 7 transferts et autorise 1km à pied maximum cumulé sur tout le voyage.

Les correspondances prennent au minimum 2min chacune, plus si le temps est fourni par la régie ou si les stations ne sont pas au même endroit.

Rappel  : pour le moment, le site contient les horaires de la RATP, SNCF Transilien, TER et Intercités. Pas d'horaires de TGV possibles malheureusement.. par contre d'autres villes pourront être prises en compte plus tard.

A utiliser sans réserves !

Nouvelle fonction : on peut maintenant choisir la date et l'heure des départs de la gare choisie.

La base de donnée n'a pas les horaires sur plusieurs années, seulement quelques mois ; une recherche sur une date trop éloignée ne donnera donc rien..

Voici les nouveauté de ce soir :

• un petit lien "Suivants" permet d'afficher plus de départs de l'arrêt selectionné.
• Dans la liste des départs d'une gare, on préçise le jour de départ. Ainsi, passé minuit, le jour change.

Voici le blog du site et logiciel nommé (pour le moment) "Gares et Horaires",  horaires.vef.fr

Le but de ce logiciel et de proposer un site simple, rapide et fiable pour tous vos transports en commun en France, en exploitant les données OpenData des régies de transport.

Voici les transports pris en compte à ce jour :

• Bus, Tram, Métros et RER RATP dans Paris
• RER et trains transiliens SNCF
• trains SNCF TER et Intercités

Pour le moment, on peut visualiser les gares proches, chercher une gare, afficher les prochains départs et les suivants et afficher le détail d'un trajet.

Ce blog annoncera les nouveauté, et sera l'occasion de revenir sur des choix techniques ou les données OpenData en général.