ウォードロップの原理

【うぉーどろっぷのげんり (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の場合に上のふたつの原理を定式化しよう. 変数は, 各枝の流れではなく各経路に沿った流れとする. 枝の集合を $E\,$, OD間の経路の集合を $M\,$ , 経路 $j\in M\,$の流れを $h_{j}\geq 0\,$ とする. 経路 $j\,$ を構成する枝を表すのに

$a_{ij}=1\,$ : 枝 $i\,$ が経路 $j\,$ に含まれるとき,

$a_{ij}=0\,$ : それ以外

とする. 枝 $i\,$ の流れ $f_{i}\,$ は, 枝 $i\,$ を通る経路の流量の和として

$f_{i}=\sum _{j\in M}a_{ij}h_{j},\qquad i\in E\,$　　　　　$(1)\,$

と表すことができる. 枝 $i\,$ を通過するのにかかる旅行時間(費用)を枝 $i\,$ の流れ $f_{i}\,$ の関数として $c_{i}(f_{i})\,$ とする. すると, 経路 $j\,$ の旅行時間は

$C_{j}=\sum _{i\in E}a_{ij}c_{i}(f_{i})\,$

である. ただし $f_{i}\,$ は式(1)で与えられるとする. 総OD交通量を $d\,$ とすると

$d=\sum _{j\in M}h_{j}\,$　　　　　$(2)\,$

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

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

　利用者最適化配分は次のように定式化できる. 経路の番号を旅行時間の短い方から順に $1\,$, $2\,$, $\ldots \,$, $|M|\,$ としたとき, 利用者最適化配分 $h\,$ は

$C_{1}(h)=C_{2}(h)=\ldots =C_{k}(h)\leq C_{k+1}(h)\leq \ldots \leq C_{|M|},\,$　　　　　$(3)\,$

$h_{1}>0,h_{2}>0,\ldots ,h_{k}>0,h_{k+1}=0,\ldots ,h_{|M|}=0\,$　　　　　$(4)\,$

を満たす.

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

$\sum _{j\in M}h_{j}C_{j}(h)=\sum _{j\in M}h_{j}\sum _{i\in E}a_{ij}c_{i}(f_{i})=\sum _{i\in E}f_{i}c_{i}(f_{i})\,$

と表されることから,

$\min _{h}\sum _{i}f_{i}c_{i}(f_{i})\,$

${\mbox{s. t.}}\;\;\;f_{i}=\sum _{j\in M}a_{ij}h_{j},\qquad i\in E,\,$

$\;\;\;\;\;\sum _{j\in M}h_{j}=d,\,$

$\;\;\;\;\;h_{j}\geq 0,\qquad j\in M\,$

である.

　各枝における総費用 $f_{i}c_{i}(f_{i})\,$ が強凸で増加関数であると仮定して, この問題と双対問題との相補条件が利用者最適配分(3), (4)と同じ形となることを示そう. (1)に関する双対変数を $\mu _{i}\,$, (2)に関する双対変数を $\lambda \,$ とすると, 双対問題は

$\max _{\mu ,\lambda }\lambda d-\sum _{i\in E}\phi _{i}(\mu _{i})\,$

${\mbox{s. t.}}\;\;\;\sum _{i\in E}\mu _{i}a_{ij}-\lambda \geq 0,\qquad j\in M,\,$

$\;\;\;\;\;\phi _{i}(\mu )=\min _{f\geq 0}\{\mu f-fc(f)\}$

となり, 相補条件は

もし $f_{i}>0\,$ ならば $\partial (f_{i}c_{i}(f_{i}))/\partial f_{i}=\mu _{i},\qquad i\in E,\,$

もし $\partial (f_{i}c_{i}(f_{i}))/\partial f_{i}|_{f=0}>\mu _{i}\,$ ならば $f_{i}=0,\qquad i\in E,\,$

もし $h_{j}>0\,$ ならば $\displaystyle \sum _{i\in E}\mu _{i}a_{ij}=\lambda ,\qquad j\in M,\,$

もし $\displaystyle \sum _{i\in E}\mu _{i}a_{ij}>0\,$ ならば $h_{j}=0,\qquad j\in M\,$

となる. $\mu _{i}\,$ は各枝の限界費用 $\partial (f_{i}c_{i}(f_{i}))/\partial f_{i}\,$ であり, 使われている経路に対しては, 経路を構成する枝の限界費用の和(経路の限界費用)は等しく, 使われていない経路の限界費用よりも小さいことがわかる. この記述は限界費用を枝の費用に置き換えると利用者最適化配分の記述そのものである. そこで, システム最適化配分問題で, $c(f)\,$ の代わりに

${\frac {1}{f}}\int _{0}^{f}c(\tau ){\mbox{d}}\tau \,$

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

${\mbox{min.}}\sum _{i}\int _{0}^{f}c_{i}(\tau ){\mbox{d}}\tau \,$ ${\mbox{s. t.}}\;\;\;\sum _{j\in M}h_{j}=d,\,$

$\;\;\;\;\;h_{j}\geq 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.