OSRM

最短路を計算するアプリとしてOSRMが無料で安定しているようなので，入れてみた．

Dockerでも入れられると書いてあるがメモリ制約のため動かないので，ローカルに入れる．方法は， 

Project-OSRM/osrm-backend

にある．環境はMacだ．

まずgitをクローンする．

git clone https://github.com/Project-OSRM/osrm-backend.git

色々とbrewでインストールする．

brew install boost git cmake libzip libxml2 lua tbb ccache
brew install GDAL

コンパイルする．

cd osrm-backend
mkdir -p build
cd build
cmake ..
make

データをこちらからダウンロードする． http://download.geofabrik.de/

wget http://download.geofabrik.de/asia/japan/kanto-latest.osm.pbf wget http://download.geofabrik.de/asia/japan/japan-latest.osm.pbf

日本全国のデータをもってくる．

./osrm-extract japan-latest.osm.pbf
./osrm-partition japan-latest.osrm
./osrm-customize japan-latest.osrm

２つのアルゴリズムで高速な最短路を解くための前処理データを準備する．

こちらは古い方法：

./osrm-routed --algorithm=MLD japan-latest.osrm

CH　(Contraction Hierarchies) アルゴリズムの場合は，もうひと手間かかる．この計算は結構かかる．16コア，64Gマシンでも数時間かかる．

 ./osrm-contract japan-latest.osrm 
./osrm-routed  japan-latest.osrm

実行時にRAMが64Gいるようだ．（追記：実験したら日本の全国で10G程度のようだ．）また，全点間の道路距離と時間を計算するには，オプションを以下のように変更する必要がある．計算時間は4000点で30秒程度（16コア）のようだ．

./osrm-routed --max-table-size=10000 japan-latest.osrm

これだとクラウドだとつらい．軽量の前処理高速化最短路は，我々が昔やったのがある https://www.logopt.com/mikiokubo/SP/  が，これをOpen Street Mapに移植するのは安定性で問題が出そうだ．

Pythonからの呼び出しは https://github.com/gojuno/osrm-py をみつけたが，ソースをみるといまいちだ．こんな感じで使う．

import osrm
client = osrm.Client(host='http://localhost:5000')
response = client.route(
   coordinates=[ [140.25605662,35.182874], [139.70691895,36.774624]],
   overview=osrm.overview.full)

で最短路計算，

response = client.nearest(
   coordinates=[[140.25605662,35.182874]],
   radiuses=[700],
   number=20
)

で近い点の探索ができるが，肝心の距離行列の計算がない．（いちいち最短経路を計算するとルート (waypoint)を返すので時間がかかる．）

直接，requests.getで結果を得る．

   ROUTE =[]
   for row in cust_df.itertuples():
       ROUTE.append( [row.latitude, row.longitude] )
   #ROUTE =[[35.182874,140.25605662],[34.651343,135.82379671],[36.774624,139.70691895], [35.134927,137.01172581],[34.651343,135.82379671],[33.740026,130.92690378]]
   route_str =""
   for (i,j) in ROUTE[:]:
       route_str += str(j)+","+str(i)+";"
   response = requests.get('http://localhost:5000/table/v1/driving/'+route_str[:-1]+"?annotations=distance,duration")
   result = response.json()
   durations = result["durations"]
   distances = result["distances"]
​