(57)【要約】【課題】  経由地の数が多くなった場合でも経由地の並び替えを高速に行って最適の経路を設定できる移動体ナビゲーション装置を提供する。【解決手段】  移動体の現在地を検出する位置検出手段１０と、地図情報を取得する地図情報取得手段２０と、経由地および目的地を入力する入力手段３０と、位置検出手段で検出された現在地、入力手段で入力された経由地および目的地の中の２地点の組み合わせの全てについて２地点間の直線距離を地図情報取得手段で取得された地図情報に基づいて計算する直線距離計算手段６１と、位置検出手段で検出された現在地から入力手段で入力された全ての経由地を経由して目的地に至る複数の経路のうち、直線距離計算手段で計算された２地点間の直線距離を経路に沿って合計した値が最小になる経路を計算する経路計算手段６６とを備えている。【選択図】        図１
2005331279.tif 000002
【特許請求の範囲】
【請求項１】
移動体の現在地を検出する位置検出手段と、
地図情報を取得する地図情報取得手段と、
経由地および目的地を入力する入力手段と、
前記位置検出手段で検出された現在地、前記入力手段で入力された経由地および目的地の中の２地点の組み合わせの全てについて２地点間の直線距離を前記地図情報取得手段で取得された地図情報に基づいて計算する直線距離計算手段と、
前記位置検出手段で検出された現在地から前記入力手段で入力された全ての経由地を経由して目的地に至る複数の経路のうち、前記直線距離計算手段で計算された２地点間の直線距離を経路に沿って合計した値が最小になる経路を計算する経路計算手段
とを備えた移動体ナビゲーション装置。
【請求項２】
直線距離計算手段において直線距離の計算に使用される２地点を直線で結ぶ線分上に障害物が存在するかどうかを検出する障害物検出手段と、
前記障害物検出手段により障害物が存在することが検出された場合に、直線距離計算手段で計算された２地点間の直線距離に所定の追加距離を加算し、該加算結果を２地点間の直線距離として出力する追加距離加算手段
とをさらに備えたことを特徴とする請求項１記載の移動体ナビゲーション装置。
【請求項３】
障害物検出手段は、地図情報取得手段で取得された地図情報に基づいて、直線距離計算手段において直線距離の計算に使用される２地点を直線で結ぶ線分と交差する特定ポリゴン又はポリラインが存在することを判断した場合に障害物が存在することを検出することを特徴とする請求項２記載の移動体ナビゲーション装置。
【請求項４】
追加距離加算手段は、追加距離を障害物の大きさおよび種類の少なくとも１つに応じて可変することを特徴とする請求項２記載の移動体ナビゲーション装置。
【請求項５】
位置検出手段で検出された現在地、入力手段で入力された経由地および目的地を所定の条件に従って複数のグループにグループ化するグループ化手段と、
前記グループ化手段でグループ化することにより得られた複数のグループの各々において、グループ内の全ての地点を経由する複数のグループ内経路のうち、直線距離計算手段で計算された２地点間の直線距離をグループ内経路に沿って合計した値が最小になるグループ内経路を計算するグループ内経路計算手段とをさらに備え、
経路計算手段は、前記位置検出手段で検出された現在地から前記グループ化手段でグループ化することにより得られた全てのグループのグループ内経路を経由して前記入力手段で入力された目的地に至る複数の経路のうち、２グループ間の直線距離を経路に沿って合計した値が最小になる経路を計算することを特徴とする請求項１記載の移動体ナビゲーション装置。
【請求項６】
位置検出手段で検出された現在地、入力手段で入力された経由地および目的地の中の２地点の組み合わせの全てについて２地点間の経路に沿った経路距離を地図情報取得手段で取得した地図情報に基づいて計算する経路距離計算手段と、
前記現在地から目的地までの経路を直線距離によって求めるか経路距離によって求めるかを選択する選択手段とを備え、
経路計算手段は、前記選択手段による選択に応じて、直線距離計算手段で計算された直線距離または経路距離計算手段で計算された経路距離を用いて経路を計算することを特徴とする請求項１記載の移動体ナビゲーション装置。
【請求項７】
移動体の現在地を検出する位置検出手段と、
地図情報を取得する地図情報取得手段と、
経由地および目的地を入力する入力手段と、
前記位置検出手段で検出された現在地、前記入力手段で入力された経由地および目的地を所定の条件に従って複数のグループにグループ化するグループ化手段と、
前記グループ化手段でグループ化することにより得られた複数のグループの各々において、グループ内の２地点の組み合わせの全てについて２地点間の経路に沿った経路距離を前記地図情報取得手段で取得した地図情報に基づいて計算する経路距離計算手段と、
前記複数のグループの各々において、グループ内の全ての地点を経由する複数のグループ内経路のうち、前記経路距離計算手段で計算された２地点間の経路距離をグループ内経路に沿って合計した値が最小になるグループ内経路を計算するグループ内経路計算手段と、
前記位置検出手段で検出された現在地から前記グループ化手段でグループ化することにより得られた全てのグループのグループ内経路を経由して前記入力手段で入力された目的地に至る複数の経路のうち、２グループ間の経路距離を経路に沿って合計した値が最小になる経路を計算する経路計算手段
とを備えた移動体ナビゲーション装置。
【請求項８】
グループ化手段は、１つの地点から所定範囲内または所定矩形内に存在する地点毎にグループ化することを特徴とする請求項５または請求項７記載の移動体ナビゲーション装置。
【請求項９】
グループ化手段は、１つの地点と同一の行政区画、郵便番号、市外局番または地図を管理するためのメッシュ内に存在する地点毎にグループ化することを特徴とする請求項５または請求項７記載の移動体ナビゲーション装置。
【請求項１０】
移動体の現在地を検出するステップと、
地図情報を取得するステップと、
経由地および目的地を入力するステップと、
前記検出された現在地、前記入力された経由地および目的地の中の２地点の組み合わせの全てについて２地点間の直線距離を前記取得された地図情報に基づいて計算するステップと、
前記検出された現在地から前記入力された全ての経由地を経由して目的地に至る複数の経路のうち、前記計算された２地点間の直線距離を経路に沿って合計した値が最小になる経路を計算するステップ
とを備えた移動体ナビゲーション方法。
【請求項１１】
移動体の現在地を検出するステップと、
地図情報を取得するステップと、
経由地および目的地を入力するステップと、
前記検出された現在地、前記入力された経由地および目的地を所定の条件に従って複数のグループにグループ化するステップと、
前記グループ化することにより得られた複数のグループの各々において、グループ内の全ての地点の組み合わせの全てについて２地点間の経路に沿った経路距離を前記取得された地図情報に基づいて計算するステップと、
前記グループ化することにより得られた複数のグループの各々において、グループ内の全ての地点を経由する複数のグループ内経路のうち、前記計算された２地点間の経路距離をグループ内経路に沿って合計した値が最小になるグループ内経路を計算するステップと、
前記検出された現在地から前記グループ化することにより得られた全てのグループのグループ内経路を経由して前記入力された目的地に至る複数の経路のうち、前記計算された、２グループ間の経路距離を経路に沿って合計した値が最小になる経路を計算するステップ
とを備えた移動体ナビゲーション方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、移動体ナビゲーション装置および移動体ナビゲーション方法に関し、特に複数の経由地が設定された場合に経由地を並び替えて最適な経路を高速に計算する技術に関する。
【背景技術】
【０００２】
従来、ユーザによって目的地が入力されることにより、ＧＰＳ（Global Positioning System）等を利用して移動体の現在位置を検出し、この検出した現在位置から目的地までの最短の経路を探索し、この探索された経路に基づいて地図表示や音声を用いて案内し、以て移動体による快適な移動を実現した移動体ナビゲーション装置が知られている。
【０００３】
このような移動体ナビゲーション装置では、目的地だけでなく複数の経由地を設定することができる。例えば、特許文献１には、指定された出発地点から複数の経由地を介して目的地点に至る経路を、各経由地点の通過順序を変えて複数計算し、この計算により得られた複数の経路の中から最短距離あるいは最短時間で通過できる１つを選択するといった経路計算方法が開示されている。
【０００４】
【特許文献１】特開平１１−９４５７８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した従来の経路計算方法では、経路中の１区間（例えば１つの経由地から他の経由地まで）の距離を経路に沿った道なりで計算しているので、経由地の数が多くなると経由地の並び替えの組み合わせが飛躍的に増大することに伴って、膨大な計算時間を要する。Ｎ個の経由地を並び替えるにはＮ！（Ｎの階乗）の組み合わせを計算する必要があるので、１区間の計算時間をＴとすると最適順を求めるために「Ｎ！×Ｔ×Ｎ」の時間を要することになる。このため、移動体ナビゲーション装置のリアルタイム性が阻害されるという問題がある。
【０００６】
この発明は、上述した問題を解消するためになされたものであり、経由地の数が多くなった場合でも経由地の並び替えを高速に行って最適の経路を設定できる移動体ナビゲーション装置及び移動体ナビゲーション方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
この発明に係る移動体ナビゲーション装置は、移動体の現在地を検出する位置検出手段と、地図情報を取得する地図情報取得手段と、経由地および目的地を入力する入力手段と、位置検出手段で検出された現在地、入力手段で入力された経由地および目的地の中の２地点の組み合わせの全てについて２地点間の直線距離を地図情報取得手段で取得された地図情報に基づいて計算する直線距離計算手段と、位置検出手段で検出された現在地から入力手段で入力された全ての経由地を経由して目的地に至る複数の経路のうち、直線距離計算手段で計算された２地点間の直線距離を経路に沿って合計した値が最小になる経路を計算する経路計算手段とを備えているものである。
【０００８】
この発明に係る移動体ナビゲーション装置は、移動体の現在地を検出する位置検出手段と、地図情報を取得する地図情報取得手段と、経由地および目的地を入力する入力手段と、位置検出手段で検出された現在地、入力手段で入力された経由地および目的地を所定の条件に従って複数のグループにグループ化するグループ化手段と、グループ化手段でグループ化することにより得られた複数のグループの各々において、グループ内の２地点の組み合わせの全てについて２地点間の経路に沿った経路距離を地図情報取得手段で取得した地図情報に基づいて計算する経路距離計算手段と、グループ化手段でグループ化することにより得られた複数のグループの各々において、グループ内の全ての地点を経由する複数のグループ内経路のうち、経路距離計算手段で計算された２地点間の経路距離をグループ内経路に沿って合計した値が最小になるグループ内経路を計算するグループ内経路計算手段と、位置検出手段で検出された現在地からグループ化手段でグループ化することにより得られた全てのグループのグループ内経路を経由して入力手段で入力された目的地に至る複数の経路のうち、２グループ間の経路距離を経路に沿って合計した値が最小になる経路を計算する経路計算手段とを備えているものである。
【０００９】
この発明に係る移動体ナビゲーション方法は、移動体の現在地を検出するステップと、地図情報を取得するステップと、経由地および目的地を入力するステップと、検出された現在地、入力された経由地および目的地の中の２地点の組み合わせの全てについて２地点間の直線距離を取得された地図情報に基づいて計算するステップと、検出された現在地から入力された全ての経由地を経由して目的地に至る複数の経路のうち、計算された２地点間の直線距離を経路に沿って合計した値が最小になる経路を計算するステップとを備えているものである。
【００１０】
この発明に係る移動体ナビゲーション方法は、移動体の現在地を検出するステップと、地図情報を取得するステップと、経由地および目的地を入力するステップと、検出された現在地、入力された経由地および目的地を所定の条件に従って複数のグループにグループ化するステップと、グループ化することにより得られた複数のグループの各々において、グループ内の全ての地点の組み合わせの全てについて２地点間の経路に沿った経路距離を取得された地図情報に基づいて計算するステップと、グループ化することにより得られた複数のグループの各々において、グループ内の全ての地点を経由する複数のグループ内経路のうち、計算された２地点間の経路距離をグループ内経路に沿って合計した値が最小になるグループ内経路を計算するステップと、検出された現在地からグループ化することにより得られた全てのグループのグループ内経路を経由して入力された目的地に至る複数の経路のうち、２グループ間の経路距離を経路に沿って合計した値が最小になる経路を計算するステップとを備えているものである。
【発明の効果】
【００１１】
この発明によれば、現在地、経由地および目的地の中の２地点の組み合わせの全てについて２地点間の直線距離を計算し、現在地から全ての経由地を経由して目的地に至る複数の経路のうち、直線距離を経路に沿って合計した値が最小になる経路を計算するように構成したので、２地点間の距離を道なりで計算する従来の移動体ナビゲーション装置に比べて経路計算の時間を大幅に短縮できる。その結果、経由地の数が多くなって経由地の並び替えの組み合わせが増大しても、経由地の並び替えを高速に行うことができるので、移動体ナビゲーション装置のリアルタイム性を確保することができる。
【００１２】
この発明によれば、現在地、経由地および目的地を所定の条件に従って複数のグループにグループ化し、このグループ化により得られた複数のグループの各々において、グループ内の２地点の組み合わせの全てについて２地点間の経路に沿った経路距離を計算し、複数のグループの各々において、グループ内の全ての地点を経由する複数のグループ内経路のうち、２地点間の経路距離をグループ内経路に沿って合計した値が最小になるグループ内経路を計算し、現在地から全てのグループのグループ内経路を経由して目的地に至る複数の経路のうち、２グループ間の経路距離を経路に沿って合計した値が最小になる経路を計算するように構成したので、経由地の並び替えの組み合わせを減らすことができる。その結果、経路計算に要する時間を減らすことができるので、移動体ナビゲーション装置のリアルタイム性を確保することができる。
【００１３】
この発明によれば、上述したこの発明に係る第１の移動体ナビゲーション装置と同様の効果を奏し、また、この発明に係る移動体ナビゲーション方法によれば、上述したこの発明に係る第２の移動体ナビゲーション装置と同様の効果を奏する。
【発明を実施するための最良の形態】
【００１４】
以下、この発明の実施の形態を、図面を参照しながら詳細に説明する。
実施の形態１．
この発明の実施の形態１に係る移動体ナビゲーション装置について説明する。図１は、この発明の実施の形態１に係る移動体ナビゲーション装置の機能的な構成を示すブロック図である。この移動体ナビゲーション装置は、位置検出手段１０、地図情報取得手段２０、入力手段３０、経路探索手段４０および出力手段５０から構成されている。
【００１５】
位置検出手段１０は移動体の現在地を検出する。この位置検出手段１０で検出された移動体の現在地を表す現在地データは経路探索手段４０に送られる。
【００１６】
地図情報取得手段２０は記憶媒体または外部から地図情報を取得する。この地図情報取得手段２０で取得された地図情報は、経路探索手段４０に送られる。
【００１７】
入力手段３０は、出発地、経由地、目的地といった経路上の地点（以下、「経路地点」という）を入力するために使用される。この入力手段３０で入力された経路地点を表す地点データは経路探索手段４０に送られる。
【００１８】
経路探索手段４０は、地図情報取得手段２０で取得された地図情報に基づき、位置検出手段１０で検出された現在地から経路地点を経由して目的地に至る案内経路を探索する。この経路探索手段で探索された案内経路を表す案内経路データは、出力手段５０に送られる。この経路探索手段４０の詳細は後述する。
【００１９】
出力手段５０は、経路探索手段４０から送られてくる案内経路データに基づいて、案内経路を画像として表示し、または音声で出力することにより案内を行う。
【００２０】
経路探索手段４０は、図１に示すように、直線距離計算手段６１、障害物検出手段６２、追加距離加算手段６３、グループ化手段６４、グループ内経路計算手段６５、経路計算手段６６および案内手段６７から構成されている。
【００２１】
直線距離計算手段６１は、位置検出手段１０で検出された現在地、入力手段３０から入力された経由地および目的地の中の２地点の組み合わせの全てについて２地点間の直線距離を地図情報取得手段２０で取得された地図情報に基づいて計算する。この直線距離計算手段６１で計算された２地点間の直線距離を表すデータは、障害物検出手段６２および追加距離加算手段６３に送られる。
【００２２】
障害物検出手段６２は、直線距離計算手段６１から送られてくる、直線距離の計算に使用された２地点を直線で結ぶ線分上に障害物が存在するかどうかを、地図情報取得手段２０から送られてくる地図情報に基づいて検出する。この障害物検出手段６２は、２地点を直線で結ぶ線分と交差する特定ポリゴン又はポリラインが存在することを判断した場合に障害物が存在することを検出するように構成できる。障害物検出手段６２における検出結果は、追加距離加算手段６３に送られる。
【００２３】
追加距離加算手段６３は、障害物検出手段６２から送られてくる検出結果が、２地点を直線で結ぶ線分上に障害物が存在することを表している場合に、直線距離計算手段６１から送られてくる２地点間の直線距離に所定の追加距離を加算する。障害物には、例えば河川、建造物等が含まれる。図４は、地点Ｗ１と地点Ｗ２とを直線で結ぶ線分上に河川という障害物が存在する状態を示している。この例では、追加距離加算手段６３は、地点Ｗ１と地点Ｗ２との間の直線距離に所定の追加距離Ｌ（ｍ）を追加し、新たな直線距離とする。この場合、追加距離Ｌは、障害物の大きさや種類に応じて可変するように構成することができる。この追加距離加算手段６３で計算された新たな２地点間の直線距離は、グループ化手段６４に送られる。
【００２４】
グループ化手段６４は、位置検出手段１０で検出された現在地、入力手段３０から入力された経由地および目的地を所定の条件に従って複数のグループにグループ化する。グループ化するための所定の条件としては、１つの地点から所定範囲内または所定矩形内に存在する地点毎にグループ化するという条件を用いることができる。この場合、現在地から目的地までを一定数に区分し、この区分に応じて上記範囲または矩形の大きさを決定するように構成できる。あるいは、上記範囲または矩形の大きさを一定とし、現在地から目的地までを、この大きさに応じて区分するように構成することもできる。
【００２５】
グループ化するための所定の条件としては、１つの地点と同一の行政区画（市区町村）、郵便番号、市外局番または地図を管理するためのメッシュ内に存在する地点毎にグループ化するという条件を用いることができる。図５は、８個の地点Ｗ１〜Ｗ８を市毎にグループ化した例を示す。このグループ化手段６４でグループ化することにより得られた複数のグループの各々に含まれる地点を表すデータはグループ内経路計算手段６５に送られる。
【００２６】
グループ内経路計算手段６５は、グループ化手段６４でグループ化することにより得られた複数のグループの各々において、グループ内の全ての地点を経由する複数のグループ内経路のうち、直線距離計算手段６１で計算された２地点間の直線距離（障害物検出手段６２で障害物が検出された場合は追加距離加算手段６３で追加距離が加算された新たな直線距離）をグループ内経路に沿って合計した値が最小になるグループ内経路を計算する。図５に示した例では、地点Ｗ１〜Ｗ４を含むグループ内の全ての地点Ｗ１〜Ｗ４を経由する複数のグループ内経路のうち、２地点間の直線距離をグループ内経路に沿って合計した値が最小になるグループ内経路が計算される。同様に、地点Ｗ５〜Ｗ８を含むグループ内の全ての地点Ｗ５〜Ｗ８を経由する複数のグループ内経路のうち、２地点間の直線距離をグループ内経路に沿って合計した値が最小になるグループ内経路が計算される。このグループ内経路計算手段６５における計算結果は、経路計算手段６６に送られる。
【００２７】
経路計算手段６６は、グループ内経路計算手段６５から送られてくる各グループのグループ内経路を統合し、現在地から目的地までの経路を計算する。具体的には、経路計算手段６６は、位置検出手段１０で検出された現在地からグループ化手段６４でグループ化することにより得られた全てのグループのグループ内経路を経由して入力手段３０で入力された目的地に至る複数の経路のうち、２グループ間の直線距離（詳しくは、直線距離計算手段６１で計算された２地点間の直線距離であって、２地点が２つのグループにそれぞれ含まれる場合の直線距離）を経路に沿って合計した値が最小になる経路を計算する。この経路計算手段６６で計算された経路を表すデータは案内手段６７に送られる。
【００２８】
案内手段６７は、経路計算手段６６から送られてくる経路を表すデータに基づいて生成した案内経路を表示するための表示データおよび案内経路を音声で出力するための音声データに、方位センサ１１、距離センサ１２およびＧＰＳ受信機１３によって検出された移動体の現在位置を表す現在地データを付加した案内経路データを生成し、出力手段５０に送る。
【００２９】
図２は、この発明の実施の形態１に係る移動体ナビゲーション装置の機器構成を示すブロック図である。
【００３０】
この移動体ナビゲーション装置は、方位センサ１１、距離センサ１２、ＧＰＳ受信機１３、地図情報読取装置２１、入力装置３１、ナビＥＣＵ（Electronic Control Unit ；電子制御装置）４１、表示装置５１および音声出力装置５２から構成されている。
【００３１】
方位センサ１１、距離センサ１２およびＧＰＳ受信機１３は位置検出手段１０に対応する。方位センサ１１は、例えばジャイロや地磁気センサなどから構成されており、移動体の方位を検出する。この方位センサ１１で検出された方位は、方位データとしてナビＥＣＵ４１に送られる。
【００３２】
距離センサ１２は、移動体の速度や移動距離を検出する。この距離センサ１２で検出された速度や距離は、距離データとしてナビＥＣＵ４１に送られる。ＧＰＳ受信機１３は、ＧＰＳ衛星から受信した情報をもとに現在位置を算出する。このＧＰＳ受信機１３で検出された現在位置は、現在位置データとしてナビＥＣＵ４１に送られる。
【００３３】
地図情報読取装置２１は、地図情報取得手段２０に対応する。この地図情報読取装置２１は、例えばＣＤ−ＲＯＭ（Compact Disc - Read Only Memory)、ＤＶＤ−ＲＯＭ（Digital Versatile Disk - Read Only Memory)やＨＤＤ（Hard Disk Drive)等といった地図情報記憶媒体に記憶された道路ネットワークデータやポリゴンデータを含む地図情報を読み取る。この地図情報読取装置２１で読み取られた地図情報はナビＥＣＵ４１に送られる。
【００３４】
入力装置３１は、入力手段３０に対応し、例えば操作スイッチやタッチパネルなどから構成されている。この入力装置３１は、出発地、経由地、目的地等の経路地点を入力するために使用される。この入力装置３１を操作することにより発生された操作データはナビＥＣＵ４１に送られる。
【００３５】
ナビＥＣＵ４１は、経路探索処理を実行する。このナビＥＣＵ４１は、ＣＰＵ（Central Processing Unit)４２、ＲＯＭ（Read Only Memory）４３、ＲＡＭ（Random Access Memory）４４、表示・音声制御部４５および入出力制御部４６から構成されている。
【００３６】
ＣＰＵ４２は、経路探索手段４０に対応し、主に経路探索における演算処理を実行する。ＲＯＭ４３は、ＣＰＵ４２で実行される処理プログラムを記憶する。ＲＡＭ４４は、ＣＰＵ４２が処理に使用するデータを一時記憶する。表示・音声制御部４５は、ＣＰＵ４２で探索された経路を画像処理および音声処理する。入出力制御部４６は、入力装置３１、表示装置５１および音声出力装置５２の入出力を制御する。
【００３７】
表示装置５１および音声出力装置５２は、出力手段５０に対応する。表示装置５１は、探索された案内経路を画像により表示するモニタディスプレイ等から構成されている。音声出力装置５２は、探索された案内経路を音声により案内するスピーカ等から構成されている。
【００３８】
次に、この発明の実施の形態１に係る移動体ナビゲーション装置の動作を、図３に示すフローチャートを参照しながら説明する。
【００３９】
まず、２地点間の直線距離が求められる（ステップＳＴ１０）。即ち、直線距離計算手段６１は、位置検出手段１０で検出された現在地データ、入力手段３０から入力された経由地および目的地を表す地点データを取り込む。そして、２地点の組み合わせの全てについて２地点間の直線距離を地図情報取得手段２０から取得した地図情報に含まれる緯度座標および経度座標に基づいて計算する。
【００４０】
次いで、各２地点間に障害物が存在するかどうかが調べられる（ステップＳＴ１１）。即ち、障害物検出手段６２は、ステップＳＴ１０において直線距離の計算に使用された２地点を直線で結ぶ線分上に障害物が存在するかどうかを、地図情報取得手段２０から取得した地図情報に基づいて検出する。
【００４１】
このステップＳＴ１１において、各２地点間に障害物が存在しないことが判断されると、シーケンスはステップＳＴ１３に進む。一方、各２地点間に障害物が存在することが判断されると、直線距離に所定の追加距離が加算される（ステップＳＴ１２）。即ち、追加距離加算手段６３は、直線距離計算手段６１から送られてくる２地点間の直線距離に所定の追加距離Ｌ（ｍ）を加算する。その後、シーケンスはステップＳＴ１３に進む。
【００４２】
ステップＳＴ１３では、各地点が所定の条件に従ってグループ化される。即ち、グループ化手段６４は、位置検出手段１０から取得した現在地、入力手段３０から入力された経由地および目的地を所定の条件に従って複数のグループにグループ化する。
【００４３】
次いで、最短のグループ内経路が求められ、その結果が統合される（ステップＳＴ１４）。即ち、グループ内経路計算手段６５は、グループ化手段６４でグループ化された複数のグループの各々において、グループ内の全ての地点を経由する複数のグループ内経路のうち、２地点間の直線距離をグループ内経路に沿って合計した値が最小になるグループ内経路を計算して経路計算手段６６に送る。経路計算手段６６は、グループ内経路計算手段６５から送られてくる各グループのグループ内経路を統合する。
【００４４】
次いで、求められた地点順に沿って経路が計算される（ステップＳＴ１５）。即ち、経路計算手段６６は、現在地から全てのグループを経由して目的地に至る複数の経路のうち、２グループ間の直線距離を経路に沿って合計した値が最小になる経路を計算する。そして、この計算により得られた経路の各地点を順番に辿って全地点を通過する経路を計算する。
【００４５】
次いで、探索された案内経路が画像および音声により案内される（ステップＳＴ１６）。即ち、案内手段６７は、経路計算手段６６から送られてくる経路を表すデータに基づいて生成した案内経路を表示するための表示データおよび案内経路を音声で出力するための音声データに、移動体の現在位置を表す現在地データを付加した案内経路データを生成して出力手段５０に送る。これにより、表示装置５１に表示された画像および／または音声出力装置５２から出力される音声による案内が行われる。
【００４６】
以上説明したように、この発明の実施の形態１における移動体ナビゲーション装置によれば、現在地、経由地および目的地の中の２地点の組み合わせの全てについて２地点間の直線距離を計算し、現在地から全ての経由地を経由して目的地に至る複数の経路のうち、直線距離を経路に沿って合計した値が最小になる経路を計算するように構成したので、２地点間の距離を道なりで計算する従来の移動体ナビゲーション装置に比べて経路計算の時間を大幅に短縮できる。その結果、経由地の数が多くなって経由地の並び替えの組み合わせが増大しても、経由地の並び替えを高速に行うことができるので、移動体ナビゲーション装置のリアルタイム性を確保することができる。
【００４７】
また、この発明の実施の形態１に係るナビゲーション装置によれば、障害物検出手段６２は、２地点を直線で結ぶ線分と交差する特定ポリゴン又はポリラインを地図情報に基づいて検知するようにしたので、確実に障害物を検出することができる。
【００４８】
また、この発明の実施の形態１に係るナビゲーション装置によれば、追加距離加算手段６３は、障害物の大きさや種類により追加距離の値を変更するように構成したので障害物の大きさを正確に評価することができる効果がある。
【００４９】
また、この発明の実施の形態１に係るナビゲーション装置によれば、グループ化手段６４は複数存在する地点のうち、所定の条件に合致する地点同士でグループ化を行い、グループ内の地点だけで直線距離の合計が最短になるように経由地の並び替えを行い、次にグループを組み合わせ、その合計の距離が最短になるように構成したので、グループ化せずに一括して経由地の並び替えを行う場合より高速に経由地の並び替えを行うことができる。
【００５０】
また、この発明の実施の形態１に係るナビゲーション装置によれば、グループ化手段６４は、１つの地点から所定範囲内または所定矩形内に存在する地点毎にグループ化するように構成したので、全ての経由地を確実にグループ化できる。
【００５１】
さらに、この発明の実施の形態１に係るナビゲーション装置によれば、グループ化手段６４は、１つの地点と同一の行政区画（市区町村）、郵便番号、市外局番または地図を管理するためのメッシュ内に存在する地点毎にグループ化するように構成したので、全ての経由地を確実にグループ化できる。
【００５２】
なお、この発明の実施の形態１に係るナビゲーション装置の経路探索手段４０は、図１に示す構成から障害物検出手段６２、追加距離加算手段６３、グループ化手段６４およびグループ内経路計算手段６５を除去して構成することもできる。この場合、直線距離計算手段６１の出力が経路計算手段６６に送られる。また、この発明の実施の形態１に係るナビゲーション装置の経路探索手段４０は、図１に示す構成から障害物検出手段６２および追加距離加算手段６３を除去して構成することもできる。この場合、直線距離計算手段６１の出力がグループ内経路計算手段６５に送られる。さらに、この発明の実施の形態１に係るナビゲーション装置の経路探索手段４０は、図１に示す構成からグループ化手段６４およびグループ内経路計算手段６５を除去して構成することもできる。この場合、追加距離加算手段６３の出力が経路計算手段６６に送られる。これらの何れの構成であっても、２地点間の距離を道なりで計算する従来の移動体ナビゲーション装置に比べて経路計算の時間を短縮できる。その結果、経由地の数が多くなって経由地の並び替えの組み合わせが増大しても、経由地の並び替えを高速に行うことができる。
【００５３】
実施の形態２．
この発明の実施の形態２は、上述した実施の形態１に係る移動体ナビゲーション装置で使用したグループ化の技術と従来の経路探索方法とを用いて経由地の並び替えを高速に行うようにしたものである。
【００５４】
図６は、この発明の実施の形態２に係る移動体ナビゲーション装置の機能的な構成を示すブロック図である。この移動体ナビゲーション装置は、経路探索手段４０の構成が、実施の形態１に係る移動体ナビゲーション装置のそれと異なる。以下においては、実施の形態１に係る移動体ナビゲーション装置の構成と同一または相当部分には同一の符号を付して説明を省略する。
【００５５】
経路探索手段４０は、実施の形態１におけるそれから直線距離計算手段６１、障害物検出手段６２および追加距離加算手段６３が除去され、経路距離計算手段６８が追加されて構成されている。
【００５６】
経路距離計算手段６８は、２地点間の経路に沿った経路距離を地図情報取得手段２０で取得した地図情報に基づいて計算する。この経路距離計算手段６８で計算された２地点間の経路距離を表すデータは、グループ内経路計算手段６５に送られる。
【００５７】
グループ内経路計算手段６５は、グループ化手段６４でグループ化された複数のグループの各々において、グループ内の全ての地点を経由する複数のグループ内経路のうち、経路距離計算手段６８で計算された２地点間の経路距離をグループ内経路に沿って合計した値が最小になるグループ内経路を計算する。このグループ内経路計算手段６５における計算結果は、経路計算手段６６に送られる。以後の動作は、実施の形態１に係る移動体ナビゲーション装置の動作と同じである。
【００５８】
以上説明したように、この発明の実施の形態２に係る移動体ナビゲーション装置によれば、グループ化手段６４は、現在地、経由地および目的地を所定の条件に従って複数のグループにグループ化し、経路距離計算手段６８は、このグループ化により得られた複数のグループの各々において、グループ内の２地点の組み合わせの全てについて２地点間の経路に沿った経路距離を計算し、グループ内経路計算手段６５は、複数のグループの各々において、グループ内の全ての地点を経由する複数のグループ内経路のうち、２地点間の経路距離をグループ内経路に沿って合計した値が最小になるグループ内経路を計算し、経路計算手段６６は、現在地から全てのグループのグループ内経路を経由して目的地に至る複数の経路のうち、２グループ間の経路距離を経路に沿って合計した値が最小になる経路を計算するように構成したので、経由地の並び替えの組み合わせを減らすことができる。その結果、経路計算に要する時間を減らすことができるので、移動体ナビゲーション装置のリアルタイム性を確保することができる。
【００５９】
なお、この発明に係るナビゲーション装置においては、実施の形態１に係る移動体ナビゲーション装置のような各地点間の直線距離が最短になるように経由地を並び替える方法と実施の形態２に係る移動体ナビゲーション装置のような各地点間の経路距離が最短または最短時間になるように並び替える方法とをユーザが選択手段を用いて選択できるように構成できる。
【００６０】
この構成によれば、ユーザは、経由地が多い場合は、直線距離が最短になるように経由地を高速に並び替える方法を用い、経由地が少ない場合は、経路距離が確実に最短または最短時間になるように経由地を並び替える方法を用いるように使い分けることができる。その結果、状況に応じて好適な経路探索が可能になる。
【００６１】
なお、上述した実施の形態１および実施の形態２では、位置検出手段１０として、方位センサ１１、距離センサ１２、ＧＰＳ受信機１３を用いたが、位置検出手段１０としては、光ファイバジャイロ、振動ジャイロ、加速度センサ等といった他のセンサや、Ｄ−ＧＰＳ（Differential GPS）や、マップマッチングや、ＰＨＳ（Personal Handy phone System)や携帯電話において位置情報サービスを提供する無線ネットワーク網を用いることもできる。
【００６２】
また、実施の形態１および実施の形態２では、地図情報取得手段２０として、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＨＤＤ等の地図情報記憶媒体に記憶された地図情報を読み取る地図情報読取装置２１を用い、処理プログラムを記憶する記憶手段としてＲＯＭ４３を用い、処理データを一時記憶する記憶手段としてＲＡＭ４４を用いたが、これらの代わりに、例えばフラッシュメモリ（Flash Memory）といった他のメモリＩＣ（Integrated Circuit）や、ＣＤ−Ｒ（Recordable）、ＣＤ−ＲＷ（Rewritable）、ＤＶＤ−ＲＡＭ、ＤＶＤ−ＲＷ、ＭＤ（Mini Disk)といった他の光ディスクや、フレキシブルディスク、ハードディスク等といった磁気ディスクや、ＩＣメモリカード、磁気メモリカード、光メモリカード等といったメモリカードや、カセットテープ等といった磁気テープや、他の読み書き可能な不揮発性の記憶媒体を用いることもできる。
【００６３】
また、地図情報読取装置２１、ＲＯＭ４３およびＲＡＭ４４として共通の記憶媒体を使用するように構成することもできる。この構成によれば、移動体ナビゲーション装置の構成を簡略化することができる。
【００６４】
また、無線により外部の情報サーバ等とデータ通信を行うことができるように構成し、インターネット等を利用して外部から地図情報を取得したり、外部の情報サーバ等に経路地点、案内経路等を登録したり、外部の情報サーバ等で経路探索処理を実行するように構成することもできる。この構成により、さらに移動体ナビゲーション装置の構成を簡略化することができる。
【００６５】
また、実施の形態１および実施の形態２では、入力手段３０として操作スイッチ等からなる入力装置３１を用いたが、タッチパネル、タッチペン、マウス、トラックボール、操作パッド、リモコン、音声認識装置等の他の入力機器を用いることができる。
【００６６】
また、実施の形態１および実施の形態２では、出力手段５０としてディスプレイモニタ等からなる表示装置５１やスピーカ等からなる音声出力装置５２を用いたが、ＣＲＴ（Cathode Ray Tube；陰極線管）モニタ、液晶モニタ、ヘッドアップディスプレイ、携帯表示端末等といった種々のディスプレイモニタの他、ヘッドホン、イヤホン、音声合成装置等といった音声出力機器や、プリンタ等といった他の出力機器を用いることもできる。
【００６７】
さらに、実施の形態１および実施の形態２では、車両に搭載されるナビゲーション装置を想定して説明したが、この発明は車両に搭載されるナビゲーション装置に限定されず、例えば列車、船舶、飛行機等といった他の移動体に搭載されるナビゲーションシステムや、ＰＤＡ（Personal Digital Assistant）等といった人の持ち歩く携帯情報端末機器等に適用することもでき、これらの場合でも上述した効果と同様の効果が得られる。
【図面の簡単な説明】
【００６８】
【図１】この発明の実施の形態１に係る移動体ナビゲーション装置の機能的な構成を示すブロック図である。
【図２】この発明の実施の形態１に係る移動体ナビゲーション装置の機器構成を示すブロック図である。
【図３】この発明の実施の形態１に係る移動体ナビゲーション装置の動作を示すフローチャートである。
【図４】この発明の実施の形態１に係る移動体ナビゲーション装置において地点間の直線距離に追加距離を加算する例を説明するための図である。
【図５】この発明の実施の形態１に係る移動体ナビゲーション装置において地点のグループ化を説明するための図である。
【図６】この発明の実施の形態２に係る移動体ナビゲーション装置の機能的な構成を示すブロック図である。
【符号の説明】
【００６９】
１０  位置検出手段、１１  方位センサ、１２  距離センサ、１３  ＧＰＳ受信機、２０  地図情報取得手段、２１  地図情報読取装置、３０  入力手段、３１  入力装置、４０  経路探索手段、４１  ナビＥＣＵ、４２  ＣＰＵ、４３  ＲＯＭ、４４  ＲＡＭ、４５  表示・音声制御部、４６  入出力制御部、５０  出力手段、５１  表示装置、５２  音声出力装置、６１  直線距離計算手段、６２  障害物検出手段、６３  追加距離加算手段、６４  グループ化手段、６５  グループ内経路計算手段、６６  経路計算手段、６７  案内手段、６８  経路距離計算手段。
【図１】
2005331279.tif 000003
【図２】
2005331279.tif 000004
【図３】
2005331279.tif 000005
【図４】
2005331279.tif 000006
【図５】
2005331279.tif 000007
【図６】
2005331279.tif 000008