pgRouting

Changeset 229

Show
Ignore:
Timestamp:
09/22/08 14:57:44 (2 months ago)
Author:
anton
Message:

--

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • branches/workshop/FOSS4G2008/Docs/11_pgrouting.weighted.chapter

    r228 r229  
     1An ordinary shortest path query result usualy looks like this: 
     2 
     3SELECT * 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); 
     4 vertex_id | edge_id |        cost          
     5-----------+---------+--------------------- 
     6      8134 |    1955 | 0.00952475464810279 
     7      5459 |    1956 |  0.0628075563112871 
     8      8137 |    1976 |  0.0812786367080268 
     9      5453 |     758 |  0.0421747270358272 
     10      5456 |    3366 |  0.0104935732514831 
     11     11086 |    3367 |   0.113400030221047 
     12      4416 |     306 |   0.111600379959229 
     13      4419 |     307 |  0.0880411972519595 
     14      4422 |    4880 |  0.0208599114366633 
     15      5101 |     612 |  0.0906859882381495 
     16      5102 |    5787 |    80089.8820919459 
     17(11 rows) 
     18 
     19That is usualy called SHORTEST path, which means that a length of an edge is its cost. 
     20 
     21But in real life we have different limitations or preferences for different road types. 
     22In other words, we want to calculate CHEAPEST path - a path with a minimal cost, doesn't metter what cost means. 
     23 
     24When we comvert data from OSM format, we get these two tables for road types and classes: 
     25                                                                                        
     26  id |   name     
     27-----+------------ 
     28   2 | cycleway 
     29   1 | highway 
     30   4 | junction 
     31   3 | tracktype 
     32 
     33 
     34 id  | type_id |        name        |  cost  
     35-----+---------+--------------------+-------- 
     36 201 |       2 | lane               |   1   
     37 204 |       2 | opposite           |   1   
     38 203 |       2 | opposite_lane      |   1   
     39 202 |       2 | track              |   1   
     40 117 |       1 | bridleway          |   1   
     41 113 |       1 | bus_guideway       |   1   
     42 118 |       1 | byway              |   1   
     43 115 |       1 | cicleway           |   1   
     44 116 |       1 | footway            |   1   
     45 108 |       1 | living_street      |   1   
     46 101 |       1 | motorway           |   0.2   
     47 103 |       1 | motorway_junction  |   0.2   
     48 102 |       1 | motorway_link      |   0.2   
     49 114 |       1 | path               |   100   
     50 111 |       1 | pedestrian         |   100   
     51 106 |       1 | primary            |   100   
     52 107 |       1 | primary_link       |   100   
     53 107 |       1 | residential        |   100   
     54 100 |       1 | road               |   0.7   
     55 100 |       1 | unclassified       |   0.7   
     56 106 |       1 | secondary          |   10   
     57 109 |       1 | service            |   10   
     58 112 |       1 | services           |   10   
     59 119 |       1 | steps              |   10   
     60 107 |       1 | tertiary           |   10   
     61 110 |       1 | track              |   10   
     62 104 |       1 | trunk              |   10   
     63 105 |       1 | trunk_link         |   10   
     64 401 |       4 | roundabout         |   10   
     65 301 |       3 | grade1             |   15   
     66 302 |       3 | grade2             |   15   
     67 303 |       3 | grade3             |   15   
     68 304 |       3 | grade4             |   15   
     69 305 |       3 | grade5             |   15   
     70 
     71Road class is linked with ways table by class_id field. 
     72Cost values for classes table assign arbitrary. The idea is to specify a rate value to multiply it by length: 
     73 
     74 
     75SELECT * 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); 
     76 vertex_id | edge_id |        cost          
     77-----------+---------+--------------------- 
     78      8134 |    1955 | 0.00666732825367195 
     79      5459 |    1956 |   0.043965289417901 
     80      8137 |    1992 |   0.126646230936747 
     81      5464 |     762 |   0.827868704808978 
     82      5467 |     763 |    0.16765902528648 
     83      5470 |    2978 |   0.164681183696497 
     84         . 
     85         . 
     86         . 
     87     11005 |    3325 |   0.108724770203164 
     88      9788 |    2801 |   0.111846516578974 
     89      9790 |    5785 | 0.00142107468268373 
     90      8548 |    5786 | 0.00066608685984761 
     91     16214 |    5787 |  0.0160179764183892 
     92(69 rows) 
     93 
     94So, we can see that search result is completely differet from SHORTEST path search.