19 - pgRouting 5 - 5. pgRouting のアルゴリズム（Workshop）

19-5 5. pgRouting のアルゴリズム
19-5-1 5.1. ダイクストラ法による最短経路探索
前提条件
reverse cost を使えるようにするには追加の cost 列を追加する必要があります。私達は reverse cost を length としてセットすることができます。

user@deb8-vmw:~$ su - postgres
パスワード:
postgres@deb8-vmw:~$ psql pgrouting-workshop
psql (9.4.3)
"help" でヘルプを表示します.

pgrouting-workshop=# ALTER TABLE ways ADD COLUMN reverse_cost double precision;
ALTER TABLE
pgrouting-workshop=# UPDATE ways SET reverse_cost = length;
UPDATE 92435

説明やパラメータについてはホームページを参照してください。

クエリの例

pgrouting-workshop=# SELECT seq, id1 AS node, id2 AS edge, cost FROM pgr_dijkstra('
pgrouting-workshop'# SELECT gid AS id,
pgrouting-workshop'# source::integer,
pgrouting-workshop'# target::integer,
pgrouting-workshop'# length::double precision AS cost
pgrouting-workshop'# FROM ways',
pgrouting-workshop(# 30, 60, false, false);

 seq | node  |  edge  |        cost         
-----+-------+--------+---------------------
   0 |    30 |  63270 |  0.0826068346706699
   1 | 34780 |  43876 |  0.0387878379553639
   2 | 34779 |  74414 |   0.116939114260876
---
 321 | 45425 |  64167 |  0.0191919170925815
 322 | 45389 |  64077 |  0.0212719045648489
 323 |    60 |     -1 |                   0
(324 行)

(END):q

結果がホームページと違っていました。

19-5-2 5.2. A* アルゴリズムによる最短経路探索
前提条件
A-Star はあなたのネットワークのテーブルに事前に latitude/longitude 列 (x1, y1 と x2, y2) を追加してそれらの値を計算しておく必要があります。

pgrouting-workshop=# ALTER TABLE ways ADD COLUMN x1 double precision;
ALTER TABLE
pgrouting-workshop=# ALTER TABLE ways ADD COLUMN y1 double precision;
ALTER TABLE
pgrouting-workshop=# ALTER TABLE ways ADD COLUMN x2 double precision;
ALTER TABLE
pgrouting-workshop=# ALTER TABLE ways ADD COLUMN y2 double precision;
ALTER TABLE
pgrouting-workshop=# UPDATE ways SET x1 = ST_x(ST_PointN(the_geom, 1));
UPDATE 92435
pgrouting-workshop=# UPDATE ways SET y1 = ST_x(ST_PointN(the_geom, 1));
UPDATE 92435
pgrouting-workshop=# UPDATE ways SET x2 = ST_x(ST_PointN(the_geom, ST_NumPoints(the_geom)));
UPDATE 92435
pgrouting-workshop=# UPDATE ways SET y2 = ST_y(ST_PointN(the_geom, ST_NumPoints(the_geom)));
UPDATE 92435

説明やパラメータについてはホームページを参照してください。

クエリの例

pgrouting-workshop=# SELECT seq, id1 AS node, id2 AS edge, cost FROM pgr_astar('
SELECT gid AS id,
source::integer,
target::integer,
length::double precision AS cost,
x1, y1, x2, y2 FROM ways',
30, 60, false, false);

 seq | node  |  edge  |        cost         
-----+-------+--------+---------------------
   0 |    30 |  63270 |  0.0826068346706699
   1 | 34780 |  43876 |  0.0387878379553639
   2 | 34779 |  74414 |   0.116939114260876
---
 307 | 45408 |  64119 |  0.0215188911800576
 308 |    61 |  64165 |  0.0907426692530298
 309 |    60 |     -1 |                   0
(310 行)

(END):q

19-5-3 5.3. kDijkstra による複数の最短経路探索
説明やパラメータについてはホームページを参照してください。

pgr_kdijkstraCost のクエリの例

pgrouting-workshop=# SELECT seq, id1 AS source, id2 AS edge, cost FROM pgr_kdijkstraCost('  
SELECT gid AS id,
source::integer,
target::integer,
length::double precision AS cost
FROM ways',
10, array[60,70,80], false, false);

 seq | source | edge |       cost       
-----+--------+------+------------------
   0 |     10 |   60 | 12.7760976802851
   1 |     10 |   70 | 10.7254161085963
   2 |     10 |   80 | 1.35366721454691
(3 行)

pgr_kdijkstraPath のクエリの例

pgrouting-workshop=# SELECT seq, id1 AS path, id2 AS edge, cost FROM pgr_kdijkstraPath('
SELECT gid AS id,
source::integer,
target::integer,
length::double precision AS cost
FROM ways',
10, array[60,70,80], false, false);

 seq | path | edge  |        cost         
-----+------+-------+---------------------
   0 |   60 |    10 |  0.0130619186690278
   1 |   60 |  9274 |  0.0394297727975931
   2 |   60 | 56902 |  0.0247002816010054
---
 292 |   80 | 49455 |   0.223475992065702
 293 |   80 |    81 |  0.0570772918753206
 294 |   80 |    80 |                   0
(295 行)

(END):q