自然災害問題（NetworkX）

自然災害問題

自然災害に関する問題の一つとして、道路ネットワーク上での交通渋滞の発生があります。

以下のようなシナリオを考えてみましょう：

🔹ある地域において、地震が発生し、複数の道路が通行不能になった。
🔹この地域には複数の車両が存在し、それぞれの車両が目的地に到達するために、どのルートを取るかを決定しなければならない。
🔹通行可能なルートは限られており、道路の通行状況は車両数に応じて変化する。
🔹車両が選択するルートによって、交通渋滞が発生する可能性がある。

このような問題を解くために、以下のような手順でNetworkXを使用することができます。

  1. 道路ネットワークのグラフを作成する。
    グラフのノードは交差点や道路の始点・終点とし、エッジは道路とし、エッジの重みはその道路の通行可能度合いとする。
  2. 車両の現在地と目的地をノードとして指定する。
  3. NetworkXの最短経路アルゴリズムを使用して、車両が最短時間で目的地に到達できる経路を計算する。
  4. 計算された最短経路を実際に走行した場合の交通渋滞の発生確率を評価する。

解法・ソースコード

交通渋滞の発生確率を評価する上記の例題をnetworkxを用いて実装します。

具体的には、以下の手順でグラフを作成し、最短経路を計算して、最短経路上での交通渋滞の発生確率を評価しています。

1. グラフを作成する
1
2
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (2, 4), (4, 5)])

まず、NetworkXを用いてグラフを作成します。ここでは、4つのノードと4つのエッジを持つグラフを作成しています。

2. エッジに重みを付ける
1
2
for (u, v) in G.edges():
    G[u][v]['weight'] = random.uniform(0.1, 1.0)

次に、各エッジにランダムな重みを付けます。

ここでは、0.1から1.0の範囲の乱数を用いて重みを設定しています。

3. ノード1からノード5への最短経路を計算する
1
2
path = nx.shortest_path(G, source=1, target=5, weight='weight')
print(f"Shortest path: {path}")

nx.shortest_path関数を用いて、ノード1からノード5までの最短経路を計算します。

weight引数には、エッジの重みを指定しています。

計算された最短経路をpath変数に格納し、print関数を用いて表示しています。

4. 計算された最短経路を実際に走行した場合の交通渋滞の発生確率を評価する
1
2
3
4
5
6
7
8
prob = 1.0
for i in range(len(path) - 1):
    u = path[i]
    v = path[i + 1]
    weight = G[u][v]['weight'] + random.uniform(-0.1, 0.1)
    G[u][v]['weight'] = max(weight - 0.1, 0)  # 通行可能度合いを減少させる
    prob *= weight  # 経路上のエッジの通行可能度合いの積を計算する
print(f"Probability of traffic congestion: {1 - prob:.3f}")

最後に、計算された最短経路上での交通渋滞の発生確率を評価します。

prob変数には、経路上のエッジの通行可能度合いの積を格納します。

forループで、最短経路上の各エッジについて、エッジの通行可能度合いをランダムに減少させ、prob変数にそのエッジの通行可能度合いを乗じます。

最後に、1 - probを計算することで、交通渋滞の発生確率を評価します。

なお、エッジの通行可能度合いの減少幅は、0から0.1の範囲の乱数を用いて決定しています。

以上の手順で、最短経路上での交通渋滞の発生確率を評価することができます。

[実行結果（例）]
Shortest path: [1, 2, 4, 5]
Probability of traffic congestion: 0.953

ノード1からノード5への最短経路は[1, 2, 4, 5]となりました。

そして、この経路上のエッジの通行可能度合いの積を計算することで、交通渋滞の発生確率を評価しました。

結果として、この経路上で交通渋滞が発生する確率は0.953となりました。