2. Enrutamiento peatonal ¶

pgRouting se llamó por primera vez pgDijkstra, porque implementó sólo la búsqueda de ruta más corta con el algoritmo Dijkstra. Más tarde se agregaron otras funciones y se cambió el nombre de la biblioteca a pgRouting.

2.1. pgr_dijkstra ¶

Dijkstra algorithm was the first algorithm implemented in pgRouting. It doesn’t require other attributes than the identifiers id, source and target and the weights cost and reverse_cost.

Puede especificar cuándo considerar el grafo como dirigido o sin dirección.

Resumen de funciones

pgr_dijkstra(Edges SQL, start_vid,  end_vid  [, directed])
pgr_dijkstra(Edges SQL, start_vid,  end_vids [, directed])
pgr_dijkstra(Edges SQL, start_vids, end_vid  [, directed])
pgr_dijkstra(Edges SQL, start_vids, end_vids [, directed])
pgr_dijkstra(Edges SQL, Combinations SQL [, directed])

RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
    OR EMPTY SET

La descripción de los parámetros se puede encontrar en pgr_dijkstra.

Nota

Muchas funciones pgRouting tienen sql::text como uno de sus argumentos. Aunque esto puede parecer confuso al principio, hace que las funciones sean muy flexibles, ya que el usuario puede pasar una instrucción SELECT como argumento de función siempre y cuando el resultado devuelto contenga el número necesario de atributos y los nombres correctos.
La mayoría de los algoritmos implementados pgRouting no requieren la geometría.
Las funciones pgRouting no devuelven una geometría, sino solo una lista ordenada de nodos o aristas.

Identificadores de las consultas

La asignación de los identificadores de vértices en las columnas de origen y destino puede ser diferentes, los siguientes ejercicios usarán los resultados de esta consulta. Para el taller, se van a utilizar algunos lugares cercanos al evento FOSS4G. Estas ubicaciones se encuentran dentro de esta área https://www.openstreetmap.org#map=15/-34.5847/-58.3970

2385630446 Nadir Xhemali Danijolli
1838481592 Qendra Sprotive
1840522495 Kalaja e Prizrenit
6917727056 Inovation and Training Park
2385655026 Lidhja Shqiptare e Prizrenit

Conéctese a la base de datos, si no está conectado:

psql city_routing

Obtener los identificadores de vértice

SELECT osm_id, id FROM ways_vertices_pgr
WHERE osm_id IN (2385630446, 1838481592, 1840522495, 6917727056, 2385655026)
ORDER BY osm_id;

   osm_id   |  id  
------------+------
 1838481592 | 2592
 1840522495 | 2820
 2385630446 | 3770
 2385655026 | 3829
 6917727056 | 5912
(5 rows)

2385630446 Nadir Xhemali Danijolli (3770)
1838481592 Qendra Sprotive (2592)
1840522495 Kalaja e Prizrenit (2820)
6917727056 Inovation and Training Park (5912)
2385655026 Lidhja Shqiptare e Prizrenit (3829)

El correspondiente id se muestra en la siguiente imagen y una ruta de ejemplo de «Kalaja e Prizrenit» a «Lidhja Shqiptare e Prizrenit».

2.1.1. Ejercicio 1: Ruteo para un solo peatón ¶

Problema:

Caminando
- desde «Nadir Xhemali Danijolli»
- hacia «Kalaja e Prizrenit».
Calcular rutas con costos en longitud con unidades por defecto generadoa por osm2pgRouting.

Solución:

El peatón quiere pasar del vértice 3770 al vértice 2820 (líneas 9 y 10).
El costo del peatón es en términos de longitud. En este caso length (línea 6), que fue calculada por osm2pgrouting, está en la unidad degrees.
Desde una perspectiva peatonal, el grafo es no dirigido (línea 11), es decir, el peatón puede moverse en ambas direcciones en todos los segmentos.

SELECT * FROM pgr_dijkstra(
    '
      SELECT gid AS id,
        source,
        target,
        length AS cost
      FROM ways
    ',
 3770,
 2820,
    directed := false);

Ejercicio: 1 (Capítulo: Peatón)

Nota

El atributo de costo devuelto representa el costo especificado en la consulta SQL interna (argumento edges_sql::text). En este ejemplo, el costo es length en la unidad «grados». El costo puede ser tiempo, distancia o cualquier combinación de ambos o cualquier otro atributo o una fórmula personalizada.
Los resultados de node y edge pueden variar dependiendo de la asignación de los identificadores a los vértices dados por osm2pgrouting.

2.1.2. Ejercicio 2: Muchos peatones van al mismo destino ¶

Problema:

Caminando
- desde «Nadir Xhemali Danijolli» y «Qendra Sprotive»
- hacia el «Kalaja e Prizrenit».
Calculate routes with costs in osm2pgRouting length_m which is in meters.

Solución:

Los peatones están saliendo en los vértices 3770 y 2592 (línea 9).
Todos los peatones quieren ir al vértice 2820 (línea 10).
El costo de estar en metros usando el atributo length_m (línea 6).

SELECT * FROM pgr_dijkstra(
    '
      SELECT gid AS id,
        source,
        target,
        length_m AS cost
      FROM ways
    ',
ARRAY[3770,2592],
2820,
directed := false);

Ejercicio: 2 (Capítulo: Peatón)

2.1.3. Ejercicio 3: Muchos peatones que salen de la misma ubicación ¶

Problema:

Caminando
- desde «Kalaja e Prizrenit»
- hacia «Nadir Xhemali Danijolli» y «Qendra Sprotive»
Calcular rutas con costos en segundos.

Solución:

Todos los peatones están saliendo del vértice 2820 (línea 9).
Los peatones quieren ir a lugares 3770 y 2592 (línea 10).
El costo a ser en segundos, con una velocidad de marcha s = 1.3 m/s y t = d/s (línea 6).

SELECT * FROM pgr_dijkstra(
    '
      SELECT gid AS id,
        source,
        target,
        length_m / 1.3 AS cost
      FROM ways
    ',
2820,
ARRAY[3770,2592],
directed := false);

Ejercicio: 3 (Capítulo: Peatón)

2.1.4. Ejercicio 4: Muchos peatones que van a diferentes destinos ¶

Problema:

Caminando
- desde «Nadir Xhemali Danijolli» y «Qendra Sprotive»
- hacia «Inovation and Training Park» y «Lidhja Shqiptare e Prizrenit»
Calcular rutas con costos en minutos.

Solución:

Los peatones parten de 3770 y 2592 (línea 9).
Los peatones quieren ir a destinos 5912 y 3829 (línea 10).
El costo a ser en minutos, con una velocidad de caminata s = 1.3 m/s y t = d/s (línea 6).
El resultado suma los costes por destino.

SELECT * FROM pgr_dijkstra(
    '
      SELECT gid AS id,
       source,
       target,
       length_m / 1.3 / 60 AS cost
      FROM ways
    ',
ARRAY[3770, 2592],
ARRAY[5912, 3829],
directed := false);

Ejercicio: 4 (Capítulo: Peatón)

Nota

Inspección de los resultados, buscando totales (edge = -1):

Desde 3770 al vértice 5912 toma 26.22 minutos (seq = 94)

Desde 3770 al vértice 3829 toma 7.11 minutos (seq = 48)

Desde 2592 al vértice 5912 toma 8.31 minutos (seq = 33)

Desde 2592 al vértice 3829 toma 12.56 minutos (seq = 20)

2.2. pgr_dijkstraCost ¶

Cuando el objetivo principal es calcular el costo total, sin «inspeccionar» los resultados de la pgr_dijkstra usando pgr_dijkstraCost devuelve un resultado más compacto.

Resumen de funciones

pgr_dijkstraCost(edges_sql, start_vid,  end_vid  [, directed])
pgr_dijkstraCost(edges_sql, start_vid,  end_vids [, directed])
pgr_dijkstraCost(edges_sql, start_vids, end_vid  [, directed])
pgr_dijkstraCost(edges_sql, start_vids, end_vids [, directed])
pgr_dijkstraCost(edges_sql, combinations_sql   [, directed])

RETURNS SET OF (start_vid, end_vid, agg_cost)
    OR EMPTY SET

La descripción de los parámetros se puede encontrar en pgr_dijkstraCost

2.2.1. Exercise 5: Time for many Pedestrians going to different destinations ¶

Problema:

Caminando
- desde «Nadir Xhemali Danijolli» o «Qendra Sprotive»
- desde «Inovation and Training Park» o «Lidhja Shqiptare e Prizrenit»
Obtener solo el costo en minutos.

Solución:

Los peatones parten de 3770 y 2592 (línea 10).
Los peatones quieren ir a destinos 5912 y 3829 (línea 11).
El costo a ser en minutos, con una velocidad de caminata s = 1.3 m/s y t = d/s (línea 7).
Resultado como costos agregados.

SELECT *
FROM pgr_dijkstraCost(
    '
      SELECT gid AS id,
       source,
       target,
       length_m  / 1.3 / 60 AS cost
      FROM ways
    ',
ARRAY[3770, 2592],
ARRAY[5912, 3829],
directed := false);

Ejercicio: 5 (Capítulo: Peatón)

Compárese con las notas del Ejercicio 4: Muchos peatones que van a diferentes destinos.

2.2.2. Ejercicio 6: Muchos peatones van a diferentes destinos resumiendo costos totales por salida ¶

Problema:

Caminando
- desde «Nadir Xhemali Danijolli» o «Qendra Sprotive»
- desde «Inovation and Training Park» o «Lidhja Shqiptare e Prizrenit»
Reportar costos en minutos.

Solución:

Los peatones parten de 3770 y 2592 (línea 10).
Los peatones quieren ir a destinos 5912 y 3829 (línea 11).
El costo a ser en minutos, con una velocidad de caminata s = 1.3 m/s y t = d/s (línea 7).
El resultado suma los costes por destino.

SELECT start_vid, sum(agg_cost)
FROM pgr_dijkstraCost(
    '
      SELECT gid AS id,
        source,
        target,
        length_m  / 1.3 / 60 AS cost
      FROM ways
    ',
    ARRAY[3770, 2592],
    ARRAY[5912, 3829],
    directed := false)
GROUP BY start_vid
ORDER BY start_vid;

Ejercicio: 6 (Capítulo: Peatón)

Nota

Una interpretación del resultado puede ser: En general, es más rápido salir de «Qendra Sprotive» que de «Nadir Xhemali Danijolli»