プラットフォーム
ラズパイ4B 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
2つのファイルを編集してPostgrSQLに接続できるようにしておきます。セキュリティ上、これは後で戻しておきます。
以下のコメントアウトを外します。
listen_addresses = ‘localhost’
以下の2行をtrustに修正
PostgreSQLを再起動
データのロード
osm2pgroutingのインストール
osm2pgrouting で OSM データを読み込む
データはOpenStreetMap Data Extractsで提供されているkansai-latest.osm.bz2
ダウンロードして解凍したものをSAMBAなどで/home/routeserver/Publicにコピーしておきます。
解凍したデータ(kansai-latest.osm)は大きいです。4GB近くあります。大きすぎます。
osm2pgroutingはメモリー食いです、このままロードするとしたら、swap領域を25GBほど取っておく必要があります。さもないと途中でOOMKillerにプロセスを切断されます。
まともに読み込んだら多分8時間以上かかると思います。
領域を限定して小さくします。
osmiumというツールを使います。
インストールしておきます。
使い方はこんな感じです。
OpenStreetMap Exportなどで座標を調べておきます。
kansai-latest.osmをコピーしておいたディレクトリ(/home/routeserver/Public)に移動して作業します。
osmファイルサイズは1GBくらい、swapは6GBくらい確保
データベースにロード
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を使っていますが、ファイルはこれ以外にも以下の3つが用意されています。
mapconfig_for_bicycles.xml(自転車)ー> 36分
mapconfig_for_cars.xml(自動車)ー> 34分
mapconfig_for_pedestrian.xml(歩行者)ー>26分
mapconfig.xmlをまんま使うと、ちょっとまずい場合もあります。このページ参照
SQLで経路探索
作成されたデータベースはこんな感じです。
ここから2地点間の経路をダイクストラアルゴリズムを使って探ってみます。
2地点はways_vertices_pgrの2点です、QGISでidを調べてみます。
QGISを開いてデータベースに接続します。
(以下では目視確認してますが、SQLを使う場合はここ参照)
接続方法はいろいろあります、このページ参照
この青い線はedgeです。
point(ノード)をみてみます。
ways_vertices_pgrの属性テーブルを開いて「地図上に表示されている地物を表示する」を選びます。
2地点のpointの1点にズームします。そのidが分かります。idは2つあります。
ただの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;
以下3つのカラムの型を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
データベース構成ファイルは以下の4つがあります。
mapconfig.xml
mapconfig_for_bicycles.xml(自転車)
mapconfig_for_cars.xml(自動車)
mapconfig_for_pedestrian.xml(歩行者)
Appendix3
Leave a Reply