ArcGIS Network Analyst エクステンションで使用されるアルゴリズム
ArcGIS Network Analyst エクステンションに含まれているルート解析（ルート、最寄り施設、OD コスト マトリックス）は、最短経路を見つける方法として有名なダイクストラのアルゴリズムに基づきます。これら 3 つの解析では、2 種類の経路検索アルゴリズムが実装されます。1 つめは厳密な最短経路、2 つめはパフォーマンスを速くするための階層ルート解析です。従来のダイクストラのアルゴリズムでは、方向が定められていない正の重み付きグラフを使って最短経路解析が行われます。このアルゴリズムを現実世界の輸送データの環境で使用するには、ユーザが指定したコスト属性を最小限に抑えながら、一方通行規制、ターン規制、ジャンクションのインピーダンス、バリア、道路の左右どちら側に停止するかの指定などのユーザ設定が考慮されるようにアルゴリズムを変更します。ダイクストラのアルゴリズムのパフォーマンスは、d ヒープなどの優れたデータ構造を使用することによってさらに向上します。また、このアルゴリズムでは、ジャンクションだけではなく、エッジに沿った任意のロケーションをモデリングできることが必要です。
ダイクストラのアルゴリズム
従来のダイクストラのアルゴリズムでは、重み付きグラフを使って単一ソースの最短経路解析が行われます。起点 s から終点 d までの最短経路を見つけるために、ダイクストラのアルゴリズムでは、s からの最終的な最短経路がすでに計算されているジャンクションのセット S が管理されます。アルゴリズムでは、ジャンクション セット内で最短経路の推定値が最小となるジャンクションを繰り返し検索し、その値をジャンクション セット S に追加し、S に含まれていない、このジャンクションの近くにあるすべてのジャンクションの最短経路の推定値を更新します。このアルゴリズムは、終点のジャンクションが S に追加されるまで継続されます。
最寄り施設
この解析は、ダイクストラのアルゴリズムに基づく複数の起点、複数の終点のアルゴリズムを使用します。指定したカットオフ内に最短経路がある場合のみ計算したり、特定数の最寄り施設を解析したりするオプションがあります。
OD コスト マトリックス
この解析は、ダイクストラのアルゴリズムに基づく複数の起点、複数の終点のアルゴリズムを使用します。指定したカットオフ内に最短経路がある場合のみ計算したり、特定数の最寄りの終点を解析したりするオプションがあります。OD コスト マトリックス解析は最寄り施設の検出に似ていますが、オーバーヘッドを減らし、パフォーマンスを向上するために、結果として得られた最短経路の形状を計算しないという点で異なります。
階層ルート
全国規模のネットワーク データセットでの厳密な最短経路の検索は、検索する必要があるエッジの数が膨大になるため時間がかかります。パフォーマンスを向上させるために、交通システムにおける自然な階層（生活道路を運転するよりも高速道路を運転する方が好ましいなど）をネットワーク データセットでモデル化することができます。階層ネットワークが作成されると、修正された双方向のダイクストラ アルゴリズムを使用して、起点と終点の間のルートが計算されます。
ここでの全体的な目的は、ネットワークに存在する上位階層を優先しながらインピーダンスを最小限にすることです。この目的を達成するために、起点と終点の両方だけでなく、上位道路への接続点や入口点からも同時に検索を行い、次に起点と終点の両方からの線分が出会うまで上位道路を検索します。検索は上位階層に限定して行われるため、検索対象となるエッジの数が少なくなり、パフォーマンスが速くなります。これはヒューリスティック アルゴリズムであり、その目標は速いパフォーマンスと適切なソリューションですが、最短経路の検出を保証するものではないことに注意してください。このヒューリスティクスが有効に昨日するには、行き止まりに達した場合に階層レベルが下位レベルに下がらないように、最上位レベルの階層を接続する必要があります。
一般に、エッジの重みが移動時間に基づく階層ネットワークでこの解析を使用することは意味があります。これは、人が通常は高速道路網を選んで運転するということを前提としています。
ルート解析用の巡回セールスマン問題オプション
ルート解析には、ストップ位置を訪問する最適な順序を生成するオプションがあります。これは巡回セールスマン問題（TSP）として知られています。TSP は組み合わせ問題です。つまり、最適な順序を検索するための直接的な方法はありません。ヒューリスティクスは、このような問題に対する適切なソリューションを短時間で検索するために使用されます。Network Analyst に TSP を実装することにより、各ストップでのタイム ウィンドウも処理されます。つまり、遅れを最小限にして各ストップを訪問する最適な順序が検索されます。
巡回セールスマン解析は、順序付けするすべてのストップ間での起点 - 終点コスト マトリックスの生成で開始され、タブー探索に基づくアルゴリズムを使用して、ストップを訪問する最適な順序を検索します。タブー探索とは、組み合わせ問題を解析するためのメタヒューリスティック アルゴリズムです。これは局所探索アルゴリズムの領域に入ります。タブー探索の厳密な実装は所有権で保護されていますが、Esri では適切な結果を迅速に得るために、社内で広範にわたる研究開発を行っています。
タイム ウィンドウを使用する配車ルート
配車ルート（VRP）は巡回セールスマン問題の上位集合です。TSP では、ストップを 1 つのセットにまとめて最適な方法で順序付けします。VRP では、全体の経路コストが最小限になるように、ルートまたは車両のセットに順序のセットを割り当てる必要があります。車両の最大積載重量、配送のタイム ウィンドウ、ドライバの特殊技能などの現実世界の制約に従う必要もあります。VRP により、運用コストとユーザの要望（タイム ウィンドウを守ることの重要性など）から構成される目的関数を最小限に抑えながら、これらの制約に従うソリューションが提供されます。
VRP 解析は、ネットワークに沿ったすべての訪問先と拠点との間の最短経路の起点 - 終点コスト マトリックスを生成することから開始します。このコスト マトリックスを使用して、最適ルートに訪問先を 1 つずつ挿入することで初期のソリューションを作成します。次に、ルートごとに訪問先の順序を再設定したり、あるルートから別のルートに訪問先を移動したり、およびルート間で訪問先を交換したりすることにより、初期のソリューションを改善します。このプロセスで使用されるヒューリスティクスは、タブー探索メタヒューリスティクスに基づくものであり、所有権で保護されていますが、Esri では適切な結果を迅速に得るために、長年にわたり社内で継続的に研究開発を行っています。
到達圏
到達圏解析もダイクストラのアルゴリズムに基づいて、ネットワークを移動します。この解析の目標は、指定されたネットワークの距離またはコスト カットオフの範囲内にある接続されたエッジ フィーチャのサブセットを返すことです。さらに、エッジが該当する一連のブレーク値によって分類されたラインを返すこともできます。到達圏解析では、ラインまたはラインを取り囲むポリゴン、あるいはその両方を生成することができます。
ポリゴンは、到達圏解析が通過するラインのジオメトリを不整三角形網モデル（TIN）データ構造に挿入することによって生成します。ラインに沿ったネットワークの距離は、TIN 内ではロケーションの高さとして使用されます。到達圏が通過しないロケーションは、非常に大きな高さの値で入力されます。この TIN でポリゴン生成ルーチンを使用することにより、指定されたブレーク値の範囲内にあるエリアを取り囲む領域を切り出すことができます。このポリゴン生成アルゴリズムには、単純化されたポリゴンまたは詳細なポリゴンを生成するため、また起こり得るさまざまな特殊な状況に対処するために、追加のロジックが用意されています。
ロケーション-アロケーション
ロケーション-アロケーションは、施設のロケーション問題の解析です。つまり、任意の候補施設を N、重み付けした需要点を M とし、施設 P のサブセットを選択するときに、各需要点 M から最も近い施設 P までの加重距離の合計を最小化します。これは、「N から P を選択」するタイプの組み合わせ問題であり、考えられるソリューションの数はきわめて膨大になります。すべての組み合わせを検証することで最適なソリューションを得ることはできません。たとえば、100 から 10 を選択するような小さな問題でも 17 兆を超える組み合わせがあります。さらに、ロケーション-アロケーション解析には、加重インピーダンスの最小化、カバーエリアの最大化、目標市場シェアの達成などのさまざまなロケーションに関する問題を解析するためのオプションがあります。ロケーション-アロケーション解析にはヒューリスティクスが使用されます。
ロケーション-アロケーション解析は、ネットワークに沿ったすべての施設と需要点のロケーション間の最短経路コストの起点 - 終点コスト マトリックスを生成することから開始します。次に、ヒルズマン編集というプロセスでコスト マトリックスの編集バージョンを構築します。この編集プロセスにより、同じ包括的な解析ヒューリスティクスでさまざまな問題タイプを処理できます。続いて 1 組のセミランダム化されたソリューションを生成し、頂点代替ヒューリスティクス（Teitz および Bart）を適用して、これらのソリューションを絞り込み、適切なソリューションのグループを作成します。その後はメタヒューリスティクスにより、この適切なソリューションのグループを統合し、より適切なソリューションを作成します。これ以上の改善が不可能になった時点で、見つかった最適なソリューションがメタヒューリスティクスによって返されます。編集されたマトリックス、セミランダム化された最初のソリューション、頂点代替ヒューリスティクス、およびメタヒューリスティクスの絞り込みを組み合わせることで、最適に近い結果が迅速に得られます。