ラズパイ（Ubuntu 20.04.1 LTS Server）でpgRoutingを使って経路探索

---

プラットフォーム

ラズパイ４B  4GB   +　PostgreSQL / PostGIS

PostgreSQL の拡張機能pgRoutingとosm2pgroutingを使ってみます。

使うMicroSDは32GB以上、64GBくらいが適当。

Raspberry Pi Imager for Windowsで MicroSDにUbuntu 20.04.1 LTS Server（64bit） をインストールしておきます。

初期設定ではrouteserverユーザーを作ってログインするようにします。

 

PostgreSQL 12.4 / PostGIS 3.0のインストール

sudo apt-get install postgresql postgresql-contrib postgis postgresql-12-postgis-3 postgresql-12-postgis-3-scripts

チューニングしておきます。

推奨される最小設定

shared_buffers = 128MB
max_wal_size = 2GB
min_wal_size = 1GB
work_mem = 32MB
maintenance_work_mem = 256MB
autovacuum = off
fsync = off

 

再起動

 

---

pgroutingをインストール

sudo apt list postgresql-12-pgroutingでパッケージチェック

で、インストール

 

---

DB作成

ユーザー名はrouteserver、データベースはosaka_routingとしておきます。

osaka_routing=#CREATE EXTENSION pgrouting;

osaka_routing=#\q

exit

 

２つのファイルを編集してPostgrSQLに接続できるようにしておきます。セキュリティ上、これは後で戻しておきます。

以下のコメントアウトを外します。

listen_addresses = ‘localhost’

以下の２行をtrustに修正

PostgreSQLを再起動

 

 

---

データのロード

osm2pgroutingのインストール

 

 

osm2pgrouting で OSM データを読み込む

 

データはOpenStreetMap Data Extractsで提供されているkansai-latest.osm.bz2

ダウンロードして解凍したものをSAMBAなどで/home/routeserver/Publicにコピーしておきます。

解凍したデータ（kansai-latest.osm）は大きいです。４GB近くあります。大きすぎます。

osm2pgroutingはメモリー食いです、このままロードするとしたら、swap領域を25GBほど取っておく必要があります。さもないと途中でOOMKillerにプロセスを切断されます。

まともに読み込んだら多分８時間以上かかると思います。

 

領域を限定して小さくします。

osmiumというツールを使います。

インストールしておきます。

 

 

使い方はこんな感じです。

 

OpenStreetMap Exportなどで座標を調べておきます。

 

kansai-latest.osmをコピーしておいたディレクトリ（/home/routeserver/Public）に移動して作業します。

osmファイルサイズは１GBくらい、swapは６GBくらい確保

データベースにロード

osm2pgrouting --file "/home/routeserver/Public/osaka_route.osm" --conf "/usr/share/osm2pgrouting/mapconfig.xml" --dbname osaka_routing --username routeserver -W ＜パスワード＞ --host localhost --clean

40分で終了（目安）

＊データベース構成ファイル

ここでは何のためらいもなくmapconfig.xmlを使っていますが、ファイルはこれ以外にも以下の３つが用意されています。

mapconfig_for_bicycles.xml（自転車）ー＞ 36分
mapconfig_for_cars.xml（自動車）ー＞ 34分
mapconfig_for_pedestrian.xml（歩行者）ー＞26分

mapconfig.xmlをまんま使うと、ちょっとまずい場合もあります。このページ参照

 

---

SQLで経路探索

作成されたデータベースはこんな感じです。

ここから２地点間の経路をダイクストラアルゴリズムを使って探ってみます。

２地点はways_vertices_pgrの２点です、QGISでidを調べてみます。

QGISを開いてデータベースに接続します。

（以下では目視確認してますが、SQLを使う場合はここ参照）

接続方法はいろいろあります、このページ参照

この青い線はedgeです。

point（ノード）をみてみます。

ways_vertices_pgrの属性テーブルを開いて「地図上に表示されている地物を表示する」を選びます。

２地点のpointの１点にズームします。そのidが分かります。idは２つあります。

ただのidはテンポラリに振られたもので、osm_idはより汎用性のあるidのようです、どちらを使ってもいいです。

同様にして他点のidも調べておきます。

SSHコンソールに戻って、以下のようなSQLを実行してみます。

ダイクストラアルゴリズムを使った経路探索です。方向を考慮しない移動を想定。

経路のジオメトリを出力してみます。

ジオメトリ値では見当がつかないので、緯度・経度でみてみます。

 

PostgreSQLの場合、SQLの実行結果を以下のコマンドでファイルに出力できます。

\g ＜絶対パス＞/res.txt

この実行結果を使ってルートのKMLファイルを作る簡易なPythonプログラムを用意してみました。

使い方は同梱のreadme.txtを見てね(^^)。

 

---

QGISを使ってみます

やり方は道路グラフでやったことと同じです。

メニュ－＞プロセシングでツールボックスを開いて、ネットワーク解析から「最短経路（指定始点から指定終点）」を開きます。

 

①最初に始点を決めます。ボタンをクリックすると、マウスカーソルが変更された地図画面が前面に出ますので地図上で出発地点クリック。

座標がセットされます。

②同様に終点の位置も決めて実行をクリック

ここからが長いんだな、これが。

こんな感じです。

---

エラー対処

最短経路探索で以下のようなエラーが発生

無効なジオメトリーのエラーです。こういうこともあるようです。

ジオメトリなど、どう修正すればいいのか分かりませんし、[無効な入力地物を無視する]オプションなどどこを探してもありませんでした。

手段として、ジオメトリの有効性をチェックして、有効なジオメトリのみ使うようにします。

以下のようにメニュのベクタから入って有効性をチェックします。

 

そこそこの時間がかかります。

終了後「閉じる」をクリックして、有効なジオメトリのレイヤを選びます。

最短経路メニュに戻って再実行します。

無事結果が出ましたが、この結果はオーライなんですが、本当にこれでいいんでしょか？

ちなみに

データ数は567355

対して、ジオメトリが正しくないとされたデータ数は169でした。

エラーメッセージはこんな感じ。

英語版ならこう（もともとの意味）

 

最短経路の結果はOKと判断してもいいかも。

 

この不正なジオメトリを持たないデータを再度PostGISに読みこんでみます。

「有効なジオメトリの出力レイヤ」で右クリックしてー＞エクスポートー＞地物の保存

マルチタイプにはしなくてもいいかも。

適当な場所（例：/home/roueserver/Public）に適当なファイル名（例：valid_ways）で保存します。

このファイル（例：valid_ways.sql）を適当なエディターで開いて以下の部分を修正。

ALTER TABLE “public”.”valid_ways” ADD COLUMN “gid” NUMERIC(20,0);
ALTER TABLE “public”.”valid_ways” ADD COLUMN “source” NUMERIC(20,0);
ALTER TABLE “public”.”valid_ways” ADD COLUMN “target” NUMERIC(20,0);

NUMERICをINTEGERに変更。

SSHコンソールに戻って以下を実行。

sudo -u postgres -i

psqlでdumpしたファイルを読み込んでSQLを実行

psql
\c osaka_routing

オーナー名をチェック、postgresをrouteserverに変更

\d

ALTER TABLE valid_ways OWNER TO routeserver;

以下３つのカラムの型をNUMERICからINTEGERに変更

ALTER TABLE valid_ways ALTER COLUMN gid TYPE integer;
ALTER TABLE valid_ways ALTER COLUMN source TYPE integer;
ALTER TABLE valid_ways ALTER COLUMN target TYPE integer;

 

 

これで新しいテーブル（valid_ways）にデータがリストアされました。

 

 

---

しかし、ラズパイ  +  QGIS + 最短経路探索は重いです….。データ量そのものが大きすぎるってこともありますが。

pgRoutingのSQLの方が速いです。

SQLで実行した結果をファイルにして、ライン描画用のKMLを作成してみます。

KMLの作成は上の「SQLで経路探索」で用意した簡易なPythonプログラムを使ってみます。

 

ちなみに、QGISでプラグインを使って経路探索したものはこんな感じ。

pgRoutingのSQL（ダイクストラアルゴリズム）の結果をKMLにしてGoogle Earthで表示すると

GoogleMapsだとこうなります

KMLはQGISではベクターデータセットとして読み込むことが可能です。

 

 

 

なんでSQLかというと、他のいろいろなパラメータをいれることで、最短経路以外に最適経路の探索も可能になるらしいから….。

SQLはデータベースに口を開かせるもの….ぐらいに思ってましたが、pgRoutingのSQLはオモシロイかも。

 

「SQLで経路探索」では目視で調べていましたが、SQLを使うとしたらこんな感じで最近傍点のIDを探すことになります。

SELECT id FROM ways_vertices_pgr ORDER BY the_geom <-> ST_SetSRID(ST_Point(＜経度＞,＜緯度＞), 4326) LIMIT 1;

 

QGISでマウスクリックで緯度・経度を取得するやり方はこのページ参照

 

ちなみに、あるポイント（緯度、経度）から指定の半径（m）内にある近傍点のIDをリストアップする場合は

select id,the_geom from ways_vertices_pgr where ST_DWithin(the_geom, ST_GeomFromText('POINT(＜経度＞ ＜緯度＞)',4326), ＜半径＞,true) order by id;

 

---

Next

GUIを使って始点・終点を取得して、その緯度・経度から近傍のノードidを取得できなければ使い勝手が悪いので、それは次回ということで…。緯度・経度取得はLeafletを使い、DB接続やらクエリーの発行などはPHPを使ったWebアプリになる予定です。

 

---

Appendix

pgRoutingで使えるアルゴリズム

All Pairs Shortest Path, Johnson’s Algorithm（全点対間最短経路探索 – ジョンソンのアルゴリズム）
All Pairs Shortest Path, Floyd-Warshall Algorithm（全点対間最短経路探索 – ワーシャル-フロイド法）
Shortest Path A*（A* アルゴリズムによる最短経路探索）
Bi-directional Dijkstra Shortest Path（双方向ダイクストラ法による最短経路探索）
Bi-directional A* Shortest Path（双方向 A* アルゴリズムによる最短経路探索）
Shortest Path Dijkstra（ダイクストラ法による最短経路探索）
Driving Distance（到達圏探索）
K-Shortest Path, Multiple Alternative Paths（K-最短経路探索 – 複数の代替経路探索）
K-Dijkstra, One to Many Shortest Path（K-ダイクストラ法 – 1対多の最短経路探索）
Traveling Sales Person（巡回セールスマン問題）
Turn Restriction Shortest Path （交差点での進入制限付き最短経路探索）(TRSP)

 

---

Appendix2

データベース構成ファイルは以下の４つがあります。

mapconfig.xml

mapconfig_for_bicycles.xml（自転車）
mapconfig_for_cars.xml（自動車）
mapconfig_for_pedestrian.xml（歩行者）

 

これらのファイルの注意点について

 

---

Appendix3

pgRouting Workshop

---