pp.55
交通量配分手法(Traffic Assignment Method)
①OD交通需要関数
②交通ネットワーク
③リンクパフォーマンス関数
→ 各リンク,経路交通量やサービス水準を求める手法
*Flow Independent配分
*静的交通量配分
*確定的交通量配分
*利用者均衡配分




* Flow Dependent配分
*動的交通量配分
*確率的交通量配分
*システム最適配分
[1] 利用者均衡(user
equilibrium)
仮説1) 利用者は常に最早経路を選択する.
仮説2) 利用者は利用経路に関する完全な情報を得ている.
hi :経路iの交通量
ti :経路iの所要時間
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 :リンクaの交通量が微小に増加したときの総交通費用の増加分
ta ( xa )
dT  {ta ( xa ) 
xa }dxa
xa
m t( xa ) :限界費用関数(marginal cost function)
リンクaの交通量が微小に増加したときの総交通費用の
増加する割合を表す関数
ta ( xa )
dT
m t( xa ) 
 ta ( xa ) 
xa
dxa
xa
(4.8)
第一項:新たに加わった利用者1台当たりの平均費用
第二項:利用者が新たに加わることによる他の利用者の費用の増加
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 最短経路探索法
[ 5 ] 最短経路探索アルゴリズム
1)最短経路配分の簡単な例
1
4
3
2
1
3
5
5
2
5
3
4
7
6
3
6
4
5
8
3
9
発ノード①、
着ノード⑦⑧⑨
q17=10、q18=5
q19=20
qrs:
tij:
Crsp:
frsp:
OD交通量
リンクコスト
経路コスト
経路交通量
Crsp(ODペアrsのp番目の経路の交通費用)
その経路上のリンクijのリンクコストtijの和
Crsp = Σtijδrsij,p
δrsij,p:リンクijがODペアrsのp番目の経路上にあれば1、な
ければ0となるリンク−経路結合行列(の要素)
ex.C172=t12+t25+t57=4+3+2=9
各ODペアの全経路とその経路費用
①②④⑦ C171=10
①②④⑦⑨
①②⑤⑦ C172=9
①②⑤⑦⑨
①③⑤⑦ C173=10
①③⑤⑦⑨
①②⑤⑧ C181=10
①②⑤⑧⑨
①③⑤⑧ C182=11
①③⑤⑧⑨
①③⑥⑧ C183=12
①②⑥⑧⑨
経路交通量 frsp
f172=q17=10, f171=f173=0
f181=q18=5 , f182=f183=0
f194=q19=20 , f171=f172=f173=f175=f176=0
C191=16
C192=15
C193=16
C194=13
C195=14
C196=15
リンク交通量x
:そのリンクを通過する経路の交通量を重ね合わせたもの
xij =ΣΣfrspδrsij,p
rs p
x58 =f181+f182+f194+f195 =5+0+20+0=25
最短経路の交通量を重ね合わせることによって、すべてのリンク
交通量を計算すれば、最短経路配分の計算は完了。
x12=35
x13=0
x24=0
x25=35
x35=0
x36=0
x47=0
x57=10
x58=25
x68=0
x79=0
x89=20
(1)最短経路配分
すべての経路を列挙することは,実際のネットワークではまず無理。
↓
最短経路探索アルゴリズム
a.ラベル確定法(Label Setting Method)
各繰り返し計算において、1つ以上のラベルを確定していく。
<リンクコストが非負でなければならない>
a.ラベル確定法(Label Setting Method)
永久ラベル(permanent label) P
一時ラベル(temporary label) T 、起点r
step0:[初期値設定]
①永久ラベル、一時ラベル集合の初期設定
起点rを永久ラベル、その他の点を一時ラベル
P←r、T←N−{r}
②ラベルの初期値設定
d(j)←0
if j=r
d(j)←trj
if (r,j)∈A
d(j)←∞
otherwise
③先行ポインタの初期値設定
pred(j)←r
if (r,j)∈A
pred(j)←0
otherwise
step1:[ノード選択]
Tからラベルの値が最小なノードiをPに移す
d(i)=min{d(j):j∈T}
→ P←P∪{i}
、T←T−{i}
step2:[ラベル更新]
リンクi→j∈A の終点jについて
d(j)>d(i)+tijならばd(j)←d(i)+tij、pred(j)←i
step3:[終了条件]
P=Nならば終了、
そうでなければstep1へ
d(i):起点rからの最短距離
最短経路:ノードiから先行ポインタを遡っていけばよい。
最短経路配分のアルゴリ
ズム
ODペア毎に、最短経路に配分する。
ODペアを通し番号で区別し、その総数はN。
step0:[初期値設定]
n←1、xij←0 for all ij
step1:[最短経路探索]
n番目のODペアについて、最短経路を探索し、その最短
経路上のリンク番号を集合Anを記録
step2:[OD交通量の配分]
リンク(i,j)∈AnのODペア別交通量yijの値をODペアnの
OD交通量とする。
yij←qrs for (i,j)∈An
step3:[リンク交通量の合算]
xij←xij+yij for (i,j)∈An
step4:[終了条件]
n= Nならば終了、
そうでなければn=n+1とし、step1へ
【国家公務員試験(Ⅰ
種)】
A~Dの4地域が図のような道路網で連絡されている。それぞ
れの地域の距離は図に示すとおりである。いま、m−n間を結ぶ
新道を建設したい。新道での走行速度は現在の道路の2倍とす
ると、新道への転換交通量は次のうちどれか。ただし、すべての
車は時間的に最短の経路を通るものとし、A~Dそれぞれの地
域間の日交通量は下のOD表に示すとおりである。
①100 ②230 ③380 ④420 ⑤460
B
8 km
m
19
km
C
A
B
80
24
20
km
A
12
km
D
n
5 km
解説:
22
km
km
C
130
110
D
100
240
70
計
170
280
180
130
480
760
590
760
2110
解説:
mn区間は2倍の速度であるから10kmとして考える
新道によって転換される交通量は
A⇔B、A⇔Cのみ
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(2次条件))
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
ダウンロード

四段階推定法(配分)