11/16進捗報告 - 上智大学情報理工学部情報理

移動コストが確率的に与えられる
ネットワークにおける
経路選択の評価方法
本日の流れ
上智大学理工学部
機械工学科
管理工学研究グループ4年
A0671125 長沢敬祐
1.
2.
3.
4.
研究背景・目的
手法説明
実験結果・考察
結論・課題
研究背景：最短路とは
目的地
最短ルート
現在地
2
研究背景：最短=最速？
目的地
事故発生
事故なら迂回
するか・・・
現在地
3
研究背景：最短=最速？
目的地
最短・・・？
現在地
4
確率的ネットワークにおける安定な路：
（以下『安定な路』）
目的地
うまくいけば10分
ですが，運が悪いと
1時間かかりますよ
10分では無理
ですが，悪くて
も30分で着き
ますよ
40分以内に
着きたい！
現在地
5
本研究の目的
踏切・渋滞しやすい道路
などを通る経路を回避
する経路の導出
・混雑による待ち時間の緩和
・納期ずれの減少
7
目次
研究背景・目的
 手法説明
 実験結果・考察
 結論・課題

8
従来手法との比較・提案手法の位置付け
従来手法*[1]
評価方法
解法
計算方法
提案手法
・CVaR最小化
・（平均＆偏差）平方和
最小化
・偏差(平方)和最小化
・最大最小幅最小化
サンプルパス最適化
ラグランジュ緩和+( 数理計画ソルバー利
劣勾配射影法or折り用
返し法)
*[1]:中根久彰：「確率的最短路問題のCVaR最小化問題による定式化とその
解法」，筑波大学大学院修士課程システム情報工学研究科修士論文，2006．
9
今までの最短路検索では・・・・・・
2
3
平均化
平均
移動
時間
>
１
・・・
n
：注目しているルート
：その他ネットワーク
10
データの個性はサンプルパス最適化で
<
<
移動
時間
サンプルデータ2
重大
でも・・・
サンプルデータ3
<<
サンプルデータ１
・・・
11
：注目しているルート
：その他ネットワーク
サンプルパス最適化とは？
ルート１
移動
時間
平均
移動
時間
最大
移動
時間
<
変動を
回避する
評価
>
<<
サンプルデータ3
12
ルート2
サンプルパス最適化の基本的な定式化
min . I ( xij ) 
K

k 1
K:シナリオの数
Sk ( xij )
I(xij):サンプル全体に関する評価関数
S(xij):各サンプルに関する評価関数
s.t.


k i,(i,k )A xik   j i,( j,i)A x ji  0, i  s, t
 j  s,( s, j )A xsj  1,
xij  {0,1},
(i, j )  A.
13
経路であるための制約
サンプルデータの経路長とは？
ある経路を決めたとき
１
2
3
・・・
・・・
14
n
サンプルデータにより同じ経路でも…
(例);データ数を５個としたとき
サンプルサンプルサンプルサンプルサンプル
平均値
1経路長 2経路長 3経路長 4経路長 5経路長
問題 5447
4394
5551
4362
5526
5912
サンプル１
サンプル２
サンプル４
サンプル３
サンプル５
15
経路が決まれば，
サンプルの経路長が全て決まる
ある経路があった場合
データ番号をｋ
移動時間
k=1
k=2
k=3
k=4
k=5


16
次項から，この図で評価を説明
どのような評価をするか？（平均移動時間）
(例);データ数を５個としたとき
移動時間
k=1
k=2
k=3
k=4
k=5
17
平均移動時間
どのような評価をするか？（最大移動時間）
(例);データ数を５個としたとき
移動時間
k=1
k=2
k=3
k=4
k=5
18
最大移動時間
どのような評価をするか？（最大―最小）
(例);データ数を５個としたとき
移動時間
k=1
k=2
k=3
k=4
k=5
最大―最小幅
最小移動時間
最大移動時間
19
提案評価（平均からの差）
(例);データ数を５個としたとき
移動時間
k=1
k=2
k=3
D
+
2
D
D
+
3
-
k=4
k=5
1
D
D
4
5
20
平均移動時間
問題設定
終
始
始点から終点の安定な路を探す．
 各評価基準に従う経路．
 サンプルパス最適化より導出
21
実験方法
評価基準を複数提案

道路ネットワーク作成．一様でも正規分布でもないランダ
ムなネットワークデータを生成．
元ネットワーク：ワシントンD.C.地図・交差点間移動時間リスト
 移動時間変動:首都高データを参考


始点終点選択：一様ランダム．

各評価基準でサンプルパス最適化を行う．
22
主な実験機器
 ハードウェア
Inter® Core™ Quad [email protected]
3.00GB RAM 物理アドレス拡張
 ソフトウェア
 CPLEX Interactive Optimizer 11.1.0

23
目次
研究背景・目的
 手法説明
 実験結果・考察
 結論・課題

24
頻度表を重ね合わせてみる
140
120
頻度[回]
100
80
最大値最小化
平均移動時間:104.32%
標準偏差
:8.51%
平均&絶対偏差平
方和
平均移動時間:101.66%
標準偏差
:8.50%
60
40
20
0
80%
90%
100%
110%
120%
移動時間 [/平均最小化による平均移動時間]
25
次の頻度表は平均値からの変動
180
160
140
120
頻度
100
80
60
平均移動時間:118.24%
標準偏差
:4.42%
40
20
175%
165%
155%
145%
135%
125%
115%
105%
95%
85%
75%
65%
55%
0
データ区間
160
140
120
頻度
100
80
60
平均移動時間:104.32%
標準偏差
:8.51%
40
26
20
0
55% 65% 75% 85% 95% 105% 115% 125% 135% 145% 155% 165% 175%
データ区間
頻度[回]
頻度表を重ね合わせてみる
最大値最小化 200
180
絶対偏差平方 160
140
和最小化
120
100
80
60
40
20
0
-20%
-10%
0%
平均移動時間:104.32%
標準偏差
:8.51%
平均移動時間:118.24%
標準偏差
:4.42%
10%
20%
27
平均経路長からの差分
結論および課題
結論：２種類安定な路を導出できた．
それら従来定義より優れている部分がある．
課題
 最悪値最小化より悪い場合．
 始点終点間が近い
 パラメータが悪い
問題：
 実データ入手困難(GPSなどで全道路を調査or時間区分ご
28
とに適正データの入手の必要があるため)
ご清聴ありがとうございました
29
提案評価（平均からの差）
(例);データ数を５個としたとき
移動時間
k=1
k=2
k=3
D
+
2
D
D
+
3
-
k=4
k=5
1
D
D
4
5
30
平均移動時間
平均絶対偏差を最小化する計画法
(投資などでよく使われる手法)
-下方向変動の平均値を最小化-
一年目の収益の偏差

1
 D D

1
 期待収益１年目の利益係数の場合の収益
D1
k=1
k=2
+
-
D 2≧0⇔D 2=0
k=3
k=4
D4
31
平均絶対偏差を最小化する計画法
(投資などでよく使われる手法)
-下方向変動の平均値を最小化
下方向偏差の絶対値の平均（平均絶対偏差は，）
n
D

i
i 1
n
と表せるので，これを最小にすれば平均リ
スクも最小になる．
32
平均絶対偏差と絶対偏差和
リスクの指標として絶対偏差和最小化計画を最初に考案した
Hazell(1971)は，絶対値の合計値（絶対偏差和）を最小化す
ることを提案している．この最適化基準は
MOTAD(Minimization of Total Absolute Deviations,絶対偏
差和最小化基準)と呼ばれている．MOTAD基準による問題
の最適解と平均絶対偏差最小化基準による問題の最適解
は同じであることが知られている．
33
CPLEXの性能比較

４階のＰＣ
DELL optiplex745 intel®Core™2 [email protected]
2.39GHz,2.99GB RAM 物理アドレス拡張
 CPLEX Interactive Optimizer 10.1.0


５階のＰＣ
Inter® Core™ Quad [email protected]
3.00GB RAM 物理アドレス拡張
 CPLEX Interactive Optimizer 11.1.0

34
CPLEXの性能比較のための問題
(-悪化（下方向）変動のばらつきを最小化-)
min . average 
D-k:サンプルデータkの移動
時間が平均移動時間を上
回る場合の偏差を正値で
表した値
K
 ( Dk )2
k 1
s. t.
D k  0,
k ,
D  k  (i , j )A ckij xij  average ,
ckij：k番目データでiからjへ
k ,
移動した場合のコスト
1 K
average (i , j )A ckij xij ,
K k
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
xij {0,1},
(i, j )  A.
i  s, t ,
xij:決定変数．iからjへ移動した
場合1．そうでない場合0．
35
CPLEXの性能比較（問題設定）

今回は環状３-放射状５-サンプル５で設定
36
CPLEXの性能比較(結果)

４階のＰＣ
DELL optiplex745 intel®Core™2 [email protected]
2.39GHz,2.99GB RAM 物理アドレス拡張
 CPLEX Interactive Optimizer 10.1.0
→56747.28[s]


５階のＰＣ
Inter® Core™ Quad [email protected]
3.00GB RAM 物理アドレス拡張
 CPLEX Interactive Optimizer 11.1.0
→0.42[s]

差は約1.35×E05倍
 二次制約計画は5階のＰＣの方が優秀そう・・・

37
線形計画的な最短路の定式化
出発地sから目的地tへ移動する場合
cij xij
i
s
c ji x ji
j
・・・
・・・
t
38
道路網を表現したネットワーク
線形計画的な定式化
min .
(i, j )A ckij xij
s. t.
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
i  s, t ,
 j  s,( s, j )A xsj  1,
xij {0,1},
cij：iからjへ移動した場合の
コスト
(i, j )  A.
xij:決定変数．iからjへ移動した
場合1．そうでない場合0．
39
放射状路について
belt line(環状線)
radial line(放射線)
節点の数=
枝の数=
×
+1(中心)
×
×1(無向グラフ)
×2(有向グラフ)
40
サンプルパス最適化によるロバスト最短路最適化の基本方策
K:シナリオの数
I(xij):サンプル全体に関する
評価関数
K
min . I ( xij )   Pr ( xij )
r 1
P(xij):各サンプルに関する
評価関数
s.t.


x
k :k  i
ik
x
j: j  s
sj
  x ji  0
i, j
j: j  i
ネットワーク制約
1
xij  {0,1}
i, j
41
サンプルパス最適化の基本的な定式化
min . I ( xij ) 
K

k 1
K:シナリオの数
Sk ( xij )
I(xij):サンプル全体に関する評価関数
S(xij):各サンプルに関する評価関数
s.t.


k i,(i,k )A xik   j i,( j,i)A x ji  0, i  s, t
 j  s,( s, j )A xsj  1,
xij  {0,1},
(i, j )  A.
42
経路であるための制約
平均最小化(評価基準1)
ckij：k番目データでiからjへ
min . average
移動した場合のコスト
s. t.
1 K
average (i , j )A ckij xij ,
K k
xij:決定変数．iからjへ移動した
場合1．そうでない場合0．
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
i  s, t ,
 j  s,( s, j )A xsj  1,
xij {0,1},
(i, j )  A.
43
下方向偏差和最小化(評価基準2)
K
min .
 ( Dk ),
D-k:サンプルデータkの移動
時間が平均移動時間を上
回る場合の偏差を正値で
表した値
k 1
s. t.
D k  0,
k ,
Dk  (i, j )A ckij xij  average,
k ,
1 K
average  (i, j )A ckij xij ,
K k
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
xij {0,1},
ckij：k番目データでiからjへ
移動した場合の移動時間
i  s, t ,
xij:決定変数．iからjへ移動
した場合1．そうでない場合
0．
(i, j )  A.
44
下方向偏差平方和最小化(評価基準3)
K
min .
 ( Dk )2 ,
D-k:サンプルデータkの移動
時間が平均移動時間を上
回る場合の偏差を正値で
表した値
k 1
s. t.
D k  0,
k ,
Dk  (i, j )A ckij xij  average,
k ,
1 K
average  (i, j )A ckij xij ,
K k
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
xij {0,1},
ckij：k番目データでiからjへ
移動した場合の移動時間
i  s, t ,
xij:決定変数．iからjへ移動
した場合1．そうでない場合
0．
(i, j )  A.
45
最大値最小化基準(評価基準4)
min . MAXIMUM
s. t.
MAXIMUM  (i, j )A ckij xij  0,
k ,
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
i  s, t ,
 j  s,( s, j )A xsj  1,
xij {0,1},
(i, j )  A.
ckij：k番目データでiからjへ
移動した場合のコスト
xij:決定変数．iからjへ移動した
場合1．そうでない場合0．
46
最大-最小幅最小化基準(評価基準5)
min . MAXIMUM  minimum ckij：k番目データでiからjへ
移動した場合のコスト
s. t.
MAXIMUM  (i, j )A ckij xij  0,
k ,
(i, j )A ckij xij  minimum  0,
k ,
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
xij {0,1},
(i, j )  A.
i  s, t ,
xij:決定変数．iからjへ移動した
場合1．そうでない場合0．
47
平均・下方向偏差平方和最小化(評価基準6)
K
min. (average) 2     ( D  k ) 2
k 1
s. t.
D k  0,
k ,
D  k  (i , j )A ckij xij  average ,
D-k:サンプルデータkの移動
時間が平均移動時間を上
回る場合の偏差を正値で
表した値
ckij：k番目データでiからjへ
k ,
移動した場合のコスト
1 K
average (i , j )A ckij xij ,
K k
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
xij {0,1},
(i, j )  A.
i  s, t ,
xij:決定変数．iからjへ移動した
場合1．そうでない場合0．
48
平均値制約付き下方向偏差平方和最小化-(評価基準7)
D-k:サンプルデータkの移動時間が
平均移動時間を上回る場合の偏差
を正値で表した値
K
min . (baverage)2   ( Dk )2 ,
k 1
s. t.
D k  0,
k ,

D k  (i , j )A ckij xij  average ,
1 K
average (i , j )A ckij xij ,
K k
1 K
baverage (i , j )A ckijbij ,
K k
k ,
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
hi,(i,h)A bih   g i,( g ,i)A bgi  0,
 j  s,( s, j )A bsj  1,
xij {0,1}, bij {0,1},
i  s, t ,
i  s, t ,
(i, j )  A.
average    baverage,
ckij：k番目データでiからjへ
移動した場合のコスト
bij ，xij:決定変数．iからjへ移動
した場合1．そうでない場合0．
49
平均値制約付き下方向偏差平方和最小化-(評価基準8)
D-k:サンプルデータkの移動時間が
平均移動時間を上回る場合の偏差
を正値で表した値
K
min . (baverage)2   ( Dk )2 ,
k 1
s. t.
D k  0,
k ,

D k  (i , j )A ckij xij  average ,
1 K
average (i , j )A ckij xij ,
K k
1 K
baverage (i , j )A ckijbij ,
K k
average    baverage,
ckij：k番目データでiからjへ
移動した場合のコスト
k ,
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
hi,(i,h)A bih   g i,( g ,i)A bgi  0,
 j  s,( s, j )A bsj  1,
xij {0,1}, bij {0,1},
i  s, t ,
i  s, t ,
(i, j )  A.
（評価基準7と異なるλの値を用いて
収束性の違いを確認したもの．）
bij ，xij:決定変数．iからjへ移動
した場合1．そうでない場合0．
50
平均値制約付き下方向偏差平方和最小化-(評価基準9)
K
min . (baverage)   ( Dk )2  (MAXIMUM )2 ,
2
k 1
s. t.
D k  0,
k ,

D k  (i , j )A ckij xij  average ,
MAXIMUM  (i, j )A ckij xij  0,
1 K
average (i , j )A ckij xij ,
K k
baverage
K
1
(i, j )A ckijbij ,
K k
average    baverage,
ckij：k番目データでiからjへ
移動した場合のコスト
k ,
k ,
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
hi,(i,h)A bih   g i,( g ,i)A bgi  0,
 j  s,( s, j )A bsj  1,
xij {0,1}, bij {0,1},
i  s, t ,
i  s, t ,
(i, j )  A.
D-k:サンプルデータkの移動時間が
平均移動時間を上回る場合の偏差
を正値で表した値
bij ，xij:決定変数．iからjへ移動
した場合1．そうでない場合0．
51
下方向偏差和最小化-(評価基準10)
D-k:サンプルデータkの移動時間が
平均移動時間を上回る場合の偏差
を正値で表した値
K
min . M  baverage   ( Dk ),
k 1
s. t.
D k  0,
k ,

D k  (i , j )A ckij xij  average ,
1 K
average (i , j )A ckij xij ,
K k
1 K
baverage (i , j )A ckijbij ,
K k
k ,
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
hi,(i,h)A bih   g i,( g ,i)A bgi  0,
 j  s,( s, j )A bsj  1,
xij {0,1}, bij {0,1},
i  s, t ,
i  s, t ,
(i, j )  A.
average    baverage,
ckij：k番目データでiからjへ
移動した場合のコスト
bij ，xij:決定変数．iからjへ移動
した場合1．そうでない場合0．
52
下方向偏差平方和最小化-(評価基準11)
D-k:サンプルデータkの移動時間が
min . M  baverage   ( Dk )2 , 平均移動時間を上回る場合の偏差
k 1
を正値で表した値
s. t.
D k  0,
k ,
hi,(i,h)A xih   g i,( g ,i)A xgi  0, i  s, t ,
D  k  (i , j )A ckij xij  average ,
k ,
 j  s,( s, j )A xsj  1,
1 K
hi,(i,h)A bih   g i,( g ,i)A bgi  0, i  s, t ,
average (i , j )A ckij xij ,
K k
 j  s,( s, j )A bsj  1,
K
1 K
baverage (i , j )A ckijbij ,
K k
xij {0,1}, bij {0,1},
(i, j )  A.
average    baverage,
ckij：k番目データでiからjへ
移動した場合のコスト
bij ，xij:決定変数．iからjへ移動
した場合1．そうでない場合0．
53
最大-最小幅最小化-(評価基準12)
min . M  baverage  MAXIMUM  minimum,
s. t.
MAXIMUM  (i, j )A ckij xij  0,
(i, j )A ckij xij  minimum  0,
1 K
average (i , j )A ckij xij ,
K k
k ,
k ,
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
hi,(i,h)A bih   g i,( g ,i)A bgi  0,
 j  s,( s, j )A bsj  1,
xij {0,1}, bij {0,1},
i  s, t ,
i  s, t ,
(i, j )  A.
1 K
baverage (i , j )A ckijbij ,
K k
average    baverage,
ckij：k番目データでiからjへ
移動した場合のコスト
bij ，xij:決定変数．iからjへ移動
した場合1．そうでない場合0．
54
下方向偏差平方和最小化基準-(評価基準13)
min . M  baverage  M  bMAXIMUM   
K
 ( Dk )2 ,
k 1
s. t.
D k  0,
k ,

D k  (i , j )A ckij xij  average ,
k ,
MAXIMUM  (i, j )A ckij xij  0,
k ,
bMAXIMUM  (i, j )A ckijbij  0,
k ,
1 K
average (i , j )A ckij xij ,
K k
1 K
baverage (i , j )A ckijbij ,
K k
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
hi,(i,h)A bih   g i,( g ,i)A bgi  0,
 j  s,( s, j )A bsj  1,
xij {0,1}, bij {0,1},
i  s, t ,
i  s, t ,
(i, j )  A.
MAXIMUM    bMAXIMUM ,
ckij：k番目データでiからjへ
移動した場合のコスト
bij ，xij:決定変数．iからjへ移動
した場合1．そうでない場合0．
55
経路長平方和最小化(評価基準14)
ckij：k番目データでiからjへ
移動した場合のコスト
K
min .
2
(
z
(
k
))
,

xij:決定変数．iからjへ移動し
た場合1．そうでない場合0．
k 1
s.t.
z (k )  (i, j )A ckij xij ,
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
i  s, t ,
 j  s,( s, j )V xsj  1,
xij {0,1},
(i, j)  A.
56
平均経路長および絶対偏差平方和最小化(評価基準15)
min . (average)  
2
K
 (D
k 1
s. t.

k)  
D  k  0,
2
K
 (D k )2 ,
k 1
移動した場合のコスト
xij:決定変数．iからjへ移動し
k , た場合1．そうでない場合0．
k ,
Dk  (i, j )A ckij xij  average,
D  k  0,
D k  average
ckij：k番目データでiからjへ
k ,
(i, j)A ckij xij ,
k ,
D-k:サンプルデータkの移動時間
が平均移動時間を上回る場合
の偏差を正値で表した値
1 K
average  (i, j )A ckij xij ,
K k
hi,(i,h)A xih   g i,( g ,i)A xgi  0, i  s, t ,
 j  s,( s, j )A xsj  1,
xij {0,1},
(i, j )  A.
57
絶対偏差平方和最小化(評価基準16)
K
min . M  baverage  
 (D
k 1

k)  
2
K
 ( D k )2 ,
k 1
s. t.
D k  0,
k ,

D k  (i , j )A ckij xij  average ,
D k  0,
D

k
 average 
k ,
k ,

c x ,
( i , j )A kij ij
1 K
average (i , j )A ckij xij ,
K k
1 K
baverage (i , j )A ckijbij ,
K k
average   baverage,
ckij：k番目データでiからjへ
移動した場合のコスト
k ,
hi,(i,h)A xih   g i,( g ,i)A xgi  0,
 j  s,( s, j )A xsj  1,
hi,(i,h)A bih   g i,( g ,i)A bgi  0,
 j  s,( s, j )A bsj  1,
i  s, t ,
i  s, t ,
xij {0,1}, bij {0,1},
(i, j )  A.
D-k:サンプルデータkの移動時間
が平均移動時間を上回る場合
の偏差を正値で表した値
bij ，xij:決定変数．iからjへ移動した
場合1．そうでない場合0．
58
180
160
140
120
100
80
60
40
20
0
データ区間
175%
165%
155%
145%
135%
125%
115%
105%
95%
85%
75%
65%
平均移動時間:100.00%
標準偏差
:12.53%
55%
頻度
平均値最小化頻度表
59
180
160
140
120
100
80
60
40
20
0
175%
165%
155%
145%
135%
125%
115%
105%
95%
85%
75%
65%
平均移動時間:100.63%
標準偏差
:11.62%
平均求解時間:45.41[s]
求解標準偏差:25.81[s]
55%
頻度
経路長平方和最小化
60
データ区間
最大－最小幅最小化
平均移動時間:108.27%
標準偏差
:10.66%
平均求解時間:27.49[s]
求解標準偏差:22.03[s]
175%
165%
155%
145%
135%
125%
115%
105%
95%
85%
75%
65%
55%
頻度
180
160
140
120
100
80
60
40
20
0
61
データ区間
180
160
140
120
100
80
60
40
20
0
175%
165%
155%
145%
135%
125%
115%
105%
95%
85%
75%
65%
平均移動時間:100.88%
標準偏差
:9.76%
平均求解時間:55.80[s]
求解標準偏差:17.08[s]
55%
頻度
平均および下方向偏差平方和最小化
62
データ区間
180
160
140
120
100
80
60
40
20
0
175%
165%
155%
145%
135%
125%
115%
105%
95%
85%
75%
65%
平均移動時間:108.06%
標準偏差
: 10.73%
平均求解時間:28.41[s]
求解標準偏差:26.30[s]
55%
頻度
下方向偏差和最小化
63
データ区間
下方向偏差平方和最小化
180
160
140
120
100
80
60
40
20
0
データ区間
175%
165%
155%
145%
135%
125%
115%
105%
95%
85%
75%
65%
55%
頻度
平均移動時間:117.45%
標準偏差
: 5.60%
平均求解時間:292.96[s]
求解標準偏差:385.13[s]
64
平均および絶対偏差平方和最小化
平均移動時間:101.66%
標準偏差
:8.50%
平均求解時間:83.91[s]
求解標準偏差:33.51[s]
65
絶対偏差平方和最小化
平均移動時間:118.24%
標準偏差
:4.42%
平均求解時間:522.83[s]
求解標準偏差:587.93[s]
66
最大値の期待値・最小値の期待値
平均値の期待値
130%
120%
110%
100%
90%
80%
最大値最小化
絶対偏差平方和
平均&絶対偏差平方和
下偏差平方和
下偏差和
平均&下偏差平方和
最大最小幅
経路長平方和
平均時間
67
道路状況の変化（特に渋滞）の原因の分類

①信号交差点・有効車線・交通容量
→ネットワーク理論・シミュレーション

②事故・天候要因
→（事故）諦める．
→その時の走行時間をデータとして入手し，再計算

③料金所
→ETCの導入により解決方向

④坂道による渋滞
→運転者の注意力次第

⑤踏切・工事
→走行ルート選択により回避可能！
68
ランダムデータ作成手法
0.70
0.60
確率[/倍]
0.50
0.40
0.30
0.20
0.10
0.00
1
2
3
4
5
6
7
8
倍率[倍]
9 10 11 12 13 14
69
70
71
最低収益を最大化
max. R
( R : 最低収益)
s. t.
n
a x
ij
j
 bi (i 1,2,...,m)
j
n
d
ij
x j  R  0 (i 1,2,...,l ) (d : 各年次の利益係数)
j
x j  0 ( j  1,2,...,n), R  0
期待収益を確保して
最低収益を最大化
max. R
( R : 最低収益)
s. t.
n
a x
ij
j
 bi (i 1,2,...,m)
j
n
d
ij
x j  R  0 (i 1,2,...,l )
j
(d : データ(各年次)の利益係数)
n
e x
j
j
j
 E (i 1,2,...,l ) (E : 期待したい収益 (自分で設定))
(e : 各品目の(予想される )利益係数)
x j  0 ( j  1,2,...,n), R  0
分散最小化
一定の期待収益を確保した上で収益の変動（分散）を最小化す
る最適解を求めるもの．ポートフォリオ理論で広く用いられ
る．
ここでは収益の関数を，
 ( x1 , x2 ,...,xn )
とする．
74
分散最小化
分散Var[ ( x1 , x2 ,..., xn )]
11 x1
  21 x2 x1
 12 x1 x2
  1n x1 xn
  22 x2
   2 n x2 xn


2

  n1 xn x1
n
n
i
j
2

  n 2 xn x2 
   ij xi x j

  nn xn
2
75
分散最小化
分散Var[ ( x1 , x2 ,..., xn )]
n
n
i
j
   ij xi x j
( ij (i  j ) : iの利益係数の予測誤差の分散)
( ij (i  j ) : iと jの利益係数の予測誤差の共分散)
( ij   ji )
76
以降２次計画問題の分野
分散最小化基準による計画
n
n
min.Var[ ( x1 , x2 ,..., xn )](   ij xi x j )
i
s. t.
n
a x
ij
j
 bi (i 1,2,...,m)
j
期待収益下限制約
n
e x
i i
j
 ( x1 , x2 ,..., xn ) : 収益の関数
( ij (i  j ) : iの利益係数の予測誤差の分散)
( ij (i  j ) : iと jの利益係数の予測誤差の共分散)
( ij   ji )
E
i
xi  0 (i  1,2,...,n)
( E : 期待収益下限(指定))
(e : 各品目の(予想される )利益係数)
77
では分散最小化で解けるネットワークの大き
さは？

記憶領域をメモリからファイルレベルに落とすと計算速度が
非常に悪くなるので，メモリに格納できる大きさを考えてみる
．各枝を変数とすると
通常のメモリの大きさ：3GBと仮定=30億byte
数値計算なのでdouble型(8byte)とする．→3.75億係数格納可能
分散共分散行列は上（下）三角行列であらわしてかまわないので，
3.75億係数→7.5億変数組み合わせ
(7.5億変数組み合わせ)^(1/2)=27300変数（今回はarc）
(参考)今回のDCデータは29818arc
このメモ用紙の裏の計算では考えていないが，これに各地点での
流入流出のための制約式が必要であるので，さらに少ない変数
でメモリがいっぱいになってしまう．
78
満足水準最大化の定式化は・・・
max.
E[ ( x1 , x2 ,..., xn )]  h Var[ ( x1 , x2 ,..., xn )]
s.t.
n
a
ij
x j  bi (i  1,2,...,m)
j
xi  0 (i  1,2,...,n)
hは設定した計画管理水準に対応する安全係数
期待効用を最大化する計画法
u ( )  1  exp(a )
効用関数の指数型
(は収益)
効用

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
a=0.01
a=0.005
a=0.001
0
200
400
600
指数型効用関数の例
800
収益
期待効用を最大化する計画法

πが確率変数の場合，
u ( )  1  exp(a )
(は収益)
u(π)も確率変数となる．この効用関数の期待値はπの確率分
布が正規分布の時は次式になる．
a  Var [ ( x1 , x2 ,..., xn )]
1  exp[ a(
 E[ ( x1 , x2 ,..., xn )])]
2
期待効用を最大化する計画法
max.
a  Var[ ( x1 , x2 ,..., xn )]
1  exp[a(
 E[ ( x1 , x2 ,..., xn )])]
2

max.
a  Var[ ( x1 , x2 ,...,xn )]
E[ ( x1 , x2 ,..., xn )] 
2
期待効用を最大化する計画法
の確率変数が正規分布の場合の期待値
a  Var[ ( x1 , x2 ,..., xn )]
1  exp[a(
 E[ ( x1 , x2 ,..., xn )])]
2
の確率変数が正規分布でない場合
u ( )    A
2
とすると，期待値は
A  Var[ ( x1 , x2 ,..., xn )]
E[ ( x1 , x2 ,..., xn )] 
2

Download Report