コスト距離分析

空間分析および地理情報システムにおいて、コスト距離分析またはコストパス分析は、制約のない（2次元）空間を通る1つ以上の最適な移動経路を決定する方法です。^{[1]最適解は、局所的な要因により空間上で変化するコスト密度（線形単位あたりのコスト）の}フィールドに基づいて、経路の総コストを最小化する解です。したがって、これは距離の摩擦という基本的な地理原理に基づいています。これは、ほとんどのGISソフトウェアに実装されている、 複数の決定論的アルゴリズム解を伴う最適化問題です。

コスト距離分析のさまざまな問題、アルゴリズム、ツールは、制約のない 2 次元空間で機能します。つまり、パスはどのような形状でもかまいません。同様のコスト最適化問題は、制約のある空間、特に道路や通信ネットワークなどの1 次元線形ネットワークでも発生する可能性があります。原理的には似ていますが、ネットワーク空間の問題を解くには、主にグラフ理論から採用された非常に異なる (通常はより単純な) アルゴリズムが必要です。これらの問題を解決するための GIS ツールのコレクションは、ネットワーク分析と呼ばれます。

人間には、最小限の労力と時間で旅行したいという生来の欲求があるようです。歴史的な道路、さらには古代の道路は、現代の計算アルゴリズムが生成するパターンに似ており、平坦な場所をまっすぐ進みながら、山や峡谷、密生した植物を迂回しています。

しかし、地理学者がこの経路最適化を説明する理論と、それを再現するアルゴリズムを開発したのは 20 世紀になってからでした。1957 年、地理学における定量的革命のさなか、社会物理学として知られる「ハード」サイエンスの原理や数学的形式を採用する傾向があったとき、ウィリアム ワーンツは屈折を例えとして、移動コストを最小化することで、距離の摩擦が大きく異なる 2 つの地形の境界(たとえば、森林から草原に出る) で輸送経路の方向が変わることのたとえとして使用しました。^[2]コストを最小化するために方向を変えるというワーンツの「節約的移動」の原理は広く受け入れられましたが、屈折の類推と数学 (スネルの法則) は、通常複雑な地理的状況にうまく対応できないという理由から、広く受け入れられませんでした。^[3]

その後、ワーンツらは別の類推を採用し、移動コストが空間的に連続的に変化する一般的な状況で、地形と比較することで、はるかに効果的であることが証明されました。^[4]彼らは、コスト率 (つまり、単位距離あたりのコスト、コストが時間の場合は速度の逆数) を地形表面の傾斜 (つまり、単位距離あたりの標高の変化) と比較しました。これらは両方とも、累積関数または累積フィールドの数学的導関数です。地形の場合は、垂直基準 (海面) からの合計標高です。特定の開始点からコスト率フィールドを積分すると、その点からの移動の総累積コストの類似した表面が作成されます。小川が下り坂で抵抗が最も少ない経路をたどるのと同じように、任意の点から「下」のソースまでのコスト累積表面上の流線は、最小コストの経路になります。^{[5] [6] 1960 年代の追加の研究では、}距離の摩擦の概念の現れとしてのコスト率フィールドの性質がさらに発展し、さまざまな地理的特徴によってコスト率フィールドがどのように影響を受けるかが研究されました。^[7]

当時、このソリューションは理論上のもので、連続ソリューションに必要なデータと計算能力が不足していました。ラスター GIS は、連続積分を離散的な合計手順に変換することで、理論ソリューションを実装するための最初の実行可能なプラットフォームを提供しました。Dana Tomlin は1986 年までにコスト距離分析を Map Analysis Package に実装し、Ronald Eastman は1989 年までに、より効率的な「プッシュブルーム」コスト累積アルゴリズムを使用して IDRISIに追加しました。 ^[8] Douglas (1994) は累積アルゴリズムをさらに改良し、これが基本的に現在のほとんどの GIS ソフトウェアに実装されています。^[9]

コスト距離分析で使用される主要なデータセットはコストラスターであり、通過コスト面、^[9]、摩擦イメージ、^[8]、コスト率フィールド、またはコスト面と呼ばれることもあります。ほとんどの実装では、これはラスターグリッドであり、各セルの値は、水平方向または垂直方向にセルを横切る経路のコスト（つまり、時間、お金、エネルギーなどの消費されたリソース）を表します。^[10]したがって、これはコスト率（線形単位あたりのコスト）のフィールドを離散化し、空間的に集約的なプロパティにします。このコストは、距離の摩擦の原理の現れです。

特定のルーティング問題では、さまざまな種類のコストが関係する可能性があります。

• 移動コスト、セル内を移動するために必要なリソースの消費量、通常は時間またはエネルギー/燃料。
• 建設コスト、道路、パイプ、ケーブルなど、移動を可能にするインフラストラクチャを構築するために必要なリソース（通常は金銭）。建設コストには一定なもの（舗装材料など）もありますが、土地の取得や掘削など、空間によって変化するものもあります。
• 環境影響とは、インフラやそれに沿った移動によって引き起こされる自然環境や人間環境への悪影響です。たとえば、住宅街や湿地帯を通る高速道路を建設すると、高い政治的コストが発生します (環境影響評価、抗議、訴訟などの形で)。

これらのコストの中には、移動時間、燃料消費、建設費など、簡単に定量化・測定できるものもあり、当然ながら計算による解決法に適しています。とはいえ、ルートを実装する前にコストを予測することは、かなりの不確実性を伴う可能性があります。その他のコストは、政治的抗議や環境への影響など、定性的または主観的な性質のために測定がはるかに困難であり、通常、尺度の作成による運用化が必要です。^[11]

多くの場合、複数の種類のコストが同時に関連している場合があり、合計コストはそれらの組み合わせになります。異なるコストは異なる単位 (スケールの場合は単位なし) で表されるため、通常は直接合計することはできず、インデックス を作成して組み合わせる必要があります。一般的な種類のインデックスは、各要素を一貫した範囲 (たとえば、[0,1]) にスケーリングしてから、加重線形結合を使用して組み合わせることによって作成されます。このようなインデックス モデルの作成で重要な部分は、キャリブレーション (統計)です。これは、階層分析プロセスなどの方法を使用して、モデル化された相対コストが実際のコストと一致するように式のパラメーターを調整することです。インデックス モデル式は通常、各コスト要素を表すラスター グリッドからマップ代数ツールを使用してラスター GIS に実装され、単一のコスト ラスター グリッドが生成されます。

従来の方法の限界の 1 つは、コスト フィールドが等方性または全方向性であることです。つまり、特定の場所のコストは、移動方向に依存しません。これは多くの状況では適切ですが、そうでない場合もあります。たとえば、風の強い場所を飛行している場合、風の方向に飛行する飛行機は、風に逆らって飛行する飛行機よりもはるかに低いコストしかかかりません。コスト距離分析アルゴリズムを拡張して方向コストを組み込む研究が行われていますが、GIS ソフトウェアではまだ広く実装されていません。^[12] IDRISI は異方性をサポートしています。^[1]

最も一般的なコスト距離タスクは、与えられた出発地と目的地の間の空間を通る、累積総コストが最小となる単一の経路を決定することである。典型的なソリューションアルゴリズムは、WarntzとLindgrenのコスト積分戦略^{[5]の離散ラスター実装であり、}決定論的（NP完全）最適化である。^[10]

1. 入力: コスト フィールド ラスター、ソース位置、宛先位置 (ほとんどの実装では、複数のソースと宛先を同時に解決できます)
2. 累積: ソース位置から始めて、グリッド内の他のすべてのセルに到達するために必要な最小の総コストを計算します。イーストマンとダグラスによって公開されたものなど、いくつかのアルゴリズムがありますが、^{[8] [9]}一般的に同様の戦略に従います。^[13]このプロセスでは、重要な副産物として、通常バックリンクグリッド(Esri) または移動方向グリッド(GRASS) と呼ばれる 2 番目のラスターグリッドも作成されます。このグリッドでは、各セルに方向コード (0-7) があり、8 つの隣接セルのうちどのセルが最もコストが低かったかを表します。
   1. すでに累積コストが割り当てられている少なくとも 1 つのセルに隣接するセルを検索します (最初はソース セルのみ)
   2. 累積コストが最も低い隣接ノードを特定します。バックリンク グリッド内のターゲットからコストが最も低い隣接ノードまでの方向をエンコードします。
   3. ターゲットセルのコスト（またはターゲットセルと隣接セルのコストの平均）を隣接セルの累積コストに追加して、ターゲットセルの累積コストを作成します。隣接セルが対角の場合、ローカルコストは次の式で乗算されます。${\displaystyle {\sqrt {2}}}$
   4. アルゴリズムでは、間接的なルートの方がコストが低くなる可能性があることも考慮する必要があり、多くの場合、ハッシュ テーブルを使用して、再検討できる計算の拡大境界に沿った一時的なコスト値を追跡します。
   5. すべてのセルが割り当てられるまでこの手順を繰り返します。
3. 排水: 地形のアナロジーに従って、ある場所から流れ出る小川のように、指定された目的地からソースに戻る最適なルートをトレースします。最も基本的な方法では、これは、目的地のセルから開始し、バックリンク グリッドで示された方向に移動し、次のセルで繰り返し、ソースに到達するまでこれを繰り返します。最近のソフトウェアでは、3 つ以上のセルを横切って見て、8 つの隣接方向以外の角度の直線を認識するなど、いくつかの改善が加えられています。たとえば、GRASS の r.walk 関数は、「ナイトの動き」(1 セルは直線、次に 1 セルは対角) を認識し、中央のセルを迂回する直線を描画できます。

最小コスト パス問題の少し異なるバージョン (ファジー バージョンとも言える) では、幅が 1 セルを超える回廊を探すため、結果の適用に柔軟性が生まれます。回廊は、交通計画や野生生物管理でよく使用されます。

この問題の解決方法は、調査空間内のすべてのセルについて、そのセルを通過する特定のソースとデスティネーション間の最適パスの合計累積コストを計算することです。したがって、上記で導出された最適パス内のすべてのセルは同じ最小値を持ちます。このパスに近いセルには、最適パスからわずかに逸脱するパスで到達するため、コスト値は比較的低くなります。遠方のセルほどコスト値が増加するため、全体としてあいまいなエッジを持つ回廊が形成されます。

このコリドー フィールドを導出するアルゴリズムは、2 つのコスト累積グリッドを生成することによって作成されます。1 つは、前述のようにソースを使用します。次に、ソースとしてデスティネーションを使用して、アルゴリズムを繰り返します。次に、マップ代数演算を使用して、これらの 2 つのグリッドを追加します。これが機能するのは、各セルを通過する最適なソース - デスティネーション パスが、そのセルからソースへの最適なパスに、そのセルからデスティネーションへの最適なパスを追加したものであるためです。これは、上記のコスト累積ツールとマップ代数演算ツールを使用して実行できますが、ArcGISには、このプロセスを自動化するコリドー ツールが用意されています。

コスト累積アルゴリズムのもう 1 つの用途は、複数のソース間で空間を分割することです。各セルは、最低コストで到達できるソースに割り当てられ、各ソースが「最も近い」一連の領域が作成されます。地形のアナロジーでは、これらは分水界に対応します (したがって、これらを「コスト シェッド」と呼ぶこともできますが、この用語は一般的に使用されていません)。これらは、本質的には一定のコストでの空間の割り当てであるボロノイ図に直接関連しています。これらは、概念的には (計算上ではないにしても)、ネットワーク分析の位置割り当てツール に似ています。

コストベースの割り当ては、2 つの方法で作成できます。1 つ目は、コスト累積アルゴリズムの修正版を使用する方法です。これは、割り当てグリッドの代わりにバックリンク グリッドを使用する方法です。この方法では、各セルにコストが最も低い隣接セルと同じソース識別子が割り当てられ、各ソースのドメインが徐々に拡大して、互いに出会うようになります。これは、ArcGIS Proで採用されているアプローチです。^[14] 2 つ目の解決策は、まず基本的な累積アルゴリズムを実行し、次にバックリンク グリッドを使用して各セルが「流入」するソースを決定することです。GRASS GIS はこのアプローチを使用します。実際、地形から流域を計算するのと同じツールが使用されています。^[15]

コスト距離ツールは、ほとんどのラスター GIS ソフトウェアで利用できます。

• GRASS GIS（多くの場合、QGISにバンドルされています）、累積（r.cost）と排出（r.walk）関数が別々に用意されています。
• ArcGIS DesktopとArcGIS Proには、累積（コスト距離）とドレイン（コストパス）のジオプロセシングツールと、コリドー生成が別々に用意されています。最近では、ArcGIS Proバージョン2.5から、より高度なアルゴリズムとより柔軟なオプションを使用した新しいコスト距離ツールセットが導入されました。^[16]
• TerrSet（旧称Idrisi）には、異方性（方向性）コストを含むさまざまな種類のコスト距離問題を解決するためのさまざまなアルゴリズムを実装したツールがいくつかあります。^[17]

コスト距離分析は考古学^[18]や景観生態学^[19]を含む地理学関連の幅広い分野で応用されています。

• Esri ArcGIS Pro の距離ツールセットのドキュメント
• GRASS GIS のコスト サーフェス ツール