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í.