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