交通ネットワーク分析

交通ネットワーク（transportation network ）は、地理的な空間におけるネットワークまたはグラフであり、移動や流れを許可または制限するインフラストラクチャを表します。 ^{[1]例としては、}道路網、鉄道、航空路、パイプライン、水道、送電線などがありますが、これらに限定されません。これらのネットワークのデジタル表現とその分析方法は、空間分析、地理情報システム、公共事業、輸送工学の中核をなしています。ネットワーク分析は、グラフ理論の理論とアルゴリズムを応用したもので、近接分析の一種です。

歴史

グラフ理論の地理的現象への応用可能性は早くから認識されていた。グラフ理論家が取り組んだ初期の問題や理論の多くは、地理的な状況に触発されたもので、例えばケーニヒスベルクの七つの橋問題は、 1736年にレオンハルト・オイラーによって解決され、グラフ理論の元々の基礎の一つとなった。 ^[2]

1970年代には、地理情報システムの初期の開発者によってこの関係が再確立され、ポリゴンの位相データ構造（ここでは関係ありません）や交通ネットワークの分析にこの関係が採用されました。Tinkler（1977）などの初期の研究では、線形データの量が少なかったことと、多くのアルゴリズムの計算が複雑だったため、主に単純な概略ネットワークに焦点を当てていました。^[3] GISソフトウェアでのネットワーク分析アルゴリズムの完全な実装は1990年代まで登場しませんでしたが、^[4]^[5]現在ではかなり高度なツールが一般的に利用可能です。

ネットワークデータ

ネットワーク分析には、ネットワークの要素とその特性を表す詳細なデータが必要です。^[6]ネットワークデータセットの中核は、移動経路を表すポリラインのベクターレイヤーです。これは、正確な地理的ルートまたは概略図（エッジ）です。さらに、ライン間の接続を表すネットワークトポロジに関する情報も必要であり、これにより、1つのラインから別のラインへの輸送をモデル化できます。通常、これらの接続ポイント、つまりノードは、追加のデータセットとして含まれています。^[7]

エッジとノードの両方に、動きや流れに関連するプロパティが割り当てられます。

容量、道路の車線数、通信帯域幅、パイプの直径など、許可される流量の制限の測定値。
インピーダンス、速度制限や交差点での禁止方向など、流れや流れの速度に対する抵抗の測定値
距離の摩擦の原理に従い、エッジに沿った、またはノードを介した個々の移動を通じて蓄積されるコスト。通常は経過時間です。たとえば、街路網のノードでは、特定の左折または右折を行うために異なる時間がかかる場合があります。このようなコストは、交通量の日周期に応じた都市の街路に沿った移動時間のパターンなど、時間の経過とともに変化する可能性があります。
フロー量、実際に起こっている動きの測定値。これは、交通量カウンターなどのセンサーネットワークを使用して収集された特定の時間エンコードされた測定値、または年間平均日次交通量(AADT)などの一定期間にわたる一般的な傾向である場合があります。

分析方法

ネットワークフローに関連する問題やタスクを解決するために、さまざまな方法、アルゴリズム、技術が開発されてきました。これらの中には、すべてのタイプの輸送ネットワークに共通するものもあれば、特定のアプリケーションドメインに固有のものもあります。^{[8]これらのアルゴリズムの多くは、}GRASS GISやEsri ArcGISのNetwork Analyst拡張機能など、商用およびオープンソースのGISソフトウェアに実装されています。

最適なルーティング

ネットワークにおける最も単純かつ一般的なタスクの 1 つは、ネットワーク上の 2 つのポイントを結ぶ最適なルートを見つけることです。最適とは、距離、エネルギー消費、時間などの何らかのコストを最小化することと定義されます。^{[9]一般的な例としては、}Google マップなどのほぼすべての Web ストリートマッピングアプリケーションの機能である、街路ネットワークでの方向検索が挙げられます。ほとんどの GIS およびマッピングソフトウェアに実装されているこのタスクを解決する最も一般的な方法は、ダイクストラのアルゴリズムです。^[10]

基本的なポイントツーポイントルーティングに加えて、複合ルーティング問題もよく見られます。巡回セールスマン問題では、複数の目的地に到達するための最適な（距離/コストが最小の）順序とルートを求めます。これはNP困難な問題ですが、解の集合が小さいため、制約のない空間よりもネットワーク空間で解く方がいくらか簡単です。^[11]車両ルーティング問題はこれを一般化したものなので、目的地に到達するための複数の同時ルートが可能です。経路検査または「中国の郵便配達」問題では、すべてのエッジを通過する最適な（距離/コストが最小の）経路を求めます。一般的な応用は、ゴミ収集車のルーティングです。これは、多項式時間アルゴリズムで解く方がはるかに簡単な問題であることがわかりました。

位置分析

このクラスの問題は、ネットワークに沿った1つ以上の施設の最適な場所を見つけることを目的とします。最適な場所とは、ネットワーク内の別のポイントセットへの（または別のポイントセットからの）総移動コストまたは平均移動コストを最小化することと定義されます。一般的な例としては、一連の小売店への配送コストを最小化する倉庫の場所の決定、または潜在的顧客の住居からの移動時間を最小化する小売店の場所の決定などがあります。制約のない（直交座標）空間では、これはNP困難な問題であり、ロイドのアルゴリズムなどのヒューリスティックなソリューションが必要ですが、ネットワーク空間では決定論的に解決できます。^[12]

特定のアプリケーションでは、既存または競合する施設の場所、施設の容量、最大コストなど、問題にさらなる制約が加わることがよくあります。

サービスエリア

ネットワークサービスエリアは、制約のない空間におけるバッファに似ており、指定された距離またはその他の累積コスト未満でポイント（通常はサービス施設）から到達できるエリアを描写したものです。^[13]たとえば、消防署の優先サービスエリアは、短時間で到達できる道路セグメントのセットになります。施設が複数ある場合、各エッジは最も近い施設に割り当てられ、ボロノイ図に似た結果が生成されます。^[14]

障害分析

公共ユーティリティネットワークにおける一般的なアプリケーションは、ネットワーク内の障害または破損の可能性のある場所 (多くの場合、埋もれているか、直接観察することが困難) を、顧客からの苦情などの簡単に見つけられるレポートから推測して特定することです。

交通工学

交通は統計物理学的手法を用いて広範囲に研究されてきた。^[15]^[16]^[17]

垂直分析

鉄道システムを可能な限り効率的にするためには、複雑性/垂直分析も実施する必要があります。この分析は、システムの持続可能性を確保する上で重要な、将来および既存のシステムの分析に役立ちます (Bednar、2022、75～76 ページ)。垂直分析は、システムの運用活動 (日常業務)、問題の予防、管理活動、活動の開発、活動の調整を把握することから構成されます。^[18]

参照

参考文献

^ Barthelemy, Marc (2010). 「空間ネットワーク」. Physics Reports . 499 (1–3): 1–101. arXiv : 1010.0302 . Bibcode :2011PhR...499....1B. doi :10.1016/j.physrep.2010.11.002. S2CID 4627021.
^ オイラー、レオンハルト (1736)。「適切な幾何学的な問題の解決策」。コメント。アカド。科学。 U. ペトロップ8、128–40。
^ Tinkler, KJ (1977). 「地理学におけるグラフ理論的手法入門」(PDF) . CATMOG (14).
^ Ahuja RK、Magnanti TL、Orlin JB (1993)ネットワークフロー: 理論、アルゴリズム、アプリケーション。Prentice Hall、Englewood Cliffs、NJ、米国
^ Daskin MS (1995)ネットワークと離散的位置 — モデル、アルゴリズム、アプリケーションWiley、NJ、米国
^ 「ネットワークデータセットとは?」。ArcGIS Pro ドキュメント。Esri。
^ 「ネットワーク要素」。ArcGIS Pro ドキュメント。Esri。2021年3 月 17 日閲覧。
^ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). 「7.2.1 概要 - ネットワークと位置分析」。地理空間分析: 原則、手法、ソフトウェアツールの包括的なガイド(第 6 改訂版)。
^ Worboys, Michael; Duckham, Matt (2004). 「5.7 ネットワーク表現とアルゴリズム」. GIS: コンピューティングの視点(第 2 版). CRC Press. pp. 211–218.
^ ダイクストラ、EW (1959)。「グラフに関連した 2 つの問題に関するメモ」(PDF)。数学数学。1 : 269–271。土井：10.1007/BF01386390。S2CID 123284777。
^ 「v.net.salesman コマンド」。GRASS GIS マニュアル。OSGEO。2021年3 月 17 日閲覧。
^ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). 「7.4.2 より大きな p 中央値と p 中心の問題」。地理空間分析: 原則、手法、ソフトウェアツールの包括的なガイド(第 6 改訂版)。
^ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). 「7.4.3 サービスエリア」。地理空間分析：原則、手法、ソフトウェアツールの包括的なガイド（第6改訂版）。
^ 「v.net.alloc コマンド」。GRASS GIS ドキュメント。OSGEO。2021年3 月 17 日閲覧。
^ Helbing, D (2001). 「交通と関連する自己駆動型多粒子システム」.現代物理学レビュー. 73 (4): 1067–1141. arXiv : cond-mat/0012229 . Bibcode :2001RvMP...73.1067H. doi :10.1103/RevModPhys.73.1067. S2CID 119330488.
^ S.、ケルナー、ボリス（2004）。交通の物理学：経験的な高速道路パターンの特徴、エンジニアリングアプリケーション、および理論。ベルリン、ハイデルベルク：シュプリンガーベルリンハイデルベルク。ISBN 9783540409861. OCLC 840291446.{{cite book}}: CS1 maint: multiple names: authors list (link)
^ Wolf , DE; Schreckenberg, M; Bachem, A ( 1996年 6 月)。トラフィックと粒状フロー。WORLD SCIENTIFIC。pp. 1–394。doi :10.1142/9789814531276。ISBN 9789810226350。
^ ベドナー、2022年、75-76ページ

[Bart-1] Barthelemy, Marc (2010). 「空間ネットワーク」. Physics Reports . 499 (1–3): 1–101. arXiv : 1010.0302 . Bibcode :2011PhR...499....1B. doi :10.1016/j.physrep.2010.11.002. S2CID 4627021.

[2] オイラー、レオンハルト (1736)。「適切な幾何学的な問題の解決策」。コメント。アカド。科学。 U. ペトロップ8、128–40。

[3] Tinkler, KJ (1977). 「地理学におけるグラフ理論的手法入門」(PDF) . CATMOG (14).

[4] Ahuja RK、Magnanti TL、Orlin JB (1993)ネットワークフロー: 理論、アルゴリズム、アプリケーション。Prentice Hall、Englewood Cliffs、NJ、米国

[5] Daskin MS (1995)ネットワークと離散的位置 — モデル、アルゴリズム、アプリケーションWiley、NJ、米国

[6] 「ネットワークデータセットとは?」。ArcGIS Pro ドキュメント。Esri。

[7] 「ネットワーク要素」。ArcGIS Pro ドキュメント。Esri。2021年3 月 17 日閲覧。

[8] Smith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). 「7.2.1 概要 - ネットワークと位置分析」。地理空間分析: 原則、手法、ソフトウェアツールの包括的なガイド(第 6 改訂版)。

[Worboys-9] Worboys, Michael; Duckham, Matt (2004). 「5.7 ネットワーク表現とアルゴリズム」. GIS: コンピューティングの視点(第 2 版). CRC Press. pp. 211–218.

[Dijkstra1959-10] ダイクストラ、EW (1959)。「グラフに関連した 2 つの問題に関するメモ」(PDF)。数学数学。1 : 269–271。土井：10.1007/BF01386390。S2CID 123284777。

[11] 「v.net.salesman コマンド」。GRASS GIS マニュアル。OSGEO。2021年3 月 17 日閲覧。

[12] Smith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). 「7.4.2 より大きな p 中央値と p 中心の問題」。地理空間分析: 原則、手法、ソフトウェアツールの包括的なガイド(第 6 改訂版)。

[13] Smith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). 「7.4.3 サービスエリア」。地理空間分析：原則、手法、ソフトウェアツールの包括的なガイド（第6改訂版）。

[14] 「v.net.alloc コマンド」。GRASS GIS ドキュメント。OSGEO。2021年3 月 17 日閲覧。

[15] Helbing, D (2001). 「交通と関連する自己駆動型多粒子システム」.現代物理学レビュー. 73 (4): 1067–1141. arXiv : cond-mat/0012229 . Bibcode :2001RvMP...73.1067H. doi :10.1103/RevModPhys.73.1067. S2CID 119330488.

[16] S.、ケルナー、ボリス（2004）。交通の物理学：経験的な高速道路パターンの特徴、エンジニアリングアプリケーション、および理論。ベルリン、ハイデルベルク：シュプリンガーベルリンハイデルベルク。ISBN 9783540409861. OCLC 840291446.{{cite book}}: CS1 maint: multiple names: authors list (link)

[17] ^ Wolf , DE; Schreckenberg, M; Bachem, A ( 1996年 6 月)。トラフィックと粒状フロー。WORLD SCIENTIFIC。pp. 1–394。doi :10.1142/9789814531276。ISBN 9789810226350。

[18] ベドナー、2022年、75-76ページ