1

ベルギーには 2750 の都市センターがあります。2 つの都市の中心間の距離を知る必要があります。しかし、それは 57MB のマトリックスになり、それらの距離 (ルートでさえも) を記憶するためだけに、非常にスケールが大きくなります。

代わりに、高速道路の交差点をハブとして使用することを検討しています。基本的に、すべての都市は近くの都市であり、近くのハブ (= 高速道路の交差点) であることを認識しています。すべてのハブは、相互の距離を認識しています。

したがって、ある都市 A から近くにない別の都市 B までの距離は、 の距離で計算できますcityA -> hubX -> hubY -> cityB。通常、ほとんどの都市には近くに 3 つのハブがあるため、9 つの組み合わせすべてを調べて、最短のものを取得する必要があるかもしれません。ただし、いずれにせよ、メモリに関してはより適切にスケーリングする必要があります。

ここで問題: 高速道路の交差点を 1 つのポイントとして記述できますか? 考えてみてください: 高速道路は 2 本の道路 (両方向に 1 本) で構成されているため、高速道路の交差点の中心には 4 本の道路があります (アームを数えなくても)。

4

1 に答える 1

1

いくつかのアイデア:

  1. これらの距離は、MapDB または GraphHopper を介してオフヒープまたはオンディスクに保存できます。単純化された DataAccess 実装により、RAM に依存しません。
  2. 〜30MBまたはさらに短いfloatを使用して、キロメートルを使用することができます
  3. ルートの計算には数ミリ秒しかかからないため、保存せずにオンデマンド ルーティングを試すことができます。指示を無効にしてポイントを計算すると、2 倍の速さになります。距離の計算を無効にして、path.weight だけを使用することもできます。これにより、別の優れた高速化が得られますが、GraphHopper の使用レベルが少し低くなる必要があり、何をするかを理解している場合にのみお勧めします。

今あなたの質問に。GraphHopper は、ノード (ジャンクション) とエッジ (ジャンクションを結ぶ通り) で構成されるグラフ モデルを使用します。それでも、ラウンドアバウトは複数のノードで構成されています。しかし、一般的には、そのような「離脱」ノードを「hub-id」として使用できるはずです。

これらのノードを計算するには、次の 2 つの方法があります。

  • 収縮階層を実行し、上位 1000 個のノードを選択して、それらをハブとして定義します。これは、「トランジット ノード ルーティング」ペーパーで説明されているものと同様です。
  • または、1 つの都市から他のすべての都市 (または 8 つの地理的方向のみ) へのルートを計算し、2 つのルートの最後の共通ノードを見つけて、いくつかを特定します。

どちらのアプローチでも、GraphHopper をもう少し深く掘り下げる必要があり、おそらく下位レベルの APIが必要になるでしょう。

于 2014-09-04T11:29:43.120 に答える