ナビゲーション装置およびそのプログラム
【課題】提示した経路探索結果に対して納得させることができ、かつストレスを感じさせずに安全運転を支援するナビゲーション装置およびそのプログラムを提供する。
【解決手段】経路探索をするための情報を格納する記憶手段１２と、記憶手段１２に格納された情報から各ノード間のリンクコストを算出するリンクコスト算出手段１５と、リンクコスト算出手段１５により算出されたリンクコストに基づいて複数の経路より一の経路を選択する経路探索手段１６と、経路探索手段１６によって選択されなかったノードのリンク切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納するリンク切断要因・区間格納手段１７と、リンク切断要因・区間格納手段１７により抽出して格納された情報を出力して表示する入出力表示手段１３と、を有するナビゲーション装置１０とした。
【解決手段】経路探索をするための情報を格納する記憶手段１２と、記憶手段１２に格納された情報から各ノード間のリンクコストを算出するリンクコスト算出手段１５と、リンクコスト算出手段１５により算出されたリンクコストに基づいて複数の経路より一の経路を選択する経路探索手段１６と、経路探索手段１６によって選択されなかったノードのリンク切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納するリンク切断要因・区間格納手段１７と、リンク切断要因・区間格納手段１７により抽出して格納された情報を出力して表示する入出力表示手段１３と、を有するナビゲーション装置１０とした。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置およびそのプログラムに関する。
【背景技術】
【０００２】
ナビゲーション装置において、たとえば車に使用されるカーナビゲーション装置の経路探索方法には、有料道路優先、一般道路優先、有料道路回避、距離優先、時間優先等がある。また、歩行ナビゲーション装置の経路探索方法には、距離優先、屋根の多い道路優先、階段が少ない道路優先、坂道のなだらかな道路優先等がある。このような経路探索方法を採用したナビゲーション装置を使用するユーザーは、自分の知っている道より遠回りとなる結果が当該ナビゲーション装置から提示されると、提示されたルートに対してなぜそのようなルートが提示されるのかという疑義が生じる。更に、このような疑義が一度生じてしまうとそのユーザーの知っている情報が正しいか否かに関わらず、当該ナビゲーション装置の性能に対しても不信感を募らせるため、ＣＳ（Ｃｕｓｔｏｍｅｒ Ｓａｔｉｓｆａｃｔｉｏｎ：顧客満足）の観点から好ましくない。このような状況を未然に防止するため、特定区間の経路について設定条件を変更しながら経路探索を完結させる区間条件設定機能を備えたカーナビゲーション装置が知られている（特許文献１参照）。
【０００３】
【特許文献１】特開２００６−２００９８１号公報（特許請求の範囲、発明の実施の形態、段落００１７など）
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１に開示されているカーナビゲーション装置は、特定区間の道路条件について十分な情報を持っているユーザーでなければ、上述した区間条件設定機能を用いて適切に設定し直すことができない。また、仮に特定区間の道路条件について十分な情報を持っているユーザーであっても、交通規制や混雑状況などは時々刻々とダイナミックに変化するため、知り得ない情報が存在する場合もある。したがって、特定区間の道路条件について十分な情報を持っていないユーザーであるか否かに関わらず、提示された経路に対して何らかの疑問を抱いてそれを解消することができないときは、ストレスとなって間接的に安全運転上の支障をきたす恐れがある。
【０００５】
本発明の目的は、このような課題を解決すべく、ユーザーが特定区間の道路条件について十分な情報を持っているか否かに関わらず、提示した経路探索結果に対して納得させることができ、かつストレスを感じさせずに安全運転を支援するナビゲーション装置およびそのプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
本発明は上述した目的を達成するために、経路探索をするための情報を格納する記憶手段と、記憶手段に格納された情報から各ノード間のリンクコストを算出するリンクコスト算出手段と、リンクコスト算出手段により算出されたリンクコストに基づいて複数の経路より一の経路を選択する経路探索手段と、経路探索手段によって選択されなかったノードのリンク切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納するリンク切断要因・区間格納手段と、リンク切断要因・区間格納手段により抽出して格納された情報を経路探索結果と共に表示する入出力表示手段と、を有するナビゲーション装置である。
【０００７】
他の発明は、経路探索をするための情報を格納する記憶手段と、記憶手段に格納された情報から各ノード間のリンクコストを算出するリンクコスト算出手段と、リンクコスト算出手段により算出されたリンクコストに基づいて複数の経路より一の経路を選択する経路探索手段と、経路探索手段によって選択されなかったノードのリンク切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納するリンク切断要因・区間格納手段と、リンク切断要因・区間格納手段に抽出して格納された情報を出力するように指示する経路探索根拠出力要求手段と、を有するナビゲーション装置である。
【０００８】
また他の発明は、上述した発明に加えて、経路探索手段により選択された一の経路を構成する各ノード情報および／または各ノード区間のリンクコストを記憶手段へ格納する探索経路登録保持手段と、探索経路登録保持手段に格納された一の経路が呼び出されたときに一の経路のリンクコストを再計算するリンクコスト再計算手段と、リンクコスト再計算手段に基づいて決定された経路が一の経路と異なることとなったとき、一の経路を構成する各ノードのうちリンクが切断された切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納する経路変更根拠格納手段と、経路変更根拠格納手段により抽出して格納された情報を経路探索結果と共に表示する入出力表示手段と、を有するナビゲーション装置である。
【０００９】
また他の発明は、上述した発明に加えて、経路探索手段により選択された一の経路を構成する各ノード情報および／または各ノード区間のリンクコストを記憶手段に格納する探索経路登録保持手段と、探索経路登録保持手段に格納された一の経路が呼び出されたときに一の経路のリンクコストを再計算するリンクコスト再計算手段と、リンクコスト再計算手段に基づいて決定された経路が一の経路と異なることとなったとき、一の経路を構成する各ノードのうちリンクが切断された切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納する経路変更根拠格納手段と、経路変更根拠格納手段により抽出して格納された情報を出力するように指示できる経路探索根拠出力要求手段と、を有するナビゲーション装置である。
【００１０】
また他の発明は、上述したナビゲーション装置のいずれか一つの装置として機能させるプログラムである。
【発明の効果】
【００１１】
本発明は、ユーザーが特定区間の道路条件について十分な情報を持っているか否かに関わらず、提示した経路探索結果に対して納得させることができ、かつストレスを感じさせずに安全運転を支援するナビゲーション装置およびそのプログラムを提供することができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明に係る第１の実施形態について説明する。図１は、本発明に係る第１の実施形態であるカーナビゲーション装置１０の概要構成を示したブロック図である。
【００１３】
図１に示すようにカーナビゲーション装置１０は、演算制御手段１１と、記憶手段１２と、入出力表示手段１３と、自己位置検出手段１４と、リンクコスト算出手段１５と、経路探索手段１６と、リンク切断要因・区間格納手段１７と、を有する。以下、カーナビゲーション装置１０を構成する各手段について説明する。
【００１４】
演算制御手段１１は、カーナビゲーション装置１０を搭載している車両の現在地についての算出処理,地図の描画処理,目的地検索処理,経路検索処理などの各種演算処理や、それらの各処理の制御処理を行なう機能を備えている。演算制御手段１１を構成するものとして、たとえばＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などが具体例として挙げられる。
【００１５】
記憶手段１２は、道路網の様々な情報を格納する機能を備えている。たとえば、高速自動車国道，都市高速道路，一般国道，主要地方道，一般都道府県道，市町村道，農道，林道などの道路種別情報、車線数，歩道の有無，交通規制，渋滞具合などの道路属性情報と、Ｍランク（自動車専用道路），Ｓランク（とても走りやすい），Ａランク（走りやすい），Ｂランク（やや走りやすい），Ｃランク（やや走りにくい），Ｄランク（走りにくい）といった走りやすさのランク情報、全長，全幅，全高などの車両情報、「幅の広めの一車線道路を好む」，「複数車線道路を好む」などのドライバーの特性情報等を格納している。これらの情報は、後述するリンクコストを決定する要素として用られる。なお、記憶手段１２を構成するものとして、たとえばハードディスク,フレキシブルディスク,ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）メモリなどの外部記憶装置や、磁気テープ,ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｃ）,ＭＤ（Ｍｉｎｉ Ｄｉｓｋ）,ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）,光ディスクなどの外部記憶媒体、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄａｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）などが具体例として挙げられる。
【００１６】
入出力表示手段１３は、地図や案内情報を出力表示する機能や、カーナビゲーション装置１０を操作するための信号を入力する機能を備えている。入出力表示手段１３は、たとえばディスプレイやタッチパネル、これらの画面上に表示されたブラウザ，ウィンドウ，ラジオボタン,アイコンなどが具体例として挙げられる。
【００１７】
自己位置検出手段１４は、カーナビゲーション装置１０を搭載している車両の位置を検出する機能を備えている。自己位置検出手段１４は、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）,ジャイロスコープ（ｇｙｒｏｓｃｏｐｅ）,車速パルスなどのカーナビゲーションに用いられる加速度センサが具体例として挙げられる。
【００１８】
リンクコスト算出手段１５は、選択可能な地点のリンクコストをそれぞれの区間において算出する機能を備えている。ここでリンクコストとは、道路を構成するそれぞれの地点間の各種情報を加味した相対的な数値情報である。たとえば、上述した道路種別情報,道路属性情報,走りやすさのランク情報,車両情報,ユーザーの特性情報などから各地点間のリンクコストを算出する。なお、リンクコストの具体的な算出方法については本発明の主旨から外れるため、割愛する。
【００１９】
経路探索手段１６は、スタート地点と目的地（ゴール地点）を取得して、リンクコスト手段１５によって算出されたリンクコストに基づいて当該区間におけるリンクコストが最も小さくなる経路（ある設定条件下における経路の中でもっとも条件を満たす経路＝最短となる経路）を求める機能を備えている。また、経路探索手段１６は、自己位置検出手段１４により取得した座標データ（スタート地点）と、入出力表示手段１３によって指示された目的地情報（ゴール地点）を取得した時点で最短経路探索処理を開始する機能を備えている。また、スタート地点は上記データ以外に入出力表示手段１３をユーザーが直接操作して、入力された地点情報や座標データとしてもよい。
【００２０】
リンク切断要因・区間格納手段１７は、経路探索手段１６による探索でリンク切断要因となった情報と、リンク切断該当区間情報を抽出して記憶手段１２に格納する機能を備えている。具体的な処理の説明については、続いて行なうカーナビゲーション装置１０の動作説明の中で説明する。
【００２１】
なお、上述した自己位置検出手段１４、リンクコスト算出手段１５、経路探索手段１６、リンク切断要因・区間格納手段１７が行なう情報処理は、それぞれ演算制御手段１１,記憶手段１２,入出力表示手段１３といったハードウェア資源を用いて実行され、演算処理、制御処理、記憶処理、入出力処理といった各種の処理を行ない、協働して動作することによりカーナビゲーション装置１０を構成している。また、自己位置検出手段１４、リンクコスト算出手段１５、経路探索手段１６、リンク切断要因・区間格納手段１７は、上記のハードウェア資源において各種のデータ・プログラムが実行されることにより機能的に実現されるが、専用の処理回路によって実現するようにしてもよい。
【００２２】
続いて、上述した各手段に基づいて本発明の第１の実施形態に係るカーナビゲーション装置１０の動作説明を行なう。なお、本発明の第１の実施形態であるカーナビゲーション装置１０はダイクストラ法に基づく経路の探索処理方法を採用している。しかし、本実施形態の各手段は、その探索処理の結果として生成されるリンクツリーに対応した情報処理を実現するために構築される。したがって、ダイクストラ法そのもののアルゴリズムについての詳細な説明は本発明の主旨から外れるため、割愛する。
【００２３】
図１に示す記憶手段１２には、上述した最短経路探索処理を行なうにあたって必要なデータが蓄積されており、これらのデータに基づいて、有料道路優先、一般道路優先、有料道路回避、距離優先、時間優先等の条件設定されたいくつかのカテゴリ規準に基づいてリンクコストを算出して、最短経路探索処理を実行していく。その処理過程においていくつかの候補となる経路が生成される。
【００２４】
はじめに上述した条件設定の詳細については考えずに、単純にリンクコストが算出された後の最短経路探索処理について説明する。図２は、単純モデル化したある道路網を示す図である。図３は、図２で示す道路網についてダイクストラ法に基づいた最短経路探索処理結果を示す図である。
【００２５】
以下に、カーナビゲーション装置１０の入出力表示手段１３に経路探索処理結果が提示されるまでの過程を説明する。図２に示す道路網では、経路探索処理過程で候補となるスタート地点Ｂからゴール地点Ｇまでのルートは、下記〔１〕〜〔６〕の６つの経路が考えられる。下記の通り、各ルートの矢印の下に該当リンクコストを明示してそれぞれの総和を求めると、
〔１〕Ｂ → Ａ → Ｃ → Ｅ → Ｇ
２ ＋ ２ ＋ １ ＋ ２ ＝７
〔２〕Ｂ → Ｄ → Ｃ → Ｅ → Ｇ
１ ＋ ４ ＋ １ ＋ ２ ＝８
〔３〕Ｂ → Ｄ → Ｅ → Ｇ
１ ＋ ３ ＋ ２ ＝ ６
〔４〕Ｂ → Ｄ → Ｅ → Ｆ → Ｊ → Ｇ
１ ＋ ３ ＋ ３ ＋ ２ ＋ １ ＝１０
〔５〕Ｂ → Ｄ → Ｆ → Ｊ → Ｇ
１ ＋ ６ ＋ ２ ＋ １ ＝１０
〔６〕Ｂ → Ｄ → Ｆ → Ｅ → Ｇ
１ ＋ ６ ＋ ３ ＋ ２ ＝１２
となり、〔３〕の経路が最もリンクコストが小さくなる。したがって、カーナビゲーション装置１０の入出力表示手段１３から、図３に示すように〔３〕の経路である「Ｂ→Ｄ→Ｅ→Ｇ」のルートが最短の経路探索処理結果として提示される。
【００２６】
続いて、図２で示した道路網にダイナミックに交通規制が発生してリンクコストが変化した場合を考える。図４は、図２で示したある道路網に特定の状況変化が生じた図である。具体的にはＡ−Ｃ間で工事による通行規制が実施されており、Ｄ−Ｅ間、Ｅ−Ｇ間に大渋滞が発生して走行時間が過大になったという状況を想定している。図５は、図４で示した特定の状況変化が生じたある道路網についてダイクストラ法に基づいた最短の経路探索結果を示す図である。
【００２７】
リンクコストが変更になった地点およびリンクコストの総和が変化したルートについては下線を引いて表すものとして、それぞれの総和を前述した〔１〕〜〔６〕の経路におけるリンクコストの総和を計算したときと同様に求めると、
〔１１〕Ｂ → Ａ → Ｃ → Ｅ → Ｇ
２ ＋ ７ ＋ １ ＋ ８ ＝１８
〔１２〕Ｂ → Ｄ → Ｃ → Ｅ → Ｇ
１ ＋ ４ ＋ １ ＋ ８ ＝１４
〔１３〕Ｂ → Ｄ → Ｅ → Ｇ
１ ＋ ９ ＋ ８ ＝ １８
〔１４〕Ｂ → Ｄ → Ｅ → Ｆ → Ｊ → Ｇ
１ ＋ ９ ＋ ３ ＋ ２ ＋ １ ＝１６
〔１５〕Ｂ → Ｄ → Ｆ → Ｊ → Ｇ
１ ＋ ６ ＋ ２ ＋ １ ＝１０
〔１６〕Ｂ → Ｄ → Ｆ → Ｅ → Ｇ
１ ＋ ６ ＋ ３ ＋ ８ ＝１８
となり、〔１５〕の経路が最もリンクコストが小さくなる。したがって、図５に示すようにカーナビゲーション装置１０の入出力表示手段１３から、この〔１５〕の経路である「Ｂ−Ｄ−Ｆ−J−Ｇ」のルートが経路探索処理結果として提示される。
【００２８】
図６は、図５に示す最短経路探索処理によりリンクが切断された地点を除いて整理したリンクツリーを示す図である。図８および図９は、図６で示すリンクツリーに対応したリンクツリーコントロールテーブルを示す図である。
【００２９】
カーナビゲーション装置１０では、図６に示すリンクツリーに対応した各リンクツリーコントロールテーブルが生成される。なお、ここでリンクツリーとは、ダイクストラ法による経路探索により生成された最短ルートを概念的に示したものである。また、リンクツリーコントロールテーブルとは、そのリンクツリーに対応してカーナビゲーション装置１０内で生成される論理構造データである。したがって、記憶手段１２には、図８及び図９に示すリンクツリーコントロールテーブルの論理構造データと共に、論理構造データにしたがって各地点に関連する情報が格納されることになる。なお、以下の説明では経路探索上の各地点のことを「ノードＡ、ノードＢ、ノードＣ・・・」という形式で表現し、ノードが格納される各論理アドレスについては「アドレス記号×××××」という表現形式を用いて説明する。
【００３０】
図７は、リンクツリーコントロールテーブル２０の基本構造を説明するための図である。リンクツリーコントロールテーブル２０は、各ノードに対応して生成される論理構造データである。個々のノードのリンクツリーコントロールテーブル２０は、図７に示すようにヘッダ部２１と複数のリンクエントリ部２２から構成される。リンクツリーコントロールテーブル２０では、ヘッダ部２１がはじめに生成される。そして、ヘッダ部２１が生成された後に、はじめてリンクエントリ部２２を複数生成することができる。なお、これらの論理構造データは、カーナビゲーション装置１０の演算処理手段１１を用いて生成または更新され、記憶手段１２に適切に格納される。以下の説明においてもこのような情報処理が適宜なされていることを前提に説明する。
【００３１】
ヘッダ部２１は、主にノード属性情報を格納するための領域であり、図７に示すように４つのパラメータから構成される。すなわちヘッダ部２１は、ノード自体を識別する「ノードＩＤ」（アドレス記号０ＬＨＮＩＤ）と、当該ノードに接続されている他のノードの数を示す「リンク数ｎ」（アドレス記号０ＬＨＮｏＬ）と、当該ノードの前ノードのアドレスを示す「前ノードリンクテーブルポインタＢＰ１」（アドレス記号０ＬＨＢＰ）と、当該ノードに接続されている他のノードがすべて切断されているか否かを判別するための「全リンク切断フラグＦ」（アドレス記号０ＬＨＦ）と、から構成される。
【００３２】
リンクエントリ部２２は、主に当該ノードに関連するノード情報について格納される領域であり、当該ノードに接続されているリンクに対応してその数だけ生成される。リンクエントリ部２２は、図７に示すように４つのパラメータで構成される。すなわち、リンクエントリ部２２は、当該ノードの次に接続されているノードを示す「次ノードＩＤ」（アドレス記号０ＬＬＥ１−１）と、次ノードＩＤによって構成されるリンクツリーコントロールテーブルの先頭アドレスを示す「次ノードリンクテーブルポインタ」（アドレス記号０ＬＬＥ１−２）と、最短経路探索処理過程において次のノードへのリンクの接続有無を格納する「次リンク評価結果フラグ」（アドレス記号０ＬＬＥ１−３）と、リンク切断に至った理由を格納する「次リンク評価結果内容」（アドレス記号０ＬＬＥ１−４）と、から構成される。なお、次リンク評価結果内容に格納されるリンク切断理由についてはリンクコストを形成する要因の大きいものから一つまたは複数個を格納することができる。また、その格納できる個数は別途定義してもよい。更に経路探索をおこなった結果求められたリンクコストの総和に対して上述した要因が占めるリンクコストの割合に所定の閾値を設定して、その所定の閾値以上であるリンクコストの値をもつ要因であれば次リンク評価結果内容に格納するといった方法を採用してもよい。
【００３３】
続いて、ダイクストラ法に基づく最短経路探索処理フローについて図２７を参照しながら説明する。図２７は、ダイクストラ法に基づく最短経路探索処理フローを簡単に示した図である。
【００３４】
まず、経路探索手段１６は、スタート地点とゴール地点が決定されると経路探索処理を開始する（ＳＴＡＲＴ）。
【００３５】
経路探索手段１６は、スタート地点に接続されているノードのリンクコストをリンクコスト算出手段１５によって算出された値を参照して設定する。なお、スタート地点のリンクコストは「０」と設定し、他のノードのリンクコストは最大値（∞）と設定する（ステップＳ１）。
【００３６】
そして、経路探索手段１６は、スタート地点のノードからミニマムリンクコストであるノードを決定する（ステップＳ２）。
【００３７】
続いて、経路探索手段１６は、スタート地点からのリンクコストの総和を算出して、経路比較を行い、不要なリンクを切断する（ステップＳ３）。
【００３８】
最後に、経路探索手段１６は、未確定ノードのなかでミニマムリンクコストであるノードを確定ノードとする（ステップＳ４）。
【００３９】
経路探索手段１６は、上述したステップＳ１〜ステップＳ４までの処理を目的地（ゴール地点）のノードにたどり着くまで繰り返す（ステップＳ５）。
【００４０】
一方、ステップＳ１〜ステップＳ５に示す処理に対応して、経路探索手段１６は、各ノードのリンクツリーコントロールテーブルを構成する図示しないヘッダ部とリンクエントリ部を生成、または更新する。そして、経路探索手段１６は、最終的に上述した図６に示すリンクツリーに対応した図８および図９に示すリンクツリーコントロールテーブルを生成する。以下に、図８および図９に示すリンクツリーコントロールテーブルが生成されるまでの処理過程を具体的に説明する。
【００４１】
図１０は、図４に示した道路網であり、最短経路探索処理結果を単純モデル化して示した図である。図１０に示すようにノードＢのリンクコストは、スタート地点であるため「０」と設定される。また、他のノードのリンクコストは、「最大値（∞）」として設定される。
【００４２】
図１１は、図１０に示す最短経路探索処理結果に次の処理ステップ（Ｓ１）を反映した図である。この処理ステップでは、スタート地点であるノードＢに接続されている各ノードのリンクコストを求める。すなわちノードＢに接続されているノードは、図１１に示すようにノードＡとノードＤであるから、ノードＡとノードＤのリンクコストを求める。図１１よりノードＤのリンクコストは「１」、ノードＡのリンクコストは「２」である。なお、これらのリンクコストは、上述したリンクコスト算出手段１５により算出されて記憶手段１２に適切に格納されているものとする。
【００４３】
図１８は、スタート地点であるノードＢ、ノードＢに接続されているノードＤ、ノードＢに接続されているノードＡの各リンクツリーコントロールテーブルを示す図である。
【００４４】
図１８に示される各リンクツリーコントロールテーブルは、上述した図１１に示す最短経路探索処理結果までを反映した図である。以下、ノードＢのリンクツリーコントロールテーブル３０、ノードＤのリンクツリーコントロールテーブル４０、ノードＡのリンクツリーコントロールテーブル５０について具体的に説明する。
【００４５】
図１８に示すノードＢのヘッダ部３１におけるノードＩＤ（アドレス記号０ＬＨＮＩＤ）には、ノードＩＤ＝Ｂが格納されている。リンク数ｎ（アドレス記号０ＬＨＮｏＬ）には、「２」が格納されている。これはノードＢに、ノードＡとノードＤが接続されているため、リンクエントリ（接続）が２つ存在することを宣言（意味）している。前ノードリンクテーブルポインタ（アドレス記号０ＬＨＢＰ）には、初期値である「０」が格納されている。ノードＢは、スタート地点のノードであり、前リンクが存在しないためである。なお、カーナビゲーション装置１０のプログラミング規約に則って設定されていればこの値は何でも良いことは言うまでもない。全リンク切断フラグＦ（アドレス記号０ＬＨＦ）には、初期値である「０」が格納されている。なお、ノードＢへのリンク全てが未接続または切断されているときに「切断」と、一つのノードでもノードＢへ接続されていれば「接続」という値に変更される。このようにしてリンクツリーコントロールテーブル３０のヘッダ部３１について生成が行なわれる。
【００４６】
次に、ノードＢのリンクエントリ部３２について生成が行なわれる。リンクエントリ部３２は、上述したリンク数ｎ（アドレス記号０ＬＨＮｏＬ）に格納されている値「２」に従って、２エントリ生成される。一つ目のエントリである次ノードＩＤ（アドレス記号０ＬＬＥ１−１）には、次ノードを示すＤが格納されている。二つ目のエントリである次ノードＩＤ（アドレス記号０ＬＬＥ２−１）には、次ノードのＩＤ＝Ａが格納されている。
【００４７】
続いて、リンクツリーコントロールテーブル４０のヘッダ部４１が生成される。そして、リンクツリーコントロールテーブル３０の次ノードリンクテーブルポインタ（アドレス記号０ＬＬＥ１−２）には、アドレス記号１ＬＨＮＩＤが格納される。これによりノードＢのリンクツリーコントロールテーブル３０とノードＤのリンクツリーコントロールテーブル４０とのコントロールテーブルリンクが確立される。
【００４８】
ヘッダ部３１の次リンク評価結果フラグ（アドレス記号０ＬＬＥ１−３）には、ノードＩＤ＝Ｄのヘッダ部４１が生成されたため、初期値である「０」から「接続」に値が変更される。次リンク評価結果内容（アドレス記号０ＬＬＥ１−４）は、次ノードのリンク評価をしていないため、初期値の「０」が格納されている。
【００４９】
一方、前述のノードＩＤ＝Ｄのヘッダ部４１におけるリンク数（アドレス記号１Ｌ１ＨＮｏＬ）は、まだヘッダ部４１のみしか生成されていないため、初期値である「０」が格納される。ヘッダ部４１の前ノードリンクテーブルポインタ（アドレス記号１Ｌ１ＨＢＰ）には、ノードＩＤ＝Ｂのテーブルの先頭アドレス記号０ＬＨＮＩＤが格納される。これにより、ノードＢのリンクツリーコントロールテーブル３０とノードＤのリンクツリーコントロールテーブル４０とのリバースリンクが確立される。尚、全リンク切断フラグ（アドレス記号１ＬＨＦ）は、この時点で図示しないリンクエントリ部が生成されていないため、初期値である「０」が格納される。続いて、ノードＩＤ＝Ａのリンクツリーコントロールテーブル５０のヘッダ部５１が生成されるが、ノードＩＤ＝Ｄのヘッダ部４１と同様に生成されるため、生成の詳細な説明は割愛する。
【００５０】
図１２は、図１１に示す最短経路探索処理結果に次の処理ステップ（Ｓ２）を反映した図である。この処理ステップではノードＢからリンクコストが最小（ミニマムリンクコスト）となるノードを求める。すなわち、ノードＢからのリンクコストが最小となるノードを確定ノードとする処理である。図１１に示すようにノードＡのリンクコストが「２」であり、ノードＤのリンクコストが「１」であるため、ミニマムリンクコストとなるノードすなわち確定ノードは、ノードＤとなる。このように、最小のリンクコストとなるノードを確定ノードとしていくことで、最短経路を決定していく。
【００５１】
図１３は、図１２に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。この処理ステップでは、ノードＤに接続されている各ノードについてスタートノードＢからのリンクコストを求める。すなわち、ノードＣ，ノードＥ、ノードＦについてノードＢからのリンクコストを算出する処理である。図１３に示すようにノードＣが１＋４＝５、ノードＥが１＋９＝１０、ノードＦ１＋６＝７である。
【００５２】
図１９は、図１０〜図１３に示す最短経路探索処理結果を反映した各リンクツリーコントロールテーブルを示す図である。なお、図１８ではノードＩＤ＝Ｄのリンクツリーコントロールテーブル４０はヘッダ部４１のみまでしか生成されていない。しかし、この時点でリンクエントリが３エントリ（次ノードＩＤ＝Ｃ リンクエントリ部４２、次ノードＩＤ＝Ｅ リンクエントリ部４３、次ノードＩＤ＝Ｆ リンクエントリ部４４）生成される。
【００５３】
生成プロセスは、図１８を参照して説明したノードＩＤ＝Ｂのリンクエントリ部３２と同様であるため割愛する。この時点では各エントリの次ノードリンクテーブルポインタ（１Ｌ１ＬＥ１−２、１Ｌ１ＬＥ２−２、１Ｌ１ＬＥ３−２）には、いずれも初期値である「０」が格納されている。
【００５４】
また、次リンクの評価結果フラグ（１Ｌ１ＬＥ１−３、１Ｌ１ＬＥ２−３、１Ｌ１ＬＥ３−３）には、次ノードのヘッダも作成されていないため、いずれも初期値の「０」が格納されている。そして、３つのリンクエントリ部４２，４３，４４が生成されると、ヘッダ部４１のリンク数（アドレス記号１Ｌ１ＨＮｏＬ）が０から３に更新される。
【００５５】
また、全リンク切断フラグ（アドレス記号１Ｌ１ＨＦ）には、初期値の「０」を「接続」に更新される。なお、ノードＩＤ＝Ａのリンクツリーコントロールテーブル５０は、図１８で生成したヘッダ部５１のみであり、格納されている値は更新されない。
【００５６】
図１４は、図１３に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。この処理ステップでは、スタート地点から接続されている各確定ノードに接続されている未確定ノードの中でミニマムリンクコストであるノードを決定する。まず、この時点で上記の条件を満たすノードは、ノードＡおよびノードＣである。ここで、更にミニマムリンクコストであるノードは、ノードＡのリンクコストが「２」で、ノードＣのリンクコストが「５」であるからノードＡである。したがって、ノードＡを確定ノードとして決定する。なお、ここで未確定ノードとは、当該ノードの経路探索処理が終了していないノードのことである。
【００５７】
図２０は、図１４に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡの各リンクツリーコントロールテーブルを示す図である。ノードＡが確定ノードになったことに伴い、各リンクツリーコントロールテーブルでは次のような更新処理がなされる。図２０に示すノードＩＤ＝Ａのリンクエントリ部５０が生成され、次ノードＩＤ＝Ｃ（アドレス記号１Ｌ２ＬＥ１−１）が格納される。リンク数（アドレス記号１Ｌ２ＨＮｏL）は「１」に更新され、全リンク切断フラグ（アドレス記号１Ｌ２ＨＦ）は、「０」から「接続」に更新される。
【００５８】
図１５は、図１４に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。この処理ステップでは、ノードＡに接続されているノードについてスタート地点であるノードＢからリンクコストを計算する。すなわち、図１５に示すようにノードＡに接続されている未確定ノードはノードＣのみであるから、「Ｂ―Ｃ」間までのリンクコストを考える。ここで、「Ｂ―Ｃ」間までの選択可能な経路は「Ｂ−Ａ−Ｃ」ルートと、「Ｂ−Ｄ−Ｃ」ルートの２通りある。それぞれのリンクコストを計算すると、「Ｂ−Ａ−Ｃ」ルートは「９（２＋７）」、「Ｂ−Ｄ−Ｃ」ルートは「５（１＋４）」であるから、「Ｂ−Ｄ−Ｃ」ルートが最短となるため、現状を維持することになる。したがって「Ｂ−Ａ−Ｃ」ルートは不要であるため、「Ａ−Ｃ」間のリンクを切断する。
【００５９】
図２１は、図１５に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡの各リンクツリーコントロールテーブルを示す図である。ノードＡのリンクエントリ部５２の次リンク評価フラグ（アドレス記号１Ｌ２ＬＥ１−３）は、ノード「Ａ−Ｃ」間のリンクが切断されたため初期値の「０」から「切断」に更新される。また、ノードＡのリンクエントリ部５２の次リンク評価結果内容（アドレス記号１Ｌ２ＬＥ１−４）には、図１に示した記憶手段１２に格納されている地図データ（図示せず）から取得した「工事による通行規制」が格納される。
【００６０】
これらの更新処理に伴って、ノードＡが全てのリンクから切断されている状態（不活性状態）となる更新処理を行なう必要がある。また、ノードＡ自身も不活性状態と同等であるため、接続されている全ノードのリンクエントリに対して更新処理を行なう必要がある。すなわち、図２１に示すようにノードＡのヘッダ部５１の全リンク切断フラグ（アドレス記号１Ｌ２ＨＢＰ）を「０」から「切断」に更新され、ノードＢのリンクエントリ部３３の次リンク評価結果フラグ（アドレス記号０ＬＬＥ２−３）も「０」から「切断」に更新される。
【００６１】
また、それに伴いノードＢのリンクエントリ部３３の次リンク評価結果内容（アドレス記号０ＬＬＥ２−４）に「Ａ−Ｃ間工事による通行規制」という情報が更新される。なお、このような更新処理を行なうことで、不要ノードの接続情報が残らず、後述するリンク切断根拠・区間を抽出する判定処理において必要な接続ノード情報を参照するだけで、判定することができる。したがって、当該判定処理をより高速化することができる。
【００６２】
図１６は、図１５に示す最短経路探索処理結果に次の処理ステップ（Ｓ４）を反映した図である。この処理ステップでは、未確定のノードの中でミニマムリンクコストを決定する。すなわち未確定ノードであって、かつミニマムリンクコストであるノードは、この時点でノードＣのみであるからノードＣを確定ノードとして決定する。
【００６３】
図２２は、図１６に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡ,ノードＣの各リンクツリーコントロールテーブルを示す図である。図１６を参照して説明したノードＣの確定処理は、ノードＩＤ＝Ｄからのルートに基づく確定処理である。したがって、図２２に示すようにノードＩＤ＝Ｄのリンクエントリ部４２の次ノードリンクテーブルポインタ（アドレス記号１Ｌ１ＬＥ１−２）にノードＩＤ＝Ｃを示す「２Ｌ１ＨＮＩＤ」が格納される。
【００６４】
また、ノードＩＤ＝Ｄのリンクエントリ部４２の次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ１−３）を「０」から「接続」に更新される。なお、ノードＣのリンクコントロールテーブル６０のヘッダ部６１は、上述したヘッダ部３１、４１、５１と同様に生成されるため、説明は割愛する。
【００６５】
図１７は、図１６に示す探索処理の次の処理ステップ（一度Ｓ５でＮｏと判断され、Ｓ１〜Ｓ４を行なう状態）を反映した図である。この処理ステップでは、ノードＣに接続されているノードのリンクコストを求める。すなわち、スタート地点のノードＢからノードＥまでのリンクコストは、「Ｂ−Ｄ−Ｅ」ルートの総和が「１０」であり、「Ｂ−Ｄ−Ｃ−Ｅ」ルートの総和は「６」であるため、「Ｂ−Ｄ−Ｃ−Ｅ」ルートの方が最短経路となる。したがって、「Ｂ−Ｄ−Ｃ−Ｅ」ルートのリンクコストの経路を維持し、「Ｄ−Ｅ」間のリンクを切断する。そして、上述した確定処理と同様に未確定ノードでミニマムリンクコストであるノードＥを確定ノードとして決定する。
【００６６】
図２３は、図１７に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡ,ノードＣ,ノードＥの各リンクツリーコントロールテーブルを示す図である。図１７を参照して説明したノードＥの確定処理は、ノードＩＤ＝Ｃからのルートに基づく確定処理である。したがって、図２３に示すようにノードＩＤ＝Ｃのリンクエントリ部４７の次ノードリンクテーブルポインタ（アドレス記号２Ｌ１ＬＥ１−２）にノードＩＤ＝Ｅを示す「３Ｌ１ＨＮＩＤ」を格納して活性化する。また、ノードＩＤ＝Ｃのリンクエントリ部４７の次リンク評価結果フラグ（アドレス記号２Ｌ１ＬＥ１−３）を「０」から「接続」に更新する。なお、ノードＥのリンクコントロールテーブル４８のヘッダ部４９は、上述したヘッダ部３１、４１、４６、５１と同様に生成されるため、説明は割愛する。
【００６７】
なお、この処理時点以降の未確定ノードＦ、Ｊ、Ｇについての経路探索処理については、図２７に示すダイクストラ法に基づく最短経路探索処理フローや上述したリンクツリーコントロールテーブルの生成、更新処理と同様になされるため割愛するが、最終的には図５および図６に示すリンクツリーに対応した図８および図９に示す各リンクツリーコントロールテーブルが生成される。
【００６８】
続いて、リンク切断要因・区間を抽出する処理フローの概要について、図２８を参照しながら説明する。図２８は、リンク切断要因・区間を抽出する処理のフローチャートを示した図である。
【００６９】
まず、ユーザーが経路探索結果に疑問を抱いてルート選定の根拠を確認するために、経路探索根拠表示要求アイコンをクリックするなどして経路探索根拠表示要求が行なわれる（ＳＴＡＲＴ）。
【００７０】
すると、図１に示すリンク切断要因・区間格納手段１７は、スタートノードのリンクツリーコントロールテーブルにおける「リンク数」を参照する（ステップＳ１０）。
【００７１】
リンク切断要因・区間格納手段１７は、「リンク数」を参照して得た値だけリンクエントリの次ノード毎に「次リンク評価結果フラグ」の値を参照する（ステップＳ１１）。
【００７２】
そして、リンク切断要因・区間格納手段１７は、参照した「次リンク評価結果フラグ」の値の判定を行なう（ステップＳ１２）。リンク切断要因・区間格納手段１７は、参照した「次リンク評価結果フラグ」の値が「切断」となっていた場合には、「次リンク評価内容」の値を取得して図１に示した記憶手段１２に格納する（ステップＳ１４）。一方、リンク切断要因・区間格納手段１７は、参照した「次リンク評価結果フラグ」の値が「接続」となっていた場合には、更に「次リンクテーブルポインタ」の値を参照する（ステップＳ１３）。
【００７３】
リンク切断要因・区間格納手段１７は、「次リンクテーブルポインタ」の値に示されるアドレスにしたがって、次ノードの先頭アドレスを参照して次ノードの「全リンク切断フラグ」の値を参照する（ステップＳ１５）。そして、リンク切断要因・区間格納手段１７は、参照した「全リンク切断フラグ」の値の判定を行なう（ステップＳ１６）。
【００７４】
リンク切断要因・区間格納手段１７は、「全リンク切断フラグ」の値が「切断」となっていた場合には、「次リンク評価内容」の値を取得して図１に示した記憶手段１２に格納する（ステップＳ１４）。リンク切断要因・区間格納手段１７は、「全リンク切断フラグ」の値が「接続」となっていた場合には、更に当該次ノードの「リンク数」を参照する（ステップＳ１７）。
【００７５】
当該次ノードの「リンク数」を参照したリンク切断要因・区間格納手段１７は、判定処理を当該次ノードの「次リンク評価結果フラグ」を参照して同様に判定処理を続ける（ステップＳ１１）。
【００７６】
このようにして、リンク切断要因・区間格納手段１７は、リンク切断要因とリンク切断区間の情報を抽出して各々図１に示した記憶手段１２に適切に格納していく。そして図１に示した入出力表示手段１３に適切に表示させる。
【００７７】
以下に、リンク切断要因・区間格納手段１７を用いて格納された情報を利用して、経路探索結果の根拠情報をユーザーに対して提示する処理について図８および図９に示す各リンクツリーコントロールテーブルを参照しながら具体的に説明する。
【００７８】
まず、上述した最短経路探索処理により経路探索結果の表示が行なわれ、ユーザーがその経路探索結果に疑義が生じた場合を想定する。なお、カーナビゲーション装置１０の入出力表示手段１３によって経路探索結果が表示されると共に、図示しない経路探索根拠出力要求手段が表示されているものとする。たとえば、入出力表示手段１３は、カーナビゲーション装置１０の一部を構成するディスプレイであり、経路探索根拠出力要求手段は経路探索根拠出力要求アイコンがディスプレイに表示されているとする。
【００７９】
ユーザーが経路探索結果に疑問を抱いてルート選定の根拠を確認するために、経路探索根拠出力要求アイコンをクリックする。経路探索根拠出力要求アイコンがクリックされると、経路探索根拠出力表示要求信号が生成され、演算制御手段１１は、記憶手段１２に格納されているリンクツリーコントロールテーブル３０のリンク数（アドレス記号０ＬＨＮｏＬ）を参照して「２」を得る。
【００８０】
これは、スタート地点であるノードＢには２つのリンクエントリがあることを示すので、リンクエントリ部３２の次ノードについて次リンク評価結果フラグ（アドレス記号０ＬＬＥ１−３およびアドレス記号０ＬＬＥ２−３）についてそれぞれリンク切断要因やリンク切断区間情報等を抽出するための判定処理を行なう。
【００８１】
まず、次ノードＩＤ＝Ｄについての次リンク評価結果フラグ（アドレス記号０ＬＬＥ１−３）を確認する。次リンク評価結果フラグ（アドレス記号０ＬＬＥ１−３）に格納されている値は、「接続」であるため、接続されている次ノードについて更に判定処理を行なう。そこで、ヘッダ部３１の次ノードリンクテーブルポインタ（アドレス記号０ＬＬＥ１−２）を確認する。
【００８２】
次ノードリンクテーブルポインタ（アドレス記号０ＬＬＥ１−２）は、アドレス記号「１ＬＨＮＩＤ」となっているため、ノードＩＤ＝Ｄであるリンクツリーコントロールテーブル４０へ判定処理を移行して、ヘッダ部４１にある全リンク切断フラグ（アドレス記号１ＬＨＦ）の値を確認する。
【００８３】
ヘッダ部４１の全リンク切断フラグ（アドレス記号１ＬＨＦ）の値は、「接続」であるため、リンク数（アドレス記号１ＬＨＮｏＬ）の値「３」を取得して、リンクエントリ部４２の次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ１−３、１Ｌ１ＬＥ２−３、１Ｌ１ＬＥ３−３）についてそれぞれ判定処理を行なう。
【００８４】
次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ１−３）の値は、「切断」となっており、次リンク評価結果内容（アドレス記号１Ｌ１ＬＥ１−４）が初期値（＝０）でなければ、切断要因があると判定する。次リンク評価結果内容（アドレス記号１Ｌ１ＬＥ１−４）に格納されているデータ内容が「Ｅ−Ｇ間大渋滞」であるため、これを取得して図１に示した記憶手段１２に格納する。
【００８５】
同様に、次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ２−３）についても判定を行なう。次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ２−３）の値も、「切断」であるから、次リンク評価結果内容（アドレス記号１Ｌ１ＬＥ２−４）が、初期値（＝０）でなければ、切断要因があると判定する。次リンク評価結果内容（アドレス記号１Ｌ１Ｅ２−４）に格納されているデータ内容は「Ｄ−Ｅ間大渋滞」であるため、これを抽出して図１に示した記憶手段１２に格納する。
【００８６】
更に、次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ３−３）の判定を行なう。次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ３−３）は、「接続」となっているため、前述した処理と同様に、接続されている次ノードについて更に判定処理を行なっていく。
【００８７】
このようにして目的地までの全ての残存リンクエントリの判定処理を繰り返して「次リンク評価結果フラグ」の値が「切断」ならば「次リンク評価結果内容」を抽出して図１に示した記憶手段１２に格納する処理を繰り返す。
【００８８】
このような判定処理を繰り返すことで、ユーザーに対してリンク切断要因に関連する情報および／またはリンク切断区間に関連する情報を抽出して、経路探索結果と共に提供することができる。なお、抽出されたリンク切断要因に関連する情報および／またはリンク切断区間に関連する情報は、抽出順に入出力表示手段１３に表示してもよいし、所定数だけ表示させる制御をしてもよい。
【００８９】
たとえば、上述した判定処理により抽出した情報のはじめの３件だけを表示させる制御を行なう。このように制御することで、たくさんのリンク切断要因等の情報があったとしても、ユーザーが一見して把握することができる出力件数に絞ることができる。また無駄にカーナビゲーション装置１０を注視することがなくなる。
【００９０】
なお、これらの判定処理によって抽出されたリンク切断要因等の情報について、当該リンクツリーの総和となるリンクコストの値のなかでリンク切断要因等の情報が占めるリンクコストの割合によって出力表示の制御を行なってもよい。たとえば、当該リンクコストが一定の閾値以上（たとえばリンクコスト値の総和の２０％以上を占める値をもつリンク切断要因など）である情報のみを表示させる制御を行なってもよい。
【００９１】
また、車速センサから車両速度を周期的に取得して、取得した速度データが一定の速度以上となった場合には、表示する件数を減少させたり、一定の速度未満となった場合には表示する件数を増加させたりする制御をおこなってもよい。このような制御をすることで、安全運転に配慮した好ましいナビゲーション装置を提供することができる。
【００９２】
上述したように本発明に係る第１の実施形態であるナビゲーション装置１０は、ユーザーが仮に経路探索結果に疑問を感じたとしても、的確にその根拠情報を抽出して経路探索結果と共に提示することができるため、ユーザーが特定区間の道路条件について十分な情報を持っているか否かに関わらず、提示した経路探索結果に対して納得させることができ、かつストレスを感じさせずに安全運転を支援することができる。
【００９３】
続いて、本発明に係る第２の実施形態であるナビゲーション装置７０について説明する。図２４は、本発明に係る第２の実施形態であるナビゲーション装置７０の概要構成を示したブロック図である。
【００９４】
ナビゲーション装置７０は、本発明に係る第１の実施形態であるカーナビゲーション装置１０の有する手段に加えて、経路探索根拠出力要求手段７８を有する。なお、図２４に示された他の各手段についてはカーナビゲーション装置１０と同じ機能であること、最短経路探索処理やリンクツリーコントロールテーブルの生成方法やリンク切断要因・区間を抽出して格納する処理についても同様であることから、これらの説明は割愛する。
【００９５】
経路探索根拠出力要求手段７８は、ユーザー側から経路探索根拠を要求することができる機能を備えている。たとえばカーナビゲーション装置７０の入出力表示手段７３に常に経路探索根拠出力要求手段７８を表示させておく。具体的には、経路探索根拠出力要求ボタンや経路探索根拠出力要求アイコンをディスプレイに備えさせるなどの具体例が挙げられる。なお、本発明に係る第２の実施形態における経路探索根拠出力要求手段７８は、カーナビゲーション装置７０に内蔵されているまたは機能的に内包されているが、外部に経路探索根拠出力要求ができるリモコン、通信端末機器などを設けて双方向通信を行なって機能させてもよい。
【００９６】
なお、経路探索根拠出力要求手段７８に加えて、過去に行なった経路探索結果を参照できるように経路探索履歴保持手段を更に設けて、過去の経路探索根拠を記憶手段７２に記録して、ユーザー側から参照できるように構成してもよい。
【００９７】
このような手段を設けることにより、経路探索表示結果を出力するタイミングでそのリンク切断要因等の根拠を知ることができるという態様ではなく、ユーザー自身が経路探索に疑義が生じたとき（たとえば経路探索が終了してしばらく経路に即して走行していたが不意に疑問を感じたとき）いつでもその経路探索結果の根拠を知ることができる。したがって、本発明に係る第1の実施形態の有する効果に加えて、よりユーザー側の視点に基づいたカーナビゲーション装置を提供することができる。
【００９８】
更に、本発明に係る第３の実施形態であるカーナビゲーション装置８０について説明する。図２５は、本発明に係る第３の実施形態であるカーナビゲーション装置８０の概要構成を示したブロック図である。
【００９９】
カーナビゲーション装置８０は、本発明に係る第１の実施形態であるカーナビゲーション装置１０と同じ機能を有する手段に加えて、探索経路登録保持手段８８と、リンクコスト再計算手段８９と、経路変更根拠格納手段９０と、を有する。
【０１００】
探索経路登録保持手段８８は、一度最短経路探索処理を行なって生成されたリンクツリーコントロールテーブルを記憶手段８２に格納しておく機能を備えている。
【０１０１】
リンクコスト再計算手段８９は、再度同じ最短経路探索処理がユーザーの操作により行なわれたときに、自動的に再度選択可能な各ノード間のリンクコストを再計算する機能を備えている。
【０１０２】
経路変更根拠格納手段９０は、リンクコスト再計算手段８９により再計算した結果に基づいて最短経路探索処理を行なった結果であるリンクツリーコントロールテーブルが、探索経路登録保持手段８８に登録されているリンクツリーコントロールテーブルと比較して異なる構成となった場合に、その異なる構成となった根拠を抽出して記憶手段８２に格納する機能を備えている。なお、その異なる構成となった根拠を抽出する場合に、抽出した根拠の順に表示する、抽出した根拠のうち所定数のみ表示する、所定の閾値以上のリンクコストである根拠だけを表示する、車速により表示する根拠の表示件数を変更するといった制御を行なってもよい。
【０１０３】
このような手段を設けることにより、再度同じ最短経路探索処理がユーザーの操作により選択されたときに、同じ経路であってもリンクコストに変化が生じていないかをチェックでき、かつ仮に、経路に変化が生じていた場合であっても、その根拠を抽出して経路探索処理結果と共にその根拠情報を提供することができる。したがって、カーナビゲーション装置８０は、同一の経路について過去に提示した探索経路結果と異なる結果を提示することになるような特殊な状況が発生したとしても、ユーザーがそのような特殊な状況について十分な情報を持っているか否かに関わらず、提示した経路探索結果に対して納得させることができ、かつストレスを感じさせずに安全運転を支援することができる。
【０１０４】
更に、本発明に係る第４の実施形態であるカーナビゲーション装置１００について説明する。図２６は、本発明に係る第４の実施形態であるカーナビゲーション装置１００の概要構成を示したブロック図である。
【０１０５】
カーナビゲーション装置１００は、本発明に係る第２の実施形態であるカーナビゲーション装置７０と同じ機能を有する手段に加えて、探索経路登録保持手段１０８と、リンクコスト再計算手段１０９と、経路変更根拠格納手段１１０と、経路探索根拠出力要求手段１１１と、を有する。
【０１０６】
なお、探索経路登録保持手段１０８,リンクコスト再計算手段１０９および経路変更根拠格納手段１１０の機能説明および効果は、上述した探索経路登録保持手段８８,リンクコスト再計算手段８９および経路変更根拠抽出手段９０と同様であるため、これらの説明は割愛する。また、経路探索根拠出力要求手段１１１の機能説明および効果は、上述した経路探索根拠出力要求手段７８と同様であるため、説明は割愛する。
【０１０７】
これらの手段を設けることによって、カーナビゲーション装置１００は、よりユーザー側の視点に基づいた仕様となる。また、カーナビゲーション装置１００は、ユーザーが特定区間の道路条件について十分な情報を持っているか否かに関わらず、いつでも提示された経路探索結果に対してその根拠を知って納得させることができる。したがって、カーナビゲーション装置１００は、ユーザーにストレスを感じさせずに安全運転を支援することができる。
【０１０８】
以上、本発明に係る第１の実施形態から第４の実施形態について説明をしたが、本発明はその要旨を逸脱しない限り種々変更実施できる。
【０１０９】
たとえば、本発明に係る第１の実施形態から第４の実施形態における特定の２点間における最短経路探索アルゴリズムとしてダイクストラ法を採用しているが、実施形態によって他のアルゴリズムを採用して構築しても勿論よい。
【０１１０】
また、上述した本発明に係る第１の実施形態から第４の実施形態では、カーナビゲーション装置の各機能を特定のハードウェアを指定して機能別手段として行なわせているが、全ての機能手段または一部の機能手段をプログラムからなるソフトウェアで処理・実行させるようにしても勿論よい。
【産業上の利用可能性】
【０１１１】
本発明は、全てのナビゲーション装置に適用できる。本発明は、特に車に搭載されたカーナビゲーション装置として利用できる。
【図面の簡単な説明】
【０１１２】
【図１】本発明に係る第１の実施形態であるカーナビゲーション装置の概要構成を示したブロック図である。
【図２】単純モデル化したある道路網を示す図である。
【図３】図２で示した道路網についてダイクストラ法に基づいて最短経路探索処理結果を示した図である。
【図４】図２で示した道路網であって、特定の状況変化が生じた道路網を示す図である。
【図５】図４で示した特定の状況変化が生じた道路網についてダイクストラ法に基づいて最短経路探索処理結果を示した図である。
【図６】図５に示す最短経路探索処理結果に基づくリンクツリーを示す図である。
【図７】リンクツリーコントロールテーブルの基本構造を説明するための図である。
【図８】図６に示すリンクツリーに対応したリンクツリーコントロールテーブルを示す図である。
【図９】図６に示すリンクツリーに対応したリンクツリーコントロールテーブルを示す図である。
【図１０】図４に示した道路網であり、最短経路探索処理結果を単純モデル化して示した図である。
【図１１】図４に示した道路網であり、図１０に示す最短経路探索処理結果に次の処理ステップ（Ｓ１）を反映した図である。
【図１２】図４に示した道路網であり、図１１に示す最短経路探索処理結果に次の処理ステップ（Ｓ２）を反映した図である。
【図１３】図４に示した道路網であり、図１２に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。
【図１４】図４に示した道路網であり、図１３に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。
【図１５】図４に示した道路網であり、図１４に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。
【図１６】図４に示した道路網であり、図１５に示す最短経路探索処理結果に次の処理ステップ（Ｓ４）を反映した図である。
【図１７】図４に示した道路網であり、図１６に示す最短経路探索処理結果に次の処理ステップ（一度Ｓ５でＮｏと判断され、Ｓ１〜Ｓ４を行なう状態）を反映した図である。
【図１８】スタート地点であるノードＢのリンクツリーコントロールテーブルと、ノードＢに接続されているノードＤのリンクツリーコントロールテーブルと、ノードＢに接続されているノードＡのリンクツリーコントロールテーブルと、を示す図である。
【図１９】図１０〜図１３までの最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡの各リンクツリーコントロールテーブルを示す図である。
【図２０】図１４に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡの各リンクツリーコントロールテーブルを示す図である。
【図２１】図１５に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡの各リンクツリーコントロールテーブルを示す図である。
【図２２】図１６に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡ,ノードＣの各リンクツリーコントロールテーブルを示す図である。
【図２３】図１７に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡ,ノードＣ,ノードＥの各リンクツリーコントロールテーブルを示す図である。
【図２４】本発明に係る第２の実施形態であるカーナビゲーション装置の概要構成を示したブロック図である。
【図２５】本発明に係る第３の実施形態であるカーナビゲーション装置の概要構成を示したブロック図である。
【図２６】本発明に係る第４の実施形態であるカーナビゲーション装置の概要構成を示したブロック図である。
【図２７】ダイクストラ法に基づく最短経路探索処理フローを簡単に示した図である。
【図２８】リンク切断要因・区間を抽出する処理のフローチャートを示した図である。
【符号の説明】
【０１１３】
ナビゲーション装置 １０、７０、８０、１００
演算制御部 １１、７１、８１、１０１
記憶手段 １２、７２、８２、１０２
入出力表示手段１３、７３、８３、１０３
リンクコスト算出手段 １５、７５、８５、１０５
リンクコスト再計算手段 ８９，１０９
経路探索手段 １６、７６、８６、１０６
探索経路登録保持手段 ８８、１０８
リンク切断要因・区間格納手段 １７、７７、８７、１０７
経路探索根拠出力要求手段 ７８、１１１
経路変更根拠格納手段 ９０，１１０
【技術分野】
【０００１】
本発明は、ナビゲーション装置およびそのプログラムに関する。
【背景技術】
【０００２】
ナビゲーション装置において、たとえば車に使用されるカーナビゲーション装置の経路探索方法には、有料道路優先、一般道路優先、有料道路回避、距離優先、時間優先等がある。また、歩行ナビゲーション装置の経路探索方法には、距離優先、屋根の多い道路優先、階段が少ない道路優先、坂道のなだらかな道路優先等がある。このような経路探索方法を採用したナビゲーション装置を使用するユーザーは、自分の知っている道より遠回りとなる結果が当該ナビゲーション装置から提示されると、提示されたルートに対してなぜそのようなルートが提示されるのかという疑義が生じる。更に、このような疑義が一度生じてしまうとそのユーザーの知っている情報が正しいか否かに関わらず、当該ナビゲーション装置の性能に対しても不信感を募らせるため、ＣＳ（Ｃｕｓｔｏｍｅｒ Ｓａｔｉｓｆａｃｔｉｏｎ：顧客満足）の観点から好ましくない。このような状況を未然に防止するため、特定区間の経路について設定条件を変更しながら経路探索を完結させる区間条件設定機能を備えたカーナビゲーション装置が知られている（特許文献１参照）。
【０００３】
【特許文献１】特開２００６−２００９８１号公報（特許請求の範囲、発明の実施の形態、段落００１７など）
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１に開示されているカーナビゲーション装置は、特定区間の道路条件について十分な情報を持っているユーザーでなければ、上述した区間条件設定機能を用いて適切に設定し直すことができない。また、仮に特定区間の道路条件について十分な情報を持っているユーザーであっても、交通規制や混雑状況などは時々刻々とダイナミックに変化するため、知り得ない情報が存在する場合もある。したがって、特定区間の道路条件について十分な情報を持っていないユーザーであるか否かに関わらず、提示された経路に対して何らかの疑問を抱いてそれを解消することができないときは、ストレスとなって間接的に安全運転上の支障をきたす恐れがある。
【０００５】
本発明の目的は、このような課題を解決すべく、ユーザーが特定区間の道路条件について十分な情報を持っているか否かに関わらず、提示した経路探索結果に対して納得させることができ、かつストレスを感じさせずに安全運転を支援するナビゲーション装置およびそのプログラムを提供することにある。
【課題を解決するための手段】
【０００６】
本発明は上述した目的を達成するために、経路探索をするための情報を格納する記憶手段と、記憶手段に格納された情報から各ノード間のリンクコストを算出するリンクコスト算出手段と、リンクコスト算出手段により算出されたリンクコストに基づいて複数の経路より一の経路を選択する経路探索手段と、経路探索手段によって選択されなかったノードのリンク切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納するリンク切断要因・区間格納手段と、リンク切断要因・区間格納手段により抽出して格納された情報を経路探索結果と共に表示する入出力表示手段と、を有するナビゲーション装置である。
【０００７】
他の発明は、経路探索をするための情報を格納する記憶手段と、記憶手段に格納された情報から各ノード間のリンクコストを算出するリンクコスト算出手段と、リンクコスト算出手段により算出されたリンクコストに基づいて複数の経路より一の経路を選択する経路探索手段と、経路探索手段によって選択されなかったノードのリンク切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納するリンク切断要因・区間格納手段と、リンク切断要因・区間格納手段に抽出して格納された情報を出力するように指示する経路探索根拠出力要求手段と、を有するナビゲーション装置である。
【０００８】
また他の発明は、上述した発明に加えて、経路探索手段により選択された一の経路を構成する各ノード情報および／または各ノード区間のリンクコストを記憶手段へ格納する探索経路登録保持手段と、探索経路登録保持手段に格納された一の経路が呼び出されたときに一の経路のリンクコストを再計算するリンクコスト再計算手段と、リンクコスト再計算手段に基づいて決定された経路が一の経路と異なることとなったとき、一の経路を構成する各ノードのうちリンクが切断された切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納する経路変更根拠格納手段と、経路変更根拠格納手段により抽出して格納された情報を経路探索結果と共に表示する入出力表示手段と、を有するナビゲーション装置である。
【０００９】
また他の発明は、上述した発明に加えて、経路探索手段により選択された一の経路を構成する各ノード情報および／または各ノード区間のリンクコストを記憶手段に格納する探索経路登録保持手段と、探索経路登録保持手段に格納された一の経路が呼び出されたときに一の経路のリンクコストを再計算するリンクコスト再計算手段と、リンクコスト再計算手段に基づいて決定された経路が一の経路と異なることとなったとき、一の経路を構成する各ノードのうちリンクが切断された切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納する経路変更根拠格納手段と、経路変更根拠格納手段により抽出して格納された情報を出力するように指示できる経路探索根拠出力要求手段と、を有するナビゲーション装置である。
【００１０】
また他の発明は、上述したナビゲーション装置のいずれか一つの装置として機能させるプログラムである。
【発明の効果】
【００１１】
本発明は、ユーザーが特定区間の道路条件について十分な情報を持っているか否かに関わらず、提示した経路探索結果に対して納得させることができ、かつストレスを感じさせずに安全運転を支援するナビゲーション装置およびそのプログラムを提供することができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明に係る第１の実施形態について説明する。図１は、本発明に係る第１の実施形態であるカーナビゲーション装置１０の概要構成を示したブロック図である。
【００１３】
図１に示すようにカーナビゲーション装置１０は、演算制御手段１１と、記憶手段１２と、入出力表示手段１３と、自己位置検出手段１４と、リンクコスト算出手段１５と、経路探索手段１６と、リンク切断要因・区間格納手段１７と、を有する。以下、カーナビゲーション装置１０を構成する各手段について説明する。
【００１４】
演算制御手段１１は、カーナビゲーション装置１０を搭載している車両の現在地についての算出処理,地図の描画処理,目的地検索処理,経路検索処理などの各種演算処理や、それらの各処理の制御処理を行なう機能を備えている。演算制御手段１１を構成するものとして、たとえばＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などが具体例として挙げられる。
【００１５】
記憶手段１２は、道路網の様々な情報を格納する機能を備えている。たとえば、高速自動車国道，都市高速道路，一般国道，主要地方道，一般都道府県道，市町村道，農道，林道などの道路種別情報、車線数，歩道の有無，交通規制，渋滞具合などの道路属性情報と、Ｍランク（自動車専用道路），Ｓランク（とても走りやすい），Ａランク（走りやすい），Ｂランク（やや走りやすい），Ｃランク（やや走りにくい），Ｄランク（走りにくい）といった走りやすさのランク情報、全長，全幅，全高などの車両情報、「幅の広めの一車線道路を好む」，「複数車線道路を好む」などのドライバーの特性情報等を格納している。これらの情報は、後述するリンクコストを決定する要素として用られる。なお、記憶手段１２を構成するものとして、たとえばハードディスク,フレキシブルディスク,ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）メモリなどの外部記憶装置や、磁気テープ,ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｃ）,ＭＤ（Ｍｉｎｉ Ｄｉｓｋ）,ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）,光ディスクなどの外部記憶媒体、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄａｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）などが具体例として挙げられる。
【００１６】
入出力表示手段１３は、地図や案内情報を出力表示する機能や、カーナビゲーション装置１０を操作するための信号を入力する機能を備えている。入出力表示手段１３は、たとえばディスプレイやタッチパネル、これらの画面上に表示されたブラウザ，ウィンドウ，ラジオボタン,アイコンなどが具体例として挙げられる。
【００１７】
自己位置検出手段１４は、カーナビゲーション装置１０を搭載している車両の位置を検出する機能を備えている。自己位置検出手段１４は、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）,ジャイロスコープ（ｇｙｒｏｓｃｏｐｅ）,車速パルスなどのカーナビゲーションに用いられる加速度センサが具体例として挙げられる。
【００１８】
リンクコスト算出手段１５は、選択可能な地点のリンクコストをそれぞれの区間において算出する機能を備えている。ここでリンクコストとは、道路を構成するそれぞれの地点間の各種情報を加味した相対的な数値情報である。たとえば、上述した道路種別情報,道路属性情報,走りやすさのランク情報,車両情報,ユーザーの特性情報などから各地点間のリンクコストを算出する。なお、リンクコストの具体的な算出方法については本発明の主旨から外れるため、割愛する。
【００１９】
経路探索手段１６は、スタート地点と目的地（ゴール地点）を取得して、リンクコスト手段１５によって算出されたリンクコストに基づいて当該区間におけるリンクコストが最も小さくなる経路（ある設定条件下における経路の中でもっとも条件を満たす経路＝最短となる経路）を求める機能を備えている。また、経路探索手段１６は、自己位置検出手段１４により取得した座標データ（スタート地点）と、入出力表示手段１３によって指示された目的地情報（ゴール地点）を取得した時点で最短経路探索処理を開始する機能を備えている。また、スタート地点は上記データ以外に入出力表示手段１３をユーザーが直接操作して、入力された地点情報や座標データとしてもよい。
【００２０】
リンク切断要因・区間格納手段１７は、経路探索手段１６による探索でリンク切断要因となった情報と、リンク切断該当区間情報を抽出して記憶手段１２に格納する機能を備えている。具体的な処理の説明については、続いて行なうカーナビゲーション装置１０の動作説明の中で説明する。
【００２１】
なお、上述した自己位置検出手段１４、リンクコスト算出手段１５、経路探索手段１６、リンク切断要因・区間格納手段１７が行なう情報処理は、それぞれ演算制御手段１１,記憶手段１２,入出力表示手段１３といったハードウェア資源を用いて実行され、演算処理、制御処理、記憶処理、入出力処理といった各種の処理を行ない、協働して動作することによりカーナビゲーション装置１０を構成している。また、自己位置検出手段１４、リンクコスト算出手段１５、経路探索手段１６、リンク切断要因・区間格納手段１７は、上記のハードウェア資源において各種のデータ・プログラムが実行されることにより機能的に実現されるが、専用の処理回路によって実現するようにしてもよい。
【００２２】
続いて、上述した各手段に基づいて本発明の第１の実施形態に係るカーナビゲーション装置１０の動作説明を行なう。なお、本発明の第１の実施形態であるカーナビゲーション装置１０はダイクストラ法に基づく経路の探索処理方法を採用している。しかし、本実施形態の各手段は、その探索処理の結果として生成されるリンクツリーに対応した情報処理を実現するために構築される。したがって、ダイクストラ法そのもののアルゴリズムについての詳細な説明は本発明の主旨から外れるため、割愛する。
【００２３】
図１に示す記憶手段１２には、上述した最短経路探索処理を行なうにあたって必要なデータが蓄積されており、これらのデータに基づいて、有料道路優先、一般道路優先、有料道路回避、距離優先、時間優先等の条件設定されたいくつかのカテゴリ規準に基づいてリンクコストを算出して、最短経路探索処理を実行していく。その処理過程においていくつかの候補となる経路が生成される。
【００２４】
はじめに上述した条件設定の詳細については考えずに、単純にリンクコストが算出された後の最短経路探索処理について説明する。図２は、単純モデル化したある道路網を示す図である。図３は、図２で示す道路網についてダイクストラ法に基づいた最短経路探索処理結果を示す図である。
【００２５】
以下に、カーナビゲーション装置１０の入出力表示手段１３に経路探索処理結果が提示されるまでの過程を説明する。図２に示す道路網では、経路探索処理過程で候補となるスタート地点Ｂからゴール地点Ｇまでのルートは、下記〔１〕〜〔６〕の６つの経路が考えられる。下記の通り、各ルートの矢印の下に該当リンクコストを明示してそれぞれの総和を求めると、
〔１〕Ｂ → Ａ → Ｃ → Ｅ → Ｇ
２ ＋ ２ ＋ １ ＋ ２ ＝７
〔２〕Ｂ → Ｄ → Ｃ → Ｅ → Ｇ
１ ＋ ４ ＋ １ ＋ ２ ＝８
〔３〕Ｂ → Ｄ → Ｅ → Ｇ
１ ＋ ３ ＋ ２ ＝ ６
〔４〕Ｂ → Ｄ → Ｅ → Ｆ → Ｊ → Ｇ
１ ＋ ３ ＋ ３ ＋ ２ ＋ １ ＝１０
〔５〕Ｂ → Ｄ → Ｆ → Ｊ → Ｇ
１ ＋ ６ ＋ ２ ＋ １ ＝１０
〔６〕Ｂ → Ｄ → Ｆ → Ｅ → Ｇ
１ ＋ ６ ＋ ３ ＋ ２ ＝１２
となり、〔３〕の経路が最もリンクコストが小さくなる。したがって、カーナビゲーション装置１０の入出力表示手段１３から、図３に示すように〔３〕の経路である「Ｂ→Ｄ→Ｅ→Ｇ」のルートが最短の経路探索処理結果として提示される。
【００２６】
続いて、図２で示した道路網にダイナミックに交通規制が発生してリンクコストが変化した場合を考える。図４は、図２で示したある道路網に特定の状況変化が生じた図である。具体的にはＡ−Ｃ間で工事による通行規制が実施されており、Ｄ−Ｅ間、Ｅ−Ｇ間に大渋滞が発生して走行時間が過大になったという状況を想定している。図５は、図４で示した特定の状況変化が生じたある道路網についてダイクストラ法に基づいた最短の経路探索結果を示す図である。
【００２７】
リンクコストが変更になった地点およびリンクコストの総和が変化したルートについては下線を引いて表すものとして、それぞれの総和を前述した〔１〕〜〔６〕の経路におけるリンクコストの総和を計算したときと同様に求めると、
〔１１〕Ｂ → Ａ → Ｃ → Ｅ → Ｇ
２ ＋ ７ ＋ １ ＋ ８ ＝１８
〔１２〕Ｂ → Ｄ → Ｃ → Ｅ → Ｇ
１ ＋ ４ ＋ １ ＋ ８ ＝１４
〔１３〕Ｂ → Ｄ → Ｅ → Ｇ
１ ＋ ９ ＋ ８ ＝ １８
〔１４〕Ｂ → Ｄ → Ｅ → Ｆ → Ｊ → Ｇ
１ ＋ ９ ＋ ３ ＋ ２ ＋ １ ＝１６
〔１５〕Ｂ → Ｄ → Ｆ → Ｊ → Ｇ
１ ＋ ６ ＋ ２ ＋ １ ＝１０
〔１６〕Ｂ → Ｄ → Ｆ → Ｅ → Ｇ
１ ＋ ６ ＋ ３ ＋ ８ ＝１８
となり、〔１５〕の経路が最もリンクコストが小さくなる。したがって、図５に示すようにカーナビゲーション装置１０の入出力表示手段１３から、この〔１５〕の経路である「Ｂ−Ｄ−Ｆ−J−Ｇ」のルートが経路探索処理結果として提示される。
【００２８】
図６は、図５に示す最短経路探索処理によりリンクが切断された地点を除いて整理したリンクツリーを示す図である。図８および図９は、図６で示すリンクツリーに対応したリンクツリーコントロールテーブルを示す図である。
【００２９】
カーナビゲーション装置１０では、図６に示すリンクツリーに対応した各リンクツリーコントロールテーブルが生成される。なお、ここでリンクツリーとは、ダイクストラ法による経路探索により生成された最短ルートを概念的に示したものである。また、リンクツリーコントロールテーブルとは、そのリンクツリーに対応してカーナビゲーション装置１０内で生成される論理構造データである。したがって、記憶手段１２には、図８及び図９に示すリンクツリーコントロールテーブルの論理構造データと共に、論理構造データにしたがって各地点に関連する情報が格納されることになる。なお、以下の説明では経路探索上の各地点のことを「ノードＡ、ノードＢ、ノードＣ・・・」という形式で表現し、ノードが格納される各論理アドレスについては「アドレス記号×××××」という表現形式を用いて説明する。
【００３０】
図７は、リンクツリーコントロールテーブル２０の基本構造を説明するための図である。リンクツリーコントロールテーブル２０は、各ノードに対応して生成される論理構造データである。個々のノードのリンクツリーコントロールテーブル２０は、図７に示すようにヘッダ部２１と複数のリンクエントリ部２２から構成される。リンクツリーコントロールテーブル２０では、ヘッダ部２１がはじめに生成される。そして、ヘッダ部２１が生成された後に、はじめてリンクエントリ部２２を複数生成することができる。なお、これらの論理構造データは、カーナビゲーション装置１０の演算処理手段１１を用いて生成または更新され、記憶手段１２に適切に格納される。以下の説明においてもこのような情報処理が適宜なされていることを前提に説明する。
【００３１】
ヘッダ部２１は、主にノード属性情報を格納するための領域であり、図７に示すように４つのパラメータから構成される。すなわちヘッダ部２１は、ノード自体を識別する「ノードＩＤ」（アドレス記号０ＬＨＮＩＤ）と、当該ノードに接続されている他のノードの数を示す「リンク数ｎ」（アドレス記号０ＬＨＮｏＬ）と、当該ノードの前ノードのアドレスを示す「前ノードリンクテーブルポインタＢＰ１」（アドレス記号０ＬＨＢＰ）と、当該ノードに接続されている他のノードがすべて切断されているか否かを判別するための「全リンク切断フラグＦ」（アドレス記号０ＬＨＦ）と、から構成される。
【００３２】
リンクエントリ部２２は、主に当該ノードに関連するノード情報について格納される領域であり、当該ノードに接続されているリンクに対応してその数だけ生成される。リンクエントリ部２２は、図７に示すように４つのパラメータで構成される。すなわち、リンクエントリ部２２は、当該ノードの次に接続されているノードを示す「次ノードＩＤ」（アドレス記号０ＬＬＥ１−１）と、次ノードＩＤによって構成されるリンクツリーコントロールテーブルの先頭アドレスを示す「次ノードリンクテーブルポインタ」（アドレス記号０ＬＬＥ１−２）と、最短経路探索処理過程において次のノードへのリンクの接続有無を格納する「次リンク評価結果フラグ」（アドレス記号０ＬＬＥ１−３）と、リンク切断に至った理由を格納する「次リンク評価結果内容」（アドレス記号０ＬＬＥ１−４）と、から構成される。なお、次リンク評価結果内容に格納されるリンク切断理由についてはリンクコストを形成する要因の大きいものから一つまたは複数個を格納することができる。また、その格納できる個数は別途定義してもよい。更に経路探索をおこなった結果求められたリンクコストの総和に対して上述した要因が占めるリンクコストの割合に所定の閾値を設定して、その所定の閾値以上であるリンクコストの値をもつ要因であれば次リンク評価結果内容に格納するといった方法を採用してもよい。
【００３３】
続いて、ダイクストラ法に基づく最短経路探索処理フローについて図２７を参照しながら説明する。図２７は、ダイクストラ法に基づく最短経路探索処理フローを簡単に示した図である。
【００３４】
まず、経路探索手段１６は、スタート地点とゴール地点が決定されると経路探索処理を開始する（ＳＴＡＲＴ）。
【００３５】
経路探索手段１６は、スタート地点に接続されているノードのリンクコストをリンクコスト算出手段１５によって算出された値を参照して設定する。なお、スタート地点のリンクコストは「０」と設定し、他のノードのリンクコストは最大値（∞）と設定する（ステップＳ１）。
【００３６】
そして、経路探索手段１６は、スタート地点のノードからミニマムリンクコストであるノードを決定する（ステップＳ２）。
【００３７】
続いて、経路探索手段１６は、スタート地点からのリンクコストの総和を算出して、経路比較を行い、不要なリンクを切断する（ステップＳ３）。
【００３８】
最後に、経路探索手段１６は、未確定ノードのなかでミニマムリンクコストであるノードを確定ノードとする（ステップＳ４）。
【００３９】
経路探索手段１６は、上述したステップＳ１〜ステップＳ４までの処理を目的地（ゴール地点）のノードにたどり着くまで繰り返す（ステップＳ５）。
【００４０】
一方、ステップＳ１〜ステップＳ５に示す処理に対応して、経路探索手段１６は、各ノードのリンクツリーコントロールテーブルを構成する図示しないヘッダ部とリンクエントリ部を生成、または更新する。そして、経路探索手段１６は、最終的に上述した図６に示すリンクツリーに対応した図８および図９に示すリンクツリーコントロールテーブルを生成する。以下に、図８および図９に示すリンクツリーコントロールテーブルが生成されるまでの処理過程を具体的に説明する。
【００４１】
図１０は、図４に示した道路網であり、最短経路探索処理結果を単純モデル化して示した図である。図１０に示すようにノードＢのリンクコストは、スタート地点であるため「０」と設定される。また、他のノードのリンクコストは、「最大値（∞）」として設定される。
【００４２】
図１１は、図１０に示す最短経路探索処理結果に次の処理ステップ（Ｓ１）を反映した図である。この処理ステップでは、スタート地点であるノードＢに接続されている各ノードのリンクコストを求める。すなわちノードＢに接続されているノードは、図１１に示すようにノードＡとノードＤであるから、ノードＡとノードＤのリンクコストを求める。図１１よりノードＤのリンクコストは「１」、ノードＡのリンクコストは「２」である。なお、これらのリンクコストは、上述したリンクコスト算出手段１５により算出されて記憶手段１２に適切に格納されているものとする。
【００４３】
図１８は、スタート地点であるノードＢ、ノードＢに接続されているノードＤ、ノードＢに接続されているノードＡの各リンクツリーコントロールテーブルを示す図である。
【００４４】
図１８に示される各リンクツリーコントロールテーブルは、上述した図１１に示す最短経路探索処理結果までを反映した図である。以下、ノードＢのリンクツリーコントロールテーブル３０、ノードＤのリンクツリーコントロールテーブル４０、ノードＡのリンクツリーコントロールテーブル５０について具体的に説明する。
【００４５】
図１８に示すノードＢのヘッダ部３１におけるノードＩＤ（アドレス記号０ＬＨＮＩＤ）には、ノードＩＤ＝Ｂが格納されている。リンク数ｎ（アドレス記号０ＬＨＮｏＬ）には、「２」が格納されている。これはノードＢに、ノードＡとノードＤが接続されているため、リンクエントリ（接続）が２つ存在することを宣言（意味）している。前ノードリンクテーブルポインタ（アドレス記号０ＬＨＢＰ）には、初期値である「０」が格納されている。ノードＢは、スタート地点のノードであり、前リンクが存在しないためである。なお、カーナビゲーション装置１０のプログラミング規約に則って設定されていればこの値は何でも良いことは言うまでもない。全リンク切断フラグＦ（アドレス記号０ＬＨＦ）には、初期値である「０」が格納されている。なお、ノードＢへのリンク全てが未接続または切断されているときに「切断」と、一つのノードでもノードＢへ接続されていれば「接続」という値に変更される。このようにしてリンクツリーコントロールテーブル３０のヘッダ部３１について生成が行なわれる。
【００４６】
次に、ノードＢのリンクエントリ部３２について生成が行なわれる。リンクエントリ部３２は、上述したリンク数ｎ（アドレス記号０ＬＨＮｏＬ）に格納されている値「２」に従って、２エントリ生成される。一つ目のエントリである次ノードＩＤ（アドレス記号０ＬＬＥ１−１）には、次ノードを示すＤが格納されている。二つ目のエントリである次ノードＩＤ（アドレス記号０ＬＬＥ２−１）には、次ノードのＩＤ＝Ａが格納されている。
【００４７】
続いて、リンクツリーコントロールテーブル４０のヘッダ部４１が生成される。そして、リンクツリーコントロールテーブル３０の次ノードリンクテーブルポインタ（アドレス記号０ＬＬＥ１−２）には、アドレス記号１ＬＨＮＩＤが格納される。これによりノードＢのリンクツリーコントロールテーブル３０とノードＤのリンクツリーコントロールテーブル４０とのコントロールテーブルリンクが確立される。
【００４８】
ヘッダ部３１の次リンク評価結果フラグ（アドレス記号０ＬＬＥ１−３）には、ノードＩＤ＝Ｄのヘッダ部４１が生成されたため、初期値である「０」から「接続」に値が変更される。次リンク評価結果内容（アドレス記号０ＬＬＥ１−４）は、次ノードのリンク評価をしていないため、初期値の「０」が格納されている。
【００４９】
一方、前述のノードＩＤ＝Ｄのヘッダ部４１におけるリンク数（アドレス記号１Ｌ１ＨＮｏＬ）は、まだヘッダ部４１のみしか生成されていないため、初期値である「０」が格納される。ヘッダ部４１の前ノードリンクテーブルポインタ（アドレス記号１Ｌ１ＨＢＰ）には、ノードＩＤ＝Ｂのテーブルの先頭アドレス記号０ＬＨＮＩＤが格納される。これにより、ノードＢのリンクツリーコントロールテーブル３０とノードＤのリンクツリーコントロールテーブル４０とのリバースリンクが確立される。尚、全リンク切断フラグ（アドレス記号１ＬＨＦ）は、この時点で図示しないリンクエントリ部が生成されていないため、初期値である「０」が格納される。続いて、ノードＩＤ＝Ａのリンクツリーコントロールテーブル５０のヘッダ部５１が生成されるが、ノードＩＤ＝Ｄのヘッダ部４１と同様に生成されるため、生成の詳細な説明は割愛する。
【００５０】
図１２は、図１１に示す最短経路探索処理結果に次の処理ステップ（Ｓ２）を反映した図である。この処理ステップではノードＢからリンクコストが最小（ミニマムリンクコスト）となるノードを求める。すなわち、ノードＢからのリンクコストが最小となるノードを確定ノードとする処理である。図１１に示すようにノードＡのリンクコストが「２」であり、ノードＤのリンクコストが「１」であるため、ミニマムリンクコストとなるノードすなわち確定ノードは、ノードＤとなる。このように、最小のリンクコストとなるノードを確定ノードとしていくことで、最短経路を決定していく。
【００５１】
図１３は、図１２に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。この処理ステップでは、ノードＤに接続されている各ノードについてスタートノードＢからのリンクコストを求める。すなわち、ノードＣ，ノードＥ、ノードＦについてノードＢからのリンクコストを算出する処理である。図１３に示すようにノードＣが１＋４＝５、ノードＥが１＋９＝１０、ノードＦ１＋６＝７である。
【００５２】
図１９は、図１０〜図１３に示す最短経路探索処理結果を反映した各リンクツリーコントロールテーブルを示す図である。なお、図１８ではノードＩＤ＝Ｄのリンクツリーコントロールテーブル４０はヘッダ部４１のみまでしか生成されていない。しかし、この時点でリンクエントリが３エントリ（次ノードＩＤ＝Ｃ リンクエントリ部４２、次ノードＩＤ＝Ｅ リンクエントリ部４３、次ノードＩＤ＝Ｆ リンクエントリ部４４）生成される。
【００５３】
生成プロセスは、図１８を参照して説明したノードＩＤ＝Ｂのリンクエントリ部３２と同様であるため割愛する。この時点では各エントリの次ノードリンクテーブルポインタ（１Ｌ１ＬＥ１−２、１Ｌ１ＬＥ２−２、１Ｌ１ＬＥ３−２）には、いずれも初期値である「０」が格納されている。
【００５４】
また、次リンクの評価結果フラグ（１Ｌ１ＬＥ１−３、１Ｌ１ＬＥ２−３、１Ｌ１ＬＥ３−３）には、次ノードのヘッダも作成されていないため、いずれも初期値の「０」が格納されている。そして、３つのリンクエントリ部４２，４３，４４が生成されると、ヘッダ部４１のリンク数（アドレス記号１Ｌ１ＨＮｏＬ）が０から３に更新される。
【００５５】
また、全リンク切断フラグ（アドレス記号１Ｌ１ＨＦ）には、初期値の「０」を「接続」に更新される。なお、ノードＩＤ＝Ａのリンクツリーコントロールテーブル５０は、図１８で生成したヘッダ部５１のみであり、格納されている値は更新されない。
【００５６】
図１４は、図１３に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。この処理ステップでは、スタート地点から接続されている各確定ノードに接続されている未確定ノードの中でミニマムリンクコストであるノードを決定する。まず、この時点で上記の条件を満たすノードは、ノードＡおよびノードＣである。ここで、更にミニマムリンクコストであるノードは、ノードＡのリンクコストが「２」で、ノードＣのリンクコストが「５」であるからノードＡである。したがって、ノードＡを確定ノードとして決定する。なお、ここで未確定ノードとは、当該ノードの経路探索処理が終了していないノードのことである。
【００５７】
図２０は、図１４に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡの各リンクツリーコントロールテーブルを示す図である。ノードＡが確定ノードになったことに伴い、各リンクツリーコントロールテーブルでは次のような更新処理がなされる。図２０に示すノードＩＤ＝Ａのリンクエントリ部５０が生成され、次ノードＩＤ＝Ｃ（アドレス記号１Ｌ２ＬＥ１−１）が格納される。リンク数（アドレス記号１Ｌ２ＨＮｏL）は「１」に更新され、全リンク切断フラグ（アドレス記号１Ｌ２ＨＦ）は、「０」から「接続」に更新される。
【００５８】
図１５は、図１４に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。この処理ステップでは、ノードＡに接続されているノードについてスタート地点であるノードＢからリンクコストを計算する。すなわち、図１５に示すようにノードＡに接続されている未確定ノードはノードＣのみであるから、「Ｂ―Ｃ」間までのリンクコストを考える。ここで、「Ｂ―Ｃ」間までの選択可能な経路は「Ｂ−Ａ−Ｃ」ルートと、「Ｂ−Ｄ−Ｃ」ルートの２通りある。それぞれのリンクコストを計算すると、「Ｂ−Ａ−Ｃ」ルートは「９（２＋７）」、「Ｂ−Ｄ−Ｃ」ルートは「５（１＋４）」であるから、「Ｂ−Ｄ−Ｃ」ルートが最短となるため、現状を維持することになる。したがって「Ｂ−Ａ−Ｃ」ルートは不要であるため、「Ａ−Ｃ」間のリンクを切断する。
【００５９】
図２１は、図１５に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡの各リンクツリーコントロールテーブルを示す図である。ノードＡのリンクエントリ部５２の次リンク評価フラグ（アドレス記号１Ｌ２ＬＥ１−３）は、ノード「Ａ−Ｃ」間のリンクが切断されたため初期値の「０」から「切断」に更新される。また、ノードＡのリンクエントリ部５２の次リンク評価結果内容（アドレス記号１Ｌ２ＬＥ１−４）には、図１に示した記憶手段１２に格納されている地図データ（図示せず）から取得した「工事による通行規制」が格納される。
【００６０】
これらの更新処理に伴って、ノードＡが全てのリンクから切断されている状態（不活性状態）となる更新処理を行なう必要がある。また、ノードＡ自身も不活性状態と同等であるため、接続されている全ノードのリンクエントリに対して更新処理を行なう必要がある。すなわち、図２１に示すようにノードＡのヘッダ部５１の全リンク切断フラグ（アドレス記号１Ｌ２ＨＢＰ）を「０」から「切断」に更新され、ノードＢのリンクエントリ部３３の次リンク評価結果フラグ（アドレス記号０ＬＬＥ２−３）も「０」から「切断」に更新される。
【００６１】
また、それに伴いノードＢのリンクエントリ部３３の次リンク評価結果内容（アドレス記号０ＬＬＥ２−４）に「Ａ−Ｃ間工事による通行規制」という情報が更新される。なお、このような更新処理を行なうことで、不要ノードの接続情報が残らず、後述するリンク切断根拠・区間を抽出する判定処理において必要な接続ノード情報を参照するだけで、判定することができる。したがって、当該判定処理をより高速化することができる。
【００６２】
図１６は、図１５に示す最短経路探索処理結果に次の処理ステップ（Ｓ４）を反映した図である。この処理ステップでは、未確定のノードの中でミニマムリンクコストを決定する。すなわち未確定ノードであって、かつミニマムリンクコストであるノードは、この時点でノードＣのみであるからノードＣを確定ノードとして決定する。
【００６３】
図２２は、図１６に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡ,ノードＣの各リンクツリーコントロールテーブルを示す図である。図１６を参照して説明したノードＣの確定処理は、ノードＩＤ＝Ｄからのルートに基づく確定処理である。したがって、図２２に示すようにノードＩＤ＝Ｄのリンクエントリ部４２の次ノードリンクテーブルポインタ（アドレス記号１Ｌ１ＬＥ１−２）にノードＩＤ＝Ｃを示す「２Ｌ１ＨＮＩＤ」が格納される。
【００６４】
また、ノードＩＤ＝Ｄのリンクエントリ部４２の次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ１−３）を「０」から「接続」に更新される。なお、ノードＣのリンクコントロールテーブル６０のヘッダ部６１は、上述したヘッダ部３１、４１、５１と同様に生成されるため、説明は割愛する。
【００６５】
図１７は、図１６に示す探索処理の次の処理ステップ（一度Ｓ５でＮｏと判断され、Ｓ１〜Ｓ４を行なう状態）を反映した図である。この処理ステップでは、ノードＣに接続されているノードのリンクコストを求める。すなわち、スタート地点のノードＢからノードＥまでのリンクコストは、「Ｂ−Ｄ−Ｅ」ルートの総和が「１０」であり、「Ｂ−Ｄ−Ｃ−Ｅ」ルートの総和は「６」であるため、「Ｂ−Ｄ−Ｃ−Ｅ」ルートの方が最短経路となる。したがって、「Ｂ−Ｄ−Ｃ−Ｅ」ルートのリンクコストの経路を維持し、「Ｄ−Ｅ」間のリンクを切断する。そして、上述した確定処理と同様に未確定ノードでミニマムリンクコストであるノードＥを確定ノードとして決定する。
【００６６】
図２３は、図１７に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡ,ノードＣ,ノードＥの各リンクツリーコントロールテーブルを示す図である。図１７を参照して説明したノードＥの確定処理は、ノードＩＤ＝Ｃからのルートに基づく確定処理である。したがって、図２３に示すようにノードＩＤ＝Ｃのリンクエントリ部４７の次ノードリンクテーブルポインタ（アドレス記号２Ｌ１ＬＥ１−２）にノードＩＤ＝Ｅを示す「３Ｌ１ＨＮＩＤ」を格納して活性化する。また、ノードＩＤ＝Ｃのリンクエントリ部４７の次リンク評価結果フラグ（アドレス記号２Ｌ１ＬＥ１−３）を「０」から「接続」に更新する。なお、ノードＥのリンクコントロールテーブル４８のヘッダ部４９は、上述したヘッダ部３１、４１、４６、５１と同様に生成されるため、説明は割愛する。
【００６７】
なお、この処理時点以降の未確定ノードＦ、Ｊ、Ｇについての経路探索処理については、図２７に示すダイクストラ法に基づく最短経路探索処理フローや上述したリンクツリーコントロールテーブルの生成、更新処理と同様になされるため割愛するが、最終的には図５および図６に示すリンクツリーに対応した図８および図９に示す各リンクツリーコントロールテーブルが生成される。
【００６８】
続いて、リンク切断要因・区間を抽出する処理フローの概要について、図２８を参照しながら説明する。図２８は、リンク切断要因・区間を抽出する処理のフローチャートを示した図である。
【００６９】
まず、ユーザーが経路探索結果に疑問を抱いてルート選定の根拠を確認するために、経路探索根拠表示要求アイコンをクリックするなどして経路探索根拠表示要求が行なわれる（ＳＴＡＲＴ）。
【００７０】
すると、図１に示すリンク切断要因・区間格納手段１７は、スタートノードのリンクツリーコントロールテーブルにおける「リンク数」を参照する（ステップＳ１０）。
【００７１】
リンク切断要因・区間格納手段１７は、「リンク数」を参照して得た値だけリンクエントリの次ノード毎に「次リンク評価結果フラグ」の値を参照する（ステップＳ１１）。
【００７２】
そして、リンク切断要因・区間格納手段１７は、参照した「次リンク評価結果フラグ」の値の判定を行なう（ステップＳ１２）。リンク切断要因・区間格納手段１７は、参照した「次リンク評価結果フラグ」の値が「切断」となっていた場合には、「次リンク評価内容」の値を取得して図１に示した記憶手段１２に格納する（ステップＳ１４）。一方、リンク切断要因・区間格納手段１７は、参照した「次リンク評価結果フラグ」の値が「接続」となっていた場合には、更に「次リンクテーブルポインタ」の値を参照する（ステップＳ１３）。
【００７３】
リンク切断要因・区間格納手段１７は、「次リンクテーブルポインタ」の値に示されるアドレスにしたがって、次ノードの先頭アドレスを参照して次ノードの「全リンク切断フラグ」の値を参照する（ステップＳ１５）。そして、リンク切断要因・区間格納手段１７は、参照した「全リンク切断フラグ」の値の判定を行なう（ステップＳ１６）。
【００７４】
リンク切断要因・区間格納手段１７は、「全リンク切断フラグ」の値が「切断」となっていた場合には、「次リンク評価内容」の値を取得して図１に示した記憶手段１２に格納する（ステップＳ１４）。リンク切断要因・区間格納手段１７は、「全リンク切断フラグ」の値が「接続」となっていた場合には、更に当該次ノードの「リンク数」を参照する（ステップＳ１７）。
【００７５】
当該次ノードの「リンク数」を参照したリンク切断要因・区間格納手段１７は、判定処理を当該次ノードの「次リンク評価結果フラグ」を参照して同様に判定処理を続ける（ステップＳ１１）。
【００７６】
このようにして、リンク切断要因・区間格納手段１７は、リンク切断要因とリンク切断区間の情報を抽出して各々図１に示した記憶手段１２に適切に格納していく。そして図１に示した入出力表示手段１３に適切に表示させる。
【００７７】
以下に、リンク切断要因・区間格納手段１７を用いて格納された情報を利用して、経路探索結果の根拠情報をユーザーに対して提示する処理について図８および図９に示す各リンクツリーコントロールテーブルを参照しながら具体的に説明する。
【００７８】
まず、上述した最短経路探索処理により経路探索結果の表示が行なわれ、ユーザーがその経路探索結果に疑義が生じた場合を想定する。なお、カーナビゲーション装置１０の入出力表示手段１３によって経路探索結果が表示されると共に、図示しない経路探索根拠出力要求手段が表示されているものとする。たとえば、入出力表示手段１３は、カーナビゲーション装置１０の一部を構成するディスプレイであり、経路探索根拠出力要求手段は経路探索根拠出力要求アイコンがディスプレイに表示されているとする。
【００７９】
ユーザーが経路探索結果に疑問を抱いてルート選定の根拠を確認するために、経路探索根拠出力要求アイコンをクリックする。経路探索根拠出力要求アイコンがクリックされると、経路探索根拠出力表示要求信号が生成され、演算制御手段１１は、記憶手段１２に格納されているリンクツリーコントロールテーブル３０のリンク数（アドレス記号０ＬＨＮｏＬ）を参照して「２」を得る。
【００８０】
これは、スタート地点であるノードＢには２つのリンクエントリがあることを示すので、リンクエントリ部３２の次ノードについて次リンク評価結果フラグ（アドレス記号０ＬＬＥ１−３およびアドレス記号０ＬＬＥ２−３）についてそれぞれリンク切断要因やリンク切断区間情報等を抽出するための判定処理を行なう。
【００８１】
まず、次ノードＩＤ＝Ｄについての次リンク評価結果フラグ（アドレス記号０ＬＬＥ１−３）を確認する。次リンク評価結果フラグ（アドレス記号０ＬＬＥ１−３）に格納されている値は、「接続」であるため、接続されている次ノードについて更に判定処理を行なう。そこで、ヘッダ部３１の次ノードリンクテーブルポインタ（アドレス記号０ＬＬＥ１−２）を確認する。
【００８２】
次ノードリンクテーブルポインタ（アドレス記号０ＬＬＥ１−２）は、アドレス記号「１ＬＨＮＩＤ」となっているため、ノードＩＤ＝Ｄであるリンクツリーコントロールテーブル４０へ判定処理を移行して、ヘッダ部４１にある全リンク切断フラグ（アドレス記号１ＬＨＦ）の値を確認する。
【００８３】
ヘッダ部４１の全リンク切断フラグ（アドレス記号１ＬＨＦ）の値は、「接続」であるため、リンク数（アドレス記号１ＬＨＮｏＬ）の値「３」を取得して、リンクエントリ部４２の次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ１−３、１Ｌ１ＬＥ２−３、１Ｌ１ＬＥ３−３）についてそれぞれ判定処理を行なう。
【００８４】
次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ１−３）の値は、「切断」となっており、次リンク評価結果内容（アドレス記号１Ｌ１ＬＥ１−４）が初期値（＝０）でなければ、切断要因があると判定する。次リンク評価結果内容（アドレス記号１Ｌ１ＬＥ１−４）に格納されているデータ内容が「Ｅ−Ｇ間大渋滞」であるため、これを取得して図１に示した記憶手段１２に格納する。
【００８５】
同様に、次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ２−３）についても判定を行なう。次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ２−３）の値も、「切断」であるから、次リンク評価結果内容（アドレス記号１Ｌ１ＬＥ２−４）が、初期値（＝０）でなければ、切断要因があると判定する。次リンク評価結果内容（アドレス記号１Ｌ１Ｅ２−４）に格納されているデータ内容は「Ｄ−Ｅ間大渋滞」であるため、これを抽出して図１に示した記憶手段１２に格納する。
【００８６】
更に、次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ３−３）の判定を行なう。次リンク評価結果フラグ（アドレス記号１Ｌ１ＬＥ３−３）は、「接続」となっているため、前述した処理と同様に、接続されている次ノードについて更に判定処理を行なっていく。
【００８７】
このようにして目的地までの全ての残存リンクエントリの判定処理を繰り返して「次リンク評価結果フラグ」の値が「切断」ならば「次リンク評価結果内容」を抽出して図１に示した記憶手段１２に格納する処理を繰り返す。
【００８８】
このような判定処理を繰り返すことで、ユーザーに対してリンク切断要因に関連する情報および／またはリンク切断区間に関連する情報を抽出して、経路探索結果と共に提供することができる。なお、抽出されたリンク切断要因に関連する情報および／またはリンク切断区間に関連する情報は、抽出順に入出力表示手段１３に表示してもよいし、所定数だけ表示させる制御をしてもよい。
【００８９】
たとえば、上述した判定処理により抽出した情報のはじめの３件だけを表示させる制御を行なう。このように制御することで、たくさんのリンク切断要因等の情報があったとしても、ユーザーが一見して把握することができる出力件数に絞ることができる。また無駄にカーナビゲーション装置１０を注視することがなくなる。
【００９０】
なお、これらの判定処理によって抽出されたリンク切断要因等の情報について、当該リンクツリーの総和となるリンクコストの値のなかでリンク切断要因等の情報が占めるリンクコストの割合によって出力表示の制御を行なってもよい。たとえば、当該リンクコストが一定の閾値以上（たとえばリンクコスト値の総和の２０％以上を占める値をもつリンク切断要因など）である情報のみを表示させる制御を行なってもよい。
【００９１】
また、車速センサから車両速度を周期的に取得して、取得した速度データが一定の速度以上となった場合には、表示する件数を減少させたり、一定の速度未満となった場合には表示する件数を増加させたりする制御をおこなってもよい。このような制御をすることで、安全運転に配慮した好ましいナビゲーション装置を提供することができる。
【００９２】
上述したように本発明に係る第１の実施形態であるナビゲーション装置１０は、ユーザーが仮に経路探索結果に疑問を感じたとしても、的確にその根拠情報を抽出して経路探索結果と共に提示することができるため、ユーザーが特定区間の道路条件について十分な情報を持っているか否かに関わらず、提示した経路探索結果に対して納得させることができ、かつストレスを感じさせずに安全運転を支援することができる。
【００９３】
続いて、本発明に係る第２の実施形態であるナビゲーション装置７０について説明する。図２４は、本発明に係る第２の実施形態であるナビゲーション装置７０の概要構成を示したブロック図である。
【００９４】
ナビゲーション装置７０は、本発明に係る第１の実施形態であるカーナビゲーション装置１０の有する手段に加えて、経路探索根拠出力要求手段７８を有する。なお、図２４に示された他の各手段についてはカーナビゲーション装置１０と同じ機能であること、最短経路探索処理やリンクツリーコントロールテーブルの生成方法やリンク切断要因・区間を抽出して格納する処理についても同様であることから、これらの説明は割愛する。
【００９５】
経路探索根拠出力要求手段７８は、ユーザー側から経路探索根拠を要求することができる機能を備えている。たとえばカーナビゲーション装置７０の入出力表示手段７３に常に経路探索根拠出力要求手段７８を表示させておく。具体的には、経路探索根拠出力要求ボタンや経路探索根拠出力要求アイコンをディスプレイに備えさせるなどの具体例が挙げられる。なお、本発明に係る第２の実施形態における経路探索根拠出力要求手段７８は、カーナビゲーション装置７０に内蔵されているまたは機能的に内包されているが、外部に経路探索根拠出力要求ができるリモコン、通信端末機器などを設けて双方向通信を行なって機能させてもよい。
【００９６】
なお、経路探索根拠出力要求手段７８に加えて、過去に行なった経路探索結果を参照できるように経路探索履歴保持手段を更に設けて、過去の経路探索根拠を記憶手段７２に記録して、ユーザー側から参照できるように構成してもよい。
【００９７】
このような手段を設けることにより、経路探索表示結果を出力するタイミングでそのリンク切断要因等の根拠を知ることができるという態様ではなく、ユーザー自身が経路探索に疑義が生じたとき（たとえば経路探索が終了してしばらく経路に即して走行していたが不意に疑問を感じたとき）いつでもその経路探索結果の根拠を知ることができる。したがって、本発明に係る第1の実施形態の有する効果に加えて、よりユーザー側の視点に基づいたカーナビゲーション装置を提供することができる。
【００９８】
更に、本発明に係る第３の実施形態であるカーナビゲーション装置８０について説明する。図２５は、本発明に係る第３の実施形態であるカーナビゲーション装置８０の概要構成を示したブロック図である。
【００９９】
カーナビゲーション装置８０は、本発明に係る第１の実施形態であるカーナビゲーション装置１０と同じ機能を有する手段に加えて、探索経路登録保持手段８８と、リンクコスト再計算手段８９と、経路変更根拠格納手段９０と、を有する。
【０１００】
探索経路登録保持手段８８は、一度最短経路探索処理を行なって生成されたリンクツリーコントロールテーブルを記憶手段８２に格納しておく機能を備えている。
【０１０１】
リンクコスト再計算手段８９は、再度同じ最短経路探索処理がユーザーの操作により行なわれたときに、自動的に再度選択可能な各ノード間のリンクコストを再計算する機能を備えている。
【０１０２】
経路変更根拠格納手段９０は、リンクコスト再計算手段８９により再計算した結果に基づいて最短経路探索処理を行なった結果であるリンクツリーコントロールテーブルが、探索経路登録保持手段８８に登録されているリンクツリーコントロールテーブルと比較して異なる構成となった場合に、その異なる構成となった根拠を抽出して記憶手段８２に格納する機能を備えている。なお、その異なる構成となった根拠を抽出する場合に、抽出した根拠の順に表示する、抽出した根拠のうち所定数のみ表示する、所定の閾値以上のリンクコストである根拠だけを表示する、車速により表示する根拠の表示件数を変更するといった制御を行なってもよい。
【０１０３】
このような手段を設けることにより、再度同じ最短経路探索処理がユーザーの操作により選択されたときに、同じ経路であってもリンクコストに変化が生じていないかをチェックでき、かつ仮に、経路に変化が生じていた場合であっても、その根拠を抽出して経路探索処理結果と共にその根拠情報を提供することができる。したがって、カーナビゲーション装置８０は、同一の経路について過去に提示した探索経路結果と異なる結果を提示することになるような特殊な状況が発生したとしても、ユーザーがそのような特殊な状況について十分な情報を持っているか否かに関わらず、提示した経路探索結果に対して納得させることができ、かつストレスを感じさせずに安全運転を支援することができる。
【０１０４】
更に、本発明に係る第４の実施形態であるカーナビゲーション装置１００について説明する。図２６は、本発明に係る第４の実施形態であるカーナビゲーション装置１００の概要構成を示したブロック図である。
【０１０５】
カーナビゲーション装置１００は、本発明に係る第２の実施形態であるカーナビゲーション装置７０と同じ機能を有する手段に加えて、探索経路登録保持手段１０８と、リンクコスト再計算手段１０９と、経路変更根拠格納手段１１０と、経路探索根拠出力要求手段１１１と、を有する。
【０１０６】
なお、探索経路登録保持手段１０８,リンクコスト再計算手段１０９および経路変更根拠格納手段１１０の機能説明および効果は、上述した探索経路登録保持手段８８,リンクコスト再計算手段８９および経路変更根拠抽出手段９０と同様であるため、これらの説明は割愛する。また、経路探索根拠出力要求手段１１１の機能説明および効果は、上述した経路探索根拠出力要求手段７８と同様であるため、説明は割愛する。
【０１０７】
これらの手段を設けることによって、カーナビゲーション装置１００は、よりユーザー側の視点に基づいた仕様となる。また、カーナビゲーション装置１００は、ユーザーが特定区間の道路条件について十分な情報を持っているか否かに関わらず、いつでも提示された経路探索結果に対してその根拠を知って納得させることができる。したがって、カーナビゲーション装置１００は、ユーザーにストレスを感じさせずに安全運転を支援することができる。
【０１０８】
以上、本発明に係る第１の実施形態から第４の実施形態について説明をしたが、本発明はその要旨を逸脱しない限り種々変更実施できる。
【０１０９】
たとえば、本発明に係る第１の実施形態から第４の実施形態における特定の２点間における最短経路探索アルゴリズムとしてダイクストラ法を採用しているが、実施形態によって他のアルゴリズムを採用して構築しても勿論よい。
【０１１０】
また、上述した本発明に係る第１の実施形態から第４の実施形態では、カーナビゲーション装置の各機能を特定のハードウェアを指定して機能別手段として行なわせているが、全ての機能手段または一部の機能手段をプログラムからなるソフトウェアで処理・実行させるようにしても勿論よい。
【産業上の利用可能性】
【０１１１】
本発明は、全てのナビゲーション装置に適用できる。本発明は、特に車に搭載されたカーナビゲーション装置として利用できる。
【図面の簡単な説明】
【０１１２】
【図１】本発明に係る第１の実施形態であるカーナビゲーション装置の概要構成を示したブロック図である。
【図２】単純モデル化したある道路網を示す図である。
【図３】図２で示した道路網についてダイクストラ法に基づいて最短経路探索処理結果を示した図である。
【図４】図２で示した道路網であって、特定の状況変化が生じた道路網を示す図である。
【図５】図４で示した特定の状況変化が生じた道路網についてダイクストラ法に基づいて最短経路探索処理結果を示した図である。
【図６】図５に示す最短経路探索処理結果に基づくリンクツリーを示す図である。
【図７】リンクツリーコントロールテーブルの基本構造を説明するための図である。
【図８】図６に示すリンクツリーに対応したリンクツリーコントロールテーブルを示す図である。
【図９】図６に示すリンクツリーに対応したリンクツリーコントロールテーブルを示す図である。
【図１０】図４に示した道路網であり、最短経路探索処理結果を単純モデル化して示した図である。
【図１１】図４に示した道路網であり、図１０に示す最短経路探索処理結果に次の処理ステップ（Ｓ１）を反映した図である。
【図１２】図４に示した道路網であり、図１１に示す最短経路探索処理結果に次の処理ステップ（Ｓ２）を反映した図である。
【図１３】図４に示した道路網であり、図１２に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。
【図１４】図４に示した道路網であり、図１３に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。
【図１５】図４に示した道路網であり、図１４に示す最短経路探索処理結果に次の処理ステップ（Ｓ３）を反映した図である。
【図１６】図４に示した道路網であり、図１５に示す最短経路探索処理結果に次の処理ステップ（Ｓ４）を反映した図である。
【図１７】図４に示した道路網であり、図１６に示す最短経路探索処理結果に次の処理ステップ（一度Ｓ５でＮｏと判断され、Ｓ１〜Ｓ４を行なう状態）を反映した図である。
【図１８】スタート地点であるノードＢのリンクツリーコントロールテーブルと、ノードＢに接続されているノードＤのリンクツリーコントロールテーブルと、ノードＢに接続されているノードＡのリンクツリーコントロールテーブルと、を示す図である。
【図１９】図１０〜図１３までの最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡの各リンクツリーコントロールテーブルを示す図である。
【図２０】図１４に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡの各リンクツリーコントロールテーブルを示す図である。
【図２１】図１５に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡの各リンクツリーコントロールテーブルを示す図である。
【図２２】図１６に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡ,ノードＣの各リンクツリーコントロールテーブルを示す図である。
【図２３】図１７に示した最短経路探索処理結果を反映したノードＢ,ノードＤ,ノードＡ,ノードＣ,ノードＥの各リンクツリーコントロールテーブルを示す図である。
【図２４】本発明に係る第２の実施形態であるカーナビゲーション装置の概要構成を示したブロック図である。
【図２５】本発明に係る第３の実施形態であるカーナビゲーション装置の概要構成を示したブロック図である。
【図２６】本発明に係る第４の実施形態であるカーナビゲーション装置の概要構成を示したブロック図である。
【図２７】ダイクストラ法に基づく最短経路探索処理フローを簡単に示した図である。
【図２８】リンク切断要因・区間を抽出する処理のフローチャートを示した図である。
【符号の説明】
【０１１３】
ナビゲーション装置 １０、７０、８０、１００
演算制御部 １１、７１、８１、１０１
記憶手段 １２、７２、８２、１０２
入出力表示手段１３、７３、８３、１０３
リンクコスト算出手段 １５、７５、８５、１０５
リンクコスト再計算手段 ８９，１０９
経路探索手段 １６、７６、８６、１０６
探索経路登録保持手段 ８８、１０８
リンク切断要因・区間格納手段 １７、７７、８７、１０７
経路探索根拠出力要求手段 ７８、１１１
経路変更根拠格納手段 ９０，１１０
【特許請求の範囲】
【請求項１】
経路探索をするための情報を格納する記憶手段と、
上記記憶手段に格納された情報から各ノード間のリンクコストを算出するリンクコスト算出手段と、
上記リンクコスト算出手段により算出されたリンクコストに基づいて複数の経路より一の経路を選択する経路探索手段と、
上記経路探索手段によって選択されなかったノードのリンク切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納するリンク切断要因・区間格納手段と、
上記リンク切断要因・区間格納手段により抽出して格納された情報を上記経路探索結果と共に表示する入出力表示手段と、を有することを特徴とするナビゲーション装置。
【請求項２】
経路探索をするための情報を格納する記憶手段と、
上記記憶手段に格納された情報から各ノード間のリンクコストを算出するリンクコスト算出手段と、
上記リンクコスト算出手段により算出されたリンクコストに基づいて複数の経路より一の経路を選択する経路探索手段と、
上記経路探索手段によって選択されなかったノードのリンク切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納するリンク切断要因・区間格納手段と、
上記リンク切断要因・区間格納手段に抽出して格納された情報を出力するように指示する経路探索根拠出力要求手段と、を有することを特徴とするナビゲーション装置。
【請求項３】
前記経路探索手段により選択された前記一の経路を構成する各ノード情報および／または各ノード区間のリンクコストを前記記憶手段へ格納する探索経路登録保持手段と、
上記探索経路登録保持手段に格納された前記一の経路が呼び出されたときに前記一の経路のリンクコストを再計算するリンクコスト再計算手段と、
上記リンクコスト再計算手段に基づいて決定された経路が前記一の経路と異なることとなったとき、前記一の経路を構成する各ノードのうちリンクが切断された切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納する経路変更根拠格納手段と、
上記経路変更根拠格納手段により抽出して格納された情報を前記経路探索結果と共に表示する入出力表示手段と、を有することを特徴とする請求項１に記載のナビゲーション装置。
【請求項４】
前記経路探索手段により選択された前記一の経路を構成する各ノード情報および／または各ノード区間のリンクコストを前記記憶手段に格納する探索経路登録保持手段と、
上記探索経路登録保持手段に抽出して格納された前記一の経路が呼び出されたときに前記一の経路のリンクコストを再計算するリンクコスト再計算手段と、
上記リンクコスト再計算手段に基づいて決定された経路が前記一の経路と異なることとなったとき、前記一の経路を構成する各ノードのうちリンクが切断された切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納する経路変更根拠格納手段と、
上記経路変更根拠格納手段により抽出して格納された情報を出力するように指示できる経路探索根拠出力要求手段と、を有することを特徴とする請求項２に記載のナビゲーション装置。
【請求項５】
コンピュータを請求項１から請求項４のいずれか1項に記載のナビゲーション装置として機能させることを特徴とするプログラム。
【請求項１】
経路探索をするための情報を格納する記憶手段と、
上記記憶手段に格納された情報から各ノード間のリンクコストを算出するリンクコスト算出手段と、
上記リンクコスト算出手段により算出されたリンクコストに基づいて複数の経路より一の経路を選択する経路探索手段と、
上記経路探索手段によって選択されなかったノードのリンク切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納するリンク切断要因・区間格納手段と、
上記リンク切断要因・区間格納手段により抽出して格納された情報を上記経路探索結果と共に表示する入出力表示手段と、を有することを特徴とするナビゲーション装置。
【請求項２】
経路探索をするための情報を格納する記憶手段と、
上記記憶手段に格納された情報から各ノード間のリンクコストを算出するリンクコスト算出手段と、
上記リンクコスト算出手段により算出されたリンクコストに基づいて複数の経路より一の経路を選択する経路探索手段と、
上記経路探索手段によって選択されなかったノードのリンク切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納するリンク切断要因・区間格納手段と、
上記リンク切断要因・区間格納手段に抽出して格納された情報を出力するように指示する経路探索根拠出力要求手段と、を有することを特徴とするナビゲーション装置。
【請求項３】
前記経路探索手段により選択された前記一の経路を構成する各ノード情報および／または各ノード区間のリンクコストを前記記憶手段へ格納する探索経路登録保持手段と、
上記探索経路登録保持手段に格納された前記一の経路が呼び出されたときに前記一の経路のリンクコストを再計算するリンクコスト再計算手段と、
上記リンクコスト再計算手段に基づいて決定された経路が前記一の経路と異なることとなったとき、前記一の経路を構成する各ノードのうちリンクが切断された切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納する経路変更根拠格納手段と、
上記経路変更根拠格納手段により抽出して格納された情報を前記経路探索結果と共に表示する入出力表示手段と、を有することを特徴とする請求項１に記載のナビゲーション装置。
【請求項４】
前記経路探索手段により選択された前記一の経路を構成する各ノード情報および／または各ノード区間のリンクコストを前記記憶手段に格納する探索経路登録保持手段と、
上記探索経路登録保持手段に抽出して格納された前記一の経路が呼び出されたときに前記一の経路のリンクコストを再計算するリンクコスト再計算手段と、
上記リンクコスト再計算手段に基づいて決定された経路が前記一の経路と異なることとなったとき、前記一の経路を構成する各ノードのうちリンクが切断された切断要因に関連する情報および／またはリンクが切断されたノード区間に関連する情報を抽出して格納する経路変更根拠格納手段と、
上記経路変更根拠格納手段により抽出して格納された情報を出力するように指示できる経路探索根拠出力要求手段と、を有することを特徴とする請求項２に記載のナビゲーション装置。
【請求項５】
コンピュータを請求項１から請求項４のいずれか1項に記載のナビゲーション装置として機能させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【公開番号】特開２００９−２４４２０９（Ｐ２００９−２４４２０９Ａ）
【公開日】平成２１年１０月２２日（２００９．１０．２２）
【国際特許分類】
【出願番号】特願２００８−９３７２７（Ｐ２００８−９３７２７）
【出願日】平成２０年３月３１日（２００８．３．３１）
【出願人】（０００００３５９５）株式会社ケンウッド (1,981)
【Ｆターム（参考）】
【公開日】平成２１年１０月２２日（２００９．１０．２２）
【国際特許分類】
【出願日】平成２０年３月３１日（２００８．３．３１）
【出願人】（０００００３５９５）株式会社ケンウッド (1,981)
【Ｆターム（参考）】
[ Back to top ]