(57)【要約】【課題】意図的に様々な通行料金の経路をユーザーに提示でき、ユーザーの経路選択の自由度を高めるナビゲーション装置を提供すること。【解決手段】探索部１０１が、有料道路のコストを順次変更して複数の候補経路を探索し、算出部１０２が、探索部１０１によって探索された各候補経路の通行料金を算出し、選択部１０３が、探索部１０１による探索結果および算出部１０２による算出結果に基づいて、探索された複数の候補経路から通行料金の異なる複数の経路を選択し、提示部１０４が、選択部１０３によって選択された複数の経路に関する情報を提示する。【選択図】        図１
2005283168.tif 000002
【特許請求の範囲】
【請求項１】
有料道路のコストを順次変更して複数の候補経路を探索する探索手段と、
前記探索手段によって探索された各候補経路の通行料金を算出する算出手段と、
前記探索手段による探索結果および前記算出手段による算出結果に基づいて、探索された複数の候補経路から通行料金の異なる複数の経路を選択する選択手段と、
前記選択手段によって選択された複数の経路に関する情報を提示する提示手段と、
を有することを特徴とするナビゲーション装置。
【請求項２】
前記算出手段は、前記探索手段によって１の候補経路が探索されると、当該１の候補経路の通行料金を算出し、
前記探索手段は、前記算出手段による算出結果に基づいて、前記有料道路のコストを変更することを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
前記探索手段は、今回探索した候補経路の通行料金とそれまでに探索した候補経路の通行料金とが同一である場合に、通行料金が同一の候補経路における有料道路のコストの範囲を次回以降の探索の際に設定しないことを特徴とする請求項２に記載のナビゲーション装置。
【請求項４】
前記探索手段は、今回探索した候補経路の通行料金とそれまでに探索した候補経路の通行料金とが同一である場合に、有料道路のコストの低いもののみを候補経路とすることを特徴とする請求項２または３に記載のナビゲーション装置。
【請求項５】
前記選択手段は、通行料金が同一の候補経路が複数存在する場合に、通行料金が同一の候補経路の中で有料道路のコストが最も低い候補経路を選択することを特徴とする請求項１乃至３のいずれか１項に記載のナビゲーション装置。
【請求項６】
所定条件に関する情報を取得する条件情報取得手段をさらに有し、
前記選択手段は、前記条件情報取得手段によって取得された情報にかかる所定条件に基づいて、複数の経路を選択することを特徴とする請求項１乃至５のいずれか１項に記載のナビゲーション装置。
【請求項７】
ユーザーの入力によって、前記選択された複数の経路から１の経路を指定する指定手段と、
前記指定手段によって１の経路が指定される毎に、指定された経路の出発地点から目的地点までの距離と、前記指定された経路の有料道路のコストとを対応させた履歴情報を蓄積して記憶する記憶手段と、
をさらに有し、
前記探索手段は、出発地から目的地までの距離および記憶されている前記履歴情報に基づいて有料道路のコストを特定し、特定された有料道路のコストを用いて特定候補経路を探索し、
前記選択手段は、探索された前記特定候補経路を選択することを特徴とする請求項１乃至６のいずれか１項に記載のナビゲーション装置。
【請求項８】
有料道路コストを順次変更して複数の候補経路を探索する探索工程と、
前記探索工程によって探索された各候補経路の通行料金を算出する算出工程と、
前記探索工程による探索結果および前記算出工程による算出結果に基づいて、探索された複数の候補経路から通行料金の異なる複数の経路を選択する選択工程と、
前記選択工程によって選択された複数の経路に関する情報を提示する提示工程と、
を含んだことを特徴とするナビゲーション方法。
【請求項９】
請求項８に記載のナビゲーション方法をコンピュータに実行させることを特徴とするナビゲーションプログラム。
【請求項１０】
請求項９に記載のナビゲーションプログラムを記録したことを特徴とするコンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置、ナビゲーション方法、ナビゲーションプログラムおよびコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
従来、カーナビゲーション装置において、出発地から目的地までの経路を設定し案内する経路探索は基本的な機能として知られている。カーナビゲーション装置では経路を複数探索することができ、その候補を選択する際、必要な通行料金を表示や音声でユーザーが知ることができる。このように、既存のカーナビゲーション装置では、複数の候補の選択基準に関して距離または時間を優先したり、高速道路を使うあるいは使わないという選択をするなどして計算した結果、結果的に通行料金がいくらになるといった表現で提示される（たとえば、特許文献１参照。）。
【０００３】
たとえばこの特許文献１では、通行料金の高い道路が安い道路に対してコストが高くなるようにする手段を持っており、同じ距離や時間で目的地まで到着できる経路であれば通行料金の安い方の経路を算出することができる。
【０００４】
上記の従来技術では、通行料金が異なる複数の候補を意図的に算出しようとしているわけではなく、たまたま他の計算条件によって異なった通行料金の候補が出ることがあるというものである。そのため異なった料金の候補が出ることもあれば出ないこともある。
【０００５】
【特許文献１】特開２００２−３２３３３４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、ユーザーによっては、「料金の異なる経路を見比べて選びたい」、「通行料金を節約したいが時間がかかりすぎるのは避けたい」、「一般道が渋滞するところだけ高速道路を使いたい」、「均一料金区間だけ乗りたい」など様々な通行料金に対しての要望があることもあるが、上記の従来技術にかかるカーナビゲーション装置ではそれらの要望に的確に対応することができないという問題点があった。
【０００７】
また、上記特許文献１では、推奨経路として同じ距離や時間で目的地まで到着できる経路であれば通行料金の安い方の経路を算出することができるが、「所要時間によっては少しぐらいお金がかかってもよい」、「お金はいくらかかってもいいから早く行きたい」、「料金の異なる経路を見比べて選びたい」などの要望に応えることはできないという問題点があった。
【課題を解決するための手段】
【０００８】
請求項１に記載の発明にかかるナビゲーション装置は、有料道路のコストを順次変更して複数の候補経路を探索する探索手段と、前記探索手段によって探索された各候補経路の通行料金を算出する算出手段と、前記探索手段による探索結果および前記算出手段による算出結果に基づいて、探索された複数の候補経路から通行料金の異なる複数の経路を選択する選択手段と、前記選択手段によって選択された複数の経路に関する情報を提示する提示手段と、を有することを特徴とする。
【０００９】
また、請求項８に記載のナビゲーション方法は、有料道路のコストを順次変更して複数の候補経路を探索する探索工程と、前記探索工程によって探索された各候補経路の通行料金を算出する算出工程と、前記探索工程による探索結果および前記算出工程による算出結果に基づいて、探索された複数の候補経路から通行料金の異なる複数の経路を選択する選択工程と、前記選択工程によって選択された複数の経路に関する情報を提示する提示工程と、を含んだことを特徴とする。
【００１０】
また、請求項９に記載のナビゲーションプログラムは、請求項８に記載のナビゲーション方法をコンピュータに実行させることを特徴とする。
【００１１】
また、請求項１０に記載のコンピュータ読み取り可能な記録媒体は、請求項９に記載のナビゲーションプログラムを記録したことを特徴とする。
【発明を実施するための最良の形態】
【００１２】
以下に添付図面を参照して、この発明にかかるナビゲーション装置、ナビゲーション方法、ナビゲーションプログラムおよびコンピュータ読み取り可能な記録媒体の好適な実施の形態を詳細に説明する。
【００１３】
（ナビゲーション装置の機能的構成）
まず、この発明の実施の形態にかかるナビゲーション装置の内容について説明する。図１は、この発明の実施の形態にかかるナビゲーション装置の機能的構成の一例を示すブロック図である。
【００１４】
図１において、車両（四輪車、二輪車を含む）などに備えられたナビゲーション装置は、探索部１０１と、算出部１０２と、選択部１０３と、提示部１０４と、条件情報取得部１０５と、指定部１０６と、記憶部１０７とを含む構成となっている。
【００１５】
探索部１０１は、有料道路のコストを順次変更して複数の候補経路を探索する。また算出部１０２は、探索部１０１によって探索された各候補経路の通行料金を算出する。また選択部１０３は、探索部１０１による探索結果および算出部１０２による算出結果に基づいて、探索された複数の候補経路から通行料金の異なる複数の経路を選択する。
【００１６】
提示部１０４は、選択部１０３によって選択された複数の経路に関する情報を提示する。提示部１０４は、表示だけでなく音声によって知らせるようにしてもよい。また、経路に関する情報には、たとえば、経路情報、料金情報、時間情報などが含まれる。
【００１７】
条件情報取得部１０５は、所定条件に関する情報を取得する。その際、選択部１０３は、条件情報取得部１０５によって取得された情報にかかる所定条件に基づいて、複数の経路を選択する。
【００１８】
指定部１０６は、ユーザーが各種スイッチなどを操作することで、選択部１０３によって選択された複数の経路から１の経路を指定する。具体的には、たとえば、ユーザーが提示部１０４に提示された複数の経路に関する情報から所望の経路をタッチパネル、リモコンや各種スイッチなどを用いて選択操作することによって発生した入力信号を受け付けて、この入力信号に基づいて１の経路が指定される。
【００１９】
記憶部１０７は、指定部１０６によって１の経路が指定される毎に、指定された経路の出発地点から目的地点までの距離と、指定された経路の有料道路のコストとを対応させた履歴情報を蓄積して記憶する。蓄積情報の詳細については、後述する。その際、探索部１０１は、出発地から目的地までの距離および記憶されている履歴情報、すなわち記憶部１０７に蓄積して記憶された蓄積情報に基づいて有料道路のコストを特定し、特定された有料道路のコストを用いて特定候補経路を探索する。そして、選択部１０３は、探索部１０１によって探索された特定候補経路を選択する。
【００２０】
また算出部１０２は、探索部１０１によって１の候補経路が探索されると、当該１の候補経路の通行料金を算出し、探索部１０１は、算出部１０２による算出結果に基づいて、有料道路のコストを変更するようにしてもよい。具体的には、有料道路を選択しないようにするために、当該有料道路のコストを増加させたり、反対に、有料道路を選択するようするために、当該有料道路のコストを減少させる。
【００２１】
また探索部１０１は、今回探索した候補経路の通行料金とそれまでに探索した候補経路の通行料金とが同一である場合に、通行料金が同一の候補経路における有料道路のコストの範囲を次回以降の探索の際に設定しないようにしてもよい。
【００２２】
また探索部１０１は、今回探索した候補経路の通行料金とそれまでに探索した候補経路の通行料金とが同一である場合に、有料道路のコストの低いもののみを候補経路とするようにしてもよい。
【００２３】
また選択部１０３は、通行料金が同一の候補経路が複数存在する場合には、通行料金が同一の候補経路の中で有料道路のコストが最も低い候補経路を選択するようにしてもよい。
【００２４】
（ナビゲーション装置の処理の手順）
つぎに、この発明の実施の形態にかかるナビゲーション装置の処理の手順について説明する。図２は、この発明の実施の形態にかかるナビゲーション装置の処理の手順の一例を示すフローチャートである。
【００２５】
図２のフローチャートにおいて、まず、有料道路のコストを順次変更して複数の候補経路を探索する（ステップＳ２０１）。つぎに、探索された各候補経路の通行料金を算出する（ステップＳ２０２）。
【００２６】
ここで、ステップＳ２０１において、１の候補経路が探索されると、ステップＳ２０２において当該１の候補経路の通行料金を算出し、さらに、当該算出結果に基づいて、ステップＳ２０１に戻って、有料道路のコストを変更するようにしてもよい。
【００２７】
このように、複数の候補経路を探索してから通行料金を算出してもよく、また、１の経路探索と当該１の経路の通行料金の算出をそれぞれ交互に繰り返しておこなうようにしてもよい。
【００２８】
また、今回探索した候補経路の通行料金とそれまでに探索した候補経路の通行料金とが同一である場合に、通行料金が同一の候補経路における有料道路のコストの範囲を次回以降の探索の際に設定しないようにしてもよい。また、今回探索した候補経路の通行料金とそれまでに探索した候補経路の通行料金とが同一である場合に、有料道路のコストの低いもののみを候補経路とするようにしてもよい。
【００２９】
その後、探索された複数の候補経路から通行料金の異なる複数の経路を選択する（ステップＳ２０３）。そして、選択された複数の経路に関する情報を提示し（ステップＳ２０４）、一連の処理を終了する。ここで、通行料金が同一の候補経路が複数存在する場合に、通行料金が同一の候補経路の中で有料道路のコストが最も低い候補経路を選択するようにしてもよい。またその際、取得された情報にかかる所定条件に基づいて、複数の経路を選択するようにしてもよい。
【００３０】
また、ユーザーの入力によって、選択部１０３によって選択された複数の経路から１の経路が指定され、１の経路が指定される毎に、指定された経路の出発地点から目的地点までの距離と、指定された経路の有料道路のコストとを対応させた履歴情報を蓄積して記憶していた場合に、ステップＳ２０１において、出発地から目的地までの距離および記憶されている履歴情報に基づいて有料道路のコストを特定し、特定された有料道路のコストを用いて特定候補経路を探索するようにしてもよい。そのようにした場合に、ステップＳ２０３において、ステップＳ２０１で探索された特定候補経路を選択するようにする。
【実施例】
【００３１】
（ハードウエア構成）
つぎにこの発明の実施例にかかるナビゲーション装置のハードウエア構成について説明する。図３は、この発明の実施例にかかるナビゲーション装置のハードウエア構成の一例を示すブロック図である。
【００３２】
図３において、この発明の実施例にかかるナビゲーション装置は、車両に搭載されており、ナビゲーション制御部３００と、ユーザー操作部３０１と、表示部３０２と、位置認識部３０３と、記録媒体３０４と、記録媒体デコード部３０５と、案内音出力部３０６と、地点検索部３０７と、経路探索部３０８と、経路誘導部３０９と、案内音生成部３１０と、スピーカ３１１と、を含む構成となっている。
【００３３】
ここで、ナビゲーション制御部３００は、ナビゲーション装置全体を制御する。また、ユーザー操作部３０１は、操作ボタン、リモコン、タッチパネルなどを含む。また、表示部３０２は、液晶ディスプレイや有機ＥＬディスプレイなどを含む。
【００３４】
位置認識部３０３は、自車位置情報を取得する。ここで自車位置情報は、ＧＰＳ衛星からの電波を受信し、ＧＰＳ衛星との幾何学的位置を求めるものであり、地球上どこでも計測可能である。電波としては、１．５７５４２ＧＨｚの搬送波で、Ｃ／Ａ（Ｃｏａｒｓｅ  ａｎｄ  Ａｃｃｅｓｓ）コードおよび航法メッセージが乗っているＬ１電波を用いておこなわれる。これによって、現在の車両の位置（緯度および経度）を検知する。さらに、車速センサやジャイロセンサ等の各種センサによって収集された情報を加味してもよい。
【００３５】
記録媒体３０４は、たとえば、ハードディスク（ＨＤ）であり、その代わりにあるいはＨＤに加えて、ＤＶＤ、コンパクトディスク（ＣＤ）などの着脱可能な記録媒体であってもよい。また、記録媒体デコード部３０５は、ＨＤ、ＤＶＤ、ＣＤを読み取り／書き込みの制御をおこなう。
【００３６】
そして、ナビゲーション制御部３００は、位置認識部３０３によって算出された自車位置情報と、記録媒体３０４から記録媒体デコード部３０５を経由して得られた地図データベース（ＤＢ）情報とに基づいて、表示部３０２へ地図上のどの位置を走行しているかを出力する。
【００３７】
案内音出力部３０６は、接続される、一つまたは複数のスピーカ３１１への出力を制御することによって、案内音を再生する。
【００３８】
地点検索部３０７は、ユーザー操作部３０１から入力された情報に基づいて、任意の地点を検索し、これを表示部３０２へ出力する。また、経路探索部３０８は、地点検索部３０７によって得られた地点情報に基づいて、当該地点までの最適な経路を算出する。また、経路誘導部３０９は、経路探索部３０８によって得られた情報と自車位置情報に基づいて、リアルタイムな経路誘導情報の生成をおこなう。
【００３９】
案内音生成部３１０は、パターンに対応したトーンと音声のデータを生成する。すなわち、経路情報に基づいて、案内ポイントに対応した仮想音源の設定と音声ガイダンス情報の生成をおこない、これを案内音出力部３０６へ出力する。
【００４０】
（ナビゲーション装置の処理の手順）
つぎに、この発明の実施例にかかるナビゲーション装置の処理の手順について説明する。なお、有料道路として高速道路を用いた例を以下に説明する。図４は、この発明の実施例にかかるナビゲーション装置の、高速道路の使用頻度と高速道路のコストとの関係を表したテーブルを示す説明図であり、図５は、この発明の実施例にかかるナビゲーション装置の、探索待ちリストに関するデータベースの内容を示す説明図である。また、図６および図７は、この発明の実施例にかかるナビゲーション装置の処理の手順を示すフローチャートである。
【００４１】
ナビゲーション装置の経路探索では、通常、記録部などに記録された道路のデータを用いて最適な経路を探索する。ここで、高速道路インターチェンジやジャンクションも含め、交差点から交差点までの１本の道路のことをリンクとする。自動車の通行において、単純に道路の長さが最短の経路が、最適な経路とは限らないため、リンクの長さのほかに、道路の幅員や種別、高速道路か否かなど様々な要素を付加したコストという値をリンク毎に設定し、出発地から目的地までの全リンクの総コストが最適になる経路を探索する。
【００４２】
また、高速道路ではない道路を、一般道とし、東名高速道路などの都市間高速道路を高速道路とし、首都高速道路などの都市高速道路を都市高速とする。通常、一般道よりも高速道路の方が速い速度で自動車は通行することができるので、同じ１ｋｍの長さのリンクであっても、一般道をコスト「１０００」とすれば高速道路はたとえば「５００」とするなどして、高速道路は一般道に比べて選びやすくして、推奨の経路が一般的に自動車の通行に最適な経路になるようにしている。
【００４３】
また、高速道路を回避する設定などにした場合には、それとは反対に一般道コスト「１０００」に対して高速道路を「１０万」などにして、高速道路のコストを増加させ、選び難くする。
【００４４】
ここで、通行料金の異なる経路を複数作成するために、高速道路のコストの算出に独自の要素を加える。そのために、高速道路の使用頻度パラメータを用意する。図４において、この実施例では、高速道路の使用頻度パラメータを、たとえば６４段階に設定する。このパラメータは経路にどのぐらい高速道路を使うかを表しており、１〜６４までの６４段階の値を取る。なお、段階はいくつにしてもよいが２のｎ乗で表せる数にする。１は最も高速道路を使わない状態を表し、６４は非常に遠回りでも高速道路を最も使う状態を表す。３２はその中間で、普通に高速道路を使うという状態を表す。
【００４５】
そして、その中間値である「３２」の高速道路のコストを「１００％」とし、それよりも高速道路の使用頻度パラメータの値が小さくなるにしたがって高速道路のコストを高く設定している。
【００４６】
ここでいう高速道路のコストは、一般道に対して高速道路のコストをどれだけ増減するかの割合である。たとえば、一般道でコストが「１０００」に相当する長さの道路と同じ長さの高速道路を、高速道路のコストが５００％とすれば、コストは「５０００」となる。また、高速道路のコストが９５％であれば、コストは「９５０」となる。このように、高速道路の使用頻度パラメータによって、高速道路のコストを増減させ高速道路の相対的な経路への採用されやすさを可変させる。
【００４７】
そして、高速道路の使用頻度が「１」の場合に、高速道路のコストを最も高く「１６２％」としている。一方、高速道路の使用頻度が「３２」よりも高速道路の使用頻度の値が大きくなるにしたがって高速道路のコストを低く設定している。そして、高速道路の使用頻度が「６４」の場合に、高速道路のコストを最も低く「３６％」としている。
【００４８】
これによって、高速道路の使用頻度毎に高速道路のコストを変更して設定する。使用頻度の段階および使用頻度毎のコストの値については、これに限定されるものではなく、任意に設定することができる。
【００４９】
図５に示す探索待ちリストに関するデータベースにおいて、探索待ちリストとは順位を持っており、順位の高い方から、一つずつ取り出す。そして、取り出した後は２位のものが１位になり以降一つずつ上に上がる。加えるときは値のある中で一番低い順位の一つ下に加える。
【００５０】
図６において、まず、たとえば図５に示した検索待ちリストに、高速道路の使用頻度の中間値である「３２」を初期値として入力する（ステップＳ６０１）。つぎに、高速道路の使用頻度を探索待ちリストの１番目の値（以下「Ａ」とする）として、経路探索を実行する（ステップＳ６０２）。その後、探索された経路に対する通行料金を算出し（ステップＳ６０３）、探索待ちリストからＡを消去する（ステップＳ６０４）。
【００５１】
そして、ステップＳ６０３において算出された通行料金が「０円」か否かを判断する（ステップＳ６０５）。ここで、「０円」ではない場合（ステップＳ６０５：Ｎｏ）は、つぎに、すでに保存されたいずれかの経路の通行料金と一致するか否かを判断する（ステップＳ６０６）。ここで、一致する場合（ステップＳ６０６：Ｙｅｓ）は、図７に示すステップＳ７０１へ移行する。
【００５２】
一方、ステップＳ６０６において、すでに保存されたいずれかの経路の通行料金と一致しない場合（ステップＳ６０６：Ｎｏ）は、ステップＳ６０７へ移行する（最初のときは、保存されている経路が存在しないので、ステップＳ６０７へ移行する）。ステップＳ６０７では、当該経路とその通行料金を保存する。これによって、新しい料金の経路ができたことになる。その後、図７に示すステップＳ７０５へ移行する。
【００５３】
ステップＳ６０５において、通行料金が「０円」である場合（ステップＳ６０５：Ｙｅｓ）は、Ａ以下の使用頻度を封鎖する、すなわちＡ以下の高速道の使用頻度を以降は使わないようにする（ステップＳ６０８）。たとえば、高速道路の使用頻度が「３２」であれば、以降の掲載の際には、「３２」〜「６４」を封鎖して、使わないようにする。その後、図７に示すステップＳ７０５へ移行する。
【００５４】
図７において、まず、図６に示したステップＳ６０６において一致した、すでに保存された経路の通行料金は、今回計算した高速道路の使用頻度より低い値で計算したものであるか否かを判断する（ステップＳ７０１）。ここで、低い値で計算したものである場合（ステップＳ７０１：Ｙｅｓ）は、一致したすでに保存された経路と通行料金を削除し、今回計算した経路と通行料金に書き換える（ステップＳ７０２）。これは、同じ料金であるならば、できるだけ高速道路の使用頻度の高い経路を選択することができるようにするためである。
【００５５】
そして、Ａから、一致した経路を計算した高速道路の使用頻度までを封鎖する（ステップＳ７０３）。たとえば、Ａ＝「２４」で、「１６」の結果と同じ通行料金であれば、「１６」〜「２４」は、それ以降は、計算しないようにする。その後、ステップＳ７０５へ移行する。
【００５６】
一方、ステップＳ７０１において、図６に示したステップＳ６０６において一致した、すでに保存された経路の通行料金は、今回計算した高速道路の使用頻度より高い値で計算したものである場合（ステップＳ７０１：Ｎｏ）は、Ａから、一致した経路を計算した高速道路の使用頻度までを封鎖する（ステップＳ７０４）。たとえば、Ａ＝「４０」で、「４８」の結果と同じ通行料金であれば、「４０」〜「４８」は、それ以降は、以降計算しないようにする。その後、ステップＳ７０５へ移行する。
【００５７】
ステップＳ７０５において、Ａがこの処理を何回通った後に算出されたのかの回数Ｎを求め、Ｎの回数によって、図５に示した探索待ちリストに、以下に示す式から算出されるＳをＡに加算した値を加える（ステップＳ７０５）。
【００５８】
ｌｏｇ2Ｍ−Ｎ−２≧０の場合は、Ｓ＝±２(log2M-N-2)
ｌｏｇ2Ｍ−Ｎ−２＜０の場合は、Ｓ＝０
ここで、Ｍは高速道路の使用頻度の段階数（本実施例においては６４）である。
【００５９】
上式からＳを算出すると、Ｎ＝０の場合は、Ｓ＝±１６、Ｎ＝１の場合は、Ｓ＝±８、Ｎ＝２の場合は、Ｓ＝±４、Ｎ＝３の場合は、Ｓ＝±２、Ｎ＝４の場合は、Ｓ＝±１、Ｎ＝５以上の場合は、Ｓ＝０すなわち加算しない、となる。
【００６０】
たとえば、Ａ＝「３２」であれば、初めての処理であるので、Ｎ＝０となり、３２±１６＝「１６」，「４８」となる。同様に、Ａ＝「４８」であれば、２回目の処理であるので、Ｎ＝１となり、４８±８＝「４０」，「５６」となり、Ａ＝「４０」であれば、３回目の処理であるので、Ｎ＝２となり、４０±４＝「３６」，「４４」となり、２つの値を探索待ちリストに加える。
【００６１】
このように高速道路の使用頻度の段階数Ｍを２のｎ乗の値に設定することで上式を用いてＳを算出することができる。なお、当然だが、上式を用いずにその他の方法でＳを算出してもよい。
【００６２】
つぎに、探索待ちリストに封鎖された高速道路の使用頻度の値があるか否かを判断する（ステップＳ７０６）。ここで、高速道路の使用頻度の値がある場合（ステップＳ７０６：Ｙｅｓ）は、当該値を探索待ちリストから消去し（ステップＳ７０７）、ステップＳ７０８へ移行する。一方、高速道路の使用頻度の値がない場合（ステップＳ７０６：Ｎｏ）は何もせず、ステップＳ７０８へ移行する。
【００６３】
ステップＳ７０８では、探索待ちリストに値があるか否かを判断し、未だ値がある場合（ステップＳ７０８：Ｙｅｓ）は、図６に示したステップＳ６０２に戻って、以後、処理を繰り返しおこなう。一方、探索待ちリストに値がすべてなくなった場合（ステップＳ７０８：Ｎｏ）は、保存された複数の経路と通行料金を結果に格納し（ステップＳ７０９）、一連の処理を終了する。
【００６４】
上記図６および図７のフローチャートの処理をおこなうことで、通行料金の異なる複数の経路を最小限の計算回数で得ることができる。この処理によって、最大６４本の通行料金の違う経路が得られる。通常は、６４本になることはまずなく、通行料金が同じ経路が得られた範囲は理論上最大効率で封鎖されて、計算回数を減らすようにしている。したがって、車載機器で実現可能な計算速度によって、異なる料金の経路を効率的に得ることができる。
【００６５】
（表示画面の具体例）
図８および図９は、この発明の実施例にかかるナビゲーション装置の表示画面の一例を示す説明図である。図８において、表示画面は、複数の異なる通行料金の経路を、１本ずつまたは複数同時に表示する。経路の表示のほかに、距離・時間・通行料金を表示するとよい。ユーザーはリモコンなどの操作装置を使って、所望の経路を指定することができる。またはタッチパネルになっていてもよい。
【００６６】
また、画面の右にあるのが選択部１０３によって選択された経路（以下「選択経路」という）であり、料金、距離、時間が表示される（（１）〜（６））。選択経路が一画面に収まらない場合は、上下についている「前」ボタン８０１、「次」ボタン８０２が押下されることによって、さらに別の選択経路を表示することができる。各表示の色がその情報の経路を示すように色分けしてもよく、また、各表示とその情報の経路に同一の符号（（１）〜（６））を付すようにしてもよい。
【００６７】
また、「条件設定」ボタン８０３が押下されることによって、料金、距離、時間で条件を絞り込むことができる。図９は、条件を設定する画面である。それぞれ何円以下かなどを指定すると、すべての条件を満たす選択経路だけを表示する。また、表示するときの並べ替える優先順位を通行料金や時間など所望のものをキーにして並べ替えることもできる。
【００６８】
たとえば、料金を１０００円以下にして、選択経路の優先順を時間にすると、１０００円以下で、一番時間が早い選択経路が一番目の表示（上の画面の（１））になる。図８において、１０００円以下で一番早いのは（３）なので、（３）→（２）→（１）の順で並ぶ。時間が同じであれば、つぎに設定された優先順（距離）がすぐれているものが上位にくることになる。
【００６９】
このように、作られた複数の選択経路をすべて表示するほかに、ユーザーによって設定された条件で表示するようにしてもよい。また、たとえば、「○○円以上〜○○円以下までを表示」、「○○円以下で時間の早い順に表示」、「○○円に近い順に表示」、「○○分で目的地に着くものの中で料金の安い順に表示」などを条件として設定するようにしてもよい。また、条件に当てはまる選択経路が一つしかなければ、自動的に当該選択経路を指定してもよい。
【００７０】
意図的に様々な通行料金の経路を生成した上でこのような絞込みをするため、通常の推奨経路を複数求めたときよりも、通行料金の異なる複数の候補経路をより多く掲示することができる。これによって、ユーザーはより多くの選択肢の中から選択できたり、また最適な条件に当てはまる経路を得ることができるようになる。
【００７１】
（通行料金嗜好の学習）
つぎに、通行料金の嗜好学習の内容について説明する。まず、ユーザーが複数の選択経路の中でどの選択経路を指定したかを、ＨＤＤなどの記録装置に保存しておく。この際、指定された選択経路の距離・通行料金のほかに、指定された選択経路を探索したときの高速道路の使用頻度を保存しておく。高速道路の使用頻度は、一般道と高速道路の使い方の割合であるので、この値を保存することによって、ユーザーがどの程度の割合で高速道路を使うのを好むかに関する履歴情報を保存することができる。
【００７２】
以降の経路探索をおこなうときに、保存されているのと同じ程度の出発地と目的地の距離であれば、推奨ルートとして経路の計算に、頻繁に選ばれる高速道路の使用頻度を使用して、推奨ルートを計算することができる。したがって、ユーザーはわざわざ通行料金を指定するなどの操作をおこなわなくても、最も嗜好する高速道路の使用比率で、推奨ルートを得ることができる。
【００７３】
図１０は、この発明の実施例にかかるナビゲーション装置の、通行料金の嗜好学習のデータベースの内容を示す説明図である。図１０に示すような、目的地までの距離と選択された経路の高速道路の使用頻度を目的地の距離順に並べたデータベースをシステム内部に作成する。
【００７４】
具体的には、たとえば距離によって分類を５つ（０〜１０ｋｍ、１０〜４０ｋｍ、４０〜８０ｋｍ、８０ｋｍ〜１５０ｋｍ、１５０ｋｍ以上）にわける。つぎに推奨ルートを求めるときに、目的地までの距離がどの分類にあたるかをまず判断し、含まれる分類のデータベースを参照して高速道路の使用頻度を決定する。
【００７５】
複数のデータから高速道路の使用頻度を決定する方法は、平均値や中央値や、他の統計手法を用いてもよい。たとえば分散値が一定以下の場合のみ値を採用するなどして、誤判定を避けるようにするとよい。また、該当する分類にある程度データ数が所定量に達するまで、この機能を有効にしないようにしてもよい。
【００７６】
このようにして、提示されている複数の選択経路から１の経路をユーザーに指定させ、１の経路が指定される毎に、指定された経路の出発地点から目的地点までの距離と、指定された経路の有料道路のコストとを対応させた履歴情報を蓄積して記憶しておく。そして、出発地から目的地までの距離および記憶されている履歴情報に基づいて有料道路のコストを特定し、特定された有料道路のコストを用いて特定候補経路を探索し、探索された特定候補経路を選択することによって、通行料金嗜好の学習機能を実現することができる。
【００７７】
なお、上記実施例にあっては、車両に搭載されているナビゲーション装置について説明したが、これに限定されるものではなく、たとえば、携帯電話機などの携帯型情報処理端末装置に搭載されている、歩行者用ナビゲーション装置や、Ｗｅｂサイトの経路提供アプリケーションなどにも適用される。
【００７８】
以上説明したように、この実施の形態によれば、探索部１０１が、有料道路のコストを順次変更して複数の候補経路を探索し、算出部１０２が、探索部１０１によって探索された各候補経路の通行料金を算出し、選択部１０３が、探索部１０１による探索結果および算出部１０２による算出結果に基づいて、探索された複数の候補経路から通行料金の異なる複数の経路を選択し、提示部１０４が、選択部１０３によって選択された複数の経路に関する情報を提示するため、出発地から目的地までの複数の候補経路の通行料金を算出し、算出された通行料金が異なる候補経路に関する情報を、当該通行料金に関する情報とともに一覧表示する、あるいは音声出力することができ、これによって、意図的に様々な通行料金の経路をユーザーに提示でき、ユーザーの経路選択の自由度を高めることができる。
【００７９】
また、この実施の形態によれば、探索部１０１が、今回探索した候補経路の通行料金とそれまでに探索した候補経路の通行料金とが同一である場合に、次回以降の探索において通行料金が同一の候補経路における有料道路のコストの範囲を設定しないようにするため、探索された候補経路の通行料金を順次算出する際、すでに算出された１の候補経路の通行料金と同一の通行料金となる２の候補経路があった場合に、有料道路の使用割合の順に上記候補経路を並べたときの上記１の候補経路と上記２の候補経路の間にある候補経路の通行料金を算出しないで済み、経路の計算を効率的におこなうことができる。
【００８０】
また、この実施の形態によれば、探索部１０１が、今回探索した候補経路の通行料金とそれまでに探索した候補経路の通行料金とが同一である場合に、有料道路のコストの低いもののみを候補経路とするため、あるいは、選択部１０３が、通行料金が同一の候補経路が複数存在する場合に、通行料金が同一の候補経路の中で有料道路のコストが最も低い候補経路を選択するため、算出された結果、同一の通行料金となる候補経路が複数存在する場合に、有料道路の使用割合が最も高い候補経路に関する情報のみを提示することができる。
【００８１】
また、この実施の形態によれば、条件情報取得部１０５が、所定条件に関する情報を取得し、選択部１０３が、条件情報取得部１０５によって取得された情報にかかる所定条件に基づいて、複数の経路を選択するため、候補経路のうち、取得された情報にかかる条件に合致する経路に関する情報のみを提示することができる。
【００８２】
なお、本実施の形態におけるナビゲーション方法は、あらかじめ用意されたコンピュータ（たとえばマイクロコンピュータ）に読み取り可能なプログラムであってもよく、またそのプログラムをコンピュータで実行することによって実現される。このプログラムは、ＨＤ、ＦＤ、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また、このプログラムは、インターネットなどのネットワークを介して配布することが可能な伝送媒体であってもよい。
【図面の簡単な説明】
【００８３】
【図１】この発明の実施の形態にかかるナビゲーション装置の機能的構成の一例を示すブロック図である。
【図２】この発明の実施の形態にかかるナビゲーション装置の処理の手順の一例を示すフローチャートである。
【図３】この発明の実施例にかかるナビゲーション装置のハードウエア構成の一例を示すブロック図である。
【図４】この発明の実施例にかかるナビゲーション装置の、高速道路の使用頻度と高速道路のコストとの関係を表したテーブルを示す説明図である。
【図５】この発明の実施例にかかるナビゲーション装置の、探索待ちリストに関するデータベースの内容を示す説明図である。
【図６】この発明の実施例にかかるナビゲーション装置の処理の手順を示すフローチャート（その１）である。
【図７】この発明の実施例にかかるナビゲーション装置の処理の手順を示すフローチャート（その２）である。
【図８】この発明の実施例にかかるナビゲーション装置の表示画面の一例を示す説明図である。
【図９】この発明の実施例にかかるナビゲーション装置の表示画面の別の一例を示す説明図である。
【図１０】この発明の実施例にかかるナビゲーション装置の、通行料金の嗜好学習のデータベースの内容を示す説明図である。
【符号の説明】
【００８４】
１０１  探索部
１０２  算出部
１０３  選択部
１０４  提示部
１０５  条件情報取得部
１０６  指定部
１０７  記憶部
３００  ナビゲーション制御部
３０１  ユーザー操作部
３０２  表示部
３０３  位置認識部
３０４  記録媒体
３０５  記録媒体デコード部
３０６  案内音出力部
３０７  地点検索部
３０８  経路探索部
３０９  経路誘導部
３１０  案内音生成部
３１１  スピーカ
【図１】
2005283168.tif 000003
【図２】
2005283168.tif 000004
【図３】
2005283168.tif 000005
【図４】
2005283168.tif 000006
【図５】
2005283168.tif 000007
【図６】
2005283168.tif 000008
【図７】
2005283168.tif 000009
【図８】
2005283168.tif 000010
【図９】
2005283168.tif 000011
【図１０】
2005283168.tif 000012