2. Enrutamiento peatonal

../_images/route.png

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

El algoritmo Dijkstra fue el primer algoritmo implementado en pgRouting. No requiere otros atributos que no sean id, source y target ID y cost y 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 de atributo 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

The assignment of the vertices identifiers on the source and target columns may be different, the following exercises will use the results of this query. For the workshop, some locations near of the FOSS4G event are going to be used. These locations are within this area https://www.openstreetmap.org#map=15/-34.5847/-58.3970

  • 266939565 Mercato Centrale

  • 2531656518 Stazione di Santa Maria Novella

  • 5020458299 Palazzo dei Congressi

  • 6483155124 Hotel Albani

  • 1798374718 Cattedrale di Santa Maria del Fiore

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

psql city_routing

Obtener los identificadores de vértice

1SELECT osm_id, id FROM ways_vertices_pgr
2WHERE osm_id IN (266939565, 2531656518, 5020458299, 6483155124, 1798374718)
3ORDER BY osm_id;

1   osm_id   |  id   
2------------+-------
3  266939565 |   956
4 1798374718 |  6354
5 2531656518 |  7039
6 5020458299 | 11186
7 6483155124 | 21407
8(5 rows)
9
  • 266939565 Mercato Centrale (956)

  • 2531656518 Stazione di Santa Maria Novella (7039)

  • 5020458299 Palazzo dei Congressi (11186)

  • 6483155124 Hotel Albani (21407)

  • 1798374718 Cattedrale di Santa Maria del Fiore (6354)

El correspondiente id se muestra en la siguiente imagen y una ruta de ejemplo de «Palazzo dei Congressi» a «Cattedrale di Santa Maria del Fiore».

../_images/route.png

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

Problema:

  • Caminando de «Mercato Centrale» al «Palazzo dei Congressi».

Desde el |place_1| al |place_3|

Solución:

  • El peatón quiere pasar del vértice 956 al vértice 11186 (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.

 1SELECT * FROM pgr_dijkstra(
 2    '
 3      SELECT gid AS id,
 4        source,
 5        target,
 6        length AS cost
 7      FROM ways
 8    ',
 9 956,
10 11186,
11    directed := false);

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

Nota

  • El atributo cost devuelto representa el costo especificado en la consulta SQL interna (edges_sql::text argument). En este ejemplo, el costo es length en la unidad «degrees». 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 «Mercato Centrale» y «Stazione di Santa Maria Novella» hasta «Palazzo dei Congressi».

Desde |place_1| y |place_2| a |place_3|

Solución:

  • Los peatones están saliendo en los vértices 956 y 7039 (línea 9).

  • Todos los peatones quieren ir al vértice 11186 (línea 10).

  • El costo de estar en metros usando el atributo length_m (línea 6).

 1SELECT * FROM pgr_dijkstra(
 2    '
 3      SELECT gid AS id,
 4        source,
 5        target,
 6        length_m AS cost
 7      FROM ways
 8    ',
 9ARRAY[956,7039],
1011186,
11directed := false);

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

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

Problema:

  • Caminando desde «Palazzo dei Congressi» hasta «Mercato Centrale» y «Stazione di Santa Maria Novella» (en segundos).

../_images/pedestrian-route2.png

Solución:

  • Todos los peatones están saliendo del vértice 11186 (línea 9).

  • Los peatones quieren ir a lugares 956 y 7039 (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).

 1SELECT * FROM pgr_dijkstra(
 2    '
 3      SELECT gid AS id,
 4        source,
 5        target,
 6        length_m / 1.3 AS cost
 7      FROM ways
 8    ',
 911186,
10ARRAY[956,7039],
11directed := false);

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

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

Problema:

  • Walking from Mercato Centrale and Stazione di Santa Maria Novella to the «Hotel Albani» and «Cattedrale di Santa Maria del Fiore» (in minutes).

../_images/pedestrian-route4.png

Solución:

  • Los peatones parten de 956 y 7039 (línea 9).

  • Los peatones quieren ir a destinos 21407 y 6354 (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.

 1SELECT * FROM pgr_dijkstra(
 2    '
 3      SELECT gid AS id,
 4       source,
 5       target,
 6       length_m / 1.3 / 60 AS cost
 7      FROM ways
 8    ',
 9ARRAY[956, 7039],
10ARRAY[21407, 6354],
11directed := false);

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

Nota

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

  • Ir a vértice 21407:

    • desde 956 toma 8.84.. minutos (seq = 35)

    • desde 7039 toma 5.84.. minutos (seq = 74)

  • Ir a vértice 6354:

    • desde 956 toma 7.44.. minutos (seq = 7)

    • desde 7039 toma 12.06.. minutos (seq = 55)

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. Ejercicio 5: Muchos peatones que van a diferentes destinos devolviendo costos agregados

Problema:

  • Caminando desde los hoteles hasta el «Hotel Albani» o «Cattedrale di Santa Maria del Fiore» (obtener sólo el costo en minutos).

De los hoteles a |place_4| y |place_5|

Solución:

  • Los peatones parten de 956 y 7039 (línea 10).

  • Los peatones quieren ir a destinos 21407 y 6354 (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.

 1SELECT *
 2FROM pgr_dijkstraCost(
 3    '
 4      SELECT gid AS id,
 5       source,
 6       target,
 7       length_m  / 1.3 / 60 AS cost
 8      FROM ways
 9    ',
10ARRAY[956, 7039],
11ARRAY[21407, 6354],
12directed := false);

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

Compare with Exercise 4: Many Pedestrians going to different destinations “s note.

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

Problema:

  • Caminando desde los hoteles hasta el «Hotel Albani» o «Cattedrale di Santa Maria del Fiore» (resumir el costo en minutos).

Solución:

  • Los peatones parten de 956 y 7039 (línea 10).

  • Los peatones quieren ir a destinos 21407 y 6354 (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.

 1SELECT start_vid, sum(agg_cost)
 2FROM pgr_dijkstraCost(
 3    '
 4      SELECT gid AS id,
 5        source,
 6        target,
 7        length_m  / 1.3 / 60 AS cost
 8      FROM ways
 9    ',
10    ARRAY[956, 7039],
11    ARRAY[21407, 6354],
12    directed := false)
13GROUP BY start_vid
14ORDER BY start_vid;

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

Nota

Una interpretación del resultado puede ser: En general, es más rápido apartarse de la «Stazione di Santa Maria Novella» que de la «Mercato Centrale».