(57)【要約】【課題】出発地から目的地までのルートを算出するルート探索装置において、ユーザの手を煩わせることなく、自動的に通過道路を設定する技術を提供する。【解決手段】ルート探索装置は、過去のある時点で取得された出発地、当該時点において指定された目的地、および当該時点において指定された通過道路の組を１つ含むレコードが１つ以上記録されるメモリを有し、ユーザが指定した指定出発地および指定目的地を取得し（ステップ１０５、１１０、１１４）、メモリに記録された１つ以上のレコード中に、指定出発地の所定の近傍にある出発地および前記指定目的地の所定の近傍にある目的地を含む該当レコードがある場合、指定出発地を出発し、該当レコードに含まれる通過道路を通過し、指定目的地に至るルートを算出する（ステップ１１５〜１４０）。【選択図】図３
2015169611.tif 000002
【特許請求の範囲】
【請求項１】
過去のある時点で取得された過去の出発地、前記時点において指定された過去の目的地、および前記時点において指定された過去の通過道路の組を１つ含むレコードが１つ以上記録されるメモリ（１６）と、
今回の出発地およびユーザが指定した今回の目的地を取得する取得手段（１０５、１１０、１１４）と、
前記メモリに記録された前記１つ以上のレコード中に、前記今回の出発地と同じ位置の過去の出発地および前記今回の目的地と同じ位置の過去の目的地を含む該当レコードがある場合、前記今回の出発地を出発し、前記該当レコードに含まれる過去の通過道路を通過し、前記今回の目的地に至る第１ルートを算出するルート探索手段（１１５〜１４０）と、を備えたルート探索装置。
【請求項２】
前記ルート探索手段は、前記メモリに記録された前記１つ以上のレコード中に、前記今回の出発地から所定の距離内にある過去の出発地および前記今回の目的地から所定の距離内にある過去の目的地を含む該当レコードがある場合、前記今回の出発地を出発し、前記該当レコードに含まれる過去の通過道路を通過し、前記今回の目的地に至る前記第１ルートを算出することを特徴とする請求項１に記載のルート探索装置。
【請求項３】
前記ルート探索手段は、前記第１ルート（４１、４３）を算出すると共に、前記今回の出発地を出発し、前記該当レコードに含まれる過去の通過道路を通過せず、前記今回の目的地に至る第２ルート（４１、４２）を算出し、前記第１ルートと前記第２ルートのコストを比較し、比較の結果に基づいて、前記第１ルートと前記第２ルートのうち一方を選んで前記ユーザに表示することを特徴とする請求項１または２に記載のルート探索装置。
【請求項４】
前記メモリでは、過去のある時点で取得された過去の出発地、前記時点において指定された過去の目的地、および前記時点において指定された過去の通過道路の組を１つ含むレコードが、前記時点において使用された過去のルート探索条件に関連付けられて記録され、
前記取得手段は更に、今回のルート探索条件を取得し、
前記ルート探索手段は、前記今回の出発地と同じ位置にある過去の出発地および前記今回の目的地と同じ位置にある過去の目的地を含む該当レコードが、前記今回のルート探索条件に合致する過去のルート探索条件に関連付けられて前記メモリに記録されている場合、前記今回の出発地を出発し、前記該当レコードに含まれる過去の通過道路を通過し、前記今回の目的地に至る前記第１ルートを、前記今回のルート探索条件に従って算出することを特徴とする請求項１ないし３のいずれか１つに記載のルート探索装置。
【請求項５】
過去のある時点で取得された過去の出発地、前記時点において指定された過去の目的地、および前記時点において指定された過去の通過道路の組を１つ含むレコードが１つ以上記録されるメモリ（１６）を有するルート探索装置に用いられるルート探索プログラムであって、
当該ルート探索装置が有する制御回路（１７）を、
今回の出発地およびユーザが指定した今回の目的地を取得する取得手段（１０５、１１０、１１４）、および
前記メモリに記録された前記１つ以上のレコード中に、前記今回の出発地と同じ位置の過去の出発地および前記今回の目的地と同じ位置の過去の目的地を含む該当レコードがある場合、前記今回の出発地を出発し、前記該当レコードに含まれる過去の通過道路を通過し、前記今回の目的地に至る第１ルートを算出するルート探索手段（１１５〜１４０）として機能させるルート探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルート探索装置およびルート探索プログラムに関するものである。
【背景技術】
【０００２】
従来、出発地から目的地までのルートを算出する際のルートを、ユーザの好みを反映して算出するルート探索装置が知られている。
【０００３】
例えば、出発地および目的地に加え、通過したい道路をユーザが指定した場合、ルート探索装置は、出発地から、当該通過したい道路を通過し、目的地に至るルートを算出する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００２−３１０６９８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、上記のような技術では、出発地、目的地が過去に指定したものと同じであっても、ユーザは通過したい道路を毎回指定する必要があり、指定のための操作がユーザにとっては煩わしい。
【０００６】
本発明は上記点に鑑み、出発地から目的地までのルートを算出するルート探索装置において、ユーザの手を煩わせることなく、自動的に通過道路を設定する技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するための請求項１に記載の発明は、過去のある時点で取得された過去の出発地、前記時点において指定された過去の目的地、および前記時点において指定された過去の通過道路の組を１つ含むレコードが１つ以上記録されるメモリ（１６）と、今回の出発地およびユーザが指定した今回の目的地を取得する取得手段（１０５、１１０、１１４）と、前記メモリに記録された前記１つ以上のレコード中に、前記今回の出発地と同じ位置の過去の出発地および前記今回の目的地と同じ位置の過去の目的地を含む該当レコードがある場合、前記今回の出発地を出発し、前記該当レコードに含まれる過去の通過道路を通過し、前記今回の目的地に至る第１ルートを算出するルート探索手段（１１５〜１４０）と、を備えたルート探索装置である。
【０００８】
このように、ルート探索装置は、今回の出発地および今回の目的地を取得すると、その今回の出発地と同じ位置の過去の出発地および今回の目的地と同じ位置の過去の目的地を含む該当レコードが記録されていれば、その該当レコードに含まれる過去の通過道路を含んだ第１ルートを算出する。したがって、ユーザの手を煩わせることなく、自動的に通過道路を設定することができる。
【０００９】
なお、上記および特許請求の範囲における括弧内の符号は、特許請求の範囲に記載された用語と後述の実施形態に記載される当該用語を例示する具体物等との対応関係を示すものである。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施形態に係る車両用ナビゲーション装置１の構成図である。
【図２】第１実施形態におけるバックアップデータの構成を示す図である。
【図３】第１実施形態において制御回路が実行するルート探索処理のフローチャートである。
【図４】第２実施形態において制御回路が実行するルート探索処理のフローチャートである。
【図５】第３実施形態において制御回路が実行するルート探索処理のフローチャートである。
【図６】第３実施形態におけるルートの比較の方法を示す図である。
【図７】第４実施形態におけるバックアップデータの構成を示す図である。
【図８】第４実施形態において制御回路が実行するルート探索処理のフローチャートである。
【発明を実施するための形態】
【００１１】
（第１実施形態）
以下、本発明の第１実施形態について説明する。図１に示すように、本実施形態の車両用ナビゲーション装置１（ルート探索装置の一例に相当する）は、車両に搭載され、位置検出器１１、表示装置１２、操作部１３、音声出力装置１４、地図データ取得装置１５、外部メモリ１６、および制御回路１７を有する。
【００１２】
位置検出器１１は、ＧＰＳ受信機、車速センサ、加速度センサ、ジャイロセンサ等、車両の現在位置を特定するための信号を制御回路１７に出力するセンサである。表示装置１２は、制御回路１７の制御に従って文字や画像をユーザに表示する液晶ディスプレイ等の装置である。操作部１３は、ユーザの操作を受け付け、受け付けた操作に応じた信号を制御回路１７に出力する装置である。音声出力装置１４は、車内のユーザに聞かせるための音声を出力する装置である。地図データ取得部１５は、制御回路１７の制御に従って地図データを取得して制御回路１７に出力する装置である。
【００１３】
外部メモリ１６は、制御回路１７の外部に配置され、図２に例示するような構成のバックアップデータを記憶する不揮発性記憶媒体である。このバックアップデータは、複数のレコードを含むことができるようになっている。各レコードは、過去のルート探索処理時に制御回路１７が取得した当該過去の時点における現在地、目的地、および通過道路の組の情報が含まれている。より具体的には、各レコードには、当該過去の現在地の位置座標、当該過去の目的地の位置座標、および当該過去の通過道路の位置座標の組が１組のみ含まれている。
【００１４】
このバックアップデータには、車両用ナビゲーション装置１の使用開始時にはレコードが１つも記録されて居らず、後述する図３の処理のステップ１５５にてレコードが１個ずつ書き込まれるようになっている。
【００１５】
制御回路１７は、ＣＰＵ、ＲＡＭ、ＲＯＭ、フラッシュメモリ等を備えた装置（例えばマイクロコントローラ）であって、ＲＯＭまたはフラッシュメモリに記録されたプログラムをＣＰＵが実行することで、各種処理を実現するようになっている。
【００１６】
制御回路１７がプログラムを実行することによって行う具体的な処理としては、現在位置特定処理、地図表示処理、ルート探索処理、ルート案内処理等がある。現在位置特定処理は、位置検出器１１からの信号に基づいて、周知のマップマッチング等の技術を用いて車両の現在位置や向きを特定する処理である。
【００１７】
地図表示処理は、車両の現在位置の周辺等の特定の領域の地図を、画像表示装置１２に表示させる処理である。この際、地図表示のために用いる情報は、道路形状データから取得する。
【００１８】
ルート探索処理は、操作部１３からユーザによる目的地の入力を受け付け、現在位置（出発位置）から当該目的地までの最適なルートを算出して表示する処理である。
【００１９】
ルート案内処理は、ルート探索処理によって表示されたルートに沿った走行を案内する処理である。制御回路１７は、ルート案内処理において、ルートと自車位置との位置関係を逐次監視する。そして、ルート上の右左折交差点等の案内ポイントの手前に自車両が到達したときに、右左折等を指示する案内音声を音声出力装置１４に出力させ、当該案内ポイントの拡大図を表示装置１２に表示させることで、ルートに沿った車両の運転を案内する。
【００２０】
以下、ルート探索処理の詳細について説明する。制御回路１７は、ユーザが操作部１３に対して所定のルート探索開始操作を行ったことに基づいて、制御回路１７のＲＯＭ等に記録されている所定のプログラムを実行することで、図３のルート探索処理を実現する。
【００２１】
図３の処理においては、まずステップ１０５で、上述の現在位置特定処理を行うことで、車両の現在地の位置座標を取得する。続いてステップ１１０では、操作部１３に対するユーザの目的地指定操作に従って、ユーザが指定した目的地を取得する。ユーザによる目的地の指定方法は、表示装置１２に表示された地図上の特定の位置をタッチパネルで指定する方法でもよいし、過去の目的地設定履歴に含まれる目的地を１つ指定する方法でもよい。
【００２２】
続いてステップ１１５では、外部メモリ１６からバックアップデータを読み出す。なお、本事例では、既に外部メモリ１６中のバックアップデータには、過去に、後述するステップ１５５の処理によって、図２に例示するように、複数個のレコードが既に記録されているものとする。
【００２３】
続いてステップ１２０では、読み出したバックアップデータ中の複数のレコード中に、該当レコードがあるか否か判定する。該当レコードは、ステップ１０５で取得した今回の現在地と同じ位置の過去の現在地を含み、ステップ１１０で取得した今回の目的地と同じ位置の過去の目的地を含むレコードである。例えば、今回の現在地および目的地の位置がａおよびｂである場合、図２における１番目のレコードが該当レコードになる。該当レコードがあると判定した場合はステップ１２５に進む。
【００２４】
該当レコードがないと判定した場合は、ステップ１２５、１３０をバイパスしてステップ１３５に進み、今回の現在地から今回の目的地までの最適な（すなわち最もコストの低い）ルートを探索する。この探索の際、通過道路（すなわち、探索するルートが必ず通らなければならない道路上の一点）は、設定しない。
【００２５】
ステップ１２５では、該当レコード中に通過道路指定データは存在するか否かを判定する。図２における１番目のレコードが該当レコードである場合には、ｃという過去の通過道路の位置、すなわち、通過道路指定データが含まれているので、存在すると判定する。存在すると判定する場合は、ステップ１３０に進む。
【００２６】
存在しないと判定する場合は、ステップ１３０をバイパスしてステップ１３５に進み、今回の現在地から今回の目的地までの最適なルートを探索する。この探索の際、通過道路は、設定しない。
【００２７】
ステップ１３０では、直前のステップ１２５で存在すると判定した対象の通過道路指定データに含まれるすべての過去の通過道路の位置（例えば位置ｃ）を、通過道路（すなわち、探索するルートが必ず通らなければならない道路上の一点）として設定する。なお、直前のステップ１２５で存在すると判定した対象の通過道路指定データに、複数の通過道路の位置が含まれている場合、それら複数の通過道路の位置を、通過道路として設定する。
【００２８】
ステップ１３０に続いては、ステップ１３５で、今回の現在地から今回の目的地までの最適なルートを探索する。ただし、この探索の際、直前のステップ１３０で設定した通過道路は、探索するルートが必ず通らなければならない道路上の一点であるとして、ルートを探索する。
【００２９】
したがって、ステップ１３０からステップ１３５に進んだ場合と、ステップ１２０またはステップ１２５からステップ１３０をバイパスしてステップ１３５に進んだ場合とでは、現在地（すなわち出発地）と目的地は同じである。しかし、前者の場合は、探索するルートが通過道路（道路上の一点）を必ず通らなければならないという追加条件が付いた上で探索が行われるのに対し、後者ではそのような追加条件が無い。したがって、多くの場合、算出されるルートは、前者の場合と後者の場合とで異なり、同じになることは希である。
【００３０】
また、前者の場合、過去に同じ出発地および同じ目的地のルート探索の際にユーザによって指定された通過道路が、今回は、ユーザによる指定を受けることなく、制御回路１７が自動的に、通過道路に設定している。したがって、ユーザの手を煩わせることなく、自動的に通過道路を設定することができる。
【００３１】
ステップ１３５に続くステップ１４０では、ルート探索の結果算出されたルートを表示装置１２に表示させる。
【００３２】
続いてステップ１４５では、通過道路の修正または追加の指示があったか否かを判定する。ユーザは、ステップ１４０で表示されたルートに対して、現在の通過道路を修正したり、通過道路を新たに追加したりしたい場合は、修正又は追加のための所定の操作を操作部１３に対して行う。このような操作があった場合、制御回路１７は、ステップ１４５で、通過道路の修正または追加の指示があったと判定し、ステップ１５０に進む。
【００３３】
また、ユーザは、ステップ１４０で表示されたルートが修正の必要なしと判断した場合は、想定のルート決定操作を操作部１３に対して行う。このような操作があった場合、制御回路１７は、ステップ１４５で、通過道路の修正または追加の指示がなかったと判定し、現在のルートを最終的なルートとして、図３の処理を終了する。この場合は、後に制御回路１７がルート案内処理を実行することで、当該ルートに沿った走行の案内を行う。
【００３４】
ステップ１５０では、通過道路の修正および追加のための処理を行う。具体的には、操作部１３に対するユーザの指定操作に従って、現在設定されている通過道路の位置を変更したり、通過道路の設定そのものを削除したり、新たな通過道路の設定を行ったりする。
【００３５】
ステップ１５０に続いては、ステップ１５５で、制御回路１７が今回取得した現在地と目的地の位置、および、ステップ１５０でユーザの指定操作によって変更または追加された通過道路の位置を、１組のレコードとして、外部メモリ１６中のバックアップデータに追加記録する。ただし、今回記録するレコードと同じ現在地および目的地を有するレコードが既にバックアップデータ中に存在する場合は、既にバックアップデータ中に存在する当該レコードを削除した上で、今回記録するレコードバックアップデータに追加記録する。
【００３６】
このように追加記録されたレコードは、後に上述の通りの処理内容で実行されるルート探索処理のステップ１１５〜１３０において、バックアップデータ中で過去の時点の現在地、目的地、および通過道路の組から成るレコードの１つとして使用される。
【００３７】
なお、ステップ１５０において、通過道路がすべて削除された場合は、ステップ１５５でバックアップデータに追加記録されるレコードは、現在地と目的地のみを含み、通過地点を含まないレコードとなる。
【００３８】
また、ステップ１５０において、最終的に通過道路が複数個設定された場合は、ステップ１５５でバックアップデータに追加記録されるレコードは、現在地と目的地に加え、複数個の通過地点を含むレコードとなる。
【００３９】
ステップ１５５に続いては、ステップ１３５に戻り、修正または追加後の通過道路を反映した上で、今回の現在地から今回の目的地までのルートの再探索を行う。ステップ１３５以降の処理は既に説明した通りである。
【００４０】
以上説明した通り、外部メモリ１６は、過去のある時点（ルート探索処理実行時点）に取得された過去の出発地、当該時点に指定された過去の目的地、および当該時点に指定された過去の通過道路の組のレコードを、１個または複数個記録している。
【００４１】
そして制御回路１７は、外部メモリ１６に記録されたレコード中に、今回の出発地（現在地）の所定の近傍にある過去の出発地および今回の目的地の所定の近傍にある過去の目的地を含む該当レコードがある場合、今回の出発地を出発し、該当レコードに含まれる過去の通過道路を通過し、今回の目的地に至るルート（第１ルートの一例に相当する）を算出する（ステップ１１５〜１４０）。
【００４２】
このように、車両用ナビゲーション装置１は、今回の出発地および今回の目的地を取得すると、その今回の出発地の近傍の過去の出発地および今回の目的地の近傍の過去の目的地を含む該当レコードが記録されていれば、その該当レコードに含まれる過去の通過道路を含んだ第１ルートを算出する。したがって、ユーザの手を煩わせることなく、自動的に通過道路を設定することができる。つまり、一度使用したいルートが探索できるよう探索した場合には、目的地を入力すれば前回と同じルートが簡単な操作で探索可能となる。
【００４３】
なお、本実施形態においては、「出発地の近傍」、「目的地の近傍」の一例として、「出発地と同一地点」、「出発地と同一地点」を採用している。
【００４４】
（第２実施形態）
次に、本発明の第２実施形態について説明する。本実施形態が第１実施形態と異なるのは、「出発地の近傍」、「目的地の近傍」の一例として、「出発地から所定距離以内」、「出発地から所定距離以内」を採用している点である。この所定距離は、例えば２００ｍでもよいし、３００ｍでもよいし、１ｋｍでもよい。
【００４５】
このような所定距離を採用することで、本実施形態の制御回路１７は、ルート探索処理において、図３の処理に代えて、図４に示す処理を実行する。図４の処理は、ステップ１２０の処理をステップ１２２に置き換えたことと、ステップ１５５の処理内容を一部変更したことのみである。
【００４６】
本実施形態の外部メモリ１６は、ステップ１１５に続いて、ステップ１２２に進み、読み出したバックアップデータ中の複数のレコード中に、該当レコードがあるか否か判定する。該当レコードは、ステップ１０５で取得した今回の現在地の周辺の位置の過去の現在地を含み、ステップ１１０で取得した今回の目的地の周辺の位置の過去の目的地を含むレコードである。
【００４７】
ここで、今回の現在地の周辺の位置とは、今回の現在地から上記所定距離以内にある位置をいう。したがって、今回の現在地と同じ位置が該当すると共に、今回の現在地と異なる位置だが上記所定距離以内にある位置も該当する。
【００４８】
また、今回の目的地の周辺の位置とは、今回の目的地から上記所定距離以内にある位置をいう。したがって、今回の目的地と同じ位置が該当すると共に、今回の目的地と異なる位置だが上記所定距離以内にある位置も該当する。
【００４９】
例えば、今回の現在地の位置から上記所定距離以内にａがあり、今回の目的地の位置から上記所定距離以内にｂがある場合、図２における１番目のレコードが該当レコードになる。該当レコードがあると判定した場合はステップ１２５に進む。該当レコードがないと判定した場合は、ステップ１２５、１３０をバイパスしてステップ１３５に進み、今回の現在地から今回の目的地までの最適なルートを探索する。この探索の際、通過道路は、設定しない。
【００５０】
また、ステップ１５５では、制御回路１７が今回取得した現在地と目的地の位置、および、ステップ１５０でユーザの指定操作によって変更または追加された通過道路の位置を、１組のレコードとして、外部メモリ１６中のバックアップデータに追加記録する。この点は、第１実施形態と同じである。
【００５１】
しかし、本実施形態では、今回記録するレコードと類似する現在地および目的地を有するレコードが既にバックアップデータ中に存在する場合は、既にバックアップデータ中に存在する当該レコードを削除した上で、今回記録するレコードバックアップデータに追加記録する。
【００５２】
ここで、レコード同士の類似について説明する。今回記録するレコードに含まれる現在地、目的地に対し、比較対象のレコードに含まれる現在地、目的地が、それぞれ、近傍にある場合に限り、今回記録するレコードと比較対象のレコードは類似であるとする。
【００５３】
より具体的には、今回記録するレコードに含まれる現在地から上記所定の距離以内に、比較対象のレコードに含まれる現在地があり、今回記録するレコードに含まれる目的地から上記所定の距離以内に、比較対象のレコードに含まれる目的地がある場合に限り、今回記録するレコードと比較対象のレコードは類似であるとする。
【００５４】
第１実施形態および本実施形態では出発地が現在地であるが、ユーザの認識としては同じ現在位置だとしても、位置座標としては異なる位置がある。例えば、駐車場の北端と南端が該当する。また、位置検出器１１の精度には誤差がある。したがって、本実施形態のように、ピンポイントで同じ位置ではなく、所定距離以内にある現在地同士については、共通のレコードを使用することで、過去の通過道路の設定記録を効率良く利用することができる。
【００５５】
また、目的地についても、表示装置１２に表示されたを地図スクロールさせた後、地図上の１点をタッチパネルで指定することで目的地を設定するような場合は、ユーザが同じ目的地を意図していたとしても、前回設定した目的地と若干の位置相違が発生する。したがって、本実施形態のように、ピンポイントで同じ位置ではなく、所定距離以内にある目的地同士については、共通のレコードを使用することで、過去の通過道路の設定記録を効率良く利用することができる。
【００５６】
このように、制御回路１７は、外部メモリ１６に記録されたレコード中に、今回の出発地（現在地）の所定の近傍（所定の距離以内）にある過去の出発地および今回の目的地の所定の近傍（所定の距離以内）にある過去の目的地を含む該当レコードがある場合、今回の出発地を出発し、該当レコードに含まれる過去の通過道路を通過し、今回の目的地に至るルート（第１ルートの一例に相当する）を算出する（ステップ１１５〜１４０）。
【００５７】
（第３実施形態）
次に、本発明の第３実施形態について説明する。本実施形態は、第２実施形態に対して、通過道路を自動的に追加した自動ルート（第１ルートの一例に相当する）と、通過道路を自動的に追加する前の単純ルート（第２ルートの一例に相当する）とを比較し、その比較結果を用いるよう変更したものである。
【００５８】
具体的には、本実施形態の制御回路１７は、ルート探索処理において、第２実施形態の図４の処理に代えて、図５の処理を実行するようになっている。図５の処理は、図４の処理に対して、ステップ１２６、１２７、１３１、１３２、１３３、１３４、１６０を追加し、ステップ１３５を削除したものである。
【００５９】
以下、ルート探索処理の変更部分について説明する。制御回路１７は、ステップ１２２で、バックアップデータ中の複数のレコード中に該当レコードがないと判定した場合、および、ステップ１２５で、該当レコード中に通過道路指定データが存在しないと判定した場合、ステップ１２６に進む。ステップ１２６では、今回の現在地から今回の目的地までの最適なルートを探索する。この探索の際、通過道路は、設定しない。このように、通過道路を設定しないまま今回の現在地から目的地まで算出されたルートを、単純ルートという。ステップ１２６に続いては、ステップ１４０に進み、ステップ１２６の探索の結果得た単純ルートを表示装置１２に表示させる。
【００６０】
また、制御回路１７は、ステップ１２５で該当レコード中に通過道路指定データが存在すると判定した場合、ステップ１２７に進み、ステップ１２６と同じ処理で、単純ルートを算出する。
【００６１】
続いてステップ１３０では、第１、第２実施形態と同じ処理を行う。すなわち、直前のステップ１２５で存在すると判定した対象の通過道路指定データに含まれるすべての過去の通過道路の位置を、通過道路として設定する。
【００６２】
ステップ１３０に続いては、ステップ１３１で、今回の現在地から今回の目的地までの最適なルートを探索する。ただし、この探索の際、直前のステップ１３０で設定した通過道路は、探索するルートが必ず通らなければならない道路上の一点であるとして、ルートを探索する。このように、ステップ１３０で自動的に追加した通過道路を用いて、今回の現在地から当該通過道路の地点を通過して今回の目的地まで算出されたルートを、自動ルートという。
【００６３】
ステップ１３１に続いては、ステップ１３２で、単純ルートと自動ルートのコストを比較することでコスト比を算出し、算出したコスト比が基準値Ｔ（例えば１．２）を超えるか否か判定する。
【００６４】
現在地（出発地）周辺や目的地周辺に通過道路指定が存在する場合、通過道路を設定した自動ルートを常に採用するのでは、ユーザの意図しない遠回りルートとなってしまうケースも考えられる。したがって、本実施形態では、単純ルートと自動ルートのどちらを使用するかを、両者のコストの比較に基づいて決定する。
【００６５】
具体的には、図６に示すように、今回の現在地と該当レコード中の過去の現在地とが同じ位置３１であり、今回の目的地３２から上記所定の距離内の範囲３３に、該当レコード中の過去の目的地３４が入っているとする。また、該当レコード中の過去の通過道路には、位置３５が含まれているとする。
【００６６】
この場合、現在地３１から過去の目的地３４へのルートとして位置３５を通過道路とすることに、ユーザとしては問題がなかったとしても、現在地３１から今回の目的地３２へのルートとして位置３５を通過道路とすることは、遠回り過ぎて問題となる可能性がある。
【００６７】
そこで、本実施形態では、ルート４１およびルート４２を繋ぐことで得られる単純ルート４１＋４２を、ルート４１および通過道路３５を通るルート４３を繋ぐことで得られる自動ルート４１＋４３と、コストで比較する。ここでいうコストの算出方法は、ルート探索処理において最適なルートであるか否かを判断するときに用いるコストと同じ算出方法を用いる。ルートのコストの算出方法については周知なので、ここではその具体例については説明しない。
【００６８】
より具体的には、単純ルートと自動ルートで共通の部分（すなわちルート４１）は除外し、互いに異なる部分のコストの比、すなわち、ルート４３のコストをルート４２のコストで除算した値を、コスト比とする。
【００６９】
そして、このコスト比が基準値Ｔ（例えば１．２）を超えたと判定すれば、ステップ１３３に進んで単純ルートを選択し、基準値Ｔ以下であると判定すれば、ステップ１３４に進んで自動ルートを選択する。
【００７０】
このように、単純ルートと自動ルートで共通の部分を除外してコスト比を算出するのは、現在地から目的地３２までの全ルートのコスト比を比較すると全長が長くなり、目的地３２周辺での遠回りルートの影響が反映されにくくなるからである。
【００７１】
ステップ１３３に続くステップ１４０では、選択した単純ルートの表示を行い、続くステップ１４５で通過道路の修正または追加の指示がなかったと判定した場合は、図５の処理が終了し、当該単純ルートがルート案内処理において案内される。
【００７２】
ステップ１３４に続くステップ１４０では、選択した自動ルートの表示を行い、続くステップ１４５で通過道路の修正または追加の指示がなかったと判定した場合は、図５の処理が終了し、当該自動ルートがルート案内処理において案内される。
【００７３】
また、制御回路１７は、ステップ１５５に続いて、ステップ１６０に進み、ステップ１５５で修正または追加された後の通過道路を反映した上で、今回の現在地から今回の目的地までのルートの再探索を行い、その後、ステップ１４０に戻る。
【００７４】
以上説明した通り、本実施形態の制御回路１７は、自動ルート４１＋４３を算出すると共に、今回の出発地を出発し、該当レコードに含まれる過去の通過道路を通過せず、今回の目的地に至る単純ルート４１＋４２を算出し、自動ルートと単純ルートのコストを比較し、比較の結果に基づいて、自動ルートと単純ルートのうち一方を選んでユーザに表示する。このようにすることで、ユーザの意図しない遠回りの自動ルートが選択されてしまう可能性が低減される。
【００７５】
なお、通過道路３５を通らない単純ルートが選択された場合でも、ユーザは、その後のステップ１４５で通過道路の修正または追加の指示操作を行い、ステップ１５０で、位置３５を通過道路として追加する旨の指示操作を操作部１３を用いて行えば、その後のステップ１６０で自動ルート４１＋４３の探索が行われ、この自動ルートがルート案内処理において案内される。
【００７６】
（第４実施形態）
次に、本発明の第４実施形態について説明する。本実施形態は、第１実施形態に対して、外部メモリ１６にバップアップデータが複数種類記録されるように変更したものである。
【００７７】
本実施形態の外部メモリ１６には、図７に示すように、有料道路優先、一般道路優先、推奨道路優先等のルート探索条件毎にバックアップデータが存在する。有料道路優先、一般道路優先、推奨道路優先等のルート探索条件については周知であるので、説明は省略する。
【００７８】
これらルート探索条件毎のバックアップデータには、１つまたは複数個のレコードが記録されるようになっている。各レコードは、過去のある時点で取得された過去の出発地（現在地）、当該時点において指定された過去の目的地、および当該時点において指定された過去の通過道路の組から成る。そして、あるルート探索条件に対応するバックアップデータに含まれるレコード、すなわち、当該ルート探索条件に関連付けられるレコードは、当該ルート探索条件でルートの探索が行われた時点の現在地、目的地、および通過道路の組から成る。
【００７９】
なお、図７に示すように、同じ現在地ａかつ同じ目的地ｂを有するレコードでも、それが関連付けられるルート探索条件に応じて、通過道路ｃ１、ｃ２、ｃ３が互いに異なる場合がある。これは、どの道路を優先的に使用するかがルート探索条件によって変化するからである。つまり、どの道路を優先的に使用するかによって、ユーザが経由したい地点も変化し得る。
【００８０】
また、本実施形態の制御回路１７は、このようなルート探索条件毎のバックアップデータを利用するために、ルート探索処理において、図３の処理に代えて、図８の処理を実行するようになっている。
【００８１】
図８の処理は、図３の処理に対して、ステップ１１５に代えてステップ１１４、１１６を設け、ステップ１５５に代えてステップ１５６を設けた点である。以下、図３の処理に対する変更部分について説明する。
【００８２】
制御回路１７は、ステップ１１０で目的地を取得した後、ステップ１１４で、操作部１３に対するユーザの探索条件指定操作に従って、ユーザが指定した探索条件（今回のルート探索条件）を１つ取得する。探索条件指定操作の方法としては、例えば、有料道路優先、一般道路優先、推奨道路優先という３つのボタンのうちいずれか１つをユーザが操作する方法がある。
【００８３】
ステップ１１４に続いては、ステップ１１６で、探索条件に対応するバックアップメモリの読み出しを行う。具体的には、ステップ１１４で取得した探索条件に対応するバックアップメモリを読み出す。ステップ１１６に続いては、ステップ１２０に進む。
【００８４】
このようになっていることで、ステップ１２０〜ステップ１５０では、使用するバックアップメモリは、ステップ１１４で取得した探索条件に対応するバックアップメモリに限定される。
【００８５】
したがって、制御回路１７は、今回の出発地（現在地）の所定の近傍にある過去の出発地および今回の目的地の所定の近傍にある過去の目的地を含む該当レコードが、今回のルート探索条件に合致する過去のルート探索条件に関連付けられて外部メモリ１６に記録されている場合、今回の出発地を出発し、該当レコードに含まれる過去の通過道路を通過し、今回の目的地に至るルート（第１のルートの一例に相当する）を、今回のルート探索条件に従って、算出する。
【００８６】
このように、出発地（現在地）、通過道路、目的地の記憶を、探索条件毎とすることにより、有料道路を積極的に使用したい場合や、時間にゆとりがあるため一般道を使用したい場合など、探索条件毎に個別に使用したいルートを設定できるため、利用範囲を広げることが出来る。
【００８７】
また、ステップ１５０に続いては、ステップ１５６で、ステップ１５５と同様に、制御回路１７が今回取得した現在地と目的地の位置、および、ステップ１５０でユーザの指定操作によって変更または追加された通過道路の位置を、１組のレコードとして、外部メモリ１６中のバックアップデータに追加記録する。ただし、記録先のバックアップデータは、ステップ１１４で取得した探索条件に対応するバックアップメモリである。
【００８８】
このように追加記録されたレコードは、後に上述の通りの処理内容で実行されるルート探索処理のステップ１１５〜１３０において、バックアップデータ中で過去の時点の現在地、目的地、および通過道路の組から成るレコードの１つとして使用される。
【００８９】
なお、上記各実施形態において、制御回路１７が、ステップ１０５、１１０、１１４を実行することで取得手段の一例として機能し、１１５〜１４０を実行することでルート探索手段の一例として機能する。
【００９０】
また、上記実施形態で「通過道路」としている対象は、道路上の一地点に該当するので、通過地点という用語で表現することも可能である。
【００９１】
（他の実施形態）
なお、本発明は上記した実施形態に限定されるものではなく、特許請求の範囲に記載した範囲内において適宜変更が可能である。また、上記各実施形態は、互いに無関係なものではなく、組み合わせが明らかに不可な場合を除き、適宜組み合わせが可能である。また、上記各実施形態において、実施形態を構成する要素は、特に必須であると明示した場合および原理的に明らかに必須であると考えられる場合等を除き、必ずしも必須のものではないことは言うまでもない。また、上記各実施形態において、実施形態の構成要素の個数、数値、量、範囲等の数値が言及されている場合、特に必須であると明示した場合および原理的に明らかに特定の数に限定される場合等を除き、その特定の数に限定されるものではない。また、上記各実施形態において、構成要素等の形状、位置関係等に言及するときは、特に明示した場合および原理的に特定の形状、位置関係等に限定される場合等を除き、その形状、位置関係等に限定されるものではない。例えば、以下のような変形例も許容される。なお、以下の変形例は、それぞれ独立に、上記実施形態に適用および不適用を選択できる。すなわち、以下の変形例のうち任意の組み合わせを、上記実施形態に適用することができる。
【００９２】
（変形例１）
上記第１〜第３実施形態の制御回路１７は、ルート探索処理において、１つのルートを算出するために目的地は１つのみを取得するようになっている。しかし制御回路１７は、ルート探索処理において、１つのルートを算出するために目的地を複数個取得するようになっていてもよい。
【００９３】
例えば、ユーザが、操作部１３を用いて第１目的地、第２目的地、第３目的地という３つの目的地を指定した場合について説明する。この場合制御回路１７は、まず、ルート探索処理において、現在地から第１目的地までのルートは、第１目的地を上記各実施形態の目的地とみなして上記各実施形態と同じ方法でルート探索を行う。次に、第１目的地から第２目的地までのルートは、第１目的地および第２目的地をそれぞれ上記各実施形態の現在地および目的地とみなして上記各実施形態と同じ方法でルート探索を行う。次に、第２目的地から第３目的地（最終目的地）までのルートは、第２目的地および第３目的地をそれぞれ上記各実施形態の現在地および目的地とみなして上記各実施形態と同じ方法でルート探索を行う。そして、これらのルート探索によって算出した全ルートを繋ぎ合わせることで、ルート案内処理によって案内されるルートを作成する。
【００９４】
より具体的には、まず、図３、図４、図５、図８のステップ１１０において第１目的地を今回の目的地として取得し、上記各図の処理を終了するまで行う。次に、上記各図のステップ１０５、１１０において、第１目的地および第２目的地をそれぞれ今回の現在地および今回の目的地として取得し、各図の処理を終了するまで行う。次に、上記各図のステップ１０５、１１０において、第２目的地および第３目的地をそれぞれ今回の現在地および今回の目的地として取得し、各図の処理を終了するまで行う。その後、上記処理によって算出した全ルートを繋ぎ合わせることで、ルート案内処理によって案内されるルートを作成する。
【００９５】
このようにすることで、例えば、第１目的地および第２目的地をそれぞれ過去の現在地および目的地として含むレコードがバックアップデータ中にあれば、第１目的地を出発地とし、当該レコード中の過去の通過道路（地点）を通過し、第２目的地を目的地とするルート探索が行われる。その結果、最終的に繋ぎ合わされたルートは、現在地を出発地とし、第１目的地、当該レコード中の過去の通過道路、第２目的地を通過し、第３目的地に至るルートとなる。
【００９６】
（変形例２）
上記第４実施形態は、第１実施形態に対する変形として実現しているが、第２実施形態、第３実施形態に対する変形としてもよい。また、上記第３実施形態は、第２実施形態に対する変形として実現しているが、第１実施形態に対する変形としてもよい。
【００９７】
（変形例３）
上記実施形態では、上記ルート探索処理を実行する車両用ナビゲーション装置１は、車両に搭載された装置である。しかし、ルート探索処理を実行する装置は、車両に搭載されない装置であってもよい。
【００９８】
例えば、ユーザが携帯する携帯端末が所定のプログラムを実行することでルート探索処理を実行してもよいし、インターネット等の広域ネットワークを介してユーザ端末と通信可能なサーバが所定のプログラムを実行することでルート探索処理を実行するようになっていてもよい。後者の場合、上記実施形態の「現在地」は、ユーザ端末を用いてユーザが指定して広域ネットワークを介してサーバが取得した「出発地」に置き換えてもよい。
【符号の説明】
【００９９】
１            車両用ナビゲーション装置
１６          外部メモリ
１７          制御回路
【図１】
2015169611.tif 000003
【図２】
2015169611.tif 000004
【図３】
2015169611.tif 000005
【図４】
2015169611.tif 000006
【図５】
2015169611.tif 000007
【図６】
2015169611.tif 000008
【図７】
2015169611.tif 000009
【図８】
2015169611.tif 000010