Urban Transportation Network
Yosef Sheffi
1985
Chap.1＆Chap.2(pp.1~pp.55)
2014 /5/1

スタートアップゼミ#1B4 森部伸一
1

「Urban Transportion Network」
について
渋滞と移動に関する意思決定の相互作用のモデル化

都市交通ネットワークにおける移動パターンを求め方

図１－Sheffi2Contents• Chap.1 Urban Transport Network Analysis
・均衡分析 （Equilibrium Analysis）
・ネットワーク表現→都市交通ネットワークにおける均衡• Chap.2 Basic Concepts in Minimization Problems
・１変数における最小化問題
・多変数における最小化問題
3

Chap.1
Urban Transport Network Analysis
・均衡分析 （Equilibrium Analysis）
・ネットワーク表現→都市交通ネットワークにおける均衡

4

都市交通に対するsystem approach
もともとは、一つの要素に関して別々に分析していた(ex.信号機・交差点のデザイン・駐車規制）
規模の大きい計画になると波及効果などの様々な要素を考慮に入れないといけない(ex.幹線道路の拡張)計画による影響を広い範囲で考慮するために全体を俯瞰するようなアプローチが(ex.最適化)が必要になった5

均衡(equilibrium)について １
市場における例(supply functionとdemand function)

図２－需要関数と供給関数

6

均衡(equilibrium)について ２
ガソリンスタンドにおける例(performance functionとdemand function)

図３－performance/demand function

水色：ガソリンの配給機材を増やしたとき
赤色：値段を上げたとき

7ネットワーク表現 １
NodeとLinkとPath

図４－ネットワーク表現の例“Impedance”(インピーダンス)
Linkごとの抵抗(時間・お金)のことを指す
PathとしてのインピーダンスはLinkのインピーダン
スの和→これがPathを選択する基準になる

8

ネットワーク表現 ２CentroidとConnectorとはCentroid：
出発地や目的地になるNodeのこと(Centroid) Connector
Centroidと外部のノードを結ぶ

9

交通ネットワークにおける均衡 １
Link Performance Function

インピーダンスには時間を使用
移動時間がどのPathでも等しくなったときに、均衡状態

10

交通ネットワークにおける均衡 ２
計算例
q’≧q のとき全員Link1を使う

q’＜q のときどうなるのか？

11

交通ネットワークにおける均衡 ３

12Chap1. まとめ
Performance関数とdemand関数による均衡
ネットワークはLinkとNodeによって形成されるLinkはimpedanceをもつ
交通ネットワークでは、Performance関数を使うことで均衡状態が求められる

13

Chap.2
Basic Concepts in Minimization Problem
・１変数における最小化問題
制約条件なし/制約条件あり
・多変数における最小化問題
制約条件なし/制約条件あり

14

はじめに

以下の章では・制約条件を満たすｘは少なくとも一つは存在・ｘが有限の場合、最小値も有限• 目的関数や制約条件は連続微分可能15

１変数における最小化問題 １
制約条件なし＜１変数最小値問題の解法
min z(x)＞∗𝑑𝑧(𝒙 )
=0 となる点(停留点：stationary point)を𝑑𝑥

求める

下に凸な関数か調べる
極小値(local minimum)のうち、どれが最小値なのかを求める
16

１変数における最小化問題 ２
制約条件なし下に狭義の凸(strictly convex)である条件
a. z[𝜃𝑥1 + (1 − 𝜃)𝑥2 ] < 𝜃𝑧(𝑥1 ) + (1 − 𝜃)𝑧(𝑥2 )b. z 𝑥1 +𝑑𝑧(𝑥1 )(𝑥2 −𝑥1 ) < 𝑧(𝑥2 )𝑑𝑥

𝑑 2 𝑧(𝑥 ∗ )c.
>0𝑑𝑥 217

１変数における最小化問題 3
制約条件なし最小値の決定について極小値が複数ある場合は比較して最小値を求めるが、極小値が一つならそれが最小値になる
では、極小値が一つであること示す条件とは？
→すべてのｘにおいて、（広義の意味で）下に凸の関数であること

18

１変数における最小化問題 ４
制約条件あり＜制約条件付きの場合＞
最小値の必要条件
𝜕𝑔𝑗 (𝑥 ∗ )𝜕𝑧 𝑥 ∗・=𝑢𝑗
𝜕𝑥𝜕𝑥𝑗・ 𝑢𝑗 ≥ 0・ 𝑢𝑗 ∗ 𝑏𝑗 − 𝑔𝑗 (𝑥 ∗ ) = 0・ 𝑏𝑗 − 𝑔𝑗 (𝑥 ∗ ) ≥ 019

１変数における最小化問題 ５
制約条件あり制約条件： g1(x)=x≧a’
グラフ[b]g2(x)=-x≧-a”
グラフ[c]

制約条件gj(x)の境界上で最小値になる場合、以下のような特徴が存在

ujは非負

20

１変数における最小化問題 ６
制約条件あり前のスライドの特徴より
𝜕𝑧 𝑥 ∗・ 𝜕𝑥=𝑗 𝑢𝑗

𝜕𝑔𝑗 (𝑥 ∗ )𝜕𝑥・・・①・ 𝑢𝑗 ≥ 0 ・・・②・ 𝑢𝑗 ∗ 𝑏𝑗 − 𝑔𝑗 (𝑥 ∗ ) = 0 ・・・③・ 𝑏𝑗 − 𝑔𝑗 𝑥 ∗ ≥ 0 ・・・④がつくられた(i)ある制約条件の境界上で最小値を取る場合
その制約条件に対応するujのみ0より大きい数をとることによって①～④の条件を満たす(ii)制約条件の境界の内部で最小値を取る場合
すべてのujを0とすることで、①～④の条件を満たす①～④式は、最小値の必要条件

21

多変数における最小化問題 １
制約条件なし停留点stationary pointである必要条件は
𝛻𝑧 𝒙∗

𝜕𝑧 𝒙∗ 𝜕𝑧 𝒙∗
𝜕𝑧 𝒙∗
=,,…,
𝜕𝑥1
𝜕𝑥2
𝜕𝑥𝐼

=𝟎

22

多変数における最小化問題 2
制約条件なし停留点(stationary point)が極小値であるための条件
・z[𝜃𝒙′ + 1 − 𝜃 𝒙′′] < 𝜃𝑧(𝒙′) + (1 − 𝜃)𝑧(𝒙′′)・z 𝒙′ + 𝛻𝑧 𝒙′ ∙ (𝒙′′ − 𝒙′) 𝑇 < 𝑧(𝒙′′)・𝛻 2 𝑧 𝑥 ∗ が正値であること

23

多変数における最小化問題 ３上をヘッセ行列という。実対称行列の一種。
・行列Hが正値ならば、ゼロベクトル以外の任意のベクトルhに対してh・H・h𝑇 >0が成立する
実対称行列において固有値がすべて正⇔正値行列24

多変数における最小化問題 ４＜制約条件がある場合＞
最小値の必要条件(クーン・タッカー条件式)
𝜕𝑔𝑗 (𝒙∗ )
𝜕𝑓 𝒙∗
=𝑢𝑗 ∗
𝜕𝑥𝑖
𝜕𝑥𝑖𝑗𝑢𝑗 ≥ 0𝑢𝑗 ∗ 𝑏𝑗 − 𝑔𝑗 (𝒙∗ ) = 0

𝑏𝑗 − 𝑔𝑗 (𝒙∗ ) ≥ 0

25

クーンタッカー条件 計算例１

クーンタッカー条件

26

クーンタッカー条件 計算例２
u=0は条件を満たさない

27

特殊な制約条件の場合
Nonnegativity Constraints
非負条件の場合(ｘ≧0)
一次変数で考えると[a]のとき[b]のときが必要条件となる多変数の場合28

まとめ
1変数と多変数の最小化問題の必要条件をしっかり理解することが大切
特に、制約条件ありの場合の多変数最小化問
題の必要条件はクーンタッカ―条件であり、今後の章で大事になってくる29