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