Blog bus et autocars Articles et actualités de Pysae pour les responsables marketing et les dirigeants de sociétés de transport de voyageurs
Retour sur 4 mois de R&D pour optimiser les algorithmes de Driver 2.0

Pour la version 2.0 de l'application conducteur (Driver), nous avons apporté de nombreuses améliorations visant l'expérience utilisateur qui ont été présentées dans cet article. Certaines sont bien visibles comme le travail sur les éléments d'interfaces. D'autres évolutions moins visibles sont tout aussi importantes pour offrir une utilisation fluide et optimale. C'est le cas de la refonte des algorithmes visant notamment à enrichir le mode hors ligne et à diminuer les latences de traitement des données liées aux caractéristiques des réseaux télécom.

La refonte des algorithme a nécessité un travail R&D d’ingénierie informatique complexe. Il a duré 4 mois et a été réalisé en interne directement par Pysae. Cet article explique le travail réalisé.

Driver en situation

Des calculs serveurs pour Driver 1.0

Dans la version 1.0, l'application conducteur (Driver) sert principalement de balise GPS, on utilise le capteur du smartphone pour récupérer la position que l'on envoie directement vers les serveurs de Pysae. Les serveurs se chargent ensuite de traiter cette information pour :

  • Identifier parmi les courses possibles celle sur laquelle le véhicule circule
  • Projeter la position du véhicule sur l'itinéraire de la course en traitant les cas complexes comme les allers-retours ou les boucles
  • Calculer les paramètres de progression : prochain arrêt, avance/retard etc.

Les résultats de ces calculs sont ensuite renvoyés à l'application conducteur qui peut mettre à jour l'interface avec les paramètres de progression. L'inconvénient majeur de cette solution est qu'en zone blanche, si l'on conservait bien les positions enregistrées pour les renvoyer dès que la connexion était rétablie, le conducteur est privé des paramètres de progression en temps réel, principal information retournée par l'interface. Cela pouvait générer de la frustration à l’utilisation et limiter l’adoption de l’application, point central du système Pysae Fleet.

Migration des serveurs vers le smartphone des calculs de progression

Il a donc été décidé de couper cette dépendance aux serveurs et de réaliser ces calculs directement dans l'application conducteur. Outre le fonctionnement amélioré en zone blanche, ce changement d'architecture permet également de réduire le temps de latence entre la réception d'une nouvelle position et le retour sur l'interface conducteur en éliminant l'étape de communication avec les serveurs.

Calculs smartphone

Si ces calculs étaient réalisés sur les serveurs c'est qu'ils sont assez intensifs. Une des étapes principales du processus est de comparer la trace du véhicule (ses positions relevées pendant les dernières 150 secondes, soit environ 30 points) avec les tracés renseignés dans le plan de transport. A titre d’exemple le réseau Lila comporte 158 tracés totalisant 43 759 segments (les tracés étants représentés par une suite de segments). Chaque nouvelle position GPS relevée doit être comparée à ces milliers de points de référence.

Compression des données pour s’adapter aux capacités des smartphones

Le premier problème qui se pose est celui du stockage de cet ensemble de données. Pour Lila, les descriptions des tracés et des courses représentent 6,1 Mo de données au format json. Pysae développant des applications hybrides, c'est l'API LocalStorage qui est utilisée pour stocker ces données. Cette API stocke des chaînes de caractère en UTF16, chaque caractère occupe donc 2 octets. En stockant directement les données on se retrouve donc avec un volume de 12,2 Mo dépassant les limites du LocalStorage.

Il est possible de mieux utiliser cet espace en appliquant un algorithme de compression d'une part et en stockant 2 octets dans chaque caractère d'autre part. C'est exactement ce que permet le module de compression des données lz-string faisant passer le volume à 1,3 Mo. Au lancement, l'application décompresse ces données et les charge en mémoire.

Compression des données

De nouveaux algorithmes spatiaux et intelligents

Les serveurs Pysae utilisent la base de données MongoDB. Une des raisons pour lesquelles cette base de données à été choisie est qu'elle fournit un index géographique. Cette fonctionnalité permet de récupérer efficacement les segments à proximité d'une nouvelle position GPS et de réduire le nombre de points à traiter de plusieurs dizaines de milliers à quelques dizaines.

Installer MongoDB sur les smartphones conducteurs n'est ni possible ni adapté, nous avons donc dû trouver une alternative pour ces requêtes spatiales. Elles ont finalement été implémentées à l'aide d'un R-tree. Dans cette structure de données les objets sont regroupés dans des zones rectangulaires de plus en plus grandes et organisés sous forme d'arbre de recherche.

Lorsqu’une nouvelle position est disponible, le R-tree est utilisé pour la comparer seulement aux segments à proximité. Sur le réseau Lila, on passe ainsi de plus de 40 000 segments à 150 en moyenne avec une recherche effectuée en 1 milliseconde environ dans le R-tree.

Recherche spatiale

Résultat d’une recherche R-tree (points vert) dans l’ensemble des segments (en blanc, extrémités en rouge) autour d’une nouvelle position GPS (point bleu)

Bilan : un effort R&D récompensé par une appli encore plus fluide et plus stable

L’effort R&D de 4 mois de travail est récompensé par une appli conducteur (appli Driver) encore plus fluide et plus stable. Les premiers retours des conducteurs sont très positifs. L’expérience utilisateur se trouve fortement améliorée grâce à aux nouveaux algorithmes intelligents intégrés directement dans l’appli smartphone. Pysae considère que cet investissement technologique donnera un vrai avantage concurrentiel supplémentaire à sa solution.

Grégoire Piffault's Picture

Grégoire Piffault