En esta serie de artículos sobre Pgrouting muestro el funcionamiento básico de esta biblioteca de rutas que trabaja sobre PostGIS.

Trato de actualizar el capítulo F.11 del libro de PostGIS, que al utilizar la versión anterior de pgrouting se ha quedado obsoleto.

Este material ha sido realizado por José Carlos Martínez y se publica mediante licencia Creative Commons

Utilización de datos OSM

Los datos OSM por su naturaleza y por ser datos cartográficos libres son ideales para utilizarlos en programas de cálculo de rutas. En el apartado F 10, pág. 301 se estudió como importar datos OSM a PostGIS utilizando los cargadores osm2pgsql y osmosis.

También acabamos de ver que la función pgr_createTopology de pgrouting crea topología de red de una capa lineal, siempre que no existan intersecciones entre los tramos (ver pág. 309), y es precisamente esta condición la que no cumple los datos OSM. Efectivamente un tramo (way) OSM puede estar formado por más de dos nodos, donde los nodos intermedios pueden formar parte de otros tramos, por lo tanto es necesario partir dichos tramos para que únicamente sus nodos inicial y final sean los que conectan con otros tramos.

La figura siguiente (izquierda) muestra como en la cartografía OSM importada con oms2pgsql los tramos lineales OSM (ways) se cruzan entre sí sin crear nodos en las intersecciones, por el contrario la cartografía de la figura de la derecha muestra como la cartografía OSM importada con osm2pgrouting ha partido dichos tramos lineales creando nuevos registros en la tabla. Los dos tramos lineales (2 filas) de la figura de la izquierda (tramos resaltados) se han transformado en 9 tramos lineales (9 filas) en la figura de la derecha.

Nodificación de cartografía OSM

Osm2pgrouting

El comando de utilidad osm2pgrouting[1] se puede instalar desde repositorios de terceros en distribuciones Ubuntu o mediante paquetes rpm para distribuciones Fedora. En MS Windows este comando se distribuye ya de forma oficial con la instalación de PostGIS. En otras distribuciones de Linux así como para obtener una versión más reciente puede ser necesaria su compilación a partir del código fuente.

Osm2pgrouting se ejecuta desde línea de comandos en una terminal del sistema. Las opciones del comando son:

• —file <fichero osm>: Nombre del fichero xml OSM a importar.
• —conf <fichero de configuración>: Ruta al archivo de configuración de osm2pgrouting. Generalmente este archivo es xml y se distribuye al instalar osm2pgrouting.
• –skipnodes
  : Si es true no importa los nodos OSM.
• —clean
  : Elimina las tablas instaladas en un proceso de osm2pgrouting

 Opciones de conexión a PostgreSQL:

• –d <base de datos>: Nombre de la base de datos en la cual cargar las capas OSM.
• –u <usuario>: Usuario de la base de datos.
• –passwd <contraseña>: Contraseña de la conexión a la base de datos.
• –h <host>: Host de la máquina donde está el servidor de PostgreSQL. Por defecto es 127.0.0.1.
• –p <puerto>: Número de puerto para la conexión. Por defecto es 5432.

En esta serie de artículos sobre Pgrouting muestro el funcionamiento básico de esta biblioteca de rutas que trabaja sobre PostGIS.

Trato de actualizar el capítulo F.11 del libro de PostGIS, que al utilizar la versión anterior de pgrouting se ha quedado obsoleto.

Este material ha sido realizado por José Carlos Martínez y se publica mediante licencia Creative Commons 

Contenido:

• Parte 1: Descripción de pgrouting, instalación y definición de grafos directos / indirectos
• Parte 2: Algoritmos de camino más corto: Dijkstra, A Star y TRSP.
• Parte 3: Rutas con cartografía OSM: osm2pgrouting y preparación de los datos
• Parte 4: Redes sin nodificar no OSM

 Pgrouting es una extensión de PostgreSQL/PostGIS que añade la funcionalidad del cálculo de rutas, en concreto se puede utilizar para resolver los siguientes problemas:

• Resolver el camino o los n caminos más cortos o Shortest Path entre dos nodos o ejes de la red lineal (dispone varios algoritmos diferentes).
• Problema del viajante o Traveling Salesperson Problem (TSP). Si imaginamos un comerciante que debe visitar una serie de ciudades distintas, el problema a resolver consiste en encontrar una ruta óptima que pase una única vez por cada una de las ciudades minimizando la distancia total recorrida por el comerciante.
• Problema de distancia de conducción o Driving Distance calculation (DD).

En este apartado se va a centrar en resolver el problema del camino más corto, primero utilizando unos datos de ejemplo y a continuación cartografía de OSM.

Instalación

A partir de la versión 2.1 de PostGIS, en MS Windows los paquetes de instalación del propio PostGIS (obtenidos ya sea directamente desde el sitio web de PostGIS o mediante la utilización de la aplicación StackBuilder de PostgreSQL) incluyen la extensión de pgrouting y por lo tanto no es necesario realizar ningún proceso adicional como en versiones más antiguas de pgrouting.

En Linux u OSX es posible que se necesiten instalar paquetes extra además de la propia instalación de PostGIS.

En Ubuntu se puede encontrar algunos repositorios especializados en pgrouting [1] y [2], aunque generalmente estos paquetes pueden estar algo desactualizados y no contener las versiones más recientes de pgrouting.

En último caso, especialmente en Linux por su facilidad siempre se podrá compilar la última versión de pgrouting según la versión de postgis y postgresql que tengamos instalada. Las instrucciones del proceso para los diferentes sistemas operativos se puede encontrar en la documentación oficial de pgrouting[3]

Si lo que se desea es probar la funcionalidad de pgrouting también se puede optar por utilizar OSGEO Live[4] que es una distribución live de Linux que lleva ya todo instalado.

Tras la instalación de pgrouting utilizaremos el comando Create Extension para añadir la extensión a nuestra base de datos espacial. Para este ejercicio guiado vamos a crear una nueva base de datos con soporte PostGIS llamada routing1.

Para los ejercicios de este capítulo crearemos una base de datos nueva routing1 y le añadiremos la extensión de PostGIS.

Puedes encontrar los datos necesarios aquí.