pp.55
交通量配分手法(Traffic Assignment Method)
①OD交通需要関数
②交通ネットワーク
③リンクパフォーマンス関数
→ 各リンク，経路交通量やサービス水準を求める手法
＊Flow Independent配分
＊静的交通量配分
＊確定的交通量配分
＊利用者均衡配分




＊ Flow Dependent配分
＊動的交通量配分
＊確率的交通量配分
＊システム最適配分
[1] 利用者均衡(user
equilibrium)
仮説１） 利用者は常に最早経路を選択する．
仮説２） 利用者は利用経路に関する完全な情報を得ている．
hi ：経路ｉの交通量
ti ：経路ｉの所要時間
t1=a1+b1h1 a1 > 0, b1 > 0
t2=a2+ b2h2 a2 > 0, b2 > 0
h1+h2 =q
t1(q)>a2, t2(q)>a1 ⇒ 直線は交点を持つ
[数理最適化問題4.1](1)
2 xa
min z ( x(h))    ta ( w)dw
a 1 0
s.t.
h
a1
a
q
ha  0
ラグランジェ関数
L(h, u)  z(h)  u(q  ha )
クーン・タッカー条件（必要条件）
L
hi
 hi (ti (hi )  u )  0　i  1,2
hi
L
 ti (hi )  u  0　i  1,2
hi
[数理最適化問題4.1](2)
L
 ti (hi )  u  0　hi
i  1,2
if　hi  0, then　ti (hi )  u　i  1,2
if　ti (hi )  u, then　hi  0　i  1,2
利用者均衡：おのおののODペアが利用者均衡状態にあるならば，
そのとき利用されている経路の所要時間は全て等しく，利用され
ていない経路の所要時間より小さいか，せいぜい等しい
[数理最適化問題4.2](1)
単一ODから複数ODへの拡張
xa
min z ( x(h))    t a ( w)dw
aL 0
k h  qrs
rs
k
ただし， xa 
xa :
hkrs :
qrs :
akrs :
hkrs  0
rs rs

rs k ak hk
リンクaの交通量
ODペアrsのk番目経路の交通量
ODペアrsのOD交通量
ODペアrsの経路行列の要素
ラグランジェ関数
L(h, u)  z( x(h))   urs (qrs   hkrs )
rs
クーン・タッカー条件（必要条件）
hkrs (Ckrs  urs )  0
Ckrs  urs  0
ただし，
hkrs  q rs
hkrs  0
Ckrs   akrs ta ( xa ) は，ODペアrsのk番目経路の所要時間
urs は，OD間の最少所要時間をあらわす
urs  C (h )
urs  C (h* )
rs
k
rs
k
*
if
if
*rs
k
*rs
k
h 0
h 0
目的関数は，リンクパフォーマンス関数が単調増加ならば，リンク
交通量に関して厳密な凸関数であり，解が一意的に求まる．しか
し，経路交通量に関しては，厳密な凸関数ではなく，解が一意的
に求まらない．
リンク交通量が与えらても，それを満足する経路交通量は無数
に存在，確定した値を求めることはできない．（演習問題4.4）
問4.4
図4.12に与えられたリンク交通量を満足する経路交通量が無数に
存在することを示せ．
[2] システム最適配分法
pp.70
ネットワーク利用者の総所要費用が最小となるような配分方法
総所要費用
T   ta ( xa )  xa
a
dT ：リンクａの交通量が微小に増加したときの総交通費用の増加分
ta ( xa )
dT  {ta ( xa ) 
xa }dxa
xa
m t( xa ) ：限界費用関数(marginal cost function)
リンクａの交通量が微小に増加したときの総交通費用の
増加する割合を表す関数
ta ( xa )
dT
m t( xa ) 
 ta ( xa ) 
xa
dxa
xa
(4.8)
第一項：新たに加わった利用者１台当たりの平均費用
第二項：利用者が新たに加わることによる他の利用者の費用の増加
ta ( xa )
dT
m t( xa ) 
 ta ( xa ) 
xa
dxa
xa
限界費用曲線
平均費用関数は単調増加関数


xa
0
dta ( xa )
0
dxa
 mt( xa )  ta ( xa )
m t( xa )dxa ： そのリンクを走行する車両
すべての総走行費用
2 xa
min z ( x(h))    ta ( w)dw
a 1 0

a
0
m t( xa )  xa  ta ( xa )
[4.1]
pp.68
利用者均衡v.s.システム最適配分
利用者均衡(UE)とシステム最適配分(SO)の配分結果は異なる
各自の行動に任せておくと社会全体の効率は最適にはならない
施策により利用者均衡状態からシステム最適状態へ移行させる
ドライバー：平均費用を考慮して行動
⇒利用者均衡状態
社会全体で増加する限界を考慮
⇒システム最適状態
Load Pricing:混雑時に負荷料金を課す
ta ( xa )
xa
xa
混雑現象：すべてのドライバーが原因者
4.2 交通量配分手法
[3] All-or-Nothing 配分法
：OD間の最短経路にOD交通量をすべて配分(all)し，
その他の経路には全く配分しない(notthing)方法．
pp.72
問4.6
問4.6 解答(1)
t1=50+x1
t2=50+x2
t3=10x3
t4=10x4
t*1 +t*4 = t*2 +t*3
50+x*1 + 10x*4 =50+x*2+10x*3
h*1 = x*1 = x*4
h*2 = x*2 = x*3
50+h*1 + 10 h*1 =50+ h*2 +10h*2
11 h*1 =11h*2 h*1 = h*2
q= h*1 + h*2 =6
h*1 = h*2 =3
x*1 = x*2 = x*3 = x*4=3
c1 = c2 = 83, TC=498
問4.6 解答(2)
t1=50+x1 t2=50+x2 t3=10x3 t4=10x4 t5=10+x5
t*1 +t*4 = t*2 +t*3 = t*3 +t*5+t*4
50+x*1 + 10x*4 =50+x*2+10x*3 =10x*3 +10+x*5 +10x*4
h*1 = x*1 = x*4- h*3
h*2 = x*2 = x*3 - h*3
h*3 = x*5
50+h*1 + 10( h*1 +h*3) =50+ h*2 +10(h*2 +h*3)
50+ h*2 +10(h*2 +h*3) =10 (h*2 +h*3) +10+ h*3 +10 ( h*1 +h*3)
h*1 = h*2= h*3
q= h*1 + h*2 + h*3 =6
h*1 = h*2 = h*2 =2
x*1 = 2, x*2 =2, x*3 =4, x*4=4, x*5=2
c1 = c2 =c3 =92, TC=552
問4.6 解答(3)
新たな道路建設により、
総交通費用が増加！！
総交通費用 498
②
①
③
552
④
IC
2.2 最短経路探索法
［ ５ ］ 最短経路探索アルゴリズム
1）最短経路配分の簡単な例
1
4
3
2
1
3
5
5
2
5
3
4
7
6
3
6
4
5
8
3
9
発ノード①、
着ノード⑦⑧⑨
ｑ17=10、ｑ18=5
ｑ19=20
ｑrs：
ｔij：
Ｃrsp：
ｆrsp：
ＯＤ交通量
リンクコスト
経路コスト
経路交通量
Ｃrsp(ODペアｒｓのｐ番目の経路の交通費用)
その経路上のリンクijのリンクコストｔijの和
Ｃrsp = Σｔijδrsij,p
δrsij,p：リンクｉｊがＯＤペアｒｓのｐ番目の経路上にあれば１、な
ければ０となるリンク−経路結合行列（の要素）
ex.Ｃ172=ｔ12+ｔ25+ｔ57=4+3+2=9
各ＯＤペアの全経路とその経路費用
①②④⑦ Ｃ171=10
①②④⑦⑨
①②⑤⑦ Ｃ172=9
①②⑤⑦⑨
①③⑤⑦ Ｃ173=10
①③⑤⑦⑨
①②⑤⑧ Ｃ181=10
①②⑤⑧⑨
①③⑤⑧ Ｃ182=11
①③⑤⑧⑨
①③⑥⑧ Ｃ183=12
①②⑥⑧⑨
経路交通量 ｆrsp
ｆ172=ｑ17=10， ｆ171=ｆ173=0
ｆ181=ｑ18=5 ， ｆ182=ｆ183=0
ｆ194=ｑ19=20 ， ｆ171=ｆ172=ｆ173=ｆ175=ｆ176=0
Ｃ191=16
Ｃ192=15
Ｃ193=16
Ｃ194=13
Ｃ195=14
Ｃ196=15
リンク交通量ｘ
:そのリンクを通過する経路の交通量を重ね合わせたもの
ｘij =ΣΣｆrspδrsij,p
rs ｐ
ｘ58 =ｆ181+ｆ182+ｆ194+ｆ195 =5+0+20+0=25
最短経路の交通量を重ね合わせることによって、すべてのリンク
交通量を計算すれば、最短経路配分の計算は完了。
ｘ12=35
ｘ13=0
ｘ24=0
ｘ25=35
ｘ35=0
ｘ36=0
ｘ47=0
ｘ57=10
ｘ58=25
ｘ68=0
ｘ79=0
ｘ89=20
（1）最短経路配分
すべての経路を列挙することは,実際のネットワークではまず無理。
↓
最短経路探索アルゴリズム
a.ラベル確定法（Label Setting Method）
各繰り返し計算において、１つ以上のラベルを確定していく。
＜リンクコストが非負でなければならない＞
a.ラベル確定法（Label Setting Method）
永久ラベル(permanent label) Ｐ
一時ラベル(temporary label) Ｔ 、起点ｒ
step0:[初期値設定]
①永久ラベル、一時ラベル集合の初期設定
起点ｒを永久ラベル、その他の点を一時ラベル
Ｐ←ｒ、Ｔ←Ｎ−{ｒ}
②ラベルの初期値設定
ｄ(ｊ)←0
if ｊ＝ｒ
ｄ(ｊ)←ｔrj
if (r,j)∈Ａ
ｄ(ｊ)←∞
otherwise
③先行ポインタの初期値設定
pred(ｊ)←r
if (r,j)∈Ａ
pred(ｊ)←0
otherwise
step1:[ノード選択]
Ｔからラベルの値が最小なノードｉをＰに移す
ｄ(ｉ)＝min｛ｄ(ｊ)：j∈Ｔ｝
→ Ｐ←Ｐ∪{ｉ}
、Ｔ←Ｔ−{ｉ}
step2:[ラベル更新]
リンクｉ→ｊ∈Ａ の終点ｊについて
ｄ(ｊ)＞ｄ(ｉ)+ｔijならばｄ(ｊ)←ｄ(ｉ)+ｔij、pred(ｊ)←ｉ
step3:[終了条件]
Ｐ＝Ｎならば終了、
そうでなければstep1へ
d(i):起点ｒからの最短距離
最短経路：ノードｉから先行ポインタを遡っていけばよい。
最短経路配分のアルゴリ
ズム
ＯＤペア毎に、最短経路に配分する。
ＯＤペアを通し番号で区別し、その総数はＮ。
step0:[初期値設定]
ｎ←1、ｘij←0 for all ij
step1:[最短経路探索]
ｎ番目のＯＤペアについて、最短経路を探索し、その最短
経路上のリンク番号を集合Ａｎを記録
step2:[ＯＤ交通量の配分]
リンク(i,j)∈ＡｎのＯＤペア別交通量ｙijの値をＯＤペアｎの
ＯＤ交通量とする。
ｙij←ｑrs for (i,j)∈Ａｎ
step3:[リンク交通量の合算]
ｘij←ｘij+ｙij for (i,j)∈Ａｎ
step4:[終了条件]
n= Nならば終了、
そうでなければn=n+1とし、step1へ
【国家公務員試験（Ⅰ
種）】
Ａ～Ｄの４地域が図のような道路網で連絡されている。それぞ
れの地域の距離は図に示すとおりである。いま、ｍ−ｎ間を結ぶ
新道を建設したい。新道での走行速度は現在の道路の２倍とす
ると、新道への転換交通量は次のうちどれか。ただし、すべての
車は時間的に最短の経路を通るものとし、Ａ～Ｄそれぞれの地
域間の日交通量は下のＯＤ表に示すとおりである。
①100 ②230 ③380 ④420 ⑤460
Ｂ
8 ｋｍ
ｍ
19
ｋｍ
Ｃ
Ａ
Ｂ
80
24
20
ｋｍ
Ａ
12
ｋｍ
Ｄ
ｎ
5 ｋｍ
解説：
22
ｋｍ
ｋｍ
Ｃ
130
110
Ｄ
100
240
70
計
170
280
180
130
480
760
590
760
2110
解説：
ｍｎ区間は２倍の速度であるから10kmとして考える
新道によって転換される交通量は
A⇔B、Ａ⇔Ｃのみ
2*（130+100）=460
-------------------最適化問題--------------
2. Non Linear Programming *
（非線形計画問題）
1) Both the object function(目的関数) and
constraint functions(制約条件) are
continuous(連続) and differentiable(微分可能).
2) The feasible region(実行可能領域) is convex(凸).
The object function is strictly convex（狭義凸）.
A unique solution(唯一解)
Non Linear Programming
Number of Variables
Multi
No
x2
x1
x1
Some
Number of Constraints
One
x2
b1≦ x1 ≦ b2
x1
x1
2.1 Programs with One Variable
first-order condition
dz ( x* )
0
dx
x = x*
x
Fig.2.1
ditonic: a function with a single minimum.
(unimodal)
Conditions for Strictly Convex Function
(second-order conditions)
1) The line segment condition
zx1  (1   ) x2   zx1   (1   ) zx2 
*
2) The linear approximation condition
z( x1 )  z( x1 )  ( x2  x1 )  z( x2 ) *
3) The second
derivative condition
2
*
d z( x )
0
2
dx
Strictly convex has only one local minimum
and guarantees the global minimum.
Fig.2.2
Constrained Minimization Programs
*
dz( x )
0
dx
dz( x* )
0
dx
a’≦x
binding constraint
dz( x* )
0
dx
x ≦ a”
Standard Form(標準形)
min z(x)
min z(x)
subject to
subject to
x ≧ a’
g1(x) ≧ b1
-x ≧ -a”
g2(x) ≧ b2
where g1(x) =x, b1= a’
g2(x)=-x, b2= -a”
Standard Form
(b)
dg1 ( x* )
1
dx
dz( x* )
0
dx
(c)
dg2 ( x* )
dz( x* )
 1
0
dx
dx
binding constraint(有効制約条件)
u j  0, b j  g j ( x* )  0　non-binding constraint
u j  0, b j  g j ( x* )  0　dz( x* )
dg1 ( x* )
 u1
dx
dx
u1 >0
dz( x* )
dg 2 ( x* )
 u2
u2 >0
dx
dx
b
*

g
(
x
)u j  0
j
j
dz( x* )
dg1 ( x* )
 u1
dx
dx
u1 >0
dz( x* )
dg 2 ( x* )
 u2
u2 >0
dx
dx
dg j ( x* )
dz( x* )
 u j
dx
dx
j
u j ≧ 0, b j  g j ( x* )u j  0, g j ( x* ) ≧ b j for　j  1,....., J
2.2 Multidimensional Programs(多変数)
min z( x1 , x2 ,...., xI )
subject to
min z(x)
subject to
g1 ( x1 , x2 ,...., xI )  b1
g j (x)  b j ; j  1,..., J
g 2 ( x1 , x2 ,...., xI )  b2

g J ( x1 , x2 ,...., xI )  bJ
x  ( x1 , x2 ,....,xI )
Unconstrained Minimization Programs
(制約条件なし，多変数)
First Order Condition(一次条件)
z (x)  (
z (x) z (x)
z (x)
,
,.....,
)
x1 x2
xI
z (x)  0
z (x)
 0　for　i  1,2,..., I
xi
Example
Z(x1,x2)=2x12+x22+2x1x2-4x1-2x2
z ( x1 , x2 )
 4 x1  2 x2  4
x1
z ( x1 , x2 )
 2 x2  2 x1  2
x2
z (x)  0
4x1  2x2  4  0
2x2  2x1  2  0
( x1 *, x2 *)  (1,0)
Conditions for Strictly Convex Functions
(second-order conditions(２次条件))
1) The line segment condition
*graph
zx'(1  ) x"  zx'  (1  ) zx"
zx1  (1  ) x2   zx2   (1  ) zx2 
2) The linear approximation condition
z (x' )  z (x' )  (x"x' )T  z (x" )
z( x1 )  z( x1 )  ( x2  x1 )  z( x2 )
Const
d 2 z ( x* )
0
2
dx
H
3) The second derivative condition
*
 2 z (x) : Positive Definite(正定値)
Hessian
  2 z ( x)

2

x
 2 1
  z ( x)
H   2 z ( x)   x x
 2 1
 2
  z ( x)
 xm x1
 2 z ( x)
x1 x2
 2 z ( x)
x22

 2 z ( x)
x1 x2




 2 z ( x) 

x1 xm 
 2 z ( x) 
x2 xm 

 
 2 z ( x) 
xm2 
Positive Definite(正定値)
1)A matrix H is positive definite
if the product of hHhT is positive for any nonzero vector h.
2) A matrix H is positive definite
if all leading principal minor determinants * are positive.
Example *
a11
0

0
0

0
0
a22
0
0
a33
0
0
0
0
 aii  0
0
a44 
Negative Definite(負定値)
1)A matrix H is positive definite,
if the product of hHhT is positive for any nonzero vector h.
2) A matrix H is positive definite,
If nth leading principal minor determinant are negative (n=2m+1) ,
and nth leading principal minor determinant are positive. (n=2m)
Leading Principal Minor Determinant(小行列式)
 a11
a11
a11
a21
a12
a22
 a11a22  a12 a21
 a11
a
 21
 a31
a
 41
a12
a13
a22
a23
a32
a42
a33
a43
a11
a12
a13
a21
a31
a22
a32
a23  a11a22 a33  a12 a23 a31  a13 a21a32
 a11a23 a32  a12 a21a33  a13 a22 a31
a33
:
:
a14 
a24 

a34 
a44 
Z(x1,x2)=2x12+x22+2x1x2-4x1-2x2
z ( x1 , x2 )
 4 x1  2 x2  4
x1
  2 z ( x1 , x2 )

2

x
H   2 z ( x1 , x2 )   2 1
  z ( x1 , x2 )
 x x
2
1

1) ( x1 , x2 )  (0,0)
z ( x1 , x2 )
 2 x2  2 x1  2
x2
 2 z ( x1 , x2 ) 

x1x2  4 2

2
 z ( x1 , x2 )  2 2

x2

 4 x1  2 x2 
4 2 x1 
hHh  ( x1 , x2 ) 
   ( x1 , x2 )


2 2 x2 
 2 x1  2 x2 
T
 4 x1  4 x1 x2  2 x2  (2 x1  x2 ) 2  x2  0
2
2)
2
a11  a11  4  0
a11
a12
a21
a22
 a11a22  a12 a21  8  4  4  0
2
Z(x1,x2)=-2x12-x22-2x1x2+4x1+2x2
z ( x1 , x2 )
z ( x1 , x2 )
 2 x2  2 x1  2
 4 x1  2 x2  4
x2
x1
 z ( x1 , x2 ) z ( x1 , x2 ) 
 x 2
x1x2   4  2
2
1
H   z ( x1 , x2 )  



z
(
x
,
x
)

z
(
x
,
x
)

2

2
1
2
1
2


 
x2 
 x2 x1
( x1 , x2 )  (0,0)
  4 x1  2 x2 
 4  2 x1 
T
hHh  ( x1 , x2 ) 
   ( x1 , x2 )


 2  2 x2 
  2 x1  2 x2 
 4 x1  4 x1 x2  2 x2  (2 x1  x2 ) 2  x2  0
2
2
a11  a11  4  0
a11
a12
a21
a22
 a11a22  a12 a21  8  4  4  0
2
Fig.2.6
Constrained Minimization Programs
min z (x1, x2)
s.t.
gj (x, x2 ) ≧ bj
x* = (x*1,x*2)
g2(x*1,x*2) = b2
g3(x*1,x*2) = b3
Direction of
decreasing objective
function
j= 1 2, ..., 6
x2*
x1* Minimum Point
Minimum Point
Direction of
decreasing objective
function
g 3
z
g2
g (x' ) g (x' )
g (x' )  (
,
)
x1
x2
 g2
 z
 g 3
x’=(x1’,x2’)
 z
gi(x1,x2)=const.
z(x*) be expressed as
a linear combination of the gradients of the binding constraints.
z (x* )  u2g 2 (x* )  u3g 3 (x* )
g 3
z
g2
z
 g 3
g 3 (x* )
z (x* )
g 2 (x* )
 u2
 u3
xi
xi
xi
 z
min z(x)
subject to
g j (x)  b j ; j  1,..., J
g j (x* )
z (x* )
 u j
for　i  1,2,..I
xi
xi
j
and
u j ≧ 0, b j  g j (x* )u j  0, g j (x* ) ≧ b j Kuhn-Tucker conditions
Complementary slackness conditions
Example of Kuhn-Tucker conditions
Min. z ( x1, x2 )  x12  2 x22  2 x1 x2  2 x1  4 x2
subject to
x1  x2  2
Kuhn-Tucker conditions
2 x1*  2 x2*  2  u
4 x2*  2 x1*  4  u
u(2  x  x )  0
*
1
x1*  x2*  2
u0
*
2
g j (x* )
z(x* )
 u j
for　i  1,2　j  1
xi
xi
j
b j  g j (x* )u j  0
g j (x* ) ≧ b j
Example of Kuhn-Tucker conditions cont.
1. If u=0
2 x1*  2 x2*  2  0u
4 x2*  2 x1*  4  0u
x1*=0
x2
*=1
x1* +x2*=1<2
2. If u≠0
2 x1*  2 x2*  2  u  0
x1*=1
2 x1*  4 x2*  4  u  0
x2*=1
x1*  x2*  2  0
u*=2
Z(1,1)= -1
Ploblem
Solve using Kuhn-Tucker conditions
Max f(x1,x2)=3x1+x2
Subject to g1=x12+x22≦5
g2=x1-x2≦1