PowerPoint プレゼンテーション

Size: px

Start display at page:

Download "PowerPoint プレゼンテーション"

ぜんまおとべ
5 years ago
Views:

1 Opmzo o rs prory he rsporo ewor usg deomposo mehodology. esh,. Srv,. Ouveys, G. Curre Trsporo Reserh Pr C, Vol. 9 (), pp , (). 468 社会基盤学専攻交通研伊藤篤志

2 概要バス専用レーンの最適配置手法の提案総旅行時間最小化計算において, 分解法を導入例題と結果 hp://r.seoul.go.r/les///ed-us-le3.jpg

3 ベンダースの分解原理数理計画法の定式化の中に, 構造を異にした種類の変数が同居例 ) [ 実数変数 ]+[ 整数変数 ] [ 線形変数 ]+[ 非線形変数 ] [ ネットワーク型変数 ]+[ 非ネットワーク型変数 ] 刀根 (7) ) それぞれの問題に分解, それを持ち寄って混合問題を解決する分解原理 m {z(, y)=+dy, y +y,, R p, y Y R q } 双対問題 m{w(y, u)=dy+u(-y) u, u } 開始双対問題定式化, w 最小化 u 固定, y について解く, 最大化 y 固定, u について解く, w 最小化 w Yes 終了 No

4 ベンダースの分解原理 3 問題実数二値 - m {z(, y)=+dy, y +y,, R p, y Y R q } 手順 y Y をひとつ選び, 固定双対問題 m{dy+u(-y) u, u } を解く () m z=3 +5 +y +4y y - y y + y y - y 4,, y, y {, } - - y =, y = とする 4 u u u 5u dy+u(-y) 8u 4u 緩和問題とに場合分け. () が最適解 u をもつ u を頂点集合 V に入れる. () は下に無界で, μ, μ なる方向 μ がみつかる μ を端線集合 W に入れる m w=5u +8u +4u 3 - u - 4u + u 3 3 3u + u - u 3 5 u, u, u 3 最適解 (u,u,u 3,w )=(4,,7,48) この解を頂点集合 Vに入れる V={(4,,7)} 双対問題の下界

5 ベンダースの分解原理 4 手順 V, W により定まる次の, y に関する計画問題を解く ( は十分大なる正数 ) dy+u(-y) y y y 6y y y m{ dy+u(-y) μ(-y) y Y, } ( u V), ( μ W), () m -7y +6y +48 y, y {, } () が不能原問題も不能, 終了 else ^ ^ () の最適解を (, y) とする最適解 (y ^, y ^, ^ )=(,,74) 不能 : 可能解が存在しない線形計画問題

6 ベンダースの分解原理 5 ^ 手順 3 yにより定まる, 次のuに関する線形問題を解く m{dy+u(-y) u, ^ ^ u } を解く () 4 u u u 4 7u dy+u(-y) ^ ^ 7u 5u とに場合分け. () が下に下界その方向 μをみつけ, 集合 Wに加えて手順へ. () が最適解 u^ をもつ dy+u(-y) ^ が成立するかどうかを調べる成立 yとは原問題の最適解 ( 終了 ) ^ ^ ^ else ^ >dy+u(-y) uを集合 Vに加えて手順へ m w=4+7u +7u +5u 3 - u - 4u + u 3 3 3u + u - u 3 5 u, u, u 3 最適解 (u^,u^,u^ 3,w^ )=(4,,7,74) ^ () が最適解 uをもつ ^ ^ ^ ^ dy+u(-y)=w =74= ^ が成立, 最適解に達した. (^, ^ )=(5/, 3/)

7 既往研究 6 RS(Rod Spe lloo): 道路空間再配分 Lol level 幹線リンクへの導入を検討専用レーンが幹線の交通に与える影響評価手法を提案旅行時間, 分散, 初期費用維持費用などの包括的費用 ly e l.(978) l(99) Curre e l.(7) ネットワーク全体を通した最適な道路空間再配分の提示に至っていない Newor level ネットワーク中のあらゆるリンクへの導入を検討. 現存のバスネットワークを保持, 自家用車とバスの間で道路空間を再配分本研究の対象. バスネットワークの改変も含めた公共交通デザイン問題 (TNDP) 公共交通網の再構築は実現性に劣る自家用車とバスが相互に与える交通量配分を考えていない

8 新規性 7 ネットワークレベルで, バスレーン導入の最適組み合わせを見つける手法を提案包括的目的関数の導入最適値計算手法の導入

9 モデル記述 8 モデルの概要ネットワークデザイン問題 (NDP) として扱う Selerg 問題 Leder: 交通ネットワーク管理者 Follower: 交通ネットワーク利用者管理者が専用レーンの位置を決定利用者が旅行時間を最小化する経路を選択 Lel(975) 仮定. OD は一定, 施策の影響を受けない. ネットワーク利用者は自家用車とバスのつに限定 3. レイアウト, リンク情報, コスト関数, 操作詳細は既知 4. バス経路, 頻度, バス停位置は一定 5. 専用レーンの導入に伴い, バスの旅行時間は減るバス停の容量は無限, つのレーンに制限されない

10 定式化 - 上位問題 9 目的関数 m Z 自家用車 O l mp s バス mp 停車時間 W 総旅行時間社会的コスト α, β, γ, η( ): 重みづけ, 単位変換, 相対的重要度 = : ネットワーク集合 : 専用レーン導入不可リンク集合 : 専用レーン導入可能リンク集合 ( 導入済 ) : 専用レーン導入可能リンク集合 ( 未導入 ) : バス経路 ( 徒歩リンク, 乗り換えリンク含む ) +/- : リンクの集合 (rom/o ode ) / : リンクの交通量 (): 旅行時間 -, / (): リンクの旅行時間 w : ノードでの待ち時間 : バス停の集合 mp / : 社会的コスト ( 排出, 騒音, 事故, 信頼性 ) O : 車利用の平均占有率 l : リンクの長さ (=Σ p L p ξ p, ): リンク上のバス頻度の合計 L: バス路線の集合 p : バス路線 p の頻度 ξ p, : バス路線リンク行列 s : リンクのバス旅行時間

11 定式化 - 上位問題制約条件 s.. E dg or 導入費用道路管理者が意思決定する要素リンクにバスレーンを導入するか否か dg: 予算 E : リンク () での専用レーンの導入費用 Φ : ダミー変数 (: リンク混合状態 )

12 定式化 - 下位問題 OD 表は既与各リンク交通量 / および旅行時間 / () は四段階推定法により算出上位問題の制約に従う 3 交通手段分担モデル P U / / ep / epu U epu * X / * X / 自家用車バス,,, : 説明変数 ( 旅行時間, 費用など ),,, : 係数

13 4 リンク配分モデル d Y m rs : rs 間経路上交通量 q rs : rs 間交通割合 δ, rs : リンクが経路上にあれば旅行時間待ち時間最小化 rs 間交通量非負制約専用レーン有リンク専用レーン無リンク定式化 - 下位問題 s r s r q rs rs rs rs rs rs,,,, w q, w mw 目的関数制約条件自家用車バス非負制約 q : ノードでのバス利用需要

14 一般化ベンダース分解の適用 3 制約には二値関数 Φ を含みながら, 上位問題目的関数はフロー関数で構成されている Φ の固定つの問題に分枝二段階問題 Z と下位問題 ( リンク配分モデル ) タスク : サブ問題の双対問題の構築上位問題目的関数に代替する

15 一般化ベンダース分解の適用 4 d Y m s r s r q rs rs rs rs rs rs,,,, Z と 4 リンク配分モデル ( 自家用車 ) ラグランジュ関数 Y を定義 d Y ω,ω : ラグランジュ乗数 : 繰り返し回数目的関数制約条件 d d d Y Z d d d d 上位問題目的関数 Z の第項 Z Z mp s mp l O W Z m Z, 式より

16 一般化ベンダース分解の適用 5 Z と 4 リンク配分モデル ( バス ) ラグランジュ関数 W を定義 w W μ, μ : ラグランジュ乗数 : 繰り返し回数目的関数制約条件上位問題目的関数 Z の第項 Z w W Z w q, w mw W W Z mp s mp l O W Z m Z 3 4 3, 4 式より

17 一般化ベンダース分解の適用 6 Z 3 と Z 4 Z Z l mp Z 3 4 O Z =Z +Z +Z 3 +Z 4 : 原問題の上界 s mp 緩和問題 v m v v Z,,,,, E dg v: 原問題の緩和問題, 下界を与える

18 最適化アルゴリズム 7 Sep 初期値の設定上界 = 下界 =- 初期解 {Φ } = ε: 収束定数 Sep Φ を固定下位問題を解き, /, ω, ω, μ, μ, Z (=Z +Z +Z 3 +Z 4 ) を算出上界 =m( 下界, Z ) Sep /, ω, ω, μ, μ, Z (=Z +Z +Z 3 +Z 4 ) を固定緩和問題を解き, Φ と v を算出下界 =v 上界 - 下界 v ε 終了 else =+, Sep に戻る

19 数値計算例 8 ノード数 : 38 リンク数 : 49 組 (98 方向 ) 各 OD 間で /h の交通量 OD ノードはネットワーク周囲と 6, 7 の右のノード ( 青の四角 ) ペア, 38,/h の交通量 9 バス路線 /5m( 路線 -7), /m( 路線 8,9) 各リンク長 : 4m 各リンク車線速度制限 5m/h 予算制約より, 専用レーンは最大 3 組 3 交通手段分担モデルパラメータ (,,, )=(, 6,.9,.) 上位問題目的関数パラメータ (α, β, γ, η)=(.5,.5, 5, ) 専用レーン導入候補

20 数値計算例 9,,,,,,,,,,, 3, 3 Cp Cp Cp Cp : 自由流でのリンク通過時間 Cp -, : リンクの交通容量 : 専用レーンなし, Cp, =,8 veh/h : 専用レーン有り, Cp, =, veh/h コスト関数 ( 専用レーン ): コスト関数 ( 普通車線 ): 最適値 9/ 回の計算で最適組み合わせを発見

21 まとめネットワークレベルで, バス専用レーンの最適導入の新しい手法を提言一般化ベンダース分解を適用, 効率的に最適値に収束

22 本研究の使い道最適化の計算手法混合整数計画専用レーンの導入問題最適化地震後に緊急車両レーンを設ける, とか

23 数式 = : ネットワーク集合 : 優先レーン導入不可のリンク集合 : 優先レーン ( 専用レーン ) のリンク集合 : 混合交通リンクの集合 ( 専用レーンなし ) : バス経路, 徒歩リンク, 乗り換えリンク含む +/- : リンクの集合 (rom/o ode ) L: バス路線の集合 : バス停の集合 (=Σ p L p ξ p, ): リンク上のバス頻度の合計 p : バス路線 p の頻度 ξ p, : バス路線リンク行列 (): 旅行時間 l : リンク () の長さ s : リンクのバス旅行時間 -, / (): リンク () の旅行時間, : 自家用車, : バス, 交通量の関数 : 専用レーンあり, : 専用レーンなし / : リンクの交通量 w : ノードでの待ち時間 α, β, γ, η( ): 重みづけ, 単位変換, 相対的重要度

24 3 下位問題 3 rd model w q s,.. q : ノードでのバス利用需要旅行時間 + 待ち時間最小化 rs 間交通量非負リンクの自家用車交通量ノーマルか対のリンクを流れる制約定式化 - 下位問題 w mw

25 書式の間 4 開始双対問題定式化, w 最小化 u 固定, y について解く, 最大化 y 固定, u について解く, w 最小化 w Yes 終了 No ナップサック問題 (KP)

Microsoft PowerPoint - mp11-02.pptx

Microsoft PowerPoint - mp11-02.pptx 数理計画法第 2 回塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 前回の復習数理計画とは? 数理計画 ( 復習 ) 数理計画問題とは? 狭義には : 数理 ( 数学 ) を使って計画を立てるための問題広義には : 与えられた評価尺度に関して最も良い解を求める問題