ナビゲーション装置および経路演算方法
【課題】エネルギー残量を考慮した経路探索ができるナビゲーション装置および経路演算方法を提供する。
【解決手段】現在地を検出する現在地検出装置と、自車両の駆動エネルギーの残量を検出する電池残量センサと、補給地DB123およびネットワーク地図DB122が記憶されたDVD−ROM106と、ネットワーク地図DB122に含まれる任意のリンクを走行する際の駆動エネルギーの消費量を算出するノード残量算出部138と、現在地から目的地に至る経路を演算する経路探索部137と、自車両の経路誘導を行う経路表示部136とを備え、経路探索部137は、補給地DB123およびネットワーク地図DB122と、電池残量センサにより検出された出発時の残量と、ノード残量算出部138により算出された消費量とに基づいて、残量が所定のしきい値を下回らない経路のうち最少のコストを有する推奨経路を演算する。
【解決手段】現在地を検出する現在地検出装置と、自車両の駆動エネルギーの残量を検出する電池残量センサと、補給地DB123およびネットワーク地図DB122が記憶されたDVD−ROM106と、ネットワーク地図DB122に含まれる任意のリンクを走行する際の駆動エネルギーの消費量を算出するノード残量算出部138と、現在地から目的地に至る経路を演算する経路探索部137と、自車両の経路誘導を行う経路表示部136とを備え、経路探索部137は、補給地DB123およびネットワーク地図DB122と、電池残量センサにより検出された出発時の残量と、ノード残量算出部138により算出された消費量とに基づいて、残量が所定のしきい値を下回らない経路のうち最少のコストを有する推奨経路を演算する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ナビゲーション装置および経路演算方法に関する。
【背景技術】
【0002】
車載用ナビゲーション装置において、車両のエネルギー残量を考慮して経路の変更及び表示を行う技術が知られている。車両のエネルギー残量とは、例えば内燃機関を利用する自動車であればガソリンなどの燃料の残量を、電気自動車であれば蓄電池の残容量を、水素自動車であれば水素燃料自体の残量もしくは水素に変換するための液体の残量を指す。また、「エネルギー残量を考慮する」とは、走行中にエネルギー不足になることのないよう、エネルギーの補給地における補給を考慮するということである。例えば特許文献1の経路探索装置は、出発地から最初の充電ステーションまでの距離が航続距離以下で、且つ最初の充電ステーションから目的地までの各充電ステーション区間の距離が満充電の航続距離以下の経路を探索する。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開平10−170293号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
特許文献1の経路探索装置は、エネルギー補給地を含む経路の組み合わせを全て選択し、その中から目的地へ到達可能な経路を探索する。従って、探索すべき経路の組み合わせが膨大となり、莫大な計算量が必要となってしまうという問題があった。
【課題を解決するための手段】
【0005】
請求項1に係る発明は、現在地を検出する現在地検出手段と、自車両の駆動エネルギーの残量を検出するエネルギー残量検出手段と、自車両への駆動エネルギーの補給地の位置情報を含む地図情報が記憶された記憶手段と、地図情報に基づいて、地図情報に含まれる任意のリンクを走行する際の駆動エネルギーの消費量を算出するエネルギー消費量算出手段と、現在地から目的地に至る経路を演算する経路演算手段と、経路演算手段による演算の結果に基づいて、自車両の経路誘導を行う経路誘導手段とを備え、経路演算手段は、地図情報と、エネルギー残量検出手段により検出された出発時の残量と、エネルギー消費量算出手段により算出された消費量とに基づいて、残量が所定のしきい値を下回らない経路のうち最少のコストを有する推奨経路を演算することを特徴とするナビゲーション装置である。
請求項7に係る発明は、出発時における自車両の駆動エネルギーの残量を設定するエネルギー残量設定工程と、自車両への駆動エネルギーの補給地の位置情報を含む地図情報に基づいて、地図情報に含まれる任意のリンクを走行する際の駆動エネルギーの消費量を算出するエネルギー消費量算出工程と、現在地から目的地に至る経路を演算する経路演算工程とを備え、経路演算工程では、地図情報と、エネルギー残量設定工程により設定された出発時の残量と、エネルギー消費量算出工程により算出された消費量とに基づいて、残量が所定のしきい値を下回らない経路のうち最少のコストを有する推奨経路を演算することを特徴とする経路演算方法である。
【発明の効果】
【0006】
本発明によれば、エネルギー残量を考慮した経路探索を計算量を抑えつつ行うことができる。
【図面の簡単な説明】
【0007】
【図1】本発明の第1の実施の形態であるナビゲーション装置の構成を示すブロック図である。
【図2】制御回路101およびDVD−ROM106の詳細を表すブロック図である。
【図3】上下限残量設定部132への入力画面を示す図である。
【図4】経路表示部136による経路表示画面の例を示す図である。
【図5】経路誘導画面の例を示す図である。
【図6】ネットワーク地図DB122のデータ構造を示す図である。
【図7】補給地DB123のデータ構造を示す図である。
【図8】候補ノードヒープのデータ構造を示す図である。
【図9】確定ノードリストのデータ構造を示す図である。
【図10】経路探索処理のフローチャートである。
【図11】ノードエネルギー残量算出処理のフローチャートである。
【図12】ノード到達可否判定処理のフローチャートである。
【図13】到達候補ノード登録判定処理のフローチャートである。
【図14】推奨経路のデータ構造を示す図である。
【発明を実施するための形態】
【0008】
(第1の実施の形態)
図1は、本発明の第1の実施の形態であるナビゲーション装置の構成を示すブロック図である。ナビゲーション装置100は自車両200に搭載され、自車両200のエネルギー残量を考慮した経路探索および経路誘導を行う。ここで自車両200は、蓄電池に充電された電気エネルギーにより駆動される、いわゆる電気自動車である。従って、第1の実施の形態において、自車両200のエネルギー残量とはすなわち自車両200の蓄電池の残量のことである。
【0009】
(ナビゲーション装置の説明)
ナビゲーション装置100は、制御回路101、DRAM103、不揮発性メモリ104、ディスクドライブ105、電池残量センサ107、交通情報受信機108、液晶モニタ109、タッチパネル110、および現在地検出装置111を有する。ディスクドライブ105には、DVD−ROM106が装填されている。
【0010】
制御回路101は、マイクロプロセッサ及びその周辺回路から構成される。DRAM103は揮発性の記憶装置である。不揮発性メモリ104は、例えばフラッシュメモリ等の不揮発性の記憶媒体であり、所定の制御プログラムが格納されている。制御回路101は、DRAM103を作業領域として不揮発性メモリ104に格納された制御プログラムを実行し、各種の制御を行う。ディスクドライブ105は、DVD−ROM106からデータの読み取りを行う装置である。
【0011】
電池残量センサ107は自車両200に接続されたセンサである。電池残量センサ107は、自車両が有する蓄電池の残量を検知し、制御回路101へ通知する。交通情報受信機108は、例えばVICS(Vehicle Information and Communication System)(登録商標)などにより提供される交通情報を受信し、制御回路101へ出力する。ここで交通情報とは、道路の渋滞情報や事故情報などである。
【0012】
液晶モニタ109は、制御回路101が出力する画像データに基づき、各種情報を画面表示として自車両200の搭乗者へ提示する。タッチパネル110は、液晶モニタ109の表面に積層される透明のタッチスイッチである。液晶モニタ109に表示される画像はタッチパネル110を介して表示される。搭乗者が液晶モニタ109の表示画面を押圧すると、タッチパネル110が押圧される。このとき、タッチパネル110から制御回路101へ押圧した位置の情報を含む操作信号が出力される。そして、制御回路101が液晶モニタ109へ表示されている地図上の押圧した位置へ目的地を設定したり、押圧した位置に表示されている各種ボタンや表示メニューに定義された処理を実行したりする。
【0013】
現在地検出装置111は自車両200の現在地を検出する装置である。現在地検出装置111はGPS(Global Positioning System)受信機111a、ジャイロスコープ111b、車速センサ111c等の各種センサを有する。GPS受信機111aはGPS衛星から送出される信号を受信し、自車両200の絶対位置を検出する。ジャイロスコープ111bは車両の進行方向を検出する。車速センサ111cは自車両200が出力する車速パルス信号を受信し、自車両200の車速を検出する。現在地検出装置111はこれらのセンサが検出した各種の情報を演算し、自車両200の現在地を検出する。
【0014】
ナビゲーション装置100は、ユーザから経路誘導の目的地を受け付けると、現在地検出装置111により検出された現在地を出発地として、目的地までの経路演算を後に詳述するアルゴリズムに基づいて行う。ナビゲーション装置100は、液晶モニタ109の表示画面へ地図を表示すると共に、この経路演算により求められた経路(以下、推奨経路という)を地図上へ表示する。ナビゲーション装置100は、ユーザに対して画面や音声などによる進行方向指示を行い、推奨経路に従って自車両200が走行できるように、自車両200を経路誘導する。
【0015】
図2は、制御回路101およびDVD−ROM106の詳細を表すブロック図である。DVD−ROM106には、POIDB(Point Of Interestデータベース)121と、ネットワーク地図DB122と、補給地DB123と、表示用地図DB124と、が格納されている。POIDB121は、ランドマークや観光スポットなど経路探索の目的地を設定するためのデータを、ジャンル検索や名称検索など様々な検索が可能な形式で整理したデータベースである。ネットワーク地図DB122は、経路探索を行う際に用いられるネットワーク地図が格納されたデータベースである。ネットワーク地図DB122に格納されたネットワーク地図は、公知のネットワーク地図と同様に、道路網を交差点などのノードとノード間のリンクとの組み合わせにより表現している。
【0016】
補給値DB123は、車両へエネルギーの補給を行う施設の情報を含むデータベースである。以下の説明では、このような施設のことを補給地と呼ぶ。本実施形態では、電気自動車である自車両200へ充電を行う充電ステーションが補給地である。表示用地図DB124は、例えば道路、鉄道、地形、施設形状、地名等、液晶モニタ109の表示画面へ地図を表示するためのデータが格納されたデータベースである。表示用地図DB124に格納されたデータのうち道路データは、リンクやノードに対して、ネットワーク地図DB122の道路データと共通のIDが利用されている。これにより、ネットワーク地図DB122と表示用地図DB124とは、道路データの相互参照が可能である。制御回路101は、例えば経路探索の結果を画面に表示する場合などに、道路データの相互参照を行う。
【0017】
制御回路101は、探索条件設定部131、上下限残量設定部132、目的地設定部133、経由地自動追加部134、目的地到達可否判定部135、経路表示部136、および経路探索部137を備える。経路探索部137は更に、ノード残量算出部138、ノード到達可否判定部139、および候補ノード登録判定部140を備える。これらの各機能部は、制御回路101が不揮発性メモリ104に格納された制御プログラムを実行することにより、ソフトウェア的に実現される。
【0018】
探索条件設定部131は、ユーザからのタッチパネル110による入力に基づき、経路探索の条件を設定する。経路探索の条件には、例えば距離優先、時間優先、金銭コスト優先、エネルギー消費量優先などの条件を設定することが可能である。経路探索部137は、探索条件設定部131により設定された経路探索の条件に基づいて経路探索を行う。
【0019】
上下限残量設定部132は、ユーザからのタッチパネル110による入力に基づき、経路探索におけるエネルギー残量の上限および下限を設定する。上下限残量設定部132は更に、目的地へ到着した時点におけるエネルギー残量の下限を設定する。経路探索部137は、上下限残量設定部132により設定されたエネルギー残量の範囲内で経路探索を行う。例えば、上下限残量設定部132がエネルギー残量の下限を20%に設定した場合、経路探索部137は走行中のエネルギー残量が常に20%を上回る推奨経路を探索する。
【0020】
目的地設定部133は、ユーザからのタッチパネル110による入力に基づき、経路探索の目的地を設定する。目的地設定部133は、POIDB121を利用して、ジャンル検索、名称検索、地図表示からの選択など、ナビゲーション装置において広く用いられている目的地の入力方法をユーザへ提供する。
【0021】
経由地自動追加部134は、推奨経路に含まれる補給地ノード群に基づいて、推奨経路へ経由地を追加する。目的地到達可否判定部135は、経路探索部137の出力に基づいて、目的地への到達可否を判定する。
【0022】
経路表示部136は、液晶モニタ109の表示画面へ地図を表示すると共に、経路探索部137が出力した経路を地図上へ表示する。経路表示部136は推奨経路を他の道路などとは異なる表示形態(例えば表示色など)で表示する。これにより、ユーザは地図上の推奨経路を他の道路などと画面上で区別することができる。また経路表示部136は、推奨経路に経由地が含まれる場合、他のノードとは異なる表示形態で経由地を表示する。
【0023】
経路探索部137は、現在地検出装置111が検出した現在地を出発地として、目的地設定部133が設定した目的地までの経路探索を行う。経路探索部137はこの経路探索を、電池残量センサ107が検知した蓄電池の残量と、交通情報受信機108が出力した交通情報と、DVD−ROM106に格納されているネットワーク地図DB122と、探索条件設定部131が設定した経路探索の条件と、に基づいて行う。経路探索部137は経路探索に成功した場合、推奨経路を出力する。他方、経路探索に失敗した場合、経路探索部137は目的地に向かう途中までの経路を出力する。
【0024】
ノード残量算出部138は、経路探索処理の際、補給地の通過有無を考慮して各ノードにおける自車両200のエネルギー残量を算出する。ノード到達可否判定部139は、各ノードについて、上下限残量設定部132により設定されたエネルギー残量の下限を上回るエネルギー残量で到達可能か否かを判定する。候補ノード登録判定部140は、各ノードについて経路探索処理を継続する必要があるか否かを判定する。
【0025】
(上下限残量設定の説明)
図3は、上下限残量設定部132への入力画面を示す図である。ユーザは経路探索に先立って、タッチパネル110によりエネルギー上下限残量設定画面141を呼び出すことが可能である。ユーザはタッチパネル110によりエネルギー残量の下限142、上限143、および目的地でのエネルギー残量の下限144を入力できる。上下限残量設定部132はこれらの入力に基づいて、経路探索におけるエネルギー残量の上限および下限を設定する。
【0026】
(経路表示の説明)
図4は、経路表示部136による経路表示画面の例を示す図である。図4(a)には、経路表示部136が表示する地図上での経路表示画面151を示す。画面151には、現在地152、目的地153、ボタン154、経路探索部137が出力した推奨経路155、経路探索部137が公知の経路探索手法により補給地を考慮せずに出力した経路156、推奨経路155上の補給地157、158、および経路156上の補給地159が表示されている。経路表示部136は画面151を表示用地図DB124に基づいて描画する。画面151において、補給地157、158、159は1〜3の数字により表現されているが、この数字の代わりに補給地の名称を用いてもよい。ユーザがタッチパネル110によりボタン154を押下すると、経路表示部136が液晶モニタ109の表示画面を画面151から図4(b)に示す詳細表示画面161に切り替える。
【0027】
図4(b)に示す詳細表示画面161は、上述した2つの経路155、156を共通の時間軸を基準として、経由地も含め比較表示した画面である。画面161上の領域162には、各々の経路を走行した場合のエネルギー残量の変化が矢印および数値で表示されている。矢印163、164は経路を表す矢印であり、特に破線で描画された矢印164は、走行中にエネルギーが不足する経路を示している。矢印の下側には、各々の時刻におけるエネルギー残量の変化が数値で表示されている。ユーザがタッチパネル110によりボタン165を押下すると、経路表示部136が液晶モニタ109の表示画面を画面161から図4(a)に示す経路表示画面151に切り替える。なお、図4(b)において、領域162の横方向は経過時間を表しているが、走行距離を表すようにしてもよい。
【0028】
なお、経路探索の後、目的地到達可否判定部135が目的地に到達できる経路を探索できなかったと判定した場合には、経路表示部136が液晶モニタ109へ、探索可能経路が発見できない旨の表示を行ってもよい。またこの場合、経路表示部136は経路探索部137が出力した途中までの経路を表示する。
【0029】
(経路誘導画面の説明)
図5は、経路誘導画面の例を示す図である。経路表示部136は、ナビゲーション装置100による経路誘導が行われているとき、経路誘導画面171を液晶モニタ109へ表示する。この経路誘導画面171では、経由地自動追加部134により推奨経路へ追加された経由地のユーザへの報知が行われる。具体的には、経路表示部136は、画面171上に表示される、自車両172の進行方向を表す矢印173に、経由地を表すマーク174を重ねて表示する。また経路表示部136は、経由地においてエネルギーの補給が必要であることを、吹き出し175によりユーザへ報知すると共に、エネルギー残量の変化量を表す数値を吹き出し175の下部に表示する。
【0030】
(データベースの説明)
図6は、ネットワーク地図DB122のデータ構造を示す図である。ネットワーク地図DB122には、ノード情報Nが複数格納されている。個々のノード情報Nは、公知のネットワーク地図と同様に、始点ノードIDN1と、接続ノード数N2と、1つ以上の接続ノード情報Lと、から構成される。また個々の接続ノード情報Lは、公知のネットワーク地図と同様に、接続ノードIDL1と、リンク長L2と、所要時間L3と、を含む。
【0031】
本実施形態では、接続ノード情報Lがこれらのデータに加えて、補給地フラグL4と、補給地IDL5と、を含む。補給地フラグL4は、当該ノードが補給地か否かを表すフラグである。すなわち、補給地フラグL4が1であれば、当該ノードの位置に充電ステーションが存在する。補給地IDL5は、補給地を特定する為のIDである。制御回路101は、補給地IDL5を用いることにより、補給地DB123の参照を高速に行うことができる。接続ノード情報Lの補給地フラグL4が0である場合、この接続ノード情報Lは補給地IDL5を含まない。
【0032】
図7は、補給地DB123のデータ構造を示す図である。補給地DB123には、補給地情報Sが複数格納されている。個々の補給地情報Sは、補給地IDS1と、補給地名称S2と、補給地のジャンルS3と、補給燃料の種類S4と、対応ノードIDS5と、正規化座標S6と、から構成される。補給地IDS1は、個々の補給地に一意に割り当てられたIDである。前述したネットワーク地図DB122に含まれる補給地IDL5には、この補給地IDS1が格納されている。
【0033】
補給地名称S2は補給地の名称を表す。補給地のジャンルS3は、各々の補給地を分類するためのジャンル名である。補給燃料の種類S4は、この補給地で補給可能なエネルギーの種類である。本実施形態では、補給燃料の種類S4は「充電」である。対応ノードIDS5は、ネットワーク地図DB122に格納されているノード情報Nを参照するための始点ノードIDである。制御回路101は、この対応ノードIDS5を用いることにより、ネットワーク地図DB122の参照を高速に行うことができる。正規化座標S6は、補給地の位置を表す座標である。
【0034】
(経路探索処理で扱うデータ構造の説明)
経路探索部137は、経路探索処理において、「候補ノードヒープ」と「確定ノードリスト」という2つのデータ集合を扱う。これらのデータ集合はいずれも、公知のダイクストラ法において用いられるデータ構造にいくつかのデータ項目を追加したものとなっている。
【0035】
図8は、候補ノードヒープのデータ構造を示す図である。図8(a)に示すように、候補ノードヒープ181は、1つ乃至複数の到着ノードデータCにより公知のヒープ構造を成す。ヒープ構造とは木構造の一種であり、親要素がどの子要素よりも小さな評価値を有するように構成される。木に対して要素の追加や削除などの操作を行った場合でも、上記の条件は常に満たされる。図8(a)では、個々のノードの評価値を、ノードを表す円の中に描画している。
【0036】
図8(b)は、候補ノードヒープ181を構成する個々の到着ノードデータCのデータ構造を示図である。1つの到着ノードデータCは1つのノードに対応しており、経路探索処理中にあるノードへ特定の経路で到達した場合の、そのノードにおける各種情報を表している。到着ノードデータCは、到着ノードIDC1と、前回ノードIDC2と、ヒープの評価値として扱われる到達コストC3と、最小残量C4と、最大残量C5と、確定補給地ノードIDC6と、直前補給地ノードIDC7と、到達可否フラグC8と、から構成される。到着ノードIDC1、前回ノードIDC2、確定補給地ノードIDC6、および直前補給地ノードIDC7は、ノードIDに付随する通番を備えている。
【0037】
到着ノードIDC1は、到達したノードのノードIDである。前回ノードIDC2は、このノードへ到達した経路において、直前に通過したノードのノードIDである。到達コストC3は、このノードへ到達するために要したコストの総計である。最小残量C4は、可能な限り補給を行わずにこのノードへ到達した場合のエネルギー残量を、確定補給地ノードIDC6は同様の場合において直前に補給を行った補給地のノードIDを表す。最大残量C5は、可能な限り頻繁に補給を行いつつこのノードへ到達した場合のエネルギー残量を、直前補給地ノードIDC7は同様の場合において直前に補給を行った補給地のノードIDを表す。到達可否フラグC8は、到達したノードに対し、エネルギー残量が上下限残量設定部132により設定された下限を下回らずに到達可能か否かを表すフラグである。
【0038】
以上のように、到着ノードデータCには、通常のダイクストラ法では用いられない最小残量C4、最大残量C5、確定補給地ノードIDC6、直前補給地ノードIDC7、および到達可否フラグC8というデータが存在する。
【0039】
図9は、確定ノードリストのデータ構造を示す図である。確定ノードリストDLを構成する1つのレコードは1つのノードに関する情報を表し、通番D1、ノードIDD2、確定情報D3、および未確定情報D4から成る。確定情報D3は、到達コストD31、前回IDD32、最小残量D33、および最大残量D34から構成される。未確定情報D4は、最小コストD41および最大残量D42から構成される。
【0040】
通番D1は、各ノードに対して1から順に割り当てられた通し番号である。この通番は、1回の経路探索処理を通して、ノードIDと1対1に対応する。経路探索部137を含む各部は、ノードIDの代わりにこの通番を用いることにより、各レコードへ高速にアクセスすることができる。ノードIDD2は、このレコードが表すノードに割り当てられた一意な識別子であり、ノード情報N(図6)における始点ノードIDN1に対応する。確定情報D3は、このレコードが表すノードへのコストが最小となる経路が確定したときの、到着ノードデータC(図8)における到達コストC3、前回ノードIDC2、最小残量C4、および最大残量C5である。未確定情報D4は、このレコードが表すノードへのコストが最小となる経路が確定していないときに用いる暫定的なデータである。未確定情報D4の最小コストD41は到着ノードデータC(図8)における到達コストC3に対応し、同様に最大残量D42は到着ノードデータC(図8)における最大残量C5に対応する。
【0041】
(経路探索処理の説明)
図10は、経路探索処理のフローチャートである。本実施形態における経路探索処理は、公知の経路探索処理において利用されるダイクストラ法のアルゴリズムをベースに、エネルギー残量を考慮した各種の処理を追加したものである。
【0042】
ステップS100では、経路探索部137が初期化処理を行う。具体的には、経路探索部137は候補ノードヒープ181を空の状態にすると共に、ネットワーク地図DB122から経路探索処理の対象とする領域内の全ノード情報を読み出す。この領域は、例えば出発地および目的地とその周辺とを含む矩形領域とし、矩形の一辺は、例えば出発地と目的地との間の距離のおよそ1.5倍〜2倍と設定し、経路探索に不要と思われる領域を排除する。経路探索部137は、このようにして読み出した複数のノード情報に基づいて、DRAM103へ図9に示した確定ノードリストDLを作成する。経路探索部137は確定ノードリストDLの各々のレコードのノードIDD2へ、読み出したノード情報に含まれるノードIDを格納し、通番D1へ1から始まる通し番号を割り当てる。経路探索部137は、確定ノードリストDLの通番D1とノードIDD2以外のフィールドには、データが存在しないことを表す「N/A」を書き込む。
【0043】
ステップS1021では、経路探索部137が、候補ノードヒープ181の構成ノードが空であるか否かを判定する。ステップS1021において、経路探索部137により空であることが肯定された場合にはステップS1022へ進み、「目的地到達経路なし」との結果を返す処理を行い経路探索処理を終了する。こうして経路探索部137によって、目的地到達可否が判定される。候補ノードヒープ181が空であることが「目的地到達経路なし」となる理由については、ステップS108の処理後の候補ノードヒープ181の状態によるため、図13の説明によって後述する。
【0044】
ステップS101では、経路探索部137が出発地ノードの到着ノードデータCを作成し、候補ノードヒープ181へ登録する。これにより、候補ノードヒープ181は、出発地ノードのみを含む状態になる。出発地ノードの到着ノードデータCは、到着ノードIDC1には出発地ノードのノードID、到達コストC3には0、最小残量C4および最大残量C5には電池残量センサ107により検知された出発時のエネルギー残量、到達か非フラグC8には「可」、がそれぞれ設定され、それ以外の項目にはデータが存在しないことを表す「N/A」が設定される。
【0045】
ステップS102では、経路探索部137が候補ノードヒープ181から最小の到達コストC3を有する到着ノードデータCを取り出し、この到着ノードデータCの情報を確定ノードリストDLの確定情報D3へ格納する。具体的には、経路探索部137は到達コストD31へ到達コストC3を、前回IDD32へ前回ノードIDC2を、最小残量D33へ最小残量C4を、最大残量D34へ最大残量C5をそれぞれ格納する。候補ノードヒープ181は、根ノードが最小の到達コストC3を有するよう構成されるので、経路探索部137は候補ノードヒープ181から根ノードを取り出せばよい。
【0046】
ステップS103では、経路探索部137はステップS102において取り出された到着ノードデータCが目的地ノードに対応するか否かを判定する。取り出された到着ノードデータCが目的地ノードに対応する到着ノードデータCではなかった場合、経路探索部137により否定判定がなされ、ステップS104へ進む。
【0047】
ステップS104では、経路探索部137が、ステップS102において取り出された到着ノードデータCのノードに接続する全てのノードを、ステップS100において読み出されたノード情報に基づいて取り出す。経路探索部137は、このようにして取り出された各々のノードについて、対応する到着ノードデータCを作成してDRAM103へ格納する。このとき、到着ノードIDC1には取り出されたノードのノードIDが、前回ノードIDC2にはステップS102において取り出された到着ノードデータCの到着ノードIDC1が、確定補給地ノードIDC6および直前補給地ノードIDC7にはステップS102において取り出された到着ノードデータCと同一の内容が、到達可否フラグC8には「可」がそれぞれ設定され、それ以外の項目にはデータが存在しないことを表す「N/A」が設定される。
【0048】
ステップS105では、経路探索部137が、ステップS104において作成された各々の到着ノードデータCに対して、ステップS106〜ステップS108の処理を実行する。ステップS106では、ノード残量算出部138が、各々の到着ノードデータCに対してノードエネルギー残量算出処理を実行する。ステップS107では、ノード到達可否判定部139が、各々の到着ノードデータCに対してノード到達可否判定処理を実行する。ステップS108では、候補ノード登録判定部140が、各々の到着ノードデータCに対して到達候補ノード登録判定処理を実行する。ノードエネルギー残量算出処理、ノード到達可否判定処理、および到達候補ノード登録判定処理については後に詳述する。ステップS106〜ステップS108の処理の実行が完了したら、経路探索処理はステップS102へ戻る。
【0049】
他方、ステップS103において経路探索部137により肯定判定がなされた場合には、経路探索処理はステップS109へ進む。ステップS109では、経路探索部137が確定ノードリストDLを用いて出発地ノードから目的地ノードへと至る到着ノードデータCのデータ列、すなわち推奨経路を出力する。具体的には、経路探索部137はまず目的地ノードのノードIDD2を取り出した後、目的地ノードの前回IDD32を取り出す。経路探索部137はその後、この前回IDD32に対応するノードIDD2を確定ノードリストDLから探索し、同様に前回IDD32を取り出す。経路探索部137は目的地ノードに到達するまでこの処理を繰り返し、取り出されたノードID列を逆順にする。最終的に経路探索部137は、この取り出されたノードID列に基づいて、到着ノードデータCの列を作成して出力する。以上の処理により、経路探索部137は推奨経路を出力する。
【0050】
なお、以上で説明した経路探索処理では、上下限残量設定部132により設定される、目的地に到着した時点におけるエネルギー残量の下限に関する処理を省略している。この下限を考慮する場合は、ノード到達可否判定処理(ステップS107)内において、目的地ノードに対し、上下限残量設定部132により設定された下限値を用いた判定を行う。詳細は、図12の説明において後述する。
【0051】
(ノードエネルギー残量算出処理の説明)
図11は、ノードエネルギー残量算出処理のフローチャートである。この処理はノード残量算出部138が、特定の到着ノードデータCに対して実行する。この処理の対象となる到着ノードデータCは、到着ノードIDC1、前回ノードIDC2、確定補給地ノードIDC6、直前補給地ノードIDC7、および到達可否フラグC8を除く全ての項目に「N/A」が設定されている。
【0052】
ステップS201では、ノード残量算出部138が、処理対象のノードのノード情報Nに基づいて、エネルギー消費量およびリンクコストを計算する。エネルギー消費量は、予め与えられた単位距離当たりのエネルギー消費量やリンク長L1(図6)などを用いて、公知の手法により計算することが可能である。リンクコストは探索条件設定部131により設定された探索条件に基づくコストであり、例えば距離優先であればリンク長L1(図6)を、時間優先であれば時間L3(図6)および交通情報受信機108により出力された交通情報を用いて、公知の手法によりそれぞれ計算される。また、探索条件がエネルギー消費量優先であれば上記のエネルギー消費量、金銭コスト優先であれば有料道路料金やエネルギー費用などにより、同様にノード残量算出部138がリンクコストを計算する。
【0053】
ステップS202では、ノード残量算出部138が、処理対象の到着ノードデータCの到達コストC3、最小残量C4、および最大残量C5を設定する。ノード残量算出部138は、ステップS102で取り出されたノードの到達コストC3とステップS201で計算されたリンクコストとを加算することにより、処理対象の到着ノードデータCの到達コストC3を算出する。ノード残量算出部138は、同様にステップS102で取り出されたノードの最小残量C4および最大残量C5から、ステップS201で計算されたエネルギー消費量を減ずることにより、処理対象の到着ノードデータCの最小残量C4および最大残量C5を算出する。なお、自車両200が例えば回生ブレーキを備える場合など、ステップS201で算出されたエネルギー消費量が負の値となる場合があり得るが、この場合は処理の都合上エネルギー消費量を0%として扱う。
【0054】
ステップS203では、ノード残量算出部138が、処理対象のノードが補給地ノードであるか否かを判定する。すなわち、処理対象のノードのノード情報Nにおいて、補給地フラグL4(図6)が1であるか否かを判定する。処理対象のノードが補給地ノードである場合、ノード残量算出部138により肯定判定がなされ、ノードエネルギー残量算出処理はステップS204へ進む。ステップS204では、ノード残量算出部138が、処理対象の到着ノードデータCの最大残量C5および直前補給地ノードIDC7を更新し、ノードエネルギー残量算出処理を終了する。具体的には、最大残量C5が上下限残量設定部132により設定されたエネルギー残量の下限となり、直前補給地ノードIDC7が処理対象の到着ノードデータCの到着ノードIDC1となる。他方、ステップS203において否定判定がなされた場合には、ノードエネルギー残量算出処理を終了する。
【0055】
(ノード到達可否判定処理の説明)
図12は、ノード到達可否判定処理のフローチャートである。この処理はノード到達可否判定部139が、特定の到着ノードデータCに対して実行する。なお、以下の説明において、上下限残量設定部132により設定されたエネルギー残量の下限を「下限値」という。
【0056】
ステップS301では、ノード到達可否判定部139が、処理対象の到着ノードデータCの最大残量C5が下限値未満であるか否かを判定する。到着ノードが目的地ノードである場合には、上下限残量設定部132により別途設定された目的地の下限値を用いてエネルギー残量の判定を行う。目的地の下限値の設定と本判定処理によって、目的地到達時点でのエネルギー残量が下限値以上であることが保証される。これにより、目的地においてエネルギーの補給を行えない場合であっても、次回出発時(このとき目的地が新たな出発地となる)には少なくとも該下限値で到達可能な補給地まで走行することが可能となる。ステップS301においてノード到達可否判定部139により肯定判定がなされた場合には、ノード到達可否判定処理はステップS302へ進む。ステップS302では、ノード到達可否判定部139が処理対象の到着ノードデータCの到達可否フラグC8を「否」に設定し、ノード到達可否判定処理を終了する。他方、ステップS301において否定判定がなされた場合には、ノード到達可否判定処理はステップS303へ進む。
【0057】
ステップS303では、ノード到達可否判定部139が、処理対象の到着ノードデータCの最小残量C4が下限値未満であるか否かを判定する。ステップS303においてノード到達可否判定部139により肯定判定がなされた場合には、ノード到達可否判定処理はステップS304へ進む。ステップS304では、ノード到達可否判定部139が処理対象の到着ノードデータCの最小残量C4および確定補給地C6を更新し、ノード到達可否判定処理を終了する。具体的には、ノード到達可否判定部139が最小残量C4を最大残量C5と同じ値に設定すると共に、確定補給地C6を到着ノードIDC1と同じ値に設定する。他方、ステップS303において否定判定がなされた場合には、ノード到達可否判定処理を終了する。
【0058】
なお、ステップS302において到達可否フラグC8が「否」に設定された到着ノードデータCは、エネルギー残量の観点から到達することができないノードであるので、このノードに対してステップS105(図8)のループ処理をこれ以上実行する必要が無い。従って、経路探索部137は、到達可否フラグC8が「否」に設定された到着ノードデータCをDRAM103から消去すると共に、ステップS108の到達候補ノード登録判定処理を実行せずにステップS105のループ処理に戻る。
【0059】
(到達候補ノード登録判定処理の説明)
図13は、到達候補ノード登録判定処理のフローチャートである。この処理は候補ノード登録判定部140が、特定の到着ノードデータCに対して実行する。
【0060】
ステップS401では、候補ノード登録判定部140が、処理対象の到着ノードデータCの到達コストC3が確定ノードリストDLに格納されている当該ノードの最小コストD41未満か否かを判定する。この処理は、公知のダイクストラ法におけるノードの絞り込みと同一の処理である。すなわちこの処理は、到達コストが小さいノードのみを候補として絞り込むことにより、計算量を削減するための処理である。なお、公知のダイクストラ法では、最短の経路が確定したノード、すなわち確定ノードリストDLの確定情報D3に「N/A」以外の値が存在するノードに対してステップS401に相当する処理を行わない。しかしながら、本実施形態においては経路が確定したノードであっても、その先のノードにおいてエネルギー残量不足になる可能性があるため、ステップS401の処理を全ての処理対象ノードに対して実行する。ステップS401において候補ノード登録判定部140により肯定判定がなされた場合、到達候補ノード登録判定処理はステップS405に進む。他方、ステップS401において否定判定がなされた場合、到達候補ノード登録判定処理はステップS403へ進む。
【0061】
ステップS403では、候補ノード登録判定部140が、処理対象の到着ノードデータCの最大残量C5が確定ノードリストDLに格納されている当該ノードの最大残量D34以下であるか否かを判定する。なお、最大残量D34が「N/A」である場合には、最大残量D42を比較に用いる。ステップS403において肯定判定がなされた場合、到達候補ノード登録判定処理は終了する。これは、ステップS403において肯定判定がなされたということは、到達コストおよびエネルギー残量が共に既知の経路より劣るということなので、処理対象のノードに対してこれ以上の経路探索処理を行う必要がないためである。他方、ステップS403において否定判定がなされた場合には、到達候補ノード登録判定処理はステップS405へ進む。
【0062】
ステップS405では、候補ノード登録判定部140が処理対象の到着ノードデータCを候補ノードヒープ181へ追加する。ステップS406では、候補ノード登録判定部140が、処理対象のノードの確定ノードリストDLにおける未確定情報D4を更新する。具体的には、候補ノード登録判定部140は、最小コストD41が到着ノードデータCの到達コストC3より大きければ、最小コストD41を到着ノードデータCの到達コストC3で置き換える。同様に、最大残量D42が到着ノードデータCの最大残量C5より小さければ、最大残量D42を到着ノードデータCの最大残量C5で置き換える。
【0063】
以上の処理により候補ノードヒープ181には、特定のノードについて、到達コストC3が最小である到着ノードデータCと、最大残量C5が最大である到着ノードデータCと、が登録されることとなる。すなわち、候補ノードヒープ181には到達コストとエネルギー残量のどちらかで優位になるノードのみが残り、無駄な経路探索が行われない。通常は到達コストが大きいほどエネルギー消費量は大きくなる。従って、到達コストが大きく且つエネルギー残量が大きいケースは、補給を行ったケースや特殊な地形を走行したケースに限られる。このようなケースは確率的に少なく、候補ノードヒープ181に含まれるノードの数は比較的小規模に抑えられる。
【0064】
次に、図10のステップS1022の説明で述べた、候補ノードヒープ181が空であることが「目的地到達経路なし」となる理由について説明する。上記で説明した通り、候補ノードヒープ181には到達コストC3が最少、または最大残量C5が最大である到達ノードデータCが登録されている。到達コストC3が最少である到達ノードデータCは、ステップS102の処理によって逐次取り出されていく。そして、最大残量C5が最大である到達ノードデータCが候補ノードヒープ181に登録されない状態、すなわち適切な補給地が存在しない状態になると、候補ノードヒープ181内のノード数が、目的地を発見する前に0になることがある。このような状態は、ステップS107(図10)のノード到達可否判定処理がエネルギー残量の不足のため新しいノードを供給しなくなること、または、最大残量C5を越えるノードが存在しないため、ステップS108の到達候補ノード登録判定処理が新しいノードを登録しなくなることにより発生する。すなわち、このような状態は、目的地に下限値以上のエネルギー残量で到達できないことを意味している。なお、目的地未到達の場合、候補ノードヒープ181が空になるまで経路探索処理が実行され続けることになるが、前述した理由により候補ノードヒープ181の大きさは抑えられることになるので、計算量の爆発的増大は避けられる。
【0065】
(経由地自動追加処理の説明)
図14は、推奨経路のデータ構造を示す図である。図14に示すように、経路探索部137が出力する推奨経路は、複数の到着ノードデータC(図8)が連なったデータ列Rである。図14に示すデータ列Rは、出発地から目的地の順に、n個の到着ノードデータCが並んでいる。経由地自動追加部134は、データ列Rに含まれる到着ノードデータCについて、先頭から順に確定補給地ノードIDの変化を検索する。経由地自動追加部134は、確定補給地ノードIDが変化しているノードを発見すると、この確定補給地ノードIDをネットワーク地図DB122から検索する。そして、対応する補給地IDL5(図6)を取得し、更にこの補給地IDL5を補給地DB123(図7)から検索する。経由地自動追加部134はこのようにして取得した補給地情報Sに基づき、補給地名称やその他表示に必要な情報を含む経由地のデータを推奨経路に追加する。経路表示部136はこれらのデータに基づいて、図5に示したような経由地の表示を行う。ユーザはこれらの経由地において補給を行い推奨経路上の他の補給地で補給を行わないことにより、補給回数を最少にすることができる。すなわち、経路探索部137は、確定補給地ノードIDという形で、補給を行う最適なタイミングを演算している。そして経路表示部136は上記のような表示を行うことにより、ユーザへ補給を行う最適なタイミングを報知している。
【0066】
上述した第1の実施の形態によるナビゲーション装置によれば、次の作用効果が得られる。
(1)経路探索部137は、ノード残量算出部138に各ノードにおけるエネルギー残量を更新させながら、エネルギー残量が上下限残量設定部132により設定された下限値を下回らない経路のうち最少の到達コストを有する推奨経路を探索する。これにより、エネルギー残量を考慮した経路探索を計算量を抑えつつ行うことができる。
【0067】
(2)経路探索部137は、推奨経路の探索時に、最少残量および確定補給地ノードIDという形で、補給回数が最も少なくなる補給タイミングを演算する。これにより、経路表示部136は、ユーザへ適切なタイミングで補給を促すことが可能となる。
【0068】
(3)上下限残量設定部132は、補給地における補給によりエネルギー残量が増加する上限値を設定する。蓄電池は充電に要する時間がバッテリー残量により大きく変動するので、これによりエネルギーの補給に要する時間を抑制することができる。
【0069】
(4)目的地到達可否判定部135は、エネルギー残量が上下限残量設定部132により設定された下限値を下回らずに目的地へ到達可能か否かを判定する。これにより、目的地の周辺に補給地が存在しない場合など、目的地に到達不可能であることをユーザへ報知することができる。
【0070】
(第2の実施の形態)
第2の実施の形態に係るナビゲーション装置は、第1の実施の形態に係るナビゲーション装置に加えて、最適な補給地の選択を行う。なお、図1および図2に示す第1の実施の形態と同一の回路および装置には同一の符号を付し、説明を省略する。
【0071】
本実施形態の経由地自動追加部134は、補給を行うべき補給地を、図14を用いて説明した手順とは異なる手順により経由地として追加する。以下、推奨経路上に1からNまでの番号が割り振られたN個の補給地ノードが存在する場合の、経由地自動追加部134による経由地自動追加処理について説明する。
【0072】
蓄電池への充電には残量に応じた時間が必要とされる。そこで、この充電に必要な時間を推定するための関数T(ri)を定義する。ここでriは、i番目の補給地まで走行した場合のエネルギー残量である。一般に、エネルギー残量が少ないほど充電に要する時間は長くなるので、関数T(ri)は、riが小さいほどその値が大きくなるよう定義される。このとき、経由地自動追加部134は、「T(r0)+T(r1)+…+T(rN)+走行の所要時間」が最小となる補給地の組み合わせを探索する。この探索は、例えば線形計画法により行うことが可能である。経由地自動追加部134は、この探索により得られた補給地を、経由地として推奨経路へ追加する。
【0073】
上述した第2の実施の形態によるナビゲーション装置によれば、第1の実施の形態によるナビゲーション装置で得られる作用効果に加えて、次の作用効果が得られる。
(1)経由地自動追加部134は、補給を行うべき補給地を、エネルギー残量に応じた充電時間を考慮して探索する。これにより、充電時間も含めた最短経路を探索することが可能となる。
【0074】
次のような変形も本発明の範囲内であり、変形例の一つ、もしくは複数を上述の実施形態と組み合わせることも可能である。
【0075】
(変形例1)
第1の実施の形態のように、単独で動作するナビゲーション装置だけではなく、経路探索機能を備えたサーバと、そのサーバに接続するクライアントと、から成るナビゲーションシステムへ本発明を適用してもよい。例えば、ナビゲーション装置が図1に示す電池残量センサ107,液晶モニタ109,タッチパネル110,現在地検出装置111、ならびに、図2に示す表示用地図DB124、探索条件設定部131、上下限残量設定部132、目的地設定部133,経路表示部136の各部に加えて、携帯電話網や無線LANなどによりサーバと双方向通信を行う通信装置を備えるように構成する。他方、サーバはナビゲーション装置から現在地、目的地、エネルギー残量、各種の経路探索条件を受信する通信装置と、図2に示すネットワーク地図DB122、補給地DB123、経路探索部137を備えるように構成する。そしてサーバは、経路探索部137が出力した推奨経路を、通信装置を介してナビゲーション装置へ送信する。ナビゲーション装置は通信装置を介して受信した推奨経路を経路表示部136により液晶モニタ109へ表示すればよい。
【0076】
(変形例2)
上述の実施形態ではダイクストラ法に対してエネルギー残量を考慮する各種処理を加えたが、ダイクストラ法以外の経路探索手法に対しても本発明を適用することが可能である。例えば、いわゆるA*探索アルゴリズムについても、上述の実施形態と同様に本発明を適用することができる。
【0077】
(変形例3)
上述の実施形態では、自車両200は電気自動車であり、補給地は充電ステーションであるとしたが、自車両200の駆動エネルギーの形態はこれに限定されない。例えば、ガソリン車とガソリン、水素自動車と水素燃料などであってもよい。
【0078】
(変形例4)
第1の実施の形態において、補給地DB123に格納されているデータのうち、補給燃料の種類S4(図7)は「充電」のみとしたが、補給地DB123は異なる様々な種類の燃料を補給する補給地のデータを含んでいてよい。この場合、経路探索部137は自車両200に関係のない補給地のデータを単純に無視する。例えば、自車両200が電気自動車であれば、経路探索部137は補給燃料の種類S4が「ガソリン」や「水素」であるような補給地を無視する。また、1つの補給地が2種類以上の燃料を供給可能であることを表すため、補給燃料の種類S4へ2種類以上のデータを格納できるよう補給地DB123を構成してもよい。
【0079】
(変形例5)
上下限残量設定部132は、目的地におけるエネルギー残量の下限の設定を行わなくてもよい。すなわち、上下限残量設定画面141(図3)から、目的地におけるエネルギー残量の下限144を削除してもよい。この場合、エネルギー残量の下限142を、目的地におけるエネルギー残量の下限としても用いる。同様に、上下限残量設定部132が、エネルギー残量の上限の設定を行わないようにしてもよい。この場合、経路探索部137は、エネルギー残量の上限を100%として経路探索処理を行う。
【0080】
(変形例6)
上下限残量設定部132は、目的地から目的地に最寄りの補給地までの経路を走行するために必要なエネルギー量を、目的地におけるエネルギー残量の下限として自動的に設定するようにしてもよい。
【0081】
本発明の特徴を損なわない限り、本発明は上記実施の形態に限定されるものではなく、本発明の技術的思想の範囲内で考えられるその他の形態についても、本発明の範囲内に含まれる。
【符号の説明】
【0082】
100…ナビゲーション装置、101…制御回路、103…DRAM、104…不揮発性メモリ、105…ディスクドライブ、106…DVD−ROM、107…電池残量センサ、108…交通情報受信機、109…液晶モニタ、110…タッチパネル、111…現在地検出装置、121…POIDB、122…ネットワーク地図DB、123…補給地DB、124…表示用地図DB、131…探索条件設定部、132…上下限残量設定部、133…目的地設定部、134…経由地自動追加部、135…目的地到達可否判定部、136…経路表示部、137…経路探索部、138…ノード残量算出部、139…ノード到達可否判定部、140…候補ノード登録判定部、200…自車両
【技術分野】
【0001】
本発明は、ナビゲーション装置および経路演算方法に関する。
【背景技術】
【0002】
車載用ナビゲーション装置において、車両のエネルギー残量を考慮して経路の変更及び表示を行う技術が知られている。車両のエネルギー残量とは、例えば内燃機関を利用する自動車であればガソリンなどの燃料の残量を、電気自動車であれば蓄電池の残容量を、水素自動車であれば水素燃料自体の残量もしくは水素に変換するための液体の残量を指す。また、「エネルギー残量を考慮する」とは、走行中にエネルギー不足になることのないよう、エネルギーの補給地における補給を考慮するということである。例えば特許文献1の経路探索装置は、出発地から最初の充電ステーションまでの距離が航続距離以下で、且つ最初の充電ステーションから目的地までの各充電ステーション区間の距離が満充電の航続距離以下の経路を探索する。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開平10−170293号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
特許文献1の経路探索装置は、エネルギー補給地を含む経路の組み合わせを全て選択し、その中から目的地へ到達可能な経路を探索する。従って、探索すべき経路の組み合わせが膨大となり、莫大な計算量が必要となってしまうという問題があった。
【課題を解決するための手段】
【0005】
請求項1に係る発明は、現在地を検出する現在地検出手段と、自車両の駆動エネルギーの残量を検出するエネルギー残量検出手段と、自車両への駆動エネルギーの補給地の位置情報を含む地図情報が記憶された記憶手段と、地図情報に基づいて、地図情報に含まれる任意のリンクを走行する際の駆動エネルギーの消費量を算出するエネルギー消費量算出手段と、現在地から目的地に至る経路を演算する経路演算手段と、経路演算手段による演算の結果に基づいて、自車両の経路誘導を行う経路誘導手段とを備え、経路演算手段は、地図情報と、エネルギー残量検出手段により検出された出発時の残量と、エネルギー消費量算出手段により算出された消費量とに基づいて、残量が所定のしきい値を下回らない経路のうち最少のコストを有する推奨経路を演算することを特徴とするナビゲーション装置である。
請求項7に係る発明は、出発時における自車両の駆動エネルギーの残量を設定するエネルギー残量設定工程と、自車両への駆動エネルギーの補給地の位置情報を含む地図情報に基づいて、地図情報に含まれる任意のリンクを走行する際の駆動エネルギーの消費量を算出するエネルギー消費量算出工程と、現在地から目的地に至る経路を演算する経路演算工程とを備え、経路演算工程では、地図情報と、エネルギー残量設定工程により設定された出発時の残量と、エネルギー消費量算出工程により算出された消費量とに基づいて、残量が所定のしきい値を下回らない経路のうち最少のコストを有する推奨経路を演算することを特徴とする経路演算方法である。
【発明の効果】
【0006】
本発明によれば、エネルギー残量を考慮した経路探索を計算量を抑えつつ行うことができる。
【図面の簡単な説明】
【0007】
【図1】本発明の第1の実施の形態であるナビゲーション装置の構成を示すブロック図である。
【図2】制御回路101およびDVD−ROM106の詳細を表すブロック図である。
【図3】上下限残量設定部132への入力画面を示す図である。
【図4】経路表示部136による経路表示画面の例を示す図である。
【図5】経路誘導画面の例を示す図である。
【図6】ネットワーク地図DB122のデータ構造を示す図である。
【図7】補給地DB123のデータ構造を示す図である。
【図8】候補ノードヒープのデータ構造を示す図である。
【図9】確定ノードリストのデータ構造を示す図である。
【図10】経路探索処理のフローチャートである。
【図11】ノードエネルギー残量算出処理のフローチャートである。
【図12】ノード到達可否判定処理のフローチャートである。
【図13】到達候補ノード登録判定処理のフローチャートである。
【図14】推奨経路のデータ構造を示す図である。
【発明を実施するための形態】
【0008】
(第1の実施の形態)
図1は、本発明の第1の実施の形態であるナビゲーション装置の構成を示すブロック図である。ナビゲーション装置100は自車両200に搭載され、自車両200のエネルギー残量を考慮した経路探索および経路誘導を行う。ここで自車両200は、蓄電池に充電された電気エネルギーにより駆動される、いわゆる電気自動車である。従って、第1の実施の形態において、自車両200のエネルギー残量とはすなわち自車両200の蓄電池の残量のことである。
【0009】
(ナビゲーション装置の説明)
ナビゲーション装置100は、制御回路101、DRAM103、不揮発性メモリ104、ディスクドライブ105、電池残量センサ107、交通情報受信機108、液晶モニタ109、タッチパネル110、および現在地検出装置111を有する。ディスクドライブ105には、DVD−ROM106が装填されている。
【0010】
制御回路101は、マイクロプロセッサ及びその周辺回路から構成される。DRAM103は揮発性の記憶装置である。不揮発性メモリ104は、例えばフラッシュメモリ等の不揮発性の記憶媒体であり、所定の制御プログラムが格納されている。制御回路101は、DRAM103を作業領域として不揮発性メモリ104に格納された制御プログラムを実行し、各種の制御を行う。ディスクドライブ105は、DVD−ROM106からデータの読み取りを行う装置である。
【0011】
電池残量センサ107は自車両200に接続されたセンサである。電池残量センサ107は、自車両が有する蓄電池の残量を検知し、制御回路101へ通知する。交通情報受信機108は、例えばVICS(Vehicle Information and Communication System)(登録商標)などにより提供される交通情報を受信し、制御回路101へ出力する。ここで交通情報とは、道路の渋滞情報や事故情報などである。
【0012】
液晶モニタ109は、制御回路101が出力する画像データに基づき、各種情報を画面表示として自車両200の搭乗者へ提示する。タッチパネル110は、液晶モニタ109の表面に積層される透明のタッチスイッチである。液晶モニタ109に表示される画像はタッチパネル110を介して表示される。搭乗者が液晶モニタ109の表示画面を押圧すると、タッチパネル110が押圧される。このとき、タッチパネル110から制御回路101へ押圧した位置の情報を含む操作信号が出力される。そして、制御回路101が液晶モニタ109へ表示されている地図上の押圧した位置へ目的地を設定したり、押圧した位置に表示されている各種ボタンや表示メニューに定義された処理を実行したりする。
【0013】
現在地検出装置111は自車両200の現在地を検出する装置である。現在地検出装置111はGPS(Global Positioning System)受信機111a、ジャイロスコープ111b、車速センサ111c等の各種センサを有する。GPS受信機111aはGPS衛星から送出される信号を受信し、自車両200の絶対位置を検出する。ジャイロスコープ111bは車両の進行方向を検出する。車速センサ111cは自車両200が出力する車速パルス信号を受信し、自車両200の車速を検出する。現在地検出装置111はこれらのセンサが検出した各種の情報を演算し、自車両200の現在地を検出する。
【0014】
ナビゲーション装置100は、ユーザから経路誘導の目的地を受け付けると、現在地検出装置111により検出された現在地を出発地として、目的地までの経路演算を後に詳述するアルゴリズムに基づいて行う。ナビゲーション装置100は、液晶モニタ109の表示画面へ地図を表示すると共に、この経路演算により求められた経路(以下、推奨経路という)を地図上へ表示する。ナビゲーション装置100は、ユーザに対して画面や音声などによる進行方向指示を行い、推奨経路に従って自車両200が走行できるように、自車両200を経路誘導する。
【0015】
図2は、制御回路101およびDVD−ROM106の詳細を表すブロック図である。DVD−ROM106には、POIDB(Point Of Interestデータベース)121と、ネットワーク地図DB122と、補給地DB123と、表示用地図DB124と、が格納されている。POIDB121は、ランドマークや観光スポットなど経路探索の目的地を設定するためのデータを、ジャンル検索や名称検索など様々な検索が可能な形式で整理したデータベースである。ネットワーク地図DB122は、経路探索を行う際に用いられるネットワーク地図が格納されたデータベースである。ネットワーク地図DB122に格納されたネットワーク地図は、公知のネットワーク地図と同様に、道路網を交差点などのノードとノード間のリンクとの組み合わせにより表現している。
【0016】
補給値DB123は、車両へエネルギーの補給を行う施設の情報を含むデータベースである。以下の説明では、このような施設のことを補給地と呼ぶ。本実施形態では、電気自動車である自車両200へ充電を行う充電ステーションが補給地である。表示用地図DB124は、例えば道路、鉄道、地形、施設形状、地名等、液晶モニタ109の表示画面へ地図を表示するためのデータが格納されたデータベースである。表示用地図DB124に格納されたデータのうち道路データは、リンクやノードに対して、ネットワーク地図DB122の道路データと共通のIDが利用されている。これにより、ネットワーク地図DB122と表示用地図DB124とは、道路データの相互参照が可能である。制御回路101は、例えば経路探索の結果を画面に表示する場合などに、道路データの相互参照を行う。
【0017】
制御回路101は、探索条件設定部131、上下限残量設定部132、目的地設定部133、経由地自動追加部134、目的地到達可否判定部135、経路表示部136、および経路探索部137を備える。経路探索部137は更に、ノード残量算出部138、ノード到達可否判定部139、および候補ノード登録判定部140を備える。これらの各機能部は、制御回路101が不揮発性メモリ104に格納された制御プログラムを実行することにより、ソフトウェア的に実現される。
【0018】
探索条件設定部131は、ユーザからのタッチパネル110による入力に基づき、経路探索の条件を設定する。経路探索の条件には、例えば距離優先、時間優先、金銭コスト優先、エネルギー消費量優先などの条件を設定することが可能である。経路探索部137は、探索条件設定部131により設定された経路探索の条件に基づいて経路探索を行う。
【0019】
上下限残量設定部132は、ユーザからのタッチパネル110による入力に基づき、経路探索におけるエネルギー残量の上限および下限を設定する。上下限残量設定部132は更に、目的地へ到着した時点におけるエネルギー残量の下限を設定する。経路探索部137は、上下限残量設定部132により設定されたエネルギー残量の範囲内で経路探索を行う。例えば、上下限残量設定部132がエネルギー残量の下限を20%に設定した場合、経路探索部137は走行中のエネルギー残量が常に20%を上回る推奨経路を探索する。
【0020】
目的地設定部133は、ユーザからのタッチパネル110による入力に基づき、経路探索の目的地を設定する。目的地設定部133は、POIDB121を利用して、ジャンル検索、名称検索、地図表示からの選択など、ナビゲーション装置において広く用いられている目的地の入力方法をユーザへ提供する。
【0021】
経由地自動追加部134は、推奨経路に含まれる補給地ノード群に基づいて、推奨経路へ経由地を追加する。目的地到達可否判定部135は、経路探索部137の出力に基づいて、目的地への到達可否を判定する。
【0022】
経路表示部136は、液晶モニタ109の表示画面へ地図を表示すると共に、経路探索部137が出力した経路を地図上へ表示する。経路表示部136は推奨経路を他の道路などとは異なる表示形態(例えば表示色など)で表示する。これにより、ユーザは地図上の推奨経路を他の道路などと画面上で区別することができる。また経路表示部136は、推奨経路に経由地が含まれる場合、他のノードとは異なる表示形態で経由地を表示する。
【0023】
経路探索部137は、現在地検出装置111が検出した現在地を出発地として、目的地設定部133が設定した目的地までの経路探索を行う。経路探索部137はこの経路探索を、電池残量センサ107が検知した蓄電池の残量と、交通情報受信機108が出力した交通情報と、DVD−ROM106に格納されているネットワーク地図DB122と、探索条件設定部131が設定した経路探索の条件と、に基づいて行う。経路探索部137は経路探索に成功した場合、推奨経路を出力する。他方、経路探索に失敗した場合、経路探索部137は目的地に向かう途中までの経路を出力する。
【0024】
ノード残量算出部138は、経路探索処理の際、補給地の通過有無を考慮して各ノードにおける自車両200のエネルギー残量を算出する。ノード到達可否判定部139は、各ノードについて、上下限残量設定部132により設定されたエネルギー残量の下限を上回るエネルギー残量で到達可能か否かを判定する。候補ノード登録判定部140は、各ノードについて経路探索処理を継続する必要があるか否かを判定する。
【0025】
(上下限残量設定の説明)
図3は、上下限残量設定部132への入力画面を示す図である。ユーザは経路探索に先立って、タッチパネル110によりエネルギー上下限残量設定画面141を呼び出すことが可能である。ユーザはタッチパネル110によりエネルギー残量の下限142、上限143、および目的地でのエネルギー残量の下限144を入力できる。上下限残量設定部132はこれらの入力に基づいて、経路探索におけるエネルギー残量の上限および下限を設定する。
【0026】
(経路表示の説明)
図4は、経路表示部136による経路表示画面の例を示す図である。図4(a)には、経路表示部136が表示する地図上での経路表示画面151を示す。画面151には、現在地152、目的地153、ボタン154、経路探索部137が出力した推奨経路155、経路探索部137が公知の経路探索手法により補給地を考慮せずに出力した経路156、推奨経路155上の補給地157、158、および経路156上の補給地159が表示されている。経路表示部136は画面151を表示用地図DB124に基づいて描画する。画面151において、補給地157、158、159は1〜3の数字により表現されているが、この数字の代わりに補給地の名称を用いてもよい。ユーザがタッチパネル110によりボタン154を押下すると、経路表示部136が液晶モニタ109の表示画面を画面151から図4(b)に示す詳細表示画面161に切り替える。
【0027】
図4(b)に示す詳細表示画面161は、上述した2つの経路155、156を共通の時間軸を基準として、経由地も含め比較表示した画面である。画面161上の領域162には、各々の経路を走行した場合のエネルギー残量の変化が矢印および数値で表示されている。矢印163、164は経路を表す矢印であり、特に破線で描画された矢印164は、走行中にエネルギーが不足する経路を示している。矢印の下側には、各々の時刻におけるエネルギー残量の変化が数値で表示されている。ユーザがタッチパネル110によりボタン165を押下すると、経路表示部136が液晶モニタ109の表示画面を画面161から図4(a)に示す経路表示画面151に切り替える。なお、図4(b)において、領域162の横方向は経過時間を表しているが、走行距離を表すようにしてもよい。
【0028】
なお、経路探索の後、目的地到達可否判定部135が目的地に到達できる経路を探索できなかったと判定した場合には、経路表示部136が液晶モニタ109へ、探索可能経路が発見できない旨の表示を行ってもよい。またこの場合、経路表示部136は経路探索部137が出力した途中までの経路を表示する。
【0029】
(経路誘導画面の説明)
図5は、経路誘導画面の例を示す図である。経路表示部136は、ナビゲーション装置100による経路誘導が行われているとき、経路誘導画面171を液晶モニタ109へ表示する。この経路誘導画面171では、経由地自動追加部134により推奨経路へ追加された経由地のユーザへの報知が行われる。具体的には、経路表示部136は、画面171上に表示される、自車両172の進行方向を表す矢印173に、経由地を表すマーク174を重ねて表示する。また経路表示部136は、経由地においてエネルギーの補給が必要であることを、吹き出し175によりユーザへ報知すると共に、エネルギー残量の変化量を表す数値を吹き出し175の下部に表示する。
【0030】
(データベースの説明)
図6は、ネットワーク地図DB122のデータ構造を示す図である。ネットワーク地図DB122には、ノード情報Nが複数格納されている。個々のノード情報Nは、公知のネットワーク地図と同様に、始点ノードIDN1と、接続ノード数N2と、1つ以上の接続ノード情報Lと、から構成される。また個々の接続ノード情報Lは、公知のネットワーク地図と同様に、接続ノードIDL1と、リンク長L2と、所要時間L3と、を含む。
【0031】
本実施形態では、接続ノード情報Lがこれらのデータに加えて、補給地フラグL4と、補給地IDL5と、を含む。補給地フラグL4は、当該ノードが補給地か否かを表すフラグである。すなわち、補給地フラグL4が1であれば、当該ノードの位置に充電ステーションが存在する。補給地IDL5は、補給地を特定する為のIDである。制御回路101は、補給地IDL5を用いることにより、補給地DB123の参照を高速に行うことができる。接続ノード情報Lの補給地フラグL4が0である場合、この接続ノード情報Lは補給地IDL5を含まない。
【0032】
図7は、補給地DB123のデータ構造を示す図である。補給地DB123には、補給地情報Sが複数格納されている。個々の補給地情報Sは、補給地IDS1と、補給地名称S2と、補給地のジャンルS3と、補給燃料の種類S4と、対応ノードIDS5と、正規化座標S6と、から構成される。補給地IDS1は、個々の補給地に一意に割り当てられたIDである。前述したネットワーク地図DB122に含まれる補給地IDL5には、この補給地IDS1が格納されている。
【0033】
補給地名称S2は補給地の名称を表す。補給地のジャンルS3は、各々の補給地を分類するためのジャンル名である。補給燃料の種類S4は、この補給地で補給可能なエネルギーの種類である。本実施形態では、補給燃料の種類S4は「充電」である。対応ノードIDS5は、ネットワーク地図DB122に格納されているノード情報Nを参照するための始点ノードIDである。制御回路101は、この対応ノードIDS5を用いることにより、ネットワーク地図DB122の参照を高速に行うことができる。正規化座標S6は、補給地の位置を表す座標である。
【0034】
(経路探索処理で扱うデータ構造の説明)
経路探索部137は、経路探索処理において、「候補ノードヒープ」と「確定ノードリスト」という2つのデータ集合を扱う。これらのデータ集合はいずれも、公知のダイクストラ法において用いられるデータ構造にいくつかのデータ項目を追加したものとなっている。
【0035】
図8は、候補ノードヒープのデータ構造を示す図である。図8(a)に示すように、候補ノードヒープ181は、1つ乃至複数の到着ノードデータCにより公知のヒープ構造を成す。ヒープ構造とは木構造の一種であり、親要素がどの子要素よりも小さな評価値を有するように構成される。木に対して要素の追加や削除などの操作を行った場合でも、上記の条件は常に満たされる。図8(a)では、個々のノードの評価値を、ノードを表す円の中に描画している。
【0036】
図8(b)は、候補ノードヒープ181を構成する個々の到着ノードデータCのデータ構造を示図である。1つの到着ノードデータCは1つのノードに対応しており、経路探索処理中にあるノードへ特定の経路で到達した場合の、そのノードにおける各種情報を表している。到着ノードデータCは、到着ノードIDC1と、前回ノードIDC2と、ヒープの評価値として扱われる到達コストC3と、最小残量C4と、最大残量C5と、確定補給地ノードIDC6と、直前補給地ノードIDC7と、到達可否フラグC8と、から構成される。到着ノードIDC1、前回ノードIDC2、確定補給地ノードIDC6、および直前補給地ノードIDC7は、ノードIDに付随する通番を備えている。
【0037】
到着ノードIDC1は、到達したノードのノードIDである。前回ノードIDC2は、このノードへ到達した経路において、直前に通過したノードのノードIDである。到達コストC3は、このノードへ到達するために要したコストの総計である。最小残量C4は、可能な限り補給を行わずにこのノードへ到達した場合のエネルギー残量を、確定補給地ノードIDC6は同様の場合において直前に補給を行った補給地のノードIDを表す。最大残量C5は、可能な限り頻繁に補給を行いつつこのノードへ到達した場合のエネルギー残量を、直前補給地ノードIDC7は同様の場合において直前に補給を行った補給地のノードIDを表す。到達可否フラグC8は、到達したノードに対し、エネルギー残量が上下限残量設定部132により設定された下限を下回らずに到達可能か否かを表すフラグである。
【0038】
以上のように、到着ノードデータCには、通常のダイクストラ法では用いられない最小残量C4、最大残量C5、確定補給地ノードIDC6、直前補給地ノードIDC7、および到達可否フラグC8というデータが存在する。
【0039】
図9は、確定ノードリストのデータ構造を示す図である。確定ノードリストDLを構成する1つのレコードは1つのノードに関する情報を表し、通番D1、ノードIDD2、確定情報D3、および未確定情報D4から成る。確定情報D3は、到達コストD31、前回IDD32、最小残量D33、および最大残量D34から構成される。未確定情報D4は、最小コストD41および最大残量D42から構成される。
【0040】
通番D1は、各ノードに対して1から順に割り当てられた通し番号である。この通番は、1回の経路探索処理を通して、ノードIDと1対1に対応する。経路探索部137を含む各部は、ノードIDの代わりにこの通番を用いることにより、各レコードへ高速にアクセスすることができる。ノードIDD2は、このレコードが表すノードに割り当てられた一意な識別子であり、ノード情報N(図6)における始点ノードIDN1に対応する。確定情報D3は、このレコードが表すノードへのコストが最小となる経路が確定したときの、到着ノードデータC(図8)における到達コストC3、前回ノードIDC2、最小残量C4、および最大残量C5である。未確定情報D4は、このレコードが表すノードへのコストが最小となる経路が確定していないときに用いる暫定的なデータである。未確定情報D4の最小コストD41は到着ノードデータC(図8)における到達コストC3に対応し、同様に最大残量D42は到着ノードデータC(図8)における最大残量C5に対応する。
【0041】
(経路探索処理の説明)
図10は、経路探索処理のフローチャートである。本実施形態における経路探索処理は、公知の経路探索処理において利用されるダイクストラ法のアルゴリズムをベースに、エネルギー残量を考慮した各種の処理を追加したものである。
【0042】
ステップS100では、経路探索部137が初期化処理を行う。具体的には、経路探索部137は候補ノードヒープ181を空の状態にすると共に、ネットワーク地図DB122から経路探索処理の対象とする領域内の全ノード情報を読み出す。この領域は、例えば出発地および目的地とその周辺とを含む矩形領域とし、矩形の一辺は、例えば出発地と目的地との間の距離のおよそ1.5倍〜2倍と設定し、経路探索に不要と思われる領域を排除する。経路探索部137は、このようにして読み出した複数のノード情報に基づいて、DRAM103へ図9に示した確定ノードリストDLを作成する。経路探索部137は確定ノードリストDLの各々のレコードのノードIDD2へ、読み出したノード情報に含まれるノードIDを格納し、通番D1へ1から始まる通し番号を割り当てる。経路探索部137は、確定ノードリストDLの通番D1とノードIDD2以外のフィールドには、データが存在しないことを表す「N/A」を書き込む。
【0043】
ステップS1021では、経路探索部137が、候補ノードヒープ181の構成ノードが空であるか否かを判定する。ステップS1021において、経路探索部137により空であることが肯定された場合にはステップS1022へ進み、「目的地到達経路なし」との結果を返す処理を行い経路探索処理を終了する。こうして経路探索部137によって、目的地到達可否が判定される。候補ノードヒープ181が空であることが「目的地到達経路なし」となる理由については、ステップS108の処理後の候補ノードヒープ181の状態によるため、図13の説明によって後述する。
【0044】
ステップS101では、経路探索部137が出発地ノードの到着ノードデータCを作成し、候補ノードヒープ181へ登録する。これにより、候補ノードヒープ181は、出発地ノードのみを含む状態になる。出発地ノードの到着ノードデータCは、到着ノードIDC1には出発地ノードのノードID、到達コストC3には0、最小残量C4および最大残量C5には電池残量センサ107により検知された出発時のエネルギー残量、到達か非フラグC8には「可」、がそれぞれ設定され、それ以外の項目にはデータが存在しないことを表す「N/A」が設定される。
【0045】
ステップS102では、経路探索部137が候補ノードヒープ181から最小の到達コストC3を有する到着ノードデータCを取り出し、この到着ノードデータCの情報を確定ノードリストDLの確定情報D3へ格納する。具体的には、経路探索部137は到達コストD31へ到達コストC3を、前回IDD32へ前回ノードIDC2を、最小残量D33へ最小残量C4を、最大残量D34へ最大残量C5をそれぞれ格納する。候補ノードヒープ181は、根ノードが最小の到達コストC3を有するよう構成されるので、経路探索部137は候補ノードヒープ181から根ノードを取り出せばよい。
【0046】
ステップS103では、経路探索部137はステップS102において取り出された到着ノードデータCが目的地ノードに対応するか否かを判定する。取り出された到着ノードデータCが目的地ノードに対応する到着ノードデータCではなかった場合、経路探索部137により否定判定がなされ、ステップS104へ進む。
【0047】
ステップS104では、経路探索部137が、ステップS102において取り出された到着ノードデータCのノードに接続する全てのノードを、ステップS100において読み出されたノード情報に基づいて取り出す。経路探索部137は、このようにして取り出された各々のノードについて、対応する到着ノードデータCを作成してDRAM103へ格納する。このとき、到着ノードIDC1には取り出されたノードのノードIDが、前回ノードIDC2にはステップS102において取り出された到着ノードデータCの到着ノードIDC1が、確定補給地ノードIDC6および直前補給地ノードIDC7にはステップS102において取り出された到着ノードデータCと同一の内容が、到達可否フラグC8には「可」がそれぞれ設定され、それ以外の項目にはデータが存在しないことを表す「N/A」が設定される。
【0048】
ステップS105では、経路探索部137が、ステップS104において作成された各々の到着ノードデータCに対して、ステップS106〜ステップS108の処理を実行する。ステップS106では、ノード残量算出部138が、各々の到着ノードデータCに対してノードエネルギー残量算出処理を実行する。ステップS107では、ノード到達可否判定部139が、各々の到着ノードデータCに対してノード到達可否判定処理を実行する。ステップS108では、候補ノード登録判定部140が、各々の到着ノードデータCに対して到達候補ノード登録判定処理を実行する。ノードエネルギー残量算出処理、ノード到達可否判定処理、および到達候補ノード登録判定処理については後に詳述する。ステップS106〜ステップS108の処理の実行が完了したら、経路探索処理はステップS102へ戻る。
【0049】
他方、ステップS103において経路探索部137により肯定判定がなされた場合には、経路探索処理はステップS109へ進む。ステップS109では、経路探索部137が確定ノードリストDLを用いて出発地ノードから目的地ノードへと至る到着ノードデータCのデータ列、すなわち推奨経路を出力する。具体的には、経路探索部137はまず目的地ノードのノードIDD2を取り出した後、目的地ノードの前回IDD32を取り出す。経路探索部137はその後、この前回IDD32に対応するノードIDD2を確定ノードリストDLから探索し、同様に前回IDD32を取り出す。経路探索部137は目的地ノードに到達するまでこの処理を繰り返し、取り出されたノードID列を逆順にする。最終的に経路探索部137は、この取り出されたノードID列に基づいて、到着ノードデータCの列を作成して出力する。以上の処理により、経路探索部137は推奨経路を出力する。
【0050】
なお、以上で説明した経路探索処理では、上下限残量設定部132により設定される、目的地に到着した時点におけるエネルギー残量の下限に関する処理を省略している。この下限を考慮する場合は、ノード到達可否判定処理(ステップS107)内において、目的地ノードに対し、上下限残量設定部132により設定された下限値を用いた判定を行う。詳細は、図12の説明において後述する。
【0051】
(ノードエネルギー残量算出処理の説明)
図11は、ノードエネルギー残量算出処理のフローチャートである。この処理はノード残量算出部138が、特定の到着ノードデータCに対して実行する。この処理の対象となる到着ノードデータCは、到着ノードIDC1、前回ノードIDC2、確定補給地ノードIDC6、直前補給地ノードIDC7、および到達可否フラグC8を除く全ての項目に「N/A」が設定されている。
【0052】
ステップS201では、ノード残量算出部138が、処理対象のノードのノード情報Nに基づいて、エネルギー消費量およびリンクコストを計算する。エネルギー消費量は、予め与えられた単位距離当たりのエネルギー消費量やリンク長L1(図6)などを用いて、公知の手法により計算することが可能である。リンクコストは探索条件設定部131により設定された探索条件に基づくコストであり、例えば距離優先であればリンク長L1(図6)を、時間優先であれば時間L3(図6)および交通情報受信機108により出力された交通情報を用いて、公知の手法によりそれぞれ計算される。また、探索条件がエネルギー消費量優先であれば上記のエネルギー消費量、金銭コスト優先であれば有料道路料金やエネルギー費用などにより、同様にノード残量算出部138がリンクコストを計算する。
【0053】
ステップS202では、ノード残量算出部138が、処理対象の到着ノードデータCの到達コストC3、最小残量C4、および最大残量C5を設定する。ノード残量算出部138は、ステップS102で取り出されたノードの到達コストC3とステップS201で計算されたリンクコストとを加算することにより、処理対象の到着ノードデータCの到達コストC3を算出する。ノード残量算出部138は、同様にステップS102で取り出されたノードの最小残量C4および最大残量C5から、ステップS201で計算されたエネルギー消費量を減ずることにより、処理対象の到着ノードデータCの最小残量C4および最大残量C5を算出する。なお、自車両200が例えば回生ブレーキを備える場合など、ステップS201で算出されたエネルギー消費量が負の値となる場合があり得るが、この場合は処理の都合上エネルギー消費量を0%として扱う。
【0054】
ステップS203では、ノード残量算出部138が、処理対象のノードが補給地ノードであるか否かを判定する。すなわち、処理対象のノードのノード情報Nにおいて、補給地フラグL4(図6)が1であるか否かを判定する。処理対象のノードが補給地ノードである場合、ノード残量算出部138により肯定判定がなされ、ノードエネルギー残量算出処理はステップS204へ進む。ステップS204では、ノード残量算出部138が、処理対象の到着ノードデータCの最大残量C5および直前補給地ノードIDC7を更新し、ノードエネルギー残量算出処理を終了する。具体的には、最大残量C5が上下限残量設定部132により設定されたエネルギー残量の下限となり、直前補給地ノードIDC7が処理対象の到着ノードデータCの到着ノードIDC1となる。他方、ステップS203において否定判定がなされた場合には、ノードエネルギー残量算出処理を終了する。
【0055】
(ノード到達可否判定処理の説明)
図12は、ノード到達可否判定処理のフローチャートである。この処理はノード到達可否判定部139が、特定の到着ノードデータCに対して実行する。なお、以下の説明において、上下限残量設定部132により設定されたエネルギー残量の下限を「下限値」という。
【0056】
ステップS301では、ノード到達可否判定部139が、処理対象の到着ノードデータCの最大残量C5が下限値未満であるか否かを判定する。到着ノードが目的地ノードである場合には、上下限残量設定部132により別途設定された目的地の下限値を用いてエネルギー残量の判定を行う。目的地の下限値の設定と本判定処理によって、目的地到達時点でのエネルギー残量が下限値以上であることが保証される。これにより、目的地においてエネルギーの補給を行えない場合であっても、次回出発時(このとき目的地が新たな出発地となる)には少なくとも該下限値で到達可能な補給地まで走行することが可能となる。ステップS301においてノード到達可否判定部139により肯定判定がなされた場合には、ノード到達可否判定処理はステップS302へ進む。ステップS302では、ノード到達可否判定部139が処理対象の到着ノードデータCの到達可否フラグC8を「否」に設定し、ノード到達可否判定処理を終了する。他方、ステップS301において否定判定がなされた場合には、ノード到達可否判定処理はステップS303へ進む。
【0057】
ステップS303では、ノード到達可否判定部139が、処理対象の到着ノードデータCの最小残量C4が下限値未満であるか否かを判定する。ステップS303においてノード到達可否判定部139により肯定判定がなされた場合には、ノード到達可否判定処理はステップS304へ進む。ステップS304では、ノード到達可否判定部139が処理対象の到着ノードデータCの最小残量C4および確定補給地C6を更新し、ノード到達可否判定処理を終了する。具体的には、ノード到達可否判定部139が最小残量C4を最大残量C5と同じ値に設定すると共に、確定補給地C6を到着ノードIDC1と同じ値に設定する。他方、ステップS303において否定判定がなされた場合には、ノード到達可否判定処理を終了する。
【0058】
なお、ステップS302において到達可否フラグC8が「否」に設定された到着ノードデータCは、エネルギー残量の観点から到達することができないノードであるので、このノードに対してステップS105(図8)のループ処理をこれ以上実行する必要が無い。従って、経路探索部137は、到達可否フラグC8が「否」に設定された到着ノードデータCをDRAM103から消去すると共に、ステップS108の到達候補ノード登録判定処理を実行せずにステップS105のループ処理に戻る。
【0059】
(到達候補ノード登録判定処理の説明)
図13は、到達候補ノード登録判定処理のフローチャートである。この処理は候補ノード登録判定部140が、特定の到着ノードデータCに対して実行する。
【0060】
ステップS401では、候補ノード登録判定部140が、処理対象の到着ノードデータCの到達コストC3が確定ノードリストDLに格納されている当該ノードの最小コストD41未満か否かを判定する。この処理は、公知のダイクストラ法におけるノードの絞り込みと同一の処理である。すなわちこの処理は、到達コストが小さいノードのみを候補として絞り込むことにより、計算量を削減するための処理である。なお、公知のダイクストラ法では、最短の経路が確定したノード、すなわち確定ノードリストDLの確定情報D3に「N/A」以外の値が存在するノードに対してステップS401に相当する処理を行わない。しかしながら、本実施形態においては経路が確定したノードであっても、その先のノードにおいてエネルギー残量不足になる可能性があるため、ステップS401の処理を全ての処理対象ノードに対して実行する。ステップS401において候補ノード登録判定部140により肯定判定がなされた場合、到達候補ノード登録判定処理はステップS405に進む。他方、ステップS401において否定判定がなされた場合、到達候補ノード登録判定処理はステップS403へ進む。
【0061】
ステップS403では、候補ノード登録判定部140が、処理対象の到着ノードデータCの最大残量C5が確定ノードリストDLに格納されている当該ノードの最大残量D34以下であるか否かを判定する。なお、最大残量D34が「N/A」である場合には、最大残量D42を比較に用いる。ステップS403において肯定判定がなされた場合、到達候補ノード登録判定処理は終了する。これは、ステップS403において肯定判定がなされたということは、到達コストおよびエネルギー残量が共に既知の経路より劣るということなので、処理対象のノードに対してこれ以上の経路探索処理を行う必要がないためである。他方、ステップS403において否定判定がなされた場合には、到達候補ノード登録判定処理はステップS405へ進む。
【0062】
ステップS405では、候補ノード登録判定部140が処理対象の到着ノードデータCを候補ノードヒープ181へ追加する。ステップS406では、候補ノード登録判定部140が、処理対象のノードの確定ノードリストDLにおける未確定情報D4を更新する。具体的には、候補ノード登録判定部140は、最小コストD41が到着ノードデータCの到達コストC3より大きければ、最小コストD41を到着ノードデータCの到達コストC3で置き換える。同様に、最大残量D42が到着ノードデータCの最大残量C5より小さければ、最大残量D42を到着ノードデータCの最大残量C5で置き換える。
【0063】
以上の処理により候補ノードヒープ181には、特定のノードについて、到達コストC3が最小である到着ノードデータCと、最大残量C5が最大である到着ノードデータCと、が登録されることとなる。すなわち、候補ノードヒープ181には到達コストとエネルギー残量のどちらかで優位になるノードのみが残り、無駄な経路探索が行われない。通常は到達コストが大きいほどエネルギー消費量は大きくなる。従って、到達コストが大きく且つエネルギー残量が大きいケースは、補給を行ったケースや特殊な地形を走行したケースに限られる。このようなケースは確率的に少なく、候補ノードヒープ181に含まれるノードの数は比較的小規模に抑えられる。
【0064】
次に、図10のステップS1022の説明で述べた、候補ノードヒープ181が空であることが「目的地到達経路なし」となる理由について説明する。上記で説明した通り、候補ノードヒープ181には到達コストC3が最少、または最大残量C5が最大である到達ノードデータCが登録されている。到達コストC3が最少である到達ノードデータCは、ステップS102の処理によって逐次取り出されていく。そして、最大残量C5が最大である到達ノードデータCが候補ノードヒープ181に登録されない状態、すなわち適切な補給地が存在しない状態になると、候補ノードヒープ181内のノード数が、目的地を発見する前に0になることがある。このような状態は、ステップS107(図10)のノード到達可否判定処理がエネルギー残量の不足のため新しいノードを供給しなくなること、または、最大残量C5を越えるノードが存在しないため、ステップS108の到達候補ノード登録判定処理が新しいノードを登録しなくなることにより発生する。すなわち、このような状態は、目的地に下限値以上のエネルギー残量で到達できないことを意味している。なお、目的地未到達の場合、候補ノードヒープ181が空になるまで経路探索処理が実行され続けることになるが、前述した理由により候補ノードヒープ181の大きさは抑えられることになるので、計算量の爆発的増大は避けられる。
【0065】
(経由地自動追加処理の説明)
図14は、推奨経路のデータ構造を示す図である。図14に示すように、経路探索部137が出力する推奨経路は、複数の到着ノードデータC(図8)が連なったデータ列Rである。図14に示すデータ列Rは、出発地から目的地の順に、n個の到着ノードデータCが並んでいる。経由地自動追加部134は、データ列Rに含まれる到着ノードデータCについて、先頭から順に確定補給地ノードIDの変化を検索する。経由地自動追加部134は、確定補給地ノードIDが変化しているノードを発見すると、この確定補給地ノードIDをネットワーク地図DB122から検索する。そして、対応する補給地IDL5(図6)を取得し、更にこの補給地IDL5を補給地DB123(図7)から検索する。経由地自動追加部134はこのようにして取得した補給地情報Sに基づき、補給地名称やその他表示に必要な情報を含む経由地のデータを推奨経路に追加する。経路表示部136はこれらのデータに基づいて、図5に示したような経由地の表示を行う。ユーザはこれらの経由地において補給を行い推奨経路上の他の補給地で補給を行わないことにより、補給回数を最少にすることができる。すなわち、経路探索部137は、確定補給地ノードIDという形で、補給を行う最適なタイミングを演算している。そして経路表示部136は上記のような表示を行うことにより、ユーザへ補給を行う最適なタイミングを報知している。
【0066】
上述した第1の実施の形態によるナビゲーション装置によれば、次の作用効果が得られる。
(1)経路探索部137は、ノード残量算出部138に各ノードにおけるエネルギー残量を更新させながら、エネルギー残量が上下限残量設定部132により設定された下限値を下回らない経路のうち最少の到達コストを有する推奨経路を探索する。これにより、エネルギー残量を考慮した経路探索を計算量を抑えつつ行うことができる。
【0067】
(2)経路探索部137は、推奨経路の探索時に、最少残量および確定補給地ノードIDという形で、補給回数が最も少なくなる補給タイミングを演算する。これにより、経路表示部136は、ユーザへ適切なタイミングで補給を促すことが可能となる。
【0068】
(3)上下限残量設定部132は、補給地における補給によりエネルギー残量が増加する上限値を設定する。蓄電池は充電に要する時間がバッテリー残量により大きく変動するので、これによりエネルギーの補給に要する時間を抑制することができる。
【0069】
(4)目的地到達可否判定部135は、エネルギー残量が上下限残量設定部132により設定された下限値を下回らずに目的地へ到達可能か否かを判定する。これにより、目的地の周辺に補給地が存在しない場合など、目的地に到達不可能であることをユーザへ報知することができる。
【0070】
(第2の実施の形態)
第2の実施の形態に係るナビゲーション装置は、第1の実施の形態に係るナビゲーション装置に加えて、最適な補給地の選択を行う。なお、図1および図2に示す第1の実施の形態と同一の回路および装置には同一の符号を付し、説明を省略する。
【0071】
本実施形態の経由地自動追加部134は、補給を行うべき補給地を、図14を用いて説明した手順とは異なる手順により経由地として追加する。以下、推奨経路上に1からNまでの番号が割り振られたN個の補給地ノードが存在する場合の、経由地自動追加部134による経由地自動追加処理について説明する。
【0072】
蓄電池への充電には残量に応じた時間が必要とされる。そこで、この充電に必要な時間を推定するための関数T(ri)を定義する。ここでriは、i番目の補給地まで走行した場合のエネルギー残量である。一般に、エネルギー残量が少ないほど充電に要する時間は長くなるので、関数T(ri)は、riが小さいほどその値が大きくなるよう定義される。このとき、経由地自動追加部134は、「T(r0)+T(r1)+…+T(rN)+走行の所要時間」が最小となる補給地の組み合わせを探索する。この探索は、例えば線形計画法により行うことが可能である。経由地自動追加部134は、この探索により得られた補給地を、経由地として推奨経路へ追加する。
【0073】
上述した第2の実施の形態によるナビゲーション装置によれば、第1の実施の形態によるナビゲーション装置で得られる作用効果に加えて、次の作用効果が得られる。
(1)経由地自動追加部134は、補給を行うべき補給地を、エネルギー残量に応じた充電時間を考慮して探索する。これにより、充電時間も含めた最短経路を探索することが可能となる。
【0074】
次のような変形も本発明の範囲内であり、変形例の一つ、もしくは複数を上述の実施形態と組み合わせることも可能である。
【0075】
(変形例1)
第1の実施の形態のように、単独で動作するナビゲーション装置だけではなく、経路探索機能を備えたサーバと、そのサーバに接続するクライアントと、から成るナビゲーションシステムへ本発明を適用してもよい。例えば、ナビゲーション装置が図1に示す電池残量センサ107,液晶モニタ109,タッチパネル110,現在地検出装置111、ならびに、図2に示す表示用地図DB124、探索条件設定部131、上下限残量設定部132、目的地設定部133,経路表示部136の各部に加えて、携帯電話網や無線LANなどによりサーバと双方向通信を行う通信装置を備えるように構成する。他方、サーバはナビゲーション装置から現在地、目的地、エネルギー残量、各種の経路探索条件を受信する通信装置と、図2に示すネットワーク地図DB122、補給地DB123、経路探索部137を備えるように構成する。そしてサーバは、経路探索部137が出力した推奨経路を、通信装置を介してナビゲーション装置へ送信する。ナビゲーション装置は通信装置を介して受信した推奨経路を経路表示部136により液晶モニタ109へ表示すればよい。
【0076】
(変形例2)
上述の実施形態ではダイクストラ法に対してエネルギー残量を考慮する各種処理を加えたが、ダイクストラ法以外の経路探索手法に対しても本発明を適用することが可能である。例えば、いわゆるA*探索アルゴリズムについても、上述の実施形態と同様に本発明を適用することができる。
【0077】
(変形例3)
上述の実施形態では、自車両200は電気自動車であり、補給地は充電ステーションであるとしたが、自車両200の駆動エネルギーの形態はこれに限定されない。例えば、ガソリン車とガソリン、水素自動車と水素燃料などであってもよい。
【0078】
(変形例4)
第1の実施の形態において、補給地DB123に格納されているデータのうち、補給燃料の種類S4(図7)は「充電」のみとしたが、補給地DB123は異なる様々な種類の燃料を補給する補給地のデータを含んでいてよい。この場合、経路探索部137は自車両200に関係のない補給地のデータを単純に無視する。例えば、自車両200が電気自動車であれば、経路探索部137は補給燃料の種類S4が「ガソリン」や「水素」であるような補給地を無視する。また、1つの補給地が2種類以上の燃料を供給可能であることを表すため、補給燃料の種類S4へ2種類以上のデータを格納できるよう補給地DB123を構成してもよい。
【0079】
(変形例5)
上下限残量設定部132は、目的地におけるエネルギー残量の下限の設定を行わなくてもよい。すなわち、上下限残量設定画面141(図3)から、目的地におけるエネルギー残量の下限144を削除してもよい。この場合、エネルギー残量の下限142を、目的地におけるエネルギー残量の下限としても用いる。同様に、上下限残量設定部132が、エネルギー残量の上限の設定を行わないようにしてもよい。この場合、経路探索部137は、エネルギー残量の上限を100%として経路探索処理を行う。
【0080】
(変形例6)
上下限残量設定部132は、目的地から目的地に最寄りの補給地までの経路を走行するために必要なエネルギー量を、目的地におけるエネルギー残量の下限として自動的に設定するようにしてもよい。
【0081】
本発明の特徴を損なわない限り、本発明は上記実施の形態に限定されるものではなく、本発明の技術的思想の範囲内で考えられるその他の形態についても、本発明の範囲内に含まれる。
【符号の説明】
【0082】
100…ナビゲーション装置、101…制御回路、103…DRAM、104…不揮発性メモリ、105…ディスクドライブ、106…DVD−ROM、107…電池残量センサ、108…交通情報受信機、109…液晶モニタ、110…タッチパネル、111…現在地検出装置、121…POIDB、122…ネットワーク地図DB、123…補給地DB、124…表示用地図DB、131…探索条件設定部、132…上下限残量設定部、133…目的地設定部、134…経由地自動追加部、135…目的地到達可否判定部、136…経路表示部、137…経路探索部、138…ノード残量算出部、139…ノード到達可否判定部、140…候補ノード登録判定部、200…自車両
【特許請求の範囲】
【請求項1】
現在地を検出する現在地検出手段と、
自車両の駆動エネルギーの残量を検出するエネルギー残量検出手段と、
自車両への前記駆動エネルギーの補給地の位置情報を含む地図情報が記憶された記憶手段と、
前記地図情報に基づいて、前記地図情報に含まれる任意のリンクを走行する際の前記駆動エネルギーの消費量を算出するエネルギー消費量算出手段と、
前記現在地から目的地に至る経路を演算する経路演算手段と、
前記経路演算手段による演算の結果に基づいて、自車両の経路誘導を行う経路誘導手段とを備え、
前記経路演算手段は、前記地図情報と、前記エネルギー残量検出手段により検出された出発時の前記残量と、前記エネルギー消費量算出手段により算出された前記消費量とに基づいて、前記残量が所定のしきい値を下回らない経路のうち最少のコストを有する推奨経路を演算することを特徴とするナビゲーション装置。
【請求項2】
請求項1に記載のナビゲーション装置において、
前記経路誘導手段による経路誘導中に、運転者へ前記駆動エネルギーの補給タイミングを報知する報知手段を更に備え
前記経路演算手段は、前記推奨経路を走行時に通過する前記補給地における補給回数が最も少なくなる補給タイミングを演算し、
前記報知手段は、前記経路演算手段により演算された補給タイミングに基づいて、補給タイミングの報知を行うことを特徴とするナビゲーション装置。
【請求項3】
請求項2に記載のナビゲーション装置において、
前記経路演算手段は、ダイクストラ法を用いた前記推奨経路の演算において、コストと共に前記残量の最小値および最大値を演算および記憶することを特徴とするナビゲーション装置。
【請求項4】
請求項1〜3のいずれか一項に記載のナビゲーション装置において、
前記所定のしきい値と前記残量の上限値とを設定する上下限値設定手段を更に備え、
前記経路演算手段は、前記補給地における補給が前記残量を前記上限値まで増加させることを前提として前記推奨経路を演算することを特徴とするナビゲーション装置。
【請求項5】
請求項1〜4のいずれか一項に記載のナビゲーション装置において、
前記残量が所定のしきい値を下回らずに前記目的地へ到達可能か否かを判定する到達可否判定手段を更に備えることを特徴とするナビゲーション装置。
【請求項6】
請求項1〜3のいずれか一項に記載のナビゲーション装置において、
前記目的地における前記残量の下限値を設定する下限値設定手段を更に備え、
前記経路演算手段は、前記目的地における前記残量が前記下限値以上である前記推奨経路を演算することを特徴とするナビゲーション装置。
【請求項7】
出発時における自車両の駆動エネルギーの残量を設定するエネルギー残量設定工程と、
自車両への前記駆動エネルギーの補給地の位置情報を含む地図情報に基づいて、前記地図情報に含まれる任意のリンクを走行する際の前記駆動エネルギーの消費量を算出するエネルギー消費量算出工程と、
前記現在地から目的地に至る経路を演算する経路演算工程とを備え、
前記経路演算工程では、前記地図情報と、前記エネルギー残量設定工程により設定された出発時の前記残量と、前記エネルギー消費量算出工程により算出された前記消費量とに基づいて、前記残量が所定のしきい値を下回らない経路のうち最少のコストを有する推奨経路を演算することを特徴とする経路演算方法。
【請求項1】
現在地を検出する現在地検出手段と、
自車両の駆動エネルギーの残量を検出するエネルギー残量検出手段と、
自車両への前記駆動エネルギーの補給地の位置情報を含む地図情報が記憶された記憶手段と、
前記地図情報に基づいて、前記地図情報に含まれる任意のリンクを走行する際の前記駆動エネルギーの消費量を算出するエネルギー消費量算出手段と、
前記現在地から目的地に至る経路を演算する経路演算手段と、
前記経路演算手段による演算の結果に基づいて、自車両の経路誘導を行う経路誘導手段とを備え、
前記経路演算手段は、前記地図情報と、前記エネルギー残量検出手段により検出された出発時の前記残量と、前記エネルギー消費量算出手段により算出された前記消費量とに基づいて、前記残量が所定のしきい値を下回らない経路のうち最少のコストを有する推奨経路を演算することを特徴とするナビゲーション装置。
【請求項2】
請求項1に記載のナビゲーション装置において、
前記経路誘導手段による経路誘導中に、運転者へ前記駆動エネルギーの補給タイミングを報知する報知手段を更に備え
前記経路演算手段は、前記推奨経路を走行時に通過する前記補給地における補給回数が最も少なくなる補給タイミングを演算し、
前記報知手段は、前記経路演算手段により演算された補給タイミングに基づいて、補給タイミングの報知を行うことを特徴とするナビゲーション装置。
【請求項3】
請求項2に記載のナビゲーション装置において、
前記経路演算手段は、ダイクストラ法を用いた前記推奨経路の演算において、コストと共に前記残量の最小値および最大値を演算および記憶することを特徴とするナビゲーション装置。
【請求項4】
請求項1〜3のいずれか一項に記載のナビゲーション装置において、
前記所定のしきい値と前記残量の上限値とを設定する上下限値設定手段を更に備え、
前記経路演算手段は、前記補給地における補給が前記残量を前記上限値まで増加させることを前提として前記推奨経路を演算することを特徴とするナビゲーション装置。
【請求項5】
請求項1〜4のいずれか一項に記載のナビゲーション装置において、
前記残量が所定のしきい値を下回らずに前記目的地へ到達可能か否かを判定する到達可否判定手段を更に備えることを特徴とするナビゲーション装置。
【請求項6】
請求項1〜3のいずれか一項に記載のナビゲーション装置において、
前記目的地における前記残量の下限値を設定する下限値設定手段を更に備え、
前記経路演算手段は、前記目的地における前記残量が前記下限値以上である前記推奨経路を演算することを特徴とするナビゲーション装置。
【請求項7】
出発時における自車両の駆動エネルギーの残量を設定するエネルギー残量設定工程と、
自車両への前記駆動エネルギーの補給地の位置情報を含む地図情報に基づいて、前記地図情報に含まれる任意のリンクを走行する際の前記駆動エネルギーの消費量を算出するエネルギー消費量算出工程と、
前記現在地から目的地に至る経路を演算する経路演算工程とを備え、
前記経路演算工程では、前記地図情報と、前記エネルギー残量設定工程により設定された出発時の前記残量と、前記エネルギー消費量算出工程により算出された前記消費量とに基づいて、前記残量が所定のしきい値を下回らない経路のうち最少のコストを有する推奨経路を演算することを特徴とする経路演算方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【公開番号】特開2011−75382(P2011−75382A)
【公開日】平成23年4月14日(2011.4.14)
【国際特許分類】
【出願番号】特願2009−226596(P2009−226596)
【出願日】平成21年9月30日(2009.9.30)
【出願人】(000001487)クラリオン株式会社 (1,722)
【Fターム(参考)】
【公開日】平成23年4月14日(2011.4.14)
【国際特許分類】
【出願日】平成21年9月30日(2009.9.30)
【出願人】(000001487)クラリオン株式会社 (1,722)
【Fターム(参考)】
[ Back to top ]