OSRM : le chemin le plus court pour tracer la route !

J’ai longtemps été impressionné par les composants interactifs HTML qui permettent à l’internaute de tracer un chemin sur un fond cartographique tout en suivant le réseau routier disponible. Je le suis moins maintenant que j’ai moi-même codé le mien !
demo-osrm
(cliquez sur l’image pour voir la démonstration)

Et c’est bien le but de cet article que de vous montrer comment arriver à un résultat plutôt impressionnant en quelques dizaines de lignes de code… Évidemment, vous aurez tout de même besoin de quelques ingrédients essentiels pour réussir ce challenge. Dans mon cas, je me suis appuyé sur OpenStreetMap, OSRM et Ember.js.

OpenStreetMap : la données de base

OpenStreetMap (https://www.openstreetmap.org/) est un projet international collaboratif collectant des données cartographiques (routes, voies ferrées, rivières, bâtiments, etc.) sur la totalité du globe. Ces données restent libres d’utilisation et peuvent ainsi être utilisées non seulement pour l’affichage de fond cartographique, mais aussi pour des problématiques de calcul d’itinéraires.

OpenStreetMap ne fournit cependant que la donnée brute et des logiciels complémentaires doivent ensuite la mettre en valeur. C’est là que le projet OSRM (Open Source Routing Machine) entre en jeu !

OSRM : la valeur ajoutée

Description du projet

Le projet OSRM (http://project-osrm.org/) utilise les données OpenStreetMap pour fournir un certain nombre de services exploitant les données disponibles ainsi que leurs relations pour tirer parti du réseau routier.

Plus précisément, OSRM fournit 6 types de services :

  • Route : trouve la route la plus courte reliant les coordonnées fournies.
    • Nearest : retrouve les n routes les plus proches des coordonnées fournies.
  • Table : calcule la durée de la route la plus rapide entre les paires de coordonnées fournies.
  • Match : tente d’établir le mapping le plus plausible entre une trace GPS et le réseau routier sous-jacent.
  • Trip : tente de résoudre la problématique du voyageur de commerce, déterminant un plus court chemin visitant chaque point une et une seule fois.
  • Tile : génère des tuiles de vecteurs au format MapBox, généralement pour en construire une représentation graphique.

Trois modes de déplacement sont par ailleurs supportés : voiture, vélo et à pieds. Par contre, leur utilisation m’échappe un peu, la documentation ne s’intéressant visiblement qu’au mode ‘voiture’.

Mise en place du serveur à l’aide de Docker

Le backend d’OSRM est un serveur implémenté en C++. S’il est clairement possible de l’installer en le recompilant, il est largement plus simple de l’utiliser au travers de sa dockerisation.

La première chose à faire pour utiliser OSRM est d’aller télécharger les données OpenStreetMap de la zone sur laquelle on souhaite travailler. Pour cela, on peut se rendre sur le site GeoFabrik pour récupérer un fichier PBF qui sera à la base des traitements suivants. Attention à ne pas être trop gourmand, car le traitement de ces données demande une grande quantité de mémoire : comptez plus de 200Go de RAM pour avoir une couverture mondiale !

Dans notre cas, l’île de France (pbf Ile-de-France) constituera un échantillon largement suffisant. On peut aller jusqu’à la France entière si on est disposé à allouer de grosses zones mémoire.

Une fois ce fichier récupéré, il est nécessaire de le pré-processer pour en extraire le profil routier à l’aide de la commande (sous Linux ou Mac OSX):

docker run -t -v $(pwd):/data osrm/osrm-backend osrm-extract -p /opt/car.lua /data/ile-de-france-latest.osm.pbf

L’argument -v $(pwd):/data créé le répertoire /data au sein du conteneur Docker et rend le répertoire courant disponible sous ce chemin. Du coup, le fichier ile-de-france-latest.osm.pbf doit se trouver à cet endroit sur la machine hôte.

Les commandes suivantes permettent de finaliser les pré-traitements :

docker run -t -v $(pwd):/data osrm/osrm-backend osrm-partition /data/ile-de-france-latest.osm
docker run -t -v $(pwd):/data osrm/osrm-backend osrm-customize /data/ile-de-france-latest.osm

Le répertoire local doit maintenant contenir de nombreux fichiers générés à partir de celui précédemment téléchargé.

idf-processed

Enfin, le serveur OSRM est lancé sur le port 5000 par la commande :

docker run -t -i -p 5000:5000 -v $(pwd):/data osrm/osrm-backend osrm-routed --algorithm mld /data/ile-de-france-latest.osm

Tests du serveur avec Postman

Pour valider le bon fonctionnement du serveur, nous allons lancer quelques requêtes HTTP. Pour cela, je vais utiliser dans cet article Postman, mais les adeptes de Curl peuvent bien sûr s’en contenter.

Globalement, le format des requêtes à OSRM sont de la forme :

GET /{service}/{version}/{profile}/{coordinates}?option=value&option=value

Avec :

  • service parmi ‘route’, ‘nearest’, ‘trip’, ‘table’ et ‘tile’ (voir plus haut dans l’article),
  • version à ‘v1’ actuellement,
  • profile à ‘driving’, ‘biking’ ou ‘foot’ (je dois avouer n’avoir toujours utilisé que ‘driving’),
  • coordinates formulées sous la forme ‘longitude,latitude’.

Le format de retour est actuellement toujours du JSON.

Ainsi, un appel du type :

http://localhost:5000/nearest/v1/driving/2.388860,45.517037?number=2

Va rechercher les 2 points sur le réseau routier les plus proches de la coordonnée fournie dans les noeuds waypoints[].location.

Postman1

De la même manière, un appel du type :

http://localhost:5000/route/v1/driving/2.025,48.9862;2.05,48.90?steps=true&geometries=geojson

Va retourner un tableau de coordonnées suivant le réseau routier reliant les deux points fournis dans le noeud routes.geometry.coordinates.

postman2

Voyons maintenant comment exploiter ces deux services pour mettre en place notre composant graphique.

Un super composant graphique avec Ember.js

Tout lecteur assidu du Blog Ippon connaît mon engagement pour tenter de faire sortir Ember.js de sa position d’outsider vis-à-vis des Angular et React, à mon sens bien moins élégants dans leur approche du code et largement moins complets.

J’espère que cette implémentation, au-delà de démontrer un cadre d’utilisation du framework, vous fera franchir le pas de son utilisation. Elle est disponible dans mon Gitlab (https://gitlab.ippon.fr/bpinel/PathEditor.git), pour ceux qui ne souhaitent pas repasser par toutes les étapes de création du projet (même si une mise en place from scratch ne réclame qu’une dizaine de minutes).

Comme dans tout projet Ember, on va passer par Ember CLI et donc par une installation de celui-ci (via un ‘npm install -g ember-cli’). Ensuite on lance simplement les commandes :

    ember new PathEditor
    cd PathEditor

La structure du projet est ainsi créée et on va y ajouter les deux add-ons :

    ember install ember-paper
    ember install ember-leaflet

Ember-paper apporte différents composants graphiques suivant le Material Design de Google et les feuilles de style correspondantes. Ember-leaftlet encapsule le framework leaftlet qui lui-même nous permet notamment l’affichage de cartographie OpenStreetMap.

Le code de notre page applicative principale est lui-même créé par la commande :

    ember g template index

Son code se résume à l’affichage de notre composant :

{{! app/templates/index.hbs }}
{{#path-editor}}<h1>Tracez la route !</h1>{{/path-editor}}

Au passage, on va supprimer l’affichage du composant d’accueil Ember welcome-page dans la page application.hbs qui devient :

{{!-- The following component displays Ember's default welcome message. --}}
{{! welcome-page}}
{{!-- Feel free to remove this! --}}

{{outlet}}

Cependant, avant de créer le composant, nous allons ajouter à notre projet un service qui sera ultérieurement injecté dans le composant. L’objectif de ce service est de calculer, à l’aide de la formule de Haversine, la distance en kilomètres séparant deux coordonnées géographiques. Cela nous permettra ultérieurement d’afficher la distance globale couverte par le chemin tracé. Pour cela, on passe par la commande :

    ember g service geo-utils

Le contenu du fichier geo-utils.js créé est simplement :

// app/services/geo-utils.js
import Ember from 'ember';

export default Ember.Service.extend({
 // Implementation of the Haversine formula: https://en.wikipedia.org/wiki/Haversine_formula
 haversine(lat1, lon1, lat2, lon2) {
     let AVERAGE_RADIUS_OF_EARTH_METER = 6371000.0;

     let dLat = Math.PI*(lat1 - lat2)/180.0;
     let dLon = Math.PI*(lon1 - lon2)/180.0;

     let a = Math.sin(dLat / 2.0) * Math.sin(dLat / 2.0)
       + Math.cos(Math.PI*lat1/180.0) * Math.cos(Math.PI*lat2/180.0) * Math.sin(dLon / 2.0) * Math.sin(dLon / 2.0);

     let c = 2.0*Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

     let dist = Math.round(AVERAGE_RADIUS_OF_EARTH_METER * c);
     return dist;
   }
});

Maintenant que les bases du projet sont là, nous allons lancer la création d’un composant path-editor d’édition de chemin grâce à la commande :

    ember g component path-editor 

Cette dernière commande va créer 3 fichiers :

  • app/components/path-editor.js : le contrôleur du composant (en JavaScript),
  • app/templates/components/path-editor.hbs : le template de présentation du composant en handlebars,
  • tests/integration/components/path-editor-test.js : les tests associés à ce composant.

C’est mal mais nous n’irons pas modifier le fichier de test... Nous nous contenterons de compléter les deux autres.

On va commencer par le template de représentation :

{{! First div to display the HTML fragment provided to the component }}
<div>{{yield}}</div>
{{! Second div to display the current lattitude and longitude with binding attributes }}
<div>
 <p>Latitude: <code>{{lat}}</code> / Longitude: <code>{{lng}}</code></p>
</div>
{{! Third div to display the core of the component: buttons + map }}
<div class="flex-none layout-row">
 {{! left column to contain the button to interact with the path drawn on top of the map }}
 <div class="layout-column layout-align-center-center">
   {{! Button to reset the path}}
   {{#paper-button iconButton=true onClick=(action "deleteAll")}}{{paper-icon "cancel"}}{{/paper-button}}
   {{! Button to delete just the last point added to path }}
   {{#paper-button iconButton=true disabled=isEnabled onClick=(action "deleteLastPoint")}}{{paper-icon "reply"}}{{/paper-button}}
   {{! Button to delete the last segment added to the path }}
   {{#paper-button iconButton=true disabled=isEnabled onClick=(action "deleteLastSegment")}}{{paper-icon "reply all"}}{{/paper-button}}
   <hr/>
   {{! Display the full distance in km for the currently drawn path thanks to the bind attribute }}
   <div>{{distance}}</div>
 </div>
 {{! Right column to contain the map}}
 <div class="flex">
   {{! Event click and move are mapped on Ember action }}
   {{#leaflet-map lat=lat lng=lng zoom=zoom onMoveend=(action "updateCenter") onClick=(action "updatePolyline")}}
     {{! Map layer is using OpenStreetMap data }}
     {{tile-layer url="http://{s}.basemaps.cartocdn.com/light_all/{z}/{x}/{y}.png"}}
     {{! Marker layer is composed of a marker for the first point binded with startPoint attribute and a polyline layer binded with polyline attribute }}
     {{#if firstClick}}
       {{marker-layer location=startPoint}}
     {{/if}}
     {{polyline-layer locations=polyline}}
   {{/leaflet-map}}
 </div>
</div>

Le code de présentation est très largement commenté et sa structure vraiment très simple. On tire ici simplement parti du binding d’attributs pour afficher les coordonnées du centre, le marqueur initial, la polyligne et la distance en kilomètres de cette polyligne.

On doit également ajouter dans le fichier styles/app.scss la déclaration suivante permettant de donner la dimension souhaitée pour la carte (sans cela, rien ne s’affiche car la map reste à 0 pixel…) :

.leaflet-container {
   height: 600px;
   z-index: 10;
 }

Le gros du composant se trouve bien entendu dans le contrôleur dont le code est lui aussi abondamment commenté.

import Ember from 'ember';
export default Ember.Component.extend({
 // Inject the services containing the haversine formula
 geoUtils: Ember.inject.service('geo-utils'),

 // Attributes binding the center of the map and its zoom
 lat: 48.874885,
 lng: 2.291342,
 zoom: 16,
 // Ember array containing the polyline to be displayed on top of the map
 polyline: Ember.A([]),
 // Boolean indicating if the target for next action is the starter marker or a polyline
 firstClick: false,
 // Keep track of the indexes of the start of the different segments of the polylines
 previousIndex: [],

 isEnabled: Ember.computed('polyline.@each.lat', 'polyline.@each.lon', function () {
   if (this.get('polyline').length > 1){
     return false;
   } else {
     return true;
   }
 }),

 // Compute the full distance for the polyline by summing the distance of each segment
 distance: Ember.computed('polyline.@each.lat', 'polyline.@each.lon', function () {
   return this.get('polyline').map(t => (t.dist)).reduce(function(a,b) {return a+b;},0.0);
 }),

 startPoint: Ember.computed('polyline', function () {
   return this.get('polyline').get('firstObject');
 }),

 actions: {
   // The different action are rather self explanatory
   updateCenter(e) {
     let center = e.target.getCenter();
     this.set('lat', center.lat);
     this.set('lng', center.lng);
   },
   deleteAll() {
       this.set("polyline", Ember.A([]));
       this.set('firstClick', false);
     },
      deleteLastPoint() {
       this.get("polyline").popObject();
     },
      deleteLastSegment() {
       if (this.get("previousIndex").length > 0) {
         this.set("polyline", this.get("polyline").slice(0, this.get('previousIndex').pop()));
       }
     },
   updatePolyline(e) {
     let url;
     let ctx = this;
     if (!this.get("firstClick")) {
       // Calling OSRM for nearest road from the given coordinates
       url = "/nearest/v1/driving/"+e.latlng.lng+","+e.latlng.lat+"?number=1"
       Ember.$.ajax({
         url: url,
         type: 'GET',
         }).then((response) => {
         if (response.code == "Ok") {
           ctx.get("polyline").pushObject({
             lat: response.waypoints[0].location[1],
             lon: response.waypoints[0].location[0],
             alt: 0,
             dist: 0
           });
           ctx.set("firstClick", true);
         }
       });
     } else {
       let prevLat = this.get('polyline').objectAt(ctx.get('polyline').length-1).lat;
       let prevLon = this.get('polyline').objectAt(ctx.get('polyline').length-1).lon;
       // Calling OSRM for a polyline segment joining the given two coordinates
       url = "/route/v1/driving/"+prevLon+","+prevLat+";"+e.latlng.lng+","+e.latlng.lat+"?steps=true&geometries=geojson";
       Ember.$.ajax({
         url: url,
         type: 'GET',
         }).then((response) => {
         if (response.code == "Ok") {
           ctx.get('previousIndex').push(ctx.get('polyline').length+1);
           // Only consider the first route
           for (var i = 1; i < response.routes[0].geometry.coordinates.length; i++) {
             // Compute distance between coordinates
             let dist = this.get("geoUtils").haversine(prevLat, prevLon,
               response.routes[0].geometry.coordinates[i][1], response.routes[0].geometry.coordinates[i][0]);
             ctx.get("polyline").pushObject({
               lat: response.routes[0].geometry.coordinates[i][1],
               lon: response.routes[0].geometry.coordinates[i][0],
               alt: 0,
               dist:dist
             });
             prevLat = response.routes[0].geometry.coordinates[i][1];
             prevLon = response.routes[0].geometry.coordinates[i][0];
           }
         }
       });
     }
   },
 },
});

Bon, ce contrôleur fait une petite centaine de lignes. Mais quand on voit le résultat. C’est tout de même assez compact !

Il ne reste plus qu’à démarrer le serveur Ember en l’utilisant en mode proxy sur le serveur OSRM (les requêtes AJAX sont ainsi redirigées sur ce dernier, démarré dans docker et attendant les requêtes sur le port 5000). Cela se fait via la commande :

ember s --proxy http://localhost:5000

Reste à se rendre sur l’URL http://localhost:4200/ pour profiter pleinement de notre composant !

En matière de conclusion...

Les données cartographiques sont des données massives et complexes. Leur exploitation a longtemps constitué un challenge mobilisant beaucoup de ressources et d’énergie pour des résultats parfois bien pauvres.

En un peu plus d’une décennie, des solutions open source matures nous permettent maintenant de les exploiter à leur plein potentiel et parfois, pour les plus inventifs de servir de base à des produits fortement innovants : que serait Uber ou Waze sans la donnée de base que constitue le réseau routier ?

Reste à trouver la nouvelle idée géniale qui couplera certainement des sources de type Big Data avec ces données cartographiques de référence fortement structurées pour innover encore et encore !


Vous avez trouvé cette publication utile? Cliquer sur
Ippon
Ippon est un cabinet de conseil en technologies, créé en 2002 par un sportif de Haut Niveau et un polytechnicien, avec pour ambition de devenir leader sur les solutions Digitales, Cloud et BigData.

Ippon accompagne les entreprises dans le développement et la transformation de leur système d’information avec des applications performantes et des solutions robustes.

Ippon propose une offre de services à 360° pour répondre à l’ensemble des besoins en innovation technologique : Conseil, Design, Développement, Hébergement et Formation.

Nous avons réalisé, en 2017, un chiffre d’affaires de 31 M€ en croissance organique de 30%. Nous sommes aujourd’hui un groupe international riche de plus de 320 consultants répartis en France, aux USA, en Australie et au Maroc.
FRANCE Website LinkedIn