(57)【要約】【課題】実際の道路状況を推測し、実際の道路状況に合わせた経路誘導を実現し、また、送信するデータ量を減らす。【解決手段】ナビゲーション装置は、道路地図データに存在しない新規道路を走行した際に少なくとも走行軌跡検出手段によって検出された新規道路の走行軌跡の情報を収集する走行軌跡情報収集手段を備え、収集された新規道路の走行軌跡の情報を情報センタへ送信するように構成され、そして、情報センタは、複数の道路地図データを比較して、廃止道路と新規道路を抽出し、これら廃止道路と新規道路に基づいて種々の道路変化モデルを作成するモデル作成手段と、ナビゲーション装置から新規道路の走行軌跡の情報を受信し、この受信した新規道路の走行軌跡の情報と道路変化モデルと道路地図データとに基づいて新規道路と廃止道路とを推測する推測手段とを備えた。【選択図】図３
2015007657.tif 000002
【特許請求の範囲】
【請求項１】
第１の道路地図データを記憶する記憶手段と、移動体の走行軌跡を検出する走行軌跡検出手段とを備えると共に、情報を外部へ送信する通信手段を備えたナビゲーション装置と、
第２の道路地図データを記憶すると共に、前記ナビゲーション装置に対して情報を通信する通信手段を備えた情報センタと、を備える道路情報更新システムにおいて、
前記情報センタは、前記第１の道路地図データを備え、前記ナビゲーション装置から送信された目的地の情報と前記移動体の出発地の情報を受信し、前記第１の道路地図データを使って現在地から目的地までの経路Ｒ１を算出する処理と、この算出された経路Ｒ１の案内情報を算出する処理とを実行し、
前記第２の道路地図データを使って現在地から目的地までの経路Ｒ２を算出する処理と、この算出された経路Ｒ２の案内情報を算出する処理とを実行し、
前記経路Ｒ１の案内情報と前記経路Ｒ２の案内情報とを比較し、前記経路Ｒ１に存在して前記経路Ｒ２に存在しない案内情報をキャンセルする案内情報キャンセル情報と、前記経路Ｒ１に存在しない案内情報であって前記経路Ｒ２に存在する案内情報を追加する案内情報追加情報とを前記ナビゲーション装置へ送信するように構成され、
前記ナビゲーション装置は、前記情報センタからの前記案内情報キャンセル情報と前記案内情報追加情報を受信し、この受信した前記案内情報キャンセル情報と前記案内情報追加情報に基づいて前記経路Ｒ１の案内情報に対して案内情報のキャンセルと案内情報の追加を反映させるように構成されていることを特徴とする道路情報更新システム。
【請求項２】
道路を走行する移動体に搭載され、前記移動体の走行軌跡を検出する走行軌跡検出手段と、第１の道路地図データを記憶する記憶手段と、情報を外部へ送信する通信手段とを備えたナビゲーション装置において、
前記移動体の出発地の情報と目的地の情報とを情報センタへ送信するように構成され、
前記第１の道路地図データを使って出発地から目的地までの経路Ｒ１を算出する処理と、この算出された経路Ｒ１の案内情報を算出する処理とを実行するように構成され、更に、
前記情報センタから送信された前記経路Ｒ１上の案内指示のメッセージのキャンセルする案内情報キャンセル情報と案内指示のメッセージを追加する案内情報追加情報を受信し、この受信した案内情報キャンセル情報と案内情報追加情報とに基づいて前記経路Ｒ１の案内情報に対して案内情報のキャンセルと案内情報の追加を反映させるように構成されていることを特徴とするナビゲーション装置。
【請求項３】
前記情報センタは、前記ナビゲーション装置に記憶されている前記第１の道路地図データと、前記第１の道路地図データとは別の第２の道路地図データとを備えており、
前記ナビゲーション装置から送信された前記移動体の出発地の情報と目的地の情報とを受信し、前記第１の道路地図データを使って前記現在地から目的地までの経路Ｒ１を算出する処理と、この算出された経路Ｒ１の案内情報を算出する処理とを実行し、
更に、前記第２の道路地図データを使って前記移動体の現在地から目的地までの経路Ｒ２を算出する処理と、この算出された経路Ｒ２の案内情報を算出する処理とを実行し、
前記経路Ｒ１の案内情報と前記経路Ｒ２の案内情報とを比較し、前記経路Ｒ１に存在して前記経路Ｒ２に存在しない案内情報についてこれらをキャンセルする案内情報キャンセル情報と、前記経路Ｒ１に存在しない案内情報であって前記経路Ｒ２に存在する案内情報についてこれらを追加する案内情報追加情報とを前記ナビゲーション装置へ送信することを特徴とする請求項２に記載のナビゲーション装置。
【請求項４】
前記案内情報とは、道路地図データまたは案内指示の少なくとも１つであることを特徴とする請求項２または３記載のナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路データを更新する道路情報更新システム及びそれを用いたナビゲーション装置に関する。
【背景技術】
【０００２】
従来技術として、例えば特許文献１には、記憶媒体に記憶された道路地図データに存在しない新規の道路を車両が走行した場合に、車両の走行軌跡に基づいて上記新規道路であることを認定する機能を備えたナビゲーション装置（例えば車載のカーナビゲーション装置）が記載されている。この特許文献１においては、ナビゲーション装置から上記認定した新規道路情報を情報センタへ送信すると、情報センタは、受信した新規道路情報に基づいて道路地図データを更新する（即ち、新規道路学習機能を備える）ように構成されている。しかし、特許文献１に記載された新規道路学習機能では、「実際には廃止された道路」を検出することができない。
【０００３】
このため、特許文献１に記載された新規道路学習では、新規道路が追加されるものの、例えば、新規道路が建設されたことにより廃止された道路がある場合には、廃止された道路が残ったままとなり、その道路を使った経路誘導がなされる虞がある。
【０００４】
また、特許文献１のように、道路地図データが更新できたとしても、更新した後の道路地図データを全て情報センタからナビゲーション装置に送信すると、そのデータ量が過多となるとの問題も生じ得る。また、道路指示データの場合においても同様であって、このような道路案内データ（道路地図データ,道路指示データ）を全て送信してしまうと、そのデータ量が過多となるとの問題も生じる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第３５５７７７６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
そこで、本発明の目的は、情報センタにて道路データを更新する場合においても、その送信するデータ量を減らすことができる道路情報更新システム、および実際の道路状況に合わせた経路誘導を実現することができるナビゲーション装置を提供することにある。
【課題を解決するための手段】
【０００７】
請求項１の発明は、第１の道路地図データを記憶する記憶手段と、移動体の走行軌跡を検出する走行軌跡検出手段とを備えると共に、情報を外部へ送信する通信手段を備えたナビゲーション装置と、第２の道路地図データを記憶すると共に、前記ナビゲーション装置に対して情報を通信する通信手段を備えた情報センタと、を備える道路情報更新システムにおいて、前記情報センタは、前記第１の道路地図データを備え、前記ナビゲーション装置から送信された目的地の情報と前記移動体の出発地の情報を受信し、前記第１の道路地図データを使って現在地から目的地までの経路Ｒ１を算出する処理と、この算出された経路Ｒ１の案内情報を算出する処理とを実行し、前記第２の道路地図データを使って現在地から目的地までの経路Ｒ２を算出する処理と、この算出された経路Ｒ２の案内情報を算出する処理とを実行し、前記経路Ｒ１の案内情報と前記経路Ｒ２の案内情報とを比較し、前記経路Ｒ１に存在して前記経路Ｒ２に存在しない案内情報をキャンセルする案内情報キャンセル情報と、前記経路Ｒ１に存在しない案内情報であって前記経路Ｒ２に存在する案内情報を追加する案内情報追加情報とを前記ナビゲーション装置へ送信するように構成され、前記ナビゲーション装置は、前記情報センタからの前記案内情報キャンセル情報と前記案内情報追加情報を受信し、この受信した前記案内情報キャンセル情報と前記案内情報追加情報に基づいて前記経路Ｒ１の案内情報に対して案内情報のキャンセルと案内情報の追加を反映させるように構成されているところに特徴を有する。
【０００８】
請求項２の発明は、道路を走行する移動体に搭載され、前記移動体の走行軌跡を検出する走行軌跡検出手段と、第１の道路地図データを記憶する記憶手段と、情報を外部へ送信する通信手段とを備えたナビゲーション装置において、前記移動体の出発地の情報と目的地の情報とを情報センタへ送信するように構成され、前記第１の道路地図データを使って出発地から目的地までの経路Ｒ１を算出する処理と、この算出された経路Ｒ１の案内情報を算出する処理とを実行するように構成され、更に、前記情報センタから送信された前記経路Ｒ１上の案内指示のメッセージのキャンセルする案内情報キャンセル情報と案内指示のメッセージを追加する案内情報追加情報を受信し、この受信した案内情報キャンセル情報と案内情報追加情報とに基づいて前記経路Ｒ１の案内情報に対して案内情報のキャンセルと案内情報の追加を反映させるように構成されているところに特徴を有する。
【図面の簡単な説明】
【０００９】
【図１】本発明の第１実施形態を示す道路地図情報更新システムの機能ブロック図
【図２】ナビゲーション装置の制御を示すフローチャート
【図３】情報センタ及びナビゲーション装置の動作を示すシーケンス図
【図４】情報センタの制御を説明する機能ブロック図
【図５】道路変化モデルの一例を説明する図
【図６】道路変化モデルの他の例を説明する図
【図７】新規道路と廃止道路を推測する制御を説明する図
【図８】本発明の第２実施形態の情報センタ及びナビゲーション装置の動作を示すシーケンス図
【図９】（ａ）はキャンセルする案内情報の一例を示す図、（ｂ）は追加する案内情報の一例を示す図
【図１０】（ａ）はキャンセルする案内情報の他の例を示す図、（ｂ）は追加する案内情報の他の例を示す図
【図１１】本発明の第３実施形態のモデル作成装置の機能ブロック図
【図１２】差分グループ抽出処理部の制御を示すフローチャート
【図１３】最新地図データ及び第１補助地図データが遷移する態様を示す図
【図１４】依存関係を判定する態様を示す図
【図１５】最新地図データ及び第２補助地図データが遷移する態様を示す図
【図１６】図１４相当図
【図１７】道路変化モデルの構成を示す図
【図１８】モデル抽出処理部の制御を示すフローチャート
【図１９】道路の変化パターンの例を示す図
【図２０】本発明の第４実施形態を示す図２相当図
【発明を実施するための形態】
【００１０】
（第１実施形態）
以下、本発明の第１実施形態について、図１ないし図７を参照して説明する。まず、図１は、本実施形態の道路情報更新システムの構成を概略的に示す機能ブロック図である。本システムは、ナビゲーション装置として例えば車載のナビゲーション装置１と、情報センタ２１とを備えている。尚、ナビゲーション装置１は複数の車両（移動体）に設けられているのであるが、図１ではその内の一つを例示している。また、情報センタ２１は、地上の所定位置に固定された施設として設けられている。
【００１１】
図１に示すように、ナビゲーション装置１は、位置検出部２、地図データ格納部３、スイッチ情報入力部４、メモリ部５、表示部６、音声出力部７、データ通信部８及び制御部９を備えている。以下、これらの構成を順に説明していく。
【００１２】
位置検出部２は、ＧＰＳセンサやジャイロセンサや車速センサ等から構成され、車両の現在位置（現在地）を検出する機能を有する。尚、車両の現在位置が検出できるのであれば、上記センサを全て備える必要はなく、少なくともいずれか一つ以上備えていればよい。但し、ＧＰＳセンサを備えている場合、車両の位置を正確に検出することができるため、以下の説明では、位置検出部２は少なくともＧＰＳセンサを備えているものとする。
【００１３】
また、地図データ格納部（記憶手段）３は、例えばＤＶＤプレーヤやハードディスク、ＣＤプレーヤ等から構成され、道路地図情報を含む道路地図データ（第１の道路地図データ）を記憶している。また、地図データ格納部３に記憶された道路地図データには、道路毎に所定の道路番号が対応付けて記憶されており、また、道路によっては、その道路の区間毎に所定の道路番号が対応付けて記憶されている。
【００１４】
スイッチ情報入力部４は、表示部６としてのディスプレイ装置の左右や上下に取り付けられたスイッチ類である。ドライバは、このスイッチ情報入力部４を介して、各種選択を行ったり各種動作の指示を行ったり目的地を設定したりすることができる。メモリ部５は、例えばＲＯＭやＲＡＭから構成されており、ＲＯＭにはナビゲーションのプログラムを始め後述の各種処理を実行するためのプログラムが格納されている。また、メモリ部５のＲＡＭには、プログラムのワークメモリや地図データ格納部３から取得した道路地図データ等を一時格納する領域が形成されている。
【００１５】
表示部６は、ドライバをナビゲートするための地図を表示したり、目的地選択画面等を表示するためのディスプレイ装置として構成されている。また、音声出力部７は、ドライバをナビゲートするための音声や画面操作の説明を発声する。データ通信部８は、相互通信機能を有しており、例えば携帯電話や自動車電話等から構成されている。
【００１６】
制御部９は、ナビゲーション装置１の上記各部を制御するもので、地図データ取得部１０、マップマッチング部１１、経路計算部１２、経路案内部１３、描画部１４、画面制御管理部１５、通信制御部１６及び走行軌跡作成部１７を備えている。これらの各部の動作を説明する。
【００１７】
まず、地図データ取得部１０は、後述のように制御部９の上記各部で必要とされる地図データを、地図データ格納部３より取得し、各部に提供する。また、この地図データ取得部１０における処理、及び他の各部における処理は、メモリ部５のＲＯＭやＲＡＭを使って実行される。
【００１８】
また、マップマッチング部１１は、位置検出部２で検出した車両の現在位置と地図データ格納部３から取得された地図データの道路形状データ等を使って、現在位置がどの道路上に存在するかを特定する。この際、地図データ取得部１０が必要な地図データを地図データ格納部３より取得する。
【００１９】
経路計算部１２では、マップマッチング部１１で算出された現在位置またはドライバが指定した出発地から、スイッチ情報入力部４を使って所望の地図を表示させる等してドライバがセットした目的地に至る経路を計算する。経路案内部１３では、その経路計算の結果と道路地図データ内に格納されている道路の形状データや、交差点の位置情報、踏切の位置情報等から、案内に必要なポイントを算出したりどのような案内（右に曲がるか左に曲がるかの指示等、即ち、いわゆるナビゲーション）が必要なのかを算出する。そして、車両が上記計算されて設定された経路上を走行するときに、経路案内部１３により上記算出された案内に基づいて経路案内が実行される。描画部１４では、現在位置の地図や、高速道路の略図や、交差点付近では交差点付近の拡大図等を、画面制御管理部１５の指示に従って描画し、表示部６に表示する。
【００２０】
走行軌跡作成部（走行軌跡検出手段）１７では、位置検出部２からの位置データに基づいて自車両の走行軌跡を作成する。そして、詳しくは後述するように、所定条件が成立した場合はその走行軌跡情報、即ち、新規道路情報をメモリ部５へ蓄積する。
【００２１】
通信制御部１６では、スイッチ情報入力部４を使ってドライバから指示があったとき及び所定時間が経過する毎にデータ通信部８に指示して、情報センタ２１との相互通信が可能な状態にする。また、データ通信部８が情報センタ２１からの要求を受信した場合にも、通信制御部１６は上記相互通信が可能な状態にする。このように相互通信が可能となったとき、メモリ部５に記憶された走行軌跡情報（新規道路情報）を情報センタ２１にアップロードする。また、情報センタ２１へ情報の配信要求をしたとき、または、情報センタ２１から通信制御部１６に対して情報の送信要求があったときには、その要求に応じて情報センタ２１から配信（送信）された情報を受信し、メモリ部５へ格納する。情報センタ２１から配信される情報には、アプリケーションプログラムや、地図データや、後述する経路案内指示情報などがある。データ通信部８と通信制御部１６とから通信手段が構成されている。
【００２２】
一方、情報センタ２１は、各車両と交信可能な無線基地局１８に電話局１９を通じて接続されており、その無線基地局１８とナビゲーション装置１との間でデータが送受信される。情報センタ２１は、電話局１９を介して通信を行う回線端末装置（通信手段）２２と、必要な情報を加工するサーバ２３と、必要なデータを蓄積しておくデータベース２４とを備えている。情報センタ２１では、通信によって車両のナビゲーション装置１から得た走行軌跡情報（新規道路情報）等のデータをデータベース２４内に記憶する。そして、情報センタ２１では、走行軌跡情報（新規道路情報）、通信によって車両のナビゲーション装置１から得た車両の現在地及び目的地の情報、並びに、データベース２４内の道路地図データに基づいて、サーバ２３によってデータ処理（例えば、後述する新旧道路推定処理（第１実施形態）や経路算出処理や経路案内比較処理（第２実施形態）等）を実行し、データ処理結果をデータベース２４内に記憶する。なお、第２実施形態では、情報センタ２１は、上記現在地及び目的地の情報を送信してきたナビゲーション装置１へ回線端末装置２２を使用して経路案内比較結果の情報を送信する機能を追加している。
【００２３】
次に、このように構成されたナビゲーション装置１及び情報センタ２１において実行される各種のデータ処理について、図２ないし図７を参照して説明する。
まず、図２は、ナビゲーション装置１の制御部９が実行する処理であり、走行軌跡を蓄積し、所定条件が成立した場合に情報センタ２１へ送信する処理を示すフローチャートである。走行軌跡作成部１７は、位置検出部２にて検出した現在位置座標（経緯度値）を一定時間（例えば１〜５秒）毎に取り込み、走行軌跡の情報を作成している（Ｓ１０１）。この走行軌跡から走行方向が判る。また、移動距離及びその移動に要した時間も得られるので、平均走行速度も判る。
【００２４】
次に、このように得た走行軌跡と、地図データ格納部３から取得された道路地図データの道路形状データとを比較し、道路離脱状態か否かを判定する（Ｓ１０２）。そして、道路離脱状態である場合には（Ｓ１０２：ＹＥＳ）、既に蓄積済みの走行軌跡の情報と比較して、同様の走行軌跡のものが存在するか否かを判定する（Ｓ１０３）。同様の走行軌跡のものが存在しない場合には（Ｓ１０３：ＮＯ）、作成回数を１とし（Ｓ１０４）、その走行軌跡を含む情報をメモリ部５へ蓄積して（Ｓ１０５）、本処理を終了する。つまり、道路地図データには存在しない新規に作成された道路であるとして、その走行軌跡などの情報（以下、走行軌跡情報と称す）を蓄積しておくのである。この走行軌跡情報とは、例えば、走行軌跡、その走行軌跡を構成する位置座標の記憶時間間隔、その走行軌跡の作成回数などを含む情報である。この場合、制御部９は、走行軌跡情報収集手段としての機能を有している。
【００２５】
尚、Ｓ１０２での道路離脱状態か否かの判定に際しては、マップマッチング部１１におけるマップマッチング処理を利用し、走行軌跡とマップマッチングが可能な所定範囲内となる道路形状データとが一致度（近似度合い）が低い（或いは、ない）場合に、道路離脱状態であると判定することが考えられる。また、例えば道路工事中に一時的に設けられる迂回路については、ここでいう新規道路に含めない方が好ましい。このような迂回路は、道路距離が短く、工事前の道路と並行に設けられ、その工事前の道路との距離も短い。このような迂回路についての走行軌跡は、その特質を基にして、蓄積対象である新規道路の走行軌跡として採用しないようにする。
【００２６】
また、前記Ｓ１０５において、走行軌跡を含む情報をメモリ部５へ蓄積する場合、走行軌跡としては、地図に存在しない新規道路（道路離脱部分）だけでなく、その新規道路の前の道路と後の道路、即ち、新規道路の前後の道路を当該新規道路に付加して（セットにして）記憶させるように構成している。
【００２７】
一方、同様の走行軌跡のものが存在する場合には（Ｓ１０３：ＹＥＳ）、その走行軌跡の作成回数が所定値以上であるか否かを判定し（Ｓ１０６）、所定値未満であれば（Ｓ１０６：ＮＯ）、その走行軌跡に対する作成回数を１増やし（Ｓ１０７）、本処理を終了する。
【００２８】
このようにして同様の走行軌跡が作成され、作成回数が増えていくことによって、その走行軌跡の作成回数が所定値以上となった場合には（Ｓ１０６：ＹＥＳ）、Ｓ１０５にて蓄積しておいた走行軌跡情報、即ち、新規道路情報を情報センタ２１へ送信する（Ｓ１０８）。その後、上記送信済みの走行軌跡などの情報をメモリ部５からクリアして（Ｓ１０９）、本処理を終了する。尚、上記Ｓ１０９においては、送信済みの走行軌跡などの情報をメモリ部５からクリアしたが、これに代えて、送信済みの走行軌跡などの情報が送信済であることをメモリ部５に記録するように構成しても良い。このように構成すると、送信済みの走行軌跡に該当する道路が送信済であることがわかるから、その後、同じ道路を走行したときに、前述した処理（新規道路として判断したり、新規道路情報を情報センタ２１へ送信したりする処理等）が実行されることを防止できる。
【００２９】
ここで、走行軌跡の作成回数が所定値以上となって初めて新規道路を走行した走行軌跡情報（新規道路情報）を情報センタ２１へ送信するようにしたのは、次の理由からである。つまり、走行軌跡を検出する際の精度などの問題から、実際の新規道路の形状・位置と一致しない走行軌跡を検出してしまう可能性もある。これに対して複数回同じ走行軌跡が検出された場合には、その軌跡は実際の新規道路の形状・位置と一致する可能性が高いと言えるからである。所定値としては、１以上の数値に設定すれば良いが、あまり大きくない数値（例えば３や５など）であることが好ましい。このように設定する理由は、車両が新規道路を走行したら、なるべく早く新規道路情報、即ち、新規道路を走行した走行軌跡情報を情報センタ２１へ送信した方が好ましいためである。
【００３０】
次に、情報センタ２１が実行する処理と、１台以上（本実施形態では１台を例に挙げて説明する）の車両にそれぞれ搭載されたナビゲーション装置１が実行する処理とについて、図３ないし図７を参照して説明する。まず、図３は、情報センタ２１の動作（処理）と、１台の車両Ａに搭載されたナビゲーション装置１の動作（処理）とを説明するシーケンス図である。
【００３１】
この図３のステップＳ２０１に示すように、情報センタ２１では、予め道路変化モデルを作成する処理（モデル作成手段としての機能）を実行しておく。この道路変化モデルを作成する処理においては、図４に示すように、過去において使用していた古い道路地図データ（以下旧道路地図データと称す）と、最近更新した最も新しい道路地図データ（以下新道路地図データと称す、第２の道路地図データ）とを比較して、廃止された道路があると共に現在使用されている新規道路がある道路変化部分を多数抽出し、廃止道路と新規道路に基づいて道路変化モデルを多種類作成し、これらをデータベース２４内に記憶する。なお、道路変化モデルを作成する際に、比較する新道路地図データは、最近更新した最も新しい道路地図データが好ましいが、これに限らず、比較対象の旧道路地図データよりも新しく更新された道路地図データであっても良い。
【００３２】
尚、情報センタ２１には、複数の道路地図データが備えられており、これら複数の道路地図データは、時系列に古い旧版（複数世代）の道路地図データと、新しい現在使用中の新版の道路地図データとである。また、情報センタ２１では、定期的に道路地図データ全体が更新されるように構成されている。この道路地図データの更新処理は、外部（道路地図データ製作会社や道路を管理する役所等）から与えられた、または、後述するようにして情報センタ２１内部で得られた廃止された道路の情報及び新規に作成された道路の情報に基づいて実行される。
【００３３】
ここで、道路変化モデルの一例を、図５に示す。旧道路地図データの中で、ある交差点が、図５（ａ）に示すような十字路であったとする。この交差点が、新道路地図データの中では、図５（ｂ）に示すようなロータリー交差点（またはラウンドアバウト）に変わったとする。この交差点の道路変化モデルは、図５（ｃ）に示すようなモデルとなる。この道路変化モデルでは、実線で描画されたロータリー道路が新規道路を示し、破線で描画された十字路が廃止道路を示す。
【００３４】
尚、道路変化モデルとしては、新規道路と廃止道路が記憶されるだけではなく、新規道路及びその前後の道路（即ち、新規道路の前の道路及び新規道路の後の道路）と、廃止道路及びその前後の道路とがセットになって記憶される構成となっている。そして、このように前後の道路をセットにして記憶しておくと、後述する走行軌跡のパターンと道路変化モデルのパターンを比較判定（照合）する処理の判定精度を高くすることができる。
【００３５】
また、図６は、道路変化モデルの他の例を示す。旧道路地図データの中で、高速道路のある交差路が、図６（ａ）に示すように、曲率半径が小さいループ状の分岐路２７であったとする。この交差路が、新道路地図データの中では、図６（ｂ）に示すように、曲率半径が大きい円弧状の分岐路２８に変わったとする。この交差路の道路変化モデルは、図６（ｃ）に示すようなモデルとなる。この道路変化モデルでは、実線で描画された分岐路２８が新規道路を示し、破線で描画された分岐路２７が廃止道路を示す。尚、この図６に示す道路変化モデルの場合も、新規道路及びその前後の道路と、廃止道路及びその前後の道路とがセットになって記憶される構成となっている。
【００３６】
本実施形態では、道路変化モデルとして上記２つの例を示したが、実際には多種類の道路変化モデルを作成して、データベース２４内に記憶している。そして、他の道路変化モデルの場合も、新規道路及びその前後の道路と、廃止道路及びその前後の道路とがセットになって記憶される構成となっている。
【００３７】
次に、車両Ａのナビゲーション装置１において、新規道路を走行した走行軌跡の作成回数が所定値以上となると、図３のステップＳ２０２にて示す制御が実行され、新規道路を走行した走行軌跡情報（新規道路情報）を情報センタ２１へ送信する。
【００３８】
続いて、情報センタ２１において、車両Ａのナビゲーション装置１からの新規道路を走行した走行軌跡情報（新規道路情報）を受信すると、図３のステップＳ２０３にて示すように、新旧道路推定処理（推定手段としての機能）が実行される。具体的には、受信した走行軌跡情報をデータベース２４内の種々の道路変化モデルと比較する処理が実行され、受信した走行軌跡に対応する道路変化モデルが選択される。例えば、受信した走行軌跡が，図７（ａ）に示すような形状の走行軌跡であったとすると、道路変化モデルとしては、図７（ｂ）に示すような形状のモデルが選択される。そして、情報センタ２１では、受信した走行軌跡（図７（ａ）参照）と道路変化モデル（図７（ｂ））とに基づいて、図７（ｃ）にて実線で示す新規道路２９と、図７（ｃ）にて破線で示す廃止道路３０とを推測し、これら推測した情報（新規道路２９の情報と廃止道路３０の情報と）をデータベース２４内に記憶する。
【００３９】
尚、情報センタ２１では、他の複数の車両（図示しない）のナビゲーション装置１から送信された新規道路を走行した走行軌跡情報（新規道路情報）も随時受信するように構成されている。そして、情報センタ２１は、他の複数の車両のナビゲーション装置１から走行軌跡情報を受信すると、上述したようにして、受信した走行軌跡に対応する道路変化モデルを選択し、新規道路と廃止道路とを推測し、これら推測した新規道路と廃止道路の情報をデータベース２４内に記憶するように構成されている。
【００４０】
また、情報センタ２１においては、上記したようにして推測した新規道路と廃止道路を、情報センタ２１に記憶されている道路地図データの更新処理に反映させる。このとき、道路地図データは、全てを更新するようにしても良いが、最近更新した最も新しい道路地図データに対して、更新する部分のみを更新するほうが良い。
【００４１】
このように、本実施形態では、道路変化モデルを使って新規道路と廃止道路とを推測するようにしたため、実際の道路状況にあった道路の推測を行うことが可能となる。また、道路変化モデルを用いているため、従来に比べ安価なシステムにおいて道路更新を行うことが可能となる。なお、情報センタ２１では、複数の車両から最新の道路情報（新規道路・廃止道路）を入手するため、外部（道路地図データ製作会社や道路を管理する役所等）から与えられる定期的な更新を待たずに、最新の道路地図データを記憶（或いは更新）することができる。
【００４２】
（第２実施形態）
図８ないし図１０は、本発明の第２実施形態を示すものである。尚、第１実施形態と同一構成及び同一ステップには、同一符号及び同一ステップ番号を付している。この第２実施形態では、情報センタ２１が実行する処理と、車両にそれぞれ搭載されたナビゲーション装置１（本実施形態では２台を例に挙げて説明する）が実行する処理とについて説明する。
【００４３】
まず、図８のステップＳ２０１に示すように、情報センタ２１では、第１実施形態と同様にして、予め道路変化モデルを作成する処理（モデル作成手段としての機能）を実行しておく。
【００４４】
次に、車両Ａのナビゲーション装置１において、新規道路を走行した走行軌跡の作成回数が所定値以上となると、図８のステップＳ２０２にて示す制御が第１実施形態と同様にして実行され、新規道路を走行した走行軌跡情報（新規道路情報）を情報センタ２１へ送信する。
【００４５】
続いて、情報センタ２１において、車両Ａのナビゲーション装置１からの新規道路を走行した走行軌跡情報（新規道路情報）を受信すると、図８のステップＳ２０３にて示すように、第１実施形態と同様にして、新旧道路推定処理（推定手段としての機能）が実行される。これにより、情報センタ２１では、新規道路と廃止道路とを推測し、これら推測した情報（新規道路の情報と廃止道路の情報と）をデータベース２４内に記憶する。そして、情報センタ２１は、第１実施形態と同様にして、他の複数の車両のナビゲーション装置１から走行軌跡情報を受信すると、受信した走行軌跡に対応する道路変化モデルを選択し、新規道路と廃止道路とを推測し、これら推測した新規道路と廃止道路の情報をデータベース２４内に記憶する。
【００４６】
この後、図８のステップＳ２０４にて示すように、車両Ｂのナビゲーション装置１において、経路算出処理および経路案内処理を実行するために、目的地が設定されると、この設定された目的地の情報と車両Ｂの現在地（出発地であっても良い）の情報を情報センタ２１へ送信する（ステップＳ２０５）。更に、車両Ｂのナビゲーション装置１においては、上記送信処理に引き続いて、ステップＳ２０６にて示すように、ナビゲーション装置１内に搭載されている道路地図データ（第１の道路地図データ）を使って現在地から目的地までの経路Ｒ１を算出する処理と、この算出された経路Ｒ１と道路地図データ内に格納されている道路の形状データや、交差点の位置情報、踏切の位置情報等から、案内指示に必要なポイントを算出し、どのような案内指示（右に曲がるか左に曲がるかの指示等、即ち、いわゆるナビゲーション）が必要なのかを算出する処理（案内情報の算出処理）とが行われる。
【００４７】
次に、情報センタ２１において、車両Ｂのナビゲーション装置１から送信された目的地の情報と車両Ｂの現在地（出発地であっても良い）の情報を受信すると、ステップＳ２０７にて示すように、データベース２４内に記憶されている道路地図データ（これは車両Ｂのナビゲーション装置１内に搭載されている道路地図データと同じもの、第１の道路地図データ）を使って現在地から目的地までの経路Ｒ１を算出する処理と、この算出された経路Ｒ１と道路地図データ内に格納されている道路の形状データや、交差点の位置情報、踏切の位置情報等から、案内指示に必要なポイントを算出し、どのような案内指示が必要なのかを算出する処理（案内情報の算出処理）とが行われる。
【００４８】
これに続いて、ステップＳ２０８にて示すように、情報センタ２１では、データベース２４内に記憶されている道路地図データ（これは車両Ｂのナビゲーション装置１内に搭載されている道路地図データと同じもの、第１の道路地図データ）と、データベース２４内に記憶されている推測した新規道路と廃止道路の情報とが反映された第２の道路地図データ（第１の道路地図データに対して推測した新規道路と廃止道路の情報が反映された道路地図データ）から現在地から目的地までの経路Ｒ２を算出する処理と、この算出された経路Ｒ２と第２の道路地図データ内に格納されている道路の形状データや、交差点の位置情報、踏切の位置情報等から、案内指示に必要なポイントを算出したり、どのような案内指示が必要なのかを算出する処理（案内情報の算出処理）とが行われる。この場合、上記算出された経路Ｒ２は、前記算出された経路Ｒ１と基本的にほぼ同じ経路であり、異なる点は、前記経路Ｒ１の中に上記推測した廃止道路が含まれるときには、上記推測した新規道路を経由する経路となる点である。尚、経路Ｒ２を算出する際に用いた道路地図データを、第１の道路地図データに対して前記推測された新規道路と廃止道路とを反映させた道路地図データを第２の道路地図データとしているが、第１の道路地図データ後に更新された道路地図データであってもよい。
【００４９】
次いで、ステップＳ２０９にて示すように、情報センタ２１では、経路Ｒ１の案内情報と経路Ｒ２の案内情報を比較し、両者の相違点を抽出する処理（経路案内比較処理）を実行する。そして、ステップＳ２１０にて示すように、情報センタ２１は、経路Ｒ１に存在して経路Ｒ２に存在しない案内情報について、これらをキャンセルする案内情報キャンセル情報を車両Ｂのナビゲーション装置１へ送信する。この案内情報キャンセル情報には、案内指示をキャンセルする情報が含まれている。
【００５０】
更に、ステップＳ２１１にて示すように、情報センタ２１は、経路Ｒ１に存在しない案内情報であって経路Ｒ２に存在する案内情報について、これらを追加する案内情報追加情報を車両Ｂのナビゲーション装置１へ送信する。この案内情報追加情報には、新規道路での案内情報を車両Ｂのナビゲーション装置１へ送信する。
【００５１】
これに対して、車両Ｂのナビゲーション装置１では、情報センタ２１から案内情報キャンセル情報を受信すると、ステップＳ２１２にて示すように、上記受信した案内情報キャンセル情報に基づいて前記経路Ｒ１の案内情報に対して案内情報のキャンセルを反映させる、即ち、該当する案内指示をキャンセルする処理を行う。
【００５２】
これと共に、車両Ｂのナビゲーション装置１では、情報センタ２１から案内情報追加情報を受信すると、ステップＳ２１３にて示すように、上記受信した案内情報追加情報に基づいて前記経路Ｒ１の案内情報に対して案内情報の追加を反映させる、即ち、該当する案内指示を追加したり、新しい地図及び新規道路を簡単に表示するための案内図を表示したりする処理を行う。この結果、車両Ｂのナビゲーション装置１では、情報センタ２１にて算出した経路Ｒ２の案内情報と同じ案内情報、即ち、新規道路を経由する経路でもって経路案内を実行することができる。
【００５３】
このような構成の本実施形態においては、車両Ａのナビゲーション装置１において、道路地図データにない新規道路を走行した走行軌跡をメモリ部に蓄積し、所定条件が成立したときに上記新規道路の走行軌跡情報を情報センタ２１へ送信するように構成した。そして、情報センタ２１では、車両Ａのナビゲーション装置１からの新規道路の走行軌跡情報を受信し、この受信した新規道路の走行軌跡情報とデータベース２４内に記憶されている道路変化モデルを比較して、新規道路と廃止道路を推測するように構成した。このように構成したので、本実施形態によれば、情報センタ２１において、道路地図データにない新規道路と廃止された廃止道路とを正確に推測することができる。
【００５４】
また、本実施形態では、情報センタ２１において、車両Ｂのナビゲーション装置１から送信された目的地の情報と車両Ｂの現在地（出発地）の情報を受信し、データベース２４内に記憶されている道路地図データ（車両Ｂのナビゲーション装置１内に搭載されている道路地図データと同じもの）を使って現在地（出発地）から目的地までの経路Ｒ１を算出する処理と、この算出された経路Ｒ１と道路地図データ内に格納されている道路の形状データや、交差点の位置情報、踏切の位置情報等から、案内指示に必要なポイントを算出したり、どのような案内指示が必要なのかを算出する処理（案内情報の算出処理）とを実行した。更に、情報センタ２１では、上記道路地図データ（車両Ｂのナビゲーション装置１内に搭載されている道路地図データと同じもの）と、データベース２４内に記憶されている推測した新規道路と廃止道路の情報とを使って現在地（出発地）から目的地までの経路Ｒ２を算出する処理と、この算出された経路Ｒ２と道路地図データ内に格納されている道路の形状データや、交差点の位置情報、踏切の位置情報等から、案内指示に必要なポイントを算出したり、どのような案内指示が必要なのかを算出する処理（案内情報の算出処理）とが行われる。この場合、上記算出された経路Ｒ２は、経路Ｒ２の中に上記推測した新規道路が含まれるときには、その推測した新規道路を経由する経路となる。加えて、情報センタ２１では、経路Ｒ１の案内情報と経路Ｒ２の案内情報を比較し、両者の相違点を抽出する処理（経路案内比較処理）を実行し、経路Ｒ１に存在して経路Ｒ２に存在しない案内情報についてこれらをキャンセルする案内情報キャンセル情報と、経路Ｒ１に存在しない案内情報であって経路Ｒ２に存在する案内情報についてこれらを追加する案内情報追加情報とを車両Ｂのナビゲーション装置１へ送信する。更に、車両Ｂのナビゲーション装置１では、情報センタ２１からの案内情報キャンセル情報と案内情報追加情報を受信すると、この受信した案内情報キャンセル情報と案内情報追加情報に基づいて前記経路Ｒ１の案内指示に対して案内指示のキャンセルと案内指示の追加を反映させる。この結果、車両Ｂのナビゲーション装置１では、情報センタ２１にて算出した経路Ｒ２の案内情報と同じ案内情報、即ち、道路地図データにない新規道路を経由する経路で経路案内を実行することができる。
【００５５】
なお、上記実施形態２では、案内情報として、経路上の案内指示を例に挙げたが、これに限らず、道路地図データであっても良い。また、経路上の案内指示と道路地図データの両方であってもよい。
【００５６】
具体的には、案内情報として、経路上の案内指示と道路地図データの両方を情報センタ２１からナビゲーション装置１に送信する場合、まず図８のステップＳ２１１にて、案内情報キャンセル情報には、案内指示をキャンセルする情報と、地図表示及び経路表示を禁止する地図エリアの情報を含むようにさせる。この禁止する地図エリアの情報は、ナビゲーション装置１のディスプレイに地図や経路等を表示する際に、古い地図及び廃止道路を表示しないようにマスクするための情報である。
【００５７】
次に、ステップＳ２１１にて示すように、情報センタ２１は、経路Ｒ１に存在しない案内情報であって経路Ｒ２に存在する案内情報について、これらを追加する案内情報追加情報を車両Ｂのナビゲーション装置１へ送信する。この案内情報追加情報には、新規道路での案内情報、新しい地図及び新規道路を簡単に表示する案内図（例えば絵や画像等の道路データ）の情報が含まれている。尚、上記案内図の情報としては、画像データやコード情報（その画像データがナビゲーション装置１側に記憶されている場合にその画像データを特定する情報）等を送信すれば良い。
【００５８】
これら情報により、車両Ｂのナビゲーション装置１では、情報センタ２１から案内情報キャンセル情報を受信すると、ステップＳ２１２にて示すように、上記受信した案内情報キャンセル情報に基づいて前記経路Ｒ１の案内情報に対して案内情報のキャンセルを反映させる、即ち、該当する案内指示をキャンセルしたり、古い地図および廃止道路を表示しないようにマスクしたりする処理を行う。
【００５９】
これと共に、車両Ｂのナビゲーション装置１では、情報センタ２１から案内情報追加情報を受信すると、ステップＳ２１３にて示すように、上記受信した案内情報追加情報に基づいて前記経路Ｒ１の案内情報に対して案内情報の追加を反映させる、即ち、該当する案内指示を追加したり、新しい地図及び新規道路を簡単に表示するための案内図を表示したりする処理を行う。この結果、車両Ｂのナビゲーション装置１では、情報センタ２１にて算出した経路Ｒ２の案内情報と同じ案内情報、即ち、新規道路を経由する経路でもって経路案内を実行することができる。なお、古い道路をマスクするだけで、新しい地図及び新規道路を簡単に表示するための案内図を送信せずに表示させなくても良い。
【００６０】
ここで、案内情報として、経路上の案内指示と道路地図データの両方を含む場合のキャンセル及び追加の一例を図９に示す。この場合、図９（ａ）に示すような廃止道路の案内情報がキャンセルされる、具体的には、「この先、左方向です」というメッセージがキャンセルされると共に、左折する道路（廃止道路）及びその周辺の地図の表示が禁止（マスク）される。そして、図９（ｂ）に示すような新規道路の案内情報が追加される、具体的には、「この先、右方向です」というメッセージが追加されると共に、右折して周回する道路（新規道路）及びその周辺の地図の案内図が表示される。この場合、「この先、右方向です」というメッセージの情報を、上記案内図の画像情報に含ませるように構成しても良い。
【００６１】
また、案内情報のキャンセル及び追加の他の例を図１０に示す。この場合、図１０（ａ）に示すような廃止道路の案内情報がキャンセルされる、具体的には、「この先、右方向です」というメッセージがキャンセルされると共に、ループ状の分岐路２７（廃止道路）及びその周辺の地図の表示が禁止（マスク）される。そして、図１０（ｂ）に示すような新規道路の案内情報が追加される、具体的には、「この先、右方向です」というメッセージが追加されると共に、曲率半径が大きい円弧状の分岐路２８（新規道路）及びその周辺の地図の案内図が表示される。この図１０の場合は、案内指示のメッセージの内容は同じであるが、メッセージを出力する時点、即ち、案内指示のポイントが異なる。尚、「この先、右方向です」というメッセージの情報を、上記案内図の画像情報に含ませるように構成しても良い。
【００６２】
尚、上記第２実施形態では、第１実施形態の道路変化モデルを使った道路情報の更新処理を前提としているが、道路情報の更新処理についてはこれに限ったことではなく、従来周知の道路情報の更新処理（道路地図データの一部または全体を更新する処理）を使っても良い。
【００６３】
（第３実施形態）
図１１ないし図１９は、本発明の第３実施形態を示すものである。尚、第１実施形態及び第２実施形態と同一構成及び同一ステップには、同一符号及び同一ステップ番号を付している。この第３実施形態では、第１実施形態及び第２実施形態で使用される多種類の道路変化モデルを作成するモデル作成装置３１の一例を示す。本実施形態のモデル作成装置３１は、例えば情報センタ２１のサーバ２３とデータベース２４で構成されている。
【００６４】
モデル作成装置３１は、図１１に示すように、差分グループ抽出処理部（差分グループ作成手段）３２と、地図データベース群３３と、差分グループデータベース（差分グループ記憶手段）３４と、地図更新情報入力部３５と、モデル抽出処理部（モデル抽出手段）３６と、道路変化モデルデータベース（モデル記憶手段）３７とを備えて構成される。この場合、差分グループ抽出処理部３２、地図更新情報入力部３５及びモデル抽出処理部３６は、情報センタ２１のサーバ２３で構成される。地図データベース群３３、差分グループデータベース３４及び道路変化モデルデータベース３６は、情報センタ２１のデータベース２４で構成される。
【００６５】
差分グループ抽出処理部３２は、道路の変化に対して、道路ネットワークを保障する最小限のグループ化する処理を行う機能を有する。尚、道路の変化とは、例えば、道路の追加・変更・削除などの変化である。地図データベース群３３は、最新地図データベース３８と、第１補助地図データベース３９と、第２補助地図データベース４０とを有する。差分グループデータベース３４には、差分グループ抽出処理部３２により抽出された多数の差分グループが記憶される。道路変化モデルデータベース３６には、モデル抽出処理部３５により抽出（または補正）された種々（多数）の道路変化モデルが記憶される。
【００６６】
地図更新情報入力部３５は、地図データに対してリンクの追加又は削除を指示する地図更新情報を外部から入力する。この場合、道路が開通したり閉鎖したりすることに応じて、例えばオペレータ（作業者）が入力機器（例えばキーボードやマウス等）（図示せず）を操作することで地図更新情報が地図更新情報入力部３５へ入力される。
【００６７】
最新地図データベース３８は、ノードとリンクとの接続態様を示す最新地図データを記憶する。ノードは道路上の交差点（分岐点）を示し、リンクはノード同士間の道路（車両の進行を許可する方向をも含む）を示す。差分グループ抽出処理部３２は、道路が開通したことに応じて、リンクの追加を指示する地図更新情報が地図更新情報入力部３５へ入力されると、そのリンクの追加を最新地図データベース３８に記憶されている最新地図データに反映し、又、道路が閉鎖したことに応じて、リンクの削除を指示する地図更新情報が地図更新情報入力部３５へ入力されると、そのリンクの削除を最新地図データベース３８に記憶されている最新地図データに反映する。即ち、最新地図データベース３８に記憶されている最新地図データは、リンクの追加を指示する地図更新及びリンクの削除を指示する地図更新の何れが発生した場合でも更新される。
【００６８】
第１補助地図データベース３９は、初期状態（地図データが第１補助地図データベース３９に登録された状態）では最新地図データベース３８に記憶されている最新地図データと同じ地図データを第１補助地図データとして記憶する。差分グループ抽出処理部３２は、リンクの削除を指示する地図更新情報が地図更新情報入力部３５へ入力されると、そのリンクの削除を第１補助地図データベース３９に記憶されている第１補助地図データに反映するが、リンクの追加を指示する地図更新情報が地図更新情報入力部３５へ入力されても、そのリンクの追加を第１補助地図データベース３９に記憶されている第１補助地図データに反映しない。即ち、第１補助地図データベース３９に記憶されている第１補助地図データは、リンクの削除を指示する地図更新が発生した場合に限って更新され、リンクの追加を指示する地図更新が発生した場合には更新されない。
【００６９】
第２補助地図データベース４０は、初期状態（地図データが第２補助地図データベース４０に登録された状態）では最新地図データベース３８に記憶されている最新地図データと同じ地図データを第２補助地図データとして記憶する。差分グループ抽出処理部３２は、リンクの追加を指示する地図更新情報が地図更新情報入力部３５へ入力されると、そのリンクの追加を第２補助地図データベース４０に記憶されている第２補助地図データに反映するが、リンクの削除を指示する地図更新情報が地図更新情報入力部３５へ入力されても、そのリンクの削除を第２補助地図データベース４０に記憶されている第２補助地図データに反映しない。即ち、第２補助地図データベース４０に記憶されている第２補助地図データは、リンクの追加を指示する地図更新が発生した場合に限って更新され、リンクの削除を指示する地図更新が発生した場合には更新されない。
【００７０】
このように第１補助地図データベース３９に記憶されている第１補助地図データと第２補助地図データベース４０に記憶されている第２補助地図データとは真逆の性質を有する。第１補助地図データは、リンクの削除を指示する地図更新、即ち、車両が通行可能な経路が減少する地図更新が発生した場合に限って更新されるので、ユーザにとって不利となる地図更新だけを反映した地図であり、一方、第２補助地図データは、リンクの追加を指示する地図更新、即ち、車両が通行可能な経路が増加する地図更新が発生した場合に限って更新されるので、ユーザにとって有利となる地図更新を反映した地図である。
【００７１】
次に、上記差分グループ抽出処理部３２が実行する差分グループ抽出処理について、図１２ないし図１６を参照して説明する。まず、図２のフローチャートのステップＳ３０１において、差分グループ抽出処理部３２は、地図更新情報が地図更新情報入力部３５に入力されたか否かを判定し、地図更新が発生したか否か判定する。差分グループ抽出処理部３２は、例えばオペレータが入力機器を操作する等し、地図更新情報が地図更新情報入力部３５に入力されたと判定し、地図更新が発生したと判定すると（ステップＳ３０１にて「ＹＥＳ」）、その地図更新の内容を最新地図データベース３８に記憶されている最新地図データに反映する（ステップＳ３０２）。即ち、差分グループ抽出処理部３２は、リンクの追加を指示する地図更新が発生した場合であれば、リンクの追加を最新地図データに反映し、リンクの削除を指示する地図更新が発生した場合であれば、リンクの削除を最新地図データに反映する。
【００７２】
次いで、差分グループ抽出処理部３２は、その地図更新がリンクの追加を指示する地図更新であるかリンクの削除を指示する地図更新であるかを判定する（ステップＳ３０３、Ｓ３０４）。差分グループ抽出処理部３２は、リンクの削除を指示する地図更新であると判定すると（ステップＳ３０３にて「ＹＥＳ」）、リンクの削除を第１補助地図データベース３９に記憶されている第１補助地図データに反映する（ステップＳ３０５）。この場合、差分グループ抽出処理部３２は、リンクの削除を第２補助地図データベース４０に記憶されている第２補助地図データには反映しない。
【００７３】
一方、差分グループ抽出処理部３２は、リンクの追加を指示する地図更新であると判定すると（ステップＳ３０４にて「ＹＥＳ」）、リンクの追加を第２補助地図データベース４０に記憶されている第２補助地図データに反映する（ステップＳ３０６）。この場合、差分グループ抽出処理部３２は、リンクの追加を第１補助地図データベース３９に記憶されている第１補助地図データには反映しない。
【００７４】
差分グループ抽出処理部３２は、リンクの削除を第１補助地図データに反映した後では、削除したリンクの両端に位置するノード間での経路探索を、その時点で第１補助地図データベース３９に記憶されている第１補助地図データ、即ち、リンクの削除を反映した第１補助地図データ上にて行い（ステップＳ３０７）、第１補助地図データ上での経路探索に成功したか否か（ノード間を通行可能であるか否か）を判定する（ステップＳ３０８）。差分グループ抽出処理部３２は、第１補助地図データ上での経路探索に成功したと判定すると（ステップＳ３０８にて「ＹＥＳ」）、一連の処理を終了する。
【００７５】
一方、差分グループ抽出処理部３２は、第１補助地図データ上での経路探索に失敗したと判定すると（ステップＳ３０８にて「ＮＯ」）、削除したリンクの両端に位置するノード間での経路探索を、その時点で最新地図データベース３８に記憶されている最新地図データ上にて行い（ステップＳ３０９）、最新地図データ上での経路探索に成功したか否かを判定する（ステップＳ３１０）。
【００７６】
差分グループ抽出処理部３２は、最新地図データ上での経路探索に成功したと判定すると（ステップＳ３１０にて「ＹＥＳ」）、初期最新地図データから現在の最新地図データまでに発生した地図更新の内容に依存関係があると判定し、依存関係があると判定した地図更新の内容を地図差分データとしてグループ化し（ステップＳ３１１）、一連の処理を終了する。
【００７７】
また、差分グループ抽出処理部３２は、最新地図データ上での経路探索に失敗したと判定すると（ステップＳ３１０にて「ＮＯ」）、第２補助地図データを複写して一時的第２補助地図データを作成し、対象のリンクを一時的第２補助地図データから削除し（ステップＳ３１２）、対象のリンクの両端に位置するノード間での経路探索を、一時的第２補助地図データ上にて行い（ステップＳ３１３）、一時的第２補助地図データ上での経路探索に成功したか否かを判定する（ステップＳ３１４）。
【００７８】
差分グループ抽出処理部３２は、一時的第２補助地図データ上での経路探索に成功したと判定すると（ステップＳ３１４にて「ＹＥＳ」）、経路探索に成功した経路に含まれる更新リンクと対象のリンクとの間に依存関係があると判定し、依存関係があると判定した地図更新の内容を地図差分データとしてグループ化し、経路探索に成功した経路に含まれる更新リンクを一時的第２補助地図データから削除し（ステップＳ３１５）、上記したステップＳ３１３、Ｓ３１４を繰返して行う。そして、差分グループ抽出処理部３２は、一時的第２補助地図データ上での経路探索に失敗したと判定すると（ステップＳ３１４にて「ＮＯ」）、一連の処理を終了する。
【００７９】
上記した処理について具体例を挙げて図１３ないし図１６を参照して説明する。ここでは、
（１）第１リンクの追加を指示する地図更新が発生し、その後、第２リンクの削除を指示する地図更新が発生した場合
（２）第１リンクの削除を指示する地図更新が発生し、その後、第２リンクの削除を指示する地図更新が発生した場合
について順次説明する。
【００８０】
まず、（１）第１リンクの追加を指示する地図更新が発生し、その後、第２リンクの削除を指示する地図更新が発生した場合について説明する。
この場合、図１３に示すように、最新地図データベース３８に記憶されている初期最新地図データではノード「Ａ」〜「Ｆ」とリンク「ａ１」、「ａ２」〜「ｇ１」、「ｇ２」との接続態様が図示のようにある場合を説明する。第１補助地図データベース３９に記憶されている初期第１補助地図データは、初期最新地図データと同じである。この状態からノード「Ｃ」とノード「Ｆ」とを接続するリンク「ｈ１」、「ｈ２」（第１リンクに相当）の追加を指示する地図更新が発生すると、差分グループ抽出処理部３２は、そのリンク「ｈ１」、「ｈ２」の追加を初期最新地図データに反映して第１期最新地図データ（次期最新地図データに相当）を作成するが、そのリンク「ｈ１」、「ｈ２」の追加を初期第１補助地図データに反映することなく、初期第１補助地図データをそのままとし、初期第１補助地図データを第１期第１補助地図データ（次期第１補助地図データに相当）とする。
【００８１】
この状態から更にノード「Ａ」とノード「Ｅ」とを接続するリンク「ｅ１」（第２リンクに相当）の削除を指示する地図更新が発生すると、差分グループ抽出処理部３２は、そのリンク「ｅ１」の削除を第１期最新地図データに反映して第２期最新地図データ（次々期最新地図データに相当）を作成し、そのリンク「ｅ１」の削除を第１期第１補助地図データに反映して第２期第１補助地図データ（次々期第１補助地図データに相当）を作成する。
【００８２】
ここで、差分グループ抽出処理部３２は、図１４に示すように、削除したリンク「ｅ１」の両端に位置するノード「Ａ」（第１ノードに相当）からノード「Ｅ」（第２ノードに相当）への経路探索を第２期第１補助地図データ上にて行うが、第２期第１補助地図データでは上記したようにリンク「ｈ１」、「ｈ２」の追加を反映していないことから、ノード「Ａ」からノード「Ｅ」への経路探索に失敗する。次いで、差分グループ抽出処理部３２は、第２期第１補助地図データ上での経路探索に失敗すると、削除したリンク「ｅ１」の両端に位置するノード「Ａ」からノード「Ｅ」への経路探索を第２期最新地図データ上にて行うが、第２期最新地図データでは上記したようにリンク「ｈ１」、「ｈ２」の追加を反映していることから、リンク「ｈ１」又は「ｈ２」を含むノード「Ａ」からノード「Ｅ」への経路探索に成功する。具体的には、リンク「ａ１」、「ｂ１」、「ｈ１」、「ｇ１」（「ｆ２」でも良い）を経由する経路探索に成功する。
【００８３】
そして、差分グループ抽出処理部３２は、このようにして第２期最新地図データ上での経路探索に成功すると、初期最新地図データから現在の最新地図データまでに発生した地図更新の内容、即ち、リンク「ｈ１」、「ｈ２」の追加とリンク「ｅ１」の削除との間に依存関係があると判定し、依存関係があると判定したリンク「ｈ１」、「ｈ２」の追加とリンク「ｅ１」の削除とを地図差分データとしてグループ化して差分グループデータベース３４に記憶する。
【００８４】
ここで、本実施形態では、上述したようにして道路の変化（更新）を地図差分データとしてグループ化して記憶させる場合に、変化した道路の目的（道路目的）の情報を付加しておく。この道路目的の情報の具体例としては、フリーウエイの本線から本線への乗り換え（図１７参照）、一般道での右左折（単なる交差点が、ロータリーなどに変更される変化パターンの例）などがあり、これらの情報を上記グループ化した地図差分データに関連付けて追加しておく。
【００８５】
次に、（２）第１リンクの削除を指示する地図更新が発生し、その後、第２リンクの削除を指示する地図更新が発生した場合について説明する。
この場合、図１５に示すように、最新地図データベース３８に記憶されている初期最新地図データではノード「Ｇ」〜「Ｌ」とリンク「ｉ１」、「ｉ２」〜「ｎ１」、「ｎ２」との接続態様が図示のようにある場合を説明する。第２補助地図データベース１１に記憶されている初期第１補助地図データは、初期最新地図データと同じである。この状態からノード「Ｉ」とノード「Ｋ」とを接続するリンク「ｌ１」、「ｌ２」（第１リンクに相当）の削除を指示する地図更新が発生すると、差分グループ抽出処理部３２は、そのリンク「ｌ１」、「ｌ２」の削除を初期最新地図データに反映して第１期最新地図データ（次期最新地図データに相当）を作成するが、そのリンク「ｌ１」、「ｌ２」の削除を初期第２補助地図データに反映することなく、初期第２補助地図データをそのままとし、初期第２補助地図データを第１期第２補助地図データ（次期第２補助地図データに相当）とする。
【００８６】
この状態から更にノード「Ｈ」とノード「Ｌ」とを接続するリンク「ｎ１」、「ｎ２」（第２リンクに相当）の削除を指示する地図更新が発生すると、差分グループ抽出処理部３２は、そのリンク「ｎ１」、「ｎ２」の削除を第１期最新地図データに反映して第２期最新地図データ（次々期最新地図データに相当）を作成するが、そのリンク「ｎ１」、「ｎ２」の削除を第１期第２補助地図データに反映することなく、第１期第２補助地図データを第２期第２補助地図データ（次々期第２補助地図データに相当）とする。
【００８７】
ここで、差分グループ抽出処理部３２は、図１６に示すように、第２期第２補助地図データを複写して一時的第２補助地図データを作成し、リンク「ｎ１」、「ｎ２」を一時的第２補助地図データから削除し、削除したリンク「ｎ１」、「ｎ２」の両端に位置するノード「Ｈ」（第１ノードに相当）からノード「Ｌ」（第２ノードに相当）への経路探索（ノード「Ｌ」からノード「Ｈ」への経路探索でも良い）を一時的第２補助地図データ上にて行うが、一時的第２補助地図データではリンク「ｎ１」、「ｎ２」の削除を反映しているが、リンク「ｌ１」、「ｌ２」の削除を反映していないことから、ノード「Ｈ」からノード「Ｌ」への経路探索に成功する。具体的には、リンク「ｊ１」、「ｌ１」、「ｍ１」を経由する経路探索に成功する。
【００８８】
そして、差分グループ抽出処理部３２は、経路探索に成功した経路に含まれるリンク「ｌ１」、「ｌ２」の削除とリンク「ｎ１」、「ｎ２」の削除との間に依存関係があると判定し、依存関係があると判定したリンク「ｌ１」、「ｌ２」の削除とリンク「ｎ１」、「ｎ２」の削除とを地図差分データとしてグループ化して差分グループデータベース３４に記憶する。ここで、本実施形態では、上述したようにして道路の変化（更新）を地図差分データとしてグループ化して記憶させる場合に、変化した道路の目的（道路目的）の情報を付加しておく。
【００８９】
そして、本実施形態では、以上説明したようにして、地図更新（道路の変化、即ち、道路の追加、変更、削除等の変化）が発生する毎に、その道路の変化を地図差分データとしてグループ化して差分グループデータベース３４に記憶されていく、即ち、差分グループ抽出処理を順次実行される構成となっている。
【００９０】
この構成によれば、道路ネットワークを保証する最小限のグループ化を実現することが可能となる。そして、このような差分グループ抽出処理を行うことで、近接する他の道路の変化を混入させることなく、次の処理を行うことが可能となる。また、道路ネットワーク的に直接接続した変化でなくても、道路ネットワークの関連として依存関係があるデータを一つのグループデータとして扱うことが可能となる。
【００９１】
尚、道路が更新（変化、変更）される場合の例として、核となる道路本線が生成され、その道路間を効率的に渡り歩けるように変更される場合などがあり、このような道路の変更も差分グループ化で抽出することが可能である。
【００９２】
また、上記した差分グループ抽出処理では、地図更新（道路の変化、即ち、道路の追加、変更、削除等の変化）が発生する毎に、その道路の変化を地図差分データとしてグループ化して記憶させるように構成したが、これに代えて、地図更新済の地図データベース（バージョンＡ（最新バージョン）の地図データベース）と地図更新前の古い地図データベース（バージョンＢ（一世代以上前の古いバージョン）の地図データベース）とを比較して、道路の変化がある部分抽出し、これら抽出した道路変化部分をそれぞれ地図差分データとしてグループ化して記憶させるように構成しても良い。このように構成しても、前記した構成とほぼ同様にして多数の差分グループを抽出して記憶することができる。
【００９３】
次に、モデル抽出処理部３６により道路変化モデルを作成または補正する処理について、図１７ないし図１９を参照して説明する。まず、モデル抽出処理部３６により作成する道路変化モデルの一例を図１７に示す。この道路変化モデルは、図１７に示すように、モデルＮＯ、道路目的、道路の変化パターン、判定許容値、及び、案内情報を有する。モデルＮＯは、道路変化モデルを特定するための番号（モデル番号）である。道路目的は、前述したように、一般道での右左折、フリーウエイの本線から本線への乗り換え等の道路の目的を示す情報である。
【００９４】
道路の変化パターンは、変化前の道路パターンと、変化後の道路パターンとで構成される。判定許容値は、変化前の道路パターンの始点及び終点の位置座標（元の道路と接続する座標）に対して許容された所定のずれ幅の情報と、変化後の道路パターンの始点及び終点の位置座標（元の道路と接続する座標）に対して許容された所定のずれ幅の情報とで構成される。案内情報は、車両が変化後の道路パターンで走行する際に必要な（適切な）カーナビの案内情報、例えば図形情報（変化後の道路の画像情報）や案内開始ポイントの位置座標や案内終了ポイントの位置座標や案内のメッセージ等で構成される。尚、案内開始および案内終了ポイントの位置座標には、設定されたずれ幅が許容されている。また、案内開始および案内終了ポイントは、判定許容値に基づいて形成される。即ち、判定許容値に基づいて、案内情報を出力するポイントを調節することが可能な構成となっている。
【００９５】
次いで、モデル抽出処理部３６の処理動作について、図１８のフローチャートを参照して説明する。まず、図１８のステップＳ４０１において、モデル抽出処理部３６は、差分グループデータベース３４内の全ての差分グループを処理したか否かを判断する。ここで、全ての差分グループを処理していない場合は、ステップＳ４０１にて「ＮＯ」へ進み、ステップＳ４０２へ進み、差分グループデータベース３４内から処理していない差分グループを取得する。
【００９６】
続いて、ステップＳ４０３へ進み、取得した差分グループと、道路変化モデルデータベース３７内の全ての道路変化モデル（地図モデルパターンと称しても良い）とを照合したか否かを判断する。ここで、全ての道路変化モデルと照合していないときには、ステップＳ４０３にて「ＮＯ」へ進み、ステップＳ４０４へ進み、道路変化モデルデータベース３７内から照合していない道路変化モデルを取得する。
【００９７】
次いで、ステップＳ４０５へ進み、対象の差分グループの道路目的と、照合対象の道路変化モデルの道路目的が一致するか否かを判断する。ここで、一致しなければ、ステップＳ４０５にて「ＮＯ」へ進み、ステップＳ４０３へ戻る。上記ステップＳ４０５にて、一致したときには、「ＹＥＳ」へ進み、ステップＳ４０６へ進み、対象の差分グループの道路の変化パターンと、照合対象の道路変化モデルの道路の変化パターンが一致するか否かを判断する。ここで、一致しなければ、ステップＳ４０６にて「ＮＯ」へ進み、ステップＳ４０３へ戻る。上記ステップＳ４０６にて、一致したときには、「ＹＥＳ」へ進み、ステップＳ４０７へ進み、対象の差分グループのデータ（例えば道路の判定許容値）を参照して照合対象の道路変化モデルの判定許容値を補正する。この後は、ステップＳ４０１へ戻る。
【００９８】
また、上記ステップＳ４０３において、道路変化モデルデータベース３７内の全ての道路変化モデルと照合したときには、ステップＳ４０３にて「ＹＥＳ」へ進み、ステップＳ４０８へ進み、新しい道路変化モデル（新しいモデルＮＯを付与した道路変化モデル）を作成する処理を開始する。まず、ステップＳ４０９へ進み、対象の差分グループのデータ（例えば道路目的）を参照して、新しい道路変化モデルの道路目的を生成する。
【００９９】
続いて、ステップＳ４１０へ進み、対象の差分グループのデータ（例えば道路の変化パターン）を参照して、新しい道路変化モデルの道路の変化パターンを生成する。そして、ステップＳ４１１へ進み、対象の差分グループのデータ（例えば道路の変化パターン）を参照して、新しい道路変化モデルの道路の判定許容値を生成する。この場合、判定許容値としては、ずれ幅のない初期値を設定する。次いで、ステップＳ４１２へ進み、対象の差分グループのデータ（例えば道路の目的、変化パターン等）を参照して、新しい道路変化モデルの道路の案内情報（案内のメッセージ（案内開始、案内終了ポイントの情報を含む）や、案内の図形情報等）を生成する。そして、これら生成した各情報と新しいモデルＮＯとからなる新しい道路変化モデルを道路変化モデルデータベース３７内に記憶する。この後は、ステップＳ４０１へ戻り、以下上述した処理を繰り返す。そして、ステップＳ４０１にて、差分グループデータベース３４内の全ての差分グループを処理したら、「ＹＥＳ」へ進み、モデル抽出処理部３６の処理を終了する。
【０１００】
ここで、道路変化モデルの変化パターンの特殊な例について説明する。図６（ａ）から図６（ｂ）に変化する道路変化モデルの変化パターンは、ループ型からスタック型への変更である。このようなループ型からスタック型への変更の変化パターンとしては、図１９（ａ）から図１９（ｂ）に変化する道路変化モデルの変化パターンが存在する。これら２つの変化パターンは、ループ型からスタック型への変更という道路形状の変化だけを考慮して判定すると、同一と判定され、その結果として、同じ案内情報で案内されてしまうおそれがある。
【０１０１】
そこで、上記２つの変化パターンを区別するための照合条件が必要となる。例えば、道路形状はある程度の誤差や大小の違いは許容範囲内であるが、道路の途中に分岐があるかどうかなどを厳密に判定すれば、上記２つの変化パターンを明確に区別することが可能となる。従って、本実施形態では、道路の途中に分岐が発生しているかどうかの情報を、道路変化モデル（や差分グループ）の変化パターンに含めるように構成している。
【０１０２】
このような構成の本実施形態によれば、照合対象の差分グループを道路変化モデルデータベース３７内の全ての道路変化モデルと照合し、一致する道路変化モデルが存在しない場合に、照合対象の差分グループのデータを参照して、新しい道路変化モデルを生成するように構成したので、必要な道路変化モデルを順次作成することができる。そして、本実施形態では、道路変化モデルを生成する場合に、道路目的、変化パターン、判定許容値、案内情報を生成して記憶するように構成したので、差分グループと道路変化モデルの照合を正確に実行できると共に、道路変化モデルに沿った経路（道路）の経路案内を適切に実行することができる。また、本実施形態では、照合対象の差分グループを道路変化モデルデータベース３７内の全ての道路変化モデルと照合して、一致した場合に、道路変化モデルの判定許容値の補正を行うように構成したので、道路変化モデルの精度を向上させることができるから、道路変化モデルに沿った経路（道路）の経路案内をより一層適切に実行できる。
【０１０３】
（第４実施形態）
図２０は、本発明の第４実施形態を示すものである。尚、第１実施形態（図２参照）と同一ステップには、同一ステップ番号を付している。この第４実施形態では、まず、図２０のＳ５０１において、走行軌跡作成部１７は、位置検出部２にて検出した現在位置座標（経緯度値）を一定時間（例えば１〜５秒）毎に取り込み、走行軌跡の情報を作成する（図２のＳ１０１の処理と同様に）と共に、作成した走行軌跡の情報をメモリ部５に記憶する。この走行軌跡から走行方向が判る。また、移動距離及びその移動に要した時間も得られるので、平均走行速度も判る。更に、本実施形態では、例えば数百ないし数千ｋｍ程度（または数週間ないし数か月分程度）の走行軌跡の情報を、過去の走行軌跡の情報としてメモリ部５に記憶することが可能になっている。
次に、このようにして得た走行軌跡と、地図データ格納部３から取得された道路地図データの道路形状データとを比較し、道路離脱状態か否かを判定する（Ｓ１０２）。そして、道路離脱状態である場合には（Ｓ１０２：ＹＥＳ）、メモリ部５内に記憶している過去の走行軌跡の情報に基づいて、道路離脱しなかったと仮定した場合に本来走行すると予想される道路地図データの道路、即ち、現在廃止された道路（廃止道路、旧道路）を過去において走行したか否かを判断する（Ｓ５１０）。ここで、上記廃止道路を過去において走行していたときには（Ｓ５１０：ＹＥＳ）、上記廃止道路の過去の走行軌跡をメモリ部５から読み出す。この場合、廃止道路及びその前後の道路をセットにして読み出す。
【０１０４】
続いて、後述するようにして蓄積した道路離脱状態の走行軌跡の情報と比較して、同様の道路離脱状態の走行軌跡のものが存在するか否かを判定する（Ｓ１０３）。同様の道路離脱状態の走行軌跡のものが存在しない場合には（Ｓ１０３：ＮＯ）、作成回数を１とし（Ｓ１０４）、その道路離脱状態の走行軌跡（即ち、新規道路及びその前後の道路を走行した走行軌跡）の情報と、前記Ｓ５２０で読み出した過去の走行軌跡（即ち、廃止道路及びその前後の道路を走行した走行軌跡）の情報があればその情報とをセットにした情報をメモリ部５へ蓄積して（Ｓ５０５）、本処理を終了する。つまり、道路地図データには存在しない新規に作成された道路（新規道路）及び廃止された道路（廃止道路）であるとして、上記各走行軌跡などの情報（走行軌跡情報）をメモリ部５に蓄積しておく。この場合、制御部９は、走行軌跡情報収集手段及び過去走行軌跡情報収集手段としての機能を有している。
【０１０５】
一方、同様の走行軌跡のものが存在する場合には（Ｓ１０３：ＹＥＳ）、その走行軌跡の作成回数が所定値以上であるか否かを判定し（Ｓ１０６）、所定値未満であれば（Ｓ１０６：ＮＯ）、その走行軌跡に対する作成回数を１増やし（Ｓ１０７）、本処理を終了する。
【０１０６】
このようにして同様の道路離脱状態の走行軌跡が作成され、作成回数が増えていくことによって、その走行軌跡の作成回数が所定値以上となった場合には（Ｓ１０６：ＹＥＳ）、Ｓ５０５にて蓄積しておいた走行軌跡情報、即ち、新規道路及びその前後の道路の走行軌跡並びに廃止道路及びその前後の道路の走行軌跡などの情報を情報センタ２１へ送信する（Ｓ５０８）。その後、上記走行軌跡などの情報が送信済であることをメモリ部５に記録して（Ｓ５０９）、本処理を終了する。尚、上記Ｓ５０９において、走行軌跡などの情報が送信済であることをメモリ部５に記録しておくと、送信済みの走行軌跡に該当する道路が送信済であることがわかるから、その後、同じ道路を走行したときに、前述した処理（新規道路として判断したり、新規道路情報等を情報センタ２１へ送信したりする処理等）が実行されることを防止できる。
【０１０７】
上述した以外の第４実施形態の構成は、第１実施形態と同じ構成となっている。従って、第４実施形態においても、第１実施形態とほぼ同じ作用効果を得ることができる。特に、第４実施形態によれば、新規道路及びその前後の道路の走行軌跡などの情報と、廃止道路及びその前後の道路の走行軌跡などの情報とをセットにして情報センタ２１へ送信する構成としたので、情報センタ２１においては、受信した新規道路及びその前後の道路の走行軌跡などの情報並びに廃止道路及びその前後の道路の走行軌跡などの情報と、道路変化モデルとに基づいて、新規道路と廃止道路を推測する構成となるから、新規道路と廃止道路の推測の精度を向上させることができる。
【０１０８】
尚、上記各実施形態では、情報センタ２１において、新規道路と廃止道路とを推測する際に、車両Ａのナビゲーション装置１から送信された新規道路の走行軌跡の情報と、データベース２４内に記憶されている道路変化モデルを比較して推測したが、これに限られるものではなく、情報センタ２１にて蓄積（収集）した交通情報、例えば渋滞情報や道路工事情報などを加味して新規道路と廃止道路とを推測するように構成しても良い。このように構成すると、新規道路の走行軌跡の情報と道路変化モデルとだけに基づいて推測する構成に比べて、新規道路と廃止道路をより一層正確に推測することができる。尚、情報センタ２１は、例えばＶＩＣＳ（登録商標）等から交通情報を回線端末装置２２、電話局１９及び無線基地局１８を介して受信して収集する機能（交通情報収集手段としての機能）を備えていることが好ましい。
【０１０９】
また、上記第２実施形態では、情報センタ２１のデータベース２４内に記憶されている現在使用中の道路地図データと、車両Ｂのナビゲーション装置１内に搭載されている道路地図データとが同じものであるとして、現在地から目的地までの経路Ｒ１、Ｒ２を算出するように構成したが、これに代えて次のように構成しても良い。通常、複数の車両の各ナビゲーション装置１では、新旧様々のバージョン（及び種々の地図データ製造会社）の道路地図データが使用されている。また、情報センタ２１のデータベース２４内には、新旧様々のバージョン（及び種々の地図データ製造会社）の道路地図データが記憶されている。そこで、車両Ｂのナビゲーション装置１から情報センタ２１へ目的地の情報と車両Ｂの現在地（出発地）の情報を送信するときに、道路地図データの識別情報（即ち、バージョン情報及び地図データ製造会社名称等の情報）を付加して送信するように構成する。そして、情報センタ２１では、車両Ｂのナビゲーション装置１から送信された目的地の情報と車両Ｂの現在地（出発地）の情報と道路地図データの識別情報とを受信し、データベース２４内に記憶されている同じバージョン且つ同じ地図データ製造会社の道路地図データ（即ち、車両Ｂのナビゲーション装置１内に搭載されている道路地図データと同じもの）を使って、上記第２実施形態と同様にして、現在地から目的地までの経路Ｒ１、Ｒ２を算出する処理と、これら算出された経路Ｒ１、Ｒ２と道路地図データ内に格納されている道路の形状データや、交差点の位置情報、踏切の位置情報等から、案内指示に必要なポイントを算出したり、どのような案内指示が必要なのかを算出する処理とを実行するように構成することが好ましい。
【０１１０】
更に、車両のナビゲーション装置１で行う経路算出処理（及び経路案内算出処理）のアルゴリズム（処理プログラム）と、情報センタ２１で行う経路算出処理（及び経路案内算出処理）のアルゴリズム（処理プログラム）とを同じにするために、車両のナビゲーション装置１の経路算出処理（及び経路案内算出処理）のアルゴリズム（処理プログラム）を識別するプログラム識別情報を、目的地の情報と車両の現在地（出発地）の情報と道路地図データの識別情報とを送信するときに、一緒に情報センタ２１に送信するように構成しても良い。このように構成すれば、車両のナビゲーション装置１のアルゴリズム（処理プログラム）が種々様々であっても、車両のナビゲーション装置１と情報センタ２１とにおいて、同じアルゴリズム（処理プログラム）で経路算出処理（及び経路案内算出処理）を行うことができる。
【０１１１】
なお、第１実施形態では、情報センタ２１にて、過去において使用していた古い道路地図データ（以下旧道路地図データと称す）と、最近更新した最も新しい道路地図データ（以下新道路地図データと称す、第２の道路地図データ）とを比較して、廃止された道路があると共に現在使用されている新規道路がある道路変化部分を多数抽出し、廃止道路と新規道路に基づいて道路変化モデルを多種類作成し、これらをデータベース２４内に記憶するようにしていたが、これに限定されるものではない。例えば、ナビゲーション装置１にて最新の道路地図データをダウンロードし、その情報を記憶し、ダウンロードする前に使用していた古い道路地図データとダウンロードした後の新しい道路地図データとを比較して、廃止された道路があると共に現在使用されている新規道路がある道路変化部分を多数抽出し、廃止道路と新規道路に基づいて道路変化モデルを多種類作成し、これらをナビゲーション装置１内に記憶させるようにしてもよい。
【０１１２】
また、情報センタ２１あるいはナビゲーション装置１にて、古い道路地図データと新しい道路地図データとを比較して道路変化モデルを作成する必要はなく、予め多数の道路変化モデルを情報センタ２１あるいはナビゲーション装置１にて記憶させておき、新規道路の走行軌跡の情報とこの予め備えたナビゲーション装置１にて記憶された道路変化モデルとに基づいて廃止道路と新規道路とを推測しても良い。このとき、ナビゲーション装置１に記憶している道路地図データを更新するようにするほうが好ましい。
【０１１３】
尚、上記第３実施形態では、モデル作成装置３１を情報センタ２１に備えるように構成したが、これに限られるものではなく、モデル作成装置を車載のナビゲーション装置や他の専用端末等に備えるように構成しても良い。
【０１１４】
また、上記各実施形態では、ナビゲーション装置として、車載のナビゲーション装置１を例に説明したが、それに限らず、例えば、ＰＮＤ（Ｐｏｒｔａｂｌｅ Ｎａｖｉｇａｔｉｏｎ Ｄｅｖｉｃｅ）や携帯ナビであっても良い。また、車両について説明したが、これに限定されるのではなく道路上を移動するものであれば、それに適用しても良い。
【符号の説明】
【０１１５】
図面中、１は車載のナビゲーション装置（ナビゲーション装置）、２は位置検出部、３は地図データ格納部（記憶手段）、４はスイッチ情報入力部、５はメモリ部、８はデータ通信部、９は制御部（走行軌跡情報収集手段、過去走行軌跡情報収集手段）、１０は地図データ取得部、１１はマップマッチング部、１２は経路計算部、１３は経路案内部、１６は通信制御部、１７は走行軌跡作成部（走行軌跡検出手段）、１８は無線基地局、１９は電話局、２１は情報センタ、２２は回線端末装置、２３はサーバ、２４はデータベース、２５は旧道路地図データ、２６は新道路地図データ、３１はモデル作成装置、３２は差分グループ抽出処理部、３３は地図データベース群、３４は差分グループデータベース、３５は地図更新情報入力部、３６はモデル抽出処理部、３７は道路変化モデルデータベース、３８は最新地図データベース、３９は第１補助地図データベース、４０は第２補助地図データベースを示す。
【図１】
2015007657.tif 000003
【図２】
2015007657.tif 000004
【図３】
2015007657.tif 000005
【図４】
2015007657.tif 000006
【図５】
2015007657.tif 000007
【図６】
2015007657.tif 000008
【図７】
2015007657.tif 000009
【図８】
2015007657.tif 000010
【図９】
2015007657.tif 000011
【図１０】
2015007657.tif 000012
【図１１】
2015007657.tif 000013
【図１２】
2015007657.tif 000014
【図１３】
2015007657.tif 000015
【図１４】
2015007657.tif 000016
【図１５】
2015007657.tif 000017
【図１６】
2015007657.tif 000018
【図１７】
2015007657.tif 000019
【図１８】
2015007657.tif 000020
【図１９】
2015007657.tif 000021
【図２０】
2015007657.tif 000022