0

Postgres/PostGIS/pgRouting を使用して、行っている分析用のデータセットを準備しています。用意する必要があるデータセットの 1 つのフィールドは、10 万世帯のデータセット (ポイント データ) と数十の活動拠点のデータセット (同じくポイント データ) の間の最短道路距離です。これに備えて、ノードとネットワーク データセットを作成しました。また、最も近いノードの id 値を保持する列を使用して、世帯と活動センターのデータセットを更新しました。

これまでのところ、私は Driving_distance() 関数を使用して、中央ビジネス地区 (CBD) からすべての世帯までの道路距離を計算することができましたが、これをすべてのセンターに対して 1 回の実行で実行し、個別の距離データセットを作成する必要がないようにしたいと考えています。センターごとに。

さらに、最終的には、各世帯と最寄りの鉄道駅の間の道路距離についても同じことを行う必要があります。

これに対する解決策はありますか？

どうもありがとう、

ロ

4

1 に答える 1

1

私はあなたの問題を正しく理解したかどうかわかりません。のような場合

  • あなたは10万世帯を持っています
  • 他の関心のあるポイント（アクティビティセンター、鉄道駅など）の数が少ない（1kの場合もあります）
  • 目的は、実行時の計算をあまり行わずに、世帯の1つから関心のあるポイントへ/への最短経路を示すことです。
  • 私はさらに、あなたが持っている道路データが指示されている、つまり片道の道路があるかもしれないと仮定しています。
  • これらのポイントはあまり頻繁に変更されませんが、

次に、次のようなアプローチを試すことができます。

  1. すべての100+1kノードと道路をエッジとして持つ有向グラフを準備します。道路は、距離に比例した重みでノードからノードへと誘導されます。
  2. 同じの逆グラフを準備します。つまり、同じ重みを維持しながら、ノードからノードとノードに切り替えるだけです。
  3. 関心のあるポイントPごとに、ダイクストラ法を実行します。ダイクストラ法は、Pから他のすべてのポイントまでの最短距離を与える100 + 1kポイントの完全な先行マップ（配列としての最短経路ツリー）を返します。これは、100 +1k値の整数配列です。
  4. 逆のグラフでこれを繰り返します。これにより、他のすべてのポイントから関心のある各ポイントPまでの最短距離を与えるpredecessor_mapが得られます。
  5. これで、2 * 1kの配列ができ、それぞれに100+1kの値があります。各配列を使用すると、その中の点Pの位置もわかります。

実行時の計算：

  • Pから他のポイントへの最短経路を計算するには、最初の配列を使用します。配列上のターゲットポイントの場所に移動し、対応する値を確認して、配列上のその要素に移動し、Pの位置に到達するまで繰り返します。

例：Pが7番目の位置にあり、終点が12番目の位置にある場合、配列要素12に移動し、その値array_val [12] = 10を読み取ります。ここで、array_val [10] = 7とすると、パスは7になります。 -10-12。

  • 同様に、2番目の配列でこの操作を行う場合、最短パスは逆の順序、つまり12-10-7のパスになります。

観察：

  1. 上記の2つのステップは、実行時（ミリ秒）で実行する方がはるかに高速です。これらの実行時にダイクストラは必要ありません。
  2. 2 * 1kの最短パスツリーの初回計算には、合計で約2 * 1000 * 0.8 = 1600秒かかります（4 GBのRAMとi5プロセッサを搭載したLinuxラップトップの場合）。
  3. ただし、これを行うには、boost-graphを直接使用することをお勧めします。

pgroutingの使用：

pgroutingを使用する場合は、boost_wrapper.cpp関数boost_dijkstraを変更して、最短パスを1つだけではなく、完全なpredecessor_mapを返すことができます（path_vectにコピーします）。これにより、pgrouting dijkstraは、最短パスだけでなく、常に最短パスツリーを返すようになります。私はこれをまだテストしていません（pgroutingは内部でインデックスの並べ替えを行いますが、このメソッドは元のインデックスIDを返すはずです）。

于 2012-09-04T16:52:19.710 に答える