Technote: OSRM vs Gosmore Schießen

Wir müssen eine ganze Reihe von Punkt-zu-Punkt-Routen für unsere Multi-Stopp-Routing-System. Wie wir Openstreetmap als Quelle für diese, wir;habe ein Vergleich zwischen zwei bekannten OSM Routingsysteme setzen: Gosmore und OSRM.

Zunächst, haben wir diesen Test für unsere eigenen Bedürfnisse eingestellt. Es ist;s nicht gedacht für alle Routing-Anforderungen in allen Situationen repräsentativ zu sein. Die Ergebnisse und Schlussfolgerungen müssen nicht gültig für Sie sein. Wenn Sie verstehen und akzeptieren, weiterlesen.

Warum: Distanzmatrix

Um die schnellsten finden Route mit mehreren Zwischenstationen, Wir müssen ein-to-B Reisedauer zwischen allen Punkten kennen. 4 Ziele aus einem Ursprungsort besuchen, wir brauchen, um Route 5 x 4 = 20 Beine. Diese Distanz Matrix exponentiell. Mit 40 Destinationen, es;s 41 x 40 = 1,640 Beine, mit 80 Destinationen 6,480 Beine, usw.

So, wie lange dauert Ihre Navigation im Auto nehmen Sie die Route zu einem Ziel zu finden? Wenn es ';s schnell, es wird so innerhalb einer Sekunde zu tun. Das scheint schnell, jedoch mit 1.000 Beine, dass ';ist mehr als 16 Minuten. Wir don ';t wollen, dass unsere Nutzer so lange warten. Wir müssen bereit und in weniger als das geschehen zu sein, welche die Optimierung selbst beinhaltet.

Deshalb, Wir minimieren die Anzahl der Beine, die wir eigentlich für unsere Optimierungsbedarf, wir wollen, dass die schnellste Routing-System zur Verfügung und führen Sie es auf mehreren dedizierten Servern.

Ach Was: OSM-Router

OpenstreetmapOpenstreetmap, die freie Weltkarte, ist die Basis, die wir für unsere Multi-Stopp-Routing-Optimierungsmodelle. Es ist;s kostenlos zu benutzen und der ganze Planet ist nur einige zehn Gigabyte zum Download. Und es gibt eine Reihe von kostenlosen Software, die OSM für die Routenberechnung verwenden.

Früher, wir den renommierten ausgewählt Gosmore wie der Router für seine gute Leistung, Stabilität und großzügigen Lizenz. Es ist;s in C programmiert und funktioniert auf unserem Setup mit dedizierten Linux-Server. Aber seine Entwicklung nicht zu aktiv und scheint mehr auf Stand-alone-Navigation für Android-Geräte ausgerichtet.

Vor Kurzem, ein weiterer bekannter Oberfräse OSRM änderte ihren eher restriktiven Lizenz. Zuvor wurde es unter der AGPL Lizenz. Seit Oktober 2013 ist es;s unter der sehr freizügig zur Verfügung gestellt (vereinfachte) 2-Klausel-BSD-Lizenz. Es ist;s soll als Dienst ausgeführt, die eher für unser Bedürfnis scheint. Es ist;s auch C und seine Entwicklung scheint aktiver.

Hinweis: es gibt viele weitere Router für Openstreetmap.

Wie: Setup für mehrere Routen

Wir haben die neueste Gosmore und OSRM, von der Quelle auf die gleiche Intel bauen i7 2,6 GHz Maschine mit 8 GB RAM, Ubuntu Linux Desktop 13,10. Gosmore gebaut wurde kopflos (keine GUI). Für beide Router wir Karten von den Niederlanden vorbereitet, wie in deren Dokumentation beschrieben.

Ein PHP-Skript wurde als Wrapper für beide Router rufen verwendet. Das is: OSRM als Rest Service und Gosmore als einfache Befehlssystem (exec mit einer CPU Grenze von 1 Sekunde). Das Skript generiert zufällige Beine, die von zwei zufälligen Orten gemacht werden (Jahre, lng) in einem festgelegten Bereich in den Niederlanden. Diese Standorte können nicht reale Adressen werden, sie können auch in der Mitte einer Gesamtstruktur oder einem See. Unsere Mitglieder tun geben alle Arten von Stellen sie für Arbeit oder zum Vergnügen besuchen müssen, nicht unbedingt Häuser oder Geschäfte nur.

Wir hatten beide Gosmore und OSRM die Route für jedes Bein zu finden. Wir überprüfen, ob eine Route gefunden wurde, ob die Reisedauer gültig war und die Zeit gemessen, bei der Berechnung ausgegeben. Wir indem jeder Dauer mit einem geschätzten minimalen und maximalen Wert validiert. Diese wurden aus dem Bein Entfernung berechnet Luftlinie, die Höchstgeschwindigkeit 130 km / h (Mindestlaufzeit) und eine Laufgeschwindigkeit von 5 km / h (Höchstdauer).

Testergebnisse

Während einem Lauf des Skripts sollte genug sein, wir liefen dreimal. Das Ausgangs:

Führen Sie # 1
 Insgesamt Beine: 1000
 Gesamtzeit OSRM: 7.851sec, Gosmore: 170,296 sec
 Success OSRM: 96,5%, Gosmore: 94,6%
 Zu langsam OSRM: 0%, Gosmore: 0%
 Zu schnell OSRM: 0%, Gosmore: 0%
Führen Sie # 2
 Insgesamt Beine: 1000
 Gesamtzeit OSRM: 7.941sec, Gosmore: 174,774 sec
 Success OSRM: 96,8%, Gosmore: 94,7%
 Zu langsam OSRM: 0%, Gosmore: 0%
 Zu schnell OSRM: 0%, Gosmore: 0%
Führen Sie # 3
 Insgesamt Beine: 1000
 Gesamtzeit OSRM: 7.785sec, Gosmore: 168,599 sec
 Success OSRM: 95,5%, Gosmore: 94,9%
 Zu langsam OSRM: 0%, Gosmore: 0%
 Zu schnell OSRM: 0%, Gosmore: 0%

Der Gewinner: OSRM (schneller, aber Fett)

Beide Router haben eine hohe Erfolgsquote. Nahezu 100% aller Beine sind erfolgreich weitergeleitet. Diese Beine, die weitergeleitet wurden, erfüllen alle Gültigkeitsprüfungen der. Aber OSRM ist schneller, viel schneller. Es berechnet Routen für 1000 Beine in weniger als 8 Sekunden, wo Gosmore dauert ca. 2 Minuten und 50 Sekunden.

Auf der Grundlage dieser Testergebnisse, wir haben einen klaren Sieger und OSRM scheint für unsere Arbeit fit zu sein. Es hat die gleiche Qualität wie Gosmore, jedoch ist viel schneller.

Es gibt eine Bemerkung gemacht werden. Wir liefen diesen Test auf einer ziemlich kleinen Karte der Niederlande. Bisher, haben wir nicht in immer OSRM gelingen, für den ganzen Planeten laufen, denen wir für unsere öffentlichen Routing-Service. Gosmore tut dienen Routen über den ganzen Planeten auf eher klein, und billig, aber dedizierte Server (zur Zeit: Amazon EC2 c3.large). So, während OSRM ist sehr vielversprechend, wir brauchen noch einen Versuch, um es für uns zu arbeiten.