(57)【要約】【課題】ユーザが安心して使える経路探索装置を提供することである。【解決手段】経路探索装置１において、プロセッサ１６は、探索開始地点から探索終了地点までの経路を探索する処理を複数行って、互いに異なる複数の経路を導出する。さらに、プロセッサ１６は、探索により得た複数の経路が相違する原因を特定した後、探索により得た複数の経路、及び相違原因を、表示装置１８及び／又はスピーカ１９から出力する。【選択図】        図１
2004251773.tif 000002
【特許請求の範囲】
【請求項１】
経路探索装置であって、
探索開始地点から探索終了地点までの経路を探索する処理を複数行って、互いに異なる複数の経路を導出する経路探索部と、
前記経路探索部が探索した複数の経路が相違する原因を特定する原因特定部と、
前記経路探索部が探索した複数の経路、及び前記原因特定部で特定された原因を出力する出力部とを備える、経路探索装置。
【請求項２】
前記経路探索装置は、外部から定期的に送られてくる交通情報を受信する受信部をさらに備え、
前記原因特定部は、前記受信部が受信した交通情報を使って、前記経路探索部が探索した複数の経路が相違する原因を特定する、請求項１に記載の経路探索装置。
【請求項３】
前記原因特定部は、
前記受信部により受信された交通情報を使って、少なくとも前記経路探索部で探索された経路上の交通状況の変化を示す状況変化情報を作成する状況変化情報作成部と、
前記経路探索部で探索された複数の経路の内、互いに異なる部分を特定する複数の差分データを作成する差分データ作成部と、
前記差分データ作成部により作成されたいずれかの差分データと、前記状況変化情報作成部で作成された状況変化情報とを使って、前記経路探索部で探索された複数の経路の内、交通状況が悪化した回避経路情報を作成する回避経路情報作成部と、
前記差分データ作成部により作成された他の差分データと、前記状況変化情報作成部で作成された状況変化情報とを使って、前記経路探索部で探索された複数の経路の内、交通状況が改善した利用経路情報を作成する利用経路情報作成部とを含む、請求項２に記載の経路探索装置。
【請求項４】
予め格納される地図データを使って、前記回避経路情報作成部で作成された回避経路情報及び／又は前記利用経路情報作成部で作成された利用経路情報を使って、前記経路探索部が探索した複数の経路が相違する原因が地図上に合成された表示画像データを作成して、前記出力部に送る画像データ作成部をさらに備える、請求項３に記載の経路探索装置。
【請求項５】
前記回避経路情報作成部で作成された回避経路情報及び／又は前記利用経路情報作成部で作成された利用経路情報を使って、前記経路探索部が探索した複数の経路が相違する原因を音声で表す合成音声データを作成して、前記出力部に送る合成音声データ作成部をさらに備える、請求項３に記載の経路探索装置。
【請求項６】
前記経路探索装置は、前記経路探索部が探索した複数の経路の中から、１つを選択する選択部をさらに備え、
前記出力部は、前記選択部で選択された経路と、前記選択部で選択されなかった経路とを異なる方法で出力し、前記原因特定部で特定された原因を互いに異なる方法で出力する、請求項１に記載の経路探索装置。
【請求項７】
経路探索方法であって、
探索開始地点から探索終了地点までの経路を探索する処理を複数行って、互いに異なる複数の経路を導出する経路探索ステップと、
前記経路探索ステップで探索した複数の経路が相違する原因を特定する原因特定ステップと、
前記経路探索ステップが探索した複数の経路、及び前記原因特定ステップで特定された原因を出力する出力ステップとを備える、経路探索方法。
【請求項８】
コンピュータ装置上で実行可能なコンピュータプログラムとして実現される、請求項７に記載の経路探索方法。
【請求項９】
前記コンピュータプログラムが記録媒体上に記録される、請求項８に記載の経路探索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路探索装置に関し、より特定的には、探索開始地点から探索終了地点までの経路を複数本探索する経路探索装置に関する。
【０００２】
【従来の技術】
従来より様々なタイプの経路探索装置が研究・開発されている。特開平９−２８７９６５号公報には、以下のような第１の経路探索装置が開示されている。第１の経路探索装置は、経路探索の開始地点及び終了地点を設定した後、設定された２地点を含む探索範囲に存在する道路網を表現する地図データを読み出す。ここで、地図データは、特徴点間の道路区間を表現するリンクを含んでおり、各リンクには、対象となる道路区間を車両が通過するために要する旅行時間が割り当てられている。その後、第１の経路探索装置は、ＶＩＣＳ（Ｖｅｈｉｃｌｅ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｙｓｔｅｍ）から、現在の交通情報（特に、渋滞情報）を受信し、受信交通情報を使って、読み出した各リンクの旅行時間を、現在の交通状況に合うように更新する。その後、第１の経路探索装置は、旅行時間を更新したリンクを使って、設定された２地点間の経路を探索する。
【０００３】
また、特開平６−１８６０４９号公報には、以下のような第２の経路探索装置が開示されている。第２の経路探索装置は、設定された開始地点から終了地点へと至る経路を、予め準備されている地図データを使って探索した後、探索した経路に従ってユーザを目的地まで案内する。この案内中に、第２の経路探索装置は、ＶＩＣＳからの受信交通情報を参照することにより、現在案内中の経路を車両がスムーズに走行できないと判断する場合がある。この場合、第２の経路探索装置は、受信交通情報を使って、読み出した各リンクの旅行時間を更新し、更新したものを使って、現在位置から終了地点までの経路を探索する。
【０００４】
また、特開平９−２９２２５２号公報には、以下のような第３の経路探索装置が開示されている。第３の経路探索装置は、予め定められた広範囲の道路網を表現した地図データと、車両が実際に走行してきた道路及び交差点の情報からなる軌跡データとを保持する。その後、第１の経路探索装置と同様にして、第３の経路探索装置は、設定された開始地点から終了地点へと至る経路を、探索範囲内の地図データを使って探索する。さらに、第３の経路探索装置は、保持中の軌跡データを使って、同じ２地点間の経路を探索する。このように、第３の経路探索装置は、経路探索を互いに異なる条件下で行い、同じ２地点間の経路ではあるが、道順の異なる複数の経路を導出する。
【０００５】
【特許文献１】
特開平９−２８７９６５号公報
【特許文献２】
特開平６−１８６０４９号公報
【特許文献３】
特開平９−２９２２５２号公報
【０００６】
【発明が解決しようとする課題】
上述の第１及び第２の経路探索装置では、ユーザがある目的地に向かう場合に、交通状況に応じて、前回探索された経路と、今回探索されたものとが異なる場合がある。しかしながら、ユーザは、今回なぜ前回と異なる経路が探索されたのか分からないため、今回探索された経路に対して不信感を持つ場合がある。このような不信感をユーザが持ってしまうと、第１又は第２の経路探索装置が、現在の交通状況に応じた適切な経路を探索したとしても、ユーザは、第１又は第２の経路探索装置が探索した経路を利用しなくなることが起こるという問題点があった。
【０００７】
また、上述の第３の経路探索装置では、道順の異なる複数の経路がユーザに提供される。しかしながら、ユーザは、どのような理由で複数の経路が提供されているのかが分からないため、提供された複数の経路から、ユーザが自分に都合のいい１つの経路を選択することが難しい。その結果、選択した経路が本当に良かったかどうか、ユーザは不安になる場合があるという問題点があった。
【０００８】
それ故に、本発明の目的は、ユーザが安心して使える経路探索装置を提供することである。
【０００９】
【課題を解決するための手段及び発明の効果】
上記目的を達成するために、第１の発明は、経路探索装置であって、探索開始地点から探索終了地点までの経路を探索する処理を複数行って、互いに異なる複数の経路を導出する経路探索部と、経路探索部が探索した複数の経路が相違する原因を特定する原因特定部と、経路探索部が探索した複数の経路、及び原因特定部で特定された原因を出力する出力部とを備える。これにより、経路探索により得られた複数の経路が相違する原因をユーザに提供することが可能になるので、ユーザが安心感を与えることが可能となる。
【００１０】
上記第１の発明において、経路探索装置は、外部から定期的に送られてくる交通情報を受信する受信部をさらに備える。さらに、原因特定部は、受信部が受信した交通情報を使って、経路探索部が探索した複数の経路が相違する原因を特定する。これにより、複数の経路が相違する原因となった交通状況を、相違原因としてユーザに与えることが可能となる。
【００１１】
上記第１の発明において、原因特定部は、受信部により受信された交通情報を使って、少なくとも経路探索部で探索された経路上の交通状況の変化を示す状況変化情報を作成する状況変化情報作成部と、経路探索部で探索された複数の経路の内、互いに異なる部分を特定する複数の差分データを作成する差分データ作成部と、差分データ作成部により作成されたいずれかの差分データと、状況変化情報作成部で作成された状況変化情報とを使って、経路探索部で探索された複数の経路の内、交通状況が悪化した回避経路情報を作成する回避経路情報作成部と、差分データ作成部により作成された他の差分データと、状況変化情報作成部で作成された状況変化情報とを使って、経路探索部で探索された複数の経路の内、交通状況が改善した利用経路情報を作成する利用経路情報作成部とを含む。これにより、複数の経路の内、互いに相違する部分を交通状況を、相違原因としてユーザに与えることが可能となる。
【００１２】
上記第１の発明において、経路探索装置は、予め格納される地図データを使って、回避経路情報作成部で作成された回避経路情報及び／又は利用経路情報作成部で作成された利用経路情報を使って、経路探索部が探索した複数の経路が相違する原因が地図上に合成された表示画像データを作成して、出力部に送る画像データ作成部をさらに備える。これにより、ユーザは表示地図上で相違原因を見ることができるので、より使い勝手のよい経路探索装置を提供することが可能となる。
【００１３】
上記第１の発明において、経路探索装置は、回避経路情報作成部で作成された回避経路情報及び／又は利用経路情報作成部で作成された利用経路情報を使って、経路探索部が探索した複数の経路が相違する原因を音声で表す合成音声データを作成して、出力部に送る合成音声データ作成部をさらに備える。これにより、音声でユーザに相違原因を提供することが可能となるので、より使い勝手のよい経路探索装置を提供することが可能となる。
【００１４】
上記第１の発明において、経路探索装置は、経路探索部が探索した複数の経路の中から、ユーザの指定に基づいて１つを選択する選択部をさらに備える。ここで、出力部は、選択部で選択された経路と、選択部で選択されなかった経路とを異なる方法で出力し、原因特定部で特定された原因を互いに異なる方法で出力する。これにより、ユーザは、自身が選択した経路と、残りの経路と、それらの経路が相違する原因とを正確に区別できる。
【００１５】
第２の発明は、経路探索方法であって、探索開始地点から探索終了地点までの経路を探索する処理を複数行って、互いに異なる複数の経路を導出する経路探索ステップと、経路探索ステップで探索した複数の経路が相違する原因を特定する原因特定ステップと、経路探索ステップが探索した複数の経路、及び原因特定ステップで特定された原因を出力する出力ステップとを備える。
【００１６】
第２の発明において、経路探索方法は、コンピュータ装置上で実行可能なコンピュータプログラムとして実現される。また、コンピュータプログラムは記録媒体上に記録される。
【００１７】
【発明の実施の形態】
図１は、本発明の一実施形態に係る経路探索装置１のハードウェア構成を示すブロック図である。図１において、経路探索装置１は、記憶装置１１と、入力装置１２と、ロケータ１３と、受信機１４と、プログラムメモリ１５と、プロセッサ１６と、ワーキングエリア１７と、表示装置１８と、スピーカ１９とを備える。
【００１８】
記憶装置１１は、ハードディスク又はＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）のように、ランダムアクセス可能で大容量の記録媒体を駆動する装置であって、地図データＤｃａｒｔを格納する。地図データＤｃａｒｔは、例えば日本全域のような広範囲の地図（以下、広域地図と称する）を作成可能な各種データを含む。
広域地図上において、道路網は大略的には、図２に示すように、ｉ個の内部ノードＮｉｎ（●印参照）と、ｊ個の内部リンクＬｉｎとを使って表現される。ただし、図２では、都合上、３個の内部ノードＮｉｎ、及び２個の内部リンクＬｉｎのみを示している。各内部ノードＮｉｎは、道路網上の交差点又は屈曲点を表す。各内部リンクＬｉｎは、２個の内部ノードＮｉｎを繋ぐ道路区間を表す。
以上の各内部ノードＮｉｎ及び各内部リンクＬｉｎを特定するために、地図データＤｃａｒｔは、図３に示すような、ノードリストＬｎｏｄｅと、リンクリストＬｌｉｎｋとを含む道路網データＤｎｅｔ  を含む。なお、図３の道路網データＤｎｅｔ  はさらに、対応関係リストＬｃｏｎｎを含むが、これについては後述する。
【００１９】
図３において、ノードリストＬｎｏｄｅは、ｉ個の内部ノードＮｉｎに一つずつ割り当てられるノードレコードＲｎ１〜Ｒｎｉからなる。各ノードレコードＲｎ１〜Ｒｎｉは、自身が割り当てられている内部ノード（以下、対象内部ノードと称する）Ｎｉｎの情報として、番号（以下、内部ノード番号と称する）Ｎｎｎ、位置（以下、内部ノード位置と称する）Ｐｎｎ及びいくつかの内部リンク番号Ｎｎｌを含む。なお、都合上、図３には、ノードレコードＲｎ１のデータ構造のみを示している。内部ノード番号Ｎｎｎは、対象内部ノードＮｉｎを一意に特定するために、それに割り当てられる番号である。内部ノード位置Ｐｎｎは、対象内部ノードＮｉｎが道路網上で存在する位置を、例えば経度及び緯度を使って特定する。また、ノードレコードＲｎ１〜Ｒｎｉに設定される、いくつかの内部リンク番号Ｎｎｌは、対象内部ノードＮｉｎに繋がっている１つ又は複数の内部リンクＬｉｎを特定する。
【００２０】
リンクリストＬｌｉｎｋは、ｊ個の内部リンクＬｉｎに一つずつ割り当てられるリンクレコードＲｋ１〜Ｒｋｊからなる。各リンクレコードＲｋ１〜Ｒｋｊは、自身が割り当てられる内部リンク（以下、対象内部リンクと称する）Ｌｉｎの情報として、内部リンク番号Ｎｎｌ、距離（以下、内部リンク距離と称する）Ｄｎｌ、道路種別Ｔｒｄ及び２個の内部ノード番号Ｎｎｎを含む。なお、都合上、図３には、リンクレコードＲｋ１のデータ構造のみを示している。内部リンク番号Ｎｎｌは、対象内部リンクＬｉｎを一意に特定するため、それに割り当てられる番号である。内部リンク距離Ｄｎｌは、対象内部リンクＬｉｎが表す道路区間の距離である。道路種別Ｔｒｄは典型的には、対象内部リンクＬｉｎが表す道路の種別であり、本実施形態では、「高速道路」、「国道」、「県道」及び「私道」のいずれかであると仮定する。ただし、道路種別は、これらだけに限られない。また、リンクレコードＲｋ１〜Ｒｋｊに設定される各内部ノード番号Ｎｎｎは、対象内部リンクＬｉｎの両端に位置する内部ノードＮｉｎを特定する。
【００２１】
なお、上述では、リンクリストＬｌｉｎｋに含まれるのは内部リンク距離Ｄｎｌであるが、これに代えて、旅行時間が設定されても良い。旅行時間とは、本経路探索装置１を使うユーザが予め定められた速度で移動するという仮定下で、ユーザが対象内部リンクＬｉｎを通過するのに要すると想定される時間である。
【００２２】
次に、対応関係リストＬｃｏｎｎに関連する外部リンクＬｅｘについて説明する。図１の受信機１４には、ＤＳＲＣ（Ｄｅｄｉｃａｔｅｄ  Ｓｈｏｒｔ  Ｒａｎｇｅ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ）を利用する路車間通信システム、及び／又はＶＩＣＳ（Ｖｅｈｉｃｌｅ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｙｓｔｅｍ）から定期的に、交通情報Ｉｔｒが送られてくる。これらシステムでは一般的に、主要道路又は幹線道路のみからなる道路網（図５の実線部分参照）を、外部ノードＮｅｘ及び外部リンクＬｅｘを使って表現した道路網データが使われる。つまり、図５の道路網は、細街路に代表される非幹線道路（点線部分参照）を含んでいない。それに対して、経路探索装置１の道路網データＤｎｅｔ  は、図２に示すように、主要道路又は幹線道路以外にも、ユーザが移動可能な多くの道路（主要道路、幹線道路及び非幹線道路を含む）から構成される道路網を表す。以上のことから、外部リンクＬｅｘと、内部リンクＬｉｎとの間には下記の相違点がある。つまり、内部リンクＬｉｎは、主要道路、幹線道路及び非幹線道路の道路区間を表す。それに対して、外部リンクＬｅｘは、主要道路及び幹線道路の道路区間を表す。以上のことから、外部リンクＬｅｘ及び内部リンクＬｉｎとは完全に一対一に対応しているわけではない。つまり、外部リンクＬｅｘは、ある１本の内部リンクＬｉｎに等しい場合もあれば、連続する複数の内部リンクＬｉｎを繋げたものである場合もある。例えば、図５は、図２の道路網と同じ範囲の道路網を示しているが、図５に例示した外部リンクＬｅｘは、図２に示す２本の内部リンクＬｉｎを繋げたものに等しい。以上の外部リンクＬｅｘがどの内部リンクＬｉｎにより構成されるかを示すため、対応関係リストＬｃｏｎｎは道路網データＤｎｅｔ  に含まれる。
【００２３】
図３において、対応関係リストＬｃｏｎｎは、ｋ個の外部リンクＬｅｘに一つずつ割り当てられる対応関係レコードＲｃ１〜Ｒｃｋからなる。各対応関係レコードＲｃ１〜Ｒｃｋは、自身が割り当てられる外部リンク（以下、対象外部リンクと称する）Ｌｅｘの情報として、番号（以下、外部リンク番号と称する）Ｎｘｌ、距離（以下、外部リンク距離と称する）Ｄｘｌ、及び情報セットＩＳｎｌを含む。なお、都合上、図３には、対応関係レコードＲｃ１のデータ構造のみを示している。外部リンク番号Ｎｘｌは、対象外部リンクＬｅｘを一意に特定するため、それに割り当てられた番号である。外部リンク距離Ｄｘｌは、対象外部リンクＬｅｘが表す道路区間の距離である。情報セットＩＳｎｌは少なくとも、対象外部リンクＬｅｘを構成するいくつかの内部リンクＬｉｎを特定する内部リンク番号Ｎｉｎを含む。
【００２４】
なお、各外部リンクＬｅｘと各内部リンクＬｉｎとの間に一対一の関係が完全に成立する場合には、上述の対応関係リストＬｃｏｎｎは不要である。
【００２５】
図１において、入力装置１２は、リモートコントローラ、タッチセンサ、いくつかのキー、マウス又はマイク、もしくはこれらのうち、２つ以上の組み合わせから構成される。以上の入力装置１２を操作して、ユーザは、後述する経路探索に必要な探索開始地点ＯＰ及び探索終了地点ＥＰ、若しくは探索終了地点ＥＰのみを指定する。
【００２６】
ロケータ１３は、外部の測位システム（典型的には、ＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ  ））の受信機、及び／又は自律航法センサ群を含む。ＧＰＳ受信機は定期的に、上記測位システムからの受信情報を使って、ユーザの現在位置Ｐｕｒを導出する。自律航法センサ群は典型的には、速度センサ及び方位センサを含み、速度センサ及び方位センサは定期的に、ユーザの移動速度Ｖｕｒ及び、その移動方向Ｄｕｒを検出する。
【００２７】
受信機１４は、交通情報Ｉｔｒを定期的に受信する。交通情報Ｉｔｒは、図４の（Ａ）に示すように、ｋ個の外部リンクＬｅｘに一つずつ割り当てられる交通情報レコードＲｔ１〜Ｒｔｋを含む。各交通情報レコードＲｔ１〜Ｒｔｋは、対象外部リンクＬｅｘについて、外部リンク番号Ｎｘｌと、いくつかの情報セットＩＳｔｒとを含む。なお、都合上、図４の（Ａ）には、交通情報レコードＲｔ１のデータ構造のみを示している。各情報セットＩＳｔｒは、対象外部リンクＬｅｘが表す道路区間上で発生している交通規制又は渋滞、及び、対象外部リンクＬｅｘの旅行時間のいずれかを示す。具体的には、各情報セットＩＳｔｒは、種別Ｔｉｎｆ  及び内容Ｃｉｎｆ  を含む。種別Ｔｉｎｆ  には、図４の（Ｂ）に示すように、少なくとも事象規制及び渋滞のいずれかが記述される。また、種別Ｔｉｎｆ  が事象規制の場合、内容Ｃｉｎｆ  には、工事及び事故のいずれかが設定される。また、種別Ｔｉｎｆ  が渋滞の場合、内容Ｃｉｎｆ  には、現在の渋滞の度合いに応じた渋滞度が記述される。
【００２８】
プログラムメモリ１５は典型的には、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）から構成され、コンピュータプログラム（以下、単にプログラムと称する）１５１を格納する。プロセッサ１６は、プログラム１５１に従って、大略的には経路探索及び理由選定という２つの処理を行う。ワーキングエリア１７は、プロセッサ１６の処理に必要な各種情報を格納する。
【００２９】
表示装置１８は、出力部の一部を構成しており、プロセッサ１６により作成される表示画像データＤｄｓｐ  に従って画像を表示する。
スピーカ１９は、出力部の一部を構成しており、プロセッサ１６により作成された合成音声データＤａｄに従って、音声を出力する。
【００３０】
以上の経路探索装置１において、プロセッサ１６は、プログラムメモリ１５内のプログラム１５１の実行をする。ここで、図６及び図７は、プログラム１５１に記述されたプロセッサ１６の処理手順を示すフローチャートである。
まず、図６のステップＡ１で、プロセッサ１６は、探索開始地点ＯＰ及び探索終了地点ＥＰを設定する。より具体的には、入力装置１２は、ユーザにより指定された両地点ＯＰ及びＥＰを特定する指定位置情報Ｉｄｐを作成し、作成したものをワーキングエリア１７に格納する。以上の指定位置情報Ｉｄｐをデコードして、プロセッサ１６は、探索開始地点ＯＰ及び探索終了地点ＥＰをワーキングエリア１７に設定する。
【００３１】
ステップＡ１では、他にも、次のようにして、探索開始地点ＯＰ及び探索終了地点ＥＰが設定されても良い。つまり、入力装置１２は、ユーザにより指定された１地点ＥＰを特定する指定位置情報Ｉｄｐを作成しワーキングエリア１７に格納する。この指定位置情報Ｉｄｐをデコードして、プロセッサ１６は、探索終了地点ＥＰをワーキングエリア１７に設定する。また、ロケータ１３は、導出した現在位置Ｐｕｒ、並びに、検出した移動速度Ｖｕｒ及び移動方向Ｄｕｒをワーキングエリア１７に格納する。プロセッサ１６は、格納された現在位置Ｐｕｒ、移動速度Ｖｕｒ及び移動方向Ｄｕｒを使って、ユーザの正確な現在位置ＰＰｕｒを導出し、ステップＡ１において、導出したものを探索開始地点ＯＰとしてワーキングエリア１７に設定する。
【００３２】
次のステップＡ２で、プロセッサ１６は、探索範囲の地図データＤｃａｒｔを、記憶装置１１からワーキングエリア１７に読み出す。ここで、探索範囲は好ましくは、探索開始地点ＯＰ及び探索終了地点ＥＰの双方を含む矩形形状の領域である。これによって、探索範囲に含まれる全内部ノードＮｉｎのノードレコードＲｎ  及び全内部リンクＬｉｎのリンクレコードＲｋ  が読み出される。
【００３３】
次のステップＡ３で、プロセッサ１６は、ステップＡ２で得られた内部リンクＬｉｎのそれぞれについて、内部リンク通過時間Ｔｎｌを算出する。具体的には、プログラム１５１は、図８に示すように、道路種別Ｔｒｄ及び初期推定速度Ｖｆｓの組みが記述される第１の推定速度テーブルＴｆｓを含んでいる。図８において、道路種別Ｔｒｄは、リンクレコードＲｋ  に記述されるものと同様である。この場合、道路種別Ｔｒｄとして、「高速道路」、「国道」、「県道」及び「私道」が記述される。初期推定速度Ｖｆｓは、同じ組みの道路種別Ｔｒｄで分類される道路をユーザが移動すると推定される速度であり、予め定められた値である。「高速道路」の場合には、初期推定速度Ｖｆｓとして、例えば「１００ｋｍ／ｈ」が記述される。また、道路種別Ｔｒｄが「国道」、「県道」及び「私道」の場合には、初期推定速度Ｖｆｓとして、例えば「６０ｋｍ／ｈ」、「４０ｋｍ／ｈ」及び「２０ｋｍ／ｈ」が記述される。以上の第１の推定速度テーブルＴｆｓを使って、プロセッサ１６は、ステップＡ３で各内部リンク通過時間Ｔｎｌを算出する。ここで、図９は、図６のステップＡ３の詳細な処理手順を示すフローチャートである。
【００３４】
図９のステップＢ１で、プロセッサ１６は、ステップＡ２で読み出された全リンクレコードＲｋ  の中から、未選択のものを１つ選択する。以下の説明では、ステップＢ１で選択されたものを、第１の処理対象リンクレコードＲｋ  と称し、第１の処理対象リンクレーコードＲｋ  で特定される内部リンクＬｉｎを、第１の処理対象内部リンクＬｉｎと称する。
次のステップＢ２で、プロセッサ１６は、第１の処理対象リンクレコードＲｋ  から、道路種別Ｔｒｄ及び内部リンク距離Ｄｎｌを取り出す。
次のステップＢ３で、プロセッサ１６は、ステップＢ２で得た道路種別Ｔｒｄと同じ組みの初期推定速度Ｖｆｓを、第１の推定速度テーブルＴｆｓから取り出す。
次のステップＢ４で、プロセッサ１６は、ステップＢ３で得た初期推定速度Ｖｆｓを、ステップＢ２で得た内部リンク距離Ｄｎｌに乗算して、第１の処理対象内部リンクＬｉｎの内部リンク通過時間Ｔｎｌを算出する。
次のステップＢ５で、プロセッサ１６は、図１０に示すように、第１の処理対象リンクレコードＲｋ  に、算出した内部リンク通過時間Ｔｎｌを追加する。
【００３５】
再度、図９を参照する。次のステップＢ６で、プロセッサ１６は、ステップＢ１で選択されていないリンクレコードＲｋ  が存在するか否かを判断する。未選択のものがあれば、プロセッサ１６はステップＢ１を行う。逆に、全リンクレコードＲｋ  を選択済であれば、プロセッサ１６は、図６のステップＡ３を終了する。以上の処理によって、プロセッサ１６は、ステップＡ２で読み出された全リンクレコードＲｋ  に、ステップＢ４で算出された内部リンク通過時間Ｔｎｌを追加する。
【００３６】
図６のステップＡ４で、プロセッサ１６は、ダイクストラ法に代表される周知のアルゴリズムに従って、最初の経路探索を行う。具体的には、プロセッサ１６は、ワーキングエリア１７上の道路網データＤｎｅｔ  を使って、探索開始地点ＯＰから探索終了地点ＥＰに至る第１の最適経路ＯＲ１  を探索する。ここで、第１の最適経路ＯＲ１  とは、設定された２地点ＯＰ及びＥＰの間をユーザが最小の旅行時間で到達可能な経路である。より具体的には、これら２地点ＯＰ及びＥＰの間を結ぶ経路のうち、第１の最適経路ＯＲ１  は、２地点ＯＰ及び地点ＥＰの間に存在する全内部リンクＬｉｎに割り当てられた内部リンク通過時間Ｔｎｌの合計が最小の経路である。
【００３７】
次のステップＡ５で、プロセッサ１６は、第１の最適経路ＯＲ１  を特定する第１の経路データＲＤ１  をワーキングエリア１７上で作成する。第１の経路データＲＤ１  は好ましくは、図１１の（Ａ）に示すように、合計値Ｖｓｕｍ  と、リンク総数ＴＮｌｋと、リンク番号セットＳｌｎとからなる。合計値Ｖｓｕｍ  は、第１の最適経路ＯＲ１  を構成する全内部リンクＬｉｎの内部リンク通過時間Ｔｎｌの合計である。リンク総数ＴＮｌｋは、第１の最適経路ＯＲ１  を構成する全内部リンクＬｉｎの総個数である。リンク番号セットＳｌｎは、第１の最適経路ＯＲ１  を構成する各内部リンクＬｉｎを特定する全ての内部リンク番号Ｎｎｌから構成される。好ましくは、リンク番号セットＳｌｎにおいて、内部リンク番号Ｎｎｌは、探索開始地点ＯＰに最も近いものから探索終了地点ＥＰに最も近いものまで、ユーザの通過順に並べられる。例えば、図１１の（Ｂ）に示すように、探索開始地点ＯＰ及び探索終了地点ＥＰが設定され、さらに、５個の内部リンクＬｉｎ６  〜Ｌｉｎ１０からなる第１の最適経路ＯＲ１  が探索された場合、例えば、図１１の（Ａ）に例示するように、合計値Ｖｓｕｍ  としての２５分、リンク総数ＴＮｌｋとしての５本、及び内部リンクＬｉｎ６  〜Ｌｉｎ１０を特定する内部リンク番号Ｎｎｌ６  〜Ｎｎｌ１０からなるリンク番号セットＳｌｎを含む第１の経路データＲＤ１  が作成される。このような第１の経路データＲＤ１  を、経路探索装置１はワーキングエリア１７で保持する。
【００３８】
再度、図６を参照する。ステップＡ６で、プロセッサ１６は、ロケータ１３から得られる現在位置Ｐｕｒ、移動速度Ｖｕｒ及び移動方向Ｄｕｒを使って、ユーザの正確な現在位置ＰＰｕｒを導出する。
次のステップＡ７で、プロセッサ１６は、ワーキングエリア１７上の地図データＤｃａｒｔから、表示範囲に含まれるものを選択する。ここで、表示範囲とは、ステップＡ６で導出された正確な現在位置ＰＰｕｒの周辺であって、表示装置１８に表示される地図の範囲である。
【００３９】
次のステップＡ８で、プロセッサ１６は、図１２に示すように、表示範囲の地図画像Ｍｄｓｐ  を含む表示画像データＤｄｓｐ１を作成する。より具体的には、プロセッサ１６は、ステップＡ７で選択した地図データＤｃａｒｔを使って、ワーキングエリア１７上に、地図画像Ｍｄｓｐ  を描画する。また、プロセッサ１６は、第１の経路データＲＤ１  を使って、表示対象範囲内に含まれる第１の最適経路ＯＲ１  を、描画した地図画像Ｍｄｓｐ  に合成する。さらに、プロセッサ１６は、描画した地図画像Ｍｄｓｐ  において、ステップＡ６で導出した正確な現在位置ＰＰｕｒに、ユーザの現在位置を示すマーク画像Ｍｕｒを合成する。これによって、表示画像データＤｄｓｐ１が完成する。なお、ステップＡ８では、必要に応じて、プロセッサ１６は、ユーザの案内に必要となる合成音声データＤａｄを作成しても良い。
【００４０】
次のステップＡ９で、プロセッサ１６は、作成した表示画像データＤｄｓｐ１を、ワーキングエリア１７から表示装置１８に転送する。表示装置１８は、受信した表示画像データＤｄｓｐ１に従って、図１２に示す画像を表示する。なお、図１２では、２次元の地図画像Ｍｄｓｐ  を例示しているが、これに限らず、３次元の地図画像Ｍｄｓｐ  が生成され出力されても良い。なお、ステップＡ８で合成音声データＤａｄが作成されている場合には、ステップＡ９で、プロセッサ１６は、それをスピーカ１９に出力する。
【００４１】
次のステップＡ１０で、プロセッサ１６は、ステップＡ６で導出した現在位置ＰＰｕｒと、ステップＡ１で設定した探索終了地点ＥＰとが一致するか否かを判断する。両者が一致する場合、プロセッサ１６は、ユーザを探索終了地点ＥＰ（つまり、ユーザの目的地）まで案内し終えたとみなして、図６及び図７の処理を終了する。逆に、両者が不一致の場合、プロセッサ１６は、ステップＡ１１に進む。
【００４２】
ステップＡ１１において、プロセッサ１６は、受信機１４により受信される交通情報Ｉｔｒがワーキングエリア１７に格納されているか否かを判断する。未格納の場合、プロセッサ１６は、再経路探索を行う必要がないとみなして、ステップＡ６を行う。この場合、上述のステップＡ６からＡ１１までの一連の処理が繰り返される。逆に、交通情報Ｉｔｒが格納されていると判断した場合、プロセッサ１６は、ステップＡ１２を行う。
【００４３】
ステップＡ１２において、プロセッサ１６は、必要な内部リンクＬｉｎについて、補正通過時間Ｔｕｄを算出し、記録する。ここで、プログラム１５１は、図１３に示すように、渋滞度Ｌｔｊ及び渋滞時推定速度Ｖｓｃの組みが記述される第２の推定速度テーブルＴｓｃを含んでいる。図１３において、渋滞度Ｌｔｊは、交通情報Ｉｔｒに記述される渋滞度と同様に、対象外部リンクＬｅｘが表す道路区間で発生している渋滞の度合いを示す。本実施形態では、説明の便宜上、渋滞度Ｌｔｊは、「０」、「１」及び「２」の３段階に分類されると仮定する。ただし、渋滞度Ｌｔｊは、３段階に限らず、何段階に分類されても良い。また、渋滞時推定速度Ｖｓｃは、同じ組みの渋滞度Ｌｔｊの道路をユーザが移動すると推定される速度であり、予め定められた値である。本実施形態では、渋滞度Ｌｔｊが「０」、「１」及び「２」の場合には、渋滞時推定速度Ｖｓｃとの例として、「補正無し」、「１５ｋｍ／ｈ」及び「５ｋｍ／ｈ」が記述される。ここで、「補正無し」とは、補正通過時間Ｔｕｄを算出する必要がないことを意味する。以上の第２の推定速度テーブルＴｓｃを使って、プロセッサ１６は、ステップＡ１２で各補正通過時間Ｔｕｄを算出する。ここで、図１４は、図６のステップＡ１２の詳細な処理手順を示すフローチャートである。
【００４４】
図１４のステップＣ１で、プロセッサ１６は、上述と同様にして、ユーザの正確な現在位置ＰＰｕｒを導出する。
次のステップＣ２で、プロセッサ１６は、ステップＡ３で内部リンク通過時間Ｔｎｌが追加された各リンクレコードＲｋ  から、処理対象範囲に属する各内部リンクＬｉｎに割り当てられたものを選択する。ここで、処理対象範囲は好ましくは、ステップＣ１で得られる正確な現在位置ＰＰｕｒ及び探索終了地点ＥＰの双方を含む矩形形状の領域である。以下の説明では、ステップＣ２で選択されたものを、第２の処理対象リンクレコードＲｋ  と称し、第２の処理対象リンクレコードＲｋ  により特定される内部リンクＬｉｎを、第２の処理対象内部リンクＬｉｎと称する。
【００４５】
次のステップＣ３で、プロセッサ１６は、全ての第２の処理対象リンクレコードＲｋ  の中から、未選択のものを１つ選択する。以下の説明では、ステップＣ３で選択されたものを、第３の処理対象リンクレコードＲｋ  と称し、第３の処理対象リンクレコードＲｋ  により特定される内部リンクＬｉｎを、第３の処理対象内部リンクＬｉｎと称する。
【００４６】
次のステップＣ４で、プロセッサ１６は、第３の処理対象リンクレコードＲｋ  から、内部リンク番号Ｎｎｌを取り出す。
次のステップＣ５で、プロセッサ１６は、記憶装置１１内の対応関係リストＬｃｏｎｎから、ステップＣ４で得た内部リンク番号Ｎｎｌを含む対応関係レコードＲｃ  を検索する。検索した対応関係レコードＲｃ  から、プロセッサ１６は、外部リンク番号Ｎｘｌを取り出す。
次のステップＣ６で、プロセッサ１６は、ワーキングエリア１７上の交通情報Ｉｔｒから、ステップＣ５で得た外部リンク番号Ｎｘｌを含む交通情報レコードＲｔ  を検索する。検索した交通情報レコードＲｔ  から、プロセッサ１６は、種別Ｔｉｎｆ  に「渋滞」と記述されている交通情報セットＩＳｔｒを検索し、検索した交通情報セットＩＳｔｒに値Ｖｉｎｆ  として記述されている現在の渋滞度Ｌｔｊ「０」、「１」又は「２」を取り出す。
【００４７】
次のステップＣ７で、プロセッサ１６は、ステップＣ６で「０」を取り出したか否かを判断する。「０」を取り出した場合、補正通過時間Ｔｕｄを算出する必要がないので、プロセッサ１６は、ステップＣ１２に進む。逆に、「０」でない場合には、プロセッサ１６は、補正通過時間Ｔｕｄを算出するために、ステップＣ８を行う。
【００４８】
次のステップＣ８で、プロセッサ１６は、ステップＣ６で得た現在の渋滞度（渋滞度Ｌｔｊ）と同じ組みの渋滞時推定速度Ｖｓｃを、第２の推定速度テーブルＴｓｃから取り出す。
次のステップＣ９で、プロセッサ１６は、第３の処理対象リンクレコードＲｋ  から、内部リンク距離Ｄｎｌを取り出す。
次のステップＣ１０で、プロセッサ１６は、ステップＣ８で得た渋滞時推定速度Ｖｓｃを、ステップＣ９で得た内部リンク距離Ｄｎｌに乗算して、第３の処理対象内部リンクＬｉｎの補正通過時間Ｔｕｄを算出する。
次のステップＣ１１で、プロセッサ１６は好ましくは、図１５に示すように、第２の処理対象リンクレコードＲｋ  に現在付加されている内部リンク通過時間Ｔｎｌ又は補正通過時間Ｔｕｄを消去し、直前のステップＣ１０で算出した補正通過時間Ｔｕｄを付加する。
【００４９】
次のステップＣ１２で、プロセッサ１６は、ステップＣ３で選択されていない第２の処理対象リンクレコードＲｋ  が存在するか否かを判断する。未選択のものがあれば、プロセッサ１６は再度ステップＣ３を行う。逆に、全リンクレコードＲｋ  を選択済であれば、プロセッサ１６は、図６のステップＡ１２を終了する。以上の処理によって、プロセッサ１６は、必要な第２の処理対象内部リンクＬｉｎについて、補正通過時間Ｔｕｄを算出し記録する。
【００５０】
図６のステップＡ１３において、プロセッサ１６は、正確な現在位置ＰＰｕｒを導出する。
次のステップＡ１４で、プロセッサ１６は、ステップＡ１３で導出した現在位置ＰＰｕｒを探索開始地点ＯＰとして設定する。なお、探索終了地点ＥＰは、ステップＡ１で設定された通りであるため、設定しなおす必要はない。
次のステップＡ１５で、プロセッサ１６は、上述の周知アルゴリズムに従って、再経路探索を行う。これによって、プロセッサ１６は、新たな探索開始地点ＯＰとしての現在位置ＰＰｕｒから探索終了地点ＥＰに至る第２の最適経路ＯＲ２  を探索する。ここで、第２の最適経路ＯＲ２  は、現在位置ＰＰｕｒから探索終了地点ＥＰの間をユーザが最小の旅行時間で到達可能な経路である。より具体的には、第２の最適経路ＯＲ２  は、両地点ＯＰ及びＥＰの間に存在する全内部リンクＬｉｎに現在割り当てられている内部リンク通過時間Ｔｎｌ又は補正通過時間Ｔｕｄの合計が最小の経路である。
【００５１】
次のステップＡ１６で、プロセッサ１６は、第２の最適経路ＯＲ２  を特定する第２の経路データＲＤ２  をワーキングエリア１７上で作成し保持する。第２の経路データＲＤ２  は、図１６の（Ａ）に示すように、第１の経路データＲＤ１  と同じデータ構造を有する。ただし、合計値Ｖｓｕｍ  は、第２の最適経路ＯＲ２  を構成する全内部リンクＬｉｎの内部リンク通過時間Ｔｎｌ又は補正通過時間Ｔｕｄの合計である。これら内部リンクＬｉｎの総個数を、リンク総数ＴＮｌｋは示す。リンク番号セットＳｌｎは、これら内部リンクＬｉｎを特定する内部リンク番号Ｎｎｌから構成される。例えば、図１６の（Ｂ）に示すように、探索開始地点ＯＰ及び探索終了地点ＥＰが設定され、さらに、３個の内部リンクＬｉｎ７  、Ｌｉｎ１１及びＬｉｎ１２からなる第２の最適経路ＯＲ２  が探索された場合、例えば、図１６の（Ａ）に示すように、合計値Ｖｓｕｍ  としての１５分、リンク総数ＴＮｌｋとしての３本、及び内部リンクＬｉｎ７  、Ｌｉｎ１１及びＬｉｎ１２を特定する内部リンク番号Ｎｉｎ７  、Ｎｉｎ１１及びＮｉｎ１２からなるリンク番号セットＳｌｎを含む第２の経路データＲＤ２  が作成される。このような第２の経路データＲＤ２  を、経路探索装置１はワーキングエリア１７で保持する。これによって、ワーキングエリア１７は、第１の経路データＲＤ１  及び第２の経路データＲＤ２  の２つを保持することになる。
【００５２】
上述の例では、最初の経路探索では、内部リンクＬｉｎ６  〜Ｌｉｎ１０及びからなる第１の最適経路ＯＲ１  が探索される。それに対して、受信交通情報Ｉｔｒを使って行われた再経路探索では、３個の内部リンクＬｉｎ７  、Ｌｉｎ１１及びＬｉｎ１２からなる第２の最適経路ＯＲ２  が探索される。この場合、プロセッサ１６は、内部リンクＬ８  〜Ｌ１０から構成される道路区間を通るよりも、内部リンクＬｉｎ１１及びＬｉｎ１２から構成される道路区間を通る方が短時間で、ユーザの目的地（探索終了地点ＥＰ）に到達できると判断したことになる。このように、プロセッサ１６は、最新の交通状況に考慮した経路探索を実現することができる。
【００５３】
次に、図７を参照する。ステップＡ１７で、プロセッサ１６は、第１の経路データＲＤ１  から、不要な内部リンク番号Ｎｎｌを削除する。具体的には、第２の最適経路ＯＲ２  は、本ステップＡ１７から３つのステップ前のステップＡ１４で設定された探索開始地点ＯＰからの経路である。それに対して、第１の最適経路ＯＲ１  は、ステップＡ１又は前回のステップＡ１４で設定された探索開始地点ＯＰからの経路である。ここで、図６及び図７から明らかなように、ステップＡ２８の終了後、プロセッサ１６は、ステップＡ１２を行うので、ステップＡ１２からＡ２８までの各ステップは複数回行われる可能性がある。ここで、ステップＡ１２からＡ２６までで１つのループを構成するとすると、前回のステップＡ１４は、３ステップ前に行われたステップＡ１４ではなく、前回のループで行われたステップＡ１４を意味する。また、たとえ再経路探索が行われようとも、ユーザがステップＡ１で設定された目的地（探索終了地点ＥＰ）に向かっていることには変わりはない。さらに、ユーザは、第１の最適経路ＯＲ１  に従って目的地に向かっている。以上のことから、現在の探索開始地点ＯＰ（第２の最適経路ＯＲ２  のもの）は、第１の最適経路ＯＲ１  上の点であるといえる。以上のことから、ステップＡ１７では、第１の経路データＲＤ１  から、現在の探索開始地点ＯＰ及び探索終了地点ＥＰを含む矩形領域に含まれない内部リンクＬｉｎを示す内部リンク番号Ｎｎｌが、不要なものとして削除される。従って、第１の経路データＲＤ１  において、リンク番号セットＳｌｎは、ステップＡ１７で削除されなかった１つ又は複数の内部リンク番号Ｎｎｌを含むことになる。例えば、図１６の（Ａ）に示す第２の経路データＲＤ２  が得られた場合には、ステップＡ１７で、第１の経路データＲＤ１  は、図１１の（Ａ）に示すものから、内部リンク番号Ｎｎｌ７  〜Ｎｎｌ１０を含むリンク番号セットＳｌｎに更新される。
【００５４】
再度、図７を参照する。ステップＡ１８で、プロセッサ１６は、今回作成された第２の経路データＲＤ２  のリンク番号セットＳｌｎと、ステップＡ１７で更新された第１の経路データＲＤ１  のリンク番号セットＳｌｎとが全て一致するか否かを判断する。つまり、プロセッサ１６は、第１の最適経路ＯＲ１  及び第２の最適経路ＯＲ２  が一致するか否かを判断する。両経路ＯＲ１  及びＯＲ２  が一致する場合、プロセッサ１６は、両者が相違する原因を特定する必要がないとみなして、ステップＡ１９をスキップして、ステップＡ２０を行う。逆に、両経路ＯＲ１  及びＯＲ２  が一致しない場合、プロセッサ１６はステップＡ１９を行う。
【００５５】
ステップＡ１９で、プロセッサ１６は、第１の最適経路ＯＲ１  及び第２の最適経路ＯＲ２  が相違する１つ又は複数の原因を特定する。ここで、図１７は、ステップＡ１９の詳細な処理手順を示すフローチャートである。
図１７のステップＤ１で、プロセッサ１６は、状況変化情報Ｉｓｃを新規作成又は更新する。ここで、図１８及び図１９は、ステップＤ１の詳細な処理手順を示すフローチャートの前半部分及び後半部分である。
【００５６】
まず、図１８のステップＥ１で、プロセッサ１６は、ワーキングエリア１７上に状況変化情報Ｉｓｃがあるか否かを判断する。それが無い場合、プロセッサ１６は、状況変化情報Ｉｓｃを新規作成するために、ステップＥ２に進む。
次のステップＥ２で、プロセッサ１６は、今回の交通情報Ｉｔｒの中から、未選択の交通情報レコードＲｔ  を一つ選択する。以下の説明では、ステップＥ２で選択されたものを、第１の処理対象交通情報レコードＲｔ  と称する。
次のステップＥ３で、プロセッサ１６は、第１の処理対象交通情報レコードＲｔ  から、外部リンク番号Ｎｘｌを取り出す。
【００５７】
次のステップＥ４で、プロセッサ１６は、第１の処理対象交通情報レコードＲｔ  から、未選択の交通情報セットＩＳｔｒを一つ選択する。以下の説明では、本ステップで選択された交通情報セットＩＳｔｒを、処理対象交通情報セットＩＳｔｒと称する。
【００５８】
次のステップＥ５で、プロセッサ１６は、処理対象交通情報セットＩＳｔｒを構成する種別Ｔｉｎｆ  及び内容Ｃｉｎｆ  の組み合わせを取り出す。以下の説明では、本ステップで取り出された内容Ｃｉｎｆ  を、今回の内容ＣＣｉｎｆ  と称する。
次のステップＥ６で、プロセッサ１６はさらに、前回の内容ＰＣｉｎｆ  を、ステップＥ５で取り出した種別Ｔｉｎｆ  に応じた初期内容ＩＣｉｎｆ  に設定する。ここで、プログラム１５１は、図２０に示すように、種別Ｔｉｎｆ  及び初期内容ＩＣｉｎｆ  の組みが記述される初期内容テーブルＴｉｃを含んでいる。図２０において、種別Ｔｉｎｆ  は上述した通りである。種別Ｔｉｎｆ  が「事象規制」の場合、初期内容ＩＣｉｎｆ  としては「規制無し」が記述される。また、種別Ｔｉｎｆ  が「渋滞」の場合、初期内容ＩＣｉｎｆ  としては「渋滞無し」が記述される。以上の初期内容テーブルＴｉｃから、プロセッサ１６は、ステップＥ５で取り出した種別Ｔｉｎｆ  と同じ組みの初期内容ＩＣｉｎｆ  を取り出し、取り出したものを、前回の内容ＰＣｉｎｆ  と決定する。
【００５９】
次のステップＥ７で、プロセッサ１６は、ステップＥ５で取り出した種別Ｔｉｎｆ  、ステップＥ６で決定した前回の内容ＰＣｉｎｆ  、及びステップＥ５で取り出した今回の内容ＣＣｉｎｆ  からなる状況変化情報セットＩＳｓｃを作成する。
次のステップＥ８で、プロセッサ１６は、処理対象交通情報レコードＲｔ  に、未選択の交通情報セットＩＳｔｒが残っているか否かを判断する。未選択のものがあれば、プロセッサ１６は再度ステップＥ４を行う。逆に、全交通情報セットＩＳｔｒを選択済みであれば、プロセッサ１６はステップＥ９を行う。
【００６０】
ステップＥ９で、プロセッサ１６は、ステップＥ２で選択された処理対象交通情報レコードＲｔ  について、ステップＥ７で作成された全ての状況変化情報セットＩＳｓｃと、ステップＥ３で取り出された外部リンク番号Ｎｘｌとを含む状況変化情報レコードＲｓｃを作成する。以上のステップＥ９を行うことで、プロセッサ１６は、図２１に状況変化レコードＲｓｃ１  として例示するように、対象外部リンクＬｅｘについて、いくつかの状況変化情報セットＩＳｓｃを有する状況変化レコードＲｓｃを作成する。以上の状況変化レコードＲｓｃは、対象外部リンクＬｅｘにおける交通状況の変化を示す。
【００６１】
次のステップＥ１０で、プロセッサ１６は、今回の交通情報Ｉｔｒに、未選択の交通情報レコードＲｔ  が残っているか否かを判断する。未選択のものがあれば、プロセッサ１６は再度ステップＥ２を行う。逆に、全交通情報レコードＲｔ  を選択済みであれば、プロセッサ１６は、図１７のステップＤ１を終了する。その結果、プロセッサ１６は、図２１に示すように、全ての対象外部リンクＬｅｘについて作成されたいくつかの状況変化レコードＲｓｃを有する状況変化情報Ｉｓｃを作成したことになる。
【００６２】
また、図１８のステップＥ１で、状況変化情報Ｉｓｃがワーキングエリア１７に既に作成されていると判断された場合、状況変化情報Ｉｓｃを更新するために、プロセッサ１６はステップＥ１１に進む。
ステップＥ１１で、プロセッサ１６は、ワーキングエリア１７上の状況変化情報Ｉｓｃから、未選択の状況変化レコードＲｓｃを選択する。以下の説明では、ステップＥ１２で選択されたものを、処理対象状況変化レコードＲｓｃと称する。
次のステップＥ１２で、プロセッサ１６は、ステップＡ１１で格納された交通情報Ｉｔｒの中から、処理対象状況変化レコードＲｓｃと同じ外部リンク番号Ｎｘｌを有する交通情報レコードＲｔ  を一つ選択する。以下の説明では、ステップＥ１２で選択されたものを、第２の処理対象交通情報レコードＲｔ  と称する。
【００６３】
次のステップＥ１３で、プロセッサ１６は、対象状況レコードＲｓｃから、未選択の状況変化情報セットＩＳｓｃを選択する。以下の説明では、ステップＥ１３で選択された状況変化情報セットＩＳｓｃを処理対象状況変化情報セットＩＳｓｃと称する。
次のステップＥ１４で、プロセッサ１６は、処理対象状況変化情報セットＩＳｓｃに設定されている今回の内容ＣＣｉｎｆ  を、前回の内容ＰＣｉｎｆ  に変更する。
【００６４】
次のステップＥ１５で、プロセッサ１６は、第２の処理対象交通情報レコードＩｔｒの中に、対象状況変化情報セットＩＳｓｃ内の種別Ｔｉｎｆ  を有する交通情報セットＩＳｔｒがあるか否かを判断する。以下、ステップＥ１５で検索される交通情報セットＩＳｔｒのことを、第１の処理対象交通情報セットＩＳｔｒと称する。
【００６５】
ステップＥ１５で、第１の処理対象交通情報セットＩＳｔｒがあると判断された場合、対象外部リンクＬｅｘで交通事故、交通規制又は交通渋滞が起こっていることになる。このような場合、ステップＥ１６で、プロセッサ１６は、第１の処理対象交通情報セットＩＳｔｒから内容Ｃｉｎｆ  を取り出し、処理対象状況変化情報セットＩＳｓｃに、今回の内容ＣＣｉｎｆ  として設定する。
【００６６】
逆に、ステップＥ１５で、第１の処理対象交通情報セットＩＳｔｒが無いと判断された場合、対象外部リンクＬｅｘで発生していた交通事故の処理が終了するか、交通規制又は交通渋滞が解消したことになる。このような場合、ステップＥ１７で、プロセッサ１６は、前述の初期内容テーブルＴｉｃから、対象状況変化情報セットＩＳｓｃ内の種別Ｔｉｎｆ  に対応する初期内容ＩＣｉｎｆ  を取り出し、処理対象状況変化情報セットＩＳｓｃに、今回の内容ＣＣｉｎｆ  として設定する。
【００６７】
ステップＥ１６又はＥ１７が終了すると、ステップＥ１８で、プロセッサ１６は、対象状況レコードＲｓｃに未選択の状況変化情報セットＩＳｓｃが残っているか否かを判断する。未選択のものがあれば、プロセッサ１６は再度ステップＥ１３を行う。逆に、対象状況レコードＲｓｃの全状況変化情報セットＩＳｓｃを選択済であれば、プロセッサ１６は、ステップＥ１９を行う。
次のステップＥ１９で、プロセッサ１６は、第２の処理対象交通情報レコードＲｔ  に未選択の交通情報セットＩＳｔｒが残っているか否かを判断する。未選択の交通情報セットＩＳｔｒが残っていない場合、プロセッサ１６は、ステップＥ２０〜Ｅ２４をスキップして、ステップＥ２５を行う。逆に、未選択の交通情報セットＩＳｔｒが残っていると判断された場合には、プロセッサ１６は、対象外部リンクＬｅｘ上で、新たに交通事故、交通規制又は交通渋滞が発生したとみなして、ステップＥ２０を行う。
【００６８】
ステップＥ２０で、プロセッサ１６は、第２の処理対象交通情報レコードＲｔ  から、未選択の交通情報セットＩＳｔｒを一つ選択する。以下の説明では、ステップＥ２０で選択されたものを、第２の処理対象交通情報セットＩＳｔｒと称する。
次のステップＥ２１〜Ｅ２４で、プロセッサ１６は、ステップＥ５〜Ｅ８と同様にして、新たな状況変化情報セットＩＳｓｃを作成する。
次に、ステップＥ２４で、プロセッサ１６は、処理対象交通情報レコードＲｔ  に、未選択の交通情報セットＩＳｔｒが残っているか否かを判断する。未選択のものがあれば、プロセッサ１６は再度ステップＥ２０を行う。逆に、全交通情報セットＩＳｔｒを選択済みであれば、プロセッサ１６はステップＥ２５を行う。
【００６９】
ステップＥ２５で、プロセッサ１６は、処理対象状況変化情報レコードＲｓｃに、ステップＥ２３で作成した各状況変化情報セットＩＳｓｃを追加する。これによって、状況変化レコードＲｓｃは、対象外部リンクＬｅｘにおける前回の交通状況と今回の交通状況との変化を示す。
次のステップＥ２６で、プロセッサ１６は、ワーキングエリア１７上の状況変化情報Ｉｓｃに未選択の状況変化レコードＲｓｃが残っているか否かを判断する。未選択の状況変化レコードＲｓｃが残っている場合、プロセッサ１６は、再度ステップＥ１１を行う。逆に、全状況変化レコードＲｓｃを選択済の場合、プロセッサ１６は、状況変化情報Ｉｓｃの更新を終了したとステップみなして、図１７のステップＤ１を終了する。
【００７０】
ステップＤ１の終了後、ステップＤ２で、プロセッサ１６は、記憶装置１１内の対応関係リストＬｃｏｎｎを参照して、第１の経路データＲＤ１  及び第２の経路データＲＤ２  に含まれる内部リンク番号Ｎｎｌの内、可能なものを、外部リンク番号Ｎｘｌに置換する。具体的には、各対応関係レコードＲｃ  に含まれる全内部リンク番号Ｎｎｌを、第１の経路データＲＤ１  及び第２の経路データＲＤ２  の中に見つけた場合に、それら内部リンク番号Ｎｎｌを外部リンク番号Ｎｘｌに置換する。以上の置換処理の結果、プロセッサ１６は、図２２の（Ａ）に示すような、第１の置換経路データＰＲＤ１  及び第２の置換経路データＰＲＤ２  を作成する。
【００７１】
図２２の（Ａ）において、第１の置換経路データＰＲＤ１  及び第２の置換経路データＰＲＤ２  は、第１の経路データＲＤ１  （図１１の（Ａ）参照）及び第２の経路データＲＤ２  （図１６の（Ａ）参照）と比較すると、必要な内部リンク番号Ｎｎｌが外部リンク番号Ｎｘｌに代わる点で相違する。例えば、図１１の（Ｂ）において、１本の内部リンクＬｉｎ７  で１本の外部リンクＬｅｘ１  が構成され、２本の内部リンクＬｉｎ８  及びＬｉｎ９  で１本の外部リンクＬｅｘ２  が構成され、さらに、１本の内部リンクＬｉｎ１０で１本の外部リンクＬｅｘ３  が構成される場合、第１の置換経路データＰＲＤ１  においてリンク番号セットＳｌｎは、図２２の（Ｂ）に示すように、外部リンクＬｅｘ１  、Ｌｅｘ２  及びＬｅｘ３  の外部リンク番号Ｎｘｌ１  、Ｎｘｌ２  及びＮｘｌ３  からなる。さらに、例えば、図１６の（Ｂ）において、２本の内部リンクＬｉｎ１１及びＬｉｎ１２で１本の外部リンクＬｅｘ４  が構成される場合、第２の置換経路データＰＲＤ２  においてリンク番号セットＳｌｎは、図２２の（Ｃ）に示すように、外部リンクＬｅｘ１  及びＬｅｘ４  の外部リンク番号Ｎｘｌ１  及びＮｘｌ４  からなる。
【００７２】
ステップＤ２の終了後、ステップＤ３で、プロセッサ１６は、ステップＤ２で作成された第１の置換経路データＰＲＤ１  及び第２の置換経路データＰＲＤ２  から、不必要な外部リンク番号Ｎｘｌを削除して、第１の差分リンクデータＤＬＤ１  及び第２の差分リンクデータＤＬＤ２  を作成する。具体的には、第１の差分リンクデータＤＬＤ１  は、図２３の（Ａ）に示すように、第１の置換経路データＰＲＤ１  には含まれるが、第２の置換経路データＰＲＤ２  には含まれない全ての外部リンク番号Ｎｘｌと、それら外部リンク番号Ｎｘｌの総数ＴＮｘｌとからなる。例えば、第１の置換経路データＰＲＤ１  及び第２の置換経路データＰＲＤ２  が図２２の（Ｂ）及び（Ｃ）のものである場合、第１の差分リンクデータＤＬＤ１  は、図２３の（Ａ）に示すように、２個の外部リンク番号Ｎｘｌ２  及びＮｘｌ３  を含む。また、第２の差分リンクデータＤＬＤ２  は、図２３の（Ｂ）に示すように、第２の置換経路データＰＲＤ２  には含まれるが、第１の置換経路データＰＲＤ１  には含まれない全ての外部リンク番号Ｎｘｌと、それら外部リンク番号Ｎｘｌの総数ＴＮｘｌとからなる。例えば、第１の置換経路データＰＲＤ１  及び第２の置換経路データＰＲＤ２  が図２２の（Ｂ）及び（Ｃ）のものである場合、第２の差分リンクデータＤＬＤ２  は、図２３の（Ｂ）に示すように、１個の外部リンク番号Ｎｘｌ４  を含む。
【００７３】
ステップＤ３の終了後、ステップＤ４で、プロセッサ１６は、ステップＤ１で新規作成又は更新した状況変化情報Ｉｓｃから、第１の差分リンクデータＤＬＤ１  に含まれる外部リンク番号Ｎｘｌを含む状況変化情報セットＩＳｓｃを全て取り出して、図２４の（Ａ）に示すように、これら状況変化情報セットＩＳｓｃからなる回避経路情報Ｉｓｓを作成する。上述のように、第１の差分リンクデータＤＬＤ１  が図２３の（Ａ）に示すものの場合、ステップＤ４で作成されるのは、外部リンク番号Ｎｘｌ２  及びＮｘｌ３  を含む２個の状況変化情報セットＩＳｓｃからなる回避情報Ｉｓｓである。
【００７４】
また、ステップＤ５では、プロセッサ１６は、ステップＤ１で新規作成又は更新した状況変化情報Ｉｓｃから、第２の差分リンクデータＤＬＤ２  に含まれる外部リンク番号Ｎｘｌを含む状況変化情報セットＩＳｓｃを全て取り出して、図２４の（Ｂ）に示すように、これら状況変化情報セットＩＳｓｃからなる利用経路情報Ｉｐｒを作成する。上述のように、第２の差分リンクデータＤＬＤ２  が図２３の（Ｂ）に示すものの場合、ステップＤ５で作成されるのは、外部リンク番号Ｎｘｌ４  を含む１個の状況変化情報セットＩＳｓｃからなる利用経路情報Ｉｐｒである。
【００７５】
以上のステップＤ５の終了により、第１の最適経路ＯＲ１  及び第２の最適経路ＯＲ２  が相違する原因を特定できたとして、プロセッサ１６は、図７のステップＡ１９を終了する。
次のステップＡ２０及びＡ２１で、プロセッサ１６は、ステップＡ６及びＡ７と同様にして、現在位置ＰＰｕｒを導出した後、表示対象範囲の地図データＤｃａｒｔを選択する。
次のステップＡ２２で、プロセッサ１６は、表示画像データＤｄｓｐ  を作成する。ここで、図２５は、ステップＡ２２の詳細な処理手順を示すフローチャートである。
【００７６】
図２５のステップＦ１において、プロセッサ１６は、ステップＡ１９を行ったか否かを判断する。ステップＡ１９を行っていないと判断した場合、ステップＦ２で、プロセッサ１６は、第１の最適経路ＯＲ１  及び第２の最適経路ＯＲ２  には相違点は無いことから、前述のステップＡ８と同様にして、表示画像データＤｄｓｐ１と、必要な合成音声データＤａｄ１  とを作成する。
次のステップＦ３で、プロセッサ１６は、前述のステップＡ９と同様にして、作成した表示画像データＤｄｓｐ１を表示装置１８に転送し、作成した合成音声データＤａｄ１  をスピーカ１９に転送する。表示装置１８は、受信した表示画像データＤｄｓｐ１に従って、図１２に示す画像を表示する。スピーカ１９は、受信した合成音声データＤａｄ１  に従って音声を出力する。
【００７７】
逆に、ステップＦ１でステップＡ１９を行っていると判断した場合、プロセッサ１６は、少なくとも回避経路情報Ｉｓｓ及び利用経路情報Ｉｐｒを構成する各外部リンクＬｅｘの影響度Ｉｎｆを算出するために、ステップＦ４を行う。
ステップＦ４で、プロセッサ１６は、まず、ワーキングエリア１７上の回避経路情報Ｉｓｓ及び利用経路情報Ｉｐｒから、外部リンク番号Ｎｘｌ、前回の内容ＰＣｉｎｆ  に設定されている渋滞度（以下、前回の渋滞度と称する）、及び今回の内容ＣＣｉｎｆ  に設定されている渋滞度（以下、今回の渋滞度と称する）の組み合わせを全て取得する。
次のステップＦ５で、プロセッサ１６は、ステップＦ４で取得した組み合わせの中から一つを選択する。以下の説明では、本ステップで選択された組み合わせ、外部リンク番号Ｎｘｌ、前回の渋滞度及び今回の渋滞度を、処理対象の組み、処理対象の外部リンク番号Ｎｘｌ、処理対象の前回の渋滞度及び処理対象の今回の渋滞度と称する。
【００７８】
次のステップＦ６で、プロセッサ１６は、記憶装置１１の対応関係リストＬｃｏｎｎから、処理対象の外部リンク番号Ｎｘｌを構成する全内部リンク番号Ｎｎｌを取得する。
次のステップＦ７で、プロセッサ１６は、記憶装置１１のリンクリストＬｌｉｎｋから、ステップＦ６で取り出した各内部リンク番号Ｎｎｌを含むリンクレコードＲｋ  を選択した後、選択した各リンクレコードＲｋ  から、内部リンク距離Ｄｎｌ及び道路種別Ｔｒｄの組みを取得する。
【００７９】
次のステップＦ８で、プロセッサ１６は、ステップＦ７で取得した内部リンク距離Ｄｎｌの総計及び道路種別Ｔｒｄと、前回の渋滞度と、前述の第１の推定速度テーブルＴｆｓ又は第２の推定速度テーブルＴｓｃに記述された情報とを使って、処理対象の外部リンクＬｅｘを前回の交通状況下でユーザが通過する際に要したと想定される外部リンク通過時間（以下、前回の外部リンク通過時間）Ｔｐｘを算出する。具体的には、前回の渋滞度が０の場合には、第１の推定速度テーブルＴｆｓに記述された値が、外部リンク通過時間Ｔｐｘの算出に使われる。この場合、従って、外部リンク通過時間Ｔｐｘは、内部リンク距離Ｄｎｌの総計と、道路種別Ｔｒｄに対応する初期推定速度Ｖｆｓとの乗算により得られる。また、前回の渋滞度が０でない場合には、第２の推定速度テーブルＴｓｃに記述された値が、外部リンク通過時間Ｔｐｘの算出に使われる。この場合、従って、外部リンク通過時間Ｔｐｘは、内部リンク距離Ｄｎｌの総計と、渋滞度に対応する渋滞時推定速度Ｖｓｃとの乗算により得られる。
【００８０】
ステップＦ８の後、ステップＦ９で、プロセッサ１６は、ステップＦ７で取得した内部リンク距離Ｄｎｌの総計及び道路種別Ｔｒｄと、今回の渋滞度と、前述の第１の推定速度テーブルＴｆｓ又は第２の推定速度テーブルＴｓｃに記述された情報とを使って、処理対象の外部リンクＬｅｘを今回の交通状況下でユーザが通過する際に要したと想定される外部リンク通過時間（以下、今回の外部リンク通過時間）Ｔｃｘを算出する。今回の外部リンク通過時間Ｔｃｘの算出方法については、ステップＦ８と同様であるので、その詳細な説明を省略する。
【００８１】
次のステップＦ１０で、プロセッサ１６は、今回の外部リンク通過時間Ｔｃｘから前回の外部リンク通過時間Ｔｐｘを引き算して、処理対象の外部リンクＬｅｘの交通状況の変化の度合い（以下、変化レベルと称する）Ｌｔｃを算出する。一般的に、外部リンクの通過時間が小さい程交通状況は良いので、変化レベルＬｔｃが正の値であれば、処理対象の外部リンクＬｅｘの交通状況は前回と比べて悪化していることになる。逆に、変化レベルＬｔｃが負であれば、その交通状況は改善されていることになる。
【００８２】
次のステップＦ１１で、プロセッサ１６は、ステップＦ４で取得した組み合わせに、未選択のものが残っているか否かを判断する。未選択の組みが残っていれば、プロセッサ１６は再度ステップＦ５を行う。逆に、全組み合わせを選択済みであれば、プロセッサ１６はステップＦ１２を行う。
【００８３】
ステップＦ１２で、プロセッサ１６は、ワーキングエリア１７に作成されている第１の置換経路データＰＲＤ１  、第２の置換経路データＰＲＤ２  、回避経路情報Ｉｓｓ、及び利用経路情報Ｉｐｒを使って、図２６に示すように、表示範囲の地図画像Ｍｄｓｐ  を含む表示画像データＤｄｓｐ２を作成する。より具体的には、プロセッサ１６は、ステップＡ２１で選択した地図データＤｃａｒｔを使って、ワーキングエリア１７上に、地図画像Ｍｄｓｐ  を描画する。また、プロセッサ１６は、第１の置換経路データＰＲＤ１  を使って、表示対象範囲内に含まれる第１の最適経路ＯＲ１  を、描画した地図画像Ｍｄｓｐ  に合成する。さらに、プロセッサ１６は、合成した第１の最適経路ＯＲ１  において、回避経路情報Ｉｓｓで特定される外部リンクＬｅｘについては、他の外部リンクＬｅｘ又は内部リンクＬｉｎとは異なる色、線種又は方法で表現する。さらに、プロセッサ１６は、回避経路情報Ｉｓｓで特定される外部リンクＬｅｘの現在の渋滞度及びステップＦ１０で算出した変化レベルＬｔｃを合成する。さらに、プロセッサ１６は、第２の置換経路データＰＲＤ２  を使って、表示対象範囲内に含まれる第２の最適経路ＯＲ２  を、描画した地図画像Ｍｄｓｐ  に合成する。さらに、プロセッサ１６は、合成した第２の最適経路ＯＲ２  において、利用経路情報Ｉｐｒで特定される外部リンクＬｅｘについては、他の外部リンクＬｅｘ又は内部リンクＬｉｎとは異なる色、線種又は方法で表現する。さらに、プロセッサ１６は、利用経路情報Ｉｐｒで特定される外部リンクＬｅｘの現在の渋滞度及びステップＦ１０で算出した変化レベルＬｔｃを合成する。さらに、プロセッサ１６は、描画した地図画像Ｍｄｓｐ  において、ステップＡ２０で導出した正確な現在位置ＰＰｕｒに、ユーザの現在位置を示すマーク画像Ｍｕｒを合成する。これによって、表示画像データＤｄｓｐ２が完成する。
【００８４】
また、ステップＦ１３で、プロセッサ１６は、ユーザの案内に用いるものが第１の最適経路ＯＲ１  から第２の最適経路ＯＲ２  へと変更した理由を表す合成音声データＤａｄ２  を作成する。ここで、図２７は、ステップＦ１３の詳細な処理手順を示すフローチャートである。
図２７のステップＧ１で、プロセッサ１６は、ワーキングエリア１７上の回避経路情報Ｉｓｓから、ステップＦ１０で算出される変化レベルＬｔｃの絶対値が最大の外部リンクＬｅｘの外部リンク番号Ｎｘｌを選択する。
次のステップＧ２で、プロセッサ１６は、ステップＧ１で選択した外部リンク番号Ｎｘｌを有する状況変化情報レコードＲｓｃから、未選択の状況変化情報セットＩＳｓｃを一つ選択する。
【００８５】
次のステップＧ３で、プロセッサ１６は、プログラム１５１に予め準備されている基本パターンに、ステップＧ２で選択された状況変化情報セットＩＳｓｃに設定されている種別Ｔｉｎｆ  を当てはめて、ユーザの案内に用いるものが第１の最適経路ＯＲ１  から第２の最適経路ＯＲ２  へと変更した理由の一部を表す部分合成音声データＰＤａｄ２  を作成する。例えば、基本パターンが「○○○のため案内経路を変更します。」であり、今回の内容ＣＣｉｎｆ  が「交通規制」である場合には、「交通規制のため案内経路を変更します。」という内容の合成音声が作成される。
次のステップＧ４で、プロセッサ１６は、対象となる状況変化情報レコードＲｓｃに、未選択の状況変化情報セットＩＳｓｃが残っているか否かを判断する。未選択のものが残っていると判断した場合、プロセッサ１６は再度、ステップＧ２を行う。逆に、全状況変化情報セットＩＳｓｃを選択済みであると判断した場合、プロセッサ１６はステップＧ５に進む。
ステップＧ５で、プロセッサ１６は、各ステップＧ３で作成された合成音声を含む合成音声データＤａｄ２  を作成し、図２５のステップＦ１３を終了する。
【００８６】
次のステップＦ１４で、プロセッサ１６は、作成した表示画像データＤｄｓｐ２を、ワーキングエリア１７から表示装置１８に転送し、作成した合成音声データＤａｄ２  をスピーカ１９に転送する。表示装置１８は、受信した表示画像データＤｄｓｐ２に従って、図１２又は図２６に示す画像を表示する。なお、図２６では、２次元の地図画像Ｍｄｓｐ  を例示しているが、これに限らず、３次元の地図画像Ｍｄｓｐ  が生成され出力されても良い。また、スピーカ１９は、受信した合成音声データＤａｄ２  が表す音声を出力する。以上により、図７のステップＡ２２が終了し、プロセッサ１６は、ステップＡ２３を行う。
【００８７】
次のステップＡ２３で、プロセッサ１６は、ステップＡ１０と同様に、ステップＡ２０で導出した現在位置ＰＰｕｒと、ステップＡ１で設定した探索終了地点ＥＰとが一致する場合、ユーザを探索終了地点ＥＰ（つまり、ユーザの目的地）まで案内し終えたとみなして、図６及び図７の処理を終了する。逆に、両者が不一致の場合、プロセッサ１６は、ステップＡ２５に進む。
ステップＡ２５で、プロセッサ１６は、ステップＡ１１と同様に、交通情報Ｉｔｒが格納されていない場合には、ステップＡ２０を再度行う。逆に、交通情報Ｉｔｒが格納されている場合には、プロセッサ１６は、ステップＡ２６を行う。
【００８８】
ステップＡ２６で、プロセッサ１６は、再度ステップＡ１９を行う可能性があることから、第２の経路データＲＤ２  及び第２の置換経路データＰＲＤ２  を、第１の経路データＲＤ１  及び第１の置換経路データＰＲＤ１  に設定する。以上の処理が終了すると、プロセッサ１６は、ステップＡ１２を再度行う。
【００８９】
以上説明したように、本実施形態によれば、２種類の最適経路ＯＲ１  及びＯＲ２  を導出した後、両経路ＯＲ１  及びＯＲ２  が相違する原因を特定し、その原因を表す表示画像データＤｄｓｐ２及び合成音声データＤａｄ２  を作成することができるので、ユーザが変更後の第２の最適経路ＯＲ２  に従って安心して目的地に向かうことが可能な経路探索装置１を提供することが可能となる。
【００９０】
なお、以上の実施形態では、経路探索装置１は、第１の経路データＲＤ１  の導出後、交通情報Ｉｔｒの格納に応答して、第２の経路データＲＤ２  を導出するようにしていたが、これに限らず、例えば特開平９−２９２２５２号公報に開示されれているように、互いに異なる条件で２回続けて経路探索を行うことで得られる第１の経路データＲＤ１  及び第２の経路データＲＤ２  を使って、第１の最適経路ＯＲ１  及び第２の最適経路ＯＲ２  が相違する原因を特定しても良い。このように第１の最適経路ＯＲ１  及び第２の最適経路ＯＲ２  が相違する原因が提供されるので、ユーザは両者の内の一方を選択し易くなる。ここで、経路探索の条件の典型例としては、最新の交通情報Ｉｔｒを使うという条件、過去の交通情報Ｉｔｒを使うという条件、目的地に到達するまでに要する料金を考慮するという条件がある。
【００９１】
また、以上の実施形態では、経路探索装置１は、経路探索により得た複数の経路と、それらが相違する原因とをそのまま出力していた。しかし、これに限らず、経路探索装置１は、互いに異なる条件で複数回続けて経路探索を行う場合には、それにより得られる複数の経路から、ユーザの指定に従って１つを選択する度に、ユーザが選択した経路と、今回選択した経路が前回選択された経路と相違する原因とを地図画像Ｍｄｓｐ  に合成するようにしても良い。さらには、ユーザの選択の度に、地図画像Ｍｄｓｐ  に合成する内容を変更しても良い。
【００９２】
また、以上の実施形態では、経路探索装置１は、２個の経路ＯＲ１  及びＯＲ２  を導出していたが、これに限らず、３個以上の最適経路を導出し、それらが相違する原因を特定しても構わない。
【００９３】
また、経路探索装置１は、経路探索により得られた複数の経路、例えば、経路ＯＲ１  及びＯＲ２  を同一条件で再評価した後に、いずれか１つを推奨経路として選択する。その後に、経路探索装置１は、推奨経路と、残りの経路と、それらが相違する原因を出力するようにしても良い。
【００９４】
また、以上の実施形態では、経路探索装置１は、交通情報Ｉｔｒが格納される度に、再経路探索を行うようにしていた。つまり、経路探索装置１は、連続する２個の交通情報Ｉｔｒを使って、２経路ＯＲ１  及びＯＲ２  が相違する原因を特定していた。しかし、周知のように経路探索は非常にプロセッサ１６に負担をかけるので、経路探索装置１は好ましくは、次回の交通情報Ｉｔｒではなく、複数個後の交通情報Ｉｔｒが格納された時に、再経路探索を行うようにしても良い。
【００９５】
また、以上の実施形態では、経路探索装置１は、地図画像Ｍｄｓｐ  に、第１の経路ＯＲ１  及び第２の経路ＯＲ２  の双方を構成する外部リンクＬｅｘに現在の渋滞度及び変化レベルＬｔｃを合成していたが、これらだけではなく、第１の経路ＯＲ１  及び第２の経路ＯＲ２  の周辺の外部リンクＬｅｘにも現在の渋滞度及び変化レベルＬｔｃを合成するようにしても良い。また、現在の渋滞度及び変化レベルＬｔｃは、対象となる外部リンクＬｅｘ上に合成されることがさらに好ましい。さらに、経路探索装置１は、地図画像Ｍｄｓｐ  と、現在の渋滞度及び変化レベルＬｔｃとを合成せずに、ユーザに個別的に提供しても良い。
【００９６】
また、以上の実施形態では、プロセッサ１６は、ステップＦ１３を行うことで、合成音声データＤａｄ２  を作成していた。これにより、最適経路の変化に最も影響を与えた外部リンクＬｅｘをユーザは知ることができる。また、合成音声データＤａｄ２  は、対象となる外部リンクＬｅｘの道路名や最寄りの交差店名を合成音声を使って、ユーザに伝えるようにしても良い。さらに、プロセッサ１６は、回避経路情報Ｉｓｓ又は利用経路情報Ｉｐｒに含まれる外部リンクＬｅｘを変化レベルＬｔｃが大きい順番に並べ、その順番に従って状況変化情報レコードＲｓｃを選択し、選択したものを使って順番に合成音声データＤａｄ２  を作成しても構わない。
【００９７】
また、ユーザの現在位置から最も近い外部リンクＬｅｘを含む状況変化情報レコードＲｓｃを使って、合成音声データＤａｄ２  を作成するのも同様に好ましい。さらに、同様に、また、プロセッサ１６は、回避経路情報Ｉｓｓ又は利用経路情報Ｉｐｒに含まれる外部リンクＬｅｘをユーザの現在位置から近い順番に並べ、その順番に従って状況変化情報レコードＲｓｃを選択し、選択したものを使って順番に合成音声データＤａｄ２  を作成しても構わない。
【００９８】
また、ユーザが複数の経路のいずれかを選択可能な場合、経路探索装置１は、回避経路情報Ｉｓｓ又は利用経路情報Ｉｐｒに含まれる状況変化情報レコードＲｓｃを選択し、選択したものを使って順番に合成音声データＤａｄ２  を作成しても構わない。
【００９９】
また、以上の実施形態では、プロセッサ１６は、利用経路情報Ｉｐｒを使って、合成音声データＤａｄ２  を作成しても良い。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る経路探索装置１のハードウェア構成を示す模式図である。
【図２】図１に示す記憶装置１１に格納される地図データＤｃａｒｔで表現される道路網を示す模式図である。
【図３】図１に示す記憶装置１１に格納される地図データＤｃａｒｔの詳細なデータ構造を示す模式図である。
【図４】図１に示す受信機１４が受信する交通情報Ｉｔｒの詳細なデータ構造を示す模式図であり、交通情報Ｉｔｒに設定される種別Ｔｉｎｆ  及び内容Ｃｉｎｆ  を説明するための図である。
【図５】一般的な路車間通信システム及び／又はＶＩＣＳで使われる道路網を示す模式図である。
【図６】図１のプログラム１５１に記述されたプロセッサ１６の処理手順を示すフローチャートの前半部分である。
【図７】図１のプログラム１５１に記述されたプロセッサ１６の処理手順を示すフローチャートの後半部分である。
【図８】図１のプログラム１５１に記述される第１の推定速度テーブルＴｆｓを示す模式図である。
【図９】図６に示すステップＡ３の詳細な処理手順を示すフローチャートである。
【図１０】図９のステップＢ５で行われる処理を示す模式図である。
【図１１】図６のステップＡ５で作成される第１の経路データＲＤ１  を説明するための図である。
【図１２】図６のステップＡ８で作成される表示画像データＤｄｓｐ１が表す地図画像Ｍｄｓｐ  を示す模式図である。
【図１３】図１のプログラム１５１に記述される第２の推定速度テーブルＴｓｃを示す模式図である。
【図１４】図６のステップＡ１２の詳細な処理手順を示すフローチャートである。
【図１５】図１４のステップＣ１１で行われる処理を示す模式図である。
【図１６】図６のステップＡ１５で作成される第２の経路データＲＤ２  を説明するための図である。
【図１７】図７のステップＡ１９の詳細な処理手順を示すフローチャートである。
【図１８】図１７のステップＤ１の詳細な処理手順を示すフローチャートの前半部分である。
【図１９】図１７のステップＤ１の詳細な処理手順を示すフローチャートの後半部分である。
【図２０】図１のプログラム１５１に記述される初期内容テーブルＴｉｃを示す模式図である。
【図２１】図１７のステップＤ１で作成される状況変化情報Ｉｓｃの詳細なデータ構造を示す模式図である。
【図２２】図１７のステップＤ２で作成される第１の置換経路データＰＲＤ１  及び第２の置換経路データＰＲＤ２  を説明するための図である。
【図２３】図１７のステップＤ３で作成される第１の差分リンクデータＤＬＤ１  及び第２の差分リンクデータＤＬＤ２  を説明するための図である。
【図２４】図１７のステップＤ４で作成される回避経路情報Ｉｓｓ、及びステップＤ５で作成される利用経路情報Ｉｐｒを示す模式図である。
【図２５】ステップＡ２２の詳細な処理手順を示すフローチャートである。
【図２６】図２５のステップＦ１２で作成される表示画像データＤｄｓｐ２が表す地図画像Ｍｄｓｐ  を示す模式図である。
【図２７】図２５のステップＦ１３の詳細な処理手順を示すフローチャートである。
【符号の説明】
１…経路探索装置
１１…記憶装置
１２…入力装置
１３…ロケータ
１４…受信機
１５…プログラムメモリ
１５１…コンピュータプログラム
１６…プロセッサ
１７…ワーキングエリア
１８…表示装置
１９…スピーカ
【図１】
2004251773.tif 000003
【図２】
2004251773.tif 000004
【図３】
2004251773.tif 000005
【図４】
2004251773.tif 000006
【図５】
2004251773.tif 000007
【図６】
2004251773.tif 000008
【図７】
2004251773.tif 000009
【図８】
2004251773.tif 000010
【図９】
2004251773.tif 000011
【図１０】
2004251773.tif 000012
【図１１】
2004251773.tif 000013
【図１２】
2004251773.tif 000014
【図１３】
2004251773.tif 000015
【図１４】
2004251773.tif 000016
【図１５】
2004251773.tif 000017
【図１６】
2004251773.tif 000018
【図１７】
2004251773.tif 000019
【図１８】
2004251773.tif 000020
【図１９】
2004251773.tif 000021
【図２０】
2004251773.tif 000022
【図２１】
2004251773.tif 000023
【図２２】
2004251773.tif 000024
【図２３】
2004251773.tif 000025
【図２４】
2004251773.tif 000026
【図２５】
2004251773.tif 000027
【図２６】
2004251773.tif 000028
【図２７】
2004251773.tif 000029