ウォードロップの原理

【うぉーどろっぷのげんり (Wardrop's two extremal principles)】

概要

出発地 (origin) と目的地 (destination) の間に代替となる経路が複数ある場合に, 利用者がどのような規準で経路を選択するのかについて, 交通流全体の状況を用いて記述したもの. ウォードロップは次の2つの規準を提案した.

(1) OD間で実際に使われている経路の旅行時間はすべて等しく, それは使われていない経路を単一の利用者が旅行する場合の旅行時間よりも短い.

(2) 平均旅行時間が最小である.

出発地 (origin) と目的地 (destination) の間に代替となる経路が複数ある場合に, 利用者がどのような規準で経路を選択するのかについて, 交通流全体の状況を用いて記述したもの. ウォードロップは次の2つの規準を提案した.

(1) OD間で実際に使われている経路の旅行時間はすべて等しく, それは使われていない経路を単一の利用者が旅行する場合の旅行時間よりも短い.

(2) 平均旅行時間が最小である.

詳説

　出発地(Origin)と目的地(Destination)の間に代替となる経路が複数ある場合に, 利用者がどのような規準で経路を選択するのかについて, 交通流全体の状況を用いて記述したものである.

　都市内の道路網の交通を例に考えよう. 様々なODを持つ車が, 可能性としては非常に多数ある経路の中からそれぞれの経路を選択し, 全体として秩序を持って通行している. それらは, もっとも距離の短い経路に集中している訳ではないし, ランダムに選択しているわけでもなく, 距離, 混雑度や料金などを判断基準として選択を行っている. これらを全体としてみたとき, 物理学の法則のような厳密性はないものの, 合理的な規準に従って経路選択が行われていると期待したい. もし, そのような原理を導くことができれば, 交通計画の際に総OD交通量データを道路網に配分することができ, 計画案を検討することができる.

　WardropはOD交通をOD間の各経路に配分する次のふたつの規準を提案した.

　1.OD間で実際に使われている経路の旅行時間はすべて等しい. そして, それは使われていない経路を単一の利用者が旅行する場合の旅行時間よりも短い.

　2.平均旅行時間が最小である.

前者は利用者最適化配分や利用者均衡配分, 後者はシステム最適化配分と呼ばれる.

　単一のODの場合に上のふたつの原理を定式化しよう. 変数は, 各枝の流れではなく各経路に沿った流れとする. 枝の集合を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle E\, } , OD間の経路の集合を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M\, } , 経路 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j\in M\, } の流れを 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h_j\ge 0\, } とする. 経路 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j\, } を構成する枝を表すのに

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a_{ij}=1\, } : 枝 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } が経路 $j\,$ に含まれるとき,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a_{ij}=0 \, }  : それ以外

とする. 枝 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } の流れ 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_i\, } は, 枝 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } を通る経路の流量の和として

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_i = \sum_{j\in M} a_{ij}h_{j} , \qquad i \in E \, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (1) \,}

と表すことができる. 枝 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } を通過するのにかかる旅行時間(費用)を枝 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i\, } の流れ 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_i\, } の関数として 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c_i(f_i)\, } とする. すると, 経路 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j\, } の旅行時間は

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle C_j = \sum_{i\in E} a_{ij}c_i(f_i)\, }

である. ただし 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_i\, } は式(1)で与えられるとする. 総OD交通量を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } とすると

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d = \sum_{j\in M} h_{j} \, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (2) \,}

となる. 変数を経路の流量としたので, 各頂点における流れの連続の条件は不要である.

　枝を通過するのにかかる旅行時間(費用)がその枝を通過する流れによらない場合は, どちらの配分によってもOD間の最短経路だけが使われるという自明な配分となる. また, 流れの容量制約があり, その中では旅行時間が一定であるという場合は, 旅行時間は流れによると考える.

　利用者最適化配分は次のように定式化できる. 経路の番号を旅行時間の短い方から順に 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 2\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \ldots\, } , 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle |M|\, } としたとき, 利用者最適化配分 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h\, } は

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle C_1(h) = C_2(h)= \ldots = C_k(h) \le C_{k+1}(h) \le \ldots \le C_{|M|} , \, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (3) \,}

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h_1 > 0, h_2 > 0, \ldots , h_k > 0, h_{k+1}=0, \ldots, h_{|M|}=0 \, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (4) \,}

を満たす.

　システム最適化配分は次のような最小化問題として定式化することができる. すなわち, 総費用が

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \sum_{j\in M}h_jC_j(h)= \sum_{j\in M}h_j\sum_{i\in E}a_{ij}c_i(f_i) = \sum_{i\in E}f_ic_i(f_i)\, }

と表されることから,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \min_{h} \sum_i f_ic_i(f_i) \, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{s. t.} \;\;\;f_i = \sum_{j\in M}a_{ij}h_j , \qquad i\in E, \, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \;\;\;\;\;\sum_{j\in M}h_j = d, \, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \;\;\;\;\;h_j \ge 0, \qquad j\in M \, }

である.

　各枝における総費用 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_ic_i(f_i)\, } が強凸で増加関数であると仮定して, この問題と双対問題との相補条件が利用者最適配分(3), (4)と同じ形となることを示そう. (1)に関する双対変数を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mu_i\, } , (2)に関する双対変数を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lambda\, } とすると, 双対問題は

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \max_{\mu ,\lambda} \lambda d - \sum_{i\in E} \phi_i(\mu_i) \, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mbox{s. t.}}\;\;\;\sum_{i\in E} \mu_ia_{ij} - \lambda \ge 0, \qquad j\in M, \, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \;\;\;\;\;\phi_i(\mu) = \min_{f\ge 0}\{ \mu f - fc(f) \}}

となり, 相補条件は

もし 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_i>0\, } ならば 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \partial (f_ic_i(f_i))/\partial f_i = \mu_i, \qquad i\in E,\, }

もし 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \partial (f_ic_i(f_i))/\partial f_i|_{f=0} > \mu_i\, } ならば 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_i=0, \qquad i\in E,\, }

もし 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h_j>0\, } ならば 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \displaystyle\sum_{i\in E}\mu_ia_{ij} = \lambda, \qquad j\in M,\, }

もし 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \displaystyle\sum_{i\in E} \mu_ia_{ij} > 0\, } ならば 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h_j=0, \qquad j\in M\, }

となる. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mu_i\, } は各枝の限界費用 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \partial (f_ic_i(f_i))/\partial f_i\, } であり, 使われている経路に対しては, 経路を構成する枝の限界費用の和(経路の限界費用)は等しく, 使われていない経路の限界費用よりも小さいことがわかる. この記述は限界費用を枝の費用に置き換えると利用者最適化配分の記述そのものである. そこで, システム最適化配分問題で, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c(f)\, } の代わりに

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \frac{1}{f}\int_0^fc(\tau){\mbox{d}}\tau\, }

を用いると, 利用者最適化配分を最小化問題として定式化することができる.

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{min.} \sum_{i} \int_0^f c_i(\tau){\mbox{d}}\tau \, } 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mbox{s. t.}}\;\;\;\sum_{j\in M} h_j = d, \, }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \;\;\;\;\;h_j \ge 0, \qquad j\in M. \, }

利用者最適化配分によると, 新たに道路を作るとかえってOD間の移動時間が長くなるという面白い交通流配分が発生する例題が知られている. これはBraessのパラドックスとよばれている.

---

参考文献

[1] D. Braess, "Über ein Paradoxen aus der Verkehrsplanung," Unternehmensforschung, 12 (1968), 258-268.

[2] M. Frank, "The Braess Paradox," Mathematical Programming, 20 (1981), 283-302.

[3] R. B. Potts and R. M. Oliver, Flows in Transportation Netwroks, Academic Press, 1972.

[4] J. G. Wardrop, "Some Theoretical Aspects of Road Traffic Reserach," in Proceedings of the Institute of Civil Engineers 2, 325-378, 1952.