計算機システム及び経路案内方法
【課題】利用者が事前に運転の計画を細部まで立案しなくても、運転の計画を細部まで立案した場合と同様の案内機能を提供する経路案内方法を提供することを目的とする。
【解決手段】出発地から目的地までの経路を利用者に案内するナビゲーション装置及びナビゲーション装置が経路を案内するために用いる案内計画情報を生成する案内計画生成装置を備える計算機システムにおける経路案内方法において、案内計画生成装置は、ナビゲーション装置の移動範囲に存在する経由候補地点、及び各経由候補地点の判定情報を含む案内計画情報を生成し、ナビゲーション装置は、ナビゲーション装置の現在位置から所定の範囲内に存在する経由候補地点の判定情報が現在時刻に対応する経由候補地点、及び現在位置から当該経由候補地点までの経路を利用者に提示する。
【解決手段】出発地から目的地までの経路を利用者に案内するナビゲーション装置及びナビゲーション装置が経路を案内するために用いる案内計画情報を生成する案内計画生成装置を備える計算機システムにおける経路案内方法において、案内計画生成装置は、ナビゲーション装置の移動範囲に存在する経由候補地点、及び各経由候補地点の判定情報を含む案内計画情報を生成し、ナビゲーション装置は、ナビゲーション装置の現在位置から所定の範囲内に存在する経由候補地点の判定情報が現在時刻に対応する経由候補地点、及び現在位置から当該経由候補地点までの経路を利用者に提示する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出発地から目的地までの経路を案内する経路案内方法に関し、特に、ナビゲーション装置が他の装置で生成された案内計画情報に基づいて経路を案内する経路案内方法に関する。
【背景技術】
【０００２】
自動車に搭載されて、目的地までの経路を案内するナビゲーションシステムが知られている。ナビゲーションシステムは、ＧＰＳ（Global Positioning System）衛星の電波を受信するＧＰＳ受信機及び車速センサ等を備え、ＧＰＳ受信機及び車速センサ等によって自動車の現在位置を特定する。
【０００３】
これによって、ナビゲーションシステムは、利用者によって設定された目的地までの経路等を利用者に提示できる。しかし、ナビゲーションシステムは、自動車に搭載されるために小型化されている。このため、利用者がナビゲーションシステムを操作しづらいという問題点があった。したがって、利用者が目的地又は経路等を事前に計画しても、計画した内容をナビゲーションシステムに入力することは利用者にとって困難であった。
【０００４】
この問題を解決するために、利用者が自動車に搭乗する前に運転の計画を立案することを支援する運転計画システムが知られている。利用者が自宅等で地図データ等を参照して運転の計画を運転計画システムに入力すると、運転計画システムは、入力された運転の計画を自動車に搭載されたナビゲーションシステムに転送する。
【０００５】
これによって、利用者は、ナビゲーションシステムをあまり操作することなく、ナビゲーションシステムに運転の計画を設定できる。
【０００６】
しかしながら、この運転計画システムでは、利用者が自動車に搭乗する前に運転の計画を細部まで立案しなければならない。このため、事前に運転の計画を立案することが煩わしいと感じる利用者にとって、この運転計画システムは、必ずしも有用でない。
【０００７】
また、事前に立案された運転の計画では予期しえない事態（渋滞又は店舗の休業等）が発生した場合には、利用者は、ナビゲーションシステムを操作して、立案された運転の計画を変更しなければならない。
【０００８】
そこで、運転の計画を柔軟に変更できるナビゲーション装置として、ナビゲーション装置が搭載された自動車の進行方向前方に存在する地点情報を次々と提示することによって運転中に目的地までの経路を変更できるナビゲーション装置が知られている（特許文献１参照）。また、曖昧な目的地をナビゲーション装置に設定して、曖昧な目的地が設定されたままナビゲーション装置が搭載された自動車が走行すると徐々に目的地を具体化するナビゲーション装置も知られている（特許文献２参照）。
【特許文献１】特開２００７―２８５８８３号公報
【特許文献２】特開２００７―２８５８７０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１及び特許文献２に記載されたナビゲーション装置において、運転の計画が頻繁に変更されると、事前に立案された運転の計画を利用できる区間が短くなってしまい、事前に立案された運転の計画がほとんど利用できなくなってしまう。
【００１０】
本発明は上記した問題を解決するためになされたものであり、利用者が事前に運転の計画を細部まで立案しなくても、運転の計画を細部まで立案した場合と同様の案内機能を提供する経路案内方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の代表的な一例を示せば、以下の通りである。出発地から目的地までの経路を利用者に案内するナビゲーション装置、及び利用者が立ち寄る候補となる経由候補地点を前記ナビゲーション装置が提示するために用いる案内計画情報を生成する案内計画生成装置を備える計算機システムにおいて、前記案内計画生成装置は、前記経由候補地点に関する情報を記憶し、前記ナビゲーション装置の移動範囲を算出し、前記経由候補地点に関する情報を参照し、前記算出された移動範囲に存在する経由候補地点を選択し、前記ナビゲーション装置が、前記選択された経由候補地点を利用者に提示するか否かを現在時刻に基づいて判定するための判定情報を生成し、前記移動範囲に存在する経由候補地点、及び前記各経由候補地点の判定情報を含む前記案内計画情報を生成し、前記ナビゲーション装置は、前記案内計画生成装置によって生成された案内計画情報を取得し、前記取得された案内計画情報に含まれる経由候補地点のうち、前記ナビゲーション装置の現在位置から所定の範囲内に存在する経由候補地点を、提示し得る経由候補地点として選択し、前記選択された提示し得る経由候補地点の判定情報が、現在時刻に適合する経由候補地点を、提示経由候補地点として取得し、前記取得された提示経由候補地点、及び前記現在位置から前記提示経由候補地点までの経路を利用者に提示することを特徴とする。
【発明の効果】
【００１２】
本発明の一形態によると、利用者は、案内計画生成装置によって生成された案内計画情報に基づいて、移動時に案内計画を柔軟に変更できる。
【発明を実施するための最良の形態】
【００１３】
本発明の実施形態を、図１〜図３を用いて説明する。
【００１４】
図１は、本発明の実施形態の運転計画立案システムの構成を示すブロック図である。
【００１５】
運転計画立案システムは、運転計画立案支援装置１００及びナビゲーション装置１２０を備える。ナビゲーション装置１２０は、出発地から目的地までの経路等を案内する装置である。運転計画立案支援装置１００は、利用者が立ち寄る候補となる経由候補地点を事前に運転計画情報（案内計画情報）を立案することを支援するための装置である。
【００１６】
運転計画立案支援装置１００は、動作制御部１０１、入力受付部１０２、地図データ記憶部１０３、利用者情報記憶部１０４、通信部１０５、外部記憶媒体出力部１０６、及び外部通信部１０７を備える。
【００１７】
動作制御部１０１は、図示しないＣＰＵ及びメモリ等から構成され、運転計画立案支援装置１００の動作の制御を司る。
【００１８】
入力受付部１０２は、利用者が図示しないディスプレイ等に表示された情報（例えば、地図データ等）を参照して、運転計画概要（出発日時、出発地方、目的地方、及び運転の目的等）の入力を受け付ける。また、出発地方及び目的地方は、出発地点又は目的地点を含む大まかな地方である。例えば、出発地方及び目的地方は、都道府県単位又は市町村単位である。
【００１９】
経路設定受付部１１３は、入力受付部１０２によって受け付けられた運転計画概要から出発地点及び目的地点を設定し、設定された出発地点から目的地点までの経路を設定する。
【００２０】
地図データ記憶部１０３は、例えば店舗等の地点情報を記憶するＤＶＤ、フラッシュメモリ又はＨＤＤ（Hard Disk Drive）等の記憶媒体である。利用者情報記憶部１０４は、利用者が過去に入力した運転計画概要等の利用情報を書き込み可能なフラッシュメモリ又はＨＤＤ等の記憶媒体である。
【００２１】
通信部１０５は、運転計画立案支援装置１００をネットワーク１３３を介してナビゲーション装置１２０に接続するためのインタフェースである。外部記憶媒体出力部１０６は、生成された運転計画情報を外部記憶媒体１１２に出力するためのインタフェースである。
【００２２】
外部通信部１０７は、運転計画立案支援装置１００の外部に存在する情報源（サーバ等）に、運転計画立案支援装置１００を接続するためのインタフェースである。
【００２３】
動作制御部１０１は、地点情報準備範囲策定部１０８、地点候補選択部１０９、経路候補選択部１１０、及び運転計画情報生成部１１１を備える。
【００２４】
地点情報準備範囲策定部１０８は、経路設定受付部１１３によって設定された経路から利用者が移動可能な範囲に存在するすべての経路を取得する。
【００２５】
地点候補選択部１０９は、外部通信部１０７を介して接続される情報源又は地図データ記憶部１０３に記憶された地点情報を参照し、地点情報準備範囲策定部１０８によって取得された走行可能な範囲の経路に関連する地点情報を選択する。そして、地点候補選択部１０９は、利用者情報記憶部１０４に記憶された利用者情報を参照し、選択された走行可能な範囲の経路に関連する地点情報から、利用者との関連度の高い地点情報を地点候補として選択する。
【００２６】
経路候補選択部１１０は、出発地点から、地点候補選択部１０９によって選択された地点情報を通って、目的地点までの経路を選択する。なお、運転計画立案支援装置１００は、経路候補選択部１１０を備えなくてもよい。
【００２７】
運転計画情報生成部１１１は、地点候補選択部１０９によって選択された地点情報と、地点情報準備範囲策定部１０８によって取得された経路とを紐付けて、紐付けた運転計画情報（案内計画情報）を、外部記憶媒体１１２又は通信部１０５を介してナビゲーション装置１２０に入力可能な形式に変換する。
【００２８】
なお、動作制御部１０１が備える構成は、ＣＰＵが所定のプログラムを実行することによって実現されるが、他の方法（例えば、ハードウェア）によって実装されてもよい。
【００２９】
なお、通信部１０５及び外部記憶媒体出力部１０６は運転計画情報をナビゲーション装置１２０に入力するための手段であるが、運転計画立案支援装置１００は、通信部１０５及び外部記憶媒体出力部１０６の両方を備える必要はなく、少なくとも一方を備えていればよい。
【００３０】
次に、ナビゲーション装置１２０について説明する。
【００３１】
ナビゲーション装置１２０は、動作制御部１２１、地図データ記憶部１２２、現在位置取得部１２３、入力受付部１２４、画像表示部１２５、音声出力部１２６、及び外部記憶媒体読取部１２７を備える。
【００３２】
動作制御部１２１は、図示しないＣＰＵ及びメモリ等から構成され、ナビゲーション装置１２０の動作の制御を司る。地図データ記憶部１２２は、地図データを記憶するＤＶＤ、フラッシュメモリ又はＨＤＤ（Hard Disk Drive）等の記憶媒体である。現在位置取得部１２３は、ナビゲーション装置１２０が搭載された自動車の現在位置を取得する。
【００３３】
入力受付部１２４は、ナビゲーション装置１２０に備わる画像表示部１２５に設けられたタッチパネル又はナビゲーション装置１２０に備わるスイッチ等から利用者の指示の入力を受け付けるインタフェースである。画像表示部１２５は、画像を表示可能なディスプレイ等である。音声出力部１２６は、音声を出力可能なスピーカ等である。
【００３４】
外部記憶媒体読取部１２７は、外部記憶媒体１１２に接続可能であって、外部記憶媒体１１２に記憶された情報を読み取る。通信部１２８は、ナビゲーション装置１２０をネットワーク１３３を介して運転計画立案支援装置１００に接続するためのインタフェースである。
【００３５】
動作制御部１２１は、状況判定部１２９、経路探索部１３０、計画策定部１３１、及び提示情報制御部１３２を備える。
【００３６】
状況判定部１２９は、現在位置及び現在日時等の現在の状況を特定する。経路探索部１３０は、二つの地点間の経路を予め設定された基準に基づいて選択する。予め設定された基準には、例えば、最も到着時間の短い経路を選択する「最速」基準、最も距離が短い経路を選択する「最短」基準、又は最も経費が安くすむ経路を選択「最安」基準がある。
【００３７】
計画策定部１３１は、状況判定部１２９によって特定された現在の状況に一致する地点情報を選択する。提示情報制御部１３２は、経路探索部１３０によって選択された経路及び計画策定部１３１によって地点情報等の画像又は音声を、画像表示部１２５又は音声出力部１２６に出力する。
【００３８】
なお、動作制御部１２１が備える構成は、ＣＰＵが所定のプログラムを実行することによって実現されるが、他の方法（例えば、ハードウェア）によって実装されてもよい。
【００３９】
なお、通信部１２８及び外部記憶媒体読取部１２７は運転計画情報をナビゲーション装置１２０に入力するための手段であるが、ナビゲーション装置１２０は、通信部１２８及び外部記憶媒体読取部１２７の両方を備える必要はなく、少なくとも一方を備えていればよい。
【００４０】
図２は、本発明の実施形態の運転計画立案システムによって実行される処理の説明図である。
【００４１】
まず、利用者は、ナビゲーション装置１２０が搭載される自動車の外（例えば、自宅又は店舗等）にある運転計画立案支援装置１００に備わる入力受付部１０２に対して、運転計画の概要を入力する。運転計画概要は、例えば、出発日時、出発地方、目的地方、及び目的等を含む。
【００４２】
経路設定受付部１１３は、入力された運転計画概要に含まれる出発地方及び目的地方から仮想的な出発地点及び仮想的な目的地点を特定する。そして、経路設定受付部１１３は、特定された仮想的な出発地点から仮想的な目的地点までの経路を設定する。
【００４３】
地点情報準備範囲策定部１０８は、特定された経路から所定の範囲にあるすべての経路を取得し、利用者が走行可能な範囲を特定する。
【００４４】
地点候補選択部１０９は、地図データ記憶部１０３に記憶された地点情報のうち、地点情報準備範囲策定部１０８によって特定された走行可能範囲に位置する地点情報を、運転計画に必要な地点情報の候補として、選択する。
【００４５】
経路候補選択部１１０は、仮想的な出発地点から、地点候補選択部１０９によって選択された地点情報を通って、仮想的な目的地点までのすべての経路を、運転計画に必要な経路の候補として、選択する。
【００４６】
そして、地点候補選択部１０９及び経路候補選択部１１０は、地点情報の候補及び経路の候補を運転計画情報生成部１１１に出力する。
【００４７】
運転計画情報生成部１１１は、地点情報の候補及び経路の候補を紐付けて、運転計画情報を生成する。そして、運転計画情報生成部１１１は、生成した運転計画情報を外部記憶媒体出力部１０６を介して、外部記憶媒体１１２に出力し、生成した運転計画情報を外部記憶媒体１１２に記憶させる。
【００４８】
外部記憶媒体１１２に記憶された運転計画情報には、利用者によって入力された運転計画概要、地点候補選択部１０９によって選択された地点情報、経路候補選択部１１０によって選択された経路、地点候補選択部１０９によって選択された地点情報の詳細情報、及び利用者が過去に確認した地点情報等から生成される利用者特徴情報等が含まれる。
【００４９】
利用者は、運転計画情報が記憶された外部記憶媒体１１２を持ち運び、外部記憶媒体１１２を、ナビゲーション装置１２０に備わる外部記憶媒体読取部１２７に接続する。動作制御部１２１は、外部記憶媒体読取部１２７に接続された外部記憶媒体１１２に記憶された運転計画情報を読み取るので、ナビゲーション装置１２０は、運転計画情報を利用可能になる。
【００５０】
なお、動作制御部１２１は、利用者に外部記憶媒体１１２に記憶された運転計画情報を読み取ってもよいか否かを確認してから、外部記憶媒体１１２に記憶された運転計画情報を読み取ってもよい。また、動作制御部１２１は、外部記憶媒体１１２が外部記憶媒体読取部１２７に接続されたことを検出した場合に、外部記憶媒体１１２に記憶された運転計画情報を読み取ってもよい。
【００５１】
計画策定部１３１は、読み取られた運転計画情報を利用して、提示すべき地点情報を選択する。具体的には、計画策定部１３１は、運転計画情報に含まれる地点情報のうち、状況判定部１２９によって取得される現在の状況を示す状況コードに対応する地点情報を、利用者に提示する地点情報として、選択する。
【００５２】
次に、計画策定部１３１は、現在位置から選択された利用者に提示する地点情報が示す地点までの経路を経路探索部１３０に探索させて、経路探索部１３０が探索した経路を取得する。
【００５３】
そして、計画策定部１３１は、利用者に提示する地点情報として選択された地点情報と、経路探索部１３０によって探索された経路とを組み合わせることによって、利用者に提示する情報を生成し、生成された利用者に提示する情報を提示情報制御部１３２に出力する。
【００５４】
提示情報制御部１３２は、入力された利用者に提示する情報を提示するのに適したタイミングで、利用者に提示する情報を画像表示部１２５に表示することによって、利用者に提示する。
【００５５】
これによって、利用者は、現在の状況で到達できる地点の情報を確認することができ、事前に立案した運転計画が細部まで立案されていない場合であっても、事前に立案した運転計画が細部まで立案された場合と同じくらい詳細な運転計画を利用できる。
【００５６】
なお、ナビゲーション装置１２０は、公知の道案内機能を備えてもよい。この場合、ナビゲーション装置１２０は、運転計画情報が入力されていない場合、公知の道案内機能で動作し、運転計画情報が入力された場合、本発明の運転計画情報に基づく道案内を動作する。これによって、利用者が運転計画を事前に立案していない場合であっても、ナビゲーション装置１２０は、公知の道案内機能を利用者に提供できる。
【００５７】
なお、ナビゲーション装置１２０は、公知の道案内機能で運転計画情報を利用してもよい。これによって、ナビゲーション装置１２０は、ナビゲーション装置１２０が保持する地点情報だけでなく、運転計画立案支援装置１００が保持する地点情報も利用者に提供できる。
【００５８】
図３は、本発明の実施形態の運転計画立案支援システムに備わる各装置の処理のフローチャートである。運転計画立案支援装置１００は、利用者から運転計画概要の入力を受け付けた場合に、運転計画情報を生成する処理を実行する。
【００５９】
まず、入力受付部１０２は、利用者の操作によって入力された運転計画概要の入力を受け付ける（３００１）。運転計画概要は、出発地方、目的地方、出発日時、及び目的を含む。運転計画概要は、運転計画に関する情報であって、出発地点及び目的地点が指定される具体的な運転計画でなくてもよい。
【００６０】
次に、経路設定受付部１１３は、入力された運転計画概要に含まれる出発地方及び目的地方から仮想的な出発地点及び仮想的な目的地点を特定し、特定された仮想的な出発地点から仮想的な目的地点までの経路を探索し、探索された経路を代表経路に設定する（３００２）。
【００６１】
具体的には、地方ごとに中心地点又は代表地点が予め設定されており、経路設定受付部１１３は、入力された出発地方及び目的地方に対応する中心地点又は代表地点を特定し、特定された出発地方及び目的地方に対応する中心地点又は代表地点を、仮想的な出発地点及び仮想的な目的地点とする。
【００６２】
なお、入力された運転計画概要に出発地方が含まれない場合には、経路設定受付部１１３は、予め設定されている利用者の自宅の住所を仮想的な出発地点としてもよい。
【００６３】
次に、地点情報準備範囲策定部１０８は、ナビゲーション装置１２０を搭載する自動車がステップ３００２の処理で設定された代表経路から外れて走行し得る範囲を推定する（３００３）。
【００６４】
具体的には、地点情報準備範囲策定部１０８は、仮想的な出発地点から仮想的な目的地点までのあらゆる経路を探索して、探索された経路を走行範囲としてもよいし、代表経路から所定の範囲を走行範囲としてもよい。走行範囲の推定方法は、代表経路から極端に遠方の地点を含まなければ、如何なる方法を用いてもよい。
【００６５】
次に、経路候補選択部１１０は、仮想的な出発地点から仮想的な目的地点までのすべての経路のうち、ステップ３００３の処理で推定された走行範囲内に存在する経路を、走行経路候補として選択する（３００４）。
【００６６】
次に、地点候補選択部１０９は、走行範囲に存在する地点情報を、ナビゲーション装置１２０が経由可能な地点情報候補として選択する（３００５）。
【００６７】
次に、運転計画情報生成部１１１は、ステップ３００４の処理で選択された走行経路候補及びステップ３００５の処理で選択された地点情報候補に、分類コードを付与し、ナビゲーション装置１２０が利用しやすい形式に変換することによって、運転計画情報を生成する（３００６）。
【００６８】
そして、運転計画立案支援装置１００は、ステップ３００６の処理で生成された運転計画情報を外部記憶媒体出力部１０６から外部記憶媒体１１２に出力する（３００７）。
【００６９】
利用者が運転計画情報を記憶した外部記憶媒体１１２を持ち運び、ナビゲーション装置１２０に外部記憶媒体１１２を接続することによって、ナビゲーション装置１２０が運転計画情報を利用できる。
【００７０】
利用者が外部記憶媒体１１２を外部記憶媒体読取部１２７に接続すると、ナビゲーション装置１２０は、外部記憶媒体１１２に記憶された運転計画情報を読み取る（３００８）。そして、ナビゲーション装置１２０は、読み取った運転計画情報に含まれる代表経路に基づいて、経路の案内を開始する。また、ナビゲーション装置１２０は、経路の案内を開始するとともに、運転計画情報に含まれる地点情報候補の情報を提示する。
【００７１】
状況判定部１２９は、ナビゲーション装置１２０を搭載した自動車の現在位置、及び現在の時刻等を取得し、取得された現在位置及び現在の時刻等から、現在の状況を示す状況コードを算出する（３００９）。
【００７２】
次に、計画策定部１３１は、ステップ３００９の処理で算出された状況コードから、利用者が現在必要とする情報の種別を選択し、選択した種別を示す種別コードを取得する。そして、計画策定部１３１は、運転計画情報に含まれる走行経路候補及び地点情報候補のうち、取得された種別コードに対応する分類コードが付与された走行経路候補及び地点情報候補（経由地）を選択する（３０１０）。
【００７３】
なお、計画策定部１３１が種別コードを取得する方法としては、状況コードと種別コードとが予め対応付けられ、計画策定部１３１は、ステップ３００９の処理で算出された状況コードに対応付けられた種別コードを取得する方法がある。また、状況コードから種別コードが特定できれば、如何なる方法を用いてもよい。
【００７４】
次に、経路探索部１３０は、ナビゲーション装置１２０を搭載した自動車が現在走行している経路から、ステップ３０１０の処理で選択された走行経路候補及び地点情報候補（経由地）を経由する経路を探索する（３０１１）。
【００７５】
具体的には、走行経路候補を経由する経路を探索する場合には、経路探索部１３０は、現在位置から走行経路候補である経路の始点までの経路を探索する。また、地点情報候補を経由する経路を探索する場合には、経路探索部１３０は、現在位置から地点情報候補である地点情報までの経路を探索する。
【００７６】
次に、計画策定部１３１は、ステップ３０１０の処理で選択された経由地及びステップ３０１１の処理で探索された経由地を経由する経路を運転計画候補とし、運転計画候補の特徴を示す運転計画詳細情報を生成する（３０１２）。
【００７７】
運転計画候補の特徴は、利用者が運転計画を変更するか否かを判定するための情報であり、例えば、各経由地までの所要時間、距離、費用、又は経由地の地点情報等を含む。
【００７８】
なお、運転計画詳細情報は、すべての経由地に対して生成される必要はなく、現在位置から必要となり得る経由地に対してのみ生成されるようにしてもよい。例えば、計画策定部１３１は、現在位置の次の交差点から侵入できる経路上にある経由地に対して、運転計画詳細情報を生成する。
【００７９】
これによって、ナビゲーション装置１２０の処理負荷を軽減でき、運転計画詳細情報を生成する処理に要する時間を短縮できる。
【００８０】
次に、提示情報制御部１３２は、運転計画詳細情報及び運転計画詳細情報を生成した経由地へ進入するための進入経路を画像表示部１２５等に提示して、運転計画が変更可能であることを通知する（３０１３）。
【００８１】
次に、計画策定部１３１は、現在位置を取得し、取得された現在位置が進入経路上にあるか否かを判定することによって、進路変更があったか否かを判定する（３０１４）。
【００８２】
ステップ３０１４の処理で、現在位置が進入経路上にあると判定された場合、つまり進路変更があったと判定された場合、計画策定部１３１は、運転計画の変更を受け付け、変更された運転計画に基づく案内を開始するためにステップ３００９の処理に戻る。
【００８３】
一方、ステップ３０１４の処理で、現在位置が進入経路上にないと判定された場合、つまり進路変更がないと判定された場合、ステップ３００９の処理に戻る。
【００８４】
以上の処理が繰り返し実行されることによって、利用者は運転計画を随時変更できる。
【００８５】
したがって、利用者が運転計画立案支援装置１００を介して立案した運転計画が曖昧であっても、運転計画立案支援装置１００は、ナビゲーション装置１２０を搭載した自動車の位置する地点で発生し得るあらゆる状況に対応できる情報を準備できる。
【００８６】
また、ナビゲーション装置１２０は、運転計画詳細情報を利用者に提示するため、利用者は十分な判断材料に基づいて、運転計画を変更するか否かを判定できる。
【００８７】
（第１実施例）
次に、本発明の第１実施例を図４〜図１６を用いて説明する。実施例１の運転計画立案システムは、運転計画立案支援装置１００によって生成された運転計画情報は、外部記憶媒体１１２を介してナビゲーション装置１２０に転送されるシステムである。
【００８８】
図４は、本発明の第１実施例の運転計画立案システムのブロック図である。
【００８９】
運転計画立案システムは、運転計画立案支援装置１００及びナビゲーション装置１２０を備える。
【００９０】
まず、運転計画立案支援装置１００について説明する。
【００９１】
運転計画立案支援装置１００は、入力装置４０１、出力装置４０２、記憶装置４０３、ＣＰＵ４０５、メモリ４０６、及び外部インタフェース（Ｉ／Ｆ）４０７を備える。
【００９２】
入力装置４０１は、例えば、マウス及びキーボード等であり、出力装置４０２は、例えば、ディスプレイである。利用者は、出力装置４０２に表示された表示内容を見て、入力装置４０１を介して、運転計画の概要を運転計画立案支援装置１００に入力する。よって、入力受付部１０２は、入力装置４０１及び出力装置４０２から構成される。
【００９３】
記憶装置４０３には、地図データ及び利用者情報が記憶される。よって、記憶装置４０３は、地図データ記憶部１０３及び利用者情報記憶部１０４の機能を備える。
【００９４】
なお、本実施例では、一台の記憶装置４０３が地図データ記憶部１０３及び利用者情報記憶部１０４の機能を備えるとしたが、複数台の記憶装置４０３が地図データ記憶部１０３及び利用者情報記憶部１０４の機能を備えてもよい。これによって、利用者が変わる場合に、利用者情報記憶部１０４の機能を備える記憶装置４０３のみを交換すればよい。
【００９５】
なお、利用者情報記憶部１０４の機能を備える記憶装置４０３は、書き込み可能な記憶装置（例えば、ＨＤＤ等）でなければならない。一方、地図データ記憶部１０３の機能を備える記憶装置４０３は、読み出ししか必要ないので、書き込み不可能な記憶装置（例えば、ＤＶＤドライブ）であってもよい。
【００９６】
メモリ４０６には、動作制御部１０１を構成する地点情報準備範囲策定部１０８、地点候補選択部１０９、経路候補選択部１１０、運転計画情報生成部１１１、及び経路設定受付部１１３の機能を実現する各種プログラムが記憶される。ＣＰＵ４０５は、メモリ４０６に記憶された各種プログラムを実行する。よって、ＣＰＵ４０５及びメモリ４０６は、動作制御部１０１の機能を備える。
【００９７】
外部Ｉ／Ｆ４０７は、外部記憶媒体１１２に接続可能なインタフェース（例えば、ＵＳＢポート）であり、外部記憶媒体出力部１０６の機能を備える。
【００９８】
なお、外部記憶媒体出力部１０６は、外部記憶媒体１１２に接続可能な外部Ｉ／Ｆ４０７によって実現されるとしたが、外部記憶媒体出力部１０６は、ＣＤ−Ｒ等の外部記憶媒体１１２にデータを直接書き込み可能な装置によっても実現できる。また、外部記憶媒体出力部１０６は、運転計画立案支援装置１００が外部記憶媒体１１２に書き込み可能な装置に接続されることによっても実現できる。
【００９９】
このように、外部記憶媒体出力部１０６は、ナビゲーション装置１２０が読み取り可能な形式で情報を出力可能であれば、どのような方法で実現してもよい。
【０１００】
次に、ナビゲーション装置１２０について説明する。第１実施例のナビゲーション装置１２０は、自動車に搭載される計算機である。
【０１０１】
ナビゲーション装置１２０は、ＣＰＵ４１１、メモリ４１２、外部インタフェース（Ｉ／Ｆ）４１３、入力装置４１４、表示装置４１５、スピーカ４１６、記憶装置４１７、及びＧＰＳ受信機４１８を備える。
【０１０２】
入力装置４１４は、ボタン及びキーボードの少なくとも一方から構成され、入力受付部１２４の機能を備える。表示装置４１５は、液晶ディスプレイ等であり、画像表示部１２５の機能を備える。
【０１０３】
なお、表示装置４１５のディスプレイがタッチパネルによって構成されている場合、表示装置４１５は、入力受付部１２４及び画像表示部１２５の機能を備える。
【０１０４】
スピーカ４１６は、例えば、自動車に搭載されているスピーカであり、音声出力部１２６の機能を備える。
【０１０５】
メモリ４１２には、動作制御部１２１を構成する状況判定部１２９、経路探索部１３０、計画策定部１３１、及び提示情報制御部１３２の機能を実現する各種プログラムが記憶される。ＣＰＵ４１１は、メモリ４１２に記憶された各種プログラムを実行する。よって、ＣＰＵ４１１及びメモリ４１２は、動作制御部１２１の機能を備える。
【０１０６】
記憶装置４１７には地図データが記憶されるので、記憶装置４１７は、地図データ記憶部１２２の機能を備える。また、記憶装置４１７は、書き込み可能な装置（例えば、ＨＤＤ等）であってもよいし、書き込み不可能な装置（例えば、ＤＶＤドライブ等）であってもよい。
【０１０７】
外部Ｉ／Ｆ４１３は、外部記憶媒体１１２に接続可能なインタフェース（例えば、ＵＳＢポート）であり、外部記憶媒体読取部１２７の機能を備える。外部記憶媒体読取部１２７は、外部記憶媒体出力部１０６によって外部記憶媒体１１２に出力された情報を読み取り可能であれば、どのような方法で実現されてもよい。
【０１０８】
ＧＰＳ受信機４１８は、現在位置を測位可能な装置であって、現在位置取得部１２３の機能を備える。
【０１０９】
記憶装置４０３及び４１７に記憶される地図データは、リンクデータ５０８（図５Ａ参照）、ノードデータ５１０（図５Ｂ参照）、地点データ６２０（図６Ａ参照）、及び地方データ６３１（図６Ｂ参照）を含む。
【０１１０】
地図データでは、交差点を意味するノード、及びノードから次のノードまでの間の道路を意味するリンクを用いて道路を表す。
【０１１１】
なお、地図データの地図は、矩形のメッシュによって分割されている。複数のメッシュに跨る道路は、メッシュの境界に仮想的なノードが配置されることによって、複数のリンクに分割される。これによって、各リンクは、いずれか一つのメッシュの領域に含まれる。
【０１１２】
図５Ａは、本発明の第１実施例のリンクデータ５０８の説明図である。
【０１１３】
リンクデータ５０８は、リンクに関する情報を示す表形式のデータであり、リンクＩＤ５０１、メッシュコード５０２、幅員５０３、種別５０４、形状５０５、始点ノード５０６、及び終点ノード５０７を含む。
【０１１４】
リンクＩＤ５０１には、リンクの一意な識別子が登録される。リンクデータ５０８は、一つのエントリにリンクＩＤ５０１に登録される識別子によって識別されるリンクに関する情報が登録される。
【０１１５】
メッシュコード５０２には、リンクＩＤ５０１に登録された識別子によって識別されるリンクを含むメッシュの一意な識別子が登録される。メッシュコード５０２にリンクを含むメッシュの識別子が登録されていることによって、例えば、ナビゲーション装置１２０が現在位置付近の道路を探索する場合に、現在位置のメッシュに含まれるリンクを探索すればよいので、現在位置付近の道路を高速に探索できるようになる。
【０１１６】
幅員５０３には、リンクＩＤ５０１に登録された識別子によって識別されるリンクの道幅を特定可能な数値が登録される。種別５０４には、リンクＩＤ５０１に登録された識別子によって識別されるリンクの道路の種別が登録される。道路の種別には、例えば、高速道路、私道、及び国道等がある。
【０１１７】
形状５０５には、リンクＩＤ５０１に登録された識別子によって識別されるリンクの形状を表す座標点の列が登録される。なお、運転計画立案支援装置１００及びナビゲーション装置１２０は、形状５０５に登録された座標点の列をポリラインによって描画することによって道路の画像を生成できる。
【０１１８】
始点ノード５０６には、リンクＩＤ５０１に登録された識別子によって識別されるリンクの一方の端点であるノードの識別子が登録される。終点ノード５０７には、リンクＩＤ５０１に登録された識別子によって識別されるリンクの他方の端点であるノードの識別子が登録される。始点ノード５０６及び終点ノード５０７に登録されたノードの識別子は、経路探索時に使用される。
【０１１９】
次に、ノードデータ５１０について図５Ｂを用いて説明する。図５Ｂは、本発明の第１実施例のノードデータ５１０の説明図である。
【０１２０】
ノードデータ５１０は、ノードとリンクとの関係を示すデータである。
【０１２１】
ノードデータ５１０は、ノードＩＤ５１１及び接続リンクＩＤ５１３を含む。ノードＩＤ５１１には、ノードの一意な識別子が登録される。接続リンクＩＤ５１３には、ノードＩＤ５１１に登録された識別子によって識別されるノードに接続される一つのリンクが登録される。
【０１２２】
あるノードの識別子でノードデータ５１０が検索された場合、このノードに接続されているすべてのリンクの識別子が取得される。そして、取得されたリンクの識別子でリンクデータ５０８が検索された場合、取得されたリンクの端点であるノードの識別子が取得される。この手順が繰り返されることによって、あるリンクから他のリンクまでの経路が探索できる。
【０１２３】
なお、図５Ａに示すリンクデータ５０８及び図５Ｂに示すノードデータ５１０は、一例であり、道路の画像の生成、及び経路探索が可能であれば、どのようなデータを用いてもよい。
【０１２４】
次に、地点データ６２０について図６Ａを用いて説明する。図６Ａは、本発明の第１実施例の地点データ６２０の説明図である。
【０１２５】
地点データ６２０には、経由地の候補又は目的地の候補となり得る地点に関する情報が登録される。
【０１２６】
地点データ６２０は、地点ＩＤ６２１、カテゴリ６２２、名称６２３、メッシュコード６２４、座標６２５、及びリンクＩＤ６２６を含む。
【０１２７】
地点ＩＤ６２１には、地点の一意な識別子が登録される。カテゴリ６２２には。地点ＩＤ６２１に登録された識別子によって識別される地点のカテゴリが登録される。例えば、カテゴリ６２２には、各地点で提供される商品又はサービスの種類（旅館業及び小売業等）が登録される。名称６２３には、地点ＩＤ６２１に登録された識別子によって識別される地点の名称が登録される。
【０１２８】
メッシュコード６２４には、地点ＩＤ６２１に登録された識別子によって識別される地点を含むメッシュの一意な識別子が登録される。座標６２５には、メッシュコード６２４に登録された識別子によって識別されるメッシュにおいて、地点ＩＤ６２１に登録された識別子によって識別される地点が位置する座標が登録される。リンクＩＤ６２６には、地点ＩＤ６２１に登録された識別子によって識別される地点に進入可能なリンクの一意な識別子が登録される。
【０１２９】
次に、地方データ６３１について図６Ｂを用いて説明する。図６Ｂは、本発明の第１実施例の地方データ６３１の説明図である。
【０１３０】
地方データ６３１は、地方ＩＤ６２７、名称６２８、メッシュコード６２９、及び座標６３０を含む。
【０１３１】
地方ＩＤ６２７には、地方の一意な識別子が登録される。名称６２８には、地方ＩＤ６２７に登録された識別子によって識別される地方の名称が登録される。メッシュコード６２９には、地方ＩＤ６２７に登録された識別子によって識別される地方の代表地点を含むメッシュの一意な識別子が登録される。座標６３０には、メッシュコード６２９に登録された識別子によって識別されるメッシュにおいて、地方ＩＤ６２７に登録された識別子によって識別される地方の代表地点が位置する座標が登録される。
【０１３２】
なお、図６Ａに示す地点データ６２０及び図６Ｂに示す地方データ６３１は、一例であり、画面表示及び音声提示等に用いる詳細テキスト、及び検索に用いるキーワード列、及び各地点の営業時間等を含んでもよい。
【０１３３】
次に、運転計画立案支援装置１００の記憶装置４０３に記憶される利用者情報７１０について、図７を用いて説明する。図７は、本発明の第１実施例の利用者情報７１０の説明図である。
【０１３４】
利用者情報７１０には、各地点が利用者によって最後に参照された年月日及び各地点が利用者によって参照された回数が登録される。
【０１３５】
利用者情報７１０は、地点ＩＤ７１１、カテゴリ７１２、メッシュコード７１３、座標７１４、最終参照７１５、及び参照回数７１６を含む。
【０１３６】
地点ＩＤ７１１、カテゴリ７１２、メッシュコード７１３、及び座標７１４は、図６Ａに示す地点データ６２０に含まれる地点ＩＤ６２１、カテゴリ６２２、名称６２３、及びメッシュコード６２４と同じであるので、説明を省略する。
【０１３７】
最終参照７１５には、地点ＩＤ７１１に登録された識別子によって識別される地点が利用者によって最後に参照された年月日が登録される。参照回数７１６には、地点ＩＤ７１１に登録された識別子によって識別される地点が利用者によって参照された回数が登録される。
【０１３８】
なお、本実施例の利用者情報７１０は、カテゴリ７１２、メッシュコード７１３、及び座標７１４を含むので、運転計画立案支援装置１００は、地点データ６２０を参照しなくとも、カテゴリ７１２、メッシュコード７１３、及び座標７１４に登録された情報を取得できるため、高速な処理が可能となる。
【０１３９】
また、記憶装置４０３の容量が小さい場合には、利用者情報７１０は、カテゴリ７１２、メッシュコード７１３、及び座標７１４を含まなくてもよい。この場合、運転計画立案支援装置１００は、カテゴリ７１２、メッシュコード７１３、及び座標７１４に登録された情報が必要となった場合には、地点データ６２０を参照して、カテゴリ６２２、メッシュコード６２４、及び座標６２５に登録された情報を取得する。
【０１４０】
なお、最終参照７１５及び参照回数７１６は、地点ＩＤ７１１に登録された識別子によって識別される地点が利用者によって参照されるごとに更新される。
【０１４１】
なお、利用者情報７１０の容量は、利用者が運転計画立案支援装置１００を利用するごとに増大するが、記憶装置４０３の容量が不足した場合等には、最終参照７１５に登録された年月日が古い地点の情報が削除又は圧縮されるようにしてもよい。
【０１４２】
次に、運転計画立案支援装置１００に備わる出力装置４０２に表示される運転計画立案画面について、図８を用いて説明する。図８は、本発明の第１実施例の運転計画立案画面の説明図である。
【０１４３】
運転計画立案支援画面は、出発地入力受付部８０１、目的地入力受付部８０２、運転計画経路出力部８０３、運転計画概要出力部８０４、決定ボタン８０５、及び計画編集ボタン８０６を含む。
【０１４４】
出発地入力受付部８０１は、出発地方の名称の入力を受け付ける部分である。目的地入力受付部８０２は、目的地方の名称の入力を受け付ける部分である。また、出発地入力受付部８０１には、必ずしも出発地方が入力される必要はない。出発地入力受付部８０１に何も入力されない場合、予め設定されている利用者の自宅の住所が出発地となる。
【０１４５】
出発地入力受付部８０１及び目的地入力受付部８０２に、出発地方及び目的地方が入力された場合、運転計画立案支援装置１００は、入力された出発地方及び目的地方に基づいて代表経路を探索して、運転計画情報を生成する。
【０１４６】
そして、運転計画立案支援装置１００は、運転計画経路出力部８０３に、代表経路を描画して、代表経路上に位置する経由地方を表示する。
【０１４７】
また、運転計画立案支援装置１００は、生成された運転計画情報の概要を運転計画概要出力部８０４に表示する。
【０１４８】
運転計画情報の概要は、往路の詳細情報、復路の詳細情報、予想旅行時間、及び旅行にかかる費用を含む。
【０１４９】
往路の詳細情報には、出発地方の出発時間、各経由地方の到着時間、及び目的地方の到着時間を含む。復路の詳細情報には、目的地方の出発時間、各経由地方の到着時間、及び出発地方の到着時間を含む。
【０１５０】
利用者は、生成された運転計画情報を編集しない場合には、決定ボタン８０５を操作する。決定ボタン８０５が操作された場合、生成された運転計画情報が外部記憶媒体１１２に転送される。一方、利用者は、生成された運転計画情報を編集する場合には、計画編集ボタン８０６を操作する。計画編集ボタン８０６が操作された場合、利用者は、生成された運転計画情報に、経由地方を追加（又は削除）したり、目的地を変更する等、運転計画情報を編集できる。
【０１５１】
次に、経路設定受付部１１３による代表経路選択処理について、図９を用いて説明する。図９は、本発明の実施形態の経路設定受付部１１３による代表経路選択処理のフローチャートである。
【０１５２】
まず、経路設定受付部１１３は、出発地入力受付部８０１に入力された出発地方を示す文字列及び目的地入力受付部８０２に入力された目的地方を示す文字列を取得する。
【０１５３】
そして、経路設定受付部１１３は、図６Ｂに示す地方データ６３１の名称６２８に登録された名称のうち、取得された出発地方を示す文字列に一致するエントリに含まれるメッシュコード６２９に登録された識別子によって識別されるメッシュ及び座標６３０に登録された座標を出発地方の代表地点とする（９０１）。
【０１５４】
また、経路設定受付部１１３は、図６Ｂに示す地方データ６３１の名称６２８に登録された名称のうち、取得された目的地方を示す文字列に一致するエントリに含まれるメッシュコード６２９に登録された識別子によって識別されるメッシュ及び座標６３０に登録された座標を目的地方の代表地点とする。
【０１５５】
次に、経路設定受付部１１３は、ステップ９０１の処理で出発地方の代表地点及び目的地方の代表地点のうち少なくとも一方において、複数の地点が代表地点として選択された場合、一の地点を代表地点として選択する。具体的には、経路設定受付部１１３は、ステップ９０１の処理で代表地点として選択された複数の地点から一つの地点を代表地点としてランダムに選択する。
【０１５６】
そして、経路設定受付部１１３は、一の出発地方の代表地点から一の目的地方の代表地点までの経路を代表経路として探索する（９０２）。
【０１５７】
なお、本実施例では、ステップ９０２の処理で、複数の地点から一つの地点が代表地点としてランダムに選択されたとしても、利用者が運転計画情報を編集できるので、多大な影響を運転計画に及ぼすことはない。
【０１５８】
次に、経路設定受付部１１３は、図６Ｂに示す地方データ６３１に登録された地方のうち、ステップ９０２の処理で探索された代表経路からの距離が所定の値以下である地方を選択する（９０３）。
【０１５９】
具体的には、経路設定受付部１１３は、代表経路を構成する各リンクから図６Ｂに示す地方データ６３１に登録される各地方までの距離を算出する。そして、経路設定受付部１１３は、算出された距離が所定の値以下である地方を選択する。
【０１６０】
次に、経路設定受付部１１３は、ステップ９０３の処理で選択された地方を経由地方に設定する（９０４）。
【０１６１】
なお、本実施例では、経路設定受付部１１３は、図６Ｂに示す地方データ６３１を参照して、経由地方を選択したが、図６Ａに地点データ６２０を参照して、代表経路からの距離が所定の値以下の地点を選択して、経由地点としてもよい。
【０１６２】
なお、本実施例では、経路設定受付部１１３は、代表経路からの距離が所定の値以下の地方を選択したが、経由する地方として適当な地方が選択されれば、如何なる方法を用いて経由地方を選択してもよい。
【０１６３】
経路設定受付部１１３が図９に示す代表経路選択処理を実行することによって、運転計画立案支援装置１００は、図８に示す運転計画立案画面を表示できる。
【０１６４】
次に、図８に示す運転計画立案画面で表示された運転計画情報の概要を編集する場合に表示される運転計画編集画面について、図１０を用いて説明する。図１０は、本発明の第１実施例の運転計画編集画面の説明図である。
【０１６５】
運転計画編集画面は、図８に示す運転計画立案画面に含まれる計画編集ボタン８０６が操作された場合に表示される。また、運転計画編集画面は、利用者が図８に示す運転計画立案画面で表示される経由地方、出発地、及び目的地を追加、削除、又は変更するための画面である。
【０１６６】
運転計画編集画面は、検索キーワード入力受付部１０００、検索地点表示部１００１、運転計画編集部１００２、及び検索地点位置表示部１００３を含む。
【０１６７】
検索キーワード入力受付部１０００は、利用者が運転計画情報の概要に追加又は変更を希望する地点を検索するためのキーワードを入力するための表示部である。
【０１６８】
検索地点表示部１００１は、検索地点名表示部１００１Ａ及び検索地点詳細情報表示部１００１Ｂを含む。
【０１６９】
検索地点名表示部１００１Ａには、検索キーワード入力受付部１０００に入力された文字列と条件が一致する地点が表示される地点の名称が表示される。検索地点詳細情報表示部１００１Ｂには、検索地点名表示部１００１Ａに表示された地点のうち、利用者によって選択された地点の詳細な情報が表示される。検索地点詳細情報表示部１００１Ｂに表示される情報は、具体的には、地点の名称、地点の住所、及び地点の営業時間等である。
【０１７０】
運転計画編集部１００２には、現在設定されている運転計画情報の概要に含まれる出発地、経由地方、及び目的地が表示される。運転計画編集部１００２に表示される出発地及び目的地の下方には、変更ボタンが表示される。また、運転計画編集部１００２に表示される各経由地方の下方には、削除ボタンが表示される。また、運転計画編集部１００２に表示される出発地と経由地方との間、各経由地方の間、及び経由地方と目的地との間には、追加ボタンが表示される。
【０１７１】
変更ボタンが操作された場合には、変更ボタンが操作された出発地又は目的地に検索地点名表示部１００１Ａで選択されている地点が変更される。削除ボタンが操作された場合には、削除ボタンが操作された経由地方が運転計画情報の概要から削除される。追加ボタンが操作された場合には、追加ボタンが操作された部分に検索地点名表示部１００１Ａで選択された地点が経由地方として運転計画情報の概要に追加される。
【０１７２】
検索地点位置表示部１００３には、運転計画編集部１００２で選択された地点の地図上での位置が表示される。
【０１７３】
そして、運転計画編集画面の完了ボタンが操作された場合には、現在の運転計画情報の概要が運転計画概要として運転計画立案支援装置１００に登録される。
【０１７４】
なお、本実施例の運転計画編集画面は一例であり、運転計画編集画面には利用者が欲する情報（例えば、経由地方及び高速道路を利用しない等）が表示されれば、他の表示方法であってもよい。
【０１７５】
次に、運転計画立案支援装置１００が運転計画概要に基づいて運転計画情報を生成する運転計画生成処理について、図１１を用いて説明する。図１１は、本発明の第１実施例の運転計画生成処理のフローチャートである。
【０１７６】
まず、地点情報準備範囲策定部１０８は、仮想的な出発地点から仮想的な目的地点に到達し得るすべての経路を探索する。そして、探索された経路を構成するリンクの一覧を周辺リンクとして取得する（１１０１）。なお、ステップ１１０１の処理の周辺リンクを取得する処理については、図１２で詳細を説明する。
【０１７７】
次に、地点候補選択部１０９は、図６Ａに示す地点データ６２０に登録された地点から、ステップ１１０１の処理で取得された周辺リンクに紐付けられる地点を取得する（１１０２）。
【０１７８】
具体的には、地点候補選択部１０９は、図６Ａに示す地点データ６２０に登録されたエントリのうち、リンクＩＤ６２６に登録されたリンクの識別子がステップ１１０１の処理で取得された周辺リンクの識別子と一致するエントリを、周辺リンクに紐付けられる地点として取得する。
【０１７９】
次に、運転計画情報生成部１１１は、ステップ１１０２の処理で取得された地点の分類コードを算出して、運転計画情報を生成する（１１０３）。分類コードは、ナビゲーション装置１２０がステップ１１０２の処理で取得された地点を経由地候補として利用者に提示するか否かを判定するために用いられるコードである。
【０１８０】
運転計画情報生成部１１１は、ステップ１１０２の処理で取得された地点のカテゴリ６２２に登録された情報に基づいて分類コードを算出する。
【０１８１】
例えば、正午ごろに到達すると予測される地点が飲食店である場合には、運転計画情報生成部１１１は、飲食店の地点が他の地点よりも優先して利用者に提示される分類コードを当該地点に付与する。また、運転時間が一定時間（例えば１時間）経過した場合に到達すると予測される地点が休憩所、パーキングエリア及び喫茶店等の休憩可能な地点である場合には、運転計画情報生成部１１１は、休憩可能な地点が他の地点よりも優先して利用者に提示される分類コードを当該地点に付与する。
【０１８２】
他の分類コードを算出する方法について説明する。運転計画情報生成部１１１は、ステップ１１０２の処理で取得された地点が図７に示す利用者情報７１０の参照回数７１６に登録された数が所定の値よりも大きい場合には、当該地点を利用者情報７１０の参照回数７１６に登録された数が所定の値以下である地点よりも優先して表示される分類コードを当該地点に付与する。
【０１８３】
したがって、分類コードには、地点で提供される商品又は役務の種類、及び地点の参照回数等が含まれ得る。
【０１８４】
次に、外部記憶媒体出力部１０６は、ステップ１１０３の処理で生成された運転計画情報をナビゲーション装置１２０が読み取り可能な形式に変換して、外部記憶媒体１１２に出力する（１１０４）。
【０１８５】
次に、ステップ１１０１の処理の周辺リンクを取得する周辺リンク取得処理について、図１２を用いて説明する。図１２は、本発明の第１実施例の周辺リンク取得処理のフローチャートである。
【０１８６】
周辺リンク取得処理は、ダイクストラ法によって仮想的な出発地点から仮想的な目的地点まで到達し得る経路のうち、累積コストが最小となる経路を探索し、コストが算出されたすべてのリンクを周辺リンクとして取得する処理である。なお、コストとは、リンクを移動するためにかかる時間又はリンクの距離である。また、累積コストは、出発地から当該リンクの始点ノードに到達するまでにかかる時間又は距離（コスト）に、当該リンクのコストを加算した値である。
【０１８７】
まず、地点情報準備範囲策定部１０８は、仮想的な出発地点に進入可能なリンクを探索開始地点としてチェック対象に追加する（１２０１）。具体的には、地点情報準備範囲策定部１０８は、図５Ａに示す地点データ６２０に登録された地点のうち、仮想的な出発地点のエントリに含まれるリンクＩＤ６２６に登録されたリンクの識別子を取得して、取得された識別子によって識別されるリンクを、探索開始地点としてチェック対象に追加する。
【０１８８】
次に、地点情報準備範囲策定部１０８は、チェック対象のリンクのうち、累積コストが最小のリンクを変数Ｔに代入する（１２０２）。そして、地点情報準備範囲策定部１０８は、ステップ１２０２の処理で変数Ｔに代入されたリンクをチェック済みのリンクとする（１２０３）。
【０１８９】
次に、地点情報準備範囲策定部 １０８は、変数Ｔに代入されたリンクに接続されるｎ番目のリンクを変数Ｘに代入して、ｎ＋１番目のリンクをｎ番目のリンクとする（１２０４）。
【０１９０】
次に、地点情報準備範囲策定部１０８は、変数Ｘに代入されたリンクは仮想的な目的地点に進入可能なリンクであるか否かを判定する（１２０５）。
【０１９１】
具体的には、地点情報準備範囲策定部１０８は、図６Ａに示す地点データ６２０に登録されたエントリのうち仮想的な目的地点のエントリを取得し、取得したエントリに含まれるリンクＩＤ６２６に登録されたリンクの識別子が、変数Ｘに代入されたリンクの識別子に一致するか否かを判定する。
【０１９２】
ステップ１２０５の処理で、地点情報準備範囲策定部１０８は、変数Ｘに代入されたリンクが仮想的な目的地点に進入可能なリンクでないと判定された場合、変数Ｘに代入されたリンクがチェック済みのリンクであるか否かを判定する（１２０６）。
【０１９３】
ステップ１２０６の処理で、地点情報準備範囲策定部１０８は、変数Ｘに代入されたリンクがチェック済みのリンクでないと判定された場合、探索開始地点から変数Ｘに代入されたリンクまでの累積コストを算出して、変数Ｘに代入されたリンクをチェック対象に追加する（１２０７）。
【０１９４】
具体的には、地点情報準備範囲策定部１０８は、探索開始地点から変数Ｔに代入されたリンクまでの累積コストに変数Ｘに代入されたリンクの通過コストを加算することによって、探索開始地点から変数Ｘに代入されたリンクまでの累積コストを算出する。
【０１９５】
次に、地点情報準備範囲策定部１０８は、変数Ｔに代入されたリンクの接続先のすべてのリンクの累積コストが算出されたか否かを判定するために、変数Ｘに代入されたリンクの番号（ｎ）が変数Ｔに代入されたリンクの接続先のリンクの数よりも小さいか否かを判定する（１２０８）。
【０１９６】
ステップ１２０８の処理で、変数Ｘに代入されたリンクの番号（ｎ）が変数Ｔに代入されたリンクの接続先のリンクの数よりも小さいと判定された場合、変数Ｔに代入されたリンクの接続先のすべてのリンクの累積コストが算出されていないので、ステップ１２０４の処理に戻る。
【０１９７】
一方、ステップ１２０８の処理で、変数Ｘに代入されたリンクの番号（ｎ）が変数Ｔに代入されたリンクの接続先のリンクの数以上であると判定された場合、変数Ｔに代入されたリンクの接続先のすべてのリンクの累積コストが算出されたので、ステップ１２０２の処理に戻る。
【０１９８】
一方、ステップ１２０５の処理で、変数Ｘに代入されたリンクは仮想的な目的地点に進入可能なリンクであると判定された場合、仮想的な出発地点から仮想的な目的地点までの経路が探索されたので、チェック済みリンクを周辺リンクに追加し（１２０９）、周辺リンク取得処理を終了する。
【０１９９】
つまり、周辺リンク取得処理では、出発地のリンクに接続されるリンクに接続されるすべてのリンクに対して累積コストを算出し、最小の累積コストのリンクを選択し、選択されたリンクに接続されるすべてのリンクに対してコストを算出し、最小の累積コストのリンクを選択していく処理を目的地に接続されるリンクまで繰り返し実行する。そして、累積コストが算出されたすべてのリンクを周辺リンクとする。
【０２００】
次に、図１１に示す運転計画生成処理によって生成される運転計画情報を、図１３Ａ及び図１３Ｂを用いて説明する。運転計画情報は、運転計画概要情報１３００及び経由地候補情報１３１０を含む。
【０２０１】
まず、運転計画概要情報１３００について、図１３Ａを用いて説明する。図１３Ａは、本発明の第１実施例の運転計画概要情報１３００の説明図である。
【０２０２】
運転計画概要情報１３００は、要素番号１３０１、種別１３０２、分類１３０３、名称１３０４、メッシュコード１３０５、及びオブジェクトＩＤ１３０６を含む。
【０２０３】
要素番号１３０１には、運転計画の概要を構成する各要素の一意な識別子が登録される。種別１３０２には、運転計画の概要を構成する各要素の種別を示す情報が登録される。例えば、種別１３０２には、運転計画の概要を構成する要素が地点（出発地、経由地、及び目的地等）を示す場合には「１」が登録され、運転計画の概要を構成する要素が道路を示す場合には「２」が登録される。
【０２０４】
分類１３０３には、図１１に示す運転計画生成処理のステップ１１０３の処理で算出された分類コードが登録される。したがって、分類１３０３には、地点で提供される商品又は役務の種類、及び地点の参照回数等が含まれ得る。
【０２０５】
名称１３０４には、運転計画の概要を構成する要素の名称を示す情報が登録される。メッシュコード１３０５には、運転計画の概要を構成する要素（地点又は代表経路）を含むメッシュの一意な識別子が登録される。オブジェクトＩＤ１３０６には、ナビゲーション装置１２０に備わる記憶装置４１７に記憶される地図データのオブジェクトのうち、運転計画の概要を構成する要素（地点又は代表経路）に対応するオブジェクトの一意な識別子が登録される。
【０２０６】
次に、経由地候補情報１３１０について、図１３Ｂを用いて説明する。図１３Ｂは、本発明の第１実施例の経由地候補情報１３１０の説明図である。
【０２０７】
経由地候補情報１３１０は、図１１に示す運転計画生成処理のステップ１１０２の処理で取得された地点の情報である。ナビゲーション装置１２０は、現在の状況に対応して、経由地候補情報１３１０に登録された地点から経由地の候補となり得る地点を利用者に提示する。
【０２０８】
経由地候補情報１３１０は、地点ＩＤ１３１１、リンクＩＤ１３１２、分類１３１３、名称１３１４、メッシュコード１３１５、及び座標１３１６を含む。
【０２０９】
地点ＩＤ１３１１には、地点の一意な識別子が登録される。リンクＩＤ１３１２には、地点ＩＤ１３１１に登録された識別子によって識別される地点に進入可能なリンクの一意な識別子が登録される。
【０２１０】
分類１３０３には、図１１に示す運転計画生成処理のステップ１１０３の処理で算出された分類コードが登録される。名称１３１４には、地点ＩＤ１３１１に登録された識別子によって識別される地点の名称が登録される。
【０２１１】
メッシュコード１３１５には、地点ＩＤ１３１１に登録された識別子によって識別される地点を含むメッシュの一意な識別子が登録される。座標１３１６には、メッシュコード１３１５に登録された識別子によって識別されるメッシュにおいて、地点ＩＤ１３１１に登録された識別子によって識別される地点が位置する座標が登録される。
【０２１２】
なお、本実施例の運転計画情報は一例であり、運転計画概要情報１３００及び経由地候補情報１３１０は他の属性情報を含んでもよい。
【０２１３】
次に、ナビゲーション装置１２０に備わる表示装置４１５に表示される案内画面について、図１４を用いて説明する。図１４は、本発明の第１実施例のナビゲーション装置１２０に備わる表示装置４１５に表示される案内画面の説明図である。
【０２１４】
ナビゲーション装置１２０は、外部記憶媒体１１２に記憶された運転計画情報を読み取って、運転計画情報に基づいて経路案内を開始する。
【０２１５】
案内画面には、案内経路１４０１、現在位置１４０２、分岐点１４０３、経由候補地点１４０４、及び代替経路１４０５が表示される。
【０２１６】
案内経路１４０１には、目的地までのナビゲーション装置１２０を搭載した自動車の現在走行中の経路が表示される。現在位置１４０２には、ＧＰＳ受信機４１８によって取得されたナビゲーション装置１２０を搭載した自動車の現在位置が表示される。
【０２１７】
分岐点１４０３には、現在走行中の案内経路と、経由候補地点を経由して目的地まで到達可能な代替経路との分岐が表示される。
【０２１８】
経由候補地点１４０４には、現在の状況（現在位置及び現在の時刻等）、及び経由地候補情報１３１０に登録された地点の分類１３１３に登録された分類コードに基づいて、経由候補地点の詳細情報が表示される。代替経路１４０５には、経由候補地点を経由して目的地まで到達可能な代替経路が表示される。
【０２１９】
次に、ナビゲーション装置１２０によって実行される案内経路提示処理について図１５を用いて説明する。図１５は、本発明の第１実施例の案内経路提示処理のフローチャートである。
【０２２０】
まず、計画策定部１３１は、ＧＰＳ受信機４１８からナビゲーション装置１２０を搭載した自動車の現在位置を取得する。そして、計画策定部１３１は、運転計画概要情報１３００を参照して、仮想的な目的地を特定する。具体的には、計画策定部１３１は、運転計画概要情報１３００に登録されたエントリのうち、分類１３０３に登録された情報が仮想的な目的地を示す情報（分類コードが「２」）であるエントリを、仮想的な目的地として取得する。
【０２２１】
そして、計画策定部１３１は、取得した現在位置から取得した仮想的な目的地までの最短経路を、ダイクストラ法を用いて探索する（１５０１）。
【０２２２】
次に、計画策定部１３１は、ステップ１５０１の処理で探索された経路を図１４に示す案内画面に案内経路１４０１として表示することによって、案内経路を利用者に提示する（１５０２）。
【０２２３】
次に、計画策定部１３１は、仮想的な目的地に到達しているか否かを判定するために、ステップ１５０１の処理で取得された現在位置からステップ１５０１の処理で取得された仮想的な目的地までの距離が所定値以下であるか否かを判定する（１５０３）。
【０２２４】
ステップ１５０３の処理で、ステップ１５０１の処理で取得された現在位置からステップ１５０１の処理で取得された仮想的な目的地までの距離が所定値以下であると判定された場合、つまり、仮想的な目的地に到達していると判定された場合、計画策定部１３１は、図１３Ｂに示す経由地候補情報１３１０を参照して、仮想的な目的地周辺の目的地となり得る地点を表示装置４１５に表示することによって、目的地候補を利用者に提示し（１５０７）、案内経路提示処理を終了する。
【０２２５】
一方、ステップ１５０３の処理で、ステップ１５０１の処理で取得された現在位置からステップ１５０１の処理で取得された仮想的な目的地までの距離が所定値より大きいと判定された場合、つまり、仮想的な目的地に到達していないと判定された場合、提示情報制御部１３２は、経由候補地点を利用者に提示する経由候補地点提示処理を実行する（１５０４）。経由候補地点提示処理については、図１６を用いて説明する。
【０２２６】
次に、計画策定部１３１は、現在走行中の案内経路から利用者に提示された経由候補地点側に経路を変更したか否かを判定する（１５０５）。具体的には、計画策定部１３１は、ＧＰＳ受信機４１８から現在位置を取得し。取得した現在位置が案内経路を外れて、利用者に提示された経由候補地点側へ移動したか否かを判定する。
【０２２７】
ステップ１５０５の処理で、現在走行中の案内経路から利用者に提示された経由候補地点側に経路を変更したと判定された場合、経由候補地点を経由地として、現在位置から経由地を経由して仮想的な目的地まで到達可能な最短経路である代替経路をダイクストラ法を用いて探索して、探索された代替経路を案内経路に更新し（１５０６）、ステップ１５０２の処理に戻る。
【０２２８】
次に、図１５に示す案内経路提示処理のステップ１５０４の処理の経由候補地点提示処理について、図１６を用いて説明する。図１６は、本発明の第１実施例の経由候補地点提示処理のフローチャートである。
【０２２９】
まず、状況判定部１２９は、現在の状況を判定して、現在の状況に対応する分類コードの一覧を生成する（１６０１）。
【０２３０】
例えば、状況判定部１２９は、現在の時刻を取得して、取得した現在の時刻が食事時間であるか否かを判定することによって、現在の状況を判定する。そして、現在の状況が食事時間であると判定された場合、状況判定部１２９は、食事時間に対応する分類コード（例えば、飲食店及び休憩可能な地点を示す分類コード）の一覧を生成する。
【０２３１】
また、状況判定部１２９は、現在の状況を示す特徴的な量を算出して、算出された特徴的な量を予め設定された識別関数に入力して、識別関数を演算して現在の状況を判定する。そして、状況判定部１２９は、識別関数の演算結果に対応する分類コードの一覧を生成してもよい。
【０２３２】
なお、状況判定部１２９が現在の状況を判定する方法は、適当に現在の状況を判定できれば、如何なる方法を用いてもよい。
【０２３３】
次に、経路探索部１３０は、現在位置に対応する次の分岐点から、ナビゲーション装置１２０を搭載した自動車が所定時間以内に到達可能な範囲にあるすべてのリンクを取得する（１６０２）。
【０２３４】
次に、計画策定部１３１は、ステップ１６０１の処理で取得された分類コード及びステップ１６０２の処理で取得されたリンクに基づいて、経由地候補情報１３１０に登録された地点を経由候補地点として取得する（１６０３）。
【０２３５】
具体的には、計画策定部１３１は、経由地候補情報１３１０に登録されたエントリのうち、分類１３１３に登録された分類コードがステップ１６０１の処理で取得された分類コードに一致し、かつリンクＩＤ１３１２に登録された識別子によって識別されるリンクが、ステップ１６０２の処理で取得されたリンクに一致するエントリの地点を、経由候補地点として取得する。
【０２３６】
次に、提示情報制御部１３２は、ステップ１６０３の処理で取得された経由候補地点を、図１４に示す案内画面に表示する（１６０４）。
【０２３７】
（第２実施例）
次に、本発明の第２実施例について、図１７〜図２２を用いて説明する。第２実施例では、利用者は、入力受付部１０２としての機能を有する移動端末１７３０（例えば、携帯電話等）から出発地方及び目的地方等を、ネットワークを介して運転計画立案支援装置１７００に入力する点、及び例えば、地点に関する情報を利用者にホームページ等によって提供する外部情報源（地点情報提供装置）１７１０で紹介された地点を運転計画情報に含まれる経由地候補情報に含めることができる点で、第１実施例と異なる。
【０２３８】
なお、第２実施例の構成及び処理のうち、第１実施例の構成及び処理と同じものは、同じ番号を付与し、説明を省略する。
【０２３９】
第２実施例の運転計画立案支援システムについて、図１７を用いて説明する。図１７は、本発明の第２実施例の運転計画立案支援システムのブロック図である。
【０２４０】
運転計画立案支援システムは、運転計画立案支援装置１７００、外部情報源１７１０、ナビゲーション装置１７２０、及び移動端末１７３０を備える。
【０２４１】
なお、運転計画立案支援装置１７００、外部情報源１７１０、ナビゲーション装置１７２０、及び移動端末１７３０は、ネットワークを介して接続される。
【０２４２】
運転計画立案支援装置１７００は、ＣＰＵ４０５、記憶装置４０３、メモリ４０６、及びＮＩＣ（Network Interface Card）１７０３を備える。ＮＩＣ１７０３は、運転計画立案支援装置１７００をネットワークに接続する通信部１０５として機能する。
【０２４３】
外部情報源１７１０は、地点に関する情報を記憶し、記憶している地点に関する情報を利用者に提供する。外部情報源１７１０は、情報交換サービス１７０１及び情報発信サイト１７０２を含む。
【０２４４】
情報交換サービス１７０１は、利用者間で情報を交換するサービスを提供する。情報発信サイト１７０２は、利用者が自身の経験等をインターネット上に発信するためのサービスを提供する。
【０２４５】
ナビゲーション装置１７２０は、第１実施例の外部Ｉ／Ｆ４１３に代わって、無線通信装置１７２１を備える。無線通信装置１７２１は、ナビゲーション装置１７２０をネットワークに接続する通信部１２８として機能する。これによって、ナビゲーション装置１７２０を搭載した自動車が移動中であっても、ナビゲーション装置１７２０はネットワークに接続できる。
【０２４６】
移動端末１７３０は、例えば携帯電話であり、入力受付部１０２として機能する。
【０２４７】
次に、外部情報源１７１０に記憶された情報を移動端末１７３０に表示する外部情報表示処理について、図１８を用いて説明する。図１８は、本発明の第２実施例の外部情報表示処理の説明図である。
【０２４８】
まず、移動端末１７３０は、利用者が移動端末１７３０に表示する地点に関する情報の文書を取得する要求である文書要求１８０１を、ネットワークを介して運転計画立案支援装置１７００に送信する。
【０２４９】
運転計画立案支援装置１７００は、文書要求１８０１を受信した場合に、受信した文書要求１８０１を外部情報源１７１０に転送する。
【０２５０】
外部情報源１７１０は、文書要求１８０１を受信した場合に、利用者が移動端末１７３０に表示することを所望する表示文書データ１８０２、及び表示文書データ１８０２によって表示される地点の位置を特定するための外部情報メタデータ１８０３を、運転計画立案支援装置１７００に送信する。
【０２５１】
外部情報メタデータ１８０３は、メッシュコード１８１３及び座標１８１４を含む。メッシュコード１８１３は、表示文書データ１８０２によって表示される地点を含むメッシュの一意な識別子が登録される。座標１８１４には、メッシュコード１８１３に登録された識別子によって識別されるメッシュにおいて、表示文書データ１８０２によって表示される地点が位置する座標が登録される。
【０２５２】
運転計画立案支援装置１７００は、表示文書データ１８０２及び外部情報メタデータ１８０３を受信した場合、利用者が外部情報を利用した履歴を図１９に示す利用者外部情報使用履歴データ１９１０に登録する。利用者外部情報使用履歴データ１９１０については、図１９で詳細を説明する。
【０２５３】
そして、運転計画立案支援装置１７００は、表示文書データ１８０２のみを移動端末１７３０に送信する。
【０２５４】
移動端末１７３０は、表示文書データ１８０２を受信した場合、受信した表示文書データ１８０２を移動端末１７３０に表示する。
【０２５５】
次に、利用者外部情報使用履歴データ１９１０について、図１９を用いて説明する。図１９は、本発明の第２実施例の利用者外部情報使用履歴データ１９１０の説明図である。
【０２５６】
利用者外部情報使用履歴データ１９１０は、参照先１９１１、メッシュコード１９１２、座標１９１３、及びタイムスタンプ１９１４を含む。
【０２５７】
参照先１９１１には、運転計画立案支援装置１７００が受信した文書要求１８０１に含まれる文書要求１８０１を取得するＵＲＬが登録される。
【０２５８】
メッシュコード１９１２には、運転計画立案支援装置１７００が受信した外部情報メタデータ１８０３に含まれるメッシュコード１８１３に登録されたメッシュの一意な識別子が登録される。座標１９１３には、運転計画立案支援装置１７００が受信した外部情報メタデータ１８０３に含まれる座標１８１４に登録された座標が登録される。
【０２５９】
タイムスタンプ１９１４には、運転計画立案支援装置１７００が表示文書データ１８０２及び外部情報メタデータ１８０３を受信した年月日及び時刻が登録される。
【０２６０】
なお、利用者外部情報使用履歴データ１９１０は、利用者が外部情報を利用するごとにエントリが追加されていくので、利用者外部情報使用履歴データ１９１０に登録されたエントリの数が所定の値以上になった場合に、運転計画立案支援装置１７００は、タイムスタンプ１９１４に登録された年月日及び時刻が古いエントリを削除してもよい。
【０２６１】
次に、運転計画立案支援装置１７００が利用者外部情報使用履歴データ１９１０に基づいて運転計画情報を生成する運転計画生成処理について、図２０を用いて説明する。図２０は、本発明の第２実施例の運転計画生成処理のフローチャートである。なお、第２実施例の運転計画生成処理のうち、図１１に示す第１実施例と同じ処理は、同じ符号を付与し、説明を省略する。
【０２６２】
まず、地点情報準備範囲策定部１０８は、ステップ１１０１の処理を実行して周辺リンクの一覧を取得する。
【０２６３】
次に、地点候補選択部１０９は、ステップ１１０２の処理を実行して、ステップ１１０１の処理で取得された周辺リンクに紐付けられる地点を取得する。
【０２６４】
次に、地点候補選択部１０９は、利用者外部情報使用履歴データ１９１０に登録された地点のうち、ステップ１１０１の処理で取得された周辺リンクに紐付けられる地点を取得する（２００１）。
【０２６５】
具体的には、地点候補選択部１０９は、図５Ａに示すリンクデータ５０８に登録されたエントリのうち、ステップ１１０１の処理で取得された周辺リンクに一致するエントリを選択する。そして、地点候補選択部１０９は、選択されたエントリに含まれるメッシュコード５０２に登録されたメッシュコード及び形状５０５に登録された座標を取得する。
【０２６６】
次に、地点候補選択部１０９は、図１９に示す利用者外部情報使用履歴データ１９１０に登録されたエントリのうち、メッシュコード１９１２に登録されたメッシュコード及び座標１９１３に登録された地点の座標によって特定される地点の位置が、周辺リンクに対応するエントリに含まれるメッシュコード５０２に登録されたメッシュコード及び形状５０５に登録された座標によって特定される周辺リンクの位置から最も近いエントリを取得する。これによって、地点候補選択部１０９は、周辺リンクに紐付けられる地点を取得する。
【０２６７】
次に、地点候補選択部１０９は、ステップ１１０２の処理で取得された地点（地点データ６２０から取得された地点）及びステップ２００１の処理で取得された地点（利用者外部情報使用履歴データ１９１０から取得された地点）の分類コードを算出して、運転計画情報を生成する（２００２）。この場合、地点候補選択部１０９は、ステップ１１０２の処理で取得された地点の分類コードと、ステップ２００１の処理で取得された地点とを区別できるように、分類コードを付与する。
【０２６８】
なお、分類コードの算出方法については、図１１に示すステップ１１０３の処理と同じであるので、説明を省略する。
【０２６９】
次に、通信部１０５は、ステップ２００２の処理で生成された運転計画情報をナビゲーション装置１７２０が読み取り可能な形式に変換し、ステップ２００２の処理で生成された運転計画情報をナビゲーション装置１７２０にネットワークを介して送信する（２００３）。
【０２７０】
次に、運転計画情報について、図２１Ａ及び図２１Ｂを用いて説明する。
【０２７１】
運転計画情報は、運転計画概要情報１３００、経由地候補情報１３１０、及び履歴地点参照情報２１２０を含む。運転計画概要情報１３００については、図１３Ａに示す第１実施例の運転計画概要情報１３００と同じなので、説明を省略する。
【０２７２】
まず、経由地候補情報１３１０について、図２１Ａを用いて説明する。図２１Ａは、本発明の第２実施例の経由地候補情報１３１０の説明図である。
【０２７３】
経由地候補情報１３１０は、図１３Ｂに示す第１実施例の経由地候補情報１３１０と同じ構成であるが、登録されるエントリが相違する。
【０２７４】
エントリ１３１０１及び１３１０２に示すように、経由地候補情報１３１０には、利用者外部情報使用履歴データ１９１０に登録された地点の情報のうち、周辺リンクに紐付けられる利用者外部情報使用履歴データ１９１０に登録された地点の情報が登録される。
【０２７５】
利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれる地点ＩＤ１３１１には、地点データ６２０に登録された地点の情報のうち、周辺リンクに紐付けられる地点の情報を示すエントリに含まれる地点ＩＤ１３１１に登録された地点を示す識別子と重複しないように一意に生成された地点を示す一意な識別子が登録される。
【０２７６】
利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれるリンクＩＤ１３１２には、利用者外部情報使用履歴データ１９１０に登録された地点のうち周辺リンクに紐付けられる地点から最も近い周辺リンクを示す一意な識別子が登録される。
【０２７７】
利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれる分類１３１３には、ステップ２００２の処理で算出された分類コードが登録される。
【０２７８】
利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれるメッシュコード１３１５及び座標１３１６には、利用者外部情報使用履歴データ１９１０に登録された地点の情報のうち周辺リンクに紐付けられる地点のメッシュコード１９１２に登録されたメッシュコード及び座標１９１３に登録された座標が登録される。
【０２７９】
また、利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれる名称１３１４には、利用者外部情報使用履歴データ１９１０に登録された地点の情報のうち周辺リンクに紐付けられる地点の参照先１９１１に登録されたＵＲＬによって特定されるホームページを参照して、当該地点の名称として使用される文字列、又は当該ホームページで頻繁に使用される単語の文字列を取得して、取得された文字列が登録される。
【０２８０】
なお、利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれる名称１３１４には、利用者外部情報使用履歴データ１９１０に登録された地点の情報のうち周辺リンクに紐付けられる地点の適切な名称として使用される文字列が登録されればよい。
【０２８１】
次に、履歴地点参照情報２１２０について、図２１Ｂを用いて説明する。図２１Ｂは、本発明の第２実施例の履歴地点参照情報２１２０の説明図である。
【０２８２】
履歴地点参照情報２１２０は、ナビゲーション装置１２０が図２１Ａに示す経由地候補情報１３１０に登録された地点の情報のうち、利用者外部情報使用履歴データ１９１０から取得された地点の情報を参照する場合に、当該地点の詳細情報を取得するためのデータである。
【０２８３】
履歴地点参照情報２１２０は、地点ＩＤ２１２１及び参照先２１２２を含む。
【０２８４】
地点ＩＤ２１２１には、経由地候補情報１３１０に登録された地点の情報のうち、利用者外部情報使用履歴データ１９１０から取得された地点の情報に含まれる地点ＩＤ１３１１に登録された地点の識別子が登録される。
【０２８５】
参照先２１２２には、経由地候補情報１３１０に登録された地点の情報のうち利用者外部情報使用履歴データ１９１０から取得された地点と一致する利用者外部情報使用履歴データ１９１０に登録された地点の参照先１９１１に登録されたＵＲＬが登録される。
【０２８６】
なお、本実施例のナビゲーション装置１２０によって実行される処理は、第１実施例のナビゲーション装置１２０によって実行される処理（図１５及び図１６）と同じなので、説明を省略する。
【０２８７】
また、図１６に示すステップ１６０４の処理（提示情報制御部１３２が経由候補地点を案内画面に表示する処理）で、提示情報制御部１３２は、経由地候補情報１３１０に登録された地点のうち、利用者外部情報使用履歴データ１９１０から取得された地点を経由候補地点として、案内画面に表示する場合には、履歴地点参照情報２１２０に登録されたエントリに含まれる地点ＩＤ２１２１に登録された識別子のうち、当該経由候補地点として表示する地点の地点ＩＤ１３１１に登録された識別子と一致するエントリを選択し、選択されたエントリに含まれる参照先２１２２に登録されたＵＲＬを取得する。そして、提示情報制御部１３２は、取得されたＵＲＬによって特定されるホームページ（外部情報源１７１０）へ、無線通信装置１７２１を用いて接続して、当該ホームページから表示文書データ１８０２を取得する。
【０２８８】
これによって、提示情報制御部１３２は、経由地候補情報１３１０に登録された地点のうち、利用者外部情報使用履歴データ１９１０から取得された地点を経由候補地点として、案内画面に表示する場合に、当該地点の詳細情報も表示することができる。
【０２８９】
次に、ナビゲーション装置１２０に備わる表示装置４１５に表示される案内画面について、図２２を用いて説明する。図２２は、本発明の第２実施例のナビゲーション装置１２０に備わる表示装置４１５に表示される案内画面の説明図である。なお、図２２に示す案内画面の構成のうち、図１４に示す第１実施例の案内画面と同じ構成は、同じ符号を付与し、説明を省略する。
【０２９０】
図２２は、経由候補地点１４０４に、経由地候補情報１３１０に登録された地点のうち、利用者外部情報使用履歴データ１９１０から取得された地点が表示される場合の案内画面である。
【０２９１】
この場合、経由候補地点１４０４には、外部情報源１７１０から取得された表示文書データ１８０２に基づいて、当該地点の詳細情報が表示される。
【０２９２】
これによって、利用者が過去に参照した地点の情報を経由候補地点として提示できる。
【０２９３】
（第３実施例）
第３実施例は、運転計画立案支援装置１００が経路候補情報を含む運転計画情報を生成して、ナビゲーション装置１２０が運転計画情報に含まれる経路候補情報に基づいて、道案内する点が第１実施例及び第２実施例と異なる。
【０２９４】
なお、第３実施例の構成及び処理のうち、第１実施例及び第２実施例の構成及び処理と同じものは、同じ番号を付与し、説明を省略する。
【０２９５】
次に、運転計画立案支援装置１００が運転計画概要に基づいて経路候補を含む運転計画情報を生成する運転計画生成処理について、図２３を用いて説明する。図２３は、本発明の第３実施例の運転計画生成処理のフローチャートである。なお、図２３に示す経路候補を含む運転計画情報を生成する処理のうち、図１１に示す第１実施例の運転計画生成処理の処理と同じ処理は、同じ符号を付与し、説明を省略する。
【０２９６】
まず、地点情報準備範囲策定部１０８は、仮想的な出発地点から仮想的な目的地点に到達し得る複数の経路を探索し、探索された複数の経路を経路候補として取得する経路候補生成処理を実行する（２３０１）。
【０２９７】
なお、ステップ２３０１の処理の経路候補生成処理については、図２４で詳細を説明する。
【０２９８】
次に、地点候補選択部１０９は、ステップ２３０１の処理で選択された経路候補として選択された経路を構成するリンクに紐付けられる地点を取得する（２３０２）。
【０２９９】
具体的には、地点候補選択部１０９は、図６Ａに示す地点データ６２０に登録されたエントリのうち、リンクＩＤ６２６に登録されたリンクの識別子がステップ２３０１の処理で選択された経路候補として選択された経路を構成するリンクの識別子と一致するエントリを、ステップ２３０１の処理で選択された経路候補として選択された経路を構成するリンクに紐付けられる地点として取得する。
【０３００】
次に、運転計画情報生成部１１１は、ステップ１１０３の処理を実行し、外部記憶媒体出力部１０６は、ステップ１１０４の処理を実行して、運転計画生成処理を終了する。
【０３０１】
次に、ステップ２３０１の処理で実行される経路候補生成処理について、図２４を用いて説明する。図２４は、本発明の第３実施例の経路候補生成処理のフローチャートである。
【０３０２】
経路候補生成処理では、予め設定された最も妥当な探索条件（例えば、最短経路）に基づいて探索された経路を主経路とし、その他の複数の探索条件に基づいて探索された複数の経路を他経路とする。
【０３０３】
なお、経路候補生成処理では、探索された主経路及び他経路を含む経路候補を記憶する経路候補記憶領域、及び主経路と他経路との分岐点を記憶する分岐候補記憶領域を用いて処理が実行される。
【０３０４】
まず、地点情報準備範囲策定部１０８は、変数リンクＸに仮想的な目的地を代入する（２４０１）。
【０３０５】
次に、地点情報準備範囲策定部１０８は、主経路を探索するための条件に基づいて、変数リンクＸに代入された地点から仮想的な目的地までの主経路を探索する（２４０２）。
【０３０６】
次に、地点情報準備範囲策定部１０８は、他経路を探索するための条件に基づいて、変数リンクＸに代入された地点から仮想的な目的地までの他経路を探索する（２４０３）。
【０３０７】
次に、地点情報準備範囲策定部１０８は、ステップ２４０２の処理で探索された主経路及びステップ２４０３の処理で探索された他経路を経路候補記憶領域に記憶する（２４００４）。
【０３０８】
次に、地点情報準備範囲策定部１０８は、主経路及び他経路を比較して、主経路と他経路との分岐点を探索し、分岐点が探索された場合には、探索された分岐点を分岐候補記憶領域に記憶する（２４０５）。
【０３０９】
次に、地点情報準備範囲策定部１０８は、分岐候補記憶領域に分岐点が記憶されているか否かを判定する（２４０６）。具体的には、地点情報準備範囲策定部１０８は、分岐候補記憶領域に記憶されている分岐点の数がゼロであるか否かを判定する。
【０３１０】
ステップ２４０６の処理で、分岐候補記憶領域に記憶されている分岐点の数がゼロであると判定された場合、つまり、分岐候補記憶領域に分岐点が記憶されていないと判定された場合、経路候補生成処理を終了する。
【０３１１】
一方、ステップ２４０６の処理で、分岐候補記憶領域に記憶されている分岐点の数がゼロでないと判定された場合、つまり、分岐候補記憶領域に分岐点が記憶されていると判定された場合、分岐候補記憶領域に記憶されている分岐点の数が所定の値よりも大きいか否かを判定する（２４０７）。
【０３１２】
ステップ２４０７の処理で、分岐候補記憶領域に記憶されている分岐点の数が所定の値よりも大きいと判定された場合、経路候補生成処理を終了する。
【０３１３】
一方、ステップ２４０７の処理で、分岐候補記憶領域に記憶されている分岐点の数が所定の値以下であると判定された場合、分岐候補記憶領域に記憶されている分岐点から一の分岐点を選択して、選択された分岐点を変数リンクＸに代入して（２４０８）、ステップ２４０２の処理に戻る。
【０３１４】
なお、ステップ２４０８の処理では、地点情報準備範囲策定部１０８は、選択された分岐点を変数リンクＸに代入した後に、選択された分岐点を分岐候補記憶領域から削除する。
【０３１５】
これによって、運転計画立案支援装置１００は、利用者が運転計画に基づいてナビゲーション装置１２０を搭載した自動車を走行させる場合に、当該自動車が走行し得る経路を予め準備できる。
【０３１６】
なお、図２４に示す経路候補生成処理は一例であり、ナビゲーション装置１２０を搭載した自動車が走行し得る経路を予め準備できれば、如何なる方法を用いてもよい。
【０３１７】
運転計画立案支援装置１００によって生成される運転計画情報に含まれる経路候補データ２５００について、図２５を用いて説明する。図２５は、本発明の第３実施例の経路候補データ２５００の説明図である。
【０３１８】
経路候補データ２５００は、経路ＩＤ２５０１、番号２５０２、リンクＩＤ２５０３、及びメッシュコード２５０４を含む。
【０３１９】
経路ＩＤ２５０１には、経路候補生成処理によって探索された他経路の一意な識別子が登録される。番号２５０２には、経路ＩＤ２５０１に登録された識別子によって識別される経路において、リンクＩＤ２５０３に登録される識別子によって識別されるリンクが何番目に位置するかを示す情報が登録される。
【０３２０】
リンクＩＤ２５０３には、経路ＩＤ２５０１に登録された識別子によって識別される経路において、番号２５０２に登録された情報が示す位置に位置するリンクの一意な識別子が登録される。メッシュコード２５０４には、リンクＩＤ２５０３に登録された識別子によって識別されるリンクを含むメッシュの一意な識別子が登録される。
【０３２１】
ナビゲーション装置１２０によって実行される経由候補地点提示処理について、図２４を用いて説明する。図２６は、本発明の第３実施例の経由候補地点提示処理のフローチャートである。なお、図２６に示す経由候補地点提示処理のうち、図１６に示す第１実施例の経由候補地点提示処理と同じ処理は、同じ符号を付与し、説明を省略する。
【０３２２】
まず、状況判定部１２９は、ステップ１６０１の処理を実行して、分類コードの一覧を生成する。
【０３２３】
次に、経路探索部１３０は、現在位置から進行方向に位置する次の交差点に接続されるリンクを取得し、経路候補データ２５００を参照し、取得されたリンクを含む経路を探索する（２６０１）。そして、ステップ２６０１の処理で取得されたリンクを含む経路が探索された経路が経路候補データ２５００に登録された経路に存在する場合、当該経路を代替経路候補とする。
【０３２４】
ステップ２６０１の処理について具体的に説明する。
【０３２５】
まず、経路探索部１３０は、図５Ａに示すリンクデータ５０８を参照し、ステップ１６０１の処理で取得された現在位置から現在走行しているリンクを取得する。
【０３２６】
具体的には、経路探索部１３０は、ステップ１６０１の処理で取得された現在位置であるメッシュ及び座標を特定し、図５Ａに示すリンクデータ５０８に登録されたエントリのうち、特定されたメッシュ及び座標に一致するメッシュコード５０２に登録された識別子によって識別されるメッシュ及び形状５０５に登録される複数の座標のうちいずれかの座標が一致するエントリを選択する。
【０３２７】
そして、経路探索部１３０は、選択されたエントリに含まれるリンクＩＤ５０１に登録された識別子によって識別されるリンクを現在走行しているリンクとして取得する。
【０３２８】
次に、経路探索部１３０は、図５Ａに示すリンクデータ５０８を参照し、進行方向に基づいて、現在走行しているリンクに対応するエントリに含まれる始点ノード５０６又は終点ノード５０７に登録された識別子によって識別されるノードを、次の交差点として取得する。
【０３２９】
次に、経路探索部１３０は、図５Ｂに示すノードデータ５１０に登録されたエントリに含まれるノードＩＤ５１１に登録された識別子のうち、取得されたノードの識別子と一致するすべてのエントリを選択し、選択されたすべてのエントリに含まれる接続リンクＩＤ５１３に登録されるリンクの識別子を取得する。
【０３３０】
次に、経路探索部１３０は、取得されたリンクの識別子のうち、現在走行しているリンクの識別子以外のリンクの識別子を代替経路に含まれるリンクとして取得する。そして、経路探索部１３０は、図２５に示す経路候補データ２５００に登録されたエントリのうち、リンクＩＤ２５０３に登録されたリンクの識別子が取得された代替経路候補に含まれるリンクと一致するエントリを選択する。そして、経路探索部１３０は、選択されたエントリに含まれる経路ＩＤ２５０１に登録される経路の識別子を、代替経路候補を示す識別子として取得する。
【０３３１】
次に、計画策定部１３１は、ステップ２６０１の処理で選択された代替経路候補となる経路を構成するリンクに紐付けられる地点を取得する。そして、計画策定部１３１は、図１３Ｂに示す経由地候補情報１３１０を参照し、取得された地点の分類コードを取得する。そして、計画策定部１３１は、取得された地点の分類コードのうち、ステップ１６０１の処理で生成された分類コードの一覧のいずれかと一致する分類コードを含む地点を経由候補地点として取得する（２６０２）。
【０３３２】
次に、計画策定部１３１は、ステップ１６０４の処理を実行して、経由候補地点を図１４に示す案内画面に表示する。
【０３３３】
これによって、ナビゲーション装置１２０の処理負荷を軽減できるため、処理能力が不足しているナビゲーション装置１２０でも、道案内が可能となる。
【０３３４】
なお、本発明の第１実施例〜第３実施例で説明した実施例は、一例であり、本発明の構成又は処理手順には、各種の変形例があり得る。例えば、ナビゲーション装置１２０の動作制御部１２１の機能の一部を他の装置が備え、ナビゲーション装置１２０は、他の装置に備わる機能によって取得された結果を通信部１２８を介して取得してもよい。
【０３３５】
また、本発明の第１実施例〜第３実施例では、自動車に搭載されるナビゲーション装置１２０について説明したが、利用者が携帯して利用者を道案内するナビゲーション装置であってもよい。
【図面の簡単な説明】
【０３３６】
【図１】本発明の実施形態の運転計画立案システムの構成を示すブロック図である。
【図２】本発明の実施形態の運転計画立案システムによって実行される処理の説明図である。
【図３】本発明の実施形態の運転計画立案支援システムに備わる各装置の処理のフローチャートである。
【図４】本発明の第１実施例の運転計画立案システムのブロック図である。
【図５Ａ】本発明の第１実施例のリンクデータの説明図である。
【図５Ｂ】本発明の第１実施例のノードデータの説明図である。
【図６Ａ】本発明の第１実施例の地点データの説明図である。
【図６Ｂ】本発明の第１実施例の地方データの説明図である。
【図７】本発明の第１実施例の利用者情報の説明図である。
【図８】本発明の第１実施例の運転計画立案画面の説明図である。
【図９】本発明の実施形態の経路設定受付部による代表経路選択処理のフローチャートである。
【図１０】本発明の第１実施例の運転計画編集画面の説明図である。
【図１１】本発明の第１実施例の運転計画生成処理のフローチャートである。
【図１２】本発明の第１実施例の周辺リンク取得処理のフローチャートである。
【図１３Ａ】本発明の第１実施例の運転計画概要情報の説明図である。
【図１３Ｂ】本発明の第１実施例の経由地候補情報の説明図である。
【図１４】本発明の第１実施例のナビゲーション装置に備わる表示装置に表示される案内画面の説明図である。
【図１５】本発明の第１実施例の案内経路提示処理のフローチャートである。
【図１６】本発明の第１実施例の経由候補地点提示処理のフローチャートである。
【図１７】本発明の第２実施例の運転計画立案支援システムのブロック図である。
【図１８】本発明の第２実施例の外部情報表示処理の説明図である。
【図１９】本発明の第２実施例の利用者外部情報使用履歴データの説明図である。
【図２０】本発明の第２実施例の運転計画生成処理のフローチャートである。
【図２１Ａ】本発明の第２実施例の経由地候補情報の説明図である。
【図２１Ｂ】本発明の第２実施例の履歴地点参照情報の説明図である。
【図２２】本発明の第２実施例のナビゲーション装置に備わる表示装置に表示される案内画面の説明図である。な
【図２３】本発明の第３実施例の運転計画生成処理のフローチャートである。
【図２４】本発明の第３実施例の経路候補生成処理のフローチャートである。
【図２５】本発明の第３実施例の経路候補データの説明図である。
【図２６】本発明の第３実施例の経由候補地点提示処理のフローチャートである。
【符号の説明】
【０３３７】
１００ 運転計画立案支援装置
１０１ 動作制御部
１０２ 入力受付部
１０３ 地図データ記憶部
１０４ 利用者情報記憶部
１０５ 通信部
１０６ 外部記憶媒体出力部
１０７ 外部通信部
１０８ 地点情報準備範囲策定部
１０９ 地点候補選択部
１１０ 経路候補選択部
１１１ 運転計画情報生成部
１１２ 外部記憶媒体
１１３ 経路設定受付部
１２０ ナビゲーション装置
１２１ 動作制御部
１２２ 地図データ記憶部
１２３ 現在位置取得部
１２４ 入力受付部
１２５ 画像表示部
１２６ 音声出力部
１２７ 外部記憶媒体読取部
１２８ 通信部
１２９ 状況判定部
１３０ 経路探索部
１３１ 計画策定部
１３２ 提示情報制御部
１３３ ネットワーク
【技術分野】
【０００１】
本発明は、出発地から目的地までの経路を案内する経路案内方法に関し、特に、ナビゲーション装置が他の装置で生成された案内計画情報に基づいて経路を案内する経路案内方法に関する。
【背景技術】
【０００２】
自動車に搭載されて、目的地までの経路を案内するナビゲーションシステムが知られている。ナビゲーションシステムは、ＧＰＳ（Global Positioning System）衛星の電波を受信するＧＰＳ受信機及び車速センサ等を備え、ＧＰＳ受信機及び車速センサ等によって自動車の現在位置を特定する。
【０００３】
これによって、ナビゲーションシステムは、利用者によって設定された目的地までの経路等を利用者に提示できる。しかし、ナビゲーションシステムは、自動車に搭載されるために小型化されている。このため、利用者がナビゲーションシステムを操作しづらいという問題点があった。したがって、利用者が目的地又は経路等を事前に計画しても、計画した内容をナビゲーションシステムに入力することは利用者にとって困難であった。
【０００４】
この問題を解決するために、利用者が自動車に搭乗する前に運転の計画を立案することを支援する運転計画システムが知られている。利用者が自宅等で地図データ等を参照して運転の計画を運転計画システムに入力すると、運転計画システムは、入力された運転の計画を自動車に搭載されたナビゲーションシステムに転送する。
【０００５】
これによって、利用者は、ナビゲーションシステムをあまり操作することなく、ナビゲーションシステムに運転の計画を設定できる。
【０００６】
しかしながら、この運転計画システムでは、利用者が自動車に搭乗する前に運転の計画を細部まで立案しなければならない。このため、事前に運転の計画を立案することが煩わしいと感じる利用者にとって、この運転計画システムは、必ずしも有用でない。
【０００７】
また、事前に立案された運転の計画では予期しえない事態（渋滞又は店舗の休業等）が発生した場合には、利用者は、ナビゲーションシステムを操作して、立案された運転の計画を変更しなければならない。
【０００８】
そこで、運転の計画を柔軟に変更できるナビゲーション装置として、ナビゲーション装置が搭載された自動車の進行方向前方に存在する地点情報を次々と提示することによって運転中に目的地までの経路を変更できるナビゲーション装置が知られている（特許文献１参照）。また、曖昧な目的地をナビゲーション装置に設定して、曖昧な目的地が設定されたままナビゲーション装置が搭載された自動車が走行すると徐々に目的地を具体化するナビゲーション装置も知られている（特許文献２参照）。
【特許文献１】特開２００７―２８５８８３号公報
【特許文献２】特開２００７―２８５８７０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１及び特許文献２に記載されたナビゲーション装置において、運転の計画が頻繁に変更されると、事前に立案された運転の計画を利用できる区間が短くなってしまい、事前に立案された運転の計画がほとんど利用できなくなってしまう。
【００１０】
本発明は上記した問題を解決するためになされたものであり、利用者が事前に運転の計画を細部まで立案しなくても、運転の計画を細部まで立案した場合と同様の案内機能を提供する経路案内方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の代表的な一例を示せば、以下の通りである。出発地から目的地までの経路を利用者に案内するナビゲーション装置、及び利用者が立ち寄る候補となる経由候補地点を前記ナビゲーション装置が提示するために用いる案内計画情報を生成する案内計画生成装置を備える計算機システムにおいて、前記案内計画生成装置は、前記経由候補地点に関する情報を記憶し、前記ナビゲーション装置の移動範囲を算出し、前記経由候補地点に関する情報を参照し、前記算出された移動範囲に存在する経由候補地点を選択し、前記ナビゲーション装置が、前記選択された経由候補地点を利用者に提示するか否かを現在時刻に基づいて判定するための判定情報を生成し、前記移動範囲に存在する経由候補地点、及び前記各経由候補地点の判定情報を含む前記案内計画情報を生成し、前記ナビゲーション装置は、前記案内計画生成装置によって生成された案内計画情報を取得し、前記取得された案内計画情報に含まれる経由候補地点のうち、前記ナビゲーション装置の現在位置から所定の範囲内に存在する経由候補地点を、提示し得る経由候補地点として選択し、前記選択された提示し得る経由候補地点の判定情報が、現在時刻に適合する経由候補地点を、提示経由候補地点として取得し、前記取得された提示経由候補地点、及び前記現在位置から前記提示経由候補地点までの経路を利用者に提示することを特徴とする。
【発明の効果】
【００１２】
本発明の一形態によると、利用者は、案内計画生成装置によって生成された案内計画情報に基づいて、移動時に案内計画を柔軟に変更できる。
【発明を実施するための最良の形態】
【００１３】
本発明の実施形態を、図１〜図３を用いて説明する。
【００１４】
図１は、本発明の実施形態の運転計画立案システムの構成を示すブロック図である。
【００１５】
運転計画立案システムは、運転計画立案支援装置１００及びナビゲーション装置１２０を備える。ナビゲーション装置１２０は、出発地から目的地までの経路等を案内する装置である。運転計画立案支援装置１００は、利用者が立ち寄る候補となる経由候補地点を事前に運転計画情報（案内計画情報）を立案することを支援するための装置である。
【００１６】
運転計画立案支援装置１００は、動作制御部１０１、入力受付部１０２、地図データ記憶部１０３、利用者情報記憶部１０４、通信部１０５、外部記憶媒体出力部１０６、及び外部通信部１０７を備える。
【００１７】
動作制御部１０１は、図示しないＣＰＵ及びメモリ等から構成され、運転計画立案支援装置１００の動作の制御を司る。
【００１８】
入力受付部１０２は、利用者が図示しないディスプレイ等に表示された情報（例えば、地図データ等）を参照して、運転計画概要（出発日時、出発地方、目的地方、及び運転の目的等）の入力を受け付ける。また、出発地方及び目的地方は、出発地点又は目的地点を含む大まかな地方である。例えば、出発地方及び目的地方は、都道府県単位又は市町村単位である。
【００１９】
経路設定受付部１１３は、入力受付部１０２によって受け付けられた運転計画概要から出発地点及び目的地点を設定し、設定された出発地点から目的地点までの経路を設定する。
【００２０】
地図データ記憶部１０３は、例えば店舗等の地点情報を記憶するＤＶＤ、フラッシュメモリ又はＨＤＤ（Hard Disk Drive）等の記憶媒体である。利用者情報記憶部１０４は、利用者が過去に入力した運転計画概要等の利用情報を書き込み可能なフラッシュメモリ又はＨＤＤ等の記憶媒体である。
【００２１】
通信部１０５は、運転計画立案支援装置１００をネットワーク１３３を介してナビゲーション装置１２０に接続するためのインタフェースである。外部記憶媒体出力部１０６は、生成された運転計画情報を外部記憶媒体１１２に出力するためのインタフェースである。
【００２２】
外部通信部１０７は、運転計画立案支援装置１００の外部に存在する情報源（サーバ等）に、運転計画立案支援装置１００を接続するためのインタフェースである。
【００２３】
動作制御部１０１は、地点情報準備範囲策定部１０８、地点候補選択部１０９、経路候補選択部１１０、及び運転計画情報生成部１１１を備える。
【００２４】
地点情報準備範囲策定部１０８は、経路設定受付部１１３によって設定された経路から利用者が移動可能な範囲に存在するすべての経路を取得する。
【００２５】
地点候補選択部１０９は、外部通信部１０７を介して接続される情報源又は地図データ記憶部１０３に記憶された地点情報を参照し、地点情報準備範囲策定部１０８によって取得された走行可能な範囲の経路に関連する地点情報を選択する。そして、地点候補選択部１０９は、利用者情報記憶部１０４に記憶された利用者情報を参照し、選択された走行可能な範囲の経路に関連する地点情報から、利用者との関連度の高い地点情報を地点候補として選択する。
【００２６】
経路候補選択部１１０は、出発地点から、地点候補選択部１０９によって選択された地点情報を通って、目的地点までの経路を選択する。なお、運転計画立案支援装置１００は、経路候補選択部１１０を備えなくてもよい。
【００２７】
運転計画情報生成部１１１は、地点候補選択部１０９によって選択された地点情報と、地点情報準備範囲策定部１０８によって取得された経路とを紐付けて、紐付けた運転計画情報（案内計画情報）を、外部記憶媒体１１２又は通信部１０５を介してナビゲーション装置１２０に入力可能な形式に変換する。
【００２８】
なお、動作制御部１０１が備える構成は、ＣＰＵが所定のプログラムを実行することによって実現されるが、他の方法（例えば、ハードウェア）によって実装されてもよい。
【００２９】
なお、通信部１０５及び外部記憶媒体出力部１０６は運転計画情報をナビゲーション装置１２０に入力するための手段であるが、運転計画立案支援装置１００は、通信部１０５及び外部記憶媒体出力部１０６の両方を備える必要はなく、少なくとも一方を備えていればよい。
【００３０】
次に、ナビゲーション装置１２０について説明する。
【００３１】
ナビゲーション装置１２０は、動作制御部１２１、地図データ記憶部１２２、現在位置取得部１２３、入力受付部１２４、画像表示部１２５、音声出力部１２６、及び外部記憶媒体読取部１２７を備える。
【００３２】
動作制御部１２１は、図示しないＣＰＵ及びメモリ等から構成され、ナビゲーション装置１２０の動作の制御を司る。地図データ記憶部１２２は、地図データを記憶するＤＶＤ、フラッシュメモリ又はＨＤＤ（Hard Disk Drive）等の記憶媒体である。現在位置取得部１２３は、ナビゲーション装置１２０が搭載された自動車の現在位置を取得する。
【００３３】
入力受付部１２４は、ナビゲーション装置１２０に備わる画像表示部１２５に設けられたタッチパネル又はナビゲーション装置１２０に備わるスイッチ等から利用者の指示の入力を受け付けるインタフェースである。画像表示部１２５は、画像を表示可能なディスプレイ等である。音声出力部１２６は、音声を出力可能なスピーカ等である。
【００３４】
外部記憶媒体読取部１２７は、外部記憶媒体１１２に接続可能であって、外部記憶媒体１１２に記憶された情報を読み取る。通信部１２８は、ナビゲーション装置１２０をネットワーク１３３を介して運転計画立案支援装置１００に接続するためのインタフェースである。
【００３５】
動作制御部１２１は、状況判定部１２９、経路探索部１３０、計画策定部１３１、及び提示情報制御部１３２を備える。
【００３６】
状況判定部１２９は、現在位置及び現在日時等の現在の状況を特定する。経路探索部１３０は、二つの地点間の経路を予め設定された基準に基づいて選択する。予め設定された基準には、例えば、最も到着時間の短い経路を選択する「最速」基準、最も距離が短い経路を選択する「最短」基準、又は最も経費が安くすむ経路を選択「最安」基準がある。
【００３７】
計画策定部１３１は、状況判定部１２９によって特定された現在の状況に一致する地点情報を選択する。提示情報制御部１３２は、経路探索部１３０によって選択された経路及び計画策定部１３１によって地点情報等の画像又は音声を、画像表示部１２５又は音声出力部１２６に出力する。
【００３８】
なお、動作制御部１２１が備える構成は、ＣＰＵが所定のプログラムを実行することによって実現されるが、他の方法（例えば、ハードウェア）によって実装されてもよい。
【００３９】
なお、通信部１２８及び外部記憶媒体読取部１２７は運転計画情報をナビゲーション装置１２０に入力するための手段であるが、ナビゲーション装置１２０は、通信部１２８及び外部記憶媒体読取部１２７の両方を備える必要はなく、少なくとも一方を備えていればよい。
【００４０】
図２は、本発明の実施形態の運転計画立案システムによって実行される処理の説明図である。
【００４１】
まず、利用者は、ナビゲーション装置１２０が搭載される自動車の外（例えば、自宅又は店舗等）にある運転計画立案支援装置１００に備わる入力受付部１０２に対して、運転計画の概要を入力する。運転計画概要は、例えば、出発日時、出発地方、目的地方、及び目的等を含む。
【００４２】
経路設定受付部１１３は、入力された運転計画概要に含まれる出発地方及び目的地方から仮想的な出発地点及び仮想的な目的地点を特定する。そして、経路設定受付部１１３は、特定された仮想的な出発地点から仮想的な目的地点までの経路を設定する。
【００４３】
地点情報準備範囲策定部１０８は、特定された経路から所定の範囲にあるすべての経路を取得し、利用者が走行可能な範囲を特定する。
【００４４】
地点候補選択部１０９は、地図データ記憶部１０３に記憶された地点情報のうち、地点情報準備範囲策定部１０８によって特定された走行可能範囲に位置する地点情報を、運転計画に必要な地点情報の候補として、選択する。
【００４５】
経路候補選択部１１０は、仮想的な出発地点から、地点候補選択部１０９によって選択された地点情報を通って、仮想的な目的地点までのすべての経路を、運転計画に必要な経路の候補として、選択する。
【００４６】
そして、地点候補選択部１０９及び経路候補選択部１１０は、地点情報の候補及び経路の候補を運転計画情報生成部１１１に出力する。
【００４７】
運転計画情報生成部１１１は、地点情報の候補及び経路の候補を紐付けて、運転計画情報を生成する。そして、運転計画情報生成部１１１は、生成した運転計画情報を外部記憶媒体出力部１０６を介して、外部記憶媒体１１２に出力し、生成した運転計画情報を外部記憶媒体１１２に記憶させる。
【００４８】
外部記憶媒体１１２に記憶された運転計画情報には、利用者によって入力された運転計画概要、地点候補選択部１０９によって選択された地点情報、経路候補選択部１１０によって選択された経路、地点候補選択部１０９によって選択された地点情報の詳細情報、及び利用者が過去に確認した地点情報等から生成される利用者特徴情報等が含まれる。
【００４９】
利用者は、運転計画情報が記憶された外部記憶媒体１１２を持ち運び、外部記憶媒体１１２を、ナビゲーション装置１２０に備わる外部記憶媒体読取部１２７に接続する。動作制御部１２１は、外部記憶媒体読取部１２７に接続された外部記憶媒体１１２に記憶された運転計画情報を読み取るので、ナビゲーション装置１２０は、運転計画情報を利用可能になる。
【００５０】
なお、動作制御部１２１は、利用者に外部記憶媒体１１２に記憶された運転計画情報を読み取ってもよいか否かを確認してから、外部記憶媒体１１２に記憶された運転計画情報を読み取ってもよい。また、動作制御部１２１は、外部記憶媒体１１２が外部記憶媒体読取部１２７に接続されたことを検出した場合に、外部記憶媒体１１２に記憶された運転計画情報を読み取ってもよい。
【００５１】
計画策定部１３１は、読み取られた運転計画情報を利用して、提示すべき地点情報を選択する。具体的には、計画策定部１３１は、運転計画情報に含まれる地点情報のうち、状況判定部１２９によって取得される現在の状況を示す状況コードに対応する地点情報を、利用者に提示する地点情報として、選択する。
【００５２】
次に、計画策定部１３１は、現在位置から選択された利用者に提示する地点情報が示す地点までの経路を経路探索部１３０に探索させて、経路探索部１３０が探索した経路を取得する。
【００５３】
そして、計画策定部１３１は、利用者に提示する地点情報として選択された地点情報と、経路探索部１３０によって探索された経路とを組み合わせることによって、利用者に提示する情報を生成し、生成された利用者に提示する情報を提示情報制御部１３２に出力する。
【００５４】
提示情報制御部１３２は、入力された利用者に提示する情報を提示するのに適したタイミングで、利用者に提示する情報を画像表示部１２５に表示することによって、利用者に提示する。
【００５５】
これによって、利用者は、現在の状況で到達できる地点の情報を確認することができ、事前に立案した運転計画が細部まで立案されていない場合であっても、事前に立案した運転計画が細部まで立案された場合と同じくらい詳細な運転計画を利用できる。
【００５６】
なお、ナビゲーション装置１２０は、公知の道案内機能を備えてもよい。この場合、ナビゲーション装置１２０は、運転計画情報が入力されていない場合、公知の道案内機能で動作し、運転計画情報が入力された場合、本発明の運転計画情報に基づく道案内を動作する。これによって、利用者が運転計画を事前に立案していない場合であっても、ナビゲーション装置１２０は、公知の道案内機能を利用者に提供できる。
【００５７】
なお、ナビゲーション装置１２０は、公知の道案内機能で運転計画情報を利用してもよい。これによって、ナビゲーション装置１２０は、ナビゲーション装置１２０が保持する地点情報だけでなく、運転計画立案支援装置１００が保持する地点情報も利用者に提供できる。
【００５８】
図３は、本発明の実施形態の運転計画立案支援システムに備わる各装置の処理のフローチャートである。運転計画立案支援装置１００は、利用者から運転計画概要の入力を受け付けた場合に、運転計画情報を生成する処理を実行する。
【００５９】
まず、入力受付部１０２は、利用者の操作によって入力された運転計画概要の入力を受け付ける（３００１）。運転計画概要は、出発地方、目的地方、出発日時、及び目的を含む。運転計画概要は、運転計画に関する情報であって、出発地点及び目的地点が指定される具体的な運転計画でなくてもよい。
【００６０】
次に、経路設定受付部１１３は、入力された運転計画概要に含まれる出発地方及び目的地方から仮想的な出発地点及び仮想的な目的地点を特定し、特定された仮想的な出発地点から仮想的な目的地点までの経路を探索し、探索された経路を代表経路に設定する（３００２）。
【００６１】
具体的には、地方ごとに中心地点又は代表地点が予め設定されており、経路設定受付部１１３は、入力された出発地方及び目的地方に対応する中心地点又は代表地点を特定し、特定された出発地方及び目的地方に対応する中心地点又は代表地点を、仮想的な出発地点及び仮想的な目的地点とする。
【００６２】
なお、入力された運転計画概要に出発地方が含まれない場合には、経路設定受付部１１３は、予め設定されている利用者の自宅の住所を仮想的な出発地点としてもよい。
【００６３】
次に、地点情報準備範囲策定部１０８は、ナビゲーション装置１２０を搭載する自動車がステップ３００２の処理で設定された代表経路から外れて走行し得る範囲を推定する（３００３）。
【００６４】
具体的には、地点情報準備範囲策定部１０８は、仮想的な出発地点から仮想的な目的地点までのあらゆる経路を探索して、探索された経路を走行範囲としてもよいし、代表経路から所定の範囲を走行範囲としてもよい。走行範囲の推定方法は、代表経路から極端に遠方の地点を含まなければ、如何なる方法を用いてもよい。
【００６５】
次に、経路候補選択部１１０は、仮想的な出発地点から仮想的な目的地点までのすべての経路のうち、ステップ３００３の処理で推定された走行範囲内に存在する経路を、走行経路候補として選択する（３００４）。
【００６６】
次に、地点候補選択部１０９は、走行範囲に存在する地点情報を、ナビゲーション装置１２０が経由可能な地点情報候補として選択する（３００５）。
【００６７】
次に、運転計画情報生成部１１１は、ステップ３００４の処理で選択された走行経路候補及びステップ３００５の処理で選択された地点情報候補に、分類コードを付与し、ナビゲーション装置１２０が利用しやすい形式に変換することによって、運転計画情報を生成する（３００６）。
【００６８】
そして、運転計画立案支援装置１００は、ステップ３００６の処理で生成された運転計画情報を外部記憶媒体出力部１０６から外部記憶媒体１１２に出力する（３００７）。
【００６９】
利用者が運転計画情報を記憶した外部記憶媒体１１２を持ち運び、ナビゲーション装置１２０に外部記憶媒体１１２を接続することによって、ナビゲーション装置１２０が運転計画情報を利用できる。
【００７０】
利用者が外部記憶媒体１１２を外部記憶媒体読取部１２７に接続すると、ナビゲーション装置１２０は、外部記憶媒体１１２に記憶された運転計画情報を読み取る（３００８）。そして、ナビゲーション装置１２０は、読み取った運転計画情報に含まれる代表経路に基づいて、経路の案内を開始する。また、ナビゲーション装置１２０は、経路の案内を開始するとともに、運転計画情報に含まれる地点情報候補の情報を提示する。
【００７１】
状況判定部１２９は、ナビゲーション装置１２０を搭載した自動車の現在位置、及び現在の時刻等を取得し、取得された現在位置及び現在の時刻等から、現在の状況を示す状況コードを算出する（３００９）。
【００７２】
次に、計画策定部１３１は、ステップ３００９の処理で算出された状況コードから、利用者が現在必要とする情報の種別を選択し、選択した種別を示す種別コードを取得する。そして、計画策定部１３１は、運転計画情報に含まれる走行経路候補及び地点情報候補のうち、取得された種別コードに対応する分類コードが付与された走行経路候補及び地点情報候補（経由地）を選択する（３０１０）。
【００７３】
なお、計画策定部１３１が種別コードを取得する方法としては、状況コードと種別コードとが予め対応付けられ、計画策定部１３１は、ステップ３００９の処理で算出された状況コードに対応付けられた種別コードを取得する方法がある。また、状況コードから種別コードが特定できれば、如何なる方法を用いてもよい。
【００７４】
次に、経路探索部１３０は、ナビゲーション装置１２０を搭載した自動車が現在走行している経路から、ステップ３０１０の処理で選択された走行経路候補及び地点情報候補（経由地）を経由する経路を探索する（３０１１）。
【００７５】
具体的には、走行経路候補を経由する経路を探索する場合には、経路探索部１３０は、現在位置から走行経路候補である経路の始点までの経路を探索する。また、地点情報候補を経由する経路を探索する場合には、経路探索部１３０は、現在位置から地点情報候補である地点情報までの経路を探索する。
【００７６】
次に、計画策定部１３１は、ステップ３０１０の処理で選択された経由地及びステップ３０１１の処理で探索された経由地を経由する経路を運転計画候補とし、運転計画候補の特徴を示す運転計画詳細情報を生成する（３０１２）。
【００７７】
運転計画候補の特徴は、利用者が運転計画を変更するか否かを判定するための情報であり、例えば、各経由地までの所要時間、距離、費用、又は経由地の地点情報等を含む。
【００７８】
なお、運転計画詳細情報は、すべての経由地に対して生成される必要はなく、現在位置から必要となり得る経由地に対してのみ生成されるようにしてもよい。例えば、計画策定部１３１は、現在位置の次の交差点から侵入できる経路上にある経由地に対して、運転計画詳細情報を生成する。
【００７９】
これによって、ナビゲーション装置１２０の処理負荷を軽減でき、運転計画詳細情報を生成する処理に要する時間を短縮できる。
【００８０】
次に、提示情報制御部１３２は、運転計画詳細情報及び運転計画詳細情報を生成した経由地へ進入するための進入経路を画像表示部１２５等に提示して、運転計画が変更可能であることを通知する（３０１３）。
【００８１】
次に、計画策定部１３１は、現在位置を取得し、取得された現在位置が進入経路上にあるか否かを判定することによって、進路変更があったか否かを判定する（３０１４）。
【００８２】
ステップ３０１４の処理で、現在位置が進入経路上にあると判定された場合、つまり進路変更があったと判定された場合、計画策定部１３１は、運転計画の変更を受け付け、変更された運転計画に基づく案内を開始するためにステップ３００９の処理に戻る。
【００８３】
一方、ステップ３０１４の処理で、現在位置が進入経路上にないと判定された場合、つまり進路変更がないと判定された場合、ステップ３００９の処理に戻る。
【００８４】
以上の処理が繰り返し実行されることによって、利用者は運転計画を随時変更できる。
【００８５】
したがって、利用者が運転計画立案支援装置１００を介して立案した運転計画が曖昧であっても、運転計画立案支援装置１００は、ナビゲーション装置１２０を搭載した自動車の位置する地点で発生し得るあらゆる状況に対応できる情報を準備できる。
【００８６】
また、ナビゲーション装置１２０は、運転計画詳細情報を利用者に提示するため、利用者は十分な判断材料に基づいて、運転計画を変更するか否かを判定できる。
【００８７】
（第１実施例）
次に、本発明の第１実施例を図４〜図１６を用いて説明する。実施例１の運転計画立案システムは、運転計画立案支援装置１００によって生成された運転計画情報は、外部記憶媒体１１２を介してナビゲーション装置１２０に転送されるシステムである。
【００８８】
図４は、本発明の第１実施例の運転計画立案システムのブロック図である。
【００８９】
運転計画立案システムは、運転計画立案支援装置１００及びナビゲーション装置１２０を備える。
【００９０】
まず、運転計画立案支援装置１００について説明する。
【００９１】
運転計画立案支援装置１００は、入力装置４０１、出力装置４０２、記憶装置４０３、ＣＰＵ４０５、メモリ４０６、及び外部インタフェース（Ｉ／Ｆ）４０７を備える。
【００９２】
入力装置４０１は、例えば、マウス及びキーボード等であり、出力装置４０２は、例えば、ディスプレイである。利用者は、出力装置４０２に表示された表示内容を見て、入力装置４０１を介して、運転計画の概要を運転計画立案支援装置１００に入力する。よって、入力受付部１０２は、入力装置４０１及び出力装置４０２から構成される。
【００９３】
記憶装置４０３には、地図データ及び利用者情報が記憶される。よって、記憶装置４０３は、地図データ記憶部１０３及び利用者情報記憶部１０４の機能を備える。
【００９４】
なお、本実施例では、一台の記憶装置４０３が地図データ記憶部１０３及び利用者情報記憶部１０４の機能を備えるとしたが、複数台の記憶装置４０３が地図データ記憶部１０３及び利用者情報記憶部１０４の機能を備えてもよい。これによって、利用者が変わる場合に、利用者情報記憶部１０４の機能を備える記憶装置４０３のみを交換すればよい。
【００９５】
なお、利用者情報記憶部１０４の機能を備える記憶装置４０３は、書き込み可能な記憶装置（例えば、ＨＤＤ等）でなければならない。一方、地図データ記憶部１０３の機能を備える記憶装置４０３は、読み出ししか必要ないので、書き込み不可能な記憶装置（例えば、ＤＶＤドライブ）であってもよい。
【００９６】
メモリ４０６には、動作制御部１０１を構成する地点情報準備範囲策定部１０８、地点候補選択部１０９、経路候補選択部１１０、運転計画情報生成部１１１、及び経路設定受付部１１３の機能を実現する各種プログラムが記憶される。ＣＰＵ４０５は、メモリ４０６に記憶された各種プログラムを実行する。よって、ＣＰＵ４０５及びメモリ４０６は、動作制御部１０１の機能を備える。
【００９７】
外部Ｉ／Ｆ４０７は、外部記憶媒体１１２に接続可能なインタフェース（例えば、ＵＳＢポート）であり、外部記憶媒体出力部１０６の機能を備える。
【００９８】
なお、外部記憶媒体出力部１０６は、外部記憶媒体１１２に接続可能な外部Ｉ／Ｆ４０７によって実現されるとしたが、外部記憶媒体出力部１０６は、ＣＤ−Ｒ等の外部記憶媒体１１２にデータを直接書き込み可能な装置によっても実現できる。また、外部記憶媒体出力部１０６は、運転計画立案支援装置１００が外部記憶媒体１１２に書き込み可能な装置に接続されることによっても実現できる。
【００９９】
このように、外部記憶媒体出力部１０６は、ナビゲーション装置１２０が読み取り可能な形式で情報を出力可能であれば、どのような方法で実現してもよい。
【０１００】
次に、ナビゲーション装置１２０について説明する。第１実施例のナビゲーション装置１２０は、自動車に搭載される計算機である。
【０１０１】
ナビゲーション装置１２０は、ＣＰＵ４１１、メモリ４１２、外部インタフェース（Ｉ／Ｆ）４１３、入力装置４１４、表示装置４１５、スピーカ４１６、記憶装置４１７、及びＧＰＳ受信機４１８を備える。
【０１０２】
入力装置４１４は、ボタン及びキーボードの少なくとも一方から構成され、入力受付部１２４の機能を備える。表示装置４１５は、液晶ディスプレイ等であり、画像表示部１２５の機能を備える。
【０１０３】
なお、表示装置４１５のディスプレイがタッチパネルによって構成されている場合、表示装置４１５は、入力受付部１２４及び画像表示部１２５の機能を備える。
【０１０４】
スピーカ４１６は、例えば、自動車に搭載されているスピーカであり、音声出力部１２６の機能を備える。
【０１０５】
メモリ４１２には、動作制御部１２１を構成する状況判定部１２９、経路探索部１３０、計画策定部１３１、及び提示情報制御部１３２の機能を実現する各種プログラムが記憶される。ＣＰＵ４１１は、メモリ４１２に記憶された各種プログラムを実行する。よって、ＣＰＵ４１１及びメモリ４１２は、動作制御部１２１の機能を備える。
【０１０６】
記憶装置４１７には地図データが記憶されるので、記憶装置４１７は、地図データ記憶部１２２の機能を備える。また、記憶装置４１７は、書き込み可能な装置（例えば、ＨＤＤ等）であってもよいし、書き込み不可能な装置（例えば、ＤＶＤドライブ等）であってもよい。
【０１０７】
外部Ｉ／Ｆ４１３は、外部記憶媒体１１２に接続可能なインタフェース（例えば、ＵＳＢポート）であり、外部記憶媒体読取部１２７の機能を備える。外部記憶媒体読取部１２７は、外部記憶媒体出力部１０６によって外部記憶媒体１１２に出力された情報を読み取り可能であれば、どのような方法で実現されてもよい。
【０１０８】
ＧＰＳ受信機４１８は、現在位置を測位可能な装置であって、現在位置取得部１２３の機能を備える。
【０１０９】
記憶装置４０３及び４１７に記憶される地図データは、リンクデータ５０８（図５Ａ参照）、ノードデータ５１０（図５Ｂ参照）、地点データ６２０（図６Ａ参照）、及び地方データ６３１（図６Ｂ参照）を含む。
【０１１０】
地図データでは、交差点を意味するノード、及びノードから次のノードまでの間の道路を意味するリンクを用いて道路を表す。
【０１１１】
なお、地図データの地図は、矩形のメッシュによって分割されている。複数のメッシュに跨る道路は、メッシュの境界に仮想的なノードが配置されることによって、複数のリンクに分割される。これによって、各リンクは、いずれか一つのメッシュの領域に含まれる。
【０１１２】
図５Ａは、本発明の第１実施例のリンクデータ５０８の説明図である。
【０１１３】
リンクデータ５０８は、リンクに関する情報を示す表形式のデータであり、リンクＩＤ５０１、メッシュコード５０２、幅員５０３、種別５０４、形状５０５、始点ノード５０６、及び終点ノード５０７を含む。
【０１１４】
リンクＩＤ５０１には、リンクの一意な識別子が登録される。リンクデータ５０８は、一つのエントリにリンクＩＤ５０１に登録される識別子によって識別されるリンクに関する情報が登録される。
【０１１５】
メッシュコード５０２には、リンクＩＤ５０１に登録された識別子によって識別されるリンクを含むメッシュの一意な識別子が登録される。メッシュコード５０２にリンクを含むメッシュの識別子が登録されていることによって、例えば、ナビゲーション装置１２０が現在位置付近の道路を探索する場合に、現在位置のメッシュに含まれるリンクを探索すればよいので、現在位置付近の道路を高速に探索できるようになる。
【０１１６】
幅員５０３には、リンクＩＤ５０１に登録された識別子によって識別されるリンクの道幅を特定可能な数値が登録される。種別５０４には、リンクＩＤ５０１に登録された識別子によって識別されるリンクの道路の種別が登録される。道路の種別には、例えば、高速道路、私道、及び国道等がある。
【０１１７】
形状５０５には、リンクＩＤ５０１に登録された識別子によって識別されるリンクの形状を表す座標点の列が登録される。なお、運転計画立案支援装置１００及びナビゲーション装置１２０は、形状５０５に登録された座標点の列をポリラインによって描画することによって道路の画像を生成できる。
【０１１８】
始点ノード５０６には、リンクＩＤ５０１に登録された識別子によって識別されるリンクの一方の端点であるノードの識別子が登録される。終点ノード５０７には、リンクＩＤ５０１に登録された識別子によって識別されるリンクの他方の端点であるノードの識別子が登録される。始点ノード５０６及び終点ノード５０７に登録されたノードの識別子は、経路探索時に使用される。
【０１１９】
次に、ノードデータ５１０について図５Ｂを用いて説明する。図５Ｂは、本発明の第１実施例のノードデータ５１０の説明図である。
【０１２０】
ノードデータ５１０は、ノードとリンクとの関係を示すデータである。
【０１２１】
ノードデータ５１０は、ノードＩＤ５１１及び接続リンクＩＤ５１３を含む。ノードＩＤ５１１には、ノードの一意な識別子が登録される。接続リンクＩＤ５１３には、ノードＩＤ５１１に登録された識別子によって識別されるノードに接続される一つのリンクが登録される。
【０１２２】
あるノードの識別子でノードデータ５１０が検索された場合、このノードに接続されているすべてのリンクの識別子が取得される。そして、取得されたリンクの識別子でリンクデータ５０８が検索された場合、取得されたリンクの端点であるノードの識別子が取得される。この手順が繰り返されることによって、あるリンクから他のリンクまでの経路が探索できる。
【０１２３】
なお、図５Ａに示すリンクデータ５０８及び図５Ｂに示すノードデータ５１０は、一例であり、道路の画像の生成、及び経路探索が可能であれば、どのようなデータを用いてもよい。
【０１２４】
次に、地点データ６２０について図６Ａを用いて説明する。図６Ａは、本発明の第１実施例の地点データ６２０の説明図である。
【０１２５】
地点データ６２０には、経由地の候補又は目的地の候補となり得る地点に関する情報が登録される。
【０１２６】
地点データ６２０は、地点ＩＤ６２１、カテゴリ６２２、名称６２３、メッシュコード６２４、座標６２５、及びリンクＩＤ６２６を含む。
【０１２７】
地点ＩＤ６２１には、地点の一意な識別子が登録される。カテゴリ６２２には。地点ＩＤ６２１に登録された識別子によって識別される地点のカテゴリが登録される。例えば、カテゴリ６２２には、各地点で提供される商品又はサービスの種類（旅館業及び小売業等）が登録される。名称６２３には、地点ＩＤ６２１に登録された識別子によって識別される地点の名称が登録される。
【０１２８】
メッシュコード６２４には、地点ＩＤ６２１に登録された識別子によって識別される地点を含むメッシュの一意な識別子が登録される。座標６２５には、メッシュコード６２４に登録された識別子によって識別されるメッシュにおいて、地点ＩＤ６２１に登録された識別子によって識別される地点が位置する座標が登録される。リンクＩＤ６２６には、地点ＩＤ６２１に登録された識別子によって識別される地点に進入可能なリンクの一意な識別子が登録される。
【０１２９】
次に、地方データ６３１について図６Ｂを用いて説明する。図６Ｂは、本発明の第１実施例の地方データ６３１の説明図である。
【０１３０】
地方データ６３１は、地方ＩＤ６２７、名称６２８、メッシュコード６２９、及び座標６３０を含む。
【０１３１】
地方ＩＤ６２７には、地方の一意な識別子が登録される。名称６２８には、地方ＩＤ６２７に登録された識別子によって識別される地方の名称が登録される。メッシュコード６２９には、地方ＩＤ６２７に登録された識別子によって識別される地方の代表地点を含むメッシュの一意な識別子が登録される。座標６３０には、メッシュコード６２９に登録された識別子によって識別されるメッシュにおいて、地方ＩＤ６２７に登録された識別子によって識別される地方の代表地点が位置する座標が登録される。
【０１３２】
なお、図６Ａに示す地点データ６２０及び図６Ｂに示す地方データ６３１は、一例であり、画面表示及び音声提示等に用いる詳細テキスト、及び検索に用いるキーワード列、及び各地点の営業時間等を含んでもよい。
【０１３３】
次に、運転計画立案支援装置１００の記憶装置４０３に記憶される利用者情報７１０について、図７を用いて説明する。図７は、本発明の第１実施例の利用者情報７１０の説明図である。
【０１３４】
利用者情報７１０には、各地点が利用者によって最後に参照された年月日及び各地点が利用者によって参照された回数が登録される。
【０１３５】
利用者情報７１０は、地点ＩＤ７１１、カテゴリ７１２、メッシュコード７１３、座標７１４、最終参照７１５、及び参照回数７１６を含む。
【０１３６】
地点ＩＤ７１１、カテゴリ７１２、メッシュコード７１３、及び座標７１４は、図６Ａに示す地点データ６２０に含まれる地点ＩＤ６２１、カテゴリ６２２、名称６２３、及びメッシュコード６２４と同じであるので、説明を省略する。
【０１３７】
最終参照７１５には、地点ＩＤ７１１に登録された識別子によって識別される地点が利用者によって最後に参照された年月日が登録される。参照回数７１６には、地点ＩＤ７１１に登録された識別子によって識別される地点が利用者によって参照された回数が登録される。
【０１３８】
なお、本実施例の利用者情報７１０は、カテゴリ７１２、メッシュコード７１３、及び座標７１４を含むので、運転計画立案支援装置１００は、地点データ６２０を参照しなくとも、カテゴリ７１２、メッシュコード７１３、及び座標７１４に登録された情報を取得できるため、高速な処理が可能となる。
【０１３９】
また、記憶装置４０３の容量が小さい場合には、利用者情報７１０は、カテゴリ７１２、メッシュコード７１３、及び座標７１４を含まなくてもよい。この場合、運転計画立案支援装置１００は、カテゴリ７１２、メッシュコード７１３、及び座標７１４に登録された情報が必要となった場合には、地点データ６２０を参照して、カテゴリ６２２、メッシュコード６２４、及び座標６２５に登録された情報を取得する。
【０１４０】
なお、最終参照７１５及び参照回数７１６は、地点ＩＤ７１１に登録された識別子によって識別される地点が利用者によって参照されるごとに更新される。
【０１４１】
なお、利用者情報７１０の容量は、利用者が運転計画立案支援装置１００を利用するごとに増大するが、記憶装置４０３の容量が不足した場合等には、最終参照７１５に登録された年月日が古い地点の情報が削除又は圧縮されるようにしてもよい。
【０１４２】
次に、運転計画立案支援装置１００に備わる出力装置４０２に表示される運転計画立案画面について、図８を用いて説明する。図８は、本発明の第１実施例の運転計画立案画面の説明図である。
【０１４３】
運転計画立案支援画面は、出発地入力受付部８０１、目的地入力受付部８０２、運転計画経路出力部８０３、運転計画概要出力部８０４、決定ボタン８０５、及び計画編集ボタン８０６を含む。
【０１４４】
出発地入力受付部８０１は、出発地方の名称の入力を受け付ける部分である。目的地入力受付部８０２は、目的地方の名称の入力を受け付ける部分である。また、出発地入力受付部８０１には、必ずしも出発地方が入力される必要はない。出発地入力受付部８０１に何も入力されない場合、予め設定されている利用者の自宅の住所が出発地となる。
【０１４５】
出発地入力受付部８０１及び目的地入力受付部８０２に、出発地方及び目的地方が入力された場合、運転計画立案支援装置１００は、入力された出発地方及び目的地方に基づいて代表経路を探索して、運転計画情報を生成する。
【０１４６】
そして、運転計画立案支援装置１００は、運転計画経路出力部８０３に、代表経路を描画して、代表経路上に位置する経由地方を表示する。
【０１４７】
また、運転計画立案支援装置１００は、生成された運転計画情報の概要を運転計画概要出力部８０４に表示する。
【０１４８】
運転計画情報の概要は、往路の詳細情報、復路の詳細情報、予想旅行時間、及び旅行にかかる費用を含む。
【０１４９】
往路の詳細情報には、出発地方の出発時間、各経由地方の到着時間、及び目的地方の到着時間を含む。復路の詳細情報には、目的地方の出発時間、各経由地方の到着時間、及び出発地方の到着時間を含む。
【０１５０】
利用者は、生成された運転計画情報を編集しない場合には、決定ボタン８０５を操作する。決定ボタン８０５が操作された場合、生成された運転計画情報が外部記憶媒体１１２に転送される。一方、利用者は、生成された運転計画情報を編集する場合には、計画編集ボタン８０６を操作する。計画編集ボタン８０６が操作された場合、利用者は、生成された運転計画情報に、経由地方を追加（又は削除）したり、目的地を変更する等、運転計画情報を編集できる。
【０１５１】
次に、経路設定受付部１１３による代表経路選択処理について、図９を用いて説明する。図９は、本発明の実施形態の経路設定受付部１１３による代表経路選択処理のフローチャートである。
【０１５２】
まず、経路設定受付部１１３は、出発地入力受付部８０１に入力された出発地方を示す文字列及び目的地入力受付部８０２に入力された目的地方を示す文字列を取得する。
【０１５３】
そして、経路設定受付部１１３は、図６Ｂに示す地方データ６３１の名称６２８に登録された名称のうち、取得された出発地方を示す文字列に一致するエントリに含まれるメッシュコード６２９に登録された識別子によって識別されるメッシュ及び座標６３０に登録された座標を出発地方の代表地点とする（９０１）。
【０１５４】
また、経路設定受付部１１３は、図６Ｂに示す地方データ６３１の名称６２８に登録された名称のうち、取得された目的地方を示す文字列に一致するエントリに含まれるメッシュコード６２９に登録された識別子によって識別されるメッシュ及び座標６３０に登録された座標を目的地方の代表地点とする。
【０１５５】
次に、経路設定受付部１１３は、ステップ９０１の処理で出発地方の代表地点及び目的地方の代表地点のうち少なくとも一方において、複数の地点が代表地点として選択された場合、一の地点を代表地点として選択する。具体的には、経路設定受付部１１３は、ステップ９０１の処理で代表地点として選択された複数の地点から一つの地点を代表地点としてランダムに選択する。
【０１５６】
そして、経路設定受付部１１３は、一の出発地方の代表地点から一の目的地方の代表地点までの経路を代表経路として探索する（９０２）。
【０１５７】
なお、本実施例では、ステップ９０２の処理で、複数の地点から一つの地点が代表地点としてランダムに選択されたとしても、利用者が運転計画情報を編集できるので、多大な影響を運転計画に及ぼすことはない。
【０１５８】
次に、経路設定受付部１１３は、図６Ｂに示す地方データ６３１に登録された地方のうち、ステップ９０２の処理で探索された代表経路からの距離が所定の値以下である地方を選択する（９０３）。
【０１５９】
具体的には、経路設定受付部１１３は、代表経路を構成する各リンクから図６Ｂに示す地方データ６３１に登録される各地方までの距離を算出する。そして、経路設定受付部１１３は、算出された距離が所定の値以下である地方を選択する。
【０１６０】
次に、経路設定受付部１１３は、ステップ９０３の処理で選択された地方を経由地方に設定する（９０４）。
【０１６１】
なお、本実施例では、経路設定受付部１１３は、図６Ｂに示す地方データ６３１を参照して、経由地方を選択したが、図６Ａに地点データ６２０を参照して、代表経路からの距離が所定の値以下の地点を選択して、経由地点としてもよい。
【０１６２】
なお、本実施例では、経路設定受付部１１３は、代表経路からの距離が所定の値以下の地方を選択したが、経由する地方として適当な地方が選択されれば、如何なる方法を用いて経由地方を選択してもよい。
【０１６３】
経路設定受付部１１３が図９に示す代表経路選択処理を実行することによって、運転計画立案支援装置１００は、図８に示す運転計画立案画面を表示できる。
【０１６４】
次に、図８に示す運転計画立案画面で表示された運転計画情報の概要を編集する場合に表示される運転計画編集画面について、図１０を用いて説明する。図１０は、本発明の第１実施例の運転計画編集画面の説明図である。
【０１６５】
運転計画編集画面は、図８に示す運転計画立案画面に含まれる計画編集ボタン８０６が操作された場合に表示される。また、運転計画編集画面は、利用者が図８に示す運転計画立案画面で表示される経由地方、出発地、及び目的地を追加、削除、又は変更するための画面である。
【０１６６】
運転計画編集画面は、検索キーワード入力受付部１０００、検索地点表示部１００１、運転計画編集部１００２、及び検索地点位置表示部１００３を含む。
【０１６７】
検索キーワード入力受付部１０００は、利用者が運転計画情報の概要に追加又は変更を希望する地点を検索するためのキーワードを入力するための表示部である。
【０１６８】
検索地点表示部１００１は、検索地点名表示部１００１Ａ及び検索地点詳細情報表示部１００１Ｂを含む。
【０１６９】
検索地点名表示部１００１Ａには、検索キーワード入力受付部１０００に入力された文字列と条件が一致する地点が表示される地点の名称が表示される。検索地点詳細情報表示部１００１Ｂには、検索地点名表示部１００１Ａに表示された地点のうち、利用者によって選択された地点の詳細な情報が表示される。検索地点詳細情報表示部１００１Ｂに表示される情報は、具体的には、地点の名称、地点の住所、及び地点の営業時間等である。
【０１７０】
運転計画編集部１００２には、現在設定されている運転計画情報の概要に含まれる出発地、経由地方、及び目的地が表示される。運転計画編集部１００２に表示される出発地及び目的地の下方には、変更ボタンが表示される。また、運転計画編集部１００２に表示される各経由地方の下方には、削除ボタンが表示される。また、運転計画編集部１００２に表示される出発地と経由地方との間、各経由地方の間、及び経由地方と目的地との間には、追加ボタンが表示される。
【０１７１】
変更ボタンが操作された場合には、変更ボタンが操作された出発地又は目的地に検索地点名表示部１００１Ａで選択されている地点が変更される。削除ボタンが操作された場合には、削除ボタンが操作された経由地方が運転計画情報の概要から削除される。追加ボタンが操作された場合には、追加ボタンが操作された部分に検索地点名表示部１００１Ａで選択された地点が経由地方として運転計画情報の概要に追加される。
【０１７２】
検索地点位置表示部１００３には、運転計画編集部１００２で選択された地点の地図上での位置が表示される。
【０１７３】
そして、運転計画編集画面の完了ボタンが操作された場合には、現在の運転計画情報の概要が運転計画概要として運転計画立案支援装置１００に登録される。
【０１７４】
なお、本実施例の運転計画編集画面は一例であり、運転計画編集画面には利用者が欲する情報（例えば、経由地方及び高速道路を利用しない等）が表示されれば、他の表示方法であってもよい。
【０１７５】
次に、運転計画立案支援装置１００が運転計画概要に基づいて運転計画情報を生成する運転計画生成処理について、図１１を用いて説明する。図１１は、本発明の第１実施例の運転計画生成処理のフローチャートである。
【０１７６】
まず、地点情報準備範囲策定部１０８は、仮想的な出発地点から仮想的な目的地点に到達し得るすべての経路を探索する。そして、探索された経路を構成するリンクの一覧を周辺リンクとして取得する（１１０１）。なお、ステップ１１０１の処理の周辺リンクを取得する処理については、図１２で詳細を説明する。
【０１７７】
次に、地点候補選択部１０９は、図６Ａに示す地点データ６２０に登録された地点から、ステップ１１０１の処理で取得された周辺リンクに紐付けられる地点を取得する（１１０２）。
【０１７８】
具体的には、地点候補選択部１０９は、図６Ａに示す地点データ６２０に登録されたエントリのうち、リンクＩＤ６２６に登録されたリンクの識別子がステップ１１０１の処理で取得された周辺リンクの識別子と一致するエントリを、周辺リンクに紐付けられる地点として取得する。
【０１７９】
次に、運転計画情報生成部１１１は、ステップ１１０２の処理で取得された地点の分類コードを算出して、運転計画情報を生成する（１１０３）。分類コードは、ナビゲーション装置１２０がステップ１１０２の処理で取得された地点を経由地候補として利用者に提示するか否かを判定するために用いられるコードである。
【０１８０】
運転計画情報生成部１１１は、ステップ１１０２の処理で取得された地点のカテゴリ６２２に登録された情報に基づいて分類コードを算出する。
【０１８１】
例えば、正午ごろに到達すると予測される地点が飲食店である場合には、運転計画情報生成部１１１は、飲食店の地点が他の地点よりも優先して利用者に提示される分類コードを当該地点に付与する。また、運転時間が一定時間（例えば１時間）経過した場合に到達すると予測される地点が休憩所、パーキングエリア及び喫茶店等の休憩可能な地点である場合には、運転計画情報生成部１１１は、休憩可能な地点が他の地点よりも優先して利用者に提示される分類コードを当該地点に付与する。
【０１８２】
他の分類コードを算出する方法について説明する。運転計画情報生成部１１１は、ステップ１１０２の処理で取得された地点が図７に示す利用者情報７１０の参照回数７１６に登録された数が所定の値よりも大きい場合には、当該地点を利用者情報７１０の参照回数７１６に登録された数が所定の値以下である地点よりも優先して表示される分類コードを当該地点に付与する。
【０１８３】
したがって、分類コードには、地点で提供される商品又は役務の種類、及び地点の参照回数等が含まれ得る。
【０１８４】
次に、外部記憶媒体出力部１０６は、ステップ１１０３の処理で生成された運転計画情報をナビゲーション装置１２０が読み取り可能な形式に変換して、外部記憶媒体１１２に出力する（１１０４）。
【０１８５】
次に、ステップ１１０１の処理の周辺リンクを取得する周辺リンク取得処理について、図１２を用いて説明する。図１２は、本発明の第１実施例の周辺リンク取得処理のフローチャートである。
【０１８６】
周辺リンク取得処理は、ダイクストラ法によって仮想的な出発地点から仮想的な目的地点まで到達し得る経路のうち、累積コストが最小となる経路を探索し、コストが算出されたすべてのリンクを周辺リンクとして取得する処理である。なお、コストとは、リンクを移動するためにかかる時間又はリンクの距離である。また、累積コストは、出発地から当該リンクの始点ノードに到達するまでにかかる時間又は距離（コスト）に、当該リンクのコストを加算した値である。
【０１８７】
まず、地点情報準備範囲策定部１０８は、仮想的な出発地点に進入可能なリンクを探索開始地点としてチェック対象に追加する（１２０１）。具体的には、地点情報準備範囲策定部１０８は、図５Ａに示す地点データ６２０に登録された地点のうち、仮想的な出発地点のエントリに含まれるリンクＩＤ６２６に登録されたリンクの識別子を取得して、取得された識別子によって識別されるリンクを、探索開始地点としてチェック対象に追加する。
【０１８８】
次に、地点情報準備範囲策定部１０８は、チェック対象のリンクのうち、累積コストが最小のリンクを変数Ｔに代入する（１２０２）。そして、地点情報準備範囲策定部１０８は、ステップ１２０２の処理で変数Ｔに代入されたリンクをチェック済みのリンクとする（１２０３）。
【０１８９】
次に、地点情報準備範囲策定部 １０８は、変数Ｔに代入されたリンクに接続されるｎ番目のリンクを変数Ｘに代入して、ｎ＋１番目のリンクをｎ番目のリンクとする（１２０４）。
【０１９０】
次に、地点情報準備範囲策定部１０８は、変数Ｘに代入されたリンクは仮想的な目的地点に進入可能なリンクであるか否かを判定する（１２０５）。
【０１９１】
具体的には、地点情報準備範囲策定部１０８は、図６Ａに示す地点データ６２０に登録されたエントリのうち仮想的な目的地点のエントリを取得し、取得したエントリに含まれるリンクＩＤ６２６に登録されたリンクの識別子が、変数Ｘに代入されたリンクの識別子に一致するか否かを判定する。
【０１９２】
ステップ１２０５の処理で、地点情報準備範囲策定部１０８は、変数Ｘに代入されたリンクが仮想的な目的地点に進入可能なリンクでないと判定された場合、変数Ｘに代入されたリンクがチェック済みのリンクであるか否かを判定する（１２０６）。
【０１９３】
ステップ１２０６の処理で、地点情報準備範囲策定部１０８は、変数Ｘに代入されたリンクがチェック済みのリンクでないと判定された場合、探索開始地点から変数Ｘに代入されたリンクまでの累積コストを算出して、変数Ｘに代入されたリンクをチェック対象に追加する（１２０７）。
【０１９４】
具体的には、地点情報準備範囲策定部１０８は、探索開始地点から変数Ｔに代入されたリンクまでの累積コストに変数Ｘに代入されたリンクの通過コストを加算することによって、探索開始地点から変数Ｘに代入されたリンクまでの累積コストを算出する。
【０１９５】
次に、地点情報準備範囲策定部１０８は、変数Ｔに代入されたリンクの接続先のすべてのリンクの累積コストが算出されたか否かを判定するために、変数Ｘに代入されたリンクの番号（ｎ）が変数Ｔに代入されたリンクの接続先のリンクの数よりも小さいか否かを判定する（１２０８）。
【０１９６】
ステップ１２０８の処理で、変数Ｘに代入されたリンクの番号（ｎ）が変数Ｔに代入されたリンクの接続先のリンクの数よりも小さいと判定された場合、変数Ｔに代入されたリンクの接続先のすべてのリンクの累積コストが算出されていないので、ステップ１２０４の処理に戻る。
【０１９７】
一方、ステップ１２０８の処理で、変数Ｘに代入されたリンクの番号（ｎ）が変数Ｔに代入されたリンクの接続先のリンクの数以上であると判定された場合、変数Ｔに代入されたリンクの接続先のすべてのリンクの累積コストが算出されたので、ステップ１２０２の処理に戻る。
【０１９８】
一方、ステップ１２０５の処理で、変数Ｘに代入されたリンクは仮想的な目的地点に進入可能なリンクであると判定された場合、仮想的な出発地点から仮想的な目的地点までの経路が探索されたので、チェック済みリンクを周辺リンクに追加し（１２０９）、周辺リンク取得処理を終了する。
【０１９９】
つまり、周辺リンク取得処理では、出発地のリンクに接続されるリンクに接続されるすべてのリンクに対して累積コストを算出し、最小の累積コストのリンクを選択し、選択されたリンクに接続されるすべてのリンクに対してコストを算出し、最小の累積コストのリンクを選択していく処理を目的地に接続されるリンクまで繰り返し実行する。そして、累積コストが算出されたすべてのリンクを周辺リンクとする。
【０２００】
次に、図１１に示す運転計画生成処理によって生成される運転計画情報を、図１３Ａ及び図１３Ｂを用いて説明する。運転計画情報は、運転計画概要情報１３００及び経由地候補情報１３１０を含む。
【０２０１】
まず、運転計画概要情報１３００について、図１３Ａを用いて説明する。図１３Ａは、本発明の第１実施例の運転計画概要情報１３００の説明図である。
【０２０２】
運転計画概要情報１３００は、要素番号１３０１、種別１３０２、分類１３０３、名称１３０４、メッシュコード１３０５、及びオブジェクトＩＤ１３０６を含む。
【０２０３】
要素番号１３０１には、運転計画の概要を構成する各要素の一意な識別子が登録される。種別１３０２には、運転計画の概要を構成する各要素の種別を示す情報が登録される。例えば、種別１３０２には、運転計画の概要を構成する要素が地点（出発地、経由地、及び目的地等）を示す場合には「１」が登録され、運転計画の概要を構成する要素が道路を示す場合には「２」が登録される。
【０２０４】
分類１３０３には、図１１に示す運転計画生成処理のステップ１１０３の処理で算出された分類コードが登録される。したがって、分類１３０３には、地点で提供される商品又は役務の種類、及び地点の参照回数等が含まれ得る。
【０２０５】
名称１３０４には、運転計画の概要を構成する要素の名称を示す情報が登録される。メッシュコード１３０５には、運転計画の概要を構成する要素（地点又は代表経路）を含むメッシュの一意な識別子が登録される。オブジェクトＩＤ１３０６には、ナビゲーション装置１２０に備わる記憶装置４１７に記憶される地図データのオブジェクトのうち、運転計画の概要を構成する要素（地点又は代表経路）に対応するオブジェクトの一意な識別子が登録される。
【０２０６】
次に、経由地候補情報１３１０について、図１３Ｂを用いて説明する。図１３Ｂは、本発明の第１実施例の経由地候補情報１３１０の説明図である。
【０２０７】
経由地候補情報１３１０は、図１１に示す運転計画生成処理のステップ１１０２の処理で取得された地点の情報である。ナビゲーション装置１２０は、現在の状況に対応して、経由地候補情報１３１０に登録された地点から経由地の候補となり得る地点を利用者に提示する。
【０２０８】
経由地候補情報１３１０は、地点ＩＤ１３１１、リンクＩＤ１３１２、分類１３１３、名称１３１４、メッシュコード１３１５、及び座標１３１６を含む。
【０２０９】
地点ＩＤ１３１１には、地点の一意な識別子が登録される。リンクＩＤ１３１２には、地点ＩＤ１３１１に登録された識別子によって識別される地点に進入可能なリンクの一意な識別子が登録される。
【０２１０】
分類１３０３には、図１１に示す運転計画生成処理のステップ１１０３の処理で算出された分類コードが登録される。名称１３１４には、地点ＩＤ１３１１に登録された識別子によって識別される地点の名称が登録される。
【０２１１】
メッシュコード１３１５には、地点ＩＤ１３１１に登録された識別子によって識別される地点を含むメッシュの一意な識別子が登録される。座標１３１６には、メッシュコード１３１５に登録された識別子によって識別されるメッシュにおいて、地点ＩＤ１３１１に登録された識別子によって識別される地点が位置する座標が登録される。
【０２１２】
なお、本実施例の運転計画情報は一例であり、運転計画概要情報１３００及び経由地候補情報１３１０は他の属性情報を含んでもよい。
【０２１３】
次に、ナビゲーション装置１２０に備わる表示装置４１５に表示される案内画面について、図１４を用いて説明する。図１４は、本発明の第１実施例のナビゲーション装置１２０に備わる表示装置４１５に表示される案内画面の説明図である。
【０２１４】
ナビゲーション装置１２０は、外部記憶媒体１１２に記憶された運転計画情報を読み取って、運転計画情報に基づいて経路案内を開始する。
【０２１５】
案内画面には、案内経路１４０１、現在位置１４０２、分岐点１４０３、経由候補地点１４０４、及び代替経路１４０５が表示される。
【０２１６】
案内経路１４０１には、目的地までのナビゲーション装置１２０を搭載した自動車の現在走行中の経路が表示される。現在位置１４０２には、ＧＰＳ受信機４１８によって取得されたナビゲーション装置１２０を搭載した自動車の現在位置が表示される。
【０２１７】
分岐点１４０３には、現在走行中の案内経路と、経由候補地点を経由して目的地まで到達可能な代替経路との分岐が表示される。
【０２１８】
経由候補地点１４０４には、現在の状況（現在位置及び現在の時刻等）、及び経由地候補情報１３１０に登録された地点の分類１３１３に登録された分類コードに基づいて、経由候補地点の詳細情報が表示される。代替経路１４０５には、経由候補地点を経由して目的地まで到達可能な代替経路が表示される。
【０２１９】
次に、ナビゲーション装置１２０によって実行される案内経路提示処理について図１５を用いて説明する。図１５は、本発明の第１実施例の案内経路提示処理のフローチャートである。
【０２２０】
まず、計画策定部１３１は、ＧＰＳ受信機４１８からナビゲーション装置１２０を搭載した自動車の現在位置を取得する。そして、計画策定部１３１は、運転計画概要情報１３００を参照して、仮想的な目的地を特定する。具体的には、計画策定部１３１は、運転計画概要情報１３００に登録されたエントリのうち、分類１３０３に登録された情報が仮想的な目的地を示す情報（分類コードが「２」）であるエントリを、仮想的な目的地として取得する。
【０２２１】
そして、計画策定部１３１は、取得した現在位置から取得した仮想的な目的地までの最短経路を、ダイクストラ法を用いて探索する（１５０１）。
【０２２２】
次に、計画策定部１３１は、ステップ１５０１の処理で探索された経路を図１４に示す案内画面に案内経路１４０１として表示することによって、案内経路を利用者に提示する（１５０２）。
【０２２３】
次に、計画策定部１３１は、仮想的な目的地に到達しているか否かを判定するために、ステップ１５０１の処理で取得された現在位置からステップ１５０１の処理で取得された仮想的な目的地までの距離が所定値以下であるか否かを判定する（１５０３）。
【０２２４】
ステップ１５０３の処理で、ステップ１５０１の処理で取得された現在位置からステップ１５０１の処理で取得された仮想的な目的地までの距離が所定値以下であると判定された場合、つまり、仮想的な目的地に到達していると判定された場合、計画策定部１３１は、図１３Ｂに示す経由地候補情報１３１０を参照して、仮想的な目的地周辺の目的地となり得る地点を表示装置４１５に表示することによって、目的地候補を利用者に提示し（１５０７）、案内経路提示処理を終了する。
【０２２５】
一方、ステップ１５０３の処理で、ステップ１５０１の処理で取得された現在位置からステップ１５０１の処理で取得された仮想的な目的地までの距離が所定値より大きいと判定された場合、つまり、仮想的な目的地に到達していないと判定された場合、提示情報制御部１３２は、経由候補地点を利用者に提示する経由候補地点提示処理を実行する（１５０４）。経由候補地点提示処理については、図１６を用いて説明する。
【０２２６】
次に、計画策定部１３１は、現在走行中の案内経路から利用者に提示された経由候補地点側に経路を変更したか否かを判定する（１５０５）。具体的には、計画策定部１３１は、ＧＰＳ受信機４１８から現在位置を取得し。取得した現在位置が案内経路を外れて、利用者に提示された経由候補地点側へ移動したか否かを判定する。
【０２２７】
ステップ１５０５の処理で、現在走行中の案内経路から利用者に提示された経由候補地点側に経路を変更したと判定された場合、経由候補地点を経由地として、現在位置から経由地を経由して仮想的な目的地まで到達可能な最短経路である代替経路をダイクストラ法を用いて探索して、探索された代替経路を案内経路に更新し（１５０６）、ステップ１５０２の処理に戻る。
【０２２８】
次に、図１５に示す案内経路提示処理のステップ１５０４の処理の経由候補地点提示処理について、図１６を用いて説明する。図１６は、本発明の第１実施例の経由候補地点提示処理のフローチャートである。
【０２２９】
まず、状況判定部１２９は、現在の状況を判定して、現在の状況に対応する分類コードの一覧を生成する（１６０１）。
【０２３０】
例えば、状況判定部１２９は、現在の時刻を取得して、取得した現在の時刻が食事時間であるか否かを判定することによって、現在の状況を判定する。そして、現在の状況が食事時間であると判定された場合、状況判定部１２９は、食事時間に対応する分類コード（例えば、飲食店及び休憩可能な地点を示す分類コード）の一覧を生成する。
【０２３１】
また、状況判定部１２９は、現在の状況を示す特徴的な量を算出して、算出された特徴的な量を予め設定された識別関数に入力して、識別関数を演算して現在の状況を判定する。そして、状況判定部１２９は、識別関数の演算結果に対応する分類コードの一覧を生成してもよい。
【０２３２】
なお、状況判定部１２９が現在の状況を判定する方法は、適当に現在の状況を判定できれば、如何なる方法を用いてもよい。
【０２３３】
次に、経路探索部１３０は、現在位置に対応する次の分岐点から、ナビゲーション装置１２０を搭載した自動車が所定時間以内に到達可能な範囲にあるすべてのリンクを取得する（１６０２）。
【０２３４】
次に、計画策定部１３１は、ステップ１６０１の処理で取得された分類コード及びステップ１６０２の処理で取得されたリンクに基づいて、経由地候補情報１３１０に登録された地点を経由候補地点として取得する（１６０３）。
【０２３５】
具体的には、計画策定部１３１は、経由地候補情報１３１０に登録されたエントリのうち、分類１３１３に登録された分類コードがステップ１６０１の処理で取得された分類コードに一致し、かつリンクＩＤ１３１２に登録された識別子によって識別されるリンクが、ステップ１６０２の処理で取得されたリンクに一致するエントリの地点を、経由候補地点として取得する。
【０２３６】
次に、提示情報制御部１３２は、ステップ１６０３の処理で取得された経由候補地点を、図１４に示す案内画面に表示する（１６０４）。
【０２３７】
（第２実施例）
次に、本発明の第２実施例について、図１７〜図２２を用いて説明する。第２実施例では、利用者は、入力受付部１０２としての機能を有する移動端末１７３０（例えば、携帯電話等）から出発地方及び目的地方等を、ネットワークを介して運転計画立案支援装置１７００に入力する点、及び例えば、地点に関する情報を利用者にホームページ等によって提供する外部情報源（地点情報提供装置）１７１０で紹介された地点を運転計画情報に含まれる経由地候補情報に含めることができる点で、第１実施例と異なる。
【０２３８】
なお、第２実施例の構成及び処理のうち、第１実施例の構成及び処理と同じものは、同じ番号を付与し、説明を省略する。
【０２３９】
第２実施例の運転計画立案支援システムについて、図１７を用いて説明する。図１７は、本発明の第２実施例の運転計画立案支援システムのブロック図である。
【０２４０】
運転計画立案支援システムは、運転計画立案支援装置１７００、外部情報源１７１０、ナビゲーション装置１７２０、及び移動端末１７３０を備える。
【０２４１】
なお、運転計画立案支援装置１７００、外部情報源１７１０、ナビゲーション装置１７２０、及び移動端末１７３０は、ネットワークを介して接続される。
【０２４２】
運転計画立案支援装置１７００は、ＣＰＵ４０５、記憶装置４０３、メモリ４０６、及びＮＩＣ（Network Interface Card）１７０３を備える。ＮＩＣ１７０３は、運転計画立案支援装置１７００をネットワークに接続する通信部１０５として機能する。
【０２４３】
外部情報源１７１０は、地点に関する情報を記憶し、記憶している地点に関する情報を利用者に提供する。外部情報源１７１０は、情報交換サービス１７０１及び情報発信サイト１７０２を含む。
【０２４４】
情報交換サービス１７０１は、利用者間で情報を交換するサービスを提供する。情報発信サイト１７０２は、利用者が自身の経験等をインターネット上に発信するためのサービスを提供する。
【０２４５】
ナビゲーション装置１７２０は、第１実施例の外部Ｉ／Ｆ４１３に代わって、無線通信装置１７２１を備える。無線通信装置１７２１は、ナビゲーション装置１７２０をネットワークに接続する通信部１２８として機能する。これによって、ナビゲーション装置１７２０を搭載した自動車が移動中であっても、ナビゲーション装置１７２０はネットワークに接続できる。
【０２４６】
移動端末１７３０は、例えば携帯電話であり、入力受付部１０２として機能する。
【０２４７】
次に、外部情報源１７１０に記憶された情報を移動端末１７３０に表示する外部情報表示処理について、図１８を用いて説明する。図１８は、本発明の第２実施例の外部情報表示処理の説明図である。
【０２４８】
まず、移動端末１７３０は、利用者が移動端末１７３０に表示する地点に関する情報の文書を取得する要求である文書要求１８０１を、ネットワークを介して運転計画立案支援装置１７００に送信する。
【０２４９】
運転計画立案支援装置１７００は、文書要求１８０１を受信した場合に、受信した文書要求１８０１を外部情報源１７１０に転送する。
【０２５０】
外部情報源１７１０は、文書要求１８０１を受信した場合に、利用者が移動端末１７３０に表示することを所望する表示文書データ１８０２、及び表示文書データ１８０２によって表示される地点の位置を特定するための外部情報メタデータ１８０３を、運転計画立案支援装置１７００に送信する。
【０２５１】
外部情報メタデータ１８０３は、メッシュコード１８１３及び座標１８１４を含む。メッシュコード１８１３は、表示文書データ１８０２によって表示される地点を含むメッシュの一意な識別子が登録される。座標１８１４には、メッシュコード１８１３に登録された識別子によって識別されるメッシュにおいて、表示文書データ１８０２によって表示される地点が位置する座標が登録される。
【０２５２】
運転計画立案支援装置１７００は、表示文書データ１８０２及び外部情報メタデータ１８０３を受信した場合、利用者が外部情報を利用した履歴を図１９に示す利用者外部情報使用履歴データ１９１０に登録する。利用者外部情報使用履歴データ１９１０については、図１９で詳細を説明する。
【０２５３】
そして、運転計画立案支援装置１７００は、表示文書データ１８０２のみを移動端末１７３０に送信する。
【０２５４】
移動端末１７３０は、表示文書データ１８０２を受信した場合、受信した表示文書データ１８０２を移動端末１７３０に表示する。
【０２５５】
次に、利用者外部情報使用履歴データ１９１０について、図１９を用いて説明する。図１９は、本発明の第２実施例の利用者外部情報使用履歴データ１９１０の説明図である。
【０２５６】
利用者外部情報使用履歴データ１９１０は、参照先１９１１、メッシュコード１９１２、座標１９１３、及びタイムスタンプ１９１４を含む。
【０２５７】
参照先１９１１には、運転計画立案支援装置１７００が受信した文書要求１８０１に含まれる文書要求１８０１を取得するＵＲＬが登録される。
【０２５８】
メッシュコード１９１２には、運転計画立案支援装置１７００が受信した外部情報メタデータ１８０３に含まれるメッシュコード１８１３に登録されたメッシュの一意な識別子が登録される。座標１９１３には、運転計画立案支援装置１７００が受信した外部情報メタデータ１８０３に含まれる座標１８１４に登録された座標が登録される。
【０２５９】
タイムスタンプ１９１４には、運転計画立案支援装置１７００が表示文書データ１８０２及び外部情報メタデータ１８０３を受信した年月日及び時刻が登録される。
【０２６０】
なお、利用者外部情報使用履歴データ１９１０は、利用者が外部情報を利用するごとにエントリが追加されていくので、利用者外部情報使用履歴データ１９１０に登録されたエントリの数が所定の値以上になった場合に、運転計画立案支援装置１７００は、タイムスタンプ１９１４に登録された年月日及び時刻が古いエントリを削除してもよい。
【０２６１】
次に、運転計画立案支援装置１７００が利用者外部情報使用履歴データ１９１０に基づいて運転計画情報を生成する運転計画生成処理について、図２０を用いて説明する。図２０は、本発明の第２実施例の運転計画生成処理のフローチャートである。なお、第２実施例の運転計画生成処理のうち、図１１に示す第１実施例と同じ処理は、同じ符号を付与し、説明を省略する。
【０２６２】
まず、地点情報準備範囲策定部１０８は、ステップ１１０１の処理を実行して周辺リンクの一覧を取得する。
【０２６３】
次に、地点候補選択部１０９は、ステップ１１０２の処理を実行して、ステップ１１０１の処理で取得された周辺リンクに紐付けられる地点を取得する。
【０２６４】
次に、地点候補選択部１０９は、利用者外部情報使用履歴データ１９１０に登録された地点のうち、ステップ１１０１の処理で取得された周辺リンクに紐付けられる地点を取得する（２００１）。
【０２６５】
具体的には、地点候補選択部１０９は、図５Ａに示すリンクデータ５０８に登録されたエントリのうち、ステップ１１０１の処理で取得された周辺リンクに一致するエントリを選択する。そして、地点候補選択部１０９は、選択されたエントリに含まれるメッシュコード５０２に登録されたメッシュコード及び形状５０５に登録された座標を取得する。
【０２６６】
次に、地点候補選択部１０９は、図１９に示す利用者外部情報使用履歴データ１９１０に登録されたエントリのうち、メッシュコード１９１２に登録されたメッシュコード及び座標１９１３に登録された地点の座標によって特定される地点の位置が、周辺リンクに対応するエントリに含まれるメッシュコード５０２に登録されたメッシュコード及び形状５０５に登録された座標によって特定される周辺リンクの位置から最も近いエントリを取得する。これによって、地点候補選択部１０９は、周辺リンクに紐付けられる地点を取得する。
【０２６７】
次に、地点候補選択部１０９は、ステップ１１０２の処理で取得された地点（地点データ６２０から取得された地点）及びステップ２００１の処理で取得された地点（利用者外部情報使用履歴データ１９１０から取得された地点）の分類コードを算出して、運転計画情報を生成する（２００２）。この場合、地点候補選択部１０９は、ステップ１１０２の処理で取得された地点の分類コードと、ステップ２００１の処理で取得された地点とを区別できるように、分類コードを付与する。
【０２６８】
なお、分類コードの算出方法については、図１１に示すステップ１１０３の処理と同じであるので、説明を省略する。
【０２６９】
次に、通信部１０５は、ステップ２００２の処理で生成された運転計画情報をナビゲーション装置１７２０が読み取り可能な形式に変換し、ステップ２００２の処理で生成された運転計画情報をナビゲーション装置１７２０にネットワークを介して送信する（２００３）。
【０２７０】
次に、運転計画情報について、図２１Ａ及び図２１Ｂを用いて説明する。
【０２７１】
運転計画情報は、運転計画概要情報１３００、経由地候補情報１３１０、及び履歴地点参照情報２１２０を含む。運転計画概要情報１３００については、図１３Ａに示す第１実施例の運転計画概要情報１３００と同じなので、説明を省略する。
【０２７２】
まず、経由地候補情報１３１０について、図２１Ａを用いて説明する。図２１Ａは、本発明の第２実施例の経由地候補情報１３１０の説明図である。
【０２７３】
経由地候補情報１３１０は、図１３Ｂに示す第１実施例の経由地候補情報１３１０と同じ構成であるが、登録されるエントリが相違する。
【０２７４】
エントリ１３１０１及び１３１０２に示すように、経由地候補情報１３１０には、利用者外部情報使用履歴データ１９１０に登録された地点の情報のうち、周辺リンクに紐付けられる利用者外部情報使用履歴データ１９１０に登録された地点の情報が登録される。
【０２７５】
利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれる地点ＩＤ１３１１には、地点データ６２０に登録された地点の情報のうち、周辺リンクに紐付けられる地点の情報を示すエントリに含まれる地点ＩＤ１３１１に登録された地点を示す識別子と重複しないように一意に生成された地点を示す一意な識別子が登録される。
【０２７６】
利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれるリンクＩＤ１３１２には、利用者外部情報使用履歴データ１９１０に登録された地点のうち周辺リンクに紐付けられる地点から最も近い周辺リンクを示す一意な識別子が登録される。
【０２７７】
利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれる分類１３１３には、ステップ２００２の処理で算出された分類コードが登録される。
【０２７８】
利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれるメッシュコード１３１５及び座標１３１６には、利用者外部情報使用履歴データ１９１０に登録された地点の情報のうち周辺リンクに紐付けられる地点のメッシュコード１９１２に登録されたメッシュコード及び座標１９１３に登録された座標が登録される。
【０２７９】
また、利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれる名称１３１４には、利用者外部情報使用履歴データ１９１０に登録された地点の情報のうち周辺リンクに紐付けられる地点の参照先１９１１に登録されたＵＲＬによって特定されるホームページを参照して、当該地点の名称として使用される文字列、又は当該ホームページで頻繁に使用される単語の文字列を取得して、取得された文字列が登録される。
【０２８０】
なお、利用者外部情報使用履歴データ１９１０に登録された地点の情報を示すエントリに含まれる名称１３１４には、利用者外部情報使用履歴データ１９１０に登録された地点の情報のうち周辺リンクに紐付けられる地点の適切な名称として使用される文字列が登録されればよい。
【０２８１】
次に、履歴地点参照情報２１２０について、図２１Ｂを用いて説明する。図２１Ｂは、本発明の第２実施例の履歴地点参照情報２１２０の説明図である。
【０２８２】
履歴地点参照情報２１２０は、ナビゲーション装置１２０が図２１Ａに示す経由地候補情報１３１０に登録された地点の情報のうち、利用者外部情報使用履歴データ１９１０から取得された地点の情報を参照する場合に、当該地点の詳細情報を取得するためのデータである。
【０２８３】
履歴地点参照情報２１２０は、地点ＩＤ２１２１及び参照先２１２２を含む。
【０２８４】
地点ＩＤ２１２１には、経由地候補情報１３１０に登録された地点の情報のうち、利用者外部情報使用履歴データ１９１０から取得された地点の情報に含まれる地点ＩＤ１３１１に登録された地点の識別子が登録される。
【０２８５】
参照先２１２２には、経由地候補情報１３１０に登録された地点の情報のうち利用者外部情報使用履歴データ１９１０から取得された地点と一致する利用者外部情報使用履歴データ１９１０に登録された地点の参照先１９１１に登録されたＵＲＬが登録される。
【０２８６】
なお、本実施例のナビゲーション装置１２０によって実行される処理は、第１実施例のナビゲーション装置１２０によって実行される処理（図１５及び図１６）と同じなので、説明を省略する。
【０２８７】
また、図１６に示すステップ１６０４の処理（提示情報制御部１３２が経由候補地点を案内画面に表示する処理）で、提示情報制御部１３２は、経由地候補情報１３１０に登録された地点のうち、利用者外部情報使用履歴データ１９１０から取得された地点を経由候補地点として、案内画面に表示する場合には、履歴地点参照情報２１２０に登録されたエントリに含まれる地点ＩＤ２１２１に登録された識別子のうち、当該経由候補地点として表示する地点の地点ＩＤ１３１１に登録された識別子と一致するエントリを選択し、選択されたエントリに含まれる参照先２１２２に登録されたＵＲＬを取得する。そして、提示情報制御部１３２は、取得されたＵＲＬによって特定されるホームページ（外部情報源１７１０）へ、無線通信装置１７２１を用いて接続して、当該ホームページから表示文書データ１８０２を取得する。
【０２８８】
これによって、提示情報制御部１３２は、経由地候補情報１３１０に登録された地点のうち、利用者外部情報使用履歴データ１９１０から取得された地点を経由候補地点として、案内画面に表示する場合に、当該地点の詳細情報も表示することができる。
【０２８９】
次に、ナビゲーション装置１２０に備わる表示装置４１５に表示される案内画面について、図２２を用いて説明する。図２２は、本発明の第２実施例のナビゲーション装置１２０に備わる表示装置４１５に表示される案内画面の説明図である。なお、図２２に示す案内画面の構成のうち、図１４に示す第１実施例の案内画面と同じ構成は、同じ符号を付与し、説明を省略する。
【０２９０】
図２２は、経由候補地点１４０４に、経由地候補情報１３１０に登録された地点のうち、利用者外部情報使用履歴データ１９１０から取得された地点が表示される場合の案内画面である。
【０２９１】
この場合、経由候補地点１４０４には、外部情報源１７１０から取得された表示文書データ１８０２に基づいて、当該地点の詳細情報が表示される。
【０２９２】
これによって、利用者が過去に参照した地点の情報を経由候補地点として提示できる。
【０２９３】
（第３実施例）
第３実施例は、運転計画立案支援装置１００が経路候補情報を含む運転計画情報を生成して、ナビゲーション装置１２０が運転計画情報に含まれる経路候補情報に基づいて、道案内する点が第１実施例及び第２実施例と異なる。
【０２９４】
なお、第３実施例の構成及び処理のうち、第１実施例及び第２実施例の構成及び処理と同じものは、同じ番号を付与し、説明を省略する。
【０２９５】
次に、運転計画立案支援装置１００が運転計画概要に基づいて経路候補を含む運転計画情報を生成する運転計画生成処理について、図２３を用いて説明する。図２３は、本発明の第３実施例の運転計画生成処理のフローチャートである。なお、図２３に示す経路候補を含む運転計画情報を生成する処理のうち、図１１に示す第１実施例の運転計画生成処理の処理と同じ処理は、同じ符号を付与し、説明を省略する。
【０２９６】
まず、地点情報準備範囲策定部１０８は、仮想的な出発地点から仮想的な目的地点に到達し得る複数の経路を探索し、探索された複数の経路を経路候補として取得する経路候補生成処理を実行する（２３０１）。
【０２９７】
なお、ステップ２３０１の処理の経路候補生成処理については、図２４で詳細を説明する。
【０２９８】
次に、地点候補選択部１０９は、ステップ２３０１の処理で選択された経路候補として選択された経路を構成するリンクに紐付けられる地点を取得する（２３０２）。
【０２９９】
具体的には、地点候補選択部１０９は、図６Ａに示す地点データ６２０に登録されたエントリのうち、リンクＩＤ６２６に登録されたリンクの識別子がステップ２３０１の処理で選択された経路候補として選択された経路を構成するリンクの識別子と一致するエントリを、ステップ２３０１の処理で選択された経路候補として選択された経路を構成するリンクに紐付けられる地点として取得する。
【０３００】
次に、運転計画情報生成部１１１は、ステップ１１０３の処理を実行し、外部記憶媒体出力部１０６は、ステップ１１０４の処理を実行して、運転計画生成処理を終了する。
【０３０１】
次に、ステップ２３０１の処理で実行される経路候補生成処理について、図２４を用いて説明する。図２４は、本発明の第３実施例の経路候補生成処理のフローチャートである。
【０３０２】
経路候補生成処理では、予め設定された最も妥当な探索条件（例えば、最短経路）に基づいて探索された経路を主経路とし、その他の複数の探索条件に基づいて探索された複数の経路を他経路とする。
【０３０３】
なお、経路候補生成処理では、探索された主経路及び他経路を含む経路候補を記憶する経路候補記憶領域、及び主経路と他経路との分岐点を記憶する分岐候補記憶領域を用いて処理が実行される。
【０３０４】
まず、地点情報準備範囲策定部１０８は、変数リンクＸに仮想的な目的地を代入する（２４０１）。
【０３０５】
次に、地点情報準備範囲策定部１０８は、主経路を探索するための条件に基づいて、変数リンクＸに代入された地点から仮想的な目的地までの主経路を探索する（２４０２）。
【０３０６】
次に、地点情報準備範囲策定部１０８は、他経路を探索するための条件に基づいて、変数リンクＸに代入された地点から仮想的な目的地までの他経路を探索する（２４０３）。
【０３０７】
次に、地点情報準備範囲策定部１０８は、ステップ２４０２の処理で探索された主経路及びステップ２４０３の処理で探索された他経路を経路候補記憶領域に記憶する（２４００４）。
【０３０８】
次に、地点情報準備範囲策定部１０８は、主経路及び他経路を比較して、主経路と他経路との分岐点を探索し、分岐点が探索された場合には、探索された分岐点を分岐候補記憶領域に記憶する（２４０５）。
【０３０９】
次に、地点情報準備範囲策定部１０８は、分岐候補記憶領域に分岐点が記憶されているか否かを判定する（２４０６）。具体的には、地点情報準備範囲策定部１０８は、分岐候補記憶領域に記憶されている分岐点の数がゼロであるか否かを判定する。
【０３１０】
ステップ２４０６の処理で、分岐候補記憶領域に記憶されている分岐点の数がゼロであると判定された場合、つまり、分岐候補記憶領域に分岐点が記憶されていないと判定された場合、経路候補生成処理を終了する。
【０３１１】
一方、ステップ２４０６の処理で、分岐候補記憶領域に記憶されている分岐点の数がゼロでないと判定された場合、つまり、分岐候補記憶領域に分岐点が記憶されていると判定された場合、分岐候補記憶領域に記憶されている分岐点の数が所定の値よりも大きいか否かを判定する（２４０７）。
【０３１２】
ステップ２４０７の処理で、分岐候補記憶領域に記憶されている分岐点の数が所定の値よりも大きいと判定された場合、経路候補生成処理を終了する。
【０３１３】
一方、ステップ２４０７の処理で、分岐候補記憶領域に記憶されている分岐点の数が所定の値以下であると判定された場合、分岐候補記憶領域に記憶されている分岐点から一の分岐点を選択して、選択された分岐点を変数リンクＸに代入して（２４０８）、ステップ２４０２の処理に戻る。
【０３１４】
なお、ステップ２４０８の処理では、地点情報準備範囲策定部１０８は、選択された分岐点を変数リンクＸに代入した後に、選択された分岐点を分岐候補記憶領域から削除する。
【０３１５】
これによって、運転計画立案支援装置１００は、利用者が運転計画に基づいてナビゲーション装置１２０を搭載した自動車を走行させる場合に、当該自動車が走行し得る経路を予め準備できる。
【０３１６】
なお、図２４に示す経路候補生成処理は一例であり、ナビゲーション装置１２０を搭載した自動車が走行し得る経路を予め準備できれば、如何なる方法を用いてもよい。
【０３１７】
運転計画立案支援装置１００によって生成される運転計画情報に含まれる経路候補データ２５００について、図２５を用いて説明する。図２５は、本発明の第３実施例の経路候補データ２５００の説明図である。
【０３１８】
経路候補データ２５００は、経路ＩＤ２５０１、番号２５０２、リンクＩＤ２５０３、及びメッシュコード２５０４を含む。
【０３１９】
経路ＩＤ２５０１には、経路候補生成処理によって探索された他経路の一意な識別子が登録される。番号２５０２には、経路ＩＤ２５０１に登録された識別子によって識別される経路において、リンクＩＤ２５０３に登録される識別子によって識別されるリンクが何番目に位置するかを示す情報が登録される。
【０３２０】
リンクＩＤ２５０３には、経路ＩＤ２５０１に登録された識別子によって識別される経路において、番号２５０２に登録された情報が示す位置に位置するリンクの一意な識別子が登録される。メッシュコード２５０４には、リンクＩＤ２５０３に登録された識別子によって識別されるリンクを含むメッシュの一意な識別子が登録される。
【０３２１】
ナビゲーション装置１２０によって実行される経由候補地点提示処理について、図２４を用いて説明する。図２６は、本発明の第３実施例の経由候補地点提示処理のフローチャートである。なお、図２６に示す経由候補地点提示処理のうち、図１６に示す第１実施例の経由候補地点提示処理と同じ処理は、同じ符号を付与し、説明を省略する。
【０３２２】
まず、状況判定部１２９は、ステップ１６０１の処理を実行して、分類コードの一覧を生成する。
【０３２３】
次に、経路探索部１３０は、現在位置から進行方向に位置する次の交差点に接続されるリンクを取得し、経路候補データ２５００を参照し、取得されたリンクを含む経路を探索する（２６０１）。そして、ステップ２６０１の処理で取得されたリンクを含む経路が探索された経路が経路候補データ２５００に登録された経路に存在する場合、当該経路を代替経路候補とする。
【０３２４】
ステップ２６０１の処理について具体的に説明する。
【０３２５】
まず、経路探索部１３０は、図５Ａに示すリンクデータ５０８を参照し、ステップ１６０１の処理で取得された現在位置から現在走行しているリンクを取得する。
【０３２６】
具体的には、経路探索部１３０は、ステップ１６０１の処理で取得された現在位置であるメッシュ及び座標を特定し、図５Ａに示すリンクデータ５０８に登録されたエントリのうち、特定されたメッシュ及び座標に一致するメッシュコード５０２に登録された識別子によって識別されるメッシュ及び形状５０５に登録される複数の座標のうちいずれかの座標が一致するエントリを選択する。
【０３２７】
そして、経路探索部１３０は、選択されたエントリに含まれるリンクＩＤ５０１に登録された識別子によって識別されるリンクを現在走行しているリンクとして取得する。
【０３２８】
次に、経路探索部１３０は、図５Ａに示すリンクデータ５０８を参照し、進行方向に基づいて、現在走行しているリンクに対応するエントリに含まれる始点ノード５０６又は終点ノード５０７に登録された識別子によって識別されるノードを、次の交差点として取得する。
【０３２９】
次に、経路探索部１３０は、図５Ｂに示すノードデータ５１０に登録されたエントリに含まれるノードＩＤ５１１に登録された識別子のうち、取得されたノードの識別子と一致するすべてのエントリを選択し、選択されたすべてのエントリに含まれる接続リンクＩＤ５１３に登録されるリンクの識別子を取得する。
【０３３０】
次に、経路探索部１３０は、取得されたリンクの識別子のうち、現在走行しているリンクの識別子以外のリンクの識別子を代替経路に含まれるリンクとして取得する。そして、経路探索部１３０は、図２５に示す経路候補データ２５００に登録されたエントリのうち、リンクＩＤ２５０３に登録されたリンクの識別子が取得された代替経路候補に含まれるリンクと一致するエントリを選択する。そして、経路探索部１３０は、選択されたエントリに含まれる経路ＩＤ２５０１に登録される経路の識別子を、代替経路候補を示す識別子として取得する。
【０３３１】
次に、計画策定部１３１は、ステップ２６０１の処理で選択された代替経路候補となる経路を構成するリンクに紐付けられる地点を取得する。そして、計画策定部１３１は、図１３Ｂに示す経由地候補情報１３１０を参照し、取得された地点の分類コードを取得する。そして、計画策定部１３１は、取得された地点の分類コードのうち、ステップ１６０１の処理で生成された分類コードの一覧のいずれかと一致する分類コードを含む地点を経由候補地点として取得する（２６０２）。
【０３３２】
次に、計画策定部１３１は、ステップ１６０４の処理を実行して、経由候補地点を図１４に示す案内画面に表示する。
【０３３３】
これによって、ナビゲーション装置１２０の処理負荷を軽減できるため、処理能力が不足しているナビゲーション装置１２０でも、道案内が可能となる。
【０３３４】
なお、本発明の第１実施例〜第３実施例で説明した実施例は、一例であり、本発明の構成又は処理手順には、各種の変形例があり得る。例えば、ナビゲーション装置１２０の動作制御部１２１の機能の一部を他の装置が備え、ナビゲーション装置１２０は、他の装置に備わる機能によって取得された結果を通信部１２８を介して取得してもよい。
【０３３５】
また、本発明の第１実施例〜第３実施例では、自動車に搭載されるナビゲーション装置１２０について説明したが、利用者が携帯して利用者を道案内するナビゲーション装置であってもよい。
【図面の簡単な説明】
【０３３６】
【図１】本発明の実施形態の運転計画立案システムの構成を示すブロック図である。
【図２】本発明の実施形態の運転計画立案システムによって実行される処理の説明図である。
【図３】本発明の実施形態の運転計画立案支援システムに備わる各装置の処理のフローチャートである。
【図４】本発明の第１実施例の運転計画立案システムのブロック図である。
【図５Ａ】本発明の第１実施例のリンクデータの説明図である。
【図５Ｂ】本発明の第１実施例のノードデータの説明図である。
【図６Ａ】本発明の第１実施例の地点データの説明図である。
【図６Ｂ】本発明の第１実施例の地方データの説明図である。
【図７】本発明の第１実施例の利用者情報の説明図である。
【図８】本発明の第１実施例の運転計画立案画面の説明図である。
【図９】本発明の実施形態の経路設定受付部による代表経路選択処理のフローチャートである。
【図１０】本発明の第１実施例の運転計画編集画面の説明図である。
【図１１】本発明の第１実施例の運転計画生成処理のフローチャートである。
【図１２】本発明の第１実施例の周辺リンク取得処理のフローチャートである。
【図１３Ａ】本発明の第１実施例の運転計画概要情報の説明図である。
【図１３Ｂ】本発明の第１実施例の経由地候補情報の説明図である。
【図１４】本発明の第１実施例のナビゲーション装置に備わる表示装置に表示される案内画面の説明図である。
【図１５】本発明の第１実施例の案内経路提示処理のフローチャートである。
【図１６】本発明の第１実施例の経由候補地点提示処理のフローチャートである。
【図１７】本発明の第２実施例の運転計画立案支援システムのブロック図である。
【図１８】本発明の第２実施例の外部情報表示処理の説明図である。
【図１９】本発明の第２実施例の利用者外部情報使用履歴データの説明図である。
【図２０】本発明の第２実施例の運転計画生成処理のフローチャートである。
【図２１Ａ】本発明の第２実施例の経由地候補情報の説明図である。
【図２１Ｂ】本発明の第２実施例の履歴地点参照情報の説明図である。
【図２２】本発明の第２実施例のナビゲーション装置に備わる表示装置に表示される案内画面の説明図である。な
【図２３】本発明の第３実施例の運転計画生成処理のフローチャートである。
【図２４】本発明の第３実施例の経路候補生成処理のフローチャートである。
【図２５】本発明の第３実施例の経路候補データの説明図である。
【図２６】本発明の第３実施例の経由候補地点提示処理のフローチャートである。
【符号の説明】
【０３３７】
１００ 運転計画立案支援装置
１０１ 動作制御部
１０２ 入力受付部
１０３ 地図データ記憶部
１０４ 利用者情報記憶部
１０５ 通信部
１０６ 外部記憶媒体出力部
１０７ 外部通信部
１０８ 地点情報準備範囲策定部
１０９ 地点候補選択部
１１０ 経路候補選択部
１１１ 運転計画情報生成部
１１２ 外部記憶媒体
１１３ 経路設定受付部
１２０ ナビゲーション装置
１２１ 動作制御部
１２２ 地図データ記憶部
１２３ 現在位置取得部
１２４ 入力受付部
１２５ 画像表示部
１２６ 音声出力部
１２７ 外部記憶媒体読取部
１２８ 通信部
１２９ 状況判定部
１３０ 経路探索部
１３１ 計画策定部
１３２ 提示情報制御部
１３３ ネットワーク
【特許請求の範囲】
【請求項１】
出発地から目的地までの経路を利用者に案内するナビゲーション装置、及び利用者が立ち寄る候補となる経由候補地点を前記ナビゲーション装置が提示するために用いる案内計画情報を生成する案内計画生成装置を備える計算機システムにおいて、
前記案内計画生成装置は、
前記経由候補地点に関する情報を記憶し、
前記ナビゲーション装置の移動範囲を算出し、
前記経由候補地点に関する情報を参照し、前記算出された移動範囲に存在する経由候補地点を選択し、
前記ナビゲーション装置が、前記選択された経由候補地点を利用者に提示するか否かを現在時刻に基づいて判定するための判定情報を生成し、
前記移動範囲に存在する経由候補地点、及び前記各経由候補地点の判定情報を含む前記案内計画情報を生成し、
前記ナビゲーション装置は、
前記案内計画生成装置によって生成された案内計画情報を取得し、
前記取得された案内計画情報に含まれる経由候補地点のうち、前記ナビゲーション装置の現在位置から所定の範囲内に存在する経由候補地点を、提示し得る経由候補地点として選択し、
前記選択された提示し得る経由候補地点の判定情報が、現在時刻に適合する経由候補地点を、提示経由候補地点として取得し、
前記取得された提示経由候補地点、及び前記現在位置から前記提示経由候補地点までの経路を利用者に提示することを特徴とする計算機システム。
【請求項２】
前記案内計画生成装置は、前記経由候補地点に関する情報として、前記経由候補地点で提供される商品又は役務の種類を記憶し、
前記判定情報は、前記経由候補地点で提供される商品又は役務の種類を含み、
前記案内計画生成装置は、前記案内計画情報に含まれる経由候補地点のうち、前記判定情報に含まれる商品又は役務の種類が前記現在時刻に適合する経由候補地点を、前記提示経由候補地点として取得することを特徴とする請求項１に記載の計算機システム。
【請求項３】
前記案内計画生成装置は、前記案内計画生成装置に記憶された前記経由候補地点に関する情報を参照する要求を利用者から受け付けた場合に、前記参照の要求を受け付けた経由候補地点に関する情報を利用者に提示し、
前記判定情報は、前記参照の要求を受け付けた回数を含み、
前記ナビゲーション装置は、前記参照要求を受け付けた回数が多い経由候補地点を優先して利用者に提示することを特徴とする請求項１に記載の計算機システム。
【請求項４】
前記案内計画生成装置は、
道路を、二つの交差点の間を接続するリンクに区分したリンク情報を記憶し、
前記出発地に接続されるリンクを移動するために必要な時間又は前記リンクの距離を示すコストを参照して、前記コストが最小となるリンクを選択し、前記選択されたリンクに接続されるリンクのコストに、前記出発地から前記選択されたリンクまでのコストを加算することによって、累積コストを算出し、前記算出された累積コストが最小となるリンクを選択する処理を、前記目的地まで繰り返し実行し、
前記累積コストが最小となるリンクを選択するためにコストが参照されたリンクを、前記ナビゲーション装置の移動範囲として算出することを特徴とする請求項１に記載の計算機システム。
【請求項５】
前記計算機システムは、経由候補地点に関する情報を利用者に提供する地点情報提供装置をさらに備え、
前記地点情報提供装置は、
情報の提供が要求された経路候補地点に関する情報を前記案内計画生成装置に送信し、
前記案内計画生成装置は、前記地点情報提供装置から送信された前記情報の提供が要求された経由候補地点のうち前記算出された移動範囲に存在する経由候補地点、及び前記算出された移動範囲に存在する各経由候補地点の判定情報を含む前記案内計画情報を生成することを特徴とする請求項１に記載の計算機システム。
【請求項６】
前記案内計画生成装置は、
前記移動範囲において、前記出発地から前記目的地までの複数の経路候補となる経路を算出し、
前記算出された経路候補となる経路上に位置する経由候補地点を選択し、
前記経路候補となる経路上に位置する経由候補地点、前記各経由候補地点の判定情報、及び前記経路候補となる経路を含む案内計画情報を生成し、
前記ナビゲーション装置は、
前記案内計画情報に含まれる経路候補となる経路のうち、前記現在位置から進行可能な経路を選択し、
前記現在位置から進入可能な経路として選択された経路上に位置する経由候補地点の判定情報が、前記現在時刻に適合する経由候補地点を、前記提示経由候補地点として取得し、
前記現在位置から進入可能な経路として選択された経路、及び前記取得された提示経由候補地点を利用者に提示することを特徴とする請求項１に記載の計算機システム。
【請求項７】
利用者が立ち寄る経由候補地点を提示しながら出発地から目的地までの経路を利用者に案内するナビゲーション装置、及び前記ナビゲーション装置が経路を案内するために用いる案内計画情報を生成する案内計画生成装置を備える計算機システムにおける経路案内方法において、
前記案内計画生成装置は、
前記経由候補地点に関する情報を記憶し、
前記ナビゲーション装置の移動範囲を算出し、
前記経由候補地点に関する情報を参照し、前記算出された移動範囲に存在する経由候補地点を選択し、
前記ナビゲーション装置が、前記選択された経由候補地点を利用者に提示するか否かを現在時刻に基づいて判定するための判定情報を生成し、
前記移動範囲に存在する経由候補地点、及び前記各経由候補地点の判定情報を含む前記案内計画情報を生成し、
前記ナビゲーション装置は、
前記案内計画生成装置によって生成された案内計画情報を取得し、
前記取得された案内計画情報に含まれる経由候補地点のうち、前記ナビゲーション装置の現在位置から所定の範囲内に存在する経由候補地点を、提示し得る経由候補地点として選択し、
前記選択された提示し得る経由候補地点の判定情報が、現在時刻に適合する経由候補地点を、提示経由候補地点として取得し、
前記取得された提示経由候補地点、及び前記現在位置から前記提示経由候補地点までの経路を利用者に提示することを特徴とする経路案内方法。
【請求項８】
前記案内計画生成装置は、前記経由候補地点に関する情報として、前記経由候補地点で提供される商品又は役務の種類を記憶し、
前記判定情報は、前記経由候補地点で提供される商品又は役務の種類を含み、
前記案内計画生成装置は、前記案内計画情報に含まれる経由候補地点のうち、前記判定情報に含まれる商品又は役務の種類が前記現在時刻に適合する経由候補地点を、前記提示経由候補地点として取得することを特徴とする請求項７に記載の経路案内方法。
【請求項９】
前記案内計画生成装置は、前記案内計画生成装置に記憶された前記経由候補地点に関する情報を参照する要求を利用者から受け付けた場合に、前記参照の要求を受け付けた経由候補地点に関する情報を利用者に提示し、
前記判定情報は、前記参照の要求を受け付けた回数を含み、
前記ナビゲーション装置は、前記参照要求を受け付けた回数が多い経由候補地点を優先して利用者に提示することを特徴とする請求項７に記載の経路案内方法。
【請求項１０】
前記案内計画生成装置は、
道路を、二つの交差点の間を接続するリンクに区分したリンク情報を記憶し、
前記出発地に接続されるリンクを移動するために必要な時間又は前記リンクの距離を示すコストを参照して、前記コストが最小となるリンクを選択し、前記選択されたリンクに接続されるリンクのコストに、前記出発地から前記選択されたリンクまでのコストを加算することによって、累積コストを算出し、前記算出された累積コストが最小となるリンクを選択する処理を、前記目的地まで繰り返し実行し、
前記累積コストが最小となるリンクを選択するためにコストが参照されたリンクを、前記ナビゲーション装置の移動範囲として算出することを特徴とする請求項７に記載の経路案内方法。
【請求項１１】
前記計算機システムは、経由候補地点に関する情報を利用者に提供する地点情報提供装置をさらに備え、
前記地点情報提供装置は、
情報の提供が要求された経路候補地点に関する情報を前記案内計画生成装置に送信し、
前記案内計画生成装置は、前記地点情報提供装置から送信された前記情報の提供が要求された経由候補地点のうち前記算出された移動範囲に存在する経由候補地点、及び前記算出された移動範囲に存在する各経由候補地点の判定情報を含む前記案内計画情報を生成することを特徴とする請求項７に記載の経路案内方法。
【請求項１２】
前記案内計画生成装置は、
前記移動範囲において、前記出発地から前記目的地までの複数の経路候補となる経路を算出し、
前記算出された経路候補となる経路上に位置する経由候補地点を選択し、
前記経路候補となる経路上に位置する経由候補地点、前記各経由候補地点の判定情報、及び前記経路候補となる経路を含む案内計画情報を生成し、
前記ナビゲーション装置は、
前記案内計画情報に含まれる経路候補となる経路のうち、前記現在位置から進行可能な経路を選択し、
前記現在位置から進入可能な経路として選択された経路上に位置する経由候補地点の判定情報が、前記現在時刻に適合する経由候補地点を、前記提示経由候補地点として取得し、
前記現在位置から進入可能な経路として選択された経路、及び前記取得された提示経由候補地点を利用者に提示することを特徴とする請求項７に記載の経路案内方法。
【請求項１】
出発地から目的地までの経路を利用者に案内するナビゲーション装置、及び利用者が立ち寄る候補となる経由候補地点を前記ナビゲーション装置が提示するために用いる案内計画情報を生成する案内計画生成装置を備える計算機システムにおいて、
前記案内計画生成装置は、
前記経由候補地点に関する情報を記憶し、
前記ナビゲーション装置の移動範囲を算出し、
前記経由候補地点に関する情報を参照し、前記算出された移動範囲に存在する経由候補地点を選択し、
前記ナビゲーション装置が、前記選択された経由候補地点を利用者に提示するか否かを現在時刻に基づいて判定するための判定情報を生成し、
前記移動範囲に存在する経由候補地点、及び前記各経由候補地点の判定情報を含む前記案内計画情報を生成し、
前記ナビゲーション装置は、
前記案内計画生成装置によって生成された案内計画情報を取得し、
前記取得された案内計画情報に含まれる経由候補地点のうち、前記ナビゲーション装置の現在位置から所定の範囲内に存在する経由候補地点を、提示し得る経由候補地点として選択し、
前記選択された提示し得る経由候補地点の判定情報が、現在時刻に適合する経由候補地点を、提示経由候補地点として取得し、
前記取得された提示経由候補地点、及び前記現在位置から前記提示経由候補地点までの経路を利用者に提示することを特徴とする計算機システム。
【請求項２】
前記案内計画生成装置は、前記経由候補地点に関する情報として、前記経由候補地点で提供される商品又は役務の種類を記憶し、
前記判定情報は、前記経由候補地点で提供される商品又は役務の種類を含み、
前記案内計画生成装置は、前記案内計画情報に含まれる経由候補地点のうち、前記判定情報に含まれる商品又は役務の種類が前記現在時刻に適合する経由候補地点を、前記提示経由候補地点として取得することを特徴とする請求項１に記載の計算機システム。
【請求項３】
前記案内計画生成装置は、前記案内計画生成装置に記憶された前記経由候補地点に関する情報を参照する要求を利用者から受け付けた場合に、前記参照の要求を受け付けた経由候補地点に関する情報を利用者に提示し、
前記判定情報は、前記参照の要求を受け付けた回数を含み、
前記ナビゲーション装置は、前記参照要求を受け付けた回数が多い経由候補地点を優先して利用者に提示することを特徴とする請求項１に記載の計算機システム。
【請求項４】
前記案内計画生成装置は、
道路を、二つの交差点の間を接続するリンクに区分したリンク情報を記憶し、
前記出発地に接続されるリンクを移動するために必要な時間又は前記リンクの距離を示すコストを参照して、前記コストが最小となるリンクを選択し、前記選択されたリンクに接続されるリンクのコストに、前記出発地から前記選択されたリンクまでのコストを加算することによって、累積コストを算出し、前記算出された累積コストが最小となるリンクを選択する処理を、前記目的地まで繰り返し実行し、
前記累積コストが最小となるリンクを選択するためにコストが参照されたリンクを、前記ナビゲーション装置の移動範囲として算出することを特徴とする請求項１に記載の計算機システム。
【請求項５】
前記計算機システムは、経由候補地点に関する情報を利用者に提供する地点情報提供装置をさらに備え、
前記地点情報提供装置は、
情報の提供が要求された経路候補地点に関する情報を前記案内計画生成装置に送信し、
前記案内計画生成装置は、前記地点情報提供装置から送信された前記情報の提供が要求された経由候補地点のうち前記算出された移動範囲に存在する経由候補地点、及び前記算出された移動範囲に存在する各経由候補地点の判定情報を含む前記案内計画情報を生成することを特徴とする請求項１に記載の計算機システム。
【請求項６】
前記案内計画生成装置は、
前記移動範囲において、前記出発地から前記目的地までの複数の経路候補となる経路を算出し、
前記算出された経路候補となる経路上に位置する経由候補地点を選択し、
前記経路候補となる経路上に位置する経由候補地点、前記各経由候補地点の判定情報、及び前記経路候補となる経路を含む案内計画情報を生成し、
前記ナビゲーション装置は、
前記案内計画情報に含まれる経路候補となる経路のうち、前記現在位置から進行可能な経路を選択し、
前記現在位置から進入可能な経路として選択された経路上に位置する経由候補地点の判定情報が、前記現在時刻に適合する経由候補地点を、前記提示経由候補地点として取得し、
前記現在位置から進入可能な経路として選択された経路、及び前記取得された提示経由候補地点を利用者に提示することを特徴とする請求項１に記載の計算機システム。
【請求項７】
利用者が立ち寄る経由候補地点を提示しながら出発地から目的地までの経路を利用者に案内するナビゲーション装置、及び前記ナビゲーション装置が経路を案内するために用いる案内計画情報を生成する案内計画生成装置を備える計算機システムにおける経路案内方法において、
前記案内計画生成装置は、
前記経由候補地点に関する情報を記憶し、
前記ナビゲーション装置の移動範囲を算出し、
前記経由候補地点に関する情報を参照し、前記算出された移動範囲に存在する経由候補地点を選択し、
前記ナビゲーション装置が、前記選択された経由候補地点を利用者に提示するか否かを現在時刻に基づいて判定するための判定情報を生成し、
前記移動範囲に存在する経由候補地点、及び前記各経由候補地点の判定情報を含む前記案内計画情報を生成し、
前記ナビゲーション装置は、
前記案内計画生成装置によって生成された案内計画情報を取得し、
前記取得された案内計画情報に含まれる経由候補地点のうち、前記ナビゲーション装置の現在位置から所定の範囲内に存在する経由候補地点を、提示し得る経由候補地点として選択し、
前記選択された提示し得る経由候補地点の判定情報が、現在時刻に適合する経由候補地点を、提示経由候補地点として取得し、
前記取得された提示経由候補地点、及び前記現在位置から前記提示経由候補地点までの経路を利用者に提示することを特徴とする経路案内方法。
【請求項８】
前記案内計画生成装置は、前記経由候補地点に関する情報として、前記経由候補地点で提供される商品又は役務の種類を記憶し、
前記判定情報は、前記経由候補地点で提供される商品又は役務の種類を含み、
前記案内計画生成装置は、前記案内計画情報に含まれる経由候補地点のうち、前記判定情報に含まれる商品又は役務の種類が前記現在時刻に適合する経由候補地点を、前記提示経由候補地点として取得することを特徴とする請求項７に記載の経路案内方法。
【請求項９】
前記案内計画生成装置は、前記案内計画生成装置に記憶された前記経由候補地点に関する情報を参照する要求を利用者から受け付けた場合に、前記参照の要求を受け付けた経由候補地点に関する情報を利用者に提示し、
前記判定情報は、前記参照の要求を受け付けた回数を含み、
前記ナビゲーション装置は、前記参照要求を受け付けた回数が多い経由候補地点を優先して利用者に提示することを特徴とする請求項７に記載の経路案内方法。
【請求項１０】
前記案内計画生成装置は、
道路を、二つの交差点の間を接続するリンクに区分したリンク情報を記憶し、
前記出発地に接続されるリンクを移動するために必要な時間又は前記リンクの距離を示すコストを参照して、前記コストが最小となるリンクを選択し、前記選択されたリンクに接続されるリンクのコストに、前記出発地から前記選択されたリンクまでのコストを加算することによって、累積コストを算出し、前記算出された累積コストが最小となるリンクを選択する処理を、前記目的地まで繰り返し実行し、
前記累積コストが最小となるリンクを選択するためにコストが参照されたリンクを、前記ナビゲーション装置の移動範囲として算出することを特徴とする請求項７に記載の経路案内方法。
【請求項１１】
前記計算機システムは、経由候補地点に関する情報を利用者に提供する地点情報提供装置をさらに備え、
前記地点情報提供装置は、
情報の提供が要求された経路候補地点に関する情報を前記案内計画生成装置に送信し、
前記案内計画生成装置は、前記地点情報提供装置から送信された前記情報の提供が要求された経由候補地点のうち前記算出された移動範囲に存在する経由候補地点、及び前記算出された移動範囲に存在する各経由候補地点の判定情報を含む前記案内計画情報を生成することを特徴とする請求項７に記載の経路案内方法。
【請求項１２】
前記案内計画生成装置は、
前記移動範囲において、前記出発地から前記目的地までの複数の経路候補となる経路を算出し、
前記算出された経路候補となる経路上に位置する経由候補地点を選択し、
前記経路候補となる経路上に位置する経由候補地点、前記各経由候補地点の判定情報、及び前記経路候補となる経路を含む案内計画情報を生成し、
前記ナビゲーション装置は、
前記案内計画情報に含まれる経路候補となる経路のうち、前記現在位置から進行可能な経路を選択し、
前記現在位置から進入可能な経路として選択された経路上に位置する経由候補地点の判定情報が、前記現在時刻に適合する経由候補地点を、前記提示経由候補地点として取得し、
前記現在位置から進入可能な経路として選択された経路、及び前記取得された提示経由候補地点を利用者に提示することを特徴とする請求項７に記載の経路案内方法。
【図１】
【図２】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６Ａ】
【図６Ｂ】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１Ａ】
【図２１Ｂ】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６Ａ】
【図６Ｂ】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１Ａ】
【図２１Ｂ】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【公開番号】特開２０１０−４３９６４（Ｐ２０１０−４３９６４Ａ）
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願番号】特願２００８−２０８４０３（Ｐ２００８−２０８４０３）
【出願日】平成２０年８月１３日（２００８．８．１３）
【出願人】（５９１１３２３３５）株式会社ザナヴィ・インフォマティクス (745)
【Ｆターム（参考）】
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願日】平成２０年８月１３日（２００８．８．１３）
【出願人】（５９１１３２３３５）株式会社ザナヴィ・インフォマティクス (745)
【Ｆターム（参考）】
[ Back to top ]