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

De esta forma el cálculo utilizando este algoritmo con los mismos parámetros que el último ejemplo con Dijkstra quedará:

routing1=# select * from pgr_astar 
  ('select gid as id, source, target, cost, 
    reverse_cost, x1, y1, x2, y2 from wr', 4, 11, true, true );

 

Turn Restricted Shortest Path

El método pgr_trsp añade al método shortest_path_astar la capacidad de introducir restricciones de giros en la red.

Para ello, es necesario crear una nueva tabla de restricciones, tabla que pasaremos como argumento a la función pgr_trsp y que debe de tener los siguientes campos:

  • to_cost: Double precision -> Nuevo coste del trayecto especificado. Para especificar el trayecto se utiliza los campos target_id y via_path.
  • target_id: Integer -> Identificador del tramo final del trayecto.
  • via_path: Text -> Lista de identificadores de tramo separados por comas, sin especificar el tramo final del trayecto target_id. Si al trayecto actual se ha llegado desde los tramos especificados en esta lista (de forma consecutiva) entonces se utiliza el coste del campo to_cost en lugar del coste normal cost o el coste reverse_cost.

Vamos a modificar la ruta obtenida con la función pgr_dijkstra de la figura estableciendo dos restricciones de giro:

  • No es posible ‘viajar’ al tramo 14 desde el tramo 13, con un coste de 10000.
  • Se penaliza debido a un semáforo el coste de ‘viajar’ al tramo 16 desde el tramo 10, con un coste de 100 (el coste del tramo 16 era de 30).

Primero creamos la tabla de restricciones:

 routing1=# create table restrictions ( 
    to_cost double precision,
    target_id integer,
    via_path text
);

Añadimos la primera restricción: viajar hasta el tramo 14 (target_id), desde el tramo 13 (via_path) no es posible:

routing1=# insert into restrictions (to_cost, target_id, via_path) 
  values (10000, 14, '13');

Añadimos la segunda restricción: viajar hasta el tramo 16 (target_id), desde el tramo 10 (via_path) tiene un coste alto debido al semáforo:

routing1=# insert into restrictions (to_cost, target_id, via_path) 
  values (100, 16, '10')

Ejecutamos el algoritmo:

routing1=# select * from pgr_trsp(
     'select gid as id, source, target, cost, reverse_cost from wr',
     4, 11, true, true, 
     'select to_cost, target_id, via_path from restrictions');
 seq | id1 | id2 |       cost
-----+-----+-----+------------------
   0 |   4 |   8 | 88.3628881374981
   1 |   5 |   4 | 16.9705627484771
   2 |  17 |   5 | 24.1246405523869
   3 |  18 |   6 |               17
   4 |   9 |   7 | 55.9464029227975
   5 |   8 |   9 |               40
   6 |   3 |  11 |               60
   7 |  10 |  21 |  115.06954418959
   8 |  13 |  22 | 56.2227711874824
   9 |  11 |  -1 |                0
(10 filas)

En la tabla de resultado el campo id1 indica el nodo inicial del tramo, y el campo id2 es el número de tramo que atraviesa.

Como se aprecia en el resultado de esta sentencia la solución de la ruta ha cambiado para adaptarse a las restricciones. Nótese como se han evitado atravesar los dos trayectos (tramo 13 a tramo 14 y tramo 10 a tramo 16).

Se podría especificar trayectos de más de dos tramos, por ejemplo, si quisiéramos establecer un coste determinado para el trayecto formado por los tramos 11, 21 y 22 la inserción de la restricción sería:

insert into restrictions (to_cost, target_id, via_path) values (coste, 12, ‘21,11’);

Nótese como los tramos del campo via_path se han separado por comas y aparecen en orden inverso (primero el 21 y luego el 11).

Ver aquí la parte anterior de este taller

Ver aquí la parte siguiente de este taller.

Para comprender adecuadamente la biblioteca Pgrouting y poder utilzarla junto con la potencia de PostGIS se recomienda ampliar los conocimientos sobre este último. Échale un vistazo al curso online de gran éxito de CartoSiG UPV.

Pages: 1 2 3 4

Tags: , ,

Leave a Reply