6. Advanced Routing Queries

../_images/route.png

Routing, is not limited to pedestrians and most of the time is used for routing vehicles.

6.1. Routing for Vehicles

A query for vehicle routing generally differs from routing for pedestrians:

  • the road segments are considered directed,
  • Costs can be:
    • Distance
    • Time
    • Euros
    • Pesos
    • Dollars
    • CO2 emittions
    • Ware and tear on the vehicle, etc.
  • The reverse_cost attribute must be taken into account on two way streets.
    • The costs should have the same units as the cost attribute
    • cost and reverse_cost can be different

This is due to the fact that there are roads that are 「one way」.

Depending on the geometry, the valid way:

  • (source, target) segment (cost >= 0 and reverse_cost < 0)
  • (target, source) segment (cost < 0 and reverse_cost >= 0)

So a 「wrong way」 is indicated with a negative value and is not inserted in the graph for processing.

For two way roads cost >= 0 and reverse_cost >= 0 and their values can be different. For example, it is faster going down hill on a sloped road. In general cost and reverse_cost do not need to be length; they can be almost anything, for example time, slope, surface, road type, etc., or they can be a combination of multiple parameters.

The following queries indicate the number of road segments, where a 「one way」 rule applies:

  1. Number of (source, target) segments with cost < 0

    SELECT count(*)
    FROM ways
    WHERE cost < 0;
    
     count 
    -------
         0
    (1 row)
    
    
  2. Number of (target, source) segments with reverse_cost < 0

    SELECT count(*)
    FROM ways
    WHERE reverse_cost < 0;
    
     count 
    -------
       870
    (1 row)
    
    

6.1.1. Exercise 7 - Vehicle routing - Going

From the Serena hotel going to the Fish market by car.

From hotel to market by car.
  • The vehicle is going from vertex 1639 to vertex 1256.
  • Use cost and reverse_cost columns, which are in unit degrees.
SELECT * FROM pgr_dijkstra(
    'SELECT gid AS id,
         source,
         target,
         cost_s AS cost,
         reverse_cost_s AS reverse_cost
        FROM ways',
    1639, 1256,
    directed := true);

Solution to Exercise 7

6.1.2. Exercise 8 - Vehicle routing - Returning

From Fish market going to the Serena hotel by car.

From market to hotel by car.
  • The vehicle is going from vertex 1256 to vertex 1639.
  • Use cost and reverse_cost columns, which are in unit degrees.
SELECT * FROM pgr_dijkstra(
    'SELECT gid AS id,
         source,
         target,
         cost_s AS cost,
         reverse_cost_s AS reverse_cost
        FROM ways',
    1256, 1639,
    directed := true);

Solution to Exercise 8

注釈

On a directed graph, going and coming back routes, most of the time are different.

6.1.3. Exercise 9 - Vehicle routing when 「time is money」

From Fish market going to the Serena hotel by taxi.

From market to hotel by taxi.
  • The vehicle is going from vertex 1256 to vertex 1639.
  • The cost is $100 per hour.
  • Use cost_s and reverse_cost_s columns, which are in unit seconds.
  • The duration in hours is cost / 3600
  • The cost in $ is cost / 3600 * 100
SELECT * FROM pgr_dijkstra('
    SELECT gid AS id,
        source,
        target,
        cost_s / 3600 * 100 AS cost,
        reverse_cost_s / 3600 * 100 AS reverse_cost
        FROM ways',
    1256, 1639);

Solution to Exercise 9

注釈

Comparing with Exercise 8:

  • The total number of records are identical
  • The node sequence is identical
  • The edge sequence is identical
  • The cost and agg_cost results are directly proportional

6.2. Cost Manipulations

Detail. Not all crossings are vertices in the graph

When dealing with data, being aware of what kind of data is being used, can improve results.

  • Vehciles can not circulate pedestrian ways,
  • Likewise, routing not using pedestrian ways

Will make the results closer to reality.

When converting data from OSM format using the osm2pgrouting tool, there is an additional tables: configuration

In the image above there is a detail of the tag_id of the roads.

osm way types

SELECT tag_id, tag_key, tag_value FROM configuration ORDER BY tag_id;
 tag_id |  tag_key  |     tag_value
--------+-----------+-------------------
    100 | highway   | road
    101 | highway   | motorway
    102 | highway   | motorway_link
    103 | highway   | motorway_junction
    104 | highway   | trunk
    105 | highway   | trunk_link
    106 | highway   | primary
    107 | highway   | primary_link
    108 | highway   | secondary
    109 | highway   | tertiary
    110 | highway   | residential
    111 | highway   | living_street
    112 | highway   | service
    113 | highway   | track
    114 | highway   | pedestrian
    115 | highway   | services
    116 | highway   | bus_guideway
    117 | highway   | path
    118 | highway   | cycleway
    119 | highway   | footway
    120 | highway   | bridleway
    121 | highway   | byway
    122 | highway   | steps
    123 | highway   | unclassified
    124 | highway   | secondary_link
    125 | highway   | tertiary_link
    201 | cycleway  | lane
    202 | cycleway  | track
    203 | cycleway  | opposite_lane
    204 | cycleway  | opposite
    301 | tracktype | grade1
    302 | tracktype | grade2
    303 | tracktype | grade3
    304 | tracktype | grade4
    305 | tracktype | grade5
    401 | junction  | roundabout
(36 rows)

Also on the ways table there is a column that can be used to JOIN with the configuration table.

The ways types

SELECT distinct tag_id, tag_key, tag_value
FROM ways JOIN configuration USING (tag_id)
ORDER BY tag_id;
 tag_id | tag_key  |   tag_value
--------+----------+---------------
    104 | highway  | trunk
    105 | highway  | trunk_link
    106 | highway  | primary
    108 | highway  | secondary
    109 | highway  | tertiary
    110 | highway  | residential
    112 | highway  | service
    113 | highway  | track
    117 | highway  | path
    118 | highway  | cycleway
    119 | highway  | footway
    122 | highway  | steps
    123 | highway  | unclassified
    125 | highway  | tertiary_link
    204 | cycleway | opposite
(15 rows)

In this workshop, costs are going to be manipulated using the configuration table.

6.2.1. Exercise 10 - Vehicle routing without penalization

From the Botanical garden to the Museum

From the Botanical garden to the Museum
  • The vehicle is going from vertex 856 to vertex 1461.
  • The vehicle’s cost in this case will be in seconds.
  • All roads have a penalty of 1
  • Costs are to be multiplied by penalty
  • Costs wont change (times 1 leaves the value unchanged).
  • The configuration table is linked with the ways table by the tag_id field using a JOIN.

ALTER TABLE configuration ADD COLUMN penalty FLOAT;
-- No penalty
UPDATE configuration SET penalty=1;


SELECT * FROM pgr_dijkstra('
    SELECT gid AS id,
        source,
        target,
        cost_s * penalty AS cost,
        reverse_cost_s * penalty AS reverse_cost
    FROM ways JOIN configuration
    USING (tag_id)',
    856, 1461);

Solution to Exercise 10

6.2.2. Exercise 11 - Vehicle routing with penalization

Change the cost values for the configuration table, in such a way, that the * pedestrian roads are not used * Using residential roads its not encouraged. * Using 「faster」 roads is highly encouraged. * The penalty values can be changed UPDATE queries.

注釈

This values are an exageration

-- Not including pedestrian ways
UPDATE configuration SET penalty=-1.0 WHERE tag_value IN ('steps','footway');
-- Penalizing with 5 times the costs
UPDATE configuration SET penalty=5 WHERE tag_value IN ('residential');
-- Encuraging the use of "fast" roads
UPDATE configuration SET penalty=0.5 WHERE tag_value IN ('tertiary');
UPDATE configuration SET penalty=0.3 WHERE tag_value
IN ('primary','primary_link',
    'trunk','trunk_link',
    'motorway','motorway_junction','motorway_link',
    'secondary');

From the Botanical garden to the Museum with penalization.

  • The vehicle is going from vertex 856 to vertex 1461.
  • Use cost_s and reverse_cost_s columns, which are in unit seconds.
  • Costs are to be multiplied by penalty
  • The configuration table is linked with the ways table by the tag_id field using a JOIN.
SELECT * FROM pgr_dijkstra('
    SELECT gid AS id,
        source,
        target,
        cost_s * penalty AS cost,
        reverse_cost_s * penalty AS reverse_cost
    FROM ways JOIN configuration
    USING (tag_id)',
    856, 1461);
rom the Botanical garden to the Museum

Solution to Exercise 11

注釈

Comparing with Exercise 9:

  • The total number of records changed.
  • The node sequence changed.
  • The edge sequence changed.
  • The route is avoiding the residential roads that have tag_id = 110