OSRM (Open Source Routing Machine) を使って経路探索する
はじめに
交通や移動に関するプログラムを書いているとき，2点間の移動経路や距離を計算したいことがよくあります[1]．2点が平面上の点であると仮定すると
緯度経度
のような計算を実装しておけば，簡単に利用することができます．大昔に私がJuliaで書いたコードをペタリします．
R = 6371000 # Radius of the Earth
S1 = Point(35.18028,136.90667) # Nagoya
S2 = Point(35.68944,139.69167) # Tokyo
# ground distance
function dG(Si::Point, Sj::Point)
φi, λi = deg2rad(Si.φ), deg2rad(Si.λ)
φj, λj = deg2rad(Sj.φ), deg2rad(Sj.λ)
v1 = sin( (φj - φi) / 2 )
v2 = sin( (λj - λi) / 2 )
return 2 * R * asin(sqrt( v1^2 + cos(φi) * cos(φj) * v2^2 ))
end
println("Example dG = $(dG(S1, S2)/1000) [km]")
そこそこに計算ができます．一方で交通や移動に関するプログラムを書いているとき，球に基づく距離ではなく道路上で移動した距離が欲しくなることが多数です．ここではOSRMを利用し，OpenStreetMapのデータの上で経路を取得する方法を説明します．
環境
OSRMです．
名前の通り，最短経路を計算するための機構です．真面目にローカルにインストールしても良いのですが，ちゃんと docker で利用できる orsm-backend というコンテナが用意されているのでそちらを利用することにします．よって以降では，何らかの方法で docker pull が行える一方で Google map にアクセスできない環境で開発しているエンジニアを想定します[2]．
まずデータとコンテナの準備ですが，今回は最近暑くなってきたことを考慮して北海道のOpenStreetMapデータを利用することにします．まとまった単位でダウンロードできるOpenStreetMapデータとして geofabrik からダウンロードできるものがあります (asia → Japan → Hokkaido)．コンテナの pull と合わせて以下を叩いておきます．
docker pull osrm/osrm-backend
wget http://download.geofabrik.de/asia/japan/hokkaido-latest.osm.pbf
前処理
まずは得られた osm.pbf ファイルをOSRMの前処理にかけます．環境としてはカレントディレクトリに hokkaido-latest.osm.pbf がダウンロードされているとして，以下のコマンドを叩きます[3]．日本全体を処理すると少し時間がかかりますが，北海道単位ぐらいだとお茶を飲んでいるぐらいの間隔で終わります．Dockerの設定でカレントディレクトリのデータをコンテナ上の /data へ対応付けさせています．
docker run -t -v "${PWD}:/data" osrm/osrm-backend \
osrm-extract -p /opt/car.lua /data/hokkaido-latest.osm.pbf
docker run -t -v "${PWD}:/data" osrm/osrm-backend \
osrm-partition /data/hokkaido-latest.osrm
docker run -t -v "${PWD}:/data" osrm/osrm-backend \
osrm-customize /data/hokkaido-latest.osrm
backendの起動
上のコマンドを叩いた後，たくさんのファイルが生成されています．この状態で backend を起動しておきます (アルゴリズムはとりあえずmld; Multi-Level Dijkstraです)．
docker run -t -i -p 5000:5000 -v "${PWD}:/data" osrm/osrm-backend \
osrm-routed --algorithm mld /data/hokkaido-latest.osrm
PythonからOSRMを利用する
現在 docker のコンテナを起動した状態になっているとします．プログラムを実行する環境から，docker が動いている環境に対してクエリを投げることで，計算結果が JSON で返ってきます．
2点間の緯度経度を
http://(docker ip):5000/route/v1/driving/{
},{ lon_1 };{ lat_1 },{ lon_2 } lat_2
の形で与えます (他にはパラメータを付けて渡します)．詳しくはOSRMのドキュメントを確認してください．
利用例
ここでは以下の2点を考えます．
- 点1:
(43.069060, 141.348117) - 点2:
(44.0997897, 142.449705)
この2点の情報を投げ，JSONとしてパースし，通過する経路を python で parse すると次のようになります (192.168.0.150は dockerを動かしているPCです)．
import requests
loc_pick = [141.348117, 43.069060]
loc_del = [142.449705, 44.0997897]
query_url = "http://192.168.0.150:5000/route/v1/driving/{},{};{},{}?steps=true".format(loc_pick[0], loc_pick[1], loc_del[0], loc_del[1])
response = requests.get(query_url)
result = response.json()
route = result["routes"][0]
legs = route["legs"][0]["steps"]
list_locations = []
for point in legs:
for it in point["intersections"]:
list_locations.append(it["location"][::-1])
このようにして経路情報がリストで得られたので，python の foliumを利用して描画してみましょう．得られたmap.htmlをサーバ的に閲覧 (例えば python -m http.server してからアクセス) すると地図が表示されます．
import folium
folium_map = folium.Map(location=loc_mid[::-1], zoom_start=14)
folium.Marker(location=loc_pick[::-1], icon=folium.Icon(color='red')).add_to(folium_map)
folium.Marker(location=loc_del[::-1]).add_to(folium_map)
line = folium.vector_layers.PolyLine(locations=list_locations, color='black', weight=10)
line.add_to(folium_map)
folium_map.save("map.html")
得られた地図と地点をプロットしたものの様子です．おそらく良さそうですね！
せっかくなので，2点間の経路検索を Google map で検索してみた図をペタりします．
微妙に異なる気もしますが，インターネットから隔離されている環境で見られる情報としてはそこそこのものでしょうか．ついでに横に並べてみます．
| OSRM + OpenStreetMap | Google map |
|---|---|
|
|
良さそうですね！これで Google map が使えない環境でも交通や移動に関するプログラムが行えそうです．
Discussion