DEIM Forum 2014 B9-6

カーナビ利用時の運転者の意向を考慮した
ルート推薦およびその学習方法
濱田

恵輔†

中島

伸介†

北山

大輔††

角谷

和俊†††

† 京都産業大学 コンピュータ理工学部 〒 603–8555 京都府京都市北区上賀茂本山†† 工学院大学 情報学部 〒 163–8677 東京都新宿区西新宿 1 丁目 24–2††† 兵庫県立大学 環境人間学部 〒 670–0092 兵庫県姫路市新在家本町 1 丁目 1–12
E-mail: †{g1044903,nakajima}@cse.kyoto-su.ac.jp, ††kitayama@cc.kogakuin.ac.jp,†††sumiya@shse.u-hyogo.ac.jp
あらまし カーナビは非常に利便性の高いものであるが，常に運転者の意向に沿った経路推薦を行えるわけではない．
例えば，カーナビが提示する推薦経路に対して，運転者が意識的に別ルートを走行することがある．これに対してカーナビが元の推薦経路に戻るような経路を再推薦することがしばしば起こるが，これでは運転者の意向に沿ったルートを提案しているとはいえない．我々はこれまでに，カーナビの推薦経路と運転者の選択経路の差異を分析する事で運転者の意向に沿ったルート推薦を可能にする手法および複数のコスト (距離，道幅，信号数など) を考慮することができる手法を提案した．本稿では，これら複数コストを考慮する際の重みの計算方法を検討したので，実験結果を交えて報告する．
キーワード

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

1. は じ め に
近年，カーナビゲーションシステム（以後，カーナビと略して記述する）は累計 5800 万台を超える出荷 [1] が行われるほど

表 1 推奨ルートに従わない理由
経路変更理由人数

抜け道を知っていたから

343

慣れた道を通りたかったから315近道だったから

250

渋滞を避けられるから

232

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

交通量が少ない方がいいから

209

更や経路記憶（よく通る道を覚える）のように，運転者にとっ

曲がりきれなかった

190て利便性の高いナビゲートが可能となっている．カーナビに関寄り道したい所があった166する研究としては，特に経路探索手法について数多く行われて幅が広い道を通りたい117

おり [2]，ダイクストラ法 [3] や A *アルゴリズム [4] といった最

いつもと違う道が通りたい

59

その他

137

広く普及している．また，これに併せて技術の高度化が進み，

短経路探索のみならず，わかりやすく説明が容易な経路を探索するアルゴリズム [5] のような，様々なアルゴリズムを用いた手法が提案されている．実距離のみをコストとするのではなく，運転者はカーナビが推薦する経路に不満を持ち，意識的に異時間距離や渋滞の有無，道路の規制情報など様々な要因をコスなる経路を選ぶ事があるが，その要因は様々である．表 1 は，トとし，運転者が設定した出発地，目的地に対してそのコスト

事前調査として 900 人の被験者にカーナビに関するアンケートにおける最短経路となる経路を運転者に推薦することが可能とを行った際の『推奨ルートから外れた道を選択する時，主にどなっている．さらに運転者が推薦経路から外れた場合でも，あのような理由があるか？』という設問の回答をまとめたものでらかじめ設定された基準に基づき経路を再探索し，提示するこある．この結果から，推奨ルートに従わない理由のうち「曲がとが可能である．

りきれなかった」に関しては，元の推薦基準を用いて再推薦す

しかしながら，利便性が向上した現在のカーナビでも，必ずることが妥当であるが，他の理由に対しては必ずしもそうでは

しも運転者の意向を反映した経路推薦が十分に行えているわけ

なく，従来のカーナビでは適切に対処することが難しい理由でではない．例えば，何らかの理由で，カーナビが推薦するルーあることが分かる．

トから外れ，別のルートを選択した場合である．この時，従来以上を踏まえ，我々は運転者の経路選択の意向を自動的に判のカーナビは，運転者の「別のルートを走りたい」という意向

断して，その意向に沿った経路を設定するアルゴリズムの開発とは関係なく，あらかじめ設定された最短経路の基準に従ってを行った．カーナビの推薦する経路とは異なる経路を運転者が経路の再探索を行う．この場合，少なからず元の推薦経路に戻選択した時の，推薦経路と選択経路の差異，およびその交差点

るような経路を再推薦することがあるが，これは運転者の意向

におけるその他の経路と選択経路の差異に運転者の経路選択を反映したものとはいえない．

意思が含まれると考え，その差異を増幅して経路探索コストに図 1 運転者の意向に沿った経路推薦アルゴリズムの概要

フィードバックすることで，最適な経路を設定するアルゴリズ
ムを開発した（図 1）．なお，この時の運転者の意向を推定する手法としては，差異増幅アルゴリズム [6] を適用する．差異

3. 差異増幅アルゴリズムに基づく運転者の意向を考慮した経路推薦

増幅アルゴリズムとは，ユーザが “選択したもの”と “選択しな本章では，差異増幅アルゴリズムに基づく運転者の意向を考かったもの”の特徴的な差異を比較し，これを増幅することで，慮した経路推薦手法について説明を行う．3. 1 節で，差異増幅

本来ユーザが求めていたものを推定しようとする手法である．

アルゴリズムに基づく単一コストにおける運転者の意向を考慮

この手法に関して，既に評価実験に基づいて有効性を確認してした経路推薦手法について説明する．3. 2 節で，上記手法を採いる [7] [8]．

用したシミュレータの開発および評価実験の結果報告を行う．

また，以上の手法では，コストが一種類である場合にのみ対

3. 3 節で，3. 1 節で説明した手法について複数コストを考慮で応していたので，距離だけでなく，道幅や信号数等の複数のコきるように拡張した経路推薦手法について説明する．3. 4 節で，ストを考慮することが可能な手法について既に提案を行った [9]．

運転者毎の各種コストに対する重みの学習方法について説明を

本稿では，運転者によって各コストに対する重み（重要視す行う．なお，具体的なシミュレータの概要および実験方法に関る比率）が異なることから如何に各運転者の好みに合うように学習を行えるか，シミュレータを使った評価実験を行う．

2. 関 連 研 究

しては文献 [7] [8] [9] にて述べているので割愛する．

3. 1 差異増幅アルゴリズムに基づく単一コストにおける運転者の意向を考慮した経路推薦手法
差異増幅アルゴリズム [6] を採用し，運転者がカーナビの推

狩野ら [10] は，動的にコストを変動させるアルゴリズムを用薦経路から意識的に外れた際に，その時の運転者の意向に沿っいて，数分毎に道路のコストデータを更新し，渋滞回避を可能た経路推薦を行う手法の説明を行う．なお，目的地は一定であにする手法の研究を行っている．しかし，このシミュレータでることを前提とする．これは，カーナビの経路推薦機能を用いは渋滞や事故，工事等の情報のみ考慮しているため，運転者のる際，運転者の目的地が変わる事はほとんどないためである．

意向を考慮するには不十分である．また，明示された交通情報

このことは表 1 より，運転者がカーナビが推薦した経路から変のみ適応可能であるため，突発的な渋滞や事故に対応出来ない．

更を行った理由に目的地の変更が挙げられていないことからもこれに対し，我々の差異増幅アルゴリズムによる経路推薦手法推測できる．差異増幅アルゴリズムとは，ユーザがでは，運転者の選択意思に影響する情報の種類については特に“選択したもの” と “選択しなかったもの”

制限はなく，結果としてどの経路を重要視したのかという意向の特徴的な差異を比較し，これを増幅することで，本来ユーザを推定しようとするものである．

が求めていたものを推定しようとする手法である．

根笹ら [11] は，運転者の提示する条件に合わせて経路推薦をそこで，行うアルゴリズムの研究を行っている．しかしながら運転者が“カーナビの推薦ルートに反して，選択したルート”と提示する条件は，立寄地や道路の種類・大きさなどに限られて“カーナビの推薦ルートではあるが選択しなかったルート”

いる．また，稲垣ら [12] は遺伝的アルゴリズムを用いて重複しのコストの差異に注目し，これを増幅処理することで，ルートない複数の経路を表示させる手法の研究を行っており，運転者のコストを再計算し，ユーザの意向に沿った経路の推薦を目指の意向に応じた経路を選出できる手法を提案している．

している．

しかし，これらの研究で提案している手法では，いずれも運以下，図 2 に示した，経路のコストと推奨ルートの例を用転者が発車前に設定することを求めており，走行中に状況が変いて，差異増幅アルゴリズムによる経路推薦手法の説明を行わるような場面には対処することができない．これに対してう．図 2 中のノードは交差点，エッジは交差点を結ぶルートで我々の手法は動的にコストを変化させるものであり，走行中であり，エッジ上の数字は走行コストを表している．赤いルート

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

(1 → 3 → 9 → 12 → 15) は，ノード 1 からノード 15 へ移動する際の最短経路である．

Ci→? ：ノード i から 1 ホップ先の経路の走行コスト
0
Ci→?
：ノード i から 1 ホップ先の経路の “仮想”走行コスト

α：増幅係数である．
図 3 に示した例に基づいて説明する．図 3 は，(1 → 3) の推奨ルートを (1 → 2) と進んだ場合の以降の経路の仮想走行コストの計算例を示したものである．ただし，この例では増幅係数

α は，1.0 としている．
まず，経路 (3 → 9) に注目する．この経路の元々のコストは20 である．
（コストの種類は特に制限はないが，例えば仮に所要
図2

時間を想定してもらっても差し支えない） この経路を走行す

経路の走行コストと推奨ルートの例

るためには，元々の推奨ルートの場合は (1 → 3)（コスト 10）を辿ることになる．(1 → 2) と進んだ後にこの経路を走行するためには，(1 → 2 → 3)（コスト 12）と辿ることになる．すな
わち，推奨ルートに逆らって (1 → 2) と進んだ運転者の行動に倍になる．運転者がより，経路 (3 → 9) への到達コストが 12
10
経路 (3 → 9) を走行したければ，推奨ルートの通り (1 → 3) と進んでいたと考えられるため，ここでは仮想走行コストを元々の 20 の 12倍と設定する．これが差異増幅アルゴリズムに基づ
10く仮想走行コストの算出方法である．
次に，経路 (2 → 5) に注目する．この経路の元々のコストは16 である．この経路を走行するためには，元々の推奨ルート
図 3 仮想走行コストの計算例(1 → 3) から辿る場合は，(1 → 3 → 2)（コスト 16）と辿るこ

ここで，ノード 1 からノード 15 へ移動する運転者が，推薦ルートに反して，(1 → 2) のルートを選択したとする．このようなケースでは，従来のカーナビは，ノード 2 からノード 15 への最短ルートを再計算して，運転者に提示することが多いが，ノード 2 からノード 15 への最短経路は，(2 → 3 → 9 → 12 → 15)
であり，この運転者に対しては (2 → 3) のルートを推薦するとになる．実際に運転者が進んだことにより (1 → 2)（コスト6）となる．すなわち，推奨ルートに逆らって (1 → 2) と進んだ
6
運転者の行動により，経路 (2 → 5) への到達コストが 16
倍になる．運転者が経路 (2 → 5) を走行したくなければ，推奨ルー
トの通り (1 → 3) と進んでいたと考えられるため，ここでは仮6
想走行コストを元々の 16 の 16倍と設定する．
C

s→y→i
このようにして各経路（エッジ）の仮想走行コストを，Cs→x→iことになる．しかしながら，ノード 3 に移動するのであれば，に基づいて計算することができる．なお，この時の増幅係数は(1 → 2 → 3) と進むことはなく，最初から (1 → 3) のルート

α により調整することが可能である．0 < α < 1.0 の時，増幅を選択するのが自然である．したがって，運転者がある意向を持って運転者が (1 → 2) のルートを選択した場合は，(2 → 3)のルートを推薦するのは適切とはいえない．

を小さく，1.0 < α の時，増幅を大きく設定することができる．
この結果，図 3 に示した各経路の仮想走行コストに基づき，
ノード 2 から 15 への最短経路の再計算を行うと，元々の最短

そこで，“選択したルート”と “選択しなかったルート”の差異に着目して，仮想的なコスト計算を行うことで，運転者の意向経路である，(2 → 3 → 9 → 12 → 15) はコスト 46 からコスト

51.22 になり，(2 → 5 → 11 → 15) はコスト 51 だったものがに沿った経路推薦を行うことを目指す．以下に，ノードｓから

32.67 となる（再計算後の最短経路）．このように最短経路のノードｘへの走行をカーナビに推奨されたが，この推奨ルート

再計算を行うことで，運転者が意識的にカーナビ推奨ルートかには従わずノードｓからノード y に走行した場合のノードｉから別のルートを選択した場合でも，無理に元のルートに戻らせ

0
ら先の “仮想”走行コスト Ci→?の算出式を示す．“仮想”走行コ

ストとは，運転者の意向に基づいて算出されるコストであり，通りたくないと推定される経路のコストは大きく，通りたいと推定される経路のコストは小さく算出される．

るようなことはせず，運転者の意向に沿った経路推薦を行うことが可能になると考えている．

3. 2 差異増幅アルゴリズムに基づく経路推薦手法の評価
実験
差異増幅アルゴリズムによる経路推薦手法の有効性を確かめ

0
Ci→?
=(

Cs→y→i α) · Ci→?
Cs→x→i(1)

るため，評価実験を行った．実験に際し，評価実験には C#で開発したシミュレータを用いた（図 4，図 5）.
表示に関して右の画面には Google のストリートビュー，左

ただし，

Ca→b→c ：ノード a から b を経由して c まで辿った時の経路の走行コストの画面には Google Maps を用いている．Google Maps は車内のカーナビを模しており，ストリートビューは車内から見たフ図 4 差異増幅アルゴリズムの有効性を確かめるためのシミュレータ(起動時)

図 6 複数コストを統合した経路推薦の概要
表 2 経路のコストの例
距離 (m) 道幅 (m) 信号数 (個)
経路 A

440

12

2

経路 B

340

7

3

経路 C

470

10

1

表 3 表 2 の各コストに偏差値を用いた正規化スコア

図 5 差異増幅アルゴリズムの有効性を確かめるためのシミュレータ

距離スコア(経路変更後)ロントガラス越しの風景を模している．内部においては Open

道幅スコア 信号数スコア

経路 A

54

39

50

経路 B

36

63

62

経路 C

60

48

38

（注 1）

Street Mapのデータにある道路情報を示す < way > タグ

や < way > タグを結び付ける < node > タグ等を道路ネット

るかというものである．したがって，何らかの正規化を行うこ

ワーク情報として読み込み，経路推薦の処理を行う．最短距離とでコストの統合を可能にする必要がある．２つ目の課題は，の求め方は最短経路問題に有効とされているダイクストラ法を運転者によって各コストに対する重み（重要視する比率）が異用いている．コストにはノード（交差点）間の距離を用いた．

なることを踏まえて，如何に各運転者の好みに合うように学習

そのため，ダイクストラ法により，最も短い経路が推薦される．

するかというものである．本節では，複数コストの統合方法に

シュミレーションを行う地域は東京 23 区，京都市中心部，大ついて述べる．２つ目の課題に対する克服方法は次節で述べる．

阪市中心部，名古屋市中心部，横浜市中心部，福岡市中心部，考慮するコストは「距離」「道幅」「信号数」とする．これは広島市中心部，札幌市中心部の八カ所である.
差異増幅アルゴリズムの増幅係数 α は，3.0 として実験を行っ

事前アンケートより，運転者が経路選択をする際に決め手となる要因の大きいものを選んだ．

た．増幅係数が 1.0 または 2.0 の場合，従来手法で推薦された

なお，本研究における各経路のコストは，交差点と交差点の経路と提案手法で推薦された経路に明確な違いが現れなかった間の一区間を最小単位経路として，この最小単位経路毎に各コが，増幅係数を 3.0 に設定した際に，それぞれの経路に明確なスト情報を付与している．経路推薦時に考慮する，出発点から違いが現れたため，まずは増幅係数を 3.0 とした．

終点までのコストをトータルコストと呼ぶ．このトータルコス

なお，開発したシミュレータを用いた評価実験の結果，従来

トは，その区間（出発点から終点）に含まれる最小単位経路の手法ではなく，差異増幅アルゴリズムによる経路推薦手法によコストを合計することで求めることができる．

り提示した経路を運転者が選択した割合は 82.3%となり有効性

以下に各コストについて簡単に説明する．

は確認した [7] [8]．

3. 3 複数コストにおける運転者の意向を考慮した経路推薦
手法
複数コストを考慮するために，２つの課題を克服する必要がある．１つ目の課題は，単位が異なる各コストを如何に統合す

•

距離コスト

距離コストは，単位区間の経路の長さ (m) をそのコストとし
ている．

•

道幅コスト

道幅コストは，“想定最大道幅−道幅”をコストとし，今回は 21m を想定最大道幅とした．これは，一般道における幅が（注 1）：http://www.openstreetmap.org/

大きい道の平均車線数が３であり，１つの車線の幅の最大値が3.5m である [13] ことに基づき，対向車線を考慮して 21m としている．

•

信号数コスト

信号数コストは，経路間の信号数１つにつき，コストの値を１とする．経路と経路の間 (交差点) の信号も１と数える．
ここで複数の異なるコストを統合する手法について説明を行う．具体的には，各種コスト毎にトータルコスト（出発点から終点までのコスト）を算出し，これを正規化した後に統合する．
正規化の手法としては，各種コスト毎に算出される偏差値を用

図 7 運転者が経路変更後の元々のカーナビが推薦した経路および運転者が選択した経路いる．
例として，出発地から目的地までの経路を経路 A，経路 B，えられる．そこで，運転者の選択経路から重要視していると推経路 C とし，各経路のトータルコストを表 2 に示す．これらの定されるコストおよび重要視していないと推定されるコストに値を，各種コスト毎に偏差値を用いた正規化を行う（表 3）．

対する重みの学習を行う方法について説明する．

正規化されたスコアの統合は以下の式に基づいて行う．

ST = α · SR + β · SW + γ · SS

表 4 図 7 における各経路の走行コストの例
距離(2)

ST ：統合スコア
SR ：距離スコア

道幅

信号数

トータルコスト トータルコスト トータルコスト
推薦経路

840

35

4

選択経路

1200

28

8

SW ：道幅スコア
SS ：信号数スコア
α, β, γ ：運転者の距離・道幅・信号数に対する重み
ただしα+β+γ =1

この重みの学習方法は，表 4 で示した各コストを用いて説明する．
求める重みは大きく分けて，“学習によって値を上げる重み”と “学習によって値が下がる重み”があるが，それぞれ求め方がα, β, γ はそれぞれのコストに対する重みである．これらの重みは運転者の価値観に応じて随時学習され，運転者毎に異なる
値となる．

異なる．
どちらの重みに属するかを判定する方法として，“運転者の選択経路”に対する “カーナビによる推薦経路”のコスト比を用

仮に，α, β, γ の値が 1/3 と等しい場合，経路 A のスコアはいる．コスト比が 1 以上であれば，“学習によって値を上げる

47.6，経路 B のスコアは 53.8，経路 C のスコアは 48.6 となり，重み”とし，1 未満であれば “学習によって値が下がる重み”と最もスコアの低い経路 A が推薦される．

する．ここでのコストとは，経路変更地から目的地までのトー

次に，α = 0.5, β = 0.2, γ = 0.3 と，距離コストに大きな重みを置いた（終点まで距離が短い道を好む）運転者のケースをタルコストである．
各コスト比は，以下の式で算出する．

考える．この場合，経路 A のスコアは 49.8，経路 B のスコアは49.4，経路 C のスコアは 50.8 となり，最もスコアの低い（終点まで距離が短い）経路 B が推薦される．
以上より，各運転者の各種コストに対する価値観（重み）に

R=

CR
CS

(3)

R：推薦経路および選択経路，２つの各コストの比応じた経路推薦が可能となる．図 6 は上記方法で複数コストをCR ：カーナビによる推薦経路の走行コスト統合する経路推薦手法の概要である．

CS ：運転者の選択経路の走行コスト

運転者が推薦された経路に不満を持ち経路を変更した場合は，

3. 1 節にて算出できる仮想走行コストを距離，道幅，信号数コ

上記算出式および表 4 より，距離コスト比は RL = 0.700，

スト毎に求める．そして，経路変更地から目的地までの各最小

道幅コスト比は RW = 1.250，信号数コスト比は RS = 0.500

仮想走行コスト３経路を求め，上記手法で各コストを統合してとなる．よって，“学習によって値を上げるべき重み”は道幅コ

その中から１つの経路を再推薦する．

ストに対する重みであり，“学習によって値を下げるべき重み”

3. 4 運転者毎の各種コストに対する重みの学習方法

は距離コストに対する重みおよび信号数コストに対する重みとカーナビが推薦した経路通りに運転者が走行した場合には，なる．

運転者はその時の重みに不満はないと考えられるため，重みの初めに “学習によって値を上げるべき重み”の算出方法から説学習は行わない．しかし，図 7 のように運転者がカーナビの推明する．“学習によって値を上げるべき重み”を求める式は以下

薦経路とは別の経路を選択して目的地に到達した場合，運転者の通りである．

はカーナビの推薦経路に不満を感じたため経路を変更したと考β0 = β · (

CRW k
)
CSW

(4)

β 0 ：道幅コストに対する，学習後の重み
β ：道幅コストに対する，学習前の重み
CRW ：カーナビによる推薦経路の道幅コスト
CSW ：運転者の選択経路の道幅コスト
k：学習係数
学習前の各コストに対する重みを，α = 0.3333，
β = 0.3333，
γ = 0.3333 とする．学習後の道幅コストに対する重みは，式(4) より β 0 = 0.4166 と算出できる．学習係数は 1.0 とした．
次に，“学習によって値が下がる重み”の算出方法を説明する．

図8

重みの学習方法の評価を行うために開発されたシミュレータ

α + β + γ = 1 より重みの総和は 1 にしなければならない．
そこで，重み β の重みの増加分を RL と RS の比で分配する．
よって，距離コストに対する学習後の重み β 0 を求める式は以下のようになる．

α0 = α − ∆β · (1)
RL · ΣR(5)

α0 ：距離コストに対する，学習後の重み
α：距離コストに対する，学習前の重み∆β ：学習前と学習後の β の変化量．∆β = β 0 − β
ΣR：重みを下げるコストのコスト比の和(例では ΣR = R1L + R1S ．RS は信号数コスト比．)
式 (5) により，α0 = 0.2986 となる．同様の方法で求めると，

図9

出発地と目的地を設定し推薦された経路

0

信号数のコストに対する重みは γ = 0.2847 となる．
学習によって，道幅コストに対する重みが大きくなり，距離コストに対する重みおよび信号数コストに対する重みが下がった．よって，次回の経路推薦時には，この運転者の実際の価値観に近づいた経路を算出できる．

4. 複数のコストにおける運転者の意向を考慮した経路推薦手法の評価実験
3. 4 節にて説明を行った “運転者毎の各種コストに対する重みの学習方法”によって，運転者にとって最適な経路推薦を行える重みの学習が行えるか検証するための実験を行った．複数
コストを考慮するため，3. 3 節にて説明を行った “異なるコストの統合方法”に基づき推薦された経路を使用した実験を行う．

4. 1 シミュレータの開発
評価実験を行うためのシミュレータを開発した（図 8 〜 11参照）．ある大阪市内の道路地図を基にノード（交差点）とエッジ（道路）からなる簡易的な地図を作成した．各ノードは判別するために，それぞれ数字を与えている．図にて，各エッジに数字が与えられているが，これは交差点間の実際の距離である．
複数コストを考慮するために，同様の地図でエッジに道幅コストを与えたものと信号数コストを与えたものをそれぞれ用意した．最小コストの経路の求め方にはダイクストラ法を用いる．
続いて，シミュレータの概要を説明する．まず，図 8 において，出発地と目的地を設定する．図 9 において，ダイクストラ
法に基づいた出発地から目的地までの最小コストの経路が推

図 10 従来手法（ダイクストラ法）における経路変更後の経路薦される．運転者が推薦経路に不満を感じた場合，経路変更をしたい地点のノードと経路変更先のノードを指定し，従来手法（ダイクストラ法）によって再推薦された経路（図 10）および 3. 1 節にて説明した提案手法によって再推薦された経路（図11）を提示する．
4. 2 評価実験の概要および実験結果
実験のタスクを以下に示す．
（ 1 ） 出発地および目的地が異なる３経路を用意する．
（ 2 ） その内１つの経路の距離，道幅，信号数のトータルコ
ストがそれぞれ最小の経路を算出し，3. 3 節にて説明した手法
で各コストの統合を行い，統合スコアが最小の経路をカーナビ

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

図 12 道幅を優先する運転者の重みの推移（α = 3.0，k = 1.0）の推薦経路とする．
（ 3 ） 運転者が経路変更をしなかった場合，現状の重みで運転者は不満に感じていないため，重みの学習は行わずに，次の経路の実験を行う．
（ 4 ） 運転者が推薦経路に不満を感じた場合，経路変更地
ノードおよび経路変更先ノードを決定する．
（ 5 ） 経路変更先ノードから目的地ノードまで，3. 1 節にて説明した手法にて，距離，道幅，信号数コストの仮想走行コストを算出し，その各最小トータルコストとなる３つの経路を，

3. 3 節にて説明した手法で各コストの統合を行い，統合スコア
が最小の経路を運転者の選択経路とする．
（ 6 ） 次回の経路推薦時に運転者にとって最適な経路推薦を

図 13 道幅を優先する運転者の重みの推移（α = 3.0，k = 3.0）

行うため，
（２）にて推薦された経路および（５）にて運転者が選択した経路から，3. 4 節にて説明した重みの学習方法で，各コストに対する重みの値を変更する．
（ 7 ）（６）にて算出した新しい重みを次の経路推薦時に使用する．
（ 8 ） 重みの学習が行えなくなるまで実験を行う．
運転者として，道幅を重要視している運転者を想定する．差異増幅アルゴリズムにおける増幅係数は 3.0 および 7.0 で実験を行った．これは，増幅係数について予備実験を行い，出発地と目的地，経路変更地が全て同一の場合における提案手法で導く再推薦経路が異なる確率が高い増幅係数であった 3.0 および7.0 で実験を行った．“学習によって値を上げるべき重み”を算図 14 道幅を優先する運転者の重みの推移（α = 7.0，k = 1.0）

出時に使用する学習係数は 1.0〜5.0 の 5 段階とする．被験者は運転経験がある大学生である．道幅を重要視している運転者に対し，道幅コストに対する重みが増加し，道幅に重きを置いた経路が推薦されるか実験を行った．

者の意向に沿う重みの学習が可能であることがわかった．

4. 3 考察

図 12 および図 13，図 15 に示した通り，運転者が重視する

道幅を優先する運転者の重みの推移を図 12〜図 15 に示す．

コストに対する重みの学習が行えた．しかしながら，図 14 の増幅係数が 3.0 の時，学習係数の値によらず運転者が重要視すように運転者が重要視していないコストに対する重みが増加す

る道幅コストに対する重みが増加した（図 12，図 13 参照）．

るケースもあり，現在の重みの学習方法では確実に運転者の意

増幅係数が 7.0 の場合，学習係数の違いにより運転者が重要視向に合致する最適解を導き出せるわけではない．現在は距離，するコストとは異なるコストに対する重みが増加したケースも

道幅，信号数のトータルコストがそれぞれ最小の経路を導き出あったが，運転者が重要視する道幅コストに対する重みが増加

し，各コストの統合を行い１つの経路を推薦しているが，運転した（図 14，図 15 参照）．この結果から，カーナビの推薦経者はその地域の道路状況等に応じて経路の選択を行うため，経路および運転者の選択経路を利用した重みの学習方法で，運転路変更地から目的地までのトータルした経路で複数のコストを

[6]

[7]

[8]

[9]
図 15 道幅を優先する運転者の重みの推移（α = 7.0，k = 5.0）

[10]

統合することは自然な方法ではない．今後，単位経路毎に距離，
道幅，信号数コストの統合を行う手法について検討する必要が[11]あると考えている．また，ダイクストラ法は最小のコストの経[12]路を探索できるが，複数の経路を探索することはできない．したがって，上記の手法と併せて複数の経路を探索できる手法についても検討する必要があると考えている．

5. お わ り に
カーナビ利用時の運転者の意向を考慮したルート推薦およびその学習方法を提案した．
既に提案を行った差異増幅アルゴリズムに基づく運転者の意
向を考慮した経路推薦手法において単一コストだけしか考慮できないことから，複数コストにおける運転者の意向を考慮できる経路推薦手法の提案ならびに運転者毎の重要視するコストに対する重みの学習が可能な手法の提案を行った．また，シミュ
レータを用いて，評価実験を行った．評価実験を通して，複数コストにおける運転者の意向を考慮した経路推薦が可能であることを確認した．
今後は，複数コストの統合方法や複数の経路を探索できる手法について検討しつつ，「渋滞を避けたい」等の運転者の意向に対し，それに沿う新たなコストの追加，「自分だけでドライブする」や「家族と一緒にドライブする」等の運転するシチュエー
ションの違いを考慮したルート推薦手法について検討する．
文

献[1] 国土交通省道路局『カーナビ・VICS の出荷台数』2013 年 9 月
末時点[2] 独立行政法人 工業所有権情報・研修館『カーナビ経路探索技術』，
2005[3] E. W. Dijkstra, “A note on two problems in connexion withgraphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–
271, Dec. 1959.
[4] P. Hart, N. Nilsson, and B. Raphael, “A Formal Basis for the
Heuristic Determination of Minimum Cost Paths,” IEEE
Transactions on Systems Science and Cybernetics, vol. 4,
no. 2, pp. 100–107, 1968.
[5] Matt Duckham, Lars Kulik, Simplest Paths: AutomatedRoute Selection for Navigation, Spatial Information Theory. Foundations of Geographic Information Science, Lec-

[13]

ture Notes in Computer Science Volume 2825, pp 169-185,
2003
中島伸介，木下真一，田中克己. 差異増幅型適合フィードバックに基づく画像データベース検索. 電子情報通信学会論文誌（データ工学特集号）VOL.J87-D1 No.2，pp.164-174，2004.
須下 善隆，中島 伸介，北山 大輔，カーナビ利用時の運転者の意図推定に基づく経路推薦手法，第 4 回データ工学と情報マネジメントに関するフォーラム（DEIM2012），B3-3，2012.
Shinsuke Nakajima, Daisuke Kitayama, Yoshitaka Sushita,
Kazutoshi Sumiya, Naiwala P. Chandrasiri and KazunariNawa. “Route Recommendation Method for Car Navigation System based on Estimation of Driver’ s Intent”. Proc.
of the 2012 IEEE International Conference on VehicularElectronics and Safety (ICVES 2012), pp.318-323, Istanbul,
Turkey, July 24-27, 2012
濱田 恵輔，須下 善隆，中島 伸介，カーナビ利用時の選択経路を考慮した運転者意図推定に基づく経路推薦手法，第 5 回デー
タ工学と情報マネジメントに関するフォーラム（DEIM2013），
P3-1，2013.
狩野均，小塚英城，CA 法による広域道路交通シミュレータを用いた経路案内方式の評価， 情報処理学会，ITS 研究会，2002.
根笹 賢一，宮岡 伸一郎，カーナビ経路探索における運転者希望
経路の反映，情報処理学会研究報告.MBL 2007.
稲垣潤，長谷山美紀，北島秀夫，遺伝的アルゴリズムを用いた経路探索における複数経路候補の決定法， 電子情報通信学会論文誌，1999.
内閣府，道路構造法，
http://law.e-gov.go.jp/htmldata/S45/S45SE320.html
1970(最終改定:2011 年).