(57)【特許請求の範囲】
【請求項１】
地図に関する情報であって、地図が示す道路に関する情報である道路情報を有する地図情報が格納される地図情報格納部と、
前記地図情報が示す各道路についての、周辺の建物に関する情報であって、個々の建物が属する一以上のカテゴリーを示す情報を含む情報である建物関連情報が格納される建物関連情報格納部と、
出発地を示す情報である出発地情報と、目的地を示す情報である目的地情報を受け付ける受付部と、
建物についての条件であって、建物のカテゴリーを示す条件である建物条件を受け付ける条件受付部と、
前記道路情報と建物関連情報と建物条件とを用いて、周辺に前記建物条件を満たす建物が多い経路が探索されやすくなるようにして、前記出発地情報が示す出発地から、前記目的地情報が示す目的地までの経路を探索する経路探索部と、
前記経路探索部の探索結果に応じた出力を行う出力部とを備え、
建物の利用時間が、建物のカテゴリーと対応づけて格納される利用時間格納部と、
目的地に到着するまでの予定時間を受け付ける予定時間受付部を更に備え、
前記道路情報は、各道路の移動に要する時間である移動時間を含んでおり、
前記経路探索部は、経路に含まれる道路の移動時間と、当該道路に対応する前記建物条件を満たす建物の利用時間とを用いて、予定時間受付部が受け付けた予定時間以内の経路を探索し、
前記経路探索部は、前記建物条件を満たす建物の利用時間として、当該建物条件が示す建物のカテゴリーと対応づけて前記利用時間格納部に格納されている利用時間を取得し、
前記経路探索部は、前記建物条件を満たす建物のうちの、前記建物条件が示す建物のカテゴリーについて指定された上限までの数の建物についての利用時間の合計を、前記建物条件を満たす建物の利用時間として取得するナビゲーション装置。
【請求項２】
前記建物関連情報格納部に格納されている建物関連情報は、前記地図情報が示す各道路についての、当該道路周辺のカテゴリーが店舗である建物に関する情報を含んでおり、
前記条件受付部が受け付ける前記建物条件は、カテゴリーが店舗である建物を指定する条件であり、
前記経路探索部は、カテゴリーが店舗である建物数の多い経路が探索されやすくなるようにして経路を探索する請求項１記載のナビゲーション装置。
【請求項３】
前記建物関連情報格納部に格納されている建物関連情報は、前記地図情報が示す各道路についての、当該道路周辺のカテゴリーがレストランである建物に関する情報を含んでおり、
前記条件受付部が受け付ける前記建物条件は、カテゴリーがレストランである建物を指定する条件であり、
前記経路探索部は、カテゴリーがレストランである建物数の多い経路が探索されやすくなるようにして経路を探索する請求項１記載のナビゲーション装置。
【請求項４】
前記建物関連情報格納部に格納されている建物関連情報は、前記地図情報が示す各道路についての、当該道路周辺のカテゴリーがショッピングである建物に関する情報を含んでおり、
前記条件受付部が受け付ける前記建物条件は、カテゴリーがショッピングである建物を指定する条件であり、
前記経路探索部は、カテゴリーがショッピングである建物数の多い経路が探索されやすくなるようにして経路を探索する請求項１記載のナビゲーション装置。
【請求項５】
地図に関する情報であって、地図が示す道路に関する情報である道路情報を有する地図情報が格納される地図情報格納部と、前記地図情報が示す各道路についての、周辺の建物に関する情報であって、個々の建物が属する一以上のカテゴリーを示す情報を含む情報である建物関連情報が格納される建物関連情報格納部と、受付部と、条件受付部と、経路探索部と、出力部と、建物の利用時間が、建物のカテゴリーと対応づけて格納される利用時間格納部と、予定時間受付部とを用いて行われるナビゲーション方法であって、
前記受付部が、出発地を示す情報である出発地情報と、目的地を示す情報である目的地情報を受け付ける受付ステップと、
前記条件受付部が、建物についての条件であって、建物のカテゴリーを示す条件である建物条件を受け付ける条件受付ステップと、
前記経路探索部が、前記道路情報と建物関連情報と建物条件とを用いて、周辺に前記建物条件を満たす建物が多い経路が探索されやすくなるようにして、前記出発地情報が示す出発地から、前記目的地情報が示す目的地までの経路を探索する経路探索ステップと、
前記出力部が、前記経路探索ステップによる探索結果に応じた出力を行う出力ステップとを備え、
前記予定時間受付部が、目的地に到着するまでの予定時間を受け付ける予定時間受付ステップを更に備え、
前記道路情報は、各道路の移動に要する時間である移動時間を含んでおり、
前記経路探索ステップは、経路に含まれる道路の移動時間と、当該道路に対応する前記建物条件を満たす建物の利用時間とを用いて、予定時間受付ステップで受け付けた予定時間以内の経路を探索し、
前記経路探索ステップは、前記建物条件を満たす建物の利用時間として、当該建物条件が示す建物のカテゴリーと対応づけて前記利用時間格納部に格納されている利用時間を取得し、
前記経路探索ステップは、前記建物条件を満たす建物のうちの、前記建物条件が示す建物のカテゴリーについて指定された上限までの数の建物についての利用時間の合計を、前記建物条件を満たす建物の利用時間として取得するナビゲーション方法。
【請求項６】
地図に関する情報であって、地図が示す道路に関する情報である道路情報を有する地図情報が格納される地図情報格納部と、前記地図情報が示す各道路についての、周辺の建物に関する情報であって、個々の建物が属する一以上のカテゴリーを示す情報を含む情報である建物関連情報が格納される建物関連情報格納部と、建物の利用時間が、建物のカテゴリーと対応づけて格納される利用時間格納部と、にアクセス可能なコンピュータを、
出発地を示す情報である出発地情報と、目的地を示す情報である目的地情報を受け付ける受付部と、
建物についての条件であって、建物のカテゴリーを示す条件である建物条件を受け付ける条件受付部と、
前記道路情報と建物関連情報と建物条件とを用いて、周辺に前記建物条件を満たす建物が多い経路が探索されやすくなるようにして、前記出発地情報が示す出発地から、前記目的地情報が示す目的地までの経路を探索する経路探索部と、
前記経路探索部の探索結果に応じた出力を行う出力部として機能させ、
目的地に到着するまでの予定時間を受け付ける予定時間受付部として更に機能させ、
前記道路情報は、各道路の移動に要する時間である移動時間を含んでおり、
前記経路探索部は、経路に含まれる道路の移動時間と、当該道路に対応する前記建物条件を満たす建物の利用時間とを用いて、予定時間受付部が受け付けた予定時間以内の経路を探索し、
前記経路探索部は、前記建物条件を満たす建物の利用時間として、当該建物条件が示す建物のカテゴリーと対応づけて前記利用時間格納部に格納されている利用時間を取得し、
前記経路探索部は、前記建物条件を満たす建物のうちの、前記建物条件が示す建物のカテゴリーについて指定された上限までの数の建物についての利用時間の合計を、前記建物条件を満たす建物の利用時間として取得するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路を探索するナビゲーション装置等に関するものである。
【背景技術】
【０００２】
従来、ダイクストラ法(Dijkstra's Algorithm)と呼ばれる最短経路を決定するアルゴリズムがあった（例えば、非特許文献１参照）。ダイクストラ法は、始点から放射状に距離の短い順に距離を計算しながら最短ルートをチェックしていく方法である。また、ダイクストラ法は、目的地点へたどり着いた時点でその経路が最短ルートとなるアルゴリズムである。さらに、ダイクストラ法において、必要なメモリ量と処理時間が、リンクやノードの数に比例して増加する。なお、ここでのノードとは、地図上の地点のことである。リンクとは、ノードとノードを接続する線等である。
【０００３】
また、従来、Ａ＊アルゴリズムと呼ばれる最短経路を決定するアルゴリズムがあった（例えば、非特許文献２参照）。Ａ＊アルゴリズムは、各頂点ｎからゴールまでの距離の推定値ｈ＊（ｎ）を知っていた場合に対して、最短経路問題を効率的に解くアルゴリズムである。Ａ＊アルゴリズムは、ダイクストラ法に予測距離を加えた考えで、ダイクストラ法に比べて目的地点までの到達ステップが短くなる。また、Ａ＊アルゴリズムにおいて、予測距離が含まれる為、目的地点へたどり着いた時点でその経路が最短ルートとならない可能性がある。また、Ａ＊アルゴリズムにおいて、目的地までたどり着く事を優先させ、メモリ容量と処理時間を抑えることができる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】"ダイクストラ法（最短経路問題）"、［online］、［平成２３年２月１７日検索］、インターネット<URL：http://www.deqnotes.net/acmicpc/dijkstra/>
【非特許文献２】"Ａ＊"［online］、［平成２３年２月１７日検索］、インターネット<URL：http://ja.wikipedia.org/wiki/A*>
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のナビゲーション装置においては、最短経路を探索するものが多く、ユーザの望む建物の数を考慮した経路探索ができないという課題があった。
【０００６】
例えば、従来のナビゲーション装置においては、ユーザが食料品等の買い物をしながら、目的地まで到達したいと考えても、付近に食料品を販売している店舗がなるべく多くなるように経路を探索することができなかった。また、例えば、ユーザが、目的地に到着するまでの経路の途中で、任意のレストランによって食事をしたいと考えても、付近にレストランがなるべく多くなるような経路を探索することができなかった。
【課題を解決するための手段】
【０００７】
本発明のナビゲーション装置は、地図に関する情報であって、地図が示す道路に関する情報である道路情報を有する地図情報が格納される地図情報格納部と、地図情報が示す各道路についての、周辺の建物に関する情報である建物関連情報が格納される建物関連情報格納部と、出発地を示す情報である出発地情報と、目的地を示す情報である目的地情報を受け付ける受付部と、建物についての条件である建物条件を受け付ける条件受付部と、道路情報と建物関連情報と建物条件とを用いて、周辺に建物条件を満たす建物が多い経路が探索されやすくなるようにして、出発地情報が示す出発地から、目的地情報が示す目的地までの経路を探索する経路探索部と、探索部の探索結果に応じた出力を行う出力部とを備えたナビゲーション装置である。
【０００８】
かかる構成により、ユーザの望む建物の数を考慮した最適な経路を探索することができる。例えば、建物条件を満たす建物が多い道路の優先度や評価値が、通常の経路探索よりも高くなるようにして、経路探索を行うことができる。
【０００９】
また、本発明のナビゲーション装置は、前記ナビゲーション装置において、建物関連情報格納部に格納されている建物関連情報は、地図情報が示す各道路についての、道路周辺のカテゴリーが店舗である建物に関する情報を含んでおり、条件受付部が受け付ける建物条件は、カテゴリーが店舗である建物を指定する条件であり、経路探索部は、カテゴリーが店舗である建物数の多い経路が探索されやすくなるようにして経路を探索するナビゲーション装置である。
【００１０】
かかる構成により、店舗の数を考慮した最適な経路を探索することができる。
【００１１】
また、本発明のナビゲーション装置は、前記ナビゲーション装置において、建物関連情報格納部に格納されている建物関連情報は、地図情報が示す各道路についての、道路周辺のカテゴリーがレストランである建物に関する情報を含んでおり、条件受付部が受け付ける建物条件は、カテゴリーが店舗である建物を指定する条件であり、経路探索部は、カテゴリーが店舗である建物数の多い経路が探索されやすくなるようにして経路を探索するナビゲーション装置である。
【００１２】
かかる構成により、レストランの数を考慮した最適な経路を探索することができる。
【００１３】
また、本発明のナビゲーション装置は、前記ナビゲーション装置において、建物関連情報格納部に格納されている建物関連情報は、地図情報が示す各道路についての、道路周辺のカテゴリーがショッピングである建物に関する情報を含んでおり、条件受付部が受け付ける建物条件は、カテゴリーがショッピングである建物を指定する条件であり、経路探索部は、カテゴリーがショッピングである建物数の多い経路が探索されやすくなるようにして経路を探索するナビゲーション装置である。
【００１４】
かかる構成により、ショッピングに適した建物の数を考慮した最適な経路を探索することができる。
【００１５】
また、本発明のナビゲーション装置は、前記ナビゲーション装置において、目的地に到着するまでの予定時間を受け付ける予定時間受付部を更に備え、道路情報は、各道路の移動に要する時間である移動時間を含んでおり、前記経路探索部は、経路に含まれる道路の移動時間を用いて、予定時間受付部が受け付けた予定時間以内の経路を探索するナビゲーション装置である。
【００１６】
かかる構成により、ユーザが指定した予定時間内に目的地に到着可能な経路を出力することができる。これにより、ユーザの要望に添った、いわば寄り道が可能な経路を提示することが可能となる。
【００１７】
また、本発明のナビゲーション装置は、前記ナビゲーション装置において、建物の利用に要する時間の情報である利用時間が格納されている利用時間格納部を更に備え、経路探索部は、経路に含まれる道路の移動時間と、道路に対応する建物条件を満たす建物の利用時間とを用いて、予定時間受付部が受け付けた予定時間以内の経路を探索するナビゲーション装置である。
【００１８】
かかる構成により、経路の途中の、建物条件を満たす建物を利用したこと考慮して、予定時間内に到着可能な経路を出力することができる。
【発明の効果】
【００１９】
本発明によるナビゲーション装置等によれば、ユーザの望む建物の数を考慮した経路探索を行うことができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態１におけるナビゲーション装置のブロック図
【図２】同ナビゲーション装置の動作の一例を示すフローチャート
【図３】同ナビゲーション装置の概念図
【図４】同ナビゲーション装置の地図図柄情報の一例を示す図
【図５】同ナビゲーション装置のノード管理表を示す図
【図６】同ナビゲーション装置のリンク管理表を示す図
【図７】同ナビゲーション装置のノード及びリンクの一部を地図上に配置した模式図
【図８】建物関連情報格納部に予め格納されている建物関連情報を示す図を示す図
【図９】同ナビゲーション装置の表示例を示す図を示す図
【図１０】重み付け値格納部に格納されている重み付け値を管理する重み付け値管理情報を示す図
【図１１】同ナビゲーション装置の取得重み付け値管理表を示す図
【図１２】同ナビゲーション装置のリンク及びノードと、補正コストとの関係を模式的に示した図
【図１３】同ナビゲーション装置の出力部経路の探索結果の表示例を示す図
【図１４】同ナビゲーション装置の建物管理情報の変形例を示す図
【図１５】本発明の実施の形態２におけるナビゲーション装置のブロック図
【図１６】同ナビゲーション装置の動作の一例を示すフローチャート
【図１７】同ナビゲーション装置のリンク管理表を示す図
【図１８】同ナビゲーション装置の表示例を示す図
【図１９】同ナビゲーション装置が探索した複数の経路を示す図
【図２０】同ナビゲーション装置の利用時間管理表を示す図
【図２１】同ナビゲーション装置の上限管理表を示す図
【図２２】同ナビゲーション装置の表示例を示す図
【図２３】同ナビゲーション装置の表示例を示す図
【図２４】本発明の各実施の形態におけるコンピュータシステムの外観の一例を示す図
【図２５】同コンピュータシステムの構成の一例を示す図
【発明を実施するための形態】
【００２１】
以下、ナビゲーション装置等の実施形態について図面を参照して説明する。なお、実施の形態において同じ符号を付した構成要素は同様の動作を行うので、再度の説明を省略する場合がある。
【００２２】
（実施の形態１）
図１は、本実施の形態におけるナビゲーション装置１のブロック図である。
【００２３】
ナビゲーション装置１は、地図情報格納部１０１、建物関連情報格納部１０２、受付部１０３、条件受付部１０４、経路探索部１０５、重み付け値格納部１０６、出力部１０７を備える。
【００２４】
ナビゲーション装置１は、例えば、現在地や目的地の地図等を出力したり、出発地（現在地）から目的地までの経路を出力したりする装置である。ナビゲーション装置１は、特に、携帯可能なナビゲーション装置であることが好ましいが、車載用のナビゲーション装置であっても良い。ナビゲーション装置１は、ナビゲーション専用の装置であっても良いし、ナビゲーション機能を実現する携帯電話やスマートフォンやカメラ等の携帯端末であっても良い。
【００２５】
地図情報格納部１０１には、地図情報が格納される。地図情報は、地図に関する情報である。地図情報は、道路情報を有している。道路情報は、地図が示す道路に関する情報である。地図情報は、通常、地図の画像である地図図柄情報を更に有している。地図図柄情報は、例えば、地図を構成するビットマップデータ（ラスタデータ）またはベクタデータ、またはこれらの組合せなどである。地図図柄情報のファイル形式は、ＧＩＦ形式やＪＰＥＧ形式や、ＰＮＧ形式等問わない。地図情報は、ＩＳＯのｋｉｗｉ地図データフォーマットであっても良い。地図情報は、地図上に表記されている地名や、建物や名勝や場所の名称などの文字列を有していても良い。
【００２６】
地図情報は、例えば、その地図情報が表示する地域の経度や緯度を有する座標情報等の、絶対的な位置を示す位置情報や、各地図情報間においてそれぞれの地図が示す領域間の位置関係が分かるような相対的な位置を示す位置情報を有している、もしくは対応付けられている。例えば、地図情報の表示する地図の範囲や中心点を、緯度と経度との範囲で定義する情報を有していてもよい。このような位置情報を用いることで、地図上の座標と、実空間における座標（例えば、緯度及び経度）とを適宜変換することが可能となる。また、地図情報は、当該地図情報により示される地図内の住所等の位置を指定可能な位置情報を有していても良い。また、地図情報は、縮尺ごとに地図図柄情報を有していてもよいし、縮尺ごとに地図情報が用意されていても良い。通常、地図情報は地図の縮尺と対応付けて管理されている。具体的には、地図情報は、当該地図情報により出力される地図の縮尺の値の情報を有していても良いし、地図情報が地図の縮尺と対応付けて１０１に格納されていてもよい。ここでの地図の縮尺とは、地図の縮尺の値を示す情報と考えても良い。
【００２７】
道路情報は、道路に関する情報である。道路情報は、例えば、ノードデータと、リンクデータとを含んでいる。ノードは、交差点や分岐点等の、道路同士が接続される地点を示すものである。ノードデータは、ノードに関する情報である。ノードデータは、道路網の接続関係を示すデータと考えても良い。行き止まり等の道路網の端点、即ち他の道路と接続されていない道路の端点もノードと考えてもよい。また、ノードは、道路同士が接続される地点以外の道路上の任意の箇所にも設けられていてもよい。ノードデータは、例えば、ノードを識別する識別情報と、ノードの地図上の座標、あるいは、実空間の座標を有する。また、ノードデータは、ノードに接続されるリンクを示す情報等を有していても良い。リンクは、ノードを結ぶ道路を示すものである。リンクは、例えば、ノード間の道路と考えても良いし、ノードを結ぶ線等と考えても良い。リンクデータは、リンクに関するデータである。リンクデータは、例えば、リンクを識別する情報であるリンク識別情報や、リンクが接続されるノード（例えば、両端のノード）を示す情報（例えばノード識別情報）を有している。また、リンクデータは、リンクの端部の地図上の座標あるいは実空間の座標を有していても良い。また、各リンクデータには、リンクデータが示すリンクを含む道路の名称や道路番号等の道路の識別情報（例えば、京浜バイパスや、烏丸通りや、国道１号線等）を有していても良い。例えば、一の道路が複数のリンクで構成されているとすると、各リンクのリングデータには、同じ道路の識別情報が付与される。なお、リンクは、必ずしも隣り合わせのノードで区切られた道路でなくても良く、一の道路上の、隣り合わせでない一組のノードで区切られた道路を示すものであっても良い。
【００２８】
リンクデータは、例えば、複数の道路特性パラメータについてのコスト等の情報を有している。道路特性パラメータとしては、距離、通行時間、有料・無料の区別、通りやすさ、道路幅などがあり、それぞれの道路特性パラメータについてコスト（距離のコスト、通行時間のコスト等）が定められている。コストは、例えば、経路を探索する場合等において、選択する道路を評価する際等に利用する評価値である。コストは、例えば、経路選択のための優先度を示す値や、道路（リンク）の選択されやすさを示す評価値と考えても良い。また、コストはスコアと考えても良い。ダイクストラ法等の経路探索は、例えば、各リンクに対応する一以上のコストを利用して行われる。なお、一のリンクに対して、複数の道路特性パラ−メータについてのコストを総合したコストや、複数の道路特性パラメータを考慮した１以上のコストが対応付けられているようにしても良い。この場合、このような総合したコスト等を用いて、経路探索を行うようにしても良い。
【００２９】
なお、道路情報は、上記のノードデータやリンクデータに加えて、道路の道筋を示すデータを有していてもよい。道路あるいはリンクの道筋を示すデータは、例えば、道路の道筋に沿った直線や曲線の線状、あるいは帯状の情報（例えば、スプライン曲線や、ベジェ曲線の情報）や、道路に沿って配置された複数の座標の集合や、道路に沿って設けられた一以上のベクトルの情報等であっても良い。道路の道筋を示すデータは、リンクデータ毎に設けられていても良い。
【００３０】
また、経路探索が、リンクやノードを利用せずに行われる場合においては、道路情報は、上記のノードデータやリンクデータの代わりに、経路探索に必要な道路の情報を有していても良い。
【００３１】
なお、ここでの格納は一時記憶も含む概念である。地図情報格納部１０１は、不揮発性の記録媒体が好適であるが、揮発性の記録媒体でも実現可能である。
【００３２】
建物関連情報格納部１０２は、地図情報が示す各道路についての、周辺の建物に関する情報である建物関連情報が格納される。ここでの建物とは、どのような用途や目的の建物であっても良い。また、一の建物内の、異なる用途や目的で利用されるフロアや、部屋等も、ここでは、それぞれ個別の建物と考えても良い。建物は、例えば、店舗や、オフィス、ランドマーク、美術館、映画館、病院等である。また、ここでは、建物を、住所によって特定可能なものと考えても良い。一の道路の周辺の建物とは、この道路が最も近い道路である建物や、この道路が最も出入り口に近い道路である建物である。また、一の道路からの距離が予め指定された距離以内である建物と考えても良い。あるいは一の道路に接している（面している）建物と考えても良い。
【００３３】
建物関連情報とは、例えば、各道路についての、周辺に位置する建物のカテゴリー別の集計数を示す情報である。集計数を示す情報とは、集計数（合計数）そのものであっても良いし、この集計数を予め用意された閾値等を用いてｎ値化した値（ｎは二以上の整数）値や、予め用意された演算式等を用いて指標化した値であっても良い。なお、例えば、複数のカテゴリーに属する建物がある場合、各カテゴリーについて建物数を集計する際に、この建物を、それぞれのカテゴリーで重複してカウントして良い。建物のカテゴリーについては後述する。
【００３４】
また、建物関連情報は、各道路についての、周辺に位置する個々の建物の情報である。この個々の建物の情報は、例えば、個々の建物が属する一以上のカテゴリーを示す情報を含む情報である。カテゴリーを示す情報とは、カテゴリーの識別情報、例えばカテゴリー名である。個々の建物の情報は、個々の建物のカテゴリー情報と考えても良い。また、この個々の建物の情報は、個々の建物の識別情報等を有していても良い。建物の識別情報は、例えば、建物名や、建物を利用するものの名前や、建物の住所である。
【００３５】
建物関連情報は、対応する各道路の識別情報を有していても良い。本実施の形態においては、特に、地図情報が示す各道路をリンク単位の道路と考えて、建物関連情報が、対応する各リンクのリンク識別情報を有している場合を例に挙げて説明する。例えば、建物関連情報は、リンク識別情報と、このリンク識別情報が示すリンクの周辺に位置する建物のカテゴリー別の集計数を示す情報とを有する情報である。あるいは、建物関連情報は、リンク識別情報と、このリンク識別情報が示すリンクの周辺に位置する個々の建物の情報とを有する情報であってもよい。なお、建物関連情報がリンク単位ではない道路の周辺の建物に関する情報である場合において、この道路が複数のリンクを有する場合、この複数のリンクのそれぞれの建物関連情報として、この道路に対応する建物関連情報を利用しても良い。
【００３６】
なお、建物関連情報は、各道路の周辺の建物数をカテゴリー別に取得可能な情報と考えても良い。
【００３７】
建物のカテゴリーとは、例えば、建物の用途や、目的等の分類である。カテゴリーはジャンルと考えても良い。建物の各カテゴリーは、例えば、カテゴリー名等のカテゴリーの識別情報と対応付けられている。建物のカテゴリーとしては、例えば、衣料品店、食料品店、雑貨店、書店、洋菓子店、店舗、美容院、病院、レストラン、喫茶店、映画館、美術館、画廊等がある。また、カテゴリーは、ユーザが建物を利用して行うことができる行動等を示す分類であってもよい。このようなカテゴリーは、例えば、ショッピング、レジャー、観光、美術鑑賞、デートスポット等である。また、建物のカテゴリーは、建物で提供されるサービスや物品のカテゴリー（例えば、整体、クリーニング、食品、雑貨、衣料等）であっても良いし、その提供形態（例えば、セルフサービス、予約制、２４時間営業）等であっても良い。また、建物のカテゴリー同士は、階層関係を有していても良い。例えば、衣料品店や、食料品店、雑貨店、書店等のカテゴリーの上位のカテゴリーが、店舗というカテゴリーであってもよい。また、ショッピングというカテゴリーの下位のカテゴリーが、衣料品店、雑貨店、靴店等であってもよい。カテゴリー間の階層関係は、例えば、建物関連情報格納部１０２等に格納される階層関係を管理する情報で管理されていても良い。また、一の建物は、複数のカテゴリーに属していても良い。例えば、一の建物が、書店と、雑貨というカテゴリーに属していてもよい。また、一の建物が属する複数のカテゴリー同士が、階層関係を有していてもよい。例えば、一の店舗が、食料品店と、スーパーマーケットというカテゴリーに属していても良い。
【００３８】
建物関連情報格納部１０２には、例えば、予め用意された建物関連情報が格納される。建物関連情報格納部１０２に格納される建物関連情報は、例えば、地図情報が示す各道路についての、各道路周辺のカテゴリーが店舗である建物に関する情報である。建物に関する情報とは、上述したような、各道路周辺のカテゴリー別の建物数を示す情報や、各道路周辺の各店舗の情報である。また、建物関連情報格納部１０２に格納される建物関連情報は、例えば、地図情報が示す各道路についての、各道路周辺のカテゴリーがレストランである建物に関する情報である。また、建物関連情報格納部１０２に格納される建物関連情報は、例えば、地図情報が示す各道路についての、各道路周辺のカテゴリーがファッションである建物に関する情報である。
【００３９】
建物関連情報格納部１０２は、不揮発性の記録媒体が好適であるが、揮発性の記録媒体でも実現可能である。
【００４０】
受付部１０３は、出発地を示す情報である出発地情報と、目的地を示す情報である目的地情報を受け付ける。受付部１０３は、出発地情報と目的地情報を含む指示であり、出発地から目的地までの経路を出力する指示である経路出力指示を受け付けても良い。経路出力指示は、経路探索のための様々な条件を指定する情報を有していてもよい。出発地情報とは、例えば、（緯度，経度）の位置情報、地名などである。出発地情報は、経路探索のスタート地点を示す情報であれば良い。また、出発地情報として、ナビゲーション装置１が有する図示しないＧＰＳ受信機等が経路探索の開始時等に出力する現在位置を示す情報を用いても良い。なお、現在位置を示す情報は、図示しないジャイロや加速度センサ等を用いて取得してもよい。現在位置を示す情報を取得する構成等はナビゲーション装置の技術として公知である。目的地情報とは、例えば、（緯度，経度）の位置情報、地名など、目的地を示す情報であれば良い。目的地情報は、経路探索の終了地点を示す情報であればよい。なお、経路探索の出発地を始点、目的地を終点と考えても良い。なお、出発地情報や、目的地情報として、出発地や目的地となるノードの識別情報やリンクの識別情報を受け付けても良い。ここでの受け付けは、ナビゲーション装置のタッチパネルやキーボードやマウス等の入力デバイスを利用したユーザ入力の受け付け、音声入力による受け付け、外部装置からの受信、記録媒体からの読み出しなどである。出発地情報や目的地情報の入力手段は、キーボードやマウスやテンキーやメニュー画面によるもの等、何でも良い。受付部１０３は、キーボード等の入力手段のデバイスドライバーや、メニュー画面の制御ソフトウェア等で実現され得る
【００４１】
条件受付部１０４は、建物についての条件である建物条件を受け付ける。建物条件は、例えば、経路探索を行う際に利用される条件である。建物条件は、例えば、道路（例えばリンク）についての重み付け値を取得する際において、各道路に対応する周辺の建物の数を取得する際に、取得対象となる建物を絞り込むために用いられる条件である。道路についての重み付け値とは、例えば、道路の評価値（コスト）の重み付けを行うための値である。建物条件とは、例えば、建物のカテゴリーを用いて、建物を絞り込むための情報である。建物条件とは、例えば、上述したような建物のカテゴリーを指定する条件である。例えば、建物条件は、雑貨店、店舗等のカテゴリーを指定する情報である。建物条件は、複数の建物のカテゴリーの指定を有する条件であっても良い。また、建物条件は、複数のカテゴリーの指定と、これらのカテゴリーの指定を、それぞれＡＮＤ条件、ＯＲ条件、ＮＯＴ条件等のどのような条件として利用するかを示す情報とを有する条件であってもよい。また、建物条件は、複数のカテゴリーの指定をグループ化したものであっても良い。建物条件は、階層化されているカテゴリーのうちの、下位階層以外の一の階層のカテゴリーを指定する条件であっても良い。このような建物条件は、このカテゴリーに従属する全てまたは一部のカテゴリーを指定する条件であるとして扱うようにしてもよい。また、建物条件は、建物のカテゴリー名等に含まれるキーワード等であっても良い。なお、建物条件は、カテゴリーを問わず、一以上の何らかのカテゴリーに属している建物を指定する条件であっても良い。あるいは、建物関連情報に、道路の周辺の建物として登録されている建物を指定する条件であっても良い。
【００４２】
条件受付部１０４は、例えば、ユーザにより入力された建物条件を受け付ける。また、予め図示しない記憶媒体等に蓄積されている建物条件を読み出してもよい。このような記憶媒体等からの読み出しも、ここでは建物条件の受け付けと考えるようにしても良い。建物条件の入力手段は、テンキーやキーボードやマウスやメニュー画面によるもの等、何でも良い。条件受付部１０４は、テンキーやキーボード等の入力手段のデバイスドライバーや、メニュー画面の制御ソフトウェア等で実現され得る。
【００４３】
経路探索部１０５は、道路情報を用いて、出発地情報が示す出発地から、目的地情報が示す目的地までの経路を探索する。経路探索部１０５は、例えば、地図情報格納部１０１に格納されている道路情報に含まれるノードデータとリンクデータとを用いて、経路探索を行う。そして、例えば、探索した経路を示す経路情報を取得する。経路探索部１０５は、ここでは特に、建物関連情報と建物条件とを更に用いて、周辺に建物条件を満たす建物が多い経路が探索されやすくなるようにして、出発地から目的地までの経路を探索する。周辺に建物条件を満たす建物が多い経路が探索されやすくなるようにしてとは、周辺に建物条件を満たす建物が多い経路が探索されやすくなる経路探索のアルゴリズムを用いるという意味と考えても良い。また、周辺に建物条件を満たす建物が多い道路が選択されやすくなるように経路を探索することと考えても良い。
【００４４】
例えば、建物条件が、カテゴリーが店舗である建物を指定する条件であったとすると、経路探索部１０５は、カテゴリーが店舗である建物数の多い経路が探索されやすくなるようにして経路を探索する。なお、建物を分類するカテゴリーとして、店舗というカテゴリーの下位の階層の１以上のカテゴリーだけが用意されている場合、何らかのカテゴリーと対応付けられている建物を、全て、カテゴリーが店舗である建物と考えてもよい。
【００４５】
また、例えば、建物条件が、カテゴリーがレストランである建物を指定する条件であったとすると、経路探索部１０５は、カテゴリーがレストランである建物数の多い経路が探索されやすくなるようにして経路を探索する。
【００４６】
また、例えば、建物条件が、カテゴリーがショッピングである建物を指定する条件であったとすると、経路探索部１０５は、カテゴリーがショッピングである建物数の多い経路が探索されやすくなるようにして経路を探索する。
【００４７】
例えば、経路探索部１０５は、建物条件が示す条件を満たす建物数に応じた重み付け値を各道路（例えばリンク）ごとに取得して、取得した重み付け値で、各道路の経路探索に利用する評価値（例えばコスト）を重み付けし、重み付けして得られた評価値を用いて、経路探索を行う。
【００４８】
以下に、道路を、リンク単位の道路とした場合について、具体的に説明する。まず、経路探索部１０５は、建物関連情報を用いて、地図情報が示す各道路（リンク）のうちの経路探索の対象となる道路について、その周辺の建物のうちの、建物条件が示す条件を満たす建物の建物数を示す情報を取得する。例えば、建物関連情報が、各道路（リンク）周辺のカテゴリー別の建物数を示す情報を有しており、建物条件が一以上のカテゴリーを指定する条件であったとすると、このカテゴリーに対応した建物数を示す情報を道路（リンク）について取得する。具体例を挙げると、一のリンクであるリンクＡに対応付けてカテゴリーが店舗である建物数の情報「２」が建物関連情報に格納されており、建物条件として、カテゴリーが店舗である建物を指定する条件を受け付けたとすると、経路探索部１０５は、このリンクについての建物条件を満たす建物数を示す情報として「２」を取得する。また、建物関連情報が、道路（リンク）周辺の個々の建物の情報（ただし、建物のカテゴリーを示す情報を含む情報であるとする）であったとすると、この建物関連情報から、建物条件が示すカテゴリーに属する建物を検索して、その数をカウントして、建物条件が示す条件を満たす建物の建物数を示す情報を取得すればよい。経路探索の対象となる各道路（リンク）とは、例えば、出発地と目的地とを含む経路探索の対象となる領域の全ての道路である。経路探索の対象となる領域はどのように決定してもよい。例えば、出力部１０７が経路探索の入力を行うために表示している地図が表示している領域を、経路探索の対象領域としてもよい。また、例えば、出発地と目的地とを対向する辺上に有する、縦横比が一定の矩形の領域を、経路探索の対象となる領域に設定しても良い。ただし、出発地と目的地を含む領域であればどのよう領域を経路探索の対象となる領域に設定しても良く、例えば、地図情報格納部１０１に格納されている地図情報が示す全ての領域を経路探索の対象に設定しても良い。また、地図情報格納部１０１に、複数の領域を示す複数の地図情報が格納されており、各地図情報に対して、各地図が示す領域内の道路情報（例えばリンクデータ）が対応付けられている場合、出発地と目的地を含む地図を出力するために用いられる１以上の地図情報が示す領域を、経路探索の対象となる領域として、これらの地図情報にそれぞれ対応付けられている道路情報（リンクデータ）が示す道路（リンク）を、経路探索の対象の道路と判断しても良い。
【００４９】
次に、経路探索部１０５は、このようにして道路（リンク）について取得した建物条件が示す条件を満たす建物の建物数を示す情報を用いて、道路（リンク）について、この建物数を示す情報に対応する重み付け値を取得する。重み付け値は、例えば、道路の評価値の重み付けのために用いられる重み係数である。この重み付け値は、建物数を示す情報を変数とした予め指定された演算式を用いて算出しても良いし、後述する重み付け値格納部１０６に予め格納されている重み付け値と、建物数を示す情報とを対応付けて有する重み付け管理情報から、取得した建物数を示す情報に対応した重み付け値を取得するようにしても良い。ここでは、一例として、重み付け値格納部１０６から道路（リンク）について重み付け値を取得する場合について説明する。取得した重み付け値は、道路（リンク）と対応付けて、図示しない記憶媒体に蓄積する。例えば、リンク識別情報と対応付けて記憶媒体に蓄積する。この記憶媒体は、ＲＡＭ等の揮発性の記憶媒体であっても良いし、不揮発性の記憶媒体であっても良い。
【００５０】
次に、経路探索部１０５は、経路探索に利用する道路（リンク）の評価値であるコストを、道路（リンク）について取得した重み付け値を用いて補正する。ここでの補正は、重み付け値を用いた重み付けのことであり、例えば、道路（リンク）のコストに対して、道路について取得した重み付け値を乗算したり、加算したりすることである。そして、補正により得られた補正コストを用いて経路探索を行う。ここでの経路探索に用いられる経路探索方法やアルゴリズムは、例えば、上述したようなダイクストラ法や、Ａ＊アルゴリズムや、その他の様々な経路探索方法や、経路探索アルゴリズム等が利用可能である。経路探索部１０５が利用する経路探索方法やアルゴリズムとしては、道路（リンク）についての評価値（例えばコスト）を用いて、経路を探索するものを用いることが好ましい。経路探索方法としては、複数経路が探索可能な方法等も利用可能である。この場合、複数の経路が探索されることとなる。なお、重み係数等を用いて補正した補正コストを用いて経路探索を行う処理については、公知技術であるのでここでは詳細な説明は省略する。そして、例えば、探索した経路を示す経路情報を取得する。
【００５１】
なお、ここでは、予め経路探索の範囲内の１以上の道路（リンク）について、予め補正コストを取得するようにしたが、経路探索アルゴリズムにより、各道路（リンク）を辿る際に、建物関連情報と建物条件とを用いて、各道路（リンク）の重み付け値を取得して、補正コストを算出するようにしても良い。
【００５２】
また、重み付け値がない道路（リンク）については、重み付けを行わないようにしても良い。
【００５３】
なお、経路探索のアルゴリズム等として、コストが小さくなる経路を探索するものを用いる場合には、重み付け値としては、建物条件を満たす建物数が増加すると、重み付けによって各道路のコストが段階的にあるいは連続的に小さくなるような重み付け値を経路探索部１０５が取得できるようにすることが好ましい。なお、このことは、建物条件を満たす建物数が減少すると、重み付けによって各道路のコストが段階的にあるいは連続的に大きくなるような重み付け値を取得できるようにすることと同じことであるとここでは考える。
【００５４】
なお、出発地情報や目的地情報が示す座標が、道路上の座標でない場合、経路探索部１０５は、例えば、出発地情報や目的地情報が示す座標に対して最も整合性の高い道路（リンク）上の位置や、最も出発地情報や目的地情報が示す座標に近い道路（リンク）上の位置を、経路探索の出発地や目的地に設定してもよい。このような道路上の位置を決定する処理は、マップマッチング等の技術等として公知であるので、ここでは詳細な説明は省略する。また、目的地情報や出発地情報が地名や住所である場合、この地名に対応した座標やノードの識別情報やリンクの識別情報等を経路探索部１０５が地図情報から取得してもよい。
【００５５】
経路探索部１０５が取得する経路情報は、探索した経路を特定可能な情報であればよい。例えば、経路情報は、経路で通過する一以上の道路や交差点や分岐点を示す情報を、それらの通過順番と対応付けて示した情報である。経路情報は、例えば、経路探索により探索された各経路における、出発地から目的地にたどり着くまでに通過するノードおよびリンクを示す情報（例えば、ノード識別情報やリンク識別情報等）で構成される。また、経路情報は、出発地情報および目的地情報、あるいはこれらの識別情報を更に有していても良い。経路情報は、例えば、出発地情報と、出発地から目的地にたどり着くまでに通過する道路情報（ノードデータやリンクデータ）と、目的地情報とを、通過順番と対応付けて有する情報、もしくはこれらの識別情報を、通過順番と対応付けて有する情報である。通過順番と対応付けて有する情報とは、通過順番を示す番号等の情報を対応付けた情報であっても良いし、通過順番に従って、予め指定されたルール等に従って配列したり蓄積したものであっても良い。例えば、ノード及びリンクの識別情報が、通過順番を示す番号の情報と対応付けて蓄積された情報であっても良いし、ノード及びリンクの識別情報が通過順番が示す順番に配列されて蓄積された情報であっても良い。また、経路情報は、ノードやリンクの代わりに、経路を、座標等を用いて表される一以上の線分の組合せで示した情報であっても良い。あるいは、経路をスプライン曲線やベジェ曲線で表した情報であっても良い。経路情報について、公知の経路探索技術で得られる経路情報が利用可能である。
【００５６】
経路探索部１０５は、通常、ＭＰＵやメモリ等から実現され得る。経路探索部１０５の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【００５７】
重み付け値格納部１０６には、経路探索部１０５が取得する建物条件を満たす建物数を示す情報と、この情報と対応付けられた重み付け値とを有する重み付け値管理情報が予め格納される。重み付け値は、経路探索の際に、リンクのコストに対して重み付けを行うために用いられる値である。重み付け値は、例えば、重み付けための係数である。建物数を示す情報は、建物数の値の範囲を設定する情報であっても良い。経路探索のアルゴリズム等として、コストが小さくなる経路を探索するものを用いる場合には、重み付け値格納部１０６には、例えば、建物数が多いことを示す建物数を示す情報に対して、同じもしくはより小さい重み付けが行われる重み付け値を対応付けて格納しておく。重み付け値格納部１０６は、不揮発性の記録媒体が好適であるが、揮発性の記録媒体でも実現可能である。
【００５８】
出力部１０７は、経路探索部１０５の探索結果に応じた出力を行う。例えば、出力部１０７は、経路探索部１０５が取得した経路情報を出力する。経路情報を出力するとは、経路情報をそのまま他の装置にネットワーク等を介して送信したり、記録媒体等に蓄積したりすることであっても良いし、経路情報が示す経路を示す情報を出力することであっても良い。例えば、経路情報に含まれる各リンクに対応する道路名や、ノードに対応する交差点名等を、経路情報が示す経路の順番に、モニタ等に表示しても良いし、これらの道路名や交差点名等を、音声として出力しても良い。また、この経路情報が示す経路を含む地図図柄情報を地図情報格納部１０１から読み出して、この地図上の経路情報が示す経路に対応する道路の表示態様を、他の道路に対して識別可能な表示態様とした地図を表示するようにしても良い。例えば、この経路に対応する道路上に予め指定された色等の表示属性を有する線を配置した地図の画像を生成して表示しても良い。また、この経路に対応する道路を予め指定された色で着色した地図の画像を生成してもよい。複数の経路を探索した場合には、経路同士も識別可能な態様で表示することが好ましい。なお、経路情報が示す経路を地図上に表示する技術等は公知の技術であるのでここでは詳細な説明は省略する。
【００５９】
ここで述べる出力とは、ディスプレイへの表示、プロジェクターを用いた投影、音出力、外部の装置への送信、記録媒体への蓄積、他の処理装置や他のプログラム等への処理結果の引渡し等を含む概念である。出力部１０７は、ディスプレイやプリンタ等の出力デバイスを含むと考えても含まないと考えても良い。出力部は、出力デバイスのドライバーソフトまたは、出力デバイスのドライバーソフトと出力デバイス等で実現され得る。
【００６０】
図２は、本実施の形態のナビゲーション装置１の動作の一例を示すフローチャートである。以下、図２を用いて、ナビゲーション装置１の動作について説明する。ここでは、一例として、道路情報に含まれるリンク情報が示すリンクごとに重み付け値を取得する場合を例に挙げて説明する。
【００６１】
（ステップＳ２０１）受付部１０３は、出発地情報と、目的地情報とを受け付けたか否かを判断する。例えば、受付部１０３は、ユーザが入力した出発地情報や目的地情報を受け付ける。また、出発地情報については、ユーザの指示に応じて図示しないＧＰＳ受信機が現在位置を取得した場合に、この現在位置を受け付けてもよい。受付部１０３が出発地情報と目的地情報とを受け付けた場合、ステップＳ２０２に進み、受け付けていない場合、ステップＳ２０１に戻る。
【００６２】
（ステップＳ２０２）条件受付部１０４は、建物条件を受け付けたか否かを判断する。条件受付部１０４は、ユーザが入力する建物条件を受け付けても良いし、予め図示しない記憶媒体等に蓄積されている建物条件を読み出しても良い。受け付けた場合、ステップＳ２０３に進み、受け付けていない場合、ステップＳ２０２に戻る。
【００６３】
（ステップＳ２０３）経路探索部１０５は、経路探索対象となる領域内の道路情報を読み出す。経路探索対象となる領域は、例えば、ユーザが出発地情報と目的地情報とを入力するために表示している地図が示す領域である。また、読み出す道路情報は、例えば、リンクデータおよびノードデータである。読み出した道路情報は、メモリ等に一時記憶する。
【００６４】
（ステップＳ２０４）経路探索部１０５は、カウンターｎに１を代入する。
【００６５】
（ステップＳ２０５）経路探索部１０５は、ステップＳ２０３で読み出した道路情報内に、ｎ番目のリンク情報があるか否かを判断する。ある場合、ステップＳ２０６に進み、ない場合、ステップＳ２１０に進む。
【００６６】
（ステップＳ２０６）経路探索部１０５は、建物関連情報を用いて、ｎ番目のリンクについて、ステップＳ２０２で受け付けた建物条件が示す条件を満たす建物数を示す情報を取得する。建物条件が示す条件を満たす建物数とは、例えば、建物条件が示すカテゴリーに属する建物数である。例えば、建物関連情報が、各リンク識別情報と、リンク周辺に位置する個々の建物についての、各建物が属しているカテゴリーの情報とを有している場合、経路探索部１０５は、建物関連情報から、ｎ番目のリンクのリンク識別情報と対応している建物であって、建物条件が示すカテゴリーに属する建物を検出して、検出した建物数をカウントして取得する。また、建物関連情報が、各リンク識別情報と、リンク周辺に位置する建物のカテゴリーと、このカテゴリー別にリンク周辺の建物数を集計した集計数を示す情報とを有する場合、経路探索部１０５は、ｎ番目のリンクのリンク識別情報と、建物条件が示すカテゴリーとに対応した集計数を示す情報を取得する。建物条件が、複数のカテゴリーを含む場合、この複数のカテゴリーが示す条件にあう集計数を示す情報を取得すればよい。
【００６７】
（ステップＳ２０７）経路探索部１０５は、取得したｎ番目のリンクについての集計数を示す情報を用いて、ｎ番目のリンクについての重み付け値を取得する。例えば、重み付け値格納部１０６に格納されている重み付け値管理情報から、ステップＳ２０６で取得した建物数を示す情報に対応した重み付け値を取得する。
【００６８】
（ステップＳ２０８）経路探索部１０５は、取得した重み付け値を、図示しない記憶媒体に、ｎ番目のリンクのリンク識別情報と対応付けて蓄積する。
【００６９】
（ステップＳ２０９）経路探索部１０５は、カウンターｎの値を１インクリメントする。そして、ステップＳ２０５に戻る。
【００７０】
（ステップＳ２１０）経路探索部１０５は、ステップＳ２０３で読み出したリンクデータおよびノードデータを含む道路データと、ステップＳ２０８で取得した重み付け値とを用いて経路探索を行う。具体的には、各リンクに対応するコストに、各リンクに対応した重み付け値を乗算して得られた補正コストを、各リンクのコストとして用いて、ステップＳ２０１で受け付けた出発値情報が示す出発地から、目的地情報が示す目的地までの経路の探索を行う。
【００７１】
（ステップＳ２１１）経路探索部１０５は、ステップＳ２１０による経路探索結果である経路情報を取得する。
【００７２】
（ステップＳ２１２）経路探索部１０５は、経路情報を出力する。そして、ステップＳ２０１に戻る。
【００７３】
なお、図２のフローチャートにおいて、電源オフや処理終了の割り込みにより処理は終了する。
【００７４】
以下、本実施の形態におけるナビゲーション装置１の具体的な動作について説明する。ナビゲーション装置１の概念図は図３である。なお、ここでは、一例として、ナビゲーション装置１は入力デバイスとしてタッチパネルを備えているものとする。
【００７５】
図４は、地図情報格納部１０１に格納されている地図図柄情報の一例を示す図である。地図情報格納部１０１には、例えば、同様の地図図柄情報が複数格納されている。なお、ここでは、一例として、地図図柄情報には、予め、この地図図柄情報の中心位置が示す位置の緯度経度の座標が対応付けられているものとする。
【００７６】
図５は、地図情報格納部１０１に格納されている道路情報のうちのノードデータを管理するノード管理表である。ノード管理表は、各ノードデータの識別情報である「ノードＩＤ」と、ノードの示す緯度と経度である「緯度，経度」等の項目を有する。
【００７７】
図６は、地図情報格納部１０１に格納されている道路情報のうちのリンクデータを管理するリンク管理表である。リンク管理表は、各リンクデータの識別情報である「リンクＩＤ」と、リンクデータの両端のノードＩＤである「両端ノード」と、リンクのコストである「コスト」と、「道路名」等の項目を有する。リンクの「コスト」は、リンクの一以上の道路特性パラメータから決定された値である。ここでは、例えば、コストの値が小さいほど、リンクは、距離が短いと判断されるものとする。ここでは、説明のため、距離を示すコストを用いているが、どのような道路特性についてのコストを用いても良いし、複数のコストを用いるようにしても良い。複数のコストを用いて経路探索を行う処理等は公知である。「道路名」は、道路の識別情報であり、一の道路に複数のリンクが含まれる場合、ここでは一例として、これらのリンクの「道路名」の値は同じ値としている。ただし、同じ道路名の末尾等に、連結順番を示す番号等を追加しても良い。
【００７８】
図７は、図５および図６に示したノード管理表およびリンク管理表が管理するノード及びリンクの一部を、図４に示した地図上に配置した模式図である。
【００７９】
図８は、建物関連情報格納部１０２に予め格納されている建物関連情報を示す図である。建物関連情報は、「建物ＩＤ」と、「リンクＩＤ」と、「カテゴリー」という項目を有している。「建物ＩＤ」は、建物を識別する情報である。ここでは、建物に割り当てられたユニークな識別番号を用いているが、「建物ＩＤ」としては、建物名や、建物を利用するユーザ名（企業名や商店名、店舗名等）を用いても良い。「リンクＩＤ」は、建物が面している道路（ここではリンク）の識別情報であり、図６の「リンクＩＤ」に対応している。つまり、各建物は、「リンクＩＤ」が示すリンクの周辺の建物である。「カテゴリー」は、建物の属するカテゴリーを示すカテゴリー名である。一の建物が複数のカテゴリーに属している場合、ここでは、「カテゴリー」項目のカテゴリー名は、「，（コンマ）」で区切って示されている。なお、一の建物が属しているカテゴリー同士は、ここでは、階層関係を有していても良いものとする。
【００８０】
ここで、まず、ユーザが、経路探索を行うために、ナビゲーション装置１のタッチパネルを操作して、出力部１０７に現在地の周辺領域の所望の縮尺の地図を表示させたとする。そして、ユーザが、タッチパネルを操作して出発地Ｓと目的地Ｐとを、表示されている地図上で指定したとする。ここでは、具体的には、出発地Ｓと、目的地Ｐを地図が表示されている画面上でタップしたとすると、このタップされた地点が、それぞれ出発地Ｓと目的地Ｐに指定される。タップとは、タッチパネルを軽く叩くことである。なお、予め、ＧＰＳ受信機等が受信した出発地が出発地Ｓとして地図上に指定されているようにしても良い。
【００８１】
図９は、現在地を中心とした地図において、出発地Ｓと目的地Ｐとを指定した状態の表示例を示す図である。この地図は、図４の地図の一部であるとする。出発地Ｓおよび目的地Ｐに指定された箇所には、例えば、予め指定されたマーク８１およびマーク８２等が表示される。また、図９に示した地図の画面の下部には、建物条件を選択する複数のボタン９１〜９３と、経路探索を開始するための「経路探索開始」ボタン９５が配置されているものとする。
【００８２】
次に、ユーザは、図９に示した地図の画面の下部に配置されている建物条件を選択するボタンの中から、「店舗」というボタン９１を押したとする。
【００８３】
そして、ユーザが、経路探索開始ボタン９５を押したとする。これにより、受付部１０３は、地図上で指定された出発地Ｓと目的地Ｐとを示す出発地情報および目的地情報を取得する。ここでは、例として、受付部１０３は、地図上で指定された出発地および目的地に最も距離が近いノードの「ノードＩＤ」を出発地情報および目的地情報として取得するものとする。ここでは、例として、出発地Ｓが最も近いノードが、「ノードＩＤ」が「Ｎ１」であるノードであり、目的地Ｐが最も近いノードが、「ノードＩＤ」が「Ｎ７」であるノードあったとすると、出発地情報として「Ｎ１」、目的地情報として「Ｎ７」をそれぞれ取得する。なお、以下、「ノードＩＤ」が「Ａ」（ただし、Ａは任意の文字列であるとする）であるノードを、ノード「Ａ」と呼ぶ。なお、出発地情報や目的地情報は、ユーザにより出発地や目的地に指定された位置に相当する道路上の位置を特定可能な情報であればよい。このような道路上の位置を示す情報は、リンクを示すリンク識別情報であっても良いし、道路上の座標であってもよい。なお、この位置の情報はどのように取得しても良い。また、出発地情報や目的地情報として、ユーザの指定した位置の座標を用いるようにして、後述する経路探索部１０５が経路を探索する際に、出発地情報や目的地情報に相当する道路上の位置や、ノードやリンクを検出して、これらを用いて、経路探索を行うようにしてもよい。
【００８４】
また、条件受付部１０４は、ボタン９１が押されていたため、カテゴリーが「店舗」である建物を指定する条件を受け付ける。ここで、カテゴリーが「店舗」である建物とは、建物関連情報の「カテゴリー」に含まれ得るカテゴリーのうちの、いずれかのカテゴリーに属する建物であることが予め指定されているものとする。このため、カテゴリーが「店舗」である建物こという条件は、建物関連情報において、１以上のカテゴリーと対応付けられている建物を指定する条件となる。つまり、ここでは、全てのカテゴリーをＯＲ条件で指定する条件と考えて良い。
【００８５】
次に、経路探索部１０５は、経路探索の処理を行う。ここでは、まず、図６に示したリンク管理表から、現在の地図に表示されている領域内のリンクについてのリンクデータをメモリ等に読み出す。ここでは、「リンクＩＤ」が「Ｌ１」〜「Ｌ８」等のリンクデータが読み出される。同様に、現在の地図に表示されている領域内のノードについてのノードデータを図５に示したノード管理表からメモリ等に読み出す。なお、目的地を含む地図情報と、出発地を含む地図情報と、その間の地図情報とにそれぞれ対応付けられているノードデータを読み出すようにしてもよい。この場合においては、目的地と出発地を含む地図を示す地図情報に対応付けられているリンクデータ等を読み出してもよい。
【００８６】
ここで、経路探索部１０５は、まず、図９に示した現在の地図に表示されている領域の各リンクについての重み付け値を取得する処理を行う。
【００８７】
経路探索部１０５は、上記で読み出したリンクデータが示す「リンクＩＤ」のうちの一の「リンクＩＤ」を取り出す。ここでは、まず、「Ｌ１」を取り出したとする。そして、この「リンクＩＤ」を有する建物管理情報のレコードを、メモリ等に図８に示した建物管理情報から読み出す。例えば、ここでは、「リンクＩＤ」が「Ｌ１」である１以上のレコードが建物管理情報から読み出される。ここでは、例えば、経路探索部１０５は、「リンクＩＤ」が「Ｌ１」であるレコードとして、「建物ＩＤ」が「６０００１１」から「６０００２９」である１９個のレコードを読み出したとする。
【００８８】
次に、経路探索部１０５は、読み出した「リンクＩＤ」が「Ｌ１」である建物管理情報の１以上のレコードの中から、建物条件を満たす建物を検出し、検出した建物の数をカウントする。ここでは、条件受付部１０４が受け付けた建物条件が「店舗」を指定する条件、即ち、全てのカテゴリーの建物を指定する条件であるため、読み出した建物管理情報のレコードに含まれる建物の数を、「建物ＩＤ」が同じ建物を重複してカウントしないようにしてカウントする。カウントによって得られた値は、「１９」であったとする。このため、経路探索部１０５は、リンク「Ｌ１」の周辺の、建物条件を満たす建物の集計数を示す情報として「１９」を取得する。
【００８９】
図１０は、重み付け値格納部１０６に格納されている重み付け値を管理する重み付け値管理情報を示す図である。重み付け値管理情報は、「建物数」と、「重み付け値」という項目を有している。「建物数」は、建物条件を満たす建物数の範囲を示す値である。「重み付け値」は、重み付け値である。なお、重み付け管理情報は、建物条件別に用意されていても良い。
【００９０】
次に、経路探索部１０５は、リンク「Ｌ１」について取得した集計数を示す情報「１９」を用いて、リンク「Ｌ１」についての重み付け値を取得する。ここでは、図１０に示す重み付け管理情報から、「建物数」の値が、取得した集計数を示す情報である「１９」を含む範囲を示すレコードを検出し、検出したレコードの「重み付け値」を取得する。ここでは、集計数「１９」は、上から５番目のレコードの「１５以上２５未満」の範囲となるため、経路探索部１０５は、このレコードの重み付け値「０．９」を取得する。そして、取得した重み付け値「０．９」を、リンク「Ｌ１」の「リンクＩＤ」である「Ｌ１」と対応付けて、図示しない記憶媒体に蓄積する。
【００９１】
同様にして、経路探索部１０５は、上記でリンク管理表から読み出したリンクデータのうちの、「リンクＩＤ」が「Ｌ１」でないリンクデータからも、順次、「リンクＩＤ」を取り出して、上記と同様の処理を行って重み付け値を取得し、取得した情報を「リンクＩＤ」と対応付けて図示しない記憶媒体値に蓄積する。
【００９２】
図１１は、経路探索部１０５がリンクＩＤ別に取得した重み付け値を管理する取得重み付け値管理表を示す図である。取得重み付け管理表は、「リンクＩＤ」と「重み付け値」とを有する。「リンクＩＤ」は、図６の「リンクＩＤ」に対応する。「重み付け値」は、各「リンクＩＤ」が示すリンクについて取得された重み付け値である。
【００９３】
次に、経路探索部１０５は、上記でリンク管理表から読み出したリンクデータ及びノードデータを用いて、出発地であるノード「Ｎ１」から、目的地であるノード「Ｎ７」までの経路（ここでは例として一の経路）を探索する。経路を探索する際には、図６に示したリンク管理表の各リンクに対応する「コスト」の値を、図１１に示した取得重み付け値管理表の各リンクに対応する「重み付け値」の値で補正した補正コストを、各リンクのコストとして用いて、ダイクストラ法等によりコストが最も小さくなる経路の探索を行う。
【００９４】
例えば、リンク「Ｌ１」のコストは図６より「１４」であり、リンクＩＤ「Ｌ１」に対応する「重み付け値」は、図１１より「０．９」であるため、補正コストは、「１２．６」となる。また、同様に、リンク「Ｌ２」のコストは、図６より「１６」であり、リンクＩＤ「Ｌ２」に対応する「重み付け値」は、図１１より「０．８」であるため、補正コストは、「１２．６」となる。このような補正コストを用いて経路探索を行う。なお、補正コストを用いた経路探索の処理等については公知の技術であるので、ここでは詳細な説明は省略する。
【００９５】
ここでは、経路探索部１０５による経路検索の結果、例えば、ノード「Ｎ１」、リンク「Ｌ１」、ノード「Ｎ２」、リンク「Ｌ２」、ノード「Ｎ４」、リンク「Ｌ５」、ノード「Ｎ５」、リンク「Ｌ７」、ノード「Ｎ７」の順番で、リンク及びノードをたどる経路を示す経路情報が取得されたとする。
【００９６】
図１２は、道路情報が示すリンク及びノードと、補正コストとの関係を模式的に示した図である。図において括弧内は各リンクの補正コストを示す。この図に示すように、ノード「Ｎ１」からノード「Ｎ７」までの経路としては、経路情報が示す経路で利用するリンクの補正コストの合計が、最も小さくなっている。
【００９７】
そして、出力部１０７は、最初に表示されている地図において、経路探索部１０５が取得した経路情報が示すノードおよびリンク上に、予め指定された色の線を配置した地図の画像を新たに生成して、経路探索結果としてモニタ等に表示する。
【００９８】
図１３は、出力部１０７による経路の探索結果の表示例である。
【００９９】
このようにして、ナビゲーション装置１は、目的地までの途中に比較的に店舗が多い経路をユーザに示すことができる。
【０１００】
ここで、ユーザが、建物条件を選択する複数のボタン９１〜９４のうちの「店舗」というボタン９１を押す代わりに、「レストラン」というボタン９２を押したとし、これにより、条件受付部１０４は、カテゴリーが「レストラン」である建物を指定する条件を受け付けたとする。
【０１０１】
この場合、経路探索部１０５が、現在の地図に表示されている領域の各リンクについての重み付け値を取得する処理は、例えば、以下のように行われる。
【０１０２】
経路探索部１０５は、上記と同様に、現在の地図に表示されている各リンクについて読み出したリンクデータが示す「リンクＩＤ」のうちの一の「リンクＩＤ」として「Ｌ１」を取り出したとする。そして、「リンクＩＤ」が「Ｌ１」である１以上のレコードを図８に示した建物管理情報から読み出す。ここでは、「建物ＩＤ」が「６０００１１」から「６０００２９」である１９個のレコードを読み出したとする。
【０１０３】
次に、経路探索部１０５は、読み出した「リンクＩＤ」が「Ｌ１」である建物管理情報の１以上のレコードの中から、建物条件を満たす建物を検出し、検出した建物の数をカウントする。ここでは、条件受付部１０４が受け付けた建物条件が「レストラン」を指定する条件であり、「店舗」のように、全てのカテゴリーの建物を指定するための予め指定された条件でないため、読み出した建物管理情報のレコードの中から、「カテゴリ−」に、「レストラン」と一致する文字列を含むレコードを検出する。例えば、ここでは、「建物ＩＤ」が「６０００１１」、「６０００１４」、「６０００２９」であるレコードが検出されたとする。そして、経路探索部１０５は、検出されたレコードに含まれる建物の数を、「建物ＩＤ」が同じ建物を重複してカウントしないようにしてカウントする。この場合のカウントによって得られた値は、「３」である。このため、経路探索部１０５は、リンク「Ｌ１」の周辺の、建物条件を満たす建物の集計数を示す情報として「３」を取得する。
【０１０４】
そして、上記と同様に、図１０に示した重み付け値管理情報を用いて、リンク「Ｌ１」についての重み付け値として、「１．２」を取得し、この重み付け値を、リンク「Ｌ１」の「リンクＩＤ」である「Ｌ１」と対応付けて図示しない記憶媒体に蓄積する。
【０１０５】
その後は、現在の地図に表示されている領域の他のリンクについても、同様に重み付け値を取得する。その後の、重み付け値を乗算して得られる補正コストを用いて経路の探索を行う処理等については、建物条件が「店舗」である場合と同様であるので、ここでは、説明を省略する。
【０１０６】
このような場合においては、ナビゲーション装置１は、目的地までの途中に比較的にレストランが多い経路をユーザに示すことができる。
【０１０７】
また、ユーザが、建物条件を選択する複数のボタン９１〜９４のうちの「レストラン」というボタン９２を押す代わりに、「ショッピング」というボタン９３を押し、これにより、条件受付部１０４は、カテゴリーが「ショッピング」である建物を指定する条件」を受け付けた場合において経路探索部１０５が行う処理も、上記において、「カテゴリー」に「レストラン」と一致する文字列を含むレコードを検出する代わりに、「カテゴリー」に「ショッピング」と一致する文字列を含むレコードを検出する点が異なることを除けば、「レストラン」というボタン９２を押した場合と同様である。
【０１０８】
このような場合においては、ナビゲーション装置１は、目的地までの途中に比較的にショッピングに適した店舗が多い経路をユーザに示すことができる。
【０１０９】
なお、図８に示したような建物管理情報を建物関連情報格納部１０２に格納しておく代わりに、図１４に示すような、地図情報に含まれる各リンクのリンク識別情報である「リンクＩＤ」と、このリンクの周辺の建物の属するカテゴリーのカテゴリー名を示す「カテゴリー」と、対応する「リンクＩＤ」が示すリンク周辺の「カテゴリー」が示すカテゴリーに属する建物の数を集計（合計）した値である「集計数」とを有する建物管理情報を格納しておくようにしても良い。「カテゴリー」の値のうちの「全カテゴリー」とは、１以上のカテゴリーに属する建物の数を合計した値で、建物条件が、「店舗」である場合に、このレコードが利用される。この建物管理情報は、例えば、図８に示した建物管理情報の、「リンクＩＤ」が同一であって、なおかつ「カテゴリー」に同じカテゴリー名を含むレコードの数を、「リンクＩＤ」とカテゴリー名との組合せごとにカウントすることで得ることができる。このような建物管理情報を用いることで、リンク毎に、リンク周辺の建物条件を満たす建物の集計数を示す情報を取得する際は、「リンクＩＤ」と「カテゴリー」の値が、重み付け値の取得対象となるリンクのリンク識別情報と、建物条件が示すカテゴリーとにそれぞれ一致するレコードの「集計数」の値を取得すればよくなる。この結果、図８に示したような建物管理情報を用いる場合のように、建物条件を満たす建物を検出してカウントする処理を省略して、経路探索の処理を高速化することができる。
【０１１０】
以上、本実施の形態によれば、建物関連情報と建物条件とを用いて、周辺に建物条件を満たす建物が多い経路が探索されやすくなるようにして、経路を探索するようにしたことにより、ユーザの望む建物の数を考慮した最適な経路探索を行うことができる。
【０１１１】
なお、本実施の形態において、上述したような建物関連情報の代わりに、地図情報が示す各道路（例えばルート）についての、建物のカテゴリー別の重み付け値を有する建物関連情報を用いるようにしても良い。このカテゴリー別の重み付け値は、例えば、予め用意された各道路の周辺のカテゴリー別の建物数を示す情報のそれぞれについて、上記の経路探索部１０５が重み付け値格納部１０６等を用いてカテゴリー別の重み付け値を取得する処理と同様の処理を行うことで取得可能である。このような建物関連情報を用いることで、各道路についての建物条件が示すカテゴリーに対応する重み付け値を、高速に取得することが可能となる。例えば、この重み付け値は、上記の具体例において図１１に示した取得重み付け値管理表で管理される重み付け値を、様々な複数のカテゴリーについて取得したものと考えても良い。あるいは、カテゴリー別の重み付け値の代わりに、条件受付部１０４が受け付けうる建物条件別の重み付け値を有する建物関連情報を用いるようにしても良い。
【０１１２】
（実施の形態２）
図１５は、本実施の形態におけるナビゲーション装置２のブロック図である。
【０１１３】
ナビゲーション装置２は、地図情報格納部２０１、建物関連情報格納部１０２、受付部１０３、条件受付部１０４、経路探索部２０５、重み付け値格納部１０６、出力部１０７、予定時間受付部２０８、および利用時間格納部２０９を備える。
【０１１４】
建物関連情報格納部１０２、受付部１０３、条件受付部１０４、重み付け値格納部１０６、出力部１０７の構成については、上記実施の形態１と同様であるのでここでは詳細な説明は省略する。
【０１１５】
予定時間受付部２０８は、出発地から目的地に到着するまでの予定時間を、ユーザ等から受け付ける。なお、予定時間受付部２０８は、結果的に予定時間を受け付けることができれば、どのように予定時間を受け付けても良い。例えば、予定時間受付部２０８は、出発予定時刻と到着予定時刻との入力を受け付け、この時刻の差を、予定時間として受け付けても良い。また、到着予定時刻の入力を受け付けるとともに、現在の時刻を時計等から取得して、この時刻の差を、予定時間として受け付けても良い。予定時間受付部２０８は、ここでの受付とは、例えば、入力手段からの受付や、他の機器等から送信される入力信号の受信や、記録媒体等からの情報の読み出し等である。予定時間の入力手段は、テンキーやキーボードやタッチパッドやマウスやメニュー画面によるもの等、何でも良い。予定時間受付部２０８は、テンキーやタッチパッドやキーボード等の入力手段のデバイスドライバーや、メニュー画面の制御ソフトウェア等で実現され得る。
【０１１６】
利用時間格納部２０９には、建物の利用に要する時間の情報である利用時間が格納されている。建物の利用に要する時間は、例えば、建物を通常の用途で利用した場合に要すると考えられる時間である。例えば、レストランであれば、利用時間は、食事に要する時間である。また、衣料品店等であれば、ショッピングに要する時間である。利用時間は、建物について個別に対応付けられていても良いし、建物のカテゴリーと対応付けられていても良い。この具体例においては、利用時間が、建物のカテゴリーと対応付けられて、利用時間格納部２０９に格納されている場合を例に挙げて説明する。利用時間格納部２０９は、不揮発性の記録媒体が好適であるが、揮発性の記録媒体でも実現可能である。
【０１１７】
地図情報格納部２０１には、地図情報格納部１０１と同様の地図情報が格納されている。ただし、地図情報格納部２０１に格納されている地図情報に含まれる道路情報は、道路情報は、各道路の移動に要する時間である移動時間を含んでいる。例えば、道路情報に含まれる各リンクデータが、このリンクの移動に要する移動時間と対応付けられている。この移動時間は、例えば、各リンクデータが有していてもよい。この移動時間を、上述した各リンクデータに含まれる時間についてのコストとしてもよいし、コストとは別に、移動時間を有していてもよい。移動時間は、移動手段別に用意されていても良い。なお、移動時間の代わりに、結果的に移動時間を算出可能な値が格納されている場合も、本実施の形態においては、移動時間が格納されていると考える。例えば、距離情報であれば、移動速度が取得できれば移動時間が算出可能であるので、距離情報がリンクに対応付けられている場合も、距離情報が対応付けられていると考えて良い。なお、移動速度は、例えば、ナビゲーション装置２を利用する際の移動手段の平均的な移動速度であっても良いし、ナビゲーション装置２が有する図示しない加速度センサ等のセンサを用いて取得される移動速度であっても良い。なお、地図情報格納部２０１のその他の構成等については、地図情報格納部１０１と同様である。
【０１１８】
経路探索部２０５は、上述した経路探索部１０５と同様に、道路情報と建物関連情報と建物条件とを用いて、周辺に建物条件を満たす建物が多い経路が探索されやすくなるようにして、出発地情報が示す出発地から、目的地情報が示す目的地までの経路を探索する。ただし、経路探索部２０５は、ここでは特に、このような経路であって、経路に含まれる道路の移動時間を用いて、予定時間受付部２０８が受け付けた予定時間以内の経路を探索する。さらには、経路に含まれる道路の移動時間と、これらの道路に対応する建物条件を満たす建物の利用時間とを用いて、予定時間受付部２０８が受け付けた予定時間以内の経路を探索する。
【０１１９】
例えば、経路探索部２０５は、まず、経路探索部１０５と同様に一の経路を候補として探索する。そして探索した経路についての、出発地から目的地までの所要時間を算出する。所要時間は、例えば、経路に含まれる各道路の移動時間の合計と、経路に含まれる道路（リンク）に対応する建物のうちの、建物条件を満たす建物の利用時間の合計とを用いて算出される。または、所要時間として、経路に含まれる各道路の移動時間の合計を用いても良い。そして、所要時間が、予定時間受付部２０８が受け付けた予定時間以内であれば、この経路の候補を、最終的な経路に決定し、経路情報を取得する。経路が予定時間以内であれば、現在の経路とは異なる経路を更に候補として探索し、同様の処理を、経路が決定されるまで繰り返すことで、経路を探索する。各道路に対応づけられた建物や建物数は、建物関連情報を用いて取得可能である。
【０１２０】
または、経路探索部２０５は、まず、経路探索部１０５と同様に複数の経路を候補として探索する。そして、複数の経路の候補について、経路探索の際に得られたコストの値が小さいものから順に、上記と同様に、所要時間を算出して、所要時間が予定時間内であるか否かを判断していき、予定時間以内である候補を、最終的な経路に決定しても良い。
【０１２１】
あるいは、経路探索部２０５は、経路探索部１０５と同様に複数の経路を候補として探索し、これにより得られた複数の経路の候補について、それぞれ、上記と同様に、所要時間を算出して、所要時間が予定時間内であるか否かを判断していき、予定時間以内である候補の全て、あるいは一部を、最終的な経路に決定しても良い。
【０１２２】
各道路の移動時間は、例えば、道路情報から各道路（リンク）に対応する移動時間を読み出すことで取得できる。
【０１２３】
各建物の利用時間は、例えば、利用時間格納部２０９に格納されている各建物に対応する利用時間、あるいは、各建物のカテゴリーに対応する利用時間を読み出すことで取得可能である。例えば、リンクに対応する各建物に対応づけられた利用時間や、各建物に対応するカテゴリーに対応づけられた利用時間を、経路探索部１０５が利用時間格納部２０９から取得しても良い。また、建物条件が示すカテゴリーと対応する建物の利用時間として、この建物条件が示すカテゴリーと対応づけられて利用時間格納部２０９に格納されている利用時間を取得するようにしてもよい。例えば、建物条件が、「衣料品店」というカテゴリーを指定する条件であったとすると、リンクに対応する建物条件を満たす各建物についての利用時間としては、この建物条件が示すカテゴリーと対応づけられて利用時間格納部２０９に格納されている利用時間「１５分」を取得するようにしてもよい。なお、経路に含まれる各道路に対応する建物条件を満たす建物の全ての利用時間を合計しなくても良い。例えば、予め、カテゴリー別に、利用時間を取得する建物数の上限等を指定しておくようにし、この指定された範囲の建物数だけ、建物の利用時間を取得して合計しても良い。例えば、カテゴリー「レストラン」については、上限を「１」に設定しておくようにして、経路上にカテゴリーが「レストラン」である建物が２以上あったとしても、上限までの数の建物についての利用時間、ここでは、１つの建物についての利用時間しか取得しないようにしても良い。同様に、例えば、カテゴリー「ショッピング」については、上限を「５」に設定しておくようにして、経路上にカテゴリーが「ショッピング」である建物が５以上あったとしても、上限までの数の建物についての利用時間、ここでは、５つの建物についての利用時間しか取得しないようにしても良い。
【０１２４】
なお、経路探索部２０５のその他の構成等については、経路探索部１０５の構成等と同様であるので、ここでは詳細な説明は省略する。
【０１２５】
図１６は、本実施の形態２のナビゲーション装置２の動作の一例を示すフローチャートである。以下、図１６を用いて動作について説明する。なお、図１６において、図２と同一符号は同一または相当するステップを示している。
【０１２６】
（ステップＳ１６０１）予定時間受付部２０８は、予定時間を受け付けたか否かを判断する。受け付けた場合、ステップＳ２０３に進み、受け付けていない場合、ステップＳ１６０１に戻る。
【０１２７】
（ステップＳ１６０２）経路探索部２０５は、ステップＳ２０３で読み出したリンクデータおよびノードデータを含む道路データと、ステップＳ２０８で取得した重み付け値とを用いて複数経路の探索を行う。具体的には、各リンクに対応するコストに、各リンクに対応した重み付け値を乗算して得られた補正コストを、各リンクのコストとして用いて、ステップＳ２０１で受け付けた出発値情報が示す出発地から、目的地情報が示す目的地までの複数の経路の探索を行う。
【０１２８】
（ステップＳ１６０３）経路探索部２０５は、カウンターｍに１を代入する。
【０１２９】
（ステップＳ１６０４）経路探索部２０５は、ステップＳ１６０２で探索した複数経路において、経路全体のコストの小さいｍ番目の経路があるか否かを判断する。ある場合、ステップＳ１６０５に進み、ない場合、ステップＳ１６０９に進む。
【０１３０】
（ステップＳ１６０５）経路探索部２０５は、ｍ番目の経路について、出発地から目的地までの所要時間を算出する。例えば、経路に含まれる各リンクに対応する移動時間の合計と、各リンクに対応する建物条件を満たす建物のすべて、あるいは一部の利用時間の合計とを合わせた時間を、所要時間として算出する。
【０１３１】
（ステップＳ１６０６）経路探索部２０５は、ステップＳ１６０５で取得したｍ番目の経路についての所要時間が、ステップＳ１６０１で受け付けた予定時間以内であるか否かを判断する。予定時間以内であればステップＳ１６０７に進み、予定時間を超える場合は、ステップＳ１６０９に進む。
【０１３２】
（ステップＳ１６０７）経路探索部２０５は、ｍ番目の経路についての経路情報を取得する。そして、ステップＳ２１２に進む。
【０１３３】
（ステップＳ１６０８）経路探索部２０５は、カウンターｍの値を１インクリメントする。そして、ステップＳ１６０４に戻る。
【０１３４】
（ステップＳ１６０９）経路探索部２０５は、エラー出力を行う。例えば、所要時間が予定時間以内の経路が探索できなかったことを示す情報を出力する。そして、ステップＳ２０１に戻る。
【０１３５】
なお、図１６のフローチャートにおいて、電源オフや処理終了の割り込みにより処理は終了する。
【０１３６】
以下、本実施の形態２の具体例について説明する。ナビゲーション装置２の概念図等は、図３と同様である。地図情報格納部２０１に格納されている地図図柄情報は、図４と同様であるとする。また、道路情報のノード管理表や、建物関連情報は、図５や、図８と同様であるとする。
【０１３７】
図１７は、地図情報格納部２０１に格納されている道路情報のうちのリンクデータを管理するリンク管理表である。このリンク管理表は、図６に示したリンク管理表において、リンクデータが有する各リンクの移動時間を管理する「移動時間」という項目を追加したものである。なお、この移動時間を、リンクにおける時間のコストと、経路の探索に利用しても良い。
【０１３８】
なお、図５および図１７に示したノード管理表およびリンク管理表が管理するノード及びリンクの位置関係は、ここでは、図７と同様であるとする。
【０１３９】
まず、ユーザが、上記実施の形態１の具体例と同様に、図９に示すような入力画面から、出発地と目的地とを入力し、さらに、建物条件を指定するボタンを押した後に、「経路探索開始」９５を押したとする。ここでは、ユーザが、目的地に着くまでに、食事とショッピングを済ませたいと考えて、建物条件を指定するボタンとして、「レストラン」のボタン９２と、「ショッピング」というボタン９３を押したとする。
【０１４０】
受付部１０３は、地図上で指定された出発地Ｓと目的地Ｐとを示す出発地情報を取得する。また、条件受付部１０４は、カテゴリーが「レストラン」または「ショッピング」である建物を指定する建物条件を受け付ける。
【０１４１】
さらに、ナビゲーション装置２のモニタには、図１８に示すように、ユーザが、出発地から目的地まで移動する際にかけても良い予定時間の入力画面が表示される。ここで、例えば、ユーザが予定時間として、「１２０」分を入力して、「ＯＫ」ボタン１８０を押したとすると、予定時間受付部２０８が予定時間「１２０」分を受け付ける。
【０１４２】
次に、経路探索部２０５は、道路情報と、建物条件と、建物関連情報とを用いて、複数の経路を探索する。ここでは、リンクに対応する、カテゴリーが「レストラン」または「ショッピング」である建物の数を、建物関連情報を用いて取得し、各リンクのコストを、この建物の数に応じて取得した重み付け値を用いて補正したコストを用いて、ダイクストラ法等のリンクのコストを利用する経路探索アルゴリズム等により複数の経路を探索する。なお、探索する経路数は問わない。
【０１４３】
ここでは、仮に、デフォルトで指定された数である３つの経路が探索されたとする。３つの経路は、図１９に示すように、出発地からリンク「Ｌ１」、リンク「Ｌ２」、リンク「Ｌ５」、リンク「Ｌ７」の順にリンクをたどって目的地に到達する経路１９１と、出発地からリンク「Ｌ１」、リンク「Ｌ２」、リンク「Ｌ６」、リンク「Ｌ８」の順にリンクをたどって目的地に到達する経路１９２と、出発地からリンク「Ｌ３」、リンク「Ｌ４」、リンク「Ｌ５」、リンク「Ｌ７」の順にリンクをたどって目的地に到達する経路１９３とが探索されたとする。経路１９１、経路１９２、および経路１９３の、経路全体の補正コストの合計は、それぞれ、仮に、「４５」、「４９」、「５４」であったとする。
【０１４４】
次に、経路探索部２０５は、補正コストの値が最も小さい経路１９１について、所要時間を算出する。具体的には、経路１９１に含まれる各リンクに対応する移動時間を、図１７に示したリンク管理表から取得する。例えば、リンク「Ｌ１」、リンク「Ｌ２」、リンク「Ｌ５」、リンク「Ｌ７」にそれぞれ対応する移動時間（分）として、「１２」、「１５」、「７」、「６」を取得する。そしてこれらを合計して、合計移動時間「４０」分を取得する。また、経路に含まれるすべてのリンクに対応する建物のうちの、建物条件を満たす建物、即ち、カテゴリーが「レストラン」または「ショッピング」である建物の利用時間の合計を、利用時間格納部２０９に、建物のカテゴリーと対応づけて格納されている利用時間を用いて取得する。
【０１４５】
図２０は、利用時間格納部２０９に格納されている利用時間を管理する利用時間管理表である。利用時間管理表は、「カテゴリー」と「利用時間」という項目を有している。「カテゴリー」は、カテゴリー名である。「利用時間」は、対応するカテゴリーに属する建物の利用時間である。
【０１４６】
図２１は、利用時間を追加する建物数のカテゴリー別の上限を管理する上限管理表である。上限管理表は、例えば、利用時間格納部２０９等に格納されている。上限管理表は、「カテゴリー」と「上限数」という項目を有している。「カテゴリー」は、カテゴリー名である。「上限数」は、一の経路において、利用時間の追加対象とすることができる建物数の上限である。
【０１４７】
経路探索部２０５は、建物条件が示すカテゴリーの一つが「レストラン」であるため、経路１９１に含まれるすべてのリンクに対応するカテゴリーが「レストラン」である建物を検出し、その合計数を取得する。合計数は、ここでは、「７」であったとする。次に、このカテゴリー「レストラン」に対応する「上限数」である「１」を、図２１の上限管理表から取得し、経路１９１から取得したカテゴリーが「レストラン」である建物の合計数「７」が上限数を超えたか否かを判断する。ここでは、上限数を超えているため、上限数である「１」を、経路１９１に含まれるリンクに対応する、カテゴリーが「レストラン」である建物の数として取得する。なお、上限数を超えていなければ、経路１９１に含まれるすべてのリンクに対応するカテゴリーが「レストラン」である建物の数をそのまま取得する。また、図２０で示した利用時間管理表から、「カテゴリー」が「レストラン」であるレコードの「利用時間」の値「３０」を取得する。そして、この値と、上記で取得した建物数「１」とを乗算して、経路１９１におけるカテゴリーが「レストラン」である建物の利用時間「３０」分を取得する。同様に、経路１９１について、カテゴリーが「ショッピング」である建物数を取得し、この建物数が、カテゴリー「ショッピング」の上限数である「５」を超えたか否かを判断する。ここでは、経路１９１における建物数が「８」であったとすると、上限数を超えているため、この上限数「５」を、経路１９１に含まれるリンクに対応する、カテゴリーが「ショッピング」である建物の数として取得する。そして、この値に、「カテゴリー」が「ショッピング」であるレコードの「利用時間」の値「１５」を乗算して、経路１９１におけるカテゴリーが「ショッピング」である建物の利用時間「７５」分を取得する。
【０１４８】
そして、上記で取得した経路１９１の合計移動時間「４０」分と、建物の利用時間である「３０」分と、「７５」分の合計である「１４５」分を取得し、この時間が予定時間である「１２０」分以内であるか否かを判断する。ここでは、予定時間以内でないため、経路探索部２０５は、この経路を採用しないことを判断する。
【０１４９】
つぎに、経路探索部２０５は、コストが２番目に小さい経路１９２について、同様の処理を行って所要時間を取得する。合計移動時間は、「３６」分となる。また、カテゴリーが「レストラン」の建物数は、上限数を超えており、カテゴリーが「レストラン」の建物の利用時間としては「３０」分が取得されたとする。また、カテゴリーが「ショッピング」の建物数は「２」であり、上限数を超えておらず、カテゴリーが「ショッピング」の建物の利用時間としては２×１５＝３０となり、「３０」分が取得されたとする。これにより、経路１９２の所要時間は、「９６」分となり、予定時間以内であると判断される。
【０１５０】
このため、経路探索部２０５は、この経路１９２の経路情報を取得する。そして、出力部１０７はこの経路情報が示すノードおよびリンク上に、予め指定された色の線を配置した地図の画像を生成して、経路探索結果としてモニタ等に表示する。
【０１５１】
図２２は、出力部１０７による経路探索結果の表示例を示す図である。
【０１５２】
以上、本実施の形態によれば、上記実施の形態１と同様の効果を奏するとともに、ユーザが指定した予定時間内に目的地に到着可能な経路を出力することができる。これにより、ユーザの要望に添った、いわば寄り道が可能な経路を提示することが可能となる。
【０１５３】
なお、上記各実施の形態において、建物関連情報は、建物についての位置情報を有していてもよく、この位置情報を用いて、探索された経路に対応付けられている、建物条件が示す条件を満たす建物の位置情報が示す地図上の位置に、図２３に示すように、建物についてのアイコンを表示しても良い。このアイコンは、建物のカテゴリーに対応して予め用意されたアイコンであっても良いし、建物関連情報に、建物の識別情報と対応付けて予め格納されているアイコンが表示されても良い。また、建物の識別情報を、そのまま、アイコンとして表示しても良い。なお、図２３は、レストランのアイコン２１０と、ショッピングのアイコン２１１が地図上に表示されている例を示す。
【０１５４】
なお、上記各実施の形態におけるナビゲーション装置を実現するソフトウェアは、以下のようなプログラムである。つまり、このプログラムは、地図に関する情報であって、地図が示す道路に関する情報である道路情報を有する地図情報が格納される地図情報格納部と、地図情報が示す各道路についての、周辺の建物に関する情報である建物関連情報が格納される建物関連情報格納部とにアクセス可能なコンピュータを、出発地を示す情報である出発地情報と、目的地を示す情報である目的地情報を受け付ける受付部と、建物についての条件である建物条件を受け付ける条件受付部と、道路情報と建物関連情報と建物条件とを用いて、周辺に建物条件を満たす建物が多い経路が探索されやすくなるようにして、出発地情報が示す出発地から、目的地情報が示す目的地までの経路を探索する経路探索部と、探索部の探索結果に応じた出力を行う出力部として機能させるためのプログラムである。
【０１５５】
なお、上記プログラムにおいて、上記プログラムが実現する機能には、ハードウェアでしか実現できない機能は含まれない。例えば、情報を取得する取得部や、情報を出力する出力部などにおけるモデムやインターフェースカードなどのハードウェアでしか実現できない機能は、上記プログラムが実現する機能には含まれない。
【０１５６】
図２４は、上記プログラムを実行して、上記実施の形態によるナビゲーション装置を実現するコンピュータの外観の一例を示す模式図である。上記実施の形態は、コンピュータハードウェア及びその上で実行されるコンピュータプログラムによって実現されうる。
【０１５７】
図２４において、コンピュータシステム９００は、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）ドライブ９０５、ＦＤ（Ｆｌｏｐｐｙ（登録商標）  Ｄｉｓｋ）ドライブ９０６を含むコンピュータ９０１と、キーボード９０２と、マウス９０３と、モニタ９０４とを備える。
【０１５８】
図２５は、コンピュータシステム９００の内部構成を示す図である。図２５において、コンピュータ９０１は、ＣＤ−ＲＯＭドライブ９０５、ＦＤドライブ９０６に加えて、ＭＰＵ（Ｍｉｃｒｏ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）９１１と、ブートアッププログラム等のプログラムを記憶するためのＲＯＭ９１２と、ＭＰＵ９１１に接続され、アプリケーションプログラムの命令を一時的に記憶すると共に、一時記憶空間を提供するＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９１３と、アプリケーションプログラム、システムプログラム、及びデータを記憶するハードディスク９１４と、ＭＰＵ９１１、ＲＯＭ９１２等を相互に接続するバス９１５とを備える。なお、コンピュータ９０１は、ＬＡＮへの接続を提供する図示しないネットワークカードを含んでいてもよい。
【０１５９】
コンピュータシステム９００に、上記実施の形態によるナビゲーション装置等の機能を実行させるプログラムは、ＣＤ−ＲＯＭ９２１、またはＦＤ９２２に記憶されて、ＣＤ−ＲＯＭドライブ９０５、またはＦＤドライブ９０６に挿入され、ハードディスク９１４に転送されてもよい。これに代えて、そのプログラムは、図示しないネットワークを介してコンピュータ９０１に送信され、ハードディスク９１４に記憶されてもよい。プログラムは実行の際にＲＡＭ９１３にロードされる。なお、プログラムは、ＣＤ−ＲＯＭ９２１やＦＤ９２２、またはネットワークから直接、ロードされてもよい。
【０１６０】
プログラムは、コンピュータ９０１に、上記実施の形態によるナビゲーション装置の機能を実行させるオペレーティングシステム（ＯＳ）、またはサードパーティプログラム等を必ずしも含んでいなくてもよい。プログラムは、制御された態様で適切な機能（モジュール）を呼び出し、所望の結果が得られるようにする命令の部分のみを含んでいてもよい。コンピュータシステム９００がどのように動作するのかについては周知であり、詳細な説明は省略する。
【０１６１】
本発明は、以上の実施の形態に限定されることなく、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【産業上の利用可能性】
【０１６２】
以上のように、本発明にかかるナビゲーション装置等は、経路を探索可能なナビゲーション装置等として適しており、特に、ユーザの要望に添った経路を探索するナビゲーション装置等として有用である。
【符号の説明】
【０１６３】
１、２  ナビゲーション装置
１０１、２０１  地図情報格納部
１０２  建物関連情報格納部
１０３  受付部
１０４  条件受付部
１０５、２０５  経路探索部
１０６  重み付け値格納部
１０７  出力部
２０８  予定時間受付部
２０９  利用時間格納部
【図１】
0005734036.tif 000002
【図２】
0005734036.tif 000003
【図３】
0005734036.tif 000004
【図４】
0005734036.tif 000005
【図５】
0005734036.tif 000006
【図６】
0005734036.tif 000007
【図７】
0005734036.tif 000008
【図８】
0005734036.tif 000009
【図９】
0005734036.tif 000010
【図１０】
0005734036.tif 000011
【図１１】
0005734036.tif 000012
【図１２】
0005734036.tif 000013
【図１３】
0005734036.tif 000014
【図１４】
0005734036.tif 000015
【図１５】
0005734036.tif 000016
【図１６】
0005734036.tif 000017
【図１７】
0005734036.tif 000018
【図１８】
0005734036.tif 000019
【図１９】
0005734036.tif 000020
【図２０】
0005734036.tif 000021
【図２１】
0005734036.tif 000022
【図２２】
0005734036.tif 000023
【図２３】
0005734036.tif 000024
【図２４】
0005734036.tif 000025
【図２５】
0005734036.tif 000026