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