8

最近、 OSRMルーティング ライブラリをいじっています。最短経路問題を解くのに非常に効率的であると思われます。ただし、それを使用して単一ソースの最短パスを計算する方法がわかりませんでした。より正確には、固定された開始点が与えられた場合、指定された距離制限内 (たとえば、30 分以内に到達可能) に到達できるすべての場所への最短距離を計算します。

OSRM は、縮約階層を内部的に使用します。私の理解では、この手法は、実世界のデータで 2 地点間の距離を計算する場合、Dijkstra のアルゴリズムよりもはるかに優れています。しかし、私の問題には、Dijkstra のアルゴリズムの方が適しているようですね。

OSRM は、単一ソースの最短経路問題 (距離に制限あり) を計算するための API を提供していますか? この種の問題により適した無料のルーティング ライブラリは他にありますか? できれば、OpenStreetMap データを適切にサポートするもの。

4

1 に答える 1

9

OSRM は縮小階層 (CH) を使用して、「1 対 1 のルーティング」を高速化します。CH を機能させるには、適合した双方向アルゴリズム (A*、Dijkstra など) が必要なので、単一ソースのケースはより困難です。ただし、必要な目的地が事前にわかっている場合、1対多のアルゴリズムは比較的単純です。

また、ルックアップ テーブルを使用する「非目標指向の双方向検索」のソリューションが必要な場合は、論文「Fast Detour Computation for Ride Sharing」またはこちらを参照してください。

他の無料のルーティング ライブラリはありますか?

私のJava GraphHopperプロジェクトをお勧めします;）

しかし、もちろんもっとあります: http://wiki.openstreetmap.org/wiki/Routing

于 2013-01-05T17:52:18.143 に答える