経路探索システム
【課題】 目的地周辺の道路の状態を考慮して、利便性の高い代替目的地を案内可能とする。
【解決手段】 目的地のポリゴンを格納する地物データおよび経路探索用のネットワークデータを有する地図データベースを用意する。地物データにおいては、それぞれの建物等に対し、その建物等から道路を通って、ネットワークデータが整備された道路に至った点を到着地点として設定しておく。目的地Ｈ０が指定された場合には、まずその到着地点ＧＨ０を起点とする経路探索を行って、到着地点から最短の道のりにある駐車場ＰＫ２を代替目的地に設定し、出発地から代替目的地までの経路探索を行う。
こうすることで、目的地Ｈ０に直線距離では近いが、無用な大回りが必要となる駐車場ＰＫ１が代替目的地に設定されることを抑制でき、利便性の高い代替目的地への案内を実現することができる。
【解決手段】 目的地のポリゴンを格納する地物データおよび経路探索用のネットワークデータを有する地図データベースを用意する。地物データにおいては、それぞれの建物等に対し、その建物等から道路を通って、ネットワークデータが整備された道路に至った点を到着地点として設定しておく。目的地Ｈ０が指定された場合には、まずその到着地点ＧＨ０を起点とする経路探索を行って、到着地点から最短の道のりにある駐車場ＰＫ２を代替目的地に設定し、出発地から代替目的地までの経路探索を行う。
こうすることで、目的地Ｈ０に直線距離では近いが、無用な大回りが必要となる駐車場ＰＫ１が代替目的地に設定されることを抑制でき、利便性の高い代替目的地への案内を実現することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、指定された目的地に向かう際に利用可能な代替目的地までの経路を探索する経路探索システムに関する。
【背景技術】
【０００２】
道路をリンク、ノードで表したネットワークデータを用いて、指定された出発地から目的地までの経路を探索し、案内するナビゲーションシステムが普及している。自動車で移動する時にナビゲーションシステムを利用する場合、目的地に駐車場が存在するとは限らないから、目的地周辺の駐車場を代替目的地とし、この代替目的地に対して経路探索および案内を行うことが好ましい。
【０００３】
目的地周辺の駐車場は、従来、次の手順で探索されていた。経路探索に用いるネットワークデータ上で目的地に最短距離にあるノードを見つけ、このノードを出発地としてネットワークデータを用いた経路探索を行うことにより、上述のノードに近い駐車場を見つける。
【０００４】
また、別の方法として、特許文献１には、目的地から所定の距離範囲内にある駐車場を探索する技術が開示されている。所定の距離範囲内に駐車場が複数探索された場合には、駐車場の混雑情報、満車情報などに基づいて、経路探索すべき駐車場が決められる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−２６３５８１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
図１は、従来技術における駐車場の探索方法を示す説明図である。
目的地Ｈ０が指定された時に、その周辺の駐車場を探索する場合を考える。目的地Ｈ０からは細い通路を経て、道路Ｒ０２に至ることができる。道路Ｒ０２は、川ＲＶを超えたところにある道路Ｒ００、Ｒ０１と交差している。道路Ｒ００、Ｒ０１には、経路探索に使用するためのリンクＬ００、Ｌ０１およびノードＮが設定されている。目的地周辺には、道路Ｒ００に面して駐車場ＰＫ１があり、道路Ｒ０２に面して駐車場ＰＫ２がある。
従来技術では、目的地Ｈ０から最短の距離にあるノードＮを起点とする経路探索によって駐車場を探索していた。図示する通り、ネットワークデータは道路Ｒ００、Ｒ０１に整備されているだけなので、リンクＬ００に沿って矢印Ｐ方向に経路探索が行われ、駐車場ＰＫ１が案内すべき駐車場として選択される。
仮に、道路Ｒ０２にネットワークデータが整備されていたとしても、ノードＮを起点とする限り、ノードＮに近い駐車場ＰＫ１が選択されることに変わりはない。
【０００７】
また特許文献１に記載されている通り、目的地Ｈ０からの距離に基づいて駐車場を選択したとしても、駐車場ＰＫ１までの距離Ｄ１の方が、駐車場ＰＫ２までの距離Ｄ２よりも短いため、駐車場ＰＫ１が選択されることになる。
【０００８】
しかし、図の道路状態を見れば明らかな通り、目的地Ｈ０に行く際に便利なのは、駐車場ＰＫ１ではなく駐車場ＰＫ２である。このように、従来技術では、目的地Ｈ０にとって、必ずしも利便性の高い駐車場が選択されるとは限らなかった。
上述の課題は、駐車場を代替目的地とする場合に限らず、その他の代替目的地を用いる場合にも共通であった。本発明は、かかる課題に鑑み、目的地周辺の道路の状態を踏まえて、利便性の高い代替目的地への案内を可能とすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、指定された目的地に向かう際に利用可能な代替目的地までの経路を探索する経路探索システムとして構成することができる。代替目的地とは、例えば、自動車で目的地に向かう場合には駐車場、自転車で向かう場合には駐輪場、馬で向かう場合には馬場のように、ユーザが利用する移動手段を停めておく場所とすることができる。また、目的地に着く前に、花屋や菓子屋で手土産を買いたい場合や、喫茶店やレストランで時間を過ごしたい場合などには、これらの店舗を代替目的地とすることができる。
本発明においては、これらの代替目的地が予めユーザに指示されている訳ではない。本発明は、目的地周辺でユーザが利用したい代替目的地を探索した上で、その代替目的地までの経路探索を行うものである。
本発明において、これらの代替目的地の属性は、予め定めておいてもよいし、ユーザが指定してもよい。
【００１０】
経路探索システムは、地図データベース記憶部、入力部、到着地点取得部、代替目的地探索部、経路探索部を備える。
地図データベース記憶部は、道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データとを格納する。ネットワークデータは、通行規制も踏まえて自動車の経路探索に使用可能な主ネットワークと、経路探索に使用可能ではあるが通行規制の整備が完全とは言えない準ネットワークなどを混在して用意してもよい。
【００１１】
入力部は、出発地および目的地の指定を入力する。出発地は、ユーザの現在位置を自動的に入力するようにしてもよい。目的地は、地物データに含まれる特定の建物等を指定してもよいし、地図上で座標値を指定してもよい。入力部は、更に、駐車場、店舗といった代替目的地の属性を入力してもよい。
【００１２】
到着地点取得部は、ネットワークデータおよび地物データを含む地図データベースを参照して、上述の主ネットワーク、つまり自動車が通行可能な道路としてネットワークデータが整備された道路上の点であって、目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点を取得する。
到着地点は、地物データの一部として、建物等の地物ごとに設定されているものとしてもよい。この場合は、到着地点取得部は、目的地として指定された地物に対応する到着地点のデータを読み込めば済む。目的地が座標値で指定された場合には、到着地点取得部は、指定された座標が対応する地物を特定し、その地物に対応する到着地点のデータを読み込めばよい。
これに対し、到着地点を予め用意しない構成とすることもできる。この場合には、到着地点取得部は、目的地を起点する経路探索によって、到着地点を見いだすことになる。この場合の経路探索には、通行規制の整備が完全とは言えない準ネットワークや、ネットワークが一切整備されてはいない道路も用いることができる。ネットワークが整備されていない道路については、地物データに含まれる道路のポリゴンデータの連結具合をネットワークデータとして扱うことにより経路探索の対象とすることができる。
【００１３】
代替目的地探索部は、ネットワークデータを参照して、到着地点を起点とする経路探索によって、到着地点から到達可能な所定の属性を有する代替目的地を探索する。代替目的地が探索されると、経路探索部は、ネットワークデータを参照して、出発地から探索された代替目的地までの経路探索を行う。
代替目的地の探索は、主ネットワークのみを用いてもよいし、準ネットワークや道路のポリゴンデータを併用してもよい。主ネットワークのみを用いる場合には、代替目的地は主ネットワークに関連づけられているはずであるから、経路探索部は、代替目的地をそのまま目的地とみなして出発地からの経路探索を行えばよい。
準ネットワークおよび道路のポリゴンデータを併用する場合には、代替目的地が主ネットワークに関連づけられているとは限らない。従って、経路探索部は、代替目的地に対して到着地点を取得し、この到着地点を目的地とみなして出発地からの経路探索を行う。
【００１４】
本発明の経路探索システムによれば、目的地に対応する到着地点を起点として代替目的地の探索を行う。到着地点は、単に目的地から最短距離にあるといった条件ではなく、目的地からの道路の状態を考慮して設定された点であるから、無用な遠回りが必要となるような場所が代替目的地となることを抑制でき、利便性の高い代替目的地が設定される。
【００１５】
本発明において、複数の代替目的地が探索された場合には、全てに対して出発地からの経路探索を行ってもよいが、探索された代替目的地のいずれかを次に示す態様によって優先してもよい。優先とは、代替目的地を一つだけ選択すること、または複数の代替目的地のうち経路探索の対象とする候補をいくつか絞り込むことを意味する。
第１の態様として、到着地点から代替目的地までの道のりが短い代替目的地を優先してもよい。こうすることで、代替目的地から目的地までの距離までを短くすることができる。
第２の態様として、到着地点から代替目的地までの経路が、目的地から到着地点までの経路と一部または全部において重複する代替目的地を優先してもよい。代替目的地が、目的地を挟んで到着地点と逆側に探索されることもある。このような代替目的地は、代替目的地から到着地点まで戻るまでなく目的地にたどりつける点で、利便性が高いことがある。上述のように、経路の重複を考慮することにより、目的地を挟んで到着地点と逆側にある代替目的地を優先することが可能となる。
第１の態様、第２の態様は、併せて適用してもよい。
【００１６】
代替目的地の探索には、ネットワークデータに加えて、地物データに含まれる道路のポリゴンデータも用いてもよい。つまり、主ネットワーク、準ネットワークおよびポリゴンを用いた探索を行ってもよい。
こうすることにより、探索の範囲が広がり、より適切な代替目的地を探索しやすくなる。
準ネットワークやポリゴンについて通行規制が十分には整備されていない場合であっても、駐車場がある道路や、車線幅が十分に広い道路などは、車両が通行可能なこともある。これらのデータを併用して代替目的地の探索を行う場合には、このように道路沿いに存在する地物や、道路の属性に基づいて、通行可否を判断した上で、探索に利用可能な道路を絞り込むようにしてもよい。
【００１７】
本発明は、その他、コンピュータを用いた経路探索方法として構成してもよいし、かかる経路探索をコンピュータに実行させるためのコンピュータプログラムとして構成してもよい。また、かかるコンピュータプログラムを記録したコンピュータが読み取り可能な記録媒体として構成してもよい。記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【図面の簡単な説明】
【００１８】
【図１】従来技術における駐車場の探索方法を示す説明図である。
【図２】経路探索システムの構成を示す説明図である。
【図３】地図データベースの構造を示す説明図である。
【図４】到着地点の設定について示す説明図である。
【図５】経路探索処理（１）のフローチャートである。
【図６】経路探索処理（２）のフローチャートである。
【図７】代替目的地の探索例（１）を示す説明図である。
【図８】代替目的地の探索例（２）を示す説明図である。
【発明を実施するための形態】
【００１９】
本発明の実施例について以下の順序で説明する。
Ａ．システム構成：
Ｂ．データ構造：
Ｂ１．ネットワークデータ：
Ｂ２．文字データ：
Ｂ３．地物データ：
Ｂ４．文字データ：
Ｃ．経路探索処理：
Ｄ．経路探索例
【実施例１】
【００２０】
Ａ．システム構成：
図２は、経路探索システムの構成を示す説明図である。経路探索システムは、ナビゲーション装置１００として構成される。本実施例では、ナビゲーション装置１００は、地図データ等を提供するサーバ２００とネットワークＮＥで接続されており、サーバ２００から地図データベースの更新を受けられるものとした。ナビゲーション装置１００は、スタンドアロンで稼働する構成としてもよいし、その機能の一部をサーバ２００等で実行する構成としてもよい。
【００２１】
サーバ２００は、地図データベース記憶部２１０、送受信部２０１、およびデータベース管理部２０２を備えている。送受信部２０１、データベース管理部２０２は、ハードウェア的に構成してもよいが、本実施例では、これらの機能を実現するコンピュータプログラムをインストールすることによって、ソフトウェア的に構成するものとした。
【００２２】
送受信部２０１は、ナビゲーション装置１００とネットワークＮＥを介した通信を行う。本実施例では、地図データベース記憶部２１０に格納されたデータや、その提供を求めるためのコマンド等が通信される。
データベース管理部２０２は、ナビゲーション装置１００から要求された地図情報を、地図データベース記憶部２１０から読み出す。地図データベース記憶部２１０には、地物データ２１１、文字データ２１２、およびネットワークデータ２１３が格納されている。
地物データ２１１は、道路や建物など地図に描画すべき地物のポリゴンデータである。文字データ２１２は、地図上に表示すべき文字情報である。例えば、建物の名称や地名などの文字情報が含まれる。ネットワークデータ２１３は、道路をノード、リンクのつながりで表したデータである。
【００２３】
ナビゲーション装置１００には、主制御部１０１の下で稼働する種々の機能ブロックが構成されている。本実施例では、主制御部１０１および各機能ブロックは、それぞれの機能を実現するソフトウェアをインストールすることによって構成したが、その一部または全部をハードウェア的に構成してもよい。
送受信部１０２は、サーバ２００とのネットワークＮＥを介した通信を行う。本実施例では、地図データベースおよびその提供を受けるためのコマンドの送受信が主として行われる。
コマンド入力部１０３は、ナビゲーション装置１００に設けられたボタン、レバー、タッチパネル等の操作を通じて、ユーザからの指示を入力する。本実施例における指示としては、経路探索の出発地、目的地の指定などが挙げられる。
ＧＰＳ入力部１０４は、ＧＰＳ（Global Positioning System）を用いてユーザの現在位置を入力する。
地図データベース記憶部１０５は、サーバ２００から提供された地図データベース記憶部２１０に記憶されている地図データベースを格納する。本実施例では、サーバ２００が備える地図データベースの全体をナビゲーション装置１００内の地図データベース記憶部１０５にも格納するものとしたが、経路探索や地図表示に必要となる部分のみを、その都度、サーバ２００から取得するものとしてもよい。
経路探索部１０７は、地図データベースを参照して、経路探索を行う。
表示制御部１０６は、地図データベース記憶部１０５を用いてナビゲーション装置１００のディスプレイに地図および探索された経路を表示する。
【００２４】
Ｂ．データ構造：
図３は、地図データベースの構造を示す説明図である。地物データ、文字データ、ネットワークデータに格納される情報の概要を示した。
【００２５】
Ｂ１．ネットワークデータ：
ネットワークデータとは、道路をリンク、ノードで表したデータである。本実施例では、ネットワークデータとして主ネットワークデータと、準ネットワークデータの２種類が用意されている。図中に実線で示したリンクＬ１〜Ｌ４およびノードＮ１、Ｎ２が主ネットワークデータであり、破線で示したリンクＬ１１〜Ｌ１３およびノードＮ１１、Ｎ１２が準ネットワークデータである。
主ネットワークデータおよび準ネットワークデータともに、それぞれに属するリンクデータおよびノードデータを格納している。リンクデータは、それぞれのリンクを形成する点列の座標、国道・県道等の種別、車線数その他の属性情報や通行規制情報などを記録している。ノードデータは、座標値、通行規制などを記録している。
ただし、主ネットワークデータは、現地調査によって通行規制が十分に整備されたデータであり、車両の経路探索に支障なく用いることができるデータとなっている。これに対し、準ネットワークデータは、通行規制の整備が十分とは言えないデータであり、車両の経路探索では、使用しない方が好ましいデータである。本実施例でも、経路探索は原則として主ネットワークデータを用いて行うものとしている。
【００２６】
Ｂ２．文字データ：
文字データ２１２は、地物の名称や地名などを表示する文字を規定するデータである。図中には、建物ＢＬＤの名称を表示するためのデータ例を示した。文字データは、内容、位置、地物、フォント、サイズなどの情報を格納する。
内容は、表示すべき文字列であり、図中の例では、「△△(株)」という会社名称である。
位置は、文字を表示する位置である。本実施例では、文字列の左下の点Ｐ５を基準点として、この座標値を指定するものとした。
地物は、文字が関連づけられる地物データのポリゴン名称である。
フォント、サイズは、表示する際のフォントおよびサイズの指定である。
この他、色、太字など、種々の属性を指定可能としてもよい。
【００２７】
Ｂ３．地物データ：
地物データ２１１について、建物Ｈ１を例にとって構造を示す。地物データ２１１は、建物、道路等の地物を描画するためのポリゴンデータであり、名称、形状、代表点、出入り口線、到着地点、属性などを格納している。
名称は、地物の名称である。ポリゴンに固有のＩＤを用いてもよい。
形状は、地物のポリゴンの頂点を示す座標の列である。図の例では、建物Ｈ１のポリゴンの頂点Ｐ１、Ｐ２、Ｐ３、Ｐ４の各座標が格納されている。
代表点は、地物の位置を表す地点Ｃの座標である。代表点は、地物の図心を用いることが多いが、任意に設定可能である。
出入口線は、地物と道路とを関連づけるための情報である。建物Ｈ１の場合、玄関から道路に出るための線分Ｄが出入口線として登録される。具体的には、線分Ｄの両端の座標が登録されることになる。出入口線は、線分Ｄのうち、道路上の端点のみを登録するものとしてもよい。また、出入口線は、建物や駐車場など、出入りを伴う地物に設定されるものであり、地物の全てに設定する必要はない。図の例では、建物ＢＬＤに対して正面の出入口線ＤＢ１および駐車場ＢＬＤＰ側の出入口線ＤＢ２、建物Ｈ２〜Ｈ４に対してそれぞれ出入口線ＤＨ２〜ＤＨ４、駐車場ＰＫに対して出入口線ＤＰＫが設定されている。
【００２８】
到着地点Ｇは、地物の出入口線の道路上の端点から、いずれかの道路を経てたどりつけるネットワーク上の点である。建物Ｈ１の場合、図中に点線で示す通り、出入口線Ｄが関連づけられている道路Ｒ２１を経て、リンクＬ２に至ることができるため、リンクＬ２上に到着地点Ｇが設定されている。出入口線Ｄから道路Ｒ２１を図中右方向にたどり、ノードＮ１１で右折してノードＮ２に至る経路をとり、ノードＮ２を到着地点とすることもできる。本実施例では、建物Ｈ１からノードＮ２に至る道のりよりも、到着地点Ｇに至る道のりの方が短いから、このように設定した。到着地点は、一つに限定する必要はないから、ノードＮ２も到着地点に設定してもよい。
図の例では、建物Ｈ２〜Ｈ４に対する到着地点は点ＧＨと設定されている。建物ＢＬＤに対しては、点ＧＨおよび点ＧＢＬＤ２と設定されている。到着地点は、出入口線と同様、駐車場にも設定でき、図の例では、駐車場ＰＫに対して到着地点ＧＰＫが設定されている。駐車場ＰＫは、リンクＬ２に面しているため、出入口線ＤＰＫの端点と到着地点ＧＰＫが一致した状態となっている。
【００２９】
Ｂ４．到着地点の設定：
図４は、到着地点の設定について示す説明図である。建物ＢＬＤ１の出入口線ＤＢを対象とする到着地点について示した。
建物ＢＬＤ１の周辺の主ネットワークデータとしては、リンクＬ７、ノードＮ７およびリンクＬ５、Ｌ６およびノードＮ５、Ｎ６が存在する。準ネットワークデータとしては、破線で示したリンクＬ１４が存在する。
建物ＢＬＤ１の出入口線ＤＢからいずれかの道路を経て主ネットワークにたどりつく経路としては、図中に点線で示した３通りがあげられる。道路Ｒ２４を経てリンクＬ７にたどりつく経路、道路Ｒ２５を経てたリンクＬ６およびリンクＬ５にそれぞれたどりつく経路である。これらの各経路がリンクＬ７、Ｌ６、Ｌ５にたどりつく点が到着地点Ｇ７、Ｇ６、Ｇ５となる。
【００３０】
これらの到着地点は、経路探索によって求めることができる。本実施例では、それぞれの地物は、出入口線によって、いずれかの道路に関連づけられているから、出入口点、つまり出入口線の道路上の端点を始点とする経路探索によって到着地点を求めればよい。
この経路探索は、主ネットワークデータ、準ネットワークデータおよび道路のポリゴンの全てを用いてもよい。道路のポリゴンは、リンク、ノードで構成されている訳ではないが、隣接するポリゴンを指定するデータは持っているから、ポリゴン同士のつながり関係は規定されており、リンク、ノードと同様に、経路探索に使用することが可能である。出入口点を起点とする経路探索の結果、主ネットワークデータにたどり着いた点を到着地点とすればよい。
【００３１】
図の例のように、到着地点がＧ７、Ｇ６、Ｇ５の３点見いだされる場合、これらの３点を建物ＢＬＤ１の到着地点として用いてもよいし、例えば、地物からの道のりが最短の地点、地物からの距離が最短の地点、地物から到着地点までの経路と準ネットワークデータとの重複部分が多い点、地物から出発点に向かう方角に近い点などの基準で選択してもよい。
図の例においては、地物からの道のりや距離を基準として選べば、建物ＢＬＤ１に最も近い点Ｇ５が到着地点となる。準ネットワークデータとの重複部分を基準として選べば、点Ｇ６が到着地点となる。出発地が図の左端方向にある場合には、出発地の方角を基準として選べば、点Ｇ７が到着地点となる。
【００３２】
本実施例では、上述の手順で、到着地点を設定し、地物データ２１１に予め設定しておくものとした。到着地点は、予め設定しておくのではなく、経路探索などの処理の過程で求めるものとしてもよい。
【００３３】
Ｃ．経路探索処理：
図５は、経路探索処理（１）のフローチャートである。ナビゲーション装置１００の経路探索部１０７が主として実行する処理であり、ハードウェア的にはナビゲーション装置１００のＣＰＵ（以下、単に「ＣＰＵ」という）が実行する処理である。
【００３４】
この処理では、ＣＰＵは出発地および目的地を入力する（ステップＳ１０）。出発地は、ユーザが指定してもよいし、ＧＰＳなどで取得した現在位置を出発地に設定してもよい。
目的地は、地物を指定してもよいし、座標値で指定してもよい。
【００３５】
ＣＰＵは、指定された目的地に対する到着地点を取得する（ステップＳ１１）。目的地となる地物が指定されている場合は、指定された地物に対応する地物データから到着地点を読み出せばよい。目的地が座標で指定されている場合には、当該座標がいずれのポリゴンに含まれるかを特定し、特定されたポリゴンの地物データに対応する到着地点を読み出せばよい。
到着地点が予め地物データに格納されていない場合には、図４で説明した経路探索を行って到着地点を得ればよい。
【００３６】
次に、ＣＰＵは、到着地点を起点とする経路探索を行い、駐車場を探索する（ステップＳ１２）。この駐車場は、代替目的地として後述する経路探索に使用される地点である。
図の右側に、駐車場の探索例を示した。ユーザが指定した目的地Ｈ０に対して道路Ｒ０３を経た位置にある到着地点ＧＨ０が設定されているとする。ＣＰＵは、到着地点ＧＨ０を起点として経路探索を行うと、リンクＬ０２を上方にたどった駐車場ＰＫ２、およびリンクＬ０２を下方にたどり、リンクＬ００をたどった駐車場ＰＫ１を探索することができる。探索範囲は、目的地Ｈ０から所定の距離内にあること、到着地点ＧＨ０から所定の道のり内にあること、などの条件で規制される。
探索においてそれぞれの駐車場を見いだすことができるのは、駐車場ＰＫ１、ＰＫ２について、それぞれ主ネットワークのリンク上に到着地点ＧＰＫ１、ＧＰＫ２が設定されているからである。このように到着地点が設定されていることにより、ＣＰＵは、駐車場ＰＫ１、ＰＫ２の出入口がそれぞれリンクＬ００、Ｌ０２に開かれていることを特定でき、これらの駐車場を探索結果として抽出することができるのである。
【００３７】
ＣＰＵは、こうして探索された駐車場のうち、到着地点からの道のりが最短となる駐車場を選択する(ステップＳ１３)。図中の例では、到着地点ＧＨ０に近い駐車場ＰＫ２が選択される。
そして、選択された駐車場ＰＫ２を代替目的地として経路探索を行い（ステップＳ１４）、出発地から駐車場ＰＫ２の到着地点ＧＰＫ２までの経路、および駐車場ＧＰＫ２から到着地点ＧＨ０までの経路を出力する（ステップＳ１５）。更に、到着地点ＧＨ０から目的地Ｈ０までの経路を出力してもよい。
【００３８】
図６は、経路探索処理（２）のフローチャートである。図５で説明した処理と同様、ＣＰＵは、出発地、目的地を入力し（ステップＳ１０）、目的地に対する到着地点を取得する(ステップＳ１１)。
【００３９】
そして、ＣＰＵは到着地点を起点とする経路探索によって駐車場を探索する（ステップＳ１２ａ）。ここでは、主ネットワークデータのみならず、準ネットワークデータおよび道路のポリゴンデータも用いて探索するものとした。
図の右側に探索例を示した。主ネットワークデータは実線で示したリンクＬ００、Ｌ０１およびノードＮである。準ネットワークデータは、破線で示したＬ０２ａである。目的地Ｈ０に対する到着地点は、道路Ｒ０３および準ネットワークデータのリンクＬ０２ａを経て主ネットワークにたどりつく点ＧＨ０ａである（ノードＮと一致する）。
到着地点ＧＨ０ａを起点とする経路探索を行うと、ＣＰＵは、リンクＬ００をたどって駐車場ＰＫ１を発見する。また、準ネットワークデータも活用するため、リンクＬ０２ａをたどって駐車場ＰＫ２を発見する。探索の範囲は、図５で説明したのと同様、目的地からの距離等で規制すればよい。
【００４０】
こうして駐車場ＰＫ１、ＰＫ２が発見されると、ＣＰＵは到着地点からの経路と、目的地から到着地点までの経路が重複する駐車場を選択する(ステップＳ１３ａ)。図の例では、目的地から到着地点までの経路は、図中に点線で示した通り、道路Ｒ０３、リンクＬ０２ａを通る経路である。到着地点から駐車場ＰＫ１に至る経路はリンクＬ００に沿う左矢印であるから、上述の点線の経路とは重複しない。これに対し、到着地点から駐車場ＰＫ２に至る経路はリンクＬ０２ａに沿う上矢印の経路であるから、上述の点線の経路と重複する。従って、図の例では、駐車場ＰＫ２が選択されることになる。
【００４１】
こうして駐車場が選択されると、ＣＰＵは選択された駐車場を目的地として経路探索を行い（ステップＳ１４）、出発地から駐車場ＰＫ２までの経路、および駐車場ＰＫ２から到着地点までの経路を出力する（ステップＳ１５ａ）。この処理例では、これらの二つの経路が、部分的に重複している場合には、駐車場ＰＫ２から到着地点までの経路のうち、重複している部分を消去して表示してもよい。こうすることにより、無用な大回りを回避することができる。
【００４２】
駐車場を選択する処理（図５のステップＳ１３および図６のステップＳ１３ａ）は、双方の基準を合わせて適用してもよい。例えば、図６のステップＳ１３ａにおいて、経路が重複する駐車場を選択する処理を行い、この処理で駐車場が一つに決まらなかった場合、つまり、この処理で複数の駐車場が選択された場合や、一つも駐車場が選択されなかった場合には、それぞれ残った駐車場の中で、道のりが最短となる駐車場を選択する（図５のステップＳ１３）ようにしてもよい。
【００４３】
また、駐車場の経路探索において、準ネットワークを使うことに合わせ、目的地Ｈ０から準ネットワークにたどりついた点を到着地点としてもよい。図６の例では、道路Ｒ０３が準リンクＬ０２ａに交差する点ＧＨ１ａが到着地点となる。この点を基準とする経路探索によっても、駐車場ＰＫ１、ＰＫ２を発見することができるが、最短の道のりとなる駐車場ＰＫ２が選択されることになる。
ただし、この場合には、出発地から到着地点ＧＨ１ａに至る経路探索においても、準ネットワークを使う必要が出てくる。かかる事態を回避するため、駐車場などの代替目的地を探索するための到着地点ＧＨ１ａと、出発地からの経路探索を行う際に用いる到着地点ＧＨ０ａの双方を建物Ｈ０に対して設定しておくようにしてもよい。
【００４４】
Ｄ．経路探索例
本実施例の処理によれば、図５および図６に示した通り、目的地Ｈ０に対する到着地点を起点とする経路探索によって代替目的地となるべき駐車場を探索することにより、川ＲＶを隔てた不便な駐車場ＰＫ１ではなく、利便性の高い駐車場ＰＫ２を選択することが可能となる。
以下、本実施例によって利便性の高い駐車場が選択される他の例を示す。
【００４５】
図７は、代替目的地の探索例（１）を示す説明図である。図中の目的地Ｈ７が指定された場合を考える。到着地点は道路Ｒ７０を経てリンクＬ７１に至った点Ｇ７に設定されている。
仮に、従来技術を用いたとすると、目的地Ｈ７から最短の距離Ｄ７にあるノードＮ７１を起点とする経路探索によって駐車場が探索されるため、矢印Ｐ７２に示すようにリンクＬ７３に沿う経路探索が行われ駐車場ＰＫ７２が選択される。
これに対し、実施例によれば、到着地点Ｇ７を起点として経路探索するため、矢印Ｐ７１に示すようにリンクＬ７１に沿って経路探索が行われ、駐車場ＰＫ７１が選択される。
実施例において、到着地点Ｇ７を起点とする経路探索の結果、駐車場ＰＫ２も発見される可能性はあるが、到着地点から最短の道のりとなっている駐車場ＰＫ７１が選択されることになる（図５のステップＳ１３参照）。
【００４６】
図８は、代替目的地の探索例（２）を示す説明図である。図中の目的地Ｈ８が指定された場合を考える。到着地点は道路Ｒ８０を経てリンクＬ８１に至った点Ｇ８（ノードＮ８２と一致する）に設定されている。目的地付近の道路Ｒ８３は、道路Ｒ８０の下を通る立体交差となっている。
仮に、従来技術を用いたとすると、目的地Ｈ８から最短の距離Ｄ８にあるノードＮ８１を起点とする経路探索によって駐車場が探索されるため、矢印Ｐ８１、８２に示すようにリンクＬ８３、Ｌ８２に沿う経路探索が行われ駐車場ＰＫ８２が選択される。
これに対し、実施例によれば、到着地点Ｇ８を起点として経路探索するため、矢印Ｐ８３に示すようにリンクＬ８１に沿って経路探索が行われ、駐車場ＰＫ８１が選択される。
実施例において、到着地点Ｇ８を起点とする経路探索の結果、駐車場ＰＫ８２も発見される可能性はあるが、到着地点から最短の道のりとなっている駐車場ＰＫ８１が選択されることになる（図５のステップＳ１３参照）。
【００４７】
これらの例に示した通り、本実施例によれば、目的地周辺の道路の状態を反映して、利便性の高い駐車場を選択することが可能となる。
以上の実施例では、代替目的地を駐車場とする例を示したが、本発明は、駐車場以外を代替目的地とする場合にも適用可能である。例えば、目的地周辺で店舗等に立ち寄ってから目的地に向かいたい場合などは、店舗を代替目的地とすればよい。本実施例で、駐車場を探索した処理に代えて、指定された店舗を探索する処理を行えばよい。それぞれの地物が指定された店舗に該当するか否かは、地物データの属性を参照して判断することができる。また、どのような店舗を代替目的地とするかは、ユーザが経路探索を行う際に指定してもよいし、予め設定しておいてもよい。
こうすることにより、目的地付近の地理に不慣れであっても、代替目的地の属性さえ指定すれば、目的地に向かうために利便性の高い場所への経路を知ることができる。
【００４８】
本発明は、必ずしも上述した実施例の全ての機能を備えている必要はなく、一部のみを実現するようにしてもよい。また、上述した内容に追加の機能を設けてもよい。
本発明は上述の実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、実施例においてハードウェア的に構成されている部分は、ソフトウェア的に構成することもでき、その逆も可能である。
【００４９】
また本発明は、以下に示す経路探索方法として構成することもできる。
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データとを有するコンピュータシステムによって指定された目的地に向かう際に利用可能な代替目的地までの経路を探索する経路探索方法であって、
出発地および目的地の指定を入力してメモリに記憶する入力ステップと、
前記地図データベースを参照して、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点を取得し、該到着地点を表す情報をメモリに記憶する到着地点取得ステップと、
前記ネットワークデータを参照して、前記到着地点を起点とする経路探索によって、該到着地点から到達可能な所定の属性を有する代替目的地を探索し、該代替目的地を表す情報をメモリに記憶する代替目的地探索ステップと、
前記ネットワークデータを参照して、前記出発地から前記探索された代替目的地までの経路探索を行う経路探索ステップとを備える経路探索方法である。
【００５０】
さらに、以下に示すコンピュータプログラムとして構成してもよい。
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データとを有するコンピュータシステムによって指定された目的地に向かう際に利用可能な代替目的地までの経路を探索するためのコンピュータプログラムであって、
出発地および目的地の指定を入力してメモリに記憶する入力機能と、
前記地図データベースを参照して、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点を取得し、該到着地点を表す情報をメモリに記憶する到着地点取得機能と、
前記ネットワークデータを参照して、前記到着地点を起点とする経路探索によって、該到着地点から到達可能な所定の属性を有する代替目的地を探索し、該代替目的地を表す情報をメモリに記憶する代替目的地探索機能と、
前記ネットワークデータを参照して、前記出発地から前記探索された代替目的地までの経路探索を行う経路探索機能とをコンピュータに実現させるためのコンピュータプログラムである。
【産業上の利用可能性】
【００５１】
本発明は、目的地が指定された時に利便性の高い代替目的地への経路を案内するために利用可能である。
【符号の説明】
【００５２】
１００…ナビゲーション装置
１０１…主制御部
１０２…送受信部
１０３…コマンド入力部
１０４…ＧＰＳ入力部
１０５…地図データベース記憶部
１０６…表示制御部
１０７…経路探索部
２００…サーバ
２０１…送受信部
２０２…データベース管理部
２１０…地図データベース記憶部
２１１…地物データ
２１２…文字データ
２１３…ネットワークデータ
【技術分野】
【０００１】
本発明は、指定された目的地に向かう際に利用可能な代替目的地までの経路を探索する経路探索システムに関する。
【背景技術】
【０００２】
道路をリンク、ノードで表したネットワークデータを用いて、指定された出発地から目的地までの経路を探索し、案内するナビゲーションシステムが普及している。自動車で移動する時にナビゲーションシステムを利用する場合、目的地に駐車場が存在するとは限らないから、目的地周辺の駐車場を代替目的地とし、この代替目的地に対して経路探索および案内を行うことが好ましい。
【０００３】
目的地周辺の駐車場は、従来、次の手順で探索されていた。経路探索に用いるネットワークデータ上で目的地に最短距離にあるノードを見つけ、このノードを出発地としてネットワークデータを用いた経路探索を行うことにより、上述のノードに近い駐車場を見つける。
【０００４】
また、別の方法として、特許文献１には、目的地から所定の距離範囲内にある駐車場を探索する技術が開示されている。所定の距離範囲内に駐車場が複数探索された場合には、駐車場の混雑情報、満車情報などに基づいて、経路探索すべき駐車場が決められる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−２６３５８１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
図１は、従来技術における駐車場の探索方法を示す説明図である。
目的地Ｈ０が指定された時に、その周辺の駐車場を探索する場合を考える。目的地Ｈ０からは細い通路を経て、道路Ｒ０２に至ることができる。道路Ｒ０２は、川ＲＶを超えたところにある道路Ｒ００、Ｒ０１と交差している。道路Ｒ００、Ｒ０１には、経路探索に使用するためのリンクＬ００、Ｌ０１およびノードＮが設定されている。目的地周辺には、道路Ｒ００に面して駐車場ＰＫ１があり、道路Ｒ０２に面して駐車場ＰＫ２がある。
従来技術では、目的地Ｈ０から最短の距離にあるノードＮを起点とする経路探索によって駐車場を探索していた。図示する通り、ネットワークデータは道路Ｒ００、Ｒ０１に整備されているだけなので、リンクＬ００に沿って矢印Ｐ方向に経路探索が行われ、駐車場ＰＫ１が案内すべき駐車場として選択される。
仮に、道路Ｒ０２にネットワークデータが整備されていたとしても、ノードＮを起点とする限り、ノードＮに近い駐車場ＰＫ１が選択されることに変わりはない。
【０００７】
また特許文献１に記載されている通り、目的地Ｈ０からの距離に基づいて駐車場を選択したとしても、駐車場ＰＫ１までの距離Ｄ１の方が、駐車場ＰＫ２までの距離Ｄ２よりも短いため、駐車場ＰＫ１が選択されることになる。
【０００８】
しかし、図の道路状態を見れば明らかな通り、目的地Ｈ０に行く際に便利なのは、駐車場ＰＫ１ではなく駐車場ＰＫ２である。このように、従来技術では、目的地Ｈ０にとって、必ずしも利便性の高い駐車場が選択されるとは限らなかった。
上述の課題は、駐車場を代替目的地とする場合に限らず、その他の代替目的地を用いる場合にも共通であった。本発明は、かかる課題に鑑み、目的地周辺の道路の状態を踏まえて、利便性の高い代替目的地への案内を可能とすることを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、指定された目的地に向かう際に利用可能な代替目的地までの経路を探索する経路探索システムとして構成することができる。代替目的地とは、例えば、自動車で目的地に向かう場合には駐車場、自転車で向かう場合には駐輪場、馬で向かう場合には馬場のように、ユーザが利用する移動手段を停めておく場所とすることができる。また、目的地に着く前に、花屋や菓子屋で手土産を買いたい場合や、喫茶店やレストランで時間を過ごしたい場合などには、これらの店舗を代替目的地とすることができる。
本発明においては、これらの代替目的地が予めユーザに指示されている訳ではない。本発明は、目的地周辺でユーザが利用したい代替目的地を探索した上で、その代替目的地までの経路探索を行うものである。
本発明において、これらの代替目的地の属性は、予め定めておいてもよいし、ユーザが指定してもよい。
【００１０】
経路探索システムは、地図データベース記憶部、入力部、到着地点取得部、代替目的地探索部、経路探索部を備える。
地図データベース記憶部は、道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データとを格納する。ネットワークデータは、通行規制も踏まえて自動車の経路探索に使用可能な主ネットワークと、経路探索に使用可能ではあるが通行規制の整備が完全とは言えない準ネットワークなどを混在して用意してもよい。
【００１１】
入力部は、出発地および目的地の指定を入力する。出発地は、ユーザの現在位置を自動的に入力するようにしてもよい。目的地は、地物データに含まれる特定の建物等を指定してもよいし、地図上で座標値を指定してもよい。入力部は、更に、駐車場、店舗といった代替目的地の属性を入力してもよい。
【００１２】
到着地点取得部は、ネットワークデータおよび地物データを含む地図データベースを参照して、上述の主ネットワーク、つまり自動車が通行可能な道路としてネットワークデータが整備された道路上の点であって、目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点を取得する。
到着地点は、地物データの一部として、建物等の地物ごとに設定されているものとしてもよい。この場合は、到着地点取得部は、目的地として指定された地物に対応する到着地点のデータを読み込めば済む。目的地が座標値で指定された場合には、到着地点取得部は、指定された座標が対応する地物を特定し、その地物に対応する到着地点のデータを読み込めばよい。
これに対し、到着地点を予め用意しない構成とすることもできる。この場合には、到着地点取得部は、目的地を起点する経路探索によって、到着地点を見いだすことになる。この場合の経路探索には、通行規制の整備が完全とは言えない準ネットワークや、ネットワークが一切整備されてはいない道路も用いることができる。ネットワークが整備されていない道路については、地物データに含まれる道路のポリゴンデータの連結具合をネットワークデータとして扱うことにより経路探索の対象とすることができる。
【００１３】
代替目的地探索部は、ネットワークデータを参照して、到着地点を起点とする経路探索によって、到着地点から到達可能な所定の属性を有する代替目的地を探索する。代替目的地が探索されると、経路探索部は、ネットワークデータを参照して、出発地から探索された代替目的地までの経路探索を行う。
代替目的地の探索は、主ネットワークのみを用いてもよいし、準ネットワークや道路のポリゴンデータを併用してもよい。主ネットワークのみを用いる場合には、代替目的地は主ネットワークに関連づけられているはずであるから、経路探索部は、代替目的地をそのまま目的地とみなして出発地からの経路探索を行えばよい。
準ネットワークおよび道路のポリゴンデータを併用する場合には、代替目的地が主ネットワークに関連づけられているとは限らない。従って、経路探索部は、代替目的地に対して到着地点を取得し、この到着地点を目的地とみなして出発地からの経路探索を行う。
【００１４】
本発明の経路探索システムによれば、目的地に対応する到着地点を起点として代替目的地の探索を行う。到着地点は、単に目的地から最短距離にあるといった条件ではなく、目的地からの道路の状態を考慮して設定された点であるから、無用な遠回りが必要となるような場所が代替目的地となることを抑制でき、利便性の高い代替目的地が設定される。
【００１５】
本発明において、複数の代替目的地が探索された場合には、全てに対して出発地からの経路探索を行ってもよいが、探索された代替目的地のいずれかを次に示す態様によって優先してもよい。優先とは、代替目的地を一つだけ選択すること、または複数の代替目的地のうち経路探索の対象とする候補をいくつか絞り込むことを意味する。
第１の態様として、到着地点から代替目的地までの道のりが短い代替目的地を優先してもよい。こうすることで、代替目的地から目的地までの距離までを短くすることができる。
第２の態様として、到着地点から代替目的地までの経路が、目的地から到着地点までの経路と一部または全部において重複する代替目的地を優先してもよい。代替目的地が、目的地を挟んで到着地点と逆側に探索されることもある。このような代替目的地は、代替目的地から到着地点まで戻るまでなく目的地にたどりつける点で、利便性が高いことがある。上述のように、経路の重複を考慮することにより、目的地を挟んで到着地点と逆側にある代替目的地を優先することが可能となる。
第１の態様、第２の態様は、併せて適用してもよい。
【００１６】
代替目的地の探索には、ネットワークデータに加えて、地物データに含まれる道路のポリゴンデータも用いてもよい。つまり、主ネットワーク、準ネットワークおよびポリゴンを用いた探索を行ってもよい。
こうすることにより、探索の範囲が広がり、より適切な代替目的地を探索しやすくなる。
準ネットワークやポリゴンについて通行規制が十分には整備されていない場合であっても、駐車場がある道路や、車線幅が十分に広い道路などは、車両が通行可能なこともある。これらのデータを併用して代替目的地の探索を行う場合には、このように道路沿いに存在する地物や、道路の属性に基づいて、通行可否を判断した上で、探索に利用可能な道路を絞り込むようにしてもよい。
【００１７】
本発明は、その他、コンピュータを用いた経路探索方法として構成してもよいし、かかる経路探索をコンピュータに実行させるためのコンピュータプログラムとして構成してもよい。また、かかるコンピュータプログラムを記録したコンピュータが読み取り可能な記録媒体として構成してもよい。記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【図面の簡単な説明】
【００１８】
【図１】従来技術における駐車場の探索方法を示す説明図である。
【図２】経路探索システムの構成を示す説明図である。
【図３】地図データベースの構造を示す説明図である。
【図４】到着地点の設定について示す説明図である。
【図５】経路探索処理（１）のフローチャートである。
【図６】経路探索処理（２）のフローチャートである。
【図７】代替目的地の探索例（１）を示す説明図である。
【図８】代替目的地の探索例（２）を示す説明図である。
【発明を実施するための形態】
【００１９】
本発明の実施例について以下の順序で説明する。
Ａ．システム構成：
Ｂ．データ構造：
Ｂ１．ネットワークデータ：
Ｂ２．文字データ：
Ｂ３．地物データ：
Ｂ４．文字データ：
Ｃ．経路探索処理：
Ｄ．経路探索例
【実施例１】
【００２０】
Ａ．システム構成：
図２は、経路探索システムの構成を示す説明図である。経路探索システムは、ナビゲーション装置１００として構成される。本実施例では、ナビゲーション装置１００は、地図データ等を提供するサーバ２００とネットワークＮＥで接続されており、サーバ２００から地図データベースの更新を受けられるものとした。ナビゲーション装置１００は、スタンドアロンで稼働する構成としてもよいし、その機能の一部をサーバ２００等で実行する構成としてもよい。
【００２１】
サーバ２００は、地図データベース記憶部２１０、送受信部２０１、およびデータベース管理部２０２を備えている。送受信部２０１、データベース管理部２０２は、ハードウェア的に構成してもよいが、本実施例では、これらの機能を実現するコンピュータプログラムをインストールすることによって、ソフトウェア的に構成するものとした。
【００２２】
送受信部２０１は、ナビゲーション装置１００とネットワークＮＥを介した通信を行う。本実施例では、地図データベース記憶部２１０に格納されたデータや、その提供を求めるためのコマンド等が通信される。
データベース管理部２０２は、ナビゲーション装置１００から要求された地図情報を、地図データベース記憶部２１０から読み出す。地図データベース記憶部２１０には、地物データ２１１、文字データ２１２、およびネットワークデータ２１３が格納されている。
地物データ２１１は、道路や建物など地図に描画すべき地物のポリゴンデータである。文字データ２１２は、地図上に表示すべき文字情報である。例えば、建物の名称や地名などの文字情報が含まれる。ネットワークデータ２１３は、道路をノード、リンクのつながりで表したデータである。
【００２３】
ナビゲーション装置１００には、主制御部１０１の下で稼働する種々の機能ブロックが構成されている。本実施例では、主制御部１０１および各機能ブロックは、それぞれの機能を実現するソフトウェアをインストールすることによって構成したが、その一部または全部をハードウェア的に構成してもよい。
送受信部１０２は、サーバ２００とのネットワークＮＥを介した通信を行う。本実施例では、地図データベースおよびその提供を受けるためのコマンドの送受信が主として行われる。
コマンド入力部１０３は、ナビゲーション装置１００に設けられたボタン、レバー、タッチパネル等の操作を通じて、ユーザからの指示を入力する。本実施例における指示としては、経路探索の出発地、目的地の指定などが挙げられる。
ＧＰＳ入力部１０４は、ＧＰＳ（Global Positioning System）を用いてユーザの現在位置を入力する。
地図データベース記憶部１０５は、サーバ２００から提供された地図データベース記憶部２１０に記憶されている地図データベースを格納する。本実施例では、サーバ２００が備える地図データベースの全体をナビゲーション装置１００内の地図データベース記憶部１０５にも格納するものとしたが、経路探索や地図表示に必要となる部分のみを、その都度、サーバ２００から取得するものとしてもよい。
経路探索部１０７は、地図データベースを参照して、経路探索を行う。
表示制御部１０６は、地図データベース記憶部１０５を用いてナビゲーション装置１００のディスプレイに地図および探索された経路を表示する。
【００２４】
Ｂ．データ構造：
図３は、地図データベースの構造を示す説明図である。地物データ、文字データ、ネットワークデータに格納される情報の概要を示した。
【００２５】
Ｂ１．ネットワークデータ：
ネットワークデータとは、道路をリンク、ノードで表したデータである。本実施例では、ネットワークデータとして主ネットワークデータと、準ネットワークデータの２種類が用意されている。図中に実線で示したリンクＬ１〜Ｌ４およびノードＮ１、Ｎ２が主ネットワークデータであり、破線で示したリンクＬ１１〜Ｌ１３およびノードＮ１１、Ｎ１２が準ネットワークデータである。
主ネットワークデータおよび準ネットワークデータともに、それぞれに属するリンクデータおよびノードデータを格納している。リンクデータは、それぞれのリンクを形成する点列の座標、国道・県道等の種別、車線数その他の属性情報や通行規制情報などを記録している。ノードデータは、座標値、通行規制などを記録している。
ただし、主ネットワークデータは、現地調査によって通行規制が十分に整備されたデータであり、車両の経路探索に支障なく用いることができるデータとなっている。これに対し、準ネットワークデータは、通行規制の整備が十分とは言えないデータであり、車両の経路探索では、使用しない方が好ましいデータである。本実施例でも、経路探索は原則として主ネットワークデータを用いて行うものとしている。
【００２６】
Ｂ２．文字データ：
文字データ２１２は、地物の名称や地名などを表示する文字を規定するデータである。図中には、建物ＢＬＤの名称を表示するためのデータ例を示した。文字データは、内容、位置、地物、フォント、サイズなどの情報を格納する。
内容は、表示すべき文字列であり、図中の例では、「△△(株)」という会社名称である。
位置は、文字を表示する位置である。本実施例では、文字列の左下の点Ｐ５を基準点として、この座標値を指定するものとした。
地物は、文字が関連づけられる地物データのポリゴン名称である。
フォント、サイズは、表示する際のフォントおよびサイズの指定である。
この他、色、太字など、種々の属性を指定可能としてもよい。
【００２７】
Ｂ３．地物データ：
地物データ２１１について、建物Ｈ１を例にとって構造を示す。地物データ２１１は、建物、道路等の地物を描画するためのポリゴンデータであり、名称、形状、代表点、出入り口線、到着地点、属性などを格納している。
名称は、地物の名称である。ポリゴンに固有のＩＤを用いてもよい。
形状は、地物のポリゴンの頂点を示す座標の列である。図の例では、建物Ｈ１のポリゴンの頂点Ｐ１、Ｐ２、Ｐ３、Ｐ４の各座標が格納されている。
代表点は、地物の位置を表す地点Ｃの座標である。代表点は、地物の図心を用いることが多いが、任意に設定可能である。
出入口線は、地物と道路とを関連づけるための情報である。建物Ｈ１の場合、玄関から道路に出るための線分Ｄが出入口線として登録される。具体的には、線分Ｄの両端の座標が登録されることになる。出入口線は、線分Ｄのうち、道路上の端点のみを登録するものとしてもよい。また、出入口線は、建物や駐車場など、出入りを伴う地物に設定されるものであり、地物の全てに設定する必要はない。図の例では、建物ＢＬＤに対して正面の出入口線ＤＢ１および駐車場ＢＬＤＰ側の出入口線ＤＢ２、建物Ｈ２〜Ｈ４に対してそれぞれ出入口線ＤＨ２〜ＤＨ４、駐車場ＰＫに対して出入口線ＤＰＫが設定されている。
【００２８】
到着地点Ｇは、地物の出入口線の道路上の端点から、いずれかの道路を経てたどりつけるネットワーク上の点である。建物Ｈ１の場合、図中に点線で示す通り、出入口線Ｄが関連づけられている道路Ｒ２１を経て、リンクＬ２に至ることができるため、リンクＬ２上に到着地点Ｇが設定されている。出入口線Ｄから道路Ｒ２１を図中右方向にたどり、ノードＮ１１で右折してノードＮ２に至る経路をとり、ノードＮ２を到着地点とすることもできる。本実施例では、建物Ｈ１からノードＮ２に至る道のりよりも、到着地点Ｇに至る道のりの方が短いから、このように設定した。到着地点は、一つに限定する必要はないから、ノードＮ２も到着地点に設定してもよい。
図の例では、建物Ｈ２〜Ｈ４に対する到着地点は点ＧＨと設定されている。建物ＢＬＤに対しては、点ＧＨおよび点ＧＢＬＤ２と設定されている。到着地点は、出入口線と同様、駐車場にも設定でき、図の例では、駐車場ＰＫに対して到着地点ＧＰＫが設定されている。駐車場ＰＫは、リンクＬ２に面しているため、出入口線ＤＰＫの端点と到着地点ＧＰＫが一致した状態となっている。
【００２９】
Ｂ４．到着地点の設定：
図４は、到着地点の設定について示す説明図である。建物ＢＬＤ１の出入口線ＤＢを対象とする到着地点について示した。
建物ＢＬＤ１の周辺の主ネットワークデータとしては、リンクＬ７、ノードＮ７およびリンクＬ５、Ｌ６およびノードＮ５、Ｎ６が存在する。準ネットワークデータとしては、破線で示したリンクＬ１４が存在する。
建物ＢＬＤ１の出入口線ＤＢからいずれかの道路を経て主ネットワークにたどりつく経路としては、図中に点線で示した３通りがあげられる。道路Ｒ２４を経てリンクＬ７にたどりつく経路、道路Ｒ２５を経てたリンクＬ６およびリンクＬ５にそれぞれたどりつく経路である。これらの各経路がリンクＬ７、Ｌ６、Ｌ５にたどりつく点が到着地点Ｇ７、Ｇ６、Ｇ５となる。
【００３０】
これらの到着地点は、経路探索によって求めることができる。本実施例では、それぞれの地物は、出入口線によって、いずれかの道路に関連づけられているから、出入口点、つまり出入口線の道路上の端点を始点とする経路探索によって到着地点を求めればよい。
この経路探索は、主ネットワークデータ、準ネットワークデータおよび道路のポリゴンの全てを用いてもよい。道路のポリゴンは、リンク、ノードで構成されている訳ではないが、隣接するポリゴンを指定するデータは持っているから、ポリゴン同士のつながり関係は規定されており、リンク、ノードと同様に、経路探索に使用することが可能である。出入口点を起点とする経路探索の結果、主ネットワークデータにたどり着いた点を到着地点とすればよい。
【００３１】
図の例のように、到着地点がＧ７、Ｇ６、Ｇ５の３点見いだされる場合、これらの３点を建物ＢＬＤ１の到着地点として用いてもよいし、例えば、地物からの道のりが最短の地点、地物からの距離が最短の地点、地物から到着地点までの経路と準ネットワークデータとの重複部分が多い点、地物から出発点に向かう方角に近い点などの基準で選択してもよい。
図の例においては、地物からの道のりや距離を基準として選べば、建物ＢＬＤ１に最も近い点Ｇ５が到着地点となる。準ネットワークデータとの重複部分を基準として選べば、点Ｇ６が到着地点となる。出発地が図の左端方向にある場合には、出発地の方角を基準として選べば、点Ｇ７が到着地点となる。
【００３２】
本実施例では、上述の手順で、到着地点を設定し、地物データ２１１に予め設定しておくものとした。到着地点は、予め設定しておくのではなく、経路探索などの処理の過程で求めるものとしてもよい。
【００３３】
Ｃ．経路探索処理：
図５は、経路探索処理（１）のフローチャートである。ナビゲーション装置１００の経路探索部１０７が主として実行する処理であり、ハードウェア的にはナビゲーション装置１００のＣＰＵ（以下、単に「ＣＰＵ」という）が実行する処理である。
【００３４】
この処理では、ＣＰＵは出発地および目的地を入力する（ステップＳ１０）。出発地は、ユーザが指定してもよいし、ＧＰＳなどで取得した現在位置を出発地に設定してもよい。
目的地は、地物を指定してもよいし、座標値で指定してもよい。
【００３５】
ＣＰＵは、指定された目的地に対する到着地点を取得する（ステップＳ１１）。目的地となる地物が指定されている場合は、指定された地物に対応する地物データから到着地点を読み出せばよい。目的地が座標で指定されている場合には、当該座標がいずれのポリゴンに含まれるかを特定し、特定されたポリゴンの地物データに対応する到着地点を読み出せばよい。
到着地点が予め地物データに格納されていない場合には、図４で説明した経路探索を行って到着地点を得ればよい。
【００３６】
次に、ＣＰＵは、到着地点を起点とする経路探索を行い、駐車場を探索する（ステップＳ１２）。この駐車場は、代替目的地として後述する経路探索に使用される地点である。
図の右側に、駐車場の探索例を示した。ユーザが指定した目的地Ｈ０に対して道路Ｒ０３を経た位置にある到着地点ＧＨ０が設定されているとする。ＣＰＵは、到着地点ＧＨ０を起点として経路探索を行うと、リンクＬ０２を上方にたどった駐車場ＰＫ２、およびリンクＬ０２を下方にたどり、リンクＬ００をたどった駐車場ＰＫ１を探索することができる。探索範囲は、目的地Ｈ０から所定の距離内にあること、到着地点ＧＨ０から所定の道のり内にあること、などの条件で規制される。
探索においてそれぞれの駐車場を見いだすことができるのは、駐車場ＰＫ１、ＰＫ２について、それぞれ主ネットワークのリンク上に到着地点ＧＰＫ１、ＧＰＫ２が設定されているからである。このように到着地点が設定されていることにより、ＣＰＵは、駐車場ＰＫ１、ＰＫ２の出入口がそれぞれリンクＬ００、Ｌ０２に開かれていることを特定でき、これらの駐車場を探索結果として抽出することができるのである。
【００３７】
ＣＰＵは、こうして探索された駐車場のうち、到着地点からの道のりが最短となる駐車場を選択する(ステップＳ１３)。図中の例では、到着地点ＧＨ０に近い駐車場ＰＫ２が選択される。
そして、選択された駐車場ＰＫ２を代替目的地として経路探索を行い（ステップＳ１４）、出発地から駐車場ＰＫ２の到着地点ＧＰＫ２までの経路、および駐車場ＧＰＫ２から到着地点ＧＨ０までの経路を出力する（ステップＳ１５）。更に、到着地点ＧＨ０から目的地Ｈ０までの経路を出力してもよい。
【００３８】
図６は、経路探索処理（２）のフローチャートである。図５で説明した処理と同様、ＣＰＵは、出発地、目的地を入力し（ステップＳ１０）、目的地に対する到着地点を取得する(ステップＳ１１)。
【００３９】
そして、ＣＰＵは到着地点を起点とする経路探索によって駐車場を探索する（ステップＳ１２ａ）。ここでは、主ネットワークデータのみならず、準ネットワークデータおよび道路のポリゴンデータも用いて探索するものとした。
図の右側に探索例を示した。主ネットワークデータは実線で示したリンクＬ００、Ｌ０１およびノードＮである。準ネットワークデータは、破線で示したＬ０２ａである。目的地Ｈ０に対する到着地点は、道路Ｒ０３および準ネットワークデータのリンクＬ０２ａを経て主ネットワークにたどりつく点ＧＨ０ａである（ノードＮと一致する）。
到着地点ＧＨ０ａを起点とする経路探索を行うと、ＣＰＵは、リンクＬ００をたどって駐車場ＰＫ１を発見する。また、準ネットワークデータも活用するため、リンクＬ０２ａをたどって駐車場ＰＫ２を発見する。探索の範囲は、図５で説明したのと同様、目的地からの距離等で規制すればよい。
【００４０】
こうして駐車場ＰＫ１、ＰＫ２が発見されると、ＣＰＵは到着地点からの経路と、目的地から到着地点までの経路が重複する駐車場を選択する(ステップＳ１３ａ)。図の例では、目的地から到着地点までの経路は、図中に点線で示した通り、道路Ｒ０３、リンクＬ０２ａを通る経路である。到着地点から駐車場ＰＫ１に至る経路はリンクＬ００に沿う左矢印であるから、上述の点線の経路とは重複しない。これに対し、到着地点から駐車場ＰＫ２に至る経路はリンクＬ０２ａに沿う上矢印の経路であるから、上述の点線の経路と重複する。従って、図の例では、駐車場ＰＫ２が選択されることになる。
【００４１】
こうして駐車場が選択されると、ＣＰＵは選択された駐車場を目的地として経路探索を行い（ステップＳ１４）、出発地から駐車場ＰＫ２までの経路、および駐車場ＰＫ２から到着地点までの経路を出力する（ステップＳ１５ａ）。この処理例では、これらの二つの経路が、部分的に重複している場合には、駐車場ＰＫ２から到着地点までの経路のうち、重複している部分を消去して表示してもよい。こうすることにより、無用な大回りを回避することができる。
【００４２】
駐車場を選択する処理（図５のステップＳ１３および図６のステップＳ１３ａ）は、双方の基準を合わせて適用してもよい。例えば、図６のステップＳ１３ａにおいて、経路が重複する駐車場を選択する処理を行い、この処理で駐車場が一つに決まらなかった場合、つまり、この処理で複数の駐車場が選択された場合や、一つも駐車場が選択されなかった場合には、それぞれ残った駐車場の中で、道のりが最短となる駐車場を選択する（図５のステップＳ１３）ようにしてもよい。
【００４３】
また、駐車場の経路探索において、準ネットワークを使うことに合わせ、目的地Ｈ０から準ネットワークにたどりついた点を到着地点としてもよい。図６の例では、道路Ｒ０３が準リンクＬ０２ａに交差する点ＧＨ１ａが到着地点となる。この点を基準とする経路探索によっても、駐車場ＰＫ１、ＰＫ２を発見することができるが、最短の道のりとなる駐車場ＰＫ２が選択されることになる。
ただし、この場合には、出発地から到着地点ＧＨ１ａに至る経路探索においても、準ネットワークを使う必要が出てくる。かかる事態を回避するため、駐車場などの代替目的地を探索するための到着地点ＧＨ１ａと、出発地からの経路探索を行う際に用いる到着地点ＧＨ０ａの双方を建物Ｈ０に対して設定しておくようにしてもよい。
【００４４】
Ｄ．経路探索例
本実施例の処理によれば、図５および図６に示した通り、目的地Ｈ０に対する到着地点を起点とする経路探索によって代替目的地となるべき駐車場を探索することにより、川ＲＶを隔てた不便な駐車場ＰＫ１ではなく、利便性の高い駐車場ＰＫ２を選択することが可能となる。
以下、本実施例によって利便性の高い駐車場が選択される他の例を示す。
【００４５】
図７は、代替目的地の探索例（１）を示す説明図である。図中の目的地Ｈ７が指定された場合を考える。到着地点は道路Ｒ７０を経てリンクＬ７１に至った点Ｇ７に設定されている。
仮に、従来技術を用いたとすると、目的地Ｈ７から最短の距離Ｄ７にあるノードＮ７１を起点とする経路探索によって駐車場が探索されるため、矢印Ｐ７２に示すようにリンクＬ７３に沿う経路探索が行われ駐車場ＰＫ７２が選択される。
これに対し、実施例によれば、到着地点Ｇ７を起点として経路探索するため、矢印Ｐ７１に示すようにリンクＬ７１に沿って経路探索が行われ、駐車場ＰＫ７１が選択される。
実施例において、到着地点Ｇ７を起点とする経路探索の結果、駐車場ＰＫ２も発見される可能性はあるが、到着地点から最短の道のりとなっている駐車場ＰＫ７１が選択されることになる（図５のステップＳ１３参照）。
【００４６】
図８は、代替目的地の探索例（２）を示す説明図である。図中の目的地Ｈ８が指定された場合を考える。到着地点は道路Ｒ８０を経てリンクＬ８１に至った点Ｇ８（ノードＮ８２と一致する）に設定されている。目的地付近の道路Ｒ８３は、道路Ｒ８０の下を通る立体交差となっている。
仮に、従来技術を用いたとすると、目的地Ｈ８から最短の距離Ｄ８にあるノードＮ８１を起点とする経路探索によって駐車場が探索されるため、矢印Ｐ８１、８２に示すようにリンクＬ８３、Ｌ８２に沿う経路探索が行われ駐車場ＰＫ８２が選択される。
これに対し、実施例によれば、到着地点Ｇ８を起点として経路探索するため、矢印Ｐ８３に示すようにリンクＬ８１に沿って経路探索が行われ、駐車場ＰＫ８１が選択される。
実施例において、到着地点Ｇ８を起点とする経路探索の結果、駐車場ＰＫ８２も発見される可能性はあるが、到着地点から最短の道のりとなっている駐車場ＰＫ８１が選択されることになる（図５のステップＳ１３参照）。
【００４７】
これらの例に示した通り、本実施例によれば、目的地周辺の道路の状態を反映して、利便性の高い駐車場を選択することが可能となる。
以上の実施例では、代替目的地を駐車場とする例を示したが、本発明は、駐車場以外を代替目的地とする場合にも適用可能である。例えば、目的地周辺で店舗等に立ち寄ってから目的地に向かいたい場合などは、店舗を代替目的地とすればよい。本実施例で、駐車場を探索した処理に代えて、指定された店舗を探索する処理を行えばよい。それぞれの地物が指定された店舗に該当するか否かは、地物データの属性を参照して判断することができる。また、どのような店舗を代替目的地とするかは、ユーザが経路探索を行う際に指定してもよいし、予め設定しておいてもよい。
こうすることにより、目的地付近の地理に不慣れであっても、代替目的地の属性さえ指定すれば、目的地に向かうために利便性の高い場所への経路を知ることができる。
【００４８】
本発明は、必ずしも上述した実施例の全ての機能を備えている必要はなく、一部のみを実現するようにしてもよい。また、上述した内容に追加の機能を設けてもよい。
本発明は上述の実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、実施例においてハードウェア的に構成されている部分は、ソフトウェア的に構成することもでき、その逆も可能である。
【００４９】
また本発明は、以下に示す経路探索方法として構成することもできる。
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データとを有するコンピュータシステムによって指定された目的地に向かう際に利用可能な代替目的地までの経路を探索する経路探索方法であって、
出発地および目的地の指定を入力してメモリに記憶する入力ステップと、
前記地図データベースを参照して、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点を取得し、該到着地点を表す情報をメモリに記憶する到着地点取得ステップと、
前記ネットワークデータを参照して、前記到着地点を起点とする経路探索によって、該到着地点から到達可能な所定の属性を有する代替目的地を探索し、該代替目的地を表す情報をメモリに記憶する代替目的地探索ステップと、
前記ネットワークデータを参照して、前記出発地から前記探索された代替目的地までの経路探索を行う経路探索ステップとを備える経路探索方法である。
【００５０】
さらに、以下に示すコンピュータプログラムとして構成してもよい。
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データとを有するコンピュータシステムによって指定された目的地に向かう際に利用可能な代替目的地までの経路を探索するためのコンピュータプログラムであって、
出発地および目的地の指定を入力してメモリに記憶する入力機能と、
前記地図データベースを参照して、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる点である到着地点を取得し、該到着地点を表す情報をメモリに記憶する到着地点取得機能と、
前記ネットワークデータを参照して、前記到着地点を起点とする経路探索によって、該到着地点から到達可能な所定の属性を有する代替目的地を探索し、該代替目的地を表す情報をメモリに記憶する代替目的地探索機能と、
前記ネットワークデータを参照して、前記出発地から前記探索された代替目的地までの経路探索を行う経路探索機能とをコンピュータに実現させるためのコンピュータプログラムである。
【産業上の利用可能性】
【００５１】
本発明は、目的地が指定された時に利便性の高い代替目的地への経路を案内するために利用可能である。
【符号の説明】
【００５２】
１００…ナビゲーション装置
１０１…主制御部
１０２…送受信部
１０３…コマンド入力部
１０４…ＧＰＳ入力部
１０５…地図データベース記憶部
１０６…表示制御部
１０７…経路探索部
２００…サーバ
２０１…送受信部
２０２…データベース管理部
２１０…地図データベース記憶部
２１１…地物データ
２１２…文字データ
２１３…ネットワークデータ
【特許請求の範囲】
【請求項１】
指定された目的地に向かう際に利用可能な代替目的地までの経路を探索する経路探索システムであって、
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データとを格納する地図データベース記憶部と、
出発地および目的地の指定を入力する入力部と、
前記ネットワークデータおよび地物データを参照して、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の地点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる地点である到着地点を取得する到着地点取得部と、
前記ネットワークデータを参照して、前記到着地点を起点とする経路探索によって、該到着地点から到達可能な所定の属性を有する代替目的地を探索する代替目的地探索部と、
前記ネットワークデータを参照して、前記出発地から前記探索された代替目的地までの経路探索を行う経路探索部とを備える経路探索システム。
【請求項２】
請求項１記載の経路探索システムであって、
前記経路探索部は、複数の代替目的地が探索された場合に、前記到着地点から代替目的地までの道のりが短い代替目的地を優先して経路探索を行う経路探索システム。
【請求項３】
請求項１または２記載の経路探索システムであって、
前記経路探索部は、複数の代替目的地が探索された場合に、前記到着地点から代替目的地までの経路が、前記目的地から到着地点までの経路と一部または全部において重複する代替目的地を優先して経路探索を行う経路探索システム。
【請求項４】
請求項１〜３いずれか記載の経路探索システムであって、
前記代替目的地探索部は、前記ネットワークデータに加えて、前記地物データに含まれる道路のポリゴンデータも用いた経路探索によって前記代替目的地の探索を行う経路探索システム。
【請求項１】
指定された目的地に向かう際に利用可能な代替目的地までの経路を探索する経路探索システムであって、
道路をノード、リンクで表したネットワークデータと、道路を含む地物を描画するポリゴンを記憶する地物データとを格納する地図データベース記憶部と、
出発地および目的地の指定を入力する入力部と、
前記ネットワークデータおよび地物データを参照して、自動車が通行可能な道路として前記ネットワークデータが整備された道路上の地点であって、前記目的地に対応する地物からいずれかの道路を通行して到着できる地点である到着地点を取得する到着地点取得部と、
前記ネットワークデータを参照して、前記到着地点を起点とする経路探索によって、該到着地点から到達可能な所定の属性を有する代替目的地を探索する代替目的地探索部と、
前記ネットワークデータを参照して、前記出発地から前記探索された代替目的地までの経路探索を行う経路探索部とを備える経路探索システム。
【請求項２】
請求項１記載の経路探索システムであって、
前記経路探索部は、複数の代替目的地が探索された場合に、前記到着地点から代替目的地までの道のりが短い代替目的地を優先して経路探索を行う経路探索システム。
【請求項３】
請求項１または２記載の経路探索システムであって、
前記経路探索部は、複数の代替目的地が探索された場合に、前記到着地点から代替目的地までの経路が、前記目的地から到着地点までの経路と一部または全部において重複する代替目的地を優先して経路探索を行う経路探索システム。
【請求項４】
請求項１〜３いずれか記載の経路探索システムであって、
前記代替目的地探索部は、前記ネットワークデータに加えて、前記地物データに含まれる道路のポリゴンデータも用いた経路探索によって前記代替目的地の探索を行う経路探索システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−２０３０７３（Ｐ２０１１−２０３０７３Ａ）
【公開日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願番号】特願２０１０−６９９３５（Ｐ２０１０−６９９３５）
【出願日】平成２２年３月２５日（２０１０．３．２５）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願日】平成２２年３月２５日（２０１０．３．２５）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]