Technote: OSRM vs Gosmore fusillade

Nous avons besoin d'un tas de routes point à point pour notre système d'itinéraire multi-stop. Comme nous utilisons OpenStreetMap comme source pour ce, nous ';avons mis en place une comparaison entre deux systèmes de routage OSM bien connus: Gosmore et OSRM.

Tout d'abord, nous avons mis en place ce test pour nos propres besoins. Il ';ne est pas destiné à être représentatif pour tous les besoins de routage dans toutes les situations. Les résultats et les conclusions ne ont pas besoin d'être valable pour vous. Si vous comprenez cela et acceptez, continuer la lecture.

Pourquoi: matrice de distances

Pour trouver le plus rapide itinéraire avec de multiples arrêts, nous devons savoir durées de voyage A-to-B entre tous les points. Pour visiter quatre destinations d'un point d'origine, nous avons besoin pour acheminer 5 x 4 = 20 jambes. Cette matrice de distance de Voyage croît de façon exponentielle. Avec 40 destinations, il ';s 41 x 40 = 1,640 jambes, avec 80 destinations 6,480 jambes, et ainsi de suite.

Si, combien de temps votre navigation automobile prendre pour trouver la voie vers une destination? Se il ';s rapide, il le fera en une seconde. Cela semble rapide, mais avec une.000 jambes qui ';s plus de 16 minutes. Nous n ';t voulons que nos utilisateurs à attendre aussi longtemps. Nous devons être prêts et en moins que, qui comprend l'optimisation elle-même.

Donc, nous minimisons le nombre de jambes que nous avons besoin pour notre optimisation, nous voulons que le système de routage plus rapide disponible et l'exécuter sur plusieurs serveurs dédiés.

Quoi: Routeurs OSM

OpenStreetMapOpenStreetMap, la carte du monde libre, est la base que nous utilisons pour nos modèles d'optimisation de routage multi-stop. Il ';est gratuit à utiliser et la planète entière est à seulement quelques dizaines de giga-octets à télécharger. Et il ya un tas de logiciels libres qui utilisent OSM pour le calcul d'itinéraire.

Plus tôt, nous avons choisi le célèbre Gosmore que le routeur pour sa bonne performance, la stabilité et la licence généreuse. Il ';s programmé en C et fonctionne très bien sur notre configuration avec les serveurs dédiés Linux. Mais son développement ne est pas trop actif et semble plus destiné à la navigation autonome pour les appareils Android.

Récemment, une autre machine routage bien connu OSRM changé sa licence plutôt restrictive. Auparavant, il a été distribué sous licence AGPL. Depuis Octobre 2013, il ';s mis à disposition sous la très permissive (simplifié) 2 article licence BSD. Il ';s destiné à fonctionner comme un service, qui semble plus adaptée à notre besoin. Il ';est aussi C et son développement semble plus actif.

Remarque: il ya beaucoup plus routeurs pour OpenStreetMap.

Comment: configuration pour plusieurs itinéraires

Nous avons utilisé la dernière Gosmore et OSRM, compiler depuis les sources sur le même Intel i7 machine à 2,6 GHz avec 8 Go de RAM, sous Ubuntu Linux Desktop 13,10. Gosmore a été construit sans tête (pas d'interface graphique). Pour les deux routeurs, nous avons préparé des cartes des Pays-Bas, comme décrit dans la documentation.

Un script PHP a été utilisé comme un wrapper pour appeler les deux routeurs. À savoir: OSRM est utilisé comme un service de repos et Gosmore comme une commande du système plaine (exec avec une limite de 1 seconde CPU). Le script génère jambes aléatoires, qui sont constitués par deux emplacements aléatoires (ans, GNL) dans une zone fixe aux Pays-Bas. Ces emplacements ne peuvent pas être des adresses réelles, ils peuvent aussi être au milieu d'une forêt ou d'un lac. Nos membres font entrer toutes sortes de lieux dont ils ont besoin pour visiter pour le travail ou le plaisir, pas nécessairement maisons ou les entreprises ne.

Nous avions tous les deux Gosmore et OSRM trouver la route pour chaque jambe. Nous avons vérifié wether un itinéraire a été trouvé, wether la durée de Voyage était valide et a mesuré le temps passé pour le calcul. Nous avons validé en comparant chaque durée avec un minimum estimé et la valeur maximale. Ceux ont été calculés à partir de la distance des jambes à vol d'oiseau, la limite de vitesse maximale de 130 kilomètres par heure (durée minimale) et une vitesse de marche de 5 kilomètres par heure (durée maximale).

Les résultats des tests

Alors qu'un terme du script doit être suffisamment, nous avons couru trois fois. La sortie:

Exécutez # 1
 Total des jambes: 1000
 Total OSRM de temps: 7.851sec, Gosmore: 170,296 sec
 Succès OSRM: 96,5%, Gosmore: 94,6%
 Trop lent OSRM: 0%, Gosmore: 0%
 Trop rapide OSRM: 0%, Gosmore: 0%
Exécutez # 2
 Total des jambes: 1000
 Total OSRM de temps: 7.941sec, Gosmore: 174,774 sec
 Succès OSRM: 96,8%, Gosmore: 94,7%
 Trop lent OSRM: 0%, Gosmore: 0%
 Trop rapide OSRM: 0%, Gosmore: 0%
Exécutez # 3
 Total des jambes: 1000
 Total OSRM de temps: 7.785sec, Gosmore: 168,599 sec
 Succès OSRM: 95,5%, Gosmore: 94,9%
 Trop lent OSRM: 0%, Gosmore: 0%
 Trop rapide OSRM: 0%, Gosmore: 0%

Le gagnant: OSRM (plus vite, mais la graisse)

Les deux routeurs ont un taux de réussite élevé. Près de 100% de toutes les jambes sont acheminés avec succès. Ces jambes qui ont été acheminés, répondre à tous les contrôles de validité. Mais OSRM est plus rapide, beaucoup plus rapide. Il calcule des itinéraires pour 1000 pieds en moins de 8 secondes, où Gosmore prend environ 2 minutes et 50 secondes.

Sur la base de cette résultats des tests, nous avons un gagnant clair et OSRM semble être plus en forme pour notre travail. Il a la même qualité que Gosmore, mais est beaucoup plus rapide.

Il ya une remarque à faire. Nous avons couru ce test sur une assez petite carte des Pays-Bas. Jusqu'ici, nous ne avons pas réussi à obtenir OSRM afin de fonctionner pour toute la planète, dont nous avons besoin pour notre service de routage publique. Gosmore ne desservir des routes sur toute la planète sur plutôt faible, et pas cher, mais les serveurs dédiés (actuellement: Amazon EC2 c3.large). Si, tandis OSRM est très prometteur, nous avons besoin d'un autre effort pour le faire fonctionner pour nous.