JP7064463B2 - ルート関連情報取得装置およびルート関連情報取得方法 - Google Patents

Description

この発明は、ルート探索により得られたルートに含まれる所定区間に関する関連情報を、ネットワーク上の他の装置から取得できるようにする装置、方法に関する。

例えば、携帯端末を通じていわゆるナビゲーションサービスを提供する場合などにおいては、複数の第三者ウェブサーバ装置または外部データベース装置などの外部装置から取得される経路情報（ルート情報）をユーザに提供することがある。このような場合、複数の第三者ウェブサーバ装置または外部データベース装置などの外部装置から取得される経路情報は、異なる地図情報及び異なる交通情報に基づいて、異なるアルゴリズムを用いて探索を行うことによって生成されたものである可能性がある。このため、ユーザが複数の経路情報を単純に比較することができないという問題がある。

このため、後に記す特許文献１には、複数の第三者ウェブサーバ装置または外部データベース装置などの外部装置から取得される複数の情報を公平に比較して評価することができる経路評価装置等に関する発明が開示されている。特許文献１に開示された経路評価装置は、以下のように動作する。まず、経路情報取得部によって、各外部データベース装置から、経路の出発地から目的地までの経由地に関する経路情報を含む経路情報を取得する。次に、取得された各経路情報を、経路再現部によって、経路評価装置の内部で使用される形式で再現する。次に、評価基準記憶部に記憶される評価基準に基づいて、経路評価部によって、経由情報で表される経由地を含む経路に関する時間および距離を計算することで評価結果を生成して、経路情報を評価する。そして、生成された評価結果を表示部に表示するように、表示制御部によって表示部を制御するようにしている。

国際公開第２０１７／０１０１４３号

近年、ＡＰＩ（Application Programming Interface）技術の進歩に伴い、例えば、自社のルート探索エンジンを用いて探索したルートの所定区間に関する情報を、他社の情報提供装置から取得することが考えられる。一例を挙げると、例えば、自社のルート探索エンジンを用いて探索したルートの有料道路区間についてのＥＴＣ（Electronic Toll Collection System）割引考慮料金を、他社の情報提供装置から取得したいとする要求がある。ＥＴＣ割引考慮料金は、時間帯、曜日、地方、自動車種別などの種々の条件によって異なる複雑なものである。このため、算定に必要なデータの提供を受けて自社で算定システムを構築するよりも、他社が既にＥＴＣ割引考慮料金の算定システムを構築済みであり、これを公開している場合には、当該算定システムを利用した方が便利である。

また、自社のルート探索エンジンを用いて探索したルートの高速道路利用区間についての所定の電気自動車の電気消費量を、他社の情報提供装置から取得したいとする要求がある。この他にも、自社のルート探索エンジンを用いて探索したルートの山間部における所定のガソリン自動車の二酸化炭素排気量やガソリン消費量を、他社の情報提供装置から取得したいとする要求など、種々の要求が存在する。これらの場合にも、必要データの提供を受けて、独自に算定システムを開発するよりも、他社が既に当該算定システムを構築済みであり、これを公開している場合には、当該算定システムを利用した方が、開発コストを削減し、利用者にも適切な情報を提供できる。

そして、自社のルート探索エンジンを用いて探索したルートの所定区間に関する情報を、他社の情報提供装置から取得しようとする場合、当該所定区間を他社の情報提供装置でも正確に特定できなければならない。しかしながら、上述した特許文献１にも記載されているように、自社のルート探索エンジンと、他社のルート探索エンジンとでは、一般に、使用する地図情報や探索アルゴリズムが異なる。このため、単に出発地と目的地との２点を用いてルート探索を行うようにした場合、自社のルート探索エンジンでの探索結果と、同一の探索結果を他社のルート探索エンジンでは得られない場合がある。この場合に、例えば、自社のルート探索エンジンで探索したルートの有料道路区間についてのＥＴＣ割引考慮料金の提供を受けたい場合でも、自社のルート探索エンジンでの探索結果に即したものではないため、正確なＥＴＣ割引考慮料金の提供を受けられない。

このため、自社のルート探索エンジンでの探索結果を、探索されたルート上の緯度、経度で示される多数の点を羅列した点列情報を形成し、これを他社のルート探索エンジンに提供して、ルート探索結果の再現率を向上させることが考えられる。しかし、当該点列情報の点の数が多いほど、他社のルート探索エンジンでの処理時間は長くなり、迅速は情報の提供を受けられない。また、他社のルート探索エンジンの負荷も大きくなるため、多くの利用者からの情報提供要求に対応しきれなくなる可能性もある。

以上のことに鑑み、この発明は、自機で特定した処理対象区間と、同じ処理対象区間を他の装置でも特定（再現）できるように情報提供し、当該処理対象区間に関する適切な関連情報を当該他の装置から得られるようにすることを目的とする。

上記課題を解決するため、この発明のルート関連情報取得装置は、
出発地と目的地とを含むルート探索要求に応じて、ルート探索用データを参照し、ルート探索を行って、出発地から目的地までのルート上の緯度、経度により示される点情報の集まりである点列情報を含む探索結果を形成するルート探索手段と、
前記ルート探索手段で形成された前記点列情報の各点情報が示す道路の種別情報に基づいて、探索されたルート上の目的とする関連情報の取得対象区間を特定する特定手段と、
前記特定手段で特定された前記取得対象区間の前記点列情報について、各点情報が示す位置の道路の属性情報を参照し、同じ属性情報を有する道路の点情報については、最初の点情報を残して他の点情報を間引き、間引き後データを形成する第１の間引き処理手段と、
前記間引き後データを含む関連情報提供要求を形成して、所定の関連情報提供装置に提供する提供要求形成手段と、
前記関連情報提供装置から提供される前記関連情報提供要求に応じた関連情報を取得する関連情報取得手段と
を備えることを特徴とする。

この発明によれば、関連情報の取得対象区間を相手先の機器でも特定可能なように、当該取得対象区間の点列情報を必要な程度間引くようにして形成した間引き後データを含む関連情報提供要求を関連情報提供装置に送信できる。これにより、取得対象区間を関連情報提供装置側で適切に再現し、当該取得対象区間に関する関連情報を適切に把握して、これを要求元に提供できる。すなわち、迅速に、かつ、関連情報提供装置の負荷を増大させることなく、取得対象区間に関する適切な関連情報を当該関連情報提供装置から提供を受けることができる。

ルート関連情報取得装置の一実施の形態であるナビゲーションサービスサーバを含む情報提供システムの構成例について説明するための図である。 ルート関連情報取得装置の一実施の形態であるナビゲーションサービスサーバの構成例を説明するためのブロック図である。 道路ネットワークデータベースの格納データの例を説明するための図である。 所定の矩形領域を単位として形成される道路ネットワークデータベースについての当該矩形領域について説明するための図である。 矩形領域のサイズの例について説明するための図である。 高速道路データフレームの格納データの例を説明するための図である。 探索結果データファイルの格納データの例を説明するための図である。 提供要求データファイルの格納データの例を説明するための図である。 対象区間特定部で行われる処理を説明するための図である。 第１の間引処理部で行われる処理を説明するための図である。 第２の間引処理部で行われる処理を説明するための図である。 実施の形態のナビゲーションサービスサーバで行われる処理を説明するためのフローチャートである。 図１２に続くフローチャートである。

以下、図を参照しながら、この発明の装置、方法の一実施の形態について説明する。この発明の装置、方法は、自機のルート探索エンジンを用いて探索したルートの所定区間に関する情報を、外部の情報提供装置から取得する種々の場合に適用できるものである。以下においては、説明を簡単にするため、この発明の装置、方法を、ナビゲーションサービスサーバに適用し、自機のルート探索エンジンで探索したルートの有料道路区間のＥＴＣ割引考慮料金を、外部の情報提供サーバから提供を受ける場合を例にして説明する。

［ナビゲーションサービスサーバを含む情報提供システムの構成例］
図１は、ルート関連情報取得装置の一実施の形態であるナビゲーションサービスサーバを含む情報提供システムの構成例について説明するための図である。図１に示すように、この実施の形態の情報提供システムは、ナビゲーションサービスサーバ１と、ルート関連情報提供サーバ２と、携帯端末４（１）、４（２）、…とが、ネットワーク３を介して相互に通信可能なように接続されて構成されている。

ネットワーク３は、主にインターネットであるが、各装置からインターネットまでを繋ぐ携帯電話網、電話網、ＬＡＮ（Local Area Network）や無線ＬＡＮなどをも含む。図１において、参照符号３Ｂ（１）、３ｂ（２）、…は、例えば、携帯電話網の基地局や無線ＬＡＮのアクセスポイントである。また、以下においては、説明を簡単にするため、「ナビゲーションサービスサーバ１」は、「ナビサーバ１」と記載し、「ルート関連情報提供サーバ２」は、「提供サーバ２」と記載する。

携帯端末４（１）、４（２）、…のそれぞれは、スマートフォンなどと呼ばれる高機能携帯電話端末やタブレットＰＣ（Personal Computer）などの既に広く一般に用いられているものである。携帯端末４（１）、４（２）、…のそれぞれは、ＧＰＳ（Global Positioning System）機能を備え、ナビサーバ１からナビゲーション用アプリケーションソフトウェア（ナビアプリ）の提供を受けて、インストールを済ませているものである。

携帯端末４（１）、４（２）、…のそれぞれは、ナビアプリを起動し、目的地、出発地、必要な場合には経由地を入力して、これをナビサーバ１に送信してルート探索を要求し、ルート探索結果と地図情報の提供を受けることができる。携帯端末４（１）、４（２）、…のそれぞれは、ナビアプリの機能により、提供を受けたルート探索結果と地図情報とを利用し、地図上に辿るべきルートと自機の現在位置を表示し、音声案内によって出発地から目的地へのルート案内を行うことができる。なお、携帯端末４（１）、（２）、…には種々のものがあるが、実現される機能は同様のものである。このため、以下においては、携帯端末４（１）、（２）、…を総称して携帯端末４と記載する。

ナビサーバ１は、上述したように、要求元の携帯端末４に対してルート探索結果や地図情報を提供する機能を実現するが、それだけではない。この実施の形態のナビサーバ１は、ルート探索により得られたルート（ルート探索結果）の内の有料道路区間について、通常の利用料金やＥＴＣ割引考慮料金についても、携帯端末４の使用者に提供する機能を備える。ただし、ＥＴＣ割引考慮料金については、外部のサーバである提供サーバ２から取得するための機能を備えている。

提供サーバ２は、外部のサーバであるためその構成の詳細は種々考えられる。しかし、提供サーバ２は、基本的な機能として、以下の機能を有する。提供サーバ２は、ナビサーバ１などの他のサーバからの有料道路区間を特定（再現）するための緯度、経度により示される点情報の集まりである点列情報の提供を受けて、当該点列情報に基づき、有料道路区間を特定（再現）する機能を有する。提供サーバ２は、特定した有料道路区間についてのＥＴＣ割引考慮料金を算定し、算定結果を要求元の他のサーバに返信する機能を有する。

このため、ナビサーバ１は、自機においてのルート探索結果に含まれる有料道路区間を特定できるようにするための情報であって、当該有料道路上の緯度、経度により示される点情報の集まりである点列情報を形成し、これを提供サーバ２に提供する。ナビサーバ１は、特に重要な機能として、提供サーバ２において、負荷を増大させることなく、かつ、迅速な処理を可能にするため、当該点列情報を有料道路区間の再現率を低下させることがない範囲で、できるだけ少ない点情報の集まりとして形成する。以下に、ナビサーバ１の構成例と、ナビサーバ１で行われる処理について、詳細に説明する。

［ナビサーバ１の構成例］
図２は、ナビサーバ１の構成例を説明するためのブロック図である。接続端１０１Ｔ及び通信Ｉ／Ｆ１０１は、ネットワーク３を通じての通信機能を実現する。制御部１０２は、図示しないが、ＣＰＵ（Central Processing Unit）、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、不揮発性メモリが接続されて構成されたマイクロプロセッサである。制御部１０２は、種々のプログラムを実行してナビサーバ１の各部を制御する。記憶装置１０３は、例えば、大容量のハードディスクとそのドライバとを備え、データの書き込み、読み出し、書き換え、削除などを行うものであり、種々の処理の途中結果を保持する作業領域としても用いられる。

地図データベース（以下、地図ＤＢと記載する。）１０４は、経路案内にも利用可能な市街図、道路図、広域図、地方図、全国図を表示するための地図情報を記憶する。市街図、道路図、広域図、地方図、全国図を表示するための地図情報は、地図を描画するための例えばベクトルデータやラスタデータ、注記（注釈）データなどを含む。なお、地図ＤＢ１０４に格納されているデータについては、変更が生じるごとに必要なタイミングで更新され、正確な情報が管理できるようになっている。

道路ネットワークデータベース（以下、道路ＮＷＤＢと記載する。）１０５は、経路探索に用いられる道路に関するネットワークデータを記憶保持する。すなわち、道路ＮＷＤＢ１０５は、ルート探索用データを記憶している。図３は、道路ＮＷＤＢ１０５に格納される自動車用のネットワークデータの例を説明するための図である。図３（Ａ）は、ネットワークの一例を示している。ネットワークデータは、ノードデータとリンクデータとからなる。ノードデータは、交差点、分岐点などの地点を表す。リンクデータは、ノードデータを結ぶ線分によって、国道、県道などの自動車が通行可能な道路などを示す。図３（Ａ）に示したネットワークの例は、４つのノードデータ（Ｎ１～Ｎ４）と４つのリンクデータ（Ｌ１～Ｌ４）とによって構成されている。

また、道路ネットワークデータは、所定の矩形領域（パーセル、リージョン、メッシュ）単位に道路区間を特定することができるようになっている。図４は、所定の矩形領域を単位として形成される道路ネットワークデータベースについての当該矩形領域について説明するための図である。図５は、当該矩形領域のサイズの例について説明するための図である。図４に示すように、道路ＮＷＤＢ１０５に格納される道路ネットワークデータは、地表面を所定の大きさの矩形領域ごとに分割し、当該矩形領域単位に道路区間を特定することができるようになっている。そして、道路上における当該矩形領域の端部地点もノードとされる。

地表面を分割する矩形領域は、この実施の形態では、図５に示すように、例えば、４種類存在し、道路ネットワークデータを階層化している。すなわち、道路ＮＷＤＢ１０５には、以下の４つの異なるレベル道路ネットワークデータが格納されている。１つは、１６０ｋｍ×１６０ｋｍの矩形領域（図５（Ａ））により分割された場合のレベル３の道路ネットワークデータである。もう１つは、４０ｋｍ×４０ｋｍの矩形領域（図５（Ｂ））により分割された場合のレベル２の道路ネットワークデータである。もう１つは、道路ＮＷＤＢ１０５には、１０ｋｍ×１０ｋｍの矩形領域（図５（Ｃ））により分割された場合のレベル１の道路ネットワークデータである。そして、最後の１つは、１ｋｍ×１ｋｍの矩形領域（図５（Ｄ））により分割された場合のレベル０の道路ネットワークデータである。なお、レベル０の矩形領域は、レベル１の矩形領域の１００分の１の大きさであるため、図５（Ｄ）においては、その大きさを示していない。

このように、この実施の形態の道路ＮＷＤＢ１０５には、レベル０～レベル３の４階層の道路ネットワークデータが格納されている。これにより、市街地においては、レベル０の矩形領域により地表面が分割されて形成された詳細な道路ネットワークデータを用いてルート探索を行う。そして、利用する道路が高速道路になった場合には、レベル３の矩形領域により地表面が分割されて形成された道路ネットワークデータを用いてルート探索を行う。

従って、この実施の形態のナビサーバ１では、道路ネットワークデータの階層をダイナミックに切り替えてルート探索を行うようにしている。これにより、無駄なく適切なレベルでルート探索を行い、ルート上の緯度、経度で示される点情報の集まりからなる点列情報としてのルート探索結果を得ることができる。なお、図５に示した矩形領域の例は一例であり、種々の大きさの矩形領域を用いるようにすることができる。

図３（Ｂ）は、図３（Ａ）に示した例のネットワークの場合のノードデータの構成を示している。各ノードデータには、各ノードの識別情報（Ｎ１、Ｎ２、…）と、そのノードの位置を示す緯度、経度情報とが対応付けられている。なお、図３（Ｂ）には示していないが、例えば、ノード種別などの他の情報をノードデータに加えることもできる。ノード種別は、当該ノード部分が、交差点、分岐点、矩形領域端部などのどれであるかを示すものである。

図３（Ｃ）は、図３（Ａ）に示した例のネットワークの場合のリンクデータの構成を示している。各リンクデータには、各リンクの識別情報（Ｌ１、Ｌ２、…）と、そのリンクを構成するノードの識別情報（Ｎ１、Ｎ２、…）と、リンクコストと、道路種別と、形状補間点と、有料／無料フラグと、その他の種々の情報とが対応付けられている。通常、リンクコストは、そのリンクの長さ（距離）、あるいは、通行に要する時間によって定められる。

そして、リンクコストは、例えばダイクストラ法により、リンクコストが最小となるルート（経路）を探索する場合に参照される。道路種別は、当該リンク部分が、国道、県道、市道、私道、フェリー航路などのどれであるかを示すものである。フェリー航路は、当該リンクが、フェリー（日常交通手段として使われる貨客船等）により移動するリンクであることを意味する。例えば、本州から北海道、九州、四国などに移動する場合、あるいは、その反対の移動の場合において、フェリーが移動手段となるリンクが存在する。

形状補間点は、当該リンクが大きくカーブしているなどして、両端の２点のノードだけでは当該リンクの形状や位置を適切に示すことができない場合に付加されている情報である。従って、形状補間点を繋ぎ合わせることにより、当該リンクの実際の形状と位置が適切に特定できる。有料／無料フラグ（有料道路フラグ）は、当該リンクが、有料道路のリンクなのか、無料道路のリンクなのかを示す情報であり、道路を所定の種類に応じて区別することを可能にする種別情報の１つである。従って、道路種別なども、種別情報の１つである。そして、当該リンクが高速道路などの有料道路のリンクである場合には、有料／無料フラグは有料を示す情報となり、当該リンクは使用料のかからない無料道路のリンクである場合には、有料／無料フラグは無料を示す情報となる。

その他にも、例えば、道路名称や道路番号、車線数など種々の情報をリンクごとに持つようにすることができる。また、図５を用いて説明したレベルを示す情報は、道路ネットワークデータのリンクデータにおいて、リンク単位に持つようにすることもできる。また、当該レベルを示す情報は、階層構造化されている各レベルの道路ネットワークデータごとのメタデータとして、レベルを示す情報を持つようにすることもできる。この実施の形態において、レベル情報は、例えば、階層構造化されている各レベルの道路ネットワークデータごとのメタデータとして管理されている。

この図３を用いて説明したような、リンクデータとノードデータとが道路ＮＷＤＢ１０５に格納されている。なお、道路ＮＷＤＢ１０５に格納されているデータについては、変更が生じるごとに必要なタイミングで更新され、正確な情報が管理できるようになっている。

なお、ここでは説明を簡単にするため、図５（Ａ）～（Ｄ）の大きさの矩形領域に地表面が分割されて形成された道路ネットワークデータを用いるものとして説明したが、これに限るものではない。例えば、レベル０～レベル３の矩形領域は、種々の大きさの矩形領域とすることができる。例えば、レベル０の矩形領域は、これが基本になるため、その大きさは変えず、レベル１～レベル３の矩形領域については、任意の大きさの領域として設定することができるようにしてもよい。また、例えば、レベル０～レベル６までというように、より多くのレベルに分割することも可能である。

また、ここでは説明を簡単にするため、全てのレベルの道路ネットワークデータを道路ＮＷＤＢ１０５に格納するものとして説明したが、これに限るものではない。例えば、レベル０の道路ネットワークデータは、道路ＮＷＤＢ１０５ではなく、地図ＤＢ１０４に格納しておくようにしてもよい。レベル０の道路ネットワークデータは、最も詳細な基本となるデータであり、使用頻度も高く、また、地図データとの連携もしやすくするためである。

このように、地図ＤＢ１０４と道路ＮＷＤＢ１０５とは、密接に関連する地図データと道路ネットワークデータとを管理するものとして、地図ＤＢ１０４と道路ＮＷＤＢ１０５とに記録するデータを調整し、連携を取りやすくすることができる。また、レベルごとに道路ＮＷＤＢを異なる記録媒体に設けるなど、地図データや道路ネットワークデータの管理の仕方は種々の対応を取ることが可能である。また、道路ネットワークデータの例として、リンクデータとノードデータからなる道路ネットワークデータについて説明したが、経路探索に利用可能であり、道路に関する情報を記憶保持できるデータであれば、これに限られない。

高速道路データフレーム（以下、高速道路ＤＦと記載する。）１０６は、この実施の形態においては、いわゆる高速道路に限られず、有料道路に関する情報を記憶する。図６は、高速道路ＤＦ１０６の格納データの例を説明するための図である。図６に示すように、高速道路ＤＦ１０６には、路線コード、名称、リンクＩＤが格納されている。路線コードは、有料道路のそれぞれを識別可能な識別ＩＤである。名称は、路線コードにより特定される有料道路に付けられている道路名称である、リンクＩＤは、当該路線コードで特定される有料道路を構成するリンク群を構成する各リンクを特定する情報である。

図６に示した高速道路ＤＦ１０６の格納データの例の場合、路線コード「００１」の有料道路は、「○○高速道路」であり、当該有料道路は、リンクＩＤが、「Ｌａ、Ｌｂ、Ｌｃ、…」により特定されるリンクによって構成されていることを示している。また、路線コード「００２」の有料道路は、「××自動車道」であり、当該有料道路は、リンクＩＤが、「Ｌα、Ｌβ、Ｌγ、…」により特定されるリンクによって構成されていることを示している。また、路線コード「００３」の有料道路は、「△△有料道路」であり、当該有料道路は、リンクＩＤが、「Ｌ１０１、Ｌ１０２、Ｌ１０３、…」により特定されるリンクによって構成されていることを示している。

探索結果データファイル１０７は、後述するルート探索部１０９により探索されたルートを示すリンク単位のデータが格納される。図７は、探索結果データファイル１０７の格納データ（探索結果データ）の例を説明するための図である。図７に示すように、探索結果データファイル１０７の格納データには携帯端末ＩＤが付される。すなわち、探索結果データファイル１０７の格納データは、ルート探索要求元の携帯端末４ごとに作成される。なお、１つのルート探索要求に応じて、出発地から目的地までの複数のルートが探索される場合もあるが、ここでは、説明を簡単にするため、１つのルートが探索されたものとして説明する。

探索結果データファイル１０７には、探索されたルートを構成するリンクごとに形成される複数の探索結果データが記憶される。リンクごとに形成される探索結果データは、図７に示すように、リンクＩＤ、点列情報、道路種別、レベル、形状補間点、有料／無料フラグ、その他の種々の情報からなる。リンクＩＤは、探索されたルートを構成するリンクを特定する情報であり、点列情報は、当該リンクＩＤにより特定されるリンクの両端のノード（位置）を特定する点情報（緯度、経度）である。従って、探索結果データの点列情報は、リンクの両端に位置するノード（点）の集まりであり、探索されたルートを特定する情報となる。

道路種別は、図３を用いて説明した道路ＮＷＤＢ１０５のリンクデータの道路種別と同様の情報であり、当該リンクＩＤで特定されるリンクが、どのような道路なのか、あるいは、フェリー航路なのかを示す情報である。レベルは、当該リンクＩＤ及び当該ノードＩＤを特定したときに用いた道路ネットワークデータのレベルを示す。すなわち、当該レベルは、図５を用いて説明したレベル０～レベル３のいずれの道路ネットワークデータを用いて当該リンクや当該ノードを特定したのかを示している。

形状補間点は、上述もしたように、特定したリンクの形状が、両端のノードだけでは正確に特定できない場合に、当該リンクの形状及び位置を正確に特定できるようにするための情報である。有料／無料フラグは、図３を用いて説明した道路ＮＷＤＢ１０５のリンクデータの有料／無料フラグと同様の情報であり、当該リンクが有料道路のリンクか、無料道路のリンクかを示している。

探索結果データファイル１０７に格納されるデータは、基本的に、道路ＮＷＤＢ１０５のリンクデータやノードデータから取得される情報であり、この他にも、道路ＮＷＤＢ１０５のリンクデータから取得できる情報を備えるようにしてもよい。もちろん、道路ＮＷＤＢ１０５以外から必要な情報を取得し、探索結果データに加えることも可能である。

提供要求データファイル１０８は、詳しくは後述するように、有料道路区間を特定する情報であって、必要最小限に間引かれた点列情報を含み、提供サーバ２に対してＥＴＣ割引考慮料金の提供を要求するための情報を記憶する。図８は、提供要求データファイル１０８の格納データの例を説明するための図である。サーバＩＤは、ＥＴＣ割引考慮料金の提供要求元のサーバを一意に特定可能なサーバの識別情報である。提供サーバ２には、種々のサーバからＥＴＣ割引考慮料金の提供要求が送信されて来るため、各提供要求の送信元を正確に特定できるようにしている。

端末ＩＤは、ルート探索要求の送信元の携帯端末４を特定するための情報である。これらのサーバＩＤ、端末ＩＤは、提供サーバ２からの返信情報にも含められ、ナビサーバ１などのＥＴＣ割引考慮料金の提供要求の送信元のサーバにおいても、元々の提供要求元の携帯端末まで特定することができるようにしている。区分は、当該間引き後データが、ＥＴＣ割引考慮料金の提供要求であることを示す情報である。

図８において、（ｘ１，ｙ２）、（ｘ２，ｙ２）、…が、緯度、経度からなる点情報が集まって形成される点列情報であり、詳しくは後述するように、ナビサーバ１において特定した有料道路区間を提供サーバ２でも正確に特定（再現）できるようにするために、ナビサーバ１の機能により形成されるものである。この図８に示す提供要求データが、提供サーバ２に対するＥＴＣ割引考慮料金の提供を要求するためのデータとなる。

なお、地図ＤＢ１０４、道路ＮＷＤＢ１０５、高速道路ＤＦ１０６、探索結果データファイル１０７、提供要求データファイル１０８のそれぞれも、ハードディスクなどの記録媒体とそのドライバとからなる記憶装置に形成されている。

ルート探索部１０９は、制御部１０２の制御の下、通信Ｉ／Ｆ１０１を通じて受け付けた携帯端末４からのルート探索要求に含まれる出発地から目的地までのルートを、道路ＮＷＤＢ１０５や必要に応じて地図ＤＢ１０４を参照して探索する。なお、ルート探索部１０９は、携帯端末４からのルート探索要求に１以上の経由地が含まれている場合にはこれを考慮すると共に、時間優先、高速道路優先などの探索モードの指定があるときには、これに応じたルート探索を行うことができる。ルート探索部１０９のルート探索処理により得られたルート探索結果が、図７を用いて説明した態様で探索結果データファイル１０７に格納される。

対象区間特定部１１０は、ルート探索部１０９により探索されたルートにおいて、ＥＴＣ割引考慮料金の算定対象となる有料道路区間を特定する処理を行う。具体的には、探索結果データファイル１０７の図７に示した態様の各リンクに対応する探索結果データを参照し、道路の種別情報の１つである有料／無料フラグが「有料」を示すリンク列の区間を特定する。図９は、対象区間特定部１１０で行われる処理を説明するための図である。図９において、白丸（○）で挟まれた区間が、料金計算対象リンク、すなわち有料道路のリンクである。また、一方または両方が黒丸（●）であるリンクは料金計算非対象リンク、すなわち、無料道路のリンクである。従って、図９において、白丸（○）または黒丸（●）は、リンクの端部のノードに対応している。

図９（Ａ）に示すように、出発地が有料道路のリンクの始まりである場合は、出発地が有料道路上となり、何処から当該有料道路に乗ったのか（進入したのか）を特定できず、ＥＴＣ割引考慮料金は算定できない。このため、対象区間特定部１１０は、図９（Ａ）に示したような区間については処理対象区間から除外する。また、図９（Ｂ）に示すように、目的地が有料道路のリンクの終わりである場合は、目的地が有料道路上となり、何処で当該有料道路から降りるのか（抜けるのか）を特定できず、ＥＴＣ割引考慮料金は算定できない。このため、対象区間特定部１１０は、図９（Ｂ）に示したような区間についても処理対象区間から除外する。

対象区間特定部１１０は、図９（Ｃ）に示すように、白丸（○）が連続する有料道路のリンク列の区間と、その前後１つずつの無料道路のリンクとを合わせた区間を、ＥＴＣ割引考慮料金を算定する処理対象区間として特定する。このように、有料道路の区間だけでなく、その前後１つずつの無料道路のリンクを合わせた区間を処理対象区間とするのは、その有料道路に何処から乗り、何処で降りるのかを特定し、真に利用する有料道路区間を特定するためである。すなわち、有料道路の前後１つずつの無料道路のリンクは、無料道路と有料道路とを接続するいわゆるランプに相当する部分になる。

対象区間特定部１１０は、探索結果データファイル１０７から、図９（Ｃ）を用いて説明したように処理対象区間の探索結果データを抽出し、処理対象区間データとして、例えば、記憶装置１０３の空き領域に記録する。すなわち、処理対象区間の探索結果データが、処理対象区間データである。なお、対象区間特定部１１０は、有料／無料フラグが「有料」を示すリンクが１つもない場合には、ＥＴＣ割引考慮料金を提供する必要はないので、後述するルート情報提供部１１５が機能して、ルート探索結果を探索要求元の携帯端末４に提供することになる。すなわち、以下に説明する間引処理部１１１、座標レベル調整部１１２、提供要求形成部１１３、合算処理部１１４が機能することはない。

対象区間特定部１１０において、図９（Ｃ）に示したように、処理対象区間が特定でき、探索結果データファイル１０７から抽出した処理対象区間データが記憶装置１０３の空き領域に記録されたとする。従って、処理対象区間データは、図７を用いて説明した探索結果データと同様の内容のものである。次に、間引処理部１１１が機能する。間引処理部１１１は、第１の間引処理部１１１Ａと、第２の間引処理部１１１Ｂとを備える。

第１の間引処理部１１１Ａは、記憶装置１０３に記録した各処理対象区間データのリンクＩＤに基づいて、高速道路ＤＦ１０６を参照し、当該処理対象区間データが示すリンクの路線コードを取得する。この路線コードは、当該リンクに対応する道路が有料道路であるという、当該道路が持っている性質を表す属性情報の１つである。第１の間引処理部１１１Ａは、路線コードが取得でき、更に同じ路線コードが連続する場合は、先頭の１件の処理対象区間データを残し、残りは間引く処理を行う。なお、路線コードが取得できなかった場合には、処理対象区間データはそのまま残すように処理する。

路線コードが整備されていないケースとしては、一般道路から有料道路へ接続するインターチェンジや有料道路から一般道路へ接続するインターチェンジ、異なる有料道路間を接続するジャンクションがあり、これらを総称してこの明細書では渡り線と呼ぶ。また、有料道路ではあるが、高速道路ＤＦ１０６にデータが整備されていない路線が存在する場合もある。

図１０は、第１の間引処理部で行われる処理を説明するための図である。図１０においても、白丸（○）と黒丸（●）の意味は、図９で説明した場合と同じである。図１０（Ａ）に示すような、処理対象区間が特定できたとする。当該処理対象区間は、一般道路（無料道路）から渡り線ＩＮを通じて路線Ａ（有料道路Ａ）に乗り、渡り線ＪＣＴを通って路線Ｂ（有料道路Ｂ）に乗り換え、渡り線ＯＵＴを通じて一般道路（無料道路）に降りるという区間である。渡り線ＩＮと渡り線ＯＵＴはインターチェンジであり、渡り線ＪＣＴはジャンクションである。

この場合、路線コードのない一般道路のリンクと渡り線のリンクに対応する処理対象区間データはそのまま残す。しかし、路線Ａのリンクはみな同じ路線ＩＤを有しているので、バツ印を始点とするリンクの処理対象区間データは間引くことができる。間引いた処理対象区間データが存在しなくても、路線Ａの最初のリンクの始点のノード（点情報）が分かり、次の渡り線が分かっていれば、路線Ａ上の経路は、提供サーバ２においても特定（再現）できるためである。

同様に、路線Ｂのリンクはみな同じ路線ＩＤを有しているので、バツ印を始点とするリンクの処理対象区間データは間引くことができる。この場合においても、間引いた処理対象区間データが存在しなくても、路線Ｂの最初のリンクの始点のノード（点情報）が分かり、次の渡り線が分かっていれば、路線Ａ上の経路は、提供サーバ２においても特定（再現）できるためである。

従って、第１の間引処理部１１１Ａは、図１０（Ａ）に示した処理対象区間の処理対象区間データについて、バツ印を始点とする区間の処理対象データを間引くことにより、図１０（Ｂ）に示すように、間引いた処理対象区間データを形成する。このようにして、不必要な処理対象区間データを間引いた後の処理対象区間データの集まりは、間引き後データとして、記憶装置１０３に記憶保持される。

図１０においては、説明を簡単にするため、路線Ａ、路線Ｂとも４つのリンクで構成されている場合を示したが、実際の有料道路の場合のリンクは更に多くのリンクを有する場合もある。このため、第１の間引処理部１１１Ａの処理により、処理対象区間を構成するリンクに対応する処理対象区間データを効率よく間引くことができる。

上述したように、渡り線や高速道路ＤＦ１０６にデータが整備されていない有料道路の場合には、路線ＩＤが存在しないいので、対応する処理対象区間データはそのままのこすことになる。路線コードが存在しいな区間は、渡り線やたまたまデータが整備されていない有料道路の区間であるので、それほど長い区間でないため、大きな問題となることは通常はない。

しかし、路線コードが整備されていない有料道路のリンク上に経由地が設定された場合には、探索結果の使用上、処理対象区間データとなる検索結果データが増えてしまい、間引き後データの点列情報の数が大きく増えてしまう場合がある。このような場合に、第２の間引処理部１１１Ｂが機能し、不要な処理対象区間データを間引く処理を行う。図１１は、第２の間引処理部１１１Ｂで行われる処理を説明するための図である。図１１においても、白丸（○）と黒丸（●）の意味は、図９で説明した場合と同じである。

図１１（Ａ）に示すように、対象区間特定部１１０において、処理対象区間が特定されたとする。この場合に、渡り線ＩＮ、渡り線ＯＵＴのそれぞれのリンクと、有料道路の本線部分のリンク列に対応する道路データフレームリンク（以下、道路ＤＦリンクと記載する。）ＲＴの各リンクには、高速道路ＤＦ１０６に路線コードが存在していないリンクであるとする。また、道路フレームリンクＲＴの中央部分のリンクは、例えば、図７のリンクＩＤがＬｃの欄に示したように、形状補間点が設けられている道路形状データフレームリンク（以下、道路形状ＤＦリンクと記載する）ＳＰであるとする。なお、図１１においては、道路形状ＤＦリンクＳＰの区間は、形状補間点が設けられている区間であるため、便宜上長い区間として示している。

このような場合に、図１１（Ｂ）に示すように、形状補間点が設けられている道路形状ＤＦリンクＳＰの途中に経由地Ｐｘを設けることが、携帯端末４からのルート探索要求により指示されていたとする。この場合、ルート探索部１０９は、道路形状ＤＦリンクＳＰについて、経由地Ｐｘとその前後のノードとの間に、形状補間点分の探索結果データを作成する。探索したルートの形状と位置を正確に把握できるようにするためであり、これが、上述したナビサーバ１における探索結果の仕様である。

図１１（Ｂ）において、白抜きの四角（□）で接続された部分が、形状補間点に対応してノードが設定されることにより設けられたリンクを意味し、この部分の探索結果データが探索結果データファイル１０７に形成されている。従って、このようにして形成された探索結果データは、そのまま処理対象区間データとなって抽出され、記憶装置１０３に記録されてしまう。

しかし、この様な場合であっても、道路形状ＤＦリンクＳＰのリンク区間の両端が適切に把握できれば、当該リンクの形状がどのような形状であっても、提供サーバ２で当該道道路形状ＤＦリンクＳＰ部分を特定（再現）できる。そこで、第２の間引処理部１１１Ｂは、路線コードが付与されていない道路形状ＤＦリンクにおいて、リンクＩＤが同じ処理対象区間データが複数存在する場合には、当該処理対象区間データを間引いて、間引き後データには組み入れないようにする。

これにより、図１１（Ｂ）に示したように、形状補間点に対応して設けられたリンクが存在していても、そのリンクの処理対象区間データは間引かれる。従って、図１１（Ｃ）に示すように、形状補間点に対応して設けられたリンクが存在しない、図１１（Ａ）に示した元の状態と同じ状態を示す処理対象区間データが記憶装置１０３に用意できる。このように、第２の間引処理部１１１Ｂは、ルート探索部１０９の機能により増えてしまう探索結果データ（処理対象区間データ）を削除し、間引き後データの点列情報が不必要に多くならないようにしている。

このように、ナビサーバ１では、対象区間特定部１１０の機能により、探索結果データファイル１０７から処理対象区間の探索結果データである処理対象区間データが、記憶装置１０３に抽出される。そして、第１の間引処理部１１１Ａにより、同一路線上のリンクに対応する処理対象区間データは、最初の処理対象区間データだけを残して、残りは間引かれる。さらに、第２の間引処理部１１１Ｂの機能により、ルート探索部１０９の機能により増えてしまう処理対象区間データは間引かれる。これにより、必要最小限度の処理対象区間データだけを間引き後データとして記憶装置１０３に残すことができる。

座標レベル調整部１１２は、記憶装置１０３に残った間引き後データ（間引き処理後の処理対象区間データ）の各ノードが示す座標位置を、一番小さな矩形領域（１ｋｍ×１ｋｍ）で地表面が分割するようにされて形成された道路ネットワークデータに対応する座標に変換する。すなわち、上述もしたように、ルート探索部１０９は、用いる道路ネットワークデータについて、探索対象の道路に応じて、そのレベルをダイナミックに変えながらルート探索を行う。

このため、一般に交差点などの分岐点の少ない有料道路が利用対象の道路になると、ルート探索部１０９は、一番大きな矩形領域（１６０ｋｍ×１６０ｋｍ）により地表面が分割するようにされて形成された道路ネットワークデータを用いて経路探索を行う。この場合、図５に示した矩形領域の大きさの関係がある場合、一番小さな矩形領域（１ｋｍ×１ｋｍ）は、一番大きな矩形領域の２５６００分の１の大きさとなり、両レベル間における座標位置は、若干の誤差を含んでしまう。

そこで、座標レベル調整部１１２は、レベル３の道路ネットワークデータにより形成された処理対象区間データの点列情報が示す各ノードに対応する座標位置（緯度、経度）を、レベル０の道路ネットワークデータに対応した座標位置（緯度、経度）に変換する。これにより、処理対象区間データの各ノードについて、ナビサーバ１において特定した座標位置と同等の座標位置を提供サーバ２などの外部装置においても特定できるようになる。

なお、記憶装置１０３に残された処理対象区間データのすべてが、レベル３の道路ネットワークデータに基づいて作成されたものであるとは限らない。このため、座標レベル調整部１１２は、図７を用いて説明したように、各処理対象区間データが有するレベルを示す情報を参照し、該当するレベルの座標からレベル０の座標に変換することができるようにしている。

提供要求形成部１１３は、記憶装置１０３に記憶されている間引き処理され、座標レベルも調整された間引き後データ（間引き処理された処理対象区間データ）の点列情報から図８を用いて説明した提供要求データを形成する。この場合、提供要求形成手段は、間引かずに残した処理対象区間データの始点（先端側）の点情報を採用し、後端側の点情報は用いないようにする。すなわち、隣り合うリンクの場合、理論的には、リンクの終わり（後端側）のノードは、その直後のリンクの始まりノードと一致するためである。なお、一致しない場合には、当該リンクの後端側のノードに対応する点情報を残してもよい。これにより、点情報が隣接して重複することなく、適切に処理対象区間を示す点列情報を構成することができる。

このようにして、提供要求形成部１１３において形成された提供要求データが、ＥＴＣ割引考慮料金の提供要求として、通信Ｉ／Ｆ１０１及び接続端１０１Ｔを通じて、ネットワークに送出され、提供サーバ２に送信される。

なお、出発地から目的地の間において、処理対象区間（有料道路区間）が複数の区間に分割される場合がある。例えば、出発地を北海道の稚内とし、目的地を九州の鹿児島としてルート探索を行うと、フェリー航路を介して、「北海道の高速道路区間」、「本州・九州の高速道路区間」が取得（特定）できる。このような場合には、「北海道の高速道路区間」と「本州・九州の高速道路区間」とのそれぞれの区間を処理対象区間として、別々にＥＴＣ割引考慮料金の提供要求を提供サーバ２に対して行う。また、ルートによっては、フェリー航路を使用しなくても、処理対象区間（有料道路区間）が複数の区間に分割される場合がある。このような場合においても、それぞれの区間を処理対象区間として、別々にＥＴＣ割引考慮料金の提供要求を提供サーバ２に対して行えばよい。

このようにして、提供要求形成部１１３において、ＥＴＣ割引考慮料金の提供要求である間引き後データを形成し、提供サーバ２に送信する。提供サーバ２では、ナビサーバ１からの間引き後データを受信すると、当該間引き後データの点列情報に基づいて、処理対象区間（有料道路区間）を特定（再現）して、当該区間のＥＴＣ割引考慮料金を算定し、これをナビサーバ１に返信する。

ナビサーバ１では、接続端１０１Ｔ及び通信Ｉ／Ｆ１０１を通じて提供サーバ２からの返信を受信すると、制御部１０２は、これを記憶装置１０３に一時記憶する。そして、制御部１０２は、自機から送信したＥＴＣ割引考慮料金の提供要求の送信の状況（履歴）に基づいて、複数の処理対象区間についてのＥＴＣ割引考慮料金の提供を要求しているか否かを判別する。複数の処理対象区間についてのＥＴＣ割引考慮料金の提供を要求している場合には、その複数の提供要求に応じた、それぞれの返信を待つ。

複数の提供要求に応じたＥＴＣ割引考慮料金の返信を受信すると、制御部１０２は、合算処理部１１４を制御し、通知された各処理対象区間についてのＥＴＣ割引考慮料金を、合算する。この後、制御部１０２の制御の下、ルート情報提供部１１５が機能し、ルート探索結果と共に、合算したＥＴＣ割引考慮料金を、通信Ｉ／Ｆ１０１及び接続端１０１Ｔを通じて、ネットワーク３に送出し、ルート探索要求元の携帯端末４に送信する。

なお、ナビサーバ１の制御部１０２は、複数の処理対象区間についてのＥＴＣ割引考慮料金の提供を要求していない場合には、合算処理部１１４が機能することはない。この場合には、ルート情報提供部１１５が機能し、ルート探索結果と共に、提供サーバ２から取得したＥＴＣ割引考慮料金を、通信Ｉ／Ｆ１０１及び接続端１０１Ｔを通じて、ネットワーク３に送出し、ルート探索要求元の携帯端末４に送信する。

［ナビサーバ１の処理のまとめ］
図１２、図１３は、ナビサーバ１で行われる処理を説明するためのフローチャートである。ナビサーバ１の制御部１０２は、常時、図１２、図１３に示す処理を実行するようにしている。制御部１０２は、接続端１０１Ｔ及び通信Ｉ／Ｆ１０１を通じて、自機宛てのルート探索要求を受信するようにし（ステップＳ１０１）、自機宛てのルート探索要求を受信したか否かを判別する（ステップＳ１０２）。ステップＳ１０２の判別処理において、自機宛てのルート探索要求を受信していないと判別したときには、ステップＳ１０１からの処理を繰り返し、ルート探索要求の到来を待つ。

ステップＳ１０２の判別処理において、自機宛てのルート探索要求を受信したと判別したときには、制御部１０２は、ルート探索部１０９を制御して、受信したルート探索要求に含まれる出発地から目的地までのルート探索を行う（ステップＳ１０３）。ルート探索結果は、図７を用いて説明した態様で、探索結果データファイル１０７に格納される。また、ルート探索要求に経由地の指定が含まれている場合には、ルート探索部１０９は、当該経由地の指定も考慮したルート探索を行える。この場合には、図１１を用いて説明したように、形状補間点が設けられているリンクに経由地が設定された場合には、形状補間点分の探索結果データが形成されて、探索結果データファイル１０７に格納される。

ルート探索部１０９によるルート探索処理が終了すると、制御部１０２は、対象区間特定部１１０を制御し、対象区間特定処理を実行する（ステップＳ１０４）。このステップＳ１０４の処理は、図９を用いて説明したように、有料道路区間（１以上のリンク区間）とその前後に１つずつの無料道路区間（１つのリンク区間）とからなる処理対象区間を特定する処理である。このステップＳ１０４の処理では、処理対象区間の探索結果データが、処理対象区間データとして記憶装置１０３に抽出される。

次に、制御部１０２は、記憶装置１０３に抽出した処理対象区間データのリンクＩＤ基づいて、高速道路ＤＦ１０６を参照し、各リンクの路線コードを取得する（ステップＳ１０５）。この後、制御部１０２は、間引処理部１１１の第１の間引処理部１１１Ａを制御して、第１の間引き処理を行う（ステップＳ１０６）。ステップＳ１０６の処理では、図１０を用いて説明したように、同じ路線コードを有する同じ路線（同じ有料道路）のリンクが連続する場合には、同じ路線コードを有する処理対象区間データのうち、最初の処理対象区間データを残して、残りは間引くようにする。

なお、路線コードが付与されているリンクに経由地が設定され、そのリンクに形状補間データが存在するために、形状補間点分の探索結果データが形成されていても、その形成された探索結果データ（処理対象区間データ）は、ステップＳ１０６で間引かれる。形状補間点分の探索結果データのリンクＩＤは、当該リンクのリンクＩＤと同じになり、路線コードが付与されているリンクとなるため、間引きの対象となるためである。

この後、制御部１０２は、間引処理部１１１の第２の間引処理部１１１Ｂを制御して、第２の間引き処理を行う（ステップＳ１０７）。ステップＳ１０７の処理は、図１１を用いて説明した処理である。すなわち、路線コードが整備されていない有料道路のリンク（区間）であって、形状補間点が設定されているリンクに経由地が設定された場合に、ルート探索処理で形成される探索結果データ（処理対象区間データ）を間引く処理を行う。なお、該当リンクに経由地が設定されていない場合、また、そもそもルート探索要求に経由地を含まない場合には、ステップＳ１０７の第２に間引き処理は行われず、次の処理に進むことになる。

ステップＳ１０７の処理の後においては、制御部１０２の制御の下、座標レベル調整部１１２が機能し、座標レベル調整処理が実行される（ステップＳ１０８）。このステップＳ１０８の処理は、上述もしたように、間引き処理された処理対象区間データの点列情報（各リンクの両端のノードに対応する点の座標データ）を、レベル０の道路ネットワークデータに対応するレベルの座標に変換する処理である。有料道路に対応するリンクの探索結果データである処理対象区間データは、レベル３の大きな矩形領域で地表面が分割するようにされて形成された道路ネットワークデータに基づいて形成されているため、座標データの精度が若干落ちているためである。

次に、制御部１０２は、提供要求形成部１１３を制御して、ＥＴＣ割引考慮料金の問い合わせ処理を実行する（ステップＳ１０９）。ステップＳ１０９において、提供要求形成部１１３は、不必要なデータが間引かれ、点列情報の座標レベルの調整もされた記憶装置１０３に記憶されている間引き後データ（間引き処理後の処理対象区間データ）に基づいて、図８を用いて説明した提供要求データを形成し、これを提供サーバ２にする。

なお、ステップＳ１０４の対象区間特定処理で、処理対象区間が１つの区間だけでなく、上述した「北海道の高速道路区間」と「本州・九州の高速道路区間」というように、複数の処理対象区間が特定できたとする。この場合には、ステップＳ１０５からステップＳ１０９の各処理は、各処理対象区間について行われる。

この後、制御部１０２は、図１３の処理に進み、提供サーバ２からの返信、すなわち、ＥＴＣ割引考慮料金の通知を受信するようにする（ステップＳ１１０）。制御部１０２は、ステップＳ１０４の対象区間特定処理の結果に基づき、処理対象区間が複存在するか否かを判別する（ステップＳ１１１）。ステップＳ１１１の判別処理において、処理対象区間が複数存在すると判別したとする。この場合、制御部１０２は、合算処理部１１４を制御して、自機から送信した複数のＥＴＣ割引考慮料金の提供要求に対応する複数の受信した返信から、ＥＴＣ割引考慮料金を抽出し、それらを合算する処理を行う（ステップＳ１１２）。

ステップＳ１１１の判別処理において、処理対象区間は複数存在しないと判別したときと、ステップＳ１１２の処理に後においては、制御部１０２は、ルート情報提供部１１５を制御して、ルート探索結果等の通知処理を行う（ステップＳ１１３）。ステップＳ１１３において、ルート情報提供部１１５は、ルート探索部１０９の探索結果と提供サーバ２から提供を受けたＥＴＣ割引考慮料金とを含む、携帯端末４用の提供データを形成し、これをルート探索要求元の携帯端末４に送信する処理を行う。この後、制御部１０２は、ステップＳ１０１からの処理を繰り返す。

これにより、ルート探索要求元の携帯端末４は、ルート探索結果とＥＴＣ割引考慮料金の提供を受けて、当該ルートを移動するかどうかを決める。提供を受けたルートが気に入らなかったときには、出発地、目的地、経由地、探索条件などを入力し直し、再度のルート探索を行うように要求できる。また、探索されたルートで移動する場合には、ナビゲーション処理の開始を指示することで、ナビサーバ１から必要な地図情報の提供を受けて、ルート案内を開始させることができる。

［実施の形態の効果］
この実施の形態のナビサーバ１によれば、自機において探索したルート上のＥＴＣ割引考慮料金の算出対象となる有料道路区間（処理対象区間）を特定し、当該処理対象区間を提供サーバ２において再現可能な点列情報を形成して、提供サーバ２に提供できる。これにより、ナビサーバ１と提供サーバ２とで、用いる地図情報やアルゴリズムが異なるルート探索エンジンを用いている場合であっても、提供サーバ２において、ナビサーバ１がと特定した処理対象区間と同じ区間を特定（再現）できる。従って、ナビサーバ１は、自機が目的とする処理対象区間についての適切なＥＴＣ割引考慮料金の提供を、提供サーバ２から受けることができる。

しかも、処理対象区間を特定するための点列情報（間引き後データ）は、提供サーバ２において、処理対象区間を適切に特定（再現）するために必要となる最小限の数の点列情報に絞り込んでいる（間引いている）。このため、提供サーバ２に大きな負荷をかけることもなく、また、提供サーバ２における処理対象区間の特定処理に時間がかかることもないようにできる。

また、提供サーバによっては、処理対象区間を特定するための点列情報の数を、例えば、１００点以下などのように制限して来る場合もあると考えられる。しかし、ナビサーバ１は、上述したように、点列情報を大きく間引くことができるので、提供サーバからの要求にも充分に対応することができる。

［変形例］
上述した実施の形態では、処理対象区間の各リンクに対応して形成されている処理対象区間データ（探索結果データ）の状態で、処理対象区間データ自体を間引く処理を行うようにした。この場合、残った処理対象区間データの点列情報は、処理対象区間データが示すリンクの両端のノードの点情報である。このうちの後端側のノードに対応する点情報は、提供要求形成部１１３によって用いないようにされる。

しかし、これに限るものではない。各処理対象データのリンクの両端のノードの座標データ自体を間引き処理の対象として、間引き後データを作成するようにできる。すなわち、残す処理対象区間データの当該リンクの両端のノードに対応する座標データの内、先端側の座標データのみを残し、その他は間引くようにして、間引き後データを形成するようにすることももちろん可能である。

また、提供サーバによっては、処理対象区間を特定するための点列情報の数を制限している場合もある。このような場合には、ナビサーバ１の間引処理部１１１は、その制限数に到達したら間引き処理をやめるようにしたり、その制限数に到達するように、各有料道路の本線区間の間引き量を調整するようにしたりすることもできる。しかし、提供サーバ２の処理の負荷を大きくしないことを考慮すれば、点列情報の間引きは最大限行うようにすることが望ましい。

また、上述した実施の形態では、外部の提供サーバからＥＴＣ割引考慮料金の提供を受ける場合を例にして説明したが、これに限るものではない。例えば、自社のルート探索エンジンを用いて探索したルートの高速道路利用区間についての所定の電気自動車の電気消費量を、他社の情報提供装置から取得したい場合にもこの発明を適用できる。また、自社のルート探索エンジンを用いて探索したルートの山間部における所定のガソリン自動車の二酸化炭素排気量やガソリン消費量を、他社の情報提供装置から取得したい場合にもこの発明を適用できる。自社のルート探索エンジンを用いて探索したルートの所定区間に関する情報を、他社の情報提供装置から取得するようにする種々の場合に、この発明を適用できる。

すなわち、処理対象区間を特定するための道路の種別情報は、有料／無料フラグだけではない。例えば、特定の道路名称の道路の区間を処理対象区間として抽出したり、道路の勾配情報から勾配が所定値以上の区間を処理対象区間として特定したりできる。また、標高が所定の高さ以上の区間を処理対象区間として特定するなど、ルートとして用いる道路について、リンク単位に特定可能な種々の種別情報を用いて、処理対象区間を特定できる。

また、間引く処理対象区間データを特定するための道路の属性情報は、路線コードにかぎるものではない。例えば、道路名称、道路番号といった、道路を特定することができる情報が、リンク単位に把握可能であれば、それらの情報を用いてもよい。

［その他］
上述した実施の形態の説明からも分かるように、請求項のルート探索手段の機能は、実施の形態のナビサーバ１（以下、単にナビサーバ１と記載する。）のルート探索部１０９が実現している。また、請求項の特定手段の機能は、ナビサーバ１の対象区間特定部１１０が実現し、請求項の第１の間引き処理手段の機能は、ナビサーバ１の第１の間引処理部１１１Ａが実現している。また、請求項の提供要求形成手段の機能は、ナビサーバ１の提供要求形成部１１３が実現し、請求項の関連情報取得手段は、接続端１０１Ｔ及び通信Ｉ／Ｆ１０１と制御部１０２とが協働して実現している。

また、請求項の関連情報提供手段の機能は、ナビサーバ１のルート情報提供部１１５が実現している。また、請求項の第２の間引き処理手段の機能は、ナビサーバ１の第２の間引処理部１１１Ｂが実現し、請求項の座標レベル調整手段の機能は、ナビサーバ１の座標レベル調整部１１２が実現している。

また、図１２、図１３に示したフローチャートにより説明した方法が、この発明のルート関連情報取得方法の一実施の形態に対応している。また、図１２、図１３に示したフローチャートにより説明した処理を実行するプログラムを、サーバ装置に搭載して実行することにより、この発明のルート関連情報取得装置を実現できる。換言すれば、ルート探索部１０９、対象区間特定部１１０、第１の間引処理部１１１Ａ、第２の間引処理部１１１Ｂ、座標レベル調整部１１２、提供要求形成部１１３、合算処理部１１４、ルート情報提供部１１５の各機は、制御部１０２により実現できる。すなわち、ナビサーバ１のこれらの各部の機能は、制御部１０２において実行するプログラムにより、制御部１０２の機能として実現することができる。

１…ナビサーバ、１０１Ｔ…接続端、１０１…通信Ｉ／Ｆ、１０２…制御部、１０３…記憶装置、１０４…地図ＤＢ、１０５…道路ＮＷＤＢ、１０６…高速道路ＤＦ、１０７…探索結果データファイル、１０８…間引き後データファイル、１０９…ルート探索部、１１０…対象区間特定部、１１１…間引処理部、１１１Ａ…第１の間引処理部、１１１Ｂ…第２の間引処理部、１１２…座標レベル調整部、１１３…提供要求形成部、１１４…合算処理部、１１５…ルート情報提供部、２…提供サーバ、３…ネットワーク、３Ｂ（１）、３Ｂ（２）…基地局又はアクセスポイント、４、４（１）、４（２）…携帯端末

Claims (8)

1. 出発地と目的地とを含むルート探索要求に応じて、ルート探索用データを参照し、ルート探索を行って、出発地から目的地までのルート上の緯度、経度により示される点情報の集まりである点列情報を含む探索結果を形成するルート探索手段と、
   前記ルート探索手段で形成された前記点列情報の各点情報が示す道路の種別情報に基づいて、探索されたルート上の目的とする関連情報の取得対象区間を特定する特定手段と、
   前記特定手段で特定された前記取得対象区間の前記点列情報について、各点情報が示す位置の道路の属性情報を参照し、同じ属性情報を有する道路の点情報については、最初の点情報を残して他の点情報を間引き、間引き後データを形成する第１の間引き処理手段と、
   前記間引き後データを含む関連情報提供要求を形成して、所定の関連情報提供装置に提供する提供要求形成手段と、
   前記関連情報提供装置から提供される前記関連情報提供要求に応じた関連情報を取得する関連情報取得手段と
   を備えることを特徴とするルート関連情報取得装置。
2. 請求項１に記載のルート関連情報取得装置であって、
   前記第１の間引き処理手段は、前記特定手段で特定された前記取得対象区間の前記点列情報について、各点情報が示す位置の道路が前記属性情報を持たない場合には、当該点情報の間引きは行わないで、前記間引き後データを形成する
   ことを特徴とするルート関連情報取得装置。
3. 請求項２に記載のルート関連情報取得装置であって、
   前記ルート探索要求に経由地が含まれており、前記第１の間引き処理手段により間引き処理が行われなかった区間に、前記経由地が含まれる場合であって、前記経由地の前後に同じ識別情報が付与されている点情報が存在する場合に、当該同じ識別情報が付与されている点情報を間引いて、前記間引き後データを形成する第２の間引き処理手段
   を備えることを特徴とするルート関連情報取得装置。
4. 請求項１、請求項２または請求項３のいずれかに記載のルート関連情報取得装置であって、
   前記ルート探索手段で用いられる前記ルート探索用データは、地表面を所定の大きさの矩形領域ごとに分割し、当該矩形領域単位に道路区間を特定することができるようになっていると共に、大きさの異なる矩形領域により分割された複数の階層を有しており、
   前記ルート探索手段は、探索対象の道路に応じて、前記階層を切り替えて、可能な限り大きな矩形領域で分割された前記ルート探索用データを用いてルート探索を行って前記点列情報を形成するものであり、
   前記間引き後データの座標を、一番小さな矩形領域に分割された階層における座標に変換する座標レベル調整手段を備え、
   前記提供要求形成手段は、前記座標レベル調整手段により調整された前記間引き後データを用いて、前記関連情報提供要求を形成する
   ことを特徴とするルート関連情報取得装置。
5. ルート探索手段が、出発地と目的地とを含むルート探索要求に応じて、ルート探索用データを参照し、ルート探索を行って、出発地から目的地までのルート上の緯度、経度により示される点情報の集まりである点列情報を含む探索結果を形成するルート探索工程と、
   前記ルート探索工程で形成した前記点列情報の各点情報が示す道路の種別情報に基づいて、特定手段が、探索されたルート上の目的とする関連情報の取得対象区間を特定する特定工程と、
   前記特定工程で特定した前記取得対象区間の前記点列情報について、第１の間引き処理手段が、各点情報が示す位置の道路の属性情報を参照し、同じ属性情報を有する道路の点情報については、最初の点情報を残して他の点情報を間引き、間引き後データを形成する第１の間引き処理工程と、
   提供要求形成手段が、前記間引き後データを含む関連情報提供要求を形成して、所定の関連情報提供装置に提供する提供要求形成工程と、
   関連情報取得手段が、前記関連情報提供装置から提供される前記関連情報提供要求に応じた関連情報を取得する関連情報取得工程と
   を有することを特徴とするルート関連情報取得方法。
6. 請求項５に記載のルート関連情報取得方法であって、
   前記第１の間引き処理工程においては、前記特定工程において特定した前記取得対象区間の前記点列情報について、各点情報が示す位置の道路が前記属性情報を持たない場合には、当該点情報の間引きは行わないで、前記間引き後データを形成する
   ことを特徴とするルート関連情報取得方法。
7. 請求項６に記載のルート関連情報取得方法であって、
   前記ルート探索要求に経由地が含まれており、前記第１の間引き処理工程において間引き処理が行われなかった区間に、前記経由地が含まれる場合であって、前記経由地の前後に同じ識別情報が付与されている点情報が存在する場合に、第２の間引き処理手段が、当該同じ識別情報が付与されている点情報を間引いて、前記間引き後データを形成する第２の間引き処理工程
   を有することを特徴とするルート関連情報取得方法。
8. 請求項５、請求項６または請求項７のいずれかに記載のルート関連情報取得方法であって、
   前記ルート探索工程で用いられる前記ルート探索用データは、地表面を所定の大きさの矩形領域ごとに分割し、当該矩形領域単位に道路区間を特定することができるようになっていると共に、大きさの異なる矩形領域により分割された複数の階層を有しており、
   前記ルート探索工程においては、探索対象の道路に応じて、前記階層を切り替えて、可能な限り大きな矩形領域で分割された前記ルート探索用データを用いてルート探索を行って前記点列情報を形成するようにしており、
   座標レベル調整手段が、前記間引き後データを、一番小さな矩形領域に分割された階層における座標データに変換する座標レベル調整工程を有し、
   前記提供要求形成工程においては、前記座標レベル調整工程において調整された前記間引き後データを用いて、前記関連情報提供要求を形成する
   ことを特徴とするルート関連情報取得方法。

Images