データベース内の
最短経路探索

とpgroutingについて

Presented by Vergara Vicky
Translated by Nagase Ko

"Al andar se hace camino
y al volver la vista atrás
se ve la senda que nunca
se ha de volver a pisar."

君が歩くとそこに道はできる
そして後ろを振り返ったとき
二度と辿ることはできない道が見えるだろう

Antonio Machado

Celia Virginia Vergara Castillo

  • 経済学者, コンピュータ科学者
  • Georepublic
  • pgRouting 開発者
  • メキシコ人
  • Vickyとして知られています

FOSS4G をお楽しみください!!!


pgRouting プロジェクト



オープンソースプロジェクト


オープンソースプロジェクト



最新リリース

pgRouting 2.1



正確な定義




例えば ....


重み付き無向グラフ

  • Let $V$ be a set of vertices
    $V = source \cup target \cup \{start_v\} \cup \{end_v\}$
  • Let $E$ be a set of edges
    • when $reverse\_cost = \varnothing$:
      $E = \{ (source_i, target_i, cost_i) | cost_i \geq 0 \}$
      $\cup \quad \{ (target_i, source_i, cost_i) | cost_i \geq 0 \}$
    • when $reverse\_cost \neq \varnothing$:
      $E = \{ (source_i, target_i, cost_i) | cost_i \geq0 \}$
      $\cup \quad \{ (target_i, source_i, cost_i) | cost_i \geq 0 \}$
      $\cup \quad \{ (target_i, source_i, reverse\_cost_i) | reverse\_cost_i \geq 0)\}$
      $\cup \quad \{ (source_i, target_i, reverse\_cost_i) | reverse\_cost_i \geq 0)\}$
  • $G_u(V,E)$ is a weighted undirected graph



多くのアルゴリズム




例えば ....


アルゴリズム

  • Shortest Path Algorithm
    • Dijkstra
    • A-Star
    • Alternative Routes
    • Turn Restrictions
  • Traveling Salesperson Algorithm
  • Drivetime Analysis
  • Vehicle Route Problem Solver




ライブラリは
データベース内での
ルート検索機能を
提供しています


ルート検索の準備


  • データベースの作成
  • データのロード



データベースの作成


CREATE DATABASE routing;
\c routing
CREATE EXTENSION postgis;
CREATE EXTENSION pgrouting; 


データのロード

                        
 BBOX="-122.8,45.4,-122.5,45.6"
 wget --progress=dot:mega  
   \-O "sampledata.osm" 
   \ "http://www.overpass-api.de
   \ /api/xapi?
   \*[bbox=${BBOX}][@meta]"
 osm2pgrouting -d routing 
   \ -f sampledata.osm
                        


ルート検索を実行!!!




1つの出発地点から
1つの到着地点



SQL クエリ

 SELECT * FROM pgr_dijkstra('
      SELECT gid as id,
             source,
             target,
             cost_s as cost,
             reverse_cost_s AS reverse_cost 
        FROM ways',
    61796, 73402, true); 


クエリの結果


.seq | path_seq | node  |  edge  |  cost  | agg_cost
-----+----------+-------+--------+--------+---------
   1 |        1 | 61796 |  27230 | 1.7314 |        0
   2 |        2 | 40331 |  27259 | 4.4036 |   1.7314
   3 |        3 | 42625 |  27258 | 2.0006 |   6.1350
  ...
   7 |        9 | 73402 |     -1 |      0 |  19.0029
  


自宅からレストラン



私たちは1人ではありません

オープンソースツールをレンダリングに使用




SQL クエリ

 SELECT * FROM pgr_dijkstra('
      SELECT gid as id,
             source, target,
             cost_s as cost,
             reverse_cost_s AS reverse_cost 
        FROM ways',
    73402, 61796);  

レストランから自宅



複数の出発地点から
1つの到着地点



SQL クエリ

 SELECT * FROM pgr_dijkstra('
    SELECT gid as id,
             source, target,
             cost_s as cost,
             reverse_cost_s AS reverse_cost 
         FROM ways',
    ARRAY[61796, 47568], 73402); 


複数の家から1つのレストラン



1つの出発地点から
複数の到着地点



SQL クエリ

 SELECT * FROM pgr_dijkstra('
    SELECT gid as id,
             source, target,
             cost_s as cost,
             reverse_cost_s AS reverse_cost 
        FROM ways',
    73402, ARRAY[ 61796, 47568], true); 


1つのレストランから複数の家



複数の出発地点から
複数の到着地点



SQL クエリ

 SELECT * FROM pgr_dijkstra('
  SELECT gid AS id,
         source, target,
             cost_s as cost,
             reverse_cost_s AS reverse_cost 
        FROM ways',
  ARRAY[61796, 47568], ARRAY[73402, 51647]); 


複数の家から複数のレストラン



一般的な
クエリの結果


|   Column  |     Content                     |
|-----------|---------------------------------|
| seq       | Sequencial number               |
| path_seq  | Sequencial number for each path |
| start_vid | Start vertex of the path        |
| end_vid   | End vertex of the path          |
| node      | Node identifier                 |
| edge      | Edge identifier                 |
| cost      | Cost of the edge                |
| agg_cost  | Cost of the path up to the node |
                         


コスト



自転車のルート検索



内部の SQL


SELECT gid AS id, source, target,
    CASE 
        WHEN (source_altitude > target_altitude)
            length / 2
        ELSE
            length * 4
    END AS cost,
    CASE 
        WHEN (source_altitude > target_altitude)
            length * 4
        ELSE  
            length / 2
    END AS reverse_cost
 FROM ways                      
                        


フィールドワーク



内部の SQL


SELECT gid AS id, source, target,
    CASE 
        WHEN (wet)
            cost_s * wet_penalty
        ELSE
            cost_s
    END AS cost,
    CASE 
        WHEN (wet)
            reverse_cost_s * wet_penalty
        ELSE  
            reverse_cost_s
    END AS reverse_cost
 FROM ways
                        


牛のルート検索



内部の SQL


SELECT gid AS id, source, target,
    length AS cost
FROM ways WHERE road_type = 'rural'
...
 directed = false
                        


ハイカーのルート検索



内部の SQL (パート1)


SELECT gid AS id, source, target,
    CASE 
        WHEN (source_altitude > target_altitude)
            length * calories
        WHEN (source_altitude > target_altitude)
            length * calories * 1.5
        ELSE
            length * calories * 3.5
        END AS cost,
        
    ...
                        


内部の SQL (パート2)


...

    CASE 
        WHEN (source_altitude = target_altitude)
            length * calories
        WHEN (source_altitude > target_altitude)
            length * calories * 3.5
        ELSE
            length * calories * 1.5
    END AS reverse_cost
 FROM ways                      
                        


pgr_dijkstra

有向グラフ

逆方向のコストあり


SELECT * FROM pgr_Dijkstra(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  3, 5,
  true);
                        

逆方向のコストなし


SELECT * FROM pgr_Dijkstra(
  'SELECT id, source, target, cost FROM edges',
  3, 5,
  true);
                        



pgr_dijkstra

無向グラフ

逆方向のコストあり


SELECT * FROM pgr_Dijkstra(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  3,  5,
  false);
			

逆方向のコストなし


SELECT * FROM pgr_Dijkstra(
  'SELECT id, source, target, cost FROM edges',
  3, 5,
  false);
			



Interested in pgRouting?



"Al andar se hace camino
y al volver la vista atrás
se ve la senda que nunca
se ha de volver a pisar."

君が歩くとそこに道はできる
そして後ろを振り返ったとき
二度と辿ることはできない道が見えるだろう

Antonio Machado