オープンソースのルーティングエンジンValhallaをビルドして使う

Valhallaとは

ValhallaはオープンソースのルーティングエンジンでライセンスはMITです。
Valhallaは元々Mapzenで開発されいていましたが、現在開発チームはMapboxに加わっています。

ここでデモを試すことができます(要Mapbox access token)。

ValhallaのGithubを見るとvalhallaのAAがあり、構成されているライブラリ群が書いてあります。

 ██▒   █▓ ▄▄▄       ██▓     ██░ ██  ▄▄▄       ██▓     ██▓    ▄▄▄      
▓██░   █▒▒████▄    ▓██▒    ▓██░ ██▒▒████▄    ▓██▒    ▓██▒   ▒████▄    
 ▓██  █▒░▒██  ▀█▄  ▒██░    ▒██▀▀██░▒██  ▀█▄  ▒██░    ▒██░   ▒██  ▀█▄  
  ▒██ █░░░██▄▄▄▄██ ▒██░    ░▓█ ░██ ░██▄▄▄▄██ ▒██░    ▒██░   ░██▄▄▄▄██
   ▒▀█░   ▓█   ▓██▒░██████▒░▓█▒░██▓ ▓█   ▓██▒░██████▒░██████▒▓█   ▓██▒
   ░ ▐░   ▒▒   ▓▒█░░ ▒░▓  ░ ▒ ░░▒░▒ ▒▒   ▓▒█░░ ▒░▓  ░░ ▒░▓  ░▒▒   ▓▒█░
   ░ ░░    ▒   ▒▒ ░░ ░ ▒  ░ ▒ ░▒░ ░  ▒   ▒▒ ░░ ░ ▒  ░░ ░ ▒  ░ ▒   ▒▒ ░
     ░░    ░   ▒     ░ ░    ░  ░░ ░  ░   ▒     ░ ░     ░ ░    ░   ▒   
      ░        ░  ░    ░  ░ ░  ░  ░      ░  ░    ░  ░    ░  ░     ░  ░
     ░          

名称	内容
Midgard	基本的なアルゴリズム
Baldr	キャッシュするための基本データ構造
Sif	コスト計算のライブラリ
Skadi	標高データにアクセスするためのライブラリ
Mjolnir	Valhallグラフタイルに変換するためのツール
Loki	graph tilesを検索して、入力された位置をタイル内のエッジ・頂点と関連付けるためのライブラリ
Meili	map-matchingに使われるライブラリ
Thor	graph tilesのパスを生成するために使用されるライブラリ
Odin	経路に基づいてルーティング案内を生成するためのライブラリ
Tyr	他のValhalla APIと通信してHTTP requestsを処理するためのライブラリ

ライブラリの名前は北欧神話が由来になってるみたいです。やだ...かっこいい...

Valhallaをビルドする

Valhallaはppaでも提供されていますが2018/12/10現在最新バージョンは3.0.1なのに対し、ppaのバージョンは2.4.7なので最新版ではありません。なのでソースからビルドして使います。
ValhallaのGithubを見るとビルド方法が載っていますがnvmを使います。
私は環境を汚したくないのでDockerでビルドをしたいと思います。

ビルド環境

今回は以下の環境で試しました。

• OS：Ubuntu 18.04.1
• Docker 17.12.1
• Docker Compose 1.17.1

ビルドする

valhalla/dockerを参考にDockerfileを作ります。

Dockerfile

FROM ubuntu:16.04

# install packages
RUN apt-get update -y && apt-get install -y software-properties-common
RUN add-apt-repository -y ppa:valhalla-core/valhalla && apt-get update -y

RUN apt-get install -y autoconf automake make libtool pkg-config g++ gcc jq lcov locales coreutils protobuf-compiler vim-common ccache clang-tidy-5.0 clang-5.0 git osmium-tool curl
RUN apt-get install -y libboost-all-dev libcurl4-openssl-dev libgeos-dev libgeos++-dev liblua5.2-dev prime-server0.6.3-bin libprime-server0.6.3-dev libprotobuf-dev libsqlite3-mod-spatialite libspatialite-dev libsqlite3-dev zlib1g-dev liblz4-dev
RUN apt-get install -y python-minimal python-all-dev python3-minimal python3-all-dev lua5.2


# nvm environment variables
ENV NVM_DIR /usr/local/nvm
ENV NODE_VERSION 8.11.3

# install node
RUN mkdir -p ${NVM_DIR}
RUN curl -o- https://raw.githubusercontent.com/creationix/nvm/v0.33.11/install.sh | bash
RUN . $NVM_DIR/nvm.sh \
    && nvm install $NODE_VERSION \
    && nvm alias default $NODE_VERSION \
    && nvm use default

# add node and npm to path so the commands are available
ENV NODE_PATH $NVM_DIR/v$NODE_VERSION/lib/node_modules
ENV PATH $NVM_DIR/versions/node/v$NODE_VERSION/bin:$PATH


# install cmake
ADD https://cmake.org/files/v3.11/cmake-3.11.2-Linux-x86_64.sh /tmp/cmake.sh
RUN sh /tmp/cmake.sh --prefix=/usr/local --skip-license && /bin/rm /tmp/cmake.sh
RUN cmake --version


# set paths
ENV PATH /usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:$PATH
ENV LD_LIBRARY_PATH /usr/local/lib:/lib/x86_64-linux-gnu:/usr/lib/x86_64-linux-gnu:/lib32:/usr/lib32

# clone valhalla
RUN git clone https://github.com/valhalla/valhalla.git
WORKDIR /valhalla
RUN npm install --ignore-scripts
RUN git submodule update --init --recursive
RUN mkdir ./build
WORKDIR /valhalla/build
RUN cmake .. -DCMAKE_BUILD_TYPE=Release
RUN make -j$(nproc)
RUN make install

これをDockerfileで保存し、ビルドします。

docker build . -t anagura/valhalla

routing tilesのビルド

Valhalla本体のビルドが終わったら次はrouting tilesをビルドします。
まず、ビルドに使うディレクトリを作成します。

mkdir valhalla_run

次に、routing tilesのビルドに必要なスクリプトを書き、先程作ったディレクトリvalhalla_runに置きます。
データはOSMのを使います。geofabrikからkanto-latest.osm.pbfをダウンロードします。

valhalla_run.sh

#!/bin/bash
curl -O http://download.geofabrik.de/asia/japan/kanto-latest.osm.pbf
mkdir -p valhalla_tiles
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

valhalla_build_tiles -c valhalla.json kanto-latest.osm.pbf
find valhalla_tiles | sort -n | tar cf valhalla_tiles.tar --no-recursion -T -

そしてビルドのためのdocker-compose.ymlを書きます。
先程使ったビルドしたコンテナを使います。ついでに起動用のコンテナも仕込んでおきます。

docker-compose.yml

version: "3"

services:
   valhalla_build:
      image: anagura/valhalla
      volumes:
        - ./valhalla_run:/valhalla_run
      working_dir: /valhalla_run
      command: ["bash", "./valhalla_run.sh"]
   valhalla_run:
      image: anagura/valhalla
      volumes:
        - ./valhalla_run:/valhalla_run
      working_dir: /valhalla_run
      command: ["valhalla_service", "valhalla.json", "1"]
      ports:
        - "8002:8002"

docker-compose run valhalla_buildでビルドします。これにはしばらく時間がかかります。
今回は関東のデータを使いましたが、日本全国のデータを使う場合、ビルド後で12GBほど容量を食うので足りない場合は容量をあけておきましょう。

Valhallaを起動する

docker-compose up -d valhalla_runで起動します。
localhost:8002/routeに接続し、APIが機能していれば成功です。エラーの場合はAPI referenceをにらめっこしながらデバッグすると良いでしょう。

以下を打ち込んでValhallaのテストをします。

curl http://localhost:8002/route --data '{"locations":[{"lat":35.6812362,"lon":139.7671248},{"lat":35.6820933,"lon":139.7752856}],"costing":"auto","directions_options":{"units":"km"}}'

結果っぽいのが帰ってきてれば成功です。
私の環境では以下のように出てきました。

APIの結果

{
	"trip": {
		"language": "en-US",
		"summary": {
			"max_lon": 139.776245,
			"max_lat": 35.682907,
			"time": 274,
			"length": 1.162,
			"min_lat": 35.67939,
			"min_lon": 139.768738
		},
		"locations": [
			{
				"original_index": 0,
				"lon": 139.76712,
				"lat": 35.681236,
				"type": "break"
			},
			{
				"original_index": 1,
				"type": "break",
				"lon": 139.775284,
				"lat": 35.682095,
				"side_of_street": "left"
			}
		],
		"units": "kilometers",
		"legs": [
			{
				"shape": "{ow`cAayxqiGx\\qfA|DiMNwCG{@WyC|@wCrAwDjAuDnX_}@jBsFsGwDgIsEmTkLoSkL}YeOke@yWe_@_Swc@{UuDyBbAyCj`@{rA`Mib@a]_SqWiNaMhb@zVfNz@\\lUhM",
				"summary": {
					"max_lon": 139.776245,
					"max_lat": 35.682907,
					"time": 274,
					"length": 1.162,
					"min_lat": 35.67939,
					"min_lon": 139.768738
				},
				"maneuvers": [
					{
						"travel_type": "car",
						"travel_mode": "drive",
						"begin_shape_index": 0,
						"length": 0.156,
						"end_shape_index": 5,
						"instruction": "Drive southeast.",
						"verbal_pre_transition_instruction": "Drive southeast for 200 meters.",
						"type": 1,
						"time": 27
					},
					{
						"travel_type": "car",
						"travel_mode": "drive",
						"verbal_pre_transition_instruction": "Bear right onto 八重洲通り, 4 08.",
						"verbal_transition_alert_instruction": "Bear right onto 八重洲通り.",
						"length": 0.141,
						"instruction": "Bear right onto 八重洲通り/408/Yaesu-dori.",
						"end_shape_index": 10,
						"type": 9,
						"time": 59,
						"verbal_post_transition_instruction": "Continue for 100 meters.",
						"street_names": [
							"八重洲通り",
							"408",
							"Yaesu-dori"
						],
						"begin_shape_index": 5
					},
					{
						"travel_type": "car",
						"travel_mode": "drive",
						"end_shape_index": 18,
						"verbal_pre_transition_instruction": "Turn left onto 15, 中央通り.",
						"begin_street_names": [
							"15",
							"中央通り",
							"旧東海道",
							"Chuo-dori"
						],
						"verbal_transition_alert_instruction": "Turn left onto 15.",
						"length": 0.389,
						"instruction": "Turn left onto 15/中央通り/旧東海道/Chuo-dori. Continue on 15/中央通り/旧東海道.",
						"type": 15,
						"time": 45,
						"verbal_post_transition_instruction": "Continue on 15, 中央通り for 400 meters.",
						"street_names": [
							"15",
							"中央通り",
							"旧東海道"
						],
						"begin_shape_index": 10
					},
					{
						"travel_type": "car",
						"travel_mode": "drive",
						"verbal_pre_transition_instruction": "Turn right onto 永代通り, 10.",
						"verbal_transition_alert_instruction": "Turn right onto 永代通り.",
						"length": 0.212,
						"instruction": "Turn right onto 永代通り/10/Eitai-dori.",
						"end_shape_index": 22,
						"type": 10,
						"time": 89,
						"verbal_post_transition_instruction": "Continue for 200 meters.",
						"street_names": [
							"永代通り",
							"10",
							"Eitai-dori"
						],
						"begin_shape_index": 18
					},
					{
						"travel_type": "car",
						"travel_mode": "drive",
						"verbal_multi_cue": true,
						"verbal_pre_transition_instruction": "Turn left onto 昭和通り, 3 16. Then Turn left.",
						"verbal_transition_alert_instruction": "Turn left onto 昭和通り.",
						"length": 0.11,
						"instruction": "Turn left onto 昭和通り/316/Showa-dori.",
						"end_shape_index": 24,
						"type": 15,
						"time": 17,
						"verbal_post_transition_instruction": "Continue for 100 meters.",
						"street_names": [
							"昭和通り",
							"316",
							"Showa-dori"
						],
						"begin_shape_index": 22
					},
					{
						"travel_type": "car",
						"travel_mode": "drive",
						"verbal_pre_transition_instruction": "Turn left. Then Turn left.",
						"verbal_transition_alert_instruction": "Turn left.",
						"length": 0.057,
						"instruction": "Turn left.",
						"end_shape_index": 25,
						"type": 15,
						"time": 6,
						"verbal_multi_cue": true,
						"verbal_post_transition_instruction": "Continue for 60 meters.",
						"begin_shape_index": 24
					},
					{
						"travel_type": "car",
						"verbal_pre_transition_instruction": "Turn left.",
						"verbal_transition_alert_instruction": "Turn left.",
						"length": 0.097,
						"instruction": "Turn left.",
						"end_shape_index": 28,
						"type": 15,
						"time": 31,
						"verbal_post_transition_instruction": "Continue for 100 meters.",
						"begin_shape_index": 25,
						"travel_mode": "drive"
					},
					{
						"travel_type": "car",
						"travel_mode": "drive",
						"begin_shape_index": 28,
						"time": 0,
						"type": 6,
						"end_shape_index": 28,
						"instruction": "Your destination is on the left.",
						"length": 0,
						"verbal_transition_alert_instruction": "Your destination will be on the left.",
						"verbal_pre_transition_instruction": "Your destination is on the left."
					}
				]
			}
		],
		"status_message": "Found route between points",
		"status": 0
	}
}

地図上で経路を引いてみる

さて、APIが使えるようになったところで地図上で確かめてみましょう。

先程のAPIの結果のdata.trip.legs[0].shapeの部分が経路になります。
この結果はpolyline encodingされており、デコードして使います。
Javascriptでデコードする場合は以下のように書きます。

polylineのデコード

let decodePolyline = function (str, precision) {
  let index = 0,
      lat = 0,
      lng = 0,
      coordinates = [],
      shift = 0,
      result = 0,
      byte = null,
      latitudeChange,
      longitudeChange,
      factor = Math.pow(10, precision || 6);


  while (index < str.length) {

    byte = null;
    shift = 0;
    result = 0;

    do {
      byte = str.charCodeAt(index++) - 63;
      result |= (byte & 0x1f) << shift;
      shift += 5;
    } while (byte >= 0x20);

    latitudeChange = ((result & 1) ? ~(result >> 1) : (result >> 1));

    shift = result = 0;

    do {
      byte = str.charCodeAt(index++) - 63;
      result |= (byte & 0x1f) << shift;
      shift += 5;
    } while (byte >= 0x20);

    longitudeChange = ((result & 1) ? ~(result >> 1) : (result >> 1));

    lat += latitudeChange;
    lng += longitudeChange;

    coordinates.push([lng / factor, lat / factor]);
  }

  return coordinates;
};

あとはこれを地図上に描画します。
mapboxの地図を使っているのでaccess tokenが必要となります。
urlのところにはAPIのURLを入れます。

index.html

<!DOCTYPE html>
<html>
<head>
  <meta charset='utf-8' />
  <title>map test</title>
  <script src='https://api.tiles.mapbox.com/mapbox-gl-js/v0.51.0/mapbox-gl.js'></script>
  <link href='https://api.tiles.mapbox.com/mapbox-gl-js/v0.51.0/mapbox-gl.css' rel='stylesheet' />

  <script src="https://code.jquery.com/jquery-3.3.1.min.js"></script>
  <style>
  body { margin:0; padding:0; }
  #map { position:absolute; top:0; bottom:0; width:100%; }
  </style>
</head>
<body>

<div id='map'></div>

<script>
  mapboxgl.accessToken = 'YOUR ACCESS TOKEN';
  let map = new mapboxgl.Map({
    container: 'map',
    style: 'mapbox://styles/mapbox/streets-v9',
    zoom: 14,
    center: [139.7639394, 35.6840311]
  });

  url = "API URL";

  let fromMarker = new mapboxgl.Marker();
  let toMarker = new mapboxgl.Marker();

  map.on('load', function () {

    let addFromMarker = false;
    let route = {}

    map.on('click', function(e) {

      if (!addFromMarker){

        // marker
        fromMarker.remove();
        toMarker.remove();

        // route
        if (map.getLayer("route")){
          map.removeLayer("route");
        }
        if (map.getSource("route")){
          map.removeSource("route");
        }
        route.from = [e.lngLat.lng, e.lngLat.lat];

        fromMarker = new mapboxgl.Marker()
        .setLngLat(route.from)
        .addTo(map);
        addFromMarker = true;
      }else{

        route.to = [e.lngLat.lng, e.lngLat.lat];
        toMarker = new mapboxgl.Marker()
        .setLngLat(route.to)
        .addTo(map);

        addRouting(route.from, route.to);
        addFromMarker = false;
      }


    });
  });

  // 経路を検索して経路を描画する
  let addRouting = function(fromPoint, toPoint){

    let json = {};
    json.locations = [{"lat":fromPoint[1],"lon":fromPoint[0],"radius":10},{"lat":toPoint[1],"lon":toPoint[0],"radius":10}];
    json.costing = "auto";
    json.costing_options = {"auto":{"country_crossing_penalty":2000.0}};
    json.directions_options = {"units":"km"};
    json.use_highway = 0;
    json.avoid_locations = true;
    json.radius = 100;
    json.minimum_reachability = 5;
    json.id = "test_route";

    let polyline = {};

    $.ajax({
      type : "POST",
      url : url,
      data : JSON.stringify(json)
    })
    .done(function( data ) {

      polyline.data = data;
      polyline.decode = decodePolyline(data.trip.legs[0].shape, 6);

      map.addLayer({
        "id": "route",
        "type": "line",
        "source": {
          "type": "geojson",
          "data": {
            "type": "Feature",
            "properties": {},
            "geometry": {
              "type": "LineString",
              "coordinates": polyline.decode
            }
          }
        },
        "layout": {
          "line-join": "round",
          "line-cap": "round"
        },
        "paint": {
          "line-color": "#888",
          "line-width": 8
        }
      });

    });
  }

  // polylineのデコード
let decodePolyline = function (str, precision) {
    let index = 0,
        lat = 0,
        lng = 0,
        coordinates = [],
        shift = 0,
        result = 0,
        byte = null,
        latitudeChange,
        longitudeChange,
        factor = Math.pow(10, precision || 6);


    while (index < str.length) {

      byte = null;
      shift = 0;
      result = 0;

      do {
        byte = str.charCodeAt(index++) - 63;
        result |= (byte & 0x1f) << shift;
        shift += 5;
      } while (byte >= 0x20);

      latitudeChange = ((result & 1) ? ~(result >> 1) : (result >> 1));

      shift = result = 0;

      do {
        byte = str.charCodeAt(index++) - 63;
        result |= (byte & 0x1f) << shift;
        shift += 5;
      } while (byte >= 0x20);

      longitudeChange = ((result & 1) ? ~(result >> 1) : (result >> 1));

      lat += latitudeChange;
      lng += longitudeChange;

      coordinates.push([lng / factor, lat / factor]);
    }

    return coordinates;
  };

  </script>
</body>
</html>

index.htmlを開いて試すと このようになります。