ナビゲーション装置および経路探索方法
【課題】枝狩りをしながら経路探索を行うアルゴリズムにおいて、特殊交通規制が存在したとしても真の最適経路を算出可能な「ナビゲーション装置および経路探索方法」を提供する。
【解決手段】探索枝を伸ばしていく過程で特殊交通規制情報を検出した場合、当該特殊交通規制が設定されているリンクにおいて枝狩りを行わずに探索枝を伸ばしたルートも含めて経路探索を行うようにすることにより、特殊交通規制が存在するために最適経路としては絶対に選択されることがないルートを構成するリンクにおいて複数のルートの累積コストを比較した結果、特殊交通規制の設定されていないルートの方が累積コストが高くて枝狩りされてしまうようなケースであっても、当該特殊交通規制のないルートも含めて探索枝を伸ばしながら経路探索を行うことができるようにする。
【解決手段】探索枝を伸ばしていく過程で特殊交通規制情報を検出した場合、当該特殊交通規制が設定されているリンクにおいて枝狩りを行わずに探索枝を伸ばしたルートも含めて経路探索を行うようにすることにより、特殊交通規制が存在するために最適経路としては絶対に選択されることがないルートを構成するリンクにおいて複数のルートの累積コストを比較した結果、特殊交通規制の設定されていないルートの方が累積コストが高くて枝狩りされてしまうようなケースであっても、当該特殊交通規制のないルートも含めて探索枝を伸ばしながら経路探索を行うことができるようにする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置および経路探索方法に関し、特に、出発地ノードから目的地ノードまで順にリンクコストを加算しながら複数のルートに沿って各ノードを辿っていき、累積コストが最も小さい経路を誘導経路として探索する経路探索機能を備えたナビゲーション装置に用いて好適なものである。
【背景技術】
【０００２】
一般にナビゲーション装置が備える経路探索機能では、ダイクストラ法と呼ばれるアルゴリズムが多く用いられている。出発地から目的地までのルートとして採り得る様々な経路の中から最適な経路を算出する方法の１つがダイクストラ法である。
【０００３】
ダイクストラ法では、出発地ノードから目的地ノードまで順にリンクコストを加算しながら複数のルートに沿って探索枝を伸ばしていく。探索枝を伸ばしていく過程で、途中同じノードに異なるルートで到着する場合は、そこまでの累積コストが低い方のルートを採用し、累積コストが高い方のルートはそれ以降の探索を中止する。それ以上探索をしても、出発地ノードから目的地ノードまでの最適経路にはなり得ないと考えられるからである。最適経路にはなり得ないと途中で判断されたルートの探索を終了させることを「枝狩り」と呼んでいる。ダイクストラ法では、出発地ノードから目的地ノードまで枝狩りをしながら探索を進めていくため、２地点間の最適経路を効率的に求めることが可能である。
【０００４】
なお、出発地から目的地の間にある道路は、道路幅や道路種別などの属性が様々であり、交通規制などが存在する場合もある。道路や車線を細かく分割して表した個々のリンクに付されるリンクコストは、これらの道路属性や交通規制などによって異なる。すなわち、リンクコストは、例えばリンクの距離をもとに、道路幅、道路種別、右折および左折、交通規制などに応じた所定の定数を乗じた値として設定されており、誘導経路として適正の程度を数値化したものである。
【０００５】
ところで、道路の中には、歩行者専用道路や単車専用道路、私道なども存在する。従来、このように自動車が通行できない道路も含めて最適な経路を探索できるようにした技術が提案されている（例えば、特許文献１参照）。この特許文献１では、通行不可条件を有するリンクが存在する場合、当該通行不可条件を一時的に解除して探索を行い、探索終了後に、通行可能道路のみを推奨経路として採用するようになされている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平１１−３４４３５０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述のように、ダイクストラ法は、出発地ノードから目的地ノードまで枝狩りをしながら探索を進めていくため、探索枝の候補が爆発的に増えるのを抑え、２地点間の最適経路を効率的に求めることができる。しかしながら、探索の過程で順次に枝狩りをするがゆえに、真に最適な経路を探索することができない場合があるという問題があった。以下に、この問題点を詳しく説明する。
【０００８】
例えば、図８（ａ）のように中央分離帯によって上下線が分離された道路では、地図データのノードとリンクは図８（ｂ）のようになっている。図８（ｂ）において、Ｌ１〜Ｌ７はリンクであり、道路や車線を細かく分割して複数のベクトルの繋がりで表わしたときの個々のベクトルに相当する。これらの各リンクＬ１〜Ｌ７に対して、道路属性や交通規制などに応じたリンクコストが設定されている。Ｎ１〜Ｎ８はノードであり、各リンクの両端点に相当する。
【０００９】
このように上下線が分離された道路において、交通規制として、図９（ａ）のようにＵターンを禁止する規制が存在したとする。この場合は、図９（ｂ）に示すように、地図データ上でＵターン経路を構成する終端リンクに当たるリンクＬ６に対して、「リンクＬ７→Ｌ４→Ｌ６」と経由してきた場合には通過できないという交通規制情報が付されている。
【００１０】
このような道路ネットワークでは、「・・・→Ｌ７→Ｌ４」の順で探索してきた第１ルートと、「・・・→Ｌ５→Ｌ４」の順で探索してきた第２ルートとを比較した場合、ダイクストラ法ではリンクＬ４まで（ノードＮ４まで）の累積コストが高い方を枝狩りしてしまう。なお、第１ルートと第２ルートとが共にノードＮ５に到着した時点で枝狩りをしないのは、左折や右折に対してもリンクコストが付されているため、リンクＬ７からリンクＬ４への左折というリンクコストを付加した後でなければ、正しい累積コストの比較ができないからである。
【００１１】
ここで、リンクＬ４までの累積コストを比較した結果、もし、第２ルートの方の累積コストが高い場合は、当該第２ルートは枝狩りされてしまい、それ以上の探索は行われなくなる。しかし、次のリンクＬ６まで加えた「・・・→Ｌ７→Ｌ４→Ｌ６」の第１ルートと「・・・→Ｌ５→Ｌ４→Ｌ６」の第２ルートとを比較した場合、第１ルートはＵターンで通過が禁止されている。そのため、リンクＬ６の地点で見た場合には、第１ルートよりも第２ルートの方が累積コストが低くなる場合がある。ところが、第２ルートはリンクＬ４の地点で既に枝狩りされてしまっているため、実際には第２ルートが選ばれることはない。
【００１２】
このような場合には、第１ルートでも第２ルートでもない、別の第３ルートが最適経路として選ばれることになる。例えば、図１０のような道路ネットワークで、自車位置（リンクＬ１３）から目的地（リンクＬ９）までの経路探索を行ったとする。この場合のリンクＬ４までの最適経路は、「Ｌ１３→Ｌ１０→Ｌ７→Ｌ４」の第１ルートであるものとする。ただし、「Ｌ７→Ｌ４→Ｌ６」のルートには通過禁止の交通規制が付されているため、目的地までの実際の最適経路は、「Ｌ１３→Ｌ８→Ｌ５→Ｌ４→Ｌ６→Ｌ９」の第２ルートであるものとする。
【００１３】
このようなケースにおいて、リンクＬ４の地点で第１ルートと第２ルートとを比較すると、リンクＬ４までの累積コストは第１ルートよりも第２ルートの方が高いため、第２ルートは枝狩りされる。その後、第１ルートの探索枝はリンクＬ６まで伸ばされるが、リンクＬ６に到着するルートには、第１ルートの他にも「Ｌ１３→Ｌ８→Ｌ１４→Ｌ１６→Ｌ１５→Ｌ１→Ｌ６」という第３ルートが存在する。
【００１４】
このリンクＬ６の地点で第１ルートと第３ルートとを比較すると、第１ルートは通過禁止の交通規制が設定されているため、累積コストは第３ルートよりも高くなり、第１ルートは枝狩りされる。その結果、第３ルートが最適経路として算出されてしまう。このように、３本以上のリンクにまたがって通過禁止（以下、これを「特殊交通規制」という）が設定されている道路ネットワークの場合、本来の最適経路（第２ルート）が算出されないことがある。
【００１５】
本発明は、このような問題を解決するために成されたものであり、出発地ノードから目的地ノードに到る途中までの累積コストに基づき枝狩りをしながら経路探索を行うアルゴリズムにおいて、特殊交通規制が存在したとしても本来の最適経路を算出できるようにすることを目的とする。
【課題を解決するための手段】
【００１６】
上記した課題を解決するために、本発明では、出発地ノードから目的地ノードまで様々なルートのリンクコストを順次加算しながら探索枝を伸ばしていく過程で、３本以上のリンクにまたがって設定された特殊交通規制情報を検出した場合、特殊交通規制が設定されているリンクにおいて枝狩りを行わずに探索枝を伸ばしたルートも含めて、出発地ノードから目的地ノードまでのリンクコストの合計が最も小さい経路を探索するようにしている。
【発明の効果】
【００１７】
上記のように構成した本発明によれば、特殊交通規制が存在するために最適経路としては絶対に選択されることがないルート（第１ルートとする）を構成するリンクにおいて複数のルートの累積コストを比較した結果、特殊交通規制の設定されていないルート（第２ルートとする）の方が累積コストが高くて枝狩りされてしまうようなケースであっても、第２ルートも含めて探索枝を伸ばしながら経路探索が行われることとなる。
【００１８】
このため、探索枝を伸ばした先のリンクにおいて、特殊交通規制の設定された第１ルートよりも累積コストが低くなる第３ルートと、探索枝を伸ばす前のリンクにおいて第１ルートよりも累積コストが高くなっていた第２ルートとが比較され、累積コストの低い方が選択されて累積コストの高い方は枝狩りされる。このとき、第２ルートの方が第３ルートよりも累積コストが低ければ、第１ルートよりも累積コストが高くて枝狩りされていたはずの第２ルートが最適なルートとして選ばれるようになる。これにより、リンク上に特殊交通規制が存在したとしても、真の最適経路を算出することができる。
【図面の簡単な説明】
【００１９】
【図１】本実施形態によるナビゲーション装置の機能構成例を示すブロック図である。
【図２】本実施形態による経路探索を行う道路ネットワークの例を示す図である。
【図３】本実施形態による経路探索を行う道路ネットワークの例を示す図である。
【図４】本実施形態による経路探索例を示す図である。
【図５】本実施形態による経路探索例を示す図である。
【図６】本実施形態による経路探索例を示す図である。
【図７】本実施形態によるナビゲーション装置の動作例（経路探索方法）を示すフローチャートである。
【図８】道路ネットワークの例を示す図である。
【図９】道路ネットワークの例を示す図である。
【図１０】従来の経路探索例を示す図である。
【発明を実施するための形態】
【００２０】
以下、本発明の一実施形態を図面に基づいて説明する。図１は、本実施形態によるナビゲーション装置の機能構成例を示すブロック図である。図１に示すように、本実施形態のナビゲーション装置１０は、その機能構成として、地図読出制御部１１、地図メモリ１２、位置測定部１３、目的地設定部１４、経路探索部１５および誘導経路メモリ１６を備えている。
【００２１】
地図読出制御部１１は、ＤＶＤ（Digital Versatile Disk）２０に記憶されている地図データの読み出しを制御する。具体的には、地図読出制御部１１は、位置測定部１３から自車両の現在位置情報を入力し、その車両現在位置を含む所定範囲の地図データの読み出し指示を出力することにより、地図表示や経路探索に必要な地図データをＤＶＤ２０から読み出して地図メモリ１２に格納する。
【００２２】
地図メモリ１２は、本発明の地図データ記憶部に相当するものであり、地図読出制御部１１の制御によってＤＶＤ２０から読み出された地図データを一時的に格納する。地図メモリ１２に格納される地図データには、マップマッチングや経路探索等の処理に必要なデータから成る道路ユニットが含まれている。この道路ユニットには、道路や車線を細かく分割して複数のベクトルの繋がりで表わしたときの個々のベクトルに相当するリンクに関する情報と、各リンクの両端点に相当するノードに関する情報とが含まれている。
【００２３】
リンクに関する情報としては、リンクの距離、コスト、道路属性、道路種別などの情報が個々のリンクに対して付与されている。また、３本以上のリンクにまたがって通過禁止などの交通規制が設定されている場合は、その交通規制を表わす特殊交通規制情報が、規制を構成している３本以上のリンクの少なくとも１つに付与されている。本実施形態では、規制を構成している３本以上のリンクのうち終端リンクに特殊交通規制情報が付与されているものとする。
【００２４】
位置測定部１３は、車両の現在位置を測定するものであり、自立航法センサ、ＧＰＳ受信機、位置計算用ＣＰＵ等で構成されている。自立航法センサは、所定走行距離毎に１個のパルスを出力して車両の移動距離を検出する車速センサ（距離センサ）と、車両の回転角度（移動方位）を検出する振動ジャイロ等の角速度センサ（相対方位センサ）とを含んでいる。自立航法センサは、これらの車速センサおよび角速度センサによって車両の相対位置および方位を検出する。
【００２５】
位置計算用ＣＰＵは、自立航法センサから出力される自車の相対的な位置および方位のデータに基づいて、絶対的な自車位置（推定車両位置）および車両方位を計算する。また、ＧＰＳ受信機は、複数のＧＰＳ衛星から送られてくる電波をＧＰＳアンテナで受信して、３次元測位処理あるいは２次元測位処理を行って車両の絶対位置および方位を計算する（車両方位は、現時点における自車位置と１サンプリング時間ΔＴ前の自車位置とに基づいて計算する）。
【００２６】
目的地設定部１４は、ユーザによるリモコン３０の操作を通じて、誘導経路の目的地を設定する。経路探索部１５は、位置測定部１３により測定された車両現在位置を出発地として、当該出発地から目的地設定部１４により設定された目的地までを結ぶ最もコストが小さな誘導経路を探索する。そして、経路探索部１５は、探索した誘導経路のデータを誘導経路メモリ１６に格納する。
【００２７】
経路探索部１５は、経路探索のアルゴリズムとしてダイクストラ法を用いる。すなわち、経路探索部１５は、出発地ノードから目的地ノードに到る様々なルート上のリンクコストを順次加算し、途中のリンクまでの累積コストに基づき枝狩りをしながら、出発地ノードから目的地ノードまでのリンクコストの合計が最も小さい経路を探索する。
【００２８】
このとき経路探索部１５は、特殊交通規制情報により交通規制が設定されているリンクにおいて枝狩りを行わずに探索したルートも含めて、出発地ノードから目的地ノードまでのリンクコストの合計が最も小さい経路を探索する。具体的には、経路探索部１５は、特殊交通規制情報により交通規制が設定されている３本以上のリンクの終端リンクにおいて、そこに到るまでの様々なルートに関する累積コストの比較を行う際に、特殊交通規制が設定されているリンクにおいて既に枝狩りされたルートを探索対象に復活させて、累積コストの比較を行う。
【００２９】
なお、枝狩りしたルートをいつでも復活させることができるように、経路探索の過程で得られる各ルートのデータを、枝狩りしたルートのデータも含めて全て誘導経路メモリ１６に格納しておく。そして、出発地から目的地までの経路探索が完了した時点で、枝狩りしたルートに関するデータを誘導経路メモリ１６から消去する。
【００３０】
一度枝狩りをしたルートを復活させた後は、その復活させたルートに関して、特殊交通規制が設定されているリンク列上では枝狩りを行わないようにする。復活させたルート上の次のリンクは、特殊交通規制を構成しているリンク列の終端リンクでない可能性もある。そのため、枝狩りを禁止しておかないと、せっかく復活させたルートの探索枝が特殊交通規制の終端リンクまで伸びる前に再び枝狩りされてしまい、復活させたことが無駄になってしまうからである。
【００３１】
なお、復活させたルートに関して、特殊交通規制が設定されているリンク列の全てにおいて枝狩りを禁止するようにしてもよいが、当該リンク列のうち終端リンクにおいては枝狩りを許可するようにしてもよい。終端リンクで枝狩りをしても、復活させたルートの探索枝が特殊交通規制の終端リンクまで伸びる前に再び枝狩りされてしまうことがないからである。本実施形態では、終端リンクでは枝狩りを許可するものとして説明する。
【００３２】
以下に、例を挙げて実際の動作を説明する。例えば、図２のような道路ネットワークが存在し、Ｕターン経路を構成する終端リンクに当たるリンクＬ７に対して、「リンクＬ８→Ｌ５→Ｌ４→Ｌ７」と経由してきた場合には通過できないという特殊交通規制情報が付されているものとする。このような道路ネットワークを有する地図データに基づいて経路探索部１５が誘導経路の探索を行った場合、探索の途中で、図３のように２つのルート（第１ルートおよび第２ルート）に沿って探索枝がリンクＬ５まで伸びてきたとする。
【００３３】
第１ルートは、「・・・→Ｌ８→Ｌ５」の順で探索枝が伸びてきてリンクＬ５に到着したルートである。一方、第２ルートは、「・・・→Ｌ６→Ｌ５」の順で探索枝が伸びてきてリンクＬ５に到着したルートである。これら第１ルートと第２ルートとでリンクＬ５までの累積コストを比較した結果、第１ルートの方が累積コストが低かったとすると、この時点で経路探索部１５は第２ルートを枝狩りし、第１ルートを選択する。
【００３４】
経路探索部１５は、選択した第１ルートに対して引き続き探索処理を行う。そして、図４のようにリンクＬ７まで探索枝が伸びてきたとき、経路探索部１５はリンクＬ７に対して特殊交通規制情報が付与されていることを検知する。これに応じて経路探索部１５は、検知した特殊交通規制情報に基づき交通規制が設定されているリンクＬ５において既に枝狩りされた第２ルートを、図５のように探索対象に復活させる。
【００３５】
経路探索部１５は、探索対象に復活させた第２ルートに対して探索処理を再開する。これにより、リンクＬ５で一度枝狩りされた第２ルートの探索枝が、リンクＬ４まで伸ばされる。この場合、リンクＬ４は既に第１ルートで探索済みであるが、リンクＬ４は特殊交通規制を構成するリンク列の１つで、かつ、終端リンクではないため、この時点で第２ルートの枝狩りは実行しない。
【００３６】
続いて、経路探索部１５は、図６のように第２ルートの探索枝をリンクＬ７まで伸ばす。リンクＬ７は特殊交通規制を構成するリンク列の終端リンクに相当するため、経路探索部１５は枝狩りを実行する。すなわち、経路探索部１５は、第１ルートと第２ルートとでリンクＬ７までの累積コストを比較し、累積コストが低い方を選択して累積コストが高い方を枝狩りする。ここでは第１ルートの方に特殊交通規制が設定されているため、リンクＬ７までの累積コストが第２ルートよりも高くなる。その結果、経路探索部１５は第１ルートを枝狩りして、第２ルートを選択する。
【００３７】
なお、ここでは第１ルートと第２ルートとの２つのルートについて累積コストの比較を行うものとして説明したが、それ以外のルート（例えば、「・・・→Ｌ８→Ｌ２→・・・→Ｌ１→Ｌ７」という第３ルート）もあれば、その第３ルートも含めて累積コストの比較を行う。すなわち、経路探索部１５は、探索枝を伸ばした先のリンクＬ７において、特殊交通規制の設定された第１ルートと、それよりも累積コストが低くなる第３ルートと、復活させた第２ルートとを比較する。このとき、第２ルートの方が第３ルートよりも累積コストが低ければ、経路探索部１５は第１ルートおよび第３ルートを枝狩りして、第１ルートよりも累積コストが高くて一度は枝狩りされた第２ルートを最適なルートとして選択する。
【００３８】
このように、本実施形態によれば、特殊交通規制が存在するために最適経路としては絶対に選択されることがない第１ルートを構成するリンクＬ５において第１ルートと第２ルートとの累積コストを比較した結果、特殊交通規制の設定されていない第２ルートの方が累積コストが高くて枝狩りされてしまうようなケースであっても、第２ルートも含めて探索枝を伸ばしながら、最適な経路の探索を行うことができる。つまり、経路探索部１５は第２ルートを最適経路として選択し、引き続き目的地までの経路を探索することができる。
【００３９】
なお、図５では説明を省略したが、探索枝がリンクＬ７まで伸びてきたときに特殊交通規制情報を検知することによって復活されるルートは、リンクＬ５で枝狩りされた第２ルートの他に、リンクＬ８で枝狩りされたルート（図示せず）も存在する。ただし、リンクＬ８で復活したルートは、その後はリンクをＬ５→Ｌ４→Ｌ７のように辿ることになるので（リンクＬ５，Ｌ４は終端リンクではないので枝狩りされない）、第１ルートと同様に特殊交通規制により通過できないルートとなり、リンクＬ７において枝狩りされる。
【００４０】
このようにいずれは枝狩りされることが分かっているルートについて探索枝を無駄に伸ばしていくことを防ぐために、特殊交通規制を構成するリンク列の始端リンクＬ８に対して、特殊交通規制を構成するリンク列の始端リンクであることを示す情報を持たせる。そして、特殊交通規制を構成するリンク列の終端リンクのみならず、始端リンクにおいても枝狩りを許可する（すなわち、始端リンクおよび終端リンクを除く中間リンクにおいてのみ枝狩りを禁止する）ようにしてもよい。
【００４１】
図７は、本実施形態によるナビゲーション装置１０の動作例（経路探索方法）を示すフローチャートである。図７に示すフローチャートは、誘導経路の目的地を設定して経路探索の指示を出したときにスタートする。図７において、経路探索部１５は、出発地ノードから順に探索枝を１つ先のリンクに伸ばし、伸ばしたリンクまでの累積コストを算出する（ステップＳ１）。
【００４２】
また、経路探索部１５は、伸ばした先のリンクに対して特殊交通規制情報が付与されているか否かを判定する（ステップＳ２）。リンクに対して特殊交通規制情報が付与されていなければ、そのリンクは特殊交通規制を構成している終端リンクではない。この場合、経路探索部１５は、そのリンクに到着するルートが複数あるときは、そのリンクに到るまでの複数のルートに関する累積コストの比較を行う。そして、当該累積コストが高いルートを枝狩りし、累積コストが最も低いルート選択する（ステップＳ３）。
【００４３】
次に、経路探索部１５は、探索枝が目的地まで伸びたか否か、つまり、出発地から目的地までの経路探索が完了したか否かを判定する（ステップＳ４）。探索枝がまだ目的地まで伸びていなければ、処理はステップＳ１に戻る。そして、経路探索部１５は、枝狩りをせずに選択したルートに対して引き続き探索処理を行う。すなわち、探索枝を更に１つ先のリンクまで伸ばし、伸ばしたリンクまでの累積コストを算出する。
【００４４】
そして、伸ばした先のリンクに対して特殊交通規制情報が付与されているか否かを再び判定する（ステップＳ２）。ここで、リンクに対して特殊交通規制情報が付与されていれば、そのリンクは特殊交通規制を構成している終端リンクである。この場合、経路探索部１５は、特殊交通規制が設定されているリンク列の何れかにおいて既に枝狩りされたルートを復活させる（ステップＳ５）。
【００４５】
枝狩りされたルートを復活させたら、経路探索部１５は、その復活させたルートの探索枝を１つ先のリンクまで伸ばし、伸ばしたリンクまでの累積コストを算出する（ステップＳ６）。ここで、伸ばした先のリンクが、特殊交通規制が設定されているリンク列のうち終端リンクであるか否かを判定する（ステップＳ７）。なお、伸ばした先のリンクに対して特殊交通規制情報が付与されていれば、そのリンクは終端リンクであると判断できる。
【００４６】
復活させたルートについて伸ばしたリンクが終端リンクでない場合、その時点での枝狩りは禁止されているので、そのまま処理はステップＳ６に戻る。すなわち、探索枝を更に１つ先のリンクまで伸ばし、伸ばしたリンクまでの累積コストを算出する。一方、復活させたルートについて伸ばしたリンクが終端リンクである場合、処理はステップＳ３に遷移する。以上のようなステップＳ１〜Ｓ７の処理を行って探索枝を順に伸ばしながら途中で枝狩りをしていき、目的地まで探索枝が伸ばされると、一連の経路探索処理が終了する。
【００４７】
以上詳しく説明したように、本実施形態では、出発地ノードから目的地ノードまで様々なルートのリンクコストを順次加算しながら探索枝を伸ばしていく過程で、リンクに付与された特殊交通規制情報を検出した場合、当該特殊交通規制情報により交通規制が設定されているリンクにおいて枝狩りされたルートを復活させて、出発地ノードから目的地ノードまでのリンクコストの合計が最も小さい経路を探索するようにしている。
【００４８】
このように構成した本実施形態によれば、特殊交通規制が存在するために最適経路としては絶対に選択されることがないルート（第１ルート）よりも、特殊交通規制の設定されていないルート（第２ルート）の方が累積コストが高くて枝狩りされてしまうようなケースであっても、当該第２ルートも含めて探索枝を伸ばしながら最適な経路を探索することができる。これにより、リンク上に特殊交通規制が存在したとしても、真の最適経路を算出することができる。
【００４９】
なお、上記実施形態では、特殊交通規制が設定されているリンク列の何れかにおいて枝狩りされたルートを復活させる例について説明したが、本発明はこれに限定されない。例えば、特殊交通規制が設定されている３本以上のリンクうち、始端リンクおよび終端リンクを除いた中間リンクにおいて枝狩りされたルートのみを復活させるようにしてもよい。始端リンクおよび終端リンクで枝狩りされたルートを復活させても意味がないからである。
【００５０】
すなわち、始端リンクで枝狩りされたルートを復活させても、探索枝を伸ばした先の終端リンクに付与されている特殊交通規制情報に基づき結局は枝狩りされる。一方、終端リンクで枝狩りされたルートについては、特殊交通規制を構成するルート以外の別のルートよりも累積コストが高いということであるから、終端リンクで枝狩りされたルートを復活させても、結局はその別のルートよりも累積コストが高くなって枝狩りされる。よって、始端リンクおよび終端リンクで枝狩りされたルートを復活させないようにすることで、意味のない無駄な処理を省くことができ、最適な経路を効率的に求めることができる。
【００５１】
また、上記実施形態では、特殊交通規制を構成している３本以上のリンクのうち終端リンクに特殊交通規制情報が付与されており、特殊交通規制情報を検出したときに、既に枝狩りされたルートを復活させる例について説明したが、本発明はこれに限定されない。例えば、終端リンクに代えてまたは加えて、始端リンクに特殊交通規制情報を付与するようにしてもよい。この場合、経路探索部１５は、始端リンクに特殊交通規制情報が付与されていることを検知したときに、特殊交通規制が設定されているリンク列での枝狩りを禁止して経路探索を行う。なお、特殊交通規制を構成しているリンク列のうち、始端リンクおよび終端リンクを除いた中間リンクにおいてのみ枝狩りを禁止するようにしてもよい。
【００５２】
また、上記実施形態では、リンクに関する情報として特殊交通規制情報を持つ例について説明したが、ノードに関する情報として特殊交通規制情報を持つようにしてもよい。
【００５３】
また、上記実施形態では、ダイクストラ法により経路探索を行う例について説明したが、本発明が適用できるアルゴリズムはこれに限定されない。すなわち、出発地ノードから目的地ノードまで順に複数のルートに沿って探索枝を伸ばしていく過程で枝狩りをし、最終的にリンクコストの合計が最小となるルートを探索するアルゴリズムであれば、本発明を適用することが可能である。
【００５４】
その他、上記実施形態は、何れも本発明を実施するにあたっての具体化の一例を示したものに過ぎず、これによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその精神、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【００５５】
１０ ナビゲーション装置
１２ 地図メモリ（地図データ記憶部）
１５ 経路探索部
【技術分野】
【０００１】
本発明は、ナビゲーション装置および経路探索方法に関し、特に、出発地ノードから目的地ノードまで順にリンクコストを加算しながら複数のルートに沿って各ノードを辿っていき、累積コストが最も小さい経路を誘導経路として探索する経路探索機能を備えたナビゲーション装置に用いて好適なものである。
【背景技術】
【０００２】
一般にナビゲーション装置が備える経路探索機能では、ダイクストラ法と呼ばれるアルゴリズムが多く用いられている。出発地から目的地までのルートとして採り得る様々な経路の中から最適な経路を算出する方法の１つがダイクストラ法である。
【０００３】
ダイクストラ法では、出発地ノードから目的地ノードまで順にリンクコストを加算しながら複数のルートに沿って探索枝を伸ばしていく。探索枝を伸ばしていく過程で、途中同じノードに異なるルートで到着する場合は、そこまでの累積コストが低い方のルートを採用し、累積コストが高い方のルートはそれ以降の探索を中止する。それ以上探索をしても、出発地ノードから目的地ノードまでの最適経路にはなり得ないと考えられるからである。最適経路にはなり得ないと途中で判断されたルートの探索を終了させることを「枝狩り」と呼んでいる。ダイクストラ法では、出発地ノードから目的地ノードまで枝狩りをしながら探索を進めていくため、２地点間の最適経路を効率的に求めることが可能である。
【０００４】
なお、出発地から目的地の間にある道路は、道路幅や道路種別などの属性が様々であり、交通規制などが存在する場合もある。道路や車線を細かく分割して表した個々のリンクに付されるリンクコストは、これらの道路属性や交通規制などによって異なる。すなわち、リンクコストは、例えばリンクの距離をもとに、道路幅、道路種別、右折および左折、交通規制などに応じた所定の定数を乗じた値として設定されており、誘導経路として適正の程度を数値化したものである。
【０００５】
ところで、道路の中には、歩行者専用道路や単車専用道路、私道なども存在する。従来、このように自動車が通行できない道路も含めて最適な経路を探索できるようにした技術が提案されている（例えば、特許文献１参照）。この特許文献１では、通行不可条件を有するリンクが存在する場合、当該通行不可条件を一時的に解除して探索を行い、探索終了後に、通行可能道路のみを推奨経路として採用するようになされている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平１１−３４４３５０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述のように、ダイクストラ法は、出発地ノードから目的地ノードまで枝狩りをしながら探索を進めていくため、探索枝の候補が爆発的に増えるのを抑え、２地点間の最適経路を効率的に求めることができる。しかしながら、探索の過程で順次に枝狩りをするがゆえに、真に最適な経路を探索することができない場合があるという問題があった。以下に、この問題点を詳しく説明する。
【０００８】
例えば、図８（ａ）のように中央分離帯によって上下線が分離された道路では、地図データのノードとリンクは図８（ｂ）のようになっている。図８（ｂ）において、Ｌ１〜Ｌ７はリンクであり、道路や車線を細かく分割して複数のベクトルの繋がりで表わしたときの個々のベクトルに相当する。これらの各リンクＬ１〜Ｌ７に対して、道路属性や交通規制などに応じたリンクコストが設定されている。Ｎ１〜Ｎ８はノードであり、各リンクの両端点に相当する。
【０００９】
このように上下線が分離された道路において、交通規制として、図９（ａ）のようにＵターンを禁止する規制が存在したとする。この場合は、図９（ｂ）に示すように、地図データ上でＵターン経路を構成する終端リンクに当たるリンクＬ６に対して、「リンクＬ７→Ｌ４→Ｌ６」と経由してきた場合には通過できないという交通規制情報が付されている。
【００１０】
このような道路ネットワークでは、「・・・→Ｌ７→Ｌ４」の順で探索してきた第１ルートと、「・・・→Ｌ５→Ｌ４」の順で探索してきた第２ルートとを比較した場合、ダイクストラ法ではリンクＬ４まで（ノードＮ４まで）の累積コストが高い方を枝狩りしてしまう。なお、第１ルートと第２ルートとが共にノードＮ５に到着した時点で枝狩りをしないのは、左折や右折に対してもリンクコストが付されているため、リンクＬ７からリンクＬ４への左折というリンクコストを付加した後でなければ、正しい累積コストの比較ができないからである。
【００１１】
ここで、リンクＬ４までの累積コストを比較した結果、もし、第２ルートの方の累積コストが高い場合は、当該第２ルートは枝狩りされてしまい、それ以上の探索は行われなくなる。しかし、次のリンクＬ６まで加えた「・・・→Ｌ７→Ｌ４→Ｌ６」の第１ルートと「・・・→Ｌ５→Ｌ４→Ｌ６」の第２ルートとを比較した場合、第１ルートはＵターンで通過が禁止されている。そのため、リンクＬ６の地点で見た場合には、第１ルートよりも第２ルートの方が累積コストが低くなる場合がある。ところが、第２ルートはリンクＬ４の地点で既に枝狩りされてしまっているため、実際には第２ルートが選ばれることはない。
【００１２】
このような場合には、第１ルートでも第２ルートでもない、別の第３ルートが最適経路として選ばれることになる。例えば、図１０のような道路ネットワークで、自車位置（リンクＬ１３）から目的地（リンクＬ９）までの経路探索を行ったとする。この場合のリンクＬ４までの最適経路は、「Ｌ１３→Ｌ１０→Ｌ７→Ｌ４」の第１ルートであるものとする。ただし、「Ｌ７→Ｌ４→Ｌ６」のルートには通過禁止の交通規制が付されているため、目的地までの実際の最適経路は、「Ｌ１３→Ｌ８→Ｌ５→Ｌ４→Ｌ６→Ｌ９」の第２ルートであるものとする。
【００１３】
このようなケースにおいて、リンクＬ４の地点で第１ルートと第２ルートとを比較すると、リンクＬ４までの累積コストは第１ルートよりも第２ルートの方が高いため、第２ルートは枝狩りされる。その後、第１ルートの探索枝はリンクＬ６まで伸ばされるが、リンクＬ６に到着するルートには、第１ルートの他にも「Ｌ１３→Ｌ８→Ｌ１４→Ｌ１６→Ｌ１５→Ｌ１→Ｌ６」という第３ルートが存在する。
【００１４】
このリンクＬ６の地点で第１ルートと第３ルートとを比較すると、第１ルートは通過禁止の交通規制が設定されているため、累積コストは第３ルートよりも高くなり、第１ルートは枝狩りされる。その結果、第３ルートが最適経路として算出されてしまう。このように、３本以上のリンクにまたがって通過禁止（以下、これを「特殊交通規制」という）が設定されている道路ネットワークの場合、本来の最適経路（第２ルート）が算出されないことがある。
【００１５】
本発明は、このような問題を解決するために成されたものであり、出発地ノードから目的地ノードに到る途中までの累積コストに基づき枝狩りをしながら経路探索を行うアルゴリズムにおいて、特殊交通規制が存在したとしても本来の最適経路を算出できるようにすることを目的とする。
【課題を解決するための手段】
【００１６】
上記した課題を解決するために、本発明では、出発地ノードから目的地ノードまで様々なルートのリンクコストを順次加算しながら探索枝を伸ばしていく過程で、３本以上のリンクにまたがって設定された特殊交通規制情報を検出した場合、特殊交通規制が設定されているリンクにおいて枝狩りを行わずに探索枝を伸ばしたルートも含めて、出発地ノードから目的地ノードまでのリンクコストの合計が最も小さい経路を探索するようにしている。
【発明の効果】
【００１７】
上記のように構成した本発明によれば、特殊交通規制が存在するために最適経路としては絶対に選択されることがないルート（第１ルートとする）を構成するリンクにおいて複数のルートの累積コストを比較した結果、特殊交通規制の設定されていないルート（第２ルートとする）の方が累積コストが高くて枝狩りされてしまうようなケースであっても、第２ルートも含めて探索枝を伸ばしながら経路探索が行われることとなる。
【００１８】
このため、探索枝を伸ばした先のリンクにおいて、特殊交通規制の設定された第１ルートよりも累積コストが低くなる第３ルートと、探索枝を伸ばす前のリンクにおいて第１ルートよりも累積コストが高くなっていた第２ルートとが比較され、累積コストの低い方が選択されて累積コストの高い方は枝狩りされる。このとき、第２ルートの方が第３ルートよりも累積コストが低ければ、第１ルートよりも累積コストが高くて枝狩りされていたはずの第２ルートが最適なルートとして選ばれるようになる。これにより、リンク上に特殊交通規制が存在したとしても、真の最適経路を算出することができる。
【図面の簡単な説明】
【００１９】
【図１】本実施形態によるナビゲーション装置の機能構成例を示すブロック図である。
【図２】本実施形態による経路探索を行う道路ネットワークの例を示す図である。
【図３】本実施形態による経路探索を行う道路ネットワークの例を示す図である。
【図４】本実施形態による経路探索例を示す図である。
【図５】本実施形態による経路探索例を示す図である。
【図６】本実施形態による経路探索例を示す図である。
【図７】本実施形態によるナビゲーション装置の動作例（経路探索方法）を示すフローチャートである。
【図８】道路ネットワークの例を示す図である。
【図９】道路ネットワークの例を示す図である。
【図１０】従来の経路探索例を示す図である。
【発明を実施するための形態】
【００２０】
以下、本発明の一実施形態を図面に基づいて説明する。図１は、本実施形態によるナビゲーション装置の機能構成例を示すブロック図である。図１に示すように、本実施形態のナビゲーション装置１０は、その機能構成として、地図読出制御部１１、地図メモリ１２、位置測定部１３、目的地設定部１４、経路探索部１５および誘導経路メモリ１６を備えている。
【００２１】
地図読出制御部１１は、ＤＶＤ（Digital Versatile Disk）２０に記憶されている地図データの読み出しを制御する。具体的には、地図読出制御部１１は、位置測定部１３から自車両の現在位置情報を入力し、その車両現在位置を含む所定範囲の地図データの読み出し指示を出力することにより、地図表示や経路探索に必要な地図データをＤＶＤ２０から読み出して地図メモリ１２に格納する。
【００２２】
地図メモリ１２は、本発明の地図データ記憶部に相当するものであり、地図読出制御部１１の制御によってＤＶＤ２０から読み出された地図データを一時的に格納する。地図メモリ１２に格納される地図データには、マップマッチングや経路探索等の処理に必要なデータから成る道路ユニットが含まれている。この道路ユニットには、道路や車線を細かく分割して複数のベクトルの繋がりで表わしたときの個々のベクトルに相当するリンクに関する情報と、各リンクの両端点に相当するノードに関する情報とが含まれている。
【００２３】
リンクに関する情報としては、リンクの距離、コスト、道路属性、道路種別などの情報が個々のリンクに対して付与されている。また、３本以上のリンクにまたがって通過禁止などの交通規制が設定されている場合は、その交通規制を表わす特殊交通規制情報が、規制を構成している３本以上のリンクの少なくとも１つに付与されている。本実施形態では、規制を構成している３本以上のリンクのうち終端リンクに特殊交通規制情報が付与されているものとする。
【００２４】
位置測定部１３は、車両の現在位置を測定するものであり、自立航法センサ、ＧＰＳ受信機、位置計算用ＣＰＵ等で構成されている。自立航法センサは、所定走行距離毎に１個のパルスを出力して車両の移動距離を検出する車速センサ（距離センサ）と、車両の回転角度（移動方位）を検出する振動ジャイロ等の角速度センサ（相対方位センサ）とを含んでいる。自立航法センサは、これらの車速センサおよび角速度センサによって車両の相対位置および方位を検出する。
【００２５】
位置計算用ＣＰＵは、自立航法センサから出力される自車の相対的な位置および方位のデータに基づいて、絶対的な自車位置（推定車両位置）および車両方位を計算する。また、ＧＰＳ受信機は、複数のＧＰＳ衛星から送られてくる電波をＧＰＳアンテナで受信して、３次元測位処理あるいは２次元測位処理を行って車両の絶対位置および方位を計算する（車両方位は、現時点における自車位置と１サンプリング時間ΔＴ前の自車位置とに基づいて計算する）。
【００２６】
目的地設定部１４は、ユーザによるリモコン３０の操作を通じて、誘導経路の目的地を設定する。経路探索部１５は、位置測定部１３により測定された車両現在位置を出発地として、当該出発地から目的地設定部１４により設定された目的地までを結ぶ最もコストが小さな誘導経路を探索する。そして、経路探索部１５は、探索した誘導経路のデータを誘導経路メモリ１６に格納する。
【００２７】
経路探索部１５は、経路探索のアルゴリズムとしてダイクストラ法を用いる。すなわち、経路探索部１５は、出発地ノードから目的地ノードに到る様々なルート上のリンクコストを順次加算し、途中のリンクまでの累積コストに基づき枝狩りをしながら、出発地ノードから目的地ノードまでのリンクコストの合計が最も小さい経路を探索する。
【００２８】
このとき経路探索部１５は、特殊交通規制情報により交通規制が設定されているリンクにおいて枝狩りを行わずに探索したルートも含めて、出発地ノードから目的地ノードまでのリンクコストの合計が最も小さい経路を探索する。具体的には、経路探索部１５は、特殊交通規制情報により交通規制が設定されている３本以上のリンクの終端リンクにおいて、そこに到るまでの様々なルートに関する累積コストの比較を行う際に、特殊交通規制が設定されているリンクにおいて既に枝狩りされたルートを探索対象に復活させて、累積コストの比較を行う。
【００２９】
なお、枝狩りしたルートをいつでも復活させることができるように、経路探索の過程で得られる各ルートのデータを、枝狩りしたルートのデータも含めて全て誘導経路メモリ１６に格納しておく。そして、出発地から目的地までの経路探索が完了した時点で、枝狩りしたルートに関するデータを誘導経路メモリ１６から消去する。
【００３０】
一度枝狩りをしたルートを復活させた後は、その復活させたルートに関して、特殊交通規制が設定されているリンク列上では枝狩りを行わないようにする。復活させたルート上の次のリンクは、特殊交通規制を構成しているリンク列の終端リンクでない可能性もある。そのため、枝狩りを禁止しておかないと、せっかく復活させたルートの探索枝が特殊交通規制の終端リンクまで伸びる前に再び枝狩りされてしまい、復活させたことが無駄になってしまうからである。
【００３１】
なお、復活させたルートに関して、特殊交通規制が設定されているリンク列の全てにおいて枝狩りを禁止するようにしてもよいが、当該リンク列のうち終端リンクにおいては枝狩りを許可するようにしてもよい。終端リンクで枝狩りをしても、復活させたルートの探索枝が特殊交通規制の終端リンクまで伸びる前に再び枝狩りされてしまうことがないからである。本実施形態では、終端リンクでは枝狩りを許可するものとして説明する。
【００３２】
以下に、例を挙げて実際の動作を説明する。例えば、図２のような道路ネットワークが存在し、Ｕターン経路を構成する終端リンクに当たるリンクＬ７に対して、「リンクＬ８→Ｌ５→Ｌ４→Ｌ７」と経由してきた場合には通過できないという特殊交通規制情報が付されているものとする。このような道路ネットワークを有する地図データに基づいて経路探索部１５が誘導経路の探索を行った場合、探索の途中で、図３のように２つのルート（第１ルートおよび第２ルート）に沿って探索枝がリンクＬ５まで伸びてきたとする。
【００３３】
第１ルートは、「・・・→Ｌ８→Ｌ５」の順で探索枝が伸びてきてリンクＬ５に到着したルートである。一方、第２ルートは、「・・・→Ｌ６→Ｌ５」の順で探索枝が伸びてきてリンクＬ５に到着したルートである。これら第１ルートと第２ルートとでリンクＬ５までの累積コストを比較した結果、第１ルートの方が累積コストが低かったとすると、この時点で経路探索部１５は第２ルートを枝狩りし、第１ルートを選択する。
【００３４】
経路探索部１５は、選択した第１ルートに対して引き続き探索処理を行う。そして、図４のようにリンクＬ７まで探索枝が伸びてきたとき、経路探索部１５はリンクＬ７に対して特殊交通規制情報が付与されていることを検知する。これに応じて経路探索部１５は、検知した特殊交通規制情報に基づき交通規制が設定されているリンクＬ５において既に枝狩りされた第２ルートを、図５のように探索対象に復活させる。
【００３５】
経路探索部１５は、探索対象に復活させた第２ルートに対して探索処理を再開する。これにより、リンクＬ５で一度枝狩りされた第２ルートの探索枝が、リンクＬ４まで伸ばされる。この場合、リンクＬ４は既に第１ルートで探索済みであるが、リンクＬ４は特殊交通規制を構成するリンク列の１つで、かつ、終端リンクではないため、この時点で第２ルートの枝狩りは実行しない。
【００３６】
続いて、経路探索部１５は、図６のように第２ルートの探索枝をリンクＬ７まで伸ばす。リンクＬ７は特殊交通規制を構成するリンク列の終端リンクに相当するため、経路探索部１５は枝狩りを実行する。すなわち、経路探索部１５は、第１ルートと第２ルートとでリンクＬ７までの累積コストを比較し、累積コストが低い方を選択して累積コストが高い方を枝狩りする。ここでは第１ルートの方に特殊交通規制が設定されているため、リンクＬ７までの累積コストが第２ルートよりも高くなる。その結果、経路探索部１５は第１ルートを枝狩りして、第２ルートを選択する。
【００３７】
なお、ここでは第１ルートと第２ルートとの２つのルートについて累積コストの比較を行うものとして説明したが、それ以外のルート（例えば、「・・・→Ｌ８→Ｌ２→・・・→Ｌ１→Ｌ７」という第３ルート）もあれば、その第３ルートも含めて累積コストの比較を行う。すなわち、経路探索部１５は、探索枝を伸ばした先のリンクＬ７において、特殊交通規制の設定された第１ルートと、それよりも累積コストが低くなる第３ルートと、復活させた第２ルートとを比較する。このとき、第２ルートの方が第３ルートよりも累積コストが低ければ、経路探索部１５は第１ルートおよび第３ルートを枝狩りして、第１ルートよりも累積コストが高くて一度は枝狩りされた第２ルートを最適なルートとして選択する。
【００３８】
このように、本実施形態によれば、特殊交通規制が存在するために最適経路としては絶対に選択されることがない第１ルートを構成するリンクＬ５において第１ルートと第２ルートとの累積コストを比較した結果、特殊交通規制の設定されていない第２ルートの方が累積コストが高くて枝狩りされてしまうようなケースであっても、第２ルートも含めて探索枝を伸ばしながら、最適な経路の探索を行うことができる。つまり、経路探索部１５は第２ルートを最適経路として選択し、引き続き目的地までの経路を探索することができる。
【００３９】
なお、図５では説明を省略したが、探索枝がリンクＬ７まで伸びてきたときに特殊交通規制情報を検知することによって復活されるルートは、リンクＬ５で枝狩りされた第２ルートの他に、リンクＬ８で枝狩りされたルート（図示せず）も存在する。ただし、リンクＬ８で復活したルートは、その後はリンクをＬ５→Ｌ４→Ｌ７のように辿ることになるので（リンクＬ５，Ｌ４は終端リンクではないので枝狩りされない）、第１ルートと同様に特殊交通規制により通過できないルートとなり、リンクＬ７において枝狩りされる。
【００４０】
このようにいずれは枝狩りされることが分かっているルートについて探索枝を無駄に伸ばしていくことを防ぐために、特殊交通規制を構成するリンク列の始端リンクＬ８に対して、特殊交通規制を構成するリンク列の始端リンクであることを示す情報を持たせる。そして、特殊交通規制を構成するリンク列の終端リンクのみならず、始端リンクにおいても枝狩りを許可する（すなわち、始端リンクおよび終端リンクを除く中間リンクにおいてのみ枝狩りを禁止する）ようにしてもよい。
【００４１】
図７は、本実施形態によるナビゲーション装置１０の動作例（経路探索方法）を示すフローチャートである。図７に示すフローチャートは、誘導経路の目的地を設定して経路探索の指示を出したときにスタートする。図７において、経路探索部１５は、出発地ノードから順に探索枝を１つ先のリンクに伸ばし、伸ばしたリンクまでの累積コストを算出する（ステップＳ１）。
【００４２】
また、経路探索部１５は、伸ばした先のリンクに対して特殊交通規制情報が付与されているか否かを判定する（ステップＳ２）。リンクに対して特殊交通規制情報が付与されていなければ、そのリンクは特殊交通規制を構成している終端リンクではない。この場合、経路探索部１５は、そのリンクに到着するルートが複数あるときは、そのリンクに到るまでの複数のルートに関する累積コストの比較を行う。そして、当該累積コストが高いルートを枝狩りし、累積コストが最も低いルート選択する（ステップＳ３）。
【００４３】
次に、経路探索部１５は、探索枝が目的地まで伸びたか否か、つまり、出発地から目的地までの経路探索が完了したか否かを判定する（ステップＳ４）。探索枝がまだ目的地まで伸びていなければ、処理はステップＳ１に戻る。そして、経路探索部１５は、枝狩りをせずに選択したルートに対して引き続き探索処理を行う。すなわち、探索枝を更に１つ先のリンクまで伸ばし、伸ばしたリンクまでの累積コストを算出する。
【００４４】
そして、伸ばした先のリンクに対して特殊交通規制情報が付与されているか否かを再び判定する（ステップＳ２）。ここで、リンクに対して特殊交通規制情報が付与されていれば、そのリンクは特殊交通規制を構成している終端リンクである。この場合、経路探索部１５は、特殊交通規制が設定されているリンク列の何れかにおいて既に枝狩りされたルートを復活させる（ステップＳ５）。
【００４５】
枝狩りされたルートを復活させたら、経路探索部１５は、その復活させたルートの探索枝を１つ先のリンクまで伸ばし、伸ばしたリンクまでの累積コストを算出する（ステップＳ６）。ここで、伸ばした先のリンクが、特殊交通規制が設定されているリンク列のうち終端リンクであるか否かを判定する（ステップＳ７）。なお、伸ばした先のリンクに対して特殊交通規制情報が付与されていれば、そのリンクは終端リンクであると判断できる。
【００４６】
復活させたルートについて伸ばしたリンクが終端リンクでない場合、その時点での枝狩りは禁止されているので、そのまま処理はステップＳ６に戻る。すなわち、探索枝を更に１つ先のリンクまで伸ばし、伸ばしたリンクまでの累積コストを算出する。一方、復活させたルートについて伸ばしたリンクが終端リンクである場合、処理はステップＳ３に遷移する。以上のようなステップＳ１〜Ｓ７の処理を行って探索枝を順に伸ばしながら途中で枝狩りをしていき、目的地まで探索枝が伸ばされると、一連の経路探索処理が終了する。
【００４７】
以上詳しく説明したように、本実施形態では、出発地ノードから目的地ノードまで様々なルートのリンクコストを順次加算しながら探索枝を伸ばしていく過程で、リンクに付与された特殊交通規制情報を検出した場合、当該特殊交通規制情報により交通規制が設定されているリンクにおいて枝狩りされたルートを復活させて、出発地ノードから目的地ノードまでのリンクコストの合計が最も小さい経路を探索するようにしている。
【００４８】
このように構成した本実施形態によれば、特殊交通規制が存在するために最適経路としては絶対に選択されることがないルート（第１ルート）よりも、特殊交通規制の設定されていないルート（第２ルート）の方が累積コストが高くて枝狩りされてしまうようなケースであっても、当該第２ルートも含めて探索枝を伸ばしながら最適な経路を探索することができる。これにより、リンク上に特殊交通規制が存在したとしても、真の最適経路を算出することができる。
【００４９】
なお、上記実施形態では、特殊交通規制が設定されているリンク列の何れかにおいて枝狩りされたルートを復活させる例について説明したが、本発明はこれに限定されない。例えば、特殊交通規制が設定されている３本以上のリンクうち、始端リンクおよび終端リンクを除いた中間リンクにおいて枝狩りされたルートのみを復活させるようにしてもよい。始端リンクおよび終端リンクで枝狩りされたルートを復活させても意味がないからである。
【００５０】
すなわち、始端リンクで枝狩りされたルートを復活させても、探索枝を伸ばした先の終端リンクに付与されている特殊交通規制情報に基づき結局は枝狩りされる。一方、終端リンクで枝狩りされたルートについては、特殊交通規制を構成するルート以外の別のルートよりも累積コストが高いということであるから、終端リンクで枝狩りされたルートを復活させても、結局はその別のルートよりも累積コストが高くなって枝狩りされる。よって、始端リンクおよび終端リンクで枝狩りされたルートを復活させないようにすることで、意味のない無駄な処理を省くことができ、最適な経路を効率的に求めることができる。
【００５１】
また、上記実施形態では、特殊交通規制を構成している３本以上のリンクのうち終端リンクに特殊交通規制情報が付与されており、特殊交通規制情報を検出したときに、既に枝狩りされたルートを復活させる例について説明したが、本発明はこれに限定されない。例えば、終端リンクに代えてまたは加えて、始端リンクに特殊交通規制情報を付与するようにしてもよい。この場合、経路探索部１５は、始端リンクに特殊交通規制情報が付与されていることを検知したときに、特殊交通規制が設定されているリンク列での枝狩りを禁止して経路探索を行う。なお、特殊交通規制を構成しているリンク列のうち、始端リンクおよび終端リンクを除いた中間リンクにおいてのみ枝狩りを禁止するようにしてもよい。
【００５２】
また、上記実施形態では、リンクに関する情報として特殊交通規制情報を持つ例について説明したが、ノードに関する情報として特殊交通規制情報を持つようにしてもよい。
【００５３】
また、上記実施形態では、ダイクストラ法により経路探索を行う例について説明したが、本発明が適用できるアルゴリズムはこれに限定されない。すなわち、出発地ノードから目的地ノードまで順に複数のルートに沿って探索枝を伸ばしていく過程で枝狩りをし、最終的にリンクコストの合計が最小となるルートを探索するアルゴリズムであれば、本発明を適用することが可能である。
【００５４】
その他、上記実施形態は、何れも本発明を実施するにあたっての具体化の一例を示したものに過ぎず、これによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその精神、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【００５５】
１０ ナビゲーション装置
１２ 地図メモリ（地図データ記憶部）
１５ 経路探索部
【特許請求の範囲】
【請求項１】
３本以上のリンクにまたがって設定された交通規制を表わす特殊交通規制情報が上記３本以上のリンクの少なくとも１つに付与されて成る地図データを記憶する地図データ記憶部と、
上記地図データに含まれる出発地ノードから目的地ノードに到る様々なルート上のリンクコストを順次加算し、途中のリンクまでの累積コストに基づき枝狩りをしながら上記目的地ノードまでのリンクコストの合計が最も小さい経路を探索する経路探索部とを備え、
上記経路探索部は、上記特殊交通規制情報により上記交通規制が設定されているリンクにおいて上記枝狩りを行わずに探索したルートも含めて、上記出発地ノードから上記目的地ノードまでのリンクコストの合計が最も小さい経路を探索することを特徴とするナビゲーション装置。
【請求項２】
上記３本以上のリンクのうち終端リンクに上記特殊交通規制情報が付与されている場合、上記経路探索部は、上記終端リンクにおいてそこに到るまでの様々なルートに関する累積コストの比較を行う際に、上記終端リンクに上記特殊交通規制情報が付与されていることを検知して、上記交通規制が設定されているリンクにおいて枝狩りされたルートを復活させて上記累積コストの比較対象に含めることを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
上記経路探索部は、上記枝狩りされたルートを復活させた場合、当該復活させたルートに関して、上記交通規制が設定されている上記３本以上のリンクでの枝狩りを禁止することを特徴とする請求項２に記載のナビゲーション装置。
【請求項４】
上記経路探索部は、上記枝狩りされたルートを復活させた場合、当該復活させたルートに関して、上記交通規制が設定されている上記３本以上のリンクのうち、始端リンクおよび終端リンクを除いた中間リンクのみで枝狩りを禁止することを特徴とする請求項２に記載のナビゲーション装置。
【請求項５】
上記経路探索部は、上記交通規制が設定されている上記３本以上のリンクのうち、始端リンクおよび終端リンクを除いた中間リンクにおいて枝狩りされたルートのみを復活させて上記累積コストの比較対象に含めることを特徴とする請求項２に記載のナビゲーション装置。
【請求項６】
上記３本以上のリンクのうち始端リンクに上記特殊交通規制情報が付与されている場合、上記経路探索部は、上記始端リンクに上記特殊交通規制情報が付与されていることを検知したときに、上記交通規制が設定されているリンクでの枝狩りを禁止して経路探索を行うことを特徴とする請求項１に記載のナビゲーション装置。
【請求項７】
上記経路探索部は、上記交通規制が設定されている上記３本以上のリンクのうち、始端リンクおよび終端リンクを除いた中間リンクにおいてのみ枝狩りを禁止することを特徴とする請求項６に記載のナビゲーション装置。
【請求項８】
３本以上のリンクにまたがって設定された交通規制を表わす特殊交通規制情報が上記３本以上のうち終端リンクに付与されて成る地図データに基づいて、出発地ノードから目的地ノードに到る様々なルート上のリンクコストを順次加算し、途中のリンクまでの累積コストに基づき枝狩りをしながら上記目的地ノードまでのリンクコストの合計が最も小さい経路を探索するナビゲーション装置の経路探索方法であって、
上記３本以上のリンクのうち終端リンクに上記特殊交通規制情報が付与されているか否かを判定する第１のステップと、
上記終端リンクにおいて上記特殊交通規制情報を検出した場合、上記交通規制が設定されているリンクにおいて既に枝狩りされたルートを復活させる第２のステップと、
上記復活させたルートを含めて、上記終端リンクに到るまでの様々なルートに関する累積コストの比較を行い、当該累積コストが高いルートを枝狩りする第３のステップとを有することを特徴とする経路探索方法。
【請求項１】
３本以上のリンクにまたがって設定された交通規制を表わす特殊交通規制情報が上記３本以上のリンクの少なくとも１つに付与されて成る地図データを記憶する地図データ記憶部と、
上記地図データに含まれる出発地ノードから目的地ノードに到る様々なルート上のリンクコストを順次加算し、途中のリンクまでの累積コストに基づき枝狩りをしながら上記目的地ノードまでのリンクコストの合計が最も小さい経路を探索する経路探索部とを備え、
上記経路探索部は、上記特殊交通規制情報により上記交通規制が設定されているリンクにおいて上記枝狩りを行わずに探索したルートも含めて、上記出発地ノードから上記目的地ノードまでのリンクコストの合計が最も小さい経路を探索することを特徴とするナビゲーション装置。
【請求項２】
上記３本以上のリンクのうち終端リンクに上記特殊交通規制情報が付与されている場合、上記経路探索部は、上記終端リンクにおいてそこに到るまでの様々なルートに関する累積コストの比較を行う際に、上記終端リンクに上記特殊交通規制情報が付与されていることを検知して、上記交通規制が設定されているリンクにおいて枝狩りされたルートを復活させて上記累積コストの比較対象に含めることを特徴とする請求項１に記載のナビゲーション装置。
【請求項３】
上記経路探索部は、上記枝狩りされたルートを復活させた場合、当該復活させたルートに関して、上記交通規制が設定されている上記３本以上のリンクでの枝狩りを禁止することを特徴とする請求項２に記載のナビゲーション装置。
【請求項４】
上記経路探索部は、上記枝狩りされたルートを復活させた場合、当該復活させたルートに関して、上記交通規制が設定されている上記３本以上のリンクのうち、始端リンクおよび終端リンクを除いた中間リンクのみで枝狩りを禁止することを特徴とする請求項２に記載のナビゲーション装置。
【請求項５】
上記経路探索部は、上記交通規制が設定されている上記３本以上のリンクのうち、始端リンクおよび終端リンクを除いた中間リンクにおいて枝狩りされたルートのみを復活させて上記累積コストの比較対象に含めることを特徴とする請求項２に記載のナビゲーション装置。
【請求項６】
上記３本以上のリンクのうち始端リンクに上記特殊交通規制情報が付与されている場合、上記経路探索部は、上記始端リンクに上記特殊交通規制情報が付与されていることを検知したときに、上記交通規制が設定されているリンクでの枝狩りを禁止して経路探索を行うことを特徴とする請求項１に記載のナビゲーション装置。
【請求項７】
上記経路探索部は、上記交通規制が設定されている上記３本以上のリンクのうち、始端リンクおよび終端リンクを除いた中間リンクにおいてのみ枝狩りを禁止することを特徴とする請求項６に記載のナビゲーション装置。
【請求項８】
３本以上のリンクにまたがって設定された交通規制を表わす特殊交通規制情報が上記３本以上のうち終端リンクに付与されて成る地図データに基づいて、出発地ノードから目的地ノードに到る様々なルート上のリンクコストを順次加算し、途中のリンクまでの累積コストに基づき枝狩りをしながら上記目的地ノードまでのリンクコストの合計が最も小さい経路を探索するナビゲーション装置の経路探索方法であって、
上記３本以上のリンクのうち終端リンクに上記特殊交通規制情報が付与されているか否かを判定する第１のステップと、
上記終端リンクにおいて上記特殊交通規制情報を検出した場合、上記交通規制が設定されているリンクにおいて既に枝狩りされたルートを復活させる第２のステップと、
上記復活させたルートを含めて、上記終端リンクに到るまでの様々なルートに関する累積コストの比較を行い、当該累積コストが高いルートを枝狩りする第３のステップとを有することを特徴とする経路探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１１−１８５６０１（Ｐ２０１１−１８５６０１Ａ）
【公開日】平成２３年９月２２日（２０１１．９．２２）
【国際特許分類】
【出願番号】特願２０１０−４７７００（Ｐ２０１０−４７７００）
【出願日】平成２２年３月４日（２０１０．３．４）
【出願人】（０００１０１７３２）アルパイン株式会社 (2,424)
【Ｆターム（参考）】
【公開日】平成２３年９月２２日（２０１１．９．２２）
【国際特許分類】
【出願日】平成２２年３月４日（２０１０．３．４）
【出願人】（０００１０１７３２）アルパイン株式会社 (2,424)
【Ｆターム（参考）】
[ Back to top ]