(コネタ) extract + contract / extract + partition + customize の差

osrm-contractがおそい

osrmで地図をビルドする方法には二通りあるわけですが、
俺々lua w/ ラスタデータ にしてから
osrm-contractの方が非常に時間がかかるようになりました。

差分は？

公式のQ&Aサイトでも contract が遅いと言っている人がいます。

@wieringen OSRM contains two "acceleration algorithms":
https://github.com/Project-OSRM/osrm-backend/issues/4584#issuecomment-340217359

で、差分はなんだろうと思い調べてみました。

osrm-extract+osrm-contract = CH (Contraction Hierarchies). Slow to pre-process, but queries are very fast on the generated data.
osrm-extract+osrm-partition+osrm-customize = MLD (Multi-Level Dijkstra). Faster to pre-process, but queries are slower than CH (perhaps 2x or 3x slower)
After data processing, the routing results should be identical, except for query speed.

検索アルゴリズムの違い

• CH(Contraction Hierarchies)はデータ作成時(pre-process)に多くのことをやるので、検索(query)が早い
• Multi-Level Dijkstra は検索がやや遅い

まとめると

• extract + contract --> データ作成遅い、ランタイム検索早い
• extract + partition + customize --> データ作成速い、ランタイム検索遅い

以上です