第12回基礎ゼミ
第5章 利用者均衡モデル

2017年6月13日（火）福田研究室 B4五百藏夏穂コンテンツ1. リンクコスト関数

1.1 利用者均衡モデル
1.2 システム最適化配分
1.3 利用者均衡とシステム最適化のパラドックス

2. ベクトル・リンクコスト関数
2.1 NCP,VIP,FPPによる利用者均衡配分
2.2 VIPを用いた利用者均衡配分の表現
2.3 均衡解の安定性

2

1.1

利用者均衡モデル

利用者均衡解の定式化
wardropの利用者均衡

最も所要時間の少ない経路を選択結果として起終点間に存在する経路のうち利用される経路の所要時間はみな等しく、利用されていない経路の所要時間より小さいか、せいぜい等しい

定式化
f𝑘𝑟𝑠 > 0のとき 𝑐𝑘𝑟𝑠 = 𝑐𝑟𝑠∀𝑘 ∈ 𝐾𝑟𝑠 ∀𝑟𝑠 ∈ Ωf𝑘𝑟𝑠 (𝑐𝑘𝑟𝑠 −𝑐𝑟𝑠 ) = 0f𝑘𝑟𝑠 = 0のとき 𝑐𝑘𝑟𝑠 ≥ 𝑐𝑟𝑠∀𝑘 ∈ 𝐾𝑟𝑠 ∀𝑟𝑠 ∈ Ω(𝑐𝑘𝑟𝑠 −𝑐𝑟𝑠 ) ≥ 0

制約条件
𝑟𝑠𝑘∈𝐾𝑟𝑠 f𝑘 − Q 𝑟𝑠 = 0 ∀𝑟𝑠 ∈ Ω𝑓𝑘𝑟𝑠 ≥ 0 ∀𝑘 ∈ 𝐾𝑟𝑠 ∀𝑟𝑠 ∈ Ωf𝑘𝑟𝑠 :ODペアrs間第k経路の経路交通量
𝑐𝑘𝑟𝑠 :ODペアrs間第k経路の経路所要時間
𝑐𝑟𝑠 :ODペアrs間の最短経路所要時間
Q 𝑟𝑠 :ODペアrs間の分布交通量3利用者均衡モデル

1.1

利用者均衡解の定式化
経路→ネットワーク𝑐𝑘𝑟𝑠 =𝑟𝑠
𝛿𝑎,𝑘𝑡𝑎 𝑥𝑎 = 0𝑎∈𝐴𝑟𝑠 𝑟𝑠
𝛿𝑎,𝑘𝑓𝑘𝑥𝑎 =𝑘∈𝐾𝑟𝑠 𝑟𝑠∈Ω∀𝑘 ∈ 𝐾𝑟𝑠 ∀𝑟𝑠 ∈ Ω 𝑡 𝑥 :リンクaのリンクコスト関数
𝑎 𝑎𝑥𝑎 :リンクaのリンク交通量
𝑟𝑠 1: ODペアrs間経路がリンク𝑎を含むとき
𝛿𝑎,𝑘:∀𝑎 ∈ 𝐴0: そうでないとき

経路122ex)𝑐112 =12𝑎∈𝐴 𝛿𝑎,2 𝑡𝑎 𝑥𝑎= 𝑡1 𝑥1 + 𝑡2 𝑥2 +𝑡8 𝑥8 +𝑡6 𝑥6

𝑐121 =

21𝑎∈𝐴 𝛿𝑎,1 𝑡𝑎 𝑥𝑎= 𝑡4 𝑥4 + 𝑡7 𝑥7 +𝑡2 𝑥2 +𝑡3 𝑥3𝑥2 =𝑘∈𝐾𝑟𝑠

21𝑟𝑠 𝑟𝑠
1221𝑟𝑠∈Ω 𝛿2,𝑘 𝑓𝑘 = 𝑓2 +𝑓1

O
1
O2
経路211

4

7

5

38

D
1
6

D
24

利用者均衡モデル

1.1

等価な最適化問題への変換
𝑚𝑖𝑛. 𝑍𝑝 =𝑥𝑎𝑎∈𝐴 0𝑡𝑎 𝑤 𝑑𝑤

Lagrangian関数
L(f,λ)=𝑍𝑝 𝑓 −制約条件

𝑓𝑘𝑟𝑠 ≥ 0𝑟𝑠𝑘∈𝐾𝑟𝑠 f𝑘 − Q 𝑟𝑠 = 0𝑥𝑎 =𝑓𝑘𝑟𝑠 ≥ 0𝑟𝑠𝑟𝑠∈Ω λ𝑟𝑠 ( 𝑘∈𝐾 f𝑘 − Q 𝑟𝑠 )𝑘∈𝐾𝑟𝑠

∀𝑟𝑠 ∈ Ω𝑟𝑠 𝑟𝑠𝑟𝑠∈Ω 𝛿𝑎,𝑘 𝑓𝑘𝑥𝑎 ≥ 0
最適化∀𝑎 ∈ 𝐴

Kuhn-Tucker条件
𝑓𝑘𝑟𝑠

𝜕𝐿(𝑓∗,λ∗)f𝜕 𝑘𝑟𝑠

𝜕𝐿(𝑓 ∗, λ ∗)𝜕λ𝑟𝑠＝０ and 𝑓𝑘𝑟𝑠
=0𝜕𝐿(𝑓∗,λ∗)f𝜕 𝑘𝑟𝑠≥0𝑓𝑘𝑟𝑠 ≥ 0 ∀𝑘, ∀𝑟𝑠∀𝑟𝑠⋮※P42,43参照

f𝑘𝑟𝑠 > 0のとき 𝑐𝑘𝑟𝑠 = λ𝑟𝑠∀𝑘 ∈ 𝐾𝑟𝑠 ∀𝑟𝑠 ∈ Ωf𝑘𝑟𝑠 = 0のとき 𝑐𝑘𝑟𝑠 ≥ λ𝑟𝑠∀𝑘 ∈ 𝐾𝑟𝑠 ∀𝑟𝑠 ∈ Ω

利用者均衡の定義と同じ
5

利用者均衡モデル

1.1

定式化

単純なネットワーク配分の例

𝑚𝑖𝑛. 𝑍𝑝 =5𝑓1 + 0.05𝑓12 + 10𝑓2 + 0.0125𝑓22 + 1015 + 0.0125𝑓32
s.t.

𝑓𝑘 ≥ 0Lagrangian関数

経路3OD交通量
Q = 200台

経路2
経路1

経路所要時間t（分）3𝑘=1 𝑓𝑘 = 200

経路1L(f,λ)=5𝑓1 + 0.05𝑓12 + 10𝑓2 + 0.0125𝑓22 + 1015 + 0.0125𝑓32 − λ( f𝑘 − 200)
𝑓𝑘 ≥ 0Kuhn-Tucker条件
5 + 0.1𝑓1 = λ (𝑓1 ≥ 0 ) , 5 + 0.1𝑓1 ≥ λ(𝑓1 = 0 )20
経路2100100200

交通量f（台）

𝑡1 = 5 + 0.1𝑓1
𝑡2 = 10 + 0.025𝑓2
𝑡3 = 15 + 0.025𝑓3

10 + 0.025𝑓2 = λ (𝑓2 ≥ 0 ) , 10 + 0.025𝑓2 ≥ λ(𝑓2 = 0 )15 + 0.025𝑓3 = λ (𝑓3 ≥ 0 ) , 15 + 0.025𝑓2 ≥ λ(𝑓3 = 0 )3𝑓𝑘 − 200 = 0
𝑘=1

所要時間の短い経路からKuhn-Tucker条件を調べて経路1,2が利用されるとき最適解
𝑓1 =80, 𝑓2 =120, 𝑓3 =0

𝑍 =2100

𝑡3 = 15分 ≥ 𝑡1 = 𝑡2 = λ=13分

6

1.1

利用者均衡モデル
証明

解の一意性

𝜕Zp
𝜕xa

= 𝑡𝑎 (𝑥𝑎 )∀𝑎 ∈ 𝐴𝑑𝑡𝑎 𝑥𝑎> 0 (𝑎 = 𝑏)
=𝑑𝑥𝑎0 (𝑎 ≠ 𝑏)∀𝑎 ∈ 𝐴𝜕2Zp
制約条件式によって示される変数の実行可能領域が凸でかつ目的関数が狭義の凸関数であればよい・制約条件式が全て線形→変数の実行可能領域の凸性
・目的関数Zが狭義凸関数→リンク交通量に関する二次のHessian行列が整定値行列

𝜕xa

Hessian行列は以下のようになる
𝑑𝑡1 𝑥1⋯𝑑𝑥1⋮⋱0⋮

𝑑𝑡𝑛 𝑥𝑛𝑑𝑥𝑛⋯

リンクコスト関数は単調増加より

𝑑𝑡𝑎 𝑥𝑎>0𝑑𝑥𝑎
任意のベクトルh ≠0について以下が成り立つので正定値
ただしこれはリンク交通量に関してのみ

0𝑡ℎ∀𝑎 ∈ 𝐴

𝛻 2 𝑍𝑝 ℎ =ℎ𝑎2 ∙𝑎∈𝐴

𝑑𝑡𝑎 𝑥𝑎>0𝑑𝑥𝑎

7

1.2

システム最適化配分

システム最適化配分
道路網における総走行時間が最小となるように配分する
𝑚𝑖𝑛. 𝑍𝑠 =𝑥𝑎 𝑡𝑎 (𝑥𝑎 )𝑚𝑖𝑛. 𝑍𝑠 =𝑎∈𝐴

制約条件
𝑟𝑠𝑘∈𝐾𝑟𝑠 f𝑘 − Q 𝑟𝑠 = 0 ∀𝑟𝑠 ∈ Ω𝑥𝑎 =𝑓𝑘𝑟𝑠 ≥ 0𝑘∈𝐾𝑟𝑠

𝑟𝑠 𝑟𝑠𝑟𝑠∈Ω 𝛿𝑎,𝑘 𝑓𝑘𝑥𝑎 ≥ 0=𝑥𝑎[𝑎∈𝐴 0𝑥𝑎𝑎∈𝐴 0 [𝑡𝑎 𝑤+𝑑 𝑤・𝑡𝑎 𝑤] dw𝑑𝑤
𝑤・𝑑 𝑡𝑎 𝑤
𝑑𝑤] dw∀𝑎 ∈ 𝐴

利用者均衡配分と同様に積分形→同じアルゴリズムで解ける

8

1.2

システム最適化配分

混雑料金政策
利用者均衡配分：ドライバー個人の費用（私的限界費用）最小化
道路利用者全体の最適化にはならない
システム最適化配分：道路利用者全体の費用（社会的限界費用）最小化（社会的限界費用）ー（私的限界費用）＝（混雑料金）

システム最適化
需要曲線
c

社会的余剰

社会的限界費用曲線a

私的限界費用曲線b

私的限界費用曲線

混雑料金𝑤・𝑑 𝑡𝑎 𝑤
𝑡𝑎 𝑤 +𝑑𝑤
社会的限界費用曲線

𝑄𝑎 𝑄𝑏

9

1.3 利用者均衡とシステム最適化のパラドックス
交通政策におけるパラドックス①Brassのパラドックス
新規道路建設によるサービスレベルの悪化

OD交通量：600台

1O
235
D
4𝑓1 = 300 𝑓2 = 300
𝑐1 = 83 𝑐2 = 83

𝑡1 = 50 + 0.01𝑥1𝑡2 = 0.1𝑥2𝑡3 = 50 + 0.01𝑥3
𝑡4 = 0.1𝑥4

𝑡5 = 10 + 0.01𝑥5
総所要時間：498台・分UEの目的関数：399

𝑓1 = 200 𝑓2 = 200 𝑓3 = 200
𝑐1 = 92 𝑐2 = 92 𝑐3 = 92
総所要時間：552台・分UEの目的関数：386
総旅行時間が10大きくなってしまった1.3 利用者均衡とシステム最適化のパラドックス
交通政策におけるパラドックス②Smithのパラドックス
信号制御等の交通規制によるサービスレベルの悪化
2台/秒
1000
LEI
𝑓1
𝑓2
𝑡1 =100(1+𝑓2 )

1台/秒

E’

I’
1000

L

3台/秒

C
𝑡2 = 300(3+𝑓1 )C’

ネットワークの総所要時間

8800
8200
7600

V=V(F,L)=2000𝑓2 +100(1+𝑓2 )2 + 2𝐿𝑓1 +300(3+𝑓1 )2
制御する地点の交通を多くするためLを最小値a
交通流全体として最適にならない

Va 300b700

L112.1

NCP,VIP,FPPによる利用者均衡配分

相補性問題・変分不等式問題・不動点問題
リンクコスト関数がほかのリンクの交通量にも依存する
𝑡𝑎= 𝑡𝑎 𝑥1 , … , 𝑥𝑎 , … 𝑥𝐿∀𝑎 ∈ 𝐴

ベクトル・リンクコスト関数(リンクコスト写像)𝑡 𝑥 : 𝑅+𝐿 → 𝑅+𝐿

12

2.1

NCP,VIP,FPPによる利用者均衡配分

まず経路交通量と経路コストのみで考える
経路コストは一般にその経路の交通量だけでなくほかのさまざまな交通量の影響も受ける

𝐶𝑘𝑟𝑠 = 𝐶𝑘𝑟𝑠 (𝑓)複雑な関数
等価最適化問題を構成困難

利用者均衡条件
𝑓𝑘𝑟𝑠 ∙ 𝐶𝑘𝑟𝑠 𝑓 − 𝑢𝑟𝑠 = 0
𝐶𝑘𝑟𝑠 𝑓 − 𝑢𝑟𝑠 ≥ 0 𝑓𝑘𝑟𝑠 ≥ 0𝑟𝑠𝑘∈𝐾𝑟𝑠 f𝑘 = 𝑞𝑟𝑠

凸計画問題（CPP）を一般化した問題の利用∀𝑘 ∈ 𝐾𝑟𝑠 ∀𝑟𝑠 ∈ 𝑊∀𝑟𝑠 ∈ 𝑊・非線形相補性問題（NCP）
・変分不等式問題（VIP）
・不動点問題（FPP）
13

2.1

NCP,VIP,FPPによる利用者均衡配分

非線形相補性問題（NCP）
標準系の相補性問題
Find 𝑥 ∈ 𝑅+𝑛 𝑠. 𝑡 𝑥 ∙ 𝐹 𝑥 = 0, 𝑥 ≥ 0 𝐹(𝑥) ≥ 0
利用者均衡の式を置き換え相補性問題に
𝑓𝑘𝑟𝑠 ∙ 𝐶𝑘𝑟𝑠 𝑓 − 𝑢𝑟𝑠
𝐶𝑘𝑟𝑠 𝑓 − 𝑢𝑟𝑠 ≥ 0=0𝑓𝑘𝑟𝑠 ≥ 0f𝑘𝑟𝑠 − 𝑞𝑟𝑠 ) = 0𝑢𝑟𝑠 (𝑘∈𝐾𝑟𝑠∀𝑟𝑠 ∈ 𝑊f𝑘𝑟𝑠 − 𝑞𝑟𝑠 ≥ 0 , 𝑢𝑟𝑠 ≥ 0𝑘∈𝐾𝑟𝑠

全ての条件が相補性形式でかつ変数(f,u)の許容領域が非負実数空間𝑅+K × 𝑅+M （𝑀: 全ODペア数, K：全経路数）

利用者均衡配分は以下の標準系の非線形相補性問題と等価【UE/FD-NCP】
Find 𝑥 = 𝑓, 𝑢 ∈ 𝑅+K × 𝑅+M
𝑠. 𝑡 𝑥 ∙ 𝐹 𝑥 = 0, 𝑥 ≥ 0 𝐹(𝑥) ≥ 014

2.1

NCP,VIP,FPPによる利用者均衡配分

変分不等式問題（VIP）

ベクトル場Fが凸集合Ωに直行している点を求める問題

変分不等式問題

Find 𝑥 ∈ Ω 𝑠. 𝑡 F x ∙ 𝑦 − 𝑥 = 0 , ∀𝑦 ∈ Ω
VIPはNCPを特殊形として含んだ一般的枠組み→Ωを非実数空間𝑅+𝑛 とすればVIP(F, 𝑅+𝑛 )はNCP(F)と等価
利用者均衡配分は以下のVIPと等価【UE/FD-VIP】
Find 𝑥 ∗= 𝑓 ∗, 𝑢 ∗ ∈ Ω ≡ 𝑅+K × 𝑅+M
𝑠. 𝑡 F x ∗ ∙ 𝑥 − x ∗ ≥ 0 , ∀𝑥 ∈ Ω𝐶𝑘𝑟𝑠 𝑓 ∗ − 𝑢 ∗𝑟𝑠 ∙ (f𝑘𝑟𝑠 − f𝑘𝑟𝑠∗ ) +𝑟𝑠𝑘∗
f𝑘𝑟𝑠 − 𝑞𝑟𝑠 ∙ (𝑢𝑟𝑠 − 𝑢𝑟𝑠)≥0(𝑟𝑠𝑘∀(𝑓, 𝑢) ∈ 𝑅+K × 𝑅+M

F(X*)
X*
X*-F(X*)
15

2.1

NCP,VIP,FPPによる利用者均衡配分

不動点問題（FPP）
不動点問題

F𝑖𝑛𝑑 𝑥 ∈ Ωs.t. X=𝑃𝑟𝑜𝑗Ω,Q (x − Q−1 F(x))F(x)がΩに直行している点を求める問題

写像演算子は以下のように定義される
𝑃𝑟𝑜𝑗Ω,Q x=arg.min.{(z-x)・Q(z-x) s.t.z ∈ Ω}
非負実数空間Ωでは射影は以下の演算に帰着する
𝑃𝑟𝑜𝑗𝑅K,M ,Q (x-F(x))=[x − Q−1 F(x)]Ω=𝑅+2F(X)

F(X*)

+X
【UE/FD-FPP】
Find 𝑥 = 𝑓, 𝑢 ∈ 𝑅+K × 𝑅+M
𝑠. 𝑡 𝑥 = [x − Q−1 F(x)]+𝑃𝑟𝑜𝑗Ω X-F(X)X*

X*-F(X*)

X-F(X)
16

2.2

VIPを用いた利用者均衡配分の表現

VIPとしてのいくつかの表現‐主問題（交通量変数）
経路変数
ｆおよびf*がフロー保存条件と非負条件を満たした凸領域Ω𝑝0 に属する
𝑞𝑟𝑠 = 𝑘∈𝐾𝑟𝑠 f𝑘𝑟𝑠 ∀𝑟𝑠 ∈ 𝑊𝑓𝑘𝑟𝑠 ≥ 0 ∀𝑘 ∈ 𝐾𝑟𝑠 ∀𝑟𝑠 ∈ 𝑊【UE/FD-VIP】より第一項のみ残り
𝑟𝑠𝑟𝑠𝑘 𝐶𝑘 𝑓 ∗− 𝑢 ∗𝑟𝑠 ∙ (f𝑘𝑟𝑠 − f𝑘𝑟𝑠∗ ) ≥ 0 ∀f,f* ∈ Ω𝑝0𝑟𝑠𝑟𝑠𝑟𝑠∗𝑘 𝑢 ∗𝑟𝑠 (f𝑘 − f𝑘 ) =𝑟𝑠𝑟𝑠𝑘 𝐶𝑘 𝑓 ∗𝑟𝑠 𝑢 ∗𝑟𝑠 ( 𝑞𝑟𝑠 − 𝑞𝑟𝑠 ) = 0∀f,f* ∈ Ω𝑝0
したがって経路交通量パターン𝑓 ∗が【UE/FD-VIP】の解であるならば∙ (f𝑘𝑟𝑠 − f𝑘𝑟𝑠∗ ) ≥ 0※逆もまたしかり

利用者均衡配分問題は変分不等式問題VIP(c, Ω𝑝0 )と等価

17

2.2VIPを用いた利用者均衡配分の表現
リンク変数
𝑐𝑘𝑟𝑠 =𝑟𝑠
𝛿𝑎,𝑘𝑡𝑎𝑎∈𝐴

ネットワーク全体の総走行費用は経路、リンクどちらについて足し合わせても変わらない
𝐶𝑘𝑟𝑠 𝑓𝑟𝑠𝑘∙ f𝑘𝑟𝑠 =𝑡𝑎 (𝑥) ∙ 𝑥𝑎𝑎∈𝐴

これより以下のVIPが得られる【UE/FD-VIP-Priminal】
Find 𝑥 ∗∈ Ω𝑝0𝑡𝑎 (𝑥 ∗) ∙ (𝑥𝑎 − 𝑥𝑎∗ ) ≥ 0 , ∀𝑥 ∈ Ω𝑝0𝑠. 𝑡𝑎∈𝐴※Ω𝑝0 はフロー保存条件式、非負条件と以下の経路交通量とリンク交通量の関係式を満たしたリンク交通量ベクトルの集合
182.2

VIPを用いた利用者均衡配分の表現
VIPとしてのいくつかの表現‐相対問題（コスト変数）【UE/FD-VIP】の領域をΩからΩD0 に置き換えたVIP(F, ΩD0 )ΩD0 = 𝑓, 𝑢 |𝑢𝑟𝑠 ≤ 𝐶𝑘𝑟𝑠 𝑓 ∀𝑘, ∀𝑟𝑠【UE/FD-VIP】 の解はΩD0 に属するのでVIP(F, ΩD0 ) は【UE/FD-VIP】 と等価

任意の(f,u)∈ ΩD0 で【UE/FD−VIP】が成立するには、f=f*として【UE/FD-VIP】の左辺第一項が消え𝑟𝑠∗∗𝑟𝑠( 𝑘 f𝑘 − 𝑞𝑟𝑠 ∙ (𝑢𝑟𝑠 − 𝑢𝑟𝑠 ) ≥ 0 ∀(f,u) ∈ ΩD0
リンクコスト関数の逆関数が存在するなら利用者均衡配分は以下のVIPとして表現できる⋮Ω𝐷0 は以下の条件を満たす集合
𝑢𝑟𝑠 ≤𝑟𝑠𝑎∈𝐴 𝛿𝑎,𝑘 𝑡𝑎∀𝑘 ∈ 𝐾𝑟𝑠 ∀𝑟𝑠 ∈ 𝑊【UE/FD-VIP-Dual】
Find (𝑡 ∗, 𝑢 ∗) ∈ ΩD0𝑡𝑎−1 𝑡 ∗ ∙ 𝑡𝑎 − 𝑡𝑎∗ −𝑠. 𝑡𝑎∈𝐴𝑞𝑟𝑠 ( 𝑢𝑟𝑠 − 𝑢 ∗𝑟𝑠 ) ≥ 0 , ∀(𝑡, 𝑢) ∈ Ω𝐷0𝑟𝑠∈𝑊192.2

VIPを用いた利用者均衡配分の表現

利用者均衡配分と最適化問題
Ωは閉凸集合,f(x):Ω→R1 が連続で微分可能な凸関数とするとCPP(f, Ω)の解とVIP(𝛻𝑓, Ω)の解は一致
CPP(f, Ω)とVIP(𝛻𝑓, Ω)は等価【UE/FD-Priminal】【UE/FD-Priminal】
𝑚𝑖𝑛. 𝑍𝑃 𝑥 =𝑥𝑎𝑎∈𝐴 0𝑡𝑎 𝜔 𝑑𝜔

【UE/FD-Dual】【UE/FD-Dual】
𝑚𝑎𝑥. 𝑍𝐷 𝑡 =𝑟𝑠𝑡𝑎 𝛿𝑎,𝑘𝑞𝑟𝑠 min𝑟𝑒∈𝑊𝑘∈𝐾𝑟𝑠𝑎∈𝐿−𝑡𝑎𝑎∈𝐴 𝑡𝑎(0)𝑥𝑎 𝑣 𝑑𝑣
20

2.2

VIPを用いた利用者均衡配分の表現

最適化問題【UE/FD-Priminal】と【UE/FD-Dual】の目的関数間の関係性・双対性定理

両問題の最適状態では目的関数ZPと 𝑍𝐷 の値は完全に一致する※ネットワーク全体の総走行費用が𝑥𝑎 𝑡𝑎 =𝑎∈𝐴𝑟𝑠𝑡𝑎 𝛿𝑎,𝑘𝑞𝑟𝑠 min𝑟𝑒∈𝑊𝑘∈𝐾𝑟𝑠𝑎∈𝐿※任意の(x,t)について
𝑥𝑎𝑎∈𝐴 0 𝑡𝑎 𝜔 𝑑𝜔 =𝑎∈𝐴 𝑥𝑎 𝑡𝑎 −𝑡𝑎𝑎∈𝐴 𝑡𝑎(0) 𝑥𝑎 𝑣 𝑑𝑣・弱双対定理
両方、あるいはいずれかの問題が最適に到達していない状態では、ZP のほうが𝑍𝐷 よりも大きい※利用者均衡状態でない(x,t)に対して常に以下が成立しているため
𝑥𝑎 𝑡𝑎 >𝑎∈𝐴

𝑟𝑠𝑡𝑎 𝛿𝑎,𝑘𝑞𝑟𝑠 min𝑟𝑒∈𝑊𝑘∈𝐾𝑟𝑠𝑎∈𝐿21

2.2

VIPを用いた利用者均衡配分の表現

均衡解の一意性𝑅𝑛 の部分集合Ω上でF: Ω →Ωが狭義単調減少
𝐹 𝑥 −𝐹 𝑥∙ 𝑥 − 𝑦 > 0 ∀𝑥, 𝑦 ∈ Ω, 𝑥 ≠ 𝑦

利用者均衡配分と等価な【UE/FD-VIP-Priminal】

が成立するなら、VIP(F,Ω)の解は唯一

定理：連続・微分可能なリンクコスト写像を持つ利用者均衡配分問題では、その均衡リンク交通量はリンクコスト写像のJacobianが正定値であれば一意的に求まる
ただしリンクコスト写像が単調でない場合は複数の均衡解が存在しうる
22

2.3

均衡解の安定性
利用者均衡配分の安定性
複数の均衡解が存在する場合、意味のある解を求めるために安定性を確認→利用者均衡状態に至るまでの過程を動的システムとして定式化①Lyapunov安定的な配分調整プロセス
コストが高い経路ほどコストの低い経路へ移動する

簡単のためODペアが一つの場合
利用者均衡状態
f*∈ Ω𝑝0 𝑎𝑛𝑑 𝑓𝑘′ [𝑐𝑘 f∗ − 𝑐𝑙 f∗ ]+ = 0∀𝑘 ≠ 𝑙 ∈ 𝐾

交通量変化
Φ𝑘 𝑓 = −𝑓𝑘 [𝑐𝑘 f − 𝑐𝑙 f ]+ +𝑘≠𝑙

𝑓𝑙 [𝑐𝑙 f − 𝑐𝑘 f ]+𝑘≠𝑙

移出

移入23

2.3

均衡解の安定性

𝑓 𝑡 = Φ 𝑓(𝑡)𝑓𝑜𝑟 𝑡 > 0

任意のtで微分可能で上式を満たすf(t)動的システムの解＝均衡解
動的システムの安定性の定義
動的システムが安定→任意の𝑓0 ∈ Ω𝑃0 に対して、初期値をf(0)=𝑓0 とする動的システムの解がt→∞で空でない均衡集合に収束する→以下の条件を満たす連続・微分可能なLyapunov関数Vが存在・V(f)≥ 0 ∀𝑓 ∈ Ω𝑃0
・fが均衡解である (𝑓 𝑡 = 0)↔ V(f)=0・fが均衡解でない (𝑓 𝑡 ≠ 0)↔ 𝛻V(f)∙ Φ 𝑓 <024

2.3

均衡解の安定性例
V(f) =𝑘𝑘≠𝑙 𝑓𝑘 [𝑐𝑘 f− 𝑐𝑙 f ]2+

𝑓𝑜𝑟 𝑓 ∈ Ω𝑃0→1,2を満たす
C(f)が連続・微分可能ならVも微分可能
C(f)が𝑅+K, 上で単調なら→3を満たす

リンクコスト関数が連続・微分可能で単調ならば動的システムは安定である→任意の初期値から出発し動的システムに従って変化する交通量パターンは必ず利用者均衡配分状態へ収束する

25

2.3

均衡解の安定性②Gap関数に基づいた配分調整プロセス
Gap関数：G 𝑥 = max 𝑡(𝑥)∙ (𝑥 − 𝑦)𝑦∈Ω𝑝均衡解からの離れの度合いを示す指標【UE/FD-VIP-Priminal】は min G 𝑥 と等価ｘ∈Ω𝑝→簡単に解けない
Gap関数を滑らかに再定義
G𝑞 𝑥 = 𝑡 𝑥 𝑥 − 𝐻 𝑥− 1/2 𝐻 𝑥 − 𝑥 𝑄(𝐻 𝑥 − 𝑥)t(x)が連続・微分可能ならG𝑞 𝑥 も連続・微分可能＊G𝑞 𝑥 は以下のような動的システムのLyapunov関数
𝑥 𝑡 = Φ(x(t)) for t>0
Φ(x)≡ 𝐻 𝑥 − 𝑥→安定性が保証される
26