(57)【特許請求の範囲】
【請求項１】
出発地から目的地までの経路を探索する経路探索装置であって、
地図データを記憶する手段と、
施設毎に、施設種別に関する情報を含む案内情報を記憶する手段と、
利用者より探索すべき経路の経由地となる施設の指定を受け付ける手段と、
指定された施設の案内情報に含まれている施設種別を用いて当該施設が有料道路専用の施設であるか否かを調べ、有料道路専用の施設である場合は、有料道路上の、指定された施設近傍の地点を経路上の地点とし、有料道路専用の施設でない場合は、有料道路以外の道路上の、指定された施設近傍の地点を経路上の地点として、出発地から目的地までの経路を前記地図データを用いて探索する探索手段と、を有すること
を特徴とする経路探索装置。
【請求項２】
出発地から目的地までの経路を探索する経路探索装置であって、
地図データを記憶する手段と、
施設毎に、施設に接続する道路のリンク情報を含む案内情報を記憶する手段と、
利用者より探索すべき経路の経由地となる施設の指定を受け付ける手段と、
指定された施設近傍の道路を経由するようにして、出発地から目的地までの経路を探索する経路探索手段と、を有し、
前記経路探索手段は、指定された施設が案内情報を有する場合に、当該案内情報に含まれているリンク情報により特定される道路上の、指定された施設近傍の地点を経路上の地点として、出発地から目的地までの経路を前記地図データを用いて探索すること
を特徴とする経路探索装置。
【請求項３】
経路探索装置が出発地から目的地までの経路を探索する経路探索方法であって、
前記経路探索装置は、地図データを記憶する手段と、施設毎に、施設種別に関する情報を含む案内情報を記憶する手段と、を有しており、
利用者より探索すべき経路の経由地となる施設の指定を受け付けるステップと、
指定された施設の案内情報に含まれている施設種別を用いて当該施設が有料道路専用の施設であるか否かを調べ、有料道路専用の施設である場合は、有料道路上の、指定された施設近傍の地点を経路上の地点とし、有料道路専用の施設でない場合は、有料道路以外の道路上の、指定された施設近傍の地点を経路上の地点として、出発地から目的地までの経路を地図データを用いて探索するステップと、を有すること
を特徴とする経路探索方法。
【請求項４】
経路探索装置が出発地から目的地までの経路を探索する経路探索方法であって、
前記経路探索装置は、地図データを記憶する手段と、施設毎に、施設種別に関する情報を含む案内情報を記憶する手段と、を有しており、
利用者より探索すべき経路の経由地となる施設の指定を受け付けるステップと、
指定された施設近傍の道路を経由するようにして、出発地から目的地までの経路を探索する経路探索ステップと、を有し、
前記経路探索ステップは、指定された施設が案内情報を有する場合に、当該案内情報に含まれているリンク情報により特定される道路上の、指定された施設近傍の地点を経路上の地点として、出発地から目的地までの経路を前記地図データを用いて探索すること
を特徴とする経路探索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、自動車に搭載されるナビゲーション装置などにおいて、利用者によって選択された経由地を経由する目的地までの経路を探索する技術に関するものである。
【０００２】
【従来の技術】
自動車に搭載されるナビゲーション装置では、道路地図データに基づいて、設定された出発地から目的地までの推奨される経路を探索し、利用者に提示する経路探索の技術が既に実用化されている。
【０００３】
また、経路探索に際して、利用者より予め用意した複数の経由地候補や目的地候補の中から１又は複数の経由地と目的地の選択を受け付け、出発地から選択された各経由地を経由して選択された目的地に至る経路を探索する技術も既に実用化されている。ここで、このような経由地や目的地の候補としては、通常、名所や、駐車場や、サービスエリアや、ガソリンスタンドなどの、利用者が利用する可能性がある各種施設が用意されることが多い。。
【０００４】
ここで、このように選択される経由地や目的地は道路上の地点ではない場合もあるため、従来は、経由地を経由する目的地までの経路を、たとえば、次のようにして求めていた。すなわち、出発地から最初の経由地として選択された施設に最も近い道路の交差／分岐点までの経路を探索する。そして、その交差点から、次の経由地として選択された施設の位置に最も近い道路の交差／分岐点までの経路を探索する処理を、最後の経由地までの経路が探索されるまで繰り返す。そして、最後の経由地から目的地に最も近い道路の交差／分岐点までの経路を探索する。
【０００５】
なお、道路上の地点間の経路探索は、たとえば、ダイクストラ法と呼ばれる技術などによって、地点間で取り得る経路のうち、コストが最小となる経路を探索することにより行われている。ここで、このような経路のコストとしては、経路の総距離などを用いることが多い。
【０００６】
【発明が解決しようとする課題】
前述した出発地から選択された各経由地を経由して目的地に至る経路を探索する技術には、次のような不具合があった。
【０００７】
たとえば、いま、経由地として有料道路付属のサービスエリアが選択された場合を考える。この場合、前記従来の技術によれば、サービスエリアに最も近い道路を通る経路を探索する。このため、有料道路以外の、サービスエリアに連結していない一般道がサービスエリア近傍に存在する場合には、有料道路ではなく一般道路を通る経路が探索されてしまうことになる。そして、この場合は、利用者がサービスエリアを利用することを意図してサービスエリアを経由地として選択したにもかかわらず、サービスエリアに連結していない一般道を通る経路が探索されてしまうために、利用者は、この経路中でサービスエリアを利用できなくなってしまう。したがって、従来の技術によれば、このような場合には、利用者の意図に適合しない経路を探索してしまうことになる。
【０００８】
そこで、本発明は、選択された経由地を考慮して、利用者の意図により適合する経路を探索することを課題とする。
【０００９】
【課題を解決するための手段】
前記課題達成のために、本発明は、たとえば、出発地から目的地までの経路を探索する経路探索装置であって、
利用者より探索すべき経路において経由地もしくは目的地となる施設の指定を受け付ける手段と、
指定された施設の種別に応じて定まる種別の道路上の、指定された施設近傍の地点を経路上の地点とする出発地から目的地までの経路を探索する探索手段とを有することを特徴とする経路探索装置を提供する。
【００１０】
このような経路探索装置によれば、サービスエリアやインターチェンジランプなどの有料道路関連の施設の施設種別と、有料道路とを関連づけておくことにより、有料道路関連の施設が利用者より経由地もしくは目的地として指定された場合には、その近傍の道路のうちの有料道路を通る経路を探索するので、利用者が、指定した有料道路関連の施設を利用できない経路を探索してしまうことを防ぐことができる。
【００１１】
【発明の実施の形態】
以下、本発明に係る経路探索装置の一実施形態を、車載用ナビゲーション装置への適用を例にとり説明する。
【００１２】
図１に、本実施形態に係るナビゲーション装置の構成を示す。
【００１３】
図中、１はマイクロプロセッサやメモリから構成される処理装置、２は表示装置、３は地図データが記憶されたＣＤ−ＲＯＭなどの記憶媒体のアクセスを担うドライブ装置、４は利用者の指示の入力を受け付ける入力装置、５は車速センサや方位センサやＧＰＳ受信機などから構成されるセンサ装置である。
【００１４】
このような構成において、処理装置１は、センサ装置５の方位センサから入力する車両の進行方位や車速センサから入力する車速やＧＰＳ受信機から入力する測定現在位置などに基づいて車両の現在位置を算出したり、入力装置５を介して利用者より入力された目的地と、入力装置５を介して利用者より入力されたもしくはセンサ装置５からの入力より算出した現在位置に基づいて、目的地までの推奨経路の算出などを行う。
【００１５】
また、処理装置１は、算出した現在位置や、車両の進行方位や、入力装置５を介して利用者より指定された内容に基づき、ドライブ装置３を制御し地図データを読み出し、当該地図データの表す地図を表示装置２に表示する。地図の表示は、たとえば、算出した現在位置周辺の領域の地図を所定の縮尺で表示したり、利用者より指定された地区の地図を所定のもしくは指定された縮尺で表示したり、現在位置から目的地までの推奨経路を含む範囲の領域の地図を適当な縮尺で、推奨経路と共に表示することにより行う。また、この際、地図上に車両の現在位置と進行方位を表すマークを地図に重畳して表示したりする。
【００１６】
次に、ドライブ装置３に装着されるＣＤ−ＲＯＭなどの記憶媒体に記録された地図データを図２に示す。
【００１７】
図示するように、地図データは、各道路毎に設けられた道路データより構成される。また、道路データは、道路情報と、リンク情報よりより構成される。
【００１８】
道路情報には、道路を一意に表す道路番号と、道路の名称を表す道路名称と、その道路の種別（有料道路、国道、県道、ランプ）などを表す道路種別と、その他の道路の情報を表すその他属性が含まれる。
【００１９】
また、リンク情報には、道路を構成する各リンクについて設けられた、リンクの情報を表すリンクデータが含まれる。ここで、リンクは、道路の形状位置を集合として近似する線分である。
【００２０】
リンクデータは、リンクを一意に表すリンク番号と、リンクが構成する道路部分の種別を表すリンクの種別とを含む。リンク種別としては、サービスエリア／パーキングエリア、インターチェンジランプ、ジャンクションなどの種別の他、その他の適当な種別を設ける。
【００２１】
また、リンクデータは、その両端の点である２つのノードについて、それぞれ、ノードを一意に示すノード番号と、ノードの位置を表すノード座標と、そのノードとリンクを介して連結する全てのノードのノード番号のリストである隣接ノード番号リストを含む。ここで、リンク同士の連結は必ずノードにおいて行われる。たとえば、十字路では、その中心にノードが設けられ、この中心に設けられたノードに４つのリンクが連結する。そして、この場合、中心に設けられたノードの隣接ノード番号リストには、自ノードに連結する４つのリンクの他端の４つのノードのノード番号が記述される。
【００２２】
また、リンクデータは、リンクの形状を特定するリンク形状データを含む。リンク形状データは、１または複数のサブノード座標からなる。リンクの形状は、サブノード座標が二つの場合、リンクの第１番目のノード座標、第１番目のサブノード座標、第２番目のサブノード座標、リンクの第２番目のノード座標を、この順序で順次直線で結んだ形状として特定される。
【００２３】
次に、図３に、図２に示した地図データに付随して、ドライブ装置３に装着されるＣＤ−ＲＯＭなどの記憶媒体に記録された案内情報の構成を示す。
【００２４】
図示するように、案内情報は、地図データがカバーする地理的範囲内に存在する代表的な施設の一覧であり、この一覧中には、各施設について、施設名称と施設座標と施設種別が記述されている。ここで、案難情報に含まれる施設としては、各種公共施設や、名所や、ガソリンスタンドや、レストランなどの施設種別の施設の他、有料道路の入り口ランプや出口ランプや、有料道路に付随するサービスエリア／パーキングエリアや、有料道路のジャンクションなどの道路関連の施設種別の施設も含まれる。また、案内情報には、各施設に連結する（車両で当該施設にアクセス可能な）リンクを特定するリンク番号が接続リンク情報として記述される。ただし、この接続リンク情報が特定するリンクは、施設名称が直接示す施設に連結するリンクでなく、その施設に関連する施設に連結するリンクであってもよい。たとえば、施設名称が示す施設が百貨店である場合に、接続リンク情報が特定するリンクを、当該百貨店の駐車場に連結するリンクとしてもよい。
【００２５】
以下、処理装置１が行う処理について説明する。
【００２６】
図４に、この処理の処理手順を示す。
【００２７】
まず、処理装置１は、利用者より目的地と経由地を受け付け、記憶する（ステップ４１）。目的地や経由地は、表示装置２にドライブ装置３に装着されるＣＤ-ＲＯＭなどの記憶媒体に記憶された案内情報に含まれる各施設の施設名称を表示し、その内から利用者によって選択された施設名称の施設を目的地や経由地として受け付ける。または、直接、目的地や経由地の座標がポインティングデバイスなどにより入力された場合には、入力された座標を目的地や経由地として受け付ける。
【００２８】
次に、処理装置１は、各経由地と目的地とについて、その地点の近傍のリンクを近傍リンクとして抽出する処理を行う（ステップ４２）。
【００２９】
この処理では、各経由地と目的地の各々を順次着目地点とし、各着目地点について図５に示す手順を行う
すなわち、まず、着目地点が図３の案内情報から選択されたものであるか、ポインティングデバイスにより直接座標が指定されたものであるかを判定する（ステップ４０１）。
【００３０】
そして、ポインティングデバイスにより直接座標が指定されたものであれば、その着目地点を中心とする一定範囲の検索範囲を設定し、検索範囲内に存在する全ての道路の全てのリンクを候補リンクとし、候補リンクの内から（ステップ４５１、４５９）、リンクから着目地点へのリンク形状を考慮した最短距離が小さいものを最も小さいものから所定数、着目地点の近傍リンクとして抽出する（ステップ４５２−４５７）。
【００３１】
なお、このステップ４５２−４５７では、より詳細には、各候補リンクに順次着目し、着目したリンクの最短距離（ステップ４５２）が、格納テーブルに既に格納されている最短距離が最大のリンクの最短距離（ステップ４５４）より小さい場合に（ステップ４５５）、この最短距離が最大のリンクを着目したリンクに置き換えている（ステップ４５９）。また、この際、格納テーブルに所定数のリンクが格納されるまでは（ステップ４５３）、無条件に着目したリンクを格納テーブルに格納している（ステップ４５８）。
【００３２】
また、着目地点が、案内情報から選択されたものである場合には、着目地点である施設に対応してリンク番号が接続リンク情報が案内情報に記述されているかどうかを調べ（ステップ４０２）、記述されている場合には、そのリンク番号のリンクを、着目地点の近傍リンクとして抽出する（ステップ４０３）。
【００３３】
また、着目地点が、案内情報から選択されたものであり、着目地点である施設に対応してリンク番号が接続リンク情報が案内情報に記述されていない場合には、まず、着目地点である施設に対応して案内情報に記述されている施設座標を参照して、着目地点を中心とする一定範囲の検索範囲を設定する（ステップ４０４）。
【００３４】
そして、着目地点である施設に対応して案内情報に記述されている施設種別を調べ、その施設種別が、有料道路専用の施設の施設種別であるかどうかを調べる（ステップ４０５）。ここでは、施設種別が入り口ランプ、出口ランプ、サービスエリア／パーキングエリア、ジャンクションなどの有料道路特有の施設の種別である場合に、有料道路専用の施設の施設種別であると判断し、他の場合は有料道路専用の施設の施設種別でないと判断する。
【００３５】
そして、有料道路専用の施設の施設種別でないと判断された場合には、地図データを参照し、検索範囲内に存在する有料道路以外の全ての道路の全てのリンクを候補リンクとし、候補リンクの中から（ステップ４３１、４３９）、リンクから着目地点へのリンク形状を考慮した最短距離が小さいものを最も小さいものから所定数、着目地点の近傍リンクとして抽出する（ステップ４３２−４３７）。なお、このステップ４３２−４３７の処理の詳細は、前述したステップ４５２−４５７の詳細と同じである。
【００３６】
一方、有料道路専用の施設の施設種別であると判断された場合には、その施設種別に応じて（ステップ３０６−４０９）、選択リンク種別を設定する（ステップ４１０−４１４）。ここでは、施設種別が入り口ランプ、出口ランプの場合はインターチェンジランプを選択リンク種別とし、施設種別がサービスエリア／パーキングエリアの場合はサービスエリア／パーキングエリアを選択リンク種別とし、施設種別がジャンクションの場合はジャンクションを選択リンク種別とし、施設種別が他の種別の場合は制限無しを選択リンク種別とする。
【００３７】
そして、検索範囲内に存在する全ての有料道路の全てのリンクを候補リンクとし、候補リンクの中から（ステップ４１５、４２４）、地図データにおいて、選択リンク種別と一致するリンク種別を持つリンクを対象とし（ステップ４１６）、対象としたリンクの中から、リンクから着目地点へのリンク形状を考慮した最短距離が小さいものを最も小さいものから所定数、着目地点の近傍リンクとして抽出する（ステップ４１６−４２３）。ここで、選択リンク種別が制限無しの場合は、検索範囲内に存在する全ての有料道路の全てのリンクを対象とする。なお、ステップ４１６−４２３の詳細は、前述したステップ４５２−４５７の詳細と同じである。
【００３８】
図４に戻り、次に、処理装置１は、地図データを参照して、出発地から目的地までの間の経由地で区切られた各区間について経路候補を探索する（ステップ４３）。
【００３９】
ここでは、出発地から第１の経由地までについては、第１番目の経由地について抽出した各近傍リンクについて各々探索した、出発地から第１番目の経由地について抽出した各近傍リンクのより第１番目の経由地に近いノードまでの経路を複数の経路候補とする。同様に、第ｉ（ｉは１からｎ−１）番目の経由地から第ｉ＋１番目の経由地までについては、第ｉ番目の経由地について抽出した各近傍リンクと第ｉ＋１番目の経由地について抽出した各近傍リンクの組み合わせの各々について探索した、第ｉ番目の経由地について抽出した各近傍リンクのより第ｉ番目の経由地に近いノードから、第ｉ＋１番目の経由地について抽出した各近傍リンクのより第ｉ＋１番目の経由地に近いノードまでの経路を複数の経路候補とする。また、第ｎ番目の経由地から目的地までについては、第ｎ番目について抽出した各近傍リンクと目的地について抽出した各近傍リンクの組み合わせの各々について探索した、第ｎ番目について抽出した各近傍リンクのより第ｎ番目の経由地に近いノードから、目的地について抽出した各近傍リンクのより目的地に近いノードまでの経路を複数の経路候補とする。
【００４０】
次に、処理装置１は、各区間について一つずつ経路候補を選択して得られる全ての組み合わせについて、それぞれ、隣り合う区間の選択した経路候補間をつなぐ経路を探索し、選択した経路候補と組み合わせて出発地から目的地までの経路を生成する処理を行い、出発地から目的地までの経路を複数生成する。そして、その中から最もコストの低いものを選択し、これを最終的な出発地から目的地までの経路とする（ステップ４４）
以上、本発明の実施形態について説明した。
【００４１】
以上のように、本実施形態によれば、経由地や目的地近傍の、経由地や目的地として設定した施設の施設種別に適合するリンク種別のリンクのノードを含む経路を探索するので、利用者が有料道路関連の施設を経由地や目的地として設定した場合には、必ず、その近傍の有料道路を経由する経路が探索される。したがって、従来のように、利用者が経由地や目的地として設定した施設を利用できないような経路を探索してしまうことを排除することができ、より利用者の意図に適合する経路を探索することができる。
【００４２】
また、接続リンク情報を利用して近傍リンクを定めているので、この場合は、必ず、利用者が経由地や目的地として設定した施設を利用できるような経路を探索できるので利用者の意図に適合する経路を探索することができる。
【００４３】
なお、本実施形態における処理装置１は、ＣＰＵやメモリや適当なＯＳを備えた電子計算機であってよく、この場合、処理装置１が行う前記各処理は、ＣＰＵが、各処理の手順を記述したプログラムを実行することにより実現される。また、このばあい、これらのプログラムはＣＤ−ＲＯＭなどの記憶媒体を介して、処理装置１に供給するようにしてもよい。
【００４４】
【発明の効果】
以上のように本発明によれば、選択された経由地を考慮して、利用者の意図により適合する経路を探索するこができる。
【図面の簡単な説明】
【図１】本発明の実施形態に係るナビゲーション装置の構成を示すブロック図である。
【図２】本発明の実施形態に係る地図データの構成を示す図である。
【図３】本発明の実施形態に係る案内情報の構成を示す図である。
【図４】本発明の実施形態に係るナビゲーション装置の動作を示すフローチャートである。
【図５】本発明の実施形態において行う近傍リンクを抽出する手順を示すフローチャートである。
【符号の説明】
１  処理装置
２  表示装置
３  ドライブ装置
４  入力装置
５  センサ装置
【図１】
0003581559.tif 000002
【図２】
0003581559.tif 000003
【図３】
0003581559.tif 000004
【図４】
0003581559.tif 000005
【図５】
0003581559.tif 000006