経路探索システム、道路データ生成装置、経路探索用データ及びサーバ装置用プログラム並びに経路探索方法
【課題】更新すべき道路情報についての地域的な範囲が無限大に広がることを防止し、更新が必要な道路情報を的確に更新して経路探索をすることが可能な経路探索システムを提供する。
【解決手段】最新の道路データを提供するサーバ装置において、道路が敷設されている地域をメッシュＭに区分し、各メッシュＭに対してその地域を代表する代表地点Ｘを定める。サーバ装置内には、全ての代表地点Ｘ相互間を移動する際の経路を網羅的に予め探索した結果を蓄積記憶しておく。カーナビゲーションシステムにおいて探索された結果とサーバ装置に蓄積されている代表地点間経路とが異なっているとき、当該代表地点間経路を示す道路データを用いてカーナビゲーションシステムに蓄積されている道路データを更新する。
【解決手段】最新の道路データを提供するサーバ装置において、道路が敷設されている地域をメッシュＭに区分し、各メッシュＭに対してその地域を代表する代表地点Ｘを定める。サーバ装置内には、全ての代表地点Ｘ相互間を移動する際の経路を網羅的に予め探索した結果を蓄積記憶しておく。カーナビゲーションシステムにおいて探索された結果とサーバ装置に蓄積されている代表地点間経路とが異なっているとき、当該代表地点間経路を示す道路データを用いてカーナビゲーションシステムに蓄積されている道路データを更新する。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、経路探索システム、道路データ生成装置、サーバ装置、端末装置、経路探索用データ、サーバ装置用プログラム及び端末装置用プログラム並び経路探索方法の技術分野に属し、より詳細には、サーバ装置に蓄積されている最新の道路情報を用いて端末装置上の道路情報を更新しつつ、当該端末装置において経路探索を行う経路探索システム及び経路探索方法並びに当該経路探索用データ、当該経路探索用データ自体を生成する道路データ生成装置、当該サーバ装置及び当該端末装置、並びに当該サーバ装置用プログラム及び当該端末装置用プログラムの技術分野に属する。
【背景技術】
【０００２】
近年、日本全国の道路に相当する道路情報を最新に更新しつつ蓄積するサーバ装置と、当該サーバ装置とネットワーク等を介して接続された端末装置等を含み、当該端末装置の移動に適した経路としての道路をサーバ装置と連携して探索する経路探索システムが普及しつつある。ここで、当該端末装置の具体例としては、例えばいわゆるカーナビゲーション装置や、携帯型電話機或いは携帯型情報端末装置に付加された個別機能としてのナビゲーション装置等が挙げられる。
【０００３】
ここで、従来の上記経路探索システムでは、端末装置の移動経路を当該端末装置において探索する場合、サーバ装置に蓄積されている最新の道路情報及び関連する地図情報を取得して端末装置内の道路情報を更新した上で、その更新された道路情報を用いて探索処理を実行することが望まれる。
【０００４】
このとき、当該端末装置上の道路情報をサーバ装置上の道路情報を用いて更新するための技術としては、例えば下記特許文献１に記載されているように、サーバ装置内に蓄積されている道路情報のバージョンと、端末装置内に蓄積されている道路情報のバージョンとを比較し、サーバ装置内に蓄積されているバージョン情報の方が新しい場合にのみ、その新しいバージョンの道路情報を用いて端末装置内の道路情報を更新する方法がある。
【０００５】
一方、当該更新を行う際、地図上のどの地域まで道路情報を更新するかの地域的な判断に当たっては、サーバ装置と端末装置間における通信量やそれに伴って発生する通信料金等を考慮すると、なるべく少ない通信量で必要な地域だけの更新処理が完了することが望ましい。
【０００６】
そこで、従来では、当該更新処理を実行する際における更新対象地域の判断に当たっては、例えば都道府県や市町村等の行政区分を基準とした範囲で、探索対象の道路が含まれている行政区分に相当する道路情報を更新することが為されていた。
【特許文献１】特開２００６−６５２４６公報 （第２図等）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した従来の更新対象地域の確定方法によると、行政区分を単位として更新対象地域を確定していたため、結果として、更新対象となった行政区分と更新対象とならなかった行政区分とに跨って敷設されている道路については、当該行政区分の境界線上において当該更新の前後において不整合（道路としての連続性が乱される食い違い）が発生する。
【０００８】
ここで、例えば経路探索処理において種々の異なる条件によって経路が探索される可能性（換言すれば、当該条件に対応した種々の道路が広範囲に探索される可能性）を考慮すると、上述した不整合は存在しない方が望ましい。このため、一つの行政区分について道路情報を更新した結果、それに隣接する行政区分との間で上述した不整合が発生した場合には、当該隣接する行政区分の道路情報まで更新する必要があることになり、このことが行政区分毎に連鎖的に繰り返されることで、結果的に更新対象地域が無限に広がってしまう可能性があるという問題点があった。
【０００９】
そしてこのことは、上記少ない通信量で更新を行うことが必要となる点を考慮した場合、是非とも解決すべき問題点となる。
【００１０】
そこで、本願は上記の各問題点に鑑みて為されたもので、その課題の一例は、更新すべき道路情報についての地域的な範囲が無限大に広がることを防止し、更新が必要な道路情報を的確に更新して経路探索をすることが可能な経路探索システム及び経路探索方法並びに当該経路探索用データ、当該経路探索用データ自体を生成する道路データ生成装置、当該サーバ装置及び当該端末装置、並びに当該サーバ装置用プログラム及び当該端末装置用プログラムを提供することにある。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、請求項１に記載の発明は、サーバ道路情報を最新に更新しつつ蓄積するサーバ装置と、当該サーバ装置に接続され且つ端末道路情報を蓄積して案内処理を行うカーナビゲーションシステム等の端末装置と、を含むナビゲーションシステムに含まれ、前記端末装置が移動する経路を探索する経路探索システムにおいて、前記サーバ装置は、道路が敷設され且つ予め区分された地域を代表するものとして当該地域毎に予め設定されている代表地点であって最新の前記サーバ道路情報に対応する代表地点を示す代表地点情報と、全ての当該代表地点情報相互間を移動する際に用いるべき前記道路を示す代表地点間経路情報と、を前記最新のサーバ道路情報と共に蓄積するデータベース等の蓄積手段を備え、前記端末装置は、前記端末装置が移動する前記経路の出発地点に対応する出発代表地点と、当該経路の目的地点に対応する目的代表地点と、を設定するナビゲーション処理部等の代表地点設定手段と、前記設定された出発代表地点から前記設定された目的代表地点までの代表地点間経路に対応する経路情報を前記サーバ装置に送信するインターフェース等の端末装置送信手段と、前記サーバ装置から前記端末道路情報の更新に用いられるべき更新道路情報が送信されて来たとき、当該送信されて来た更新道路情報を用いて前記蓄積されている端末道路情報を更新するナビゲーション処理部等の更新手段と、前記更新後の端末道路情報を用いて前記出発地点から前記目的地点までの経路を探索するナビゲーション処理部等の探索手段と、を備え、更に前記サーバ装置は、前記送信されて来た経路情報に対応する前記出発代表地点から前記送信されて来た経路情報に対応する前記目的代表地点まで移動する際に用いるべき前記道路を示す前記代表地点間経路情報を、前記蓄積手段から抽出するＣＰＵ等の抽出手段と、前記抽出された代表地点間経路情報と、前記送信されて来た経路情報と、を比較し、前記端末道路情報を更新すべきか否かを判断するＣＰＵ等の判断手段と、前記端末道路情報を更新すべきであると判断されたとき、当該更新に用いられるべき前記更新道路情報を前記端末装置に送信するインターフェース等のサーバ装置送信手段と、を備える。
【００１２】
上記の課題を解決するために、請求項１１に記載の発明は、請求項７から１０のいずれか一項に記載の経路探索システムに含まれる前記サーバ装置に蓄積される前記サーバ道路情報と、前記代表地点情報と、前記代表地点間経路情報と、を夫々生成する道路データ生成装置であって、予め設定された期間毎に前記サーバ道路情報を最新に更新するＣＰＵ等のサーバ道路情報更新手段と、前記更新されたサーバ道路情報に対応して前記代表地点情報を更新するＣＰＵ等の代表地点情報更新手段と、前記更新されたサーバ道路情報に対応して前記代表地点間経路情報を更新するＣＰＵ等の代表地点間経路情報更新手段と、を備える。
【００１３】
上記の課題を解決するために、請求項１２に記載の発明は、請求項１から１１のいずれか一項に記載のサーバ装置内の前記蓄積手段に蓄積されている経路探索用データであって、前記代表地点間経路情報の生成に用いられ且つ前記更新道路情報を抽出可能に構成された前記サーバ道路情報と、最新の前記サーバ道路情報に対応した前記地域を示す地域情報と、当該最新の地域毎に設定された前記代表地点を示す前記代表地点情報と、当該最新の代表地点情報に基づいて網羅的に探索された代表地点間経路としての前記道路を示す前記代表地点間経路情報と、を含むように構成されている。
【００１４】
上記の課題を解決するために、請求項１３に記載の発明は、請求項１から１０に記載の経路探索システムに含まれる前記サーバ装置であって、前記蓄積手段と、前記抽出手段と、前記判断手段と、前記サーバ装置送信手段と、を備える。
【００１５】
上記の課題を解決するために、請求項１４に記載の発明は、請求項１から１０に記載の経路探索システムに含まれる前記端末装置であって、前記代表地点設定手段と、前記端末装置送信手段と、前記更新手段と、前記探索手段と、を備える。
【００１６】
上記の課題を解決するために、請求項１５に記載の発明は、請求項１から１０に記載の経路探索システムに含まれ且つ前記蓄積手段を備える前記サーバ装置に含まれるコンピュータを、前記抽出手段、前記判断手段、及び、前記サーバ装置送信手段、として機能させる。
【００１７】
上記の課題を解決するために、請求項１６に記載の発明は、請求項１から１０に記載の経路探索システムに含まれる前記端末装置に含まれるコンピュータを、前記代表地点設定手段、前記端末装置送信手段、前記更新手段、及び、前記探索手段、として機能させる。
【００１８】
上記の課題を解決するために、請求項１７に記載の発明は、サーバ道路情報を最新に更新しつつ蓄積するサーバ装置と、当該サーバ装置に接続され且つ端末道路情報を蓄積して案内処理を行うカーナビゲーションシステム等の端末装置と、を含むナビゲーションシステムに含まれる当該端末装置が移動する経路を探索する経路探索方法において、前記サーバ装置は、道路が敷設され且つ予め区分された地域を代表するものとして当該地域毎に予め設定されている代表地点であって最新の前記サーバ道路情報に対応する代表地点を示す代表地点情報と、全ての当該代表地点情報相互間を移動する際に用いるべき前記道路を示す代表地点間経路情報と、を前記最新のサーバ道路情報と共に蓄積する蓄積手段を備えており、前記端末装置が移動する前記経路の出発地点に対応する出発代表地点と、当該経路の目的地点に対応する目的代表地点と、を当該端末装置において設定する代表地点設定工程と、前記設定された出発代表地点から前記設定された目的代表地点までの代表地点間経路に対応する経路情報を当該端末装置から前記サーバ装置に送信する第１送信工程と、前記サーバ装置において、前記送信されて来た経路情報に対応する前記出発代表地点から前記送信されて来た経路情報に対応する前記目的代表地点まで移動する際に用いるべき前記道路を示す前記代表地点間経路情報を、前記蓄積手段から抽出する抽出工程と、前記サーバ装置において、前記抽出された代表地点間経路情報と、前記送信されて来た経路情報と、を比較し、前記端末道路情報を更新すべきか否かを判断する判断工程と、前記判断工程において前記端末道路情報を更新すべきであると判断されたとき、当該更新に用いられるべき更新道路情報を前記サーバ装置から当該端末装置に送信する第２送信工程と、前記更新道路情報が送信されて来た前記端末装置において、当該送信されて来た更新道路情報を用いて前記蓄積されている端末道路情報を更新する更新工程と、前記端末道路情報が更新された前記端末装置において、当該更新後の端末道路情報を用いて前記出発地点から前記目的地点までの経路を探索する探索工程と、を含む。
【発明を実施するための最良の形態】
【００１９】
次に、本願を実施するための最良の形態について、図面に基づいて説明する。なお、以下に説明する実施形態は、経路探索用の道路データを含む地図データを常時最新の状態となるように更新しつつ蓄積するサーバ装置と、当該サーバ装置に蓄積されている最新の道路データを用いて自ら蓄積している道路データを更新しつつ経路探索を行うカーナビゲーションシステムと、を含む経路探索システムに対して本願を適用した場合の実施の形態である。
【００２０】
（Ｉ）第１実施形態
始めに、本願に係る第１実施形態について、図１乃至図７を用いて説明する。なお、図１は第１実施形態に係る経路探索システムの概要構成を示すブロック図であり、図２は当該経路探索システムに含まれる各装置の細部構成を示すブロック図であり、図３は第１実施形態に係る道路データの構成を例示する図であり、図４は第１実施形態に係る代表地点の状態を例示する図であり、図５は第１実施形態に係るサーバ装置における地図データ等の更新を示すフローチャートであり、図６は第１実施形態に係るカーナビゲーションシステムの概要構成を示すブロック図であり、図７は第１実施形態に係る経路探索処理を示すフローチャートである。
【００２１】
図１に示すように、第１実施形態に係る経路探索システムＳは、上記サーバ装置ＳＶと、インターネット等のネットワークＮＴと、複数のカーナビゲーションシステムＮＶと、地図データ更新装置ＰＣと、により構成されている。
【００２２】
このとき、地図データ更新装置ＰＣは、サーバ装置ＳＶ内に蓄積されている上記地図データを最新の状態に更新する際、当該更新のための地図更新データＳupdateを生成し、サーバ装置ＳＶに出力する。
【００２３】
そして、サーバ装置ＳＶは、当該地図更新データＳupdateを用いて上記地図データを最新の状態に更新しつつ、各カーナビゲーションシステムＮＶと別個独立に夫々地図データ等の授受を行ない、後述する第１実施形態に係る経路探索処理を実行する。
【００２４】
このとき、サーバ装置ＳＶから出力される各種データは、サーバ信号ＳsvとしてネットワークＮＴに送信される。そして、当該ネットワークＮＴを介してカーナビ信号Ｓnvとして各カーナビゲーションシステムＮＶに出力される。
【００２５】
これと反対に、カーナビゲーションシステムＮＶから出力されるべき各種データは、カーナビ信号ＳnvとしてネットワークＮＴに送信される。そして、当該ネットワークＮＴを介してサーバ信号Ｓsvとしてサーバ装置ＳＶに出力される。
【００２６】
次に、上記サーバ装置ＳＶの細部構成及び動作について、図２（ａ）並びに図３及び図４を用いて説明する。
【００２７】
図２（ａ）に示すように、サーバ装置ＳＶは、例えばハードディスク等からなる蓄積手段としてのデータベース１と、抽出手段及び判断手段としてのＣＰＵ２と、メモリ３と、キーボード又はマウス等を含む入力部５と、液晶ディスプレイ等からなるディスプレイ６と、ネットワークＮＴ又は地図データ更新装置ＰＣとＣＰＵ２とを接続するサーバ装置送信手段としてのインターフェース４と、により構成されている。
【００２８】
このとき、データベース１内には第１実施形態に係る経路探索用の道路データ１Ａと、後述する代表地点の内容を各代表地点毎に夫々示す代表地点情報１Ｂと、後述する代表地点間経路情報１Ｃと、を含む上記地図データが、上記地図更新データＳupdateを用いて定期的に更新されつつ蓄積記憶されている。
【００２９】
一方、インターフェース４は、上記地図更新データＳupdate又は上記サーバ信号Ｓsvに対して予め設定された入出力インターフェース処理を実行する。そして、上記地図更新データＳupdate又は上記サーバ信号Ｓsvとしてサーバ装置ＳＶに入力されるべきデータをインターフェース信号ＳifとしてＣＰＵ２に出力すると共に、上記サーバ信号Ｓsvとして各カーナビゲーションシステムＮＶに出力すべきデータがインターフェース信号ＳifとしてＣＰＵ２から出力されて来ると、これをサーバ信号Ｓsvに変換してネットワークＮＴに出力する。
【００３０】
そして、ＣＰＵ２は、データベース１内の地図データの更新時においては上記地図更新データＳupdateとして送信されて来る地図データ更新用のデータを用いて当該地図データの更新処理を実行すると共に、当該更新された地図データを用いて後述する第１実施形態に係る経路探索処理を実行する。
【００３１】
このとき、例えば上記地図データの更新時においてＣＰＵ２を動作させるために必要な指示は、入力部５を用いてその操作者により実行され、当該実行された指示操作に対応する操作信号ＳopとしてＣＰＵ２に送信される。これにより、当該ＣＰＵ２は、当該操作信号Ｓopの内容に応じて上記更新のための処理等を実行する。
【００３２】
また、サーバ装置ＳＶ自体の稼働状態は、ＣＰＵ２から出力される表示信号Ｓdpとしてディスプレイ６に出力され、当該ディスプレイ６において予め設定された表示形式で表示される。
【００３３】
更に、上記ＣＰＵ２の動作に必要な種々のデータは、メモリ信号Ｓmとしてメモリ３に出力され、当該メモリ３において揮発的に又は不揮発的に記憶され、更に必要に応じて再度メモリ信号Ｓmとして読み出される。
【００３４】
次に、データベース１内に蓄積されている、第１実施形態に係る上記道路データ１Ａ、代表地点情報１Ｂ及び代表地点間経路情報１Ｃについて、夫々図３及び図４を用いて具体的に説明する。
【００３５】
先ず、第１実施形態に係る経路探索処理用の道路データ１Ａは、具体的には、道路上の地点を示すノードを示すノード情報（当該ノードの位置を示す緯度情報及び経度情報並びに高度情報等を含む）と、当該ノード間を連結するリンクを示すリンク情報（当該リンクに相当する道路を識別するための道路識別情報や、当該リンクに相当する道路の実際の（現実の）長さを示す情報等を含む）と、の組み合わせから構成されている。
【００３６】
そして、当該道路データ１Ａは、例えば図３に例示するように、道路が敷設されている地域的範囲であってメッシュ番号により区分されるメッシュＭ１、Ｍ２、Ｍ３、…、Ｍnを単位としてデータベース１内に蓄積されている。
【００３７】
ここで、当該メッシュＭの決め方については、基本的には、経路探索処理を実行する際の便宜を考慮してその地図データの制作者により任意に決定し得るものであるが、例えば、当該道路データ１Ａに対応する地図の縮尺毎に異なる広さに相当するものとして決定してもよいし、或いは同一縮尺の地図内でも、道路密集度又は交通量等に基づいて異なる広さのメッシュＭを決めることも可能である。
【００３８】
なお、以下に説明する第１実施形態では、当該メッシュＭの例として方形のメッシュＭについて説明しているが、メッシュＭの形状自体については、方形に限らず、任意の多角形として決めることができるのであり、更には、都道府県等の行政区分境界を基準としてメッシュＭを分割することも可能である。
【００３９】
次に、第１実施形態では、上記各メッシュＭ毎に、そのメッシュＭに相当する地域内に敷設されている道路上の地点を代表する代表地点を設定する。すなわち、例えば隣接する県を含めた東京都の例を用いて図４に示すように、各メッシュＭＬ、ＭＬ＋１、ＭＬ＋２、ＭＬ＋３、…の夫々について、一対一の関係となる代表地点ＸＬ、ＸＬ＋１、ＸＬ＋２、ＸＬ＋３、…を各々設定する。
【００４０】
ここで、一つのメッシュＭ内の代表地点Ｘの決定方法としては、これも基本的には経路探索処理を実行する際の便宜を考慮してその地図データの制作者により任意に決定し得るものであるが、例えば、その代表地点Ｘが代表するメッシュＭ内において最も交通量の多い交差点と当該代表地点Ｘとすることもできるし、また、その代表地点Ｘが代表するメッシュＭの中心に最も近い道路上の地点を当該代表地点Ｘとしてもよい。更には、その代表地点Ｘが代表するメッシュＭ内にある高速道路の入口のいずれかを当該代表地点Ｘとしてもよい。
【００４１】
そして、これら代表地点Ｘ夫々を識別するための代表地点識別情報、当該代表地点Ｘ夫々の地図データ更新におけるバージョン情報並びに各代表地点Ｘの位置自体を示す緯度情報、経度情報及び高度情報等が上記代表地点情報１Ｂとしてデータベース１内に蓄積されている。
【００４２】
最後に、第１実施形態に係る経路探索処理用の代表地点間経路情報１Ｃは、一つの代表地点Ｘを出発地点とし、他の全ての代表地点Ｘを夫々目的地点とした経路の各々を示す経路情報を、全ての代表地点Ｘを出発地点とした場合について網羅的に集積した経路情報である。すなわち、全ての縮尺の地図における上記代表地点Ｘにつき、二つの代表地点Ｘ間を移動する際に採用される経路を、全ての二つの代表地点Ｘの組み合わせてについて夫々求めた経路情報である。
【００４３】
次に、上記地図データ更新装置ＰＣの細部構成及び動作について、図２（ｂ）を用いて説明する。
【００４４】
図２（ｂ）に示すように、地図データ更新装置ＰＣは、ハードディスクを含むＨＤＤ（Hard Disc Drive）１０と、サーバ道路情報更新手段、代表地点情報更新手段及び代表地点間経路情報更新手段としてのＣＰＵ１１と、メモリ１２と、キーボード又はマウス等を含む入力部１４と、液晶ディスプレイ等からなるディスプレイ１５と、サーバ装置ＳＶとＣＰＵ１１とを接続するインターフェース１３と、により構成されている。
【００４５】
このとき、ＨＤＤ１０内には外部からインターフェース１３を介して送信されてきた最新の地図データ等が蓄積記憶される。
【００４６】
一方、インターフェース１３は、上記地図更新データＳupdateに対して予め設定された入出力インターフェース処理を実行する。そして、上記地図更新データＳupdateとしてサーバ装置ＳＶに出力すべきデータがインターフェース信号ＳifとしてＣＰＵ１１から出力されて来ると、これを地図更新データＳupdateに変換してサーバ装置ＳＶに出力する。
【００４７】
そして、ＣＰＵ１１は、ＨＤＤ１０内の最新の地図データ等を用いて後述するサーバ装置ＳＶ内の地図データの更新処理に必要なデータを生成する。
【００４８】
このとき、当該データの生成時においてＣＰＵ１１を動作させるために必要な指示は、入力部１４を用いてその操作者により実行され、当該実行された指示操作に対応する操作信号ＳopとしてＣＰＵ１１に送信される。これにより、当該ＣＰＵ１１は、当該操作信号Ｓopの内容に応じて上記データの生成処理等を実行する。
【００４９】
また、地図データ更新装置ＰＣ自体の稼働状態は、ＣＰＵ１１から出力される表示信号Ｓdpとしてディスプレイ１５に出力され、当該ディスプレイ１５において予め設定された表示形式で表示される。
【００５０】
更に、上記ＣＰＵ１１の動作に必要な種々のデータは、メモリ信号Ｓmとしてメモリ１２に出力され、当該メモリ１２において揮発的に又は不揮発的に記憶され、更に必要に応じて再度メモリ信号Ｓmとして読み出される。
【００５１】
次に、上記地図データ更新装置ＰＣにおいて実行される、その前処理としての新たなメッシュＭ及び対応する代表地点Ｘの生成処理を含む（サーバ装置ＳＶ内の）地図データの更新処理について、具体的に図５を用いて説明する。
【００５２】
地図データ更新装置ＰＣにおいては、上記サーバ装置ＳＶ内の地図データの更新処理に際し、その前処理として、新たな地図データが取得された場合にその地図データに対応する新たなメッシュＭ並びに代表地点Ｘの新たな決定処理（すなわち、メッシュＭ並びに代表地点Ｘのバージョンアップ処理）を行う。
【００５３】
すなわち、図５に示すように、当該前処理を含む地図データの更新処理としては、外部から最新の地図データが取得されると（ステップＳ１）、当該取得された地図データ自体について、例えば、その地図データが相当する地図の縮尺、道路密集度又は交通量等に基づいて上記メッシュＭとしての分割数をＭnと決定し（ステップＳ２）、更にその決めた分割数で新しい地図データを分割して上記メッシュＭを生成する（ステップＳ３）。
【００５４】
次に、当該生成されたメッシュＭの夫々につき、上述したように、各メッシュＭ内において最も交通量の多い交差点又はその中心に最も近い道路上の地点或いはその中にある高速道路の入口のいずれかをもって代表地点Ｘを決定し、その座標（緯度情報及び経度情報等）を代表地点情報１Ｂとして算出する（ステップＳ４）。なおこのとき、当該新たな代表地点Ｘに相当するバージョン情報も当該新たな代表地点情報１Ｂ内に含まれることとなる。
【００５５】
更に、上記代表地点間経路情報１Ｃを新たな地図データ（代表地点Ｘ）について生成すべく、出発地点となる代表地点Ｘを含むメッシュＭのメッシュ番号を示すパラメータｉ並びに目的地点となる代表地点Ｘを含むメッシュＭのメッシュ番号を示すパラメータｊを夫々初期化する（ステップＳ５）。
【００５６】
そして、その時のパラメータｉの値をメッシュ番号とする、メッシュＭ内の代表地点Ｘを出発代表地点Ｓとし（ステップＳ６）、更にその時のパラメータｊの値をメッシュ番号とする、メッシュＭ内の代表地点Ｘを目的代表地点Ｇとし（ステップＳ７）、当該出発代表地点Ｓから目的代表地点Ｇまでの経路を新たな地図データ（道路データ）を用いて探索する（ステップＳ８）。このとき、当該経路としては、代表的な経路を一つ探索してもよいし、異なる条件で複数探索してもよい。
【００５７】
次に、その探索した結果としての経路を用いた場合の移動コストＲを算出し、当該経路上にある道路を識別する道路識別情報と共に、その時のパラメータｉの値をｘ軸の値としその時のパラメータｊの値をｙ軸の値とするマトリックスＭＴＸ（当該マトリックスＭＴＸ自体はＨＤＤ１０内に記憶されている）内の座標ＭＴＸ（ｉ、ｊ）に記憶させる。
【００５８】
なお、当該移動コストＲについて詳細には、後述する第２実施形態において説明する。また、本第１実施形態に係る経路探索処理では、当該移動コストＲ自体は用いない。
【００５９】
そして、パラメータｊの値を「１」だけインクリメントし（ステップＳ１０）、更に、そのインクリメント後のパラメータｊの値がメッシュＭの番号の最大値Ｍnとなったか否か、すなわち、そのときに出発代表地点Ｓとなっている代表地点Ｘを除く他の全ての代表地点Ｘを目的代表地点Ｇとして経路探索をし終わったか否かを確認する（ステップＳ１１）。
【００６０】
そして、未だパラメータｊの値がメッシュＭの番号の最大値Ｍnとなっていない場合は（ステップＳ１１；ＮＯ）、そのときに出発代表地点Ｓとなっている代表地点Ｘについて未だ経路を探索していない他の代表地点Ｘ（目的代表地点Ｇ）があるとして、上記ステップＳ７に戻って以降の処理を当該経路未探索の目的代表地点Ｇに対して実行する。一方、パラメータｊの値がメッシュＭの番号の最大値Ｍnとなったときは（ステップＳ１１；ＹＥＳ）、次に、パラメータiの値を「１」だけインクリメントし（ステップＳ１２）、更に、そのインクリメント後のパラメータiの値がメッシュＭの番号の最大値Ｍnとなったか否か、すなわち、全ての代表地点Ｘを出発代表地点Ｓとして経路探索をし終わったか否かを確認する（ステップＳ１３）。
【００６１】
そして、未だパラメータｉの値がメッシュＭの番号の最大値Ｍnとなっていない場合は（ステップＳ１３；ＮＯ）、新たな出発代表地点Ｓとなるべき他の代表地点Ｘがあるとして、上記ステップＳ６に戻って以降の処理を当該新たな出発代表地点Ｓに対して実行する。一方、パラメータｉの値がメッシュＭの番号の最大値Ｍnとなったときは（ステップＳ１３；ＹＥＳ）、全ての代表地点Ｘ間についての網羅的な経路探索が終了したこととなるので、前処理としての代表地点間経路情報１Ｃ（上記移動コストＲを含む）の生成を終了する。
【００６２】
その後、上記新しい道路データ１Ａ、新しい代表地点情報１Ｂ及び新しい代表地点間経路情報１Ｃに加えて、当該代表地点間経路情報１Ｃにおいて更新対象となる道路データを示す識別情報又はポインタ情報を上記地図更新データＳupdateとしてサーバ装置ＳＶに出力する（ステップＳ１４）。
【００６３】
これにより、上記サーバ装置ＳＶは、取得した地図更新データＳupdateを用いてデータベース１内の古い道路データ１Ａ、代表地点情報１Ｂ及び代表地点間経路情報１Ｃを更新することとなる。
【００６４】
最後に、上記更新されたデータベース１を含むサーバ装置ＳＶと、カーナビゲーションシステムＮＶのいずれかと、を用いた第１実施形態に係る経路探索処理について説明する。
【００６５】
先ず、当該カーナビゲーションシステムＮＶ自体の構成について説明する。
【００６６】
図６に示すように、一つのカーナビゲーションシステムＮＶは、ハードディスクを含むＨＤＤ（Hard Disc Drive）２０と、代表地点設定手段、更新手段及び探索手段としてのナビゲーション処理部２１と、メモリ２２と、操作ボタン又はリモートコントローラ等を含む入力部２５と、液晶ディスプレイ等からなるディスプレイ２６と、サーバ装置ＳＶとナビゲーション処理部２１とを接続する端末装置送信手段としてのインターフェース２３と、航法衛星からの航法電波を受信した現在位置を検出するＧＰＳ（Global Positioning System）センサや、自立的に現在位置を検出する距離センサ及び加速度センサを含むセンサ部２４と、により構成されている。
【００６７】
このとき、ＨＤＤ１０内にはサーバ装置ＳＶから送信されて来る後述の更新道路データを用いて更新される経路探索用の道路データ２０Ａ（上記道路データ１Ａと同様のメッシュＭに分割されている）が、代表地点情報２０Ｂと共に蓄積記憶される。
【００６８】
ここで、当該道路データ２０Ａ自体としては、上記道路データ１Ａと同様に、道路上の地点を示すノードを示すノード情報と、当該ノード間を連結するリンクを示すリンク情報と、の組み合わせから構成されており、更に道路データ１Ａと同様メッシュＭを単位としてＨＤＤ１０内に蓄積されている。
【００６９】
また、代表地点情報２０Ｂ自体としては、上記代表地点情報１Ｂと同様に、対応する代表地点Ｘを識別するための代表地点識別情報、当該代表地点Ｘの地図データ更新におけるバージョン情報並びに当該代表地点Ｘの位置自体を示す緯度情報、経度情報及び高度情報等が含まれている。
【００７０】
このとき、カーナビゲーションシステムＮＶ内の道路データ２０Ａ及び代表地点情報２０Ｂは、サーバ装置ＳＶ内のデータベース１に蓄積されている全国版の道路データ１Ａ及び代表地点情報１Ｂとは異なり、当該カーナビゲーションシステムＮＶにおいて実際に行なわれる経路探索処理に供される当該道路データ２０Ａ及び代表地点情報２０Ｂのみが蓄積記憶されている。
【００７１】
一方、インターフェース２３は、上記カーナビ信号Ｓnvに対して予め設定されたい入出力インターフェース処理を実行する。そして、上記サーバ信号Ｓnvとしてサーバ装置ＳＶから上記更新道路データ等が出力されて来ると、これをインターフェース信号Ｓifに変換してＣＰＵ２１に出力すると共に、サーバ装置ＳＶに送信すべきデータが当該インターフェース信号ＳifとしてＣＰＵ２１から出力されて来ると、これをカーナビ信号Ｓnvに変換してサーバ装置ＳＶに出力する。
【００７２】
他方、センサ部２４は、上記航法電波を用いて又は自立的に現在位置及び速度並びに移動方向等を検出し、その検出内容を示すセンサ信号Ｓcを生成してナビゲーション処理部２１に出力する。
【００７３】
そして、ナビゲーション処理部２１は、ＨＤＤ２０内の道路データ等を用いて後述する第１実施形態に係る経路探索処理を含む案内処理を実行する。
【００７４】
このとき、当該案内処理時においてナビゲーション処理部２１を動作させるために必要な指示は、入力部２５を用いてその操作者により実行され、当該実行された指示操作に対応する操作信号Ｓopとしてナビゲーション処理部２１に送信される。これにより、当該ナビゲーション処理部２１は、当該操作信号Ｓopの内容に応じて上記案内処理等を実行する。
【００７５】
また、カーナビゲーションシステムＮＶ自体の稼働状態は、ナビゲーション処理部２１から出力される表示信号Ｓdpとしてディスプレイ２６に出力され、当該ディスプレイ２６において予め設定された表示形式で表示される。
【００７６】
更に、上記ナビゲーション処理部２１の動作に必要な種々のデータは、メモリ信号Ｓmとしてメモリ２２に出力され、当該メモリ２２において揮発的に又は不揮発的に記憶され、更に必要に応じて再度メモリ信号Ｓmとして読み出される。
【００７７】
次に、上述した構成を備えるカーナビゲーションシステムＮＶとサーバ装置ＳＶとの連携により実行される、第１実施形態に係る経路探索処理について、図７を用いて説明する。
【００７８】
図７に示すように、当該経路探索処理においては、先ず、カーナビゲーションシステムＮＶにおいて、自らが移動する際の出発地点及び目的地点が設定されると（ステップＳ２０）、当該設定された出発地点が含まれているメッシュＭを代表する出発代表地点と、当該設定された目的地点が含まれているメッシュＭを代表する目的代表地点と、が代表地点情報２０Ｂ内において検索される（ステップＳ２１）。
【００７９】
次に、当該検索された出発代表地点及び目的代表地点夫々に相当する代表地点情報２０ＢがネットワークＮＴを介してサーバ装置ＳＶに送信される（ステップＳ２３）。
【００８０】
次に、サーバ装置ＳＶでは、当該送信されて来た出発代表地点及び目的代表地点夫々に相当する代表地点情報２０Ｂに基づき、その代表地点情報２０Ｂに含まれている出発代表地点及び目的代表地点夫々に相当してサーバ装置ＳＶ内に蓄積されている代表地点に相当する代表地点情報１Ｂを、サーバ装置ＳＶ内において確定する（ステップＳ２４）。
【００８１】
そして、カーナビゲーションシステムＮＶから送信されて来た（ステップＳ２３）代表地点情報２０Ｂに含まれる各代表地点Ｘ（具体的には出発代表地点及び目的代表地点の夫々）のバージョンと、サーバ装置ＳＶにおいて確定（ステップＳ２４）された代表地点Ｘのバージョンと、を比較し（ステップＳ２５、Ｓ２６）、サーバ装置ＳＶにおいて確定された（出発代表地点及び目的代表地点に相当する）代表地点Ｘの方が新しく更新されたものであるときは（ステップＳ２６；ＹＥＳ）、その確定された代表地点Ｘ間の経路に相当する経路情報（当該経路に含まれる道路識別情報等を含む道路データ１Ａ）を上記データベース１内から抽出し、当該カーナビゲーションシステムＮＶに送信する（ステップＳ２８）。
【００８２】
これにより、当該新しい経路情報が送信されたカーナビゲーションシステムＮＶでは、当該送信されて来た経路情報に含まれる道路データ１Ａを用いてＨＤＤ２０内の道路データ２０Ａを更新すると共に（ステップＳ２９）、当該更新後の道路データ２０Ａを用いて元の（ステップＳ２０）出発地点から目的地点までの経路を探索し（ステップＳ３０）、当該探索結果を用いて以後の案内処理を実行する。
【００８３】
一方、ステップＳ２６の判定において、カーナビゲーションシステムＮＶから送信されて来た代表地点情報２０Ｂに含まれる代表地点Ｘのバージョンと、サーバ装置ＳＶにおいて確定された代表地点Ｘのバージョンと、が同一であるときは（ステップＳ２６；ＮＯ）、カーナビゲーションシステムＮＶにおいて探索された経路上の道路データは更新されていないものとして、元の（ステップＳ２０）出発地点から目的地点までの経路を、その時にカーナビゲーションシステムＮＶ内に蓄積されている道路データ２０Ａを用いて探索して（ステップＳ２７）以後の案内処理を実行する。
【００８４】
以上夫々説明したように、第１実施形態に係る経路探索システムＳの動作によれば、全ての代表地点Ｘ間についての代表地点間経路情報１Ｃを予め網羅的にサーバ装置ＳＶ内に蓄積しているので、カーナビゲーションシステムＮＶにおいて必要な経路を確定する際に、代表地点Ｘ間の経路を確定するまでのサーバ装置ＳＶにおける負荷を大幅に軽減することができる。
【００８５】
また、カーナビゲーションシステムＮＶにおいて設定された出発代表地点及び目的代表地点夫々のバージョンと、サーバ装置ＳＶ内における対応する代表地点のバージョンと、を比較して道路データ２０Ａを更新するか否かを判断するので、カーナビゲーションシステムＮＶの移動に必要な経路に無関係の道路データ２０Ａが更新されることがないことから、カーナビゲーションシステムＮＶの移動に必要な最低限の更新すべき道路データ２０Ａの範囲を的確に確定して迅速に当該道路データ２０Ａを更新することができる。
【００８６】
従って、カーナビゲーションシステムＮＶにおける経路探索に必要な道路データ２０Ａの更新範囲を的確に判断して効率的に当該更新処理を実行することができる。
【００８７】
また、出発代表地点と目的代表地点との間の経路が含まれるメッシュＭを代表する代表地点Ｘの少なくともいずれか一つが、カーナビゲーションシステムＮＶ上で先に探索した経路が含まれるメッシュＭを代表する代表地点Ｘの少なくともいずれか一つに対して更新された当該いずれか一つであるとき、道路データ２０Ａを更新すべきであると判断するので、更新された代表地点Ｘがある場合に限って必要最小限且つ最新の更新道路データをもって道路データ２０Ａを効率的に更新することができる。
【００８８】
更に、代表地点Ｘが代表するメッシュＭが、サーバ装置ＳＶ内の道路データ１Aに対応する地図の縮尺、道路密集度又は交通量の少なくともいずれか一つに基づいて予め区分されたメッシュＭであるので、経路案内処理の際に実際に問題となる要素に基づいてメッシュＭが区分されていることから、より的確な経路探索に資することができる。
【００８９】
更にまた、代表地点Ｘを、対応するメッシュＭ内において最も交通量の多い交差点とした場合には、経路案内処理の際に実際に問題となる交通量に基づいて代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【００９０】
また、代表地点Ｘを、対応するメッシュＭの中心に最も近い道路地点とした場合には、経路案内処理の際に実際に問題となるメッシュＭ内の中心地点として代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【００９１】
更にまた、代表地点Ｘを、対応するメッシュＭ内にある高速道路の入口とした場合には、長距離移動の際の経路案内処理の際に実際に問題となる高禄道路に基づいて代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【００９２】
また、第１実施形態に係る地図データ更新装置ＰＣによれば、道路データ１Ａの更新に合わせて代表地点情報１Ｂと代表地点間経路情報１Ｃとが更新されるので、常に最新の各情報をサーバ装置ＳＶ内に蓄積して経路探索に供させることができる。
【００９３】
（II）第２実施形態
次に、本願に係る他の実施形態である第２実施形態について、図８を用いて説明する。なお、図８は第２実施形態に係る経路探索処理を示すフローチャートである。
【００９４】
また、第２実施形態に係る経路探索処理を実行する経路探索システムの構成は、基本的に第１実施形態に係る経路探索システムＳの構成と同様であるので、以下の第２実施形態においては同様の部材番号を用いて細部の説明は省略する。更に、図８に示すフローチャートにおいて、上述した第１実施形態に係る経路探索処理（図７参照）と同一の処理については同一のステップ番号を付して細部の説明は省略する。
【００９５】
上述した第１実施形態においては、経路上の出発代表地点及び目的代表地点がサーバ装置ＳＶにおいて更新されている場合にのみカーナビゲーションシステムＮＶ内の道路データ２０Ａを更新する場合について説明したが、以下に説明する第２実施形態では、当該各代表地点Ｘのバージョンではなく、探索された経路上を移動する際の上記移動コストＲ（図５ステップＳ９参照）を考慮して道路データ２０Ａの更新の可否を判断する。
【００９６】
ここで、当該移動コストＲとは、当該移動に伴って発生する負荷を意味するものであり、より具体的には、例えば、当該移動に必要な移動時間、当該移動における実際の移動距離、又は当該移動に必要な料金等が該当する。
【００９７】
また、第２実施形態に係るサーバ装置ＳＶ内の代表地点間経路情報１Ｃとしては、当該各代表地点間に係る上記移動コストＲ（すなわち、当該代表地点間に係る移動時間、移動距離又は必要料金等）が蓄積されている。
【００９８】
図８に示すように、第２実施形態に係る経路探索処理においては、先ず、カーナビゲーションシステムＮＶにおいて、図７に示すステップＳ２０及びＳ２１と同様の処理を事項する。
【００９９】
次に、当該検索された出発代表地点から当該検索された目的代表地点までの経路が、カーナビゲーションシステムＮＶにおいて探索され、更に当該探索された経路上を移動する際に必要な上記移動コストＲが算出される（ステップＳ４０）。
【０１００】
そして、当該探索された経路内にある上記出発代表地点及び目的代表地点を夫々示す代表地点情報２０Ｂと、上記算出された移動コストＲを示す情報と、がネットワークＮＴを介してサーバ装置ＳＶに送信される（ステップＳ４１）。
【０１０１】
次に、サーバ装置ＳＶでは、当該送信されて来た代表地点情報２０Ｂに基づき、その代表地点情報２０Ｂに含まれている出発代表地点及び目的代表地点夫々に相当するサーバ装置ＳＶに蓄積されている代表地点に相当する代表地点情報１Ｂを確定すると共に、当該各確定された出発代表地点及び目的代表地点間に相当する上記移動コストＲを、第２実施形態係る代表地点間経路情報１Ｃ内から抽出して確定する（ステップＳ４２）。
【０１０２】
なお、当該ステップＳ４２の処理について、当該第２実施形態に係る代表地点間経路情報１Ｃは、地図データ更新装置ＰＣによりサーバ装置ＳＶ内の代表地点間経路情報１Ｃを更新する際に、当該更新される代表地点間経路情報１Ｃに対応する移動コストＲが併せて更新されることとなる。
【０１０３】
更に、例えば重要な道路データ２０Ａの更新であって、移動コストＲの如何に拘わらず更新すべき道路データ２０Ａがある場合等においては、上記ステップＳ４２の処理に用いられる移動コストＲを、意図的に良好な移動コストＲとなるように上記代表地点間経路情報１Ｃの更新時に更新しておくように構成することも可能である。
【０１０４】
そして、カーナビゲーションシステムＮＶから送信されて来た（ステップＳ４１）移動コストＲと、サーバ装置ＳＶにおいて確定された（ステップＳ４２）移動コストＲと、を比較し（ステップＳ４３）、サーバ装置ＳＶにおいて確定された移動コストＲの方がカーナビゲーションシステムＮＶから送信されて来た移動コストＲよりも良好である（移動コストＲとして低い）ときは（ステップＳ４３；サーバの方が良好）、上記ステップＳ４２の処理において確定された出発代表地点及び目的代表地点間の経路に相当する経路情報（当該経路に含まれる道路識別情報等を含む道路データ１Ａ）を上記データベース１内から抽出し、当該カーナビゲーションシステムＮＶに送信する（ステップＳ２８）。
【０１０５】
これにより、図７に示すステップＳ２９及びＳ３０と同様の処理を行ない、当該再探索結果を用いて以後の案内処理を実行する。
【０１０６】
一方、ステップＳ４３の判定において、カーナビゲーションシステムＮＶから送信されて来た移動コストＲの方がサーバ装置ＳＶにおいて確定された移動コストＲよりも良好であるときは（ステップＳ４３；ナビの方が良好）、元の（ステップＳ２０）出発地点から目的地点までの経路を、その時にカーナビゲーションシステムＮＶ内に蓄積されている道路データ２０Ａを用いて探索して（ステップＳ２７）以後の案内処理を実行する。
【０１０７】
以上夫々説明したように、第２実施形態に係る経路探索システムの動作によれば、第１実施形態に係る経路探索システムＳの動作と同様に、全ての代表地点Ｘ間についての代表地点間経路情報１Ｃを予め網羅的にサーバ装置ＳＶ内に蓄積しているので、カーナビゲーションシステムＮＶにおいて必要な経路を確定する際に、代表地点Ｘ間の経路を確定するまでのサーバ装置ＳＶにおける負荷を大幅に軽減することができる。
【０１０８】
また、カーナビゲーションシステムＮＶにおいて設定された出発代表地点及び目的代表地点間の移動コストＲと、サーバ装置ＳＶにおいて探索した対応する代表地点Ｘ間の移動コストＲと、を比較して道路データ２０Ａを更新するか否かを判断するので、カーナビゲーションシステムＮＶの移動に必要な経路に無関係の道路データ２０Ａが更新されることがないことから、カーナビゲーションシステムＮＶの移動に必要な最低限の更新すべき道路データ２０Ａの範囲を的確に確定して迅速に当該道路データ２０Ａを更新することができる。
【０１０９】
従って、カーナビゲーションシステムＮＶにおける経路探索に必要な道路データ２０Ａの更新範囲を的確に判断して効率的に当該更新処理を実行することができる。
【０１１０】
更に、代表地点Ｘが代表するメッシュＭが、サーバ装置ＳＶ内の道路データ１Aに対応する地図の縮尺、道路密集度又は交通量の少なくともいずれか一つに基づいて予め区分されたメッシュＭであるので、経路案内処理の際に実際に問題となる要素に基づいてメッシュＭが区分されていることから、より的確な経路探索に資することができる。
【０１１１】
更にまた、代表地点Ｘを、対応するメッシュＭ内において最も交通量の多い交差点とした場合には、経路案内処理の際に実際に問題となる交通量に基づいて代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【０１１２】
また、代表地点Ｘを、対応するメッシュＭの中心に最も近い道路地点とした場合には、経路案内処理の際に実際に問題となるメッシュＭ内の中心地点として代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【０１１３】
更にまた、代表地点Ｘを、対応するメッシュＭ内にある高速道路の入口とした場合には、長距離移動の際の経路案内処理の際に実際に問題となる高禄道路に基づいて代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【０１１４】
これらに加えて、サーバ装置ＳＶにおいて探索された経路を移動する際の移動態様の方が、カーナビゲーションシステムＮＶ上で先に探索した経路を当該カーナビゲーションシステムＮＶが移動する際の移動態様よりも有利であるとき、道路データ２０Ａを更新すべきであると判断するので、移動しようとするカーナビゲーションシステムＮＶにとって真に必要な場合にのみ道路データ２０Ａを効率的に更新することができる。
【０１１５】
更に、移動コストＲとして移動時間を採用する場合には、サーバ装置ＳＶにおいて探索された経路を移動する際の移動時間の方が、カーナビゲーションシステムＮＶ上で先に探索した経路を当該カーナビゲーションシステムＮＶが移動する際の移動時間よりも短いとき、道路データ２０Ａを更新すべきであると判断するので、移動時間を基準として、移動しようとするカーナビゲーションシステムＮＶにとって真に必要な場合にのみ道路データ２０Ａを効率的に更新することができる。
【０１１６】
更にまた、移動コストＲとして移動距離を採用する場合には、サーバ装置ＳＶにおいて探索された経路を移動する際の移動距離の方が、カーナビゲーションシステムＮＶ上で先に探索した経路を当該カーナビゲーションシステムＮＶが移動する際の移動距離よりも短いとき、道路データ２０Ａを更新すべきであると判断するので、移動距離を基準として、移動しようとするカーナビゲーションシステムＮＶにとって真に必要な場合にのみ道路データ２０Ａを効率的に更新することができる。
【０１１７】
また、移動コストＲとして移動のための料金を採用する場合には、サーバ装置ＳＶにおいて探索された経路を移動する際に必要な料金の方が、カーナビゲーションシステムＮＶ上で先に探索した経路を当該カーナビゲーションシステムＮＶが移動する際に必要な料金よりも短いと判断されたとき、道路データ２０Ａを更新すべきであると判断するので、移動のための料金を基準として、移動しようとするカーナビゲーションシステムＮＶにとって真に必要な場合にのみ道路データ２０Ａを効率的に更新することができる。
【０１１８】
なお、上述した各実施形態においては、カーナビゲーションシステムＮＶにおいて経路探索処理を実行する場合について説明したが、これ以外に、例えば携帯型の情報端末装置や携帯型の電話機において経路探索処理を実行する場合について本願を適用することも可能である。
【０１１９】
更に、図５、図７又は図８に夫々示すフローチャートに対応するプログラムを、フレキシブルディスク又はハードディスク等の情報記録媒体に記録しておき、又はインターネット等を介して取得して記録しておき、これらを汎用のコンピュータで読み出して実行することにより、当該コンピュータを各実施形態に係る地図データ更新装置ＰＣ内のＣＰＵ１１（図５に示すフローチャートに対応するプログラムの場合）又はサーバ装置ＳＶ或いはカーナビゲーションシステムＮＶ内のナビゲーション処理部２１（図７又は図８に示すフローチャートに対応するプログラムの場合）として活用することも可能である。
【図面の簡単な説明】
【０１２０】
【図１】第１実施形態に係る経路探索システムの概要構成を示すブロック図である。
【図２】第１実施形態に係る経路探索システムに含まれる各装置の細部構成を示すブロック図であり、（ａ）は第１実施形態に係るサーバ装置の細部構成を示すブロック図であり、（ｂ）は第１実施形態に係る地図データ更新装置の細部構成を示すブロック図である。
【図３】第１実施形態に係る道路データの構成を例示する図である。
【図４】第１実施形態に係る代表地点の状態を例示する図である。
【図５】第１実施形態に係るサーバ装置における地図データ等の更新を示すフローチャートである。
【図６】第１実施形態に係るカーナビゲーションシステムの概要構成を示すブロック図である。
【図７】第１実施形態に係る経路探索処理を示すフローチャートである。
【図８】第２実施形態に係る経路探索処理を示すフローチャートである。
【符号の説明】
【０１２１】
１ データベース
１Ａ、２０Ａ 道路データ
１Ｂ、２０Ｂ 代表地点情報
１Ｃ 代表地点間経路情報
２、１１ ＣＰＵ
３、１２、２２ メモリ
４、１３、２３ インターフェース
５、１４、２５ 入力部
６、１５、２６ ディスプレイ
１０、２０ ＨＤＤ
２１ ナビゲーション処理部
２４ センサ部
Ｓ 経路探索システム
ＳＶ サーバ装置
ＰＣ 地図データ更新装置
ＮＶ カーナビゲーションシステム
ＮＴ ネットワーク
Ｍ１、Ｍ２、Ｍ３、Ｍ４、Ｍ５、ＭＬ、ＭＬ＋１、ＭＬ＋２、ＭＬ＋３、Ｍn、Ｍn-1 メッシュ
ＸＬ、ＸＬ＋１、ＸＬ＋２、ＸＬ＋３ 代表地点
【技術分野】
【０００１】
本願は、経路探索システム、道路データ生成装置、サーバ装置、端末装置、経路探索用データ、サーバ装置用プログラム及び端末装置用プログラム並び経路探索方法の技術分野に属し、より詳細には、サーバ装置に蓄積されている最新の道路情報を用いて端末装置上の道路情報を更新しつつ、当該端末装置において経路探索を行う経路探索システム及び経路探索方法並びに当該経路探索用データ、当該経路探索用データ自体を生成する道路データ生成装置、当該サーバ装置及び当該端末装置、並びに当該サーバ装置用プログラム及び当該端末装置用プログラムの技術分野に属する。
【背景技術】
【０００２】
近年、日本全国の道路に相当する道路情報を最新に更新しつつ蓄積するサーバ装置と、当該サーバ装置とネットワーク等を介して接続された端末装置等を含み、当該端末装置の移動に適した経路としての道路をサーバ装置と連携して探索する経路探索システムが普及しつつある。ここで、当該端末装置の具体例としては、例えばいわゆるカーナビゲーション装置や、携帯型電話機或いは携帯型情報端末装置に付加された個別機能としてのナビゲーション装置等が挙げられる。
【０００３】
ここで、従来の上記経路探索システムでは、端末装置の移動経路を当該端末装置において探索する場合、サーバ装置に蓄積されている最新の道路情報及び関連する地図情報を取得して端末装置内の道路情報を更新した上で、その更新された道路情報を用いて探索処理を実行することが望まれる。
【０００４】
このとき、当該端末装置上の道路情報をサーバ装置上の道路情報を用いて更新するための技術としては、例えば下記特許文献１に記載されているように、サーバ装置内に蓄積されている道路情報のバージョンと、端末装置内に蓄積されている道路情報のバージョンとを比較し、サーバ装置内に蓄積されているバージョン情報の方が新しい場合にのみ、その新しいバージョンの道路情報を用いて端末装置内の道路情報を更新する方法がある。
【０００５】
一方、当該更新を行う際、地図上のどの地域まで道路情報を更新するかの地域的な判断に当たっては、サーバ装置と端末装置間における通信量やそれに伴って発生する通信料金等を考慮すると、なるべく少ない通信量で必要な地域だけの更新処理が完了することが望ましい。
【０００６】
そこで、従来では、当該更新処理を実行する際における更新対象地域の判断に当たっては、例えば都道府県や市町村等の行政区分を基準とした範囲で、探索対象の道路が含まれている行政区分に相当する道路情報を更新することが為されていた。
【特許文献１】特開２００６−６５２４６公報 （第２図等）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した従来の更新対象地域の確定方法によると、行政区分を単位として更新対象地域を確定していたため、結果として、更新対象となった行政区分と更新対象とならなかった行政区分とに跨って敷設されている道路については、当該行政区分の境界線上において当該更新の前後において不整合（道路としての連続性が乱される食い違い）が発生する。
【０００８】
ここで、例えば経路探索処理において種々の異なる条件によって経路が探索される可能性（換言すれば、当該条件に対応した種々の道路が広範囲に探索される可能性）を考慮すると、上述した不整合は存在しない方が望ましい。このため、一つの行政区分について道路情報を更新した結果、それに隣接する行政区分との間で上述した不整合が発生した場合には、当該隣接する行政区分の道路情報まで更新する必要があることになり、このことが行政区分毎に連鎖的に繰り返されることで、結果的に更新対象地域が無限に広がってしまう可能性があるという問題点があった。
【０００９】
そしてこのことは、上記少ない通信量で更新を行うことが必要となる点を考慮した場合、是非とも解決すべき問題点となる。
【００１０】
そこで、本願は上記の各問題点に鑑みて為されたもので、その課題の一例は、更新すべき道路情報についての地域的な範囲が無限大に広がることを防止し、更新が必要な道路情報を的確に更新して経路探索をすることが可能な経路探索システム及び経路探索方法並びに当該経路探索用データ、当該経路探索用データ自体を生成する道路データ生成装置、当該サーバ装置及び当該端末装置、並びに当該サーバ装置用プログラム及び当該端末装置用プログラムを提供することにある。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、請求項１に記載の発明は、サーバ道路情報を最新に更新しつつ蓄積するサーバ装置と、当該サーバ装置に接続され且つ端末道路情報を蓄積して案内処理を行うカーナビゲーションシステム等の端末装置と、を含むナビゲーションシステムに含まれ、前記端末装置が移動する経路を探索する経路探索システムにおいて、前記サーバ装置は、道路が敷設され且つ予め区分された地域を代表するものとして当該地域毎に予め設定されている代表地点であって最新の前記サーバ道路情報に対応する代表地点を示す代表地点情報と、全ての当該代表地点情報相互間を移動する際に用いるべき前記道路を示す代表地点間経路情報と、を前記最新のサーバ道路情報と共に蓄積するデータベース等の蓄積手段を備え、前記端末装置は、前記端末装置が移動する前記経路の出発地点に対応する出発代表地点と、当該経路の目的地点に対応する目的代表地点と、を設定するナビゲーション処理部等の代表地点設定手段と、前記設定された出発代表地点から前記設定された目的代表地点までの代表地点間経路に対応する経路情報を前記サーバ装置に送信するインターフェース等の端末装置送信手段と、前記サーバ装置から前記端末道路情報の更新に用いられるべき更新道路情報が送信されて来たとき、当該送信されて来た更新道路情報を用いて前記蓄積されている端末道路情報を更新するナビゲーション処理部等の更新手段と、前記更新後の端末道路情報を用いて前記出発地点から前記目的地点までの経路を探索するナビゲーション処理部等の探索手段と、を備え、更に前記サーバ装置は、前記送信されて来た経路情報に対応する前記出発代表地点から前記送信されて来た経路情報に対応する前記目的代表地点まで移動する際に用いるべき前記道路を示す前記代表地点間経路情報を、前記蓄積手段から抽出するＣＰＵ等の抽出手段と、前記抽出された代表地点間経路情報と、前記送信されて来た経路情報と、を比較し、前記端末道路情報を更新すべきか否かを判断するＣＰＵ等の判断手段と、前記端末道路情報を更新すべきであると判断されたとき、当該更新に用いられるべき前記更新道路情報を前記端末装置に送信するインターフェース等のサーバ装置送信手段と、を備える。
【００１２】
上記の課題を解決するために、請求項１１に記載の発明は、請求項７から１０のいずれか一項に記載の経路探索システムに含まれる前記サーバ装置に蓄積される前記サーバ道路情報と、前記代表地点情報と、前記代表地点間経路情報と、を夫々生成する道路データ生成装置であって、予め設定された期間毎に前記サーバ道路情報を最新に更新するＣＰＵ等のサーバ道路情報更新手段と、前記更新されたサーバ道路情報に対応して前記代表地点情報を更新するＣＰＵ等の代表地点情報更新手段と、前記更新されたサーバ道路情報に対応して前記代表地点間経路情報を更新するＣＰＵ等の代表地点間経路情報更新手段と、を備える。
【００１３】
上記の課題を解決するために、請求項１２に記載の発明は、請求項１から１１のいずれか一項に記載のサーバ装置内の前記蓄積手段に蓄積されている経路探索用データであって、前記代表地点間経路情報の生成に用いられ且つ前記更新道路情報を抽出可能に構成された前記サーバ道路情報と、最新の前記サーバ道路情報に対応した前記地域を示す地域情報と、当該最新の地域毎に設定された前記代表地点を示す前記代表地点情報と、当該最新の代表地点情報に基づいて網羅的に探索された代表地点間経路としての前記道路を示す前記代表地点間経路情報と、を含むように構成されている。
【００１４】
上記の課題を解決するために、請求項１３に記載の発明は、請求項１から１０に記載の経路探索システムに含まれる前記サーバ装置であって、前記蓄積手段と、前記抽出手段と、前記判断手段と、前記サーバ装置送信手段と、を備える。
【００１５】
上記の課題を解決するために、請求項１４に記載の発明は、請求項１から１０に記載の経路探索システムに含まれる前記端末装置であって、前記代表地点設定手段と、前記端末装置送信手段と、前記更新手段と、前記探索手段と、を備える。
【００１６】
上記の課題を解決するために、請求項１５に記載の発明は、請求項１から１０に記載の経路探索システムに含まれ且つ前記蓄積手段を備える前記サーバ装置に含まれるコンピュータを、前記抽出手段、前記判断手段、及び、前記サーバ装置送信手段、として機能させる。
【００１７】
上記の課題を解決するために、請求項１６に記載の発明は、請求項１から１０に記載の経路探索システムに含まれる前記端末装置に含まれるコンピュータを、前記代表地点設定手段、前記端末装置送信手段、前記更新手段、及び、前記探索手段、として機能させる。
【００１８】
上記の課題を解決するために、請求項１７に記載の発明は、サーバ道路情報を最新に更新しつつ蓄積するサーバ装置と、当該サーバ装置に接続され且つ端末道路情報を蓄積して案内処理を行うカーナビゲーションシステム等の端末装置と、を含むナビゲーションシステムに含まれる当該端末装置が移動する経路を探索する経路探索方法において、前記サーバ装置は、道路が敷設され且つ予め区分された地域を代表するものとして当該地域毎に予め設定されている代表地点であって最新の前記サーバ道路情報に対応する代表地点を示す代表地点情報と、全ての当該代表地点情報相互間を移動する際に用いるべき前記道路を示す代表地点間経路情報と、を前記最新のサーバ道路情報と共に蓄積する蓄積手段を備えており、前記端末装置が移動する前記経路の出発地点に対応する出発代表地点と、当該経路の目的地点に対応する目的代表地点と、を当該端末装置において設定する代表地点設定工程と、前記設定された出発代表地点から前記設定された目的代表地点までの代表地点間経路に対応する経路情報を当該端末装置から前記サーバ装置に送信する第１送信工程と、前記サーバ装置において、前記送信されて来た経路情報に対応する前記出発代表地点から前記送信されて来た経路情報に対応する前記目的代表地点まで移動する際に用いるべき前記道路を示す前記代表地点間経路情報を、前記蓄積手段から抽出する抽出工程と、前記サーバ装置において、前記抽出された代表地点間経路情報と、前記送信されて来た経路情報と、を比較し、前記端末道路情報を更新すべきか否かを判断する判断工程と、前記判断工程において前記端末道路情報を更新すべきであると判断されたとき、当該更新に用いられるべき更新道路情報を前記サーバ装置から当該端末装置に送信する第２送信工程と、前記更新道路情報が送信されて来た前記端末装置において、当該送信されて来た更新道路情報を用いて前記蓄積されている端末道路情報を更新する更新工程と、前記端末道路情報が更新された前記端末装置において、当該更新後の端末道路情報を用いて前記出発地点から前記目的地点までの経路を探索する探索工程と、を含む。
【発明を実施するための最良の形態】
【００１９】
次に、本願を実施するための最良の形態について、図面に基づいて説明する。なお、以下に説明する実施形態は、経路探索用の道路データを含む地図データを常時最新の状態となるように更新しつつ蓄積するサーバ装置と、当該サーバ装置に蓄積されている最新の道路データを用いて自ら蓄積している道路データを更新しつつ経路探索を行うカーナビゲーションシステムと、を含む経路探索システムに対して本願を適用した場合の実施の形態である。
【００２０】
（Ｉ）第１実施形態
始めに、本願に係る第１実施形態について、図１乃至図７を用いて説明する。なお、図１は第１実施形態に係る経路探索システムの概要構成を示すブロック図であり、図２は当該経路探索システムに含まれる各装置の細部構成を示すブロック図であり、図３は第１実施形態に係る道路データの構成を例示する図であり、図４は第１実施形態に係る代表地点の状態を例示する図であり、図５は第１実施形態に係るサーバ装置における地図データ等の更新を示すフローチャートであり、図６は第１実施形態に係るカーナビゲーションシステムの概要構成を示すブロック図であり、図７は第１実施形態に係る経路探索処理を示すフローチャートである。
【００２１】
図１に示すように、第１実施形態に係る経路探索システムＳは、上記サーバ装置ＳＶと、インターネット等のネットワークＮＴと、複数のカーナビゲーションシステムＮＶと、地図データ更新装置ＰＣと、により構成されている。
【００２２】
このとき、地図データ更新装置ＰＣは、サーバ装置ＳＶ内に蓄積されている上記地図データを最新の状態に更新する際、当該更新のための地図更新データＳupdateを生成し、サーバ装置ＳＶに出力する。
【００２３】
そして、サーバ装置ＳＶは、当該地図更新データＳupdateを用いて上記地図データを最新の状態に更新しつつ、各カーナビゲーションシステムＮＶと別個独立に夫々地図データ等の授受を行ない、後述する第１実施形態に係る経路探索処理を実行する。
【００２４】
このとき、サーバ装置ＳＶから出力される各種データは、サーバ信号ＳsvとしてネットワークＮＴに送信される。そして、当該ネットワークＮＴを介してカーナビ信号Ｓnvとして各カーナビゲーションシステムＮＶに出力される。
【００２５】
これと反対に、カーナビゲーションシステムＮＶから出力されるべき各種データは、カーナビ信号ＳnvとしてネットワークＮＴに送信される。そして、当該ネットワークＮＴを介してサーバ信号Ｓsvとしてサーバ装置ＳＶに出力される。
【００２６】
次に、上記サーバ装置ＳＶの細部構成及び動作について、図２（ａ）並びに図３及び図４を用いて説明する。
【００２７】
図２（ａ）に示すように、サーバ装置ＳＶは、例えばハードディスク等からなる蓄積手段としてのデータベース１と、抽出手段及び判断手段としてのＣＰＵ２と、メモリ３と、キーボード又はマウス等を含む入力部５と、液晶ディスプレイ等からなるディスプレイ６と、ネットワークＮＴ又は地図データ更新装置ＰＣとＣＰＵ２とを接続するサーバ装置送信手段としてのインターフェース４と、により構成されている。
【００２８】
このとき、データベース１内には第１実施形態に係る経路探索用の道路データ１Ａと、後述する代表地点の内容を各代表地点毎に夫々示す代表地点情報１Ｂと、後述する代表地点間経路情報１Ｃと、を含む上記地図データが、上記地図更新データＳupdateを用いて定期的に更新されつつ蓄積記憶されている。
【００２９】
一方、インターフェース４は、上記地図更新データＳupdate又は上記サーバ信号Ｓsvに対して予め設定された入出力インターフェース処理を実行する。そして、上記地図更新データＳupdate又は上記サーバ信号Ｓsvとしてサーバ装置ＳＶに入力されるべきデータをインターフェース信号ＳifとしてＣＰＵ２に出力すると共に、上記サーバ信号Ｓsvとして各カーナビゲーションシステムＮＶに出力すべきデータがインターフェース信号ＳifとしてＣＰＵ２から出力されて来ると、これをサーバ信号Ｓsvに変換してネットワークＮＴに出力する。
【００３０】
そして、ＣＰＵ２は、データベース１内の地図データの更新時においては上記地図更新データＳupdateとして送信されて来る地図データ更新用のデータを用いて当該地図データの更新処理を実行すると共に、当該更新された地図データを用いて後述する第１実施形態に係る経路探索処理を実行する。
【００３１】
このとき、例えば上記地図データの更新時においてＣＰＵ２を動作させるために必要な指示は、入力部５を用いてその操作者により実行され、当該実行された指示操作に対応する操作信号ＳopとしてＣＰＵ２に送信される。これにより、当該ＣＰＵ２は、当該操作信号Ｓopの内容に応じて上記更新のための処理等を実行する。
【００３２】
また、サーバ装置ＳＶ自体の稼働状態は、ＣＰＵ２から出力される表示信号Ｓdpとしてディスプレイ６に出力され、当該ディスプレイ６において予め設定された表示形式で表示される。
【００３３】
更に、上記ＣＰＵ２の動作に必要な種々のデータは、メモリ信号Ｓmとしてメモリ３に出力され、当該メモリ３において揮発的に又は不揮発的に記憶され、更に必要に応じて再度メモリ信号Ｓmとして読み出される。
【００３４】
次に、データベース１内に蓄積されている、第１実施形態に係る上記道路データ１Ａ、代表地点情報１Ｂ及び代表地点間経路情報１Ｃについて、夫々図３及び図４を用いて具体的に説明する。
【００３５】
先ず、第１実施形態に係る経路探索処理用の道路データ１Ａは、具体的には、道路上の地点を示すノードを示すノード情報（当該ノードの位置を示す緯度情報及び経度情報並びに高度情報等を含む）と、当該ノード間を連結するリンクを示すリンク情報（当該リンクに相当する道路を識別するための道路識別情報や、当該リンクに相当する道路の実際の（現実の）長さを示す情報等を含む）と、の組み合わせから構成されている。
【００３６】
そして、当該道路データ１Ａは、例えば図３に例示するように、道路が敷設されている地域的範囲であってメッシュ番号により区分されるメッシュＭ１、Ｍ２、Ｍ３、…、Ｍnを単位としてデータベース１内に蓄積されている。
【００３７】
ここで、当該メッシュＭの決め方については、基本的には、経路探索処理を実行する際の便宜を考慮してその地図データの制作者により任意に決定し得るものであるが、例えば、当該道路データ１Ａに対応する地図の縮尺毎に異なる広さに相当するものとして決定してもよいし、或いは同一縮尺の地図内でも、道路密集度又は交通量等に基づいて異なる広さのメッシュＭを決めることも可能である。
【００３８】
なお、以下に説明する第１実施形態では、当該メッシュＭの例として方形のメッシュＭについて説明しているが、メッシュＭの形状自体については、方形に限らず、任意の多角形として決めることができるのであり、更には、都道府県等の行政区分境界を基準としてメッシュＭを分割することも可能である。
【００３９】
次に、第１実施形態では、上記各メッシュＭ毎に、そのメッシュＭに相当する地域内に敷設されている道路上の地点を代表する代表地点を設定する。すなわち、例えば隣接する県を含めた東京都の例を用いて図４に示すように、各メッシュＭＬ、ＭＬ＋１、ＭＬ＋２、ＭＬ＋３、…の夫々について、一対一の関係となる代表地点ＸＬ、ＸＬ＋１、ＸＬ＋２、ＸＬ＋３、…を各々設定する。
【００４０】
ここで、一つのメッシュＭ内の代表地点Ｘの決定方法としては、これも基本的には経路探索処理を実行する際の便宜を考慮してその地図データの制作者により任意に決定し得るものであるが、例えば、その代表地点Ｘが代表するメッシュＭ内において最も交通量の多い交差点と当該代表地点Ｘとすることもできるし、また、その代表地点Ｘが代表するメッシュＭの中心に最も近い道路上の地点を当該代表地点Ｘとしてもよい。更には、その代表地点Ｘが代表するメッシュＭ内にある高速道路の入口のいずれかを当該代表地点Ｘとしてもよい。
【００４１】
そして、これら代表地点Ｘ夫々を識別するための代表地点識別情報、当該代表地点Ｘ夫々の地図データ更新におけるバージョン情報並びに各代表地点Ｘの位置自体を示す緯度情報、経度情報及び高度情報等が上記代表地点情報１Ｂとしてデータベース１内に蓄積されている。
【００４２】
最後に、第１実施形態に係る経路探索処理用の代表地点間経路情報１Ｃは、一つの代表地点Ｘを出発地点とし、他の全ての代表地点Ｘを夫々目的地点とした経路の各々を示す経路情報を、全ての代表地点Ｘを出発地点とした場合について網羅的に集積した経路情報である。すなわち、全ての縮尺の地図における上記代表地点Ｘにつき、二つの代表地点Ｘ間を移動する際に採用される経路を、全ての二つの代表地点Ｘの組み合わせてについて夫々求めた経路情報である。
【００４３】
次に、上記地図データ更新装置ＰＣの細部構成及び動作について、図２（ｂ）を用いて説明する。
【００４４】
図２（ｂ）に示すように、地図データ更新装置ＰＣは、ハードディスクを含むＨＤＤ（Hard Disc Drive）１０と、サーバ道路情報更新手段、代表地点情報更新手段及び代表地点間経路情報更新手段としてのＣＰＵ１１と、メモリ１２と、キーボード又はマウス等を含む入力部１４と、液晶ディスプレイ等からなるディスプレイ１５と、サーバ装置ＳＶとＣＰＵ１１とを接続するインターフェース１３と、により構成されている。
【００４５】
このとき、ＨＤＤ１０内には外部からインターフェース１３を介して送信されてきた最新の地図データ等が蓄積記憶される。
【００４６】
一方、インターフェース１３は、上記地図更新データＳupdateに対して予め設定された入出力インターフェース処理を実行する。そして、上記地図更新データＳupdateとしてサーバ装置ＳＶに出力すべきデータがインターフェース信号ＳifとしてＣＰＵ１１から出力されて来ると、これを地図更新データＳupdateに変換してサーバ装置ＳＶに出力する。
【００４７】
そして、ＣＰＵ１１は、ＨＤＤ１０内の最新の地図データ等を用いて後述するサーバ装置ＳＶ内の地図データの更新処理に必要なデータを生成する。
【００４８】
このとき、当該データの生成時においてＣＰＵ１１を動作させるために必要な指示は、入力部１４を用いてその操作者により実行され、当該実行された指示操作に対応する操作信号ＳopとしてＣＰＵ１１に送信される。これにより、当該ＣＰＵ１１は、当該操作信号Ｓopの内容に応じて上記データの生成処理等を実行する。
【００４９】
また、地図データ更新装置ＰＣ自体の稼働状態は、ＣＰＵ１１から出力される表示信号Ｓdpとしてディスプレイ１５に出力され、当該ディスプレイ１５において予め設定された表示形式で表示される。
【００５０】
更に、上記ＣＰＵ１１の動作に必要な種々のデータは、メモリ信号Ｓmとしてメモリ１２に出力され、当該メモリ１２において揮発的に又は不揮発的に記憶され、更に必要に応じて再度メモリ信号Ｓmとして読み出される。
【００５１】
次に、上記地図データ更新装置ＰＣにおいて実行される、その前処理としての新たなメッシュＭ及び対応する代表地点Ｘの生成処理を含む（サーバ装置ＳＶ内の）地図データの更新処理について、具体的に図５を用いて説明する。
【００５２】
地図データ更新装置ＰＣにおいては、上記サーバ装置ＳＶ内の地図データの更新処理に際し、その前処理として、新たな地図データが取得された場合にその地図データに対応する新たなメッシュＭ並びに代表地点Ｘの新たな決定処理（すなわち、メッシュＭ並びに代表地点Ｘのバージョンアップ処理）を行う。
【００５３】
すなわち、図５に示すように、当該前処理を含む地図データの更新処理としては、外部から最新の地図データが取得されると（ステップＳ１）、当該取得された地図データ自体について、例えば、その地図データが相当する地図の縮尺、道路密集度又は交通量等に基づいて上記メッシュＭとしての分割数をＭnと決定し（ステップＳ２）、更にその決めた分割数で新しい地図データを分割して上記メッシュＭを生成する（ステップＳ３）。
【００５４】
次に、当該生成されたメッシュＭの夫々につき、上述したように、各メッシュＭ内において最も交通量の多い交差点又はその中心に最も近い道路上の地点或いはその中にある高速道路の入口のいずれかをもって代表地点Ｘを決定し、その座標（緯度情報及び経度情報等）を代表地点情報１Ｂとして算出する（ステップＳ４）。なおこのとき、当該新たな代表地点Ｘに相当するバージョン情報も当該新たな代表地点情報１Ｂ内に含まれることとなる。
【００５５】
更に、上記代表地点間経路情報１Ｃを新たな地図データ（代表地点Ｘ）について生成すべく、出発地点となる代表地点Ｘを含むメッシュＭのメッシュ番号を示すパラメータｉ並びに目的地点となる代表地点Ｘを含むメッシュＭのメッシュ番号を示すパラメータｊを夫々初期化する（ステップＳ５）。
【００５６】
そして、その時のパラメータｉの値をメッシュ番号とする、メッシュＭ内の代表地点Ｘを出発代表地点Ｓとし（ステップＳ６）、更にその時のパラメータｊの値をメッシュ番号とする、メッシュＭ内の代表地点Ｘを目的代表地点Ｇとし（ステップＳ７）、当該出発代表地点Ｓから目的代表地点Ｇまでの経路を新たな地図データ（道路データ）を用いて探索する（ステップＳ８）。このとき、当該経路としては、代表的な経路を一つ探索してもよいし、異なる条件で複数探索してもよい。
【００５７】
次に、その探索した結果としての経路を用いた場合の移動コストＲを算出し、当該経路上にある道路を識別する道路識別情報と共に、その時のパラメータｉの値をｘ軸の値としその時のパラメータｊの値をｙ軸の値とするマトリックスＭＴＸ（当該マトリックスＭＴＸ自体はＨＤＤ１０内に記憶されている）内の座標ＭＴＸ（ｉ、ｊ）に記憶させる。
【００５８】
なお、当該移動コストＲについて詳細には、後述する第２実施形態において説明する。また、本第１実施形態に係る経路探索処理では、当該移動コストＲ自体は用いない。
【００５９】
そして、パラメータｊの値を「１」だけインクリメントし（ステップＳ１０）、更に、そのインクリメント後のパラメータｊの値がメッシュＭの番号の最大値Ｍnとなったか否か、すなわち、そのときに出発代表地点Ｓとなっている代表地点Ｘを除く他の全ての代表地点Ｘを目的代表地点Ｇとして経路探索をし終わったか否かを確認する（ステップＳ１１）。
【００６０】
そして、未だパラメータｊの値がメッシュＭの番号の最大値Ｍnとなっていない場合は（ステップＳ１１；ＮＯ）、そのときに出発代表地点Ｓとなっている代表地点Ｘについて未だ経路を探索していない他の代表地点Ｘ（目的代表地点Ｇ）があるとして、上記ステップＳ７に戻って以降の処理を当該経路未探索の目的代表地点Ｇに対して実行する。一方、パラメータｊの値がメッシュＭの番号の最大値Ｍnとなったときは（ステップＳ１１；ＹＥＳ）、次に、パラメータiの値を「１」だけインクリメントし（ステップＳ１２）、更に、そのインクリメント後のパラメータiの値がメッシュＭの番号の最大値Ｍnとなったか否か、すなわち、全ての代表地点Ｘを出発代表地点Ｓとして経路探索をし終わったか否かを確認する（ステップＳ１３）。
【００６１】
そして、未だパラメータｉの値がメッシュＭの番号の最大値Ｍnとなっていない場合は（ステップＳ１３；ＮＯ）、新たな出発代表地点Ｓとなるべき他の代表地点Ｘがあるとして、上記ステップＳ６に戻って以降の処理を当該新たな出発代表地点Ｓに対して実行する。一方、パラメータｉの値がメッシュＭの番号の最大値Ｍnとなったときは（ステップＳ１３；ＹＥＳ）、全ての代表地点Ｘ間についての網羅的な経路探索が終了したこととなるので、前処理としての代表地点間経路情報１Ｃ（上記移動コストＲを含む）の生成を終了する。
【００６２】
その後、上記新しい道路データ１Ａ、新しい代表地点情報１Ｂ及び新しい代表地点間経路情報１Ｃに加えて、当該代表地点間経路情報１Ｃにおいて更新対象となる道路データを示す識別情報又はポインタ情報を上記地図更新データＳupdateとしてサーバ装置ＳＶに出力する（ステップＳ１４）。
【００６３】
これにより、上記サーバ装置ＳＶは、取得した地図更新データＳupdateを用いてデータベース１内の古い道路データ１Ａ、代表地点情報１Ｂ及び代表地点間経路情報１Ｃを更新することとなる。
【００６４】
最後に、上記更新されたデータベース１を含むサーバ装置ＳＶと、カーナビゲーションシステムＮＶのいずれかと、を用いた第１実施形態に係る経路探索処理について説明する。
【００６５】
先ず、当該カーナビゲーションシステムＮＶ自体の構成について説明する。
【００６６】
図６に示すように、一つのカーナビゲーションシステムＮＶは、ハードディスクを含むＨＤＤ（Hard Disc Drive）２０と、代表地点設定手段、更新手段及び探索手段としてのナビゲーション処理部２１と、メモリ２２と、操作ボタン又はリモートコントローラ等を含む入力部２５と、液晶ディスプレイ等からなるディスプレイ２６と、サーバ装置ＳＶとナビゲーション処理部２１とを接続する端末装置送信手段としてのインターフェース２３と、航法衛星からの航法電波を受信した現在位置を検出するＧＰＳ（Global Positioning System）センサや、自立的に現在位置を検出する距離センサ及び加速度センサを含むセンサ部２４と、により構成されている。
【００６７】
このとき、ＨＤＤ１０内にはサーバ装置ＳＶから送信されて来る後述の更新道路データを用いて更新される経路探索用の道路データ２０Ａ（上記道路データ１Ａと同様のメッシュＭに分割されている）が、代表地点情報２０Ｂと共に蓄積記憶される。
【００６８】
ここで、当該道路データ２０Ａ自体としては、上記道路データ１Ａと同様に、道路上の地点を示すノードを示すノード情報と、当該ノード間を連結するリンクを示すリンク情報と、の組み合わせから構成されており、更に道路データ１Ａと同様メッシュＭを単位としてＨＤＤ１０内に蓄積されている。
【００６９】
また、代表地点情報２０Ｂ自体としては、上記代表地点情報１Ｂと同様に、対応する代表地点Ｘを識別するための代表地点識別情報、当該代表地点Ｘの地図データ更新におけるバージョン情報並びに当該代表地点Ｘの位置自体を示す緯度情報、経度情報及び高度情報等が含まれている。
【００７０】
このとき、カーナビゲーションシステムＮＶ内の道路データ２０Ａ及び代表地点情報２０Ｂは、サーバ装置ＳＶ内のデータベース１に蓄積されている全国版の道路データ１Ａ及び代表地点情報１Ｂとは異なり、当該カーナビゲーションシステムＮＶにおいて実際に行なわれる経路探索処理に供される当該道路データ２０Ａ及び代表地点情報２０Ｂのみが蓄積記憶されている。
【００７１】
一方、インターフェース２３は、上記カーナビ信号Ｓnvに対して予め設定されたい入出力インターフェース処理を実行する。そして、上記サーバ信号Ｓnvとしてサーバ装置ＳＶから上記更新道路データ等が出力されて来ると、これをインターフェース信号Ｓifに変換してＣＰＵ２１に出力すると共に、サーバ装置ＳＶに送信すべきデータが当該インターフェース信号ＳifとしてＣＰＵ２１から出力されて来ると、これをカーナビ信号Ｓnvに変換してサーバ装置ＳＶに出力する。
【００７２】
他方、センサ部２４は、上記航法電波を用いて又は自立的に現在位置及び速度並びに移動方向等を検出し、その検出内容を示すセンサ信号Ｓcを生成してナビゲーション処理部２１に出力する。
【００７３】
そして、ナビゲーション処理部２１は、ＨＤＤ２０内の道路データ等を用いて後述する第１実施形態に係る経路探索処理を含む案内処理を実行する。
【００７４】
このとき、当該案内処理時においてナビゲーション処理部２１を動作させるために必要な指示は、入力部２５を用いてその操作者により実行され、当該実行された指示操作に対応する操作信号Ｓopとしてナビゲーション処理部２１に送信される。これにより、当該ナビゲーション処理部２１は、当該操作信号Ｓopの内容に応じて上記案内処理等を実行する。
【００７５】
また、カーナビゲーションシステムＮＶ自体の稼働状態は、ナビゲーション処理部２１から出力される表示信号Ｓdpとしてディスプレイ２６に出力され、当該ディスプレイ２６において予め設定された表示形式で表示される。
【００７６】
更に、上記ナビゲーション処理部２１の動作に必要な種々のデータは、メモリ信号Ｓmとしてメモリ２２に出力され、当該メモリ２２において揮発的に又は不揮発的に記憶され、更に必要に応じて再度メモリ信号Ｓmとして読み出される。
【００７７】
次に、上述した構成を備えるカーナビゲーションシステムＮＶとサーバ装置ＳＶとの連携により実行される、第１実施形態に係る経路探索処理について、図７を用いて説明する。
【００７８】
図７に示すように、当該経路探索処理においては、先ず、カーナビゲーションシステムＮＶにおいて、自らが移動する際の出発地点及び目的地点が設定されると（ステップＳ２０）、当該設定された出発地点が含まれているメッシュＭを代表する出発代表地点と、当該設定された目的地点が含まれているメッシュＭを代表する目的代表地点と、が代表地点情報２０Ｂ内において検索される（ステップＳ２１）。
【００７９】
次に、当該検索された出発代表地点及び目的代表地点夫々に相当する代表地点情報２０ＢがネットワークＮＴを介してサーバ装置ＳＶに送信される（ステップＳ２３）。
【００８０】
次に、サーバ装置ＳＶでは、当該送信されて来た出発代表地点及び目的代表地点夫々に相当する代表地点情報２０Ｂに基づき、その代表地点情報２０Ｂに含まれている出発代表地点及び目的代表地点夫々に相当してサーバ装置ＳＶ内に蓄積されている代表地点に相当する代表地点情報１Ｂを、サーバ装置ＳＶ内において確定する（ステップＳ２４）。
【００８１】
そして、カーナビゲーションシステムＮＶから送信されて来た（ステップＳ２３）代表地点情報２０Ｂに含まれる各代表地点Ｘ（具体的には出発代表地点及び目的代表地点の夫々）のバージョンと、サーバ装置ＳＶにおいて確定（ステップＳ２４）された代表地点Ｘのバージョンと、を比較し（ステップＳ２５、Ｓ２６）、サーバ装置ＳＶにおいて確定された（出発代表地点及び目的代表地点に相当する）代表地点Ｘの方が新しく更新されたものであるときは（ステップＳ２６；ＹＥＳ）、その確定された代表地点Ｘ間の経路に相当する経路情報（当該経路に含まれる道路識別情報等を含む道路データ１Ａ）を上記データベース１内から抽出し、当該カーナビゲーションシステムＮＶに送信する（ステップＳ２８）。
【００８２】
これにより、当該新しい経路情報が送信されたカーナビゲーションシステムＮＶでは、当該送信されて来た経路情報に含まれる道路データ１Ａを用いてＨＤＤ２０内の道路データ２０Ａを更新すると共に（ステップＳ２９）、当該更新後の道路データ２０Ａを用いて元の（ステップＳ２０）出発地点から目的地点までの経路を探索し（ステップＳ３０）、当該探索結果を用いて以後の案内処理を実行する。
【００８３】
一方、ステップＳ２６の判定において、カーナビゲーションシステムＮＶから送信されて来た代表地点情報２０Ｂに含まれる代表地点Ｘのバージョンと、サーバ装置ＳＶにおいて確定された代表地点Ｘのバージョンと、が同一であるときは（ステップＳ２６；ＮＯ）、カーナビゲーションシステムＮＶにおいて探索された経路上の道路データは更新されていないものとして、元の（ステップＳ２０）出発地点から目的地点までの経路を、その時にカーナビゲーションシステムＮＶ内に蓄積されている道路データ２０Ａを用いて探索して（ステップＳ２７）以後の案内処理を実行する。
【００８４】
以上夫々説明したように、第１実施形態に係る経路探索システムＳの動作によれば、全ての代表地点Ｘ間についての代表地点間経路情報１Ｃを予め網羅的にサーバ装置ＳＶ内に蓄積しているので、カーナビゲーションシステムＮＶにおいて必要な経路を確定する際に、代表地点Ｘ間の経路を確定するまでのサーバ装置ＳＶにおける負荷を大幅に軽減することができる。
【００８５】
また、カーナビゲーションシステムＮＶにおいて設定された出発代表地点及び目的代表地点夫々のバージョンと、サーバ装置ＳＶ内における対応する代表地点のバージョンと、を比較して道路データ２０Ａを更新するか否かを判断するので、カーナビゲーションシステムＮＶの移動に必要な経路に無関係の道路データ２０Ａが更新されることがないことから、カーナビゲーションシステムＮＶの移動に必要な最低限の更新すべき道路データ２０Ａの範囲を的確に確定して迅速に当該道路データ２０Ａを更新することができる。
【００８６】
従って、カーナビゲーションシステムＮＶにおける経路探索に必要な道路データ２０Ａの更新範囲を的確に判断して効率的に当該更新処理を実行することができる。
【００８７】
また、出発代表地点と目的代表地点との間の経路が含まれるメッシュＭを代表する代表地点Ｘの少なくともいずれか一つが、カーナビゲーションシステムＮＶ上で先に探索した経路が含まれるメッシュＭを代表する代表地点Ｘの少なくともいずれか一つに対して更新された当該いずれか一つであるとき、道路データ２０Ａを更新すべきであると判断するので、更新された代表地点Ｘがある場合に限って必要最小限且つ最新の更新道路データをもって道路データ２０Ａを効率的に更新することができる。
【００８８】
更に、代表地点Ｘが代表するメッシュＭが、サーバ装置ＳＶ内の道路データ１Aに対応する地図の縮尺、道路密集度又は交通量の少なくともいずれか一つに基づいて予め区分されたメッシュＭであるので、経路案内処理の際に実際に問題となる要素に基づいてメッシュＭが区分されていることから、より的確な経路探索に資することができる。
【００８９】
更にまた、代表地点Ｘを、対応するメッシュＭ内において最も交通量の多い交差点とした場合には、経路案内処理の際に実際に問題となる交通量に基づいて代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【００９０】
また、代表地点Ｘを、対応するメッシュＭの中心に最も近い道路地点とした場合には、経路案内処理の際に実際に問題となるメッシュＭ内の中心地点として代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【００９１】
更にまた、代表地点Ｘを、対応するメッシュＭ内にある高速道路の入口とした場合には、長距離移動の際の経路案内処理の際に実際に問題となる高禄道路に基づいて代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【００９２】
また、第１実施形態に係る地図データ更新装置ＰＣによれば、道路データ１Ａの更新に合わせて代表地点情報１Ｂと代表地点間経路情報１Ｃとが更新されるので、常に最新の各情報をサーバ装置ＳＶ内に蓄積して経路探索に供させることができる。
【００９３】
（II）第２実施形態
次に、本願に係る他の実施形態である第２実施形態について、図８を用いて説明する。なお、図８は第２実施形態に係る経路探索処理を示すフローチャートである。
【００９４】
また、第２実施形態に係る経路探索処理を実行する経路探索システムの構成は、基本的に第１実施形態に係る経路探索システムＳの構成と同様であるので、以下の第２実施形態においては同様の部材番号を用いて細部の説明は省略する。更に、図８に示すフローチャートにおいて、上述した第１実施形態に係る経路探索処理（図７参照）と同一の処理については同一のステップ番号を付して細部の説明は省略する。
【００９５】
上述した第１実施形態においては、経路上の出発代表地点及び目的代表地点がサーバ装置ＳＶにおいて更新されている場合にのみカーナビゲーションシステムＮＶ内の道路データ２０Ａを更新する場合について説明したが、以下に説明する第２実施形態では、当該各代表地点Ｘのバージョンではなく、探索された経路上を移動する際の上記移動コストＲ（図５ステップＳ９参照）を考慮して道路データ２０Ａの更新の可否を判断する。
【００９６】
ここで、当該移動コストＲとは、当該移動に伴って発生する負荷を意味するものであり、より具体的には、例えば、当該移動に必要な移動時間、当該移動における実際の移動距離、又は当該移動に必要な料金等が該当する。
【００９７】
また、第２実施形態に係るサーバ装置ＳＶ内の代表地点間経路情報１Ｃとしては、当該各代表地点間に係る上記移動コストＲ（すなわち、当該代表地点間に係る移動時間、移動距離又は必要料金等）が蓄積されている。
【００９８】
図８に示すように、第２実施形態に係る経路探索処理においては、先ず、カーナビゲーションシステムＮＶにおいて、図７に示すステップＳ２０及びＳ２１と同様の処理を事項する。
【００９９】
次に、当該検索された出発代表地点から当該検索された目的代表地点までの経路が、カーナビゲーションシステムＮＶにおいて探索され、更に当該探索された経路上を移動する際に必要な上記移動コストＲが算出される（ステップＳ４０）。
【０１００】
そして、当該探索された経路内にある上記出発代表地点及び目的代表地点を夫々示す代表地点情報２０Ｂと、上記算出された移動コストＲを示す情報と、がネットワークＮＴを介してサーバ装置ＳＶに送信される（ステップＳ４１）。
【０１０１】
次に、サーバ装置ＳＶでは、当該送信されて来た代表地点情報２０Ｂに基づき、その代表地点情報２０Ｂに含まれている出発代表地点及び目的代表地点夫々に相当するサーバ装置ＳＶに蓄積されている代表地点に相当する代表地点情報１Ｂを確定すると共に、当該各確定された出発代表地点及び目的代表地点間に相当する上記移動コストＲを、第２実施形態係る代表地点間経路情報１Ｃ内から抽出して確定する（ステップＳ４２）。
【０１０２】
なお、当該ステップＳ４２の処理について、当該第２実施形態に係る代表地点間経路情報１Ｃは、地図データ更新装置ＰＣによりサーバ装置ＳＶ内の代表地点間経路情報１Ｃを更新する際に、当該更新される代表地点間経路情報１Ｃに対応する移動コストＲが併せて更新されることとなる。
【０１０３】
更に、例えば重要な道路データ２０Ａの更新であって、移動コストＲの如何に拘わらず更新すべき道路データ２０Ａがある場合等においては、上記ステップＳ４２の処理に用いられる移動コストＲを、意図的に良好な移動コストＲとなるように上記代表地点間経路情報１Ｃの更新時に更新しておくように構成することも可能である。
【０１０４】
そして、カーナビゲーションシステムＮＶから送信されて来た（ステップＳ４１）移動コストＲと、サーバ装置ＳＶにおいて確定された（ステップＳ４２）移動コストＲと、を比較し（ステップＳ４３）、サーバ装置ＳＶにおいて確定された移動コストＲの方がカーナビゲーションシステムＮＶから送信されて来た移動コストＲよりも良好である（移動コストＲとして低い）ときは（ステップＳ４３；サーバの方が良好）、上記ステップＳ４２の処理において確定された出発代表地点及び目的代表地点間の経路に相当する経路情報（当該経路に含まれる道路識別情報等を含む道路データ１Ａ）を上記データベース１内から抽出し、当該カーナビゲーションシステムＮＶに送信する（ステップＳ２８）。
【０１０５】
これにより、図７に示すステップＳ２９及びＳ３０と同様の処理を行ない、当該再探索結果を用いて以後の案内処理を実行する。
【０１０６】
一方、ステップＳ４３の判定において、カーナビゲーションシステムＮＶから送信されて来た移動コストＲの方がサーバ装置ＳＶにおいて確定された移動コストＲよりも良好であるときは（ステップＳ４３；ナビの方が良好）、元の（ステップＳ２０）出発地点から目的地点までの経路を、その時にカーナビゲーションシステムＮＶ内に蓄積されている道路データ２０Ａを用いて探索して（ステップＳ２７）以後の案内処理を実行する。
【０１０７】
以上夫々説明したように、第２実施形態に係る経路探索システムの動作によれば、第１実施形態に係る経路探索システムＳの動作と同様に、全ての代表地点Ｘ間についての代表地点間経路情報１Ｃを予め網羅的にサーバ装置ＳＶ内に蓄積しているので、カーナビゲーションシステムＮＶにおいて必要な経路を確定する際に、代表地点Ｘ間の経路を確定するまでのサーバ装置ＳＶにおける負荷を大幅に軽減することができる。
【０１０８】
また、カーナビゲーションシステムＮＶにおいて設定された出発代表地点及び目的代表地点間の移動コストＲと、サーバ装置ＳＶにおいて探索した対応する代表地点Ｘ間の移動コストＲと、を比較して道路データ２０Ａを更新するか否かを判断するので、カーナビゲーションシステムＮＶの移動に必要な経路に無関係の道路データ２０Ａが更新されることがないことから、カーナビゲーションシステムＮＶの移動に必要な最低限の更新すべき道路データ２０Ａの範囲を的確に確定して迅速に当該道路データ２０Ａを更新することができる。
【０１０９】
従って、カーナビゲーションシステムＮＶにおける経路探索に必要な道路データ２０Ａの更新範囲を的確に判断して効率的に当該更新処理を実行することができる。
【０１１０】
更に、代表地点Ｘが代表するメッシュＭが、サーバ装置ＳＶ内の道路データ１Aに対応する地図の縮尺、道路密集度又は交通量の少なくともいずれか一つに基づいて予め区分されたメッシュＭであるので、経路案内処理の際に実際に問題となる要素に基づいてメッシュＭが区分されていることから、より的確な経路探索に資することができる。
【０１１１】
更にまた、代表地点Ｘを、対応するメッシュＭ内において最も交通量の多い交差点とした場合には、経路案内処理の際に実際に問題となる交通量に基づいて代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【０１１２】
また、代表地点Ｘを、対応するメッシュＭの中心に最も近い道路地点とした場合には、経路案内処理の際に実際に問題となるメッシュＭ内の中心地点として代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【０１１３】
更にまた、代表地点Ｘを、対応するメッシュＭ内にある高速道路の入口とした場合には、長距離移動の際の経路案内処理の際に実際に問題となる高禄道路に基づいて代表地点Ｘが設定されることから、より的確な経路探索に資することができる。
【０１１４】
これらに加えて、サーバ装置ＳＶにおいて探索された経路を移動する際の移動態様の方が、カーナビゲーションシステムＮＶ上で先に探索した経路を当該カーナビゲーションシステムＮＶが移動する際の移動態様よりも有利であるとき、道路データ２０Ａを更新すべきであると判断するので、移動しようとするカーナビゲーションシステムＮＶにとって真に必要な場合にのみ道路データ２０Ａを効率的に更新することができる。
【０１１５】
更に、移動コストＲとして移動時間を採用する場合には、サーバ装置ＳＶにおいて探索された経路を移動する際の移動時間の方が、カーナビゲーションシステムＮＶ上で先に探索した経路を当該カーナビゲーションシステムＮＶが移動する際の移動時間よりも短いとき、道路データ２０Ａを更新すべきであると判断するので、移動時間を基準として、移動しようとするカーナビゲーションシステムＮＶにとって真に必要な場合にのみ道路データ２０Ａを効率的に更新することができる。
【０１１６】
更にまた、移動コストＲとして移動距離を採用する場合には、サーバ装置ＳＶにおいて探索された経路を移動する際の移動距離の方が、カーナビゲーションシステムＮＶ上で先に探索した経路を当該カーナビゲーションシステムＮＶが移動する際の移動距離よりも短いとき、道路データ２０Ａを更新すべきであると判断するので、移動距離を基準として、移動しようとするカーナビゲーションシステムＮＶにとって真に必要な場合にのみ道路データ２０Ａを効率的に更新することができる。
【０１１７】
また、移動コストＲとして移動のための料金を採用する場合には、サーバ装置ＳＶにおいて探索された経路を移動する際に必要な料金の方が、カーナビゲーションシステムＮＶ上で先に探索した経路を当該カーナビゲーションシステムＮＶが移動する際に必要な料金よりも短いと判断されたとき、道路データ２０Ａを更新すべきであると判断するので、移動のための料金を基準として、移動しようとするカーナビゲーションシステムＮＶにとって真に必要な場合にのみ道路データ２０Ａを効率的に更新することができる。
【０１１８】
なお、上述した各実施形態においては、カーナビゲーションシステムＮＶにおいて経路探索処理を実行する場合について説明したが、これ以外に、例えば携帯型の情報端末装置や携帯型の電話機において経路探索処理を実行する場合について本願を適用することも可能である。
【０１１９】
更に、図５、図７又は図８に夫々示すフローチャートに対応するプログラムを、フレキシブルディスク又はハードディスク等の情報記録媒体に記録しておき、又はインターネット等を介して取得して記録しておき、これらを汎用のコンピュータで読み出して実行することにより、当該コンピュータを各実施形態に係る地図データ更新装置ＰＣ内のＣＰＵ１１（図５に示すフローチャートに対応するプログラムの場合）又はサーバ装置ＳＶ或いはカーナビゲーションシステムＮＶ内のナビゲーション処理部２１（図７又は図８に示すフローチャートに対応するプログラムの場合）として活用することも可能である。
【図面の簡単な説明】
【０１２０】
【図１】第１実施形態に係る経路探索システムの概要構成を示すブロック図である。
【図２】第１実施形態に係る経路探索システムに含まれる各装置の細部構成を示すブロック図であり、（ａ）は第１実施形態に係るサーバ装置の細部構成を示すブロック図であり、（ｂ）は第１実施形態に係る地図データ更新装置の細部構成を示すブロック図である。
【図３】第１実施形態に係る道路データの構成を例示する図である。
【図４】第１実施形態に係る代表地点の状態を例示する図である。
【図５】第１実施形態に係るサーバ装置における地図データ等の更新を示すフローチャートである。
【図６】第１実施形態に係るカーナビゲーションシステムの概要構成を示すブロック図である。
【図７】第１実施形態に係る経路探索処理を示すフローチャートである。
【図８】第２実施形態に係る経路探索処理を示すフローチャートである。
【符号の説明】
【０１２１】
１ データベース
１Ａ、２０Ａ 道路データ
１Ｂ、２０Ｂ 代表地点情報
１Ｃ 代表地点間経路情報
２、１１ ＣＰＵ
３、１２、２２ メモリ
４、１３、２３ インターフェース
５、１４、２５ 入力部
６、１５、２６ ディスプレイ
１０、２０ ＨＤＤ
２１ ナビゲーション処理部
２４ センサ部
Ｓ 経路探索システム
ＳＶ サーバ装置
ＰＣ 地図データ更新装置
ＮＶ カーナビゲーションシステム
ＮＴ ネットワーク
Ｍ１、Ｍ２、Ｍ３、Ｍ４、Ｍ５、ＭＬ、ＭＬ＋１、ＭＬ＋２、ＭＬ＋３、Ｍn、Ｍn-1 メッシュ
ＸＬ、ＸＬ＋１、ＸＬ＋２、ＸＬ＋３ 代表地点
【特許請求の範囲】
【請求項１】
サーバ道路情報を最新に更新しつつ蓄積するサーバ装置と、当該サーバ装置に接続され且つ端末道路情報を蓄積して案内処理を行う端末装置と、を含むナビゲーションシステムに含まれ、前記端末装置が移動する経路を探索する経路探索システムにおいて、
前記サーバ装置は、道路が敷設され且つ予め区分された地域を代表するものとして当該地域毎に予め設定されている代表地点であって最新の前記サーバ道路情報に対応する代表地点を示す代表地点情報と、全ての当該代表地点情報相互間を移動する際に用いるべき前記道路を示す代表地点間経路情報と、を前記最新のサーバ道路情報と共に蓄積する蓄積手段を備え、
前記端末装置は、
前記端末装置が移動する前記経路の出発地点に対応する出発代表地点と、当該経路の目的地点に対応する目的代表地点と、を設定する代表地点設定手段と、
前記設定された出発代表地点から前記設定された目的代表地点までの代表地点間経路に対応する経路情報を前記サーバ装置に送信する端末装置送信手段と、
前記サーバ装置から前記端末道路情報の更新に用いられるべき更新道路情報が送信されて来たとき、当該送信されて来た更新道路情報を用いて前記蓄積されている端末道路情報を更新する更新手段と、
前記更新後の端末道路情報を用いて前記出発地点から前記目的地点までの経路を探索する探索手段と、
を備え、
更に前記サーバ装置は、
前記送信されて来た経路情報に対応する前記出発代表地点から前記送信されて来た経路情報に対応する前記目的代表地点まで移動する際に用いるべき前記道路を示す前記代表地点間経路情報を、前記蓄積手段から抽出する抽出手段と、
前記抽出された代表地点間経路情報と、前記送信されて来た経路情報と、を比較し、前記端末道路情報を更新すべきか否かを判断する判断手段と、
前記端末道路情報を更新すべきであると判断されたとき、当該更新に用いられるべき前記更新道路情報を前記端末装置に送信するサーバ装置送信手段と、
を備えることを特徴とする経路探索システム。
【請求項２】
請求項１に記載の経路探索システムにおいて、
前記判断手段は、前記抽出された代表地点間経路情報に相当する経路を前記端末装置が移動する際の移動態様と、前記送信されて来た経路情報に相当する経路を前記端末装置が移動する際の移動態様と、を比較し、前記代表地点間経路情報に相当する経路を前記端末装置が移動する際の移動態様の方が、前記経路情報に相当する経路を前記端末装置が移動する際の移動態様よりも当該端末装置において有利であるとき、前記端末道路情報を更新すべきであると判断することを特徴とする経路探索システム。
【請求項３】
請求項２に記載の経路探索システムにおいて、
前記判断手段は、前記代表地点間経路情報に相当する経路を前記端末装置が移動する際に必要な移動時間の方が、前記経路情報に相当する経路を前記端末装置が移動する際に必要な移動時間よりも短いとき、前記端末道路情報を更新すべきであると判断することを特徴とする経路探索システム。
【請求項４】
請求項２に記載の経路探索システムにおいて、
前記判断手段は、前記代表地点間経路情報に相当する経路を前記端末装置が移動する際に必要な移動距離の方が、前記経路情報に相当する経路を前記端末装置が移動する際に必要な移動距離よりも短いとき、前記端末道路情報を更新すべきであると判断することを特徴とする経路探索システム。
【請求項５】
請求項２に記載の経路探索システムにおいて、
前記判断手段は、前記代表地点間経路情報に相当する経路を前記端末装置が移動する際に必要な料金の方が、前記経路情報に相当する経路を前記端末装置が移動する際に必要な料金よりも安いとき、前記端末道路情報を更新すべきであると判断することを特徴とする経路探索システム。
【請求項６】
請求項１に記載の経路探索システムにおいて、
前記判断手段は、前記抽出された代表地点間経路情報に対応する経路が含まれる前記地域を代表する前記代表地点の少なくともいずれか一つが、前記送信されて来た経路情報に相当する経路が含まれる前記地域を代表する前記代表地点の少なくともいずれか一つに対して更新された当該いずれか一つであるとき、前記端末道路情報を更新すべきであると判断することを特徴とする経路探索システム。
【請求項７】
請求項１から６のいずれか一項に記載の経路探索システムにおいて、
前記地域は、前記サーバ道路情報に対応する地図の縮尺、道路密集度又は交通量の少なくともいずれか一つに基づいて予め区分された地域であることを特徴とする経路探索システム。
【請求項８】
請求項１から７のいずれか一項に記載の経路探索システムにおいて、
前記代表地点は、当該代表地点が代表する前記地域内において最も交通量の多い交差点であることを特徴とする経路探索システム。
【請求項９】
請求項１から７のいずれか一項に記載の経路探索システムにおいて、
前記代表地点は、道路上の地点であって当該代表地点が代表する前記地域の中心に最も近い地点であることを特徴とする経路探索システム。
【請求項１０】
請求項１から７のいずれか一項に記載の経路探索システムにおいて、
前記代表地点は、当該代表地点が代表する前記地域内にある高速道路の入口であることを特徴とする経路探索システム。
【請求項１１】
請求項１から１０のいずれか一項に記載の経路探索システムに含まれる前記サーバ装置に蓄積される前記サーバ道路情報と、前記代表地点情報と、前記代表地点間経路情報と、を夫々生成する道路データ生成装置であって、
予め設定された期間毎に前記サーバ道路情報を最新に更新するサーバ道路情報更新手段と、
前記更新されたサーバ道路情報に対応して前記代表地点情報を更新する代表地点情報更新手段と、
前記更新されたサーバ道路情報に対応して前記代表地点間経路情報を更新する代表地点間経路情報更新手段と、
を備えることを特徴とする道路データ生成装置。
【請求項１２】
請求項１から１１のいずれか一項に記載のサーバ装置内の前記蓄積手段に蓄積されている経路探索用データであって、
前記代表地点間経路情報の生成に用いられ且つ前記更新道路情報を抽出可能に構成された前記サーバ道路情報と、
最新の前記サーバ道路情報に対応した前記地域を示す地域情報と、
当該最新の地域毎に設定された前記代表地点を示す前記代表地点情報と、
当該最新の代表地点情報に基づいて網羅的に探索された代表地点間経路としての前記道路を示す前記代表地点間経路情報と、
を含むことを特徴とする経路探索用データ。
【請求項１３】
請求項１から１０に記載の経路探索システムに含まれる前記サーバ装置であって、
前記蓄積手段と、
前記抽出手段と、
前記判断手段と、
前記サーバ装置送信手段と、
を備えることを特徴とするサーバ装置。
【請求項１４】
請求項１から１０に記載の経路探索システムに含まれる前記端末装置であって、
前記代表地点設定手段と、
前記端末装置送信手段と、
前記更新手段と、
前記探索手段と、
を備えることを特徴とする端末装置。
【請求項１５】
請求項１から１０に記載の経路探索システムに含まれ且つ前記蓄積手段を備える前記サーバ装置に含まれるコンピュータを、
前記抽出手段、
前記判断手段、及び、
前記サーバ装置送信手段、
として機能させることを特徴とするサーバ装置用プログラム。
【請求項１６】
請求項１から１０に記載の経路探索システムに含まれる前記端末装置に含まれるコンピュータを、
前記代表地点設定手段、
前記端末装置送信手段、
前記更新手段、及び、
前記探索手段、
として機能させることを特徴とする端末装置用プログラム。
【請求項１７】
サーバ道路情報を最新に更新しつつ蓄積するサーバ装置と、当該サーバ装置に接続され且つ端末道路情報を蓄積して案内処理を行う端末装置と、を含むナビゲーションシステムに含まれる当該端末装置が移動する経路を探索する経路探索方法において、
前記サーバ装置は、道路が敷設され且つ予め区分された地域を代表するものとして当該地域毎に予め設定されている代表地点であって最新の前記サーバ道路情報に対応する代表地点を示す代表地点情報と、全ての当該代表地点情報相互間を移動する際に用いるべき前記道路を示す代表地点間経路情報と、を前記最新のサーバ道路情報と共に蓄積する蓄積手段を備えており、
前記端末装置が移動する前記経路の出発地点に対応する出発代表地点と、当該経路の目的地点に対応する目的代表地点と、を当該端末装置において設定する代表地点設定工程と、
前記設定された出発代表地点から前記設定された目的代表地点までの代表地点間経路に対応する経路情報を当該端末装置から前記サーバ装置に送信する第１送信工程と、
前記サーバ装置において、前記送信されて来た経路情報に対応する前記出発代表地点から前記送信されて来た経路情報に対応する前記目的代表地点まで移動する際に用いるべき前記道路を示す前記代表地点間経路情報を、前記蓄積手段から抽出する抽出工程と、
前記サーバ装置において、前記抽出された代表地点間経路情報と、前記送信されて来た経路情報と、を比較し、前記端末道路情報を更新すべきか否かを判断する判断工程と、
前記判断工程において前記端末道路情報を更新すべきであると判断されたとき、当該更新に用いられるべき更新道路情報を前記サーバ装置から当該端末装置に送信する第２送信工程と、
前記更新道路情報が送信されて来た前記端末装置において、当該送信されて来た更新道路情報を用いて前記蓄積されている端末道路情報を更新する更新工程と、
前記端末道路情報が更新された前記端末装置において、当該更新後の端末道路情報を用いて前記出発地点から前記目的地点までの経路を探索する探索工程と、
を含むことを特徴とする経路探索方法。
【請求項１】
サーバ道路情報を最新に更新しつつ蓄積するサーバ装置と、当該サーバ装置に接続され且つ端末道路情報を蓄積して案内処理を行う端末装置と、を含むナビゲーションシステムに含まれ、前記端末装置が移動する経路を探索する経路探索システムにおいて、
前記サーバ装置は、道路が敷設され且つ予め区分された地域を代表するものとして当該地域毎に予め設定されている代表地点であって最新の前記サーバ道路情報に対応する代表地点を示す代表地点情報と、全ての当該代表地点情報相互間を移動する際に用いるべき前記道路を示す代表地点間経路情報と、を前記最新のサーバ道路情報と共に蓄積する蓄積手段を備え、
前記端末装置は、
前記端末装置が移動する前記経路の出発地点に対応する出発代表地点と、当該経路の目的地点に対応する目的代表地点と、を設定する代表地点設定手段と、
前記設定された出発代表地点から前記設定された目的代表地点までの代表地点間経路に対応する経路情報を前記サーバ装置に送信する端末装置送信手段と、
前記サーバ装置から前記端末道路情報の更新に用いられるべき更新道路情報が送信されて来たとき、当該送信されて来た更新道路情報を用いて前記蓄積されている端末道路情報を更新する更新手段と、
前記更新後の端末道路情報を用いて前記出発地点から前記目的地点までの経路を探索する探索手段と、
を備え、
更に前記サーバ装置は、
前記送信されて来た経路情報に対応する前記出発代表地点から前記送信されて来た経路情報に対応する前記目的代表地点まで移動する際に用いるべき前記道路を示す前記代表地点間経路情報を、前記蓄積手段から抽出する抽出手段と、
前記抽出された代表地点間経路情報と、前記送信されて来た経路情報と、を比較し、前記端末道路情報を更新すべきか否かを判断する判断手段と、
前記端末道路情報を更新すべきであると判断されたとき、当該更新に用いられるべき前記更新道路情報を前記端末装置に送信するサーバ装置送信手段と、
を備えることを特徴とする経路探索システム。
【請求項２】
請求項１に記載の経路探索システムにおいて、
前記判断手段は、前記抽出された代表地点間経路情報に相当する経路を前記端末装置が移動する際の移動態様と、前記送信されて来た経路情報に相当する経路を前記端末装置が移動する際の移動態様と、を比較し、前記代表地点間経路情報に相当する経路を前記端末装置が移動する際の移動態様の方が、前記経路情報に相当する経路を前記端末装置が移動する際の移動態様よりも当該端末装置において有利であるとき、前記端末道路情報を更新すべきであると判断することを特徴とする経路探索システム。
【請求項３】
請求項２に記載の経路探索システムにおいて、
前記判断手段は、前記代表地点間経路情報に相当する経路を前記端末装置が移動する際に必要な移動時間の方が、前記経路情報に相当する経路を前記端末装置が移動する際に必要な移動時間よりも短いとき、前記端末道路情報を更新すべきであると判断することを特徴とする経路探索システム。
【請求項４】
請求項２に記載の経路探索システムにおいて、
前記判断手段は、前記代表地点間経路情報に相当する経路を前記端末装置が移動する際に必要な移動距離の方が、前記経路情報に相当する経路を前記端末装置が移動する際に必要な移動距離よりも短いとき、前記端末道路情報を更新すべきであると判断することを特徴とする経路探索システム。
【請求項５】
請求項２に記載の経路探索システムにおいて、
前記判断手段は、前記代表地点間経路情報に相当する経路を前記端末装置が移動する際に必要な料金の方が、前記経路情報に相当する経路を前記端末装置が移動する際に必要な料金よりも安いとき、前記端末道路情報を更新すべきであると判断することを特徴とする経路探索システム。
【請求項６】
請求項１に記載の経路探索システムにおいて、
前記判断手段は、前記抽出された代表地点間経路情報に対応する経路が含まれる前記地域を代表する前記代表地点の少なくともいずれか一つが、前記送信されて来た経路情報に相当する経路が含まれる前記地域を代表する前記代表地点の少なくともいずれか一つに対して更新された当該いずれか一つであるとき、前記端末道路情報を更新すべきであると判断することを特徴とする経路探索システム。
【請求項７】
請求項１から６のいずれか一項に記載の経路探索システムにおいて、
前記地域は、前記サーバ道路情報に対応する地図の縮尺、道路密集度又は交通量の少なくともいずれか一つに基づいて予め区分された地域であることを特徴とする経路探索システム。
【請求項８】
請求項１から７のいずれか一項に記載の経路探索システムにおいて、
前記代表地点は、当該代表地点が代表する前記地域内において最も交通量の多い交差点であることを特徴とする経路探索システム。
【請求項９】
請求項１から７のいずれか一項に記載の経路探索システムにおいて、
前記代表地点は、道路上の地点であって当該代表地点が代表する前記地域の中心に最も近い地点であることを特徴とする経路探索システム。
【請求項１０】
請求項１から７のいずれか一項に記載の経路探索システムにおいて、
前記代表地点は、当該代表地点が代表する前記地域内にある高速道路の入口であることを特徴とする経路探索システム。
【請求項１１】
請求項１から１０のいずれか一項に記載の経路探索システムに含まれる前記サーバ装置に蓄積される前記サーバ道路情報と、前記代表地点情報と、前記代表地点間経路情報と、を夫々生成する道路データ生成装置であって、
予め設定された期間毎に前記サーバ道路情報を最新に更新するサーバ道路情報更新手段と、
前記更新されたサーバ道路情報に対応して前記代表地点情報を更新する代表地点情報更新手段と、
前記更新されたサーバ道路情報に対応して前記代表地点間経路情報を更新する代表地点間経路情報更新手段と、
を備えることを特徴とする道路データ生成装置。
【請求項１２】
請求項１から１１のいずれか一項に記載のサーバ装置内の前記蓄積手段に蓄積されている経路探索用データであって、
前記代表地点間経路情報の生成に用いられ且つ前記更新道路情報を抽出可能に構成された前記サーバ道路情報と、
最新の前記サーバ道路情報に対応した前記地域を示す地域情報と、
当該最新の地域毎に設定された前記代表地点を示す前記代表地点情報と、
当該最新の代表地点情報に基づいて網羅的に探索された代表地点間経路としての前記道路を示す前記代表地点間経路情報と、
を含むことを特徴とする経路探索用データ。
【請求項１３】
請求項１から１０に記載の経路探索システムに含まれる前記サーバ装置であって、
前記蓄積手段と、
前記抽出手段と、
前記判断手段と、
前記サーバ装置送信手段と、
を備えることを特徴とするサーバ装置。
【請求項１４】
請求項１から１０に記載の経路探索システムに含まれる前記端末装置であって、
前記代表地点設定手段と、
前記端末装置送信手段と、
前記更新手段と、
前記探索手段と、
を備えることを特徴とする端末装置。
【請求項１５】
請求項１から１０に記載の経路探索システムに含まれ且つ前記蓄積手段を備える前記サーバ装置に含まれるコンピュータを、
前記抽出手段、
前記判断手段、及び、
前記サーバ装置送信手段、
として機能させることを特徴とするサーバ装置用プログラム。
【請求項１６】
請求項１から１０に記載の経路探索システムに含まれる前記端末装置に含まれるコンピュータを、
前記代表地点設定手段、
前記端末装置送信手段、
前記更新手段、及び、
前記探索手段、
として機能させることを特徴とする端末装置用プログラム。
【請求項１７】
サーバ道路情報を最新に更新しつつ蓄積するサーバ装置と、当該サーバ装置に接続され且つ端末道路情報を蓄積して案内処理を行う端末装置と、を含むナビゲーションシステムに含まれる当該端末装置が移動する経路を探索する経路探索方法において、
前記サーバ装置は、道路が敷設され且つ予め区分された地域を代表するものとして当該地域毎に予め設定されている代表地点であって最新の前記サーバ道路情報に対応する代表地点を示す代表地点情報と、全ての当該代表地点情報相互間を移動する際に用いるべき前記道路を示す代表地点間経路情報と、を前記最新のサーバ道路情報と共に蓄積する蓄積手段を備えており、
前記端末装置が移動する前記経路の出発地点に対応する出発代表地点と、当該経路の目的地点に対応する目的代表地点と、を当該端末装置において設定する代表地点設定工程と、
前記設定された出発代表地点から前記設定された目的代表地点までの代表地点間経路に対応する経路情報を当該端末装置から前記サーバ装置に送信する第１送信工程と、
前記サーバ装置において、前記送信されて来た経路情報に対応する前記出発代表地点から前記送信されて来た経路情報に対応する前記目的代表地点まで移動する際に用いるべき前記道路を示す前記代表地点間経路情報を、前記蓄積手段から抽出する抽出工程と、
前記サーバ装置において、前記抽出された代表地点間経路情報と、前記送信されて来た経路情報と、を比較し、前記端末道路情報を更新すべきか否かを判断する判断工程と、
前記判断工程において前記端末道路情報を更新すべきであると判断されたとき、当該更新に用いられるべき更新道路情報を前記サーバ装置から当該端末装置に送信する第２送信工程と、
前記更新道路情報が送信されて来た前記端末装置において、当該送信されて来た更新道路情報を用いて前記蓄積されている端末道路情報を更新する更新工程と、
前記端末道路情報が更新された前記端末装置において、当該更新後の端末道路情報を用いて前記出発地点から前記目的地点までの経路を探索する探索工程と、
を含むことを特徴とする経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００８−３９４８８（Ｐ２００８−３９４８８Ａ）
【公開日】平成２０年２月２１日（２００８．２．２１）
【国際特許分類】
【出願番号】特願２００６−２１１４４７（Ｐ２００６−２１１４４７）
【出願日】平成１８年８月２日（２００６．８．２）
【出願人】（０００００５０１６）パイオニア株式会社 (3,620)
【出願人】（５９５１０５５１５）インクリメント・ピー株式会社 (197)
【Ｆターム（参考）】
【公開日】平成２０年２月２１日（２００８．２．２１）
【国際特許分類】
【出願日】平成１８年８月２日（２００６．８．２）
【出願人】（０００００５０１６）パイオニア株式会社 (3,620)
【出願人】（５９５１０５５１５）インクリメント・ピー株式会社 (197)
【Ｆターム（参考）】
[ Back to top ]