Valhalla(OSSルート検索エンジン)を使ってOSMデータで経路探索する

前回に投稿した [OSMデータをPostGISにインポートしてQGISで可視化する - Qiita](https://qiita.com/hiyuzawa/items/ba1b9de36bf911145c1c) の続きの投稿です。
今回はOSM(OpenStreetMap)の道路ネットワークデータを用いて経路探索が可能なオープンソースソフトウェアである Valhalla を利用して経路探索してみる。

## Valhallaとは

ValhallaとはOpenStreetMapを利用したルーティング(経路探索)エンジンである。詳しくは以下のGitHubおよびドキュメントサイトを参照。かなりの高機能にも関わらず、少スペックのPCでもオンラインにてルート検索を応答することができる。またプラグインな拡張を持ちカスタマイズも可能。マルチモーダルに適応（自動車、歩行者、自転車、公共交通機関を混在させたり、その場所に到着する時間を設定することも可能）

* https://github.com/valhalla/valhalla
* https://valhalla.readthedocs.io/en/latest/

## Valhalla環境の構築

前回と同様にValallaの動作環境をDocker内に構築する。GitHubにてDockerfileも提供されているが今回は、[ubuntu用のInstallスクリプト](https://github.com/valhalla/valhalla/blob/master/scripts/Ubuntu_Bionic_Install.sh)が提供されているのでこれを用いて構築してみた。

```bash
# ubntueのdocker image でコンテナを起動
$ docker run -it ubuntu
root@624a86b637f3:/#

# apt にてビルドの事前準備に必要なものをインストール
root@624a86b637f3:/# apt update
root@624a86b637f3:/# apt install sudo git curl python

# build用のscriptを Github からダウンロード & 実行
root@624a86b637f3:/# curl -O https://raw.githubusercontent.com/valhalla/valhalla/master/scripts/Ubuntu_Bionic_Install.sh
root@624a86b637f3:/# sh ./Ubuntu_Bionic_Install.sh

# 自分の環境では1hぐらいかかって終了。
```

#### docker imageを作成
今後のためにこの段階(Valhalla入りUbuntu)のイメージを作成しておく。


```bash
#Docker離脱
#(TODO: install用の作業ファイル等はcleanにしておいたほうが良いかもしれない)
root@624a86b637f3:/# exit
exit

# docker imageを作成
$ docker ps -a
CONTAINER ID   IMAGE                    COMMAND                  CREATED          STATUS                        PORTS                    NAMES
624a86b637f3   ubuntu                   "/bin/bash"              52 minutes ago   Exited (0) 27 seconds ago                              affectionate_mclean
$ docker commit 624a86b637f3 ubuntu_with_valhalla
$ docker images
REPOSITORY               TAG       IMAGE ID       CREATED          SIZE
ubuntu_with_valhalla     latest    ec21f429a10a   29 seconds ago   2.37GB
```

## Tileデータの作成
Valhallaの利用するOpenStreetMapのネットワークデータはTile分割されてIndex管理される。そのTileインデックスを作成する。Tileのイメージは以下のドキュメント内のimageが理解しやすい

* [Why tiles? - valhalla docs] (https://valhalla.readthedocs.io/en/latest/mjolnir/why_tiles/)

今回も前回と同様にOpenStreetMapの関西エリアのデータを用意する.
準備の方法は[前回の記事を参考にする](https://qiita.com/hiyuzawa/items/ba1b9de36bf911145c1c#osm%E3%83%87%E3%83%BC%E3%82%BF%E3%82%92%E5%8F%96%E5%BE%97%E3%81%99%E3%82%8B)。

#### dockerを起動する

```bash
$ cd (作業ディレクトリ. kansai-latest.osm.pbf が保存されていること)

# 作成したvalhalla入りubuntuのimageを起動. valhallaサーバの起動Portが8002なのでこの時点でバインドしておく
$ docker run -it -v `pwd`:/work -p 8002:8002 ubuntu_with_valhalla
root@962c6e2a28b0:/#

# osmデータが確認できる.(前回の記事の作業ディレクトリを流用している)
root@962c6e2a28b0:/# ls -l /work
total 196620
-rw-r--r--  1 root root      6025 Dec 20 14:16 default.style
-rw-r--r--  1 root root 198153708 Dec 17 15:35 kansai-latest.osm.pbf
drwx------ 26  999 root       832 Dec 20 13:55 postgis_data

# マウント先領域へ移動
root@962c6e2a28b0:/# cd /work/

# Tileインデックスの保存先ディレクトリを作成
root@962c6e2a28b0:/work# mkdir valhalla_tiles

# valhalla configの作成
root@962c6e2a28b0:/work# valhalla_build_config --mjolnir-tile-dir ${PWD}/valhalla_tiles --mjolnir-tile-extract ${PWD}/valhalla_tiles.tar --mjolnir-timezone ${PWD}/valhalla_tiles/timezones.sqlite --mjolnir-admin ${PWD}/valhalla_tiles/admins.sqlite > valhalla.json

# tileインデックス作成
root@962c6e2a28b0:/work# valhalla_build_tiles -c valhalla.json kansai-latest.osm.pbf

# しばらく時間がかかって終了(30minぐらい)

# 371MBのTileが作成された
root@962c6e2a28b0:/work# du -d1 -h ./valhalla_tiles/
26M	./valhalla_tiles/0
48M	./valhalla_tiles/1
298M	./valhalla_tiles/2
371M	./valhalla_tiles/

# Tileをtarでまとめる
root@962c6e2a28b0:/work# find valhalla_tiles | sort -n | tar cf valhalla_tiles.tar --no-recursion -T -
root@962c6e2a28b0:/work# ls -l valhalla_tiles.tar
-rw-r--r-- 1 root root 361625600 Dec 21 12:14 valhalla_tiles.tar
```

## Valhalla起動

```bash
root@962c6e2a28b0:/work# export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib/
root@962c6e2a28b0:/work# valhalla_service valhalla.json 1
```

#### 動作確認

Portマッピングの確認もかねてホスト側からcurlを呼び出して確認する.
下の例は Valhallaの複数あるAPIのなかで最も基本な経路探索をする [turn-by-turn api](https://valhalla.readthedocs.io/en/latest/api/turn-by-turn/api-reference/) である。

```bash
# 京都駅付近をスタートとして四条河原町までの経路を探索する
$ curl http://localhost:8002/route --data '{"locations":[{"lat":34.98597,"lon":135.75795},{"lat":35.00373,"lon":135.76928}],"costing":"auto","directions_options":{"units":"kilometers"}, "language": "ja-JP"}' | jq '.'
```

正常に起動しているとレスポンスは以下となる

```json
{
  "trip": {
    "status": 0,
    "language": "ja-JP",
    "status_message": "Found route between points",
    "legs": [
      {
        "shape": "elkvaAal~|aG]O]G_@?gHA_D`@cEBoc@X}C?AuCH_CBu\\@}HD{k@B{^GkK}BWgDYe\\Rqn@D{ODkV?@}ECo`@A_m@Iuo@Ek\\AiPAeICiKCkW?sBCuM?qFAsJAiJAwB_KQsKBqm@FslA@gG?oY?cFa@ad@kOwV_LqR}HqYmLkb@mSsb@mVkZ}QyJmFaLgGuHaEeS_HsKsDy\\oKiXqIwGqByBq@}p@iTcRwFkEwAoFiBwCcAyFsBai@}RcIyCy@]yB}@{s@}YcDsAmBy@sImDk[qMsH{CsKiEuDyAcCw@yAa@_B_@gBYyBSsGEgCF}VRcWRqLE",
        "summary": {
          "max_lon": 135.76934,
          "min_lat": 34.986195,
          "cost": 578.404,
          "max_lat": 35.00373,
          "length": 2.657,
          "has_time_restrictions": false,
          "min_lon": 135.757502,
          "time": 285.765
        },
        "maneuvers": [
          {
            "travel_type": "car",
            "travel_mode": "drive",
            "verbal_multi_cue": true,
            "end_shape_index": 8,
            "begin_shape_index": 0,
            "cost": 58.324,
            "time": 12.535,
            "verbal_pre_transition_instruction": "北方向です。。その先右方向です。その先塩小路通です。",
            "verbal_post_transition_instruction": "100メートル直進です。",
            "instruction": "北方向です。",
            "length": 0.116,
            "type": 2
          },
          {
            "travel_type": "car",
            "travel_mode": "drive",
            "end_shape_index": 15,
            "begin_shape_index": 8,
            "cost": 81.521,
            "time": 25.534,
            "verbal_pre_transition_instruction": "右方向です。その先塩小路通, Shio-koji doriです。",
            "street_names": [
              "塩小路通",
              "Shio-koji dori"
            ],
            "verbal_transition_alert_instruction": "右方向です。その先塩小路通です。",
            "verbal_post_transition_instruction": "200メートル直進です。",
            "instruction": "右方向です。その先塩小路通/Shio-koji doriです。",
            "length": 0.202,
            "type": 10
          },
          {
            "travel_type": "car",
            "travel_mode": "drive",
            "end_shape_index": 21,
            "begin_shape_index": 15,
            "cost": 47.306,
            "time": 25.633,
            "verbal_pre_transition_instruction": "左方向です。その先烏丸通, 32です。",
            "street_names": [
              "烏丸通",
              "32",
              "Karasuma avenue"
            ],
            "verbal_transition_alert_instruction": "左方向です。その先烏丸通です。",
            "verbal_post_transition_instruction": "200メートル直進です。",
            "instruction": "左方向です。その先烏丸通/32/Karasuma avenueです。",
            "length": 0.225,
            "type": 15
          },
          {
            "travel_type": "car",
            "travel_mode": "drive",
            "end_shape_index": 36,
            "begin_shape_index": 21,
            "cost": 105.704,
            "time": 52.298,
            "verbal_pre_transition_instruction": "右方向です。その先24, 七条通です。",
            "street_names": [
              "24",
              "七条通",
              "一般国道24号",
              "Shichijo-dori Avenue"
            ],
            "verbal_transition_alert_instruction": "右方向です。その先24です。",
            "verbal_post_transition_instruction": "400メートル直進です。",
            "instruction": "右方向です。その先24/七条通/一般国道24号/Shichijo-dori Avenueです。",
            "length": 0.41,
            "type": 10
          },
          {
            "travel_type": "car",
            "travel_mode": "drive",
            "end_shape_index": 87,
            "begin_shape_index": 36,
            "cost": 285.549,
            "time": 169.765,
            "verbal_pre_transition_instruction": "左方向です。その先河原町通, 32です。",
            "street_names": [
              "河原町通",
              "32",
              "京都府道32号下鴨京都停車場線",
              "Kawaramachi avenue"
            ],
            "verbal_transition_alert_instruction": "左方向です。その先河原町通です。",
            "verbal_post_transition_instruction": "1.5キロメートル直進です。",
            "instruction": "左方向です。その先河原町通/32/京都府道32号下鴨京都停車場線/Kawaramachi avenueです。",
            "length": 1.703,
            "type": 15
          },
          {
            "travel_type": "car",
            "travel_mode": "drive",
            "end_shape_index": 87,
            "begin_shape_index": 87,
            "cost": 0,
            "time": 0,
            "verbal_pre_transition_instruction": "目的地に到着しました。",
            "verbal_transition_alert_instruction": "まもなく目的地に到着します。",
            "instruction": "目的地に到着しました。",
            "length": 0,
            "type": 4
          }
        ]
      }
    ],
    "units": "kilometers",
    "summary": {
      "max_lon": 135.76934,
      "min_lat": 34.986195,
      "cost": 578.404,
      "max_lat": 35.00373,
      "length": 2.657,
      "has_time_restrictions": false,
      "min_lon": 135.757502,
      "time": 285.765
    },
    "locations": [
      {
        "original_index": 0,
        "lon": 135.75795,
        "side_of_street": "right",
        "lat": 34.98597,
        "type": "break"
      },
      {
        "original_index": 1,
        "lon": 135.76928,
        "lat": 35.00373,
        "type": "break"
      }
    ]
  }
}
```

レスポンスを見ていると経路のサマリ。経路内での各ポイントでの詳細がレスポンスされていることがわかる。trip.legs.shape 内のエンコードされたデータは下記仕様のデコーダーを通すと緯度経度の列が取得できる

* https://valhalla.readthedocs.io/en/latest/decoding/

## Valhalla提供の 簡易View

valhallaから簡易にValhallaの動作確認ができるWebベースのdemoが提供されているのでそれを利用してみる

* https://github.com/valhalla/demos

```bash
# demo を checkout
$ git clone --depth=1 --recurse-submodules --single-branch --branch=gh-pages https://github.com/valhalla/demos.git
```

checkoutした demos内の routing/index-internal.html をブラウザで開くと地図アプリケーションが開く。Tileが存在する地域を表示して始点と終点をクリックスるとlocalhost:8002で起動したValhallaサーバにアクセスして経路探索を行い結果が表示される
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/36803/0ccc8d86-7969-4629-646d-68cbcd9015cf.png)

京都駅から大阪駅までのルート(表示されるパネルでは経路詳細が表示され、名神高速を利用する一般的な経路で探索結果が表示されている事がわかる。)

また、左メニューから「Drive」「Walk」を選択すると「車」「徒歩」に応じた経路が切り替わって表示される。（例：京都二条城から平安神宮までの経路。左が「Drive」右が「Walk」。「Walk」の場合は大通りに回り込まず東に突き進んでいることがわかる）
<img alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/36803/0edf4d68-e806-7ac7-534e-5d4812614a8a.png" width=300> <img alt="image.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/36803/cdfbf63e-d001-9829-6fa9-36764d8e2a53.png" width=300>

## QGISでValhallaを利用してみる

QGISのプラグインで「Valhallaプラグイン」が存在する。それを利用して経路結果をQGIS内に表示してみる。合わせて、前回の説明したPostGISにインポートしたOSSデータも合わせて表示して経路をあわせてみる。 

#### Valallaプラグインのインストール

QGISメニューの「プラグイン」-「プラグインの管理とインストール...」を選択し、表示されたダイアログからvalhallaを検索しインストールを行う。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/36803/f87af60d-7796-99bd-4d2d-40e65ec58d8c.png)

OpenStreetMapをQGIS内でレイヤーとして加え([方法は前回の記事参照](https://qiita.com/hiyuzawa/items/ba1b9de36bf911145c1c#qgis-%E3%81%A7-osm%E3%83%87%E3%83%BC%E3%82%BF%E3%82%92%E5%8F%AF%E8%A6%96%E5%8C%96))、ValhalaのTileが存在する関西地方を表示したあとに、QGIS上部の機能アイコンリストに追加されているValhallaのロゴをクリックする。

Valhallaのダイアログが表示されるので「＋」のボタンをクリックして地図上の2点を選ぶと緯度経度がそこに登録される
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/36803/e2a4c8f5-53b9-3023-63dc-2ebd4c9489c1.png)
ダイアログの「Apply」を選択するとQGISのレイヤーに「RouteAuto」が追加され経路結果が表示される（OpenStreetMapのレイヤーが邪魔をして経路が見にくい場合はOSMのレイヤーを非表示にするなり、RouteAutoレイヤのデザインを変更（線分を濃く太くする）したりするとよい）
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/36803/f4e64c0e-89cf-52e1-875b-b998f3879bf0.png)

## OSSデータとValhalla経路を深堀りする

QGISをもう少し使いこなして、OSSの道路データとValhallaで算出された経路の関係をもう少し深堀りする。Valhallaでインデックスされた経路の元ネタはOSMのデータ(今回はkansai-latest.osm.pbf)であり、前回の記事でPostGISにインポートしてQGISで可視化した元ネタも同じなので一致することが当然期待できる。

#### OpenStreetMap内のlineデータから道路に関するデータのみを抽出する

OSMのlineデータ(PostGISのテーブル planet_osm_line )には行政境界線,河川,路線,電線,等々の道路"以外"のデータも多数登録されている。この中から道路に関係するものだけを抽出してみる。まずは QGISブラウザから PostGIS -> planet_osm_line を選択してレイヤーに加える。この時点ではline全体が表示されるはずである。

京都市中心部のplanet_osm_line全図 (道路っぽく見えるが道路だけではない)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/36803/ed25afaa-0ac4-7db8-fb8e-7774c684cbf9.png)

レイヤのplanet_osm_lineを右選択、メニュー内の「フィルター」を選択しクエリビルダを表示する。lineの属性値のなかでどのkeyのなんのvalueを抽出すれば道路のみを抽出すればよいか。

当然、valhalla内ではその抽出は行われているはずなのでソースからあたりを付けてみると [/lua/graph.lua](https://github.com/valhalla/valhalla/blob/0200898a773832166aac25512cb560e549d899bc/lua/graph.lua)のコード部分が参考になりそうな予感がする。
(highway属性が "motorway","motorway_link","trunk",...がvalhallaが選択しうる経路=道路) 。これをクエリビルダの条件式に加えると以下のようになる(今回はauto=trueのものだけを選択する)

```
"highway" IN ('motorway','motorway_link','trunk','trunk_link','primary','primary_link','secondary','secondary_link','service','tertiary','tertiary_link','road','track','unclassified')
```
この条件を加えたあとの画面は以下となり、上記のline全てを表示したものと比べてかなり間引かれていることがわかる。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/36803/c7487bfe-e353-257c-a909-3498c8c6e8e8.png)

この経路図上で、Valhallaプラグインより経路探索を行うと以下のようになり、OSMネットワーク上の経路を選択して経路探索が行われていることが可視化されていることがわかる。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/36803/e05bc3a2-7e06-71c2-c08c-777eaf3c6d43.png)
（東西に伸びる一部区間を選択し地形情報を確認すると osm_id=250534121, highway="trunk", name="曽根崎筋"であることがわかる。※図中の赤い区間)