3. Vehicle Routing

../_images/ad7.png

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

3.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 emissions

    • Wear 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 values can be different

      • Due to the fact that there are roads that are one way

Depending on the geometry, the valid way:

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

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

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

Two way roads - IF 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 (line 3).

    1SELECT count(*)
2FROM ways
3WHERE cost < 0;

    1 count 
2-------
3     0
4(1 row)
5

  2. Number of (target, source) segments with 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. Exercise 1: Vehicle routing - going

Problem:

  • From the “Nadir Xhemali Danijolli” to the “Kalaja e Prizrenit” by car.

From |place_1| to the |place_3| by car.

Solution:

  • The vehicle is going from vertex 3770 (line 10) to 2820 (line 11).

  • Use cost (line 6) and reverse_cost (line 7) columns, which are in unit degrees.

 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);

Exercise: 1 (Chapter: Vehicle)

3.1.2. Exercise 2: Vehicle routing - returning

Problem:

  • From “Kalaja e Prizrenit” to the “Nadir Xhemali Danijolli” by car.

From |place_3| to the |place_1| by car.

Solution:

  • The vehicle is going from vertex 2820 (line 10) to 3770 (line 11).

  • Use cost (line 6) and reverse_cost (line 7) columns, which are in unit degrees.

 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);

Exercise: 2 (Chapter: Vehicle)

Note

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

3.1.3. Exercise 3: Vehicle routing when time is money

Problem:

  • From “Nadir Xhemali Danijolli” to the “Kalaja e Prizrenit” by taxi.

From |place_1| to |place_3| by taxi.

Solution:

  • The vehicle is going from vertex 3770 (line 10) to 2820 (line 11).

  • The cost is $100 per hour.

  • Use cost_s (line 6) and reverse_cost_s (line 7) columns, which are in unit seconds.

  • The duration in hours is cost_s / 3600.

  • The cost in $ is 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);

Exercise: 3 (Chapter: Vehicle)

Note

Comparing with Exercise 2: Vehicle routing - returning:

  • 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.

3.2. Cost manipulations

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

  • Vehicles can not circulate on pedestrian ways


Penalizing or removal of pedestrian ways will make the results closer to reality.

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

The configuration table structure can be obtained with the following command.

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
tag_id values

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

The OSM way types:

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

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

The ways types:

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

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

3.2.1. Exercise 4: Vehicle routing without penalization

Problem:

  • From the “Kalaja e Prizrenit” to “Nadir Xhemali Danijolli”

From |place_3| to |place_1|

Solution:

  • The vehicle is going from vertex 2820 (line 17) to vertex 3770 (line 18).

  • The vehicle’s cost in this case will be in seconds.

  • All roads have a penalty of 1 (line 3).

  • Costs (in seconds) are to be multiplied by penalty (lines 12 and 13).

  • 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 (lines 14 and 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);

Exercise: 4 (Chapter: Vehicle)

3.2.2. Exercise 5: Vehicle routing with penalization

Concept:

  • Change the cost values for the configuration table, in such a way, that the

    • Pedestrian roads are not used.

    • Using residential roads is not encouraged.

    • Using “faster” roads is highly encouraged.

    • The penalty values can be changed with UPDATE queries.

Note

These values are an exaggeration.

 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');

Problem:

  • From the “Kalaja e Prizrenit” to “Nadir Xhemali Danijolli” with penalization.

From |place_5| to |place_3|

Solution:

  • The vehicle is going from vertex 2820 (line 11) to vertex 3770 (line 12).

  • Use cost_s (line 6) and reverse_cost_s (line 7) columns, which are in unit seconds.

  • Costs are to be multiplied by penalty (lines 6 and 7).

  • The configuration table is linked with the ways table by the tag_id field using a JOIN (lines 8 and 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);

Exercise: 5 (Chapter: Vehicle)

Note

Comparing with Exercise 3: Vehicle routing when time is money:

  • 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.

  • The cost did not change proportionally because of the penalty to some of the roads which was uniform (penalty=1) while routing with cost as money.