DEIM Forum 2016 H1-6

カーナビ利用時の運転者ルート選択意図の学習およびルート推薦手法の実験的評価
濱田 恵輔†

中島 伸介††

北山 大輔†††

角谷和俊††††† 京都産業大学大学院 先端情報学研究科 〒 603–8555 京都府京都市北区上賀茂本山†† 京都産業大学 コンピュータ理工学部 〒 603–8555 京都府京都市北区上賀茂本山††† 工学院大学 情報学部 〒 163–8677 東京都新宿区西新宿 1 丁目 24 番 2 号†††† 関西学院大学 総合政策学部 〒 669–1337 兵庫県三田市学園 2 丁目 1 番地
E-mail: †i1458067@cse.kyoto-su.ac.jp, ††nakajima@cc.kyoto-su.ac.jp, †††kitayama@cc.kogakuin.ac.jp,††††sumiya@kwansei.ac.jp
あらましカーナビゲーションシステムは非常に利便性の高いものだが，常に運転者の意向に沿った経路推薦を行えているわけではない．例えば，カーナビが提示する推薦経路に対して，運転者が意識的に別ルートを走行するケースを想定する．この際，カーナビは元の推薦経路に戻るような経路を再推薦することがしばしば起こるが，これでは運転者の意向に沿ったルートを提示しているとは言い難い．我々はこれまでに，多種コストを考慮しつつ運転者の意向に沿ったルート推薦が可能となるアルゴリズムを開発し，良好な結果を得た．本稿では，ドライバーの運転履歴からルート選択の傾向を反映した各コストに対する重みの計算方法を検討したので，実験結果を交えて報告する．
キーワード

情報推薦，経路探索，差異増幅アルゴリズム，カーナビゲーション

1. は じ め にることで，最適な経路の設定を行うものである（図 1）．なお，
この時の運転者の意向を推定する手法としては，差異増幅アル

近年，カーナビゲーションシステム（以後，カーナビと略しゴリズム [2] を適用する．差異増幅アルゴリズムは，ユーザがて記述する）は累計 6,700 万台を超える出荷 [1] が行われるほ“選択したもの”と “選択しなかったもの”の特徴的な差異を比ど広く普及している．また，これに併せて技術の高度化が進較し，これを増幅し，本来ユーザが求めていたものを推定しよ

み，VICS による渋滞情報や道路の規制情報等による推薦経路

うとする手法である．差異増幅アルゴリズムに基づく運転者のの変更や経路記憶（よく通る道を覚える）のように，運転者に意向を考慮した経路推薦手法について，既に評価実験を行い良とって利便性の高いナビゲートが可能となっている．さらに，好な結果を得た [3] [4]．

運転者がカーナビの推薦経路から外れた道を走行した場合でも，

ただし，先述の差異増幅アルゴリズムに基づく運転者の意向

カーナビにあらかじめ設定された基準に基づき経路を再探索し，を考慮した経路推薦手法で扱えるコストは，1 種類の場合にの提示することが可能である．

みと限られている．運転者の多くは目的地までの距離だけでな

しかしながら，利便性が向上した現在のカーナビでも運転者

く道路の道幅や信号数など様々な道路情報から総合的に判断しの意向が常に反映された経路推薦を行えているわけではない．

てルートの選択を行っている．そのため，各種コストを考慮でたとえば，カーナビが推薦するルートに対して，運転者が “意きることが望ましい．これまでに，各種コストを考慮すること識的”に別ルートを走行するケースを想定する．このとき，現が可能な差異増幅アルゴリズムに基づく運転者の意向を考慮し在のカーナビは，運転者の意向とは関係なく，あらかじめ設定

た経路推薦手法ならびに重視するコストの学習方法の提案と評された基準に従って経路の再探索を行い，その結果，カーナビ

価実験を行った [5]．

が元々推薦したルートに戻るような経路を運転者に提示するこ

ただし，運転者の重視するコストを反映した学習は行えたが，とがしばしば起こる．運転者が何らかの理由で “意識的”にカー

運転者の重視するコストが反映された経路推薦までは行えていナビが推薦したルートとは別のルートを選択したにもかかわらなかった．また，運転者が過去に走行した経路を反映した学習ず，カーナビが前述のようなルートを提示することは，運転者は行えていなかった．

の意向に沿った経路推薦であるとはいい難い．

本稿では，過去の経路選択を反映した運転者ごとの各コスト以上をふまえ，我々は運転者の経路選択の意向を自動的に判に対する重視する比率（重み）の学習方法についての提案を行断して，その意向に沿った経路を設定するアルゴリズムを開発

う．さらに，運転者の経路変更から各運転者の意向に沿うようした．このアルゴリズムはカーナビの推薦経路とは異なる経路

な学習を行い，運転者の意向に沿った経路推薦が行えるか，シを運転者が選択したときの，カーナビの推薦経路と運転者の選

ミュレータを使った評価実験を行ったので報告する．また，運択経路の差異に運転者の経路選択意図が含まれると考える．そ

転者の過去の経路選択の履歴を反映した学習方法についての評

して，その差異を増幅して経路探索コストにフィードバックす

価実験を行ったので報告する．

図 1 運転者の意向に沿った経路推薦アルゴリズムの概要

以下，本稿の構成を示す．2 章では，関連研究について述べ

転者が発車前に設定することを求めている．したがって，走行

る．3 章では，各種コストを考慮しながら運転者の意向を反映

中に状況が変わるような場面には対処することができない．こ可能な経路推薦方式について説明する．4 章では，各種コスト

れに対し，我々の手法は動的にコストを変化させるものであり，を統合する際に，運転者ごとの各コストに対する重視する比率

走行中であっても柔軟に対処する事が可能である．

（重み）の学習方法について説明する．5 章では，作成したシミュレータに基づく 2 種類の評価実験とその結果について述べる．6 章では，まとめと今後の課題について述べる．
なお，本稿で述べる提案手法とは，差異増幅アルゴリズムに基づく運転者の意向を考慮した経路推薦手法をさす．

2. 関 連 研 究
カーナビに関する研究としては，特に経路探索手法について数多く行われており [6]，ダイクストラ法 [7] や A *アルゴリズ

3. 各種コストにおける差異増幅アルゴリズムに基づく運転者の意向を考慮した経路推薦方式
本章では，各種コストが考慮可能な差異増幅アルゴリズムに基づく運転者の意向を考慮した経路推薦方式について説明を行う．まず，本手法の説明にあたり，3. 1 節では，本手法を用いるに至った背景について説明する．3. 2 節では，本手法である
単位経路毎の各種コスト統合方式について説明する．3. 3 節では，本手法の具体例を示す．

ム [8] といった最短経路探索のみならず，わかりやすく説明が容3. 1 各種コストを考慮した経路推薦における課題

易な経路を探索するアルゴリズム [9] のような，様々なアルゴ

本論文におけるコストは，
「距離」，
「道幅」，
「信号数」とした．

リズムを用いた手法が提案されている．狩野ら [10] は，動的に

これは事前アンケートより，運転者が経路選択をする差異に決コストを変動させるアルゴリズムを用いて，数分毎に道路のコめ手となる要因の大きいものを選んだ．なお，本論文におけるストデータを更新し，渋滞回避を可能にする手法の研究を行っ

各経路のコストとは，交差点と交差点の間の一区間を単位経路ている．しかし，このシミュレータでは渋滞や事故，工事等のとして，この単位経路毎におけるコストである．出発点から終情報のみ考慮しているため，運転者の意向を考慮するには不十点までの経路を総経路と呼び，総経路のコストをトータルコス

分である．また，明示された交通情報のみ適応可能であるため，

トと呼ぶ．このトータルコストは，総経路に含まれる単位経路

突発的な渋滞や事故に対応出来ない．これに対し，我々の差異のコストを合計することで求めることができる．

増幅アルゴリズムによる経路推薦手法では，運転者の選択意思

前述のとおり，各種コストを考慮した経路推薦を行う必要がに影響する情報の種類については特に制限はない．経路の選択ある．カーナビに目的地を設定してルートが提示され，推薦さ結果としてどの経路を重要視したのかという意向を反映しよう

れた経路から運転者が意識的に経路変更を行ったと想定する．

とするものである．

これまでに各種コストを考慮するための方法として我々は，3

根笹ら [11] は，運転者の提示する条件に合わせて経路推薦を

種類のコスト（距離，道幅，信号数）それぞれについて差異増行うアルゴリズムの研究を行っている．しかしながら運転者が

幅アルゴリズムに基づく経路推薦手法から推薦経路候補を求め提示する条件は，立寄地や道路の種類・大きさなどに限られてた．差異増幅アルゴリズムに基づく経路推薦手法にて扱えるコ

いる．また，稲垣ら [12] は遺伝的アルゴリズムを用いて重複しストは 1 種類限定であるため，3 種類のコストそれぞれについない複数の経路を表示させる手法の研究を行っており，運転者て推薦経路候補を求めた．その 3 つの推薦経路候補における統の意向に応じた経路を選出できる手法を提案している．

合コスト（3 種類のコストのトータルコストを統合）の比較か

しかし，これらの研究で提案している手法では，いずれも運ら最上位の経路を再推薦していた [13]．しかし，3 つの推薦経路

候補の比較を行う際，3 つの推薦経路候補の中に運転者の意向

を運転者毎に変更することで，係数の範囲を重要度に応じて大に沿った経路が存在するとは限らなかった．そのため，運転者

小に変化することが可能となる．

の意向には沿わない経路が最上位の経路になるケースがあった．

3. 2 単位経路毎の各種コスト統合方式

式（1），式（2）および実際の単位経路の距離を用いて，以下の算出式から統合コスト求める．

本論文では，前述の各種コストのトータルコストを統合して各種コストの考慮した経路推薦を行わず，単位経路毎に各種コ

0

L = L × Cw × Cs

(3)0

ストを統合して各種コストの考慮した経路推薦を行う方法につ

L ：統合コスト

いて説明する．単位経路毎に統合コストを求める際には，距離

L：実際の距離（m）

コストをベースとし，道幅コストと信号数コストは距離コスト式（3）により算出する統合コストを単位経路毎に求めるこに対する重みとしている．運転者がカーナビを使用する目的は，とにより，各種コストを考慮した経路推薦を実現する．また，

効率よく目的地に到着したいためであり，その中でも目的地に

本稿では想定するコストを「距離」，「道幅」，「信号数」としてなるべく早く到着することはカーナビの経路推薦において基本

いるが，新たなコストを追加する場合（たとえば，高速道路のであると考えられる．そのことから，統合コストを求める際に有無など）でも容易に対応することが可能となっている．

距離をベースにすることは自然である．また，道幅コストと信号数コストは距離コストに対する重みとすることで，たとえば，

3. 3 単位経路毎の各種コスト統合方式を用いた経路推薦の具体例

道幅が広い道を通りたい運転者の場合，道幅重みを小さくする．
もしくは，信号数が少ない道を通りたい運転者の場合，信号数
重みを小さくするなど柔軟に対応することが可能になる．単位経路に与えるコストは各種コストを考慮した統合コスト 1 種類のみである．そのため，差異増幅アルゴリズムに基づく経路推薦手法にて扱えるコストは 1 種類限定であるという条件にも合致しており，統合コストを用いた経路推薦手法の有用性は担保されている．
以下に，距離コストに対する道幅を考慮した重み係数および信号数を考慮した重み係数の算出方法について説明する．

•

道幅を考慮した重み係数の算出

以下に，算出式を示す．

{
Cw =

1−

(

w − 14
7

)

×α

}
(1)

w：実際の道幅（m）
α：運転者の道幅に対する重み（初期値 = α0 ，算出方法は 4

図 2 単位経路毎に算出した統合コストによる架空のグラフ

章参照）
道幅は片側 2 車線，対向車線も含めて 4 車線の道路を基準

表 1 図 2 における各単位経路の架空の道路データとしている．それよりも道幅が狭ければ係数を大きく，道幅が単位経路

距離 (m)

広ければ係数を小さくする．道幅の範囲は 7m〜21m とする．

R（出発地 → 1）150

道幅 7m よりも狭い道路は 7m，道幅 21m よりも広い道路はR（出発地 → 2）

21m とみなす．これは，運転者が 7m より狭い道路であれば実R（出発地 → 3）

際の道幅に関係なく狭いという認識を持つと考えられるためである．α の値を運転者毎に変更することで，係数の範囲を重要度に応じて大小に変化することが可能となる．

•

信号数を考慮した重み係数の算出

以下に，算出式を示す．

Cs = 1 + (s − 1) × β(2)

s：200m あたりの信号数（基）β：運転者の信号数に対する重み（初期値 = β0 ，算出方法は
4 章参照）

道幅 (m) 信号数 (基)

14

4

200

7

1

250

14

4

R（ 1 → 2 ）

200

7

1

R（ 1 → 4 ）

500

14

6

R（ 2 → 3 ）

100

7

0

R（ 2 → 5 ）

600

7

3

R（ 3 → 5 ）

300

7

1

R（ 3 → 6 ）

400

14

1

R（ 4 → 5 ）

100

7

0

R（4 → 目的地）

250

14

3

R（ 5 → 6 ）

100

7

0

R（5 → 目的地）

200

7

3

R（6 → 目的地）

400

14

2

200m あたりの信号数が 1 基の道路を基準としている．それよりも信号数が多ければ係数を大きく，信号数が少なければ係

3. 2 節で説明した各種コスト統合方式を用いた経路推薦の具数を小さくする．信号数の個数に制限は設けていない．β の値

体例について説明する．説明にあたり表 1，図 2 を使用して説が下がる重み”がある．“学習によって値を上げる重み”とは，カーナビが推薦した経路と運転者が選択した経路と比較して，運転者が選択した経路の各コストが低い経路（たとえば，道幅がより広いなど）だった場合に，値を上げる重みのことである．

図 3 差異増幅アルゴリズムによる仮想統合コストの算出例

明する．表 1 は図 2 における架空の道路データであり，図 2 は統合コストを求める例として用意した架空のグラフである．
経路 R（出発地 → 1）を例に説明する．表 1 より道幅は 14mであり，式（1）より Cw = 1.0．信号数は 4 基であり，式（2）より Cs = 1.43 である．道幅，信号数各重み係数における重み係数の値は，α = 0.1000，β = 0.1000 である．前述の結果と式0（3）より統合コストは L = 215 である．この統合コストを全ての単位経路毎に求めたものが図 2 である．図 2 における最小

図 4 各種コストに対する重みの学習のフローチャート

図 4 は，各種コストに対する重みの学習のフローチャートを示したものである．運転者が目的地に到着するまで重みの計算
は運転者の経路変更ごとに行われる．
このとき算出された重みは，式（1），（2）で各種コストを統合する際に用いられる．そのため，次回経路推薦時には過去の運転パターンを反映した経路推薦が可能となる．

4. 2 重みの計算方法

コストの経路はダイクストラ法より，経路 R（出発地 → 3 →5 → 目的地）である（トータルコスト：888）．
次に，運転者がノード 3 にて，カーナビが推薦したノード 5の方向ではなく，ノード 6 を意識的に選択した場合を想定する．
この場合ダイクストラ法で再探索すると，経路 R（6 → 5 → 目
的地）のコストが 363，経路 R（6 → 目的地）のコストが 400である．その結果，最小コストである経路 R（6 → 5 → 目的地）が再推薦される．差異増幅アルゴリズムに基づく経路推薦
手法を用いて再探索を行うと，経路 R（5 → G），経路 R（6→ 目的地）の仮想統合コストがそれぞれ 396，364 となる．経路 R（6 → 5 → 目的地）のコストが 495，経路 R（6 → 目的地）のコストが 364 であり，最小コストのルートである経路 R（6 → 目的地）が再推薦される（図 3 参照）．

4. 運転者ごとの各種コストに対する重みの学習方法
4. 1 概要

運転者が意識的にカーナビが推薦された経路とは異なる経路を選択した場合，運転者ははじめに提示されたカーナビの推薦経路に対し，不満を感じたために経路を変更したと考えられる．
本章では，運転者の選択経路から重要視していると推定される
コストおよび重要視していないと推定されるコストに対する重みの学習方法について説明する．
重みは，“学習によって値を上げる重み”と “学習によって値

図5

経路変更後の重みの計算時に用いる経路

図 5 は，重みの計算時に用いる経路を示したものである．青色の矢印（推薦経路）は，出発地と目的地を設定して得られた経路を示している．赤色の矢印（選択経路）は，運転者が意識的にノード 1 にて経路を変更した場合，差異増幅アルゴリズムに基づく経路推薦手法（提案手法）によって得られた経路を示している．
各コストに対する重みの学習に際し，比較に用いるデータは，カーナビが推薦した経路（推薦経路）および運転者が選択した経路（選択経路）それぞれの出発地から目的地までの，平均道幅（m）と総信号数（基）とする．“学習によって値を上げる重み”と “学習によって値が下がる重み”どちらの重みに属するか

経路変更 1 回で運転者が目的地に到着した場合，計算された各コストに対する重みを学習し，次回経路推薦時に利用する．
図 6 は，同一経路における 2 回目の経路変更後の重みの計算時に用いる経路を示したものである．同一経路において複数回
経路変更が行われる場合，1 回目の経路変更時に算出した重みに追加して重みを計算するのではなく，再度推薦経路と 2 回目の経路変更時に得られる経路（図 6 では，選択経路 2）と比較して，重みを計算する．すなわち，1 回目の経路変更で計算された重みを計算前の重みに戻して，再計算する．この方法を採用する理由は，運転者はまだ目的地に到着していないため，その途中段階の重みを学習すると本来学習すべきではない重みを反映する可能性があるからである．

4. 3 運転者の過去の経路選択を反映した重みの計算方法
本節では，運転者の過去の経路選択を反映した重みの計算方

図 6 2 回目の経路変更後の重みの計算時に用いる経路法について説明する．4. 2 節で説明した重みの計算方法は，過を判定する方法として，推薦経路および選択経路の平均道幅と総信号数の比を用いる．各比が 1 以上であれば，“学習によって値を上げる重み”とし，1 未満であれば “学習によって値が下がる重み”とする．

去の経路選択については考慮せずに，その場面における運転者の経路選択から，重みの計算を行っていた．ただ，運転者が長期にわたって経路を選択することにより，その経路選択履歴を用いることで何らかの傾向が存在するものと考えられる．そのため，運転者の経路選択を考慮した重みの計算を行うことで，平均道幅の比は，以下の式で算出する．

より実用度の高い学習が行えると考えている．

RW =

AWP
AWC

(4)

過去の経路選択を考慮した各コストに対する重みの学習係数のRW ：推薦経路および選択経路，平均道幅の比算出を行う．この学習係数は，運転者の過去の経路選択により

AWP ：選択経路の平均道幅算出される各コスト比の平均を用いることで算出する．

AWC ：推薦経路の平均道幅

道幅コストに対する重みの学習係数は，以下の式で算出する．

RW 0 =

総信号数の比は，以下の式で算出する．

1
RS = T S

P

式（4），式（5）で算出した各コスト比を用いて，運転者の

(5)

T SC

nRW n + (n − 1)RW n−1 + · · · + RW 1
∑n
i
i=1

(8)

RW 0 ：道幅コストに対する重みの学習係数nRW n ：n 回目の学習時の道幅コスト比

RS ：推薦経路および選択経路，総信号数の比

ただし，n は 5 以上とし，1 回目〜4 回目の学習時は，コスト

T SP ：選択経路の総信号数

比を 1 と仮定して，計算する．

T SC ：推薦経路の総信号数

道幅コストに対する重みは，以下の式で算出する．

ただし，T SP = 0 のときは，コスト比を T SC とする．

α0 = α × RW 0

T SC = 0 のときは，コスト比を T S1P とする．
T SP = 0, T SC = 0 のときは，コスト比を 1 とする．

α0 ：計算後の道幅コストに対する重み各コストに対する重みの計算は，式（4），式（5）で算出した各コスト比を用いて行う．

α = α × RW

計算する．

(6)

RS 0 =

α：計算前の道幅コストに対する重み

β ：計算前の信号数コストに対する重み

nRSn + (n − 1)RSn−1 + · · · + RS1
∑n
i
i=1

(10)

RW 0 ：信号数コストに対する重みの学習係数

信号数コストに対する重みは，以下の式で算出する．

β 0 ：計算後の信号数コストに対する重み信号数コストに対する重みの学習係数は，以下の式で算出する．

α0 ：計算後の道幅コストに対する重みβ 0 = β × RS

α：計算前の道幅コストに対する重み
ただし，1 回目〜4 回目の学習時は，コスト比を 1 と仮定して，道幅コストに対する重みは，以下の式で算出する．
0(9)

RW n ：n 回目の学習時の信号数コスト比(7)ただし，n は 5 以上とし，1 回目〜4 回目の学習時は，コスト比を 1 と仮定して，計算する．
信号数コストに対する重みは，以下の式で算出する．

β 0 = β × RS 0(11)

β 0 ：計算後の信号数コストに対する重み
β ：計算前の信号数コストに対する重み
これにより，4. 2 節では，重みの学習係数は一定であったものが，運転者の過去の経路選択履歴に応じて，学習係数の調節が行えるようになる．

5. 評 価 実 験
本章では，行った評価実験について説明する．5.1 節では，評価実験を行った際に用いたシミュレータについて説明する．5.2
節および 5.3 節では，3 章および 4 章で述べた算出式を用いて

図8

出発地（ノード 2）と目的地（ノード 16）を設定し推薦された
経路

2 種類の評価実験を行ったので，それぞれ説明する．
5. 1 シミュレータの開発

図9

提案手法における経路変更後の経路

実験のタスクを以下に示す．
（ 1 ） 出発地および目的地を設定する．
図 7 評価実験を行うために開発したシミュレータ（ 2 ） 運転者が経路変更をしなかった場合，現状の重みで運転者は不満に感じていないため，重みの学習は行わずに，次の評価実験を行うためのシミュレータを開発した（図 7 参照 ）．

経路の実験を行う．

ある大阪市内の道路地図を基にノード（交差点）とエッジ（道（ 3 ） 運転者が推薦経路に不満を感じた場合，経路変更地路）からなる簡易的な地図を作成した．各ノードは判別するた

ノードおよび経路変更先ノードを決定する．

めに，それぞれ数字を与えている．図にて，各エッジに数字が（ 4 ） 経路変更先ノードから目的地ノードまで，提案手法

与えられているが，これは交差点間の実際の距離，道幅，信号（差異増幅アルゴリズムによる経路推薦）にて得られる経路を数を基に 3. 2 節で説明した方法で各種コストを統合したもので運転者の選択経路とする．

ある．各データについては，Open Street Map（注 1）のデータを（ 5 ） 推薦経路と選択経路の出発地から目的地までの平均道参考にした．最小コストの経路の探索にはダイクストラ法を用

幅と総信号数を求め，4. 2 節にて説明した各種コストに対するいる．

重みの計算を行う．

続いて，シミュレータの概要を説明する．まず，図 7 におい（ 6 ） 目的地に到着するまで，経路変更が行われるごとに重て，出発地と目的地を設定する．図 8 において，ダイクストラ

みの計算を行う．

法に基づいた出発地から目的地までの最小コストの経路が推（ 7 ）（6）にて算出した重みを次回の経路推薦時に使用する．

薦される．運転者が推薦経路に不満を感じて意識的に経路を変運転者として，「道幅」を重要視している運転者を想定する．

更したい場合，経路変更をしたい地点のノードと経路変更先の被験者は運転経験がある大学生である．本実験では，出発地とノードを指定し，提案手法（差異増幅アルゴリズムによる経路

目的地が異なるルートを 5 パターン用意して，それぞれ運転推薦）によって再推薦された経路（図 9）を提示する．

者がカーナビの推薦した経路よりも “道幅の広い”経路を選択

5. 2 運転者の経路選択意図の学習に関する実験
5. 2. 1 概

要する．

5. 2. 2 差異増幅アルゴリズムに関する実験結果

運転者の経路変更から各運転者の意向に沿うような学習を行

表 2 は，出発地と目的地，経路変更地を設定して得られた最い，運転者の意向に沿った経路推薦が行えるか，シミュレータ

初の推薦経路と本手法により推薦された経路（図 8，図 9 参照）を使った評価実験を行った．

の違いを示したものである．本実験では，道幅，信号数各重み係数における重みの値はそれぞれ α = 0.1，β = 0.1 として実

（注 1）：https://openstreetmap.jp/

表 2 図 9 における経路変更後の従来推薦および提案手法の経路の違い
従来手法による 提案手法によるまた，表 4 は，図 10 における運転者の経路選択パターンの学習による最初の推薦経路と学習前の最初の推薦経路それぞれの

推薦ルート

推薦ルート

平均道幅と総信号数である．これらより，4. 2 節で説明した重平均道幅（m）

11.90

13.65

みの計算を行うことで，道幅を重視する運転者に対して，道幅

総信号数（基）3537

験を行った．平均道幅，総信号数はそれぞれ出発地から目的地までのデータである．本手法で得られた経路は，平均道幅におの広い経路が推薦されるような学習が行えた．
表 5 各ルートでの運転者の経路選択パターンの学習による最初の推薦経路の変化
学習前の

いて最初の推薦経路より広い経路であり，運転者の経路選択により，運転者が重視する要素を反映した経路が推薦された．
表3

各ルートでの最初の推薦経路および本手法による推薦経路の違い

8 回出発地，目的地設定をし最初の推薦ルート 走行した後の最初の推薦ルート
ルート 1

11.90

13.65

ルート 2

12.83

14.00

平均道幅

ルート 3

11.30

14.00

（m）

ルート 4

12.40

13.63

ルート 5

12.16

14.00

最初の

本手法による

推薦ルート

推薦ルート

ルート 1

11.90

13.65

ルート 2

12.83

13.71

表 5 は，出発地と目的地が異なる経路 5 パターンの出発地と平均道幅（m） ルート 3

11.30

13.65

目的地を設定したときに得られる最初の推薦経路において学習

ルート 4

12.40

13.67

ルート 5

前と学習後の平均道幅の違いを示したものである．このことか

12.16

14.00

ら，他の経路についても，道幅を重視する運転者に対して，道幅の広い経路が推薦されるような学習が行えた．

表 3 は，出発地と目的地が異なる経路 5 パターンの最初の推
薦経路および提案手法による推薦経路の違いを示したものである．平均道幅は出発地から目的地までのデータである．本手法で得られた経路は，最初の推薦経路より道幅の広い経路が推薦された．

5. 3 過去の運転者の経路選択意図の学習に関する実験
5. 3. 1 概要

運転者の過去の経路選択に対応した学習係数の調整が行える
か検証を行った．
実験のタスクを以下に示す．

5. 2. 3 重みの学習に関する実験結果（ 1 ） 出発地および目的地を設定する．

道幅を重視する運転者に対し，4. 2 節で説明した重みの計算を行い，出発地と目的地を設定したときに得られる最初の推薦
経路が道幅を重視した経路となるように学習を行った．

（ 2 ） 運転者が経路変更をしなかった場合，現状の重みで運転者は不満に感じていないため，重みの学習は行わずに，次の経路の実験を行う．
（ 3 ） 運転者が推薦経路に不満を感じた場合，経路変更地
ノードおよび経路変更先ノードを決定する．
（ 4 ） 経路変更先ノードから目的地ノードまで，提案手法（差異増幅アルゴリズムによる経路推薦）にて得られる経路を運転者の選択経路とする．
（ 5 ） 推薦経路と選択経路の出発地から目的地までの平均
道幅と総信号数を求め，4. 3 節にて説明した過去の経路選択パ
ターンを反映した各種コストに対する重みの計算を行う．
（ 6 ） 目的地に到着するまで，経路変更が行われるごとに重みの計算を行う．

図 10 8 回出発地，目的地設定をし走行した後の最初の推薦経路（ 7 ）（6）にて算出した重みを次回の経路推薦時に使用し，出発地と目的地を設定したときに得られる最初の推薦経路に変表 4 図 10 における運転者の経路選択パターンの学習による最初の推化が見られるまで繰り返し学習を行う．
運転者として，「道幅」を重要視している運転者を想定する．

薦経路の変化
学習前の

8 回出発地，目的地設定をし最初の推薦ルート 走行した後の最初の推薦ルート

被験者は運転経験がある大学生である．

5. 3. 2 実 験 結 果

平均道幅（m）

12.16

14.00

図 11 は，運転者の過去の経路選択パターンによる学習係数

総信号数（基）3752の変化を表したものである．11 回目の学習を終了後，出発地と目的地を選択した最初の経路に変化が見られたため，学習は終図 10 は，運転者がカーナビの推薦経路よりも道幅の広い経了した．1〜3 回目および 5〜11 回目の学習時に，運転者が道幅路を選択し，それを 8 回出発地，目的地設定を行った後の出発の広いルートを選択した場合には，道幅コストに対する重みの地と目的地を設定したときに得られる最初の推薦経路である．

学習係数の値が増加した．4 回目の学習時に，学習係数が減少

図 11 運転者の過去の経路選択パターンによる学習係数の変化したのは，運転者が信号数の少ない経路を選択したためである．
ただ，今回の実験では，過去の運転者の経路選択パターンを反映した学習に重点をおいたため，過去の経路選択パターンに当てはまらない経路選択を運転者が行った場合の学習係数の変化が大きいものとなった．今後は，学習において，過去の経路
選択パターンを反映した “長期的”な観点に基づく経路変更と渋滞になっていたから道を変更したなどの “短期的”な観点に基づ
く経路変更それぞれの場面について，検討を行う必要があると考えている．

6. お わ り に
カーナビ利用時の運転者ルート選択意図の学習およびルート
推薦手法の実験的評価を行った．すでに，提案を行った差異増
幅アルゴリズムに基づく経路推薦手法には単一のみのコストしか扱えない課題があった．そのため，各種コストの考慮を行う
ために，単位経路毎にコストを統合することで，コストを仮想的に 1 種類とみなし，前述のアルゴリズムが適用することが可能な手法について提案した．また，運転者は推薦経路に対し何らかの不満を持つことにより異なる経路を選択したとの仮説に基づき，カーナビの推薦経路と運転者の選択経路から運転者毎に重要視するコストを反映する学習方法について説明し，その評価実験を行った．さらに，過去の運転者の経路選択履歴を考慮した重みの学習方法について提案を行い，その評価実験を行った．今後は，重みの学習方法について検討を行い，さらなる評価実験を実施する予定である．
謝辞

本研究の一部は，JSPS 科研費 26280042 による．ここに記して謝意を表す．

文献[1] 国土交通省道路局：カーナビ・VICS の出荷台数，2015 年 09 月
末時点．
[2] 中島 伸介，木下 真一，田中 克己：差異増幅型適合フィードバッ
クに基づく画像データベース検索（画像検索・映像データベー
ス〈特集〉データ工学論文），電子情報通信学会論文誌 D-I，情報・システム，Vol.J87-D-I，No.2，pp.164–174（2004）．
[3] 中島 伸介，北山 大輔，濱田 恵輔：カーナビ利用時の推薦経路と選択経路の差異に基づくルート推薦方式，情報処理学会論文
誌データベース（TOD），Vol.7，No.2，pp.83–92（2014）．
[4] Shinsuke Nakajima, Daisuke Kitayama, Yoshitaka Sushita,
Kazutoshi Sumiya, Naiwala P. Chandrasiri and Kazunari
Nawa:“Route Recommendation Method for Car Navigation

System based on Estimation of Driver’ s Intent”. Proc. ofthe 2012 IEEE International Conference on Vehicular Electronics and Safety (ICVES 2012), pp.318-323 (2012).
[5] 濱田 恵輔，中島 伸介，北山 大輔：カーナビ利用時の多種コス
トの考慮およびドライバーのルート選択意図に基づく経路推薦方式の実験的評価，第 7 回データ工学と情報マネジメントに関するフォーラム（DEIM2015），B3–1（2015）.
[6] 独立行政法人工業所有権情報・研修館:カーナビ経路探索技術(2005).
[7] Dijkstra, E.W.: A note on two problems in connexion withgraphs, Numerische Mathematik, Vol.1, No.1, pp.269–271(1959).
[8] Hart, P., Nilsson, N. and Raphael, B.: A Formal Basisfor the Heuristic Determination of Minimum Cost Paths,
IEEE Trans. Systems Science and Cybernetics, Vol.4, No.2,
pp.100–107 (1968).
[9] Duckham, M. and Kulik, L.: “Simplest” Paths: AutomatedRoute Selection for Navigation, Spatial Information Theory.
Foundations of Geographic Information Science, Lecture
Notes in Computer Science, Vol.2825, pp.169–185 (2003).
[10] 狩野 均，小塚 英城：CA 法による広域道路交通シミュレータを用いた経路案内方式の評価，情報処理学会研究報告（ITS 研究会），Vol.2002，No.83，pp.37–43（2002）．
[11] 根笹 賢一，宮岡 伸一郎：カーナビ経路探索における運転者希望
経路の反映の評価，情報処理学会研究報告（MBL），Vol.2007，
No.116，pp.1–7（2007）．
[12] 稲垣 潤，長谷山美紀，北島秀夫：遺伝的アルゴリズムを用いた経路探索における複数経路候補の決定法（人工知能，認知科学），電子情報通信学会論文誌 D-I，Vol.J82-D-I，No.8，pp.1102–1111（1999）．
[13] 濱田 恵輔，中島 伸介，北山 大輔：カーナビ利用時の運転者の意
向を考慮したルート推薦およびその学習方法，第 6 回データ工学と情報マネジメントに関するフォーラム（DEIM2014），B9-6（2014）.