道路ネットワークデータの扱い方¶

道路ネットワークは、交差点をノード、道路をエッジとするグラフとして扱う。本研究室で道路ネットワーク上の最適化問題(フロー捕捉型施設配置問題FCLM、フロー補給型施設配置問題FRLM、配送計画問題VRPなど)を扱うときは、この形式のグラフを前提とする。

実際の研究では市販の道路ネットワークデータを使うが、これは購入データであり著作権の制約から公開できない。そこで教材では、実データと同じファイル形式のダミーデータを生成して使う。FCLM、FRLM、VRPの各教材の数値例は、すべて本資料で生成するダミー道路網 nodes_ud.csv と links_ud.csv を前提としている。

1. データ形式¶

道路ネットワークは2つのCSVファイル(ヘッダ行なし)で表す。

nodes_ud.csv はノード(交差点)の一覧であり、各行の構成は次のとおりである。

ノードID, 経度, 緯度

links_ud.csv はエッジ(ノードをつなぐ道路)の一覧であり、各行の構成は次のとおりである。

始点ノードID, 終点ノードID, 道路長 [m], 始点の経度, 始点の緯度, 終点の経度, 終点の緯度, 道路種別番号

エッジは無向であり、各行が1本の道路区間を表す。道路種別番号は実データに含まれる属性で、本教材では使わない。グラフ理論の基礎については「グラフ理論入門」(optimization/graph/graph.ipynb)を参照してほしい。

2. ダミーデータの生成¶

6列5行の格子状ネットワーク(30ノード)を基本とし、一部の道を取り除き、斜めの道を加え、ノード位置に乱数で揺らぎを与えて、実在しない架空の道路網を作る。座標は経度と緯度の形式で持たせ、道路長は座標差をメートルに換算したユークリッド距離とする。乱数のシードを固定しているため、何度実行しても同じデータが生成される。

In [1]:
import numpy as np

rng = np.random.default_rng(7)

NC, NR = 6, 5                  # 列数と行数
lon0, lat0 = 140.000, 35.700   # 基準座標(架空)
dlon, dlat = 0.004, 0.003      # 格子間隔
M_LON = 111320 * np.cos(np.deg2rad(35.706))  # 経度1度あたりのメートル
M_LAT = 110950                               # 緯度1度あたりのメートル

# ノード座標(格子+揺らぎ)
nodes = {}
nid = 0
for r in range(NR):
    for c in range(NC):
        nid += 1
        lon = lon0 + c * dlon + rng.uniform(-0.0008, 0.0008)
        lat = lat0 + r * dlat + rng.uniform(-0.0006, 0.0006)
        nodes[nid] = (round(lon, 6), round(lat, 6))

def idx(r, c):
    """格子位置 (r, c) のノードID"""
    return r * NC + c + 1

# 格子の隣接エッジ
edges = set()
for r in range(NR):
    for c in range(NC):
        if c + 1 < NC:
            edges.add((idx(r, c), idx(r, c + 1)))
        if r + 1 < NR:
            edges.add((idx(r, c), idx(r + 1, c)))

# 一部の道を削って格子らしさを崩す(連結性は保たれる)
for e in [(idx(1, 2), idx(1, 3)), (idx(3, 1), idx(3, 2)),
          (idx(0, 3), idx(1, 3)), (idx(2, 4), idx(3, 4)),
          (idx(3, 3), idx(4, 3)), (idx(1, 0), idx(2, 0))]:
    edges.discard(e)

# 斜めの道を追加
edges.add((idx(0, 2), idx(1, 3)))
edges.add((idx(2, 3), idx(3, 4)))

def length(u, v):
    (lo1, la1), (lo2, la2) = nodes[u], nodes[v]
    return round(np.hypot((lo1 - lo2) * M_LON, (la1 - la2) * M_LAT), 1)

# CSV の書き出し
with open('nodes_ud.csv', 'w') as f:
    for i, (lon, lat) in nodes.items():
        f.write(f'{i},{lon:.6f},{lat:.6f}\n')

with open('links_ud.csv', 'w') as f:
    for u, v in sorted(edges):
        (lo1, la1), (lo2, la2) = nodes[u], nodes[v]
        f.write(f'{u},{v},{length(u, v)},{lo1:.6f},{la1:.6f},{lo2:.6f},{la2:.6f},8\n')

print(f'ノード数: {len(nodes)}, エッジ数: {len(edges)}')

ノード数: 30, エッジ数: 45

3. 読み込みとグラフの構築¶

生成したCSVを読み込み、networkxのグラフを構築する。ヘッダ行がない数値だけのCSVなので np.loadtxt で読める。エッジの重みには道路長を使う。描画用のノード位置(pos)は、リンクファイルに含まれる始点と終点の座標から組み立てる。この手順は実データを扱うときもまったく同じである。

In [2]:
import networkx as nx
from matplotlib import pyplot as plt

edgs = np.loadtxt('links_ud.csv', delimiter=',')
nds = np.loadtxt('nodes_ud.csv', delimiter=',')

# グラフの構築(エッジの重み = 道路長)
G = nx.Graph()
G.add_weighted_edges_from([(int(e[0]), int(e[1]), e[2]) for e in edgs])

# ノード位置をエッジの座標データから組み立てる
pos = {}
for e in edgs:
    pos[int(e[0])] = [e[3], e[4]]
    pos[int(e[1])] = [e[5], e[6]]

print('ノード数:', G.number_of_nodes())
print('エッジ数:', G.number_of_edges())
print('連結か:', nx.is_connected(G))

plt.figure(figsize=(8, 6))
nx.draw_networkx_edges(G, pos)
nx.draw_networkx_nodes(G, pos, node_size=220, node_color='white', edgecolors='black')
nx.draw_networkx_labels(G, pos, font_size=8)
plt.axis('equal')
plt.axis('off')
plt.tight_layout()
plt.show()

ノード数: 30
エッジ数: 45
連結か: True
No description has been provided for this image

4. 最短経路の計算¶

道路ネットワーク上の最適化では、2地点間の移動は最短経路に沿うと仮定することが多い。networkxでは nx.shortest_path で最短経路(通過ノードの列)が、nx.path_weight でその長さが得られる。内部ではダイクストラ法(Dijkstra's algorithm)が使われている。weight='weight' を忘れると道路長ではなくエッジ本数で最短が判定されてしまうため注意すること。

In [3]:
o, d = 1, 30
path = nx.shortest_path(G, o, d, weight='weight')
L = nx.path_weight(G, path, weight='weight')
print(f'ノード{o} からノード{d} への最短経路: {path}')
print(f'経路長: {L:.1f} [m]')

# 最短経路を赤で描画
pe = list(zip(path[:-1], path[1:]))
plt.figure(figsize=(8, 6))
nx.draw_networkx_edges(G, pos, edge_color='lightgray')
nx.draw_networkx_edges(G, pos, edgelist=pe, edge_color='red', width=2.5)
nx.draw_networkx_nodes(G, pos, node_size=220, node_color='white', edgecolors='black')
nx.draw_networkx_labels(G, pos, font_size=8)
plt.axis('equal')
plt.axis('off')
plt.tight_layout()
plt.show()

ノード1 からノード30 への最短経路: [1, 2, 3, 10, 16, 23, 24, 30]
経路長: 2668.9 [m]
No description has been provided for this image

5. 経路データの生成¶

道路ネットワーク上の最適化(FCLM、FRLM)では、ネットワーク上を移動する交通流を、経路 $j$ が通過するノードの列 $N_j$ と、経路 $j$ の交通量 $f_j$ で表す。出発地と目的地のペアを与え、最短経路を計算して経路データを作り、N.csv と f.csv に保存する。N.csv は行 $j$ が経路 $j$ の通過ノード列(ヘッダなし、行ごとに長さが異なる)、f.csv は行 $j$ が経路 $j$ の交通量である。実データを使う研究でも、経路データはこの形式で保存している。

In [4]:
od = [[1, 6], [25, 30], [1, 25], [6, 30], [3, 27], [13, 18], [11, 24]]  # 出発地と目的地
f = [120, 100, 90, 80, 150, 60, 70]                                     # 経路ごとの交通量

N = [nx.shortest_path(G, o, d, weight='weight') for o, d in od]

with open('N.csv', 'w') as fp:
    for Nj in N:
        fp.write(','.join(map(str, Nj)) + '\n')

with open('f.csv', 'w') as fp:
    for fj in f:
        fp.write(f'{fj}\n')

for j, (Nj, fj) in enumerate(zip(N, f), 1):
    print(f'経路{j}: f_{j} = {fj}, N_{j} = {Nj}')

経路1: f_1 = 120, N_1 = [1, 2, 3, 4, 5, 6]
経路2: f_2 = 100, N_2 = [25, 26, 27, 28, 29, 30]
経路3: f_3 = 90, N_3 = [1, 7, 8, 14, 20, 26, 25]
経路4: f_4 = 80, N_4 = [6, 12, 18, 24, 30]
経路5: f_5 = 150, N_5 = [3, 9, 15, 21, 27]
経路6: f_6 = 60, N_6 = [13, 14, 15, 16, 17, 18]
経路7: f_7 = 70, N_7 = [11, 12, 18, 24]

6. 各教材との関係¶

FCLM教材とFRLM教材では、本資料で生成した道路網(links_ud.csv、nodes_ud.csv)と経路データ(N.csv、f.csv)をそのまま読み込んで施設配置を最適化する。VRP教材では、このネットワーク上の最短経路距離から距離行列を作って配送ルートを構成する。いずれの教材でも、本資料の手順(np.loadtxtで読み、add_weighted_edges_fromでグラフを作り、shortest_pathで経路を求める)をそのまま使う。