2014 BinN論文セミナーについて

■内容• 論文ゼミは，BinNで毎年行なっているゼミの1つで，昨年度から外部に公開してやっています．
• 毎週2人のひとが，各自論文（基本英語）を読んでその内容をまとめ，発表・議論するものです．
• 単に論文を理解するだけでなく，先生方を交えてどのように応用可能か，自分の研究にどう生かせそうかなどを議論できる場となっています．

論文ゼミ

■基本事項• 日時：毎週金曜日19:00 – 21:00（羽藤先生の都合により，曜日が水or土曜に変わることがあります）• 場所：工学部1号館4階セミナーA• 発表：2人（BinN学生1人，ゲスト1人？）■発表について• 4月の間は，BinN学生で回します．
• 5月以降（7月末まで），1人1回〜2回程度，発表をしていただこうと考えています．（B4は除く？）

論文ゼミ

■主なテーマ•••••••

古典的な基礎理論
課金・制御（最適化理論・配分）
回遊，アクティビティ（行動モデル）
Social Networks，対人相互作用（ゲーム理論）
歩行者，避難（シミュレーション）
GPS，ビッグデータ（統計・確率過程）…
※各自テーマに沿った論文を選んでもらいます．
（いくつかのテーマについてはこちらでリストも作成しています．）

論文ゼミ

4/9（水）2014年度 第1回BinN論文ゼミ＠セミナーA

Fosgerau, M., Frejinger, E., Karlstrom, A.,

A link based network route choice modelwith unrestricted choice set
Transportation Research Part B, 	Vol.56, pp.70-80, 2013.

D1 大山雄己１■経路選択モデル• 経路選択モデルはインフラ投資計画，交通規制，容量制御といった政策に大きな役割を果たしてきた．
• 近年，GPS技術の進展によって，正確な経路情報が得られるようになっている．（実際の経路が直接観測可能）• さまざまな経路選択の要因に対して，パラメータ推定の精度が重要．

リンクベースの再帰的な経路選択モデルの提案（Recursive Logit Model）

はじめに

２

■リンクベースの動的経路選択モデル• 簡単のため，時間に静的なネットワークを考える．
• 各意思決定において，リンクｋの sink-nodeに接続するリンク集合が選択肢となる．
選択肢集合• 目的地についてはダミーリンクによる吸収状態を考える．

吸収状態
ダミーリンク問題設定

３■リンクベースの動的経路選択モデル• 各選択肢は固有の効用関数と，そのリンクを選んだ場合の目的地までの期待効用を考慮して選択される．
誤差項：ガンベル分布

価値関数

(1)
(2)

Bellman 方程式 (Rust,1987)

n : 意思決定者 µ : スケールパラメータ€€€

リンクの説明変数

€

問題設定

４

■リンクベースの動的経路選択モデル• 各選択肢は固有の効用関数と，そのリンクを選んだ場合の目的地までの期待効用を考慮して選択される．
誤差項：ガンベル分布(1)(2)
状態 k におけるリンクa の選択確率は，ロジットの形式で表される．

€€

(3)

価値関数は ログサム変数を用いて次のように書き換えられる．

€：のとき1，それ以外で0€(4)問題設定

５■ベルマン方程式の解法
式（4）を変形すると，(5)行列をを要素として持つベクトルとすれば，

€
なお，は

b(6)

は，

€€
(4)

モデル特性

６

■ベルマン方程式の解法(6)⎛ 1 V (1) ⎞⎜e µ ⎟⎜!
⎟⎜⎟
1⎜ µ V (k ) ⎟⎜e⎟⎜⎟
1⎝⎠
€

=

⎛0⎜
⎜
⎜"⎜
⎜⎜
⎝0⎞ ⎛ µ1 V (1) ⎞⎟⎟ ⎜e⎟ ⎜! € ⎟⎟⎟ ⎜1⎟ ⎜ µ V (k ) ⎟⎟⎟ ⎜e⎟⎟
0 ! 0 0 ⎠ ⎜⎝1⎠€!

+⎛0⎞⎜ ⎟⎜ ⎟⎜! ⎟⎜ ⎟⎜0⎟⎜ ⎟⎝1 ⎠

(I − M) −1 が存在することが，解を持つ条件となる．
€

吸収マルコフ連鎖の基本行列（佐佐木，1965）€€€

ノードに接続する経路の数や，効用の確定項の値のバランスによって決まる．

€(5)

モデル特性

７

■経路の選択確率• 出発地から目的地までの「経路」は，一連のリンクとして記述され，コスト（効用）はリンクコストの和となる．
ki+1ki+2ki€€€• モデルのマルコフ性より，リンクベースの選択確率を用いて経路 σの観測尤度を算出することができる．

(7)
€(3)

€

(5)

€

モデル特性

８

■経路の選択確率
式（3）,（5）を用いれば，式（7）はより簡単に，(8)
1P(ki+1 | k i ) の分母は e µ V (ki )（式5）
さらに，€とおけば，€€(9)Ω ：経路の選択肢集合

経路の選択確率もロジット型で表わせ，2経路の確率比ものみに依存する．

€€

(3)

€(5)

(7)

モデル特性
€９

■リンクフロー• リンクベースの選択確率は交通量の予測・算出にも適用できる．
• 簡単のため，複O単Dのネットワークで考える（展開可能）．
P(a | k)

F(k)

€G(a)

€€

F(k) ：リンク k （k ∈ A）の交通量
G(a) ：リンク a を通過後，目的地 D に向かう交通量
このとき，リンクaに存在する交通量は，

€€

(10)
(11)
€

モデル特性
€

■経路選択モデルにおける相関10• ここまで，吸収マルコフ連鎖 × Bellman方程式による動的経路選択モデルを記述した．
• しかしロジット型配分では経路間のリンク重複が問題となる．
下2経路の相関が考慮されず，平等に配分されてしまう．
・Path Size Logit (Ben-Akiba and Bierlaire, 1999)
・C-Logit (Cascetta et al., 1996)
経路列挙が必要な（not link additive）ため，提案したモデルには適用できない．

リンクa を通過する経路数

Path-Size 修正項（重複が魅力減少）

Link Size (LS) 修正項の導入

Link Size の導入

11■Link Size (LS) 修正項• 経路選択肢の数の代わりに，期待リンク交通量を用いる．

(12)：設定する（説明変数の）パラメータは，発生交通量をとしたときの，式（11）の解である．
€(13)

=

⎛1 ⎞⎜ ⎟⎜0⎟⎜! ⎟
⎜ ⎟
⎜ ⎟
⎜ ⎟
⎝0⎠

€
各リンクのLS値は0~1をとる．

€(11)

€

Link Size の導入

■モデル間比較

12・Uターン不可
・コストはリンク長のみ（＝-1.5）• RL（Recursive Logit）では，MNLと同様に重複が考慮されず等配分されてしまっているが，LSを導入することで改善（PSLと同等）．
• 周回経路に微小量が配分されており，正確な等配分にはならない．
• 精度は同等だが経路を列挙する必要がない点で優れている．

Link Size の導入

13■Link SizeとLink効用の関係

リンク長パラメータ

LS修正項のパラメータ

Link Size の導入

14■最尤推定法••••価値関数の計算には，Rust(1987)のNFXP法に似たアプローチをとる．
（詳細は書いていない：リクエストすればコードがもらえる）
BFGS法で各反復の最適化問題を解く．
無限周回経路の除去等，現実と整合性のある範囲で仮定を置き式（6）の計算性を確保．
さらに正確性を増すために，Analytical Gradient を導入．
（※参考） 対数尤度関数は，(14)なので，Analytical Derivative は，

€(8)
(6)

€(15)

€モデル推定15■最尤推定法（※参考つづき）(15)
式（6）を偏微分して，

€€

(16)

(17)

€
(8)
(6)

€

モデル推定

16

■効用関数の設定• ボルレンゲ（瑞典）の実ネットワーク（3077ノード, 7459リンク）を用いて計算．

(13)：リンク a の旅行時間：左折ダミー（左方向に40°以上であれば1，それ以外0）€：交差点が多いリンクで1，それ以外0のダミー：Uターンダミー（回転角度177°以上で1，それ以外0）

1．シミュレーションデータでのモデル推定・検証
2．GPSデータを用いたパラメータ推定

モデル推定

17

■シミュレーションデータ
••••10のODサンプルに対して，500台ずつ流してデータを作成．
各ODに対して，平均で39の経路（35~44）が観測された．
全体の0.7％が周回経路を含んでいるものだった．
旅行時間は平均 9 min (8.8min ~ 12.3min).

モデルの仮定の正しさと，推定可能性を検証

(13)

モデル推定

18

■実データ推定• 200台の車から2年間で得られたGPSデータを使用．
• 正規化ののち，1832トリップ（最小5リンク）データで推定．
• 466の目的地が観測．サンプル数：37,000（リンク選択）．

説明力が高い．

LS項を入れることで精度向上．

モデル推定

19

■結論
• 選択肢集合の制約（経路列挙）がない経路選択モデルを提案した．
• リングベースの選択モデルから，各経路の選択確率がMNL型で記述できることを証明した．
• リンクの和として記述される経路に対してLink Size項を導入し，経路の重複を考慮し，良好な推定結果を得た．

まとめ

ご清聴ありがとうございました．