RoutaR, un outil de planification de tournées de véhicules performant et facilement adaptable, une solution de mobilité intelligente

Avec la crise sanitaire de la Covid 19, les commerces, contraints de fermer, se sont adaptés… et les clients aussi :  le commerce en ligne a littéralement explosé ! Mais qui dit plus de demandes auprès des services de livraison et des services à domiciles, dit aussi plus d’attente…Nous avons tous déjà dû rester bloqués des heures à la maison pour recevoir un colis, ou pour attendre le passage du plombier, prévu très précisément “entre 9h et 17h”...pour finalement ne pas le recevoir à temps ou devoir être absent lors du passage ! 

L’augmentation du recours au e-commerce a provoqué une surcharge de travail pour les chauffeurs et des plannings de service et livraison de plus en plus étriqués… De plus, beaucoup d’entreprises font face à la situation écologique actuelle, au coût de l’essence toujours plus élevé…. Elles cherchent à réduire les déplacements et à rentabiliser chaque trajet en générant des plannings optimaux, condensés et rentables ! Pour cela, ces plannings doivent respecter un ensemble de contraintes métiers, ce qui n’est pas une mince affaire… un outil adapté est donc nécessaire ! C’est ici que RoutaR, un outil de planification performant et facilement adaptable aux besoins des PME,  intervient…

Prérequis

Pour la lecture de ce document, la compréhension de certains termes techniques est nécessaire : 

• - Le format JSON : JSON est un format de fichier souvent utilisé en informatique. Similairement au format XML, il permet de transférer des données de manière structurée et documentée. Ce qui permet de rendre le fichier compréhensible par un humain et facilement intégrable dans une application.

• - Les microservices : Les microservices sont un style architectural pour les applications web. Chaque service est pensé pour être individuel, indépendant et spécifique à une tâche bien précise. Ce n’est qu’une fois assemblés qu’ils constituent l’application dans son entièreté. Chaque service a son propre cycle de vie et peut donc être déployé, mis à jour et géré de façon  plus légère et parfaitement autonome, sans perturber tout le système.

• - Une gaussienne : une gaussienne ou fonction gaussienne est une courbe exponentielle mathématique. Elle est facilement reconnaissable par sa forme en cloche.

  Pour qui ?

RoutaR est un outil qui  s’adresse de façon générale à toute entreprise rencontrant une problématique liée à l'optimisation du transport de personnes ou de marchandises et il concerne plus particulièrement les entreprises actives dans le domaine de 

• - la logistique (livraison de colis, logistique sur les chantiers, etc), 

• - le transport (covoiturage, service de navettes , taxis, bus scolaires, etc), 

• - les soins à domicile (infirmiers, infirmières, kinés, aides à domicile, aides-soignants, aides ménagers, etc), 

• - les services de livraison pour restaurant et magasins qui veulent livrer leurs produits eux-mêmes, 

• - les interventions et services à domicile (téléphonie, relevé de compteurs, plombiers, chauffagistes, etc)

• - l’économie circulaire (commerces locaux)

  Pour quoi faire ?

Vous désirez optimiser vos trajets en tenant compte du trafic routier à moindre coût ? 

RoutaR est fait pour vous ! Il s’agit d’une application web proposant sa propre solution de calcul de matrices de distances avec trafic et offrant un très bon compromis entre le coût et la qualité des données. 

L’application est directement déployable sur la majorité des systèmes informatiques et l'importance apportée à la performance de la plateforme ainsi que son architecture orientée microservice (vous trouverez plus de détails à ce sujet dans la section “Fonctionnement de RoutaR”) lui permettent de monter en charge rapidement et facilement afin de s'adapter au mieux à votre besoin.
Afin de résoudre vos problèmes d'optimisation, RoutaR s'appuie sur OscarR.CLBS, une librairie informatique proposant des algorithmes de recherche opérationnelle liés aux problèmes de routage et de planification. Ces derniers permettent de modéliser et résoudre une grande variété de problèmes de mobilité.

En effet, RoutaR solutionne plusieurs types de problèmes concernant ;

• - les taxis partagés

• - les livraisons de colis

• - les tournées de service (infirmiers, plombiers,...)

Mais il peut également répondre à tout type de besoin particulier telle que la collaboration entre entreprises ou le covoiturage.

De plus, RoutaR est capable de résoudre des problèmes intégrant de nombreuses contraintes métiers telles que :

• - des contraintes horaires : heure de passage, horaire des chauffeurs, durée de la tâche (soin, interventions techniques…), arrivée au plus tôt, arrivée au plus tard,...

• - des contraintes géographiques : embouteillages, coordonnées GPS…

• - des contraintes de capacité : nombre de places assises, volume maximal transportable, nombre de personnes à déposer ou à récupérer au point X,...

• - des contraintes de précédences : taxi, ordre de passage sans limitation…

Cette liste est cependant amenée à évoluer rapidement pour résoudre des problèmes encore plus complexes et de grandes tailles grâce à la flexibilité du moteur de recherche générique utilisé dans RoutaR et à la technologie Constraint Based Local Search.

  Les atouts de RoutaR

• - La généricité de l’application : vous pouvez traiter n’importe quel type de problème (contraintes de temps, de capacité,...) du moment que vous utilisez le format JSON pour définir le fichier que RoutaR va utiliser afin de trouver une solution qui respecte tout cela.

• - La réduction des coûts pour estimer le trafic : pour être le plus optimal possible, votre planning optimisé doit tenir compte du trafic et le coût de ce type de données est souvent très élevé.  Pour répondre à cette problématique, RoutaR intègre un mécanisme basé sur le machine learning représentant un bon compromis qualité/coût. A partir d'un ensemble restreint de données trafic achetées, il est capable d'estimer tous les réseaux de trajet se trouvant dans la zone couvertes par ces dernières.

• - Gagner du temps : RoutaR réduit le coût temporel des employés grâce à une meilleure organisation des plannings de véhicules de livraison ou de services. Ces derniers sont plus légers, réalisables et fiables pour les chauffeurs… et on sait tous que le temps, c’est de l’argent !

• - Gagner de l’argent : RoutaR augmente le chiffre d’affaires des entreprises en leur permettant de traiter de plus en plus de demandes et en leur proposant sa propre solution de calcul de matrices de distance avec trafic alors que, d'habitude, ce sont des données très onéreuses. RoutaR représente donc  le parfait compromis entre le coût et la qualité des données ! 

• -  Augmenter la satisfaction des clients : les colis et services sont délivrés en temps et en heure avec des tranches horaires réduites, plus besoin de prendre congé pour recevoir le chauffagiste !

• - L’architecture modulaire et flexible d’OscaR.CBLS : il s’agit du moteur de recherche opérationnelle utilisé dans RoutaR. Il vous permet de modéliser facilement un problème de routage en implémentant chaque contrainte métier séparément et en les sélectionnant indépendamment. Pour en ajouter une nouvelle, il vous suffit donc de la créer et elle sera directement utilisable. Si la contrainte métier est plus complexe, OscaR.CBLS dispose tout de même des mécanismes nécessaires pour la représenter. De ce fait, RoutaR est capable d’être adapté pour correspondre au maximum des besoins réels.

• - Déployable dans l’entreprise : chaque business peut avoir sa propre instance avec sa/ses contraintes spécifiques.

Fonctionnement de RoutaR

Pour générer un planning optimal, vous devez disposer des besoins de vos clients et formater tout cela dans un fichier JSON qui sera directement utilisable par RoutaR une fois que vous lui aurez envoyé le fichier. RoutaR va ensuite trouver une solution correspondant aux spécificités demandées  et vous la renvoyer en format JSON, en vue d’être intégrée avec un autre logiciel client (ERP). 

RoutaR est une solution complète qui contient :

• - 3 microservices (détaillés dans la section suivante).

• - le système de stockage open source REDIS (appelé “le cache” plus loin dans cette fiche) pour les matrices de distances car il est très léger et basé sur un système de clé-valeur qui est simple et facile à utiliser. 

• - Un démonstrateur développé en angular.

• - Toute une série de fournisseurs de données brutes qui servent à construire les matrices de distances. Vous avez notamment  :

  • GraphHopper, dont la version open-source a été intégrée dans un micro-service de RoutaR  et qui va utiliser des fichiers d’OpenStreetMap, des données cartographiques brutes totalement gratuites mais sans trafic (sans les embouteillages).

  • Google Maps et TomTom, des fournisseurs de données externes qui sont accessibles via leur API et moyennant paiement pour avoir des données cartographiques avec ou sans embouteillage.

  • RoutaR peut également utiliser Custom, un provider qui permet, via des endpoints (requêtes spécifiques) de stocker des données de trajet sans embouteillage récoltées grâce à des trackers présents dans les véhicules de l'entreprise en question. Ces données seront utilisées lors de l'optimisation. Ceci représente un gain de temps car il n’y a alors pas besoin de calculer les données avec graphhopper ou autre.

Les microservices

Comme vous pouvez le constater sur l’illustration ci-dessus, l’application RoutaR contient 3 microservices écrits principalement en Scala. 

L’architecture microservices est une architecture pour les applications web : les services y sont individuels, indépendants, spécifiques à une tâche et, une fois assemblés, ils constituent l’application. Chaque service  a son propre cycle de vie et peut donc être déployé, mis à jour et géré de façon  plus légère et parfaitement autonome, sans perturber tout le système.

Les microservices doivent être asynchrones, c’est-à-dire capable de répondre à plusieurs requêtes simultanément. Au delà de l’envie d’exploiter au maximum la puissance des processeurs récents, il y a plusieurs contraintes techniques à prendre en compte :

• - Il y a un nombre indéterminé de requêtes qui peuvent arriver dans ces services

• - Les microservices font de nombreux appels à des services externes (TomTom, Google Maps,...) et ils peuvent être très longs (il faut compter quelques minutes d'attente chez TomTom pour calculer une grande matrice par exemple).

• - Certaines opérations sont très longues : le training du modèle avec trafic, la résolution de problèmes d’optimisation…

Toutes ces contraintes nous poussent à mettre en place des services asynchrones afin de ne pas bloquer toutes les requêtes car l’une d’entre elles prend du temps à être traitée.

RoutaR possède donc un microservice appelé routar qui se focalise sur la résolution de problèmes. Il communique avec le deuxième microservice, matrix, pour obtenir une matrice de distances qui correspond au problème à résoudre.

Une matrice de distances, qu'est-ce que c'est ? les matrices de distances sont utilisées en cours d'optimisation pour réduire la longueur totale du trajet et s'assurer qu'on respecte les contraintes de temps. Une matrice prend en entrée une liste de coordonnées d'origines et une liste de coordonnées de destinations, et pour chaque paire d'origine et de destination, on calcule la distance et le temps du trajet. Quand on dit “une matrice 50X50” (pour 50 origines et 50 destinations), on a en réalité 2500 calculs à faire car on a 2500 couples origines-destinations. On appelle plus précisément cela une matrice carrée, c’est-à-dire une matrice du type (n, n), autrement dit une matrice à n lignes et n colonnes.

Lorsqu’on parle de matrice cubique dans cette fiche, c’est parce qu’on a rajouté la dimension du temps.

Le troisième microservice est le microservice path, pensé pour les aspects de démonstration, il sert à calculer le trajet précis reliant le point A et sa destination B empruntant telles ou telles rues... Il fournit un trajet détaillé qui pourra être affiché sur une carte.

Comment fonctionne le microservice Matrix ?

Voyons plus en détails comment fonctionne le microservice Matrix, que ce soit pour un calcul de matrice de distance sans trafic ou avec trafic. 

1. 1. Calcul de matrice de distance sans embouteillage 

Pour un calcul simple sans embouteillages, Matrix doit disposer en entrée  :

• - des coordonnées d’origines/de destination

• - d’une liste de fournisseurs ordonnée par priorité d’utilisation. On parle de liste car si un fournisseur ne trouve pas la distance entre tel ou tel point et qu’il renvoie une erreur, il faut pouvoir spécifier un fournisseur de secours pour pouvoir compléter la matrice. Bien que la particularité de RoutaR est de ne pas imposer de fournisseur pour que vous puissiez utiliser votre préféré (Google Maps, TomTom,...), GraphHopper est celui qui est utilisé par défaut car il génère des matrices de distances sans embouteillage gratuitement.

Le microservice va d’abord vérifier si des distances pré-calculées (des matrices de distances) sont enregistrées dans le cache (Redis) :  si le cache est vide, il faut faire une demande de matrice de distances. Pour cela, Matrix va utiliser GraphHopper (ou un autre premier fournisseur) qui va faire ce calcul gratuitement et renvoyer le résultat à Matrix. Matrix, avant de renvoyer la matrice à l’utilisateur ou à un service, va d’abord la stocker dans le cache Redis; si une demande est faite à propos de la même matrice, Matrix ira tout simplement la rechercher dans le cache. 

Si le résultat présent dans le cache n’est pas complet, Matrix envoie une demande à un autre fournisseur (ou “provider”) présent dans la liste de fournisseurs ( par exemple Google Maps) pour ce qu’il reste à calculer. Matrix va de nouveau rechercher dans le cache les données enregistrées par rapport à Google Maps et si le cache n’en contient pas, Matrix fait la demande de matrice et le fournisseur de données, Google Maps, envoie le résultat qui est fusionné avec le résultat précédent. Si le résultat final n’est toujours pas complet, Matrix passe de nouveau au fournisseur suivant de la liste et va de nouveau rechercher dans le cache les données enregistrées par rapport au nouveau fournisseur… et ainsi de suite.

Au final, Matrix fournit en sortie  : 

• - l’ensemble des origines,

• - les destinations,

• - la matrice  sans embouteillage qui a été calculée,

• - les détails sur la complétude de la matrice (les erreurs rencontrées, les fournisseurs utilisés).

1. 2. Calcul de matrice de distances avec embouteillage

Un des points forts de RoutaR est sa façon de gérer le trafic. Pour optimiser correctement les plannings de chauffeurs, il faut disposer de matrices de distances qui tiennent compte des embouteillages afin d’être au plus près de la réalité. En effet, rouler à minuit n’est pas vraiment la même chose que rouler en pleine heure de pointe… Or, à l‘heure actuelle, il n’existe pas de fournisseur de données de trafic gratuit, les prix peuvent être vite élevés ! 

Par exemple si vous prenez le cas des infirmiers à domicile : vous avez les adresses de 500 patients et le point de départ de 25 infirmiers (a priori leur domicile), vous obtenez une matrice de 525x525X48 (le chiffre 48 fait référence au nombre de demi-heures dans une journée), ce qui correspond à 13 millions de données à acheter… et cela revient à peu près à 132.000 euros chez Google Maps et à 6000 euros chez TomTom… Cela représente un certain coût !

 

1. a) Les coordonnées d'entraînement

RoutaR vous permet de réduire ce coût grâce à l’utilisation de données d'entraînement : il  va utiliser plusieurs points d’une même zone pour calculer la matrice de distance de cette zone, pour chaque demi-heure et en tenant compte du trafic, et, à partir de la détermination de cette petite matrice, RoutaR va estimer le temps de trajet  d’autres points dans les alentours.

Reprenons l’exemple des infirmiers à domicile. Si ceux-ci se trouvent dans la région de Namur, cela correspond à 38 communes. Nous avons donc  une matrice de distance pour ces 38 communes de 38x38x48 (pour tenir compte de toutes les demi-heures d’une journée également), ce qui correspond approximativement à 69.000 données…  L’ensemble coûte 700 euros chez Google Maps et 30 euros chez TomTom… Nous sommes bien loin du coût précédemment décrit ! 

Une fois que ces données moins chères sont acquises auprès d’un fournisseur de données, RoutaR dispose des données de trafic pour les 38 communes, il va pouvoir estimer le temps de trajet pour le problème à résoudre (l’optimisation pour les 500 patients et les 25 infirmiers).  Les données de ce calcul vont donc servir de coordonnées d'entraînement pour RoutaR qui dispose, en résumé :

1.  1) d’un ensemble de trajets connus (voir l’illustration 3 : les points noirs représentent les 38 communes de Namur).

   

2. 2) un ensemble de trajets inconnus (les points bleus sur l’illustration ci-dessous). RoutaR va utiliser la matrice et les données connues pour estimer le temps de trajet entre tous ces différents points. 

2. b) Apprentissage à partir des coordonnées d'entraînement

Voyons plus en détails comment les données d'entraînement vont permettre de déterminer le temps de trajet pour des points inconnus.

1. 1) Obtention de la matrice de distances

Une fois les coordonnées d'entraînement sélectionnées (les données achetées préalablement auprès d’un fournisseur), RoutaR dispose de la matrice de distances carrée complète pour chaque demi-heure. Autrement dit, RoutaR dispose, pour chaque couple de coordonnées, du temps de trajet entre les deux points pour chaque demi-heure d’une journée (voir illustration 5). 

 

Par exemple, vous avez 

• un temps de trajet de 25 minutes et 43 secondes  pour le trajet de A vers B à minuit, 

• un temps de trajet de 20 minutes et 32 secondes pour le trajet de A vers C à minuit, 

• un temps de trajet de 37 minutes et 32 secondes pour le trajet de A vers B à 06H30

• etc.,... 

Le tableau de l’illustration ci-dessous correspond aux résultats de chaque trajet par rapport aux données achetées pour notre exemple d’infirmiers à domicile en région Namuroise. Il s’agit dans ce cas d’une matrice cubique qui représente tous les temps de trajet aux différentes heures.  Ici, Matrix n’a pas fait les calculs mais a envoyé des requêtes vers le fournisseur de données pour les obtenir.

1. 2) Les gaussiennes

Une fois qu’il a obtenu toutes les matrices (une matrice pour chaque demi-heure), le microservice Matrix peut générer des gaussiennes (ou “fonctions gaussiennes”) pour chaque couple de points. Il y en a 3 par couple de coordonnées : 

• 1) une gaussienne pour le pic du matin, 

• 2) une deuxième pour le pic du midi 

• 3) une troisième pour le pic du soir. 

Les 3 gaussiennes sont fusionnées afin d’obtenir un schéma représentant l’évolution du temps de trajet pour un couple de coordonnées, et non le temps de trajet en lui-même ! Ce schéma représente la fonction des 3 gaussiennes et l’ensemble est stocké dans Redis, l’espace de stockage, pour être utilisé ultérieurement.

 

• Estimation des matrices de distances avec trafic pour les coordonnées de test

Rappelez-vous, ce qui nous intéresse dans notre exemple, c’est de déterminer la matrice de distances avec trafic pour les 25 domiciles des infirmiers et les 500 adresses de patients provenant de Namur (nous appellerons ces données les “coordonnées de test”). Pour  estimer cela, RoutaR va se baser sur  la matrice de distances connue concernant les 38 communes de Namur (ces données sont appelées “coordonnées d'entraînement”, voir les sections ci-dessus) car, comme expliqué précédemment, on connaît déjà le temps de trajet pour chaque couple de coordonnées d'entraînement ainsi que l’évolution du temps de trajet (grâce aux gaussiennes).  

Matrix va réutiliser le calcul utilisé pour les 38 communes et estimer le temps de trajet pour le problème à résoudre, pour cela : 

1. 1. RoutaR va d’abord calculer la matrice de distances sans embouteillage entre chaque paire de coordonnées de test (voir illustration 5). Cela peut se faire gratuitement avec GraphHopper par exemple.

2. 2. Ensuite, pour connaître l’évolution du temps de trajet entre le couple de points bleus présentés dans l’illustration-ci dessous, RoutaR va sélectionner un nombre k de coordonnées d'entraînement,  les plus proches de ces deux coordonnées de test (dans notre exemple, k =3).

   

3. 3. Puis, RoutaR récupère dans le cache les fonctions gaussiennes (les traits mauves dans l’illustration ci-dessous) pour chaque coordonnées d'entraînement (rappelez-vous, chaque fonction de gaussiennes représente une évolution du temps de trajet).

   

    4. RoutaR dispose donc de 9 fonctions gaussiennes connues et va faire la moyenne de l'évolution du temps de trajet pour chaque demi-heure afin d’obtenir l’évolution du temps de trajet entre les couple de points bleus. 

   1. Donc si on reprend notre exemple et qu’on prend la tranche horaire de midi (12h00), on aura 9 valeurs correspondant au 9 fonctions gaussiennes récupérées dans la base de données. RoutaR va faire la moyenne des ces 9 valeurs et stocker le résultat dans un tableau. On fait cela pour toutes les demi-heures de la journée et, au final, RoutaR représente l’évolution du temps de trajet grâce à la génération de 3 gaussiennes et d’un schéma de fonctions de gaussiennes.  

4. 5. Au final, pour connaître le temps de trajet entre nos deux points bleus à 12h00 avec embouteillage, il faut  faire : le temps de trajet sans embouteillage X l’évolution du temps de trajet estimé pour 12h00.

GraphHopper 

GraphHopper est un fournisseur d’accès focalisé sur l’optimisation des problèmes de routing. Il dispose de sa propre solution pour les calculs de distance,... et une partie de celle-ci est open source.  Les fonctionnalités basiques proposées sont : 

• le calcul de trajet point à point

• l’utilisation de différents modes de transports 

• l’exploitation de différents types de cartes dont Open Street Map (celles-ci sont gratuites et mises à jour quotidiennement).

 

Par contre, il ne permet pas de calculer gratuitement les matrices de distance. Pour cela, GraphHopper a été intégré à RoutaR et un service de calcul de matrices a été ajouté pour éviter d’envoyer des milliers d’appels vers GraphHopper. 

RoutaR permet également  de sélectionner les zones exploitées par GraphHopper (à l'échelle d'un pays ou d'une région) : dans la configuration du microservice, il suffit de définir les cartes OSM à télécharger et via un simple script, le microservice va télécharger les cartes, les fusionner et les préparer pour qu'elles puissent être utilisées par GraphHopper.

En résumé, voici les avantages de GraphHopper :

• gratuit

• nettement plus rapide que Google ou Tomtom

• prioritaire (dans le sens ou Google pourrait définir des priorités en fonction des clients)

• possibilité de dupliquer le service en cas de forte demande

Et ses inconvénients : 

• pas de trafic

• Si une des coordonnées est hors de la zone couverte par les cartes OSM, GraphHopper est incapable de fournir des information sur la distance.

  La démonstration en vidéo

Voici le replay du webinaire organisé par le Hub-C le 10 mars 2022 afin de faire une démonstration de RoutaR. La présentation est réalisée par Fabian Germeau, expert  en recherche locale basée sur les contraintes pour l'optimisation de tournées de véhicules au sein du CETIC.

Pour aller plus loin

Comme expliqué précédemment, l’outil utilisé pour optimiser les planning est le moteur de recherche opérationnelle OscaR.CBLS. Ce dernier est également développé au CETIC, plus précisément au sein du département COAL. Le routage de véhicules étant sa principale spécialité, c’est, dans un premier temps, cette fonctionnalité qui a été mise en avant au travers de RoutaR.

Cependant, différents domaines d’expertise sont également développés dans OscaR.CBLS. Il est également possible de résoudre des problèmes de type scheduling; il s’agit également de problèmes de planification, mais forts différents que ceux de type routage de véhicules. En effet, ils sont basés sur la notion de partage de ressources et non plus sur une notion d’optimisation de trajet.

Dans cette fiche, les fonctionnalités présentées sont celles en date de mars 2022. Bien évidemment nous avons la volonté d’ajouter de plus en plus de fonctionnalités afin de proposer un outil au plus proche de la réalité. Parmis celles-ci, on peut citer par exemple :

• l’optimisation multi-zone
• l’optimisation avec flotte hétérogène
• l’optimisation sur plusieurs jours
• le respect de préférences utilisateurs
• l’optimisation basée sur le coût du trajet et non plus sur la longueur
• …

Toutes ces fonctionnalités ont l’avantage de pouvoir être intégrées assez facilement grâce à la grande modularité d’OscaR.CBLS.

  Besoin d’une aide supplémentaire ?

Le Hub-C dans le cadre de ses services d’accompagnement numérique organise des workshops et groupes de travail en lien avec les nouvelles technologies de prototypages.  Vous souhaitez un accompagnement pour votre projet innovant ou vous souhaitez participer à un prochain workshop? N'hésitez pas à contacter un membre du Hub ! 
Vous avez une question spécifique à propos d’une fiche? Elles sont réalisées par les experts du CETIC (Centre d'Excellence en Technologies de l'Information et de la Communication), un  centre de recherche appliquée en informatique situé à Charleroi. Vous trouverez toutes les coordonnées ici.