PENTAHO, PG ROUTING

Cálculo de Rutas Óptimas con Pentaho y PgRouting (Optimal Routes)

Gente:

Lo prometido es deuda, un pequeño ejercicio para el cálculo de rutas óptimas(problema muy común entre nosotros) usando el ETL Spoon de Pentaho y PgRouting (algoritmo pgr_astar).

Problema: “Determinar las rutas mas óptimas de los proveedores ,analizando el coste (distancia) para la reducción de gastos asociados al desplazamiento“.

a1
En la Figura anterior se aprecia los proveedores de una tienda de electrodomésticos en la ciudad de Trujillo.

Para este ejercicio necesitamos:

  • Una malla vial. Podemos descargar de Openstreetmap. Les dejo un link donde se explica la extracción y los filtros necesarios.
  • Descargamos el Spoon de este link.

Empecemos:

  1. Para usar pgRouting, necesitamos construir una topología red, con ello nos aseguramos de conectar todas las vías a través de un conjunto de nodos. De esta forma, el final de cada vía queda conectado con el inicio de otra a través de un nodo.
  2. Vamos a utilizar el algoritmo pgr_astar que está mas preparado para grandes volúmenes de datos. Necesitamos crear las siguientes columnas:
    • gid : Identificador de la vía.
    • source: Identificador del vértice inicial de la vía.
    • target: Identificador del vértice final de la vía.
    • length: Distancia de la vía(costo).
    • x1: Coordenada x del vértice inicial de la vía.
    • x2: Coordenada y del vértice inicial de la vía.
    • y1: Coordenada x del vértice final de la vía.
    • y2: Coordenada x del vértice final de la vía
  3. Como queremos hacerlo dinámico es decir ejecutar este proceso para cualquier red vial , declaramos una variable ${vias_osm}. Con esto hacemos llamado a la red vial de trujillo.
  4. Creamos un Job en Spoon y agregamos la transformación “SQL”, con ello ejecutaremos un script para la creación de las columnas.
  5. Agregamos otra transformación “SQL” para crear la topología de red y actualizar las coordenadas iniciales y finales.
  6. Con ello se han creado las intersecciones de las vías y se han actualizado los campos del paso 2.a6
  7. Ahora lo que tenemos que hacer es asignarle el código de la intersección mas cercano a todos los proveedores (id_origen) y a la tienda de electrodomésticos (id_destino).
  8. Ahora necesitamos saber una matriz con todas las combinaciones posibles entre los proveedores y la tienda de electrodomésticos . Ejecutamos una consulta espacial por cercanía para obtener:

    A10
    En el gráfico observamos una matriz con los 75 códigos de proveedores y su único código de destino en este caso la tienda de electrodomésticos.
  9. Ahora la última parte y la mas importante ejecutamos el algoritmo pgr_astar con los parámetros del punto 2:
    • gid : Id
    • source: id_origen
    • target: Id_destino
    • length: distancia
    • x1: Coordenada x1.
    • x2: Coordenada y1 .
    • y1: Coordenada x1.
    • y2: Coordenada x2.
    • Todo resultado de la tabla de matriz distancia.
  10. Vamos a ejecutar el ETL y nos pedirá las variables que hemos definido en el proceso en este caso la red vial y el código de la tienda de electrodomésticos.

     

  11. Para una visualización en forma dinámica vamos a agregar los resultados a geoserver y generamos un pequeños visor con openlayers.a15
  12. Y este es el resultado 75 rutas optimas de desplazamientos de los proveedores hacia su destino ( tiempo de proceso 1 minuto).

Visualmente FME es mas atractivo pero la gran ventaja de Spoon de Pentaho aparte de ser free es que podemos utilizar postgres ,sql nativo y eso es una gran ventaja para los que conocemos algo de código.

pd: Si queremos hacer rutas óptimas hacia múltiples destino existen 2 formas: agregar tantas variables cuantos destinos quieran o utilizar ETL Metadata Injection que es una transformación de pentaho para agregar dinámicamente las variables de una tabla ( En un futuro post).

 

A16
Resultado para 2 destinos.

 

 

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

w

Conectando a %s