第14回基礎ゼミ

交通ネットワーク分析ゼミ
第9章 確率的利用者均衡モデルの解法
2017/07/04
朝倉研究室 修士1年 金氏直也

1

はじめにロジット型確率配分の解法（経路限定）
ロジット型確率配分の解法（経路限定しない）
プロビット型確率配分の解法

確率的利用者均衡配分の解法

2

Dialのアルゴリズム
通常の道路網計画のための交通需要予測においては，経路交通量よりむしろリンク交通量のほうが重要なことが多い．

経路交通量を直接計算するのではなく，リンク交通通量のみを計算
経路の列挙を行うことなく、ロジット型確率配分とリンク交通量パターンの計算が可能

3

Dialのアルゴリズム
Step 0 : 準備(a)起点rから最短経路アルゴリズムを実行し、全てのノードの最小交通費用𝑐 𝑖 を計算
𝑐 𝑖 ← 𝐶𝑚𝑖𝑛 𝑟 → 𝑖
𝐶𝑚𝑖𝑛 𝑟 → 𝑖 :起点ノードrからノードiへの最小経路費用
1331112ｒ
23223s2264444

Dialのアルゴリズム
Step 0 : 準備(b)ノードの最小コストとリンクコストから、リンクのリンク尤度（選ばれやすさ）を計算
exp 𝜃 𝑐 𝑗 − 𝑐 𝑖 − 𝑡𝑖𝑗𝑐 𝑖 < 𝑐(𝑗)𝐿[𝑖 → 𝑗] = ቊ0𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
𝐿 = 0.368
31𝐿=11ｒ

1𝐿 = 0.368
2𝐿=112
𝐿=12
2

2
𝐿=1Ex)

3

3

𝐿=1𝐿 2 → 3 = exp 𝑐 3 − 𝑐 2 − 𝑡23= exp 3 − 2 − 1 = 1s

𝐿[4 → 𝑠] = exp{𝑐 𝑠 − 𝑐 4 − 𝑡4𝑠 }= exp 6 − 4 − 4 = 0.135

3𝐿 = 0.368
264𝐿 = 0.135445Dialのアルゴリズム
Step 1 : 前進処理
リンク尤度から、各リンクの分岐確率(リンク・ウェイト)を計算
𝐿[𝑖 → 𝑗]𝑓𝑜𝑟 𝑖 = 𝑟𝑊[𝑖 → 𝑗] = ൞𝐿[𝑖 → 𝑗] ෍ 𝑊[𝑚 → 𝑖] 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒𝑚∈𝐼𝑖

𝐿=1𝑊=1ｒ

𝐼𝑗 :ノードjに流入するリンクの始点集合

𝐿 = 0.368
1𝑊 = 0.368

1𝐿=1𝑊 = 1.734

3

𝐿 = 0.368
𝑊 = 0.368
𝐿=1𝑊 = 1.368

𝑊=1𝐿=13

𝐿 = 0.368
𝑊 = 0.639

22

𝑊 = 1.368
𝐿=14Ex)
𝑊 𝑟→2 =𝐿 𝑟→2 =1𝑊 2→3=𝐿 2→3 𝑊 𝑟→2 +𝑊 1→2
𝑊 = 0.272 = 1 ∗ 1 + 0.368 = 1.368

s6

𝐿 = 0.135

46

Dialのアルゴリズム
Step 2 : 後退処理 リンクウェイトから、リンク交通量の配分を計算
𝑊[𝑖 → 𝑗]𝑥𝑖𝑗 = (𝑞𝑟𝑗 + ෍ 𝑥𝑗𝑚 )σ𝑚∈𝐼𝑗 𝑊[𝑚 → 𝑗]𝑚∈𝑂𝑗

𝑂𝑗 :ノードjから流出するリンクの終点集合
𝐼𝑗 :ノードjに流入するリンクの始点集合
𝑥 = 192
𝑊 = 0.368

1𝑥 = 410
𝑊=1ｒ

1Ex) 𝑞𝑟𝑠 = 1000の場合

3𝑥 = 865
𝑊 = 1.734

3𝑥 = 217
𝑊 = 1.368

𝑥 = 43𝑊 = 0.639

s𝑥 = 715
𝑊 = 1.368
𝑊=1𝑥 = 590

22

𝑊 = 1.368
𝑥 = 926

𝑊 = 0.272
𝑥 = 1354

𝑊 3→𝑠
𝑊 4→𝑠 +𝑊 3→𝑠
1.734= 1000 ×= 865
0.272 + 1.734
𝑊 2→3
𝑥23 = 𝑥34 + 𝑥3𝑠𝑊 1→3 +𝑊 2→3
1.368= 43 + 865= 715
0.368 + 1.368
𝑥3𝑠 = 𝑞𝑟𝑠

47

Dialのアルゴリズム
リンク尤度の特性1)リンクi→jが起点からノードjまでの最短経路上にあるなら，そのリンク尤度は最大値1を取る
全経路の中で，最短経路の選ばれる確率が最も大きい．
2)リンクi→jを通ってノードjに到達する経路が最短経路よりも遠回りする度合いが大きくなるほど，そのリンク尤度の値は小さくなる．
コストの大きい経路ほど選択率が小さくなる
𝐿 = 0.368
31

𝐿=11ｒ1

𝐿 = 0.368
2
𝐿=112
𝐿=1222
𝐿=133

3

𝐿=1

𝐿 = 0.368
2s44
𝐿 = 0.135

648

Dialのアルゴリズム
リンク尤度の特性
3)リンクiからjへ進むと，起点からの最短距離で考えて後戻りする場合，リンクi→jのリンク尤度は0に設定される

このアルゴリズムで配分対象となる経路は，起点から遠ざかるノードのみから構成されているものに限る
𝐿 = 0.368
31𝐿=11ｒ1

𝐿 = 0.368
2𝐿=112
𝐿=1222
𝐿=1333

𝐿=1

𝐿 = 0.368
2s44
𝐿 = 0.135

649

Dialのアルゴリズムとロジットモデルの等価性
Dialのアルゴリズムによるリンク交通量パターンはロジットモデルによって起算した場合と一致する

ODペアrsのk番目の経路が選択される確率𝑃𝑘 を求める．
この経路は
𝑟 → 𝐴 → 𝐵 →∙∙∙→ 𝑌 → 𝑍 → 𝑠の順番で進んでいくとする

10

Dialのアルゴリズムとロジットモデルの等価性
Step 2 より，
𝑊[𝑍 → 𝑠]𝑊[𝑌 → 𝑍]𝑊[𝐴 → 𝐵]𝑊[𝑟 → 𝐴]
𝑃𝑘 =∙∙∙
σ𝑚 𝑊[𝑚 → 𝑠] σ𝑚 𝑊[𝑚 → 𝑍] σ𝑚 𝑊[𝑚 → 𝐵] σ𝑚 𝑊[𝑚 → 𝐴]
リンク･ウェイトの定義
𝑊 𝑖 → 𝑗 = 𝐿[𝑖 → 𝑗] σ𝑚 𝑊[𝑚 → 𝑖]

𝑃𝑘 = 𝐿 𝑍 → 𝑠 𝐿 𝑌 → 𝑍 ∙∙∙ 𝐿 𝐴 → 𝐵 𝐿 𝑟 → 𝐴 / ෍ 𝑊[𝑚 → 𝑠]𝑚

リンク尤度の定義より

𝑃𝑘 =exp θ 𝑐 𝑠 − 𝑐𝑘
σ𝑚 𝑊[𝑚 → 𝑠]

𝐿 𝑍 → 𝑠 𝐿 𝑌 → 𝑍 ∙∙∙ 𝐿 𝐴 → 𝐵 𝐿 𝑟 → 𝐴= exp θ 𝑐 𝑠 − 𝑐 𝑍 − 𝑡𝑍𝑠 exp θ 𝑐 𝑍 − 𝑐 𝑌 − 𝑡𝑌𝑍∙∙∙ exp θ 𝑐 𝐵 − 𝑐 𝐴 − 𝑡𝐴𝐵 exp θ 𝑐 𝐴 − 𝑐 𝑟 − 𝑡𝑟𝐴= exp θ 𝑐 𝑠 − (𝑡𝑟𝐴 +𝑡𝐴𝐵 +∙∙∙ +𝑡𝑌𝑍 + 𝑡𝑍𝑠 )= exp θ 𝑐 𝑠 − 𝑐𝑘𝑐𝑘 :k番目の経路の経路費用
11Dialのアルゴリズムとロジットモデルの等価性
exp θ𝑐 𝑠 exp[−θ𝑐𝑘 ]𝑃𝑘 =σ𝑚 𝑊[𝑚 → 𝑠]

フロー保存則෍ 𝑃𝑘 = 1𝑘exp θ𝑐 𝑠 σ𝑘 exp[−θ𝑐𝑘 ]෍ 𝑃𝑘 ==1σ𝑚 𝑊[𝑚 → 𝑠]
𝑘exp θ𝑐 𝑠
1=
σ𝑚 𝑊[𝑚 → 𝑠] σ𝑘 exp[−θ𝑐𝑘 ]exp[−θ𝑐𝑘 ]𝑃𝑘 =σ𝑘 exp[−θ𝑐𝑘 ]ロジットモデルの経路選択率12

Dialのアルゴリズムの問題点経路を限定しているため，非現実的なフローパターンを生成する場合がある
以下の図では𝑟 → 1 → 𝑠, 𝑟 → 2 → 𝑠の2つの経路を考える
𝐿 1 → 𝑠 = exp 𝑐 𝑠 − 𝑐 1 − 𝑡1𝑠 = exp[9 − 8 − 1] = 1𝐿[2 → 𝑠] = 0 (𝑐 2 ≥ 𝑐 𝑠 より)
リンク･ウェイトが0となり，交通量が配分されない
𝑐 1 =8811ｒs
1021𝑐 𝑠 = 9 起点からの最短距離で見て”逆戻り”していることになる

𝑐 2 = 1013

ロジット型確率配分の解法（経路限定しない）
配分対象とする経路集合を限定することのない計算方法であり，Markov連鎖配分を応用したものである．
Markov連鎖とは・・・
過去の状態によらず現在の状態のみで決まるような確率過程

14

ロジット型確率配分の解法（経路限定しない）
各ノードをマルコフ連鎖における状態に対応し，車は，支店からマルコフ連鎖則にしたがって分岐を繰り返し，終点に到着すると確率1で吸収される．
マルコフ連鎖配分では，配分対象経路をまったく限定せず，cycleも含むすべての可能な経路を配分対象経路として考えている．
推移確率は，多起点･1終点のODパターンにも1起点･多終点のODパターンに対しても成り立つ．

15

プロビット型確率配分の解法
プロビット･モデルは，一般的には，誤差項の多重正規分布を決定するための共分散行列のすべての要素をパラメータとするモデルである．
通常，共分散行列の構造に関して何らかの仮定を設定し，パラメータの個数を減らしたモデルとする．

16

プロビット型確率配分の解法
利用者の認知するリンクコスト𝑡ǁ𝑖𝑗 が，測定可能なリンクコス
ト𝑡𝑖𝑗 に誤差項𝜀𝑖𝑗
ǁ が加わったものと仮定
利用者の認知する経路コスト𝑐𝑘ǁ 𝑟𝑠 と認知リンクコスト𝑡ǁ𝑖𝑗 の関係は𝑟𝑠𝑐𝑘ǁ 𝑟𝑠 = ෍ 𝑡ǁ𝑖𝑗 𝛿𝑖𝑗,𝑘𝑖𝑗

プロビット型確率的配分では，経路選択率はこれらの認知経路コストが最小となる確率で計算される．

17

プロビット型確率配分の解法
2つの経路同士でともに通るリンクがない場合は，それらの認知経路コストは無相関である
重なりが大きいほど，その認知コスト間の相関が高くなる

これはロジットモデルで問題となるIIA特性を改善したものである．

18

確率的利用者均衡配分の解法
等価最適化問題を解くことで，均衡交通量を計算する3つの方法を示す．
(1)逐次平均法(2)起点別リンク交通量を未知変数とした部分線形化法(3)経路交通量を未知変数としたSimplicial Decomposition法

19確率的利用者均衡配分の解法(1)逐次平均法
Frank-Wolfe法と類似あらかじめ決められた定数列をステップサイズとする．
この計算法は，各種経路選択モデルに対応できる
ものの， 収束は非常に遅い

20

確率的利用者均衡配分の解法(1)逐次平均法
この方法での最も簡単なステップサイズは，
𝛼𝑛 = 1/𝑛
各繰り返しでの解の改訂は
𝒙(𝑛+1) = 𝒙(𝑛) + 𝛼𝑛 𝒚 𝑛 − 𝒙 𝑛= 1−=𝑛−1 𝑛−2 (𝑛−1)𝑛𝒙+𝒚 𝑛−1𝑛𝑛−1𝑛−1=𝑛−2 (𝑛−1)1𝒙+𝑛𝑛1𝑛1𝑛𝒙𝑛 + 𝒚𝑛
1𝑛+ 𝒚𝑛𝒚 𝑛 + 𝒚 𝑛−11𝑛= σ𝑛𝑚=1 𝒚 𝑚21

確率的利用者均衡配分の解法(1)逐次平均法
Step 0:初期許容解を求める(0)

繰り返し回数n:=0

リンクコスト𝑡𝑖𝑗 ≔ 𝑡𝑖𝑗 (0)

その配分結果を𝒙(0) とする
Step 1:リンクコスト改訂
(𝑛)

(𝑛)

𝑡𝑖𝑗 ≔ 𝑡𝑖𝑗 (𝑥𝑖𝑗 )Step 2:降下方向ベクトルを求める
リンクコスト𝑡 (𝑛) に対して確率的配分を行い，その配分効果のリンク交通量パターンを𝑦 (𝑛) とする
降下方向ベクトル𝑑 (𝑛) を計算: 𝒅(𝑛) ≔ 𝒚(𝑛) − 𝒙(𝑛)22

確率的利用者均衡配分の解法(1)逐次平均法
Step 3:1次元探索
ステップサイズを以下のように与える．

𝛼 ≔ 1/𝑛

Step 4:解の改訂
リンク交通量ベクトルを改訂

𝒙(𝑛+1) ≔ 𝒙 𝑛 + 𝛼𝒅(𝑛)Step 5:収束判定
収束していれば終了，それでなければ，𝑛 ≔ 𝑛 + 1とし，step1へ

23

確率的利用者均衡配分の解法(2)起点別リンク交通量を未知変数とした部分線形化法

起点別リンク交通量によって表現された等価最適化問題をとくことを考える．
この問題では，経路変数を含まず，起点別リンク交通量を未知変数とすれば，目的間数値を計算することが容易．

24

確率的利用者均衡配分の解法(2)起点別リンク交通量を未知変数とした部分線形化法

部分線形化法を適用すると，Wardrop均衡配分をFrank-Wolfe法で解く際の最短経路配分をDial配分/Markov配分に置き換えた以下のアルゴリズムとなる

25

確率的利用者均衡配分の解法(2)起点別リンク交通量を未知変数とした部分線形化法
Step 0:初期許容解を求める
繰り返し回数n:=0(0)

リンクコスト𝑡𝑖𝑗 ≔ 𝑡𝑖𝑗 (0)

その配分結果を𝑥 (0)とする
Step 1:リンクコスト改訂
(𝑛)

(𝑛)

𝑡𝑖𝑗 ≔ 𝑡𝑖𝑗 (𝑥𝑖𝑗 )Step 2:降下方向ベクトルを求める
リンクコスト𝑡 (𝑛) に対して確率的配分を行い，その配分効果のリンク交通量パターンを𝑦 (𝑛) とする

降下方向ベクトル𝑑 (𝑛) を計算: 𝒅(𝑛) ≔ 𝒚(𝑛) − 𝒙(𝑛)26

確率的利用者均衡配分の解法(2)起点別リンク交通量を未知変数とした部分線形化法
Step 3:1次元探索
以下の位置次元探索問題を解き，step size 𝛼を決定

𝑚𝑖𝑛. 𝑍 𝒙 𝑛 + 𝛼𝒅(𝑛) 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 0 ≤ 𝛼 ≤ 1
Step 4:解の改訂
リンク交通量ベクトルを改訂

𝒙(𝑛+1) ≔ 𝒙 𝑛 + 𝛼𝒅(𝑛)Step 5:収束判定
収束していれば終了，それでなければ，𝑛 ≔ 𝑛 + 1とし，step1へ

27

確率的利用者均衡配分の解法(2)起点別リンク交通量を未知変数とした部分線形化法
この方法はきわめて効率よくSUE配分モデルを解くことができる
表は逐次平均法との比較を行っている．

28

確率的利用者均衡配分の解法(2)起点別リンク交通量を未知変数とした部分線形化法

この方法は，収束の効率性に関しては非常に優れている．しかし，明示的未知変数を起点別リンク交通量としているため，逐次平均法の場合よりも多くの記憶容量を必要とする．

29

確率的利用者均衡配分の解法(3)経路交通量を未知変数としたSimplicial Decomposition法
経路交通量を明示的に未知変数として取り扱う．
そのため，規模の大きくないネットワークの分析を行う場合では有効な手法である．

このアルゴリズムの理論的基礎は，凸多面体の許容領域内の任意の点は，その端点の凸結合によって表現される．

30

確率的利用者均衡配分の解法(3)経路交通量を未知変数としたSimplicial Decomposition法
限定親問題
限定された経路集合に対する経路交通量を用いてもとの問題を表現し，その経路交通量パターンを最適化する問題
この問題の最も単純な解法が部分線形化法である．

列生成
新たな経路の生成を意味する．
経路コスト･パターンを基準にした最短経路を新たな経路とするものである．

31

確率的利用者均衡配分の解法(3)経路交通量を未知変数としたSimplicial Decomposition法
Step 0:初期設定
繰り返し回数 m:=0(𝑚)෡𝑟𝑠 を設定
初期経路集合𝐾

Step 1:親問題フェイズ
Step 1.0:初期設定

繰り返し回数 m:=0
初期経路交通量パターンとそれに対応するリンク交通量設定:𝒇ത (𝑛) ≔ 𝒇 𝑚 , 𝒙 𝑚 ≔ ∆𝒇ത (𝑚)32確率的利用者均衡配分の解法(3)経路交通量を未知変数としたSimplicial Decomposition法
Step 1.1:補助問題(部分線形化問題)を解く
(𝑛)

(𝑛)

𝑟𝑠(𝑛)

𝑟𝑠
≔ σ𝑖𝑗 𝑡𝑖𝑗 𝛿𝑖𝑗,𝑘(a)リンクコストの設定: 𝑡𝑖𝑗 ≔ 𝑡𝑖𝑗 (𝑥𝑖𝑗 )(b)経路コストの設定：𝑐𝑘(𝑛)(𝑚)෡𝑟𝑠 に対して補助経路交通量お(c)ロジット式により経路集合𝐾よびそれに対応するリンク交通量設定を計算
𝑟𝑠 𝑛
exp−𝜃𝑐𝑘𝑟𝑠(𝑛)𝑐𝑘≔ 𝑡𝑖𝑗σ𝑘∈𝐾෡ exp −𝜃𝑐𝑘𝑟𝑠 𝑛𝑛(𝑛)𝑟𝑠 𝑛𝑡𝑖𝑗 ≔ ෍ 𝑔𝑘𝑟𝑠𝛿𝑖𝑗,𝑘෡𝑛𝑘∈𝐾

33

確率的利用者均衡配分の解法(3)経路交通量を未知変数としたSimplicial Decomposition法
Step 1.2:一時元探索と解の改訂(a)以下の一時元探索問題を解き，step size 𝛼を決定
𝑚𝑖𝑛. 𝑍 𝒙 𝑛 + 𝛼 𝒚 𝑛 − 𝒙 𝑛 , 𝒇ത 𝑛 + 𝛼 𝒈 𝑛 − 𝒇 𝑛

𝑠. 𝑡 0 ≤ 𝛼 ≤ 1(b)経路交通量，リンク交通量の改訂
𝑟𝑠(𝑛+1)
𝑟𝑠 𝑛
𝑟𝑠 𝑛
𝑟𝑠 𝑛𝑓𝑘ҧ≔ 𝑓𝑘ҧ
+ 𝛼(𝑔𝑘− 𝑓𝑘ҧ)(𝑛)𝑛𝑛𝑛
𝑥𝑖𝑗 ≔ 𝑥𝑖𝑗 + 𝛼(𝑦𝑖𝑗 − 𝑥𝑖𝑗 )34

確率的利用者均衡配分の解法(3)経路交通量を未知変数としたSimplicial Decomposition法
Step 1.3:収束判定
もし，𝒇ത 𝑛 ≈ 𝒈 𝑛 なら𝒇ത ≔ 𝒇ത 𝑛 として step2へ

そうでなければ， 𝑛 ≔ 𝑛 + 1としてstep1.1へ

Step 2:経路生成フェイズ(𝑚)

上で説明したような方法によって，経路集合𝑅෠𝑟𝑠 を拡張する
もし，新たな経路が見つからなければ終了ത 𝑚 ≔ 𝑚 + 1とし，step1へ
そうでなければ，𝒇ത 𝑚+1 ≔ 𝒇,

35

まとめ
確率的利用者均衡配分には3つの解法があり，
リンク交通量と起点別交通量を未知変数とするMSAとPLはそれぞれ収束速度，記憶容量が異なる
経路交通量を未知変数として扱うSimplicial
Decomposition法は小規模なネットワーク分析に有効36