pgRoutingでOpenStreetMapデータの経路探索を試してみる

この記事は、[FOSS4G 二個目だよ Advent Calendar 2015](http://qiita.com/advent-calendar/2015/foss4gvol2) の20日目の内容になります。

# はじめに

pgRoutingは、オープンソースのPostgreSQLの拡張機能(Extension)で、経路探索に特化したものです。

pgRoutingのワークショップマニュアルでは、OSGeoLiveという、GeoServer+OpenLayers3が利用できるLinux環境での説明となっているため、手近なデスクトップ環境で、QGISのpgRoutingLayerプラグインを使った場合の手順をざっくりと記載しようと思います。

[pgRouting ワークショップマニュアル]
http://workshop.pgrouting.org/ja/index.html

# 環境構築

## 必要環境

まずは、以下のツールが利用できる環境を構築します。

- PostgreSQL 9.1 以上
- PostGIS 2.0 以上
- **pgRouting 2.0.x**
 - ※最新版は2.1ですが、QGISのpgRoutingLayerプラグインがまだ対応できていないため、一つ前の2.0を使用します。
- **osm2pgrouting 2.0**
- QGIS 2.0 以上

### Windows環境の場合

なお、Windows環境に関しては、pgRouting 2.0、osm2pgrouting 2.0を利用できるのは、現状、以下の組み合わせのみとなりますので、注意してください。

- PostgreSQL 9.4
- PostGIS 2.1.x
- pgRouting 2.0.1
 - Stack Builder より、"PostGIS 2.1 Bundle for PostgreSQL 9.4 (XX bit) v2.1.x"を選択すると、まとめてインストールされます。
- osm2pgrouting 2.0 
 - http://winnie.postgis.net/download/windows/pg94/buildbot/extras/ から、osm2pgrouting-pg94-2.0w32gcc481.zip (32bit用)、もしくは、osm2pgrouting-pg94-2.0w64gcc48.zip (64bit用)をダウンロードし、解凍後、中のファイルを"C:\Program Files\PostgreSQL\9.4\bin"フォルダ内にコピーします。

### Mac/Linux環境の場合
Mac環境でHomebrewを利用している場合は、pgRoutingとosm2pgroutingは以下でインストール可能です。

```
brew update
brew install osm2pgrouting
brew tap sanak/versions
brew install pgrouting20
```

その他のMac/Linux環境の場合は、ソースからビルド/インストールした方が早いかもしれません。

- pgRouting-2.0.1: https://github.com/pgRouting/pgrouting/releases/tag/pgrouting-2.0.1
- osm2pgrouting v2.0.0: https://github.com/pgRouting/osm2pgrouting/releases/tag/osm2pgrouting-2.0.0

ソースをダウンロード、解凍後、以下のコマンドで、ビルド/インストールします。

```
mkdir build
cd build
cmake ../
make
sudo make install
```

## コマンドの設定

以下のコマンドがターミナル(Windows環境ではコマンドプロンプト)から実行可能なことを確認します。

- psql
- osm2pgrouting

※Windowsの場合は、環境変数のPATHに"C:\Program Files\PostgreSQL\9.4\bin"を追加します。

続けて、ターミナルからpsqlコマンドでデータベースに接続可能なことを確認します。

```
psql -U postgres
```

接続が確認できれば、```postgres=#```と表示されるので、"\q"と入力してpsqlコマンドを終了します。

接続できない場合は、PostgreSQLのデータベースの設定ファイル(pg_hba.conf)末尾の以下の箇所の"md5"を"trust"に変更し、設定を読み込む必要があります。

```
# IPv4 local connections:
host    all             all             127.0.0.1/32            md5
# IPv6 local connections:
host    all             all             ::1/128                 md5
```

PostgreSQLのGUIツールpgAdmin IIIから、以下の方法でも接続設定を変更することが可能です。

1. pgAdmin IIIを起動し、[ファイル] / [pg_hba.confを開く...]メニューを選択し、pg_hba.confファイルを開く<br>(※Windows環境の場合は、"C:\Program Files\PostgreSQL\9.4\data\pg_hba.conf"を指定します。)
2. [バックエンド アクセス認証 エディタ]画面が表示されるので、チェックの付いている行をダブルクリック
3. [クライアントアクセス認証]ダイアログが表示されるので、[方法]を"md5"から"trust"に変更して[OK]ボタンをクリック<br>
![pg_hba1_0.75.png](https://qiita-image-store.s3.amazonaws.com/0/104365/8b38450c-3a8a-3b2d-d992-02fac993a882.png)
4. チェックの付いている2行とも[方法]列が"trust"に変更したことを確認したら、[ファイル] / [保存]メニューか、ツールバーの ![pg_hba2.png](https://qiita-image-store.s3.amazonaws.com/0/104365/db9e637b-5d50-e140-9f52-8b47a9a37b9c.png) アイコンをクリックして、設定を保存し、閉じる
5. pgAdmin IIIメイン画面の左側の[オブジェクトブラウザ]ツリーから、サーバの子要素(以下では"PostgreSQL 9.4 (localhost:5432)")を選択して右クリックし、コンテキストメニューから[構成をリロード]を選択<br>
![pg_hba3_0.75.png](https://qiita-image-store.s3.amazonaws.com/0/104365/ecd76874-d33e-741c-2dcb-c2ae3d6211eb.png)


# OpenStreetMapデータのインポート

## OpenStreetMapデータのダウンロード

経路探索の元となるデータを、OpenStreetMapからダウンロードします。

1. ブラウザからOpenStreetMapのサイト(http://www.openstreetmap.org/ )にアクセスして、経路探索を試してみたい任意の位置に拡大・移動
2. 上部の緑色の[エクスポート]メニューをクリックし、左側の[エクスポート]パネルで、適宜、範囲を調整<br>
(あまり大きい範囲を選択すると、サーバの方に負荷がかかるので、少し狭めの範囲(市区町村レベル)が良いかもしれません。<br>
以下では、[ドラッグして別の領域を選択]リンクをクリックして、京都府向日市の領域を指定しています。)![osm_export2.png](https://qiita-image-store.s3.amazonaws.com/0/104365/fed857a3-4482-a78f-beac-4ac70b647c78.png)
3. 範囲の指定が終わったら、中段の青色の[エクスポート]ボタンをクリック
4. 3.でエクスポートに失敗した場合は、ブラウザの戻るボタンをクリックし、範囲を選択し直してから、[Overpass API]リンクをクリック<br>("Overpass API"を使用した場合は、ダウンロードファイル名が"map"となりますので、"map.osm"にリネームします。)

## osm2pgroutingでのPostgreSQLデータベースへのインポート

ワークショップマニュアルの「6. osm2pgrouting インポートツール」の章を参考にします。
http://workshop.pgrouting.org/ja/chapters/osm2pgrouting.html

まず、ターミナルから、以下のコマンドを入力し、経路探索用のデータベースを作成します。

```bash
createdb -U postgres pgrouting-workshop
psql -U postgres -d pgrouting-workshop -c "CREATE EXTENSION postgis;"
psql -U postgres -d pgrouting-workshop -c "CREATE EXTENSION pgrouting;"
```

次に、osm2pgroutingを実行して、作成したデータベースにOpenStreetMapのデータを読み込みます。

```bash
osm2pgrouting -file [map.osmのパス] -conf [mapconfig.xmlのパス] -dbname pgrouting-workshop -user postgres -host localhost -clean
```

以下は、私のWindows環境(ユーザ名:sanak)でのコマンド入力例となります。

```bash
osm2pgrouting -file "C:\Users\sanak\Downloads\map.osm" -conf "C:\Program Files\PostgreSQL\9.4\bin\mapconfig.xml" -dbname pgrouting-workshop -user postgres -host localhost -clean
```

# QGISでの経路探索実行

ここまで来ると、もうあと少しです。QGISでPostgreSQLデータベースにインポートしたOpenStreetMapデータを表示し、経路探索を試してみます。

## PostGISレイヤの追加

QGISを起動し、以下の手順で、PostGISレイヤを追加します。

1. [レイヤ] / [レイヤの追加] / [PostGISレイヤの追加]メニューを選択
2. [PostGIS テーブルを追加]画面で、[接続]グループから[新規]ボタンをクリックし、以下のように入力<br>
![qgis_postgis_connection1_0.75.png](https://qiita-image-store.s3.amazonaws.com/0/104365/9407ed43-8894-9aa1-209c-88c00e66312d.png)
 - 名称: pgrouting-workshop
 - ホスト: localhost
 - データベース: pgrouting-workshop
 - ユーザ名: postgres
 - パスワード: (postgresユーザのパスワード)
 - ユーザ名の保存: チェックON
 - パスワード保存: チェックON<br>
3. [接続テスト]ボタンをクリックして、"pgrouting-workshop への接続に成功しました"とメッセージが表示されることを確認し、[OK]ボタンをクリック
4. パスワード保存の警告画面が表示されたら、そのまま[OK]ボタンをクリック
5. 元の画面に戻り、[接続]ボタンをクリック後、リストのスキーマ列から"public"を展開し、"ways"テーブルを選択して、[追加]ボタンをクリック<br>
![qgis_postgis_layer1_0.75.png](https://qiita-image-store.s3.amazonaws.com/0/104365/b117b9d4-74d5-3d86-5fd1-9c2baba63095.png)

## pgRoutingLayerプラグインのインストールと設定

以下の手順で、pgRoutingLayerプラグインのインストールと設定を行います。

1. [プラグイン] / [プラグインの管理とインストール]メニューを選択
2. [プラグイン]画面が表示されるので、左側の[設定]項目を選択し、[実験的プラグインも表示する]のチェックをON
3. 左側の[全ての]項目を選択し、検索ボックスから"pgRoutingLayer"と入力して、"pgRoutingLayer"項目を真ん中のリストから選択
4. 右下の[プラグインをインストール]ボタンをクリック
5. [pgRouting Layer]パネルが左下に表示されるので、他の[ブラウザ]パネル、[最短経路]パネルを閉じるなどして、パネルレイアウトを適宜調整
6. [pgRouting Layer]パネルの[Database]コンボボックスから、"pgrouting-workshop"を選択し、[sql]グループの箇所を以下の通りに設定します。<br>
![qgis_pgrouting_layer0.png](https://qiita-image-store.s3.amazonaws.com/0/104365/7336b8de-5728-5071-5777-157d41f40a01.png)
 - edge_table: **ways**
 - geometry: the_geom
 - id: **gid**
 - source: source
 - target: target
 - cost: **length**

## 経路探索の実行

それでは、以下の手順で経路探索を試してみます。

1. [pgRouting Layer]パネルの[Function]コンボボックスで、最も基本的な"dijkstra"(ダイクストラ法による最短経路探索)を選択
2. 下部の[source_id]の右端の ![qgis_pgrouting_layer_node_icon.png](https://qiita-image-store.s3.amazonaws.com/0/104365/cdadb7f2-7f56-7b66-bd9a-df7aeef6bcd1.png) アイコンをクリックして、地図内のノード(ラインの端点・交差点)付近をクリックし、地図内に青色の始点(×)シンボルが表示され、テキスト欄にノードIDが入力されることを確認
3. 同様に、[target_id]の右端の ![qgis_pgrouting_layer_node_icon.png](https://qiita-image-store.s3.amazonaws.com/0/104365/cdadb7f2-7f56-7b66-bd9a-df7aeef6bcd1.png) アイコンをクリックし、終点を確定
4. [Run]ボタンをクリックし、最短経路が赤いラバーバンドで表示されることを確認
5. 始点と終点を適宜変更して、[Run]ボタンをクリックし、動作を確認

![qgis_pgrouting_layer1.png](https://qiita-image-store.s3.amazonaws.com/0/104365/62bdadee-1bc2-fe6b-76d3-63e73c35ff44.png)

[Function]コンボボックスでは、pgRouting 2.0の以下の機能の実行をサポートしています。
いろいろと試してみてください。

- dijkstra: ダイクストラ法による最短経路探索
- astar: A* アルゴリズムによる最短経路探索
- drivingDistance: 到達圏探索
- alphaShape: 点列の凹包ポリゴン取得
- tsp(euclid): 巡回セールスマン問題(ユークリッド距離)
- trsp(vertex): 交差点での進入制限付き最短経路探索(TRSP, ノードベース)
- trsp(edge): 交差点での進入制限付き最短経路探索(TRSP, エッジベース)
- kdijkstra(cost): K-ダイクストラ法 - 1対多の最短経路探索(コスト取得用)
- kdijkstra(path): K-ダイクストラ法 - 1対多の最短経路探索(経路取得用)
- bdDijkstra: 双方向ダイクストラ法による最短経路探索
- bdAstar: 双方向 A* アルゴリズムによる最短経路探索
- ksp: K-最短経路探索 - 複数の代替経路探索

なお、今のところ、pgRoutingLayerでは、pgRouting 2.0の以下の機能には対応していません。

- tsp(matrix): 巡回セールスマン問題(距離行列)
- apspJohnson: 全点対間最短経路探索 - ジョンソンのアルゴリズム
- apspWarshall: 全点対間最短経路探索 - ワーシャル-フロイド法

# おわりに

今回は、デスクトップ環境でpgRouting 2.0を試してみる方法について、駆け足で説明しました。

pgRoutingは、ワークショップマニュアル以外の日本語翻訳の方が、なかなか進んでいないのと、
バージョン2.0から、APIが刷新され、使える機能(関数)も2倍近く増えて、pgRoutingで
何ができて何ができないかが分かりにくくなっているところがあるかもしれません。
(例えば、グラフアルゴリズムのフロー(流量)解析などには対応していません。)

実際に試してみて、「pgRoutingでこういうことができるのかー」と実感頂けますと、幸いです。

それでは、良いお年を！