OSRM : routage haute performance open-source

Publié le • ≈ 15 min de lecture

1. Introduction et historique

L’Open Source Routing Machine (OSRM) est apparu en 2011 sous l’impulsion de l’équipe de [Project OSRM.org](https://project-osrm.org/) et d’un financement initial par la fondation The DAT Group. Construit en C++ pour la vitesse, OSRM a pour vocation de répondre à des millions de requêtes de routage en quelques millisecondes, grâce à l’algorithme de Contraction Hierarchies (CH).

Contrairement aux API propriétaires (Google Directions, Mapbox), OSRM peut être déployé entièrement en interne, garantissant la souveraineté des données et l’absence de coûts par requête. Son code source, publié sous licence BSD, est maintenu sur GitHub (repo officiel).

2. Installation et préparation des données

OSRM repose sur des cartes OSM au format PBF et un préprocesseur qui génère un graphe optimisé.

  1. Prérequis : Ubuntu 20.04+, build-essential, CMake, libboost.
  2. Compilation :
git clone https://github.com/Project-OSRM/osrm-backend.git
cd osrm-backend
mkdir build && cd build
cmake ..
cmake --build . -- -j4

3. Import des données :

osrm-extract -p ../profiles/car.lua your-region.osm.pbf
osrm-contract your-region.osrm

Vous obtenez trois fichiers principaux :

  • your-region.osrm.nodes
  • your-region.osrm.edges
  • your-region.osrm.hsgr (graphe contractionné)

Enfin, lancez le serveur :

osrm-routed --algorithm mld your-region.osrm

Le paramètre --algorithm mld active le nouvel algorithme Multi-Level Dijkstra pour même plus de performance.

3. Contraction Hierarchies (CH)

L’algorithme CH est au cœur de l’extrême rapidité d’OSRM (Delling et al., 2010). Le principe :

  1. Contraction : chaque nœud du graphe est supprimé selon un ordre hiérarchique, en ajoutant des arêtes « shortcuts » pour préserver la distance la plus courte.
  2. Query : pour calculer un itinéraire, on réalise deux Dijkstra bidirectionnels sur le graphe simplifié, ce qui réduit drastiquement le nombre de nœuds explorés.

Le prétraitement (contraction) peut prendre plusieurs heures pour une région entière, mais il s’effectue une fois. Les requêtes ensuite ne durent que quelques millisecondes, même sur de grandes étendues.

4. API et endpoints principaux

OSRM propose plusieurs services REST clés :

  • /route : calcul d’itinéraire entre plusieurs points.
  • /table : matrice de distances ou durées.
  • /nearest : point OSM le plus proche d’une coordonnée.
  • /match : corrige une trace GPS (map matching).
  • /trip : résoudre le problème du voyageur de commerce (TSP).

Exemple de requête simple :

GET http://localhost:5000/route/v1/car/2.3522,48.8566;2.2945,48.8584?overview=full&steps=true

Réponses JSON détaillées incluent :

  • routes[0].distance (en mètres)
  • routes[0].duration (en secondes)
  • routes[0].geometry (polyline)
  • routes[0].legs[*].annotation (vitesse, segments)

Pour tous les paramètres, référez-vous à la documentation officielle : OSRM API Docs.

5. Fonctionnalités avancées

Au-delà du routage de base, OSRM supporte :

  • Distance Matrix for batches of origin–destination pairs via /table.
  • Map Matching to snap raw GPS tracks to the road network via /match.
  • Trip Optimization (/trip) solving the TSP using heuristics.
  • Custom Profiles in Lua (profiles/car.lua) to adjust speeds, restrictions, and turn penalties.

Chaque fonctionnalité peut être parallélisée et containerisée pour des traitements en batch ou en temps réel.

6. Performance & scalabilité

Pour des environnements à fort trafic (> 100 000 requêtes/jour) :

  • Utilisez l’algorithme MLD (--algorithm mld) pour un prétraitement plus rapide (Multi-Level Dijkstra).
  • Déployez plusieurs instances derrière un load-balancer (NGINX, Traefik).
  • Mettez en cache les requêtes communes dans Redis ou CDN.
  • Exploitez Prometheus et Grafana pour surveiller latence, erreurs et QPS.

Des benchs internes montrent un temps moyen de 3 ms par route sur un graphe européen, contre 50 ms pour un Dijkstra classique.

7. Intégration front-end

OSRM fournit un plugin pour Leaflet Routing Machine :

L.Routing.control({
  router: L.Routing.osrmv1({ serviceUrl: 'http://your-osrm-server/route/v1' }),
  routeWhileDragging: true
}).addTo(map);

Vous pouvez également consommer les endpoints API directement depuis un front React/Vue avec fetch/Axios, pour construire des interfaces de planification de trajets riches.

8. Utilisation mobile & offline

Pour des applications Android/iOS offline, intégrez :

  • osrm-backend compilé en native, ou osrm-rust pour ARM.
  • MBTiles pré-générées pour le fond de carte
  • Un service local OSRM via JNI ou gRPC pour le routage embarqué.

Cette approche est idéale pour les flottes de terrain, la logistique ou le secteur de la sécurité civile.

9. Cas d’usage & retours d’expérience

Exemples concrets :

  • Service de covoiturage : calcul d’itinéraire optimisé en millisecondes pour proposer des correspondances précises.
  • Plannification de tournées : intégration du solver VRP d’OSRM pour réduire de 15 % les coûts logistiques.
  • IoT et géofencing : détection d’entrée/sortie d’une zone géographique en temps réel avec /closest.

Ces projets ont démontré la robustesse d’OSRM en production, avec des clusters > 10 nœuds gérant ensemble plus d’un million de routes quotidiennes.

10. Conclusion & prochaines étapes

OSRM demeure la référence du routage open-source pour des besoins extrêmes de performance. Associé à OpenStreetMap pour les données et à GraphHopper pour des profils multi-modal, il compose un stack géospatial complet.

Pour démarrer :

  1. Installer OSRM-backend et importer un extrait OSM.
  2. Configurer un profil Lua adapté à votre flotte.
  3. Déployer en container et monitorer via Prometheus/Grafana.

← Retour au dossier principal

← Retour à l’accueil