ナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置
【課題】位置情報を持たない複数の出入り口等を有する地点を目的地や出発地とする場合にも当該出入り口を特定した最適経路が探索できるようにする。
【解決手段】不特定多数が利用した案内経路、その経路上の位置履歴を含む経路探索ログを蓄積した探索ログデータベース４０と、同一探索ログ抽出手段３８と、仮想ノード設定手段３９と、経路探索手段３３と、を備え、出発地、目的地を含む経路探索要求があった場合、同一探索ログ抽出手段３８は、探索ログデータベース４０を参照して出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、仮想ノード設定手段３９は各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、経路探索手段３３は仮想ノードを出発地または目的地として最適経路を探索する。
【解決手段】不特定多数が利用した案内経路、その経路上の位置履歴を含む経路探索ログを蓄積した探索ログデータベース４０と、同一探索ログ抽出手段３８と、仮想ノード設定手段３９と、経路探索手段３３と、を備え、出発地、目的地を含む経路探索要求があった場合、同一探索ログ抽出手段３８は、探索ログデータベース４０を参照して出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、仮想ノード設定手段３９は各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、経路探索手段３３は仮想ノードを出発地または目的地として最適経路を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所望の出発地から目的地までの最適経路を探索して案内するナビゲーションシステムに関するものであり、特に、出発地または目的地がイベント会場や駐車場など比較的大きなエリアでかつその位置が緯度、経度によりピンポイントで示され、位置情報を持たない複数の出入り口がある場合にも最適経路が探索できるよう、経路探索サーバが探索した不特定多数の経路探索ログから当該出発地または目的地とした経路データを用いて最適経路となる出入り口を含む経路を探索できるようにしたナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
交通機関を利用する経路を探索する経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースと、これに基づいて交通ネットワークをデータベース化したデータを備えている。そして、これらのデータベースを参照して、乗り継ぎ（乗り換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００７】
交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。
【０００８】
徒歩経路に加えて交通機関を用いた経路を探索するナビゲーションシステムは、例えば、下記の特許文献２（特開２０００−２５８１８４号公報）に開示されている。この特許文献２に開示されたナビゲーションシステムは、出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法により最短コスト条件下で探索する交通ネットワーク経路探索方法を用いるものである。
【０００９】
そして、出発地点および目的地点から利用する交通機関の駅までの経路として、出発地点および目的地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を、緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、歩行経路を決定し、求められた歩行経路を交通機関の交通ネットワーク経路に組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索するように構成されている。
【００１０】
出発地または目的地がイベント会場や駐車場など比較的大きなエリアでかつその位置が緯度、経度によりピンポイントで示される場合にも最適経路が探索できることが好ましい。目的地に複数の出入り口や店舗がある場合に、その出入り口や個々の店舗までの経路を案内するナビゲーションシステムとしては、例えば、下記の特許文献３（特開２００２−３２３３３７号公報）、特許文献４（特開２００２−３４０６０４号公報）にナビゲーション装置の発明として開示されている。
【００１１】
特許文献３に開示されたナビゲーション装置は、ＰＯＩ（ポイントオブインタレスト）に複数の出入り口が存在する場合、現在位置から最も近い出入り口に案内する。地図情報にＰＯＩに関するＰＯＩ情報を含ませ、特定されたＰＯＩまでの経路を探索するナビゲーション装置の経路探索方法である。所定のＰＯＩ（ＡＡＡショッピングセンター）に複数の入口が存在する場合、各入口が接続する道路リンク（Ａ-link〜Ｄ-link）の識別データをＰＯＩ情報に予め含ませておく。ナビゲーション装置は、目的地として所定のＰＯＩ（ＡＡＡショッピングセンター）が設定された時、ＰＯＩ情報を参照して該ＰＯＩに複数の道路リンクが対応付けられているか調べ、対応付けられていれば、それぞれの道路リンクまでの経路を探索し、得られた経路のうち最適の経路を誘導経路として決定する。
【００１２】
また、特許文献４に開示されたナビゲーション装置は、ＰＯＩと該ＰＯＩ内の駐車場、ＰＯＩと該ＰＯＩ内の店舗などの関係を親子関係であると定義し、ＰＯＩにポリゴンデータ、住所、位置などの詳細情報を対応させ、更に、該ＰＯＩが親であれば子ＰＯＩのリストあるいはポリゴンデータを対応させ、親ＰＯＩが選択された時、親の詳細情報及びポリゴンを表示し、要求により、子ＰＯＩのリストあるいは子ＰＯＩのポリゴンを表示し、子POIリストあるいは子ＰＯＩポリゴンより子ＰＯＩを選択して目的地を入力するように構成したものである。
【００１３】
【特許文献１】特開２００１−１６５６８１号公報
【特許文献２】特開２０００−２５８１８４号公報
【特許文献３】特開２００２−３２３３３７号公報
【特許文献４】特開２００２−３４０６０４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
ところで、出発地や目的地に複数の出入り口や店舗がある場合に、その出入り口や個々の店舗までの経路を案内する場合、複数の出入り口や店舗に位置情報が対応づけられ、道路ネットワークのノードと当該複数の出入り口や店舗を結ぶリンク情報が用意されている場合には、上記特許文献３や特許文献４に開示されたナビゲーション装置のようにして最適経路を探索することができるが、複数の出入り口等に個々の位置情報が対応づけられておらず、また、道路ネットワークのノードとの間のリンク情報が用意されていない場合には最適経路を探索することができない。
【００１５】
一般に、大きな駐車場などにおいては複数の出入り口を有する場合が多いが、その出入り口に位置情報が対応付けられていないことも多い。駐車場には緯度、経度による位置情報が対応付けられていても、個々の出入り口に位置情報が対応付けられていないと道路ネットワークの近接ノードからのリンク情報が作られることもない。このような場合、駐車場から一定の距離範囲の道路ネットワーク上のノードを抽出して各ノード位置から駐車場の位置までの直線距離が近似的に駐車場までのリンクコストとして経路探索が行われる。このような探索を行った場合、最適経路として探索された経路が現実に最短の経路（最適経路）である保証はない。
【００１６】
図１１はこのような目的地の具体例を示す図である。図１１において道路Ｒ１〜道路Ｒ４に囲まれたエリアにＡショッピングモールがあり、その位置は緯度ｘ、経度ｙで表されている。各道路Ｒ１〜道路Ｒ４の各交差点はノードＮ１１、Ｎ１３、Ｎ１４、Ｎ１６になっている。Ａショッピングモールには駐車場Ｐが設置されており、出入り口ＩＯ１〜出入り口ＩＯ４が設けられている。出入り口ＩＯ１は道路Ｒ１に面しており、道路Ｒ１のノードＮ１２に接続されている。出入り口ＩＯ２は道路Ｒ２に面しており、道路２のノードＮ１５に接続されている。出入り口ＩＯ３とＩＯ４はそれぞれ道路Ｒ２、道路Ｒ４に面しているがノードに接続されていない。
【００１７】
また、各出入り口ＩＯ１〜出入り口ＩＯ４にはノードが設定されておらず位置情報を有していない。このＡショピングモールを目的地として経路探索する場合、Ａショッピングモール（位置ｘ、ｙ）の周辺のノードＮ１１〜Ｎ１６を抽出し、ノードＮ１１〜Ｎ１６のそれぞれからＡショッピングモールまでは直線距離をリンクコストとして、設定された出発地から各ノードＮ１１〜Ｎ１６のそれぞれを通る経路を探索し、出発地からＡショピングモールまでの累計の経路コスト（累計リンクコスト）が最小になる経路を最適経路として案内する。
【００１８】
各出入り口ＩＯ１〜ＩＯ４に最も近いノードＮ１１〜Ｎ１６の何れかへの経路コストはＡショッピングモールまでの直線距離で置き換えられているから探索した各経路の累計コストは出発地からそれぞれの出入り口ＩＯ１〜ＩＯ４までの経路コストを正確に表すものでなく、最適経路として案内された経路が最適経路である保証はない。
【００１９】
経路探索によって案内された道路のノードから駐車場の位置までの直線距離が、実際の駐車場出入り口までの距離に一致するとは限らないから、案内された道路を利用しても、更に遠回りしなければ実際の駐車場の出入り口まで到達できないこともあるからである。
【００２０】
本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、経路探索サーバ３０において、全ての利用者の経路探索ログを蓄積しておき、ある利用者から経路探索要求があった場合同じ出発地または目的地を探索条件とした経路探索ログから、道路上から最後に端末装置の位置が消失した地点、あるいは道路上に端末装置の位置が最初に復帰した地点が抽出でき、抽出した地点が出発地または目的地の出入り口を示すことを見出し、これらの消失点、復帰点を、リンクコストをゼロとする仮想ノードに接続し、この仮想ノードを出発地または目的地として経路探索すれば最適経路となる出入り口に到達する経路を探索し得ることに想到して本発明を完成するに至ったものである。
【００２１】
すなわち、本発明は上記の問題点を解消することを課題とし、出発地または目的地が比較的大きなエリアで、その位置が緯度、経度によりピンポイントで示され、かつ、位置情報を持たない複数の出入り口等を有する場合にも当該出入り口を特定した最適経路が探索できるようにしたナビゲーションシステムを提供することを目的とするものである。
【課題を解決するための手段】
【００２２】
前記課題を解決するために、本願の請求項１にかかる発明は、
探索用ネットワークデータを用いて出発地から目的地までの経路を探索するナビゲーションシステムにおいて、
前記ナビゲーションシステムは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とする。
【００２３】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記各出入り口のそれぞれと仮想ノードを接続するリンクのリンクコストはゼロであることを特徴とする。
【００２４】
本願の請求項３にかかる発明は、請求項１または請求項２にかかるナビゲーションシステムにおいて、前記ナビゲーションシステムは、経路探索条件を送信する端末装置と、ネットワークを介して前記端末装置と接続される経路探索サーバとを備えて構成されることを特徴とする。
【００２５】
また、本願の請求項４にかかる発明は、
ネットワークを介して経路探索条件を指定して経路探索要求を送信する端末装置と接続される経路探索サーバであって、
前記経路探索サーバは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とする。
【００２６】
本願の請求項５にかかる発明は、請求項４にかかる経路探索サーバにおいて、前記各出入り口のそれぞれと仮想ノードを接続するリンクのリンクコストはゼロであることを特徴とする。
【００２７】
また、本願の請求項６にかかる発明は、
探索用ネットワークデータを用いて出発ノードから目的ノードまでの経路を探索する経路探索方法において、
前記ナビゲーションシステムは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段が、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出するステップと、前記仮想ノード設定手段が前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定するステップと、前記経路探索手段が前記仮想ノードを出発地または目的地として最適経路を探索して案内経路とするステップとからなることを特徴とする。
【００２８】
本願の請求項７にかかる発明は、請求項６にかかる経路探索方法において、前記仮想ノード設定手段が前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定するステップは、リンクコストの値を０とするステップを含むことを特徴とする。
【００２９】
また、本願の請求項８にかかる発明は、
経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とする経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、通常の経路探索要求を行う探索要求モードと本発明による経路探索要求を行う同一探索ログ探索モードを備え、端末装置２０のユーザがモード指定をして経路探索サーバに経路探索を要求することを特徴とする。
【発明の効果】
【００３０】
請求項１にかかる発明においては、ナビゲーションシステムは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とする。
【００３１】
このような構成によれば、出発地または目的地がイベント会場や駐車場など比較的大きなエリアでかつその位置が緯度、経度によりピンポイントで示され、位置情報を持たない複数の出入り口がある場合にも、不特定多数の端末装置２０が同じ地点を出発地や目的地として探索した探索ログを抽出して出入り口の位置を抽出し、仮想ノードを設定して経路探索するから、最適経路となる出入り口を含む経路を案内できるようになる。
【００３２】
請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、各出入り口のそれぞれと仮想ノードを接続するリンクのリンクコストはゼロとするものであるから、経路探索において周辺への探索の拡散を生じることなく、効率的な経路探索を行うことができるようになる。
【００３３】
請求項３にかかる発明においては、請求項１または請求項２にかかるナビゲーションシステムにおいて、経路探索条件を送信する端末装置と、ネットワークを介して前記端末装置と接続される経路探索サーバとを備えて構成される。従って、経路探索サーバは、不特定多数の探索ログを蓄積することができ、同じ地点を出発地や目的地として探索した探索ログを抽出して出入り口の位置を抽出し、仮想ノードを設定して経路探索するから、最適経路となる出入り口を含む経路を案内できるようになる。
【００３４】
請求項４、請求項５にかかる発明においては、それぞれ請求項１、請求項２にかかるナビゲーションシステムを構成する経路探索サーバを提供することができ、請求項６、請求項７にかかる発明においては、それぞれ請求項１、請求項２にかかるナビゲーションシステムを実現する経路探索方法を提供することができる。また、請求項８にかかる発明は、請求項１〜請求項３にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。
【発明を実施するための最良の形態】
【００３５】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例１】
【００３６】
図１は、本発明の実施例１にかかるナビゲーションシステム１０の構成を示すシステム構成図である。図１に示すようにナビゲーションシステム１０は、ネットワーク１２を介して接続される端末装置２０と経路探索サーバ３０を備えて構成されている。このナビゲーションシステム１０は、各種カテゴリに属するＰＯＩの所在地やサービス内容などの詳細情報を提供するＰＯＩ情報配信サーバ５０、画像データや音楽データなどの各種コンテンツを配信する情報配信サーバ５１などを備えて構成されている。
【００３７】
経路探索サーバ３０はＰＯＩ情報配信サーバ５０や情報配信サーバ５１からネットワーク１２を経由して必要なデータを取得して自身のデータベースに追加することができる。また、同様にしてＰＯＩ情報配信サーバ５０に検索要求を送信して所望の検索結果を取得することもできる。端末装置２０としては携帯電話を用いることができ、またＰＤＡや音楽プレイヤーや携帯ゲーム機などの携帯機器であってもよい。
【００３８】
図１に示す経路探索サーバ３０は、探索用ネットワークデータベース３５、探索ログデータベース４０、ＰＯＩデータベース４１を備え、端末装置２０から経路探索要求があると、探索用ネットワークデータベース３５を参照して経路探索する。そして経路探索の結果により得た最適経路（案内経路経路）を端末装置２０に送信する一般的なナビゲーション機能を有している。また、端末装置２０から所望の地点やＰＯＩを指定して検索要求があると、ＰＯＩデータベース４１を参照して該当するＰＯＩの情報を読み出して端末装置２０に配信する。
【００３９】
経路探索サーバ３０は各端末装置２０からの経路探索要求に対して経路探索して端末装置２０に案内経路の情報を送信し、経路案内をすると、出発地、目的地、案内経路、および端末装置２０案内経路上（道路上）の位置履歴などの探索ログデータを逐一探索ログデータベース４０に蓄積する。探索ログデータベース４０に蓄積された各端末装置の探索ログは経路探索の際、参照して他の端末装置からある地点Ａ（例えば特定のＰＯＩなど）を目的地または出発地とした経路探索要求があると、同じ地点Ａを目的地または出発地とした探索ログを抽出することができる。
【００４０】
そして、抽出した探索ログを用いて、その地点Ａを目的地または出発地とした経路データ、位置履歴から地点Ａにおける道路上の位置履歴の消失点、復帰点を抽出し、その位置データから地点Ａにおける複数の出入り口の位置を特定することができる。消失点は地点Ａに到着時に道路上における位置情報が最後に得られた地点であり、復帰点は地点Ａから出発時に道路上における位置情報が最初に得られた地点であるから、地点Ａにおける出入り口を示す地点であると推定できる。また、探索ログはその地点Ａを目的地または出発地とする経路を探索した全端末装置の探索ログであるから、地点Ａに複数の出入り口が存在した場合、その全ての出入り口を利用した探索ログがある確率が極めて高いから、それらの消失点、復帰点が地点Ａにおける複数の出入り口の位置を示すと推定することできるのである。
【００４１】
複数の出入り口の位置が特定できたら、それらの各位置からリンクコストを「ゼロ」とする仮想ノードを設定し、前記他の端末装置２０が設定した出発地から仮想ノードを目的地とした経路探索を行う。それぞれの出入り口と仮想ノードのリンクコストは「ゼロ」であるから、探索された最適経路は出入り口の位置までの最適経路になる。複数の地点に対してリンクコスト「ゼロ」の仮想ノードを設定して経路探索するナビゲーションシステムの発明は本出願人により出願され、特開２００６−３００７３５号公報に開示されている。
【００４２】
以下、具体例に基づいて本発明を説明するが、その前に本発明にかかるシステムの詳細な構成を説明する。図２は、本発明の実施例にかかるナビゲーションシステムの詳細な構成を示すブロック図である。経路探索サーバ３０は、図１において述べたように、探索用の道路ネットワークデータを蓄積した探索用ネットワークデータベース３５、探索ログデータベース４０、ＰＯＩデータベース４１を備えている。
【００４３】
端末装置２０は、制御手段２１、通信手段２２、測位手段２３、表示手段２４、案内経路データ記憶手段２５、配信要求編集手段２６、操作・入力手段２７を備えて構成されている。測位手段２３は、ＧＰＳ受信機を備えＧＰＳ衛星信号を受信、処理して端末装置２０の現在位置（緯度・経度）を測位する。
【００４４】
通信手段２２は、無線通信ユニットを含み、経路探索サーバ３０と通信するためのものである。操作・入力手段２７は、キー、ダイヤル等からなり、端末装置２０を操作するための入力、出発地、目的地などの入力機能として用いられる。表示手段２４は液晶表示パネル等からなり、経路探索サーバ３０から配信された案内経路データの案内経路、地図の表示に使用されるものである。また、表示手段２４はメニュー画面を表示し端末装置２０を操作するための入力手段としても機能する。配信要求編集手段２６は、操作・入力手段２７を使用して入力された出発地、目的地、あるいは、測位手段２３で測位した端末装置２０の現在位置を出発地として、これらの情報に基づいて、経路探索サーバ３０に送信する経路探索要求を作成するものである。
【００４５】
案内経路データ記憶手段２５は、経路探索サーバ３０から配信された経路探索結果である案内経路データ、地図データ、ガイダンスなどを記憶するものであり、これらのデータは必要に応じて案内経路データ記憶手段２５から読み出され、表示手段２４に表示される。一般的には、測位手段２３で測位した端末装置２０の現在位置を含む一定の縮尺、一定の範囲の地図に、案内経路と、端末装置２０の現在位置を示すマークを重ね合わせて該現在位置マークが表示画面の中心になるように表示する。
【００４６】
測位手段２３によりＧＰＳ衛星信号を受信して測位した現在位置情報（緯度・経度の情報）には誤差が含まれるため、現在位置が案内経路からずれている場合には現在位置を案内経路上に補正するルートマッチング処理が行われる。また、経路探索サーバ３０から配信される案内経路データに音声ガイド（例えば、「この先、３００ｍ交差点です。左折して下さい」などの音声メッセージ）のデータが付加されている場合は、スピーカを介して音声メッセージを再生出力してユーザをガイドする。
【００４７】
一方、経路探索サーバ３０は、制御手段３１、経路案内手段３２、経路探索手段３３、通信手段３４、探索用ネットワークデータベース３５、同一探索ログ抽出手段３８、仮想ノード設定手段３９、探索ログデータベース４０、ＰＯＩデータベース４１などを備えて構成されている。探索用ネットワークデータベース３５には自動車による移動経路を探索するための道路ネットワークデータ３６を有する。経路探索サーバ３０が徒歩や公共交通機関を利用した経路を探索して端末装置２０に案内する機能を有する場合、探索用ネットワークデータベース３５には更に、徒歩専用のネットワークデータ、交通機関の運行時刻表データに基づく交通ネットワークデータ３７を蓄積しておく。
【００４８】
制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３４は、ネットワーク１２を介して端末装置２０と通信するためのインターフェースである。
【００４９】
経路探索手段３３は、端末装置２０からの経路探索条件に基づいて探索用ネットワークデータベース３５を参照して出発地から目的地までの最適経路を探索する。経路案内手段３２は、経路探索手段３３が探索した最適経路（案内経路）のデータを編集して端末装置２０に配信するためのものであり、通信手段３４は、端末装置２０からの各種要求を受信し、あるいは、端末装置２０に各種情報を配信する。
【００５０】
経路探索手段３３による経路探索は次のように行う。例えば、道路が図３に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
すなわち、図３において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図３では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００５１】
このような道路ネットワークのデータを探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図３において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００５２】
図３ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００５３】
これに対して、交通機関の経路探索のための交通ネットワークデータ３７は以下のように構成されている。例えば、図４に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図４において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図４では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００５４】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図４に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００５５】
図４に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【００５６】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
例えば、図４において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００５７】
各端末装置２０の要求に応じて経路探索した探索ログ（探索履歴）は探索ログデータベース４０に蓄積される。探索ログには出発地、目的地の他、案内経路上の移動において測位された現在位置の履歴が含まれる。従って、案内経路の道路上で最初に得られた位置情報（復帰点）が端末装置２０の出発地における出入り口、最後に得られた位置情報（消失点）が端末装置２０の目的地における出入り口を示す位置情報として利用することができる。
【００５８】
経路探索サーバ３０にある端末装置２０から複数の出入り口を有する駐車場、イベント会場あるいは施設などを目的地、例えば地点Ａを目的地または出発地とした経路探索要求があると、同一探索ログ抽出手段３８は探索ログデータベース４０を参照して、同一地点Ａを出発地または目的地とする探索ログを抽出し、各探索ログにおける端末装置２０の道路上への消失点、復帰点の位置情報を抽出して地点Ａの複数の出入り口位置とする。
【００５９】
仮想ノード設定手段３９は、このようにして同一探索ログ抽出手段３８が抽出した複数の出入り口の位置情報に基づいて、各出入り口の位置とリンクコストがゼロのリンクで接続される仮想ノード（位置情報を持たずユニークなノード番号のみを有する仮想的なノード）を設定する。これによりある端末装置２０が経路探索の目的地または出発地とした地点Ａは、地点Ａに設けられた複数の出入り口からリンクコストがゼロのリンクで接続された仮想ノードに置き換えることができる。
【００６０】
従って、経路探索手段３３は目的地または出発地である地点Ａの代わりに仮想ノードを目的地または出発地とした経路探索を行うことにより最適経路を探索する。探索の結果として得られた経路は、それぞれの出入り口と仮想ノードのリンクコストが「ゼロ」であるから、探索された最適経路は、経路探索条件で指定された地点Ａに対する目的地または出発地から地点Ａの各出入り口の位置を結ぶ経路のうち最小の累計コストを与える出入り口を通る経路になる。
【００６１】
仮想ノードを用いた経路探索の概念について以下に説明する。図５は、複数の地点、例えば、広いエリアＡＲを有する駐車場の出入り口Ｇ１〜Ｇ５を目的地として出発地ＳＴＡＲＴからの最適経路を探索する場合の位置関係を例示する模式図である。通常の経路探索においては出発点ＳＴＡＲＴからそれぞれの出入り口Ｇ１〜Ｇ５までの経路を探索して累計の経路コスト（リンクコスト）が最小の経路を最適経路として案内する。
【００６２】
この場合、各出入り口Ｇ１〜Ｇ５の位置が既知であることが前提となる。各出入り口Ｇ１〜Ｇ５の位置が特定できない場合にはこのような通常の経路探索を行うことができず、地点ＡＡを目的地とした経路探索をするしかない。それでは前述したように最適経路として案内した経路の出入り口が必ずしも最短経路であることを保証するものではないという問題が生じる。
【００６３】
図６は、図５のような経路探索において、同一探索ログ抽出手段３８が出入り口Ｇ１〜Ｇ５の位置を特定し、仮想ノードを設定した経路探索を行う場合の概念を示す図である。
同一探索ログ抽出手段３８が前述のようにして目的地である地点Ａの出入り口Ｇ１〜Ｇ５の位置を抽出すると、図６に示すように、経路探索サーバ３０は、出入り口Ｇ１〜Ｇ５の位置からリンクコストが「０」の値を持つリンクで接続される仮想ノードＰＮを設定する。この仮想ノードＰＮは経路探索のために仮に探索用のネットワークに接続されるものであり、リンクコスト累計の演算に用いられるだけであるから、探索用のネットワークのノードのように緯度、経度からなる位置情報を持つ必要はない。また、仮想ノードは経路探索上必要なだけなので表示する必要もない。従って仮想ノードに位置情報の値を設定する処理は一切必要がない。
【００６４】
仮想ノードＰＮが設定されると、経路探索サーバ３０は、出発地（ＳＴＡＲＴ）から仮想ノードＰＮまでの最適経路を探索する。この経路探索において、仮想ノードＰＮから各出入り口Ｇ１〜Ｇ５結ぶリンクのリンクコストは実際の距離によらず全て「０」であるから、仮想ノードＰＮと各出入り口Ｇ１〜Ｇ５の距離は仮想的に等距離である。
従って、出入り口Ｇ３を経由する経路が最短距離であれば、その経路が出発地（ＳＴＡＲＴ）から各出入り口Ｇ１〜Ｇ５までの経路の中で最短の経路であることになり、１回の経路探索で複数の出入り口Ｇ１〜Ｇ５のうち最も近い出入り口とそこまでの経路を端末装置２０に提供することができるようになる。
【００６５】
ここで、各出入り口Ｇ１〜Ｇ５から仮想ノードＰＮへのリンクのリンクコストは論理的にはそれぞれの値が等しければよく、必ずしも値が「０」である必要はない。しかしながら、リンクコストが「０」以外の値である場合には、経路探索時にダイクストラ法における拡散がその値の分だけ周辺に進む可能性があり、経路探索の処理時間が増大する場合がある。
この点、リンクコストの値が「０」であると、仮想ノードＰＮに探索が到達した時点で経路探索処理が終わる。すなわち、仮想ノードＰＮのリンクコストの値が「０」であれば効率的な経路探索処理を行うことができる。
【００６６】
このような探索ログと仮想ノードを用いた経路探索を行えば、徒歩と交通機関を利用した経路探索において、目的地や出発地の最寄り駅が複数の出入り口を有していて、かつ各出入り口に位置情報を持つノードが設定されていない場合であっても、探索ログから各出入り口の位置情報を特定し、仮想ノードを設定して経路探索すれば、図６と同様にして最適経路となる出入り口を案内することができる。
【００６７】
図７は、出発地側の駅に複数の出入り口が存在する場合の経路探索の概念を説明するための説明図である。図７は、目的地（ＧＯＡＬ）に対して出発地側の駅ＳＴ１に複数の出入り口Ａ１〜Ａ５が存在する場合を示している。出発地の最寄り駅ＳＴ１に複数の出入り口Ａ１〜Ａ５がある場合、同一探索ログ抽出手段３８が探索ログデータベース４０を参照して出入り口Ａ１〜Ａ５の位置を特定する。そして各出入り口Ａ１〜Ａ５の位置からリンクコストが「０」の値を持つリンクで接続される仮想ノードＰＮを設定する。
【００６８】
仮想ノードＰＮが設定されると、経路探索サーバ３０は、仮想ノードＰＮから目的地（ＧＯＡＬ）までの最適経路を探索する。この経路探索において、仮想ノードＰＮから各出入り口Ａ１〜Ａ５を結ぶリンクのリンクコストは実際の距離によらず全て「０」であるから、仮想ノードＰＮと出入り口Ａ１〜Ａ５の距離は仮想的に等距離である。
従って、出入り口Ａ３を経由する経路ＲＴ１が最短距離であれば、その経路が出発地側の出入り口Ａ１〜Ａ５の経路の中で最短の経路であることになる。
【００６９】
同様にして、出発地側、目的地側ともに位置情報を持たない複数の出入り口を有する場合の経路探索も可能である。図８は、このような経路探索の概念を説明するための説明図である。図８は端末装置２０からの経路探索要求において、出発地側の最寄り駅などのＰＯＩに複数の出入り口Ａ１〜Ａ５が存在し、目的地側のテーマパークなどのＰＯＩに複数の出入り口Ｇ１〜Ｇ５が存在している場合を示している。
【００７０】
このような経路探索要求が端末装置２０から経路探索サーバ３０に要求されると、経路探索サーバ３０は先ず、同一探索ログ抽出手段３８が探索ログデータベース４０を参照して出発地を同一とする探索ログがあるかを調べ、同一探索ログがあればその経路履歴から各端末装置２０の消失点、復帰点を抽出する。この消失点、復帰点の位置が複数の出入り口Ａ１〜Ａ５の位置になる。次に、仮想ノード設定手段３９は各出入り口Ａ１〜Ａ５のそれぞれからリンクコスト「０」のリンクで接続される仮想ノードＰＮ１を設定する。
【００７１】
目的地側についても出発地に対する処理と同様にして、同一探索ログ抽出手段３８が探索ログデータベース４０を参照して目的地を同一とする探索ログがあるかを調べ、同一探索ログがある場合その経路履歴から各端末装置２０の消失点、復帰点を抽出する。この消失点、復帰点の位置が複数の出入り口Ｇ１〜Ｇ５の位置になる。次に、仮想ノード設定手段３９は各出入り口Ｇ１〜Ｇ５のそれぞれからリンクコスト「０」のリンクで接続される仮想ノードＰＮ２を設定する。
【００７２】
次いで、経路探索サーバ３０において経路探索手段３３は仮想ノードＰＮ１、ＰＮ２を探索用ネットワークデータベース３５に一時的に追加する。図７において、点線が探索用のネットワークを模式的に表し、仮想ノードＰＮ１、ＰＮ２が追加される。経路探索手段３３はこの探索用ネットワークデータベース３５を用いて仮想ノードＰＮ１から仮想ノードＰＮ２に至る最適経路を探索する。
【００７３】
この探索はダイクストラ法など、一般的な経路探索において用いられる手法で行うことができる。すなわち、実際に経路探索を行う範囲は実際の探索用ネットワーク上になるが、仮想ノードＰＮ１（出発地側）と仮想ノードＰＮ２（目的地側）を置くことにより、この間で求められた最適経路は出発地と目的地も同時に特定している点に特徴がある。
【００７４】
仮想ノードＰＮ１と各出入り口Ａ１〜Ａ５の間のリンクコストは全て「０」で等しく、仮想ノードＰＮ２と各出入り口Ｇ１〜Ｇ５の間のリンクコストは、全て「０」で等しいから、経路探索の結果、仮想ノードＰＮ１から仮想ノードＰＮ２に至る最短経路ＲＴ１が得られ、この最短経路ＲＴ１が経由する出発地側の出入り口Ａ５と、目的地側の出入り口Ｇ１がそれぞれ出発地側、目的地側の最適な出入り口となる。
【００７５】
次に、ある地点Ａを出発地または目的地とした経路探索の結果である探索ログから、地点Ａの出入り口の位置を特定する手順を詳細に説明する。図９は、図１１に示した地点（Ａショピングモール）の駐車場の出入り口ＩＯ１〜ＩＯ４と探索ログにおける現在位置履歴を示す図である。出入り口ＩＯ１から駐車場を出入りしたある端末装置２０の現在位置履歴における消失点または復帰点の位置Ｍ１は、駐車場において該端末装置２０が最後または最初に位置情報を取得した場所である。
【００７６】
消失点または復帰点の位置Ｍ１から道路Ｒ１までの経路履歴は端末装置２０の位置情報履歴（図中のＰ１、Ｐ２、Ｐ３により結ぶことができるから、この経路履歴から道路Ｒ１上の駐車場の出入り口ＩＯへの位置を特定することができる。経路探索ログは不特定多数であるから、それらの経路履歴から得られた出入り口ＩＯ１に対する道路Ｒ１上の複数の位置情報の重心位置を算出すれば、出入り口ＩＯ１に対する道路Ｒ１上の位置をほぼ特定することができる。
【００７７】
以上、説明した本発明のナビゲーションシステムの経路探索手順について、図１０に示すフローチャートを参照して説明する。ステップＳ１０の処理において経路探索サーバ３０はナビゲーション端末装置２０から経路探索条件を受信する。
【００７８】
経路探索サーバ３０は経路探索条件を受信すると、先ずステップＳ１１の処理において同一探索ログ抽出手段３８は探索ログデータベース４０を参照して出発地を同一とする探索ログがあるか調べる。同一探索ログがあれば同一探索ログ抽出手段３８はステップＳ１３の処理において、同一探索ログの経路履歴から各端末装置２０の消失点、復帰点を抽出する。この消失点、復帰点の位置が複数の出入り口Ａ１〜Ａ５の位置になる。そして仮想ノード設定手段３９は、各出入り口Ａ１〜Ａ５からのリンクコストがゼロの仮想ノードＰＮ１を設定する。
【００７９】
同一探索ログがなかった場合はステップＳ１４の処理において経路探索手段３３は端末装置２０が設定した出発地を出発地ノードとする。
【００８０】
次に経路探索サーバ３０は目的地側についてもステップＳ１５〜ステップＳ１８の処理においてステップＳ１１〜ステップＳ１３と同様の処理を行い目的地側の複数の出入り口Ｇ１〜Ｇ５の位置に基づいて仮想ノードＰＮ２を設定する。同一探索ログがなかった場合はステップＳ１７の処理において経路探索手段３３は端末装置２０が設定した目的地を目的地ノードとする。
【００８１】
次に，経路探索手段３３は、仮想ノードＰＮ１を出発地、仮想ノードＰＮ２を目的地とした経路探索を行いステップＳ２０の処理において経路案内手段３２は経路探索手段３３が探索した最適経路を案内経路として端末装置２０に配信して経路案内を行う。出発地側、目的地側とも同一探索ログがない場合、ステップＳ１４、ステップＳ１７で決定される出発地ノード、目的地ノードは端末装置２０で設定された出発地、目的地となるから、通常の経路探索が行われる。
【００８２】
ステップＳ１９の処理において経路探索手段３３により最適経路が探索されると経路探索サーバ３０は探索した案内経路のデータをステップＳ２０の処理において端末装置２０に配信して処理を終了する。案内経路のデータを受信した端末装置２０は、案内経路のデータを案内経路データ記憶手段２５に一時記憶し、表示手段２４に地図、案内経路等を表示する。
【００８３】
なお、出発地側または目的地側を同一とする探索ログがなく、あるいは出入り口の位置が抽出できず、ステップＳ１４またはステップＳ１７の処理において、出発地または目的地が出発地ノードまたは目的地ノードとして決定されている場合、ステップＳ１９の処理におけるノードは仮想ノードでなく出発地ノードまたは目的地ノードが用いられることは当然である。
【００８４】
また、同一探索ログ抽出手段３８が抽出する探索ログは、出発地または目的地における出入り口の位置を抽出するものであるから、出発地と目的地が同一である探索ログを抽出する必要はなく、端末装置２０が経路探索の条件として指定した出発地と同一の出発地または目的地を有する探索ログ、端末装置２０が経路探索の条件として指定した目的地と同一の出発地または目的地を有する探索ログを独立に抽出して、それぞれの探索ログの位置履歴からその消失点、復帰点を抽出すればよい。
【００８５】
以上説明した図１０の処理手順は端末装置２０から経路探索要求に対して、経路探索サーバ３０は全て同一探索ログを抽出する処理を行う例を示したが、本発明はこの手順に限ることなく、端末装置２０に通常の経路探索要求を行う探索要求モードと本発明による経路探索要求を行う同一探索ログ探索モードを備え、端末装置２０のユーザがモード指定をして経路探索サーバに経路探索を要求するように構成することもできる。
【００８６】
以上、詳細に説明したように本発明によれば、出発地または目的地がイベント会場や駐車場など比較的大きなエリアでかつその位置が緯度、経度によりピンポイントで示され、位置情報を持たない複数の出入り口がある場合にも、不特定多数の端末装置２０が同じ地点を出発地や目的地として探索した探索ログを抽出して出入り口の位置を抽出するから、最適経路となる出入り口を含む経路を案内できるようになる。
【図面の簡単な説明】
【００８７】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】本発明の実施例にかかるナビゲーションシステムの詳細な構成を示すブロック図である。
【図３】道路ネットワークのデータの概念を示す模式図である。
【図４】交通ネットワークのデータの概念を示す模式図である。
【図５】複数の出入り口を有するエリアを目的地とする経路探索の概念を示す模式図である。
【図６】位置情報を持たない複数の出入り口を有するエリアを目的地として仮想ノードを設定して最適経路を探索する概念を示す模式図である。
【図７】出発地側の駅に複数の出入り口が存在する場合の経路探索の概念を説明するための説明図である。
【図８】出発地側、目的地側の双方に複数の出入り口がある場合の経路探索の概念を示す模式図である。
【図９】探索ログから複数の出入り口を特定する処理の詳細を説明するための模式図である。
【図１０】本発明の実施例にかかるナビゲーションシステムにおける経路探索の手順を示すフローチャートである。
【図１１】出入り口を有する出発地または目的地と、その周辺の道路および道路上に設定されたノードの一例を示す図である。
【符号の説明】
【００８８】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２１・・・・制御手段
２２・・・・通信手段
２３・・・・測位手段（ＧＰＳ受信手段）
２４・・・・表示手段
２５・・・・案内経路データ記憶手段
２６・・・・配信要求編集手段
２７・・・・操作・入力手段
３０・・・・経路探索サーバ
３１・・・・制御手段
３２・・・・経路案内手段
３３・・・・経路探索手段
３４・・・・通信手段
３５・・・・探索用ネットワークデータベース
３６・・・・道路ネットワークデータ
３７・・・・交通ネットワークデータ
３８・・・・同一探索ログ抽出手段
３９・・・・仮想ノード設定手段
４０・・・・探索ログデータベース
４１・・・・ＰＯＩデータベース
５０・・・・ＰＯＩ情報提供サーバ
５１・・・・情報配信サーバ
【技術分野】
【０００１】
本発明は、所望の出発地から目的地までの最適経路を探索して案内するナビゲーションシステムに関するものであり、特に、出発地または目的地がイベント会場や駐車場など比較的大きなエリアでかつその位置が緯度、経度によりピンポイントで示され、位置情報を持たない複数の出入り口がある場合にも最適経路が探索できるよう、経路探索サーバが探索した不特定多数の経路探索ログから当該出発地または目的地とした経路データを用いて最適経路となる出入り口を含む経路を探索できるようにしたナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。
【０００４】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
交通機関を利用する経路を探索する経路探索システムは、ユーザが指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースと、これに基づいて交通ネットワークをデータベース化したデータを備えている。そして、これらのデータベースを参照して、乗り継ぎ（乗り換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００７】
交通機関を利用した経路探索、経路案内をするナビゲーションシステムなどにおける探索用のデータは、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、所要時間がリンクコストのデータとして加えられる。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。
【０００８】
徒歩経路に加えて交通機関を用いた経路を探索するナビゲーションシステムは、例えば、下記の特許文献２（特開２０００−２５８１８４号公報）に開示されている。この特許文献２に開示されたナビゲーションシステムは、出発地点から目的地点までの経路を、地点をノード、地点間をリンクとして交通ネットワークを表現し、コンピュータを用いてラベル確定法により最短コスト条件下で探索する交通ネットワーク経路探索方法を用いるものである。
【０００９】
そして、出発地点および目的地点から利用する交通機関の駅までの経路として、出発地点および目的地点から利用する交通機関の駅までの直線距離、および目的地点から利用する交通機関の駅までの直線距離を、緯度経度情報を用いて求め、該直線距離を変数として平均コストを算出し、前記平均コストが指定したコストの範囲内に含まれるすべての利用交通機関の駅を求め、歩行経路を決定し、求められた歩行経路を交通機関の交通ネットワーク経路に組み込んで総合交通ネットワークを表現し、コンピュータを用いてラベル確定法により求めるコスト条件下で探索するように構成されている。
【００１０】
出発地または目的地がイベント会場や駐車場など比較的大きなエリアでかつその位置が緯度、経度によりピンポイントで示される場合にも最適経路が探索できることが好ましい。目的地に複数の出入り口や店舗がある場合に、その出入り口や個々の店舗までの経路を案内するナビゲーションシステムとしては、例えば、下記の特許文献３（特開２００２−３２３３３７号公報）、特許文献４（特開２００２−３４０６０４号公報）にナビゲーション装置の発明として開示されている。
【００１１】
特許文献３に開示されたナビゲーション装置は、ＰＯＩ（ポイントオブインタレスト）に複数の出入り口が存在する場合、現在位置から最も近い出入り口に案内する。地図情報にＰＯＩに関するＰＯＩ情報を含ませ、特定されたＰＯＩまでの経路を探索するナビゲーション装置の経路探索方法である。所定のＰＯＩ（ＡＡＡショッピングセンター）に複数の入口が存在する場合、各入口が接続する道路リンク（Ａ-link〜Ｄ-link）の識別データをＰＯＩ情報に予め含ませておく。ナビゲーション装置は、目的地として所定のＰＯＩ（ＡＡＡショッピングセンター）が設定された時、ＰＯＩ情報を参照して該ＰＯＩに複数の道路リンクが対応付けられているか調べ、対応付けられていれば、それぞれの道路リンクまでの経路を探索し、得られた経路のうち最適の経路を誘導経路として決定する。
【００１２】
また、特許文献４に開示されたナビゲーション装置は、ＰＯＩと該ＰＯＩ内の駐車場、ＰＯＩと該ＰＯＩ内の店舗などの関係を親子関係であると定義し、ＰＯＩにポリゴンデータ、住所、位置などの詳細情報を対応させ、更に、該ＰＯＩが親であれば子ＰＯＩのリストあるいはポリゴンデータを対応させ、親ＰＯＩが選択された時、親の詳細情報及びポリゴンを表示し、要求により、子ＰＯＩのリストあるいは子ＰＯＩのポリゴンを表示し、子POIリストあるいは子ＰＯＩポリゴンより子ＰＯＩを選択して目的地を入力するように構成したものである。
【００１３】
【特許文献１】特開２００１−１６５６８１号公報
【特許文献２】特開２０００−２５８１８４号公報
【特許文献３】特開２００２−３２３３３７号公報
【特許文献４】特開２００２−３４０６０４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
ところで、出発地や目的地に複数の出入り口や店舗がある場合に、その出入り口や個々の店舗までの経路を案内する場合、複数の出入り口や店舗に位置情報が対応づけられ、道路ネットワークのノードと当該複数の出入り口や店舗を結ぶリンク情報が用意されている場合には、上記特許文献３や特許文献４に開示されたナビゲーション装置のようにして最適経路を探索することができるが、複数の出入り口等に個々の位置情報が対応づけられておらず、また、道路ネットワークのノードとの間のリンク情報が用意されていない場合には最適経路を探索することができない。
【００１５】
一般に、大きな駐車場などにおいては複数の出入り口を有する場合が多いが、その出入り口に位置情報が対応付けられていないことも多い。駐車場には緯度、経度による位置情報が対応付けられていても、個々の出入り口に位置情報が対応付けられていないと道路ネットワークの近接ノードからのリンク情報が作られることもない。このような場合、駐車場から一定の距離範囲の道路ネットワーク上のノードを抽出して各ノード位置から駐車場の位置までの直線距離が近似的に駐車場までのリンクコストとして経路探索が行われる。このような探索を行った場合、最適経路として探索された経路が現実に最短の経路（最適経路）である保証はない。
【００１６】
図１１はこのような目的地の具体例を示す図である。図１１において道路Ｒ１〜道路Ｒ４に囲まれたエリアにＡショッピングモールがあり、その位置は緯度ｘ、経度ｙで表されている。各道路Ｒ１〜道路Ｒ４の各交差点はノードＮ１１、Ｎ１３、Ｎ１４、Ｎ１６になっている。Ａショッピングモールには駐車場Ｐが設置されており、出入り口ＩＯ１〜出入り口ＩＯ４が設けられている。出入り口ＩＯ１は道路Ｒ１に面しており、道路Ｒ１のノードＮ１２に接続されている。出入り口ＩＯ２は道路Ｒ２に面しており、道路２のノードＮ１５に接続されている。出入り口ＩＯ３とＩＯ４はそれぞれ道路Ｒ２、道路Ｒ４に面しているがノードに接続されていない。
【００１７】
また、各出入り口ＩＯ１〜出入り口ＩＯ４にはノードが設定されておらず位置情報を有していない。このＡショピングモールを目的地として経路探索する場合、Ａショッピングモール（位置ｘ、ｙ）の周辺のノードＮ１１〜Ｎ１６を抽出し、ノードＮ１１〜Ｎ１６のそれぞれからＡショッピングモールまでは直線距離をリンクコストとして、設定された出発地から各ノードＮ１１〜Ｎ１６のそれぞれを通る経路を探索し、出発地からＡショピングモールまでの累計の経路コスト（累計リンクコスト）が最小になる経路を最適経路として案内する。
【００１８】
各出入り口ＩＯ１〜ＩＯ４に最も近いノードＮ１１〜Ｎ１６の何れかへの経路コストはＡショッピングモールまでの直線距離で置き換えられているから探索した各経路の累計コストは出発地からそれぞれの出入り口ＩＯ１〜ＩＯ４までの経路コストを正確に表すものでなく、最適経路として案内された経路が最適経路である保証はない。
【００１９】
経路探索によって案内された道路のノードから駐車場の位置までの直線距離が、実際の駐車場出入り口までの距離に一致するとは限らないから、案内された道路を利用しても、更に遠回りしなければ実際の駐車場の出入り口まで到達できないこともあるからである。
【００２０】
本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、経路探索サーバ３０において、全ての利用者の経路探索ログを蓄積しておき、ある利用者から経路探索要求があった場合同じ出発地または目的地を探索条件とした経路探索ログから、道路上から最後に端末装置の位置が消失した地点、あるいは道路上に端末装置の位置が最初に復帰した地点が抽出でき、抽出した地点が出発地または目的地の出入り口を示すことを見出し、これらの消失点、復帰点を、リンクコストをゼロとする仮想ノードに接続し、この仮想ノードを出発地または目的地として経路探索すれば最適経路となる出入り口に到達する経路を探索し得ることに想到して本発明を完成するに至ったものである。
【００２１】
すなわち、本発明は上記の問題点を解消することを課題とし、出発地または目的地が比較的大きなエリアで、その位置が緯度、経度によりピンポイントで示され、かつ、位置情報を持たない複数の出入り口等を有する場合にも当該出入り口を特定した最適経路が探索できるようにしたナビゲーションシステムを提供することを目的とするものである。
【課題を解決するための手段】
【００２２】
前記課題を解決するために、本願の請求項１にかかる発明は、
探索用ネットワークデータを用いて出発地から目的地までの経路を探索するナビゲーションシステムにおいて、
前記ナビゲーションシステムは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とする。
【００２３】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記各出入り口のそれぞれと仮想ノードを接続するリンクのリンクコストはゼロであることを特徴とする。
【００２４】
本願の請求項３にかかる発明は、請求項１または請求項２にかかるナビゲーションシステムにおいて、前記ナビゲーションシステムは、経路探索条件を送信する端末装置と、ネットワークを介して前記端末装置と接続される経路探索サーバとを備えて構成されることを特徴とする。
【００２５】
また、本願の請求項４にかかる発明は、
ネットワークを介して経路探索条件を指定して経路探索要求を送信する端末装置と接続される経路探索サーバであって、
前記経路探索サーバは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とする。
【００２６】
本願の請求項５にかかる発明は、請求項４にかかる経路探索サーバにおいて、前記各出入り口のそれぞれと仮想ノードを接続するリンクのリンクコストはゼロであることを特徴とする。
【００２７】
また、本願の請求項６にかかる発明は、
探索用ネットワークデータを用いて出発ノードから目的ノードまでの経路を探索する経路探索方法において、
前記ナビゲーションシステムは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段が、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出するステップと、前記仮想ノード設定手段が前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定するステップと、前記経路探索手段が前記仮想ノードを出発地または目的地として最適経路を探索して案内経路とするステップとからなることを特徴とする。
【００２８】
本願の請求項７にかかる発明は、請求項６にかかる経路探索方法において、前記仮想ノード設定手段が前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定するステップは、リンクコストの値を０とするステップを含むことを特徴とする。
【００２９】
また、本願の請求項８にかかる発明は、
経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とする経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、通常の経路探索要求を行う探索要求モードと本発明による経路探索要求を行う同一探索ログ探索モードを備え、端末装置２０のユーザがモード指定をして経路探索サーバに経路探索を要求することを特徴とする。
【発明の効果】
【００３０】
請求項１にかかる発明においては、ナビゲーションシステムは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とする。
【００３１】
このような構成によれば、出発地または目的地がイベント会場や駐車場など比較的大きなエリアでかつその位置が緯度、経度によりピンポイントで示され、位置情報を持たない複数の出入り口がある場合にも、不特定多数の端末装置２０が同じ地点を出発地や目的地として探索した探索ログを抽出して出入り口の位置を抽出し、仮想ノードを設定して経路探索するから、最適経路となる出入り口を含む経路を案内できるようになる。
【００３２】
請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、各出入り口のそれぞれと仮想ノードを接続するリンクのリンクコストはゼロとするものであるから、経路探索において周辺への探索の拡散を生じることなく、効率的な経路探索を行うことができるようになる。
【００３３】
請求項３にかかる発明においては、請求項１または請求項２にかかるナビゲーションシステムにおいて、経路探索条件を送信する端末装置と、ネットワークを介して前記端末装置と接続される経路探索サーバとを備えて構成される。従って、経路探索サーバは、不特定多数の探索ログを蓄積することができ、同じ地点を出発地や目的地として探索した探索ログを抽出して出入り口の位置を抽出し、仮想ノードを設定して経路探索するから、最適経路となる出入り口を含む経路を案内できるようになる。
【００３４】
請求項４、請求項５にかかる発明においては、それぞれ請求項１、請求項２にかかるナビゲーションシステムを構成する経路探索サーバを提供することができ、請求項６、請求項７にかかる発明においては、それぞれ請求項１、請求項２にかかるナビゲーションシステムを実現する経路探索方法を提供することができる。また、請求項８にかかる発明は、請求項１〜請求項３にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。
【発明を実施するための最良の形態】
【００３５】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例１】
【００３６】
図１は、本発明の実施例１にかかるナビゲーションシステム１０の構成を示すシステム構成図である。図１に示すようにナビゲーションシステム１０は、ネットワーク１２を介して接続される端末装置２０と経路探索サーバ３０を備えて構成されている。このナビゲーションシステム１０は、各種カテゴリに属するＰＯＩの所在地やサービス内容などの詳細情報を提供するＰＯＩ情報配信サーバ５０、画像データや音楽データなどの各種コンテンツを配信する情報配信サーバ５１などを備えて構成されている。
【００３７】
経路探索サーバ３０はＰＯＩ情報配信サーバ５０や情報配信サーバ５１からネットワーク１２を経由して必要なデータを取得して自身のデータベースに追加することができる。また、同様にしてＰＯＩ情報配信サーバ５０に検索要求を送信して所望の検索結果を取得することもできる。端末装置２０としては携帯電話を用いることができ、またＰＤＡや音楽プレイヤーや携帯ゲーム機などの携帯機器であってもよい。
【００３８】
図１に示す経路探索サーバ３０は、探索用ネットワークデータベース３５、探索ログデータベース４０、ＰＯＩデータベース４１を備え、端末装置２０から経路探索要求があると、探索用ネットワークデータベース３５を参照して経路探索する。そして経路探索の結果により得た最適経路（案内経路経路）を端末装置２０に送信する一般的なナビゲーション機能を有している。また、端末装置２０から所望の地点やＰＯＩを指定して検索要求があると、ＰＯＩデータベース４１を参照して該当するＰＯＩの情報を読み出して端末装置２０に配信する。
【００３９】
経路探索サーバ３０は各端末装置２０からの経路探索要求に対して経路探索して端末装置２０に案内経路の情報を送信し、経路案内をすると、出発地、目的地、案内経路、および端末装置２０案内経路上（道路上）の位置履歴などの探索ログデータを逐一探索ログデータベース４０に蓄積する。探索ログデータベース４０に蓄積された各端末装置の探索ログは経路探索の際、参照して他の端末装置からある地点Ａ（例えば特定のＰＯＩなど）を目的地または出発地とした経路探索要求があると、同じ地点Ａを目的地または出発地とした探索ログを抽出することができる。
【００４０】
そして、抽出した探索ログを用いて、その地点Ａを目的地または出発地とした経路データ、位置履歴から地点Ａにおける道路上の位置履歴の消失点、復帰点を抽出し、その位置データから地点Ａにおける複数の出入り口の位置を特定することができる。消失点は地点Ａに到着時に道路上における位置情報が最後に得られた地点であり、復帰点は地点Ａから出発時に道路上における位置情報が最初に得られた地点であるから、地点Ａにおける出入り口を示す地点であると推定できる。また、探索ログはその地点Ａを目的地または出発地とする経路を探索した全端末装置の探索ログであるから、地点Ａに複数の出入り口が存在した場合、その全ての出入り口を利用した探索ログがある確率が極めて高いから、それらの消失点、復帰点が地点Ａにおける複数の出入り口の位置を示すと推定することできるのである。
【００４１】
複数の出入り口の位置が特定できたら、それらの各位置からリンクコストを「ゼロ」とする仮想ノードを設定し、前記他の端末装置２０が設定した出発地から仮想ノードを目的地とした経路探索を行う。それぞれの出入り口と仮想ノードのリンクコストは「ゼロ」であるから、探索された最適経路は出入り口の位置までの最適経路になる。複数の地点に対してリンクコスト「ゼロ」の仮想ノードを設定して経路探索するナビゲーションシステムの発明は本出願人により出願され、特開２００６−３００７３５号公報に開示されている。
【００４２】
以下、具体例に基づいて本発明を説明するが、その前に本発明にかかるシステムの詳細な構成を説明する。図２は、本発明の実施例にかかるナビゲーションシステムの詳細な構成を示すブロック図である。経路探索サーバ３０は、図１において述べたように、探索用の道路ネットワークデータを蓄積した探索用ネットワークデータベース３５、探索ログデータベース４０、ＰＯＩデータベース４１を備えている。
【００４３】
端末装置２０は、制御手段２１、通信手段２２、測位手段２３、表示手段２４、案内経路データ記憶手段２５、配信要求編集手段２６、操作・入力手段２７を備えて構成されている。測位手段２３は、ＧＰＳ受信機を備えＧＰＳ衛星信号を受信、処理して端末装置２０の現在位置（緯度・経度）を測位する。
【００４４】
通信手段２２は、無線通信ユニットを含み、経路探索サーバ３０と通信するためのものである。操作・入力手段２７は、キー、ダイヤル等からなり、端末装置２０を操作するための入力、出発地、目的地などの入力機能として用いられる。表示手段２４は液晶表示パネル等からなり、経路探索サーバ３０から配信された案内経路データの案内経路、地図の表示に使用されるものである。また、表示手段２４はメニュー画面を表示し端末装置２０を操作するための入力手段としても機能する。配信要求編集手段２６は、操作・入力手段２７を使用して入力された出発地、目的地、あるいは、測位手段２３で測位した端末装置２０の現在位置を出発地として、これらの情報に基づいて、経路探索サーバ３０に送信する経路探索要求を作成するものである。
【００４５】
案内経路データ記憶手段２５は、経路探索サーバ３０から配信された経路探索結果である案内経路データ、地図データ、ガイダンスなどを記憶するものであり、これらのデータは必要に応じて案内経路データ記憶手段２５から読み出され、表示手段２４に表示される。一般的には、測位手段２３で測位した端末装置２０の現在位置を含む一定の縮尺、一定の範囲の地図に、案内経路と、端末装置２０の現在位置を示すマークを重ね合わせて該現在位置マークが表示画面の中心になるように表示する。
【００４６】
測位手段２３によりＧＰＳ衛星信号を受信して測位した現在位置情報（緯度・経度の情報）には誤差が含まれるため、現在位置が案内経路からずれている場合には現在位置を案内経路上に補正するルートマッチング処理が行われる。また、経路探索サーバ３０から配信される案内経路データに音声ガイド（例えば、「この先、３００ｍ交差点です。左折して下さい」などの音声メッセージ）のデータが付加されている場合は、スピーカを介して音声メッセージを再生出力してユーザをガイドする。
【００４７】
一方、経路探索サーバ３０は、制御手段３１、経路案内手段３２、経路探索手段３３、通信手段３４、探索用ネットワークデータベース３５、同一探索ログ抽出手段３８、仮想ノード設定手段３９、探索ログデータベース４０、ＰＯＩデータベース４１などを備えて構成されている。探索用ネットワークデータベース３５には自動車による移動経路を探索するための道路ネットワークデータ３６を有する。経路探索サーバ３０が徒歩や公共交通機関を利用した経路を探索して端末装置２０に案内する機能を有する場合、探索用ネットワークデータベース３５には更に、徒歩専用のネットワークデータ、交通機関の運行時刻表データに基づく交通ネットワークデータ３７を蓄積しておく。
【００４８】
制御手段３１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３４は、ネットワーク１２を介して端末装置２０と通信するためのインターフェースである。
【００４９】
経路探索手段３３は、端末装置２０からの経路探索条件に基づいて探索用ネットワークデータベース３５を参照して出発地から目的地までの最適経路を探索する。経路案内手段３２は、経路探索手段３３が探索した最適経路（案内経路）のデータを編集して端末装置２０に配信するためのものであり、通信手段３４は、端末装置２０からの各種要求を受信し、あるいは、端末装置２０に各種情報を配信する。
【００５０】
経路探索手段３３による経路探索は次のように行う。例えば、道路が図３に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
すなわち、図３において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図３では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００５１】
このような道路ネットワークのデータを探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図３において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００５２】
図３ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００５３】
これに対して、交通機関の経路探索のための交通ネットワークデータ３７は以下のように構成されている。例えば、図４に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図４において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図４では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００５４】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図４に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００５５】
図４に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【００５６】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
例えば、図４において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００５７】
各端末装置２０の要求に応じて経路探索した探索ログ（探索履歴）は探索ログデータベース４０に蓄積される。探索ログには出発地、目的地の他、案内経路上の移動において測位された現在位置の履歴が含まれる。従って、案内経路の道路上で最初に得られた位置情報（復帰点）が端末装置２０の出発地における出入り口、最後に得られた位置情報（消失点）が端末装置２０の目的地における出入り口を示す位置情報として利用することができる。
【００５８】
経路探索サーバ３０にある端末装置２０から複数の出入り口を有する駐車場、イベント会場あるいは施設などを目的地、例えば地点Ａを目的地または出発地とした経路探索要求があると、同一探索ログ抽出手段３８は探索ログデータベース４０を参照して、同一地点Ａを出発地または目的地とする探索ログを抽出し、各探索ログにおける端末装置２０の道路上への消失点、復帰点の位置情報を抽出して地点Ａの複数の出入り口位置とする。
【００５９】
仮想ノード設定手段３９は、このようにして同一探索ログ抽出手段３８が抽出した複数の出入り口の位置情報に基づいて、各出入り口の位置とリンクコストがゼロのリンクで接続される仮想ノード（位置情報を持たずユニークなノード番号のみを有する仮想的なノード）を設定する。これによりある端末装置２０が経路探索の目的地または出発地とした地点Ａは、地点Ａに設けられた複数の出入り口からリンクコストがゼロのリンクで接続された仮想ノードに置き換えることができる。
【００６０】
従って、経路探索手段３３は目的地または出発地である地点Ａの代わりに仮想ノードを目的地または出発地とした経路探索を行うことにより最適経路を探索する。探索の結果として得られた経路は、それぞれの出入り口と仮想ノードのリンクコストが「ゼロ」であるから、探索された最適経路は、経路探索条件で指定された地点Ａに対する目的地または出発地から地点Ａの各出入り口の位置を結ぶ経路のうち最小の累計コストを与える出入り口を通る経路になる。
【００６１】
仮想ノードを用いた経路探索の概念について以下に説明する。図５は、複数の地点、例えば、広いエリアＡＲを有する駐車場の出入り口Ｇ１〜Ｇ５を目的地として出発地ＳＴＡＲＴからの最適経路を探索する場合の位置関係を例示する模式図である。通常の経路探索においては出発点ＳＴＡＲＴからそれぞれの出入り口Ｇ１〜Ｇ５までの経路を探索して累計の経路コスト（リンクコスト）が最小の経路を最適経路として案内する。
【００６２】
この場合、各出入り口Ｇ１〜Ｇ５の位置が既知であることが前提となる。各出入り口Ｇ１〜Ｇ５の位置が特定できない場合にはこのような通常の経路探索を行うことができず、地点ＡＡを目的地とした経路探索をするしかない。それでは前述したように最適経路として案内した経路の出入り口が必ずしも最短経路であることを保証するものではないという問題が生じる。
【００６３】
図６は、図５のような経路探索において、同一探索ログ抽出手段３８が出入り口Ｇ１〜Ｇ５の位置を特定し、仮想ノードを設定した経路探索を行う場合の概念を示す図である。
同一探索ログ抽出手段３８が前述のようにして目的地である地点Ａの出入り口Ｇ１〜Ｇ５の位置を抽出すると、図６に示すように、経路探索サーバ３０は、出入り口Ｇ１〜Ｇ５の位置からリンクコストが「０」の値を持つリンクで接続される仮想ノードＰＮを設定する。この仮想ノードＰＮは経路探索のために仮に探索用のネットワークに接続されるものであり、リンクコスト累計の演算に用いられるだけであるから、探索用のネットワークのノードのように緯度、経度からなる位置情報を持つ必要はない。また、仮想ノードは経路探索上必要なだけなので表示する必要もない。従って仮想ノードに位置情報の値を設定する処理は一切必要がない。
【００６４】
仮想ノードＰＮが設定されると、経路探索サーバ３０は、出発地（ＳＴＡＲＴ）から仮想ノードＰＮまでの最適経路を探索する。この経路探索において、仮想ノードＰＮから各出入り口Ｇ１〜Ｇ５結ぶリンクのリンクコストは実際の距離によらず全て「０」であるから、仮想ノードＰＮと各出入り口Ｇ１〜Ｇ５の距離は仮想的に等距離である。
従って、出入り口Ｇ３を経由する経路が最短距離であれば、その経路が出発地（ＳＴＡＲＴ）から各出入り口Ｇ１〜Ｇ５までの経路の中で最短の経路であることになり、１回の経路探索で複数の出入り口Ｇ１〜Ｇ５のうち最も近い出入り口とそこまでの経路を端末装置２０に提供することができるようになる。
【００６５】
ここで、各出入り口Ｇ１〜Ｇ５から仮想ノードＰＮへのリンクのリンクコストは論理的にはそれぞれの値が等しければよく、必ずしも値が「０」である必要はない。しかしながら、リンクコストが「０」以外の値である場合には、経路探索時にダイクストラ法における拡散がその値の分だけ周辺に進む可能性があり、経路探索の処理時間が増大する場合がある。
この点、リンクコストの値が「０」であると、仮想ノードＰＮに探索が到達した時点で経路探索処理が終わる。すなわち、仮想ノードＰＮのリンクコストの値が「０」であれば効率的な経路探索処理を行うことができる。
【００６６】
このような探索ログと仮想ノードを用いた経路探索を行えば、徒歩と交通機関を利用した経路探索において、目的地や出発地の最寄り駅が複数の出入り口を有していて、かつ各出入り口に位置情報を持つノードが設定されていない場合であっても、探索ログから各出入り口の位置情報を特定し、仮想ノードを設定して経路探索すれば、図６と同様にして最適経路となる出入り口を案内することができる。
【００６７】
図７は、出発地側の駅に複数の出入り口が存在する場合の経路探索の概念を説明するための説明図である。図７は、目的地（ＧＯＡＬ）に対して出発地側の駅ＳＴ１に複数の出入り口Ａ１〜Ａ５が存在する場合を示している。出発地の最寄り駅ＳＴ１に複数の出入り口Ａ１〜Ａ５がある場合、同一探索ログ抽出手段３８が探索ログデータベース４０を参照して出入り口Ａ１〜Ａ５の位置を特定する。そして各出入り口Ａ１〜Ａ５の位置からリンクコストが「０」の値を持つリンクで接続される仮想ノードＰＮを設定する。
【００６８】
仮想ノードＰＮが設定されると、経路探索サーバ３０は、仮想ノードＰＮから目的地（ＧＯＡＬ）までの最適経路を探索する。この経路探索において、仮想ノードＰＮから各出入り口Ａ１〜Ａ５を結ぶリンクのリンクコストは実際の距離によらず全て「０」であるから、仮想ノードＰＮと出入り口Ａ１〜Ａ５の距離は仮想的に等距離である。
従って、出入り口Ａ３を経由する経路ＲＴ１が最短距離であれば、その経路が出発地側の出入り口Ａ１〜Ａ５の経路の中で最短の経路であることになる。
【００６９】
同様にして、出発地側、目的地側ともに位置情報を持たない複数の出入り口を有する場合の経路探索も可能である。図８は、このような経路探索の概念を説明するための説明図である。図８は端末装置２０からの経路探索要求において、出発地側の最寄り駅などのＰＯＩに複数の出入り口Ａ１〜Ａ５が存在し、目的地側のテーマパークなどのＰＯＩに複数の出入り口Ｇ１〜Ｇ５が存在している場合を示している。
【００７０】
このような経路探索要求が端末装置２０から経路探索サーバ３０に要求されると、経路探索サーバ３０は先ず、同一探索ログ抽出手段３８が探索ログデータベース４０を参照して出発地を同一とする探索ログがあるかを調べ、同一探索ログがあればその経路履歴から各端末装置２０の消失点、復帰点を抽出する。この消失点、復帰点の位置が複数の出入り口Ａ１〜Ａ５の位置になる。次に、仮想ノード設定手段３９は各出入り口Ａ１〜Ａ５のそれぞれからリンクコスト「０」のリンクで接続される仮想ノードＰＮ１を設定する。
【００７１】
目的地側についても出発地に対する処理と同様にして、同一探索ログ抽出手段３８が探索ログデータベース４０を参照して目的地を同一とする探索ログがあるかを調べ、同一探索ログがある場合その経路履歴から各端末装置２０の消失点、復帰点を抽出する。この消失点、復帰点の位置が複数の出入り口Ｇ１〜Ｇ５の位置になる。次に、仮想ノード設定手段３９は各出入り口Ｇ１〜Ｇ５のそれぞれからリンクコスト「０」のリンクで接続される仮想ノードＰＮ２を設定する。
【００７２】
次いで、経路探索サーバ３０において経路探索手段３３は仮想ノードＰＮ１、ＰＮ２を探索用ネットワークデータベース３５に一時的に追加する。図７において、点線が探索用のネットワークを模式的に表し、仮想ノードＰＮ１、ＰＮ２が追加される。経路探索手段３３はこの探索用ネットワークデータベース３５を用いて仮想ノードＰＮ１から仮想ノードＰＮ２に至る最適経路を探索する。
【００７３】
この探索はダイクストラ法など、一般的な経路探索において用いられる手法で行うことができる。すなわち、実際に経路探索を行う範囲は実際の探索用ネットワーク上になるが、仮想ノードＰＮ１（出発地側）と仮想ノードＰＮ２（目的地側）を置くことにより、この間で求められた最適経路は出発地と目的地も同時に特定している点に特徴がある。
【００７４】
仮想ノードＰＮ１と各出入り口Ａ１〜Ａ５の間のリンクコストは全て「０」で等しく、仮想ノードＰＮ２と各出入り口Ｇ１〜Ｇ５の間のリンクコストは、全て「０」で等しいから、経路探索の結果、仮想ノードＰＮ１から仮想ノードＰＮ２に至る最短経路ＲＴ１が得られ、この最短経路ＲＴ１が経由する出発地側の出入り口Ａ５と、目的地側の出入り口Ｇ１がそれぞれ出発地側、目的地側の最適な出入り口となる。
【００７５】
次に、ある地点Ａを出発地または目的地とした経路探索の結果である探索ログから、地点Ａの出入り口の位置を特定する手順を詳細に説明する。図９は、図１１に示した地点（Ａショピングモール）の駐車場の出入り口ＩＯ１〜ＩＯ４と探索ログにおける現在位置履歴を示す図である。出入り口ＩＯ１から駐車場を出入りしたある端末装置２０の現在位置履歴における消失点または復帰点の位置Ｍ１は、駐車場において該端末装置２０が最後または最初に位置情報を取得した場所である。
【００７６】
消失点または復帰点の位置Ｍ１から道路Ｒ１までの経路履歴は端末装置２０の位置情報履歴（図中のＰ１、Ｐ２、Ｐ３により結ぶことができるから、この経路履歴から道路Ｒ１上の駐車場の出入り口ＩＯへの位置を特定することができる。経路探索ログは不特定多数であるから、それらの経路履歴から得られた出入り口ＩＯ１に対する道路Ｒ１上の複数の位置情報の重心位置を算出すれば、出入り口ＩＯ１に対する道路Ｒ１上の位置をほぼ特定することができる。
【００７７】
以上、説明した本発明のナビゲーションシステムの経路探索手順について、図１０に示すフローチャートを参照して説明する。ステップＳ１０の処理において経路探索サーバ３０はナビゲーション端末装置２０から経路探索条件を受信する。
【００７８】
経路探索サーバ３０は経路探索条件を受信すると、先ずステップＳ１１の処理において同一探索ログ抽出手段３８は探索ログデータベース４０を参照して出発地を同一とする探索ログがあるか調べる。同一探索ログがあれば同一探索ログ抽出手段３８はステップＳ１３の処理において、同一探索ログの経路履歴から各端末装置２０の消失点、復帰点を抽出する。この消失点、復帰点の位置が複数の出入り口Ａ１〜Ａ５の位置になる。そして仮想ノード設定手段３９は、各出入り口Ａ１〜Ａ５からのリンクコストがゼロの仮想ノードＰＮ１を設定する。
【００７９】
同一探索ログがなかった場合はステップＳ１４の処理において経路探索手段３３は端末装置２０が設定した出発地を出発地ノードとする。
【００８０】
次に経路探索サーバ３０は目的地側についてもステップＳ１５〜ステップＳ１８の処理においてステップＳ１１〜ステップＳ１３と同様の処理を行い目的地側の複数の出入り口Ｇ１〜Ｇ５の位置に基づいて仮想ノードＰＮ２を設定する。同一探索ログがなかった場合はステップＳ１７の処理において経路探索手段３３は端末装置２０が設定した目的地を目的地ノードとする。
【００８１】
次に，経路探索手段３３は、仮想ノードＰＮ１を出発地、仮想ノードＰＮ２を目的地とした経路探索を行いステップＳ２０の処理において経路案内手段３２は経路探索手段３３が探索した最適経路を案内経路として端末装置２０に配信して経路案内を行う。出発地側、目的地側とも同一探索ログがない場合、ステップＳ１４、ステップＳ１７で決定される出発地ノード、目的地ノードは端末装置２０で設定された出発地、目的地となるから、通常の経路探索が行われる。
【００８２】
ステップＳ１９の処理において経路探索手段３３により最適経路が探索されると経路探索サーバ３０は探索した案内経路のデータをステップＳ２０の処理において端末装置２０に配信して処理を終了する。案内経路のデータを受信した端末装置２０は、案内経路のデータを案内経路データ記憶手段２５に一時記憶し、表示手段２４に地図、案内経路等を表示する。
【００８３】
なお、出発地側または目的地側を同一とする探索ログがなく、あるいは出入り口の位置が抽出できず、ステップＳ１４またはステップＳ１７の処理において、出発地または目的地が出発地ノードまたは目的地ノードとして決定されている場合、ステップＳ１９の処理におけるノードは仮想ノードでなく出発地ノードまたは目的地ノードが用いられることは当然である。
【００８４】
また、同一探索ログ抽出手段３８が抽出する探索ログは、出発地または目的地における出入り口の位置を抽出するものであるから、出発地と目的地が同一である探索ログを抽出する必要はなく、端末装置２０が経路探索の条件として指定した出発地と同一の出発地または目的地を有する探索ログ、端末装置２０が経路探索の条件として指定した目的地と同一の出発地または目的地を有する探索ログを独立に抽出して、それぞれの探索ログの位置履歴からその消失点、復帰点を抽出すればよい。
【００８５】
以上説明した図１０の処理手順は端末装置２０から経路探索要求に対して、経路探索サーバ３０は全て同一探索ログを抽出する処理を行う例を示したが、本発明はこの手順に限ることなく、端末装置２０に通常の経路探索要求を行う探索要求モードと本発明による経路探索要求を行う同一探索ログ探索モードを備え、端末装置２０のユーザがモード指定をして経路探索サーバに経路探索を要求するように構成することもできる。
【００８６】
以上、詳細に説明したように本発明によれば、出発地または目的地がイベント会場や駐車場など比較的大きなエリアでかつその位置が緯度、経度によりピンポイントで示され、位置情報を持たない複数の出入り口がある場合にも、不特定多数の端末装置２０が同じ地点を出発地や目的地として探索した探索ログを抽出して出入り口の位置を抽出するから、最適経路となる出入り口を含む経路を案内できるようになる。
【図面の簡単な説明】
【００８７】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】本発明の実施例にかかるナビゲーションシステムの詳細な構成を示すブロック図である。
【図３】道路ネットワークのデータの概念を示す模式図である。
【図４】交通ネットワークのデータの概念を示す模式図である。
【図５】複数の出入り口を有するエリアを目的地とする経路探索の概念を示す模式図である。
【図６】位置情報を持たない複数の出入り口を有するエリアを目的地として仮想ノードを設定して最適経路を探索する概念を示す模式図である。
【図７】出発地側の駅に複数の出入り口が存在する場合の経路探索の概念を説明するための説明図である。
【図８】出発地側、目的地側の双方に複数の出入り口がある場合の経路探索の概念を示す模式図である。
【図９】探索ログから複数の出入り口を特定する処理の詳細を説明するための模式図である。
【図１０】本発明の実施例にかかるナビゲーションシステムにおける経路探索の手順を示すフローチャートである。
【図１１】出入り口を有する出発地または目的地と、その周辺の道路および道路上に設定されたノードの一例を示す図である。
【符号の説明】
【００８８】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２１・・・・制御手段
２２・・・・通信手段
２３・・・・測位手段（ＧＰＳ受信手段）
２４・・・・表示手段
２５・・・・案内経路データ記憶手段
２６・・・・配信要求編集手段
２７・・・・操作・入力手段
３０・・・・経路探索サーバ
３１・・・・制御手段
３２・・・・経路案内手段
３３・・・・経路探索手段
３４・・・・通信手段
３５・・・・探索用ネットワークデータベース
３６・・・・道路ネットワークデータ
３７・・・・交通ネットワークデータ
３８・・・・同一探索ログ抽出手段
３９・・・・仮想ノード設定手段
４０・・・・探索ログデータベース
４１・・・・ＰＯＩデータベース
５０・・・・ＰＯＩ情報提供サーバ
５１・・・・情報配信サーバ
【特許請求の範囲】
【請求項１】
探索用ネットワークデータを用いて出発地から目的地までの経路を探索するナビゲーションシステムにおいて、
前記ナビゲーションシステムは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とするナビゲーションシステム。
【請求項２】
前記各出入り口のそれぞれと仮想ノードを接続するリンクのリンクコストはゼロであることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記ナビゲーションシステムは、経路探索条件を送信する端末装置と、ネットワークを介して前記端末装置と接続される経路探索サーバとを備えて構成されることを特徴とする請求項１または請求項２に記載のナビゲーションシステム。
【請求項４】
ネットワークを介して経路探索条件を指定して経路探索要求を送信する端末装置と接続される経路探索サーバであって、
前記経路探索サーバは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とする経路探索サーバ。
【請求項５】
前記各出入り口のそれぞれと仮想ノードを接続するリンクのリンクコストはゼロであることを特徴とする請求項４に記載の経路探索サーバ。
【請求項６】
探索用ネットワークデータを用いて出発ノードから目的ノードまでの経路を探索する経路探索方法において、
前記ナビゲーションシステムは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段が、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出するステップと、前記仮想ノード設定手段が前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定するステップと、前記経路探索手段が前記仮想ノードを出発地または目的地として最適経路を探索して案内経路とするステップとからなることを特徴とする経路探索方法。
【請求項７】
前記仮想ノード設定手段が前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定するステップは、リンクコストの値を０とするステップを含むことを特徴とする請求項６に記載の経路探索方法。
【請求項８】
経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とする経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、通常の経路探索要求を行う探索要求モードと本発明による経路探索要求を行う同一探索ログ探索モードを備え、端末装置２０のユーザがモード指定をして経路探索サーバに経路探索を要求することを特徴とする端末装置。
【請求項１】
探索用ネットワークデータを用いて出発地から目的地までの経路を探索するナビゲーションシステムにおいて、
前記ナビゲーションシステムは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とするナビゲーションシステム。
【請求項２】
前記各出入り口のそれぞれと仮想ノードを接続するリンクのリンクコストはゼロであることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記ナビゲーションシステムは、経路探索条件を送信する端末装置と、ネットワークを介して前記端末装置と接続される経路探索サーバとを備えて構成されることを特徴とする請求項１または請求項２に記載のナビゲーションシステム。
【請求項４】
ネットワークを介して経路探索条件を指定して経路探索要求を送信する端末装置と接続される経路探索サーバであって、
前記経路探索サーバは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とする経路探索サーバ。
【請求項５】
前記各出入り口のそれぞれと仮想ノードを接続するリンクのリンクコストはゼロであることを特徴とする請求項４に記載の経路探索サーバ。
【請求項６】
探索用ネットワークデータを用いて出発ノードから目的ノードまでの経路を探索する経路探索方法において、
前記ナビゲーションシステムは、経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段が、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出するステップと、前記仮想ノード設定手段が前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定するステップと、前記経路探索手段が前記仮想ノードを出発地または目的地として最適経路を探索して案内経路とするステップとからなることを特徴とする経路探索方法。
【請求項７】
前記仮想ノード設定手段が前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定するステップは、リンクコストの値を０とするステップを含むことを特徴とする請求項６に記載の経路探索方法。
【請求項８】
経路探索して得た案内経路および案内経路上における位置履歴を含む経路探索ログを蓄積した探索ログデータベースと、同一探索ログ抽出手段と、仮想ノード設定手段と、経路探索手段と、を備え、
出発地、目的地を含む経路探索要求があった場合、前記同一探索ログ抽出手段は、前記探索ログデータベースを参照して前記出発地または目的地と同一の出発地または目的地を有する探索ログを抽出してその位置履歴から該出発地または目的地の出入り口の位置を抽出し、前記仮想ノード設定手段は前記各出入り口のそれぞれをリンクコストが等しいリンクで接続した位置情報を持たない仮想ノードを設定し、前記経路探索手段は前記仮想ノードを出発地または目的地として最適経路を探索し、案内経路とすることを特徴とする経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、通常の経路探索要求を行う探索要求モードと本発明による経路探索要求を行う同一探索ログ探索モードを備え、端末装置２０のユーザがモード指定をして経路探索サーバに経路探索を要求することを特徴とする端末装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００８−１９１１１５（Ｐ２００８−１９１１１５Ａ）
【公開日】平成２０年８月２１日（２００８．８．２１）
【国際特許分類】
【出願番号】特願２００７−２８６４９（Ｐ２００７−２８６４９）
【出願日】平成１９年２月８日（２００７．２．８）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
【公開日】平成２０年８月２１日（２００８．８．２１）
【国際特許分類】
【出願日】平成１９年２月８日（２００７．２．８）
【出願人】（５００１６８８１１）株式会社ナビタイムジャパン (410)
【Ｆターム（参考）】
[ Back to top ]