16 pgRouting in Debian6 5 - ルートの検索1 Dijkstra

2 ルートの検索（最短距離の計算）

6. Shortest Path Search¶
http://workshop.pgrouting.org/chapters/shortest_path.html

を参考にルート検索をします。
３つのルート検索アルゴリズムと必要な属性について説明しています。
OpenStreetMap のデータを osm2pgrouting ツールで追加したなら、３つのルート検索関数を実行できます。

6.1. Dijkstra を参考にルート検索をしてみます。
Dijkstra は pgRouting 二最初に実装されたアルゴリズムで、source ID、target ID と cost 属性が必要です。
直接グラフと直接でないグラフを識別できます。
ネットワークが reverse cost またはそうでないかを明記できます。

事前準備として、reverce cost を使用するために、追加 cost カラムを追加する必要があります。

routing2=# ALTER TABLE ways ADD COLUMN reverse_cost double precision;
routing2=# UPDATE ways SET reverse_cost = length;
UPDATE 759212


それぞれのアルゴリズムは、core 関数であり、wrapper 関数の基本です。
6.1.1. Core を参考にコマンドを実行してみます。

routing2=# SELECT * FROM shortest_path('
routing2'# SELECT gid as id,
routing2'# source::integer,
routing2'# target::integer,
routing2'# length::double precision as cost FROM ways',
routing2(# 10, 1, false, false);

 vertex_id | edge_id |        cost        
-----------+---------+--------------------
        10 |       8 |  0.346119164295792
         9 |      23 | 0.0146912365339526
        11 |      22 |  0.075644096442472
        22 |      21 | 0.0618382434046277
        21 |      20 | 0.0915961112943772
        20 |      19 | 0.0790971710844567
        19 |     111 | 0.0382842275772729
        96 |     112 |  0.286175933407192
        97 |     113 | 0.0520291616070434
       100 |     565 |  0.289789710373784
       490 |  380609 |   0.76797799806671
       123 |  380608 |  0.735939901886778
       186 |     215 |  0.226197723036394
        30 |      36 |  0.634325320625154
         1 |      -1 |                  0
(15 行)

~~
(stdin):q


6.1.2. Wrapper を参考にコマンドを実行してみます。

Wrapper WITHOUT bounding box （box 境界線のない Wrapper）

Wrapper 関数は、遷移や box 境界線制限などで core 関数を拡張します。
Wrapper は、結果のフォーマットと順序を変えることができます。
Wrapper は、デフォルトの関数パラメータを設定し pgRouting の使い方をより簡単にします。

routing2=# SELECT gid, AsText(the_geom) AS the_geom FROM dijkstra_sp('ways', 10, 1);

  gid   |                                          the_geom                                              
--------+----------------------------------------------------------------------------------------------------------------------
      8 | MULTILINESTRING((139.7577762 35.6405846,139.7602379 35.6429693))
     23 | MULTILINESTRING((139.7576138 35.6405785,139.7577762 35.6405846))
     22 | MULTILINESTRING((139.7567768 35.6405692,139.7576138 35.6405785))
     21 | MULTILINESTRING((139.7560925 35.6405677,139.7567768 35.6405692))
     20 | MULTILINESTRING((139.7550789 35.6405698,139.7560925 35.6405677))
     19 | MULTILINESTRING((139.7542037 35.64058,139.7543194 35.6405713,139.7550789 35.6405698))
    111 | MULTILINESTRING((139.7542037 35.64058,139.7540437 35.6402612))
    112 | MULTILINESTRING((139.7540437 35.6402612,139.7535339 35.6392546,139.7528491 35.6378777))
    113 | MULTILINESTRING((139.7528491 35.6378777,139.7526395 35.6374419))
    565 | MULTILINESTRING((139.7526395 35.6374419,139.75219 35.6368954,139.7517603 35.6360734,139.7513313 35.6350625))
 380609 | MULTILINESTRING((139.7545699 35.6414479,139.7542355 35.6407687,139.75286 55 35.6380556,139.7518411 35.6360552,139.7513313 35.6350625))
 380608 | MULTILINESTRING((139.7576194 35.6475849,139.7568929 35.6461283,139.755837 35.6439893,139.7545699 35.6414479))
    215 | MULTILINESTRING((139.7585756 35.6494649,139.7576194 35.6475849))
     36 | MULTILINESTRING((139.7585756 35.6494649,139.7576702 35.6475689,139.7573095 35.6468001,139.7572599 35.6465017,139.7572966 35.646252,139.7573598 35.6460477,139.7577062 35.6453051,139.7577759 35.6451083,139.7578078 35.6449769,139.757837 35.6448058,139.7578311 35.6446378,139.7578 35.6437952))
(14 行)

(END):q


Wrapper WITH bounding box （box 境界線がある Wrapper）

box 境界線を追加することによって検索範囲を限定できます。
これは特に大きなネットワークに対してパフォーマンスを向上させます。

routing2=# SELECT gid, AsText(the_geom) AS the_geom FROM dijkstra_sp_delta('ways', 10, 1, 0.1);

  gid   |                                  the_geom                                             
--------+-------------------------------------------------------------------------------------------------------------------
      8 | MULTILINESTRING((139.7577762 35.6405846,139.7602379 35.6429693))
     23 | MULTILINESTRING((139.7576138 35.6405785,139.7577762 35.6405846))
     22 | MULTILINESTRING((139.7567768 35.6405692,139.7576138 35.6405785))
     21 | MULTILINESTRING((139.7560925 35.6405677,139.7567768 35.6405692))
     20 | MULTILINESTRING((139.7550789 35.6405698,139.7560925 35.6405677))
     19 | MULTILINESTRING((139.7542037 35.64058,139.7543194 35.6405713,139.7550789 35.6405698))
    111 | MULTILINESTRING((139.7542037 35.64058,139.7540437 35.6402612))
    112 | MULTILINESTRING((139.7540437 35.6402612,139.7535339 35.6392546,139.7528491 35.6378777))
    113 | MULTILINESTRING((139.7528491 35.6378777,139.7526395 35.6374419))
    565 | MULTILINESTRING((139.7526395 35.6374419,139.75219 35.6368954,139.7517603 35.6360734,139.7513313 35.6350625))
 380609 | MULTILINESTRING((139.7545699 35.6414479,139.7542355 35.6407687,139.7528655 35.6380556,139.7518411 35.6360552,139.7513313 35.6350625))
 380608 | MULTILINESTRING((139.7576194 35.6475849,139.7568929 35.6461283,139.755837 35.6439893,139.7545699 35.6414479))
     36 | MULTILINESTRING((139.7585756 35.6494649,139.7576702 35.6475689,139.7573095 35.6468001,139.7572599 35.6465017,139.7572966 35.646252,139.7573598 35.6460477,139.7577062 35.6453051,139.7577759 35.6451083,139.7578078 35.6449769,139.757837 35.6448058,139.7578311 35.6446378,139.7578 35.6437952))
(14 行)

(END):q

OSM データの投影法は度数なので、例えば、0.1度足した始点と終点 vertex を含む box 境界線を設定します。