OSRM - Open Source Routing Machine

Introduction à OSRM

1. OSRM
Open Source Routing Machine
SotM-France 2016
Clermont-Ferrand
Frédéric Rodrigo – CC BySA 2016

2. Chemin le plus court
●Algorithme de Dijkstra
–1959
●A*
–1968
–Dijkstra guidé
https://en.wikipedia.org/wiki/File:Dijkstras_progress_animation.gif
https://commons.wikimedia.org/wiki/File:Astar_progress_animation.gif

3. Chemin le plus court
●Contraction de Hiérarchies
–2008 Karlsruhe Institut für Theoretische (KIT)
–Pré-calculer les raccourcis
https://www.mjt.me.uk/posts/contraction-hierarchies/

4. État de l'art
Route Planning in Transportation Networks http://arxiv.org/abs/1504.05140

5. Stratégie
Vitesse
réponse
Configuration
dynamique
CH
A*
OSRM (KIT, MapBox)
Valhalla (Mapzen)
(double A* multi-niveau) GraphHopper

6. OSRM
●API v4 → v5
●KIT
●MapBox

7. OSRM / route
●http://router.project-
osrm.org/route/v1/car/
-76.9964,38.89711;-
77.03647,38.90840
{
"code":"Ok",
"routes":[{
"legs":[{
"steps":[],
"duration":323.9,
"distance":4507.3
}],
"geometry":"}allF`i}tMhLArDxLGhNqJj[M|
HuEzEaK~[eRvx@gD@EpMuJn`@mCrIuAfBHhAx@n@?lXePA",
"duration":323.9,
"distance":4507.3
}],
"waypoints":[{
"name":"7th Street Northeast",
"location":[
-76.996167, 38.897111
]}, {
"name":"16th Street Northwest",
"location":[
-77.036521, 38.9084
]}
]}
step
leg
route

8. OSRM / table
●http://router.project-
osrm.org/table/v1/car/
-76.9964,38.89711;-
77.03647,38.90840
{
"code":"Ok",
"durations":[
[0, 323.9],
[344.2, 0]
],
"destinations":[{
"name":"7th Street Northeast",
"location":[
-76.996167, 38.897111
]}, {
"name":"16th Street Northwest",
"location":[
-77.036521, 38.9084
]}
],
"sources":...
}

9. OSRM / match
●http://router.project-
osrm.org/match/v1/ca
r/-76.9964,38.89711;-
77.03647,38.90840

10. OSRM / trip
●http://router.project-
osrm.org/trip/v1/car/-
76.9964,38.89711;-
77.03647,38.90840;7
6.9878,38.8246
●Problème du
voyageur de
commerce
{
"code":"Ok",
"trips":[{
"legs":[{
"summary":"",
"duration":344.2,
"distance":4536.7
}, {
"summary":"",
"duration":323.9,
"distance":4507.3
}],
"geometry":"ohnlFfeeuMb\\BBw~@xCyMfD?
L}M|Lse@}@{DQ_D?ilBjR?hLArDxLGhNqJj[M|
HuEzEaK~[eRvx@gD@EpMuJn`@mCrIuAfBHhAx@
n@?lX",
"duration":668.1,
"distance":9044
}],
...

11. OSRM / tile
http://map.project-osrm.org/debug/

12. Mise en place
●Facile !
●Profils (car, bicycle,
foot)
●osrm-extract
●osrm-contract
●osrm-routed
speed_profile = {
["motorway"] = 90,
["trunk"] = 85,
["primary"] = 65,
["secondary"] = 55,
surface_speeds = {
["grass"] = 40,
["unpaved"] = 40,
properties.u_turn_penalty = 20
properties.traffic_signal_penalty = 2
function node_function (node, result)
function way_function (way, result)
bridge, tunnel, oneway, lanes...

13. OSRM en production
●Rapide : beaucoup de mémoire
●Un serveur OSRM par profil
●Mise à jour données sans interruption de
service
●Utilisable en lib sans serveur
–maps.me
–binding node.js

14. Futur
●Court terme
–Résultat pas uniquement au plus rapide
–Matrice de temps et de distance
–Respect de restriction (acces=destination)
●Possible à long terme
–Isochrone
–Multi-profil