Risk-averse user equilibrium traffic assignment: an application of game theory Michael G. H. Bell, Chris Cassir Transportation Research Part B, Vol. 36, (2002), pp.671-681 20140426 BinN論文セミナー#3 M2伊藤篤志不確実なリスクを回避するネットワーク利用者の経路選択行動を記述macroscopic,決定論交通日均衡範分“利用される経路は全て最小コスト” ⇔”最小コストを超えるどの経路も利用されない” microscopic,催重系論n人1OD ⑤解法アルゴリズムの提示⑥簡易ネットワークへの適用既律研究¦ Uchida, Iida (1993) ¹)仮定:経路選択時,ネットワーク利用者は安全マージンを考えている. →|実行旅行時間|の概念ドライバーが出発前にあらかじめ見積もる旅行時間実効旅行時間= 予定到着時刻–出発時刻=平均旅行時間+|安全マージンσφ-1 l o Y ifニ<ニ! σ.旅行時間分布の標準偏差! γ:遅延に対するペナルティ! Φ -1:生起確率密度関数の逆関数0 otherwise問題点:混雑状態の発生確率を実データから算出する必要あり

ネットワークの条件
・ひとつのODペア・複数の経路選択肢・n人の一様な利用者h 経路交通量ベクトルh;:経路jの交通量g:経路コストベクトルg;(h): h条件下での経路jのコストh = (h , h , h ) g(h) = (10, 10, 20) ⇔ g 1(h) = g 2 (h) < g 3 (h)利用者あり利用者なし交通量均衡配分の必要十分条件最小コストでない経路jは選択されないg j (h)> min g k (h)⇒ h j = 0 h j > 0 ⇒ g j (h) = min g j (h) = g oD (h)利用者がいる経路jは最小コスト

ネットワークの条件
・ひとつのODペア・複数の経路選択肢・n人の一様な利用者利用者a (戦略s。) n次元混合戦略集合sg:利用者aの混合戦略s-g:利用者a以外の利用者の混合戦略π ai:利用者aが経路jを選択する純戦略p j:利用者aが経路jを選択する確率p:経路選択確率ベクトル利用者aが被るコスト期待値利用者aが経路iを選択して被るコスト経路iのコスト・ネットワーク利用者は一様である・大数の法則より, h→pn |$_a, π aj |= g ; (h利用者aが経路jを選択して被るコスト本手法(混合戦略ナッシュ均衡)の必要十分条件c α (s_α, π αj )> min c α (s_α, π αk )⇒  p αj = 0利用者aが最小コストでない経路jを選択する確率は0 P αj > 0 ⇒ c α (s_α, π αj )= min c α (s_α,π αk )経路jの選択確率が正ならば,コストは最小不確実なリスクを回避するネットワーク利用者の経路選択行動を記述macroscopic,決定論交通日本海海御御礼分“利用される経路は全て最小コスト” ⇒"最小コストを超えるどの経路も利用されない" ①等価microscopic,衛星等論n人1OD ⑤解法アルゴリズムの提示⑥簡易ネットワークへの適用

ネットワークの条件
・ひとつのODペア・複数の経路選択肢・n人の一様な利用者と1体のdemon demonの参加ネットワーク利用者のコストを最大化したい→シナリオkの発生によりリンクコスト増大G定式化利用者a min c.シナリオk (リンクダメージ)の発生確率全シナリオdemon I k C demon,k s:利用者の混合戦略集合s.g:利用者a以外の利用者の混合戦略πρj:利用者αが経路jを選択する純戦略利用者aが経路iを選択する確率Pai経路選択確率ベクトルプレイヤーiにとってのコストdemonがシナリオkを選択したときのコストnが大きいとき,均衡点を特定するのは難しい→2階最適化問題への書き換えを提案

ネットワークの条件
・ひとつのODペア・複数の経路選択肢・n人の一様な利用者と1体のdemon B 1 2階最適化問題定式化max , 9 k 8 jk (h )h , q全経路,全シナリオにおける期待コストを最大化! qk:シナリオkの発生確率q:シナリオ発生確率ベクトルg ik (h):シナリオk時の経路jのコストh経路jの交通量Lower ( Vu ( h ) subject to l x dx V ,, = min . I k h Uシナリオk時,リンクuの流量に依存するコストリンクu交通量ダミー変数全リンク,全シナリオにおける期待コストを最小化Upper
・大数の法則より, nが大きいほど|ネットワークコスト|は個々の期待コストの和に近接8 jk (h)h ,l Upper C demon,k (S) < max C demon,r (S) ⇒ q k  = 0 9 k > 0 ⇒ C demon,k (S) = max C demon,r (S)コストの総和cdemon,kが最大でない場合,シナリオkの発生確率q,は0シナリオkの発生確率qçが正の場合,コストの総和Cdemon,kは最大・大数の法則より, nが大きいほどl経路iの期待コストには個々の期待コストに近接Ill 8 ik (h)qk | Cak (S-a , π aj Ik = C a (S-a , π aj Lower C a (S_a , π aj )> min c a (s_a , π ar )⇒ p aj = 0 P aj > 0 ⇒ c a (S_a , π aj ) = min c a (s_a, π ar )経路jのコストが最小コストより大きいとき, jを選択する確率は0経路jを選択する確率が正のとき, jのコストは最小これらの条件は,非協力混合戦略n+1プレイヤーナッシュ均衡問題における必要十分条件を満たす

ネットワークの条件
• m組のODペア・複数の経路選択肢・n人の一様な利用者とm体のdemon Bշ定式化Upperod max , IkOD 8 jkOD (h)h jOD qOD h = (h 1, hշ,…., hm) Lower od min 9 kod hOD t uk (x)dxは全ての経路交通量を表す共通ベクトルhによって結びつく2階平行問題Bշ標準器不確実なリスクを回避するネットワーク利用者の経路選択行動を記述macroscopic,決定論交通日本海海御御礼分“利用される経路は全て最小コスト” ⇔”最小コストを超えるどの経路も利用されない” ①等価microscopic,衛星等論n+1人複数OD ⑤解法アルゴリズムの提示⑥簡易ネットワークへの適用
B,問題を解くにあたり,逐次平均法(MSA)を用いるStep 1 各ODペアに対する期待リンクコストを算出Step 2 最小コストの経路を示すOD表を読み込むStep 3｜OD依存リンク交通量をMSAによって更新三輪,山本,竹下,森川I²) MSA: hod = - hod   1+ hod h op*:各イタレーションStep2で得られたOD交通量Step 4 最大期待コストをもつOD依存損失シナリオを特定Step 5  OD依存リンク欠損確率をMSAによって更新Step 6 |収束するまでStep 1に戻る
図コスト期待値→傾は急速に収束図各リンクにおけるシナリオ発生確率→対象性により,シナリオ発生箇所が特定されず収束しないまとめ不確実なリスクを回避するネットワーク利用者の経路選択行動を記述→ゲーム理論を用いた新しい手法を提案2種類のプレイヤーによる,非協力混合戦略ナッシュ均衡→demonは各ODペアの最も脆弱なリンクを特定課題制約的な仮定1. demonはネットワークの利用者コストを最大化するということ→交通利用者がリスクに対して悲観的過ぎる2. どのプレイヤーも次の動きに関する情報をもたない→demonの支配が強すぎるため,現実との整合性に欠ける1) T. Uchida, Y. Iida: Risk assignment model considering risk of travel time variation, Proceedings of the 12th International Symposium on Transportation and Traffic Theory, pp.89-105, 1993. 2)三輪富生,山本俊行,竹下知範,森川高行:プローブカーの速度情報を用いた動的OD交通量の推定可能性に関する研究, 2007.純戦略各プレイヤーが選択し得る戦略混合戦略確率的に意思決定される戦略ナッシュ均衡全プレイヤーが相手の戦略のもとで自身の利益を最大化するよう行動するとき成立する均衡状態(cf.男女の争い)