• Grafo indirecto: la dirección de los tramos no se utiliza, es decir, se puede atravesar el tramo de A->B o de B->A indistintamente y con el mismo coste (campo cost) en ambas direcciones.
• Grafo directo: la dirección de los tramos se utiliza en los cálculos. Pgrouting da la opción de utilizar un coste reverso (reverse_cost) para atravesar el tramo de B->A, estableciendo el parámetro directed en los diferentes algoritmos.
  • Si directed es false entonces no se utiliza el valor reverse_cost, luego los tramos no podrán atravesarse en dirección opuesta.
  • Si directed es true, el coste de atravesar los tramos en dirección opuesta vendrá dado por el valor reverse_cost.

En un grafo indirecto el coste inverso (campo reverse_cost) no se utiliza y será ignorado por pgrouting, ya que ambas direcciones son consideradas igual.

Una forma de modelar la red es definir el grafo como directo con directed a true. Entonces, para una vía de doble sentido se especifica un reverse_cost igual al coste de dirección normal (cost) mientras que para una vía de sentido único el reverse_cost se establece con un valor muy alto para que no sea atravesada en dirección contraria o simplemente con un valor negativo (de esta forma pgrouting eliminará dicha dirección del grofo).

Antes de realizar cualquier cálculo de camino más corto con pgrouting al menos hay que resolver las siguientes cuestiones:

¿Cuál es el coste de atravesar un eje? Pgrouting minimizará este coste para encontrar la ruta más óptima. Se puede considerar dicho coste como la longitud que mide cada tramo o utilizar alguna fórmula un poco más compleja como el tiempo empleado en atravesar dicho tramo (se necesita saber la velocidad media de cada tramo).

¿Los tramos son de sentido único o doble sentido? Si un tramo es de sentido único, el sentido vendrá dado por la dirección de atravesar el tramo partiendo desde el nodo inicial hasta el nodo final (flechas de la figura anterior) y dicho tramo no se podrá atravesar en dirección contraria a no ser que se establezca un reverse_cost apropiado.

Problema del camino más corto

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.

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)

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.