Pythonで利用者均衡配分【前編】|混雑すると、車はどの道を選ぶのか

空いているときに早い道へ、みんなが集まったらどうなるでしょうか。その道が混み始めれば、最初は遠回りに見えた道の方が早くなるかもしれません。

前回は、9ノードの交通網で距離最短と時間最短を求めました。今回は同じ道路網に車の台数と混雑を加え、「利用者均衡配分」まで計算します。最短経路へ交通量を載せるところから始め、Pythonで均衡を求め、道路別交通量と経路の所要時間を図で確かめます。

データはすべて教材用の仮想データです。Pythonの基本文法と、前回の「リンクの時間を足して最短経路を求める」という考え方を前提にしています。入力CSV・計算コード・図は第6章からダウンロードできます。

本記事は均衡配分の前編です。まず1組のODで均衡の意味をつかみ、後編(2026年11月21日9時公開予定・公開日時以降に閲覧できます)では同じ9ノードに複数ODを載せ、道路を共有する相互作用と収束計算へ進みます。

1.最短経路に全員が集まったら?

前回の交通網では、A→Iの時間最短は左側から下側へ進むA→D→G→H→Iで、合計6分でした。上側から右側へ進むA→B→C→F→Iは12分です。今回は、前回の時間を「道路が空いているときの時間」として引き継ぎます。

1人だけが移動するなら、6分の道を選べばよさそうです。ところが、AからIへ毎時1,200台が向かうとしたらどうでしょうか。全員が同じ道を選ぶと、混雑によって6分では通れなくなる可能性があります。

ここで解きたいのは、車が経路を選ぶことで道路が混み、混雑が経路の選び方を変えるという、双方向の関係です。

2.OD交通量と交通配分:経路に台数を載せる

出発地をOrigin、目的地をDestinationと呼び、その組み合わせごとの移動量をOD交通量と呼びます。今回は経路の変化に集中するため、ODは1組に絞ります。

出発地目的地OD交通量
AI1,200台/時(その他のODは0)

このOD交通量を道路網へ割り当て、各リンクを通る交通量を求めるのが交通配分です。たとえばA→D→G→H→Iに1,200台/時を載せると、A→D、D→G、G→H、H→Iの各リンクに、それぞれ1,200台/時が計上されます。

4リンクの値を足した4,800は、移動した車の台数ではありません。同じ車を通過リンクごとに数えているからです。ODの需要と、道路ごとの通過量を区別しておきましょう。

今回の道路条件

前回の9ノード・12本の双方向道路について、つながりと距離は変えず、時間に関する容量パラメーターを追加します。

前回と同じ3×3の9ノード。左・下は1.5分と600台毎時、上・右は3分と1000台毎時、中央は5分と1000台毎時。
ラベルは自由走行時間/片方向の容量パラメーター。AからIへ1,200台/時が移動する架空の設定です。
道路のまとまり各リンクの自由走行時間各方向の容量パラメーター
左・下:A–D、D–G、G–H、H–I1.5分600台/時
上・右:A–B、B–C、C–F、F–I3分1,000台/時
中央:B–E、D–E、E–F、E–H5分1,000台/時

前回は両方向を同じ重みで扱いました。今回は方向ごとに混み方を分けるため、1本の道路を往路と復路の2本の有向リンクとして登録します。12本の道路で計24有向リンクです。初期の時間と容量は往復で同じですが、交通量は別々に集計し、対向車の影響は考えません。

3.まず「全か無か配分」で、時間最短の道へ載せる

各ODの交通量を、その時点での最短経路にすべて載せる方法を全か無か配分(All-or-Nothing配分)と呼びます。最短経路が複数ある場合の扱いも必要ですが、混雑前の今回の時間最短は一意です。

まず、自由走行時間で最短経路を求めます。6分のA→D→G→H→Iが選ばれ、1,200台/時の全量がここへ載ります。上側・右側と中央の道路は0台/時です。

この配分を「時間がずっと6分のまま」として終えるのが、固定時間での配分です。今回はもう一歩進み、配分した交通量を使って、所要時間を更新してみます。

4.交通量が増えると時間が延びる:BPR関数

混雑による時間の変化を、次のBPR関数で表します。

所要時間 t(x) = t0 × [1 + 0.15 × (x / c)^4]
記号意味今回の単位
t0自由走行時間:交通量がほぼないときのリンク時間分
xその方向のリンク交通量台/時
c容量パラメーター:混雑の強まり方の基準台/時
t(x)交通量xのときのリンク時間分

0.15と4は、BPR関数の代表的な係数として使われる値です。今回は教材用に採用しています。道路ごとの実測値に合わせた推定ではありません。BPR関数と入力条件についてはFHWAの解説も参考になります。

左側・下側の各リンクは、t0=1.5分、c=600台/時です。1,200台/時が載ると、各リンクは次の時間になります。

1.5 × [1 + 0.15 × (1200 / 600)^4]
= 1.5 × (1 + 0.15 × 16)
= 5.1 分

経路全体:5.1 × 4 = 20.4 分

一方、上側・右側はまだ0台/時なので、合計12分のままです。空いているときは6分だった経路が、全員を載せたあとは20.4分。これでは、12分の道へ移る人が出てきそうです。

左側から下側の経路に1200台毎時が集中し、各リンクが5.1分となった図。別の上側右側の経路は12分。
自由走行時間で全か無か配分し、その交通量で時間を再計算した状態。矢印は進行方向、線の太さは交通量を表します。

「容量600台/時なのに、1,200台/時を載せてよいの?」

この式の容量は、交通量をそこで打ち切る制約ではありません。xがcを超えても計算は続き、時間が大きくなる仕組みです。cを超えた台数が実際に1時間で通り抜けられると保証するものではありません。

これは定常的な交通量と所要時間の関係を表すモデルです。入口で何台が待ち、渋滞がどこまで延びるかは計算しません。台数ごとの待ち行列や時間的な渋滞の変化は、別のモデルで扱う必要があります。

5.利用者均衡とは「自分だけ道を変えても早くならない」状態

20.4分の道から12分の道へ車が移ると、前者は空いて時間が短くなり、後者は混んで時間が長くなります。その結果、どの経路を使っても、自分だけ変更することで時間を短縮できない状態へ近づきます。

これが利用者均衡(User Equilibrium)です。ここでは、各利用者が経路の時間を把握し、自分の時間を短くしようとする、同質な利用者を考えます。また、交通量は連続量として扱い、1台の経路変更が道路全体の時間に与える影響は無視できるものとします。

同じODについて、条件は次の2つです。

  1. 使われている経路の所要時間は等しく、最短になっている。
  2. 使われていない経路も、それより短くない。

等しくなるのは、出発地から目的地まで足し合わせた経路全体の時間です。すべての道路区間の時間が等しくなる、という意味ではありません。また、全員の時間の合計を最小にした状態とも限りません。

今回の均衡は、2経路の時間の交点で見える

左側・下側の経路の交通量をqとすると、上側・右側は1,200−qです。各経路の4リンクは同じ条件なので、経路時間は次の式になります。

左・下の時間 = 6 × [1 + 0.15 × (q / 600)^4]
上・右の時間 = 12 × [1 + 0.15 × ((1200 − q) / 1000)^4]
左側下側の交通量を横軸に、二つの経路時間を比較。約964.3台毎時、約12.006分で交わる。
横軸は左側・下側の交通量。上側・右側の交通量は1,200からその値を引きます。交点で2経路の時間がそろいます。

交点では、左側・下側が約964.3台/時、上側・右側が約235.7台/時となり、時間はどちらも約12.006分です。ただし、2経路の時間が等しいだけでは、中央を通るもっと早い経路を見落としている可能性があります。次の計算では中央も含む道路網全体で探索し、第7章で全経路を照合します。

6.Pythonで、交通量と時間が整合する状態を求める

データとコードをダウンロード

利用者均衡配分の教材一式をダウンロード(ZIP・約0.38 MB)

ファイル内容
links.csv前回と同じ距離・つながり、自由走行時間、追加した容量
od.csvA→Iに1,200台/時のOD需要
assignment.py入力、全か無か配分、BPR関数、均衡計算
run_all.py図とCSVの生成、独立した計算法による検算
results/図4枚、リンク別結果、全経路表、収束記録
requirements.txt/README.txt/LICENSE実行環境、使い方、前提、利用条件

ZIPを展開し、ue-grid-kitフォルダーをターミナルで開きます。Python 3.11を用意したWindows PowerShellでは、次の順で実行できます。

python -m venv .venv
.venv\Scripts\python.exe -m pip install -r requirements.txt
.venv\Scripts\python.exe assignment.py
.venv\Scripts\python.exe run_all.py

macOS・Linuxではpythonをpython3、.venv\Scripts\python.exeを.venv/bin/pythonに置き換えます。検証環境はPython 3.11.5、NetworkX 3.1、NumPy 1.24.3、Matplotlib 3.7.2、SciPy 1.11.1です。ライブラリの初回取得以外に通信は不要です。

まず、全か無か配分をコードにする

計算の入口は、前回と同じ最短経路探索です。リンクの時間を使って最短経路を求め、その経路の各リンクにOD需要を加算します。実装の中心を抜き出すと、次のようになります。

# graphは24有向リンクを持つnx.DiGraph。
# 各リンクのcostには、その時点の所要時間を設定済み。
flow = {edge: 0.0 for edge in graph.edges()}
for origin, destination, demand in od:
    path = nx.dijkstra_path(graph, origin, destination, weight="cost")
    for u, v in zip(path, path[1:]):
        flow[u, v] += demand

上は考え方を示す抜粋です。配布版では計算を速く書けるよう、リンクに番号を付けてNumPy配列で交通量を持ちます。入力の読み込みも含めた実行可能なコードはassignment.pyに入っています。

全車を一度に移すと、行ったり来たりする

時間を更新するたびに全車を最短経路へ移すだけでは、左側が混む→全車が上側へ→上側が混む→全車が左側へ、という振動が起こり得ます。今回の条件でも、全車を上側・右側へ移すと、その経路は約15.732分、空いた左側・下側は6分となり、また逆転します。

そこで、現在の交通量xと、今の時間で全か無か配分した目標交通量yを混ぜて更新します。

次の交通量 = (1 − λ) × 現在の交通量x + λ × 目標交通量y
0 ≤ λ ≤ 1

今回使うのはFrank–Wolfe法です。混ぜる割合λを毎回決めて、交通量と所要時間が整合する方向へ進みます。利用者均衡を解く代表的な方法の一つで、AequilibraEの公式解説でも計算法と収束判定が整理されています。

  1. 自由走行時間で全か無か配分し、需要を満たす初期交通量xを作る。
  2. xから、BPR関数で各リンクの時間を計算する。
  3. その時間で最短経路を求め、目標交通量yを作る。
  4. 均衡に十分近ければ終了する。
  5. λを求め、xを更新して2へ戻る。

最初に0台から始めず、需要を満たす配分を用意するのがポイントです。xもyも同じOD需要を満たすので、0〜1の割合で混ぜても需要が保存されます。

λを求める処理は同梱のline_searchです。ここではリンク時間を0から交通量まで積分した量の合計(Beckmannポテンシャル)が最小になる更新幅を、二分法で求めています。これは利用者均衡に対応する目的関数で、全車の総所要時間そのものを最小にしているわけではありません。数式の導出は補足に回し、まずは全か無か配分と時間更新の組み合わせを押さえれば十分です。

計算を呼び出し、経路交通量を表示する

次のコードを教材フォルダー内の別の.pyファイルとして保存すると、結果を取り出せます。assignment.pyを直接実行しても同じ内容を表示します。

from assignment import solve

result = solve()
print("Relative gap:", result["history"][-1]["relative_gap"])
for (origin, destination, path), flow in result["path_flows"].items():
    if flow > 1e-5:
        time = sum(result["times"][result["index"][edge]]
                   for edge in zip(path, path[1:]))
        print(" → ".join(path), f"{flow:.3f} 台/時 / {time:.6f} 分")
A → D → G → H → I 964.337 台/時 / 12.005552 分
A → B → C → F → I 235.663 台/時 / 12.005552 分

この例は対称性が強く、使われる2経路がリンクを共有していないため、適切なλを求めると1回の交通量更新で収束します。一般の道路網が1回で解けるという意味ではありません。反復計算は、実際の車が何日かかけて経路を学ぶ様子を再現したものでもなく、均衡を数値的に求める手順です。

7.図と数値で、利用者均衡になったかを確かめる

利用者均衡の配分結果。左側下側約964.3台毎時、上側右側約235.7台毎時、中央は0台毎時。
線の太さは方向別交通量。時間は表示桁で丸めています。経路合計は各リンクの丸め前の値を足し合わせます。
状態左・下の交通量上・右の交通量左・下の時間上・右の時間
自由走行時間で全か無か配分し、時間を更新1,200台/時0台/時20.400分12.000分
利用者均衡約964.337台/時約235.663台/時約12.005552分約12.005552分

交通量は半分ずつではありません。同じ時間になるように分かれた結果です。今回は各経路内の4リンクを対称に設定したので、使われるリンクの時間もたまたま近い値になっていますが、それは均衡の一般条件ではありません。

チェック1:台数が保存されているか

経路交通量の合計は964.337…+235.663…=1,200台/時です。Aから出る量、Iへ入る量も1,200台/時で、途中の各ノードでは流入量と流出量が一致します。24有向リンクの逆方向はすべて0台/時です。小数は交通量を連続量として近似した結果です。

チェック2:使われていない経路に、もっと早い道はないか

同じノードを繰り返さないA→Iの経路を、中央経由も含めて全12本列挙し、最終的なリンク時間で合計しています。使われる2経路は約12.005552分で一致し、使われていない経路はそれより短くないことを確認しました。重みが正なので、同じノードへ戻る回り道でさらに早くなることはありません。

経路ごとの値はresults/all-paths.csvで確認できます。全経路列挙は、小さな教材を検算するための処理です。均衡計算自体は最短経路探索を使っており、大規模道路網ですべての経路を列挙することを勧めるものではありません。

チェック3:Relative gapは十分小さいか

収束判定にはRelative gapを使います。現在の時間で計った「現在の配分の総コスト」と「各ODがその時点の最短経路を使った場合の総コスト」の差を、前者で割った指標です。比較する両方に、同じ現在のリンク時間を使います。

Relative gap = [Σ xₐ tₐ(xₐ) − Σ yₐ tₐ(xₐ)] / Σ xₐ tₐ(xₐ)

xは現在の交通量、yは現在の時間での全か無か配分です。yを実際に載せ直した後の時間で比較するのではありません。0に近いほど均衡条件に近くなります。ただし、平均のずれを表す指標なので、個々の経路の誤差が同じ割合以内に収まる保証ではありません。

交通量の更新回数Relative gap
0回:初期配分約0.411765
1回:均衡配分約3.8×10⁻¹⁶

教材の目標値は10⁻⁸、最大更新回数は20,000回です。今回は目標値を満たしました。浮動小数点計算なので、数学的に厳密な0との一致を要求していません。最大回数に達しても目標を満たさない場合は、均衡が得られたと扱わずエラーで停止します。

さらに、経路交通量を直接最適化する別の方法(SLSQP)と、2経路の時間が等しくなる点を探す方法でも照合しました。SLSQPとのリンク交通量の差は最大約0.00012台/時で、教材の結果と整合しています。

この計算で分かること・分からないこと

分かるのは、与えたOD需要と道路条件のもとで、時間だけを基準に経路を選ぶ利用者が均衡するときの交通量と所要時間です。出発時刻の変化、信号や交差点の詳細、渋滞列の延伸、情報の不足や好みの違いは含めていません。また、この仮想データの結果を現実の道路の予測値として読むことはできません。

利用者均衡は、個人が自分の時間を短縮できない状態です。全員の総所要時間を最小にする「システム最適」との違いは、後の比較記事で扱います。

次は、違う目的地へ向かう車が、同じ道路を使ったら?

今回の道路網は9ノードでしたが、起終点はA→Iの1組に絞り、最後は道路を共有しない2経路の時間の交点として均衡を理解しました。「この程度なら、2本の時間を比べればよいのでは」と感じた方もいるかもしれません。

ところが現実の道路には、違う出発地・目的地を持つ車が重なります。A→Iの車が使う道路に、A→HやD→Iの車も入ってきたらどうでしょうか。自分たちの台数が変わらなくても、その道路は混み、選ぶ経路も変わります。あるODの経路変更が別のODの時間を変え、その変更が再び自分に返ってきます。

各ODを別々に解いて結果を足すだけでは、合計したあとの混雑と経路選択が食い違う。そこで、道路網全体の交通量と時間が、すべてのODの選択と整合する状態を求める必要があります。均衡配分の役割は、こうした道路の共有を考えると、よりはっきり見えてきます。

後編では、道路条件を変えずにA→HとD→Iの移動を追加します。前編で使わなかった中央の道路にも交通が流れる理由と、最短経路探索・交通量調整を繰り返して均衡へ近づく過程を、図とPythonで追います。

なお、今回の交点も数値計算で求めています。9ノードになると数式で表せなくなるのではなく、複数ODが共有する道路の混雑を一緒に扱うため、反復計算の意味が見えやすくなる、という違いです。

後編:複数ODが道路を共有すると何が起きる?(2026年11月21日9時公開予定・公開日時以降に閲覧できます)

参考資料

コメント

タイトルとURLをコピーしました