(57)【要約】【課題】小さい記憶容量で高速に経路計算を行う。【解決手段】入力情報と経路計算要求信号とが供給される入力情報受信手段と、入力情報に基づいて推薦経路と推薦分岐経路の経路を計算する第１の経路計算手段１０ｂと、分岐点情報と道路リンク数と進行方向情報とを特徴点候補情報として算出する特徴点候補算出手段１０ｄと、経路計算のオーバー時間内に計算された特徴点候補情報を道路リンク数の多い順に特徴点情報として抽出する特徴点情報算出手段１０ｅと、特徴点情報を含む特徴点履歴情報に基づいて経路を計算する第２の経路計算手段１０ｆと、経路計算要求信号が供給されたときに、供給された入力情報が読み出した特徴点履歴情報の入力情報に各々一致する場合には第２の経路計算手段１０ｆに経路を計算させ、一致しない場合には第１の経路計算手段１０ｃに経路を計算させる経路計算判定手段１０ｇとを備える。【選択図】図１
2008241553.tif 000002
【特許請求の範囲】
【請求項１】
自装置の現在地を検出すると共に、表示部に表示された地図上の１つの地点を目的地として設定し、利用者操作により入力された探索条件に基づいて現在地から目的地までの経路計算を行う経路計算装置であって、
現在地を示す現在地情報と目的地を示す目的地情報と探索条件を示す探索条件情報と経路計算を要求する経路計算要求信号とが供給される入力情報受信手段と、
前記現在地情報と前記目的地情報と前記探索条件情報とから現在地から目的地までの経路を計算し、この計算した経路のうち最も前記探索条件に適合する経路を推薦経路とし、この推薦経路上に存在する分岐点から分岐する経路を推薦分岐経路とする第１の経路計算手段と、
前記第１の経路計算手段が推薦経路の計算に要した計算所要時間を計測する時間計測手段と、
計測された計算所要時間が所定時間以上である場合に、前記分岐点を示す分岐点情報と、前記推薦分岐経路上に存在する分岐点と分岐点を結ぶ経路数を示す道路リンク数と、前記推薦経路上に存在する分岐点における進行方向を示す進行方向情報とを特徴点候補情報として算出する特徴点候補算出手段と、
前記計算所要時間の内、前記所定時間を越えた分をオーバー時間として算出し、前記第１の経路計算手段により前記オーバー時間内に計算された推薦経路上の各分岐点における特徴点候補情報を前記道路リンク数の多い順に特徴点情報として抽出する特徴点情報算出手段と、
前記入力情報受信手段に経路計算要求信号が供給されたときの現在地情報と目的地情報と探索条件情報と特徴点情報とを関連付けて特徴点履歴情報として記憶する特徴点記憶手段と、
前記特徴点記憶手段に記憶された特徴点履歴情報を読み出し、読み出した特徴点履歴情報に基づいて特徴点情報が示す特徴点間の経路を計算し、計算した特徴点間の経路に基づいて現在地から目的地までの経路を計算する第２の経路計算手段と、
前記入力情報受信手段に経路計算要求信号が供給されたときに、前記特徴点記憶手段に記憶された特徴点履歴情報を読み出し、前記入力情報受信手段に供給された現在地情報と目的地情報と探索条件情報とが、前記読み出した特徴点履歴情報の現在地情報と目的地情報と探索条件情報に各々一致するか否かを判定し、一致する場合には前記第２の経路計算手段に経路を計算させ、一致しない場合には前記第１の経路計算手段に経路を計算させる経路計算判定手段と
を備えたことを特徴とする経路計算装置。
【請求項２】
自装置の現在地を検出すると共に、表示部に表示された地図上の１つの地点を目的地として設定し、利用者操作により入力された探索条件に基づいて現在地から目的地までの経路計算を行う経路計算装置であって、
現在地を示す現在地情報と目的地を示す目的地情報と探索条件を示す探索条件情報と経路計算を要求する経路計算要求信号とが供給される入力情報受信手段と、
前記現在地情報と前記目的地情報と前記探索条件情報とから現在地から目的地までの経路を計算し、この計算した経路のうち最も前記探索条件に適合する経路を推薦経路とし、この推薦経路上に存在する分岐点から分岐する経路を推薦分岐経路とする第１の経路計算手段と、
前記分岐点を示す分岐点情報と、前記推薦分岐経路上に存在する分岐点と分岐点を結ぶ経路数を示す道路リンク数と、前記推薦経路上に存在する分岐点における進行方向を示す進行方向情報とを特徴点候補情報として算出する特徴点候補算出手段と、
前記特徴点候補情報の数が予め定めた閾値より大きい場合には、前記閾値を特徴点情報数として決定し、この決定した特徴点情報数に相当する前記特徴点候補情報を前記道路リンク数が多い順に特徴点情報として抽出する特徴点情報算出手段と、
前記入力情報受信手段に経路計算要求信号が供給されたときの現在地情報と目的地情報と探索条件情報と特徴点情報とを関連付けて特徴点履歴情報として記憶する特徴点記憶手段と、
前記特徴点記憶手段に記憶された特徴点履歴情報を読み出し、読み出した特徴点履歴情報に基づいて特徴点情報が示す特徴点間の経路を計算し、計算した特徴点間の経路に基づいて現在地から目的地までの経路を計算する第２の経路計算手段と、
前記入力情報受信手段に経路計算要求信号が供給されたときに、前記特徴点記憶手段に記憶された特徴点履歴情報を読み出し、前記入力情報受信手段に供給された現在地情報と目的地情報と探索条件情報とが、前記読み出した特徴点履歴情報の現在地情報と目的地情報と探索条件情報に各々一致するか否かを判定し、一致する場合には前記第２の経路計算手段に経路を計算させ、一致しない場合には前記第１の経路計算手段に経路を計算させる経路計算判定手段と
を備えたことを特徴とする経路計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自車両の現在地から設定された目的地までの経路計算を行う経路計算装置に関する。
【背景技術】
【０００２】
車両に装備されるナビゲーション装置は、車両の現在位置を測定し、測定した現在位置から利用者が設定した目的地までの経路計算を行い、計算した経路に基づいて自車両を誘導する機能を提供するものである。この機能によって利用者は容易にかつ確実に目的地へ到着することができる。
【０００３】
しかしながら、上記のような経路計算を行う際、経路の候補が多い場合、即ち道路上の分岐点が多い場合等経路計算に時間がかかり、利用者はストレスを感じる場合があった。
【０００４】
そこで、特許文献１には、現在位置の検出が開始されると、予め記憶するメモリ地点や過去に目的地として設定された地点を終点とし、現在位置を始点とする経路を計算し、計算した経路を記憶部に記憶する。そして、ユーザがメモリ地点や過去に目的地として設定した地点を目的地として設定する場合には、ユーザの設定した目的地を終点とする既に計算済みの経路を記憶部から読み出し、この読み出した経路を経路案内に利用するナビゲーション装置が提案されている。
【特許文献１】特開２００３−１５６３４９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に記載のナビゲーション装置では、記憶部にユーザの設定した目的地を終点とする計算済みの経路の全てを履歴情報として記憶させておくので、この記憶部に記憶された履歴情報の数に比例して必要とされる記憶容量が膨大となる可能性があった。また、履歴情報の記憶に必要な記憶容量は、出発地と目的地の距離に依存するので、出発地と目的地との間の距離が大きい長距離の履歴情報を複数記録する場合には、限られた記憶部の資源を大きく圧迫することになりかねなかった。
【０００６】
また、近年では、持ち運びが可能であり、かつ大容量のハードディスクを搭載しないポータブルタイプのナビゲーションシステムが市場に投入されており、記憶容量を節約し、かつ高速に経路計算を行う経路計算装置が切望されていた。
【０００７】
本発明は、上記問題点に鑑みてなされたものであり、小さい記憶容量で高速に経路計算を行う経路計算装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を解決するため、本発明に係る経路計算装置の第１の特徴は、現在地を示す現在地情報と目的地を示す目的地情報と探索条件を示す探索条件情報と経路計算を要求する経路計算要求信号とが供給される入力情報受信手段と、現在地情報と目的地情報と探索条件情報とから現在地から目的地までの経路を計算し、この計算した経路のうち最も探索条件に適合する経路を推薦経路とし、この推薦経路上に存在する分岐点から分岐する経路を推薦分岐経路とする第１の経路計算手段と、第１の経路計算手段が推薦経路の計算に要した計算所要時間を計測する時間計測手段と、計測された計算所要時間が所定時間以上である場合に、分岐点を示す分岐点情報と、推薦分岐経路上に存在する分岐点と分岐点を結ぶ経路数を示す道路リンク数と、推薦経路上に存在する分岐点における進行方向を示す進行方向情報とを特徴点候補情報として算出する特徴点候補算出手段と、計算所要時間の内、所定時間を越えた分をオーバー時間として算出し、第１の経路計算手段によりオーバー時間内に計算された推薦経路上の各分岐点における特徴点候補情報を道路リンク数の多い順に特徴点情報として抽出する特徴点情報算出手段と、入力情報受信手段に経路計算要求信号が供給されたときの現在地情報と目的地情報と探索条件情報と特徴点情報とを関連付けて特徴点履歴情報として記憶する特徴点記憶手段と、特徴点記憶手段に記憶された特徴点履歴情報を読み出し、読み出した特徴点履歴情報に基づいて特徴点情報が示す特徴点間の経路を計算し、計算した特徴点間の経路に基づいて現在地から目的地までの経路を計算する第２の経路計算手段と、入力情報受信手段に経路計算要求信号が供給されたときに、特徴点記憶手段に記憶された特徴点履歴情報を読み出し、入力情報受信手段に供給された現在地情報と目的地情報と探索条件情報とが、読み出した特徴点履歴情報の現在地情報と目的地情報と探索条件情報に各々一致するか否かを判定し、一致する場合には第２の経路計算手段に経路を計算させ、一致しない場合には第１の経路計算手段に経路を計算させる経路計算判定手段とを備えたことにある。
【０００９】
上記目的を解決するため、本発明に係る経路計算装置の第２の特徴は、現在地を示す現在地情報と目的地を示す目的地情報と探索条件を示す探索条件情報と経路計算を要求する経路計算要求信号とが供給される入力情報受信手段と、現在地情報と目的地情報と探索条件情報とから現在地から目的地までの経路を計算し、この計算した経路のうち最も探索条件に適合する経路を推薦経路とし、この推薦経路上に存在する分岐点から分岐する経路を推薦分岐経路とする第１の経路計算手段と、分岐点を示す分岐点情報と、推薦分岐経路上に存在する分岐点と分岐点を結ぶ経路数を示す道路リンク数と、推薦経路上に存在する分岐点における進行方向を示す進行方向情報とを特徴点候補情報として算出する特徴点候補算出手段と、特徴点候補情報の数が予め定めた閾値より大きい場合には、閾値を特徴点情報数として決定し、この決定した特徴点情報数に相当する前記特徴点候補情報を前記道路リンク数が多い順に特徴点情報として抽出する特徴点情報算出手段と、入力情報受信手段に経路計算要求信号が供給されたときの現在地情報と目的地情報と探索条件情報と特徴点情報とを関連付けて特徴点履歴情報として記憶する特徴点記憶手段と、特徴点記憶手段に記憶された特徴点履歴情報を読み出し、読み出した特徴点履歴情報に基づいて特徴点情報が示す特徴点間の経路を計算し、計算した特徴点間の経路に基づいて現在地から目的地までの経路を計算する第２の経路計算手段と、入力情報受信手段に経路計算要求信号が供給されたときに、特徴点記憶手段に記憶された特徴点履歴情報を読み出し、入力情報受信手段に供給された現在地情報と目的地情報と探索条件情報とが、読み出した特徴点履歴情報の現在地情報と目的地情報と探索条件情報に各々一致するか否かを判定し、一致する場合には第２の経路計算手段に経路を計算させ、一致しない場合には第１の経路計算手段に経路を計算させる経路計算判定手段とを備えたことにある。
【発明の効果】
【００１０】
本発明に係る経路計算装置によれば、小さい記憶容量で高速に経路計算を行うことができる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明を実施するための最良の形態について図面を参照して説明する。
【００１２】
＜第１の実施形態＞
図１は、本発明を実施するための第１の実施形態である経路計算装置の構成を示したブロック図である。
【００１３】
図１に示すように、経路計算装置１は、ＣＰＵ１０と、このＣＰＵ１０に接続された特徴点記憶部１１、入力部１２、ＧＰＳセンサ１３、音声出力部１４、及び表示部１５を備えている。
【００１４】
ＣＰＵ１０は、入力情報受信手段１０ａと、第１の経路計算手段１０ｂと、時間計測手段１０ｃと、特徴点候補算出手段１０ｄと、特徴点情報算出手段１０ｅと、第２の経路計算手段１０ｆと、経路計算判定手段１０ｇと、出力制御手段１０ｈとを備えており、経路誘導プログラム等のプログラムに従って、経路計算判定処理や経路計算処理等の各種処理を実行する。
【００１５】
特徴点記憶部１１は、メモリやＨＤＤ等の記憶媒体であり、特徴点履歴情報として目的地履歴情報テーブル及び目的地履歴詳細情報テーブルを記憶し、その他にも経路誘導プログラム等のＣＰＵ１０が処理を実行する上で必要な情報を記憶する。
【００１６】
図２は、特徴点記憶部１１が記憶している目的地履歴情報テーブルの一例を示した説明図である。
【００１７】
図２に示すように、特徴点記憶部１１は、カラム名“目的地名称”（符号２１）と、カラム名“目的地位置”（符号２２）と、外部キーとしてカラム名“探索条件詳細番号”（符号２３）とを関連付けて目的地履歴情報テーブルとして記憶している。ここで、カラム名“目的地名称”（符号２１）、又はカラム名“目的地位置”（符号２２）が目的地情報となる。
【００１８】
図３は、特徴点記憶部１１が記憶している目的地履歴詳細情報テーブルの一例を示した説明図である。
【００１９】
図３に示すように、特徴点記憶部１１は、主キーとしてカラム名“探索条件詳細番号”（符号３１）と、カラム名“出発地情報”（符号３２）と、カラム名“探索条件情報”（符号３３）と、カラム名“特徴点情報の数”（符号３４）と、カラム名“特徴点情報”（符号４３）とを関連付けて目的地履歴詳細情報テーブルとして記憶している。
【００２０】
入力部１２は、タッチパネルやリモートコントロール装置等であり、利用者の操作により目的地を示す情報である目的地情報、探索条件を示す情報である探索条件情報、及び経路計算を要求する経路計算要求信号を生成し、生成した目的地情報、探索条件情報、及び経路計算要求信号をＣＰＵ１０へ送信する。
【００２１】
ＧＰＳセンサ１３は、車両の位置を検出するためのＧＰＳ衛星からのＧＰＳ信号を受信し、受信したＧＰＳ信号に基づいて、現在地を示す現在地情報を生成し、生成した現在地情報をＣＰＵ１０へ送信する。
【００２２】
音声出力部１４は、例えばスピーカ等であり、走行中に適切なタイミングで経路の音声案内を出力する。表示部１５は、例えば液晶ディスプレイ等であり、ＣＰＵ１０からの出力信号を受信して地図、経路及び指示案内等を表示する装置である。
【００２３】
ＣＰＵ１０の入力情報受信手段１０ａは、現在地を示す現在地情報と目的地を示す目的地情報と探索条件を示す探索条件情報と経路計算を要求する経路計算要求信号とを受信する。
【００２４】
ＣＰＵ１０の第１の経路計算手段１０ｂは、現在地情報と目的地情報と探索条件情報とから現在地から目的地までの経路を計算し、この計算した経路のうち最も探索条件に適合する経路を推薦経路とし、この推薦経路上に存在する分岐点から分岐する経路を推薦分岐経路とする。
【００２５】
ＣＰＵ１０の時間計測手段１０ｃは、第１の経路計算手段１０ｂが推薦経路の計算に要した計算所要時間を計測する。
【００２６】
ＣＰＵ１０の特徴点候補算出手段１０ｄは、計測された計算所要時間が所定時間以上である場合に、分岐点を示す分岐点情報と、推薦分岐経路上に存在する分岐点と分岐点を結ぶ経路数を示す道路リンク数と、推薦経路上に存在する分岐点における進行方向を示す進行方向情報とを特徴点候補情報として算出する。
【００２７】
ＣＰＵ１０の特徴点情報算出手段１０ｅは、計算所要時間の内、所定時間を越えた分をオーバー時間として算出し、第１の経路計算手段１０ｂによりオーバー時間内に計算された推薦経路上の各分岐点における特徴点候補情報を道路リンク数の多い順に特徴点情報として抽出する。
【００２８】
ＣＰＵ１０の第２の経路計算手段１０ｆは、特徴点記憶手段１１に記憶された特徴点履歴情報を読み出し、読み出した特徴点履歴情報に基づいて特徴点情報が示す特徴点間の経路を計算し、計算した特徴点間の経路に基づいて現在地から目的地までの経路を計算する。
【００２９】
ＣＰＵ１０の経路計算判定手段１０ｇは、入力情報受信手段１０ａに経路計算要求信号が供給されたときに、特徴点記憶手段１１に記憶された特徴点履歴情報を読み出し、入力情報受信手段１０ａに供給された現在地情報と目的地情報と探索条件情報とが、読み出した特徴点履歴情報の現在地情報と目的地情報と探索条件情報に各々一致するか否かを判定し、一致する場合には第２の経路計算手段１０ｆに経路を計算させ、一致しない場合には第１の経路計算手段１０ｃに経路を計算させる。
【００３０】
ＣＰＵ１０の出力制御手段１０ｈは、第１の経路計算手段１０ｂ又は第２の経路計算手段１０ｆにより計算された現在地から目的地までの経路に基づいて、音声出力部１４及び表示部１５に経路案内を出力させる。
【００３１】
≪経路計算装置の作用≫
次に図４のフローチャートに従って、第１の実施形態である経路計算装置１における処理手順について説明する。
【００３２】
まず、経路計算装置１のＣＰＵ１０の入力情報受信手段１０ａは、ＧＰＳセンサ１３により生成された現在地を示す情報である現在地情報を受信し、さらに、入力部１２により生成された目的地を示す情報である目的地情報と探索条件を示す情報である探索条件情報と経路計算を要求する経路計算要求信号とを受信する。
【００３３】
そして、ＣＰＵ１０の経路計算判定手段１０ｇは、入力情報受信手段１０ａから経路計算要求信号、現在地情報、及び目的地情報が供給されると、目的地情報が示す目的地が新規に設定された地点であるか、又は過去に設定されたことのある地点かを判定する。具体的には、ＣＰＵ１０の経路計算判定手段１０ｇは、特徴点記憶部１１から目的地履歴情報を読み出し、入力情報受信手段１０ａから供給された目的地情報が、読み出した目的地履歴情報の目的地情報と一致するか否かを判定する（ステップＳ１００）。
【００３４】
そして、経路計算判定手段１０ｇは、目的地情報が示す目的地が新規に設定された地点であると判定した場合には、探索条件情報が示す探索条件が新規に設定された条件であるか、又は過去に設定されたことのある条件かを判定する。具体的には、ＣＰＵ１０の経路計算判定手段１０ｇは、特徴点記憶部１１から目的地履歴詳細情報を読み出し、入力情報受信手段１０ａから供給された探索条件情報が、読み出した目的地履歴詳細情報の探索条件情報と一致するか否かを判定する（ステップＳ１０１）。
【００３５】
そして、ＣＰＵ１０の経路計算判定手段１０ｇが、ステップＳ１００において目的地情報が示す目的地が新規に設定された地点であると判定し、又はステップＳ１０１において、探索条件情報が示す探索条件が新規に設定された条件であると判定した場合には、時間計測手段１０ｃは、第１の経路計算手段１０ｂが経路計算を行うのに要する計算所要時間の計測を開始する（ステップＳ１０２）。
【００３６】
次に、ＣＰＵ１０の経路計算判定手段１０ｇは、経路を計算させる経路計算指示信号を第１の経路計算手段１０ｂに送信する。そして、経路計算指示信号を受信した第１の経路計算手段１０ｂは、入力情報受信手段１０ａに供給された現在地情報と目的地情報と探索条件情報に基づいて現在地から目的地までの経路を計算する（ステップＳ１０３）。そして、第１の経路計算手段１０ｂは、計算した経路のうち、最も探索条件に適合する経路を推薦経路とし、この推薦経路上に存在する分岐点から分岐する経路を推薦分岐経路とする。
【００３７】
図５は、第１の経路計算手段１０ｂにより経路計算された推薦経路を示した説明図である。
【００３８】
図５に示すように、入力情報受信手段１０ａに供給された現在地情報が示す現在地５０から目的地情報が示す目的地５１までの推薦経路５２を算出している。ここで推薦経路は、経路計算した経路の中で、入力情報受信手段１０ａに供給された探索条件に最も適合している経路のことをいう。
【００３９】
図６は、第１の経路計算手段１０ｂにより経路計算された推薦経路、及び推薦分岐経路を示した説明図である。
【００４０】
図６に示すように、現在地５０から目的地５１までの推薦経路５２上に、分岐点Ｐ１乃至Ｐ８が存在している。そのため、第１の経路計算手段１０ｂは、分岐点Ｐ１乃至Ｐ８から分岐する推薦経路５２以外の経路である経路５３乃至６０を、推薦分岐経路（図６中、破線で描く）として設定する。
【００４１】
次に、第１の経路計算手段１０ｂにより経路計算が終了すると、時間計測手段１０ｃが、第１の経路計算手段１０ｂによって経路計算を行われるのに要した時間である計算所要時間の計測を終了する（ステップＳ１０４）。
【００４２】
次に、ＣＰＵ１０の特徴点候補算出手段１０ｄは、時間計測手段１０ｃにより計測された計算所要時間が所定の時間以上であるか否かの判定を行う（ステップＳ１０５）。
【００４３】
ここで、所定の時間は経路計算装置１の提供者等により予め設定されており、経路計算装置１のハードウェアの能力に応じて設定されることが望ましい。例えば、比較的能力の低いハードウェア構成で経路計算装置１を実現している場合、所定時間を１０秒と設定し、経路計算に１０秒以上要した場合には、計算所要時間が所定の時間以上であると判定する。
【００４４】
そして、ＣＰＵ１０の特徴点候補算出手段１０ｄは、計算所要時間が所定の時間以上であると判定した場合、第１の経路計算手段１０ｂにより計算された推薦経路と推薦分岐経路の分岐点の情報を示す分岐点情報と、道路リンク数と、推薦経路上の分岐点における進行方向を示す進行方向情報とを特徴点候補情報として算出する（ステップＳ１０６）。
【００４５】
ここで、道路リンク数とは、推薦分岐経路上の分岐点と分岐点との間の経路の数を示す。例えば、図６に示すように、推薦分岐経路５５には分岐点Ｓ１及び分岐点Ｓ２が存在し、推薦経路と推薦分岐経路との分岐点Ｐ３から分岐点Ｓ１までの経路である経路５５−１、分岐点Ｓ１から分岐点Ｓ２までの経路である経路５５−２、分岐点Ｓ２から分岐点Ｓ３までの経路である経路５５−３の経路が存在するので、推薦分岐経路５５における道路リンク数は、“３”となる。
【００４６】
そして、特徴点候補算出手段１０ｄは、この特徴候補点毎の道路リンク数が多い順、即ち推薦分岐経路上の分岐点間の経路の数が多い順になるように特徴候補点情報を並び替える。
【００４７】
次に、ＣＰＵ１０の特徴点情報算出手段１０ｅは、計算所要時間の内、所定時間を越えた分をオーバー時間として算出し、第１の経路計算手段１０ｂによりオーバー時間内に計算された特徴点候補情報の数を特徴点情報数として決定する（ステップＳ１０７）。
【００４８】
例えば、下記の数式１によりオーバー時間内に経路計算された道路リンク数ａを算出する。
【００４９】
（数１）
a = ((L1 + L2) / T) × t
L1：推薦経路の道路リンク数
L2：全ての推薦分岐経路の道路リンク数
T ：計算所要時間(秒)
t ：オーバー時間(秒)
a ：オーバー時間内に経路計算された道路リンク数
そして、オーバー時間内に経路計算された道路リンク数ａから、特徴候補点情報が有する道路リンク数の高い順に、個々の特徴候補点情報が有する道路リンク数を減算し、ａがゼロ以下となった時の減算回数を特徴点情報数として決定する。
【００５０】
なお、ステップＳ１０５において、特徴点候補算出手段１０ｄが、計算所要時間が所定の時間未満であると判定した場合は、特徴点情報数を“０”に設定し、処理を終了する。
【００５１】
次に、特徴点情報算出手段１０ｅは、決定した特徴点情報数に相当する特徴点候補情報を特徴点情報として抽出し、入力情報受信手段１０ａに経路計算要求信号が供給されたときの現在地情報である出発地情報と目的地情報と探索条件情報と抽出した特徴点情報とを関連付けて特徴点履歴情報として特徴点記憶部１１に記憶させる（ステップＳ１０９）。
【００５２】
具体的には、特徴点情報算出手段１０ｅは、特徴点履歴情報を目的地履歴情報テーブルと目的地履歴詳細情報テーブルとに分けて、この２つのテーブルを“探索条件詳細番号”で関連付けて特徴点記憶部１１に記憶させる。
【００５３】
図２に示すように、カラム名“目的地名称”（符号２１）と、カラム名“目的地位置”（符号２２）と、外部キーとしてカラム名“探索条件詳細番号”（符号２３）とが関連付けて目的地履歴情報テーブルとして特徴点記憶部１１に記憶させる。ここで、カラム名“目的地名称”（符号２１）と、カラム名“目的地位置”（符号２２）とが目的地情報となる。
【００５４】
さらに、特徴点情報算出手段１０ｅは、図３に示すように、主キーとしてカラム名“探索条件詳細番号”（符号３１）と、カラム名“出発地情報”（符号３２）と、カラム名“探索条件情報”（符号３３）と、カラム名“特徴点情報の数”（符号３４）と、カラム名“特徴点情報”（符号４３）とが関連付けて履歴詳細情報テーブルとして特徴点記憶部１１に記憶させる。
【００５５】
図７は、特徴点情報算出手段１０ｅが抽出した特徴点情報が示す特徴点を説明した説明図である。
【００５６】
図７に示すように、推薦経路５２上の特徴候補点Ｐ１乃至Ｐ８のうち、特徴点情報数に相当する特徴点情報として特徴点Ｐ３，Ｐ４，Ｐ６が抽出されている。これにより、特徴候補点から道路リンク数の多い順、即ち経路計算に時間を要する順に特徴点として抽出されることになる。
【００５７】
また、ステップＳ１０１において、ＣＰＵ１０の経路計算判定手段１０ｇは、探索条件情報が示す探索条件が過去に設定された条件であると判定した場合、経路を計算させる経路計算指示信号を第２の経路計算手段１０ｆに送信する。そして、経路計算指示信号を受信した第２の経路計算手段１０ｆは、特徴点記憶部１１に記憶された特徴点履歴情報の特徴点情報の数を読み出し（ステップＳ１１０）、更に出発地情報と目的地情報と探索条件情報と特徴点情報を読み出す（ステップＳ１１１）。
【００５８】
次に、第２の経路計算手段１０ｆは読み出した特徴点履歴情報に基づいて特徴点情報が示す特徴点間の経路を計算する（ステップＳ１１２）。
【００５９】
図８は、第２の経路計算手段１０ｆによる経路計算の処理手順を示したフローチャートである。
【００６０】
第２の経路計算手段１０ｆは、出発地情報と目的地情報と探索条件情報が一致する特徴点情報が残っているか否かを判定し、出発地情報と目的地情報と探索条件情報が一致する特徴点情報がなくなるまで全ての特徴点間の経路について経路計算を行う（ステップＳ２００）。
【００６１】
具体的には、第２の経路計算手段１０ｆが、特徴点を始点と終点として設定し（ステップＳ２０１）、各特徴点間について経路計算を行う（ステップＳ２０２）。
【００６２】
図７に示した図では、第２の経路計算手段１０ｆは、まず始点として現在地５０を始点とし、特徴点Ｐ３を終点と設定して、現在地５０から特徴点Ｐ３までの経路を計算する。次に、始点として特徴点Ｐ３を設定し、特徴点Ｐ４を終点と設定して、特徴点Ｐ３から特徴点Ｐ４までの経路を計算する。このように、第２の経路計算手段１０ｆは、現在地５０から目的地５１までを特徴点間の経路として経路計算する。
【００６３】
そして、ステップＳ２００において、出発地情報と目的地情報と探索条件情報が一致する特徴点情報がなくなるまで全ての特徴点間の経路について経路計算が終了したと判定したときに、ステップＳ２０２において計算した特徴点間の経路をつなぎ合わせ、現在地５０から目的地５１までの経路として推薦経路を算出する（ステップＳ２０３）。
【００６４】
これにより、経路計算に時間を要する特徴点に接続された推薦分岐経路の経路計算を行う必要がないので、現在地から目的地までの経路計算を素早く行うことができる。また、現在地から目的地までの数ある分岐点のうち、特徴点となる分岐点の情報のみを特徴点記憶部１１に記憶するので、記憶容量を節約することができる。
【００６５】
以上により、第１の実施形態である経路計算装置１によれば、小さい記憶容量で高速に経路計算を行うことができる。
【００６６】
＜第２の実施形態＞
第２の実施形態である経路計算装置は、特徴点情報算出手段１０ｅが、特徴点候補算出手段１０ｄにより算出された特徴点候補情報の数が予め定めた閾値より大きい場合には、閾値を特徴点情報数として決定し、この決定した特徴点情報数に相当する特徴点候補情報を道路リンク数が多い順に特徴点情報として抽出する。
【００６７】
≪経路計算装置の作用≫
次に図９のフローチャートに従って、第２の実施形態である経路計算装置１０１における処理手順について説明する。
【００６８】
まず、経路計算装置１０１のＣＰＵ１０の入力情報受信手段１０ａは、ＧＰＳセンサ１３により生成された現在地を示す情報である現在地情報を受信し、さらに、入力部１２により生成された目的地を示す情報である目的地情報と探索条件を示す情報である探索条件情報と経路計算を要求する経路計算要求信号とを受信する。
【００６９】
そして、ＣＰＵ１０の経路計算判定手段１０ｇは、入力情報受信手段１０ａから経路計算要求信号、現在地情報、及び目的地情報が供給されると、目的地情報が示す目的地が新規に設定された地点であるか、又は過去に設定されたことのある地点かを判定する。具体的には、ＣＰＵ１０の経路計算判定手段１０ｇは、特徴点記憶部１１から目的地履歴情報を読み出し、入力情報受信手段１０ａから供給された目的地情報が、読み出した目的地履歴情報の目的地情報と一致するか否かを判定する（ステップＳ３００）。
【００７０】
さらに、ＣＰＵ１０の経路計算判定手段１０ｇは、目的地情報が示す目的地が新規に設定された地点であると判定した場合には、探索条件情報が示す探索条件が新規に設定された条件であるか、又は過去に設定されたことのある条件かを判定する。具体的には、ＣＰＵ１０の経路計算判定手段１０ｇは、特徴点記憶部１１から目的地履歴詳細情報を読み出し、入力情報受信手段１０ａに供給された探索条件情報が、読み出した目的地履歴詳細情報の探索条件情報と一致するか否かを判定する（ステップＳ３０１）。
【００７１】
そして、ＣＰＵ１０の経路計算判定手段１０ｇは、ステップＳ３００において目的地情報が示す目的地が新規に設定された地点であると判定し、又はステップＳ３０１において、探索条件情報が示す探索条件が新規に設定された条件であると判定した場合には、経路を計算させる経路計算指示信号を第１の経路計算手段１０ｂに送信する。
【００７２】
次に、経路計算指示信号を受信した第１の経路計算手段１０ｂは、入力情報受信手段１０ａに供給された現在地情報と目的地情報と探索条件情報とから現在地から目的地までの経路を計算する（ステップＳ３０２）。第１の経路計算手段１０ｂは、計算した経路のうち最も探索条件に適合する経路を推薦経路とし、この推薦経路上の分岐点から分岐する経路を推薦分岐経路とする。
【００７３】
次に、ＣＰＵ１０の特徴点候補算出手段１０ｄは、第１の経路計算手段１０ｂにより計算された推薦経路と推薦分岐経路との分岐点の情報を示す分岐点情報と、道路リンク数と、推薦経路上の分岐点における進行方向を示す進行方向情報とを特徴点候補情報として算出する（ステップＳ３０３）。
【００７４】
さらに、特徴点候補算出手段１０ｄは、この特徴候補点毎の道路リンク数が多い順、即ち推薦分岐経路上の分岐点と分岐点との間の経路数が多い順になるように特徴候補点情報を並び替える。
【００７５】
次に、特徴点情報算出手段１０ｅは、ＣＰＵ１０の特徴点候補算出手段１０ｄにより算出された特徴点候補情報の数が予め定めた閾値より大きいか否かを判定する（ステップＳ３０４）。
【００７６】
ここで、閾値は経路計算装置１０１の提供者等により予め設定されており、経路計算装置１０１のハードウェアの能力に応じて設定されることが望ましい。例えば、比較的能力の低いハードウェア構成で経路計算装置１０１を実現している場合、閾値を“１０”と設定する。
【００７７】
そして、特徴点候補算出手段１０ｄにより算出された特徴点候補情報の数が予め定めた閾値より大きいと判定した場合には、この閾値を特徴点情報数として決定し（ステップＳ３０５）、この決定した特徴点情報数に相当する特徴点候補情報を道路リンク数が大きい順に特徴点情報として抽出する。
【００７８】
なお、ステップＳ３０４において、特徴点候補算出手段１０ｄが、特徴点候補情報の数が予め定めた閾値以下であると判定した場合は、特徴点情報数を“０”に設定し、処理を終了する。
【００７９】
次に、特徴点情報算出手段１０ｅは、決定した特徴点情報数に相当する特徴点候補情報を特徴点情報として抽出し、入力情報受信手段１０ａに経路計算要求信号が供給されたときの現在地情報である出発地情報と目的地情報と探索条件情報と抽出した特徴点情報とを関連付けて特徴点履歴情報として特徴点記憶部１１に記憶させる（ステップＳ３０７）。
【００８０】
具体的には、特徴点情報算出手段１０ｅは、特徴点履歴情報を目的地履歴情報テーブルと目的地履歴詳細情報テーブルとに分けて、この２つのテーブルを“探索条件詳細番号”で関連付けて特徴点記憶部１１に記憶させる。
【００８１】
図２に示すように、カラム名“目的地名称”（符号２１）と、カラム名“目的地位置”（符号２２）と、外部キーとしてカラム名“探索条件詳細番号”（符号２３）とが関連付けて目的地履歴情報テーブルとして特徴点記憶部１１に記憶させる。ここで、カラム名“目的地名称”（符号２１）と、カラム名“目的地位置”（符号２２）とが目的地情報となる。
【００８２】
さらに、特徴点情報算出手段１０ｅは、図３に示すように、主キーとしてカラム名“探索条件詳細番号”（符号３１）と、カラム名“出発地情報”（符号３２）と、カラム名“探索条件情報”（符号３３）と、カラム名“特徴点情報の数”（符号３４）と、カラム名“特徴点情報”（符号４３）とが関連付けて履歴詳細情報テーブルとして特徴点記憶部１１に記憶させる。
【００８３】
また、ステップＳ３０１において、ＣＰＵ１０の経路計算判定手段１０ｇは、探索条件情報が示す探索条件が過去に設定された条件であると判定した場合、経路を計算させる経路計算指示信号を第２の経路計算手段１０ｆに送信する。そして、経路計算指示信号を受信した第２の経路計算手段１０ｆは、特徴点記憶部１１に記憶された特徴点履歴情報の特徴点情報数を読み出し（ステップＳ３０８）、更に出発地情報と目的地情報と探索条件情報と特徴点情報を読み出す（ステップＳ３０９）。
【００８４】
次に、第２の経路計算手段１０ｆは、読み出した出発地情報と目的地情報と探索条件情報と特徴点情報とに基づいて特徴点間の経路を計算する（ステップＳ３１０）。
【００８５】
なお、第２の経路計算手段１０ｆによる経路計算の詳細な処理手順については、図８に示した第１の実施形態である経路計算装置１における経路検索の処理フローと同様であるので、説明は省略する。
【００８６】
このように、第２の実施形態である経路計算装置１０１によれば、特徴点候補算出手段１０ｄにより算出された特徴点候補情報の数が予め定めた閾値より大きいか否かを判定することにより、特徴点情報数を算出するので、より簡易的に特徴点情報数を算出することができる。
【００８７】
これにより、現在地から目的地までの経路計算をより素早く行うことができる。また、現在地から目的地までの数ある分岐点のうち、特徴点となる分岐点の情報のみを特徴点記憶部１１に記憶するので、記憶容量を節約することができる。
【００８８】
以上により、第２の実施形態である経路計算装置１０１によれば、小さい記憶容量で高速に経路計算を行うことができる。
【図面の簡単な説明】
【００８９】
【図１】本発明を実施するための第１の実施形態である経路計算装置の構成を示したブロック図である。
【図２】特徴点記憶部が記憶している目的地履歴情報テーブルの一例を示した説明図である。
【図３】特徴点記憶部が記憶している目的地履歴詳細情報テーブルの一例を示した説明図である。
【図４】第１の実施形態である経路計算装置における処理手順を示したフローチャートである。
【図５】第１の経路計算手段により経路計算された推薦経路を示した説明図である。
【図６】第１の経路計算手段により経路計算された推薦経路、及び推薦分岐経路を示した説明図である。
【図７】特徴点情報算出手段が抽出した特徴点情報が示す特徴点を説明した説明図である。
【図８】第２の経路計算手段による経路検索の処理手順を示したフローチャートである。
【図９】第２の実施形態である経路計算装置における処理手順を示したフローチャートである。
【符号の説明】
【００９０】
１，１０１…経路計算装置
１０…ＣＰＵ
１０ａ…入力情報受信手段
１０ｂ…第１の経路計算手段
１０ｃ…時間計測手段
１０ｄ…特徴点候補算出手段
１０ｅ…特徴点情報算出手段
１０ｆ…第２の経路計算手段
１０ｇ…経路計算判定手段
１０ｈ…出力制御手段
１１…特徴点記憶部（特徴点記憶手段）
１２…入力部
１３…ＧＰＳセンサ
１４…音声出力部
１５…表示部
【図１】
2008241553.tif 000003
【図２】
2008241553.tif 000004
【図３】
2008241553.tif 000005
【図４】
2008241553.tif 000006
【図５】
2008241553.tif 000007
【図６】
2008241553.tif 000008
【図７】
2008241553.tif 000009
【図８】
2008241553.tif 000010
【図９】
2008241553.tif 000011