Technote: OSRM vs Gosmore shootout

We hebben een heleboel point-to-point routes voor onze multi-stop routing systeem. Als we gebruik maken van Openstreetmap als bron voor deze, we’;heb het opzetten van een vergelijking tussen twee bekende OSM routing systemen: Gosmore en OSRM.

Allereerst, we hebben opgezet deze test voor onze eigen behoeften. It’;s niet bedoeld representatief voor alle routing behoeften in alle situaties te zijn. De resultaten en conclusies hoeven niet geldig voor u te zijn. Als je dit begrijpt en gaat ermee akkoord, Lees verder.

Waarom: afstandsmatrix

Om de snelste te vinden route met meerdere tussenstops, we moeten weten A naar B reizen looptijden tussen alle punten. Voor een bezoek aan 4 bestemmingen van de ene herkomst, We moeten traject 5 x 4 = 20 poten. Dit reisafstand matrix groeit exponentieel. Met 40 bestemmingen, it’;s 41 x 40 = 1.640 poten, met 80 bestemmingen 6.480 benen, enzovoort.

Zo, hoe lang duurt uw navigatiesysteem in de auto nemen om de route naar een bestemming te vinden? If it’;s snel, het zal dit doen binnen één seconde. Dat lijkt snel, maar met 1.000 legs that’;is meer dan 16 minuten. We don’;t willen dat onze gebruikers zo lang wachten. We moeten klaar en gedaan in minder dan dat te zijn, waarin de optimalisatie zelf omvat.

daarom, minimaliseren we het aantal poten dat we eigenlijk nodig hebben voor onze optimalisatie, we willen dat de snelste routing systeem beschikbaar zijn en deze vervolgens op diverse dedicated servers.

Wat: OSM routers

OpenstreetmapOpenstreetmap, de gratis kaart van de wereld, is de basis die we gebruiken voor onze multi-stop routing optimalisatiemodellen. It’;is gratis te gebruiken en de hele planeet is slechts enkele tientallen gigabytes te downloaden. En er is een heleboel gratis software die OSM gebruiken voor het berekenen van de route.

vroeger, we gekozen voor de gerenommeerde Gosmore als de router voor zijn goede prestaties, stabiliteit en royale licentie. It’;s geprogrammeerd in C ++ en werkt geweldig op onze opstelling met dedicated Linux servers. Maar de ontwikkeling ervan is niet al te actief en lijkt meer gericht op stand-alone navigatie voor Android-apparaten.

Kort geleden, andere bekende freesmachine OSRM veranderde haar vrij beperkte licentie. Voorheen werd gelicenseerd onder de AGPL. Since October 2013 it’;S onder de zeer tolerante ter beschikking gesteld (vereenvoudigd) 2-clausule BSD licentie. It’;s bedoeld om te draaien als een service, die lijkt meer gericht op onze behoefte. It’;s ook C ++ en de ontwikkeling ervan lijkt meer actief.

Notitie: er zijn veel meer routers voor Openstreetmap.

Hoe: setup voor meerdere routes

We gebruikten de laatste Gosmore en OSRM, bouwen van de bron op dezelfde Intel i7 2,6 GHz machine met 8 GB RAM, Ubuntu Linux Desktop 13.10. Gosmore werd gebouwd headless (geen GUI). Voor beide routers bereid we kaarten van Nederland, zoals beschreven in de documentatie.

Een php script werd gebruikt als een wrapper voor beide routers bellen. Mensen: OSRM wordt gebruikt als een rust service en Gosmore als een gewone opdracht systeem (exec met een CPU hoogste 1 seconde). Het script genereert willekeurige benen, die zijn opgebouwd door twee willekeurige locaties (jaar, lng) in een vast gebied in Nederland. Deze locaties kunnen niet worden echte adressen, ze kunnen ook in het midden van een bos of een meer. De gebruikers doen voeren allerlei locaties die ze nodig hebben om te bezoeken voor werk of plezier, niet per se huizen of bedrijven alleen.

We hadden beiden Gosmore en OSRM vind de route voor elk been. Wij controleerden Of een route werd gevonden, Of de reisduur geldig was en de gemeten tijd voor de berekening. We gevalideerd door het vergelijken van elke duur met een geschatte minimale en maximale waarde. Die werden berekend op basis van de etappe afstand zoals de kraai vliegt, de maximumsnelheid 130 km / h (minimumduur) en een loopsnelheid van 5 km / h (maximumduur).

Test resultaten

Terwijl één run van het script voldoende moeten zijn, we liep het drie keer. Het resultaat:

Run # 1
 Totaal benen: 1000
 Total time OSRM: 7.851sec, Gosmore: 170.296 sec
 Success OSRM: 96,5%, Gosmore: 94.6%
 Too slow OSRM: 0%, Gosmore: 0%
 Too fast OSRM: 0%, Gosmore: 0%
Run # 2
 Totaal benen: 1000
 Total time OSRM: 7.941sec, Gosmore: 174.774 sec
 Success OSRM: 96,8%, Gosmore: 94.7%
 Too slow OSRM: 0%, Gosmore: 0%
 Too fast OSRM: 0%, Gosmore: 0%
Run # 3
 Totaal benen: 1000
 Total time OSRM: 7.785sec, Gosmore: 168.599 sec
 Success OSRM: 95,5%, Gosmore: 94.9%
 Too slow OSRM: 0%, Gosmore: 0%
 Too fast OSRM: 0%, Gosmore: 0%

De winnaar: OSRM (sneller, maar vet)

Beide routers hebben een hoog slagingspercentage. Bijna 100% van alle poten worden met succes geleid. Die benen die werden gerouteerd, voldoen aan alle geldigheidscontroles de. Maar OSRM is sneller, een stuk sneller. Het berekent routes voor 1000 benen in minder dan 8 seconden, waarbij Gosmore duurt ongeveer 2 minuten en 50 seconden.

Op basis van deze testresultaten, we hebben een duidelijke winnaar en OSRM lijkt meer geschikt voor ons werk te zijn. Het heeft dezelfde kwaliteit als Gosmore, maar is veel sneller.

Er is een opmerking te maken. We liepen deze test op een vrij kleine kaart van Nederland. Dusver, slaagden we er niet in het krijgen van OSRM uit te voeren voor de hele planeet, die we nodig hebben voor onze publieke routeringsservice. Gosmore doet routes dienen over de hele planeet op vrij klein, en goedkoop, maar dedicated servers (momenteel: Amazon EC2 c3.large). Zo, terwijl OSRM is veelbelovend, we hebben nog een poging te krijgen om te werken voor ons.