(57)【特許請求の範囲】
【請求項１】
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段と、前記経路探索手段が探索した推奨経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、当該エリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、前記推奨経路と前記比較経路を評価する経路評価手段と、を備え、
前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示することを特徴とするナビゲーションシステム。
【請求項２】
前記エリア決定手段は、前記表示手段の表示領域に表示された地図画像の各隅の地点の緯度および経度を算出して前記エリアを決定することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記エリア決定手段は、前記表示手段に表示された所定の大きさの単位地図、または、前記表示手段に表示された所定の大きさの単位地図と前記推奨経路の進行方向に隣接する所定数の単位地図とを前記エリアとして決定することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項４】
前記エリア決定手段は、前記表示手段の表示領域に表示された地図画像の各隅までの地図上の実距離を算出し、最大の実距離を半径とする円で囲まれるエリアを前記エリアとして決定することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項５】
前記エリア決定手段は、前記現在位置が、エリア決定手段が決定したエリアの境界の所定距離手前に到達した時、当該エリアに隣接したエリアを決定することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項６】
経路探索手段が探索した推奨経路を表示する表示手段を備えた端末装置とネットワークを介して接続され、前記端末装置から送信された出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段を備えた経路探索サーバにおいて、
前記端末装置は、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、推奨経路と比較経路を評価する経路評価手段と、を備え、前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示する端末装置であって、
前記経路探索サーバは、前記エリア決定手段が決定したエリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、を備え、前記比較経路探索手段が探索した比較経路を前記端末装置に送信することを特徴とする経路探索サーバ。
【請求項７】
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段を備えた経路探索サーバにネットワークを介して接続され、前記経路探索手段が探索した推奨経路を表示する表示手段を備えた端末装置において、
前記経路探索サーバは、前記端末装置が決定した所定の距離範囲のエリアに基づいて、当該エリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、を備え、前記比較経路探索手段が探索した比較経路を前記端末装置に送信する経路探索サーバであって、
前記端末装置は、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、前記推奨経路と前記比較経路を評価する経路評価手段と、を備え、
前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示することを特徴とする端末装置。
【請求項８】
前記エリア決定手段は、前記表示手段の表示領域に表示された地図画像の各隅の地点の緯度および経度を算出して前記エリアを決定することを特徴とする請求項７に記載の端末装置。
【請求項９】
前記エリア決定手段は、前記表示手段に表示された所定の大きさの単位地図、または、前記表示手段に表示された所定の大きさの単位地図と前記推奨経路の進行方向に隣接する所定数の単位地図とを前記エリアとして決定することを特徴とする請求項７に記載の端末装置。
【請求項１０】
前記エリア決定手段は、前記表示手段の表示領域に表示された地図画像の各隅までの地図上の実距離を算出し、最大の実距離を半径とする円で囲まれるエリアを前記エリアとして決定することを特徴とする請求項７に記載の端末装置。
【請求項１１】
前記エリア決定手段は、前記現在位置が、エリア決定手段が決定したエリアの境界の所定距離手前に到達した時、当該エリアに隣接したエリアを決定することを特徴とする請求項７に記載の端末装置。
【請求項１２】
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段と、前記経路探索手段が探索した推奨経路を表示する表示手段と、を備えたナビゲーションシステムにおける経路案内方法において、
前記ナビゲーションシステムは、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、当該エリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、前記推奨経路と前記比較経路を評価する経路評価手段と、を備え、
前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示するステップを有することを特徴とする経路案内方法。
【請求項１３】
経路探索手段が探索した推奨経路を表示する表示手段を備えた端末装置とネットワークを介して接続され、前記端末装置から送信された出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段を備えた経路探索サーバにおける経路案内方法において、
前記端末装置は、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、推奨経路と比較経路を評価する経路評価手段と、を備え、前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示する端末装置であって、
前記経路探索サーバは、前記エリア決定手段が決定したエリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、を備え、
前記エリア抽出手段が、前記エリア決定手段が決定したエリア内の経路探索用のネットワークデータを抽出するステップと、前記比較経路探索手段が、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とするステップと、前記比較経路探索手段が探索した比較経路を前記端末装置に送信するステップを有することを特徴とする経路案内方法。
【請求項１４】
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段を備えた経路探索サーバにネットワークを介して接続され、前記経路探索手段が探索した推奨経路を表示する表示手段を備えた端末装置における経路案内方法において、
前記経路探索サーバは、前記端末装置が決定した所定の距離範囲のエリアに基づいて、当該エリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、を備え、前記比較経路探索手段が探索した比較経路を前記端末装置に送信する経路探索サーバであって、
前記端末装置は、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、前記推奨経路と前記比較経路を評価する経路評価手段と、を備え、
前記エリア決定手段が、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定ステップと、前記経路評価手段が前記推奨経路と前記比較経路を評価するステップと、
前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示するステップを有することを特徴とする経路案内方法。
【請求項１５】
前記エリア決定ステップは、前記表示手段の表示領域に表示された地図画像の各隅の地点の緯度および経度を算出して前記エリアを決定する処理を含むことを特徴とする請求項１４に記載の経路案内方法。
【請求項１６】
前記エリア決定ステップは、前記表示手段に表示された所定の大きさの単位地図、または、前記表示手段に表示された所定の大きさの単位地図と前記推奨経路の進行方向に隣接する所定数の単位地図とを前記エリアとして決定する処理を含むことを特徴とする請求項１４に記載の経路案内方法。
【請求項１７】
前記エリア決定ステップは、前記表示手段の表示領域に表示された地図画像の各隅までの地図上の実距離を算出し、最大の実距離を半径とする円で囲まれるエリアを前記エリアとして決定することを特徴とする請求項１４に記載の経路案内方法。
【請求項１８】
前記エリア決定ステップは、前記現在位置が、エリア決定手段が決定したエリアの境界の所定距離手前に到達した時、当該エリアに隣接したエリアを決定する処理を含むことを特徴とする請求項１４に記載の経路案内方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所望の出発地から目的地までの経路を探索して案内するナビゲーションシステム、経路探索サーバおよび端末装置ならびに経路案内方法に関するものであり、特に、経路案内中の案内経路に対して、地図上にそれよりも有利な経路（道路）が認められる場合に、有利な経路が案内経路に該当しない理由を表示するようにしたナビゲーションシステム、経路探索サーバおよび端末装置ならびに経路案内方法に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られている。このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。
【０００４】
一般的なナビゲーション装置、通信型のナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００５】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００６】
リンクデータにはリンク長などのコストデータの他に該当する道路に関する種々の付帯情報が属性情報として付加されている。属性情報には、国道や高速道路などの道路種別や道路の幅員や傾斜などの道路構造などを示す情報の他、工事中、事故や災害による通行止め、一方通行など道路の現況に関する情報がある。また、表示の際の表示色の情報や、道路交通情報に基づく渋滞度などの情報もある。経路探索にあたっては属性情報も考慮される。例えば、通行止めのリンクに対してはリンクコストを無限大に調整することで案内経路として探索されないようにする。渋滞度の高いリンクについてはリンクコストを一定の係数を積算して通常よりも大きく調整することで渋滞のないリンクとの差が生ずるようにして最適経路として探索される確率を低くする。
【０００７】
このようなナビゲーションシステムにおいて経路探索条件としては少なくとも出発地と目的地を設定する。また、途中に立ち寄りたい経由地がある場合には、その地点を経由地として設定し、出発地から経由地を経由して目的地に至る最適経路や複数の候補経路を探索する。これらの地点を設定するためには、通常は、経路探索条件入力画面を表示し、地点の名称や住所（所在場所）、電話番号を入力する方法、表示画面に地図を表示して地図上の所望地点をカーソル選択して設定する方法などが採られる。
【０００８】
経路探索して得た出発地から目的地までの経路のうち、経路の累計コスト（距離または時間）が最小となる経路が最適な案内経路として決定され、案内経路データが作成される。案内経路データには、最適経路のデータの他に地図データ、ガイダンスデータが含まれ、案内経路データは必要に応じて案内データ記憶手段から読み出され表示手段に表示される。一般的には、ナビゲーション装置が有するＧＰＳ受信機を用いて測位したナビゲーション装置の現在位置を含む一定の縮尺、一定の範囲の地図に、案内経路と、ナビゲーション装置の現在位置を示すマークを重ね合わせ、該現在位置マークが表示画面の中心になるように表示する。
【０００９】
ＧＰＳ受信機を用いて測位した位置情報には誤差が含まれるため、現在位置が案内経路からずれている場合には現在位置を案内経路上に補正するルートマッチング処理や地図上の最も近い道路上に補正するマップマッチング処理が行われる。また、案内経路データに交差点などのガイダンスポイントが設定され、そのガイダンスポイントにおけるガイダンスとして音声ガイド（例えば、「この先、３００ｍ交差点です。左折して下さい」などの音声メッセージ）のデータが付加されている場合は、スピーカを介して音声メッセージを再生出力して利用者をガイドする。
【００１０】
ところで、表示画面に地図画像と地図画像上に案内経路を重ね合わせて表示して利用者に対して経路案内を実行している時に、その案内経路よりも有利な経路（道路）があることに気づく場合がある。図１２は、そのような場合を模式的に示す図であり、表示手段に表示された案内画像を模式的に示している。図１２においてＧＲＤ１（太線）は経路探索によって得られた案内経路（最適経路）であり、ノードｎ０で右折し、交差点ｎ１を左折、交差点ｎ２を左折してノードｎ３に至る経路が特定の色などで他の道路と識別できるように表示されている。車両の現在位置ＰＰがノードｎ０の手前の所定距離に到達すると図１２に示すように「次の交差点を右折して下さい」という案内が表示または音声により行われる。
【００１１】
これに対して、案内経路ＧＲＤ１のノードｎ０とノードｎ３との間を斜めにつなぐ道路（リンク）ＲＤ２があり、地図画像として表示されている場合、案内経路ＧＲＤ１に対して一見して道路ＲＤ２の距離が短いというように認識される。このようなケースが発生すると、利用者は経路探索が正しく行われているか疑問を持ってしまうことになる。この場合、道路ＲＤ２が最短経路にならなかった理由が存在する筈である。例えば、道路ＲＤが渋滞しており、案内経路ＧＲＤ１を経路とするほうが累計リンクコストが小さくなるようなケースである。また、道路ＲＤ２がノードｎ０から進入できない一方通行であったり、何らかの理由で一時的に通行止めになったりしている場合も同様である。
【００１２】
このような不安を解消するナビゲーションシステムとしては、例えば、下記の特許文献２（特開２００６−１８４１２６号公報）には、経路探索において得られた経路の特徴量を算出し探索経路間の比較を行う経路特徴量比較部と特徴量グラフ作成部を備え、ユーザが経路選択する際に前記特徴量のグラフを提示するようにした経路案内装置が開示されている。このように構成すれば、利用者は提示された複数の経路について、特徴（案内経路の平均カーブ曲率、急カーブ数、右左折割合や直進路割合など）を理解した上で経路案内を受ける案内経路を選択することができるようになる。
【００１３】
また、下記の特許文献３（特開２００６−２１５１８９号公報）には、道路交通情報に基づく渋滞状況を加味した最適経路と、通常の経路探索用のネットワークデータ（ノード、リンク、リンクコストなどのデータ）を用いて探索した比較経路とを探索し、両方の経路を表示し、その相違点を表示するようにしたナビゲーション装置が開示されている。このように構成すれば、案内経路よりも有利な経路があっても渋滞による影響である場合には利用者がその原因を理解することができる。
【００１４】
【特許文献１】特開２００１−１６５６８１号公報
【特許文献２】特開２００６−１８４１２６号公報
【特許文献３】特開２００６−２１５１８９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１５】
前述したように、表示画面に地図画像と地図画像上に推奨経路を重ね合わせて表示して利用者に対して経路案内を実行している時に、その推奨経路よりも有利な経路（道路）があることに気づく場合がある。すなわち、図１２に図示したような状態が生じた場合、上記特許文献３に開示されたナビゲーション装置によれば、推奨経路以外に有利な経路が存在しても、当該有利な経路が渋滞を原因として推奨経路として探索されなかった場合には、当該渋滞した経路が推奨経路にならなかった原因を利用者に示すことができる。
【００１６】
しかしながら上記特許文献３に開示されたナビゲーション装置では、渋滞以外の原因を考慮しておらず、工事中、一方通行、通行止めなどを含めた汎用的な対応ができないという問題点があった。また、上記特許文献３に開示されたナビゲーション装置の技術を応用してこのような種々の条件を加味した最適経路と比較経路を探索しようとする場合、出発地から目的地までの経路探索において比較経路の探索を行うため、経路探索処理の負荷が大きくなるという問題点が生ずる。
【００１７】
更に、出発地から目的地までの距離が大きい場合には、図１２に示すような箇所が多数存在する可能性があり、比較経路自体が単一でなく多数存在することになる。その場合は、車両が該当する交差点などに到達する度に推奨経路として他の有利な経路が探索されなかった原因を抽出して案内しなければならず、案内処理の負荷も増大するという問題点が生ずる。
【００１８】
本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、経路探索により得られた推奨経路を案内中に、現在位置周辺の限られたエリア内を対象に、そのエリア内の推奨経路を構成する各ノードを対象にリンク属性を除いた（無視した）最適経路探索を行い比較経路とし、推奨経路と比較経路が一致しない場合、推奨経路より比較経路が有利であると判断し、その比較経路のリンク属性を抽出して当該比較経路が推奨経路にならなかった原因を提示するようになせば、上記の問題点を解消し得ることに想到して本発明を完成するに至ったものである。
【００１９】
すなわち、本発明は、上記の問題点を解消することを課題とし、経路案内中の推奨経路に対して、地図上にそれよりも有利な経路（道路）が認められる場合に、有利な経路が推奨経路に該当しない理由を表示するようにしたナビゲーションシステム、経路探索サーバおよび端末装置ならびに経路案内方法を提供することを目的とするものである。
【課題を解決するための手段】
【００２０】
前記課題を解決するために、本願の請求項１にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段と、前記経路探索手段が探索した推奨経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、当該エリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、前記推奨経路と前記比較経路を評価する経路評価手段と、を備え、
前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示することを特徴とする。
【００２１】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記エリア決定手段は、前記表示手段の表示領域に表示された地図画像の各隅の地点の緯度および経度を算出して前記エリアを決定することを特徴とする。
【００２２】
本願の請求項３にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記エリア決定手段は、前記表示手段に表示された所定の大きさの単位地図、または、前記表示手段に表示された所定の大きさの単位地図と前記推奨経路の進行方向に隣接する所定数の単位地図とを前記エリアとして決定することを特徴とする。
【００２３】
本願の請求項４にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記エリア決定手段は、前記表示手段の表示領域に表示された地図画像の各隅までの地図上の実距離を算出し、最大の実距離を半径とする円で囲まれるエリアを前記エリアとして決定することを特徴とする。
【００２４】
本願の請求項５にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記エリア決定手段は、前記現在位置が、エリア決定手段が決定したエリアの境界の所定距離手前に到達した時、当該エリアに隣接したエリアを決定することを特徴とする。
【００２５】
また、本願の請求項６にかかる発明は、
経路探索手段が探索した推奨経路を表示する表示手段を備えた端末装置とネットワークを介して接続され、前記端末装置から送信された出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段を備えた経路探索サーバにおいて、
前記端末装置は、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、推奨経路と比較経路を評価する経路評価手段と、を備え、前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示する端末装置であって、
前記経路探索サーバは、前記エリア決定手段が決定したエリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、を備え、前記比較経路探索手段が探索した比較経路を前記端末装置に送信することを特徴とする。
【００２６】
また、本願の請求項７にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段を備えた経路探索サーバにネットワークを介して接続され、前記経路探索手段が探索した推奨経路を表示する表示手段を備えた端末装置において、
前記経路探索サーバは、前記端末装置が決定した所定の距離範囲のエリアに基づいて、当該エリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、を備え、前記比較経路探索手段が探索した比較経路を前記端末装置に送信する経路探索サーバであって、
前記端末装置は、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、前記推奨経路と前記比較経路を評価する経路評価手段と、を備え、
前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示することを特徴とする。
【００２７】
本願の請求項８にかかる発明は、請求項７にかかる端末装置において、前記エリア決定手段は、前記表示手段の表示領域に表示された地図画像の各隅の地点の緯度および経度を算出して前記エリアを決定することを特徴とする。
【００２８】
本願の請求項９にかかる発明は、請求項７にかかる端末装置において、前記エリア決定手段は、前記表示手段に表示された所定の大きさの単位地図、または、前記表示手段に表示された所定の大きさの単位地図と前記推奨経路の進行方向に隣接する所定数の単位地図とを前記エリアとして決定することを特徴とする。
【００２９】
本願の請求項１０にかかる発明は、請求項７にかかる端末装置において、前記エリア決定手段は、前記表示手段の表示領域に表示された地図画像の各隅までの地図上の実距離を算出し、最大の実距離を半径とする円で囲まれるエリアを前記エリアとして決定することを特徴とする。
【００３０】
本願の請求項１１にかかる発明は、請求項７にかかる端末装置において、前記エリア決定手段は、前記現在位置が、エリア決定手段が決定したエリアの境界の所定距離手前に到達した時、当該エリアに隣接したエリアを決定することを特徴とする。
【００３１】
また、本願の請求項１２にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段と、前記経路探索手段が探索した推奨経路を表示する表示手段と、を備えたナビゲーションシステムにおける経路案内方法において、
前記ナビゲーションシステムは、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、当該エリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、前記推奨経路と前記比較経路を評価する経路評価手段と、を備え、
前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示するステップを有することを特徴とする。
【００３２】
また、本願の請求項１３にかかる発明は、
経路探索手段が探索した推奨経路を表示する表示手段を備えた端末装置とネットワークを介して接続され、前記端末装置から送信された出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段を備えた経路探索サーバにおける経路案内方法において、
前記端末装置は、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、推奨経路と比較経路を評価する経路評価手段と、を備え、前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示する端末装置であって、
前記経路探索サーバは、前記エリア決定手段が決定したエリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、を備え、
前記エリア抽出手段が、前記エリア決定手段が決定したエリア内の経路探索用のネットワークデータを抽出するステップと、前記比較経路探索手段が、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とするステップと、前記比較経路探索手段が探索した比較経路を前記端末装置に送信するステップを有することを特徴とする。
【００３３】
また、本願の請求項１４にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータベースを参照して推奨経路を探索する経路探索手段を備えた経路探索サーバにネットワークを介して接続され、前記経路探索手段が探索した推奨経路を表示する表示手段を備えた端末装置における経路案内方法において、
前記経路探索サーバは、前記端末装置が決定した所定の距離範囲のエリアに基づいて、当該エリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、を備え、前記比較経路探索手段が探索した比較経路を前記端末装置に送信する経路探索サーバであって、
前記端末装置は、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、前記推奨経路と前記比較経路を評価する経路評価手段と、を備え、
前記エリア決定手段が、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定ステップと、前記経路評価手段が前記推奨経路と前記比較経路を評価するステップと、
前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示するステップを有することを特徴とする。
【００３４】
本願の請求項１５にかかる発明は、請求項１４にかかる経路案内方法において、前記エリア決定ステップは、前記表示手段の表示領域に表示された地図画像の各隅の地点の緯度および経度を算出して前記エリアを決定する処理を含むことを特徴とする。
【００３５】
本願の請求項１６にかかる発明は、請求項１４にかかる経路案内方法において、前記エリア決定ステップは、前記表示手段に表示された所定の大きさの単位地図、または、前記表示手段に表示された所定の大きさの単位地図と前記推奨経路の進行方向に隣接する所定数の単位地図とを前記エリアとして決定する処理を含むことを特徴とする。
【００３６】
本願の請求項１７にかかる発明は、請求項１４にかかる経路案内方法において、前記エリア決定ステップは、前記表示手段の表示領域に表示された地図画像の各隅までの地図上の実距離を算出し、最大の実距離を半径とする円で囲まれるエリアを前記エリアとして決定することを特徴とする。
【００３７】
本願の請求項１８にかかる発明は、請求項１４にかかる経路案内方法において、前記エリア決定ステップは、前記現在位置が、エリア決定手段が決定したエリアの境界の所定距離手前に到達した時、当該エリアに隣接したエリアを決定する処理を含むことを特徴とする。
【発明の効果】
【００３８】
請求項１にかかる発明においては、ナビゲーションシステムは、現在位置に応じて現在位置を含む所定の距離範囲のエリアを決定するエリア決定手段と、当該エリア内の経路探索用のネットワークデータを抽出するエリア抽出手段と、当該エリア内の推奨経路上の各ノードを起点とし、各リンクの属性情報を除いて最適経路を探索して比較経路とする比較経路探索手段と、前記推奨経路と前記比較経路を評価する経路評価手段と、を備え、前記経路評価手段において比較経路が推奨経路より有利であると評価した場合、比較経路のリンク属性に基づき、該比較経路が推奨経路にされなかった理由を推奨経路の案内画像とともに前記表示手段に表示する。
【００３９】
このような構成によれば、交差点などのガイダンスポイントにおいて経路案内中の推奨経路に対してより有利な道路（比較経路）があった場合に、その比較経路が推奨経路として探索されなかった理由が提示されるので、ナビゲーションシステムの経路探索のエラーであるという誤解を招くことがなくなる。また、推奨経路よりも有利な道路があっても、その道路が推奨経路として探索されなかった理由を知ることができ、経路探索に対して高い信頼度評価が得られるようになる。
【００４０】
請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、エリア決定手段は、前記表示手段の表示領域に表示された地図画像の各隅の地点の緯度および経度を算出して前記エリアを決定する。
【００４１】
請求項３にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、エリア決定手段は、表示手段に表示された所定の大きさの単位地図、または、前記表示手段に表示された所定の大きさの単位地図と前記推奨経路の進行方向に隣接する所定数の単位地図とを前記エリアとして決定する。
【００４２】
請求項４にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、エリア決定手段は、前記表示手段の表示領域に表示された地図画像の各隅までの地図上の実距離を算出し、最大の実距離を半径とする円で囲まれるエリアを前記エリアとして決定する。
【００４３】
このような構成によれば、出発地から目的地までを対象とすることなく、現在位置を含む一定の限られたエリアを対象として比較経路の探索が可能になり、経路探索および経路案内の処理を軽くすることができるようになる。
【００４４】
請求項５にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、エリア決定手段は、前記現在位置が、エリア決定手段が決定したエリアの境界の所定距離手前に到達した時、当該エリアに隣接したエリアを決定する。
【００４５】
このような構成によれば、推奨経路上を移動する端末装置に対して連続的に、交差点などのガイダンスポイントにおいて経路案内中の推奨経路に対してより有利な道路（比較経路）があった場合に、比較経路が推奨経路として探索されなかった理由を提示することができるようになる。
【００４６】
請求項６にかかる発明においては、請求項１にかかるナビゲーションシステムを構成する経路探索サーバを提供することができ、請求項７ないし請求項１１に発明においては、それぞれ請求項１ないし請求項５にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。また、請求項１２、請求項１３にかかる発明においては、それぞれ請求項１にかかるナビゲーションシステム、請求項６にかかる経路探索サーバにおける経路案内方法を提供することができ、請求１４ないし請求項１８にかかる発明においては、それぞれ請求項７ないし請求項１１にかかる端末装置における経路案内方法を提供することができるようになる。
【発明を実施するための最良の形態】
【００４７】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例】
【００４８】
図１は、本発明の実施例にかかるナビゲーションシステム１０の構成を示すシステム構成図である。図１に示すようにナビゲーションシステム１０は、ネットワーク１２を介して接続される端末装置２０と経路探索サーバ３０を備えて構成されている。このナビゲーションシステム１０は、各種カテゴリに属するＰＯＩ（Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ：興味対象場所）の所在地やサービス内容、広告などの詳細情報を提供するＰＯＩ情報配信サーバ５０、地図データ、交通路線データや運行時刻表データ、音楽や各種画像などのコンテンツ、その他の情報を提供する各種の情報配信サーバ５１などを備えて構成されている。
【００４９】
経路探索サーバ３０はＰＯＩ情報配信サーバ５０や他の情報配信サーバ５１からネットワーク１２を経由して必要なデータを取得して自身のデータベースに追加することができる。また、同様にしてＰＯＩ情報配信サーバ５０や他の情報配信サーバ５１に検索要求を送信して所望の検索結果を取得することもできる。
【００５０】
本発明にかかるナビゲーションシステム１０は、上記の構成に限られるものではなく、経路探索サーバ３０はナビゲーションサービス機能とともにＰＯＩ所在場所の地図を配信する地図配信サーバの機能を有していてもよい。また、端末装置２０も携帯電話を用いることができ、またＰＤＡや音楽プレイヤーや携帯ゲーム機などの携帯機器、あるいは、パーソナルコンピュータ（ＰＣ）であってもよい。また通信型のナビゲーションシステムに限らず、スタンドアロンタイプのナビゲーション装置にも適用可能である。
【００５１】
図１に示す経路探索サーバ３０は、地図データベース３４、経路探索用ネットワークデータベース３５を備え、端末装置２０から経路探索要求があると、経路探索用ネットワークデータベース３５を参照して経路探索する。そして経路探索の結果により得た最適経路や複数の候補経路（推奨経路）を端末装置２０に送信する一般的なナビゲーション機能を有している。また、経路探索サーバ３０は、ＰＯＩの所在地や電話番号、住所、営業時間などのＰＯＩ情報を蓄積したＰＯＩ情報データベース３６を備えている。
【００５２】
経路探索サーバ３０は、端末装置２０から所望の地点やＰＯＩを指定して地図データの取得要求があると、地図データベース３４を参照して該当する地図データを読み出して端末装置２０に配信する。端末装置２０が経路探索サーバ３０に経路探索を要求し、経路案内のサービスを受ける場合には、前述のように端末装置２０において所望の出発地や目的地を設定し、経路探索サーバ３０に経路探索要求を送信する。出発地と目的地との間に立ち寄りたい経由地がある場合は当該経由地も設定する。
【００５３】
これらの地点を設定する方法としては、例えば、経路探索条件入力画面を表示し、地点の名称や住所（所在場所）、電話番号を入力する方法、表示画面に地図を表示して地図上の所望地点をカーソル選択して設定する方法などが採られる。出発地、経由地、目的地は、一般的には特定の施設の場所や興味対象場所（ＰＯＩ：Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ）の場所を設定するが、施設やＰＯＩに最も近い道路上のリンクやノードの位置が経路探索上の当該施設やＰＯＩの場所として用いられることもある。
【００５４】
また、このナビゲーションシステム１０においては、経路探索条件入力画面を表示して地点を入力する方法の他に、所望エリアを指定したり、ＰＯＩ検索して注目ＰＯＩを選択したりしてそのＰＯＩが所在するエリアの地図を表示し、表示された地図上で所望の地点を指定して出発地や目的地、経由地を指定することができる。
【００５５】
端末装置２０は、経路探索サーバ３０から地図データや案内経路のデータを受信すると、表示手段に地図画像を表示し、案内経路の画像や端末装置２０の現在位置を地図画像上に重ね合わせて表示する。一般的には案内画像として地図画像、推奨経路の画像を表示する表示態様が採られるが、表示画面の小さい携帯機器を端末装置とする場合には、背景画像上に進行方向の案内をするための矢印を表示して案内画像とする態様もある。
【００５６】
経路の案内にあたっては、交差点や分岐点などのノードをガイダンスポイントとして設定し、そのノードにおける進行方向のガイダンス（右折や左折、直進など案内する音声ガイダンスなど）を設定する。ガイダンスは、例えば、交差点の２００ｍ手前の実行ポイントで出力される。この出力ポイントをガイダンス実行ポイントといい、これらのデータは推奨経路のデータとともに案内経路データとして編集され、経路探索サーバ３０から端末装置２０に送信される。
【００５７】
経路探索サーバ３０に複数の候補経路の探索を要求した場合には各候補経路の概要を端末装置２０に送り利用者が選択した候補経路を推奨経路として経路案内のための案内経路データを編集する。最適経路の探索の場合は当該最適経路が推奨経路になる。一般的なナビゲーションシステムにおける端末装置２０は、経路探索サーバ３０から推奨経路のデータやガイダンス関連のデータを含む案内経路データを受信し、所定の時間間隔で現在位置を測位してナビゲーションサービスを受けている間、地図や推奨経路、現在位置などの案内画像を表示し、設定されたガイダンス実行ポイントに到達すると、ガイダンスを出力する。
【００５８】
本発明にかかるナビゲーションシステムにおいては、経路探索サーバ３０から受信した案内経路データに基づいて、端末装置２０において推奨経路を案内経路として経路案内を実行している時、現在位置周辺の限られたエリア内を対象に、そのエリア内の推奨経路を構成する各ノードを対象にリンク属性を除いた（無視した）最適経路探索を行って比較経路とする。比較経路と推奨経路が一致しなければ比較経路が推奨経路よりも有利な経路であるから、比較経路のリンク属性を抽出して当該比較経路が推奨経路にならなかった原因を表示などにより提示する。
【００５９】
前記原因の表示は推奨経路と比較経路の分岐ノード（ガイダンスポイント）に対するガイダンス実行ポイントに端末装置２０が到達した時点であってよく、右折や左折のガイダンスとともに行われる。原因としては前述したように比較経路が進入禁止の一方通行路である場合や、工事中や自然災害による通行止めの場合や、上記特許文献３に示されるような渋滞している道路の場合などである。これらの原因は比較経路のリンクに付加されている属性情報を参照することにより判別することができる。
【００６０】
ナビゲーションシステムをこのような構成にすれば、交差点などのガイダンスポイントにおいて経路案内中の推奨経路に対してより有利な道路（比較経路）があった場合に、その比較経路が推奨経路として探索されなかった理由が提示されるので、ナビゲーションシステムの経路探索のエラーであるという誤解を招くことがなくなる。
【００６１】
以下、具体例に基づいて本発明を説明するが、その前に本発明にかかるナビゲーションシステムにおける経路探索の概念、ナビゲーションシステムの詳細な構成を説明する。図２は、図１のナビゲーションシステム１０の詳細な構成を示す図である。
【００６２】
端末装置２０は、ナビゲーションサービスを受けることができる端末であり、制御手段２０１、通信手段２１、ＧＰＳ受信手段２２、探索要求手段２３、受信データ記憶手段２４、経路評価手段２５、エリア決定手段２６、表示手段２７、表示制御手段２８、操作入力手段２９を備えて構成されている。
【００６３】
一方、経路探索サーバ３０は、制御手段３０１、通信手段３１、エリア抽出手段３２、比較経路探索手段３３、地図データベース３４、経路探索用ネットワークデータベース３５、ＰＯＩ情報データベース３６、地図データ配信手段３７、探索要求記憶手段３８、経路探索手段３９を備えて構成されている。
【００６４】
端末装置２０において、制御手段２０１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段２１はネットワーク１２を介して経路探索サーバ３０などと通信データを送受信するための通信インターフェースである。
【００６５】
ＧＰＳ受信手段２２はＧＰＳ衛星からの信号を受信して現在位置を緯度・経度で算出する。操作入力手段２９は、キー、ダイヤル等からなり、端末装置２０を操作するための入力を行い、また、出発地、目的地などの経路探索条件の入力機能としても用いられる。表示手段２７は液晶表示パネル等からなり、経路探索サーバ３０から配信（送信）された推奨経路や地図の表示に使用されるものである。また、表示手段２７はメニュー画面を表示し、操作入力手段２９を用いてメニュー画面から所望の項目を選択することにより端末装置２０を操作するための入力手段としても機能する。
【００６６】
表示手段２７に表示されるメニュー画面や操作入力手段２９を用いて、出発地や目的地、必要に応じて経由地を含む経路探索条件が設定されると、探索要求手段２３は経路探索要求を経路探索サーバ３０に送信する。
【００６７】
経路探索サーバ３０から端末装置２０に送信されるガイダンス関連のデータや推奨経路のデータを含む案内経路データは地図データとともに受信データ記憶手段２４に記憶され、受信データ記憶手段２４に記憶された推奨経路データ、ガイダンス関連のデータや地図データは、必要に応じて読み出され、表示手段２７に表示される。
【００６８】
端末装置２０において、エリア決定手段２６は端末装置２０の現在位置に基づいて比較経路探索のためのエリアを決定する。エリアは端末装置２０の現在位置に基づいて表示手段に表示される単位地図（所定の緯度、経度範囲のエリア）、表示範囲、現在位置を中心とした所定の距離範囲などの何れかにより決定する。
【００６９】
エリア決定手段２６が決定したエリア情報は、経路探索サーバ３０に送られ、経路探索サーバ３０は後述するエリア抽出手段を用いてエリア内の推奨経路上の分岐ノードを抽出し、比較経路探索手段が当該ノードから分岐するリンクを、リンク属性を除いて（無視して）最適経路探索を行う。推奨経路と異なる最適経路が比較経路として探索された場合、推奨経路より比較経路が有利な経路であると判断して比較経路を得る。そして比較経路のデータを端末装置２０に送信する。
【００７０】
端末装置２０は経路探索サーバ３０から比較経路のデータを受信すると、経路評価手段２５は経路探索サーバ３０から送信された比較経路の属性情報を参照して推奨経路にならなかった理由を抽出する。表示制御手段２８は推奨経路と比較経路の分岐ノードに対するガイダンス実行ポイントに端末装置２０が到達すると、推奨経路におけるガイダンスとともに比較経路が推奨経路として探索されなかった理由を表示手段２７に表示する制御を行う。
【００７１】
一方、経路探索サーバ３０は、経路探索用ネットワークデータベース３５に自動車による移動経路を探索するための道路ネットワークデータを蓄積している。また、経路探索サーバ３０が徒歩や公共交通機関を利用した経路を探索して端末装置２０に案内する機能を有する場合、経路探索用ネットワークデータベース３５には更に、徒歩専用のネットワークデータ、交通機関の運行時刻表データに基づく交通ネットワークデータなども蓄積しておく。本発明は交通機関を用いた経路案内にも同様に適用することができる。
【００７２】
制御手段３０１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３１、ネットワーク１２を介して端末装置２０と通信するためのインターフェースである。
【００７３】
経路探索手段３９は、端末装置２０からの経路探索条件に基づいて経路探索用ネットワークデータベース３５を参照して出発地から目的地までの最適経路を探索する。経路探索サーバ３０は、経路探索手段３９が探索した最適経路や候補経路のうち端末装置２０を案内する推奨経路のデータや前述したガイダンス関連のデータを編集して案内経路データとし、これを端末装置２０に配信する。通信手段３１は、端末装置２０からの各種要求を受信し、あるいは、端末装置２０に各種情報を配信する。
【００７４】
経路探索手段３９による経路探索は次のように行う。例えば、道路が図３に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
すなわち、図３において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図３では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００７５】
このような道路ネットワークのデータを探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図３において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００７６】
図３ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００７７】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図４に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図４において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図４では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００７８】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図４に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【００７９】
図４に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【００８０】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
例えば、図４において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【００８１】
図５は、地図データベースに蓄積される地図データを示す図である。通信型のナビゲーションシステムにおいて、案内経路やガイダンスポイントおよびガイダンスデータ（音声データ等）の配信方法は種々の形態をとり得るが、例えば、経路探索サーバ３０が端末装置２０から送信された経路探索条件に従って案内経路を探索し、前述したようなガイダンスポイントなどを設定した案内経路データを作成し、出発地から目的地までの案内経路を一括して端末装置２０に送信し、地図データは端末装置２０からの地図要求に基づいて端末装置２０に送信するように構成している。
【００８２】
すなわち、経路探索サーバ３０から端末装置２０に経路データと地図データを別々に配信し、端末装置２０は地図表示に必要な地図データに不足が生じた場合に、経路データから当該経路を含む単位地図の配信を経路探索サーバ３０に要求することができる。通常、地図データは現在位置を含むメッシュ状の単位地図データを中心とする上下左右、斜め方向に隣接する９つのメッシュ状単位の地図データを端末装置２０に配信する。
【００８３】
地図データベース３４に蓄積される地図データは図５に示すように所定の緯度・経度範囲で区分された単位地図データから構成されている。すなわち、地図データは図５に示すように所定の緯度、経度単位で地図エリアが分けられ、メッシュ状の単位地図データＭ１１〜Ｍ３３のように構成されている。端末装置２０に配信される場合は、端末装置２０の現在位置ＰＰを含む単位地図データＭ２２を中心にして、その上下方向、左右方向、斜め方向に隣接する単位地図データＭ２１、Ｍ２３、Ｍ１２、Ｍ３２、Ｍ１１、Ｍ１３、Ｍ３１、Ｍ３３の合計９つの単位地図が配信される。
【００８４】
端末装置２０が移動して地図データが不足する場合は、端末装置２０の移動方向を判別して経路探索サーバ３０は不足分の単位地図データを配信する。端末装置２０が特定の地点やＰＯＩの位置を指定して地図データの配信要求をした場合も同様である。案内経路のデータはこのベクトル地図データとともに端末装置２０に配信される。端末装置２０は、経路探索サーバ３０からこのようにして地図データおよび案内経路のデータを受信して、前述した条件に従って案内画像を表示手段２７に表示する。
【００８５】
図６は、本発明の実施例にかかる端末装置２０としての携帯電話の外観を示す図である。端末装置２０が携帯電話機である場合、図６に示すように、表示手段２７と操作入力手段２９とを備えている。操作入力手段２９の各キーにはスクロールキーＳＫ（ランチャーキー）が設けられ、特定の数字キー等にクリアキー、表示モード切り替えキーが割り当てられている。
【００８６】
表示手段２７には第１の地図表示画面２６１と第２の地図表示画面２６２が示されており、第１の地図表示画面２６１にはカーソルＣがスクロール操作の開始点とカーソルの現在位置が直線Ｌで結ばれてカーソル移動状態が視認できるように表示されている。第２の地図表示画面２６２には第１の地図表示画面２６１に表示されている地図の表示範囲を示す表示枠２６３が表示されている。
【００８７】
スクロールキーＳＫが操作されると、自動的にスクロールモードに切り替わり表示画面にカーソルＣが表示される。この場合は、スクロールキーＳＫが所定時間操作されない状態になるまで、あるいはクリアキーが操作されるまでスクロールモードが継続される。カーソルＣの初期表示位置は画面の中央である。
【００８８】
経路探索サーバ３０は、前述したように端末装置２０からエリア決定手段２６が決定したエリアの情報を受信すると、エリア抽出手段３２は経路探索用ネットワークデータベース３５から該当するエリア内のネットワークデータ（ノードやリンク）を抽出してリンクデータ中の属性情報を無効化する。そして、端末装置２０に対して経路案内中の推奨経路と、エリア抽出手段３２が抽出したネットワークデータとから、推奨経路上の分岐ノードを抽出する。
【００８９】
比較経路探索手段３３はエリア抽出手段３２が抽出した分岐ノード（推奨経路上のノード）を起点として、エリア抽出手段が抽出し、リンクの属性情報を無効化したネットワークデータを用いて最適経路を探索して比較経路とする。比較経路探索手段３３は、推奨経路と比較経路を比較し、両者が一致しない場合は、比較経路のデータを端末装置２０に送信する。この比較経路探索においては、エリア決定手段２６が決定したエリアの境界（端部）における推奨経路上のノードまたはリンクを探索の終点とする。すなわち、比較経路探索手段３３は推奨経路上の分岐ノードを起点（出発地）とし、後述する図８ないし図１０に示す方法で決定したエリア境界（端部）における推奨経路上のノードまたはリンクを終点（目的地）とし、リンク属性情報を無視して最適経路を探索する。エリア境界がリンク途中である場合は、そのリンクの両端のノードの何れかを終点（目的地）とする。
【００９０】
端末装置２０は経路探索サーバ３０から比較経路のデータを受信すると、経路評価手段２５は推奨経路と比較経路とを比較する。比較経路探索手段３３により最適経路として探索された比較経路が推奨経路と一致しない場合は、推奨経路に対して比較経路のほうが有利（距離や時間コストが小さい）であると判別できる。なぜなら、比較経路はリンク属性を無効にして最適経路を探索した結果だからである。推奨経路と比較経路が一致すれば推奨経路よりも有利な経路は存在しないことになる。リンクの属性情報を有効にして探索した経路と無効にして探索した経路が一致するということは、推奨経路がリンクの属性情報による影響を受けていないと判別できるからである。なお、この判別は経路探索サーバ３０に経路評価手段２５を設けて行うこともできる。
【００９１】
経路評価手段２５が比較経路と推奨経路が異なり、推奨経路に対して比較経路がより有利であると判別すると、その比較経路のリンクに付加された属性情報を抽出する。そして推奨経路上でその比較経路が分岐する分岐ノード（ガイダンスポイント）を特定し、端末装置２０がそのガイダンスポイントに応じたガイダンス実行ポイントに到達すると、表示制御手段２８は地図、推奨経路、自車位置（現在位置）およびガイダンス（右折や左折、直進の案内）とともに比較経路が推奨経路として案内されなかった理由として前記抽出したリンクの属性情報に応じた案内を表示する。
【００９２】
図７は、本実施例にかかるナビゲーションシステム１０における案内画像の構成を模式的に示す図である。図７の案内画像は、図１２に相当する案内画像である。図７において図１２に相当する要素は同じ参照符号を付しである。経路案内中の推奨経路はＧＲＤ１であり、分岐ノードはｎ０を起点として比較経路探索手段３３が各リンクの属性情報を除いて最適経路探索をすると、ノードｎ３までの道路ＲＤ２が探索される。道路ＲＤ２は推奨経路ＧＲＤ１とは一致しないので比較経路とされる。
【００９３】
この比較経路ＲＤ２は、実際には車両通行禁止路であり、分岐ノードｎ０からのリンクに付加された属性情報には侵入禁止または通行禁止の情報が記録されており、通常の経路探索では探索対象とならないものである。端末装置２０の現在位置ＰＰ（自車位置）が分岐ノードｎ０（ガイダンスポイント）手前のガイダンス実行ポイントに到達すると、表示制御手段２８はそのガイダンスボイントに設定された右折のガイダンス（案内）を表示するとともに、比較経路ＲＤ２が進入禁止路であり、「次の交差点、右斜め方向の道路が近道ですが、車両通行禁止区間のため進入できません」のように推奨経路にならなかった理由を表示する。
【００９４】
比較経路が存在する各分岐ノードに到達するごとに、図７に示すような案内画像を表示することで、端末装置２０の利用者は推奨経路よりも有利な道路があっても、その道路が推奨経路として探索されなかった理由を知ることができ、経路探索に対して高い信頼度評価が得られるようになる。
【００９５】
また、比較経路探索手段３３における比較経路の探索にあたっては、出発地から目的地までの全体を対象に最適経路探索をする処理でなく、限られたエリアに限定した最適経路探索を行うため、経路探索サーバ３０における経路探索処理の負荷を軽くすることができる。また、比較経路の存在する分岐ノードもエリア内の限られた数のノードであるから、案内画像を表示する経路案内処理の負荷も軽くすることができる。
【００９６】
端末装置の現在位置に基づいて周囲の限られたエリアを決定する手順には、図８ないし図１０に例示するように、いくつかの方法を採ることができる。図８は、現在位置に基づいて一定のエリアを決定する手順の一例を模式的に示す図である。表示手段２７に表示される地図画像は、図８に示すように現在位置を含む一定の範囲をエリアとする画像である。エリア決定手段２６は表示手段２７の表示領域２６１（表示枠）に表示された地図画像の４隅の地点の緯度、経度を算出して、各点で囲まれるエリアを決定する。４隅の緯度、経度のデータはエリア決定手段２６が決定したエリアの情報として経路探索サーバ３０に送られる。
【００９７】
図９は、現在位置に基づいて一定のエリアを決定する手順の他の一例を模式的に示す図である。端末装置２０に送られる地図データは図５を用いて説明した通りである。従って、現在位置を含む単位地図（地図メッシュ）をエリア決定の単位とすることができる。端末装置２０には現在位置を含む単位地図ｍ１１を中心に９枚の単位地図が送られているから、図９に示すように、表示手段２７に表示されている現在位置を含む単位地図ｍ１１をエリアとして決定する。エリアを広く決定したい場合は、現在位置を含む単位地図ｍ１１と、推奨経路の進行方向に隣接して連続している次の単位地図ｍ１２とを合わせてエリアとして決定することができる。連続する単位地図を複数選択してエリアを決定してもよい。
【００９８】
図１０は、現在位置に基づいて一定のエリアを決定する手順の更に他の一例を模式的に示す図である。図８に示す例では表示手段２７に表示された地図画像の４隅を算出する例を示したが、図１０は現在位置ＰＰから地図画像の４隅まで（画面枠の４隅まで）の実距離ｒを算出してその最大距離を半径とした円ＣＲの内部をエリアとして決定する例を示している。これにより推奨経路の進行方向がどの方向であっても一定の範囲のエリアを決定することができる。
【００９９】
なお、端末装置２０の現在位置が上記の何れかの方法により決定したエリアを超える前、例えば、エリアの境界の手前２００ｍ手前になったら、エリア決定手段２６は、端末装置２０の進行方向に連続するエリアを決定し、経路探索サーバ３０に送信して、予め次のエリアにおける比較経路探索を行わせれば、連続的に本発明の経路案内を継続することができる。
【０１００】
次に、以上詳細に説明した本発明の実施例にかかるナビゲーションシステム１０における経路案内の手順を説明する。図１１はナビゲーションシステム１０における経路案内の手順を示すフローチャートである。ここでは、端末装置２０から経路探索サーバ３０に経路探索要求を送信し、経路探索サーバ３０による経路探索が終了し、端末装置２０においては、経路探索サーバ３０から受信した案内経路データに基づいて経路案内が開始されているものとする。
【０１０１】
端末装置２０はステップＳ１０１の処理においてＧＰＳ受信手段２２により現在位置を測位する。ＧＰＳ受信手段２２による現在位置の測位は、一般的なナビゲーションシステムと同様に所定の時間間隔で行われる。現在位置が測位されると、ステップＳ１０２の処理において、エリア決定手段２６は図８ないし図１０に示した方法の何れかに従って所定のエリアを決定する。
【０１０２】
端末装置２０は、ステップＳ１０３の処理においてエリア情報を経路探索サーバ３０に送信し、経路探索サーバ３０がエリア情報を受信すると、エリア抽出手段３２はステップＳ１０４の処理においてエリア内に含まれる道路ネットワーク等のデータを抽出し、推奨経路上の分岐ノードを抽出する。
【０１０３】
次に、比較経路探索手段３３は、エリア抽出手段３２が抽出した分岐ノードを起点としてネットワークデータのリンクに付加された属性情報を無効にして最適経路探索を行う。そして探索した最適経路が推奨経路と一致すれば比較経路なしとし、一致しなければ最適経路を比較経路とする（ステップＳ１０５）。経路探索サーバ３０はステップＳ１０６おいて比較経路のデータを端末装置２０に送信する。
【０１０４】
端末装置２０は、経路探索サーバ３０から比較経路のデータを受信すると、現在位置が比較経路の存在する推奨経路上の分岐ノードに応じたガイダンス実行ポイントに到達したかが判別される。ガイダンス実行ポイントでなければステップＳ１０７の処理を繰り返す。現在位置がガイダンス実行ポイントに到達したと判別されると、経路評価手段２５は比較経路を評価し、比較経路のリンクの属性情報に基づいて比較経路が推奨経路にならなかった原因を抽出する。
【０１０５】
表示手段２８は、ステップＳ１０８の処理において、案内経路画像、ガイダンスとともに、比較経路が推奨経路にならなかった理由を表示する（図７参照）。そしてステップＳ１０９の処理において、端末装置２０は現在位置がステップＳ１０２で決定したエリアを超えたか否かを判別する。エリアを超えていたらステップＳ１０１の測位処理に戻る。
【０１０６】
エリアを超えていなければ、ステップＳ１１０の処理において、目的地に到達したか否かを判別する。目的地に到達していなければ、ステップＳ１０７ガイダンスポイント判別の処理に戻り、目的地に到達していれば経路案内の処理を終了する。
【０１０７】
以上、詳細に説明したように本発明によれば、交差点などのガイダンスポイントにおいて経路案内中の推奨経路に対してより有利な道路（比較経路）があった場合に、その比較経路が推奨経路として探索されなかった理由が提示されるので、ナビゲーションシステムの経路探索のエラーであるという誤解を招くことがなくなる。また、推奨経路よりも有利な道路があっても、その道路が推奨経路として探索されなかった理由を知ることができ、経路探索に対して高い信頼度評価が得られるようになる。
【図面の簡単な説明】
【０１０８】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】本発明の実施例にかかるナビゲーションシステムの詳細な構成を示すブロック図である。
【図３】道路ネットワークのデータの概念を示す模式図である。
【図４】交通ネットワークのデータの概念を示す模式図である。
【図５】地図データベースに蓄積される地図データを示す図である。
【図６】本発明の実施例にかかる端末装置としての携帯電話機の外観を示す図である。
【図７】本発明の実施例にかかるナビゲーションシステムにおける経路案内の表示画像の構成を模式的に示す図である。
【図８】現在位置に基づいて一定のエリアを決定する手順の一例を模式的に示す図である。
【図９】現在位置に基づいて一定のエリアを決定する手順の他の一例を模式的に示す図である。
【図１０】現在位置に基づいて一定のエリアを決定する手順の更に他の一例を模式的に示す図である。
【図１１】本発明の実施例にかかるナビゲーションシステムにおける経路案内の手順を示すフローチャートである。
【図１２】従来のナビゲーション装置における経路案内の案内画像の表示例を模式的に示す図である。
【符号の説明】
【０１０９】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２０１・・・制御手段
２１・・・・通信手段
２２・・・・ＧＰＳ受信手段
２３・・・・探索要求手段
２４・・・・受信データ記憶手段
２５・・・・経路評価手段
２６・・・・エリア決定手段
２７・・・・表示手段
２８・・・・表示制御手段
２９・・・・操作入力手段
３０・・・・経路探索サーバ
３０１・・・制御手段
３１・・・・通信手段
３２・・・・エリア抽出手段
３３・・・・比較経路探索手段
３４・・・・地図データベース
３５・・・・経路探索用ネットワークデータベース
３６・・・・ＰＯＩ情報データベース
３７・・・・地図データ配信手段
３８・・・・探索要求記憶手段
３９・・・・経路探索手段
【図１】
0004571169.tif 000002
【図２】
0004571169.tif 000003
【図３】
0004571169.tif 000004
【図４】
0004571169.tif 000005
【図５】
0004571169.tif 000006
【図６】
0004571169.tif 000007
【図７】
0004571169.tif 000008
【図８】
0004571169.tif 000009
【図９】
0004571169.tif 000010
【図１０】
0004571169.tif 000011
【図１１】
0004571169.tif 000012
【図１２】
0004571169.tif 000013