JP2009150907A

JP2009150907A - 走行リンク特定システム

Info

Publication number: JP2009150907A
Application number: JP2009076975A
Authority: JP
Inventors: Kenji Nagase; 健児長瀬; Masami Kususe; 雅実楠瀬
Original assignee: Aisin AW Co Ltd
Current assignee: Aisin AW Co Ltd
Priority date: 2009-03-26
Filing date: 2009-03-26
Publication date: 2009-07-09
Anticipated expiration: 2025-12-26
Also published as: JP4766139B2

Abstract

【課題】車両の位置情報からの走行経路の正確な特定を可能とした走行リンク特定システムを提供する。
【解決手段】プローブカー２から送信されたプローブ情報の内、特にプローブカー２の２点の位置座標からプローブカー２の走行したリンクを検出し、検出されたリンクに対して接続される接続リンクが上位レベルの地図データで同一リンクであると判定された場合（Ｓ１４：ＹＥＳ）に、同一リンクであると判定された接続リンクを走行リンクに特定する（Ｓ１８）ように構成する。
【選択図】図８

Description

本発明は、取得した車両の位置情報から車両の走行した走行リンクを特定する走行リンク特定システムに関する。

近年、車両の走行案内を行い、運転者が所望の目的地に容易に到着できるようにしたナビゲーション装置が車両に搭載されていることが多い。ここで、ナビゲーション装置とは、ＧＰＳ受信機などにより自車の現在位置を検出し、その現在位置に対応する地図データをＤＶＤ−ＲＯＭやＨＤＤなどの記録媒体またはネットワークを通じて取得して液晶モニタに表示することが可能な装置である。更に、かかるナビゲーション装置には、所望する目的地を入力すると、自車位置から目的地までの最適経路を探索する経路探索機能を備えており、ディスプレイ画面に誘導経路を表示するとともに、交差点に接近した場合等には音声による案内をすることによって、運転者を所望の目的地まで確実に案内するようになっている。

また、従来のナビゲーション装置では、上記経路の探索を行う際に、例えば、高速道路、有料道路、国道、主要地方道、県道、細街路等の道路種別や、右左折禁止、一方通行等の交通規制の有無や、リンクの長さ、即ちリンク長の大小、道路の幅員の大小、車線数の多寡等によって、それぞれ、リンク又はリンク間（ノード）に各種のコストが設定される。そして、自車位置から目的地までの最適経路を探索する際においては、地図データに記憶されたリンクに沿って出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積されたコストと目的地側から累積されたコストとを加算した値、即ちコスト加算値が算出されるようになっている。その結果、算出されたコスト加算値が最小になる経路が誘導経路として設定される。

ここで、上記の経路探索に用いられるコストやリンクを通過するのに必要な旅行時間を設定する要素の一つとして、リンクの長さや種類のみでは判別できない実際の交通情報（渋滞情報等）が必要となる。従来において、このような交通情報は、道路交通情報システム（ＶＩＣＳ）に代表されるように、路側に設置されたセンサ等を用いて収集されている。また、プローブカーと呼ばれる路面を実際に走行する車両自体から交通情報を収集する仕組みについても導入されている。
例えば、２００３−２８１６７４号公報には、指定された２点のポイントをプローブカーが通過する通過時刻を算出することにより、ポイント間の旅行時間の特定や交通混雑があるか否かの判定を行うことが可能な交通情報処理システムについて記載されている。

特開２００３−２８１６７４号公報（第７頁〜第１０頁、図２１〜２４）

しかしながら、前記特許文献１に記載の交通情報処理システムでは、２点のポイントにおける通過時刻に基づいて、交通混雑や旅行時間等の各種パラメータの判定や算出を行うが、そのポイント間において車両がどのような経路を走行したのかを判定することはできなかった。
即ち、車両の中にはポイント間を最短距離で走行する車両もあれば、走行の容易さを優先して遠回りをして走行する車両もある。特に、そのポイントの間が相当離れており、多数の経路パターンが存在するような場合には、通過時刻のみに基づいた判定及び算出方法では、交通混雑や旅行時間等の正確な判定及び算出をすることができなかった。

本発明は前記従来における問題点を解消するためになされたものであり、取得した車両の位置情報から車両が走行した走行リンクを特定することが可能となり、特定した走行リンクに基づいた交通混雑や旅行時間等の正確な判定及び算出をすることを可能とした走行リンク特定システムを提供することを目的とする。

前記目的を達成するため本願の請求項１に係る走行リンク特定システム（１）は、所定距離間隔又は所定時間間隔で車両の現在位置に係る位置情報を取得する情報取得手段（６）と、地図データを道路網の情報量に基づいて複数レベルに階層化して記憶する地図データ記憶手段（１６）と、前記情報取得手段により取得した位置情報に基づいて、前記地図データ記憶手段に記憶された所定のレベルの地図データから前記車両が走行した２以上のリンクを検出する位置リンク検出手段（１１）と、前記複数レベルの地図データにおけるリンク毎の接続関係を記憶する接続関係記憶手段（１６）と、前記接続関係記憶手段に記憶された接続関係に基づいて、前記位置リンク検出手段によって検出された各リンクの間を接続する接続リンクが、検出された各リンクと前記所定のレベルより道路網の情報量の少ない上位レベルの地図データにおいて前記検出された各リンクと同一リンクであるか否かを判定する同一リンク判定手段（１１）と、前記同一リンク判定手段によって同一リンクであると判定された場合に、当該同一リンクと判定された接続リンクを前記車両が走行した走行リンクに特定する走行リンク特定手段（１１）と、を有することを特徴とする。

また、請求項２に係る走行リンク特定システム（１）は、請求項１に記載の走行リンク特定システムにおいて、前記走行リンク特定手段（１１）によって特定された走行リンクと前記走行リンクを前記車両が走行する所要時間とに基づいて、前記走行リンクの旅行時間を算出する旅行時間算出手段（１１）を有することを特徴とする。

前記構成を有する請求項１の走行リンク特定システムでは、検出された各リンクを接続する接続リンクが、上位レベルの地図データにおいて検出された各リンクと同一リンクであると判定された場合に、同一リンクであると判定された接続リンクを車両が走行した走行リンクに特定するので、レベルの異なる地図データを考慮して、取得した車両の位置情報から車両が走行した走行リンクを正確に予測することが可能となる。従って、特定した走行リンクに基づいた交通混雑や旅行時間等の正確な判定及び算出をすることが可能となる。

また、請求項２の走行リンク特定システムでは、特定された走行リンクと走行リンクを車両が走行する所要時間とに基づいて、走行リンクの旅行時間を算出するので、実際にリンクを走行した車両からの情報に基づいて走行リンクの旅行時間を正確に算出することが可能となる。

本実施形態に係る走行リンク特定システムの概略構成図である。本実施形態に係る走行リンク特定システムの特にプローブ情報センタの構成について示したブロック図である。本実施形態に係る走行リンク特定システムの特に端末車両の構成について示したブロック図である。本実施形態に係る走行地点テーブルを示した図である。本実施形態に係るリンク統計ＤＢの記憶領域を示した図である。本実施形態に係る走行履歴ＤＢの記憶領域を示した図である。本実施形態に係る走行リンク特定システムにおける走行リンク特定処理プログラムのフローチャートである。本実施形態に係るリンク補完処理プログラムのフローチャートである。ステップ４における走行リンクの旅行時間の算出方法について説明した説明図である。ステップ２で検出された２点の位置座標に対応するリンクが同一のリンクである場合を示した模式図である。ステップ２で検出された２点の位置座標に対応するリンクが互いに接続するリンクである場合を示した模式図である。ステップ２で検出された２点の位置座標に対応するリンクの間を接続する一又は複数のリンクの組合せが一の組合せに特定できる場合を示した模式図である。ステップ２で検出された２点の位置座標に対応するリンクの間を接続する一又は複数のリンクの組合せが一の組合せに特定できる場合を示した模式図である。ステップ２で検出された２点の位置座標に対応するリンクに接続する接続リンクが上位レベルの地図データで同一のリンクである場合を示した模式図である。ステップ２で検出された２点の位置座標に対応するリンクに接続する接続リンクが道なりの関係にある場合、及びリンクの間に過去にプローブカーが走行したリンクがあると判定された場合を示した模式図である。ステップ１９〜ステップ２１の処理における走行リンクの特定方法について説明した説明図である。本実施形態に係る走行リンク特定システムにおける交通情報配信処理プログラムのフローチャートである。

以下、本発明に係る走行リンク特定システムについて具体化した一実施形態に基づき図面を参照しつつ詳細に説明する。
先ず、本実施形態に係る走行リンク特定システム１の概略構成について図１を用いて説明する。図１は本実施形態に係る走行リンク特定システム１の概略構成図である。

図１に示すように、本実施形態に係る走行リンク特定システム１は、路面上を走行するとともにプローブ情報を取得する複数のプローブカー（車両）２と、プローブカー２から送信されたプローブ情報を受信して蓄積するとともに蓄積されたプローブ情報から交通情報（本実施形態ではリンクの旅行時間を含む）を作成するプローブ情報センタ３と、プローブ情報センタ３から配信された交通情報を利用する利用者端末である端末車両４とから基本的に構成されている。
そして、プローブカー２とプローブ情報センタ３は、プローブカー２に設けられた通信装置５と、プローブ情報センタ３に設けられたセンタ側通信装置６（情報取得手段）とによって相互に情報通信が可能となっている。また、プローブ情報センタ３と端末車両４は、センタ側通信装置６と端末車両４に設けられた端末通信装置７とによって相互に情報通信が可能となっている。

ここで、通信装置５は、通信ネットワーク１０（図２参照）を介してプローブ情報をプローブ情報センタ３に送信する通信手段であり、道路に沿って配設された電波ビーコン装置、光ビーコン装置等を介して電波ビーコン、光ビーコン等として受信するビーコンレシーバである。また、通信装置５としては、ＬＡＮ、ＷＡＮ、イントラネット、携帯電話回線網、電話回線網、公衆通信回線網、専用通信回線網、インターネット等の通信回線網等の通信系において通信を可能とするネットワーク機器であっても良い。
そして、プローブカー２が取得し、通信装置５を介して送信するプローブ情報としては、例えば、自車両の現在位置、ナビゲーション装置で設定している目的地、シフトレバーの位置、ステアリングの角度、アクセルの開度、ブレーキ圧、エンジンオイル等の残量、燃料の残量、シートベルト装着状況、自車両の速度、自車両の進行方向、自車両の走行距離、ワイパーの動作状況、ウィンカの状態、現在時刻等がある。尚、プローブ情報としては車両によって取得可能な情報であれば、車両自身の情報以外にも車両の周辺環境に関する情報でも良く、例えば車両の前方又は後方に設置されたカメラで撮像した画像や、ミリ波レーダで検出した前方車両までの距離や前方車両の車速に関する情報も含めることができる。

また、センタ側通信装置６は、通信ネットワーク１０（図２参照）を介してプローブカー２からプローブ情報を受信するとともに、蓄積されたプローブ情報から作成された交通情報を端末車両４に送信する通信手段である。

更に、端末通信装置７は、通信ネットワーク１０（図２参照）を介してプローブ情報センタ３から端末車両４へと送信された必要な交通情報を受信する通信手段である。

尚、本実施形態ではプローブカー２と端末車両４とを異なる種別の車両として区分して説明しているが、端末車両４はプローブカー２としても用いることも可能であり、また、プローブカー２は端末車両４としても用いることも可能である。更に、端末車両４の代わりに携帯電話機、ＰＤＡ、パーソナルコンピュータ等の情報端末を用いることも可能である。

次に、本実施形態に係る走行リンク特定システム１の具体的な構成について図２及び図３を用いて説明する。図２は本実施形態に係る走行リンク特定システム１の特にプローブ情報センタ３の構成について示したブロック図、図３は本実施形態に係る走行リンク特定システム１の特に端末車両４の構成について示したブロック図である。

図２に示すように、走行リンク特定システム１はプローブカー２と、プローブ情報センタ３と、端末車両４と、通信ネットワーク１０とから構成される。そして、プローブカー２とプローブ情報センタ３と端末車両４は、通信ネットワーク１０を介して各種の情報の送受信が可能となるように構成されている。

ここで、プローブカー２にはＧＰＳ８が設置されており、ＧＰＳ８によって自車の現在位置や現在時刻などのプローブ情報を取得し、所定時間間隔（例えば１分間隔）でプローブ情報センタ３へと送信する。尚、プローブカー２にはＧＰＳ８や通信装置５を含むナビゲーション装置を搭載することとしても良い。

また、プローブ情報センタ３は、センタ側通信装置６と、サーバ（位置リンク検出手段、組合せ判定手段、走行リンク特定手段、同一リンク判定手段、道なり判定手段、走行履歴判定手段、地点検出手段、地点間所要時間算出手段、リンク列所要時間算出手段、リンク列統計走行所要時間算出手段、走行リンク列特定手段、旅行時間算出手段）１１と、サーバ１１に接続された情報記録部としてのプローブ情報ＤＢ１５と、センタ地図情報ＤＢ（接続関係記憶手段、地図データ記憶手段）１６と、リンク統計ＤＢ（所要時間記憶手段）１７、走行履歴ＤＢ（走行履歴記憶手段）１８とを備える。また、サーバ１１は、サーバ１１の全体の制御を行う演算装置及び制御装置としてのＣＰＵ１２、並びにＣＰＵ１２が各種の演算処理を行うに当たってワーキングメモリとして使用されるＲＡＭ１３、プローブ情報ＤＢ１５に蓄積されたプローブ情報の内、プローブカー２の時間毎の位置情報からプローブカーの走行リンクを特定するとともに、走行リンクを構成する各リンクの旅行時間を算出する走行リンク特定処理プログラム（図７、図８参照）や端末車両４からの要求に基づいて作成された交通情報を送信する交通情報配信処理プログラム（図１７参照）等のサーバ１１を制御するための各種の制御プログラムが記録されたＲＯＭ１４等の内部記憶装置を備えている。また、ＣＰＵ１２に代えてＭＰＵ等を使用することができる。

また、プローブ情報ＤＢ１５は全国を走行する各プローブカー２から所定時間間隔（例えば１分間隔）で通信ネットワーク１０を介して送信されるプローブ情報を累積して記憶する記憶手段である。尚、本実施形態においては、プローブ情報ＤＢ１５の記憶媒体としてハードディスクが使用されるが、磁気ディスク、メモリーカード、磁気テープ、磁気ドラム、ＣＤ、ＭＤ、ＤＶＤ、光ディスク、ＭＯ、ＩＣカード、光カード等を外部記憶装置として使用することもできる。

また、本実施形態に係るプローブ情報センタ３のプローブ情報ＤＢ１５にはプローブ情報の一つとして全国を走行する各プローブカー２の時刻毎の位置座標を累積的に記録した走行地点テーブル１９が格納されている。図４は本実施形態に係る走行地点テーブル１９を示した図である。
図４に示すように、走行地点テーブル１９にはプローブカー２を特定する識別ＩＤと、各プローブカー２の時刻毎の位置座標とから構成されている。ここで、本実施形態に係る走行リンク特定システム１においてプローブカー２は、搭載されたＧＰＳ８によって現在時刻を検出し、更に１分間隔でＧＰＳ８によって検出された自車の位置と現在時刻をプローブ情報としてプローブ情報センタ３に対して送信する。
従って、サーバ１１は、走行地点テーブル１９に基づいて各プローブカー２が過去に走行した経路及び現在走行する経路を特定することが可能となる。

また、センタ地図情報ＤＢ１６はプローブカー２の走行リンクを特定するのに必要な地図データが記録された記憶手段である。ここで、地図データは、例えば地図を表示するための地図表示データ、各交差点に関する交差点データ、道路（リンク）に関するリンクデータ、ノード点に関するノードデータ、施設に関する施設データ等から構成されている。

また、本実施形態において地図データは、道路網の情報量に応じて３層に階層化されている。例えば、レベル１の階層は１０ｋｍ四方のメッシュによって複数に区分された地図データであり、レベル２の階層は２０ｋｍ四方のメッシュによって複数に区分された地図データであり、レベル３の階層は４０ｋｍ四方のメッシュによって複数に区分された地図データである。
そして、下位レベルの階層の地図データは上位レベルの階層の地図データより道路網の情報量がより多く含まれており、例えばレベル３の地図データは高速自動車国道、自動車専用道路、都市高速道路、有料道路に関する情報が格納されている。また、レベル２の地図データはレベル３に含まれる道路網に加えて国道や県道等の主要な一般道路に関する情報が格納されている。また、レベル１の地図データはレベル２に含まれる道路網に加えて細街路等のその他全ての一般道に関する詳細な道路網に関する情報が格納されている。

更に、下位レベルの階層における地図データのメッシュでは詳細なデータを有する代わりにカバーする範囲が狭く、上位レベルの階層における地図データのメッシュでは粗いデータしか有していない代わりにカバーする範囲が広くなっている。例えば、最下位レベル（レベル１）の階層におけるメッシュでは細街路を含む全ての道路の道路データを有するが市町村範囲しかカバーしておらず、最上位レベル（レベル３）の階層におけるメッシュでは高速道路や有料道路等の道路の道路データしか有していないが日本全国をカバーする。

ここで、特に各階層の地図データを構成する地図表示データとしては、各レベル階層の地図データに応じた地図表示を行う為の地図描画情報が記憶される。

また、リンクデータとしては、それぞれのレベル階層の地図データにおいて道路を構成する各リンクに関してリンクの属する道路の幅員、勾（こう）配、カント、バンク、路面の状態、道路の車線数、車線数の減少する箇所、幅員の狭くなる箇所、踏切り等を表すデータが、コーナに関して、曲率半径、交差点、Ｔ字路、コーナの入口及び出口等を表すデータが、道路属性に関して、降坂路、登坂路等を表すデータが、道路種別に関して、国道、県道、細街路等の一般道のほか、高速自動車国道、自動車専用道路、都市高速道路、一般有料道路、有料橋等の有料道路を表すデータがそれぞれ記録される。また、有料道路に関しては、有料道路の入口及び出口の取付道（ランプウェイ）、料金所（インターチェンジ）等に関するデータが記録される。また、リンクデータには各リンクを通過するのに必要の旅行時間についても記憶される。更に、リンク毎の接続関係を特定する為に各リンクに対して接続する一又は複数の接続リンクのリンク番号を示したリストであるリンク接続関係リスト、各リンクに対して接続された接続リンクが道なりの関係にあるか否かを示す道なり関係リストについても記憶されている。尚、道なりの関係とは、一方のリンクに対して近い状態にあると判断されるリンクとの関係をいい、例えば（１）同一直線上に位置するリンク、（２）同じ舗装であるリンク、（３）同じ種類の勾配（上り又は下り）にあるリンク、（４）道幅の同じリンク、（５）センターラインのあるリンク、（６）最も接続する角度の緩いリンク、（７）一時停止のないリンク、などが道なりの関係にあるリンクと判断される。

また、ノードデータとしては、それぞれのレベル階層の地図データにおいて道路の分岐点（交差点、Ｔ字路等も含む）、各道路に曲率半径等に応じて所定の距離ごとに設定されたノード点の座標（位置）、ノードが交差点に対応するノードであるか等を表すノード属性、ノードに接続するリンクのリンク番号のリストである接続リンク番号リスト、ノードにリンクを介して隣接するノードのノード番号のリストである隣接ノード番号リスト、各ノード点の高さ（高度）等に関するデータ等が記録される。

また、施設データとしては、各地域のホテル、病院、ガソリンスタンド、駐車場、観光施設、インターチェンジ、レストラン、サービスエリア等の建物に関するデータが建物を特定する施設ＩＤとともに記録される。

また、リンク統計ＤＢ１７はセンタ地図情報ＤＢ１６の地図データを構成する各リンクにおいて過去にプローブカー２が通過に必要とした所要時間を累積的に記録する記憶手段である。ここで、図５は本実施形態に係るリンク統計ＤＢ１７の記憶領域を示した図である。
図５に示すように、リンク統計ＤＢ１７にはリンクを特定するリンク番号と、プローブカー２が当該リンクを走行した走行日時と、リンクを通過するのに必要であった所要時間とが記憶される。そして、後述するようにサーバ１１は、リンク統計ＤＢ１７に記憶されたリンクを通過するのに必要な所要時間の平均値を用いて、プローブカー２が走行した走行リンクを特定し、交通情報（本実施形態ではリンクの旅行時間）を作成する（図７のＳ４）。

また、走行履歴ＤＢ１８は過去にプローブカー２の走行した走行履歴を累積的に記録する記憶手段である。ここで、図６は本実施形態に係る走行履歴ＤＢ１８の記憶領域を示した図である。
図６に示すように、走行履歴ＤＢ１８にはプローブカー２を特定する識別ＩＤと、各プローブカー２が過去に走行したリンクと、当該リンクの走行を開始した時刻とが記憶される。そして、後述するようにサーバ１１は、過去にプローブカー２が走行したリンクの種類を用いて、次回以降にプローブカー２が走行した走行リンクを特定し、交通情報（本実施形態ではリンクの旅行時間）を作成する（図７のＳ４）。

次に、図３を用いて走行リンク特定システム１を構成する端末車両４の構成について説明すると、本実施形態に係る端末車両４には端末通信装置７を有するナビゲーション装置２０が搭載されている。
図３に示すようにナビゲーション装置２０は、自車の現在位置を検出する現在地検出処理部２１と、各種のデータが記録されたデータ記録部２２と、入力された情報に基づいて、各種の演算処理を行うナビゲーションＥＣＵ２３と、操作者からの操作を受け付ける操作部２４と、操作者に対して地図等の情報を表示する液晶ディスプレイ２５と、経路案内に関する音声ガイダンスを出力するスピーカ２６と、プローブ情報センタ３や交通情報センタ等の情報センタとの間で通信を行う端末通信装置７と、から構成されている。また、ナビゲーションＥＣＵ２３には自車の走行速度を検出する車速センサ３０が接続される。

以下に、ナビゲーション装置２０を構成する各構成要素について説明する。
現在地検出処理部２１は、ＧＰＳ３１、地磁気センサ３２、距離センサ３３、ステアリングセンサ３４、方位検出部としてのジャイロセンサ３５、高度計（図示せず）等からなり、現在の自車の位置、方位、目標物（例えば、交差点）までの距離等を検出することが可能となっている。

具体的には、ＧＰＳ３１は、人工衛星によって発生させられた電波を受信することにより、地球上における自車の現在地及び現在時刻を検出し、地磁気センサ３２は、地磁気を測定することによって自車方位を検出し、距離センサ３３は、道路上の所定の位置間の距離等を検出する。ここで、距離センサ３３としては、例えば、自車の車輪（図示せず）の回転速度を測定し、測定した回転速度に基づいて距離を検出するセンサ、加速度を測定し、測定した加速度を２回積分して距離を検出するセンサ等を使用することができる。

また、ステアリングセンサ３４は自車の舵（だ）角を検出する。ここで、ステアリングセンサ３４としては、例えば、ステアリングホイール（図示せず）の回転部に取り付けられた光学的な回転センサ、回転抵抗センサ、車輪に取り付けられた角度センサ等が使用される。

そして、ジャイロセンサ３５は自車の旋回角を検出する。ここで、ジャイロセンサ３５としては、例えば、ガスレートジャイロ、振動ジャイロ等が使用される。また、ジャイロセンサ３５によって検出された旋回角を積分することにより、自車方位を検出することができる。

また、データ記録部２２は、外部記憶装置及び記録媒体としてのハードディスク（図示せず）と、ハードディスクに記録された地図情報ＤＢ２８及び所定のプログラム等を読み出すとともにハードディスクに所定のデータを書き込む為のドライバである記録ヘッド（図示せず）とを備えている。尚、本実施形態においては、データ記録部２２の外部記憶装置及び記憶媒体としてハードディスクが使用されるが、ハードディスクのほかに、フレキシブルディスク等の磁気ディスクを外部記憶装置として使用することができる。また、メモリーカード、磁気テープ、磁気ドラム、ＣＤ、ＭＤ、ＤＶＤ、光ディスク、ＭＯ、ＩＣカード、光カード等を外部記憶装置として使用することもできる。

ここで、地図情報ＤＢ２８には、経路案内及び地図表示に必要な地図データが記録されている。本実施形態において地図データは、前記したように道路網の情報量に応じて３層に階層化されており、各階層の地図データは、例えば地図を表示するための地図表示データ、各交差点に関する交差点データ、道路（リンク）に関するリンクデータ、ノード点に関するノードデータ、経路を探索するための探索データ、施設に関する施設データ、地点を検索するための検索データ等から構成されている。

ここで、探索データとしては、それぞれのレベル階層の地図データにおいて設定された目的地までの経路を探索及び表示する際に使用されるデータについて記録されており、ノードを通過する際のコスト（以下、ノードコストという）や道路を構成するリンクのコスト（以下、リンクコストという）からなる探索コストを算出する為に使用するコストデータ、リンクを通過するのに必要な旅行時間、経路探索により選択された経路を液晶ディスプレイ２５の地図上に表示するための経路表示データ等から構成されている。
ここで、ノードコストは交差点に対応するノードに対して基本的に設定されており、本実施形態に係るナビゲーション装置２０では、信号の有無や交差点を通過する際の自車の走行経路（即ち直進、右折及び左折の種類）によってその値が決定される。
また、リンクコストは、リンクを構成する道路属性や道路種別、道路幅、車線数、リンク長さ、旅行時間、渋滞情報等に関するデータを用いて算出される。更に、本実施形態に係る走行リンク特定システム１では、プローブ情報センタ３から配信される交通情報に従って、リンクの旅行時間やリンクコストが調整される（図１７のＳ１０５）。

尚、探索データ以外に地図データを構成する交差点データ、リンクデータ、ノードデータに関しては既に説明したプローブ情報センタ３のセンタ地図情報ＤＢ１６（図２参照）に記憶されているものと同一内容であるので、ここではその説明は省略する。

そして、ナビゲーションＥＣＵ２３は、現在地（出発地）から目的地までの距離が短距離（例えば、３ｋｍ程度）の経路探索の場合には、現在地周辺の最下層の地図データであるレベル１の地図データのメッシュのみを使用して経路を探索する。
また、現在地から目的地までの距離が中距離（例えば、５０ｋｍ程度）の経路探索の場合には、現在地及び目的地周辺については最下層の地図データであるレベル１の地図データのメッシュを使用し、前記レベル１の地図データのメッシュに隣接するエリアは中間層の地図データであるレベル２の地図データのメッシュを使用して経路を探索する。
更に、現在地から目的地までの距離が長距離（例えば、３００ｋｍ程度）の経路探索の場合には、現在地及び目的地周辺の最下層の地図データであるレベル１の地図データのメッシュを使用し、前記レベル１の地図データのメッシュに隣接するエリアは中間層の地図データであるレベル２の地図データのメッシュを使用し、前記レベル２の地図データのメッシュに隣接するエリアは最上層の地図データであるレベル３の地図データのメッシュを使用して経路を探索する。それによって、経路を探索の為の演算量を抑えることができ、経路探索に必要な時間を短縮することができる。

そして、ナビゲーションＥＣＵ２３が経路を探索する際には、地図データにおける探索データ中の道路データを調査して、探索に使用されるメッシュに含まれる道路（リンク及びノード）についての探索コスト（ノードコスト及びリンクコスト）を計算して、経路を探索する。具体的には、出発地側及び目的地側から経路の探索が行われ、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算した値、即ち、コスト加算値が算出される。その結果、コストが小さい順に経路を複数本（例えば３本）選択し、最もコスト加算値が小さくなった経路、又は利用者によって選択された経路を誘導経路として設定する。

また、これら地図情報ＤＢ２８の内容は、ＤＶＤや外部に接続したメモリーカード等の記録媒体から情報を転送すること、又は特定の情報センタ等から端末通信装置７を介して情報をダウンロードすること等によって更新される。

更に、ナビゲーションＥＣＵ２３は、ナビゲーション装置２０の全体の制御を行う演算装置及び制御装置としてのＣＰＵ４１、並びにＣＰＵ４１が各種の演算処理を行うに当たってワーキングメモリとして使用されるとともに、経路が探索されたときの経路データ等が記憶されるＲＡＭ４２、制御用のプログラムのほか、プローブ情報センタ３から配信された交通情報を受信して目的地までの経路を探索する交通情報配信処理プログラム（図１１参照）が記録されたＲＯＭ４３、ＲＯＭ４３から読み出したプログラムを記録するフラッシュメモリ４４等の内部記憶装置を備えている。尚、前記ＲＡＭ４２、ＲＯＭ４３、フラッシュメモリ４４等としては半導体メモリ、磁気コア等が使用される。そして、演算装置及び制御装置としては、ＣＰＵ４１に代えてＭＰＵ等を使用することも可能である。

また、本実施形態においては、前記ＲＯＭ４３に各種のプログラムが記録され、前記データ記録部２２に各種のデータが記録されるようになっているが、プログラム、データ等を同じ外部記憶装置、メモリーカード等からプログラム、データ等を読み出して前記フラッシュメモリ４４に書き込むこともできる。更に、メモリーカード等を交換することによって前記プログラム、データ等を更新することができる。

更に、前記ナビゲーションＥＣＵ２３には、操作部２４、液晶ディスプレイ２５、スピーカ２６、端末通信装置７の各周辺装置（アクチュエータ）が電気的に接続されている。

操作部２４は、案内開始地点としての出発地及び案内終了地点としての目的地を入力する際等に操作され、各種のキー、ボタン等の複数の操作スイッチ（図示せず）から構成される。そして、ナビゲーションＥＣＵ２３は、各スイッチの押下等により出力されるスイッチ信号に基づき、対応する各種の動作を実行すべく制御を行う。尚、操作部２４としては、キーボード、マウス、バーコードリーダ、遠隔操作用のリモートコントロール装置、ジョイスティック、ライトペン、スタイラスペン等を使用することもできる。更に、液晶ディスプレイ２５の前面に設けたタッチパネルによって構成することもできる。

また、液晶ディスプレイ２５には、操作案内、操作メニュー、キーの案内、現在地から目的地までの誘導経路、誘導経路に沿った案内情報、交通情報、ニュース、天気予報、時刻、メール、テレビ番組等が表示される。尚、液晶ディスプレイ２５の代わりに、ＣＲＴディスプレイ、プラズマディスプレイ等を使用したり、車両のフロントガラスにホログラムを投影するホログラム装置等を使用することも可能である。

また、スピーカ２６は、ナビゲーションＥＣＵ２３からの指示に基づいて誘導経路に沿った走行を案内する音声ガイダンスを出力する。ここで、案内される音声ガイダンスとしては、例えば、「３００ｍ先の交差点を右方向です。」や「この先の国道○○号線が渋滞しています。」等がある。なお、スピーカ２６より出力される音声としては、合成された音声のほかに、各種効果音、予めテープやメモリ等に録音された各種の案内情報を出力することもできる。

そして、端末通信装置７は、前記したプローブ情報センタ３から配信された交通情報を受信する他に、交通情報センタ、例えば、ＶＩＣＳ（登録商標：ＶｅｈｉｃｌｅＩｎｆｏｒｍａｔｉｏｎａｎｄＣｏｍｍｕｎｉｃａｔｉｏｎＳｙｓｔｅｍ）センタ等から送信された渋滞情報、規制情報、駐車場情報、交通事故情報等の各情報から成る交通情報を、道路に沿って配設された電波ビーコン装置、光ビーコン装置等を介して電波ビーコン、光ビーコン等として受信するビーコンレシーバである。また、端末通信装置７としては、ＬＡＮ、ＷＡＮ、イントラネット、携帯電話回線網、電話回線網、公衆通信回線網、専用通信回線網、インターネット等の通信回線網等の通信系において通信を可能とするネットワーク機器であっても良い。更に、端末通信装置７は前記情報センタからの情報の他に、ニュース、天気予報等の情報から成るＦＭ多重情報を、ＦＭ放送局を介してＦＭ多重放送として受信するＦＭ受信機を備える。尚、前記ビーコンレシーバ及びＦＭ受信機は、ユニット化されてＶＩＣＳレシーバとして配設されるようになっているが、別々に配設することもできる。

続いて、前記構成を有する本実施形態に係る走行リンク特定システム１を構成するプローブ情報センタ３のサーバ１１が実行する走行リンク特定処理プログラムについて図７に基づき説明する。図７は本実施形態に係る走行リンク特定システム１における走行リンク特定処理プログラムのフローチャートである。ここで、走行リンク特定処理プログラムは、プローブ情報ＤＢ１５に蓄積されたプローブ情報の内、プローブカー２の時間毎の位置情報からプローブカーの走行リンクを特定するとともに、走行リンクを構成する各リンクの旅行時間を算出するプログラムである。尚、以下に図７及び図８にフローチャートで示されるプログラムはサーバ１１が備えているＲＯＭ１４やＲＡＭ１３に記憶されており、イグニションがＯＮされた後にＣＰＵ１２により所定間隔毎（例えば４ｍｓ毎）で実行される。

先ず、走行リンク特定処理プログラムではステップ（以下、Ｓと略記する）１において、ＣＰＵ１２はプローブカー２から所定時間間隔（例えば１分間隔）で送信されたプローブ情報をセンタ側通信装置６で受信し、受信したプローブ情報をプローブ情報ＤＢ１５に対して累積的に記録する。ここで、取得されるプローブ情報としては、自車両の現在位置、ナビゲーション装置で設定している目的地、シフトレバーの位置、ステアリングの角度、アクセルの開度、ブレーキ圧、エンジンオイル等の残量、燃料の残量、シートベルト装着状況、自車両の速度、自車両の進行方向、自車両の走行距離、ワイパーの動作状況、ウィンカの状態、現在時刻等がある。

次に、Ｓ２では前記Ｓ１で取得したプローブ情報の内、特にプローブカー２から最も新しく送信された位置座標と前回に送信された位置座標との２点をマップマッチングし、２点の位置座標に対応するリンク（即ち、プローブカー２が走行したリンク）をセンタ地図情報ＤＢ１６のリンクデータからそれぞれ検出する。尚、Ｓ２で検出されるリンクはセンタ地図情報ＤＢ１６に記録された地図データの内、最も道路網の情報量が多いレベル１の地図データを構成するリンクデータに基づいて検出される。そして、上記Ｓ２が位置リンク検出手段の処理に相当する。

続いて、Ｓ３では前記Ｓ２で検出されたリンクの間を接続するリンクからプローブカー２が走行した走行リンクを特定し、検出されたリンクの間において接続するリンクを特定したリンクにより補完するリンク補完処理（図８）が行われる。リンク補完処理では、後述するように検出されたリンクと他のリンクの接続関係やプローブカー２の走行履歴、リンク統計ＤＢ１７に記録されたリンク通過の所要時間等によってプローブカー２が走行したリンクを特定する。

その後、Ｓ４では前記Ｓ３によって特定された走行リンクと、前記Ｓ２で検出された２点の位置座標をプローブカー２が通過した時刻から走行リンクを構成する各リンクの旅行時間を算出する。そして、算出された各リンクの旅行時間はセンタ地図情報ＤＢ１６へと格納され、その後に端末車両４からの要求に対して交通情報として送信される（図１７のＳ１１３）。尚、上記Ｓ４が旅行時間算出手段の処理に相当する。

ここで、図９は前記Ｓ４における走行リンクの旅行時間の算出方法について説明した説明図である。
図９では、特に前記Ｓ１でプローブカー２の位置座標として座標Ａと座標Ｂが取得され、前記Ｓ２で座標Ａに対応するリンクとしてリンク５１が、座標Ｂに対応するリンクとしてリンク５２がそれぞれ検出され、更に前記Ｓ３でリンク５１とリンク５２の間でプローブカー２が走行した走行リンクとしてリンク５３とリンク５４が特定された場合を例に挙げて説明する。
図９に示す例では、座標Ａをプローブカー２が通過した時刻である９：１０と座標Ｂをプローブカー２が通過した時刻である９：１１とから、座標Ａから座標Ｂまでをプローブカー２が走行した所要時間は１分である。従って、座標Ａからノード５５までの距離ａと、リンク５３の長さｂと、リンク５４の長さｃと、ノード５６から座標Ｂまでの長さｄの比率からリンク５３、５４の旅行時間を算出することが可能となる。また、リンク５１の長さに対する距離ａの割合及びリンク５２の長さに対する距離ｄの割合を更に考慮することによってリンク５１、５２の旅行時間を算出することが可能となる。

次に、前記Ｓ３でサーバ１１のＣＰＵ１２が実行するリンク補完処理について図８に基づき説明する。図８は本実施形態に係るリンク補完処理プログラムのフローチャートである。

先ず、Ｓ１１ではＣＰＵ１２は前記Ｓ２で検出された２点の位置座標に対応するリンクが同一のリンクであるか否かが判定される。ここで、図１０は前記Ｓ２で検出された２点の位置座標に対応するリンクが同一のリンクである場合を示した模式図である。
図１０に示すように前記Ｓ１でプローブカー２の位置座標として座標Ｃと座標Ｄが取得されている場合には、前記Ｓ２で座標Ｃ及び座標Ｄに対応するリンクとして共通のリンク６１が検出される。この場合には、座標Ｃと座標Ｄの間でプローブカー２の走行したリンクは６１のみに特定される。

そして、図１０に示すように２点の位置座標に対応するリンクが同一のリンクであると判定された場合（Ｓ１１：ＹＥＳ）には、その同一のリンク（図１０ではリンク６１）をプローブカー２が走行した走行リンクに特定し（Ｓ１７）、Ｓ４へと移行する。尚、Ｓ４ではリンク６１の旅行時間が算出される。

一方、２点の位置座標に対応するリンクが同一のリンクでないと判定された場合（Ｓ１１：ＮＯ）には、続いてＣＰＵ１２は前記Ｓ２で検出された２点の位置座標に対応するリンクが互いに接続するリンクであるか否かを判定する（Ｓ１２）。尚、互いに接続するリンクであるか否かは、センタ地図情報ＤＢ１６のレベル１の地図データを構成するリンクデータと、その接続関係を示したリンク接続関係リストから判定される。ここで、図１１は前記Ｓ２で検出された２点の位置座標に対応するリンクが互いに接続するリンクである場合を示した模式図である。
図１１に示すように前記Ｓ１でプローブカー２の位置座標として座標Ｅと座標Ｆが取得されている場合には、前記Ｓ２で座標Ｅに対応するリンクとしてリンク６２が、座標Ｆに対応するリンクとしてリンク６３が検出される。また、リンク６２とリンク６３とはノード６４で互いに接続されるリンクである。この場合には、座標Ｅと座標Ｆの間でプローブカー２の走行したリンクは６２、６３のみに特定される。

そして、図１１に示すように２点の位置座標に対応するリンクが互いに接続するリンクであると判定された場合（Ｓ１２：ＹＥＳ）には、その接続する２本のリンク（図１１ではリンク６２、６３）をプローブカー２が走行した走行リンクに特定し（Ｓ１７）、Ｓ４へと移行する。尚、Ｓ４ではリンク６２、６３の旅行時間が算出される。

一方、２点の位置座標に対応するリンクが互いに接続しないと判定された場合（Ｓ１２：ＮＯ）には、続いてＣＰＵ１２は前記Ｓ２で検出された２点の位置座標に対応するリンクの間を接続する一又は複数のリンクの組合せが一の組合せに特定できるか否かを判定する（Ｓ１３）。尚、一の組合せに特定できるか否かは、センタ地図情報ＤＢ１６のレベル１の地図データを構成するリンクデータと、その接続関係を示したリンク接続関係リストから判定される。ここで、図１２及び図１３は前記Ｓ２で検出された２点の位置座標に対応するリンクの間を接続する一又は複数のリンクの組合せが一の組合せに特定できる場合を示した模式図である。
先ず、図１２に示すように前記Ｓ１でプローブカー２の位置座標として座標Ｇと座標Ｈが取得されている場合には、前記Ｓ２で座標Ｇに対応するリンクとしてリンク６５が、座標Ｈに対応するリンクとしてリンク６６が検出される。そして、リンク６５に対して接続される接続リンクと、リンク６６に対して接続される接続リンクとを比較すると、共通のリンクとしてノード６７、６８を介して接続されるリンク６９を有する。この場合には、リンク６５、６６の間を接続するリンクはリンク６９のみとなり、座標Ｇと座標Ｈの間でプローブカー２の走行したリンクはリンク６５、６９、６６に特定される。
また、図１３に示すように前記Ｓ１でプローブカー２の位置座標として座標Ｉと座標Ｊが取得されている場合には、前記Ｓ２で座標Ｉに対応するリンクとしてリンク７０が、座標Ｊに対応するリンクとしてリンク７１が検出される。そして、リンク７０に対して接続される接続リンクと、リンク７１に対して接続される接続リンクとを比較すると、共通のリンクが存在しないので、更に接続リンク同士が接続されているか否かを判定する。その結果、接続されると判定される組合せが一通りしかない場合には、リンク７０、７１の間を接続する一又は複数のリンクの組合せが一の組合せに特定できると判定する。図１３では、接続リンク７２、７３同士がノード７４で接続される組合せしかないので、座標Ｉと座標Ｊの間でプローブカー２の走行したリンクはリンク７０、７２、７３、７１のみに特定される。尚、検出されたリンクの間に更に複数のリンクが存在する場合には、同様の処理を繰り返し行う。

そして、図１２及び図１３に示すように２点の位置座標に対応するリンクの間を接続する一又は複数のリンクの組合せが一の組合せに特定できると判定された場合（Ｓ１３：ＹＥＳ）には、そのリンクの組合せ（図１２ではリンク６５、６６、６９）をプローブカー２が走行した走行リンクに特定し、特定された走行リンクにより検出されたリンクの間のリンク補完を行う（Ｓ１８）。その後、後述するＳ２２の判定処理へと移行する。尚、上記Ｓ１３が組合せ判定手段の処理に相当する。

一方、２点の位置座標に対応するリンクに接続の間を接続する一又は複数のリンクの組合せが一の組合せに特定できないと判定された場合（Ｓ１３：ＮＯ）には、続いてＣＰＵ１２は前記Ｓ２で検出された２点の位置座標に対応するリンクに接続する接続リンクが上位レベルの地図データで同一のリンクであるか否かを判定する（Ｓ１４）。尚、接続リンクが上位レベルの地図データで同一のリンクであるか否かは、センタ地図情報ＤＢ１６のレベル１〜レベル３の地図データを構成するリンクデータと、その接続関係を示したリンク接続関係リストから判定される。ここで、図１４は前記Ｓ２で検出された２点の位置座標に対応するリンクに接続する接続リンクが上位レベルの地図データで同一のリンクである場合を示した模式図である。
図１４に示すように前記Ｓ１でプローブカー２の位置座標として座標Ｋと座標Ｌが取得されている場合には、前記Ｓ２で座標Ｋに対応するリンクとしてリンク７５が、座標Ｌに対応するリンクとしてリンク７６が検出される。ここで、レベル１の地図データでリンク７５とリンク７６の間を接続するリンクの組合せはリンク７７、７８を経由する組合せと、リンク７９、８０、８１を経由する組合せが存在し、走行リンクを一に特定することができない。
しかし、レベル２の地図データにおいては、リンク７５に対して接続される接続リンクの内、リンク７７がリンク７５とともに同一のリンク８２に相当し、リンク７６に対して接続される接続リンクの内、リンク７８がリンク７６とともに同一のリンク８３に相当する。この場合には、座標Ｋと座標Ｌの間でプローブカー２の走行したリンクとしてリンク７５、７６に加えてリンク７７、７８が新たに特定される。

そして、図１４に示すように２点の位置座標に対応するリンクに接続する接続リンクが上位レベルの地図データで同一のリンクであると判定された場合（Ｓ１４：ＹＥＳ）には、その同一リンクとなったリンクの組合せ（図１４ではリンク７５、７７とリンク７６、７８）をプローブカー２が走行した走行リンクに特定し、特定された走行リンクにより検出されたリンクの間のリンク補完を行う（Ｓ１８）。その後、後述するＳ２１の判定処理へと移行する。尚、図１４では新たに補完されたリンク７７とリンク７８が互いに接続するリンクである（Ｓ１２：ＹＥＳ）ので、その後にＳ１７において座標Ｋと座標Ｌの間でプローブカー２の走行したリンクはリンク７５、７７、７８、７６のみに特定され、リンクの補完が完了することとなる。尚、上記Ｓ１４が同一リンク判定手段の処理に相当する。

一方、２点の位置座標に対応するリンクに接続する接続リンクが上位レベルの地図データで同一のリンクでないと判定された場合（Ｓ１４：ＮＯ）には、続いてＣＰＵ１２は前記Ｓ２で検出された２点の位置座標に対応するリンクに接続する接続リンクが道なりの関係にあるか否かを判定する（Ｓ１５）。尚、接続リンクが道なりの関係にあるか否かは、センタ地図情報ＤＢ１６のレベル１〜レベル３の地図データを構成するリンクデータと、その接続関係を示したリンク接続関係リストと、接続リンクが道なりの関係にあるか否かを示す道なり関係リストから判定される。ここで、図１５は前記Ｓ２で検出された２点の位置座標に対応するリンクに接続する接続リンクが道なりの関係にある場合を示した模式図である。
図１５に示すように前記Ｓ１でプローブカー２の位置座標として座標Ｍと座標Ｎが取得されている場合には、前記Ｓ２で座標Ｍに対応するリンクとしてリンク８５が、座標Ｎに対応するリンクとしてリンク８６が検出される。ここで、リンク８５とリンク８６の間を接続するリンクの組合せはリンク８７、８８を経由する組合せと、リンク８９、９０を経由する組合せと、リンク８７、９１、９２を経由する組合せが存在し、走行リンクを一に特定することができない。
しかし、道なり関係リストによってリンク８５に対して接続される接続リンクの内、リンク８７が道なりの関係を有する。この場合には、座標Ｍと座標Ｎの間でプローブカー２の走行したリンクとしてリンク８５、８６に加えてリンク８７が新たに特定される。

そして、図１５に示すように２点の位置座標に対応するリンクに接続する接続リンクが道なりの関係にあると判定された場合（Ｓ１５：ＹＥＳ）には、その道なりの関係にあると判定された接続リンク（図１５ではリンク８７）をプローブカー２が走行した走行リンクに特定し、特定された走行リンクにより検出されたリンクの間のリンク補完を行う（Ｓ１８）。その後、後述するＳ２２の判定処理へと移行する。尚、上記Ｓ１５が道なり判定手段の処理に相当する。

一方、２点の位置座標に対応するリンクに接続する接続リンクが道なりの関係にないと判定された場合（Ｓ１５：ＮＯ）には、続いてＣＰＵ１２は前記Ｓ２で検出された２点の位置座標に対応するリンクの間を接続するリンクの内、過去にプローブカー２が走行したリンクがあるか否かを判定する（Ｓ１６）。尚、過去に走行したリンクがあるか否かは、センタ地図情報ＤＢ１６のレベル１〜レベル３の地図データを構成するリンクデータと、その接続関係を示したリンク接続関係リストと、走行履歴ＤＢ１８から判定される。ここで、図１５を用いて、前記Ｓ２で検出された２点の位置座標に対応するリンクの間にプローブカー２が過去に走行したリンクがある場合を示す。
図１５に示すようにリンク８５とリンク８６の間を接続するリンク８７〜９２の内、リンク８８が過去にプローブカー２が走行したリンクとする。この場合には、座標Ｍと座標Ｎの間でプローブカー２の走行したリンクとしてリンク８５、８６に加えてリンク８８が新たに特定される。尚、前記Ｓ１６ではプローブカー２が過去に複数回（例えば３回）以上走行したリンクがあるか否かを判定し、複数回以上走行したことのあるリンクを走行リンクとして特定することとしても良い。

そして、図１５に示すように２点の位置座標に対応するリンクの間を接続するリンクの内、過去にプローブカー２が走行したリンクがあると判定された場合（Ｓ１６：ＹＥＳ）には、その過去に走行されたと判定されたリンク（図１５ではリンク８８）をプローブカー２が走行した走行リンクに特定し、特定された走行リンクにより検出されたリンクの間のリンク補完を行う（Ｓ１８）。その後、後述するＳ２２の判定処理へと移行する。
尚、図１５に示すように既に道なりの関係にあると判定されたリンク８７が補完されており、更に過去にプローブカー２が走行したと判定されたリンク８８が新たに補完された場合には、リンク８７とリンク８８とリンク８６とが互いに接続するリンクである（Ｓ１２：ＹＥＳ）ので、その後にＳ１７において座標Ｍと座標Ｎの間でプローブカー２の走行したリンクはリンク８５、８７、８８、７６のみに特定され、リンクの補完が完了することとなる。また、上記Ｓ１６が走行履歴判定手段の処理に相当する。

一方、２点の位置座標に対応するリンクの間を接続するリンクの内、過去にプローブカー２が走行したリンクがないと判定された場合（Ｓ１６：ＮＯ）には、Ｓ１９へと移行する。

Ｓ１９でＣＰＵ１２は、前記Ｓ２で検出された２点の間をプローブカー２が走行するのに要した所要時間（以下、リンク所要時間とする）を算出し、更に、算出されたリンク所要時間を用いて２点の位置座標に対応するリンクの間を接続するリンク列を走行するのに要した所要時間（以下、リンク列所要時間とする）を算出する。尚、上記Ｓ１９が地点間所要時間算出手段及びリンク列所要時間算出手段の処理に相当する。

その後、Ｓ２０ではリンク統計ＤＢ１７から前記Ｓ２で検出された２点の間を接続するリンク列の平均走行所要時間を算出する。具体的には、リンク統計ＤＢ１７に記憶された過去にプローブカー２が各リンクを走行するのに要した所要時間から、リンク毎の平均走行所要時間を算出し、更にリンク毎の平均走行所要時間を加算することによりリンク列の平均走行所要時間を算出する。尚、上記Ｓ２０がリンク列統計走行所要時間取得手段の処理に相当する。

次に、Ｓ２１では前記Ｓ１９で算出されたリンク列所要時間と、前記Ｓ２０で算出されたリンク列の平均走行所要時間とを比較することにより、最もリンク列所要時間に近い平均走行所要時間を備えたリンク列を走行リンクに特定し、特定された走行リンクにより検出されたリンクの間のリンク補完を行う。

ここで、図１６を用いて、前記Ｓ１９〜Ｓ２１の処理における走行リンクの特定方法について説明する。
図１６に示すように前記Ｓ１でプローブカー２の位置座標として座標Ｏと座標Ｐが取得された場合には、前記Ｓ２で座標Ｏに対応するリンクとしてリンク９５が、座標Ｐに対応するリンクとしてリンク１００が検出される。ここで、リンク９５とリンク１００の間を接続するリンクの組合せはリンク９６、９７を経由する組合せと、リンク９８、９９を経由する組合せが存在し、走行リンクを一に特定することができない。
ここで、座標Ｏをプローブカー２が通過した時刻が１２：１０であり、座標Ｐをプローブカー２が通過した時刻が１２：１１である場合には、前記Ｓ１９で算出されるリンク所要時間は６０秒となる。また、リンク９５の長さに対する座標Ｏからノード１０１までの区間ｅの距離に対する割合とリンク統計ＤＢ１７から読み出したリンク９５の旅行時間とから、区間ｅの走行に要する所要時間（図１６では７秒）を算出する。一方、リンク１００の長さに対する座標Ｐからノード１０２までの区間ｆの距離に対する割合とリンク１００の旅行時間とから、区間ｆの走行に要する所要時間（図１６では８秒）を算出する。その後、リンク所要時間から区間ｅ及び区間ｆの走行に要する時間を差し引くことにより、リンク列所要時間（図１６では４５秒）が算出される。
また、リンク統計ＤＢ１７に記憶された過去にプローブカー２が各リンクを走行するのに要した所要時間からリンク９６〜９９の平均走行所要時間を算出すると、図１６に示すようにリンク９６の平均走行所要時間は３０秒であり、リンク９７の平均走行所要時間は１８秒であり、リンク９８の平均走行所要時間は２５秒であり、リンク９９の平均走行所要時間は４０秒となる。従って、座標Ｏと座標Ｐを接続するリンク列の一つであるリンク９６、９７の平均走行所要時間は４８秒であり、他方のリンク列であるリンク９８、９９の平均走行所要時間は６５秒となる。
その場合、リンク列所要時間である４５秒に最も近いリンク列であるリンク９６、９７が座標Ｏと座標Ｐの間においてプローブカー２の走行した走行リンクとして特定される。

その後、Ｓ２２でＣＰＵ１２は前記Ｓ１８及び前記Ｓ２１における処理によって、前記Ｓ２で検出された２点の位置座標の間を接続するリンクの補完が完了したか否かを判定する。そして、リンクの補完が完了したと判定された場合（Ｓ２２：ＹＥＳ）にはＳ４へと移行する。尚、Ｓ４では補完された各リンクの旅行時間が算出される。

一方、リンクの補完が完了していないと判定された場合（Ｓ２２：ＮＯ）にはＳ１１へと戻り、継続して走行リンクの特定とリンクの補完が行われる。尚、上記Ｓ１７乃至Ｓ２２が走行リンク特定手段及び走行リンク列特定手段の処理に相当する。

次に、走行リンク特定システム１において端末車両４のナビゲーションＥＣＵ２３及びプローブ情報センタ３のサーバ１１が実行する交通情報配信処理プログラムについて図１７に基づき説明する。図１７は本実施形態に係る走行リンク特定システムにおける交通情報配信処理プログラムのフローチャートである。ここで、交通情報配信処理プログラムは端末車両４からの要求に基づいてプローブ情報センタ３で作成された交通情報を送信するプログラムである。尚、以下の図１７にフローチャートで示されるプログラムは、ナビゲーション装置２０が備えているＲＡＭ４２やＲＯＭ４３、又はサーバ１１が備えているＲＡＭ１３やＲＯＭ１４に記憶されており、ＣＰＵ４１或いはＣＰＵ１２により実行される。

先ず、図１７に基づいてナビゲーション装置２０のＣＰＵ４１が実行する交通情報配信処理プログラムについて説明する。Ｓ１０１において、ＣＰＵ４１は利用者の操作部２４の操作に基づいて目的地を設定する。

次に、Ｓ１０２では現在地検出処理部２１を用いて自車（端末車両４）の現在位置を検出する。その後、Ｓ１０３では前記Ｓ１０１で設定された目的地に関する情報（具体的には目的地となる施設のＩＤや位置座標）と前記Ｓ１０２で検出された自車の現在位置に関する情報（具体的には位置座標）を端末通信装置７によりプローブ情報センタ３に対して送信する。

そして、Ｓ１０４ではプローブ情報センタ３から送信された交通情報（前記Ｓ４で算出されたリンクの旅行時間を含む）を端末通信装置７により受信する。

次に、Ｓ１０５では前記Ｓ１０４で受信した交通情報を用いて目的地までの経路を探索する。
具体的にナビゲーションＥＣＵ２３による経路の探索処理について説明すると、先ず、地図データにおける探索データ中の道路データを調査して、探索に使用されるメッシュに含まれる道路（リンク及びノード）についての探索コスト（ノードコスト及びリンクコスト）を前記Ｓ１０４で受信した交通情報を用いて計算する。その後、出発地側からの探索と目的地側からの探索との重なり部分において、出発地側から累積された探索コストと目的地側から累積された探索コストとを加算した値、即ち、コスト加算値が算出される。その結果、コストが最も小さい経路を選択する。

次に、Ｓ１０６では前記Ｓ１０５で探索された経路を誘導経路に設定する。そして、設定された誘導経路に従って液晶ディスプレイ２５及びスピーカ２６を用いた各種走行の案内が行われる（Ｓ１０７）。

次に、図１７に基づいてサーバ１１のＣＰＵ１２が実行する走行予測処理プログラムについて説明する。先ずＳ１１１においては、ＣＰＵ１２は前記Ｓ１０３で端末車両４から送信された端末車両４の現在位置及び設定された目的地に関する情報をセンタ側通信装置６により受信する。

次に、Ｓ１１２においてＣＰＵ１２は、前記Ｓ１１１で受信した端末車両４の現在位置及び設定された目的地に合わせた交通情報を作成する。具体的には、端末車両４の現在位置から目的地までの経路の探索において関連するエリア内の交通情報（渋滞情報や平均車速など）をプローブ情報ＤＢ１５から作成する。また、前記Ｓ４において作成されたリンクの旅行時間の内、関連するエリア内のリンクの旅行時間を抽出する。

そして、Ｓ１１３では前記Ｓ１１２で作成及び抽出された交通情報をセンタ側通信装置６により端末車両４に対して送信する。

以上詳細に説明した通り、本実施形態に係る走行リンク特定システム１では、プローブカー２から送信されたプローブ情報の内、特にプローブカー２の２点の位置座標からプローブカー２の走行したリンクを検出し（Ｓ２）、検出されたリンクの間を接続するリンクの組合せが一の組合せに特定できる場合（Ｓ１３：ＹＥＳ）に、特定されたリンクの組合せを走行リンクに特定する（Ｓ１８）ので、リンクの接続関係を考慮して、取得した車両の位置情報から車両が走行した走行リンクを正確に予測することが可能となる。従って、特定した走行リンクに基づいた交通混雑や旅行時間等の正確な判定及び算出をすることが可能となる。
また、検出されたリンクに対して接続される接続リンクが上位レベルの地図データで同一リンクであると判定された場合（Ｓ１４：ＹＥＳ）に、同一リンクであると判定された接続リンクを走行リンクに特定する（Ｓ１８）ので、レベルの異なる地図データを考慮して、取得した車両の位置情報から車両が走行した走行リンクを正確に予測することが可能となる。
また、検出されたリンクに対して接続される接続リンクが道なりの関係にあると判定された場合（Ｓ１５：ＹＥＳ）に、道なりの関係にあると判定された接続リンクを走行リンクに特定する（Ｓ１８）ので、道路状態を考慮して、取得した車両の位置情報から車両が走行した走行リンクを正確に予測することが可能となる。
また、検出されたリンクの間を接続するリンクの内、プローブカー２が過去に走行したリンクがあると判定された場合（Ｓ１６：ＹＥＳ）に、過去に走行したリンクを走行リンクに特定する（Ｓ１８）ので、過去の走行履歴を考慮して、取得した車両の位置情報から車両が走行した走行リンクを正確に予測することが可能となる。
また、検出された２点間をプローブカー２が走行するのに要した所要時間に対して最も平均走行所要時間が近いと判定されたリンク列を走行リンクに特定する（Ｓ２１）ので、リンクの走行時間を考慮して、取得した車両の位置情報から車両が走行した走行リンクを正確に予測することが可能となる。
更に、特定されたリンク又はリンク列に基づいて各リンクの旅行時間を算出する（Ｓ４）ので、プローブ情報センタ３は実際にリンクを走行したプローブカー２からの情報に基づいて走行リンクの旅行時間を正確に算出することが可能となる。

尚、本発明は前記実施形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の改良、変形が可能であることは勿論である。
例えば、本実施形態では、プローブカー２の走行した２点の位置座標を検出し（Ｓ２）、２点の位置座標の間においてプローブカー２が走行した走行リンクを特定することとしているが、３点以上の位置座標の間においてプローブカー２が走行した走行リンクを特定することとしても良い。

また、プローブカー２の走行した２点の位置座標を検出した（Ｓ２）後に、２点の位置座標をそれぞれ出発地及び目的地に設定してルート探索を行い、探索された経路に沿ったリンクを走行リンクとして特定することとしても良い。

また、プローブカー２が自車の現在位置と現在時刻をプローブ情報センタ３に対して送信するタイミングを所定時間間隔（本実施形態では１分間隔）でなく、所定距離間隔（例えば１００ｍ間隔）にしても良い。更に、ノードを通過する毎に送信することとしても良い。

１走行リンク特定システム
２プローブカー
３プローブ情報センタ
４端末車両
６センタ側通信装置
１１サーバ
１２ＣＰＵ
１３ＲＡＭ
１４ＲＯＭ
１５プローブ情報ＤＢ
１６センタ地図情報ＤＢ
１７リンク統計ＤＢ
１８走行履歴ＤＢ
２１現在地検出処理部
２３ナビゲーションＥＣＵ
２５液晶ディスプレイ
４１ＣＰＵ
４２ＲＡＭ
４３ＲＯＭ

Claims

所定距離間隔又は所定時間間隔で車両の現在位置に係る位置情報を取得する情報取得手段と、
地図データを道路網の情報量に基づいて複数レベルに階層化して記憶する地図データ記憶手段と、
前記情報取得手段により取得した位置情報に基づいて、前記地図データ記憶手段に記憶された所定のレベルの地図データから前記車両が走行した２以上のリンクを検出する位置リンク検出手段と、
前記複数レベルの地図データにおけるリンク毎の接続関係を記憶する接続関係記憶手段と、
前記接続関係記憶手段に記憶された接続関係に基づいて、前記位置リンク検出手段によって検出された各リンクの間を接続する接続リンクが、前記所定のレベルより道路網の情報量の少ない上位レベルの地図データにおいて前記検出された各リンクと同一リンクであるか否かを判定する同一リンク判定手段と、
前記同一リンク判定手段によって同一リンクであると判定された場合に、当該同一リンクと判定された接続リンクを前記車両が走行した走行リンクに特定する走行リンク特定手段と、を有することを特徴とする走行リンク特定システム。
前記走行リンク特定手段によって特定された走行リンクと前記走行リンクを前記車両が走行する所要時間とに基づいて、前記走行リンクの旅行時間を算出する旅行時間算出手段を有することを特徴とする請求項１に記載の走行リンク特定システム。