モンテカルロ木探索を用いたユーザ個人の嗜好を考慮した経路推薦手法の高速化

摘要

スマートフォンやタブレットの普及が進み，経路推薦・案内サービスが幅広く利用されている．従来のインターネット上で提供されてきた経路推薦・案内サービスでは，経路長・所要時間・料金の点で最適化した経路を推薦するサービスが主流だが，これらのサービスでは各ユーザの区別がされない．このため現在地や目的地等の入力情報が同じであれば，各ユーザは安全性や快適性の面から多種多様な嗜好を有しているにもかかわらず，異なるユーザでも同一の経路推薦がされることになる．これまでに我々は，モンテカルロ木探索を用いた経路推薦手法(P-UCT 手法) を提案し，同手法がユーザ個人の嗜好を考慮した経路を推薦することを，評価実験によって確認している．ところが，目的地点に到達するまでランダムなモンテカルロ・シミュレーションを繰り返して経路を探索するため，探索対象の経路長が大きくなると実行時間が指数的に増大してしまう問題がある．本稿では，モンテカルロ木探索を用いたユーザ個人の嗜好を考慮した経路推薦における高速化手法を提案する．提案手法では，目的地点周辺範囲(AD) を新たに定義・導入することで，従来のP-UCT 手法のアルゴリズムの高速化を図る．