3. Enrutamiento de vehículos

../_images/ad7.png

Ruteo, no se limita a los peatones y la mayor parte del tiempo se utiliza para la ruta de vehículos.

3.1. Ruteo para vehículos

Una consulta para el enrutamiento de vehículos generalmente difiere de la ruta para los peatones:

  • Los segmentos de carretera se consideran dirigidos

  • Los costos pueden ser:

    • Distancia

    • Tiempo

    • Euros

    • Pesos

    • Dólares

    • CO2 emisiones

    • Desgaste en el vehículo, etc.

  • El atributo reverse_cost debe tenerse en cuenta en calles de dos vías.

    • Los costes deben tener las mismas unidades que el atributo cost

    • Los valores cost y reverse_cost pueden ser diferentes

      • Debido al hecho de que hay carreteras que son de una manera

Dependiendo de la geometría, la forma válida:

  • (source, target) segmento IF cost >= 0 AND reverse_cost < 0

  • (target, source) segmento IF cost < 0 AND reverse_cost >= 0

Un camino incorrecto se indica con un valor negativo y no se inserta en el grafo para su procesamiento.

Carreteras bidireccionales -IF cost >= 0 AND reverse_cost >= 0 y sus valores pueden ser diferentes. Por ejemplo, es más rápido ir cuesta abajo en una carretera inclinada. En general, cost y reverse_cost no necesitan ser de longitud; pueden ser casi cualquier cosa, por ejemplo, tiempo, pendiente, superficie, tipo de carretera, etc., o pueden ser una combinación de múltiples parámetros.

Las siguientes consultas indican el número de segmentos de carretera, donde se aplica una regla «unidireccional»:

  1. Número de (source, target) segmentos con cost < 0 (line 3).

    1SELECT count(*)
    2FROM ways
    3WHERE cost < 0;
    
    1 count 
    2-------
    3     0
    4(1 row)
    5
    
  2. Número de segmentos (target, source) segmentos con reverse_cost < 0 (line 3).

    1SELECT count(*)
    2FROM ways
    3WHERE reverse_cost < 0;
    
    1 count 
    2-------
    3   931
    4(1 row)
    5
    

3.1.1. Ejercicio 1: Ruteo de vehículos - ida

Problema:

  • Desde «Nadir Xhemali Danijolli» hacia «Kalaja e Prizrenit» en automóvil.

Desde |place_1| al |place_3| en coche.

Solución:

  • El vehículo va desde vértice 3770 (line 10) hacia 2820 (line 11).

  • Utilice las columnas cost (línea 6) y reverse_cost (línea 7), que están en la unidad grados.

 1SELECT * FROM pgr_dijkstra(
 2  '
 3  SELECT gid AS id,
 4    source,
 5    target,
 6    cost,
 7    reverse_cost
 8  FROM ways
 9  ',
103770,
112820,
12directed := true);

Ejercicio: 1 (Capítulo: vehículo)

3.1.2. Ejercicio 2: Ruteo de vehículos - regreso

Problema:

  • Desde «Kalaja e Prizrenit» hacia «Nadir Xhemali Danijolli» en automóvil.

Desde |place_3| al |place_1| en coche.

Solución:

  • El vehículo va de vértice 2820 (línea 10) para 3770 (línea 11).

  • Utilice las columnas cost (línea 6) y reverse_cost (línea 7), que están en la unidad grados.

 1SELECT * FROM pgr_dijkstra(
 2  '
 3    SELECT gid AS id,
 4      source,
 5      target,
 6      cost,
 7      reverse_cost
 8    FROM ways
 9  ',
102820,
113770,
12directed := true);

Ejercicio: 2 (Capítulo: Vehículo)

Nota

En un grafo dirigido, las rutas para ir y volver, la mayoría de las veces son diferentes.

3.1.3. Ejercicio 3: Ruteo de vehículos cuando el tiempo es dinero

Problema:

  • Desde «Nadir Xhemali Danijolli» hacia «Kalaja e Prizrenit» en taxi.

Desde |place_1| a |place_3| en taxi.

Solución:

  • El vehículo va desde vértice 3770 (line 10) hacia 2820 (line 11).

  • El costo es de $100 por hora.

  • Utilizar las columnas cost_s (línea 6) y reverse_cost_s (línea 7) que están en unidad de segundos.

  • La duración en horas es cost_s / 3600.

  • El costo en $ es cost_s / 3600 * 100.

 1SELECT * FROM pgr_dijkstra(
 2  '
 3    SELECT gid AS id,
 4      source,
 5      target,
 6      cost_s / 3600 * 100 AS cost,
 7      reverse_cost_s / 3600 * 100 AS reverse_cost
 8    FROM ways
 9  ',
103770,
112820);

Ejercicio: 3 (Capítulo: Vehículo)

Nota

Comparación con Ejercicio 2: Ruteo de vehículos - regreso:

  • El número total de registros es idéntico.

  • La secuencia de nodos es idéntica.

  • La secuencia de aristas es idéntica.

  • El coste y los resultados agg_cost son directamente proporcionales.

3.2. Manipulaciones de costes

Al tratar con datos, ser consciente de qué tipo de datos se están utilizando puede mejorar los resultados.

  • Los vehículos no pueden circular por vías peatonales


Penalizar o eliminar las vías peatonales hará que los resultados se acerquen a la realidad.

Al convertir datos del formato OSM mediante la herramienta osm2pgrouting, hay una tabla adicional: configuration.

La estructura de tabla configuration se puede obtener con el siguiente comando.

1\dS+ configuration
 1                                                                 Table "public.configuration"
 2      Column       |       Type       | Collation | Nullable |                  Default                  | Storage  | Compression | Stats target | Description 
 3-------------------+------------------+-----------+----------+-------------------------------------------+----------+-------------+--------------+-------------
 4 id                | integer          |           | not null | nextval('configuration_id_seq'::regclass) | plain    |             |              | 
 5 tag_id            | integer          |           |          |                                           | plain    |             |              | 
 6 tag_key           | text             |           |          |                                           | extended |             |              | 
 7 tag_value         | text             |           |          |                                           | extended |             |              | 
 8 priority          | double precision |           |          |                                           | plain    |             |              | 
 9 maxspeed          | double precision |           |          |                                           | plain    |             |              | 
10 maxspeed_forward  | double precision |           |          |                                           | plain    |             |              | 
11 maxspeed_backward | double precision |           |          |                                           | plain    |             |              | 
12 force             | character(1)     |           |          |                                           | extended |             |              | 
13Indexes:
14    "configuration_pkey" PRIMARY KEY, btree (id)
15    "configuration_tag_id_key" UNIQUE CONSTRAINT, btree (tag_id)
16Referenced by:
17    TABLE "ways" CONSTRAINT "ways_tag_id_fkey" FOREIGN KEY (tag_id) REFERENCES configuration(tag_id)
18Access method: heap
19Options: autovacuum_enabled=false
20
valores de `tag_id`

En la imagen de arriba hay un detalle de la tag_id de las carreteras.

Los tipos OSM way:

1SELECT tag_id, tag_key, tag_value
2FROM configuration
3ORDER BY tag_id;
 1 tag_id |  tag_key  |     tag_value     
 2--------+-----------+-------------------
 3    100 | highway   | road
 4    101 | highway   | motorway
 5    102 | highway   | motorway_link
 6    103 | highway   | motorway_junction
 7    104 | highway   | trunk
 8    105 | highway   | trunk_link
 9    106 | highway   | primary
10    107 | highway   | primary_link
11    108 | highway   | secondary
12    109 | highway   | tertiary
13    110 | highway   | residential
14    111 | highway   | living_street
15    112 | highway   | service
16    113 | highway   | track
17    114 | highway   | pedestrian
18    115 | highway   | services
19    116 | highway   | bus_guideway
20    117 | highway   | path
21    118 | highway   | cycleway
22    119 | highway   | footway
23    120 | highway   | bridleway
24    121 | highway   | byway
25    122 | highway   | steps
26    123 | highway   | unclassified
27    124 | highway   | secondary_link
28    125 | highway   | tertiary_link
29    201 | cycleway  | lane
30    202 | cycleway  | track
31    203 | cycleway  | opposite_lane
32    204 | cycleway  | opposite
33    301 | tracktype | grade1
34    302 | tracktype | grade2
35    303 | tracktype | grade3
36    304 | tracktype | grade4
37    305 | tracktype | grade5
38    401 | junction  | roundabout
39(36 rows)
40

Además, en la tabla ways hay una columna que se puede utilizar para JOIN con la tabla configuration.

Los tipos de caminos:

1SELECT distinct tag_id, tag_key, tag_value
2FROM ways JOIN configuration USING (tag_id)
3ORDER BY tag_id;
 1 tag_id | tag_key |   tag_value    
 2--------+---------+----------------
 3    101 | highway | motorway
 4    102 | highway | motorway_link
 5    106 | highway | primary
 6    107 | highway | primary_link
 7    108 | highway | secondary
 8    109 | highway | tertiary
 9    110 | highway | residential
10    111 | highway | living_street
11    112 | highway | service
12    113 | highway | track
13    114 | highway | pedestrian
14    115 | highway | services
15    117 | highway | path
16    119 | highway | footway
17    120 | highway | bridleway
18    122 | highway | steps
19    123 | highway | unclassified
20    124 | highway | secondary_link
21    125 | highway | tertiary_link
22(19 rows)
23

En este taller, los costes se van a manipular utilizando la tabla configuración.

3.2.1. Ejercicio 4: Ruteo de vehículos sin penalización

Problema:

  • Desde «Kalaja e Prizrenit» hacia «Nadir Xhemali Danijolli»

Desde |place_3| a |place_1|

Solución:

  • El vehículo va desde el vértice 2820 (línea 17) al vértice 3770 (línea 18).

  • El costo del vehículo en este caso será en segundos.

  • Todas las carreteras tienen una penalización de 1 (línea 3).

  • Los costos (en segundos) deben multiplicarse por penalty (líneas 12 y 13).

  • Los costes no cambiarán (las veces 1 dejan el valor sin cambios).

  • La tabla configuration está vinculada a la tabla ways mediante el campo tag_id y usando un JOIN (líneas 14 y 15).

 1ALTER TABLE configuration ADD COLUMN penalty FLOAT;
 2-- No penalty
 3UPDATE configuration SET penalty=1;
 4
 5
 6SELECT *
 7FROM pgr_dijkstra(
 8  '
 9    SELECT gid AS id,
10        source,
11        target,
12        cost_s * penalty AS cost,
13        reverse_cost_s * penalty AS reverse_cost
14    FROM ways JOIN configuration
15    USING (tag_id)
16  ',
172820,
183770);

Ejercicio: 4 (Capítulo: Vehículo)

3.2.2. Ejercicio 5: Ruteo de vehículos con penalización

Concepto:

  • Cambiar los valores de coste de la tabla configuration de forma que el

    • No se utilizan carreteras peatonales.

    • No se fomenta el uso de carreteras residenciales.

    • El uso de carreteras «más rápidas» es muy alentador.

    • Los valores penalty se pueden cambiar con las consultas UPDATE.

Nota

Estos valores son una exageración.

 1-- Not including pedestrian ways
 2UPDATE configuration SET penalty=-1.0 WHERE tag_value IN ('steps','footway','pedestrian');
 3
 4-- Penalizing with 5 times the costs
 5UPDATE configuration SET penalty=5 WHERE tag_value IN ('unclassified');
 6
 7-- Encuraging the use of "fast" roads
 8UPDATE configuration SET penalty=0.5 WHERE tag_value IN ('tertiary');
 9UPDATE configuration SET penalty=0.3 WHERE tag_value IN (
10    'primary','primary_link',
11    'trunk','trunk_link',
12    'motorway','motorway_junction','motorway_link',
13    'secondary');

Problema:

  • Desde «Kalaja e Prizrenit» hacia «Nadir Xhemali Danijolli» con la penalización.

Desde |place_5| a |place_3|

Solución:

  • El vehículo va de vértice 2820 (línea 11) al vértice 3770 (línea 12).

  • Utilizar las columnas cost_s (línea 6) y reverse_cost_s (línea 7) que están en unidad de segundos.

  • Los costos deben multiplicarse por penalty (líneas 6 y 7).

  • La tabla configuration está vinculada a la tabla ways por el campo:code:tag_id mediante un campo JOIN (líneas 8 y 9).

 1SELECT * FROM pgr_dijkstra(
 2  '
 3    SELECT gid AS id,
 4        source,
 5        target,
 6        cost_s * penalty AS cost,
 7        reverse_cost_s * penalty AS reverse_cost
 8    FROM ways JOIN configuration
 9    USING (tag_id)
10  ',
112820,
123770);

Ejercicio: 5 (Capítulo: Vehículo)

Nota

Comparando con Ejercicio 3: Ruteo de vehículos cuando el tiempo es dinero:

  • El número total de registros cambió.

  • La secuencia de nodos cambió.

  • La secuencia de bordes cambió.

  • La ruta está evitando las carreteras residenciales que tienen tag_id = 110.

  • El costo no cambió proporcionalmente debido a la penalización a algunas de las carreteras que era uniforme (penalización = 1) mientras que el enrutamiento con el costo como dinero.