ネットワーク上の行動モデルと観測理論（動的交通流モデル編）
井料隆雅（神戸大学）

27/10/2012

Takamasa Iryo1

ネットワーク交通量配分• 所与の起終点を旅行する車両が選ぶ経路を（一般化交通）費用に応じて決める．
• リンク旅行時間関数で旅行時間を決定する．
– リンク交通量に応じてリンク旅行時間を決める．
– リンク交通量はそのリンクを使う経路の交通量の合計で決定する．

• Wardropの第１原理「各ODペアにおいて，利用されている経路は，必ずその経路の費用が最小である」
27/10/2012

Takamasa Iryo2

利用者均衡配分問題(UE)• 所与のネットワークとOD交通量に対して，Wardropの第１原理を満たすように車両を各経路に配分する問題．
• 凸計画問題に置き換えて解ける．
Beckmann et al. (1956)– Frank-Wolfe法が（いまでも）著名

27/10/2012

Takamasa Iryo3

おまけ：Frank–Wolfe algorithm• http://en.wikipedia.org/wiki/Frank%E2%80%93Wolfe_algorithm– ..(snip).. While the method is slower thancompeting methods and has been abandoned as a
general purpose method of nonlinear
programming, it remains widely used for speciallystructured problems of large scale optimization. In
particular, the reduced gradient method remains
popular and effective for finding approximate
minimum–cost flows in transportation networks,
which often have enormous size.
27/10/2012

Takamasa Iryo4

UEの「よい」性質• 均衡解は必ず存在する．
– もし存在しないことがあれば，将来を予測するための一般的な規準として採用できない．

• 均衡解は唯一である．
– もし複数あれば，将来どれが実現するかを別途考えなくてはならない．

• 均衡解は安定である． Smith(1984)– もし安定でなければ，利用者行動は均衡解の周辺にとどまってくれない．
27/10/2012

Takamasa Iryo

5

なぜ「よい」性質を持つか• 静的なスキームでは相互作用が対称– 同じリンクを使う２台の車両は，互いに同じ量だけ外部費用を他方に与えている．

• 対称な相互作用を持つシステムは，Potential Gameと呼ばれるゲームで記述できる．Monderer & Shapley (1996)．
– Every finite ordinal potential game possesses a purestrategy equilibrium. (M&S)– … Then, the better-response dynamics given by (11.23)
converges a.s. to the set of Nash equilibria(Fernando Vega-Redondo, 2003)
27/10/2012

Takamasa Iryo6動的な交通量配分• 動的な交通流モデルで交通量配分を行うこと．
• 静的な交通量配分問題とは，具体的に何が異なるのだろうか？
– 各時間帯で静的配分を解けば動的配分になるのか，といえば，そんなことはない！

• ３つの問題○ 交通量の非保存性○ 混雑の時間軸方向の外部性○ 利用者が出発時刻を選びうる
27/10/2012

Takamasa Iryo

7

動的な混雑モデルと交通量保存則• 動的な混雑モデルでは，「時刻ごとにリンク旅行時間が異なる」• 時刻ごとにリンク旅行時間が異なれば…
リンク入口でのフローと，リンク出口での交通量が一致するとは限らない．

27/10/2012

Takamasa Iryo

8

車両軌跡

あるリンクの範囲

位置

車頭間時間

走行速度

時刻
27/10/2012

Takamasa Iryo

9

第１車両の旅行時間あるリンクの範囲

位置

車頭間時間が広くなっている

最終車両の旅行時間

時刻
27/10/2012

Takamasa Iryo10

交通量の非保存性• 静的配分：上流と下流の交通量は同じ
動的配分：
上流と下流の交通量は同じとは限らない．
• その結果，静的配分では下流側の混雑が過大評価されることがある．
27/10/2012

Takamasa Iryo11

交通量の非保存性• 静的配分の場合

2000 veh/h

2000+800=2800 veh/h2000 veh/h

800 veh/h

下流側では，2800 veh/h の交通量に対応する混雑が発生する
27/10/2012

Takamasa Iryo12

交通量の非保存性• 動的配分（ボトルネックモデル）の場合
交通流がしぼられる
2000 veh/h

800+1200=2000 veh/h1200 veh/h

容量1200 veh/h
800 veh/h

下流側では，2000 veh/h の交通量に対応する混雑しか発生しない！
27/10/2012

Takamasa Iryo

13

混雑の時間軸方向の外部性• ある混雑するリンクに車両を追加したとき，それまでいる車両のこうむる旅行時間はどのようになるか？
• 静的配分の場合：同じリンクにいるすべての車両の旅行時間が増大する．

27/10/2012

Takamasa Iryo

14

混雑の時間軸方向の外部性• 動的配分の場合：
追加された車両以降にリンクへ流入する車両の旅行時間が増大する．

• 外部性が対称でないので，Beckmann et al.
(1956)の方法によって最適化問題を構成することができない．
27/10/2012

Takamasa Iryo

15

利用者が出発時刻を選びうる• 静的配分：利用者は，指定されたODで道路を使用することを決定すれば，あとは経路しか選ぶものはない．
• 動的配分：利用者は経路以外に出発時刻も選択できる．
出発時刻の選択の有無で，問題の性質，さらには渋滞緩和施策まで異なってくる．
27/10/2012

Takamasa Iryo

16

動的均衡配分問題• 動的なスキームの下で均衡配分問題を行う．
• ２つの基本的な枠組み– 出発時刻固定：経路のみ自由に選択– 出発時刻も経路も自由に選択• 到着地にスケジュール制約がある．

• Wardropの第１原理を規準とすることは同じ.

27/10/2012

Takamasa Iryo

17

出発時刻固定• 均衡解の存在（Smith and Wisten, 1995）• 均衡解の一意性（か凸集合）限定的！
（1経路１ボトルネック: Mounce and Smit, 2007）（1起点１終点：Mounce, 2007）（一意性への反例：Iryo, 2011)←New!!

• 1起点多終点ネットワークの解法限定的！
（Kuwahara and Akamatsu, 1993）（井料, 2011：ゲーム理論による定式化）※ 一般ネットワークで確実に解を出す解法は知られていない！

27/10/2012

Takamasa Iryo

18

Bottleneck

Destination

１起点多終点ネットワーク

OriginOne-to-Many Network
またはSingle Origin NetworkOrigin

Bottleneck

Destination

１経路１ボトルネックネットワーク
One (Single)
Bottleneck per RouteNetwork
27/10/2012

Takamasa Iryo

19

出発時刻選択問題• １経路１ボトルネックの出発時刻選択問題は，ボトルネックの容量をどのように各車両に配分するか，という線形計画問題に置き換えられる．（井料他，2005, Iryo and Yoshii, 2007）• 需要制約・容量制約の下で，全車両のスケジュールコストの和を最小にするLPを組む．
• LPの双対変数の解がボトルネックコスト．
– 遅れ時間に相当する．
27/10/2012

Takamasa Iryo20

LPによる出発時刻選択問題のポイント• もし，ボトルネックコストを渋滞でなく，混雑料金により回収する方策をとれば，「均衡状態」＝「最適状態」にできる！
• 出発時刻選択問題の定式化が適用できる環境であれば，最適状態を市場原理によって実現できる可能性がある！
– でも，どうやって市場化すればいいの？

27/10/2012

Takamasa Iryo

21

通行権取引制度とオークション• 渋滞を解消させる方法としては，もともと，「道路の利用権を予め予約する」という考えがあった（赤羽他, 2000）• その利用権を市場で取引させれば，均衡状態でのボトルネックコストに対応する適正な価格が自動的に付くのではないか？
（赤松他，2006; 赤松, 2007：一般ネットワーク）• オークションによる値付けのメカニズムの詳細分析（和田・赤松, 2011）27/10/2012

Takamasa Iryo22

観測と交通システム• 観測理論というからには，その目的がほしい．
• よりよい交通システムの実現ために観測システムを構築するのであれば，それは，交通システムと一体化するべきである．
– 鉄道や航空にはそういう発想があるようだが，上下分離によるインフラと規定されている道路にはそのような発想が完全に欠落している．
– 何を測れば何がわかるのか？
GPSがそんなに万能なのか？？
27/10/2012

Takamasa Iryo

23

References
••
•
•
•
•

••••••••••

Smith, M. J. (1984) The Stability of a Dynamic Model of Traffic Assignment - an Application of a Method of Lyapunov.
Transportation Science, 18(3) : 245-52.
Beckmann, Martin, C. B. McGuire, and Christopher B. Winsten. Studies in the Economics of Transportation. New Haven: Yale
University Press, 1956.
Monderer, D., and Shapley, L. S. (1996) Potential Games. Games and Economic Behavior, 14(1): 124-43.
Vega-Redondo, F. (2003) Economic and the Theory of Games. Cambridge: Cambridge University Press.
Smith, M. J., and Wisten., M. B. (1995) A Continuous Day-to-Day Traffic Assignment Model and the Existence of a Continuous
Dynamic User Equilibrium. Annals of Operations Research, 60: 59-79.
Mounce, R. (2007) Existence of Equilibrium in a Continuous Dynamic Queueing Model for Traffic Networks. In Mathematics
in Transport, edited by B. G. Heydecker, 219-29. Oxford: Elsevier.
Mounce, R., and Smith, M. J. (2007) Uniqueness of Equilibrium in Steady State and Dynamic Traffic Networks. In
Transportation and Traffic Theory, edited by Richard E. Allsop, Michael G. H. Bell and Benjamin G. Heydecker, 281-99. Oxford:
Elsevier.
Kuwahara, M., and Akamatsu, T. (1993 ) Dynamic Equilibrium Assignment with Queues for a One-to-Many Od Pattern." InTransportation and Traffic Theory : Proceedings of the 12th International Symposium on the Theory of Traffic Flow andTransportation, Berkeley, California, USA, 21-23 July, 1993, a Symposium in Honor of Gordon F. Newell, edited by Carlos F.
Daganzo, 185-204. New York: Elsevier.
Iryo, T. (2011) Multiple Equilibria in a Dynamic Traffic Network, Transportation Research Part B, 45(6): p. 867-879.
井料隆雅. (2011) 車両を離散化した動的交通量配分問題のNash均衡解の解法, 土木学会論文集D3, 67(1): p. 70-83.
井料隆雅, 吉井稔雄, 朝倉康夫. (2005)出発時刻選択問題の均衡状態に関する数理的分析. 土木学会論文集, 779/IV-66:
105-18.
Iryo, T., and Yoshii, T. (2007 ) Equivalent Optimization Problem for Finding Equilibrium in the Bottleneck Model withDeparture Time Choices. In Mathematics in Transport, edited by B. G. Heydecker, 231-44. Oxford: Elsevier.
赤羽弘和，桑原雅夫，佐藤拓也. (2000) 高速道路の利用予約制に関する基礎研究，土木学会論文集，IV-49: 79-87.
赤松隆, 佐藤慎太郎, Nguyen, X. L. (2006) 時間帯別ボトルネック通行権取引制度に関する研究. 土木学会論文集D, 62(4):605-20.
赤松隆. (2007) 一般ネットワークにおけるボトルネック通行権取引制度. 土木学会論文集D, 63(3): 287-301.
和田健太郎, 赤松隆. (2011) ネットワーク通行権取引市場のオークション・メカニズム.土木学会論文集D, 67(3): 376-389.

27/10/2012

Takamasa Iryo24