(57)【要約】【課題】本願の課題の一例は、サーバ装置において新規道路情報をメンテナンスする場合に、新規道路の影響領域を設定することで、経路計算結果が影響領域の範囲内であれば経路計算に影響がある道路として選別することにより、選別された道路だけをオブジェクト単位で更新することで、更新データ量を最小にすることが可能となる地図情報処理装置等を提供することを目的とする。【解決手段】本実施形態に記載の地図情報処理装置は、新設道路に関する更新有効範囲を設定し、ナビゲーション装置における経路探索結果の一部又は全部が更新有効範囲と重なる場合には、新設道路に関する追加地図情報をナビゲーション装置へ送出する。ナビゲーション装置は追加地図情報を記憶し、追加地図情報を加えた地図情報に基づいて、経路探索を行なう。【選択図】図１
2008032644.tif 000002
【特許請求の範囲】
【請求項１】
地図情報と追加地図情報とを記憶する記憶手段と、
ナビゲーション装置における経路探索情報を受信する受信手段と、
前記経路探索情報と前記追加地図情報に付属される情報との関係を判断する判断手段と、
前記判断手段による判断の結果、前記経路探索情報に影響を与える前記追加地図情報を選択する選択手段と、
前記ナビゲーション装置へ前記選択手段によって選択された前記追加地図情報を送信する送信手段と、
を備えることを特徴とする地図情報処理装置。
【請求項２】
請求項１に記載の地図情報処理装置において、
前記地図情報処理装置は、
前記追加地図情報における新たな道路情報に関連する関連領域情報を前記地図情報に設定する設定手段を更に備え、
前記判断手段は、前記経路探索情報における経路情報と前記関連領域情報とに重複する部分があるか否かを判断し、前記選択手段は前記重複する部分を有する前記新たな道路情報に対応する前記追加地図情報を選択することを特徴とする地図情報処理装置。
【請求項３】
請求項１または２に記載の地図情報処理装置において、
前記地図情報処理装置は、
前記新たな道路情報における予め定められた位置間を移動体が移動する場合の移動コストを演算する移動コスト演算手段を更に備え、
前記関連領域情報は、前記移動コスト演算手段によって算出された移動コストに関連して設定されることを特徴とする地図情報処理装置。
【請求項４】
請求項１乃至３の何れか一項に記載の地図情報処理装置において、
前記地図情報処理装置は、
前記新たな道路情報における予め定められた位置間を前記地図情報に基づいて移動体が移動する場合の移動コストと、前記新たな道路情報における前記予め定められた位置間を移動体が前記追加地図情報に基づいて移動する場合の移動コストとを比較演算する比較演算手段を更に備え、
前記関連領域情報は、前記比較演算手段によって算出された移動コストに関連して設定されることを特徴とする地図情報処理装置。
【請求項５】
請求項１乃至請求項４の何れか一項に記載の地図情報処理装置と、
経路探索を実行する経路探索手段と、
前記追加地図情報および前記経路探索手段による経路探索情報を送受信する送受信手段と、
前記送受信手段によって受信された前記追加地図情報を記憶する追加地図情報記憶手段と、
を備える前記ナビゲーション装置と、
を有することを特徴とする地図情報処理システム。
【請求項６】
請求項５に記載の地図情報処理システムにおいて、
前記ナビゲーション装置は、
前記経路探索手段によって検索された経路探索情報を表示する表示手段を備え、
前記表示手段は、前記送受信手段によって受信された前記追加地図情報を含む前記地図情報に基づいて、前記経路探索手段によって検索された経路探索情報を表示することを特徴とする地図情報処理システム。
【請求項７】
地図情報と追加地図情報とを記憶する記憶工程と、
ナビゲーション装置における経路探索情報を受信する受信工程と、
前記経路探索情報と前記追加地図情報に付属される情報との関係を判断する判断工程と、
前記判断工程における判断の結果、前記経路探索情報に影響を与える前記追加地図情報を選択する選択工程と、
前記ナビゲーション装置へ前記選択工程において選択された前記追加地図情報を送信する送信工程と、
を備えることを特徴とする地図情報処理装置の制御方法。
【請求項８】
地図情報処理装置に含まれるコンピュータを
地図情報と追加地図情報とを記憶する記憶手段、
ナビゲーション装置における経路探索情報を受信する受信手段、
前記経路探索情報と前記追加地図情報に付属される情報との関係を判断する判断手段、
前記判断手段による判断の結果、前記経路探索情報に影響を与える前記追加地図情報を選択する選択手段、
前記ナビゲーション装置へ前記選択手段によって選択された前記追加地図情報を送信する送信手段、
として機能させることを特徴とする地図情報処理装置の制御プログラム。
【請求項９】
請求項８に記載の地図情報処理装置の制御プログラムがコンピュータに読み取り可能に記録されていることを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、ナビゲーション情報等の情報処理システムの分野に関する。
【背景技術】
【０００２】
従来のカーナビゲーション装置としては、例えば、車両の走行に伴ってＧＰＳ等により現在位置を検出し、その現在位置をディスプレイ上に道路地図と共に表示することにより位置案内をし、現在地から目的地までの適切な目的地経路を設定し、その目的地経路に従って車両が走行できるように所定の経路案内を行う機能が知られている。
【０００３】
そして、これらの案内機能は、ＨＤ（Hard Disc）およびＤＶＤ（Digital Versatile Disc）等の記録媒体に記憶され、又は通信回線によって供給される道路地図データが用いられて実現されている。
【０００４】
しかし、道路は日々整備され、また新たな道路が設けられることもあり、ＨＤおよびＤＶＤ等の記録媒体に記憶されている道路地図データは、それらの記録媒体をユーザが入手した時点から刻々と変化しているのが現状である。従って、一旦入手した道路地図データも最新の道路事情を反映させるために頻繁に更新を行なう必要がある。それを怠ると新規開通の近道があるにも関わらず、従来通りの遠回りの経路が案内されたり、閉鎖された道路を通る経路が案内されたりする不都合が発生する。
【０００５】
そこで、道路を構成するリンク等のオブジェクトに不変のリンクＩＤを付け、オブジェクト単位での情報更新を可能にしている地図情報提供サービスがある。
（例えば、特許文献１に開示されている。）
【０００６】
また、カーナビゲーション装置が探索した経路の距離をサーバに送信し、サーバで同じ経路計算を行なった結果と比較した結果が異なっている場合に、カーナビゲーションの道路の更新を行なう地図情報提供サービスが知られている。
（例えば、特許文献２に開示されている。）
【特許文献１】特開２００４−２８７７０５号公報
【特許文献２】特開２００６−０６５２４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記特許文献１では、更新されるべき道路情報の選別については何ら記載されていない。また、上記特許文献２では、経路を構成する区分単位に情報が更新されてしまうので、区分に含まれる不要な情報も更新されてしまう。すなわち、これら従来のナビゲーション装置では、経路に沿った道路をオブジェクト単位で更新することは可能であるが、経路計算に必要な道路としてどこまで更新すればよいかは決定できなく、また、経路計算に影響のある道路の特定もできないという課題があった。また、経路計算に必要とされない余分な道路情報を記憶する記憶容量と余分な道路情報を処理する処理時間が必要となるという課題もあった。
【０００８】
本発明は、上記問題点を解決するものであり、その課題の一例は、サーバ装置において新規道路情報をメンテナンスする場合に、新規道路の影響領域を設定することで、経路計算結果が影響領域の範囲内であれば経路計算に影響がある道路として選別することにより、選別された道路だけをオブジェクト単位で更新することで、更新データ量を最小にすることが可能となる地図情報処理装置、地図情報処理装置の制御方法、地図情報処理装置の制御プログラム、および地図情報処理装置の制御プログラムを記録した記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の請求項１に記載の地図情報処理装置は、地図情報と追加地図情報とを記憶する記憶手段と、ナビゲーション装置における経路探索情報を受信する受信手段と、前記経路探索情報と前記追加地図情報に付属される情報との関係を判断する判断手段と、前記判断手段による判断の結果、前記経路探索情報に影響を与える前記追加地図情報を選択する選択手段と、前記ナビゲーション装置へ前記選択手段によって選択された前記追加地図情報を送信する送信手段と、を備えることを特徴とする。
【００１０】
本発明の請求項７に記載の地図情報処理装置の制御方法は、地図情報と追加地図情報とを記憶する記憶工程と、ナビゲーション装置における経路探索情報を受信する受信工程と、前記経路探索情報と前記追加地図情報に付属される情報との関係を判断する判断工程と、前記判断工程における判断の結果、前記経路探索情報に影響を与える前記追加地図情報を選択する選択工程と、前記ナビゲーション装置へ前記選択工程において選択された前記追加地図情報を送信する送信工程と、を備えることを特徴とする。
【００１１】
本発明の請求項８に記載の地図情報処理装置の制御プログラムは、地図情報処理装置に含まれるコンピュータを、地図情報と追加地図情報とを記憶する記憶手段、ナビゲーション装置における経路探索情報を受信する受信手段、前記経路探索情報と前記追加地図情報に付属される情報との関係を判断する判断手段、前記判断手段による判断の結果、前記経路探索情報に影響を与える前記追加地図情報を選択する選択手段、前記ナビゲーション装置へ前記選択手段によって選択された前記追加地図情報を送信する送信手段、として機能させることを特徴とする。
【発明を実施するための最良の形態】
【００１２】
次に、本願に最適な実施の形態について、図１乃至図８に基づいて説明する。図１（ａ）は、本実施形態に係わるナビゲーション装置および道路情報サーバ装置（地図情報処理装置、道路情報処理装置）を含む地図情報処理システムのシステム構成例である。図１（ｂ）は、本実施形態に係わるナビゲーション装置の内部ブロック構成例である。図１（ｃ）は、本実施形態に係わる道路情報サーバ装置の内部ブロック構成例である。
【００１３】
図２は、実施形態に係わる道路情報サーバ装置に記憶されている地図情報に
追加地図情報が追加記憶される様子を示した図である。
【００１４】
図３は、実施形態に係わる追加地図情報における新設道路の更新対象領域の一例を示す図である。
【００１５】
図４は、実施形態に係わる追加地図情報における新設道路の更新対象領域の作成方法をあらわすフローチャートである。
【００１６】
図５は、実施形態に係わるナビゲーション装置において、地図情報を基づいて経路探索を行なった状態を示す図である。
【００１７】
図６は、実施形態に係わる道路情報サーバ装置において、地図情報と追加地図情報に基づいて、経路探索を行なった状態を示す図である。
【００１８】
図７は、本実施形態に係わるナビゲーション装置および道路情報サーバ装置（道路情報処理装置）を含む地図情報処理システムにおけるシステムシーケンスを示す図である。
【００１９】
図８は、本実施形態に関わる、地図情報処理システムを用いて経路探索を行なった一例を示す図である。
【００２０】
最初に、図１（ａ）に基づいて、本実施形態に係わるナビゲーション装置１および道路情報サーバ装置２を含む地図情報処理システムのシステム構成例を説明する。
【００２１】
図１（ａ）に示すように、ナビゲーション装置１および道路情報サーバ装置２は通信回線網３を介して、相互に情報の送受信ができるように接続されている。ナビゲーション装置１は複数の移動体に搭載されており、随時、それらの移動体に搭載されたナビゲーション装置１と道路情報サーバ装置２との間で情報の送受信が行なわれている。
【００２２】
ナビゲーション装置１において経路探索が行なわれた結果が、通信回線網３を介して道路情報サーバ装置２に送信される。また、道路情報サーバ装置２は、ナビゲーション装置１において行なわれた経路探索の始点情報と終点情報に基づいて、道路情報サーバ装置２に記憶されている追加地図情報を含めて経路探索を行なう。その結果、道路情報サーバ装置２が経路探索に関連する追加地図情報をナビゲーション装置１に送付するべきであると判断した場合には、道路情報サーバ装置２は通信回線網３を介してナビゲーション装置１に、経路探索に関連する追加地図情報を送信する。
【００２３】
次に、図１（ｂ）に基づいて、本実施形態に係わるナビゲーション装置１の内部ブロック構成例について説明する。
【００２４】
本実施形態に係わるナビゲーション装置１は、記憶部４、表示部５、操作部６、位置検出部７、制御部８および送受信部９を備えている。
【００２５】
記憶部４には、ナビゲーション機能を発揮するための道路情報等の地図情報が記憶されている。地図情報には、必要に応じて道路情報サーバ装置２から送信される追加地図情報も含まれる。道路情報はＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disc）またはＨＤ（Hard Disc）等の記憶媒体に記憶されてユーザに供給される場合があり、記憶部４はこれらの記憶媒体も含む記憶装置である。一般的には、数年に一回程度すべての道路情報が更新された状態で、更新されたすべての道路情報が記憶されたＣＤ、ＤＶＤまたはＨＤ等の記憶媒体が、道路地図情報供給会社からユーザに供給される。また、道路情報が、道路情報サーバ装置２から供給される場合には、通信回線網３、送受信部９を介して記憶部４に記憶される。また、記憶部４は、制御部８の制御機能における一時記憶装置としての機能も有している。
【００２６】
位置検出部７は、移動体の位置が検出される部分である。例えば位置検出部７としては、ＧＰＳ（Global Positioning System）装置、方位センサー、傾斜センサー、スピードセンサー、移動時間を計測するタイマー、移動体である車両のウィンカー、アクセル操作、ブレーキ操作などの各種情報取得装置が使用される。
【００２７】
表示部５には、記憶部４に記憶された道路情報および道路情報サーバ装置２から送信された追加地図情報に基づいて道路等の情報および経路探索結果が表示される。また、位置検出部７において検出された移動体位置情報に基づいて、現在位置が道路情報に重ねて表示部５に表示される。表示部５に表示される移動体の位置情報は、位置検出部７から検出された情報に対して制御部８においてあらかじめ定められた処理が行なわれた後の処理情報が表示部５に表示される。また、位置検出部７から検出された情報がそのまま使用され、表示部５に表示される場合もある。
【００２８】
また、制御部８は、位置検出部７において検出された位置情報と、記憶部４に記憶された道路情報および道路情報サーバ装置２から送信された追加地図情報に基づき、道路情報に含まれる道路上に位置検出部７によって検出された移動体の位置を表示部５に表示する処理を行なう。
【００２９】
さらに、制御部８は、送受信部９を介して受信した追加地図情報を、記憶部４に記憶させる処理を行なう。
【００３０】
さらに、制御部８は、記憶部４に記憶された道路情報およびユーザが操作部６を介して指定した始点情報と終点情報とに基づき経路探索を行なう。経路探索結果は、送受信部９、通信回線網３を介して、道路情報サーバ装置２に送信される。また、道路情報サーバ装置２から送信される追加地図情報および記憶部４に記憶された道路情報を基づき経路探索を行なう。そして、制御部８は、追加地図情報を含めたコストが最も小さい経路探索結果を表示部５に表示させる。
【００３１】
さらに、制御部８は、記憶部４、表示部５、操作部６、位置検出部７、および送受信部９を統合的に制御する動作を行なう。
【００３２】
送受信部９は、道路情報および追加地図情報を道路情報サーバ装置２から受信する。
【００３３】
また、制御部５が経路探索した経路探索結果情報を、通信回線網３を経由して、道路情報サーバ装置２に対して送信する。そして、道路情報サーバ装置２は、通信回線網３を介して受信した、ナビゲーション装置２が経路探索した経路情報に基づいて更新有効範囲との照合を行なう。その結果、道路情報サーバ装置２は、ナビゲーション装置１の記憶部４に記憶されていない追加地図情報が経路探索に必要であると判断した場合（経路情報の全部又は一部が更新有効範囲と重なる場合）には、追加地図情報が道路情報サーバ装置２から、通信回線網３を介してナビゲーション装置２の送受信部９へ送信される。
【００３４】
操作部６には、ユーザが経路探索を行なう場合の始点情報と終点情報が入力される。また、ユーザがナビゲーション装置１の各種機能を発揮させるために操作するスイッチなどが設けられている。
【００３５】
次に、図１（ｃ）に基づいて、本実施形態に係わる道路情報サーバ装置２の内部ブロックについて説明する。
【００３６】
道路情報サーバ装置２は、記憶部１０、送受信部１１、操作部１２、および制御部１３を備えている。
【００３７】
記憶部１０には、各種の道路情報および図４の手順で作成された更新有効範囲リストと当該追加地図情報が記憶されている。追加地図情報には新設道路情報が含まれる。また、新設道路情報が既設の道路情報に追加された場合には、新設道路情報と既設道路情報との新たなノード情報も記憶部１０に記憶される。
【００３８】
これらの追加地図情報は、ナビゲーション装置１が搭載されている移動体において経路探索が行なわれ、その経路探索結果情報を道路情報サーバ装置２が受信した場合において必要に応じて各種移動体に送信される。また、操作部１２を介して、道路情報および追加地図情報が入力され、記憶部１０に記憶される。
【００３９】
送受信部１１は、ナビゲーション装置１において経路探索された経路探索結果情報の受信、および記憶部１０に記憶された追加地図情報を必要に応じて移動体に送信する。
【００４０】
操作部１２には、道路地図情報供給会社が道路情報サーバ装置２の各種機能を発揮するために操作するスイッチなどが備えられている。また、道路情報サーバ装置２には操作部１２を介して新設道路に関する情報および既設道路に関する新たな情報である追加地図情報が入力される。入力された追加地図情報は、記憶部１０に記憶される。
【００４１】
制御部１３は、記憶部１０、送受信部１１、および操作部１２を図７の１８〜２０の要領で制御する。また、移動体から送信された経路情報に基づいて、記憶部１０に記憶されている追加地図情報が経路探索に必要か否かを判断する。移動体で行なわれた経路探索に、移動体に搭載されているナビゲーション装置１の記憶部４に記憶されていない追加地図情報が必要であると、道路情報サーバ装置２の制御部１３が判断した場合には道路情報サーバ装置２の記憶部１０に記憶されている追加地図情報を、送受信部１１、通信回線網３を介してナビゲーション装置１に送信する機能を備えている。
【００４２】
次に、図２について説明する。
【００４３】
図２は、道路情報サーバ装置２の記憶部１０に記憶されている道路情報に追加地図情報としての新設道路ＳＤ１が追加記憶される様子を示した図である。
【００４４】
図２において従来の地図情報として、道路Ｌ１、道路Ｌ２、道路Ｌ３、道路Ｌ４、道路Ｌ５、道路Ｌ６、道路ノードＡ１、道路ノードＡ２、道路ノードＡ３、道路ノードＡ４、道路ノードＡ５、道路ノードＡ６、道路ノードＡ７、道路ノードＡ８、および道路ノードＡ８が記憶部１０に記憶されている。
【００４５】
新設道路ＳＤ１は、道路Ｌ１の道路ノードＡ１と道路ノードＡ４との間に接続している。この接続点を道路ノードＢ１として記憶部１０に記憶する。また、新設道路ＳＤ１は、道路Ｌ６の道路ノードＡ９と道路ノードＡ８との間に接続している。この接続点を道路ノードＢ２として記憶部１０に記憶する。
【００４６】
すなわち、道路ノードＡ１と道路ノードＡ４との間のリンクが、道路ノードＡ１と道路ノードＢ１とのリンクと道路ノードＢ１と道路ノードＡ４とのリンクとに分割される。また道路ノードＡ８と道路ノードＡ９との間のリンクが、道路ノードＡ８と道路ノードＢ２とのリンクと道路ノードＢ２と道路ノードＡ９とのリンクとに分割される。分割されたリンク情報も記憶部１０に記憶される。また、新設道路ＳＤ１には、道路ノードＢ１と道路ノードＢ２とが関連付けられる。
【００４７】
追加地図情報として、新設道路ＳＤ１と、新設道路ＳＤ１に関連付けされた道路ノードＢ１と道路ノードＢ２とが記憶部１０に記憶される。
【００４８】
次に、図３について説明する。
【００４９】
図３は、図２において道路情報サーバ装置２の記憶部１０に記憶された追加地図情報における新設道路ＳＤ１の関連領域Ｒ１（更新有効範囲）の範囲を示した図である。
【００５０】
図３において新設道路ＳＤ１の関連領域Ｒ１は斜線で図示されている部分である。関連領域Ｒ１は任意に設定することが可能である。ここでは、関連領域の設定方法
の一例を示す。
【００５１】
一例としての関連領域Ｒ１は、新設道路ＳＤ１の道路ノードＢ１を中心に半径Ｂ１Ｒで示される半円領域と、図３において新設道路ＳＤ１の上側と下側に平行な線分と道路ノードＢ２を中心に半径Ｂ２Ｒで示される半円領域とから構成されている。
【００５２】
新設道路ＳＤ１における道路ノードＢ１と道路ノードＢ２間の移動体の移動コストを新設道路移動コストＮＣとする。また道路ノードＢ１と道路ノードＢ２間において新設道路ＳＤ１を使用しないで移動体が移動した場合の移動コストを従来移動コストＮＮとする。道路ノードＢ１と道路ノードＢ２間において新設道路ＳＤ１を使用しないで移動体が移動する場合の移動系路の一例としては、道路ノードＢ１から、道路ノードＡ４、道路ノードＡ７、および道路ノードＡ８を介して、道路ノードＢ１に至る経路がある。
【００５３】
関連領域Ｒ１は、従来移動コストＮＮから新設道路移動コストＮＣを差し引いた量に比例する量とすることができる。
【００５４】
例えば、移動コストとして時間を考えた場合に、新設道路を移動体が予め定められた速度（一定速度ではなく速度は変化してもよい。）で移動した場合の新設道路移動コストＮＣに対応する時間が１時間で、従来道路を移動体が予め定められた速度（一定速度ではなく速度は変化してもよい。）で移動した場合の従来移動コストＮＮが３時間となった場合には、差し引き２時間に対応する量が関連領域Ｒ１の広さに対応する。差し引きの２時間を予め定められた速度で割り算した距離を半径Ｂ１Ｒおよび半径Ｂ２Ｒとすることができる。また、差し引きの２時間を予め定められた速度で割算した値に対して、予め定められた値を加減乗除等の演算をして調整を行なった値を関連領域Ｒ１とすることもできる。
【００５５】
また、関連領域Ｒ１（更新有効範囲）の決定はＡ／（新設道路移動コスト）ＮＣとすることもできる。Ａは定数である。新設道路移動コストＮＣが大きいほど移動時間が長くなるので、更新有効範囲は狭くなる。しかし、新設道路移動コストＮＣが小さいほど移動時間が短くなるので、更新有効範囲は大きく（広く）なる。新設道路によって移動体がスムーズに移動できるほど更新有効範囲は大きくなる。
【００５６】
さらに、新設道路が高速道路である場合には、新設高速道路の入口と出口ポイントのみを中心に更新有効範囲を設定することにしてもよい。例えば、一定半径の円が最も簡単な一例となる。また、新規高速道路の入口と出口ポイントに接続する従来道路のリンクコストに逆比例する形で、更新有効範囲の大きさを演算することもできる。  
【００５７】
さらに、新設道路（リンクコストＮＣ）に接続する道路（リンクコストＮＩ）に沿って、更新有効範囲を演算する。例えば、Ａ／（ＮＣ＊ＮＩ）またはＡ／（ＮＣ＋ＮＩ）などのように新設道路とそれに接続する道路のリンクコストの双方に逆比例する形式で値を求めると、求められた値が新設道路に接続する道路の更新有効範囲となる。
【００５８】
さらに、新設道路の道路種別（例えば、道路幅、車線数、制限速度、高速道路であるか否か、有料道路であるか否か、国道であるか否か）に基づいて更新有効範囲の大きさを決定する、または新設道路の道路種別に基づいて予め定められた係数を掛けることによって有効更新範囲の大きさに変化をつけることができる。さらに、新設道路の道路種別に基づいて予め定められた係数は、その道路の渋滞状況など、時間と共に変化する動的な状況に対応して変化する値に設定されることが可能である。さらに、それらの時間とともに変化する状況に対応して、サーバ側で係数の再計算をする事が可能であり、サーバ側の再計算の結果に基づいてサーバが係数を再設定することが可能である。
【００５９】
さらに、更新有効範囲を２次元的に設定せずに、従来道路に沿って更新有効範囲を設定することもできる。
【００６０】
新設道路に接続される従来道路を移動コストに従って、予め選別・リスト化しておいて、選別リストの道路とユーザの経路とが一致するか否かを判断することもできる。
【００６１】
次に図４を用いて、新設道路が設定される場合における新設道路毎の更新有効範囲を演算するフローチャートの一例について説明する。この演算は、道路情報サーバ装置２の制御部１３で行なわれ、道路情報サーバ装置２の記憶部１０に記憶される場合がある。また、予め道路情報サーバ装置２の外部で図４の手順で演算された更新有効範囲データが、道路情報サーバ装置２の操作部１２が操作されることによって、道路情報サーバ装置２の記憶部１０に記憶される場合もある。
【００６２】
ステップＳ１において、道路情報サーバ装置２に新設道路情報を操作部１２等の入力部を介して入力し、記憶部１０に記憶する。次にステップＳ２に進む。
【００６３】
ステップＳ２において、道路情報サーバ装置２の制御部１３は新設道路カウンタIを０に初期化する。次にステップＳ３に進む。
【００６４】
ステップＳ３において、制御部１３は記憶部１０に記憶されている新設道路Ｎ（Ｉ）の情報を抽出し新設道路Ｎとする。次にステップＳ４に進む。
【００６５】
ステップＳ４において、制御部１３は、新設道路が追加地図情報として記憶される前の地図データを記憶部１０から抽出する。制御部１３は、抽出された地図データにBefore Mapという名称をつける。次にステップＳ５に進む。
【００６６】
ステップＳ５において、制御部１３は、新設道路Ｎの一端を出発地点Before Nsとし、反対の一端を目標地点Before Nｇとする。次にステップＳ６に進む。
【００６７】
ステップＳ６において、制御部１３は、更新前の地図データを用いて出発地点Before Nsから目標地点Before Nｇまでの経路探索を行ない、更新前の地図データにおける出発地点Before Nsから目標地点Before Nｇまでの移動コストＮＮＣの演算を行なう。次にステップＳ７に進む。
【００６８】
ステップＳ７において、制御部１３は、新設道路が追加地図情報として記憶されている更新後の地図情報を記憶部１０から抽出する。制御部１３は、抽出された地図データにNew Mapという名称をつける。次にステップＳ８に進む。
【００６９】
ステップＳ８において、制御部１３は、新設道路Ｎの一端を出発地点Nsとし、出発地点Nsと反対の一端を目標地点Nｇとする。次にステップＳ９に進む。
【００７０】
ステップＳ９において、制御部１３は、抽出された地図データであるNew Mapを用いて出発地点Nsから目標地点Nｇまでの経路探索を行ない、出発地点Nsから目標地点Nｇまでの移動コストＮＣの演算を行なう。次にステップＳ１０に進む。
【００７１】
ステップＳ１０において、新設道路を含まない移動コストＮＮＣから新設道路を含む移動コストＮＣを減算し、減算結果をＮＮＸとする。次にステップＳ１１に進む。
【００７２】
ステップＳ１１において、新設道路の各ノードＮＮを中心にＮＸを加算演算し、更新有効範囲を設定する。例えば、新設道路のノード１をＮ１とすると、Ｎ１からＮＸの距離が更新有効範囲となる。次にステップＳ１２に進む。
【００７３】
ステップＳ１２において、制御部１３はステップＳ１０において演算された演算結果ＮＮＸを記憶部１０に記憶された有効範囲判定リストに追加する。制御部１３はステップＳ１３においてインクリメントされるＩごとに有効範囲判定リストＮＮＸＬｉｓｔ（Ｉ）に演算結果ＮＮＸを記録し、記憶部１０に記憶する。次にステップＳ１３に進む。
【００７４】
ステップＳ１３において、新設道路カウンタを１つインクリメントする。次にステップＳ１４に進む。
【００７５】
ステップＳ１４において、新設道路の全てについて更新有効範囲が設定されたか否かが判断される。新設道路の全てについて更新有効範囲が設定された場合（ステップＳ１４：ＹＥＳ）の場合には処理を終了する。新設道路の全てについて更新有効範囲が設定されていない場合（ステップＳ１４：ＮＯ）には、ステップＳ３に進む。
【００７６】
以上の動作フローに基づいて、道路情報サーバ装置２において、新設道路の全てについて更新有効範囲が設定される。
【００７７】
次に、図５を用いて、ナビゲーション装置１において、制御部８が地図情報に新設道路が追加地図情報として記憶部４に記憶されていない状態における記憶部４の地図情報を用いて、図２における領域において経路探索を行なった結果を図示する。
【００７８】
出発地点Ｓは、道路Ｌ６上の地点で、到着地点Ｇは道路Ｌ９上の地点である。経路探索の結果である経路は経路Ｋ１で示されている。経路Ｋ１は道路Ｌ６上の出発地点Ｓから道路ノードＡ１、道路ノードＡ４、道路ノードＡ７、道路ノードＡ８および道路ノードＡ９を介して到着地点Ｇへ至る経路である。
【００７９】
ナビゲーション装置１は、図５において経路探索された経路Ｋ１が最も移動コストが小さいか否かを確認するために、経路Ｋ１に関する経路探索情報を送受信部９を介して、道路情報サーバ装置２へ送信する。
【００８０】
経路Ｋ１に関する経路探索情報を送受信部９を介して受信した道路情報サーバ装置２は、経路１に新設道路を考慮した関連領域Ｒ１と重なる部分があるか否かを判断する。経路１に新設道路を考慮した関連領域Ｒ１と重なる部分がある場合には、道路情報サーバ装置２は、記憶部１０に記憶されている関連領域R1の新設道路情報を送受信部９を介してナビゲーション装置１に送信する。経路１に新設道路を考慮した関連領域Ｒ１と重なる部分がない場合には、道路情報サーバ装置２は、更新情報無しという結果情報を送受信部９を介してナビゲーション装置１に送信する。
【００８１】
ナビゲーション装置１における制御部８が、追加地図情報を加えて、経路を探索する手順を図６に示す。
【００８２】
図６は、新規道路ＳＤ１の関連領域Ｒ１である有効更新範囲に、図５においてナビゲーション装置１が選択した探索経路Ｋ１が含まれていることを示した図である。
【００８３】
図６において、探索経路Ｋ１の一部に該当する道路ノードＢ１から道路ノードＡ４に至る経路が関連領域Ｒ１と重なっているので、制御部８は、移動体によって設定された出発地点Ｓから到着地点Ｇまでに至る経路における経路探索において関連領域Ｒ１に関わる新設道路ＳＤ１を利用して経路探索を実行する。探索経路Ｋ１の一部が関連領域Ｒ１と重なっていない場合には、道路情報サーバ装置２から追加地図情報がナビゲーション装置１には送信されないので、制御部８は、関連領域Ｒ１に関わる新設道路ＳＤ１を移動体によって設定された出発地点Ｓから到着地点Ｇまでに至る経路において使用できるか否かを判断しない。この場合には、道路情報サーバ装置２は、更新データがないことをナビゲーション装置１に送信している。従って、制御部８は、経路探索において新設道路ＳＤ１を使用できるか否かは初めから検討しない。その結果、ナビゲーション装置１の制御部８は、経路Ｋ１をナビゲーション装置１の表示部５へ表示する。
【００８４】
本実施形態の場合には、探索経路Ｋ１の一部に該当する道路ノードＢ２から道路ノードＡ８に至る経路も関連領域Ｒ１と重なっているので、制御部８は、移動体によって設定された出発地点Ｓから到着地点Ｇまでに至る経路において、関連領域Ｒ１に関わる新設道路ＳＤ１を利用して経路探索を実行する。
【００８５】
制御部８は、道路ノードＡ７が、道路ノードＢ１から道路ノードＡ４の延長線上にあるとともに、道路ノードＢ２から道路ノードＡ８の延長線上にもあることを認識する。従って、制御部８は、道路ノードＢ１から、道路ノードＡ７を介して、道路ノードＢ２に至る経路が従来道路によって経路探索された経路探索結果Ｋ１の一部分であることを認識する。
【００８６】
そこで、制御部８は、道路ノードＢ１から、道路ノードＡ４、道路ノードＡ７、道路ノードＡ８を介して、道路ノードＢ２に、従来道路を利用して移動体が移動した場合の移動コストを計算しながら経路探索をする。また、制御部８は、移動体が道路ノードＢ１から道路ノードＢ２に新設道路ＳＤ１を利用して移動する場合の移動コストを演算しながら経路探索をする。制御部８が経路探索をする場合の経路はこれらに限られるわけではなく、追加地図情報が加えられた地図情報に基づいて、移動体が移動できる経路の全てについて移動コストを計算しつつ最適な経路を求めるための経路探索を行なう。
【００８７】
その結果、本実施形態においては、新設道路ＳＤ１を利用して道路ノードＢ１から道路ノードＢ２へ至る経路を使用すると移動コストが最も小さい（移動距離が短い等）ので、ナビゲーション装置１において、追加地図情報が道路情報サーバ装置２から送信される前に求められた道路Ｌ６上の出発地点Ｓから道路ノードＡ１、道路ノードＡ４、道路ノードＡ７、道路ノードＡ８および道路ノードＡ９を介して到着地点Ｇへ至る経路Ｋ１よりも、新設道路を使用した道路Ｌ６上の出発地点Ｓから道路ノードＡ１、道路ノードＢ１、道路ノードＢ２、および道路ノードＡ９を介して到着地点Ｇへ至る経路Ｋ２を選択するべきことをナビゲーション装置１の制御部８は判断する。
【００８８】
その結果、ナビゲーション装置１の制御部８は、経路Ｋ２をナビゲーション装置１の表示部５へ表示する。従って、ナビゲーション装置１の表示部５には、経路Ｋ１は一度も表示されない。このようにして、常に新設道路を考慮した最適な経路が、ナビゲーション装置１のユーザに提供されることになる。
【００８９】
次に図７について説明する。
【００９０】
図７は、図２乃至図６において説明した各部分の動作をシステムシーケンスとして表した図である。
【００９１】
図７における横軸の上段左側からエンドユーザの動作１４、ナビゲーション装置１における経路探索１５、ナビゲーション装置１における地図情報１６、道路情報サーバ装置２における地図情報の更新１７、道路情報サーバ装置２における地図情報の更新１８、道路情報サーバ装置２における更新有効範囲の処理１９、および道路情報サーバ装置２における追加地図情報２０を示している。
【００９２】
図７のステップＳ２０において、エンドユーザがナビゲーション装置１に対して、最短距離となる経路探索指示を行なう。
【００９３】
ステップＳ２１において、ナビゲーション装置１の制御部８は経路探索に必要な地図情報をナビゲーション装置１の記憶部４に要求する。
【００９４】
ステップＳ２２において、ナビゲーション装置１の制御部８は、ナビゲーション装置１の記憶部４から経路探索に必要な地図情報を抽出する。
【００９５】
ステップＳ２３において、ナビゲーション装置１の制御部８は、経路探索のために経路演算を行い、経路を算出する。
【００９６】
ステップＳ２４において、ステップＳ２３において算出された経路をカーナビゲーション装置１における経路候補とする。
【００９７】
ステップＳ２５において、カーナビゲーション装置１は、道路情報サーバ装置２に対して、ステップＳ２３において算出された経路とともに、最新の新設道路等の地図情報を問い合わせる。
【００９８】
ステップ２６において、道路情報サーバ装置２の制御部１３は、新設道路に伴う更新有効範囲リストを道路情報サーバ装置２の記憶部１０に要求する。
【００９９】
ステップＳ２７において、道路情報サーバ装置２の記憶部１０から、新設道路に伴う更新有効範囲リストが道路情報サーバ装置２の制御部１３に送られる。
【０１００】
ステップＳ２８において、道路情報サーバ装置２の制御部１３は、ステップ２３において経路探索された経路の全部または一部が新設道路に伴う更新有効範囲リストと重なるか否かを判断する。
【０１０１】
ステップＳ２９において、経路探索データと更新有効範囲リストとで重なる部分がある場合には、道路情報サーバ装置２の制御部１３は、更新有効範囲リストに対応する新設道路に関わる追加地図情報を、道路情報サーバ装置２の記憶部１０に要求する。経路探索データと更新有効範囲リストとで重なる部分がない場合には、道路情報サーバ装置２の制御部１３は、更新データがないことを送信して終了する。  
【０１０２】
ステップＳ３０において、更新有効範囲リストに対応する新設道路に関わる追加地図情報が、道路情報サーバ装置２の記憶部１０から道路情報サーバ装置２の制御部１３に送られる。
【０１０３】
ステップＳ３１において、更新有効範囲リストに対応する新設道路に関わる追加地図情報が道路情報サーバ装置２からナビゲーション装置１に送られる。
【０１０４】
ステップＳ３２において、更新有効範囲リストに対応する新設道路に関わる追加地図情報がナビゲーション装置１の記憶部４に更新記憶される。
【０１０５】
ステップＳ３３において、ナビゲーション装置１は、更新された追加地図情報を含む地図情報に基づいて経路探索を開始する。
【０１０６】
ステップＳ３４において、ナビゲーション装置１の制御部８は、ナビゲーション装置１の記憶部４に対して経路探索の計算に用いられる追加地図情報を含む地図情報を要求する。
【０１０７】
ステップＳ３５において、ナビゲーション装置１の記憶部４から、経路探索の計算に用いられる追加地図情報を含む地図情報がナビゲーション装置１の制御部８に送られる。
【０１０８】
ステップＳ３６において、ナビゲーション装置１の制御部８は、更新された追加地図情報を含む地図情報に基づいて経路探索をする。
【０１０９】
ステップＳ３７において、ステップＳ３６において行なわれた経路探索結果に基づいて、最短経路をナビゲーション装置１の表示部５に表示してエンドユーザに知らせる。
【０１１０】
次に図８について説明する。
【０１１１】
図８は、東京湾に設けられたアクアラインを新設道路情報として、本願の発明を適用した一実施例を示す図である。
【０１１２】
図８（ａ）は、アクアラインを新設道路情報として登録する前のナビゲーション装置１における経路探索結果を示している。出発点Ｓは川崎市で到着点Ｇは木更津市である。図８（ａ）における経路Ｋ３は、東京都内を通過し、千葉県の市川市、千葉市、市原市を経由して到着点Ｇである木更津市に到着する経路が示されている。この経路Ｋ３は東京湾に沿って移動体が移動するので、かなり遠回りになるため出発点Ｓである川崎市から到着点Ｇである木更津市に到達するまでにかなり多くの時間を要していた。
【０１１３】
一方図８（ｂ）は、アクアライン（ＩＣ１からＩＣ２に至る道路）を新設道路情報としての追加地図情報として従来の地図情報に追加して経路探索した結果と、アクアラインの関連領域Ｒ２である有効更新範囲を示した図である。
【０１１４】
ＩＣ１からＩＣ２に移動体が移動する場合にアクアラインを使用しない場合（図８（ａ））と、アクアラインを使用する場合（図８（ｂ））とでは、移動時間が大きく異なるので、アクアラインを使用して経路探索をすることが有効だと考えられる範囲はかなり広い範囲となる。従って、図８（ｂ）に示される関連領域Ｒ２はアクアライン（ＩＣ１からＩＣ２に至る道路）に沿ってかなり広範囲に設定されている様子が分かる。また、本実施形態に関わる出発点Ｓである川崎市から到着点Ｇである木更津市に至る経路探索の結果であるＫ３の一部が関連領域Ｒ２と重なっていることが示されている。  
【０１１５】
Ｋ３の一部が関連領域Ｒ２と重なっている結果、新設道路であるアクアラインを道路情報サーバ装置２から追加地図情報として、ナビゲーション装置１の記憶部４に更新登録して、ナビゲーション装置１において出発点Ｓである川崎市から到着点Ｇである木更津市に至る経路探索を、再度実行する。その結果、経路Ｋ４が移動コストが最も小さい経路としてナビゲーション装置１の表示部５に表示された結果が図８（ｂ）に表示されている図である。
【０１１６】
（変形例）
以上の実施形態においては、追加地図情報として新設道路が設けられる場合について述べてきた。しかし、実際には従来道路が閉鎖される場合など、従来道路の一部が地図情報から削除される場合もある。以下に、従来道路の一部が削除される場合（この場合の地図情報を、削除地図情報または追加地図情報（追加地図情報には、新設道路に係わる情報と削除道路に係わる情報とが含まれる。）と称する。）について各構成要素の動作について説明する。
【０１１７】
道路情報サーバ装置２の記憶部１０に従来道路の一部が削除された情報が操作部１２を介して入力される。
【０１１８】
道路情報サーバ装置２の制御部１３は、削除された道路について更新有効範囲（関連領域）を設定する。更新有効範囲は、新設道路が設けられた場合の更新有効範囲と同様の手法によって求められる他、任意に設定することができる。
【０１１９】
道路情報サーバ装置２の制御部１３は、ナビゲーション装置１から送信される経路情報の一部または全部が、削除された道路に係わる更新有効範囲と重なるか否かを判定する。
【０１２０】
ナビゲーション装置１から送信される経路情報の一部または全部が、削除された道路に係わる更新有効範囲と重なると道路情報サーバ装置２の制御部１３が判断した場合には、制御部１３は従来道路の一部が削除されている情報を送受信部１１を介して、ナビゲーション装置１に対して送信する。
【０１２１】
ナビゲーション装置１は、送受信部９を介して従来道路の一部が削除されている情報を受信する。そして、ナビゲーション装置１の制御部８は、記憶部４に記憶されている地図情報を、受信した従来道路の一部が削除されている情報を基に更新する。更新された地図情報には、削除されるべき従来道路の一部の情報が削除されている。制御部８は更新された地図情報を記憶部４に記憶する。
【０１２２】
ナビゲーション装置１の制御部８は、更新された地図情報に基づいて、従来道路の一部が削除されている情報を受信する前に経路探索をした出発地点と目標地点について、再び経路探索をする。
【０１２３】
ナビゲーション装置１の制御部８は、通常、最も移動コストが小さくなるような経路を探索するように、経路探索をする。
【０１２４】
ナビゲーション装置１の制御部８は、再経路探索結果である経路情報を表示部５に表示する。
【０１２５】
従って、ナビゲーション装置１の表示部５には、経路Ｋ１は一度も表示されない。このようにして、常に削除された道路情報を考慮した最適な経路が、ナビゲーション装置１のユーザに提供されることになる。
【０１２６】
なお、図２乃至図７における動作手順および変形例に係わる動作手順を、ハードディスク等の記録媒体に予め記録しておき、或いはインターネット等のネットワークを介して予め記録しておき、これを汎用のマイクロコンピュータ等により読み出して実行することにより、当該汎用のマイクロコンピュータ等を実施形態に係わるＣＰＵとして機能させることも可能である。
【０１２７】
以上述べてきたように本実施形態によれば、サーバに新規道路をメンテナンスする場合に、新設道路の影響エリアを設定することで、経路計算結果が影響エリアの範囲内であれば経路計算に影響がある道路として選別することができる。また、選別された道路だけをオブジェクト単位で更新することで、更新データ量も最小にすることができる。
【０１２８】
また、クライアント（ユーザおよびエンドユーザ等）が用いているナビゲーション装置において経路探索計算を行なった場合に、その結果を直ちに、表示部に表示するなどしてクライアントに知覚させずに、サーバ装置に経路探索計算結果を送信する。サーバ装置において、道路の更新情報が必要か否かの判定処理を行なった後に、道路の更新情報が必要であると判断された場合に、クライアントのナビゲーション装置に更新情報を送信する。更新情報を受け取ったナビゲーション装置は、更新情報に含まれる道路情報に基づいて、経路計算を再度実施して経路探索結果を表示部に表示し、または音声で案内する等してクライアントに知覚させることができる。
【０１２９】
従って、常に最新の地図データに基づいて、経路計算結果をクライアントは知ることができる。また、経路計算に影響度の大きい道路が更新されるので、次回以降の経路探索計算にも有効となる可能性が高くなるという効果を有する。
【０１３０】
また、本願によれば、更新結果を発揮する最小リンク・オブジェクトの更新だけで済むので、通信コストや通信トラフィックの不必要な増加を抑止することが可能となった。また、通信が不通になってしまった場合であっても、クライアントのナビゲーション装置において経路探索が可能であり、クライアントのナビゲーション装置においてトランザクションを残しておけば通信が可能になり次第、サーバ装置との間で再更新することも可能となる。
【０１３１】
また、新設道路を含まない地図情報に基づいて経路探索を行なった場合において、経路探索結果情報に新設道路の道路ノードが含まれない場合においても、新設道路の有効更新範囲が経路探索結果情報の経路の一部と重なれば、新設道路を含む追加地図情報が、道路情報サーバ装置２からナビゲーション装置１に送信されるという効果を有する。すなわち、基幹道路に接続されていない新設道路が更新されにくくなる状態がなくなるので、より効率的な新設道路を含む追加地図情報の更新を行なうことができるようになった。
【０１３２】
また、地図データの更新において、経路探索結果に影響を与える最小限の範囲について、ナビゲーション装置に対して更新地図データを追加することができる。また、更新すべき道路情報の選別や経路計算を効率的に処理することが可能となった。
【図面の簡単な説明】
【０１３３】
【図１】（ａ）は、本実施形態に係わるナビゲーション装置および道路情報サーバ装置（道路情報処理装置）を含む地図情報処理システムのシステム構成例である。（ｂ）は、本実施形態に係わるナビゲーション装置の内部ブロック構成例である。（ｃ）は、本実施形態に係わる道路情報サーバ装置の内部ブロック構成例である。
【図２】は、実施形態に係わる道路情報サーバ装置に記憶されている地図情報に追加地図情報が追加記憶される様子を示した図である。
【図３】は、実施形態に係わる追加地図情報における新設道路の更新対象領域の一例を示す図である。
【図４】は、実施形態に係わる追加地図情報における新設道路の更新対象領域の作成方法をあらわすフローチャートである。
【図５】は、実施形態に係わるナビゲーション装置において、地図情報を基づいて経路探索を行なった状態を示す図である。
【図６】は、実施形態に係わる道路情報サーバ装置において、地図情報と追加地図情報に基づいて、経路探索を行なった状態を示す図である。
【図７】は、本実施形態に係わるナビゲーション装置および道路情報サーバ装置（道路情報処理装置）を含む地図情報処理システムにおけるシステムシーケンスを示す図である。
【図８】は、本実施形態に関わる、地図情報処理システムを用いて経路探索を行なった一例を示す図である。
【符号の説明】
【０１３４】
１…ナビゲーション装置
２…道路情報サーバ装置
３…通信回線網
４、１０…記憶部、記憶部
５…表示部
６、１２…操作部
７…位置検出部
８、１３…制御部
９、１１…送受信部
【図１】
2008032644.tif 000003
【図２】
2008032644.tif 000004
【図３】
2008032644.tif 000005
【図４】
2008032644.tif 000006
【図５】
2008032644.tif 000007
【図６】
2008032644.tif 000008
【図７】
2008032644.tif 000009
【図８】
2008032644.tif 000010