Instalaremos Open Source Routing Machine (OSRM), un motor de ruteo de alta performance, de uso libre, que permite además adquirir grillas de calles de forma muy simple usando datos de OpenStreetMap.
Estas instrucciones fueron testeadas en un sistema corriendo Ubuntu. También deberían funcionar sin modificaciones con cualquier otra versión de Linux, e incluso en macOS.
Los comandos mostrados a continuación deben ser ejecutados en una terminal.
Instrucciones en https://docs.docker.com/install/
Por ejemplo,
mkdir -p /data/osrm/Argentina
cd /data/osrm/Argentina
Es importante no usar espacios en blanco en los nombres de los directorios, ya que causa problemas con docker. Es decir, evitar directorios tipo “/data/ruteo con osrm/datos argentina/”
Podemos usar la información geográfica contenida en la base de OpenStreetMap para obtener la grilla de calles de nuestra área de interés… o de todo el mundo.
Por ejemplo, para el contenido completo de toda la Argentina podemos usar el servicio OpenStreetMap Data Extracts provisto por GeoFabrik.
Descargamos el extracto más reciente para la Argentina con:
wget https://download.geofabrik.de/south-america/argentina-latest.osm.pbf
OSRM requiere un procesamiento previo de los datos extraidos de OpenStreetMap, construyendo un modelo optimizado de la grilla de calles. Para la optimización se debe elegir un modo de transporte. Las opciones disponibles por default son - car - foot - bicycle
Hacemos la extracción para el modo automóvil (car) con:
docker run -t -v $(pwd):/data osrm/osrm-backend osrm-extract -p /opt/car.lua /data/argentina-latest.osm.pbf
Esto inicia una instancia de docker, corre el comando osrm-extract y luego desactiva la instacia.
La opción -v $(pwd):/data crea un directorio /data dentro del contenedor de docker, y muestra en el el contenido del directorio desde donde corrimos el comando; es decir, el directorio donde está descargada la data de Argentina. Así es como queda accesible para la instancia de docker como /data/argentina-latest.osm.pbf.
Cuando corremos el comando por primera vez tomará unos cuantos minutos, ya que docker necesita descargar antes el container con OSRM. En lo sucesivo no será necesario, ya que tras la descaga guarda una copia local del container.
Quedan dos operaciones pendientes que OSRM necesita antes de poder realizar ruteos.
Dividir el grafo en celdas, ejecutando:
docker run -t -v $(pwd):/data osrm/osrm-backend osrm-partition /data/argentina-latest.osrm
Obsérvese que ahora usamos argentina-latest.osrm (ya no es “.pbf”), un archivo que quedó en el directorio de trabajo tras ejecutar el paso anterior.
… y por últumo asignar “peso” a cada celda del grafo con
docker run -t -v $(pwd):/data osrm/osrm-backend osrm-customize /data/argentina-latest.osrm
Con los datos ya preparados, sólo resta iniciar el servicio de ruteo:
docker run -t -i -p 5000:5000 -v $(pwd):/data osrm/osrm-backend osrm-routed --algorithm mld /data/argentina-latest.osrm
A partir de ahora, pasamos a R. El resto del documento muestra código ejecutado en el entorno R.
Podemos hacer uso de las funciones de OSRM desde R en forma fácil usando el paquete osrm. Si aún no lo tenemos instalado, lo obtenemos con:
install.packages("osrm")library(tidyverse)
library(osrm)Avisamos que vamos a usar nuestra instancia local de OSRM, en lugar del default que es usar la API pública del proyecto.
options(osrm.server = "http://127.0.0.1:5000/")Para testear, cargamos un dataset con las coordenadas de los grandes aglomerados urbanos de la Argentina.
ciudades <- read.csv("http://bitsandbricks.github.io/data/aglomerados.csv")
ciudadesCon osrmTable podemos hacer una matriz origen-destino conteniendo el tiempo de viaje entre todas las ciudades:
distancias <- osrmTable(loc = ciudades)Examinando el resultado, podemos ver el tiempo que lleva conducir entre cada par de puntos (en minutos)
distancias$duration[1:5,1:5] %>% as.data.frame()Podemos obtener la ruta necesaria para conducir de un punto dado a otro usando osrmRoute
Elegimos origen y destino, en forma de vectores conteniendo un identificador (nombre), longitud y latitud. Por ejemplo Río Gallegos y Tucumán
ciudades[c(24, 16),]Obtenemos la ruta más corta para conducir de una ciudad a la otra:
de_Gallegos_a_Tucuman <- osrmRoute(src = ciudades[24,],
dst = ciudades[16,],
sp = TRUE,
overview = "full")La opción sp = TRUE permite obtener un dataframe espacial como resultado, que podemos proyectar luego sobre un mapa. overview = "full" hace que osrmRoute calcule la ruta precisa (con posiciones exactas) en lugar de un aproximado; de nuevo, solicitamos esto para luego poder visualizar el camino exacto en un mapa.
osrmRoute también estima la distancia (en kilómetros) y el tiempo (en minutos) del trayecto, a los que accedemos así:
de_Gallegos_a_Tucuman@dataProyectamos la ruta sobre un mapa, usando leaflet:
library(leaflet)
leaflet(de_Gallegos_a_Tucuman) %>%
addProviderTiles(providers$OpenStreetMap, group = "OSM") %>%
addPolylines(color = "red")Un ejemplo más, ahora con una ruta intra-ciudad: De Parque Centenario a la Estación Retiro, ambos puntos en la Ciudad de Buenos Aires.
pcentenario <- c(nombre = "Parque Centenario",
lon = -58.435609,
lat = -34.606411)
eretiro <- c(nombre = "Estación Retiro",
lon = -58.374873,
lat = -34.591394)
centenario_a_retiro <- osrmRoute(src = pcentenario,
dst = eretiro,
sp = TRUE,
overview = "full")Detalles:
centenario_a_retiro@dataen el mapa:
leaflet(centenario_a_retiro) %>%
addProviderTiles(providers$OpenStreetMap, group = "OSM") %>%
addPolylines(color = "red")La performance de los algoritmos de OSRM es muy alta, devolviendo resultados en una fracción del tiempo que una api online de ruteo alla Google Maps. En una laptop (circa 2016, cuatro núcleos Intel i5) superó los 15.000 ruteos por minuto, sin realizar ninguna optimización más allá de las mencionadas al principio del documento.