JP4975075B2 - ナビゲーション装置および経路演算方法 - Google Patents

Description

本発明は、ナビゲーション装置および経路演算方法に関する。

車載用ナビゲーション装置において、車両のエネルギー残量を考慮して経路の変更及び表示を行う技術が知られている。車両のエネルギー残量とは、例えば内燃機関を利用する自動車であればガソリンなどの燃料の残量を、電気自動車であれば蓄電池の残容量を、水素自動車であれば水素燃料自体の残量もしくは水素に変換するための液体の残量を指す。また、「エネルギー残量を考慮する」とは、走行中にエネルギー不足になることのないよう、エネルギーの補給地における補給を考慮するということである。例えば特許文献１の経路探索装置は、出発地から最初の充電ステーションまでの距離が航続距離以下で、且つ最初の充電ステーションから目的地までの各充電ステーション区間の距離が満充電の航続距離以下の経路を探索する。

特開平１０−１７０２９３号公報

特許文献１の経路探索装置は、エネルギー補給地を含む経路の組み合わせを全て選択し、その中から目的地へ到達可能な経路を探索する。従って、探索すべき経路の組み合わせが膨大となり、莫大な計算量が必要となってしまうという問題があった。

請求項１に係る発明は、現在地を検出する現在地検出手段と、自車両の駆動エネルギーの残量を検出するエネルギー残量検出手段と、自車両への駆動エネルギーの補給地の位置情報を含む地図情報が記憶された記憶手段と、地図情報に基づいて、地図情報に含まれる任意のリンクを走行する際の駆動エネルギーの消費量を算出するエネルギー消費量算出手段と、現在地から目的地に至る経路を演算する経路演算手段と、経路演算手段による演算の結果に基づいて、自車両の経路誘導を行う経路誘導手段とを備え、経路演算手段は、確定済み経路の終端ノードに隣接するノードを辿って経路を探索する際、終端ノードに隣接するそれぞれのノードについて、補給地の位置情報と、エネルギー消費量算出手段により算出された終端ノードから当該ノードまで走行する際の消費量とから、残量が所定のしきい値を下回ることなく確定済み経路を辿って当該ノードまで走行可能な他の経路を演算し、当該ノードに最小コストで到達する経路を走行後の残量がしきい値を下回る場合には、他の経路のうち残量が最大となるものを、確定済み経路を辿り当該ノードに到達する経路として確定させることにより、残量が所定のしきい値を下回らない経路のうち最小のコストを有する推奨経路を演算することを特徴とするナビゲーション装置である。
請求項７に係る発明は、出発時における自車両の駆動エネルギーの残量を設定するエネルギー残量設定工程と、自車両への駆動エネルギーの補給地の位置情報を含む地図情報に基づいて、地図情報に含まれる任意のリンクを走行する際の駆動エネルギーの消費量を算出するエネルギー消費量算出工程と、現在地から目的地に至る経路を演算する経路演算工程とを備え、経路演算工程では、確定済み経路の終端ノードに隣接するノードを辿って経路を探索する際、終端ノードに隣接するそれぞれのノードについて、補給地の位置情報と、エネルギー消費量算出行程により算出された終端ノードから当該ノードまで走行する際の消費量とから、残量が所定のしきい値を下回ることなく確定済み経路を辿って当該ノードまで走行可能な他の経路を演算し、当該ノードに最小コストで到達する経路を走行後の残量がしきい値を下回る場合には、他の経路のうち残量が最大となるものを、確定済み経路を辿り当該ノードに到達する経路として確定させることにより、残量が所定のしきい値を下回らない経路のうち最小のコストを有する推奨経路を演算することを特徴とする経路演算方法である。

本発明によれば、エネルギー残量を考慮した経路探索を計算量を抑えつつ行うことができる。

本発明の第１の実施の形態であるナビゲーション装置の構成を示すブロック図である。 制御回路１０１およびＤＶＤ−ＲＯＭ１０６の詳細を表すブロック図である。 上下限残量設定部１３２への入力画面を示す図である。 経路表示部１３６による経路表示画面の例を示す図である。 経路誘導画面の例を示す図である。 ネットワーク地図ＤＢ１２２のデータ構造を示す図である。 補給地ＤＢ１２３のデータ構造を示す図である。 候補ノードヒープのデータ構造を示す図である。 確定ノードリストのデータ構造を示す図である。 経路探索処理のフローチャートである。 ノードエネルギー残量算出処理のフローチャートである。 ノード到達可否判定処理のフローチャートである。 到達候補ノード登録判定処理のフローチャートである。 推奨経路のデータ構造を示す図である。

（第１の実施の形態）
図１は、本発明の第１の実施の形態であるナビゲーション装置の構成を示すブロック図である。ナビゲーション装置１００は自車両２００に搭載され、自車両２００のエネルギー残量を考慮した経路探索および経路誘導を行う。ここで自車両２００は、蓄電池に充電された電気エネルギーにより駆動される、いわゆる電気自動車である。従って、第１の実施の形態において、自車両２００のエネルギー残量とはすなわち自車両２００の蓄電池の残量のことである。

（ナビゲーション装置の説明）
ナビゲーション装置１００は、制御回路１０１、ＤＲＡＭ１０３、不揮発性メモリ１０４、ディスクドライブ１０５、電池残量センサ１０７、交通情報受信機１０８、液晶モニタ１０９、タッチパネル１１０、および現在地検出装置１１１を有する。ディスクドライブ１０５には、ＤＶＤ−ＲＯＭ１０６が装填されている。

制御回路１０１は、マイクロプロセッサ及びその周辺回路から構成される。ＤＲＡＭ１０３は揮発性の記憶装置である。不揮発性メモリ１０４は、例えばフラッシュメモリ等の不揮発性の記憶媒体であり、所定の制御プログラムが格納されている。制御回路１０１は、ＤＲＡＭ１０３を作業領域として不揮発性メモリ１０４に格納された制御プログラムを実行し、各種の制御を行う。ディスクドライブ１０５は、ＤＶＤ−ＲＯＭ１０６からデータの読み取りを行う装置である。

電池残量センサ１０７は自車両２００に接続されたセンサである。電池残量センサ１０７は、自車両が有する蓄電池の残量を検知し、制御回路１０１へ通知する。交通情報受信機１０８は、例えばＶＩＣＳ（Ｖｅｈｉｃｌｅ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）（登録商標）などにより提供される交通情報を受信し、制御回路１０１へ出力する。ここで交通情報とは、道路の渋滞情報や事故情報などである。

液晶モニタ１０９は、制御回路１０１が出力する画像データに基づき、各種情報を画面表示として自車両２００の搭乗者へ提示する。タッチパネル１１０は、液晶モニタ１０９の表面に積層される透明のタッチスイッチである。液晶モニタ１０９に表示される画像はタッチパネル１１０を介して表示される。搭乗者が液晶モニタ１０９の表示画面を押圧すると、タッチパネル１１０が押圧される。このとき、タッチパネル１１０から制御回路１０１へ押圧した位置の情報を含む操作信号が出力される。そして、制御回路１０１が液晶モニタ１０９へ表示されている地図上の押圧した位置へ目的地を設定したり、押圧した位置に表示されている各種ボタンや表示メニューに定義された処理を実行したりする。

現在地検出装置１１１は自車両２００の現在地を検出する装置である。現在地検出装置１１１はＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）受信機１１１ａ、ジャイロスコープ１１１ｂ、車速センサ１１１ｃ等の各種センサを有する。ＧＰＳ受信機１１１ａはＧＰＳ衛星から送出される信号を受信し、自車両２００の絶対位置を検出する。ジャイロスコープ１１１ｂは車両の進行方向を検出する。車速センサ１１１ｃは自車両２００が出力する車速パルス信号を受信し、自車両２００の車速を検出する。現在地検出装置１１１はこれらのセンサが検出した各種の情報を演算し、自車両２００の現在地を検出する。

ナビゲーション装置１００は、ユーザから経路誘導の目的地を受け付けると、現在地検出装置１１１により検出された現在地を出発地として、目的地までの経路演算を後に詳述するアルゴリズムに基づいて行う。ナビゲーション装置１００は、液晶モニタ１０９の表示画面へ地図を表示すると共に、この経路演算により求められた経路（以下、推奨経路という）を地図上へ表示する。ナビゲーション装置１００は、ユーザに対して画面や音声などによる進行方向指示を行い、推奨経路に従って自車両２００が走行できるように、自車両２００を経路誘導する。

図２は、制御回路１０１およびＤＶＤ−ＲＯＭ１０６の詳細を表すブロック図である。ＤＶＤ−ＲＯＭ１０６には、ＰＯＩＤＢ（Ｐｏｉｎｔ Ｏｆ Ｉｎｔｅｒｅｓｔデータベース）１２１と、ネットワーク地図ＤＢ１２２と、補給地ＤＢ１２３と、表示用地図ＤＢ１２４と、が格納されている。ＰＯＩＤＢ１２１は、ランドマークや観光スポットなど経路探索の目的地を設定するためのデータを、ジャンル検索や名称検索など様々な検索が可能な形式で整理したデータベースである。ネットワーク地図ＤＢ１２２は、経路探索を行う際に用いられるネットワーク地図が格納されたデータベースである。ネットワーク地図ＤＢ１２２に格納されたネットワーク地図は、公知のネットワーク地図と同様に、道路網を交差点などのノードとノード間のリンクとの組み合わせにより表現している。

補給値ＤＢ１２３は、車両へエネルギーの補給を行う施設の情報を含むデータベースである。以下の説明では、このような施設のことを補給地と呼ぶ。本実施形態では、電気自動車である自車両２００へ充電を行う充電ステーションが補給地である。表示用地図ＤＢ１２４は、例えば道路、鉄道、地形、施設形状、地名等、液晶モニタ１０９の表示画面へ地図を表示するためのデータが格納されたデータベースである。表示用地図ＤＢ１２４に格納されたデータのうち道路データは、リンクやノードに対して、ネットワーク地図ＤＢ１２２の道路データと共通のＩＤが利用されている。これにより、ネットワーク地図ＤＢ１２２と表示用地図ＤＢ１２４とは、道路データの相互参照が可能である。制御回路１０１は、例えば経路探索の結果を画面に表示する場合などに、道路データの相互参照を行う。

制御回路１０１は、探索条件設定部１３１、上下限残量設定部１３２、目的地設定部１３３、経由地自動追加部１３４、目的地到達可否判定部１３５、経路表示部１３６、および経路探索部１３７を備える。経路探索部１３７は更に、ノード残量算出部１３８、ノード到達可否判定部１３９、および候補ノード登録判定部１４０を備える。これらの各機能部は、制御回路１０１が不揮発性メモリ１０４に格納された制御プログラムを実行することにより、ソフトウェア的に実現される。

探索条件設定部１３１は、ユーザからのタッチパネル１１０による入力に基づき、経路探索の条件を設定する。経路探索の条件には、例えば距離優先、時間優先、金銭コスト優先、エネルギー消費量優先などの条件を設定することが可能である。経路探索部１３７は、探索条件設定部１３１により設定された経路探索の条件に基づいて経路探索を行う。

上下限残量設定部１３２は、ユーザからのタッチパネル１１０による入力に基づき、経路探索におけるエネルギー残量の上限および下限を設定する。上下限残量設定部１３２は更に、目的地へ到着した時点におけるエネルギー残量の下限を設定する。経路探索部１３７は、上下限残量設定部１３２により設定されたエネルギー残量の範囲内で経路探索を行う。例えば、上下限残量設定部１３２がエネルギー残量の下限を２０％に設定した場合、経路探索部１３７は走行中のエネルギー残量が常に２０％を上回る推奨経路を探索する。

目的地設定部１３３は、ユーザからのタッチパネル１１０による入力に基づき、経路探索の目的地を設定する。目的地設定部１３３は、ＰＯＩＤＢ１２１を利用して、ジャンル検索、名称検索、地図表示からの選択など、ナビゲーション装置において広く用いられている目的地の入力方法をユーザへ提供する。

経由地自動追加部１３４は、推奨経路に含まれる補給地ノード群に基づいて、推奨経路へ経由地を追加する。目的地到達可否判定部１３５は、経路探索部１３７の出力に基づいて、目的地への到達可否を判定する。

経路表示部１３６は、液晶モニタ１０９の表示画面へ地図を表示すると共に、経路探索部１３７が出力した経路を地図上へ表示する。経路表示部１３６は推奨経路を他の道路などとは異なる表示形態（例えば表示色など）で表示する。これにより、ユーザは地図上の推奨経路を他の道路などと画面上で区別することができる。また経路表示部１３６は、推奨経路に経由地が含まれる場合、他のノードとは異なる表示形態で経由地を表示する。

経路探索部１３７は、現在地検出装置１１１が検出した現在地を出発地として、目的地設定部１３３が設定した目的地までの経路探索を行う。経路探索部１３７はこの経路探索を、電池残量センサ１０７が検知した蓄電池の残量と、交通情報受信機１０８が出力した交通情報と、ＤＶＤ−ＲＯＭ１０６に格納されているネットワーク地図ＤＢ１２２と、探索条件設定部１３１が設定した経路探索の条件と、に基づいて行う。経路探索部１３７は経路探索に成功した場合、推奨経路を出力する。他方、経路探索に失敗した場合、経路探索部１３７は目的地に向かう途中までの経路を出力する。

ノード残量算出部１３８は、経路探索処理の際、補給地の通過有無を考慮して各ノードにおける自車両２００のエネルギー残量を算出する。ノード到達可否判定部１３９は、各ノードについて、上下限残量設定部１３２により設定されたエネルギー残量の下限を上回るエネルギー残量で到達可能か否かを判定する。候補ノード登録判定部１４０は、各ノードについて経路探索処理を継続する必要があるか否かを判定する。

（上下限残量設定の説明）
図３は、上下限残量設定部１３２への入力画面を示す図である。ユーザは経路探索に先立って、タッチパネル１１０によりエネルギー上下限残量設定画面１４１を呼び出すことが可能である。ユーザはタッチパネル１１０によりエネルギー残量の下限１４２、上限１４３、および目的地でのエネルギー残量の下限１４４を入力できる。上下限残量設定部１３２はこれらの入力に基づいて、経路探索におけるエネルギー残量の上限および下限を設定する。

（経路表示の説明）
図４は、経路表示部１３６による経路表示画面の例を示す図である。図４（ａ）には、経路表示部１３６が表示する地図上での経路表示画面１５１を示す。画面１５１には、現在地１５２、目的地１５３、ボタン１５４、経路探索部１３７が出力した推奨経路１５５、経路探索部１３７が公知の経路探索手法により補給地を考慮せずに出力した経路１５６、推奨経路１５５上の補給地１５７、１５８、および経路１５６上の補給地１５９が表示されている。経路表示部１３６は画面１５１を表示用地図ＤＢ１２４に基づいて描画する。画面１５１において、補給地１５７、１５８、１５９は１〜３の数字により表現されているが、この数字の代わりに補給地の名称を用いてもよい。ユーザがタッチパネル１１０によりボタン１５４を押下すると、経路表示部１３６が液晶モニタ１０９の表示画面を画面１５１から図４（ｂ）に示す詳細表示画面１６１に切り替える。

図４（ｂ）に示す詳細表示画面１６１は、上述した２つの経路１５５、１５６を共通の時間軸を基準として、経由地も含め比較表示した画面である。画面１６１上の領域１６２には、各々の経路を走行した場合のエネルギー残量の変化が矢印および数値で表示されている。矢印１６３、１６４は経路を表す矢印であり、特に破線で描画された矢印１６４は、走行中にエネルギーが不足する経路を示している。矢印の下側には、各々の時刻におけるエネルギー残量の変化が数値で表示されている。ユーザがタッチパネル１１０によりボタン１６５を押下すると、経路表示部１３６が液晶モニタ１０９の表示画面を画面１６１から図４（ａ）に示す経路表示画面１５１に切り替える。なお、図４（ｂ）において、領域１６２の横方向は経過時間を表しているが、走行距離を表すようにしてもよい。

なお、経路探索の後、目的地到達可否判定部１３５が目的地に到達できる経路を探索できなかったと判定した場合には、経路表示部１３６が液晶モニタ１０９へ、探索可能経路が発見できない旨の表示を行ってもよい。またこの場合、経路表示部１３６は経路探索部１３７が出力した途中までの経路を表示する。

（経路誘導画面の説明）
図５は、経路誘導画面の例を示す図である。経路表示部１３６は、ナビゲーション装置１００による経路誘導が行われているとき、経路誘導画面１７１を液晶モニタ１０９へ表示する。この経路誘導画面１７１では、経由地自動追加部１３４により推奨経路へ追加された経由地のユーザへの報知が行われる。具体的には、経路表示部１３６は、画面１７１上に表示される、自車両１７２の進行方向を表す矢印１７３に、経由地を表すマーク１７４を重ねて表示する。また経路表示部１３６は、経由地においてエネルギーの補給が必要であることを、吹き出し１７５によりユーザへ報知すると共に、エネルギー残量の変化量を表す数値を吹き出し１７５の下部に表示する。

（データベースの説明）
図６は、ネットワーク地図ＤＢ１２２のデータ構造を示す図である。ネットワーク地図ＤＢ１２２には、ノード情報Ｎが複数格納されている。個々のノード情報Ｎは、公知のネットワーク地図と同様に、始点ノードＩＤＮ１と、接続ノード数Ｎ２と、１つ以上の接続ノード情報Ｌと、から構成される。また個々の接続ノード情報Ｌは、公知のネットワーク地図と同様に、接続ノードＩＤＬ１と、リンク長Ｌ２と、所要時間Ｌ３と、を含む。

本実施形態では、接続ノード情報Ｌがこれらのデータに加えて、補給地フラグＬ４と、補給地ＩＤＬ５と、を含む。補給地フラグＬ４は、当該ノードが補給地か否かを表すフラグである。すなわち、補給地フラグＬ４が１であれば、当該ノードの位置に充電ステーションが存在する。補給地ＩＤＬ５は、補給地を特定する為のＩＤである。制御回路１０１は、補給地ＩＤＬ５を用いることにより、補給地ＤＢ１２３の参照を高速に行うことができる。接続ノード情報Ｌの補給地フラグＬ４が０である場合、この接続ノード情報Ｌは補給地ＩＤＬ５を含まない。

図７は、補給地ＤＢ１２３のデータ構造を示す図である。補給地ＤＢ１２３には、補給地情報Ｓが複数格納されている。個々の補給地情報Ｓは、補給地ＩＤＳ１と、補給地名称Ｓ２と、補給地のジャンルＳ３と、補給燃料の種類Ｓ４と、対応ノードＩＤＳ５と、正規化座標Ｓ６と、から構成される。補給地ＩＤＳ１は、個々の補給地に一意に割り当てられたＩＤである。前述したネットワーク地図ＤＢ１２２に含まれる補給地ＩＤＬ５には、この補給地ＩＤＳ１が格納されている。

補給地名称Ｓ２は補給地の名称を表す。補給地のジャンルＳ３は、各々の補給地を分類するためのジャンル名である。補給燃料の種類Ｓ４は、この補給地で補給可能なエネルギーの種類である。本実施形態では、補給燃料の種類Ｓ４は「充電」である。対応ノードＩＤＳ５は、ネットワーク地図ＤＢ１２２に格納されているノード情報Ｎを参照するための始点ノードＩＤである。制御回路１０１は、この対応ノードＩＤＳ５を用いることにより、ネットワーク地図ＤＢ１２２の参照を高速に行うことができる。正規化座標Ｓ６は、補給地の位置を表す座標である。

（経路探索処理で扱うデータ構造の説明）
経路探索部１３７は、経路探索処理において、「候補ノードヒープ」と「確定ノードリスト」という２つのデータ集合を扱う。これらのデータ集合はいずれも、公知のダイクストラ法において用いられるデータ構造にいくつかのデータ項目を追加したものとなっている。

図８は、候補ノードヒープのデータ構造を示す図である。図８（ａ）に示すように、候補ノードヒープ１８１は、１つ乃至複数の到着ノードデータＣにより公知のヒープ構造を成す。ヒープ構造とは木構造の一種であり、親要素がどの子要素よりも小さな評価値を有するように構成される。木に対して要素の追加や削除などの操作を行った場合でも、上記の条件は常に満たされる。図８（ａ）では、個々のノードの評価値を、ノードを表す円の中に描画している。

図８（ｂ）は、候補ノードヒープ１８１を構成する個々の到着ノードデータＣのデータ構造を示図である。１つの到着ノードデータＣは１つのノードに対応しており、経路探索処理中にあるノードへ特定の経路で到達した場合の、そのノードにおける各種情報を表している。到着ノードデータＣは、到着ノードＩＤＣ１と、前回ノードＩＤＣ２と、ヒープの評価値として扱われる到達コストＣ３と、最小残量Ｃ４と、最大残量Ｃ５と、確定補給地ノードＩＤＣ６と、直前補給地ノードＩＤＣ７と、到達可否フラグＣ８と、から構成される。到着ノードＩＤＣ１、前回ノードＩＤＣ２、確定補給地ノードＩＤＣ６、および直前補給地ノードＩＤＣ７は、ノードＩＤに付随する通番を備えている。

到着ノードＩＤＣ１は、到達したノードのノードＩＤである。前回ノードＩＤＣ２は、このノードへ到達した経路において、直前に通過したノードのノードＩＤである。到達コストＣ３は、このノードへ到達するために要したコストの総計である。最小残量Ｃ４は、可能な限り補給を行わずにこのノードへ到達した場合のエネルギー残量を、確定補給地ノードＩＤＣ６は同様の場合において直前に補給を行った補給地のノードＩＤを表す。最大残量Ｃ５は、可能な限り頻繁に補給を行いつつこのノードへ到達した場合のエネルギー残量を、直前補給地ノードＩＤＣ７は同様の場合において直前に補給を行った補給地のノードＩＤを表す。到達可否フラグＣ８は、到達したノードに対し、エネルギー残量が上下限残量設定部１３２により設定された下限を下回らずに到達可能か否かを表すフラグである。

以上のように、到着ノードデータＣには、通常のダイクストラ法では用いられない最小残量Ｃ４、最大残量Ｃ５、確定補給地ノードＩＤＣ６、直前補給地ノードＩＤＣ７、および到達可否フラグＣ８というデータが存在する。

図９は、確定ノードリストのデータ構造を示す図である。確定ノードリストＤＬを構成する１つのレコードは１つのノードに関する情報を表し、通番Ｄ１、ノードＩＤＤ２、確定情報Ｄ３、および未確定情報Ｄ４から成る。確定情報Ｄ３は、到達コストＤ３１、前回ＩＤＤ３２、最小残量Ｄ３３、および最大残量Ｄ３４から構成される。未確定情報Ｄ４は、最小コストＤ４１および最大残量Ｄ４２から構成される。

通番Ｄ１は、各ノードに対して１から順に割り当てられた通し番号である。この通番は、１回の経路探索処理を通して、ノードＩＤと１対１に対応する。経路探索部１３７を含む各部は、ノードＩＤの代わりにこの通番を用いることにより、各レコードへ高速にアクセスすることができる。ノードＩＤＤ２は、このレコードが表すノードに割り当てられた一意な識別子であり、ノード情報Ｎ（図６）における始点ノードＩＤＮ１に対応する。確定情報Ｄ３は、このレコードが表すノードへのコストが最小となる経路が確定したときの、到着ノードデータＣ（図８）における到達コストＣ３、前回ノードＩＤＣ２、最小残量Ｃ４、および最大残量Ｃ５である。未確定情報Ｄ４は、このレコードが表すノードへのコストが最小となる経路が確定していないときに用いる暫定的なデータである。未確定情報Ｄ４の最小コストＤ４１は到着ノードデータＣ（図８）における到達コストＣ３に対応し、同様に最大残量Ｄ４２は到着ノードデータＣ（図８）における最大残量Ｃ５に対応する。

（経路探索処理の説明）
図１０は、経路探索処理のフローチャートである。本実施形態における経路探索処理は、公知の経路探索処理において利用されるダイクストラ法のアルゴリズムをベースに、エネルギー残量を考慮した各種の処理を追加したものである。

ステップＳ１００では、経路探索部１３７が初期化処理を行う。具体的には、経路探索部１３７は候補ノードヒープ１８１を空の状態にすると共に、ネットワーク地図ＤＢ１２２から経路探索処理の対象とする領域内の全ノード情報を読み出す。この領域は、例えば出発地および目的地とその周辺とを含む矩形領域とし、矩形の一辺は、例えば出発地と目的地との間の距離のおよそ１．５倍〜２倍と設定し、経路探索に不要と思われる領域を排除する。経路探索部１３７は、このようにして読み出した複数のノード情報に基づいて、ＤＲＡＭ１０３へ図９に示した確定ノードリストＤＬを作成する。経路探索部１３７は確定ノードリストＤＬの各々のレコードのノードＩＤＤ２へ、読み出したノード情報に含まれるノードＩＤを格納し、通番Ｄ１へ１から始まる通し番号を割り当てる。経路探索部１３７は、確定ノードリストＤＬの通番Ｄ１とノードＩＤＤ２以外のフィールドには、データが存在しないことを表す「Ｎ／Ａ」を書き込む。

ステップＳ１０２１では、経路探索部１３７が、候補ノードヒープ１８１の構成ノードが空であるか否かを判定する。ステップＳ１０２１において、経路探索部１３７により空であることが肯定された場合にはステップＳ１０２２へ進み、「目的地到達経路なし」との結果を返す処理を行い経路探索処理を終了する。こうして経路探索部１３７によって、目的地到達可否が判定される。候補ノードヒープ１８１が空であることが「目的地到達経路なし」となる理由については、ステップＳ１０８の処理後の候補ノードヒープ１８１の状態によるため、図１３の説明によって後述する。

ステップＳ１０１では、経路探索部１３７が出発地ノードの到着ノードデータＣを作成し、候補ノードヒープ１８１へ登録する。これにより、候補ノードヒープ１８１は、出発地ノードのみを含む状態になる。出発地ノードの到着ノードデータＣは、到着ノードＩＤＣ１には出発地ノードのノードＩＤ、到達コストＣ３には０、最小残量Ｃ４および最大残量Ｃ５には電池残量センサ１０７により検知された出発時のエネルギー残量、到達か非フラグＣ８には「可」、がそれぞれ設定され、それ以外の項目にはデータが存在しないことを表す「Ｎ／Ａ」が設定される。

ステップＳ１０２では、経路探索部１３７が候補ノードヒープ１８１から最小の到達コストＣ３を有する到着ノードデータＣを取り出し、この到着ノードデータＣの情報を確定ノードリストＤＬの確定情報Ｄ３へ格納する。具体的には、経路探索部１３７は到達コストＤ３１へ到達コストＣ３を、前回ＩＤＤ３２へ前回ノードＩＤＣ２を、最小残量Ｄ３３へ最小残量Ｃ４を、最大残量Ｄ３４へ最大残量Ｃ５をそれぞれ格納する。候補ノードヒープ１８１は、根ノードが最小の到達コストＣ３を有するよう構成されるので、経路探索部１３７は候補ノードヒープ１８１から根ノードを取り出せばよい。

ステップＳ１０３では、経路探索部１３７はステップＳ１０２において取り出された到着ノードデータＣが目的地ノードに対応するか否かを判定する。取り出された到着ノードデータＣが目的地ノードに対応する到着ノードデータＣではなかった場合、経路探索部１３７により否定判定がなされ、ステップＳ１０４へ進む。

ステップＳ１０４では、経路探索部１３７が、ステップＳ１０２において取り出された到着ノードデータＣのノードに接続する全てのノードを、ステップＳ１００において読み出されたノード情報に基づいて取り出す。経路探索部１３７は、このようにして取り出された各々のノードについて、対応する到着ノードデータＣを作成してＤＲＡＭ１０３へ格納する。このとき、到着ノードＩＤＣ１には取り出されたノードのノードＩＤが、前回ノードＩＤＣ２にはステップＳ１０２において取り出された到着ノードデータＣの到着ノードＩＤＣ１が、確定補給地ノードＩＤＣ６および直前補給地ノードＩＤＣ７にはステップＳ１０２において取り出された到着ノードデータＣと同一の内容が、到達可否フラグＣ８には「可」がそれぞれ設定され、それ以外の項目にはデータが存在しないことを表す「Ｎ／Ａ」が設定される。

ステップＳ１０５では、経路探索部１３７が、ステップＳ１０４において作成された各々の到着ノードデータＣに対して、ステップＳ１０６〜ステップＳ１０８の処理を実行する。ステップＳ１０６では、ノード残量算出部１３８が、各々の到着ノードデータＣに対してノードエネルギー残量算出処理を実行する。ステップＳ１０７では、ノード到達可否判定部１３９が、各々の到着ノードデータＣに対してノード到達可否判定処理を実行する。ステップＳ１０８では、候補ノード登録判定部１４０が、各々の到着ノードデータＣに対して到達候補ノード登録判定処理を実行する。ノードエネルギー残量算出処理、ノード到達可否判定処理、および到達候補ノード登録判定処理については後に詳述する。ステップＳ１０６〜ステップＳ１０８の処理の実行が完了したら、経路探索処理はステップＳ１０２へ戻る。

他方、ステップＳ１０３において経路探索部１３７により肯定判定がなされた場合には、経路探索処理はステップＳ１０９へ進む。ステップＳ１０９では、経路探索部１３７が確定ノードリストＤＬを用いて出発地ノードから目的地ノードへと至る到着ノードデータＣのデータ列、すなわち推奨経路を出力する。具体的には、経路探索部１３７はまず目的地ノードのノードＩＤＤ２を取り出した後、目的地ノードの前回ＩＤＤ３２を取り出す。経路探索部１３７はその後、この前回ＩＤＤ３２に対応するノードＩＤＤ２を確定ノードリストＤＬから探索し、同様に前回ＩＤＤ３２を取り出す。経路探索部１３７は目的地ノードに到達するまでこの処理を繰り返し、取り出されたノードＩＤ列を逆順にする。最終的に経路探索部１３７は、この取り出されたノードＩＤ列に基づいて、到着ノードデータＣの列を作成して出力する。以上の処理により、経路探索部１３７は推奨経路を出力する。

なお、以上で説明した経路探索処理では、上下限残量設定部１３２により設定される、目的地に到着した時点におけるエネルギー残量の下限に関する処理を省略している。この下限を考慮する場合は、ノード到達可否判定処理（ステップＳ１０７）内において、目的地ノードに対し、上下限残量設定部１３２により設定された下限値を用いた判定を行う。詳細は、図１２の説明において後述する。

（ノードエネルギー残量算出処理の説明）
図１１は、ノードエネルギー残量算出処理のフローチャートである。この処理はノード残量算出部１３８が、特定の到着ノードデータＣに対して実行する。この処理の対象となる到着ノードデータＣは、到着ノードＩＤＣ１、前回ノードＩＤＣ２、確定補給地ノードＩＤＣ６、直前補給地ノードＩＤＣ７、および到達可否フラグＣ８を除く全ての項目に「Ｎ／Ａ」が設定されている。

ステップＳ２０１では、ノード残量算出部１３８が、処理対象のノードのノード情報Ｎに基づいて、エネルギー消費量およびリンクコストを計算する。エネルギー消費量は、予め与えられた単位距離当たりのエネルギー消費量やリンク長Ｌ１（図６）などを用いて、公知の手法により計算することが可能である。リンクコストは探索条件設定部１３１により設定された探索条件に基づくコストであり、例えば距離優先であればリンク長Ｌ１（図６）を、時間優先であれば時間Ｌ３（図６）および交通情報受信機１０８により出力された交通情報を用いて、公知の手法によりそれぞれ計算される。また、探索条件がエネルギー消費量優先であれば上記のエネルギー消費量、金銭コスト優先であれば有料道路料金やエネルギー費用などにより、同様にノード残量算出部１３８がリンクコストを計算する。

ステップＳ２０２では、ノード残量算出部１３８が、処理対象の到着ノードデータＣの到達コストＣ３、最小残量Ｃ４、および最大残量Ｃ５を設定する。ノード残量算出部１３８は、ステップＳ１０２で取り出されたノードの到達コストＣ３とステップＳ２０１で計算されたリンクコストとを加算することにより、処理対象の到着ノードデータＣの到達コストＣ３を算出する。ノード残量算出部１３８は、同様にステップＳ１０２で取り出されたノードの最小残量Ｃ４および最大残量Ｃ５から、ステップＳ２０１で計算されたエネルギー消費量を減ずることにより、処理対象の到着ノードデータＣの最小残量Ｃ４および最大残量Ｃ５を算出する。なお、自車両２００が例えば回生ブレーキを備える場合など、ステップＳ２０１で算出されたエネルギー消費量が負の値となる場合があり得るが、この場合は処理の都合上エネルギー消費量を０％として扱う。

ステップＳ２０３では、ノード残量算出部１３８が、処理対象のノードが補給地ノードであるか否かを判定する。すなわち、処理対象のノードのノード情報Ｎにおいて、補給地フラグＬ４（図６）が１であるか否かを判定する。処理対象のノードが補給地ノードである場合、ノード残量算出部１３８により肯定判定がなされ、ノードエネルギー残量算出処理はステップＳ２０４へ進む。ステップＳ２０４では、ノード残量算出部１３８が、処理対象の到着ノードデータＣの最大残量Ｃ５および直前補給地ノードＩＤＣ７を更新し、ノードエネルギー残量算出処理を終了する。具体的には、最大残量Ｃ５が上下限残量設定部１３２により設定されたエネルギー残量の下限となり、直前補給地ノードＩＤＣ７が処理対象の到着ノードデータＣの到着ノードＩＤＣ１となる。他方、ステップＳ２０３において否定判定がなされた場合には、ノードエネルギー残量算出処理を終了する。

（ノード到達可否判定処理の説明）
図１２は、ノード到達可否判定処理のフローチャートである。この処理はノード到達可否判定部１３９が、特定の到着ノードデータＣに対して実行する。なお、以下の説明において、上下限残量設定部１３２により設定されたエネルギー残量の下限を「下限値」という。

ステップＳ３０１では、ノード到達可否判定部１３９が、処理対象の到着ノードデータＣの最大残量Ｃ５が下限値未満であるか否かを判定する。到着ノードが目的地ノードである場合には、上下限残量設定部１３２により別途設定された目的地の下限値を用いてエネルギー残量の判定を行う。目的地の下限値の設定と本判定処理によって、目的地到達時点でのエネルギー残量が下限値以上であることが保証される。これにより、目的地においてエネルギーの補給を行えない場合であっても、次回出発時（このとき目的地が新たな出発地となる）には少なくとも該下限値で到達可能な補給地まで走行することが可能となる。ステップＳ３０１においてノード到達可否判定部１３９により肯定判定がなされた場合には、ノード到達可否判定処理はステップＳ３０２へ進む。ステップＳ３０２では、ノード到達可否判定部１３９が処理対象の到着ノードデータＣの到達可否フラグＣ８を「否」に設定し、ノード到達可否判定処理を終了する。他方、ステップＳ３０１において否定判定がなされた場合には、ノード到達可否判定処理はステップＳ３０３へ進む。

ステップＳ３０３では、ノード到達可否判定部１３９が、処理対象の到着ノードデータＣの最小残量Ｃ４が下限値未満であるか否かを判定する。ステップＳ３０３においてノード到達可否判定部１３９により肯定判定がなされた場合には、ノード到達可否判定処理はステップＳ３０４へ進む。ステップＳ３０４では、ノード到達可否判定部１３９が処理対象の到着ノードデータＣの最小残量Ｃ４および確定補給地Ｃ６を更新し、ノード到達可否判定処理を終了する。具体的には、ノード到達可否判定部１３９が最小残量Ｃ４を最大残量Ｃ５と同じ値に設定すると共に、確定補給地Ｃ６を到着ノードＩＤＣ１と同じ値に設定する。他方、ステップＳ３０３において否定判定がなされた場合には、ノード到達可否判定処理を終了する。

なお、ステップＳ３０２において到達可否フラグＣ８が「否」に設定された到着ノードデータＣは、エネルギー残量の観点から到達することができないノードであるので、このノードに対してステップＳ１０５（図８）のループ処理をこれ以上実行する必要が無い。従って、経路探索部１３７は、到達可否フラグＣ８が「否」に設定された到着ノードデータＣをＤＲＡＭ１０３から消去すると共に、ステップＳ１０８の到達候補ノード登録判定処理を実行せずにステップＳ１０５のループ処理に戻る。

（到達候補ノード登録判定処理の説明）
図１３は、到達候補ノード登録判定処理のフローチャートである。この処理は候補ノード登録判定部１４０が、特定の到着ノードデータＣに対して実行する。

ステップＳ４０１では、候補ノード登録判定部１４０が、処理対象の到着ノードデータＣの到達コストＣ３が確定ノードリストＤＬに格納されている当該ノードの最小コストＤ４１未満か否かを判定する。この処理は、公知のダイクストラ法におけるノードの絞り込みと同一の処理である。すなわちこの処理は、到達コストが小さいノードのみを候補として絞り込むことにより、計算量を削減するための処理である。なお、公知のダイクストラ法では、最短の経路が確定したノード、すなわち確定ノードリストＤＬの確定情報Ｄ３に「Ｎ／Ａ」以外の値が存在するノードに対してステップＳ４０１に相当する処理を行わない。しかしながら、本実施形態においては経路が確定したノードであっても、その先のノードにおいてエネルギー残量不足になる可能性があるため、ステップＳ４０１の処理を全ての処理対象ノードに対して実行する。ステップＳ４０１において候補ノード登録判定部１４０により肯定判定がなされた場合、到達候補ノード登録判定処理はステップＳ４０５に進む。他方、ステップＳ４０１において否定判定がなされた場合、到達候補ノード登録判定処理はステップＳ４０３へ進む。

ステップＳ４０３では、候補ノード登録判定部１４０が、処理対象の到着ノードデータＣの最大残量Ｃ５が確定ノードリストＤＬに格納されている当該ノードの最大残量Ｄ３４以下であるか否かを判定する。なお、最大残量Ｄ３４が「Ｎ／Ａ」である場合には、最大残量Ｄ４２を比較に用いる。ステップＳ４０３において肯定判定がなされた場合、到達候補ノード登録判定処理は終了する。これは、ステップＳ４０３において肯定判定がなされたということは、到達コストおよびエネルギー残量が共に既知の経路より劣るということなので、処理対象のノードに対してこれ以上の経路探索処理を行う必要がないためである。他方、ステップＳ４０３において否定判定がなされた場合には、到達候補ノード登録判定処理はステップＳ４０５へ進む。

ステップＳ４０５では、候補ノード登録判定部１４０が処理対象の到着ノードデータＣを候補ノードヒープ１８１へ追加する。ステップＳ４０６では、候補ノード登録判定部１４０が、処理対象のノードの確定ノードリストＤＬにおける未確定情報Ｄ４を更新する。具体的には、候補ノード登録判定部１４０は、最小コストＤ４１が到着ノードデータＣの到達コストＣ３より大きければ、最小コストＤ４１を到着ノードデータＣの到達コストＣ３で置き換える。同様に、最大残量Ｄ４２が到着ノードデータＣの最大残量Ｃ５より小さければ、最大残量Ｄ４２を到着ノードデータＣの最大残量Ｃ５で置き換える。

以上の処理により候補ノードヒープ１８１には、特定のノードについて、到達コストＣ３が最小である到着ノードデータＣと、最大残量Ｃ５が最大である到着ノードデータＣと、が登録されることとなる。すなわち、候補ノードヒープ１８１には到達コストとエネルギー残量のどちらかで優位になるノードのみが残り、無駄な経路探索が行われない。通常は到達コストが大きいほどエネルギー消費量は大きくなる。従って、到達コストが大きく且つエネルギー残量が大きいケースは、補給を行ったケースや特殊な地形を走行したケースに限られる。このようなケースは確率的に少なく、候補ノードヒープ１８１に含まれるノードの数は比較的小規模に抑えられる。

次に、図１０のステップＳ１０２２の説明で述べた、候補ノードヒープ１８１が空であることが「目的地到達経路なし」となる理由について説明する。上記で説明した通り、候補ノードヒープ１８１には到達コストＣ３が最少、または最大残量Ｃ５が最大である到達ノードデータＣが登録されている。到達コストＣ３が最少である到達ノードデータＣは、ステップＳ１０２の処理によって逐次取り出されていく。そして、最大残量Ｃ５が最大である到達ノードデータＣが候補ノードヒープ１８１に登録されない状態、すなわち適切な補給地が存在しない状態になると、候補ノードヒープ１８１内のノード数が、目的地を発見する前に０になることがある。このような状態は、ステップＳ１０７（図１０）のノード到達可否判定処理がエネルギー残量の不足のため新しいノードを供給しなくなること、または、最大残量Ｃ５を越えるノードが存在しないため、ステップＳ１０８の到達候補ノード登録判定処理が新しいノードを登録しなくなることにより発生する。すなわち、このような状態は、目的地に下限値以上のエネルギー残量で到達できないことを意味している。なお、目的地未到達の場合、候補ノードヒープ１８１が空になるまで経路探索処理が実行され続けることになるが、前述した理由により候補ノードヒープ１８１の大きさは抑えられることになるので、計算量の爆発的増大は避けられる。

（経由地自動追加処理の説明）
図１４は、推奨経路のデータ構造を示す図である。図１４に示すように、経路探索部１３７が出力する推奨経路は、複数の到着ノードデータＣ（図８）が連なったデータ列Ｒである。図１４に示すデータ列Ｒは、出発地から目的地の順に、ｎ個の到着ノードデータＣが並んでいる。経由地自動追加部１３４は、データ列Ｒに含まれる到着ノードデータＣについて、先頭から順に確定補給地ノードＩＤの変化を検索する。経由地自動追加部１３４は、確定補給地ノードＩＤが変化しているノードを発見すると、この確定補給地ノードＩＤをネットワーク地図ＤＢ１２２から検索する。そして、対応する補給地ＩＤＬ５（図６）を取得し、更にこの補給地ＩＤＬ５を補給地ＤＢ１２３（図７）から検索する。経由地自動追加部１３４はこのようにして取得した補給地情報Ｓに基づき、補給地名称やその他表示に必要な情報を含む経由地のデータを推奨経路に追加する。経路表示部１３６はこれらのデータに基づいて、図５に示したような経由地の表示を行う。ユーザはこれらの経由地において補給を行い推奨経路上の他の補給地で補給を行わないことにより、補給回数を最少にすることができる。すなわち、経路探索部１３７は、確定補給地ノードＩＤという形で、補給を行う最適なタイミングを演算している。そして経路表示部１３６は上記のような表示を行うことにより、ユーザへ補給を行う最適なタイミングを報知している。

上述した第１の実施の形態によるナビゲーション装置によれば、次の作用効果が得られる。
（１）経路探索部１３７は、ノード残量算出部１３８に各ノードにおけるエネルギー残量を更新させながら、エネルギー残量が上下限残量設定部１３２により設定された下限値を下回らない経路のうち最少の到達コストを有する推奨経路を探索する。これにより、エネルギー残量を考慮した経路探索を計算量を抑えつつ行うことができる。

（２）経路探索部１３７は、推奨経路の探索時に、最少残量および確定補給地ノードＩＤという形で、補給回数が最も少なくなる補給タイミングを演算する。これにより、経路表示部１３６は、ユーザへ適切なタイミングで補給を促すことが可能となる。

（３）上下限残量設定部１３２は、補給地における補給によりエネルギー残量が増加する上限値を設定する。蓄電池は充電に要する時間がバッテリー残量により大きく変動するので、これによりエネルギーの補給に要する時間を抑制することができる。

（４）目的地到達可否判定部１３５は、エネルギー残量が上下限残量設定部１３２により設定された下限値を下回らずに目的地へ到達可能か否かを判定する。これにより、目的地の周辺に補給地が存在しない場合など、目的地に到達不可能であることをユーザへ報知することができる。

（第２の実施の形態）
第２の実施の形態に係るナビゲーション装置は、第１の実施の形態に係るナビゲーション装置に加えて、最適な補給地の選択を行う。なお、図１および図２に示す第１の実施の形態と同一の回路および装置には同一の符号を付し、説明を省略する。

本実施形態の経由地自動追加部１３４は、補給を行うべき補給地を、図１４を用いて説明した手順とは異なる手順により経由地として追加する。以下、推奨経路上に１からＮまでの番号が割り振られたＮ個の補給地ノードが存在する場合の、経由地自動追加部１３４による経由地自動追加処理について説明する。

蓄電池への充電には残量に応じた時間が必要とされる。そこで、この充電に必要な時間を推定するための関数Ｔ（ｒｉ）を定義する。ここでｒｉは、ｉ番目の補給地まで走行した場合のエネルギー残量である。一般に、エネルギー残量が少ないほど充電に要する時間は長くなるので、関数Ｔ（ｒｉ）は、ｒｉが小さいほどその値が大きくなるよう定義される。このとき、経由地自動追加部１３４は、「Ｔ（ｒ０）＋Ｔ（ｒ１）＋…＋Ｔ（ｒＮ）＋走行の所要時間」が最小となる補給地の組み合わせを探索する。この探索は、例えば線形計画法により行うことが可能である。経由地自動追加部１３４は、この探索により得られた補給地を、経由地として推奨経路へ追加する。

上述した第２の実施の形態によるナビゲーション装置によれば、第１の実施の形態によるナビゲーション装置で得られる作用効果に加えて、次の作用効果が得られる。
（１）経由地自動追加部１３４は、補給を行うべき補給地を、エネルギー残量に応じた充電時間を考慮して探索する。これにより、充電時間も含めた最短経路を探索することが可能となる。

次のような変形も本発明の範囲内であり、変形例の一つ、もしくは複数を上述の実施形態と組み合わせることも可能である。

（変形例１）
第１の実施の形態のように、単独で動作するナビゲーション装置だけではなく、経路探索機能を備えたサーバと、そのサーバに接続するクライアントと、から成るナビゲーションシステムへ本発明を適用してもよい。例えば、ナビゲーション装置が図１に示す電池残量センサ１０７，液晶モニタ１０９，タッチパネル１１０，現在地検出装置１１１、ならびに、図２に示す表示用地図ＤＢ１２４、探索条件設定部１３１、上下限残量設定部１３２、目的地設定部１３３，経路表示部１３６の各部に加えて、携帯電話網や無線ＬＡＮなどによりサーバと双方向通信を行う通信装置を備えるように構成する。他方、サーバはナビゲーション装置から現在地、目的地、エネルギー残量、各種の経路探索条件を受信する通信装置と、図２に示すネットワーク地図ＤＢ１２２、補給地ＤＢ１２３、経路探索部１３７を備えるように構成する。そしてサーバは、経路探索部１３７が出力した推奨経路を、通信装置を介してナビゲーション装置へ送信する。ナビゲーション装置は通信装置を介して受信した推奨経路を経路表示部１３６により液晶モニタ１０９へ表示すればよい。

（変形例２）
上述の実施形態ではダイクストラ法に対してエネルギー残量を考慮する各種処理を加えたが、ダイクストラ法以外の経路探索手法に対しても本発明を適用することが可能である。例えば、いわゆるＡ＊探索アルゴリズムについても、上述の実施形態と同様に本発明を適用することができる。

（変形例３）
上述の実施形態では、自車両２００は電気自動車であり、補給地は充電ステーションであるとしたが、自車両２００の駆動エネルギーの形態はこれに限定されない。例えば、ガソリン車とガソリン、水素自動車と水素燃料などであってもよい。

（変形例４）
第１の実施の形態において、補給地ＤＢ１２３に格納されているデータのうち、補給燃料の種類Ｓ４（図７）は「充電」のみとしたが、補給地ＤＢ１２３は異なる様々な種類の燃料を補給する補給地のデータを含んでいてよい。この場合、経路探索部１３７は自車両２００に関係のない補給地のデータを単純に無視する。例えば、自車両２００が電気自動車であれば、経路探索部１３７は補給燃料の種類Ｓ４が「ガソリン」や「水素」であるような補給地を無視する。また、１つの補給地が２種類以上の燃料を供給可能であることを表すため、補給燃料の種類Ｓ４へ２種類以上のデータを格納できるよう補給地ＤＢ１２３を構成してもよい。

（変形例５）
上下限残量設定部１３２は、目的地におけるエネルギー残量の下限の設定を行わなくてもよい。すなわち、上下限残量設定画面１４１（図３）から、目的地におけるエネルギー残量の下限１４４を削除してもよい。この場合、エネルギー残量の下限１４２を、目的地におけるエネルギー残量の下限としても用いる。同様に、上下限残量設定部１３２が、エネルギー残量の上限の設定を行わないようにしてもよい。この場合、経路探索部１３７は、エネルギー残量の上限を１００％として経路探索処理を行う。

（変形例６）
上下限残量設定部１３２は、目的地から目的地に最寄りの補給地までの経路を走行するために必要なエネルギー量を、目的地におけるエネルギー残量の下限として自動的に設定するようにしてもよい。

本発明の特徴を損なわない限り、本発明は上記実施の形態に限定されるものではなく、本発明の技術的思想の範囲内で考えられるその他の形態についても、本発明の範囲内に含まれる。

１００…ナビゲーション装置、１０１…制御回路、１０３…ＤＲＡＭ、１０４…不揮発性メモリ、１０５…ディスクドライブ、１０６…ＤＶＤ−ＲＯＭ、１０７…電池残量センサ、１０８…交通情報受信機、１０９…液晶モニタ、１１０…タッチパネル、１１１…現在地検出装置、１２１…ＰＯＩＤＢ、１２２…ネットワーク地図ＤＢ、１２３…補給地ＤＢ、１２４…表示用地図ＤＢ、１３１…探索条件設定部、１３２…上下限残量設定部、１３３…目的地設定部、１３４…経由地自動追加部、１３５…目的地到達可否判定部、１３６…経路表示部、１３７…経路探索部、１３８…ノード残量算出部、１３９…ノード到達可否判定部、１４０…候補ノード登録判定部、２００…自車両

Claims (7)

1. 現在地を検出する現在地検出手段と、
   自車両の駆動エネルギーの残量を検出するエネルギー残量検出手段と、
   自車両への前記駆動エネルギーの補給地の位置情報を含む地図情報が記憶された記憶手段と、
   前記地図情報に基づいて、前記地図情報に含まれる任意のリンクを走行する際の前記駆動エネルギーの消費量を算出するエネルギー消費量算出手段と、
   前記現在地から目的地に至る経路を演算する経路演算手段と、
   前記経路演算手段による演算の結果に基づいて、自車両の経路誘導を行う経路誘導手段とを備え、
   前記経路演算手段は、確定済み経路の終端ノードに隣接するノードを辿って経路を探索する際、前記終端ノードに隣接するそれぞれのノードについて、前記補給地の位置情報と、前記エネルギー消費量算出手段により算出された前記終端ノードから当該ノードまで走行する際の前記消費量とから、前記残量が所定のしきい値を下回ることなく前記確定済み経路を辿って当該ノードまで走行可能な他の経路を演算し、当該ノードに最小コストで到達する経路を走行後の前記残量が前記しきい値を下回る場合には、前記他の経路のうち前記残量が最大となるものを、前記確定済み経路を辿り当該ノードに到達する経路として確定させることにより、前記残量が前記しきい値を下回らない経路のうち最小のコストを有する推奨経路を演算することを特徴とするナビゲーション装置。
2. 請求項１に記載のナビゲーション装置において、
   前記経路誘導手段による経路誘導中に、運転者へ前記駆動エネルギーの補給タイミングを報知する報知手段を更に備え、
   前記経路演算手段は、前記推奨経路を走行時に通過する前記補給地における補給回数が最も少なくなる補給タイミングを演算し、
   前記報知手段は、前記経路演算手段により演算された補給タイミングに基づいて、補給タイミングの報知を行うことを特徴とするナビゲーション装置。
3. 請求項２に記載のナビゲーション装置において、
   前記経路演算手段は、ダイクストラ法を用いた前記推奨経路の演算において、コストと共に前記残量の最小値および最大値を演算および記憶することを特徴とするナビゲーション装置。
4. 請求項１〜３のいずれか一項に記載のナビゲーション装置において、
   前記所定のしきい値と前記残量の上限値とを設定する上下限値設定手段を更に備え、
   前記経路演算手段は、前記補給地における補給が前記残量を前記上限値まで増加させることを前提として前記推奨経路を演算することを特徴とするナビゲーション装置。
5. 請求項１〜４のいずれか一項に記載のナビゲーション装置において、
   前記残量が所定のしきい値を下回らずに前記目的地へ到達可能か否かを判定する到達可否判定手段を更に備えることを特徴とするナビゲーション装置。
6. 請求項１〜３のいずれか一項に記載のナビゲーション装置において、
   前記目的地における前記残量の下限値を設定する下限値設定手段を更に備え、
   前記経路演算手段は、前記目的地における前記残量が前記下限値以上である前記推奨経路を演算することを特徴とするナビゲーション装置。
7. 出発時における自車両の駆動エネルギーの残量を設定するエネルギー残量設定工程と、
   自車両への前記駆動エネルギーの補給地の位置情報を含む地図情報に基づいて、前記地図情報に含まれる任意のリンクを走行する際の前記駆動エネルギーの消費量を算出するエネルギー消費量算出工程と、
   前記現在地から目的地に至る経路を演算する経路演算工程とを備え、
   前記経路演算工程では、確定済み経路の終端ノードに隣接するノードを辿って経路を探索する際、前記終端ノードに隣接するそれぞれのノードについて、前記補給地の位置情報と、前記エネルギー消費量算出行程により算出された前記終端ノードから当該ノードまで走行する際の前記消費量とから、前記残量が所定のしきい値を下回ることなく前記確定済み経路を辿って当該ノードまで走行可能な他の経路を演算し、当該ノードに最小コストで到達する経路を走行後の前記残量が前記しきい値を下回る場合には、前記他の経路のうち前記残量が最大となるものを、前記確定済み経路を辿り当該ノードに到達する経路として確定させることにより、前記残量が前記しきい値を下回らない経路のうち最小のコストを有する推奨経路を演算することを特徴とする経路演算方法。

Images