posted by on Blog

No comments

 

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 cc_byncsa


Dijkstra

Como primer ejemplo se va a calcular el camino más corto desde el nodo 10 al nodo 17 utilizando el algoritmo de Dijkstra que nos asegura la mejor ruta posible. Vamos a considerar todos los tramos de doble dirección (grafo indirecto) y el coste va a consistir en la longitud de cada tramo.

pgrouting4

Ruta más corta en grafo indirecto

La función a utilizar se llama shortest_path y tiene una firma similar a la siguiente:

CREATE OR REPLACE FUNCTION pgr_dijkstra(
edges_sql text,
start_vid integer,                                          
end_vid integer,
directed boolean, -- por defecto si no se especifica es true
) RETURNS SETOF (seq, path_seq, node, edge, cost, agg_cost)

Argumentos:

  • edges_sql: Se corresponde con una consulta que pgrouting ejecutará para obtener los datos de la red. Esta consulta Select debe de devolver los siguientes campos (no es necesario que estén en orden, aunque hay que respetar el nombre y el tipo de datos).
  • id: Any-Integer -> Identifica el número de eje/tramo de la red.
  • source: Any-Integer -> Identifica el número de nodo inicial del tramo.
  • target: Any-Integer -> Identifica el número de nodo final del tramo.
  • cost: Any-Numerical (ej.: Double precisión) -> Coste del tramo necesario para atravesarlo en la dirección del nodo inicial al nodo final.
  • reverse_cost: Any-Numerical (opcional) -> Coste del tramo necesario para atravesarlo en la dirección del nodo final al nodo inicial. Únicamente se necesita si el grafo se ha definido directo y el argumento directed es true.

 Any-Integer hace referencia a cualquier entero, ej.: Integer, BigInt, etc. Any-Numerical hace referencia a cualquier tipo decimal, ej.: Double precisión, Real, Integer, etc.

  • start_vid: Número de nodo origen de la ruta a calcular.
  • end_vid: Número de nodo final de la ruta a calcular.
  • directed: true (el grafo es directo) o false (el grafo es indirecto). En el caso de grafo directo se utilizará el campo reverse_cost de la consulta SQL del primer argumento (edges_sql) como coste para atravesar el tramo en dirección opuesta.

Como salida la función devuelve el conjunto de filas conteniendo la ruta calculada, cada fila tiene los siguientes campos:

  • seq: Valor secuencial empezando en 1
  • path_seq: Posición relativa respecto al inicio de la ruta. El valor 1 representa el inicio.
  • [start_vid]: Identifica el número de nodo inicial del tramo de la ruta. Solo aparece cuando se utiliza la variedad del algoritmo que permite varios vértices de salida.
  • [end_vid]: Identifica el número de nodo final del tramo de la ruta. Solo aparece cuando se utiliza la variedad del algoritmo que permite varios vértices de llegada.
  • node: Número de nodo en la ruta, desde start_vid hasta end_vid.
  • edge: Identifica el eje del tramo de la ruta. Toma el valor -1 para el último eje.
  • cost: Coste del tramo.
  • agg_cost: Coste total acumulado desde el tramo inicial
routing1=# select * from pgr_dijkstra ('select gid as id, source, 
  target, st_length(geom) as cost from wr', 4, 11, false);
 seq | path_seq | node | edge |       cost       |     agg_cost
-----+----------+------+------+------------------+------------------
   1 |        1 |    4 |    8 | 88.3628881374981 |                0
   2 |        2 |    5 |    3 | 13.9283882771841 | 88.3628881374981
   3 |        3 |   16 |    2 | 18.5440037453175 | 102.291276414682
   4 |        4 |   15 |    1 | 13.8924439894498 |     120.83528016
   5 |        5 |    9 |    7 | 55.9464029227975 |  134.72772414945
   6 |        6 |    8 |    9 |               40 | 190.674127072247
   7 |        7 |    3 |   10 | 33.3016516106934 | 230.674127072247
   8 |        8 |    2 |   13 | 38.0131556174964 |  263.97577868294
   9 |        9 |    1 |   14 | 29.0172362570938 | 301.988934300437
  10 |       10 |    7 |   17 |               43 | 331.006170557531
  11 |       11 |    6 |   19 | 32.9544385764327 | 374.006170557531
  12 |       12 |   12 |   20 | 48.0104155366312 | 406.960609133963
  13 |       13 |   11 |   -1 |                0 | 454.971024670595

Como se puede observar la ruta trazada atraviesa algunos ejes y las rotondas en dirección contraria a la establecida por los nodos inicial y final (flechas de la figura).

Páginas: 1 2 3 4

posted by on Blog

No comments

 

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  cc_byncsa

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

Páginas: 1 2 3 4 5