経路探索装置および経路探索方法
【課題】ユーザが以前に走行したことのない場所であっても、ユーザの嗜好に合致した経路を探索して提示する。
【解決手段】経路探索装置は、走行経路を蓄積する走行経路蓄積手段と、蓄積された走行経路に基づいて利用者の嗜好に合致する経路探索アルゴリズムを選択するアルゴリズム選択手段と、選択されたアルゴリズムを用いて、目的地までの経路探索を行う経路探索手段とを有する。アルゴリズム探索手段は、蓄積された走行経路のそれぞれについて、複数の経路探索アルゴリズムによって探索し、探索結果の経路と実際の走行経路の一致率をアルゴリズムごとに算出し、最も一致率の高いアルゴリズムを選択することが好適である。また、蓄積された走行経路から、ユーザが回避する道路に共通する条件を抽出し、そのような道路を選択しにくくするように探索コストを調整して経路探索を行うことが好ましい。
【解決手段】経路探索装置は、走行経路を蓄積する走行経路蓄積手段と、蓄積された走行経路に基づいて利用者の嗜好に合致する経路探索アルゴリズムを選択するアルゴリズム選択手段と、選択されたアルゴリズムを用いて、目的地までの経路探索を行う経路探索手段とを有する。アルゴリズム探索手段は、蓄積された走行経路のそれぞれについて、複数の経路探索アルゴリズムによって探索し、探索結果の経路と実際の走行経路の一致率をアルゴリズムごとに算出し、最も一致率の高いアルゴリズムを選択することが好適である。また、蓄積された走行経路から、ユーザが回避する道路に共通する条件を抽出し、そのような道路を選択しにくくするように探索コストを調整して経路探索を行うことが好ましい。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地までの経路を探索する経路探索技術に関し、特に、利用者の嗜好に合致する経路探索アルゴリズムを用いて経路探索を行う技術に関する。
【背景技術】
【０００２】
従来、不案内な道路での運転をスムーズに行えるようにするための経路探索装置（ナビゲーション装置）が広く利用されている。経路探索においては、例えば、走行経路最短、走行時間最短、有料道路優先、有料道路は利用しないなど複数の経路探索アルゴリズムが存在する。そこで、あらかじめ経路探索アルゴリズムをユーザに指定させた上で経路探索を行ったり、複数のアルゴリズムを用いて経路探索を行い複数の経路をユーザに提示する手法などがとられている。
【０００３】
さらに、よりユーザの嗜好に合致した経路選択が行えるように、次のような手法も提案されている。特許文献１では、地図データに基づいて算出した経路と走行軌跡データとを比較し、比較結果に基づいて探索コストを修正して目的地までの経路を算出する手法を提案している。また、特許文献２では、複数の検索条件による経路と分岐点を求め、ユーザに好みの誘導経路を設定させる手法を提案している。
【特許文献１】特許第３５９６７０４号公報
【特許文献２】特開２００７−２４０４００号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記の従来技術には次のような問題点がある。一般に、ユーザの経路選択の傾向（嗜好）は、必ずしもあらかじめ定められた経路探索アルゴリズムと合致するものではない。そこで、複数の経路探索アルゴリズムによる探索結果の中から自分の好みに合致した経路を探索しようとしても、未知の場所においてはどの経路が自分に適しているのかを判断することは難しい。
【０００５】
特許文献１は、通過経路（走行軌跡データ）と異なる経路の探索コストを修正しているため、ユーザが既知の場所でしか有効に動作しない。また、特許文献２の方法は、分岐点で誘導経路をユーザ自身が選択する操作を行う必要があり、煩雑である。
【０００６】
本発明は上記実情に鑑みてなされたものであって、その目的とするところは、ユーザが以前に走行したことのない場所であっても、ユーザの嗜好に合致した経路を提示することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するために本発明では、以下の手段または処理によって経路探索を行う。
【０００８】
本発明に係る経路探索装置は、複数の経路探索アルゴリズムを利用可能であり、走行した経路を取得し蓄積する走行経路蓄積手段と、蓄積された走行経路に基づいて、利用者の嗜好に合致する経路探索アルゴリズムを選択するアルゴリズム選択手段と、選択されたアルゴリズムを用いて、目的地までの経路探索を行う経路探索手段とを有する。
【０００９】
ここで、アルゴリズム選択手段は、まず、蓄積された走行経路のそれぞれについて、その出発点から目的地点へ到達するための経路を、複数のアルゴリズムのそれぞれを用いて
探索する。そして、探索結果の経路と実際の走行経路の一致率（経路一致率）をアルゴリズムごとに算出する。そして、各アルゴリズムについて、ユーザの経路選択傾向とそのアルゴリズムとの一致率（アルゴリズムの嗜好度）を算出する。このユーザの経路選択傾向とアルゴリズムとの一致率は、各経路について経路一致率に基づいて算出することができる。例えば、蓄積された各経路についての経路一致率を平均（重み付け平均でも良い）することによって、アルゴリズムの一致率を求めることが好適である。そして、アルゴリズム選択手段は、ユーザの経路選択傾向との一致率が最も高いアルゴリズムを、利用者の嗜好に合致するアルゴリズムとして選択する。
【００１０】
このように、利用者の過去の走行経路から、利用者の経路選択の嗜好を判別することで、未知の場所であっても利用者に適した経路を提示することが可能となる。
【００１１】
また、本発明におけるアルゴリズム選択手段は、探索結果の経路と実際の走行経路とが分岐する点である不一致点を求め、不一致点が存在する場合には、不一致点以降について改めて経路探索を行い、この探索結果も利用して一致率を算出することが好適である。
【００１２】
これは、例えば、出発点から近い地点で探索結果の経路と実際の経路が異なった場合、残りの行程では全ての経路が異なるものとなってしまうが、これは必ずしも利用者がその経路探索アルゴリズムを好んでいないことを意味するものではない。そこで、不一致点以降について改めて経路探索を行い、実際の経路との一致率を求めることで、利用者がその経路探索アルゴリズムを好んでいるか否かをより精度良く判断することが可能となる。
【００１３】
また、本発明におけるアルゴリズム選択手段は、複数の探索結果から得られる複数の不一致点について共通点（不一致共通点）を抽出してもよい。そして、経路探索手段は、選択されたアルゴリズムで経路探索を行う際に、不一致共通点と一致するリンクについては、選択コストを大きくして（選択されにくくして）経路探索を行うことが好ましい。なお、共通点としては、例えば、交通情報（信号の有無、渋滞の有無、一方通行など）や、周辺ＰＯＩ（Point of Interest）情報（店舗や学校等の施設）などの情報が挙げられる。
【００１４】
多くの経路で探索結果と異なるリンクが存在した場合、そのような経路をユーザの好みに合致しないものと判断することができる。そこで、共通する不一致点を求めて、そのようなリンクでの選択コストを大きくすることで、ユーザの嗜好により合致した経路選択が行える。
【００１５】
なお、上記のように不一致共通点を利用する場合は、経路探索手段は、選択されたアルゴリズムを用いて探索を行い、その探索経路上に共通点と一致するリンクが存在する場合には、当該リンクのコストを大きく設定した上で再度経路探索を行うことが好ましい。
【００１６】
目的地までのリンク全てについて、不一致共通点に関するコスト修正を行うことは処理負荷が大きいので、まず不一致共通点を考慮せずに経路探索を行い、この経路上に不一致共通点がある場合のみコスト修正を行うことで、効率的に処理を行うことが可能となる。
【００１７】
なお、経路の再探索は、探索結果の経路上に不一致共通点が存在しなくなるまでか、あるいは、再探索しても同一の経路が選択されるまでとすることで、ユーザの嗜好に合致した経路を求めることが可能となる。ただし、処理時間を考慮して、再探索回数に上限を設けても良い。
【００１８】
なお、本発明は、上記手段の少なくとも一部を有する経路探索装置として捉えることができる。また、本発明は、上記処理の少なくとも一部を含む経路探索方法、または、かかる方法を実現するためのプログラムとして捉えることもできる。上記手段および処理の各
々は可能な限り互いに組み合わせて本発明を構成することができる。
【発明の効果】
【００１９】
本発明によれば、ユーザが以前に走行したことのない場所であっても、ユーザの嗜好に合致した経路を提示することが可能となる。
【発明を実施するための最良の形態】
【００２０】
以下に図面を参照して、この発明の好適な実施の形態を例示的に詳しく説明する。
【００２１】
（第１の実施形態）
本実施形態に係るカーナビゲーション装置は、ユーザがそれまでに走行した経路を解析することで、ユーザがどのような経路選択を好むかを判断し、新たに経路探索を行う場合にはユーザの好みに合致する経路探索アルゴリズムを用いる。図１は、本実施形態に係るカーナビゲーション装置（経路探索装置）の機能構成を示す概略図である。
【００２２】
本カーナビゲーション装置は、大略、走行経路蓄積部３とアルゴリズム選択部５と経路探索部６とを備え、走行経路蓄積部３が蓄積した走行経路をアルゴリズム選択部５が解析してユーザの嗜好に合致した経路探索アルゴリズムを選択し、そのアルゴリズムを用いて経路探索部６が経路の探索を行う。なお、このような経路探索アルゴリズムの例として、最短距離（距離優先）、最短時間（時間優先）、有料道路優先、右折回避などを挙げることができるが、これらに限られず任意の経路探索アルゴリズムを用いてことができる。
【００２３】
〈経路蓄積処理〉
走行経路蓄積部３は、ＧＰＳ装置１から取得される位置データと、リンク情報を含む地図データ２とをマッチングして、走行経路（走行リンク）を求めて、走行履歴テーブル４に格納する。本実施形態では、ユーザの嗜好に合致した探索アルゴリズムを求めるので、走行経路の履歴データもユーザごとに記憶することが望ましい。そして、そのためには、運転時にユーザの識別を行うことが好ましい。
【００２４】
走行履歴テーブル４の具体的な構成を図２に示す。図２（Ａ）に示すように、走行履歴テーブル４は、ユーザＩＤ４１２とＯＤ（Ｏｒｉｇｉｎ／Ｄｅｓｔｉｎａｔｉｏｎ：始点／終点）−ＩＤ４１３、経路ＩＤ４１４ごとに経路セットＩＤ４１１を設け、その走行回数４１５および最終更新日４１６を記憶する。
【００２５】
走行履歴テーブル４を補助するためのその他のテーブルとして、経路テーブル（図２（Ｂ））、ＯＤテーブル（図２（Ｃ））、およびＰＯＩ（Ｐｏｉｎｔ ｏｆ Ｉｎｔｅｒｅｓｔ）テーブル（図２（Ｄ））を利用する。
【００２６】
経路テーブルは、経路ＩＤ４２１とＯＤ−ＩＤ４２２とリンク列４２３を記憶する。リンク列４２３は、その経路を構成するリンクのＩＤを経路の順に並べたものである。図から分かるように、始点と終点が同じであっても経路が異なる場合には、その経路は異なる経路ＩＤを有するレコードとして保存される。ＯＤテーブルはＯＤデータを記憶するものであり、ＯＤ−ＩＤ４３１と始点４３２と終点４３３を記憶する。始点４３２と終点４３３には、その位置がＰＯＩ−ＩＤとして格納される。ＰＯＩテーブルはＰＯＩデータを記憶するものであり、ＰＯＩ−ＩＤ４４１、緯度４４２、経度４４３、および場所４４４を記憶する。
【００２７】
〈アルゴリズム選択処理〉
アルゴリズム選択部５は、走行経路蓄積部３が作成した走行履歴テーブル４から、ユーザの嗜好に合致する経路探索アルゴリズムを求める。アルゴリズム選択部５は、大略、経
路一致率算出部５１とアルゴリズム嗜好度算出部５６を有する。経路一致率算出部５１は、ユーザが実際に走行した経路（経路テーブルに格納されている経路）と各探索アルゴリズムによる経路探索結果がどの程度一致するか算出し、一致率テーブル５５に格納する。アルゴリズム嗜好度算出部５６は、ユーザが過去に走行した走行履歴と、経路一致率テーブル５５とから、各ユーザがどの経路選択アルゴリズムを好む傾向にあるかを示すアルゴリズム嗜好度を算出し、アルゴリズム嗜好度テーブル５７に格納する。
【００２８】
アルゴリズム選択部５における経路一致率算出部５１は、より詳細には、経路探索部５２と不一致点抽出部５３と経路一致率算出部５４を備える。各機能部の動作の詳細を、図３に示すフローチャートともに説明する。図３は、アルゴリズム選択部５によるアルゴリズム嗜好度算出処理の全体の流れを示すフローチャートである。
【００２９】
経路探索部５２は、走行履歴テーブル４の格納されている各経路について、その始点（出発点）から終点（目的地）までへの経路を、あらかじめ定められた経路探索アルゴリズムによって探索する。具体的には、まずステップＳ３１で、走行履歴テーブル４に格納されている経路について、その始点と終点とを経路探索の目的地の条件として入力する。そして、ステップＳ３２であらかじめ定められた経路探索アルゴリズムのうちの１つを選び、ステップＳ３３でそのアルゴリズムを用いて経路探索を実行する。
【００３０】
ステップＳ３４で、不一致点抽出部５３は、実際の走行経路と探索結果の経路との不一致点を抽出する。例えば、図４に示すように、実際の走行経路のリンク列が１，２，３，４，５である場合に、探索結果の経路のリンク列が１，６，７，８であるときは、ノードＮ１で不一致が生じていると判断する。この場合、経路探索部５２は、ステップＳ３３に戻って、不一致が生じたリンク（リンク２）の終端ノードであるノードＮ２を始点として、経路探索を再度行う。この再探索処理は、探索結果に不一致がある間は継続して行うこととする。図４の例では、探索結果の経路のリンク列は、１，６，３，４，５となる。なお、リンク６とリンク３は接続していないが、探索経路の一致率を求めることが目的なのでこのような結果で問題ない。また、上記のように再探索を行うことで、ユーザの経路選択傾向と経路アルゴリズムがどの程度合致するか算出する際に、ユーザの実際の走行履歴を可能な限り反映させることができる。
【００３１】
そして、ステップＳ３５で、経路一致率算出部５４が、ユーザが実際に走行した経路と、ある経路探索アルゴリズムで探索を行った経路との一致率を算出して経路一致率テーブル５５に格納する。経路の一致率は、ユーザの実際の走行経路と、ある経路探索アルゴリズムによる探索経路とがどの程度一致するかを表す数値である。経路の一致率は、例えば、（一致するリンクの数）／（実際の走行経路のリンクの数）として求めて良いし、（一致するリンクの合計距離）／（実際の走行経路の合計距離）として求めても良い。また、（一致するノードの数）／（実際の走行経路のノードの数）として求めて良いし、道路の種類が異なるリンクを接続するノードのみに注目し、（一致するノードの数）／（実際の走行経路のノードの数）としても良い。
【００３２】
経路一致率の算出は、各経路についてあらかじめ定められた全ての経路探索アルゴリズムで行われる。したがって、全てのアルゴリズムで一致率を算出したかをステップＳ３６で判断し、一致率を算出していないアルゴリズムがある場合にはステップＳ３２に戻って、そのアルゴリズムについての一致率算出を行う。
【００３３】
また、ある経路について全てのアルゴリズムについて一致率を算出した場合（Ｓ３６：ＹＥＳ）は、一致率を求めていない経路が存在するかをステップＳ３７で判断し、未処理の経路が走行経路テーブル４に存在する場合は、ステップＳ３１に戻ってその経路について一致率の算出を行う。
【００３４】
上記のようにして求められた一致率は、経路一致率テーブル５５に格納される。経路一致率テーブル５５の例を、図５に示す。経路一致率テーブル５５は、探索ＩＤ５５１，経路ＩＤ５５２、ＯＤ−ＩＤ５５３，探索アルゴリズム５５４、リンク列５５５，一致率５５６を記憶する。図に示すように、各経路について探索アルゴリズムごとに、探索結果の経路（リンク列５５５）と、実際の走行経路との一致率５５６が格納される。
【００３５】
各経路について、各探索アルゴリズムによる探索経路との一致率が求められたら、アルゴリズム嗜好度算出部５６が、ユーザの経路探索傾向と経路探索アルゴリズムとが合致する度合いである、アルゴリズム嗜好度を算出し、アルゴリズム嗜好度テーブル５７に格納する。ある探索アルゴリズムについてのアルゴリズム嗜好度は、ユーザが実際に走行した各経路と対象とする探索アルゴリズムによる探索結果との一致率に基づいて算出される。例えば、ユーザが実際に走行した各経路についての一致率を、その経路の走行回数に応じた重み付けをした平均をとることで求めることができる。この重み付けは、走行回数に比例して大きくなるような値とすることもできる。ただし、頻繁に走行する経路についての経路選択傾向が過剰に反映されてしまわないように、走行回数に応じて大きくなるが増加率は徐々に減少するような重み付けを利用することも好適である。また、最近の経路選択傾向をより反映するために、最終更新日からの時間経過が大きいほど重み付けを小さくすることも好適である。
【００３６】
アルゴリズム嗜好度テーブル５７は、図６に示すように、ユーザＩＤ５７１、探索アルゴリズム５７２，一致率（嗜好度）５７３を記憶する。このように、アルゴリズム嗜好度テーブルには、ユーザごとに、各探索アルゴリズムのユーザの経路探索傾向との一致率、すなわちその探索アルゴリズムの嗜好度が格納される。
【００３７】
なお、上述したアルゴリズム選択部５によるアルゴリズム嗜好度の算出処理は、ユーザが運転を終了したとき（エンジンを切ったとき）や、運転を開始するとき（エンジンを始動したとき）などの適当な時期に、それまでの走行履歴について行えばよい。なお、毎回全ての経路について上記の処理を行う必要はなく、前回の実行から新たに追加された経路についてのみ上記の処理を行えばよい。また、ユーザによる走行経路は、運転開始位置から運転終了位置まで走行する間に、中継地点（立ち寄り地点）が含まれる場合があるので、中継地点が存在するかどうかユーザに確認を求めてから処理を行っても良い。また、上記では全ての走行経路について一致率を求めることとして説明しているが、一部の走行経路については一致率算出処理の対象から除外しても構わない。
【００３８】
〈経路探索処理〉
経路探索部６は、ユーザから出発地点（通常は現在地点）と目的地点が与えられた場合に、その目的地までの経路を探索する。この経路探索を行う際に、アルゴリズム嗜好度テーブル５７を参照して、そのユーザの嗜好に最も合致するアルゴリズムを用いて、経路選択を行う。
【００３９】
図７は、経路探索処理の流れを示すフローチャートである。まず、経路探索部６は、ユーザから目的地の入力を受け付ける（ステップＳ７１）。ここで、経路探索の起点としてはＧＰＳ装置１から得られる現在地を利用する。そして、アルゴリズム嗜好度テーブル５７を参照して、ユーザの経路選択嗜好に最も合致する経路選択アルゴリズムを選択する（ステップＳ７２）。そして、経路探索部６は、選択した経路探索アルゴリズムを用いて経路の探索を行い（ステップＳ７３）、探索結果をディスプレイなどに表示してユーザに提示する（ステップＳ７４）。
【００４０】
〈実施形態の作用／効果〉
本実施形態によれば、ユーザがそれまでに走行した経路の履歴から、そのユーザの経路選択の嗜好に最も合致する経路選択アルゴリズムを決定することができる。したがって、新たに経路探索を行う際に、ユーザの嗜好に最もマッチした経路選択アルゴリズムによる探索経路を提示することが可能となる。
【００４１】
このような方法によれば、ユーザがそれまでに走行したことのなく詳しく知らない場所であっても、日常利用する経路と似た経路を探索して提示することが可能となる。
【００４２】
また、従来は数種類程度の経路探索アルゴリズムが用いられている。これは、探索アルゴリズム数を増やしてしまうと、ユーザがどのアルゴリズムを選択すればいいのか判断が難しくなることが一つの理由である。本実施形態によれば、多数の探索アルゴリズムを用いた場合であっても、ユーザは明示的にどの探索アルゴリズムを用いるか指定する必要がない。したがって、ユーザに負担をかけることなく、多数の探索アルゴリズムの中からユーザの嗜好に合致する最適なアルゴリズムを選択することが可能となる。
【００４３】
（第２の実施形態）
第２の実施形態に係るカーナビゲーション装置は、第１の実施形態の機能に加え、ユーザが走行を回避するポイント（リンク）を抽出し、そのような経路を選びにくくすることで、よりユーザの経路探索傾向に合致した経路を提示する。
【００４４】
図８に本実施形態に係るカーナビゲーション装置の機能構成を示す。第１の実施形態と異なる点は、不一致点テーブル７と回避ポイント抽出部８と回避ポイントテーブル９とが設けられている点である。
【００４５】
〈回避ポイント抽出処理〉
不一致点テーブル７には、経路一致率算出部５１において実際の走行経路と探索結果の経路とに不一致点があった場合に、その不一致点が格納される。図９に示すように、不一致点テーブル７は、ユーザＩＤ７０１と不一致リンクペア７０２とを格納する。不一致リンクペアは、不一致が生じたリンクの対であり、図４に示すようにノードＮ１において、実際にはリンク２を走行したが、探索アルゴリズムはリンク６を選択した場合は、不一致リンクペアは２と６となる。不一致点は各ユーザに特有の情報であるので、ユーザＩＤごとに格納される。
【００４６】
図９では、不一致が発生したリンクペアを格納しているだけだが、そのリンクペアについて不一致が発生した回数と、探索アルゴリズムによる経路と実際の走行経路が一致した場合の回数をそれぞれ格納しておいても良い。すなわち、不一致が発生した割合（確率）を格納しておいても良い。あるリンクペアについて、不一致が毎回発生するとは限らず、多くの場合に探索アルゴリズムによって選択されたリンクを走行している場合は、ユーザは必ずしもそのリンクを回避しているとは限らないからである。このように、そのリンクを回避した割合を格納しておくことで、より的確にユーザが回避するリンクを判断することができるようになる。
【００４７】
回避ポイント抽出部８は、不一致点テーブル７から、そのユーザが回避するリンク（回避ポイント）を抽出する。回避ポイントの抽出は、不一致点テーブル７に含まれる不一致点に存在する共通点を求めることによって実行される。例えば、不一致の理由として考えられるいくつかの条件（例えば、渋滞、右折、学校施設など）を設けておき、不一致点テーブルに含まれる不一致点がこの条件と合致するかを判断する。あらかじめ定義した条件が不一致点として所定回数以上現れた場合には、ユーザがそのような条件のポイントを回避するものと判断することができる。回避ポイントの抽出は、その他にも、ニューラルネットワークの手法などを用いても抽出することができる。
【００４８】
図１０に、回避ポイント抽出部８が行う回避ポイント抽出処理の流れの一例をフローチャートとして示す。この例では、回避ポイント抽出部８は、ユーザが回避するポイント理由として考えられる理由（不一致条件）をあらかじめ保持している。不一致条件としては、例えば、通学路、信号、右折、渋滞、などを挙げることができる。
【００４９】
回避ポイント抽出部８は、不一致点テーブル７から不一致点を抽出する（ステップＳ１０１）。そして、その不一致点が、あらかじめ保持している不一致条件と合致しているか判断する（ステップＳ１０２）。例えば、探索アルゴリズムを用いて選択されたリンクが通学路であり、ユーザが実際に走行したリンクが通学路でない場合には、不一致条件「通学路」に合致することになる。この場合、合致した不一致条件についてのカウント値をインクリメントする（ステップＳ１０３）。なお、一つの不一致点が複数の不一致条件に合致することもある。このような不一致条件のカウントを全ての不一致点について行う（ステップＳ１０４）。
【００５０】
そして、不一致条件のカウント値が所定値以上となった場合に、そのような条件を有するリンクを回避ポイントとして抽出し、回避ポイントテーブル９に格納する（ステップＳ１０５）。例えば、不一致条件「通学路」に対するカウント値がしきい値以上であれば、そのユーザは通学路を回避する傾向にあるものと判断でき、通学路を回避ポイントとして抽出する。
【００５１】
回避ポイントテーブル９の構成を図１１に示す。回避ポイントテーブル９はユーザＩＤ９０１と回避ポイント９０２を含み、ユーザごとに、そのユーザがどのようなポイントを回避するかを格納している。
【００５２】
〈経路選択処理〉
次に、このようにして抽出した回避ポイントを利用して行う、経路探索部６による経路探索処理について、図１２のフローチャートを参照して説明する。経路探索部６は、まず、ユーザから目的地の入力を受け付け（ステップＳ１２１）、アルゴリズム嗜好度テーブル５７からユーザの経路選択嗜好に合致する経路選択アルゴリズムを選択し（ステップＳ１２２）、そのアルゴリズムを用いて経路探索を行う（ステップＳ１２３）。そして、探索結果の経路上に、回避ポイントテーブル９に格納されている回避ポイントに一致するリンクが存在するか判断する（ステップＳ１２４）。探索経路に回避ポイントが存在する場合は、そのリンクの探索コストを大きくしてそのリンクが選択されにくくするような調整を行う（ステップＳ１２５）。そして、調整後の探索コストに基づいて再度経路探索処理を実行する。このような処理を、探索結果の経路に回避ポイントが存在しなくなるか、探索コストを調整しても同じ経路が探索されるまで実行するが、再探索回数に上限値を設けても構わない。そして、このようにして求めた経路を、探索結果の経路としてユーザに提示する（ステップＳ１２６）。
【００５３】
〈実施形態の作用／効果〉
本実施形態によれば、あらかじめ定義された経路探索アルゴリズムのうち、ユーザの経路選択嗜好に最も合致したアルゴリズムを利用できるだけでなく、ユーザが回避する傾向にある道路を選択しにくくなるように経路探索を行うことができる。すなわち、より柔軟にユーザの経路選択傾向を反映した、経路探索を実行することが可能となる。
【図面の簡単な説明】
【００５４】
【図１】図１は、第１の実施形態に係るカーナビゲーション装置の機能構成を示す図である。
【図２】図２は、走行履歴テーブルの構成を示す図である。
【図３】図３は、アルゴリズム嗜好度算出処理の流れを示すフローチャートである。
【図４】図４は、経路探索における不一致点、および不一致点が存在する場合の再探索処理について説明する図である。
【図５】図５は、経路一致率テーブルの構成を示す図である。
【図６】図６は、アルゴリズム嗜好度テーブルの構成を示す図である。
【図７】図７は、経路探索処理の流れを示すフローチャートである。
【図８】図８は、第２の実施形態に係るカーナビゲーション装置の機能構成を示す図である。
【図９】図９は、不一致点テーブルの構成を示す図である。
【図１０】図１０は、不一致点に共通な条件である回避ポイントを抽出する処理の流れを示すフローチャートである。
【図１１】図１１は、回避ポイントテーブルの構成を示す図である。
【図１２】図１２は、経路探索処理の流れを示すフローチャートである。
【符号の説明】
【００５５】
３ 走行経路蓄積部
４ 走行履歴テーブル
５ アルゴリズム選択部
５１ 経路一致率算出部
５５ 一致率テーブル
５６ アルゴリズム嗜好度算出部
５７ アルゴリズム嗜好度テーブル
６ 経路探索部
７ 不一致点テーブル
８ 回避ポイント抽出部
９ 回避ポイントテーブル
【技術分野】
【０００１】
本発明は、目的地までの経路を探索する経路探索技術に関し、特に、利用者の嗜好に合致する経路探索アルゴリズムを用いて経路探索を行う技術に関する。
【背景技術】
【０００２】
従来、不案内な道路での運転をスムーズに行えるようにするための経路探索装置（ナビゲーション装置）が広く利用されている。経路探索においては、例えば、走行経路最短、走行時間最短、有料道路優先、有料道路は利用しないなど複数の経路探索アルゴリズムが存在する。そこで、あらかじめ経路探索アルゴリズムをユーザに指定させた上で経路探索を行ったり、複数のアルゴリズムを用いて経路探索を行い複数の経路をユーザに提示する手法などがとられている。
【０００３】
さらに、よりユーザの嗜好に合致した経路選択が行えるように、次のような手法も提案されている。特許文献１では、地図データに基づいて算出した経路と走行軌跡データとを比較し、比較結果に基づいて探索コストを修正して目的地までの経路を算出する手法を提案している。また、特許文献２では、複数の検索条件による経路と分岐点を求め、ユーザに好みの誘導経路を設定させる手法を提案している。
【特許文献１】特許第３５９６７０４号公報
【特許文献２】特開２００７−２４０４００号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記の従来技術には次のような問題点がある。一般に、ユーザの経路選択の傾向（嗜好）は、必ずしもあらかじめ定められた経路探索アルゴリズムと合致するものではない。そこで、複数の経路探索アルゴリズムによる探索結果の中から自分の好みに合致した経路を探索しようとしても、未知の場所においてはどの経路が自分に適しているのかを判断することは難しい。
【０００５】
特許文献１は、通過経路（走行軌跡データ）と異なる経路の探索コストを修正しているため、ユーザが既知の場所でしか有効に動作しない。また、特許文献２の方法は、分岐点で誘導経路をユーザ自身が選択する操作を行う必要があり、煩雑である。
【０００６】
本発明は上記実情に鑑みてなされたものであって、その目的とするところは、ユーザが以前に走行したことのない場所であっても、ユーザの嗜好に合致した経路を提示することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するために本発明では、以下の手段または処理によって経路探索を行う。
【０００８】
本発明に係る経路探索装置は、複数の経路探索アルゴリズムを利用可能であり、走行した経路を取得し蓄積する走行経路蓄積手段と、蓄積された走行経路に基づいて、利用者の嗜好に合致する経路探索アルゴリズムを選択するアルゴリズム選択手段と、選択されたアルゴリズムを用いて、目的地までの経路探索を行う経路探索手段とを有する。
【０００９】
ここで、アルゴリズム選択手段は、まず、蓄積された走行経路のそれぞれについて、その出発点から目的地点へ到達するための経路を、複数のアルゴリズムのそれぞれを用いて
探索する。そして、探索結果の経路と実際の走行経路の一致率（経路一致率）をアルゴリズムごとに算出する。そして、各アルゴリズムについて、ユーザの経路選択傾向とそのアルゴリズムとの一致率（アルゴリズムの嗜好度）を算出する。このユーザの経路選択傾向とアルゴリズムとの一致率は、各経路について経路一致率に基づいて算出することができる。例えば、蓄積された各経路についての経路一致率を平均（重み付け平均でも良い）することによって、アルゴリズムの一致率を求めることが好適である。そして、アルゴリズム選択手段は、ユーザの経路選択傾向との一致率が最も高いアルゴリズムを、利用者の嗜好に合致するアルゴリズムとして選択する。
【００１０】
このように、利用者の過去の走行経路から、利用者の経路選択の嗜好を判別することで、未知の場所であっても利用者に適した経路を提示することが可能となる。
【００１１】
また、本発明におけるアルゴリズム選択手段は、探索結果の経路と実際の走行経路とが分岐する点である不一致点を求め、不一致点が存在する場合には、不一致点以降について改めて経路探索を行い、この探索結果も利用して一致率を算出することが好適である。
【００１２】
これは、例えば、出発点から近い地点で探索結果の経路と実際の経路が異なった場合、残りの行程では全ての経路が異なるものとなってしまうが、これは必ずしも利用者がその経路探索アルゴリズムを好んでいないことを意味するものではない。そこで、不一致点以降について改めて経路探索を行い、実際の経路との一致率を求めることで、利用者がその経路探索アルゴリズムを好んでいるか否かをより精度良く判断することが可能となる。
【００１３】
また、本発明におけるアルゴリズム選択手段は、複数の探索結果から得られる複数の不一致点について共通点（不一致共通点）を抽出してもよい。そして、経路探索手段は、選択されたアルゴリズムで経路探索を行う際に、不一致共通点と一致するリンクについては、選択コストを大きくして（選択されにくくして）経路探索を行うことが好ましい。なお、共通点としては、例えば、交通情報（信号の有無、渋滞の有無、一方通行など）や、周辺ＰＯＩ（Point of Interest）情報（店舗や学校等の施設）などの情報が挙げられる。
【００１４】
多くの経路で探索結果と異なるリンクが存在した場合、そのような経路をユーザの好みに合致しないものと判断することができる。そこで、共通する不一致点を求めて、そのようなリンクでの選択コストを大きくすることで、ユーザの嗜好により合致した経路選択が行える。
【００１５】
なお、上記のように不一致共通点を利用する場合は、経路探索手段は、選択されたアルゴリズムを用いて探索を行い、その探索経路上に共通点と一致するリンクが存在する場合には、当該リンクのコストを大きく設定した上で再度経路探索を行うことが好ましい。
【００１６】
目的地までのリンク全てについて、不一致共通点に関するコスト修正を行うことは処理負荷が大きいので、まず不一致共通点を考慮せずに経路探索を行い、この経路上に不一致共通点がある場合のみコスト修正を行うことで、効率的に処理を行うことが可能となる。
【００１７】
なお、経路の再探索は、探索結果の経路上に不一致共通点が存在しなくなるまでか、あるいは、再探索しても同一の経路が選択されるまでとすることで、ユーザの嗜好に合致した経路を求めることが可能となる。ただし、処理時間を考慮して、再探索回数に上限を設けても良い。
【００１８】
なお、本発明は、上記手段の少なくとも一部を有する経路探索装置として捉えることができる。また、本発明は、上記処理の少なくとも一部を含む経路探索方法、または、かかる方法を実現するためのプログラムとして捉えることもできる。上記手段および処理の各
々は可能な限り互いに組み合わせて本発明を構成することができる。
【発明の効果】
【００１９】
本発明によれば、ユーザが以前に走行したことのない場所であっても、ユーザの嗜好に合致した経路を提示することが可能となる。
【発明を実施するための最良の形態】
【００２０】
以下に図面を参照して、この発明の好適な実施の形態を例示的に詳しく説明する。
【００２１】
（第１の実施形態）
本実施形態に係るカーナビゲーション装置は、ユーザがそれまでに走行した経路を解析することで、ユーザがどのような経路選択を好むかを判断し、新たに経路探索を行う場合にはユーザの好みに合致する経路探索アルゴリズムを用いる。図１は、本実施形態に係るカーナビゲーション装置（経路探索装置）の機能構成を示す概略図である。
【００２２】
本カーナビゲーション装置は、大略、走行経路蓄積部３とアルゴリズム選択部５と経路探索部６とを備え、走行経路蓄積部３が蓄積した走行経路をアルゴリズム選択部５が解析してユーザの嗜好に合致した経路探索アルゴリズムを選択し、そのアルゴリズムを用いて経路探索部６が経路の探索を行う。なお、このような経路探索アルゴリズムの例として、最短距離（距離優先）、最短時間（時間優先）、有料道路優先、右折回避などを挙げることができるが、これらに限られず任意の経路探索アルゴリズムを用いてことができる。
【００２３】
〈経路蓄積処理〉
走行経路蓄積部３は、ＧＰＳ装置１から取得される位置データと、リンク情報を含む地図データ２とをマッチングして、走行経路（走行リンク）を求めて、走行履歴テーブル４に格納する。本実施形態では、ユーザの嗜好に合致した探索アルゴリズムを求めるので、走行経路の履歴データもユーザごとに記憶することが望ましい。そして、そのためには、運転時にユーザの識別を行うことが好ましい。
【００２４】
走行履歴テーブル４の具体的な構成を図２に示す。図２（Ａ）に示すように、走行履歴テーブル４は、ユーザＩＤ４１２とＯＤ（Ｏｒｉｇｉｎ／Ｄｅｓｔｉｎａｔｉｏｎ：始点／終点）−ＩＤ４１３、経路ＩＤ４１４ごとに経路セットＩＤ４１１を設け、その走行回数４１５および最終更新日４１６を記憶する。
【００２５】
走行履歴テーブル４を補助するためのその他のテーブルとして、経路テーブル（図２（Ｂ））、ＯＤテーブル（図２（Ｃ））、およびＰＯＩ（Ｐｏｉｎｔ ｏｆ Ｉｎｔｅｒｅｓｔ）テーブル（図２（Ｄ））を利用する。
【００２６】
経路テーブルは、経路ＩＤ４２１とＯＤ−ＩＤ４２２とリンク列４２３を記憶する。リンク列４２３は、その経路を構成するリンクのＩＤを経路の順に並べたものである。図から分かるように、始点と終点が同じであっても経路が異なる場合には、その経路は異なる経路ＩＤを有するレコードとして保存される。ＯＤテーブルはＯＤデータを記憶するものであり、ＯＤ−ＩＤ４３１と始点４３２と終点４３３を記憶する。始点４３２と終点４３３には、その位置がＰＯＩ−ＩＤとして格納される。ＰＯＩテーブルはＰＯＩデータを記憶するものであり、ＰＯＩ−ＩＤ４４１、緯度４４２、経度４４３、および場所４４４を記憶する。
【００２７】
〈アルゴリズム選択処理〉
アルゴリズム選択部５は、走行経路蓄積部３が作成した走行履歴テーブル４から、ユーザの嗜好に合致する経路探索アルゴリズムを求める。アルゴリズム選択部５は、大略、経
路一致率算出部５１とアルゴリズム嗜好度算出部５６を有する。経路一致率算出部５１は、ユーザが実際に走行した経路（経路テーブルに格納されている経路）と各探索アルゴリズムによる経路探索結果がどの程度一致するか算出し、一致率テーブル５５に格納する。アルゴリズム嗜好度算出部５６は、ユーザが過去に走行した走行履歴と、経路一致率テーブル５５とから、各ユーザがどの経路選択アルゴリズムを好む傾向にあるかを示すアルゴリズム嗜好度を算出し、アルゴリズム嗜好度テーブル５７に格納する。
【００２８】
アルゴリズム選択部５における経路一致率算出部５１は、より詳細には、経路探索部５２と不一致点抽出部５３と経路一致率算出部５４を備える。各機能部の動作の詳細を、図３に示すフローチャートともに説明する。図３は、アルゴリズム選択部５によるアルゴリズム嗜好度算出処理の全体の流れを示すフローチャートである。
【００２９】
経路探索部５２は、走行履歴テーブル４の格納されている各経路について、その始点（出発点）から終点（目的地）までへの経路を、あらかじめ定められた経路探索アルゴリズムによって探索する。具体的には、まずステップＳ３１で、走行履歴テーブル４に格納されている経路について、その始点と終点とを経路探索の目的地の条件として入力する。そして、ステップＳ３２であらかじめ定められた経路探索アルゴリズムのうちの１つを選び、ステップＳ３３でそのアルゴリズムを用いて経路探索を実行する。
【００３０】
ステップＳ３４で、不一致点抽出部５３は、実際の走行経路と探索結果の経路との不一致点を抽出する。例えば、図４に示すように、実際の走行経路のリンク列が１，２，３，４，５である場合に、探索結果の経路のリンク列が１，６，７，８であるときは、ノードＮ１で不一致が生じていると判断する。この場合、経路探索部５２は、ステップＳ３３に戻って、不一致が生じたリンク（リンク２）の終端ノードであるノードＮ２を始点として、経路探索を再度行う。この再探索処理は、探索結果に不一致がある間は継続して行うこととする。図４の例では、探索結果の経路のリンク列は、１，６，３，４，５となる。なお、リンク６とリンク３は接続していないが、探索経路の一致率を求めることが目的なのでこのような結果で問題ない。また、上記のように再探索を行うことで、ユーザの経路選択傾向と経路アルゴリズムがどの程度合致するか算出する際に、ユーザの実際の走行履歴を可能な限り反映させることができる。
【００３１】
そして、ステップＳ３５で、経路一致率算出部５４が、ユーザが実際に走行した経路と、ある経路探索アルゴリズムで探索を行った経路との一致率を算出して経路一致率テーブル５５に格納する。経路の一致率は、ユーザの実際の走行経路と、ある経路探索アルゴリズムによる探索経路とがどの程度一致するかを表す数値である。経路の一致率は、例えば、（一致するリンクの数）／（実際の走行経路のリンクの数）として求めて良いし、（一致するリンクの合計距離）／（実際の走行経路の合計距離）として求めても良い。また、（一致するノードの数）／（実際の走行経路のノードの数）として求めて良いし、道路の種類が異なるリンクを接続するノードのみに注目し、（一致するノードの数）／（実際の走行経路のノードの数）としても良い。
【００３２】
経路一致率の算出は、各経路についてあらかじめ定められた全ての経路探索アルゴリズムで行われる。したがって、全てのアルゴリズムで一致率を算出したかをステップＳ３６で判断し、一致率を算出していないアルゴリズムがある場合にはステップＳ３２に戻って、そのアルゴリズムについての一致率算出を行う。
【００３３】
また、ある経路について全てのアルゴリズムについて一致率を算出した場合（Ｓ３６：ＹＥＳ）は、一致率を求めていない経路が存在するかをステップＳ３７で判断し、未処理の経路が走行経路テーブル４に存在する場合は、ステップＳ３１に戻ってその経路について一致率の算出を行う。
【００３４】
上記のようにして求められた一致率は、経路一致率テーブル５５に格納される。経路一致率テーブル５５の例を、図５に示す。経路一致率テーブル５５は、探索ＩＤ５５１，経路ＩＤ５５２、ＯＤ−ＩＤ５５３，探索アルゴリズム５５４、リンク列５５５，一致率５５６を記憶する。図に示すように、各経路について探索アルゴリズムごとに、探索結果の経路（リンク列５５５）と、実際の走行経路との一致率５５６が格納される。
【００３５】
各経路について、各探索アルゴリズムによる探索経路との一致率が求められたら、アルゴリズム嗜好度算出部５６が、ユーザの経路探索傾向と経路探索アルゴリズムとが合致する度合いである、アルゴリズム嗜好度を算出し、アルゴリズム嗜好度テーブル５７に格納する。ある探索アルゴリズムについてのアルゴリズム嗜好度は、ユーザが実際に走行した各経路と対象とする探索アルゴリズムによる探索結果との一致率に基づいて算出される。例えば、ユーザが実際に走行した各経路についての一致率を、その経路の走行回数に応じた重み付けをした平均をとることで求めることができる。この重み付けは、走行回数に比例して大きくなるような値とすることもできる。ただし、頻繁に走行する経路についての経路選択傾向が過剰に反映されてしまわないように、走行回数に応じて大きくなるが増加率は徐々に減少するような重み付けを利用することも好適である。また、最近の経路選択傾向をより反映するために、最終更新日からの時間経過が大きいほど重み付けを小さくすることも好適である。
【００３６】
アルゴリズム嗜好度テーブル５７は、図６に示すように、ユーザＩＤ５７１、探索アルゴリズム５７２，一致率（嗜好度）５７３を記憶する。このように、アルゴリズム嗜好度テーブルには、ユーザごとに、各探索アルゴリズムのユーザの経路探索傾向との一致率、すなわちその探索アルゴリズムの嗜好度が格納される。
【００３７】
なお、上述したアルゴリズム選択部５によるアルゴリズム嗜好度の算出処理は、ユーザが運転を終了したとき（エンジンを切ったとき）や、運転を開始するとき（エンジンを始動したとき）などの適当な時期に、それまでの走行履歴について行えばよい。なお、毎回全ての経路について上記の処理を行う必要はなく、前回の実行から新たに追加された経路についてのみ上記の処理を行えばよい。また、ユーザによる走行経路は、運転開始位置から運転終了位置まで走行する間に、中継地点（立ち寄り地点）が含まれる場合があるので、中継地点が存在するかどうかユーザに確認を求めてから処理を行っても良い。また、上記では全ての走行経路について一致率を求めることとして説明しているが、一部の走行経路については一致率算出処理の対象から除外しても構わない。
【００３８】
〈経路探索処理〉
経路探索部６は、ユーザから出発地点（通常は現在地点）と目的地点が与えられた場合に、その目的地までの経路を探索する。この経路探索を行う際に、アルゴリズム嗜好度テーブル５７を参照して、そのユーザの嗜好に最も合致するアルゴリズムを用いて、経路選択を行う。
【００３９】
図７は、経路探索処理の流れを示すフローチャートである。まず、経路探索部６は、ユーザから目的地の入力を受け付ける（ステップＳ７１）。ここで、経路探索の起点としてはＧＰＳ装置１から得られる現在地を利用する。そして、アルゴリズム嗜好度テーブル５７を参照して、ユーザの経路選択嗜好に最も合致する経路選択アルゴリズムを選択する（ステップＳ７２）。そして、経路探索部６は、選択した経路探索アルゴリズムを用いて経路の探索を行い（ステップＳ７３）、探索結果をディスプレイなどに表示してユーザに提示する（ステップＳ７４）。
【００４０】
〈実施形態の作用／効果〉
本実施形態によれば、ユーザがそれまでに走行した経路の履歴から、そのユーザの経路選択の嗜好に最も合致する経路選択アルゴリズムを決定することができる。したがって、新たに経路探索を行う際に、ユーザの嗜好に最もマッチした経路選択アルゴリズムによる探索経路を提示することが可能となる。
【００４１】
このような方法によれば、ユーザがそれまでに走行したことのなく詳しく知らない場所であっても、日常利用する経路と似た経路を探索して提示することが可能となる。
【００４２】
また、従来は数種類程度の経路探索アルゴリズムが用いられている。これは、探索アルゴリズム数を増やしてしまうと、ユーザがどのアルゴリズムを選択すればいいのか判断が難しくなることが一つの理由である。本実施形態によれば、多数の探索アルゴリズムを用いた場合であっても、ユーザは明示的にどの探索アルゴリズムを用いるか指定する必要がない。したがって、ユーザに負担をかけることなく、多数の探索アルゴリズムの中からユーザの嗜好に合致する最適なアルゴリズムを選択することが可能となる。
【００４３】
（第２の実施形態）
第２の実施形態に係るカーナビゲーション装置は、第１の実施形態の機能に加え、ユーザが走行を回避するポイント（リンク）を抽出し、そのような経路を選びにくくすることで、よりユーザの経路探索傾向に合致した経路を提示する。
【００４４】
図８に本実施形態に係るカーナビゲーション装置の機能構成を示す。第１の実施形態と異なる点は、不一致点テーブル７と回避ポイント抽出部８と回避ポイントテーブル９とが設けられている点である。
【００４５】
〈回避ポイント抽出処理〉
不一致点テーブル７には、経路一致率算出部５１において実際の走行経路と探索結果の経路とに不一致点があった場合に、その不一致点が格納される。図９に示すように、不一致点テーブル７は、ユーザＩＤ７０１と不一致リンクペア７０２とを格納する。不一致リンクペアは、不一致が生じたリンクの対であり、図４に示すようにノードＮ１において、実際にはリンク２を走行したが、探索アルゴリズムはリンク６を選択した場合は、不一致リンクペアは２と６となる。不一致点は各ユーザに特有の情報であるので、ユーザＩＤごとに格納される。
【００４６】
図９では、不一致が発生したリンクペアを格納しているだけだが、そのリンクペアについて不一致が発生した回数と、探索アルゴリズムによる経路と実際の走行経路が一致した場合の回数をそれぞれ格納しておいても良い。すなわち、不一致が発生した割合（確率）を格納しておいても良い。あるリンクペアについて、不一致が毎回発生するとは限らず、多くの場合に探索アルゴリズムによって選択されたリンクを走行している場合は、ユーザは必ずしもそのリンクを回避しているとは限らないからである。このように、そのリンクを回避した割合を格納しておくことで、より的確にユーザが回避するリンクを判断することができるようになる。
【００４７】
回避ポイント抽出部８は、不一致点テーブル７から、そのユーザが回避するリンク（回避ポイント）を抽出する。回避ポイントの抽出は、不一致点テーブル７に含まれる不一致点に存在する共通点を求めることによって実行される。例えば、不一致の理由として考えられるいくつかの条件（例えば、渋滞、右折、学校施設など）を設けておき、不一致点テーブルに含まれる不一致点がこの条件と合致するかを判断する。あらかじめ定義した条件が不一致点として所定回数以上現れた場合には、ユーザがそのような条件のポイントを回避するものと判断することができる。回避ポイントの抽出は、その他にも、ニューラルネットワークの手法などを用いても抽出することができる。
【００４８】
図１０に、回避ポイント抽出部８が行う回避ポイント抽出処理の流れの一例をフローチャートとして示す。この例では、回避ポイント抽出部８は、ユーザが回避するポイント理由として考えられる理由（不一致条件）をあらかじめ保持している。不一致条件としては、例えば、通学路、信号、右折、渋滞、などを挙げることができる。
【００４９】
回避ポイント抽出部８は、不一致点テーブル７から不一致点を抽出する（ステップＳ１０１）。そして、その不一致点が、あらかじめ保持している不一致条件と合致しているか判断する（ステップＳ１０２）。例えば、探索アルゴリズムを用いて選択されたリンクが通学路であり、ユーザが実際に走行したリンクが通学路でない場合には、不一致条件「通学路」に合致することになる。この場合、合致した不一致条件についてのカウント値をインクリメントする（ステップＳ１０３）。なお、一つの不一致点が複数の不一致条件に合致することもある。このような不一致条件のカウントを全ての不一致点について行う（ステップＳ１０４）。
【００５０】
そして、不一致条件のカウント値が所定値以上となった場合に、そのような条件を有するリンクを回避ポイントとして抽出し、回避ポイントテーブル９に格納する（ステップＳ１０５）。例えば、不一致条件「通学路」に対するカウント値がしきい値以上であれば、そのユーザは通学路を回避する傾向にあるものと判断でき、通学路を回避ポイントとして抽出する。
【００５１】
回避ポイントテーブル９の構成を図１１に示す。回避ポイントテーブル９はユーザＩＤ９０１と回避ポイント９０２を含み、ユーザごとに、そのユーザがどのようなポイントを回避するかを格納している。
【００５２】
〈経路選択処理〉
次に、このようにして抽出した回避ポイントを利用して行う、経路探索部６による経路探索処理について、図１２のフローチャートを参照して説明する。経路探索部６は、まず、ユーザから目的地の入力を受け付け（ステップＳ１２１）、アルゴリズム嗜好度テーブル５７からユーザの経路選択嗜好に合致する経路選択アルゴリズムを選択し（ステップＳ１２２）、そのアルゴリズムを用いて経路探索を行う（ステップＳ１２３）。そして、探索結果の経路上に、回避ポイントテーブル９に格納されている回避ポイントに一致するリンクが存在するか判断する（ステップＳ１２４）。探索経路に回避ポイントが存在する場合は、そのリンクの探索コストを大きくしてそのリンクが選択されにくくするような調整を行う（ステップＳ１２５）。そして、調整後の探索コストに基づいて再度経路探索処理を実行する。このような処理を、探索結果の経路に回避ポイントが存在しなくなるか、探索コストを調整しても同じ経路が探索されるまで実行するが、再探索回数に上限値を設けても構わない。そして、このようにして求めた経路を、探索結果の経路としてユーザに提示する（ステップＳ１２６）。
【００５３】
〈実施形態の作用／効果〉
本実施形態によれば、あらかじめ定義された経路探索アルゴリズムのうち、ユーザの経路選択嗜好に最も合致したアルゴリズムを利用できるだけでなく、ユーザが回避する傾向にある道路を選択しにくくなるように経路探索を行うことができる。すなわち、より柔軟にユーザの経路選択傾向を反映した、経路探索を実行することが可能となる。
【図面の簡単な説明】
【００５４】
【図１】図１は、第１の実施形態に係るカーナビゲーション装置の機能構成を示す図である。
【図２】図２は、走行履歴テーブルの構成を示す図である。
【図３】図３は、アルゴリズム嗜好度算出処理の流れを示すフローチャートである。
【図４】図４は、経路探索における不一致点、および不一致点が存在する場合の再探索処理について説明する図である。
【図５】図５は、経路一致率テーブルの構成を示す図である。
【図６】図６は、アルゴリズム嗜好度テーブルの構成を示す図である。
【図７】図７は、経路探索処理の流れを示すフローチャートである。
【図８】図８は、第２の実施形態に係るカーナビゲーション装置の機能構成を示す図である。
【図９】図９は、不一致点テーブルの構成を示す図である。
【図１０】図１０は、不一致点に共通な条件である回避ポイントを抽出する処理の流れを示すフローチャートである。
【図１１】図１１は、回避ポイントテーブルの構成を示す図である。
【図１２】図１２は、経路探索処理の流れを示すフローチャートである。
【符号の説明】
【００５５】
３ 走行経路蓄積部
４ 走行履歴テーブル
５ アルゴリズム選択部
５１ 経路一致率算出部
５５ 一致率テーブル
５６ アルゴリズム嗜好度算出部
５７ アルゴリズム嗜好度テーブル
６ 経路探索部
７ 不一致点テーブル
８ 回避ポイント抽出部
９ 回避ポイントテーブル
【特許請求の範囲】
【請求項１】
複数の経路探索アルゴリズムを利用可能な経路探索装置であって、
走行した経路を取得し蓄積する走行経路蓄積手段と、
前記走行経路蓄積手段に蓄積された走行経路に基づいて、利用者の嗜好に合致する経路探索アルゴリズムを選択するアルゴリズム選択手段と、
前記アルゴリズム選択手段によって選択されたアルゴリズムを用いて、目的地までの経路探索を行う経路探索手段と、
を有し、
前記アルゴリズム選択手段は、
前記走行経路蓄積手段に蓄積された走行経路のそれぞれについて、その出発地点から目的地点へ到達するための経路を、前記複数のアルゴリズムによって探索し、
探索結果の経路と実際の走行経路の一致率である経路一致率をアルゴリズムごとに算出し、
アルゴリズムごとに、各経路についての経路一致率に基づいて、ユーザの経路選択傾向とそのアルゴリズムの一致率を求め、
ユーザの経路選択傾向との一致率が最も高いアルゴリズムを、利用者の嗜好に合致するアルゴリズムとして選択する
ことを特徴とする経路探索装置。
【請求項２】
前記アルゴリズム選択手段は、探索結果の経路と実際の走行経路が分岐する点である不一致点を求め、不一致点が存在する場合には、不一致点以降について改めて経路探索を行い、この探索結果も利用して前記経路一致率を算出する
ことを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記アルゴリズム選択手段は、探索結果の経路と実際の走行経路が分岐する点である不一致点を求め、複数の探索結果から得られる複数の不一致点についての共通点を抽出し、
前記経路探索手段は、前記選択されたアルゴリズムで経路探索を行う際に、前記共通点と一致するリンクについてはコストを大きくして経路探索を行う
ことを特徴とする請求項１または２に記載の経路探索装置。
【請求項４】
前記経路探索手段は、前記選択されたアルゴリズムを用いて探索を行い、探索された経路上に前記共通点と一致するリンクが存在する場合は、当該リンクのコストを大きく設定した上で、再度経路探索を行う
ことを特徴とする請求項３に記載の経路探索装置。
【請求項５】
走行した経路を取得し蓄積する走行経路蓄積工程と、
蓄積された走行経路に基づいて、利用者の嗜好に合致する経路探索アルゴリズムを選択するアルゴリズム選択工程と、
選択されたアルゴリズムを用いて、目的地までの経路探索を行う経路探索工程と、
を備え、
前記アルゴリズム選択工程は、
蓄積された走行経路のそれぞれについて、その出発地点から目的地点へ到達するための経路を、複数のアルゴリズムによって探索する工程と、
探索結果の経路と実際の走行経路との一致率である経路一致率をアルゴリズムごとに算出する工程と、
アルゴリズムごとに、各経路についての経路一致率に基づいて、ユーザの経路選択傾向とそのアルゴリズムの一致率を求める工程と、
ユーザの経路選択傾向との一致率が最も高いアルゴリズムを、利用者の嗜好に合致するアルゴリズムとして選択する工程と
を含むことを特徴とする経路探索方法。
【請求項６】
前記アルゴリズム選択工程では、
探索結果の経路と実際の走行経路が分岐する点である不一致点を求め、不一致点が存在する場合には、不一点以降について改めて経路探索を行い、この探索結果も利用して前記経路一致率を算出する
ことを特徴とする請求項５に記載の経路探索方法。
【請求項７】
前記アルゴリズム選択工程では、探索結果の経路と実際の走行経路が分岐する点である不一致点を求め、複数の探索結果から得られる複数の不一致点についての共通点を抽出し、
前記経路探索工程では、前記選択されたアルゴリズムで経路探索を行う際に、前記共通点と一致するリンクについてはコストを大きくして経路探索を行う
ことを特徴とする請求項５または６に記載の経路探索方法。
【請求項８】
前記経路探索工程では、前記選択されたアルゴリズムを用いて探索を行い、探索された経路上に前記共通点と一致するリンクが存在する場合は、当該リンクのコストを大きく設定した上で、再度経路探索を行う
ことを特徴とする請求項７に記載の経路探索方法。
【請求項１】
複数の経路探索アルゴリズムを利用可能な経路探索装置であって、
走行した経路を取得し蓄積する走行経路蓄積手段と、
前記走行経路蓄積手段に蓄積された走行経路に基づいて、利用者の嗜好に合致する経路探索アルゴリズムを選択するアルゴリズム選択手段と、
前記アルゴリズム選択手段によって選択されたアルゴリズムを用いて、目的地までの経路探索を行う経路探索手段と、
を有し、
前記アルゴリズム選択手段は、
前記走行経路蓄積手段に蓄積された走行経路のそれぞれについて、その出発地点から目的地点へ到達するための経路を、前記複数のアルゴリズムによって探索し、
探索結果の経路と実際の走行経路の一致率である経路一致率をアルゴリズムごとに算出し、
アルゴリズムごとに、各経路についての経路一致率に基づいて、ユーザの経路選択傾向とそのアルゴリズムの一致率を求め、
ユーザの経路選択傾向との一致率が最も高いアルゴリズムを、利用者の嗜好に合致するアルゴリズムとして選択する
ことを特徴とする経路探索装置。
【請求項２】
前記アルゴリズム選択手段は、探索結果の経路と実際の走行経路が分岐する点である不一致点を求め、不一致点が存在する場合には、不一致点以降について改めて経路探索を行い、この探索結果も利用して前記経路一致率を算出する
ことを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記アルゴリズム選択手段は、探索結果の経路と実際の走行経路が分岐する点である不一致点を求め、複数の探索結果から得られる複数の不一致点についての共通点を抽出し、
前記経路探索手段は、前記選択されたアルゴリズムで経路探索を行う際に、前記共通点と一致するリンクについてはコストを大きくして経路探索を行う
ことを特徴とする請求項１または２に記載の経路探索装置。
【請求項４】
前記経路探索手段は、前記選択されたアルゴリズムを用いて探索を行い、探索された経路上に前記共通点と一致するリンクが存在する場合は、当該リンクのコストを大きく設定した上で、再度経路探索を行う
ことを特徴とする請求項３に記載の経路探索装置。
【請求項５】
走行した経路を取得し蓄積する走行経路蓄積工程と、
蓄積された走行経路に基づいて、利用者の嗜好に合致する経路探索アルゴリズムを選択するアルゴリズム選択工程と、
選択されたアルゴリズムを用いて、目的地までの経路探索を行う経路探索工程と、
を備え、
前記アルゴリズム選択工程は、
蓄積された走行経路のそれぞれについて、その出発地点から目的地点へ到達するための経路を、複数のアルゴリズムによって探索する工程と、
探索結果の経路と実際の走行経路との一致率である経路一致率をアルゴリズムごとに算出する工程と、
アルゴリズムごとに、各経路についての経路一致率に基づいて、ユーザの経路選択傾向とそのアルゴリズムの一致率を求める工程と、
ユーザの経路選択傾向との一致率が最も高いアルゴリズムを、利用者の嗜好に合致するアルゴリズムとして選択する工程と
を含むことを特徴とする経路探索方法。
【請求項６】
前記アルゴリズム選択工程では、
探索結果の経路と実際の走行経路が分岐する点である不一致点を求め、不一致点が存在する場合には、不一点以降について改めて経路探索を行い、この探索結果も利用して前記経路一致率を算出する
ことを特徴とする請求項５に記載の経路探索方法。
【請求項７】
前記アルゴリズム選択工程では、探索結果の経路と実際の走行経路が分岐する点である不一致点を求め、複数の探索結果から得られる複数の不一致点についての共通点を抽出し、
前記経路探索工程では、前記選択されたアルゴリズムで経路探索を行う際に、前記共通点と一致するリンクについてはコストを大きくして経路探索を行う
ことを特徴とする請求項５または６に記載の経路探索方法。
【請求項８】
前記経路探索工程では、前記選択されたアルゴリズムを用いて探索を行い、探索された経路上に前記共通点と一致するリンクが存在する場合は、当該リンクのコストを大きく設定した上で、再度経路探索を行う
ことを特徴とする請求項７に記載の経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１０−８２８４（Ｐ２０１０−８２８４Ａ）
【公開日】平成２２年１月１４日（２０１０．１．１４）
【国際特許分類】
【出願番号】特願２００８−１６９２７９（Ｐ２００８−１６９２７９）
【出願日】平成２０年６月２７日（２００８．６．２７）
【出願人】（５０２０８７４６０）株式会社トヨタＩＴ開発センター (232)
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【Ｆターム（参考）】
【公開日】平成２２年１月１４日（２０１０．１．１４）
【国際特許分類】
【出願日】平成２０年６月２７日（２００８．６．２７）
【出願人】（５０２０８７４６０）株式会社トヨタＩＴ開発センター (232)
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【Ｆターム（参考）】
[ Back to top ]