(57)【要約】【課題】複数の行先施設を訪れる際にアクセスが良い施設を少ない計算コストで短時間に検索できる「施設検索装置および施設検索方法」を提供する。【解決手段】地図上で複数の行先施設の地点を含むエリアを指定するエリア指定部１３と、地図上において複数の施設が存在する地点の間の連結関係を表したグラフデータを記憶するグラフデータ記憶部１４と、指定エリア内のグラフデータに基づいて、指定エリア内に存在する各地点の媒介中心性を算出する媒介中心性算出部１５と、媒介中心性の値が所定の条件を満たす地点の施設を抽出する位置抽出部１６とを備え、指定されたエリア内に存在する各地点のうち、グラフデータで連結が示された地点を対象として媒介中心性を算出するだけで、複数の行先施設に対してアクセスの良い施設を検索することができるようにする。【選択図】図１
2018163407.tif 000002
【特許請求の範囲】
【請求項１】
地図上において複数の位置の間の連結関係を表したグラフデータを記憶するグラフデータ記憶部と、
上記地図上でエリアを指定するエリア指定部と、
上記エリア指定部により指定されたエリア内の上記グラフデータに基づいて、上記エリア指定部により指定されたエリア内に存在する各位置の媒介中心性を算出する媒介中心性算出部と、
上記媒介中心性算出部により算出された媒介中心性の値が所定の条件を満たす位置を抽出する位置抽出部と、
上記位置抽出部により抽出された位置に該当する施設を検索結果として提示する施設提示部とを備えたことを特徴とする施設検索装置。
【請求項２】
上記グラフデータ記憶部は、地図上において複数の地点の間の連結関係を表したグラフデータを記憶し、
上記エリア指定部は、上記地図上で複数の行先施設の地点を含むエリアを指定し、
上記媒介中心性算出部は、上記エリア指定部により指定されたエリア内の上記グラフデータに基づいて、上記エリア指定部により指定されたエリア内に存在する各地点の媒介中心性を算出し、
上記位置抽出部は、上記媒介中心性算出部により算出された媒介中心性の値が所定の条件を満たす地点を抽出し、
上記施設提示部は、上記位置抽出部により抽出された地点に該当する施設を上記検索結果として提示することを特徴とする請求項１に記載の施設検索装置。
【請求項３】
上記位置抽出部は、上記媒介中心性の値が上記所定の条件を満たす地点のうち、上記複数の行先施設の地点との距離が所定値未満である地点を抽出することを特徴とする請求項２に記載の施設検索装置。
【請求項４】
上記エリア指定部は、上記地図上で２つの行先施設の地点を含むエリアを指定し、
上記位置抽出部は、上記媒介中心性の値が上記所定の条件を満たす駐車場の地点を抽出することを特徴とする請求項２に記載の施設検索装置。
【請求項５】
上記エリア指定部は、上記地図上で３つ以上の行先施設の地点を含むエリアを指定し、
上記位置抽出部は、上記媒介中心性の値が上記所定の条件を満たす駐車場または駐車場付き行先施設の地点を抽出することを特徴とする請求項２に記載の施設検索装置。
【請求項６】
上記グラフデータ記憶部は、駐車場が存在する地点と上記駐車場以外の施設が存在する地点との間は連結させず、上記駐車場が存在する地点どうしの間を連結させた連結関係を表したグラフデータを記憶することを特徴とする請求項２に記載の施設検索装置。
【請求項７】
上記グラフデータ記憶部は、所定距離以内にある駐車場の地点どうしの間を連結させた連結関係を表したグラフデータを記憶することを特徴とする請求項６に記載の施設検索装置。
【請求項８】
上記グラフデータ記憶部は、駐車場が存在する地点と上記駐車場以外の施設が存在する地点との間は連結させず、上記駐車場および駐車場付き施設が存在する地点どうしの間を連結させた連結関係を表したグラフデータを記憶することを特徴とする請求項５に記載の施設検索装置。
【請求項９】
上記グラフデータ記憶部は、地図上において複数の区画の間の連結関係を表したグラフデータを記憶し、
上記エリア指定部は、上記地図上で複数の区画を含むエリアを指定し、
上記媒介中心性算出部は、上記エリア指定部により指定されたエリア内の上記グラフデータに基づいて、上記エリア指定部により指定されたエリア内に存在する各区画の媒介中心性を算出し、
上記位置抽出部は、上記媒介中心性算出部により算出された媒介中心性の値が所定の条件を満たす区画を抽出し、
上記施設提示部は、上記位置抽出部により抽出された区画の中で検索条件に合致する施設を検索し、当該検索した施設を上記検索結果として提示することを特徴とする請求項１に記載の施設検索装置。
【請求項１０】
上記施設の検索条件を入力する検索条件入力部を更に備え、
上記施設提示部は、上記位置抽出部により抽出された区画の中で、上記検索条件入力部により入力された上記検索条件に合致する施設を検索し、当該検索した施設を上記検索結果として提示することを特徴とする請求項９に記載の施設検索装置。
【請求項１１】
上記区画は、交差点および道路によって区割りされる領域であることを特徴とする請求項９に記載の施設検索装置。
【請求項１２】
上記区画は、所定形状および所定サイズのメッシュによって区割りされる領域であることを特徴とする請求項９に記載の施設検索装置。
【請求項１３】
施設検索装置のエリア指定部が、地図上でエリアを指定する第１のステップと、
上記施設検索装置の媒介中心性算出部が、上記地図上において複数の位置の間の連結関係を表したグラフデータを記憶したグラフデータ記憶部を参照して、上記エリア指定部により指定されたエリア内の上記グラフデータに基づいて、上記エリア指定部により指定されたエリア内に存在する各位置の媒介中心性を算出する第２のステップと、
上記施設検索装置の位置抽出部が、上記媒介中心性算出部により算出された媒介中心性の値が所定の条件を満たす位置を抽出する第３のステップと、
上記施設検索装置の施設提示部が、上記位置抽出部により抽出された位置に該当する施設を検索結果として提示する第４のステップとを有することを特徴とする施設検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、施設検索装置および施設検索方法に関し、特に、ナビゲーション装置において誘導経路の目的地や経由地等に設定し得る所望の施設を検索する装置に用いて好適なものである。
【背景技術】
【０００２】
一般に、ナビゲーション装置は、ジャンルやカテゴリ等を指定して所望の施設を検索する機能を有している。検索した施設は、経路探索の目的地や経由地に設定することが可能である。施設の一例として、駐車場を検索することも可能である。
【０００３】
例えば、行先の施設に専用の駐車場が敷設されていない場合には、その行先施設の周辺にある駐車場を検索し、その駐車場を経路探索の目的地に設定することがある。また、一定のエリア内に行先施設が複数ある場合に、それぞれの行先施設を目的地や経由地に設定して経路探索を行うのではなく、それぞれの行先施設に歩いて行ける場所にある駐車場を探して経路探索の目的地に設定することもある。
【０００４】
従来、複数の目的地がある場合に、当該複数の目的地に行くのに好適な駐車場を検索して経路探索を行うナビゲーション装置が知られている（例えば、特許文献１，２参照）。特許文献１に記載のナビゲーション装置は、同一地域に存在する複数の施設を目的地に設定したとき、移動距離最小の条件に基づいて、１回の駐車で済む駐車場を検索して表示するようになされている。
【０００５】
特許文献２に記載のナビゲーション装置では、設定された複数の目的地のうち、データベース内で群としてあらかじめ関連付けされている個々の目的地については徒歩によって移動するための第１の経路誘導路を算出する一方で、当該群から外れる他の目的地については車両によって移動するための第２の経路誘導路を算出する。この第１および第２の経路誘導路を結ぶ地点には、当該群内に含まれる複数の目的地を訪れるのに好適な駐車場が設定される。
【０００６】
しかしながら、上記特許文献１，２において、複数の行先施設に対して最寄りの駐車場を検索するには、各行先施設とその周辺にある複数の駐車場との総組み合わせで距離計算をしなければならず、計算コストが高くなってしまうという問題があった。例えば、行先施設が２つの場合、一方の行先施設を中心としてその周囲３６０度で所定距離の範囲内にある複数の駐車場と、他方の行先施設を中心としてその周囲３６０度で所定距離の範囲内にある複数の駐車場との総組み合わせとして、駐車場から各行先施設への距離を計算し、２つの行先施設に対する距離が最も短くなる駐車場を探さなければならない。
【０００７】
なお、目的地と駐車場との対応関係を解析するシステムにおいて、目的地と駐車領域（その目的地を訪問する際に利用される複数の駐車位置を囲む矩形領域）とを１対１に対応づけて記憶しておき、駐車領域同士が重複しているか否かを判定し、重複している場合、それらの重複している駐車領域を複数の目的地に対する共用駐車領域であると特定するようにした技術が知られている（例えば、特許文献３参照）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００１−５０７５８号公報
【特許文献２】特開２００３−２１４８７５号公報
【特許文献３】特開２０１４−１８２５４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上記特許文献３に記載された解析システムを利用して共用駐車領域を特定すれば、２つの目的地に行くのに好適な駐車場を検索する際に、当該２つの目的地に関して特定された共用駐車領域を対象として駐車場の検索を行うようにすることが可能である。しかしながら、特許文献３に記載の解析を行うためには、１つ１つの目的地について、そこに訪問する際に利用される複数の駐車位置を囲む矩形領域を駐車領域としてあらかじめ設定しておく必要がある。そのため、この駐車領域を設定するための計算コストが高くなってしまうという問題があった。
【００１０】
本発明は、このような問題を解決するために成されたものであり、複数の行先施設を訪れる際にアクセスが良い施設を少ない計算コストで短時間に検索できるようにすることを目的とする。
【課題を解決するための手段】
【００１１】
上記した課題を解決するために、本発明では、地図上でエリアを指定すると、地図上において複数の位置の間の連結関係を表したグラフデータに基づいて、指定されたエリア内に存在する各位置の媒介中心性を算出し、媒介中心性の値が所定の条件を満たす位置に該当する施設を抽出して提示するようにしている。
【発明の効果】
【００１２】
上記のように構成した本発明によれば、複数の行先施設に対してアクセスの良い施設を検索する際、指定されたエリア内に存在する各位置のうち、グラフデータで連結が示された位置を対象として媒介中心性を算出すればよい。また、アクセスの良い駐車場を検索できるようにするために、行先施設となり得る１つ１つの施設について、そこに訪問する際に利用される複数の駐車位置を囲む矩形領域を駐車領域としてあらかじめ設定しておく必要もない。これにより、複数の行先施設を訪れる際にアクセスが良い施設を少ない計算コストで短時間に検索することができる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施形態による施設検索装置の機能構成例を示すブロック図である。
【図２】第１の実施形態の媒介中心性の算出に用いるグラフデータを模式的に示す図である。
【図３】第１の実施形態のエリア指定部によるエリアの指定例を示す図である。
【図４】第１の実施形態の施設提示部による検索結果の提示例を示す図である。
【図５】第１の実施形態による施設検索装置の動作例を示すフローチャートである。
【図６】第２の実施形態による施設検索装置の機能構成例を示すブロック図である。
【図７】第２の実施形態によるグラフデータにおいて連結関係を有する区画の一例を示す図である。
【図８】第２の実施形態の媒介中心性の算出に用いるグラフデータを模式的に示す図である。
【図９】第２の実施形態の施設提示部による検索結果の提示例を示す図である。
【図１０】第２の実施形態による施設検索装置の動作例を示すフローチャートである。
【図１１】第２の実施形態によるグラフデータにおいて連結関係を有する区画の他の例を示す図である。
【発明を実施するための形態】
【００１４】
（第１の実施形態）
以下、本発明の第１の実施形態を図面に基づいて説明する。図１は、第１の実施形態による施設検索装置の機能構成例を示すブロック図である。第１の実施形態による施設検索装置１００は、地図データを用いて現在地から目的地までを結ぶ誘導経路を探索し、その探索した誘導経路に従って車両を目的地まで案内するナビゲーション装置に実装して好適なものである。例えば、誘導経路の目的地とする施設を検索する際に、本実施形態の施設検索装置１００は使用される。
【００１５】
図１に示すように、第１の実施形態による施設検索装置１００は、その機能構成として、地図データ取得部１１、地図表示部１２、エリア指定部１３、グラフデータ記憶部１４、媒介中心性算出部１５、位置抽出部１６および施設提示部１７を備えている。これらの機能ブロック１１〜１７は、ハードウェア、ＤＳＰ（Digital Signal Processor）、ソフトウェアの何れによっても構成することが可能である。例えばソフトウェアによって構成する場合、上記各機能ブロック１１〜１７は、実際にはコンピュータのＣＰＵ、ＲＡＭ、ＲＯＭなどを備えて構成され、ＲＡＭやＲＯＭ、ハードディスクまたは半導体メモリ等の記録媒体に記憶されたプログラムが動作することによって実現される。
【００１６】
地図データ取得部１１は、地図データ記憶部２００から地図データを取得する。地図データ記憶部２００に記憶された地図データは、地図表示や経路探索などに必要な地図データを記憶するものであり、例えばハードディスクにより構成される。地図データの中には、道路に関するノードデータやリンクデータの他に、目的地として設定され得る各種施設に関するデータも含まれている。施設データは、施設の名称、ジャンル（カテゴリ）、地点ＩＤ、位置（緯度経度）などの情報を含んでいる。
【００１７】
第１の実施形態において、地図データ記憶部２００に記憶された地図データは、地図上において複数の位置（第１の実施形態では、位置の一例として、施設が存在する地点を用いる）の間の連結関係を表したグラフデータも含んでいる。図２は、第１の実施形態によるグラフデータを模式的に示す図である。図２（ａ）において、ノードＮ１〜Ｎ５は、複数の施設が存在する各地点を示している。ノードＮ１〜Ｎ５間に引かれた線Ｌ１〜Ｌ５は、地点間の連結関係の有無を示している。例えば、ノードＮ１，Ｎ２間は連結関係があるが、ノードＮ２，Ｎ３間は連結関係がないことが示されている。
【００１８】
図２（ｂ）に示すように、グラフデータは、ノード情報および連結情報から構成される。ノード情報は、地点ＩＤおよび緯度経度の情報により構成される。連結情報は、Ｆｒｏｍ地点ＩＤ、Ｔｏ地点ＩＤおよび地点間の距離の情報により構成される。
【００１９】
第１の実施形態では、ある範囲のエリア内にある複数の行先施設を訪れる際に、両方の行先施設に対して徒歩で行けるアクセスが良い駐車場を検索できるようにすることを想定する。この場合、グラフデータは、駐車場が存在する地点と駐車場以外の施設が存在する地点との間は連結させず、駐車場が存在する地点どうしの間を連結させた連結関係を表したグラフデータとすればよい。特に、所定距離以内にある駐車場の地点どうしを連結させたグラフデータとするのが好ましい。
【００２０】
地図表示部１２は、地図データ取得部１１により地図データ記憶部２００から取得された地図データに基づいて、ディスプレイ３００に地図画像を表示させる。この地図画像は、施設検索を行う対象のエリアを指定する際に使用される。また、地図画像は、施設検索の結果を表示する際にも使用される。
【００２１】
エリア指定部１３は、操作部４００に対するユーザ操作に応じて、地図上で複数の行先施設の地点を含むエリアを検索対象のエリアとして指定する。一例として、エリア指定部１３は、地図上で２つの行先施設の地点を含むエリアを指定する。例えば、ディスプレイ３００に表示されている地図画像上で所望のエリアを囲む操作を行うことにより、その囲まれたエリアを検索対象のエリアとして指定する。地図画像上で所望のエリアを囲む操作は、タッチパネル（操作部４００の一例）に対するタッチ操作や、ポインティングデバイス（操作部４００の他の例）のカーソル移動操作などによって行うことが可能である。
【００２２】
なお、エリアの指定方法はこれに限定されない。例えば、図３に示すように、ユーザ操作により２つの行先施設の地点Ｐ１，Ｐ２を指定すると、その指定した地点Ｐ１，Ｐ２を２つの角とする矩形エリアを自動的に指定するようにしてもよい。あるいは、図３に示す矩形エリアよりも四方にそれぞれ所定距離ずつ広いエリアを指定するようにしてもよい。また、エリアの別の指定方法として、ユーザ操作により所望の行政区画を指定することにより、行政区画を単位としてエリアを指定するようにしてもよい。
【００２３】
エリアを指定する際には、２つの行先施設の地点Ｐ１，Ｐ２がエリア内で離れた位置となるように指定するのが好ましい。特に、２つの行先施設の地点Ｐ１，Ｐ２が何れもエリア内の周辺域に入るようにエリアを指定するのがより好ましい。あまりにも広い範囲をエリアとして指定することによって、２つの行先施設の地点Ｐ１，Ｐ２が何れもエリア内のほぼ中央域に入ったり、２つの行先施設の地点Ｐ１，Ｐ２が何れもエリア内の同じ周辺域に偏って入ったりすると、後述する媒介中心性の計算によって、２つの行先施設にアクセスのよい駐車場が必ずしも検索されなくなる可能性があるからである。
【００２４】
グラフデータ記憶部１４は、地図データ取得部１１により地図データ記憶部２００から取得された地図データのうち、エリア指定部１４により指定されたエリア内のグラフデータを記憶する。
【００２５】
媒介中心性算出部１５は、エリア指定部１４により指定されたエリア内のグラフデータ、すなわち、グラフデータ記憶部１４に記憶されたグラフデータに基づいて、指定されたエリア内に存在する各地点の媒介中心性を算出する。媒介中心性とは、２つのノードを結ぶ経路上にあるノードを高く評価する中心性指標のことをいい、あるノードが他の２つのノード間を結ぶ最短経路上にある度合いを示している。この媒介中心性は、公知の方法により算出することが可能である。
【００２６】
図２の例で、ノードＮ１は、ノードＮ２とノードＮ３との最短経路上にあるので、媒介中心性の値は１つカウントアップされる。同様に、ノードＮ２とノードＮ４との最短経路上にも、ノードＮ２とノードＮ５との最短経路上にもノードＮ１が存在するので、合わせて３つのカウントアップとなる。これに対し、ノードＮ３とノードＮ５との最短経路はノードＮ１を通らないので、カウントアップされない。ノードＮ３からノードＮ５に至る経路は２つあるが、Ｎ３→Ｎ１→Ｎ５の経路よりもＮ３→Ｎ４→Ｎ５の経路の方が距離が短いため、最短経路はＮ３→Ｎ４→Ｎ５の経路となる。結果、ノードＮ１の媒介中心性の値は３となる。
【００２７】
位置抽出部１６は、媒介中心性算出部１５により算出された媒介中心性の値が所定の条件を満たす地点を抽出する。例えば、位置抽出部１６は、媒介中心性の値が所定の値より大きな地点を指定エリア内から抽出する。あるいは、位置抽出部１６は、媒介中心性の値が大き方から順番に所定数の地点を指定エリア内から抽出するようにしてもよい。
【００２８】
施設提示部１７は、位置抽出部１６により抽出された地点に該当する施設（駐車場）を検索結果としてディスプレイ３００に提示する。図４は、施設提示部１７による検索結果の提示例を示す図である。図４に示すように、施設提示部１７は、エリア指定部１３により指定されたエリアを含む地図画像をディスプレイ３００に表示させるとともに、位置抽出部１６により抽出された地点における駐車場のアイコン４１を、地図画像上の該当する位置に重ねて表示する。なお、エリア指定部１３によりエリアを指定する際に、２つの行先施設Ｐ１，Ｐ２を指定している場合は、その行先施設Ｐ１，Ｐ２のアイコンも併せて表示するのが好ましい。
【００２９】
第１の実施形態のように、２つの行先施設Ｐ１，Ｐ２が比較的離れた状態で含まれるようなエリアを指定し、駐車場の地点どうしを連結させたグラフデータを用いて媒介中心性を算出すると、一方の行先施設Ｐ１の周辺にある駐車場でもなく、他方の行先施設Ｐ２の周辺にある駐車場でもなく、各行先施設Ｐ１，Ｐ２の中間辺りにある駐車場が、媒介中心性の値が大きい駐車場として抽出される。そのため、図４に示すように、各行先施設Ｐ１，Ｐ２の中間辺りにある駐車場が検索結果として提示されるようになる。
【００３０】
なお、エリアの指定のし方によっては、２つの行先施設Ｐ１，Ｐ２との距離が所定値以上となって、徒歩には向かない駐車場の地点が位置抽出部１６により抽出される場合も考えられる。そこで、位置抽出部１６は、媒介中心性の値が所定の条件を満たす地点のうち、２つの行先施設Ｐ１，Ｐ２の地点との距離が所定値未満である地点を抽出するようにしてもよい。
【００３１】
ユーザは、図４のように表示された駐車場アイコン４１の中から何れかを選択する操作を行うことにより、選択した駐車場を目的地に設定することが可能である。なお、検索結果の提示方法は、図４の例に限定されない。例えば、位置抽出部１６により抽出された地点に該当する駐車場を一覧形式でリスト表示するようにしてもよい。
【００３２】
図５は、上記のように構成した第１の実施形態による施設検索装置１００の動作例を示すフローチャートである。なお、図５に示すフローチャートは、駐車場のジャンルを指定して施設検索を行うことがナビゲーション装置に対して指示されたときに開始する。
【００３３】
まず、地図表示部１２は、地図データ取得部１１により地図データ記憶部２００から取得された地図データに基づいて、ディスプレイ３００に地図画像を表示させる（ステップＳ１）。ここでは、２つの行先施設Ｐ１，Ｐ２がある地点周辺の地図画像を表示させる。これは、例えば、地図画面のスクロール操作によって行うことが可能である。あるいは、行先施設Ｐ１，Ｐ２の何れかを検索することにより、検索した地点の周辺地図にジャンプ表示させることも可能である。
【００３４】
次に、エリア指定部１３は、ユーザ操作に応じて、地図上で２つの行先施設Ｐ１，Ｐ２の地点を含むエリアを検索対象のエリアとして指定する（ステップＳ２）。エリアが指定されると、そのエリア内のグラフデータがグラフデータ記憶部１４に記憶される（ステップＳ３）。媒介中心性算出部１５は、グラフデータ記憶部１４に記憶されたグラフデータに基づいて、指定されたエリア内に存在する各駐車場の地点の媒介中心性を算出する（ステップＳ４）。
【００３５】
次いで、位置抽出部１６は、媒介中心性算出部１５により算出された媒介中心性の値が所定の条件を満たす地点を抽出する（ステップＳ５）。そして、施設提示部１７は、位置抽出部１６により抽出された地点の駐車場を検索結果としてディスプレイ３００に提示する（ステップＳ６）。これにより、図５に示すフローチャートの処理を終了する。
【００３６】
以上詳しく説明したように、第１の実施形態では、地図上で複数の行先施設の地点を含むエリアを指定し、指定されたエリア内のグラフデータに基づいて、当該指定されたエリア内に存在する各駐車場の地点の媒介中心性を算出し、媒介中心性の値が所定の条件を満たす地点の駐車場を抽出して提示するようにしている。
【００３７】
このように構成した第１の実施形態によれば、複数の行先施設に対してアクセスの良い駐車場を検索するために、各行先施設とその周辺にある複数の駐車場との総組み合わせで距離計算をする必要がなく、指定されたエリア内に存在する各地点のうち、グラフデータで連結が示された地点を対象として媒介中心性を算出すればよい。また、行先施設となり得る１つ１つの施設について、そこに訪問する際に利用される複数の駐車位置を囲む矩形領域を駐車領域としてあらかじめ設定しておく必要もない。これにより、複数の行先施設を訪れる際にアクセスが良い駐車場を少ない計算コストで短時間に検索することができる。
【００３８】
なお、上記第１の実施形態では、エリア指定部１３により地図上で２つの行先施設の地点を含むエリアを指定する例について説明したが、３つ以上の行先施設の地点を含むエリアを指定し、３つ以上の行先施設を訪れる際にアクセスが良い駐車場を抽出するようにすることも可能である。３つ以上の行先施設が互いに比較的離れた状態で含まれるようなエリアを指定し、駐車場の地点どうしを連結させたグラフデータを用いて媒介中心性を算出すれば、各行先施設の中間辺りにある駐車場を、媒介中心性の値が大きい駐車場として抽出することができる。
【００３９】
行先施設が３つ以上ある場合、その中の１つが駐車場付きの施設であって、他の残りの行先施設に対して媒介中心性が大きい施設である可能性もある。この場合は、その駐車場付き施設に駐車すれば、３つ以上の施設を効率よく訪問することができる。そこで、３つ以上の行先施設を指定してエリアの指定が行われた場合、位置抽出部１６は、媒介中心性の値が所定の条件を満たす駐車場または駐車場付き行先施設の地点を抽出するようにしてもよい。ただし、これを実現するためには、駐車場の地点どうしを連結させるだけでなく、駐車場付き施設の地点も連結に加えたグラフデータを用いる必要がある。
【００４０】
また、上記第１の実施形態では、アクセスの良い駐車場を検索して提示する例について説明した、検索する施設は駐車場に限定されない。
【００４１】
（第２の実施形態）
次に、本発明の第２の実施形態を図面に基づいて説明する。上述した第１の実施形態では、グラフデータにおいて連結関係を表す位置の例として施設（駐車場）の「地点」を用いたが、これに対して第２の実施形態では、連結関係を表す位置として「区画」を用いる。
【００４２】
図６は、第２の実施形態による施設検索装置の機能構成例を示すブロック図である。なお、この図６において、図１に示した符号と同一の符号を付したものは同一の機能を有するものであるので、ここでは重複する説明を省略する。
【００４３】
図６に示すように、第２の実施形態による施設検索装置１００’は、その機能構成として、検索条件入力部１８を更に備えるとともに、エリア指定部１３、グラフデータ記憶部１４、媒介中心性算出部１５、位置抽出部１６および施設提示部１７に代えて、エリア指定部１３’、グラフデータ記憶部１４’、媒介中心性算出部１５’、位置抽出部１６’および施設提示部１７’を備えている。また、地図データ記憶部２００に代えて地図データ記憶部２００’が備えられている。
【００４４】
第２の実施形態において、地図データ記憶部２００’が記憶する地図データには、地図上において複数の区画の間の連結関係を表したグラフデータが含まれている。図７は、第２の実施形態によるグラフデータにおいて連結関係を有する区画の一例を示す図である。また、図８は、第２の実施形態によるグラフデータを模式的に示す図である。
【００４５】
図７に示すように、区画は、交差点および道路によって区割りされる領域として設定されている。個々の区画には、区画ＩＤ（便宜上、０１〜１３の番号で示す）が設定されている。また、図８において、ノード０１〜１３は、複数の区画を示している。ノード０１〜１３間に引かれた線は、区画間の連結関係の有無を示している。図８の例では、隣り合う区画のノード間に連結関係が設定され、隣り合わない区画のノード間には連結関係が設定されていない。なお、図７では全ての交差点ごとに区割りする例を示しているが、任意の交差点を選択して区割りするようにしてもよい。
【００４６】
エリア指定部１３’は、地図上で複数の区画を含むエリアを指定する。図７は、複数の区画０１〜１３が含まれるように指定した矩形のエリアであるものとする。ここで、矩形の指定エリア内に一部のみが含まれる区画は、媒介中心性の算出対象に含めるようにしてもよいし、含めないようにしてもよい。また、指定エリア内において、領域の全体が含まれる区画のみを媒介中心性の算出対象とした場合に、算出対象となる区画が所定数以上のときは、領域の一部のみが含まれる区画は媒介中心性の算出対象に含めないようにし、区画が所定数未満のときは算出対象に含めるようにしてもよい。
【００４７】
グラフデータ記憶部１４’は、地図データ取得部１１により地図データ記憶部２００’から取得された地図データのうち、エリア指定部１３’により指定されたエリア内のグラフデータを記憶する。特に、媒介中心性の算出対象とされた区画のグラフデータを記憶する。第２の実施形態においてグラフデータ記憶部１４’が記憶するグラフデータは、図８に示すように、地図上において複数の区画の間の連結関係を表したものである。
【００４８】
媒介中心性算出部１５’は、エリア指定部１３’により指定されたエリア内のグラフデータ、すなわち、グラフデータ記憶部１４’に記憶されたグラフデータに基づいて、指定されたエリア内に存在する各区画の媒介中心性を算出する。
【００４９】
位置抽出部１６’は、媒介中心性算出部１５’により算出された媒介中心性の値が所定の条件を満たす区画を抽出する。例えば、位置抽出部１６’は、媒介中心性の値が最も大きい区画を指定エリア内から抽出する。図８の例では、区画ＩＤが“１０”の区画が、媒介中心性の値が最も大きくなる。なお、位置抽出部１６’は、媒介中心性の値が大き方から順番に所定数の区画を指定エリア内から抽出するようにしてもよい。
【００５０】
検索条件入力部１８は、操作部４００に対するユーザ操作に応じて、施設の検索条件を入力する。例えば、検索したい施設を検索条件として入力することが可能である。すなわち、駐車場を検索したいときは、検索条件として「駐車場」を入力すればよい。また、宿泊施設を検索したいときは、検索条件として「宿泊施設」を入力すればよい。その他、施設の利用料金、営業時間、ジャンル（カテゴリ）など、当該施設に付随している属性情報を検索条件として入力するようにしてもよい。
【００５１】
施設提示部１７’は、位置抽出部１６’により抽出された区画の中で、検索条件入力部１８により入力された検索条件に合致する施設を検索し、当該検索した施設を検索結果として提示する。図９は、施設提示部１７’による検索結果の提示例を示す図である。図９の例は、駐車場を検索条件として入力した場合の検索結果を示している。具体的には、位置抽出部１６’によって区画ＩＤ“１０”の区画が抽出され、その区画の中に含まれる駐車場のアイコン９１が地図画像上の該当する位置に重ねて表示された状態を示している。
【００５２】
なお、ここでは検索条件をユーザが入力する例を説明したが、本発明はこれに限定されない。例えば、施設提示部１７’は、位置抽出部１６’により抽出された区画の中から、施設検索装置１００’によってあらかじめ決められた検索条件に合致する施設を検索し、当該検索した施設を検索結果として提示するようにしてもよい。
【００５３】
図１０は、上記のように構成した第２の実施形態による施設検索装置１００’の動作例を示すフローチャートである。なお、図１０に示すフローチャートは、例えば、検索条件入力部１８により検索条件が入力され、施設検索を行うことがユーザにより指示されたときに開始する。
【００５４】
まず、地図表示部１２は、地図データ取得部１１により地図データ記憶部２００’から取得された地図データに基づいて、ディスプレイ３００に地図画像を表示させる（ステップＳ１１）。
【００５５】
次に、エリア指定部１３’は、ユーザ操作に応じて、地図上で複数の区画を含むエリアを検索対象のエリアとして指定する（ステップＳ１２）。エリアが指定されると、そのエリア内のグラフデータがグラフデータ記憶部１４’に記憶される（ステップＳ１３）。媒介中心性算出部１５’は、グラフデータ記憶部１４’に記憶されたグラフデータに基づいて、指定されたエリア内に存在する各区画の媒介中心性を算出する（ステップＳ１４）。
【００５６】
次いで、位置抽出部１６’は、媒介中心性算出部１５’により算出された媒介中心性の値が所定の条件を満たす区画を抽出する（ステップＳ１５）。そして、施設提示部１７’は、位置抽出部１６’により抽出された区画の中で、検索条件入力部１８により入力された検索条件に合致する施設を検索し（ステップＳ１６）、当該検索した施設を検索結果としてディスプレイ３００に提示する（ステップＳ１７）。これにより、図１０に示すフローチャートの処理を終了する。
【００５７】
以上詳しく説明したように、第２の実施形態では、地図上で複数の区画を含むエリアを指定し、指定されたエリア内のグラフデータに基づいて、当該指定されたエリア内に存在する各区画の媒介中心性を算出し、媒介中心性の値が所定の条件を満たす区画を抽出して、さらにその区画内から検索条件に合致する施設を検索して提示するようにしている。
【００５８】
このように構成した第２の実施形態によれば、例えば、所望のエリア内で複数の施設に訪問して周遊したいような場合に、周遊に都合の良い施設を少ない計算コストで短時間に検索することができる。例えば、周遊エリアに対して最もアクセスの良い駐車場を検索したり、複数日にまたがって経路を設定できるようなナビゲーション装置において最もアクセスの良い宿泊施設を検索したり、電気自動車で周遊する際に最もアクセスの良い充電ステーションを検索したりするといったことを、少ない計算コストで短時間に実行することができる。
【００５９】
なお、上記第２の実施形態では、図７のように、交差点および道路によって区割りされる領域を区画として設定する例について説明したが、本発明はこれに限定されない。例えば、図１１に示すように、所定形状および所定サイズのメッシュによって区割りされる領域を区画として設定するようにしてもよい。なお、図１１では矩形形状のメッシュを示しているが、この形状に限定されるものではない。
【００６０】
また、上記第１および第２の実施形態では、グラフデータが地図データの一部として地図データ記憶部２０１にあらかじめ記憶されている例について説明したが、本発明はこれに限定されない。例えば、エリア指定部１３によりエリアが指定されたときに、その指定エリア内のグラフデータをリアルタイムに生成するようにしても良い。指定エリア内に限定すれば、グラフデータの生成にそれほど大きな計算コストはかからない。
【００６１】
また、上記第１および第２の実施形態では、媒介中心性の値が所定の条件を満たす駐車場を抽出して提示する例について説明したが、他の抽出条件を加えてもよい。例えば、施設データとして駐車場の料金情報が含まれる場合は、媒介中心性の値が所定の条件を満たし、かつ、駐車場の料金が所定値以下の駐車場のみを抽出して提示するようにしてもよい。検索結果をリスト表示する場合は、媒介中心性の値が所定の条件を満たす駐車場を、料金が安い順に提示するようにしてもよい。
【００６２】
その他、上記第１および第２の実施形態は、何れも本発明を実施するにあたっての具体化の一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその要旨、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【００６３】
１３，１３’  エリア指定部
１４，１４’  グラフデータ記憶部
１５，１５’  媒介中心性算出部
１６，１６’  位置抽出部
１７，１７’  施設提示部
１８  検索条件入力部
１００，１００’  施設検索装置
２００，２００’  地図データ記憶部
【図１】
2018163407.tif 000003
【図２】
2018163407.tif 000004
【図３】
2018163407.tif 000005
【図４】
2018163407.tif 000006
【図５】
2018163407.tif 000007
【図６】
2018163407.tif 000008
【図７】
2018163407.tif 000009
【図８】
2018163407.tif 000010
【図９】
2018163407.tif 000011
【図１０】
2018163407.tif 000012
【図１１】
2018163407.tif 000013