Rutas en PostGIS con la nueva versión de Pgrouting (parte 2/4): Dijkstra, A Star y TRSP

Feb
2016
15

posted by on Blog

No comments

Aunque en nuestra pequeña red no tiene sentido, el procedimiento a seguir consistiría por ejemplo en pasar a pgrouting únicamente los tramos de la red que están dentro de una caja expandida en 50 metros.

routing1=# select * from pgr_dijkstra (
  'select gid as id, source, target, cost, reverse_cost 
   from wr, 
   ( select st_expand (st_extent(wr.geom)::geometry, 50) from wr 
     where wr.source in (4,11) or wr.target in (4,11)
   ) as tabla (caja) 
   where wr.geom && caja', 
  4, 11, true);

El método pgr_dijkstra tiene varias firmas alternativas que permiten el cálculo de varias rutas a partir de uno o varios puntos de inicioa a uno o varios puntos final. Para ello, en lugar de especifiar un único nodo de inicio o final se utiliza un array.

Por ejemplo, el siguiente método utiliza un array en el argumento del nodo inicial para especificar dos nodos iniciales. Modificando nuestro primer ejemplo:

s1=#  select * from pgr_dijkstra ('select gid as id, source, target, 
     st_length(geom) as cost from wr', array[4,10], 11, false);
seq | path_seq | start_vid | node | edge |  cost  | agg_cost
-----+----------+-----------+------+------+--------+----------
   1 |        1 |         4 |    4 |    8 |  88.36 |     0.00
   2 |        2 |         4 |    5 |    3 |  13.93 |    88.36
   …
  13 |       13 |         4 |   11 |   -1 |   0.00 |   454.97
  14 |        1 |        10 |   10 |   21 | 115.07 |     0.00
  15 |        2 |        10 |   13 |   22 |  56.22 |   115.07
  16 |        3 |        10 |   11 |   -1 |   0.00 |   171.29
(16 filas)

Si se utilizara también un array para establecer más de un nodo final, la tabla de resultado tendría un nuevo campo end_vid.

A Star

El método pgr_astar es el encargado del cálculo del camino más corto utilizando técnicas heurísticas que limitan las combinaciones de las rutas candidatas analizando la configuración geométrica de los nodos. En redes muy grandes el algoritmo de Dijkstra puede ser inviable debido al tiempo empleado en el cálculo.

Los argumentos que toma pgr_astar son iguales a los de la función pgr_dijkstra salvo que en la consulta SQL habrá que pasarle a pgrouting además los campos x1, y1, x2, y2 que se corresponden con las coordenadas de los puntos inicial y final de cada uno de los tramos.

Se pueden añadir estos campos directamente a la tabla wr y rellenarlos con la orden Update o directamente utilizar los comandos STX_Startpoint y STX_Endpoint dentro del Select que se le pasa a la función. En este caso vamos a rellenar los campos:

routing1=# alter table wr add column x1 double precision;
routing1=# alter table wr add column y1 double precision;
routing1=# alter table wr add column x2 double precision;
routing1=# alter table wr add column y2 double precision;
routing1=# update wr set 
  x1 = ST_X(Stx_startpoint (geom)), 
  y1 = ST_Y(Stx_startpoint (geom)), 
  x2 = ST_X(Stx_endpoint (geom)), 
  y2 = ST_Y(Stx_endpoint (geom));

 

Pages: 1 2 3 4

Tags: , ,

Leave a Reply