第11回 基礎ゼミ
確率的利用者均衡モデル

福田研究室

修士1年
城間 洋也

Outline はじめに• 今日やること• 前回の復習

 確率的利用者均衡配分• 確率的配分モデル（6.1）• エントロピー・モデル（6.2）• 確率的利用者均衡配分の定式化（6.3）• 確率的利用者均衡配分と等価最適化問題（6.4）

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

2

はじめに：今日やること 位置づけ
交通量配分問題（Traffic assignment problem）
均衡型配分

••
•

静的均衡
需要固定型

需要変動型

確定的利用者均衡（UE/FD）

確定的利用者均衡（UE/VD）

論理が明解
信頼性が高い（均衡解の一意性）
予測精度の向上が期待できる

非均衡型配分
•分割配分法（IA法）

拡張

確率的利用者均衡（SUE/FD） 確率的利用者均衡（SUE/VD）

動的均衡
動的利用者均衡（DUE）

どのような経路選択規範・OD需要等の仮定を置くかで均衡モデルは様々

3

はじめに：前回の復習 需要固定型確定的利用者均衡配分（UE/FD : User Equilibrium with Fixed Demand）
経路選択規範がWardropの第一原則に従う→利用される経路の旅行時間は皆等しく、利用されない経路の旅行時間よりも小さいかせいぜい等しい
利用者均衡式：
𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 > 0のとき
� 𝑟𝑟𝑟𝑟𝑓𝑓𝑘𝑘 = 0のとき
制約条件：

𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 = 𝑐𝑐𝑟𝑟𝑟𝑟
𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 ≥ 𝑐𝑐𝑟𝑟𝑟𝑟

� 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 − 𝑞𝑞𝑟𝑟𝑟𝑟 = 0

𝑘𝑘∈𝐾𝐾𝑟𝑟𝑟𝑟

𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ≥ 0

等価な最適化問題：(∀𝑘𝑘 ∈ 𝐾𝐾𝑟𝑟𝑟𝑟 , ∀𝑟𝑟𝑟𝑟 ∈ Ω)
∀𝑟𝑟𝑟𝑟 ∈ Ω(∀𝑘𝑘 ∈ 𝐾𝐾𝑟𝑟𝑟𝑟 , ∀𝑟𝑟𝑟𝑟 ∈ Ω)

効率化

𝑟𝑟1

𝑟𝑟2

𝑥𝑥𝑎𝑎

𝑚𝑚𝑚𝑚𝑚𝑚. 𝑍𝑍𝑝𝑝 = � � 𝑡𝑡𝑎𝑎 𝑤𝑤 𝑑𝑑𝑑𝑑𝑎𝑎∈𝐴𝐴 0𝑟𝑟𝑟𝑟 𝑟𝑟𝑟𝑟
𝑠𝑠𝑠𝑠𝑠𝑠. 𝑡𝑡𝑡𝑡 � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 − 𝑞𝑞𝑟𝑟𝑟𝑟 = 0 ∀𝑟𝑟𝑟𝑟 ∈ Ω , 𝑥𝑥𝑎𝑎 = � � 𝛿𝛿𝑎𝑎,𝑘𝑘
𝑓𝑓𝑘𝑘 ∀𝑎𝑎 ∈ 𝐴𝐴
𝑘𝑘∈𝐾𝐾𝑟𝑟𝑟𝑟

𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ≥ 0, 𝑥𝑥𝑎𝑎 ≥ 0𝑘𝑘∈𝐾𝐾𝑟𝑟𝑟𝑟 𝑟𝑟𝑠𝑠∈Ω𝑥𝑥2𝑥𝑥3𝑥𝑥1𝑥𝑥4

𝑓𝑓111

𝑓𝑓211𝑥𝑥5

𝑠𝑠1𝑥𝑥6

𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 : ODペア𝑟𝑟𝑟𝑟の経路𝑘𝑘の経路交通量
𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 : ODペア𝑟𝑟𝑟𝑟の経路𝑘𝑘の所要時間
𝑐𝑐𝑟𝑟𝑟𝑟 : ODペア𝑟𝑟𝑟𝑟の最小所要時間
𝑞𝑞𝑟𝑟𝑟𝑟 : ODペア𝑟𝑟𝑟𝑟の分布交通量
𝐾𝐾𝑟𝑟𝑟𝑟 : ODペア𝑟𝑟𝑟𝑟の経路集合𝑥𝑥𝑎𝑎 : リンク𝑎𝑎のリンク交通量
𝑡𝑡𝑎𝑎 𝑥𝑥𝑎𝑎 : リンク𝑎𝑎のリンクコスト関数
Ω: ネットワーク上のODペア集合
𝐴𝐴: ネットワーク上のリンク集合
1 ∶ ODペア𝑟𝑟𝑟𝑟経路𝑘𝑘がリンク𝑎𝑎を含む𝑟𝑟𝑟𝑟𝛿𝛿𝑎𝑎,𝑘𝑘:=�
0 ∶ そうでないとき
4

確率的利用者均衡配分（SUE : Stochastic User Equilibrium）
 確定的利用者均衡

もはやどの利用者も経路を変更することによって自己の旅行時間をそれ以上短縮できない均衡状態（前提条件）• 全ての利用者は常に旅行時間最小化という同一の評価水準に基づき行動• 利用者は利用可能な経路に関する完全な旅行時間情報を得ている

𝑐𝑐1𝑟𝑟𝑟𝑟 = 𝑡𝑡1 𝑥𝑥1 + 𝑡𝑡3 𝑥𝑥3𝑟𝑟

𝑡𝑡4 𝑥𝑥4

𝑠𝑠

𝑈𝑈1𝑟𝑟𝑟𝑟 = −𝑐𝑐1𝑟𝑟𝑟𝑟 + 𝜉𝜉1𝑟𝑟𝑟𝑟

 確率的利用者均衡→ ランダム効用理論に基づき拡張された利用者均衡
利用者の認知誤差を考慮

𝑡𝑡2 𝑥𝑥2

𝑡𝑡3 𝑥𝑥3𝑐𝑐2𝑟𝑟𝑟𝑟 = 𝑡𝑡2 𝑥𝑥2 + 𝑡𝑡4 𝑥𝑥4→ 確定的な経路費用のみを考慮

もはやどの利用者も経路を変更することによって自己の旅行時間をそれ以上短縮することはできないと信じている均衡状態

𝑡𝑡1 𝑥𝑥1

𝑠𝑠𝑟𝑟
𝑈𝑈2𝑟𝑟𝑟𝑟 = −𝑐𝑐2𝑟𝑟𝑟𝑟 + 𝜉𝜉2𝑟𝑟𝑟𝑟

5確率的配分モデル
 確率的配分モデル

経路費用が一定（混雑なし）の場合の利用者の経路選択行動をランダム効用理論に基づく離散選択モデルで表現する• 一般的な定式化
効用関数：𝑈𝑈𝑘𝑘𝑟𝑟𝑟𝑟 = −𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 + 𝜉𝜉𝑘𝑘𝑟𝑟𝑟𝑟• 具体的な定式化a)誤差項の確率分布••

𝑈𝑈𝑘𝑘𝑟𝑟𝑟𝑟 : ODペア𝑟𝑟𝑟𝑟の𝑘𝑘番目の経路の効用𝜉𝜉𝑘𝑘𝑟𝑟𝑟𝑟 : 利用者の認知誤差を表す確率変数(ex) 互いに独立なWeibull分布𝑊𝑊(0, 𝜃𝜃)

ランダム効用理論

選択確率：𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟 = 𝑃𝑃𝑃𝑃. 𝑈𝑈𝑘𝑘𝑟𝑟𝑟𝑟 ≥ 𝑚𝑚𝑚𝑚𝑚𝑚
𝑈𝑈𝑘𝑘 ′′= 𝑃𝑃𝑃𝑃.

𝑟𝑟𝑟𝑟𝒕𝒕𝑘𝑘 ≠𝑘𝑘𝑟𝑟𝑟𝑟
𝑟𝑟𝑟𝑟
𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 − 𝜉𝜉𝑘𝑘𝑟𝑟𝑟𝑟 ≤ 𝑚𝑚𝑖𝑖𝑖𝑖𝑐𝑐′ − 𝜉𝜉𝑘𝑘 ′𝑘𝑘𝑘𝑘 ′ ≠𝑘𝑘𝐸𝐸[𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ] = 𝑞𝑞𝑟𝑟𝑟𝑟

𝒕𝒕← 一旦𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟 が定まると𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 は二項分布：𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ~𝐵𝐵 𝑞𝑞𝑟𝑟𝑟𝑟 , 𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟 に従う

配分交通量の確率特性：
𝐸𝐸 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟= 𝑞𝑞𝑟𝑟𝑟𝑟 𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟
𝑉𝑉𝑉𝑉𝑉𝑉 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 = 𝑞𝑞𝑟𝑟𝑟𝑟 𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟 (1 − 𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟 )𝐶𝐶𝐶𝐶𝐶𝐶 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 , 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟′ = −𝑞𝑞𝑟𝑟𝑟𝑟 𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟 𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟′•フローの保存則

� 𝐸𝐸 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 = 𝑞𝑞𝑟𝑟𝑟𝑟
𝑘𝑘𝑟𝑟𝑟𝑟
𝐸𝐸 𝑥𝑥𝑎𝑎 = � � 𝐸𝐸 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 𝛿𝛿𝑎𝑎,𝑘𝑘𝑟𝑟𝑠𝑠

正規分布→プロビット・モデル
Weibull分布→ロジット・モデル

𝑘𝑘exp(−𝜃𝜃𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 )∑𝑘𝑘 ′ ∈𝐾𝐾 exp(−𝜃𝜃𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟′ )𝑟𝑟𝑠𝑠b)対象とする経路集合※詳しくは9章• Simple path(同一リンクを二度以上通過しない)の集合• ある規則でSimple path集合をさらに限定した集合• 限定なしの全ての可能経路集合等を決める必要がある

以降、期待値計算は𝐸𝐸 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 →𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 のように表す

6

確率的配分モデル
 期待最大効用

ランダム効用理論では意思決定者が選択行動によって得ると認知する効用は𝑚𝑚𝑚𝑚𝑚𝑚 {𝑈𝑈𝑘𝑘 }→ 確率変数であるため確定的に評価は不可、確率分布・期待値で評価される
最大効用の期待値：𝑆𝑆 ∗ = 𝐸𝐸[𝑚𝑚𝑚𝑚𝑚𝑚{𝑈𝑈𝑘𝑘 = 𝑉𝑉𝑘𝑘 + 𝜀𝜀𝑘𝑘 }]𝑘𝑘ロジット・モデルの場合

𝐾𝐾

1𝛾𝛾𝑆𝑆 ∗ 𝑽𝑽 = 𝑙𝑙𝑙𝑙 � exp(𝜃𝜃𝑉𝑉𝑘𝑘 ) + 𝜂𝜂 +𝜃𝜃𝜃𝜃𝑘𝑘=1𝜀𝜀𝑘𝑘 ~𝐸𝐸𝐸𝐸(𝜂𝜂, 𝜃𝜃)𝑉𝑉𝑘𝑘′ = 𝑉𝑉𝑘𝑘 + 𝜂𝜂

𝑈𝑈𝑘𝑘 ~𝐸𝐸𝐸𝐸(𝑉𝑉𝑘𝑘′ , 𝜃𝜃)

2.
3.
4.
5.
6.

𝐾𝐾

1
𝑈𝑈 = 𝑚𝑚𝑚𝑚𝑚𝑚{𝑈𝑈𝑘𝑘 } ~𝐸𝐸𝐸𝐸𝑙𝑙𝑙𝑙 � exp(𝜃𝜃𝑉𝑉𝑘𝑘′ ) , 𝜃𝜃𝑘𝑘𝜃𝜃∗

代表的性質：
1.

𝑘𝑘

確定効用𝑽𝑽に対する期待最大効用の変化率が選択確率となる：
確定効用𝑽𝑽に関して連続・微分可能な狭義凸関数である
選択肢集合中のどの効用よりも大きい：𝑆𝑆 ∗ 𝑽𝑽 ≥ max 𝑉𝑉𝑘𝑘

𝑘𝑘=1

𝜕𝜕𝑆𝑆 ∗ 𝑽𝑽𝜕𝜕𝑉𝑉𝑘𝑘= 𝑃𝑃𝑘𝑘 (𝑽𝑽)𝑘𝑘∈𝐾𝐾

選択肢集合のサイズに関して単調増加関数：𝑆𝑆 ∗ (𝑉𝑉1 , 𝑉𝑉2 , … , 𝑉𝑉𝑘𝑘 , 𝑉𝑉𝑘𝑘+1 ) ≥ 𝑆𝑆 ∗ (𝑉𝑉1 , 𝑉𝑉2 , … , 𝑉𝑉𝑘𝑘 )𝜕𝜕𝑆𝑆 ∗ 𝑽𝑽
𝜕𝜕𝛽𝛽𝑖𝑖𝜕𝜕𝑆𝑆 ∗ 𝑽𝑽
𝜕𝜕𝛽𝛽𝑖𝑖= 𝐸𝐸𝑷𝑷 [𝒂𝒂𝒊𝒊 ]= 𝑉𝑉𝑉𝑉𝑉𝑉𝑷𝑷 [𝒂𝒂𝒊𝒊 ]𝑉𝑉𝑘𝑘 = � 𝛽𝛽𝑖𝑖 𝑎𝑎𝑖𝑖,𝑘𝑘𝑘𝑘

7確率的配分モデル
 期待最小費用
効用最大化

費用最小化

⇔

確率的な認知費用：𝑐𝑐𝑘𝑘̃ 𝑟𝑟𝑟𝑟 ≡ −𝑈𝑈𝑘𝑘𝑟𝑟𝑟𝑟 = 𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 − 𝜉𝜉𝑘𝑘𝑟𝑟𝑟𝑟 を最小化
𝑆𝑆𝑟𝑟𝑟𝑟 𝒄𝒄𝒓𝒓𝒓𝒓 ≡ 𝐸𝐸 min 𝑐𝑐𝑘𝑘̃ 𝑟𝑟𝑟𝑟
𝑘𝑘∈𝐾𝐾𝑟𝑟𝑟𝑟= −𝑆𝑆 ∗ −𝒄𝒄𝒓𝒓𝒓𝒓

期待最大効用の符号を逆転させた量

ロジット・モデルの場合

𝑆𝑆𝑟𝑟𝑟𝑟 𝒄𝒄𝒓𝒓𝒓𝒓 =1ln � exp(−𝜃𝜃𝒄𝒄𝒓𝒓𝒓𝒓 )𝜃𝜃𝑘𝑘∈𝐾𝐾𝑟𝑟𝑟𝑟

例題ネットワーク：

O

𝑐𝑐1
𝑐𝑐2D

最小費用関数min{𝒄𝒄}を一般化したもの

𝑐𝑐2 (固定)
lim 𝑆𝑆(𝑐𝑐1 , 𝑐𝑐2 ) = min[𝑐𝑐1 , 𝑐𝑐2 ]𝜃𝜃→∞

図：期待最小費用と最小費用

𝑐𝑐18

エントロピー・モデル
 経路交通量と状態

経路交通量 ← 個々の利用者の経路選択の集計結果
全利用者の経路選択パターン𝜽𝜽 = … , 𝑛𝑛𝑖𝑖 , … をシステムの”状態”と呼ぶ
𝑛𝑛𝑖𝑖 ：利用者𝑖𝑖の経路選択結果（経路番号）1

状態 𝜃𝜃𝐟𝐟
状態 𝜃𝜃𝐟𝐟2⋮
𝑁𝑁(𝐟𝐟)状態 𝜃𝜃𝐟𝐟

経路交通量パターン𝐟𝐟

例題ネットワーク：
経路交通量パターン𝐟𝐟

状態𝜽𝜽

𝑁𝑁(𝐟𝐟)個の状態

1ブタ , 2ネコ , 2イヌ , 3トラ , 3パンダ , 3サル

2ブタ , 2ネコ , 3イヌ , 3トラ , 1パンダ , 3サル⋮⋮⋮

状態数𝑁𝑁 𝐟𝐟 = 6𝐶𝐶1 × 5𝐶𝐶2 × 3𝐶𝐶3 = 60

9

エントロピー・モデル
 エントロピー・モデル
各状態 𝜽𝜽1 , 𝜽𝜽𝟐𝟐 , … が同確率で生成すると仮定す
ると、対応する状態数が最大の経路交通量パターン𝐟𝐟 ∗ が最も起こりやすい
OD交通量𝑞𝑞𝑟𝑟𝑟𝑟 が与えられたとき、交通量パターン𝐟𝐟に対応する状態数𝑁𝑁 𝐟𝐟 は𝑁𝑁 𝐟𝐟 = �𝑟𝑟𝑠𝑠

𝑞𝑞𝑟𝑟𝑟𝑟 !
∏𝑘𝑘 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 !

𝑁𝑁 𝐟𝐟 の対数の最大化によって最も生成されやすい交通量パターン𝐟𝐟 ∗ を求める
最適解𝐟𝐟 ∗ ：𝑞𝑞𝑟𝑟𝑟𝑟
𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 =𝐾𝐾𝑟𝑟𝑟𝑟→ ネットワークの総走行費用の制約がない場合各経路に均等に交通量が配分される＝
経路選択の不確実性を最大化している＊最適化問題＊
目的関数：

max. ln 𝑁𝑁 𝐟𝐟 = � ln 𝑞𝑞𝑟𝑟𝑟𝑟 ! − � ln 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 !
𝑟𝑟𝑠𝑠

𝑘𝑘Stirlingの公式：ln 𝑥𝑥! ~ 𝑥𝑥 ln 𝑥𝑥 − 𝑥𝑥max. ln 𝑁𝑁 𝐟𝐟 = � 𝑞𝑞𝑟𝑟𝑟𝑟 ln 𝑞𝑞𝑟𝑟𝑟𝑟 − � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ln 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟
𝑟𝑟𝑠𝑠

𝑞𝑞𝑟𝑟𝑟𝑟 は所与（定数）𝑘𝑘max. 𝑍𝑍 𝐟𝐟 = − � � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ln 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟

制約条件：

𝑟𝑟𝑠𝑠

𝑘𝑘𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟 ≡ 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 /𝑞𝑞𝑟𝑟𝑟𝑟

𝑞𝑞𝑟𝑟𝑟𝑟 = ∑𝑘𝑘 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 （フローの保存則）

𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 > 0（非負条件）

エントロピー関数：𝐻𝐻𝑟𝑟𝑟𝑟 𝐏𝐏 = − ∑𝑘𝑘 𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟 ln 𝑃𝑃𝑘𝑘𝑟𝑟𝑟𝑟
max. 𝐻𝐻 𝐏𝐏 = 𝐻𝐻 1⁄𝐾𝐾 , … , 1⁄𝐾𝐾 = ln 𝐾𝐾
min. 𝐻𝐻 𝐏𝐏 = 𝐻𝐻 1,0, … , 0 = ⋯ = 0→ 不確実性を表す指標となっている∑𝑟𝑟𝑠𝑠 𝐻𝐻𝑟𝑟𝑟𝑟 𝐏𝐏 の最大化と等価

10エントロピー・モデル
 エントロピー・モデル（エントロピー最大化モデル）
�
ネットワーク全体の総走行費用がたかだか𝐸𝐸であることが観測によりわかっているとき観測情報に整合的で最も生成しやすい交通量パターンを求める最適化問題

max. 𝑍𝑍 𝐟𝐟 = − � � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ln 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟
Sub. to𝑟𝑟𝑠𝑠𝑘𝑘� � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 ≤ 𝐸𝐸�
𝑟𝑟𝑠𝑠 𝑘𝑘

最短経路配分や全くランダムな配分のような極端な交通量パターンではなく、それらの中間的な交通量パターンが最適解として求まる

𝑞𝑞𝑟𝑟𝑟𝑟 = � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 , 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 > 0

 解の唯一性

𝑘𝑘・最大化目的関数が狭義凹関数↑エントロピー関数のHessianは負定値行列
・ 𝐟𝐟の許容領域が閉凸集合↑制約条件式は線形式，非負条件のみ

エントロピー関数：𝐻𝐻 𝐏𝐏 = − ∑𝑘𝑘 𝑃𝑃𝑘𝑘 ln 𝑃𝑃𝑘𝑘
𝜕𝜕 2 𝐻𝐻−1/𝑃𝑃𝑙𝑙=�0𝜕𝜕𝑃𝑃𝑙𝑙 𝜕𝜕𝑃𝑃𝑚𝑚

(𝑙𝑙 = 𝑚𝑚)(𝑙𝑙 ≠ 𝑚𝑚)𝐫𝐫 𝑇𝑇 𝛻𝛻 2 𝐻𝐻𝐫𝐫 = − � 𝑟𝑟𝑘𝑘2 ⁄𝑃𝑃𝑘𝑘 < 0 (𝐫𝐫: 任意の実数ベクトル)𝑘𝑘

・ 𝐟𝐟の許容領域が有界↑制約条件式が示す𝐟𝐟の許容領域は有界（サイクリックな経路を考慮しない場合）

11エントロピー・モデル
 エントロピー・モデルとロジットモデルの等価性【 Lagrangianを用いた最適化問題】
max. 𝐿𝐿 𝐟𝐟, 𝜃𝜃, 𝜼𝜼 = 𝑍𝑍 𝐟𝐟 + 𝜃𝜃 𝐸𝐸� − � � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 + � 𝜂𝜂𝑟𝑟𝑟𝑟 𝑞𝑞𝑟𝑟𝑟𝑟 − � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟Sub. to

𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟

𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ≥ 0, 𝜃𝜃 ≥ 0

𝑟𝑟𝑠𝑠

𝑘𝑘𝑟𝑟𝑠𝑠Kuhn-Tucker条件

𝜕𝜕𝐿𝐿
𝜕𝜕𝐿𝐿
=0
𝑎𝑎𝑎𝑎𝑎𝑎≤0
𝜕𝜕𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟
𝜕𝜕𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟𝜃𝜃 ≥ 0,𝑘𝑘

� 𝑞𝑞𝑟𝑟𝑟𝑟 = � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 , 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ≥ 0
� � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 ≤ 𝐸𝐸,
𝑟𝑟𝑠𝑠

𝑘𝑘𝑟𝑟𝑟𝑟exp(−𝜃𝜃𝑐𝑐)𝑘𝑘
𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 = 𝑞𝑞𝑟𝑟𝑟𝑟∑𝑘𝑘 exp(−𝜃𝜃𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 )𝑘𝑘∀𝑘𝑘 ∈ 𝐾𝐾𝑟𝑟𝑟𝑟 , ∀𝑟𝑟𝑟𝑟 ∈ Ω

ロジットモデルと等価𝜃𝜃 = (総走行費用制約式の𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿𝐿乗数)

�→最適化問題を解くと𝐸𝐸に応じた𝜃𝜃が自動的に求まる

ロジットモデルでは外生的に与える
12

エントロピー・モデル
 エントロピー・コスト調和モデル

 コスト最小化モデル

経路選択のばらつきを示すパラメータ𝜃𝜃を与える�
エントロピーの観測値𝐻𝐻を与える
min. 𝑍𝑍 𝐟𝐟 = � � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟

sub.to𝑟𝑟𝑟𝑟

𝑘𝑘𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟
�𝑞𝑞𝑟𝑟𝑟𝑟 = � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 , 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ≥ 0 ,− � � 𝑓𝑓𝑘𝑘 ln 𝑓𝑓𝑘𝑘 ≥ 𝐻𝐻𝑘𝑘

𝑟𝑟𝑠𝑠

1
min. 𝑍𝑍 𝐟𝐟 = � � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 + � � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ln 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟𝜃𝜃
sub.to𝑘𝑘𝑟𝑟𝑟𝑟𝑘𝑘𝑟𝑟𝑠𝑠𝑞𝑞𝑟𝑟𝑟𝑟 = � 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 , 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ≥ 0 ,𝑘𝑘𝑘𝑘

いずれも配分結果はロジットモデルと等価になる 各エントロピーモデルの比較

� 𝐻𝐻を観測により推定する必要がある
�→ エントロピー最大化モデルとコスト最小化モデルではそれぞれ𝐸𝐸と𝐟𝐟̃ ：観測交通量パターン
サンプリングのバイアスが無い場合 𝐟𝐟 ∗ = 𝐸𝐸[𝐟𝐟]̃𝐟𝐟 ∗ ： 𝐟𝐟の不偏推定値•

エントロピー最大化モデル

𝐸𝐸 𝐸𝐸� 𝐟𝐟̃

= 𝐸𝐸� 𝐟𝐟 ∗観測による推定値•コスト最小化モデル

� 𝐟𝐟̃
𝐸𝐸 𝐻𝐻

� 𝐟𝐟 ∗< 𝐻𝐻

�
コスト最小化モデルでは𝐻𝐻が過少推定となるバイアスが生じる
加えて推定値の分散がエントロピー最大化モデルより大きくなることが知られている
不偏性・効率性： エントロピー最大化モデル＞ コスト最小化モデル

13

確率的利用者均衡配分の定式化
 確率的利用者均衡状態

もはやどの利用者も経路を変更することによって自己の旅行時間をそれ以上短縮することはできないと信じている均衡状態

観測リンクコスト：

𝐶𝐶𝑖𝑖 = 𝐶𝐶𝑖𝑖 𝑓𝑓𝑖𝑖

経路選択確率： 𝑃𝑃𝑖𝑖 = 𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃. {𝐶𝐶𝑖𝑖 + 𝜉𝜉𝑖𝑖 ≤ 𝐶𝐶𝑗𝑗 + 𝜉𝜉𝑗𝑗 }確率的利用者均衡状態

これらの条件が同時に成立している状態へと収束した定常状態

経路交通量（期待値）： 𝑓𝑓𝑖𝑖 = 𝑞𝑞𝑃𝑃𝑖𝑖•例題ネットワーク
𝐶𝐶1 𝑓𝑓1

確率的均衡配分

𝐶𝐶2 𝑓𝑓214

確率的利用者均衡配分と等価な最適化問題
 等価な最適化問題

確率的利用者均衡配分→確率的配分

＋Wardrop均衡配分（p4）P11~13の3つのエントロピー・モデル•

エントロピー・コスト調和モデル
𝑥𝑥𝑎𝑎

1min. 𝑍𝑍 𝐟𝐟 = � � 𝑡𝑡𝑎𝑎 𝑤𝑤 𝑑𝑑𝑑𝑑 − � 𝑞𝑞𝑟𝑟𝑟𝑟 𝐻𝐻𝑟𝑟𝑟𝑟 𝐟𝐟 𝑟𝑟𝑟𝑟
𝜃𝜃0sub. to𝑎𝑎∈𝐴𝐴𝑟𝑟𝑟𝑟

� 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 − 𝑞𝑞𝑟𝑟𝑟𝑟 = 0 ∀𝑟𝑟𝑟𝑟 ∈ Ω ,𝑘𝑘∈𝐾𝐾𝑟𝑟𝑟𝑟

𝐻𝐻𝑟𝑟𝑟𝑟 𝐟𝐟𝑟𝑟𝑟𝑟

𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟≡ −��ln𝑞𝑞𝑟𝑟𝑟𝑟 𝑞𝑞𝑟𝑟𝑟𝑟
𝑟𝑟𝑠𝑠

𝑘𝑘𝑟𝑟𝑟𝑟 𝑟𝑟𝑟𝑟
𝑥𝑥𝑎𝑎 = � � 𝛿𝛿𝑎𝑎,𝑘𝑘𝑓𝑓𝑘𝑘 ∀𝑎𝑎 ∈ 𝐴𝐴 ,𝑘𝑘∈𝐾𝐾𝑟𝑟𝑟𝑟 𝑟𝑟𝑠𝑠∈Ω𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 ≥ 0, 𝑥𝑥𝑎𝑎 ≥ 0

エントロピー最大化モデル・コスト最小化モデルでも同様に最適化問題を考えることができる

配分交通量(𝐟𝐟 ∗ , 𝐱𝐱 ∗ )が一意に求まる
更に均衡解は次の式を満たす

𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 = 𝑞𝑞𝑟𝑟𝑟𝑟

exp(−𝜃𝜃𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 [𝐱𝐱 𝐟𝐟 ])∑𝑘𝑘 exp(−𝜃𝜃𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 [𝐱𝐱 𝐟𝐟 ])これら3つの最適化問題の均衡解はp11~12と同じ議論により，いずれも解の一意性・ロジット型配分の式を満たしp14の定式化を表現できている

15

確率的利用者均衡配分と等価な最適化問題
 双対問題→ 同一の条件を異なる視点から定式化したもの（厳密な理解は参考文献でお願いします…）（ex）主問題：利潤最大化 ↔ 双対問題：費用最小化

 双対問題からみた確定的/確率的均衡配分
p15のエントロピー・コスト調和モデルを用いた最適化問題から(𝐟𝐟, 𝐱𝐱)を消去し整理（『交通ネットワークの均衡分析』p89~90）

確率的均衡

𝑡𝑡𝑎𝑎

min. 𝑍𝑍𝐷𝐷 𝐭𝐭 = − � �𝑎𝑎∈𝐴𝐴 𝑡𝑡𝑎𝑎 0𝑥𝑥𝑎𝑎 𝑣𝑣 𝑑𝑑𝑣𝑣 + � 𝑞𝑞𝑟𝑟𝑟𝑟 𝑆𝑆𝑟𝑟𝑟𝑟 (𝒄𝒄𝑟𝑟𝑟𝑟 (𝐭𝐭))𝑟𝑟𝑟𝑟

1𝑆𝑆𝑟𝑟𝑟𝑟 𝐜𝐜 𝑟𝑟𝑟𝑟 ≡ − ln � exp(−𝜃𝜃𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 )𝜃𝜃𝑘𝑘

期待最小費用関数（p8）確定的均衡（ 『交通ネットワークの均衡分析』p60 ）𝑡𝑡𝑎𝑎min. 𝑍𝑍𝐷𝐷 𝐭𝐭 = − � �𝑎𝑎∈𝐴𝐴 𝑡𝑡𝑎𝑎 0𝑥𝑥𝑎𝑎 𝑣𝑣 𝑑𝑑𝑣𝑣 + � 𝑞𝑞𝑟𝑟𝑟𝑟 min{𝒄𝒄𝑟𝑟𝑟𝑟 𝐭𝐭 }𝑟𝑟𝑟𝑟𝑘𝑘最小費用関数

 一般のランダム効用理論モデルに基づいた配分→ 期待最小費用関数をモデルに適した関数形にすれば良い
交通量を未知変数とする等価最適化問題はあくまでロジットモデルを前提としたもの

16確率的利用者均衡配分と等価な最適化問題
 双対問題の応用 – 料金設定問題

任意の交通量パターン�
𝐱𝐱を達成する料金設定問題を考える

経路交通量パターン𝐟𝐟： 𝑓𝑓𝑘𝑘𝑟𝑟𝑟𝑟 = 𝑞𝑞𝑟𝑟𝑟𝑟

exp{−𝜃𝜃(𝜔𝜔𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 + 𝐸𝐸𝑘𝑘𝑟𝑟𝑟𝑟 )}∑𝑘𝑘 exp{−𝜃𝜃(𝜔𝜔𝑐𝑐𝑘𝑘𝑟𝑟𝑟𝑟 + 𝐸𝐸𝑘𝑘𝑟𝑟𝑟𝑟 )}

𝑟𝑟𝑟𝑟
𝑟𝑟𝑟𝑟
経路所要時間𝐜𝐜：𝑐𝑐𝑘𝑘 = � 𝑡𝑡𝑎𝑎 (𝑥𝑥𝑎𝑎 )𝛿𝛿𝑎𝑎,𝑘𝑘𝑎𝑎

𝑟𝑟𝑟𝑟
𝑟𝑟𝑟𝑟
経路料金𝐄𝐄： 𝐸𝐸𝑘𝑘 = � 𝑒𝑒𝑎𝑎 𝛿𝛿𝑎𝑎,𝑘𝑘𝑎𝑎

𝑟𝑟𝑟𝑟 𝑟𝑟𝑟𝑟
フローの保存条件：𝑥𝑥𝑎𝑎 = � � 𝑓𝑓𝑘𝑘 𝛿𝛿𝑎𝑎,𝑘𝑘（𝑒𝑒𝑎𝑎 : リンク𝑎𝑎の所要料金
𝑟𝑟𝑠𝑠

𝑘𝑘̂
max. 𝑍𝑍𝐷𝐷 (𝐜𝐜) = − � 𝑥𝑥𝑎𝑎 �𝑐𝑐𝑎𝑎 + � 𝑞𝑞𝑟𝑟𝑟𝑟 𝑆𝑆𝑟𝑟𝑟𝑟 (𝐜𝐜 𝑟𝑟𝑟𝑟 (𝐜𝐜))𝑎𝑎

𝑐𝑐𝑎𝑎 = 𝜔𝜔𝑡𝑡𝑎𝑎 + 𝑒𝑒𝑎𝑎
一般化コスト： �𝑟𝑟𝑠𝑠

これらが同時に成立するようなリンク料
金𝐞𝐞を求める𝜔𝜔: 時間価値）̂ 𝐜𝐜̂ ∗ としてこの最適化問題を𝐱𝐱につ𝐜𝐜をいて解くと𝐱𝐱 = 𝐱𝐱� は上の条件を全て満たし，唯一の均衡解となっている

𝑐𝑐𝑎𝑎 ∗ − 𝜔𝜔𝑡𝑡𝑎𝑎 (𝑥𝑥𝑎𝑎 ) ← 一意性はない
最適料金： 𝑒𝑒𝑎𝑎∗ = �

交通量パターン�𝐱𝐱を達成する料金設定
は複数存在する

17

確率的利用者均衡配分と等価な最適化問題
 等価最適化問題のリンク変数による表現
一般的なネットワークでは経路列挙が難しいため，数値計算のためには経路交通量を用いた定式化はあまり望ましくない
フローの保存条件：
𝑟𝑟𝑟𝑟(𝐹𝐹𝑘𝑘 ≡) � 𝑥𝑥𝑖𝑖𝑖𝑖− � 𝑥𝑥𝑘𝑘𝑘𝑘+ � 𝑞𝑞𝑟𝑟𝑟𝑟 𝛿𝛿𝑟𝑟𝑟𝑟 − 𝑞𝑞𝑟𝑟𝑟𝑟 𝛿𝛿𝑠𝑠𝑠𝑠 = 0 (∀𝑘𝑘 ∈ 𝑁𝑁, ∀𝑟𝑟 ∈ 𝑅𝑅)
𝑖𝑖

リンク交通量を用いて定式化
詳しくは参考文献

𝑗𝑗

𝑠𝑠…..

𝑘𝑘

𝑟𝑟
𝐹𝐹𝑘𝑘 = 0 − � 𝑥𝑥𝑟𝑟𝑗𝑗+ � 𝑞𝑞𝑟𝑟𝑟𝑟
𝑗𝑗𝑥𝑥𝑖𝑖𝑖𝑖

𝑠𝑠𝑟𝑟

𝑟𝑟
sub. to 𝑥𝑥𝑖𝑖𝑖𝑖 = � 𝑥𝑥𝑖𝑖𝑖𝑖∀𝑖𝑖, 𝑗𝑗 ∈ 𝐴𝐴 , 𝑥𝑥𝑖𝑖𝑖𝑖 ≥ 0 ∀𝑖𝑖, 𝑗𝑗 ∈ 𝐴𝐴, ∀𝑟𝑟 ∈ 𝑅𝑅
𝑟𝑟

𝑖𝑖

𝑘𝑘

𝑟𝑟
𝐹𝐹𝑘𝑘 = � 𝑥𝑥𝑖𝑖𝑖𝑖− 0 −𝑞𝑞𝑟𝑟𝑟𝑟

𝑟𝑟
𝑟𝑟
𝐹𝐹𝑘𝑘 = � 𝑥𝑥𝑖𝑖𝑖𝑖− � 𝑥𝑥𝑟𝑟𝑗𝑗

1min. 𝑍𝑍 𝐱𝐱 = � � 𝑡𝑡𝑖𝑖𝑖𝑖 𝑤𝑤 𝑑𝑑𝑑𝑑 − � 𝐻𝐻𝐻𝐻 𝐱𝐱 𝑟𝑟 − 𝐻𝐻𝐻𝐻 𝐱𝐱 𝑟𝑟𝜃𝜃
0𝑖𝑖𝑖𝑖…..

𝑘𝑘𝑖𝑖

𝑗𝑗𝑟𝑟
𝑟𝑟
𝐻𝐻𝐻𝐻 𝐱𝐱 𝑟𝑟 ≡ − � � 𝑥𝑥𝑖𝑖𝑗𝑗
ln � 𝑥𝑥𝑖𝑖𝑖𝑖
𝑗𝑗𝑖𝑖

𝑟𝑟
𝑟𝑟
𝐻𝐻𝐻𝐻 𝐱𝐱 𝑟𝑟 ≡ − � 𝑥𝑥𝑖𝑖𝑖𝑖
ln 𝑥𝑥𝑖𝑖𝑖𝑖
𝑖𝑖𝑖𝑖

𝑖𝑖

18

確率的利用者均衡配分の解法
 等価最適化問題の計算アルゴリズム
確率的配分の解法＊ロジット型確率的配分••

Dialのアルゴリズム→ 経路を限定Markov連鎖配分→ 経路を限定しない＊プロビット型確率的配分•

経路列挙せず，リンク交通量を直接計算するアルゴリ
ズム

モンテカルロシミュレーション

均衡配分の解法＊逐次平均法（MSA：Method of Successive Averages）••

各種配分モデルに対するSUE配分に適用化
収束が遅い

•
•
•

起点別リンク交通量を未知変数とする
ロジット型SUE配分のみ適用化
収束が速い•••

経路交通量を未知変数とするロジット型SUE配分のみ適用化
収束が速い＊部分線形化法＊Simplicial Decomposition法

これらの組み合わせにより確率的利用者均衡配分の均衡解が計算できる

19

確率的利用者均衡配分の解法
 逐次平均法（MSA：Method of Successive Averages）
Frank-Wolfe法（第10回）で予め定数列をステップサイズとする

目的変数に経路変数が含まれているとステップサイズの一次元探索ができない

Step A

𝑛𝑛回目の計算ステップにおいて与えられたリンク交通量ベクトルの点𝑥𝑥 (𝑛𝑛)において目的関数を部分的（積分項）に線形近似し制約条件下で最小化

Step B0. 初期許容解を求める
繰り返し回数: 𝑛𝑛 = 0,リンクコスト:𝑡𝑡𝑖𝑖𝑖𝑖 (0) = 𝑡𝑡𝑖𝑖𝑖𝑖 (𝟎𝟎)
確率的配分を行い𝐱𝐱 (0) を得る

1. リンクコスト更新(𝑛𝑛)𝑡𝑡𝑖𝑖𝑖𝑖 (𝑛𝑛) = 𝑡𝑡𝑖𝑖𝑖𝑖 (𝑥𝑥𝑖𝑖𝑖𝑖 )2. 降下方向ベクトルの計算
リンクコスト𝒕𝒕(𝑛𝑛) に対して確率的配分を行い，配分結果のリンク交通量パターン𝐲𝐲 (𝑛𝑛) を用いて降下方向ベクトル𝐝𝐝(𝑛𝑛) = 𝐲𝐲 (𝑛𝑛) − 𝐱𝐱 (𝑛𝑛) を計算
3. 一次元探索
1
ステップサイズを𝛼𝛼 = で与える

4. 解の更新

𝑛𝑛𝐱𝐱 (𝑛𝑛+1) = 𝐱𝐱 (𝑛𝑛) + 𝛼𝛼𝐝𝐝(𝑛𝑛)5. 収束判定
収束していれば終了，そうでなければ𝑛𝑛 = 𝑛𝑛 + 1とし1.へ

20

確率的利用者均衡配分の解法
 Markov連鎖配分（MCA : Markov Chain Assignment）
𝑔𝑔個の起点， 𝑎𝑎個の終点を含む𝑛𝑛個のノードからなるネットワークを考える
MCAでは各ノードがMarkov連鎖における“状態”に対応し，車は始点からマル
コフ連鎖則に従って分岐を繰り返し，終点に到着すると確率1で吸収される
またMCAでは対象経路を全く限定せず，cycleを含む全ての経路を考えている
𝑎𝑎𝐈𝐈
推移確率行列：𝐏𝐏 =𝐑𝐑

𝑛𝑛 − 𝑎𝑎𝟎𝟎
𝐐𝐐𝑔𝑔𝟎𝟎𝐐𝐐 =𝑛𝑛 − 𝑎𝑎𝟎𝟎

𝑎𝑎𝑛𝑛 − 𝑔𝑔 − 𝑎𝑎

𝐐𝐐𝟏𝟏𝐐𝐐𝟐𝟐𝑔𝑔

𝑛𝑛 − 𝑔𝑔 − 𝑎𝑎Markov連鎖では最初の時点で状態𝑖𝑖にいた車が𝑛𝑛回の状態遷移後に状態𝑗𝑗にいる確率は𝐐𝐐𝑛𝑛 の(𝑖𝑖, 𝑗𝑗)要素(= 𝑝𝑝(𝑗𝑗|𝑖𝑖))で与えられる

起点から発生した車が各ノードにいる確率は

𝐈𝐈 + 𝐐𝐐1 + 𝐐𝐐2 + ⋯ + 𝐐𝐐𝑛𝑛 + ⋯ =𝐈𝐈 − 𝐐𝐐 −𝟏𝟏 =リンク𝑖𝑖𝑖𝑖の選択率は，ノード𝑖𝑖の選択率を𝑃𝑃(𝑖𝑖)として𝑝𝑝𝑖𝑖𝑖𝑖 = 𝑃𝑃(𝑖𝑖)𝑝𝑝(𝑗𝑗|𝑖𝑖)

𝐈𝐈 𝐐𝐐𝟏𝟏 𝐈𝐈 − 𝐐𝐐𝟐𝟐 −𝟏𝟏𝟎𝟎
𝐈𝐈 − 𝐐𝐐𝟐𝟐 −𝟏𝟏𝑔𝑔

𝑛𝑛 − 𝑔𝑔 − 𝑎𝑎21

確率的利用者均衡配分の解法
 ロジットモデルと整合的な推移確率

推移確率を以下の式で与えれば，MCAによるフローパターンはロジット型確率的配分と等価になる∞

𝑉𝑉𝑗𝑗𝑗𝑗𝑝𝑝 𝑗𝑗 𝑖𝑖 = exp −𝜃𝜃𝑡𝑡𝑖𝑖𝑖𝑖(𝑉𝑉𝑖𝑖𝑖𝑖 = � exp[−𝜃𝜃𝑐𝑐𝑘𝑘𝑖𝑖𝑖𝑖 ])𝑉𝑉𝑖𝑖𝑠𝑠𝑘𝑘=1𝑟𝑟𝑟𝑟,𝑛𝑛exp[−𝜃𝜃𝑐𝑐𝑘𝑘𝑟𝑟𝑠𝑠 ]𝛿𝛿𝑖𝑖𝑖𝑖,𝑘𝑘𝑟𝑟𝑟𝑟
𝑃𝑃𝑘𝑘 = � 𝑝𝑝(𝑗𝑗|𝑖𝑖)= ∞∑𝑘𝑘=1 exp[−𝜃𝜃𝑐𝑐𝑘𝑘𝑟𝑟𝑠𝑠 ]𝑖𝑖𝑖𝑖

𝑟𝑟𝑟𝑟,𝑛𝑛𝛿𝛿𝑖𝑖𝑖𝑖,𝑘𝑘= �𝑛𝑛0

𝑂𝑂𝑂𝑂ペア𝑟𝑟𝑟𝑟の𝑘𝑘番目の経路がリンク𝑖𝑖𝑖𝑖を𝑛𝑛回通過
𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑉𝑉𝑖𝑖𝑗𝑗 を要素とする行列𝐕𝐕の評価が必要だが，経路を列挙するような直接的な方法では評価できない

22

確率的利用者均衡配分の解法
 経路を限定しないロジット型配分の計算法
𝐕𝐕をMCAに類似した行列演算により評価
exp[−𝜃𝜃𝑡𝑡𝑖𝑖𝑖𝑖 ]重み行列𝐖𝐖：𝑤𝑤𝑖𝑖𝑖𝑖 = �0𝐖𝐖

𝑛𝑛[𝑛𝑛]: 𝑤𝑤𝑖𝑖𝑖𝑖 =�𝑖𝑖𝑖𝑖𝑘𝑘∈𝐾𝐾𝑛𝑛

𝐕𝐕を𝐖𝐖を用いて表すと∞𝑖𝑖𝑖𝑖

𝐾𝐾𝑛𝑛 : 𝑛𝑛本のリンクを通過してノード𝑖𝑖. 𝑗𝑗を結ぶ経路の集合
𝑖𝑖𝑖𝑖
𝑖𝑖𝑖𝑖
𝑐𝑐𝑘𝑘,𝑛𝑛 : 𝐾𝐾𝑛𝑛 に属する𝑘𝑘番目の経路のコスト

𝑖𝑖𝑖𝑖
exp[−𝜃𝜃𝑐𝑐𝑘𝑘,𝑛𝑛 ]𝑖𝑖𝑗𝑗

𝑉𝑉𝑖𝑖𝑗𝑗 = � exp[−𝜃𝜃𝑐𝑐𝑘𝑘 ]𝑘𝑘=1

ノード𝑖𝑖𝑖𝑖間にリンクが存在
その他

𝐕𝐕 = 𝐖𝐖 + 𝐖𝐖 2 + ⋯𝐖𝐖が収束条件（Hawkins-Simon条件）を満足していると仮定すると

𝐕𝐕 = [𝐈𝐈 − 𝐖𝐖]−1 −𝐈𝐈23

確率的利用者均衡配分の解法
 経路を限定しないロジット型配分の計算法
𝐕𝐕をMCAに類似した行列演算により評価
exp[−𝜃𝜃𝑡𝑡𝑖𝑖𝑖𝑖 ]重み行列𝐖𝐖：𝑤𝑤𝑖𝑖𝑖𝑖 = �0𝐖𝐖

𝑛𝑛[𝑛𝑛]: 𝑤𝑤𝑖𝑖𝑖𝑖 =�𝑖𝑖𝑖𝑖

𝑘𝑘∈𝐾𝐾𝑛𝑛

𝐕𝐕を𝐖𝐖を用いて表すと∞𝑖𝑖𝑖𝑖

𝐾𝐾𝑛𝑛 : 𝑛𝑛本のリンクを通過してノード𝑖𝑖. 𝑗𝑗を結ぶ経路の集合
𝑖𝑖𝑖𝑖
𝑖𝑖𝑖𝑖
𝑐𝑐𝑘𝑘,𝑛𝑛 : 𝐾𝐾𝑛𝑛 に属する𝑘𝑘番目の経路のコスト

𝑖𝑖𝑖𝑖
exp[−𝜃𝜃𝑐𝑐𝑘𝑘,𝑛𝑛 ]𝑖𝑖𝑗𝑗

𝑉𝑉𝑖𝑖𝑗𝑗 = � exp[−𝜃𝜃𝑐𝑐𝑘𝑘 ]𝑘𝑘=1

ノード𝑖𝑖𝑖𝑖間にリンクが存在
その他

𝐕𝐕 = 𝐖𝐖 + 𝐖𝐖 2 + ⋯𝐖𝐖が収束条件（Hawkins-Simon条件）を満足していると仮定すると

𝐕𝐕 = [𝐈𝐈 − 𝐖𝐖]−1 −𝐈𝐈24

確率的利用者均衡配分の解法
 ロジット型確率的配分の手順まとめ
Step 1

推移確率𝐐𝐐 の計算
𝐕𝐕 = [𝐈𝐈 − 𝐖𝐖]−1 −𝐈𝐈の逆行列計算により𝐕𝐕を計算

Step 2

𝑝𝑝 𝑗𝑗 𝑖𝑖 = exp −𝜃𝜃𝑡𝑡𝑖𝑖𝑖𝑖

𝑉𝑉𝑗𝑗𝑗𝑗
により推移確率𝐐𝐐を計算
𝑉𝑉𝑖𝑖𝑖𝑖

Markov配分によりリンク選択率を計算
12𝑛𝑛𝐈𝐈 + 𝐐𝐐 + 𝐐𝐐 + ⋯ + 𝐐𝐐 + ⋯ = 𝐈𝐈 − 𝐐𝐐−𝟏𝟏𝐈𝐈=𝟎𝟎

𝐐𝐐𝟏𝟏 𝐈𝐈 − 𝐐𝐐𝟐𝟐 −𝟏𝟏𝐈𝐈 − 𝐐𝐐𝟐𝟐 −𝟏𝟏

起点別ノード選択率行列から計算

リンク選択率： 𝑝𝑝𝑖𝑖𝑖𝑖 = 𝑃𝑃(𝑖𝑖)𝑝𝑝(𝑗𝑗|𝑖𝑖) を計算
ノード選択率： 𝑃𝑃 𝑟𝑟𝑟𝑟 𝑖𝑖 = 𝑉𝑉𝑟𝑟𝑟𝑟 𝑉𝑉𝑖𝑖𝑖𝑖 /𝑉𝑉𝑟𝑟𝑠𝑠

リンク選択率： 𝑝𝑝𝑖𝑖𝑖𝑖 = 𝑝𝑝 𝑗𝑗 𝑖𝑖 𝑉𝑉𝑟𝑟𝑟𝑟 𝑉𝑉𝑖𝑖𝑖𝑖 ⁄𝑉𝑉𝑟𝑟𝑟𝑟 = 𝑉𝑉𝑟𝑟𝑖𝑖 𝑤𝑤𝑖𝑖𝑖𝑖 𝑉𝑉𝑗𝑗𝑠𝑠 /𝑉𝑉𝑟𝑟𝑟𝑟
リンク交通量： 𝑦𝑦𝑖𝑖𝑖𝑖 = 𝑞𝑞𝑟𝑟𝑠𝑠 𝑝𝑝𝑖𝑖𝑖𝑖 = 𝑞𝑞𝑟𝑟𝑟𝑟 𝑉𝑉𝑟𝑟𝑖𝑖 𝑤𝑤𝑖𝑖𝑖𝑖 𝑉𝑉𝑗𝑗𝑠𝑠 /𝑉𝑉𝑟𝑟𝑟𝑟

25確率的利用者均衡配分の解法
 大規模ネットワークのための計算法

実際の数値計算で～p25で説明した方法を行うには膨大な記憶容量と計算時間を要する

𝑦𝑦𝑖𝑖𝑖𝑖 = 𝑞𝑞𝑟𝑟𝑠𝑠 𝑝𝑝𝑖𝑖𝑖𝑖 = 𝑞𝑞𝑟𝑟𝑟𝑟 𝑉𝑉𝑟𝑟𝑖𝑖 𝑤𝑤𝑖𝑖𝑖𝑖 𝑉𝑉𝑗𝑗𝑠𝑠 /𝑉𝑉𝑟𝑟𝑟𝑟

リンク交通量を計算するために行列𝐕𝐕の全ての要素が必要なわけではない

𝑉𝑉𝑟𝑟𝑟𝑟 , 𝑉𝑉𝑗𝑗𝑗𝑗 （リンク起終点がそれぞれ発生・集中ノード）が計算できれば良い

p25の方程式を起点別（or終点別）に分解して解く

Step 1

行列𝐖𝐖 = [𝑊𝑊𝑖𝑖𝑖𝑖 ]の設定

𝑊𝑊𝑖𝑖𝑖𝑖 = exp −𝜃𝜃𝑡𝑡𝑖𝑖𝑖𝑖(∀(𝑖𝑖, 𝑗𝑗) ∈ 𝐴𝐴)

各起点𝑟𝑟 ∈ 𝑅𝑅について以下の線形連立方程式を解き，𝐕𝐕𝑟𝑟 = [𝑉𝑉𝑟𝑟𝑟 , … , 𝑉𝑉𝑟𝑟𝑟𝑟 ]を算出

Step 2A[𝐈𝐈 − 𝐖𝐖]𝑇𝑇 𝐕𝐕𝑟𝑟𝑇𝑇 = 𝐖𝐖𝑟𝑟𝑇𝑇 (� 𝛿𝛿𝑖𝑖𝑖𝑖 − 𝑊𝑊𝑖𝑖𝑖𝑖 𝑉𝑉𝑟𝑟𝑟𝑟 = 𝑊𝑊𝑟𝑟𝑟𝑟 )𝑖𝑖

Step 3

𝐕𝐕𝑟𝑟𝑠𝑠 = 𝑉𝑉𝑟𝑟𝑠𝑠 を算出

𝑉𝑉𝑟𝑟𝑟𝑟 = 𝑉𝑉𝑟𝑟𝑗𝑗 ′ (𝑗𝑗 ′ は𝑠𝑠に接続するノード)

Step 4

リンク交通量を計算

𝑦𝑦𝑖𝑖𝑖𝑖 = 𝑞𝑞𝑟𝑟𝑟𝑟 𝑉𝑉𝑟𝑟𝑖𝑖 𝑤𝑤𝑖𝑖𝑖𝑖 𝑉𝑉𝑗𝑗𝑠𝑠 /𝑉𝑉𝑟𝑟𝑟𝑟

各起点𝑠𝑠 ∈ 𝑆𝑆について以下の線形連立方程式を解き，𝐕𝐕𝑠𝑠 = [𝑉𝑉1𝑆𝑆 , … , 𝑉𝑉𝑛𝑛𝑛𝑛 ]𝑇𝑇 を算出

Step 2B

𝐈𝐈 − 𝐖𝐖 𝐕𝐕𝑠𝑠 = 𝐖𝐖𝑠𝑠 (� 𝛿𝛿𝑖𝑖𝑖𝑖 − 𝑊𝑊𝑖𝑖𝑖𝑖 𝑉𝑉𝑗𝑗𝑗𝑗 = 𝑊𝑊𝑖𝑖𝑖𝑖 )𝑗𝑗

26

確率的利用者均衡配分の解法
 Markov連鎖配分の問題点•••

ネットワークの構造によっては，非常に非現実に過大なcycle flowが発生する
行列𝐖𝐖の収束条件が満たされず解が発散する↑非常に小さいコストを持つリンクが接続してcycleを形成する場合に起こりやすい
IIA特性が増幅される場合がある（細街路と1本のバイパスからなるネットワークを考えると，経路数が多い細街路が過剰推計される）↑均衡配分を考えることで緩和される

27

参考文献

28