FR:Open Source Routing Machine
Open Source Routing Machine | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Auteur : | Dennis Luxen | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Licence : | BSD | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Plateformes : | Linux, macOS et FreeBSD | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Version : | 0.3.6 (2013-10-14) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Langue : | anglais | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Site Internet : | http://project-osrm.org/ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Code source : | https://svn.project-osrm.org/svnroot/routed/osrm/ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Langage de programmation : | C++ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Routing server, Contraction Hierarchies routing, extremely fast |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Open Source Routing Machine (OSRM) calcule les plus courts trajets d'un graphe routier. Il a été conçu pour fonctionner avec les données cartographiques du projet OpenStreetMap
Détails du projet
Contrairement à la plupart des serveurs de routage, OSRM n'utilise pas l'algorithme A* pour calculer le plus court chemin, mais The contraction hierarchies . Il en résulte des temps de requêtes très rapides, généralement inférieure à 1 ms pour les ensembles de données comme l'Europe, faisant OSRM un bon candidat pour les applications et sites sensibles routage sur le Web.
OSRM est actuellement maintenu par Dennis Luxen.
Caractéristiques
- Routage très rapide
- Instructions de conduite rudimentaires
- Fortement portatif
- Le format de données simple, il est facile d'importer des ensembles de données personnalisés à la place de données OpenStreetMap
- Faisant usage d' interdictions de tourner
Projet : vérification et amélioration du graphe routier des 16 premières agglomérations de Rhône-Alpes
Présentation du projet
Dans le cadre d'une unité d'enseignement sur la gestion des données, les étudiants du Master 2 SIG de Saint-Étienne ont mené un projet de production collaborative sur OpenStreet- Map (OSM). L'objectif était d’améliorer les incohérences d'itinéraires à partir du moteur Open Source Routing Machine (OSRM) développé par la communauté OSM, en ne réalisant, lorsque c'est nécessaire, que des modifications topologiques, géométriques, sémantiques et attributaires. L'algorithme utilisé par OSRM n'a donc pas été modifié car ne faisant pas partie de ce projet. Les itinéraires étudiés sont ceux reliant les 16 plus grandes agglomérations de la région Rhône-Alpes.
Méthodologie
La méthodologie employée pour ce projet s'articule autour de grands points :
- La constitution de la liste des 16 premières plus grandes agglomérations, constituant l'ossature primaire du graphe routier de Rhône-Alpes.
- Calculs comparatifs d’itinéraires avec OSRM, GMaps, ViaMichelin : essentiellement, une comparaison d'écarts de temps et de distance.
- Recensement des incohérences sur les itinéraires OpenStreetMap
- Regroupement des incohérences (sémantiques, topologiques, géométriques et attributaires)
- Réalisation des différents tutoriels nécessaires au travail
- Amélioration du graphe routier via l'éditeur ID d'OSRM
Vous trouverez tous les documents expliquant plus précisément la démarche et les modifications opérées sur le lien Méthodologie
Les 16 plus grandes agglomérations de Rhône-Alpes
Nom de l'unité urbaine | Population |
Lyon | 1 509 766 |
Grenoble | 494878 |
Saint-Etienne | 372 967 |
Chambéry | 174833 |
Annecy | 153288 |
Genève-Annemasse (partie française) | 145 507 |
Valence | 126 832 |
Vienne | 91796 |
Roanne | 79 159 |
Thonon-les-Bains | 67 350 |
Bourg-en-Bresse | 58 356 |
Saint-Just-Saint-Rambert | 57 629 |
Romans-sur-Isère | 54 758 |
Bourgoin-Jallieu | 52 225 |
Montélimar | 50415 |
Sallanches | 44 643 |
- Données extraites de l’INSEE pour le recensement de la population de 2007
Bilan
La comparaison des itinéraires du routeur OSRM et des deux grands routeurs du web montre plusieurs points :
- Les écarts de distance-temps sont assez faibles pour les 16 villes analysées en Rhône-Alpes : OSRM donne des valeurs similaires aux calculateurs d'itinéraires classiques.
- Les écarts existants sont dus à des incohérences de données géométriques, d'itinéraires (suite à des modifications de voiries), de topologies ou de valeurs attributaires (vitesse de circulation dans certains tronçons).
- Les grandes villes sont mieux renseignées mais l'écart entre Lyon et Sallanches est malgré tout assez faible.
- Les incohérences relevées ne viennent pas toujours d'OSRM, qui a souvent proposé des temps d'itinéraires et des trajets plus judicieux.
- Une très grande flexibilité d'OSRM via trois modules d'édition et une communauté très présente.
Liens
- OSRM online Demo Web server (Planet-Wide, mise à jour toutes les 12 heures)
- OSRM website and wiki
- OSRM manual
- Mailing list