Technote: OSRM vs Gosmore tiroteo

Necesitamos una gran cantidad de rutas de punto a punto para nuestro sistema de enrutamiento de varias paradas. Como usamos Openstreetmap como una fuente para este, nosotros ';hemos establecido una comparación entre dos sistemas de enrutamiento de OSM conocidos: Gosmore y OSRM.

Ante todo, hemos puesto en marcha esta prueba para nuestras propias necesidades. Es ';s no pretende ser representativa para todas las necesidades de enrutamiento en todas las situaciones. Los resultados y conclusiones no tienen que ser válido para usted. Si usted entiende esto y está de acuerdo, seguir leyendo.

¿Por qué: matriz de distancia

Para encontrar el más rápido ruta con múltiples paradas, necesitamos saber A-to-B duraciones de viaje entre todos los puntos. Para visitar 4 destinos de un lugar de origen, necesitamos ruta 5 x 4 = 20 patas. Esta matriz de distancias de viajes crece exponencialmente. Con 40 destinos, es;s 41 x 40 = 1,640 piernas, con 80 destinos 6,480 piernas, etcétera.

Así, ¿cuánto tiempo su toma de navegación en el coche para encontrar la ruta a un destino? Si ';s rápido, lo hará dentro de un segundo. Eso parece rápido, pero con 1.000 piernas que ';s más de 16 minutos. Nos don ';t quiere a nuestros usuarios a esperar tanto tiempo. Tenemos que estar listos y en menos que eso, que incluye la propia optimización.

Por lo tanto, minimizamos el número de patas que realmente necesitamos para nuestra optimización, queremos que el sistema de enrutamiento más rápido disponible y ejecutarlo en múltiples servidores dedicados.

Qué: Routers OSM

OpenStreetMapOpenStreetMap, el mapa libre del mundo, es la base que utilizamos para nuestros modelos de optimización de enrutamiento multi-stop. Es ';es libre de usar y todo el planeta está a sólo unas decenas de gigabytes de descarga. Y hay un montón de software libre que utilizan OSM para el cálculo de rutas.

Más temprano, seleccionamos el reconocido Gosmore como el router por su buen desempeño, estabilidad y generosa licencia. Es ';s programado en C y funciona muy bien en nuestra configuración con servidores dedicados Linux. Pero su desarrollo no es demasiado activo y parece más dirigido hacia la navegación autónoma para dispositivos Android.

Recientemente, otra máquina de enrutamiento conocido OSRM cambió su licencia y no restrictiva. Anteriormente fue licenciado bajo la AGPL. Desde octubre de 2013 ';S hecha disponible bajo la muy permisiva (simplificado) Licencia BSD de 2 clausulas. Es ';significó para funcionar como un servicio, que parece más orientado a nuestra necesidad. Es ';Es también C y su desarrollo parece más activo.

Nota: hay muchos más routers para Openstreetmap.

Cómo: configuración de múltiples rutas

Utilizamos la última OSRM Gosmore y, construir desde el código fuente en el mismo procesador Intel i7 máquina de 2,6 GHz con 8 GB de RAM, Ubuntu Linux Desktop 13.10. Gosmore fue decapitado construcción (sin GUI). Para ambos routers preparamos mapas de los Países Bajos, como se describe en su documentación.

Un script php se utilizó como un contenedor para llamar ambos routers. Eso es: OSRM se utiliza como un servicio de descanso y Gosmore como un comando del sistema llanura (exec con un límite de CPU de 1 segundo). El script genera piernas al azar, que se componen por dos lugares al azar (año, lng) en un área fija en los Países Bajos. Estas ubicaciones pueden no ser direcciones reales, también pueden estar en medio de un bosque o un lago. Nuestros usuarios hacen entrar en todo tipo de lugares que necesitan para visitar por trabajo o placer, no necesariamente sólo casas o negocios.

Teníamos tanto Gosmore y OSRM encontrar la ruta para cada pierna. Comprobamos wether se encontró una ruta, wether la duración del viaje era válida y se mide el tiempo empleado para el cálculo. Hemos validado mediante la comparación de cada duración, con un valor mínimo y máximo estimados. Aquellos se calcularon a partir de la distancia de la pierna en línea recta, el límite de velocidad máxima 130 kmh (duración mínima) y una velocidad de caminata de 5 kmh (la duración máxima).

Resultados de la prueba

Mientras que una carrera de la escritura debe ser suficiente, corrimos tres veces. La salida:

Run # 1
 Piernas totales: 1000
 El tiempo total de OSRM: 7.851sec, Gosmore: 170.296 seg
 Éxito OSRM: 96,5%, Gosmore: 94,6%
 Demasiado lento OSRM: 0%, Gosmore: 0%
 Demasiado rápido OSRM: 0%, Gosmore: 0%
Run # 2
 Piernas totales: 1000
 El tiempo total de OSRM: 7.941sec, Gosmore: 174.774 seg
 Éxito OSRM: 96,8%, Gosmore: 94,7%
 Demasiado lento OSRM: 0%, Gosmore: 0%
 Demasiado rápido OSRM: 0%, Gosmore: 0%
El ciclo # 3
 Piernas totales: 1000
 El tiempo total de OSRM: 7.785sec, Gosmore: 168.599 seg
 Éxito OSRM: 95,5%, Gosmore: 94,9%
 Demasiado lento OSRM: 0%, Gosmore: 0%
 Demasiado rápido OSRM: 0%, Gosmore: 0%

El ganador: OSRM (más rápido, pero la grasa)

Ambos routers tienen una alta tasa de éxito. Cerca del 100% de todas las patas se encaminan con éxito. Esas piernas que fueron enviados, cumplir con todos los controles de validez. Pero OSRM es más rápido, mucho más rápido. Se calcula rutas para 1000 piernas en menos de 8 segundos, donde Gosmore tarda aproximadamente 2 minutos y 50 segundos.

Basado en estos resultados de la prueba, tenemos un ganador claro y OSRM parece ser más conveniente para nuestro trabajo. Tiene la misma calidad que Gosmore, pero es mucho más rápido.

Hay una observación a realizar. Corrimos esta prueba en un lugar pequeño mapa de los Países Bajos. Hasta aquí, no tuvimos éxito en conseguir OSRM para funcionar para todo el planeta, que necesitamos para nuestro servicio de enrutamiento pública. Gosmore sirve a rutas por todo el planeta en bastante pequeño, y barato, pero los servidores dedicados (Actualmente: Amazon EC2 c3.large). Así, mientras OSRM es muy prometedor, necesitamos otro esfuerzo para conseguir que funcione para nosotros.