JP4369900B2 - マッチング用ネットワークデータおよびマッチング用ネットワークデータの作成方法、ならびに、マッチング用ネットワークデータを有するナビゲーションシステム、経路探索サーバおよびナビゲーション端末装置 - Google Patents

Description

本発明は、車載用あるいは歩行者用のナビゲーションシステムにおいて、衛星航法または自律航法を用いて測位した現在位置を、道路ネットワークデータ上のリンクにマッチングするナビゲーションシステムに関するものであり、特に、マッチング精度を向上させることができるマッチング用ネットワークデータおよびマッチング用ネットワークデータの作成方法、ならびに、マッチング用ネットワークデータを有するナビゲーションシステム、経路探索サーバおよびナビゲーション端末装置に関するものである。
このマッチング用ネットワークデータは、経路探索用の道路ネットワークデータとは構成が異なり、分岐点にノードを設定せず、分岐ノードに接続されるリンクの途中にノードを設定し、各ノード間をノードから分岐点を通過して他のノードに至る複数のリンクで接続した構成である。

従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。

特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに列車時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。

また、航空機、列車、電車、バスなどの交通手段を用いて出発地から目的地までの経路を探索して案内する経路探索システムも知られている。このような経路探索システムは一般的には、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行データをデータベース化した運行データＤＢ（データベース）を参照して、乗り継ぎを含めて出発地と目的地を結ぶ、利用可能な各交通手段を経路として順次たどり、経路探索条件に合致する案内経路（列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。

歩行者ナビゲーションシステムやカーナビゲーションシステムにおける経路探索のための道路ネットワークは、例えば、図１１に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで道路ネットワークデータを構成している。すなわち、図１１において、○印、◎印がノードを示し、◎印は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図１１では図示を簡略化するため矢印の向きのリンクのみを図示している。

このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図１１において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。図１１ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至る可能な経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。

上記のような道路ネットワークは、図１１に模式的に示すようにリンクコストが固定であり、経路が定まればその累積リンクコストは一意に定まる静的なネットワークデータであり、データの量も道路ネットワークの量に比例したものになる。交通機関の運行ネットワークデータも同様でありバス路線が設定されている道路ネットワークのデータが路線ネットワークのデータとして使用される。

現在、このようなナビゲーションシステムを利用した路線バスの運行管理システムも存在している。このような運行管理システムは、例えば、各路線バスの車両に移動体端末を設置し、現在位置を測位して路線ネットワーク上にマッチング処理することで、各車両の運行位置を把握し、各停留所に車両が到着する予定時刻を表示するサービスを行ったり、道路の渋滞状況を検出したり、車両の配車状況や車両の運行状況の履歴を管理したりするシステムである。

一般に、上記のようなナビゲーションシステムにおいて、ナビゲーション端末装置は測位手段としてＧＰＳ受信機を搭載している。この測位手段は複数のＧＰＳ衛星信号が送信するＧＰＳ衛星信号を受信して処理し、現在位置（緯度・経度）を測位している。この方法は衛星航法と言われる。ＧＰＳ衛星信号はトンネル内や地下では受信することができず、また、ビルが密集した場所ではＧＰＳ信号の反射があり、測位精度が悪化する。

このため、車載用のナビゲーション装置などでは、加速度センサー、舵角センサー、ジャイロ、車速センサーなどを設けて現在位置を測位する測位手段を併用している。この測位方法は各自律航法と言われる。携帯電話をナビゲーション端末装置とする歩行者用のナビゲーション端末装置においても最近では姿勢検出センサーやジャイロを搭載して自律航法による測位機能を併用させた機器も出現している。

ＧＰＳ受信機を用いた測位手段による現在位置にはＧＰＳ衛星信号の処理における演算誤差が含まれることは周知である。一般的にＧＰＳの単独測位精度は１０ｍ強であり、ＧＰＳ測位手段で測位した位置（緯度・経度）が道路上から外れる場合がある。マッチング処理とはこの誤差による道路からのずれを修正する処理をいう。通常は測位した現在位置（測位した緯度・経度）に最も近い道路を抽出し、現在位置からこの道路に垂線をおろし、道路との交点を現在位置（補正緯度・経度）として補正する処理である。このような処理方法を投影法という。地図上の道路データを使用して上記の処理を行う方法をマップマッチングと言い、経路探索サーバが探索した経路データを使用して上記の処理を行う方法をルートマッチングという。

また、自律航法手段により測位した位置情報は、前回測位した自車位置から各種センサーによって計測した移動距離や方位の変化分を累積して現在位置を測位するものであり、測位誤差が累積されてゆく。この場合にもマッチング処理が必要になる。一般的にはＧＰＳを使用した衛星航法による測位では自車の絶対位置が測位できるので、天空が開け、ＧＰＳ衛星信号の受信状態が良い場所では衛星航法による測位結果が用いられる。

マッチング処理を行って自車位置の測位誤差の修正を行うことにより、地図上に自車位置を表示するにあたって、案内経路である道路上に正しく表示することができ、利用者は自車位置が案内経路である道路上を走行していることを確認しながら運転を続けることができる。従って、マッチングのエラーが生じると、案内経路から外れた道路上に自車位置が表示され、利用者は案内経路上を走行しているにもかかわらず、案内経路から外れたものと誤認してしまうことになる。

一方、現在位置が案内経路から逸脱し、そのずれ量が一定の範囲（一定時間経過、あるいは一定の距離）を超えると、当初の経路探索で案内した経路が役に立たなくなるため、その時の現在位置を起点にして目的地までの案内経路を再探索してナビゲーション装置に配信し直すことが必要になる。この再探索の処理をリルート処理と称している。

すなわち、マッチング処理は、自車位置を地図上に表示する際に正しく案内経路である道路上を走行しているか否かを利用者に告知する目的と、自車位置が案内経路から一定の範囲以上逸脱した際にリルート処理を起動し、目的地までの案内経路を改めて探索する目的のために行われるものである。

マップマッチング処理においては、通常、経路探索のための道路ネットワークデータ（図１１参照）を用いて行う。測位した現在位置に対してマッチングすべき道路が接近して複数ある場合には、補正した現在位置が本来の経路（経路探索により探索した出発地から目的地までの最短の案内経路）上でなく、隣接する他の道路上に誤って補正されるエラーが生じる場合がある。特に道路が狭い角度で分岐し、分岐した道路が分岐点以降狭い間隔で平行しているような道路構造の場所では特にマッチング処理でエラーが生じ易い。

このようなマッチング処理のエラーが生じると、先に述べたように、正しい案内経路を走行しているにもかかわらず利用者に案内経路から逸脱したという誤った判断をさせてしまうことになる。そして、案内経路からの逸脱の範囲が一定の範囲を超えている場合には、正しい案内経路を走行していても、リルート処理が起動されてしまい、経路探索処理の無駄が発生してしまう。

そして、リルート処理の結果、新たな案内経路がナビゲーション端末装置に伝えられると実際には当初の正しい案内経路を走行しているにもかかわらず、他の道路上を出発点とした新たな案内経路に走行道路を変更するか、時間が経過して現在位置が当初の案内経路に戻り再度リルートが行われるまで利用者の判断で走行を続けるなど、一時的に案内経路が役に立たない状態に陥る。

従ってマッチング処理には正確性が求められ、この精度を向上させるための技術も種々行われている。例えば、下記の特許文献１（特開平８−６８６５６号公報）に開示された「車載用ナビゲーション装置」が知られている。

この特許文献１に開示された車載用ナビゲーション装置は、予め、経路探索部により出発地と目的地を結ぶ誘導経路が探索され、誘導経路記憶部に記憶される。ＧＰＳ受信機の検出車両位置に基づき、マップマッチング部がＣＤ−ＲＯＭ等のメモリに記憶された車両位置周辺の地図データを用いて車両位置近くの複数のマッチング候補道路を選び出し、その中に誘導経路があるときは該誘導経路の優先度を上げて１つのマッチング候補道路を決定し、該決定したマッチング候補道路上に車両位置を修正するように構成されている。
また、地図画像描画部は車両位置周辺の地図データを用いて修正車両位置を含む地図画像を誘導経路とともにビデオＲＡＭに描画し、更に、地図画像上の修正車両位置に相当する箇所に車両位置マークを描画する。ビデオＲＡＭの画像は映像変換部により読み出され、所定の映像信号に変換されたのちディスプレイ装置に出力されて画面表示されるように構成されている。

すなわち、特許文献１に開示された車載用ナビゲーション装置は、誘導経路を含む複数のマッチング候補道路がある場合、誘導経路を優先してマッチング処理することによりマッチング処理の精度を向上させようとしたものである。

前述したように、道路が狭い角度で分岐し、分岐した道路が分岐点以降狭い間隔で平行しているような道路構造の場所では特にマッチング処理でエラーが生じ易い。また、幹線道路から側道に分岐する場合なども、幹線道路と側道が非常に接近したままなので、マッチング処理を誤りやすい。例えば、図１３に示すように道路が分岐ノードＮ１において、狭い角度でリンクＬ１とＬ２に分岐し分岐後リンクＬ１とＬ２とがしばらく平行して走り、リンクＬ２が立体交差でリンクＬ１の下または上を通過する道路構造であり、案内経路がＬ２を進行してノードＮ３をリンクＬ３に直進する経路である場合の投影法を用いたマッチング処理について説明する。

図１４には各時点において測位した現在位置Ｐ１〜Ｐ４が×印で図示されおり、この現在位置が案内経路であるリンクＬ２にマッチングされれば問題ないが、リンクＬ２とリンクＬ１の間の距離が小さい場合、案内経路でないリンクＬ１にマッチングされるエラーを生じることがある。すなわち、図１４の測位点Ｐ４の測位データが得られた瞬間において、測位位置がリンクＬ２から所定距離以上離れたので、マッチング処理が行われる。ナビゲーション端末装置２０はリンクＬ２を走行しているのであるから、位置Ｐａにマッチング処理されればよいのであるが、測位した現在位置Ｐ４に最も近いリンクはリンクＬ１であるから、投影法により位置Ｐｂにマッチングされてしまう。

このようにマックチングエラーが生じると、表示手段に表示される自車位置が案内経路であるリンクＬ２から外れ、リンクＬ１上に表示される不都合が生じる。路線バスの車両運行管理システムにおいては各バス車両の位置を正確に把握し運行状況を正確に管理する必要があり、マッチング精度を向上させることが望まれている。

また、このエラーが一定の範囲（時間または走行距離）を超過すると、経路のリルート（再探索要求）が発生する。リルートの結果、新たに探索された経路は、リンクＬ１を直進してノードＮ２に至り、ノードＮ２で右折してリンクＬ４をノードＮ４まで走行し、ノードＮ４を右折してリンクＬ５をノードＮ３まで走行し、ノードＮ３左折してもとの案内経路であるリンクＬ３に至る経路である。この場合、現在位置を別の道路にマッチングしてしまったので、リルート処理した結果誤ったガイダンス音声を発生してしまうことになり、利用者を混乱させるので、このような不具合を防止することが好ましい。

また、実際の自車位置が当初の案内経路であるリンクＬ２にあるので、このリルート処理は無駄な処理であり、利用者を混乱させるという不都合を生じる。この観点からもマッチング精度を向上させることが望まれている。

このような問題点を解決する技術として、下記の特許文献２（特開２００４−２７１２９３号公報）に開示された「ナビゲーション装置」が知られている。この特許文献２に開示されたナビゲーション装置は、表示部と、現在位置表示情報を記憶する履歴位置情報Ｄ
Ｂと、現在位置情報をＧＰＳから獲得する位置情報受信部と、現在位置情報を解析して現在位置を算出する位置情報解析部と、地図情報を記憶するＭＡＰＤＢと、車両の車速パルス値と進行方向を計測する計測部と、車速パルス及び進行方向と、直前の現在位置表示情報とから予測移動距離及び予測移動方向を算出し、現在位置と地図情報とに基づいて、測位位置情報を算出する中央処理部と、算出された予測移動距離、予測移動方向及び測位位置情報を記憶する位置情報ＤＢと、許容範囲の閾値テーブルを記憶する許容テーブルＤＢとを備えて構成されている。

そして、このナビゲーション装置においては、中央処理手段は、位置情報記憶手段に記憶されている予測移動距離及び予測移動方向から車両の予測移動位置を算出し、当該予測移動位置と許容テーブル記憶手段に記憶されている閾値テーブルに基づいて、予測位置範囲を決定し、位置情報記憶手段に記憶されている測位位置情報と予測位置範囲を比較して、測位位置情報が予測位置範囲内であれば、測位位置情報を現在位置表示情報とし、測位位置情報が予測位置範囲外であれば、予測移動位置を現在位置表示情報とするようにしている。

また、本願の出願人は、路線バスの運行管理におけるマッチング処理の精度を向上させる目的で、既に特願２００５−０１３９５７号の発明についての特許出願を行っている。

この特願２００５−０１３９５７号（以下、「先願１」という。）に開示された発明においては、路線バスの車両に設置される移動体端末装置と運行管理サーバとがネットワークを介して接続されるように構成されている。そして、移動体端末装置は、衛星航法に基づき位置を検出する位置検出手段と、自律航法手段と、通信手段と、マッチング手段と、路線ネットワークデータを記憶した路線データ記憶手段と、を備え、路線ネットワークデータは、所定のバス路線のネットワークデータのみで構成され、マッチング手段は、前記位置検出手段が検出した現在位置データを路線ネットワークデータにマッチング処理し、マッチング処理した現在位置データを、通信手段を介して運行管理サーバに送信するように構成されたものである。

また、先願１においては、駅前のバスターミナルなど、周囲にビルが密集しＧＰＳ測位におけるマルチパスの影響からマッチングエラーが生じ易いエリアにおいては、ＧＰＳ測位手段を使用せず、自律航法を使用した測位手段を用いて測位、マッチング処理するように構成されている。

図１２は、駅前のバスターミナルにおける経路探索用の道路ネットワークデータの１例を示す模式図である。駅前は基本的に右周りのロータリーになっている。この駅前には２系統の路線が運行されている。図１２の上方向から駅前のバスターミナルに入りバスターミナルを折り返して上方向に出てゆく経路Ｒ１をとる路線と、左右方向にこの駅前を経由する経路Ｒ２、Ｒ３をとる路線である。駅前は右回りのロータリーなので、道路ネットワークは図１２に示すノードＮ（図中の〇印）と、各ノード間をつなぐリンクＬ（図中の実線）のように構成されている。Ｔ１〜Ｔ３はそれぞれの路線におけるバス停留所を示している。

ノードＮは、一般の車載用ナビゲーションシステムと同様に交差点や分岐点、合流点に置かれ、比較的短いリンクでそれぞれ結ばれている。駅前のバスターミナルでは一般車両は通行禁止であり、ナビゲーションシステムがバス車両を対象とする場合には通常の道路ネットワークデータにバス専用の道路のネットワークデータを追加することが必要である。ナビゲーションシステムがバス車両のみを対象とする場合には、先願１のようにバス路線のみの道路ネットワークデータとすることもできる。

このような細かいリンクで構成されたネットワークでは、交差点や分岐が多い（それが当然と考えられていた）のでマッチングを誤る頻度も多くなる。例えば、図１２に代表的に参照符号を付してあるノードＮ１〜ノードＮ３とリンクＬ１〜Ｌ３のように、交差点、分岐点や合流点に置かれるのでその間は短いリンクで結ばれるため、狭い範囲にリンクが接近して設けられ、図１３のような道路構造の場所と同様にマッチング処理を誤る頻度が多くなる。

特開平８−６８６５６号公報（図１、図５） 特開２００４−２７１２９３号公報（図１、図４）

前述したように、図１３、図１４に示すように道路が狭い角度で分岐し、分岐した道路が分岐点以降狭い間隔で平行しているような道路構造の場所では特にマッチング処理でエラーが生じ易い。また、駅前のバスターミナルなど、周囲にビルが密集しＧＰＳ測位におけるマルチパスの影響からマッチングエラーが生じ易い。

しかしながら、上記特許文献１に開示された車載用ナビゲーション装置においては、誘導経路を優先してマッチング処理するものであるが、これは、車両が誘導経路に従って正しく走行しているという前提が満たされる限りにおいては、マッチングの精度を高めることができるが、車両が誘導経路から外れて走行している場合には、誤ったマッチングを行ってしまうという問題点があった。

また、上記特許文献２に開示された技術では、一定の閾値範囲を設定しておき、ＧＰＳにより測位した現在位置がその閾値範囲内にあればその測位位置を現在位置とするものであり、道路が狭い角度で分岐し、分岐した道路が分岐点以降、狭い間隔で平行しているような道路構造の場所では正確にマッチングを行える保証がないという問題点があった。

また、先願１に開示した発明は、バス路線のように設定された一定の経路を走行するバス車両などのマッチング処理においては効果を発揮するが、バス車両の運行路線が変わる都度、路線ネットワークデータを入れ換える必要が生じるという問題点があり、また、一般の車両には適用することができないという問題点があった。

本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、従来マッチング処理に用いている道路ネットワークデータが、交差点、分岐点、合流点にノードを設定して各ノード間をリンクで結ぶ構成をとっているため、これらの場所では狭い領域に複数の異なるリンクが接近して設けられている結果、マッチング処理を誤る頻度が高くなっていることを見出して本発明を完成するに至ったものである。

すなわち、本願の発明者は、経路探索用の道路ネットワークデータとは構成が異なり、分岐点にノードを設定せず、交差点、分岐点、合流点に接続されるリンクの途中にノードを設定し、各ノード間をノードから交差点、分岐点、合流点を通過して他のノードに至る複数のリンクで接続したマッチング用ネットワークデータを提供することによって、駅前のような複雑な道路構造においても、ノードの数を減らすことで交差点や分岐点、合流点でのマッチング処理の誤りを減らし、あるいは正しく修正することができ、マッチング精度を向上させ得ることを想到して本発明を完成するに至ったものである。

本発明は、前記の問題点を解消することを課題とし、マッチング処理の精度を向上させることのできるマッチング用ネットワークデータおよびマッチング用ネットワークデータの作成方法、ならびに、マッチング用ネットワークデータを有するナビゲーションシステム、経路探索サーバおよびナビゲーション端末装置を提供することを目的とするものである。

前記課題を解決するために、本願の請求項１にかかる発明は、
移動体の現在位置をノードとノード間を結ぶリンクにより表現されたネットワークデータのリンク上にマッチングするためのマッチング用ネットワークデータであって、
前記マッチング用ネットワークデータは、道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定し、前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とする。

また、本願の請求項２にかかる発明は、請求項１の発明にかかるマッチング用ネットワークデータにおいて、前記マッチング用ネットワークデータは、前記交差地点の手前に設定されたノードから、移動体の進行方向にそって移動可能な経路に設定された全てのノードの間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とする。

また、本願の請求項３にかかる発明は、請求項１または請求項２の発明にかかるマッチング用ネットワークデータにおいて、前記各リンクは同一の道路区間においては同じ座標データを有することを特徴とする。

本願の請求項４にかかる発明は、
移動体の現在位置をノードとノード間を結ぶリンクにより表現されたネットワークデータのリンク上にマッチングするためのマッチング用ネットワークデータの作成方法であって、
道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定するステップと、
前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定するステップと、を有することを特徴とする。

また、本願の請求項５にかかる発明は、請求項４の発明にかかるマッチング用ネットワークデータの作成方法において、前記交差地点の手前に設定されたノードから、移動体の進行方向にそって移動可能な経路に設定された全てのノードの間を結ぶそれぞれ１本のリンクを設定するステップを含むことを特徴とする。

また、本願の請求項６にかかる発明は、請求項４または請求項５の発明にかかるマッチング用ネットワークデータの作成方法において、前記各リンクには同一の道路区間においては同じ座標データを付与するステップを含むことを特徴とする。

本願の請求項７にかかる発明は、
現在位置を測位する測位手段を備え、移動体の現在位置をノードとノード間を結ぶリンクにより表現されたネットワークデータのリンク上にマッチングするためのマッチング用ネットワークデータを有するナビゲーションシステムであって、
前記マッチング用ネットワークデータは、道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定し、前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とするマッチング用ネットワークデータを有するナビゲーションシステム。

また、本願の請求項８にかかる発明は、請求項７の発明にかかるマッチング用ネットワークデータを有するナビゲーションシステムにおいて、
前記交差地点の手前に設定されたノードから、移動体の進行方向にそって移動可能な経路に設定された全てのノードの間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とする。

また、本願の請求項９にかかる発明は、請求項７または請求項８の発明にかかるマッチング用ネットワークデータを有するナビゲーションシステムにおいて、
前記各リンクには同一の道路区間においては同じ座標データを有することを特徴とする。

本願の請求項１０にかかる発明は、
現在位置を測位する測位手段を備え、移動体の現在位置をノードとノード間を結ぶリンクにより表現されたネットワークデータのリンク上にマッチングするためのマッチング用ネットワークデータを有するナビゲーションシステムを構成する経路探索サーバであって、
前記経路探索サーバは、道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定し、前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定して構成したマッチング用ネットワークデータを備えたことを特徴とする。

また、本願の請求項１１にかかる発明は、請求項１０の発明にかかる経路探索サーバにおいて、前記交差地点の手前に設定されたノードから、移動体の進行方向にそって移動可能な経路に設定された全てのノードの間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とする。

また、本願の請求項１２にかかる発明は、請求項１０または請求項１１の発明にかかる経路探索サーバにおいて、前記各リンクには同一の道路区間においては同じ座標データを有することを特徴とする。

本願の請求項１３にかかる発明は、
現在位置を測位する測位手段を備え、移動体の現在位置をノードとノード間を結ぶリンクにより表現されたネットワークデータのリンク上にマッチングするためのマッチング用ネットワークデータを有するナビゲーションシステムを構成するナビゲーション端末装置であって、
前記経路探索サーバは、道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定し、前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定して構成したマッチング用ネットワークデータを備えたことを特徴とする。

また、本願の請求項１４にかかる発明は、請求項１３の発明にかかるナビゲーション端末装置において、前記交差地点の手前に設定されたノードから、移動体の進行方向にそって移動可能な経路に設定された全てのノードの間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とする。

また、本願の請求項１５にかかる発明は、請求項１３または請求項１４の発明にかかるナビゲーション端末装置において、前記各リンクには同一の道路区間においては同じ座標データを有することを特徴とする。

請求項１、請求項２にかかる発明においては、マッチング用ネットワークデータは、道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定し、前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定して構成されている。
従って、マッチングのエラーが発生しやすい交差点、分岐点などにおいて、通過の可能性のある全てのリンク上に推定位置が継続して維持されることから、マッチングの精度を向上させることができ、また正しい現在位置への復帰が可能となる。このためには、自律航法手段によりノード通過後の移動距離（走行距離）を得てこれに基づいて、進行する可能性のある全てのリンク上の推定位置を示す地点情報を記憶手段に記憶し、自律航法手段により移動方向を得て当該移動方向に合致するリンク上の地点をマッチング位置として選択する処理を行えばよい。

請求項３にかかる発明においては、請求項１または請求項２の発明にかかるマッチング用ネットワークデータにおいて、前記各リンクは同一の道路区間においては同じ座標データを有する。
従って、マッチングするリンクを誤っていても、正しいリンクと座標が同じ区間は結果的に正しい位置を出力することができるようになる。

請求項４ないし請求項６にかかる発明においては、それぞれ請求項１ないし請求項３にかかる発明のマッチング用ネットワークデータを提供することができるようになる。

請求項７、請求項８にかかる発明においては、ナビゲーションシステムが道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定し、前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定して構成したマッチング用ネットワークデータを備える。
従って、マッチングのエラーが発生しやすい交差点、分岐点などにおいて、通過の可能性のある全てのリンク上に推定位置が継続して維持されることから、マッチングの精度を向上させることができ、また正しい現在位置への復帰が可能となる。

請求項９にかかる発明においては、請求項７または請求項８の発明にかかるナビゲーションシステムにおいて、前記各リンクは同一の道路区間においては同じ座標データを有する。
従って、マッチングするリンクを誤っていても、正しいリンクと座標が同じ区間は結果的に正しい位置を出力することができるようになる。

請求項１０ないし請求項１２にかかる発明においては、それぞれ請求項７ないし請求項９にかかる発明のナビゲーションシステムを構成する経路探索サーバを提供することができるようになる。

請求項１３ないし請求項１５にかかる発明においては、それぞれ請求項７ないし請求項９にかかる発明のナビゲーションシステムを構成するナビゲーション端末装置を提供することができるようになる。

以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。図１〜図３は駅前バスターミナルの道路におけるマッチング用ネットワークデータのノード構成、リンク構成を説明するための模式図であり、図４は、一般的な道路におけるマッチング用ネットワークデータの構成の他の例を示す模式図である。なお、以下の説明においては交差点、分岐点、合流点を総称して単に分岐点ということとする。

本発明の実施例にかかるマッチング用ネットワークデータは図１〜図４に示すように、経路探索用の道路ネットワークデータとは構成が異なり、分岐点にノードを設定せず、分岐点に接続されるリンクの途中にノードを設定し、各間をそれぞれのノードから分岐点を通過して他のノードに至る経路を示す複数のリンクで接続した構成としたものである。

すなわち、図１〜図３は、図１２において説明した駅前のバスターミナルにおける道路ネットワーク（バス路線ネットワーク）を本発明にかかる作成方法で作成したマッチング用ネットワークデータの構成を概念的に示すものである。図１に示すように本発明のマッチング用ネットワークデータは、分岐点Ｃ１〜Ｃ９にノードを設定せず、分岐点Ｃ１〜Ｃ９に接続されるリンクの途中にノードＮ１〜Ｎ４を設定している。

ノードＮ１〜Ｎ４を結ぶリンクは、図２に示すように、ノードＮ１からバスターミナルに入りノードＮ３を経由して折り返しノードＮ１に出てゆく経路Ｒ１（図１２参照）に相当するリンクＬ１、左右方向にノードＮ２とノードＮ４を経由する経路Ｒ２に相当するリンクＬ２、ノードＮ２から駅前に入りノードＮ３を経由してノードＮ４に出てゆく経路Ｒ３に相当するリンクＬ３、Ｌ４で構成されている。

このように、従来のネットワークデータではノード間を結ぶ特定の方向を持ったリンクは１本（リンクは有向性であるから、一方通行でない限り通常は上りと下りの２本で構成される）であるが、本発明によるマッチング用ネットワークデータでは、図２のリンクＬ１とリンクＬ３のように１本の道路上（座標が同じ道路上）で同じ向きに複数のリンクが存在する。座標が同じリンクは実際には重なっているが図２では説明の便宜上、離間して図示している。ナビゲーション装置が測位した現在位置をどのリンクにマッチングするかを判別するマッチング処理方法については後に詳細に説明する。

左右方向にノードＮ２とノードＮ４を経由する経路Ｒ２と、ノードＮ２から駅前に入りノードＮ３を経由してノードＮ４に出てゆく経路Ｒ３の路線が、駅前のノードＮ３（停留所Ｔ２：図１参照）が終点で、このノードＮ３（停留所Ｔ２）を始発として折り返すような運行車両がある場合には、図３に示すように太線のリンクＬａ、リンクＬｂを設定することによって経路（路線ネットワーク）を表すことができる。

本発明にかかるマッチング用ネットワークデータは図１、図２のようなバスターミナルにおける道路だけでなく、図４に示すような一般的な道路ネットワークについても同様に構成できる。図４において道路は分岐点Ｃ１で直進路と左折路に分岐し、分岐点Ｃ２で直進路と右折路に分岐し、分岐点Ｃ３で直進路、右折路、左折路に分岐している。分岐点Ｃ１〜Ｃ３にはノードは設定しておらず、各分岐点Ｃ１〜Ｃ３に接続するそれぞれの道路の途中にノードＮ１〜Ｎ８が設定されている。リンクＬ１〜Ｌ８は説明を簡略化するため１方向のリンクのみ図示されている。

各ノードＮ１〜Ｎ８間はリンクＬ０〜Ｌ８で接続されている。例えば、ノードＮ１とノードＮ２はリンクＬ２で接続され、ノードＮ１とノードＮ３はリンクＬ１で接続されている。同様にノードＮ３とノードＮ４はリンクＬ４で接続され、ノードＮ３とノードＮ５はリンクＬ３で接続され、ノードＮ５とノードＮ７はリンクＬ７で接続され、ノードＮ５とノードＮ８はリンクＬ８で接続され、ノードＮ５とノードＮ６はリンクＬ５で接続されている。

従って、図２と同様に同じ道路に複数の同方向のリンクが設定されている区間が生じる。例えば、ノードＮ１から分岐点Ｃ１の間には、リンクＬ１とリンクＬ２とが設定されており、同様にノードＮ３から分岐点Ｃ２の間には、リンクＬ３とリンクＬ４、ノードＮ５から分岐点Ｃ３の間にはリンクＬ５、リンクＬ７、リンクＬ８の３本のリンクが設定されている。

次に、図１〜図４に示した本発明にかかるマッチング用ネットワークデータを用いてマッチング処理する概念について図５を参照して説明する。図５に示すようにマッチング用ネットワークデータは、分岐点Ｃ１に接続される道路の途中にノードＮ１〜Ｎ４が設定され、ノードＮ１から分岐点Ｃ１を直進するリンクＬ１、分岐点Ｃ１を左折するリンクＬ２、分岐点Ｃ１を右折するリンクＬ３が設定されている。

ナビゲーション端末装置は測位手段として衛星航法手段と自律航法手段自動を備えており、マッチング処理においては、自律航法手段によりノード通過後の移動距離（走行距離）を得てこれに基づいて、進行する可能性のある全てのリンク上の推定位置を示す地点情報を記憶手段に記憶し、自律航法手段により移動方向を得て当該移動方向に合致するリンク上の地点をマッチング位置として選択する。

図１〜図４のようなマッチング用ネットワークデータを用い、このようなマッチング処理を行えば、マッチングのエラーが発生しやすい交差点、分岐点などにおいて、通過の可能性のある全てのリンク上に推定位置が継続して維持されることから、マッチングの精度を向上させることができ、また正しい現在位置への復帰が可能となる。

ナビゲーション端末装置は、測位手段選択部を備え、ＧＰＳ信号の受信状況や道路（リンク）構造等により、測位位置の信頼性が高いほうの測位手段を選択して現在位置を得るように構成されている。ナビゲーション端末装置が分岐点Ｃ１に接続しているリンク上のノードＮ１を通過した後のマッチング処理において、自車がとり得るリンクは、Ｌ１〜Ｌ３の３方向である。マッチング処理手段は、自律航法手段によりノードＮ通過後の移動距離（走行距離）に基づいて、上記可能性のある全てのリンクＬ１〜Ｌ３上の到達推定位置を地点情報（Ｐ１１〜Ｐ１３）として地点記憶手段に記憶する。この時の測位位置はＰ１であったとする。

ノードＮ通過後のナビゲーション端末装置の移動距離（走行距離）は、衛星航法手段（ＧＰＳ）による測位履歴から算出することもできるが、誤差が累積され、自律航法手段による距離計測よりも誤差が大きくなる場合があるので、自律航法手段による移動距離を用いることが好ましい。

さらにナビゲーション端末装置が走行し、測位位置がＰ２になった場合も同様の処理を行い、走行距離に基づいて全てのリンクＬ１〜Ｌ３上の到達推定位置を地点情報（Ｐ２１〜Ｐ２３）として地点記憶手段に記憶する。以下、測位位置を得る都度、同様に各リンクＬ１〜Ｌ３上の地点情報を逐次記憶してゆく。

次に、マッチング処理手段は、測位位置Ｐ１、Ｐ２のデータあるいは自律航法手段に備える舵角センサの出力から、ナビゲーション端末装置の進行方向（方位）を算出し、この方位に合致する（あるいは最も近い方位を持つ）リンクを判別する。図５の場合、リンクＬ２が進行方向に最も近い方位のリンクであり、そのリンク上の地点、すなわち、図５の場合、位置Ｐ２１（方位がＰ２到達時点まで決定できなかった場合は位置Ｐ２２）をマッチング位置として選択する。

測位手段選択部により衛星航法手段が選択された場合は、自律航法手段が選択された場合と同様に衛星航法手段２１２（ＧＰＳ）による測位履歴から進行方向（方位）を算出して、当該進行方向に最も近い方位を持つリンクを特定してマッチング位置を選択することもできるが、誤差が大きい場合は、衛星航法手段が測位した測位位置（現在位置）に最も近い推定位置の地点をマッチング位置として選択すればよい。

ナビゲーション端末装置２０が何れかのリンクＬ１〜Ｌ３を走行し、次のノードに到達したら、地点記憶手段に記憶した地点情報をリセットし、次の分岐点に接続される道路上に設定されたノードからの各リンクについて前記と同様のマッチング処理が実行される。このように、新たなノードに到達したときに各候補リンクの地点情報をリセットするように構成すれば、追跡する候補リンクの地点情報が一方的に増えてしまうこともない。あるいは所定地を越えた候補リンクの地点情報は追跡しない（維持しない）ようにして、候補リンク追跡の負荷を軽くすることもできる。

なお、衛星航法手段と自律航法手段の何れが測位した位置情報を用いるかは、測位手段選択部が両者の信頼度が高い方を判別して決定する。前述したように、衛星航法手段の測位結果には１０ｍ程度の誤差があることから、半径１０ｍの範囲内に案内経路のリンクと隣接する他の道路のリンクが存在するかを判別し、この範囲内に他の道路のリンクが存在する場合は自律航法手段による測位結果を用いる。なお、余裕をもって判別するためにはこの判別範囲を１０ｍ以内でなく２０ｍ以内の範囲とすればよい。

トンネルの中で分岐するような場合も、衛星航法手段（ＧＰＳ）が使用できないので、自律航法手段を選択する。マルチパスの影響が大きくなるエリアが特定されていれば、当該エリア内でも同様に自律航法手段が選択される。なお、衛星航法手段（ＧＰＳ）の信頼度が高いときに、ＧＰＳによる測位位置から離れすぎたリンクは候補リンクとせず、地点情報の維持（記憶）を行わないようにして、制御手段の処理負荷を軽くしても良い（例えばＧＰＳの信頼度が十分あってＧＰＳによる測位位置から２００ｍ以上離れた候補リンクは対象としないなどの判別を行う）。

図６は、上記の測位手段選択の概念を説明するための模式図である。なお、図６のマッチング用ネットワークデータは図１３の道路構造に対応するものである。ナビゲーション端末装置が分岐点Ｃ１の手前に設定されたノードＮ１を通過すると、分岐点Ｃ１を通るリンクは、リンクＬ１とリンクＬ２の２つが設定されており、自律航法手段から得られる走行距離に基づいて、走行可能性のある各リンクＬ１、Ｌ２についてそのリンク上における推定位置の位置情報が逐次地点記憶手段に記憶されてゆく。

測位手段選択部は、以下のようにして衛星航法手段と自律航法手段のうち信頼性の高いほうの測位結果を選択する。まず、区間Ａ１においてはリンクＬ１とリンクＬ２との間隔が例えば１０ｍ以内であり、この間は、衛星航法手段の測位誤差の範囲内にリンクＬ１とＬ２が存在し、衛星航法手段による測位結果の信頼性は自律航法手段の測位結果よりも低くなるので、自律航法手段の測位結果が選択される。

区間Ａ２においてはリンクＬ１とリンクＬ２の間隔が１０ｍ以上になり、この間は、衛星航法手段測位誤差の範囲内には一方のリンクＬ１またはＬ２しか存在しないため、衛星航法手段の測位結果の信頼性が回復するので、衛星航法手段の測位結果が選択される。なお、一般には、衛星航法手段の測位結果によりマッチングされたリンクに対する測位位置のばらつきを監視しナビゲーション端末装置が走行しているリンクを追跡する処理が行われるが、この間においてはこのような処理を併用してもよい。

区間Ａ３においては、リンクＬ１とリンクＬ２が立体交差するため、両リンクＬ１、Ｌ２の間隔が再び１０ｍ以内となり、この区間Ａ３では区間Ａ１と同様に自律航法手段による測位結果が選択される。区間Ａ３に入った時ノードＮ１からのナビゲーション端末装置の走行距離によるリンクＬ１上の地点は位置Ｐａ、リンクＬ２上の地点は位置Ｐｂである。

この時にナビゲーション端末装置の走行方向（方位）を自律航法手段から取得すると、ナビゲーション端末装置はリンクＬ２を走行して右方向にカーブしてリンクＬ１の上（または下）を通過してゆくから、図中の矢印Ｄの方位に変化する。この方位に該当する（または最も近い方向の）リンクはリンクＬ２であるから、マッチング処理手段は、測位地点Ｐ４における測位情報をマッチングするリンクとしてリンクＬ２を選択する。この結果、測位地点Ｐ４はリンクＬ２上の推定位置Ｐａに正しくマッチングされることになる。

このようなマッチング処理を行えば、本発明の如く、座標の同じ複数のリンクが存在するネットワークデータの構成であっても、ナビゲーション端末装置が走行を継続する間に自車の正確な進行方向（方位）が得られるため、より正確なマッチングを行うことができる。

また、ナビゲーション端末装置が進行する可能性のある複数のリンクについて、各リンク上の走行距離に該当する地点情報を地点記憶手段に蓄積しているから、万が一マッチングを誤っていても正しい位置への復帰が可能となる。すなわち、現在位置を選択してマッチング処理しても、他の候補リンクについて走行距離情報からリンク上の位置が更新維持される。測位を繰り返すうちに、もし他のリンク上の位置の方が正しいと判断したら、そちらの候補に変更される。

この修正までの時間あるいは移動距離（走行距離）は、ナビゲーション端末装置の走行方向が定まる短い時間あるいは距離の間に行うことができるからリルート処理要求を行う前に正しいリンクへのマッチング修正ができ、無駄なリルート処理を行うようなケースを減少させることもできる。

次に、本発明にかかるマッチング用ネットワークデータを用いたナビゲーションシステム１０の構成について図７を参照して説明する。このナビゲーションシステム１０は、図７のブロック図に示すように、ネットワーク１２を介して接続される車載用のナビゲーション端末装置２０と経路探索サーバ３０とを備えて構成されている。

経路探索サーバ３０は、ナビゲーション端末装置２０から、出発地、目的地などの経路探索条件に基づいて最適な経路を探索して案内経路のデータや地図データを配信する。ナビゲーション端末装置２０は地図データ、案内経路のデータ、ナビゲーション端末装置２０の現在位置（自車位置）を重ね合わせて表示手段に表示し、目的地までの経路のガイダンスを受けるように構成されている。

経路探索サーバ３０は、制御手段３１１、通信手段３１２、配信データ編集手段３１３、経路探索手段３１４、経路探索用の道路ネットワークデータ３１５を蓄積したデータベース、地図データ３１６を蓄積したデータベースと、本発明にかかるマッチング用ネットワークデータ３１７を蓄積したデータベースを備えている。ナビゲーションシステム１０が歩行者用のナビゲーション機能を備える場合には、徒歩専用の道路を探索するための歩行者ネットワークデータや交通機関を用いた経路探索のための交通ネットワークデータを蓄積したデータベース（図示せず）を備える。道路ネットワークデータ３１５は図１１を参照して説明したように構成され、マッチング用ネットワークデータ３１７は図１〜図４を参照し説明したように構成されている。

制御手段３１１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３１２は、ネットワーク１２を介してナビゲーション端末装置２０と通信するためのインターフェースである。配信データ編集手段３１３は、経路探索の結果得た最適な案内経路のデータや地図データをナビゲーション端末装置２０に配信するためのデータに編集するためのものである。

経路探索手段３１４はマルチモーダルな経路探索エンジンであって、ナビゲーション端末装置２０から送信された検索条件（出発地または現在地、目的地、移動手段、出発時刻など）に基づいて道路ネットワークデータ３１５を参照して出発地または現在地から目的地までの最適な経路（距離や所要時間が最小になる経路）を探索する。探索された案内経路は配信データ編集手段３１３で編集されナビゲーション端末装置２０に配信される。経路探索手段３１４は自動車と徒歩、徒歩と交通機関を併用した経路探索機能を有する場合、経路探索手段３１４はマルチモーダルな経路探索エンジンを用いる。このような経路探索エンジンは例えば特開２０００−２５８１８４号公報などに開示されている。経路の探索方法としては周知のダイクストラ法と呼ばれる手法が適用される。

また、経路探索サーバ３０はナビゲーション端末装置２０に必要な地図データを配信する。地図データ３１６は、緯度、経度によって所定の大きさに分割された単位地図からなり、通常、ナビゲーション端末装置２０の現在位置を中心に上下、左右の９枚分の地図がナビゲーション端末装置２０に配信される。ナビゲーション端末装置２０が移動し、地図データが不足すると、ナビゲーション端末装置２０は不足分の単位地図の配信を経路探索サーバ３０に要求し、所用の単位地図の配信を受ける。

ナビゲーション端末装置２０は経路探索サーバ３０から地図データ、案内経路のデータ、マッチング用ネットワークデータの配信を受けると、地図、案内経路、自車現在位置を表示し、利用者は目的地までの経路の案内を受けることができる。

ナビゲーション端末装置２０は、図７に示すように、制御手段２１１、衛星航法手段２１２、自律航法手段２１３、測位手段選択部２１４、マッチング処理手段２１５、配信要求編集手段２１６、通信手段２１７、配信データ記憶手段２１８、地点記憶手段２１９、表示手段２２０、操作・入力手段２２１を備えて構成されている。

制御手段２１１は、図示してはいないがＲＡＭ、ＲＯＭを有するマイクロプロセッサ（ＣＰＵ）を備えて構成され、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。操作・入力手段２２１は、数字キーやアルファベットキー、その他の機能キー、選択キー、スクロールキーなどからなる操作・入力のためのものであり、出力手段である表示手段２２０に表示されるメニュー画面から所望のメニューを選択し、あるいは、キーを操作して種々の入力操作を行うものである。従って、表示手段２２０は操作・入力手段２２１の一部としても機能する。通信手段２１７は、ネットワーク１２を介して経路探索サーバ３０と通信するためのインターフェースである。

配信要求編集手段２１６は、操作・入力手段２２１を使用して入力された出発地、目的地、あるいは、衛星航法手段２１２または自律航法手段２１３で測位したナビゲーション端末装置２０の現在位置を出発地として、これらの情報を経路探索条件とした経路探索要求を編集するものである。経路探索条件には移動手段（自動車、徒歩、交通機関など）、出発時刻や到着時刻などを設定することもできる。また、配信要求編集手段２１６は、ナビゲーション端末装置２０の移動に伴い、経路探索サーバ３０から配信を受けている地図データに不足が生じた場合に不足分の地図データを要求する地図データ要求を編集し、経路探索サーバ３０に送信する。

配信データ記憶手段２１８は、経路探索サーバ３０から配信された経路探索結果である案内経路データ、地図データ、ガイダンスなどを記憶するものであり、これらのデータは必要に応じて配信データ記憶手段２１８から読み出され、表示手段２２０に表示される。一般的には、ナビゲーション端末装置２０の現在位置を含む一定の縮尺、一定の範囲の地図に、案内経路と、ナビゲーション端末装置２０の現在位置を示すマークを重ね合わせて該現在位置マークが表示画面の中心になるように表示する。また、経路探索サーバ３０から配信される案内経路データに音声ガイド（例えば、「この先、３００ｍ交差点です。左折して下さい」などの音声メッセージ）のデータが付加されている場合は、スピーカを介して音声メッセージを再生出力してユーザをガイドする。

衛星航法手段２１２はＧＰＳ受信機を備えＧＰＳ衛星信号を受信処理してナビゲーション端末装置２０の現在位置を測位する第１の測位手段である。自律航法手段２１３は加速度センサー、舵角センサー、ジャイロ、車速センサーなどを備え、ナビゲーション端末装置２０の現在位置を測位する第２の測位手段である。先に述べたように、一般的にはＧＰＳを使用した衛星航法による測位では自車の絶対位置が測位できるので、天空が開け、ＧＰＳ衛星信号の受信状態が良い場所では衛星航法手段２１２による測位結果が優先されて用いられる。

トンネル内などＧＰＳ衛星信号を受信できない場所では当然に自律航法手段２１３による測位結果が用いられる。またＧＰＳによる測位結果には１０ｍ程度の測位誤差が含まれるため、１０ｍの範囲内に案内経路以外のリンクが存在する場所では、自律航法手段２１３による測位結果のほうが衛星航法手段２１２による測位結果より信頼度が高くなるので自律航法手段２１３による測位結果が優先されて用いられる。マルチパスの影響により衛星航法手段２１２による測位結果の誤差が大きくなる場所においても同様である。測位手段選択部２１４は以上のような条件を判別して衛星航法手段２１２と自律航法手段２１３の何れかの測位結果を選択する。なお、自律航法手段２１３による測位結果は、測位手段選択部２１４の選択のいかんにかかわらず保持され、自車の移動距離や方位等の算出結果も保持される。

マッチング処理手段２１５は、経路探索サーバ３０から配信されたマッチング用ネットワークデータを用いて衛星航法手段２１２、自律航法手段２１３等により測位した現在位置を道路上に補正する処理を行うものである。なお、経路探索サーバ３０から配信されるマッチング用ネットワークデータは、案内経路にそった必要範囲のデータであってよい。

マッチング処理手段２１５は、分岐点に接続される道路の途中に設定されたノードを通過後のナビゲーション端末装置２０の移動距離（走行距離）に基づいて、ナビゲーション端末装置２０が到達している可能性のある各リンク上のそれぞれの地点情報を地点記憶手段２１９に記憶し、測位手段選択部２１４が衛星航法測位手段２１２と自律航法測位手段２１３による測位出力のうち信頼度の高い測位手段を選択する。

そして、マッチング処理手段２１５は、地点記憶手段２１９に記憶された地点情報を参照して、測位手段選択部で選択された測位手段が測位した現在位置に最も近い地点を選択してこの地点をマッチング位置として選択する処理を行う。

測位手段選択部２１４により自律航法手段２１３が選択された場合はナビゲーション端末装置２０の走行方位が得られるので、当該走行方位に合致した（最も近い）リンク上の地点を選択してその地点をマッチング位置とする。衛星航法手段２１２が選択された場合は、衛星航法手段２１２が測位した測位位置（現在位置）に最も近い推定位置の地点をマッチング位置として選択すればよい。

図８のフローチャートを参照してこのナビゲーションシステム１０におけるマッチング処理の手順を詳細に説明する。ナビゲーション端末装置２０はステップＳ１１の処理において衛星航法手段２１２、自律航法手段２１３がそれぞれ現在位置を測位する。

ステップＳ１２の処理において、マッチング処理手段２１５は、ナビゲーション端末装置２０が分岐点手前に設定されたノードを通過したかを判別する。このノードを通過していない場合には、ステップＳ１３の処理において、通常（従来と同様）の投影法によるマッチング処理を行いリターンする。

ステップＳ１２の処理において、前記のノードを通過したと判別された場合には、ステップＳ１４の処理に進み、マッチング処理手段２１５は自律航法手段２１３からノード通過後の走行距離のデータを受領する。そしてステップＳ１５の処理において、ノード通過後の各リンク毎に走行距離相当の推定位置の地点情報を地点記憶手段２１９に記憶する。

ステップＳ１６の処理において、測位手段選択部２１４は図３において説明した選択条件に従って、衛星航法手段２１２、自律航法手段２１３の何れか測位結果の信頼性の高いほうの測位手段を選択する。衛星航法手段２１２が選択された場合にはステップＳ２０の処理に進み、自律航法手段２１３が選択された場合はステップＳ１７の処理に進む。

衛星航法手段２１２が選択された場合、マッチング処理手段２１５はステップＳ２０の処理において衛星航法手段２１２の測位した位置情報（測位データ）を選択し、ステップＳ２１の処理において、各リンク上の推定位置の地点のうち、測位した現在位置に最も近い地点をマッチング位置として選択する。そしてステップＳ２２の処理に進む。

一方、自律航法手段２１３が選択された場合、マッチング処理手段２１５はステップＳ１７の処理において自律航法手段２１３の測位した位置情報（測位データ）を選択し、ステップＳ１８の処理において、自律航法手段２１３が備える舵角センサ、ジャイロなどにより得られた走行方位情報を取得する。そして、ステップＳ１９の処理において、走行方位と合致するリンク（または最も近い向きのリンク）を選択し、図３において説明したように当該リンク上の推定位置の地点をマッチング位置として選択する。

マッチング処理手段２１５はステップＳ２２の処理においてナビゲーション端末装置２０が次の分岐点手前のノードに到達したかを判別し、次の分岐点手前のノードに到達していなければリターンする。次の分岐点手前のノードに到達したならば、ステップＳ２３の処理において地点記憶手段２１９に記憶したリンク、各リンク上の地点情報をクリア（リセット）し、リターンする。

なお、上記の実施例においては、ナビゲーション端末装置２０の走行方位は自律航法手段２１３により検出する例を説明したが、精度は若干劣るが衛星航法手段２１２において測位履歴をもとに算出することも可能である。その場合、ステップＳ２１における処理を自律航法手段２１３が選択された場合のステップＳ１８、ステップＳ１９における処理と同様にすることも可能である。

次に、図９のフローチャートを参照してナビゲーション端末装置２０がリルート要求を行う手順について説明する。ステップＳ３１の処理においてマッチング処理手段２１５が図８のフローチャートの処理手順によってマッチング処理すると、ステップＳ３２の処理においてマッチングされたリンクが案内経路のリンクであるか否かが判別される。マッチングされたリンクが案内経路のリンクである場合はステップＳ３１の処理に戻る。

マッチングされたリンクが案内経路のリンクでない場合、ナビゲーション端末装置２０はステップＳ３３の処理において、時間または走行距離を監視する。そしてステップＳ３４の処理において、時間または走行距離が一定の範囲を超えたか否かが判別される。一定の範囲を超えていなければ、ステップＳ３１の処理に戻り、時間または走行距離の計測を継続する。

ステップＳ３４の判別処理において、時間または走行距離が一定の範囲を超えた場合にはステップＳ３５の処理においてリルート処理要求が生成され、配信要求編集手段２１６で経路探索サーバ３０に対するリルート要求情報が編集される。編集されたリルート処理要求はナビゲーション端末装置２０から経路探索サーバ３０に送信され、経路探索サーバ３０はマッチングされた現在位置を出発地として目的地までの経路を再探索する。

このようなマッチング処理を行えば、ナビゲーション端末装置２０が走行を継続する間に自車の正確な進行方向（方位）が得られるため、より正確なマッチングを行うことができる。例えば、図１０のリンクＬ４は、図２のマッチング用ネットワークデータ上の経路Ｒ３（図１２参照）の路線上を走行する車両の経路履歴である。このエリアでは自律航法手段２１３の測位位置の信頼性が高く、自律航法手段２１３が測位手段として選択される。車両がバスターミナルのロータリーを出たところで自律航法手段２１３のジャイロの出力から得られる進行方向が定まるのでこれに合致する方向のリンクＬ４、すなわち、ノードＮ４に向かうリンクＬ４がマッチングするリンクとして選択され、当該リンクＬ４上の地点がマッチング位置として選択される。

また、正しいリンクでないリンクにマッチングエラーを生じていても、他のリンク上の位置の方が正しいと判断したら、そちらの候補に変更される。この修正までの時間あるいは移動距離（走行距離）は、ナビゲーション端末装置２０の走行方向が定まる短い時間あるいは距離の間に行うことができるからリルート処理要求を行う前に正しいリンクへのマッチング修正ができ、無駄なリルート処理を行うようなケースを減少させることもできる。
また本発明のように交差点や分岐にノードを置かない方が、ノード通過時に過去の候補リンク上の地点情報を消去することも減るので、信頼度の高い現在位置候補の中から現在地を選ぶことが出来る。

本発明は、経路の定められたバスの運行監視以外にも、一般的なカーナビなどにも適用することができる。現在位置の検出を誤りやすい複雑な交差点などにおいて、交差点内にはノードを置かず、交差点の手前から、とり得る経路全てをリンクで表現し、最も信頼度が高い現在位置を選ぶようにしてもよい。もしマッチングするリンクを誤っていても、正しいリンクと座標が同じ区間は結果的に正しい位置を出力することができるようになる。

また、車両にＧＰＳによる衛星航法手段と車両の走行距離に基づく自律航法手段のみを搭載し、推定位置算出とその地点を記憶する手段と道路ネットワークデータは通信ネットワークで結んだ経路探索サーバに持つ構成であってもよいし、スタンドアロン型のナビゲーションシステムであってもよい。

図１は、駅前バスターミナルの道路における本発明にかかるマッチング用ネットワークデータのノード構成を説明するための模式図である。 図２は、駅前バスターミナルの道路における本発明にかかるマッチング用ネットワークデータのリンク構成を説明するための模式図である。 図３は、駅前バスターミナルの道路における本発明にかかるマッチング用ネットワークデータのリンク構成を説明するための模式図である。 図４は、一般的な道路における本発明にかかるマッチング用ネットワークデータの構成を示す模式図である。 図５は、本発明にかかるマッチング用ネットワークデータを用いたマッチング処理の概念を示す図である。 図６は、衛星航法手段と自律航法手段によるそれぞれの測位出力の選択処理を説明するための模式図である。 図７は、本発明にかかるマッチング用ネットワークデータを用いたナビゲーションシステムの構成を示すブロック図である。 図８は、図７のナビゲーションシステムにおけるマッチング処理の手順を示すフローチャートである。 図９は、図７のナビゲーションシステムにおけるリルート処理要求の手順を示すフローチャートである。 図１０は、図２のマッチング用ネットワークデータ上のマッチング結果を説明するための説明図である。 図１１は、経路探索のための道路ネットワークデータを説明するための模式図である。 図１２は、駅前のバスターミナルにおける経路探索用の道路ネットワークデータを示す模式図である。 図１３は、分岐路におけるマッチング処理を説明するための模式図である。 図１４は、図１３においてマッチングエラーが生じた場合の処理を説明するための模式図である。

符号の説明

Ｎ、Ｎ１〜Ｎ８・・ノード
Ｌ、Ｌ０〜Ｌ８・・リンク
Ｃ１〜Ｃ８・・・・分岐点、交差点、合流点
Ｔ１〜Ｔ３・・・・停留所
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・ナビゲーション端末装置
２１１・・・制御手段
２１２・・・衛星航法手段
２１３・・・自律航法手段
２１４・・・測位手段選択部
２１５・・・マッチング処理手段
２１６・・・配信要求編集手段
２１７・・・通信手段
２１８・・・配信データ記憶手段
２１９・・・地点記憶手段
２２０・・・表示手段
２２１・・・操作・入力手段
３０・・・・経路探索サーバ
３１１・・・制御手段
３１２・・・通信手段
３１３・・・配信データ編集手段
３１４・・・経路探索手段
３１５・・・道路ネットワークデータ
３１６・・・地図データ
３１７・・・マッチング用ネットワークデータ

Claims (15)

1. 移動体の現在位置をノードとノード間を結ぶリンクにより表現されたネットワークデータのリンク上にマッチングするためのマッチング用ネットワークデータであって、
   前記マッチング用ネットワークデータは、道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定し、前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とするマッチング用ネットワークデータ。
2. 前記マッチング用ネットワークデータは、前記交差地点の手前に設定されたノードから、移動体の進行方向にそって移動可能な経路に設定された全てのノードの間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とする請求項１に記載のマッチング用ネットワークデータ。
3. 前記各リンクは同一の道路区間においては同じ座標データを有することを特徴とする請求項１または請求項２に記載のマッチング用ネットワークデータ。
4. 移動体の現在位置をノードとノード間を結ぶリンクにより表現されたネットワークデータのリンク上にマッチングするためのマッチング用ネットワークデータの作成方法であって、
   道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定するステップと、
   前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定するステップと、を有することを特徴とするマッチング用ネットワークデータの作成方法。
5. 前記交差地点の手前に設定されたノードから、移動体の進行方向にそって移動可能な経路に設定された全てのノードの間を結ぶそれぞれ１本のリンクを設定するステップを含むことを特徴とする請求項４に記載のマッチング用ネットワークデータの作成方法。
6. 前記各リンクには同一の道路区間においては同じ座標データを付与するステップを含むことを特徴とする請求項４または請求項５に記載のマッチング用ネットワークデータの作成方法。
7. 現在位置を測位する測位手段を備え、移動体の現在位置をノードとノード間を結ぶリンクにより表現されたネットワークデータのリンク上にマッチングするためのマッチング用ネットワークデータを有するナビゲーションシステムであって、
   前記マッチング用ネットワークデータは、道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定し、前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とするマッチング用ネットワークデータを有するナビゲーションシステム。
8. 前記交差地点の手前に設定されたノードから、移動体の進行方向にそって移動可能な経路に設定された全てのノードの間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とする請求項７に記載のマッチング用ネットワークデータを有するナビゲーションシステム。
9. 前記各リンクには同一の道路区間においては同じ座標データを有することを特徴とする請求項７または請求項８に記載のマッチング用ネットワークデータを有するナビゲーションシステム。
10. 現在位置を測位する測位手段を備え、移動体の現在位置をノードとノード間を結ぶリンクにより表現されたネットワークデータのリンク上にマッチングするためのマッチング用ネットワークデータを有するナビゲーションシステムを構成する経路探索サーバであって、
    前記経路探索サーバは、道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定し、前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定して構成したマッチング用ネットワークデータを備えたことを特徴とする経路探索サーバ。
11. 前記交差地点の手前に設定されたノードから、移動体の進行方向にそって移動可能な経路に設定された全てのノードの間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とする請求項１０に記載の経路探索サーバ。
12. 前記各リンクには同一の道路区間においては同じ座標データを有することを特徴とする請求項１０または請求項１１に記載の経路探索サーバ。
13. 現在位置を測位する測位手段を備え、移動体の現在位置をノードとノード間を結ぶリンクにより表現されたネットワークデータのリンク上にマッチングするためのマッチング用ネットワークデータを有するナビゲーションシステムを構成するナビゲーション端末装置であって、
    前記経路探索サーバは、道路ネットワークデータにおける道路の交わる交差地点にノードを設定することなく、前記交差地点に接続されるそれぞれの道路の途中にノードを設定し、前記交差地点を経由して前記各ノード間を結ぶそれぞれ１本のリンクを設定して構成したマッチング用ネットワークデータを備えたことを特徴とするナビゲーション端末装置。
14. 前記交差地点の手前に設定されたノードから、移動体の進行方向にそって移動可能な経路に設定された全てのノードの間を結ぶそれぞれ１本のリンクを設定して構成したことを特徴とする請求項１３に記載のナビゲーション端末装置。
15. 前記各リンクには同一の道路区間においては同じ座標データを有することを特徴とする請求項１３または請求項１４に記載のナビゲーション端末装置。

Images