複数OD経路選択ゲームの均衡解探索の高速化 (高度情報化社会に向けた数理最適化の新潮流)

Abstract

交通割当問題は広く研究されてきたテーマである. この問題は都市工学とゲーム理論の2つの側面から成り立つものである. 本研究ではゲーム理論の視点から交通割当問題をネットワーク上の混雑ゲームとして扱った. 交通割当問題は混雑ゲームの文脈においては利己的経路選択ゲームと呼ばれることがある. 利己的経路選択ゲームにおいて, 我々はプレイヤーの意思決定による均衡点の探索手法を提案する. 各プレイヤーは出発地から目的地までの各経路に流す流量を決定する. よく知られた探索手法としては辺流量を利用して探索するFrank-Wolfe法があり, この手法では高速に求解可能であるものの, 辺流量を利用していることから表現力が弱いという問題が存在する. そのため, 本研究ではさらに複雑な現象をモデリングするための手法として経路流量を考慮する手法を採用する. この手法ではネットワーク上の経路を全て考慮する必要があるため, 均衡解探索に莫大な時間がかかってしまうことが知られている. 本稿では, 複数OD利己的経路選択ゲームにおける求解手法と, 一般的な利己的経路選択ゲームに対する求解手法及びその高速化手法について扱う. 我々のアルゴリズムではレプリケータダイナミクスを反復求解手法として用いる. レプリケータダイナミクスによる求解手法では, 扱うネットワーク上で各反復ですべての経路について計算を行うため計算時間が非常に大きいものとなる. そこで, 提案手法では均衡解において利用されない経路を求解前に削除することで計算時間を短縮する. 本稿では計算機実験により提案するアルゴリズムを評価する.