1. No category

Friesz, T.L., Luque, J., Tobin, R.L., Wie, B-W.:
Dynamic network traffic assignment
considered as a continuous time optimal control problem,
Operations Research, Vol. 37(6), pp. 893-901, 1989.
Nonlinear Pricing and Revenue Optimization
Freight Systems and Logistics
Dynamic Network Games and Dynamic Traffic Assignment
Network Design and MPECs
2014/6/27(金)
集中理論談話会 #4
D2 浦田 淳司
論文目次
研究概要：
・動的交通配分の定式化
・Pontryaginの最大値原理の導入
・システム最適，ワードロップ均衡(利用者最適)のそれぞれで定式化
＋Dynamic Control Problem (Pntryagin’s maximum principle)のエッセンス
1. Notation, Dynamics and Constraints
2. System Optimization
3. User Optimization
4. Conclusions
2
動学的問題への3つのアプローチ
著：A.C. チャン (訳：小田正雄, 仙波憲一，高森寛，平澤憲男)
動学的最適化の基礎，シーエーピー出版, 2006
1. 動的計画法（Bellman, R.E.(1953)）
- 多段階意思決定モデル / 再帰的計算過程
2. 変分法（Newton，I(1687)）
- 最適関数の決定問題(最速降下曲線など)
T
max V ( y ) = ∫ F (t , y (t ), y ' (t ))dt
0
subject to y (0) = A, y (T ) = Z
3. 最適制御理論（Pontryagin，L.S. et al.(1962)）
- 変分法の進化
- 時間変数t, 状態変数y(t)に加えて，制御変数u(t)を追加
3
最適制御理論(Dynamic Control Problem)
状態変数
制御変数
=
,…,
= { ,…,
目的関数 maxV = max
等価
…,
…,
, ,
連続（区分的に微分可能，鋭点あり）
}( ) 非連続可（区分的に連続）
制約条件
=
,
,
運動方程式
(yは初期条件と運動方程式で決定)
初期条件
0 =
,…, …,
0
終端条件
自由 （制約を設定することも可能）
制御集合 u
∈!
最大値原理（ハミルトニアンHの最大化）
, , + ∑' &' ' , ,
H≡
max ( , , , & ∀
yについての運動方程式
λについての運動方程式
横断性条件
&
=0
+
=
=
*
+
*
・制御変数の最適な時間経路が決定
・時間積分を各時間帯ごとの最適化
計算に分解
・制御変数は非連続でも可
4
(制約条件)交通量変化率
研究概要：
・動的交通配分の定式化
・Pontryaginの最大値原理の導入
・システム最適，ワードロップ均衡(利用者最適)のそれぞれで定式化
,(-, .)：ノードN，リンクAで形成されるネットワーク
ノードNのうちnを終着点ノード，M={1,2,…,n-1}は発ノード．
t ： 時刻 t ∈ 0,
12 ( )：時刻tでのリンクa上の交通量＝状態変数
32 [12 ( )]：交通量12 ( )のときの旅行時間コスト
2 ( )：リンクaへの流入交通量＝制御変数
62 [12 ( )]：リンクaからの流出交通量
交通量変化率
（制約条件）
dxa (t )
= ua (t ) − g a [ xa (t )] ∀a, ∀t
dt
（1）
運動方程式：制御変数 を決めると，状態変数xが決まる
1. Notation, Dynamics and Constraints
5
(制約条件)交通量保存則，基本条件
S8 ( )：時刻tでのノードkからの発生交通量
.(9)：ノードkが着点となるリンク集合
:(9)：ノードkが発点となるリンク集合
交通量保存則 S k (t ) =
（制約条件）
基本条件
（制約条件）
∑u
a∈ A ( k )
a
(t ) −
∑ g [ x (t )] ∀k ∈ M , ∀t （2）
a∈B ( k )
a
xa (0) = xa0 ∀a
（3）
ua (t ) ≥ 0 ∀a, ∀t
（4）
xa (t ) ≥ 0 ∀a, ∀t
（5）
a
定義 Ω ≡ {( x, u ) : (1), (2), (3), (4) are satisfied }
1. Notation, Dynamics and Constraints
（6）
6
Definition 1
動的交通配分が成立するには次の条件を満足すればよい．
1. SOにおいて，その瞬間のコスト関数 C2 [12 ( )]は 非負，単調増加，微分可能，
凸である．これをすべてのa, tで成立し，12 ( ) ≥ 0を満たす．
2. UEにおいて，その瞬間のコスト関数=2 [12 ( )]は正，単調増加，微分可能，で
あり，合成関数 >2 12
= =2 [12 ( )]6′2 [12 ( )]で 表せる．これをすべてのa,
tで成立し，12 ( ) ≥ 0を満たす．
3. 流出関数62 [12 ]は非負，微分可能，単調増加，凹である．これをすべての
a, tで成立し，12 ( ) ≥ 0を満たす．
4. 初期条件62 0 = 0がすべてのa,tで成立する．
5. 初期条件12 0 ≥ 0がすべてのaで成立する．
=2 [12 ( )]：時刻tでの交通量ｘのリンクaでの旅行時間(1台あたり)
定義
1. Notation, Dynamics and Constraints
Ca ( xa ) ≡ ca ( xa ) g a ( xa ) ∀a
7
ハミルトニアン(2. System Optimization)
システム最適の目的関数
>@A@>@BC D = E F 32 12
H IJC=
（7）
2∈G
K (1, ) ∈ Ω
（全期間全リンクの旅行時間の合計の最小化）
ハミルトニアンの定義
( 1, , M,
= E 32 (12 ) + E M2 [
2∈G
2∈G
2
− 62 12 ]
（8）
M2 : 随伴変数(状態方程式に対するラグランジュ乗数)
- (8)式が解を持つには，Arrow-Kurzの十分定理より，Hが凸であることが必要
- Hが凸であるためには，M2 ≥ 0 (∀P)であることが求められる．
2. System Optimization
8
ラグラジアン・KKT条件
制御変数の制約条件(2)(4)を考慮して，Hの最小化問題に対し，ラグラジアンを設定
Q = ( + E R8 S8 − E
8∈U
2∈G 8
2
+ E 62 (12 ) + E V2 [−
2∈G
2∈T 8
2]
（11）
R8 , V2 : ラグランジュ乗数
Lの最小化問題
必要十分条件
KKT条件
（12）
M2 − R8 − V2 = 0
∀P ∈ .(9), ∀9 ∈ W, ∀ ∈ [0, ]
（13）
V2 ≥ 0, 2 ≥ 0, V2 2 = 0
∀P ∈ ., ∀ ∈ [0, ]
R8 ≥ 0, R8 S8 − ∑2∈G 8 2 + ∑2∈T 8 62 12 = 0∀9 ∈ W, ∀ ∈ [0, ] （14）
Eular-Lagrange方程式より
YQ
（15）
−M2X =
∀P ∈ ., ∀ ∈ [0, ]
Y12
∀P ∈ :(9), ∀9 ∈ W, ∀ ∈ [0, ]
−M2X = 32Z − M2 6Z 2 + R8 6Z 2
横断性条件
2. System Optimization
M2
=0
∀P ∈ .
（17）
（16）
※ ・はt微分，’はx微分を示す
9
最適制御問題の必要条件の再定式化
M2 ≥ R8
∀P ∈ .(9), ∀9 ∈ W, ∀ ∈ [0, ]
（18）
（17）より
M2
∀P ∈ .(9)
（19）
（16）より
−M2X = 32Z − M2 6Z 2 + R8 6Z 2 ∀P ∈ :(9), ∀9 ∈ W, ∀ ∈ [0, ]
（12）（13）より
（12）（13）より
2
=0
M2 − R8 = 0 ∀9, P,
（20）
∀P ∈ .(9), ∀9 ∈ W, ∀ ∈ [0, ]
（21）
(14)と(18)より， M2 ≥ 0 が成立するため，Hは凸であり，解を持つ．
(18)(21)より，制御変数
これを求めたい．
2. System Optimization
2は
M2 − R8 = 0のときに0でない値をとる．
10
制御変数の算出
M2 − R8 = 0が∀P, 9で成立することが必要
M2X ( ) = R8X ( )
M2[
= R8[
K\ ∈
,
]
⊆ [0, ]
（22）
(22)を(20)に代入
（23）
(τ a − µl ) g 'a −C 'a − µɺ k = 0
(τɺa − µɺ l ) g 'a +(τ a − µl ) g "a xɺ a − C"a xɺa − µɺɺk = 0
（24） （(23)をｘで微分）
(22)(24)(1)より
ua
[
( µ k − µl ) g"a −C"a ]g a − ( µɺ k − µɺ l ) g 'a + µɺɺk
=
( µ k − µl ) g"a −C"a
（26）
(26)式または0で，制御変数は与えられる．
2. System Optimization
11
交通量保存則の証明
(7)式が満たされれば(18-21)，交通量保存則が満たされることを示す
S k (t ) =
交通量保存則
（制約条件）
∑u
a∈ A ( k )
a
(t ) −
∑ g [ x (t )] ∀a, ∀t
a∈B ( k )
a
a
（2）
証明
あるkにおいて，保存則が成立していないと仮定し，背理法で示す
(14)式より R8 = 0
(18)式より M2 ≥ R8 = 0 ∀P
case i) M2 = R8 = 0の場合
M2 ( ) = 0より，MX 2 ( ) = 0
式(20)より， 0 = 32Z + R_ 6Z 2 ∀ , P = (9, ∀`)
Def1より，32Z と6Z 2 は正なので R_ < 0． これは(14)式と矛盾
case ii) M2 > R8 = 0の場合
S k (t ) +
2
∑ g [ x (t )] < ∑ u (t ) ∀k ∈ M , ∀t
a∈B ( k )
a
a
a∈ A ( k )
a
= 0 (∀P = (9, `))なので，
Sk +
∑ g [ x (t )] < 0 ∀k ∈ M , ∀t
a∈B ( k )
a
a
S8 , 62 (12 )は非負なので矛盾． 以上により，交通量保存則は成立∎
2. System Optimization
12
経路表現を用いた定式化とその解釈
ここでの疑問は，制御変数と状態変数は，通常のシステム最適の交通流と一致するのか．
ノードkからノードnまでの経路pを考える．
d = 9 = e , P , e , … , efg , Pf , ef = A
それぞれの経路で次が成立する．
Φp = ∑
(C 'a +τɺa )
a∈ p
D∗ [1
g 'a
（31）
静的システム最適における
32Z
i6Z
2 フローのリンクaにおける限界費用
動的な
MX 2
i6Z
2 フローのリンクaにおける限界費用
（32）
, ]を最適軌跡に従ったシステム最適の目的関数とすると，
フロー：単位時間あたり交通量
∂J1*[ x(t ), t ]
τa =
∂xa
∀P, ∀
フロー増分あたりの
経路総コストの増分[cost・t/veh]

 ∂J1*  
d
  g 'a
Φ p = ∑  C 'a + 
dt  ∂xa  
a∈ p 
経路pのフロー
の限界費用
2. System Optimization
1台増あたりの
総コストの増分[cost/veh]
（33）
（34）
1台増あたりの
フローの増分[1/t]
13
フローの限界費用と解の導出
定理：
∃ ∈ 0, , 2 > 0 ∀P ∈ d ∈ k8 において，
Φm
= @A Φn : ∀\ ∈ k8 となり，これはDefinition 1の解となる
証明：
式(20)より
Φp = ∑
(C 'a +τɺa )
a∈ p
ここで，式(18)より
m
g 'a
= ∑ (τ ai − µ vi )
i =1
τ a ≥ µ v ∀i
i
（35）
i −1
（36）
m
(35)(36)より
Φ p ≥ ∑ ( µ vi−1 − µ vi ) = µ v0 − µ vm = µ k − µ n
（37）
i =1
> 0では，式(21)より式(36)は等号が成立する必要があり，
Φm は式(37)の下界を解とする．
2
⇒ここでは，利用される経路の時刻tでの限界費用は，
経路候補の中での最小値であることを意味し，静的システム最適の概念と一致
2. System Optimization
14
DUE
同様の証明を目的関数を変えて実施
pq
>@A@>@BC D] = E F F 32 o2 6′2 o2
2∈G
H IJC=
( 1, , M,
= E F 32 o2 6′2 o2
2∈G
Q = ( + E R8 S8 − E
3. User Optimization
（38）
K (1, ) ∈ Ω
pq
8∈U
o2
2∈G 8
2
o2
+ E M2 [
2∈G
2
− 62 12 ]
+ E 62 (12 ) + E V2 [−
2∈T 8
2∈G
2]
（39）
（41）
15
まとめ
・動的交通配分における連続時間の最適制御問題は
静的配分における配分の考え方を保存している
・多くの定式化を行ったが，ひとつの定式化を出発点としている
・出発時刻選択，最適課金，，などに拡張可能
・複数目的地の場合はFIFO原則が保たれないという課題
⇒”exit function”は流入交通流率とリンク旅行時間の関係が非考慮 (桑原(2005)，赤松(2007))
所感
・動学配分の問題が解を持つことを示したい
→最適制御理論による定式化が可能（旅行時間最小化と運動方程式，制約）
→最適制御問題が解を持つことを示せばよい
・（動的）交通配分も初期値が決まれば解が一意に決まるので，運動方程式ではない
のか．．避難の問題で，目安としての最適解が求められる．
・（動的）制御変数と状態変数をどうするか．運動方程式として記述可能か．
→状態変数は流出台数と流入台数．
→制御変数は出発時刻，チェイン選択率
4. Conclusion
16
ご清聴ありがとうございました．
17
TRｃの式1(Nested Dynamic Discrete Choice)
時間割引率
スケールパラメータ
選択確率（時刻t, Pair Set g）
exp((u ( S g ,t ) + βυ ( S g ,t ) ) σ ) exp(σ ln RL ,t )
P ( d t | S g , t ; θ ) = P ( d t | L, S g , t ; θ ) P ( L , S g , t ; θ ) =
RL , t
∑L ' exp(σ ln RL ',t )
選択結果 上位ネスト パラメータ
ログサム
RL ,t = ∑ g∈L exp((u ( S g ,t ) + βυ ( S g ,t ) ) σ )
(2)
υ (d t , S g ,t ) = ∑S υ ( S g ,t +1 ) p( S g ,t +1 | d t , S g ,t )
(3)
v(d t , S g ,t ) = u (d t , S g ,t ) + σε t (d t ) + ε t ( L) + βυ (d t , S g ,t )
(4)
(1)
推移確率
将来価値
g ,t
価値関数
利他差
Network Utility
t期でintra g内
のリンクが形成
形成あり効用
形成なし効用
同調性(集中性)

l g ,t  1
dam
dam
intra
intra
inter
inter

θ
δ
θ
δ
θ
S g ,t ( d t ) = m 
|
x
−
x
|
+
ln
k
+
ln
k
∑
4
j ,t
g ,t
g
g ,t
 N ij∈g 1 i ,t
 g 3
g


inter
S g ,t (d t ) = S g ,t (d t = (l g ,t −1 + 1, k gintra
(6)
,t −1 + 1, k g ,t −1 ))
1
u ( d t , S g ,t ) = S g ,t ( d t ) +
Ng
危険度
rain
5 t
u ( d t , S g ,t ) = θ x
(5)
形成コスト
dis
(7)
2 ij
∑θ x
ij∈g
root
(8)
Nest L
m
l g ,t
Ng
形成による利他差の縮小
g内の一定時間以内の形成数
g内のpair数
δ gintra , δ ginter
gがintraかinterか
k
intra
g ,t
,k
inter
g ,t
g内の形成数
xijdis
ij間距離
xtrain
当該時間帯の雨量
xidam
,t
iのダメージ
making pair
Non-make
Pair Set g
Intra A
Inter A&B
…
Pair ij
a1-a2
Intra B
a1-a3
a2-a3
a1-b1
a1-b2
a1-b3 … a3-b3
b1-b2
b1-b3
b2-b3
18
TRc の式
効用関数
Pair Cost
new pair
Pair Altruism
Majority Tuning 同調
time
previous pair
non-make
t-1
state
st −1
DP
time
Future Utility
Pair Utility
non-make
t
state
st
空間的準拠集団形成
time
non-make
t+1
Network Utility
state
st +1
Spatial Stochastic
Choice Set
Observed
time
non-make
t+2
state
Choice
st + 2
Latent
pair
Inter Pairs of A & B
a1
node
a3
b1
b2
nest
b3
Intra Pairs of A
Intra Pairs of B
a1
b1
A
a2
B
a) Dividing Basic Group
b2
a3
a2
b3
b) Dividing Intra and Inter Pairs by basic groups
++. Omake
19
TRｃの式2 (Tuning Effect)
選択確率（時刻t, Pair Set g）
exp((u ( S g ,t ) + βυ ( S g ,t ) ) σ ) exp(σ ln RL ,t )
P ( d t | S g , t ; θ ) = P ( d t | L, S g , t ; θ ) P ( L , S g , t ; θ ) =
RL , t
∑L ' exp(σ ln RL ',t )
Network Utility
 1
S g ,t ( d t ) = m 
N
 g
= O1 + θ ' ln k g ,t
l g ,t
exp((u ( S g ,t ) + βυ ( S g ,t ) ) σ )
RL ,t
∑θ
ij∈g
1
dam
i ,t
|x
−x
= exp(u ( S g ,t ) σ )

|  + δ gintraθ 3 ln k gintra
+ δ ginterθ 4 ln k ginter
,
t
,t


dam
j ,t
exp(βυ ( S g ,t ) σ )
RL , t
[
] O
= [exp(θ ' ln k )exp(O )]
= exp(θ ' ln k g ,t + O1 )
1σ
2
1σ
g ,t
1
[ ( ( ))] O O
= (k ) O O = (k )
= exp ln k g ,t
1σ
θ'
3
θ' 1σ
g ,t
2
θ' σ
3
適応度モデル
P(vi ) =
ノードe のリンク形成確率
O2
2
g ,t
O3O2
η i ki
∑ jη j k j
20