Advanced usage of pgRouting shortest path search
An ordinary shortest path query with result usualy looks like this:
SELECT * FROM shortest_path_shooting_star(
'SELECT gid as id, source, target, length as cost, x1, y1, x2, y2, rule,
to_cost, reverse_cost FROM ways', 1955, 5787, true, true);
vertex_id | edge_id | cost
-----------+---------+---------------------
8134 | 1955 | 0.00952475464810279
5459 | 1956 | 0.0628075563112871
8137 | 1976 | 0.0812786367080268
5453 | 758 | 0.0421747270358272
5456 | 3366 | 0.0104935732514831
11086 | 3367 | 0.113400030221047
4416 | 306 | 0.111600379959229
4419 | 307 | 0.0880411972519595
4422 | 4880 | 0.0208599114366633
5101 | 612 | 0.0906859882381495
5102 | 5787 | 80089.8820919459
(11 rows)
That is usually called SHORTEST path, which means that a length of an edge is its cost.
Costs can be anything ("Weighted costs")
But in real networks we have different limitations or preferences for different road types for example. In other words, we want to calculate CHEAPEST path - a path with a minimal cost. There is no limitation in what we take as costs.
When we convert data from OSM format using the osm2pgrouting tool, we get these two additional tables for road types and classes:
\d classes
id | name
-----+------------
2 | cycleway
1 | highway
4 | junction
3 | tracktype
\d types id | type_id | name | cost -----+---------+--------------------+-------- 201 | 2 | lane | 1 204 | 2 | opposite | 1 203 | 2 | opposite_lane | 1 202 | 2 | track | 1 117 | 1 | bridleway | 1 113 | 1 | bus_guideway | 1 118 | 1 | byway | 1 115 | 1 | cicleway | 1 116 | 1 | footway | 1 108 | 1 | living_street | 1 101 | 1 | motorway | 0.2 103 | 1 | motorway_junction | 0.2 102 | 1 | motorway_link | 0.2 114 | 1 | path | 100 111 | 1 | pedestrian | 100 106 | 1 | primary | 100 107 | 1 | primary_link | 100 107 | 1 | residential | 100 100 | 1 | road | 0.7 100 | 1 | unclassified | 0.7 106 | 1 | secondary | 10 109 | 1 | service | 10 112 | 1 | services | 10 119 | 1 | steps | 10 107 | 1 | tertiary | 10 110 | 1 | track | 10 104 | 1 | trunk | 10 105 | 1 | trunk_link | 10 401 | 4 | roundabout | 10 301 | 3 | grade1 | 15 302 | 3 | grade2 | 15 303 | 3 | grade3 | 15 304 | 3 | grade4 | 15 305 | 3 | grade5 | 15
Road class is linked with the ways table by class_id field. Cost values for classes table are assigned arbitrary.
UPDATE classes SET cost=15 WHERE id>300;
For better performance it is worth to create an index on id field of classes table.
CREATE INDEX class_idx ON ways (id);
The idea behind these two tables is to specify a factor to be multiplied with the cost of each link (usually length):
SELECT * FROM shortest_path_shooting_star(
'SELECT gid as id, class_id, source, target, length*c.cost as cost,
x1, y1, x2, y2, rule, to_cost, reverse_cost*c.cost as reverse_cost
FROM ways w, classes c
WHERE class_id=c.id', 1955, 5787, true, true);
vertex_id | edge_id | cost
-----------+---------+---------------------
8134 | 1955 | 0.00666732825367195
5459 | 1956 | 0.043965289417901
8137 | 1992 | 0.126646230936747
5464 | 762 | 0.827868704808978
5467 | 763 | 0.16765902528648
... | ... | ...
9790 | 5785 | 0.00142107468268373
8548 | 5786 | 0.00066608685984761
16214 | 5787 | 0.0160179764183892
(69 rows)
We can see that the shortest path result is completely different from the example before. We call this "weighted costs".
Another example is to restrict access to roads of a certain type:
UPDATE classes SET cost=100000 WHERE name LIKE 'motorway%';
Through subqueries you can "mix" your costs as you like and this will change the results of your routing request immediately. Cost changes will affect the next shortest path search, and there is no need to rebuild your network.
