(57)【要約】【課題】経路探索装置において、過度の処理負荷を負うことなく、現在位置から目的地までの最適経路に加えて類似経路を探索する技術を提供する。【解決手段】経路探索装置において、現在位置から目的地までの最適経路と、現在位置から目的地までの複数の経路のうち、最適経路におけるリンクコストの累計値に許容コストを加えた値以下のリンクコストの累計値である類似経路を探索するにあたり、探索対象のリンクとノードを所定の領域内のものに限定する。【選択図】図８
2015125065.tif 000002
【特許請求の範囲】
【請求項１】
出発地点から目的地点までの経路を探索する経路探索装置であって、
道路をノード及び通行の難易度を示すコストに関するコスト情報が付与されているリンクで表現した道路ネットワークデータが記憶された道路ネットワークデータ記憶部と、
前記出発地点から前記目的地点までの経路であって、該経路を構成する複数の前記リンクのコストを累計して求めた累計コストが最小となる最適経路を求める第一段階経路探索部と、
許容コストを設定する許容コスト設定部と、
前記最適経路を構成するリンクの少なくとも一部が包含される所定領域を選択する領域選択部と、
前記最適経路となる道路に対応したノード及びリンク並びに前記所定領域の内部に存在する道路に対応する前記ノード及びリンクを用いて、前記最適経路のほかに、前記出発地点から目的地点までの経路であって該経路を構成する複数のリンクの累計コストと前記最適経路の累計コストとの乖離が前記許容コスト以下となる経路を求める第二段階経路探索部と
を備える経路探索装置。
【請求項２】
前記リンクには、道路の種別を表わす道路種別属性情報が付与されており、
前記領域選択部は、前記最適経路を構成する少なくとも１つのリンクと、該リンクにノードを介して直接的又は間接的に接続されており前記道路種別属性情報が特定の種別である複数のリンクとを外周辺とする領域を前記所定領域として選択する請求項１に記載の経路探索装置。
【請求項３】
前記リンクには、該リンクに対応する道路が歩道である場合において、該リンクが歩道であることを示す情報としての歩道属性情報が付与されており、
前記領域選択部は、前記最適経路を構成する少なくとも１つのリンクと、該リンクにノードを介して直接的又は間接的に接続されており前記歩道属性情報が付与されている複数のリンクとを外周辺とする領域を前記所定領域として選択する請求項１記載の経路探索装置。
【請求項４】
前記リンクには、道路の種別を表わす道路種別属性情報が付与されており、
前記第一段階経路探索部は、特定の前記道路種別属性情報が付与されたリンクのみを用いて前記最適経路を求める請求項１に記載の経路探索装置。
【請求項５】
前記領域選択部は、前記所定領域を、該所定領域の外周辺を構成するリンクの合計コストが所定値以下となるように選択する請求項１〜４の何れかに記載の経路探索装置。
【請求項６】
前記所定値は、前記許容コストの値である請求項５に記載の経路探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置に関するものである。
【背景技術】
【０００２】
近年では、現在位置（出発地点）から目的地点までの経路を探索する経路探索装置として、自動車に搭載されたカーナビゲーションシステム、スマートフォンを含む携帯電話機、携帯ゲーム機、ＰＮＤ（Personal Navigation Device）、ＰＤＡ（Personal
Digital Assistant）等が知られている。経路探索装置の中には、現在位置から目的地点までの経路として、利用者に複数の経路を提示するものもある。
【０００３】
例えば、特許文献１には、現在位置から目的地点まで最短時間で到着する最適経路を探索するのに加え、到着するまでに利用者が許容できる時間や距離に基づいて許容量を設定し、最適経路のリンクコストの累計値に許容量を加算したリンクコストの累計値の範囲で最適経路とは異なる景観の良い経路を探索する技術が開示されている。また、特許文献２には、自動車が探索された経路を走行しているときに、予め設定された経路途中の交差点等の分岐点に近づくと、分岐点から目的地点までのサブルートを新たに探索して利用者に提示する技術が開示されている。また、特許文献３には、現在位置や目的地点といった特徴地点周辺を探索エリアとして、利用者が利用したいガソリンスタンド等の施設を探索する技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００３−１８５４５３号公報
【特許文献２】特開２００１−３０４８９０号公報
【特許文献３】特開２０００−２３４９３７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、上記従来の技術では、特定の条件の下、最適経路に加えてサブルートが新たに探索されて利用者に提示されるが、特定の条件で探索されたサブルートは、最適経路と大きく異なるリンクを通過する場合があり、最適経路と並列で利用者に提示されるのが適当ではない場合があった。また、歩行者や自転車のように、経路を通過しているときにＵターンや道を横切るといった進行方向を変更する自由度が高い利用者の場合には、最適経路と並列で特定の条件で探索されたサブルートが提示されることがさらに適当ではない場合があり、最適経路と類似する複数の経路を提示して利用者の利便性を高めたいという課題があった。
【０００６】
また、移動中の経路において、特定の分岐点に近づいてから他の経路を再度探索すると、経路探索装置の処理負担が重くなってしまうという課題があった。また、分岐点ごとに経路を再探索して、新たに提示されたサブルートを利用者が選択してしまうと、サブルートを選択することの積み重ねによって、最適経路との乖離が大きくなってしまうという課題があった。その上、経路探索において用いられることのあるダイクストラ法のアルゴリズムでは経路探索の起点とネットワークとしてつながりのある道路の全てについて探索を行なうこととなるため、経路探索処理の負荷が重くなるという難点がある。
【０００７】
このため、特許文献１に記載の技術のように最適経路をダイクストラ法で求めた後でリンクコストを変動させる処理を行なう場合はもちろん、特許文献３に記載の技術のように経路上の特徴点を基準に探索のエリアを設定する場合においても、経路探索のアルゴリズムとしてダイクストラ法を用いる以上は、経路探索装置の処理負担が重くなってしまうという課題があった。
本発明は、上記の課題を解決することのできる経路探索装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、上記課題の少なくとも１つを解決するためになされたものであり、以下の形態として実現可能である。
【０００９】
本発明の一形態によれば、出発地点から目的地点までの経路を探索する経路探索装置が提供される。この経路探索装置は、道路をノード及び通行の難易度を示すコストに関するコスト情報が付与されているリンクで表現した道路ネットワークデータが記憶された道路ネットワークデータ記憶部と、前記出発地点から前記目的地点までの経路であって、該経路を構成する複数の前記リンクのコストを累計して求めた累計コストが最小となる最適経路を求める第一段階経路探索部と、許容コストを設定する許容コスト設定部と、前記最適経路を構成するリンクの少なくとも一部が包含される所定領域を選択する領域選択部と、前記最適経路となる道路に対応したノード及びリンク並びに前記所定領域の内部に存在する道路に対応する前記ノード及びリンクを用いて、前記最適経路のほかに、前記出発地点から目的地点までの経路であって該経路を構成する複数のリンクの累計コストと前記最適経路の累計コストとの乖離が前記許容コスト以下となる経路を求める第二段階経路探索部とを備える。
【００１０】
上記形態の経路探索装置において、前記リンクには、道路の種別を表わす道路種別属性情報が付与されており、前記領域選択部は、前記最適経路を構成する少なくとも１つのリンクと、該リンクにノードを介して直接的又は間接的に接続されており前記道路種別属性情報が特定の種別である複数のリンクとを外周辺とする領域を前記所定領域として選択するものとしてもよい。
【００１１】
上記形態の経路探索装置において、前記リンクには、該リンクに対応する道路が歩道である場合において、該リンクが歩道であることを示す情報としての歩道属性情報が付与されており、前記領域選択部は、前記最適経路を構成する少なくとも１つのリンクと、該リンクにノードを介して直接的又は間接的に接続されており前記歩道属性情報が付与されている複数のリンクとを外周辺とする領域を前記所定領域として選択するものとしてもよい。
【００１２】
上記形態の経路探索装置において、前記領域選択部は、前記所定領域を、該所定領域の外周辺を構成するリンクの合計コストが所定値以下となるように選択するものとしてもよい。
上記形態の経路探索装置において、さらに、前記所定値は、前記許容コストの値としてもよい。
【００１３】
なお、上述した特徴は、本発明の特徴のすべてを列挙したものではなく、これらを要部とする構成（または方法）もまた発明となり得る。
【発明の効果】
【００１４】
本発明によれば、利用者にとっての利便性を高めるための、最適経路とは異なる経路の探索を、従来技術に比べ少ない負荷で行なうことができる。これにより、目的地点に到着するまでの時間にゆとりのある状況で経路探索要求を行なうユーザに対し複数の経路候補を提示することが容易になる。
【図面の簡単な説明】
【００１５】
【図１】経路案内システムの構成図。
【図２】経路探索処理全体のフローチャート。
【図３】第一段階経路探索処理のフローチャート。
【図４】所定領域選択処理のフローチャート。
【図５】設定される所定領域の一例を示す説明図。
【図６】各リンクのコストを示す説明図。
【図７】第二段階経路探索処理のフローチャート。
【図８】探索された最適経路と類似経路との関係を示す説明図。
【図９】探索された最適経路及び類似経路と準類似経路との関係を示す説明図。
【図１０】３次メッシュを用いた所定領域の選択処理を示す説明図。
【図１１】所定領域の選択処理を示す説明図。
【発明を実施するための形態】
【００１６】
以下、本発明を具体化した実施例について説明する。
図１に示すように、本実施例における経路案内システムは、経路探索装置としてのサーバ１０と、複数の携帯端末２０とで構成される。サーバ１０と携帯端末２０とは、インターネット回線３０及び基地局４０を介して通信可能に接続されている。
【００１７】
サーバ１０は、道路ネットワークデータ記憶部としてのハードディスク１１、第一段階経路探索部１２、許容コスト設定部１３、領域選択部１４、第二段階経路探索部１５、サーバ送受信部１６を備える。第一段階経路探索部１２、許容コスト設定部１３、領域選択部１４、第二段階経路探索部１５は、サーバ１０に備えられた図示しないＣＰＵがメモリに展開されたソフトウェアを実行することにより実現される。
【００１８】
ハードディスク１１には、道路ネットワークデータが記憶されている。道路ネットワークは、主に交差点を表現したノードと、道路や歩道を表現したリンクとを含んで構成されている。リンクには、当該リンクに対応する道路を通行する際の難易度を示すコストに関するコスト情報が付与されている。また、リンクには、道路の種別を表わす道路種別属性情報も付与されている。道路種別属性情報を参照することによって、当該リンクに対応する道路が国道であるか、県道であるか、市道であるか等を識別することができる。さらに、ハードディスク１１には、携帯端末２０で経路案内時に表示される地図に関する地図情報も記憶されている。
【００１９】
第一段階経路探索部１２は、出発地点から目的地点まで最適に通行することのできる最適経路を求める機能を有する。ここで、最適経路とは、最短の時間で到達できる経路や最短の距離で到達できる経路、渋滞を極力回避した経路、降雨時にできるだけ濡れることなく通行できる経路など、ユーザの要望に応じた各種経路である。この最適経路は、周知のダイクストラ法で求められる。具体的には、リンクに付与されているコストを累計した場合において、その累計コストが最小となる経路が最適経路として採用される。
【００２０】
許容コスト設定部１３は、許容コストを設定する機能を有する。許容コストとは、最適経路の累計コストと最適経路に共通する部分を有する類似経路の累計コストとの乖離許容幅を定める値である。すなわち、許容コストは、最適経路に含まれる各ノードにリンクを通じて接続する直近のノードが最適経路に含まれない場合において当該直近のノードを経由する最適経路以外の経路を最適経路に類似する類似経路として設定することの可否を定める値である。なお、類似経路には、最適経路に類似した経路のほか、最適経路とは出発地点及び目的地点が同じであって当該最適経路の累計コストよりも許容コスト分だけ高いコスト以内で通行できる経路も含まれる。
【００２１】
領域選択部１４は、第一段階経路探索部１２で求められた最適経路を構成するリンクの少なくとも一部が包含される領域を所定領域として選択する機能を有する。所定領域を選択する処理については後ほど詳述する。
【００２２】
第二段階経路探索部１５は、最適経路とは異なる複数の類似経路を探索する機能を有する。ここで、類似経路は、最適経路における累計コストと許容コストとを合計したコスト内で上述した所定領域内に存在する道路を通行する経路である。この類似経路は、最適経路となる道路に対応したノード及びリンク並びに所定領域の内部に存在する道路に対応するノード及びリンクを用いて探索される。このとき、所定領域の外に存在する道路に対応するノード及びリンクは探索の対象に含まれない。したがって、類似経路を探索する際に探索枝が四方八方に延びることによる経路探索処理の負荷を軽減することができる。
【００２３】
サーバ送受信部１６は、携帯端末２０から送信される各種データを受信するとともに、携帯端末２０に各種データを送信する機能を有する。
携帯端末２０は、ＧＰＳ受信部２１、表示部２２、目的地点設定部２３、端末送受信部２４を備える。
【００２４】
ＧＰＳ受信部２１は、ＧＰＳ（Global Positioning System／全地球測位システム）を構成する人工衛星を用いて測定した携帯端末２０の現在位置（緯度、経度）を特定する位置情報を電波によって受信する。
表示部２２は、経路案内時における現在位置付近の地図等を表示する。表示部２２は、液晶ディスプレイとこれを駆動する駆動回路とを備えている。なお、表示部２２としては、液晶ディスプレイに限らず、有機ＥＬディスプレイなど、種々の表示デバイスを採用することが可能である。
目的地点設定部２３は、テンキーやカーソルキーやタッチパネルなどから構成される入力デバイスであって、利用者による目的地点の設定入力を受け付ける。
【００２５】
端末送受信部２４は、位置情報及び目的地点設定部２３により設定された目的地点情報等をサーバ１０に送信するとともに、サーバ送受信部１６から送信された各種データを受信する機能を有する。具体的には、出発地点としての現在位置及び目的地点に関する位置情報等をサーバ１０に送信する。また、端末送受信部２４は、サーバ１０から経路案内に用いられる地図情報や経路データ等を受信する。
【００２６】
次に、本実施例における経路案内システムを用いて経路を探索する方法について説明する。
図２に示すように、まず、携帯端末２０は、ＧＰＳ受信部２１により、当該携帯端末２０の現在位置（緯度、経度）に関する情報を、出発地点を特定する情報として取得する（ステップＳ１１）。
【００２７】
続いて、携帯端末２０は目的地点設定部２３により利用者による目的地点の入力を受け付ける。携帯端末２０は、出発地点と目的地点とが特定された後、端末送受信部２４により、出発地点及び目的地点の情報とともに、経路探索要求を、インターネット回線３０を介してサーバ１０に送信する（ステップＳ１２）。
【００２８】
サーバ１０のサーバ送受信部１６は、携帯端末２０から送信された出発地点及び目的地点の情報及び経路探索要求を受信する（ステップＳ２０）。
【００２９】
次に、第一段階経路探索部１２は、出発地点から目的地点までの最適経路を求める（ステップＳ３０）。続いて、領域選択部１４は、求められた最適経路を構成するリンクデータ及びノードデータを用いて、所定領域の選択を行なう（ステップＳ４０）。そして、第二段階経路探索部１５は、最適経路を構成するリンクデータ及びノードデータ並びに所定領域の範囲内に存在する道路を表わすリンクデータ及びノードデータを用いて、最適経路とは異なる複数の類似経路を求める（ステップＳ５０）。
【００３０】
なお、第一段階経路探索処理（ステップＳ３０）、所定領域選択処理（ステップＳ４０）、第二段階経路探索処理（ステップＳ５０）の詳細については後述する。
サーバ送受信部１６は、経路データ（最適経路及び複数の類似経路）とハードディスク１１から読み出された経路探索結果に関連する地図情報とをあわせて、インターネット回線３０を介して携帯端末２０に送信する（ステップＳ６０）。
【００３１】
携帯端末２０は、端末送受信部２４により、経路データと経路に関連する地図情報とを受信する（ステップＳ１３）。
最後に、携帯端末２０は、表示部２２により、サーバ１０から得た経路探索結果を地図情報とあわせて携帯端末の利用者に提示することで目的地点までの経路案内を実行する（ステップＳ１４）。
【００３２】
（１）第一段階経路探索処理（図２：ステップＳ３０）
第一段階経路探索部１２は、ハードディスク１１に記憶されている道路ネットワークに基づき、出発地点から目的地点までの最適経路をダイクストラ法により求める。
図３に示すように、まず、第一段階経路探索部１２は、携帯端末２０から受信した出発地点及び目的地点の情報により、出発地点と目的地点とを設定する（ステップＳ３０１）。具体的には、第一段階経路探索部１２は、出発地点の座標情報（緯度、経度）に最も近いリンクまたはノードを出発地点として決定する。目的地点についても同様である。本実施例では、出発地点及び目的地点が何れもノードであるとして説明する。
【００３３】
第一段階経路探索処理において、通常のダイクストラ法を用いて最適経路を探索する場合、あらゆるリンクに探索枝が延びるため探索処理負荷が大きくなる場合もある。そこで本実施例では、探索負荷を軽減するために探索枝が延びるリンクを制限する。具体的には、幅員が一定幅以上である道路に対応するリンクのみを用いて最適経路の探索を行う。一例としては、道路レベルが県道以上である道路に対応するリンクのみを用いる。また、リンクに属性情報として付与されている幅員情報から、一定幅以上の道路のみを用いてもよい。
なお、出発地点及び目的地点付近については県道以上の道路でない場合もある。したがって、出発地点及び目的地点付近についてはすべてのリンクを用いるようにしてよい。
【００３４】
次に、第一段階経路探索部１２は、出発地点であるノードにリンクを介して直接接続されるノードをすべて候補ノードに設定する（ステップＳ３０２）。
続いて、第一段階経路探索部１２は、設定された候補ノードのうち、当該候補ノードに至るまでの累計コストが最小となる候補ノードを確定ノードに決定する（ステップＳ３０３）。
【００３５】
ここで、第一段階経路探索部１２は、確定ノードが目的地点に対応するノードであるか否かを判断する（ステップＳ３０４）。
確定ノードが目的地点に対応するノードでないと判断された場合（ステップＳ３０４：ＮＯ）、第一段階経路探索部１２は、新たな候補ノードを設定する（ステップＳ３０５）。具体的には、第一段階経路探索部１２は、確定ノードにリンクを介して接続される全てのノードを新たな候補ノードに設定する。そして、新たに設定された候補ノードに対して、第一段階経路探索部１２は、確定ノードの決定処理を実行する（ステップＳ３０３）。
【００３６】
一方、確定ノードが目的地点に対応するノードであると判断された場合（ステップＳ３０４：ＹＥＳ）、第一段階経路探索部１２は、出発地点から目的地点までの複数のリンク及びノードのコストを累計した値が最小となる経路を最適経路として決定する（ステップＳ３０６）。そして、第一段階経路探索部１２は第一段階経路探索処理を終了する。
【００３７】
（２）所定領域選択処理（図２：ステップＳ４０）
以下では、リンクに、道路の種別を表わす道路種別属性情報が付与されている場合を例に説明する。一例として、リンクに対応する道路が国道の場合に道路種別属性情報は道路レベル１、都道府県道の場合に道路種別属性情報は道路レベル２、一般道の場合に道路種別属性情報は道路レベル３とする。また、第一段階経路探索部１２における経路探索によって求められた最適経路は、道路種別が都道府県道（道路レベル２）であることを示す道路属性情報が付与されたリンクで構成されている場合を例に説明する。
【００３８】
図４に示すように、許容コスト設定部１３は、許容コストの設定を行なう（ステップＳ４０１）。許容コストの意義は次のとおりである。図５において、最適経路ＯＣ（リンクＬ１７，Ｌ１５，Ｌ１４，Ｌ１３，Ｌ６，Ｌ１）は、出発地点ＳＴから目的地点ＧＬまでの経路のうち、リンクコスト（図６参照）の累計値が最小となる経路である。この最適経路ＯＣとは異なる別の経路（類似経路）を選び出す場合、リンクコストの累計値が最小であるという制約条件を取り払うことになる。許容コストとは、この制約条件を取り払った場合において経路を探索する領域が際限なく広がることを制限するための条件となるものである。以下では、所定領域選択処理において許容コスト設定部１３が許容コストを３と設定した場合を例に説明する。
【００３９】
なお、許容コストの値を大きくすれば、出発地点から目的地点までの経路を探索する際に探索枝が延びる範囲（所定領域）は広くなり得る。その結果として、大回りして目的地点に到着するといった経路が探索される場合もある。それでも許容コストの値を大きくする例としては、目的地点に到着しなければならない時間に余裕があり、寄り道しながら散策したい場合などがあげられる。
【００４０】
次に、領域選択部１４は、最適経路ＯＣを構成するリンクの中から、所定領域選択処理において所定領域ＰＤを選択する際の基準となるリンク（以下、「領域選択基準リンク」という）を設定する（ステップＳ４０２）。この領域選択基準リンクは、所定領域ＰＤを選択する際に当該所定領域ＰＤを規定する外周の一部を構成する。したがって、領域選択基準リンクは最適経路ＯＣ上の連続する複数のリンクであってもよい。領域選択基準リンクを領域選択の際の基準とすることで、求められた所定領域ＰＤの範囲においてある地点からいったんは最適経路ＯＣとは異なる経路を通る経路（いわば迂回経路）を採用したとしても、当該迂回経路は目的地点ＧＬ寄りの別の地点で最適経路ＯＣに帰着することになる。
【００４１】
ここで、領域選択基準リンクの設定方法の一例を、図５を用いて説明する。
なお、図５において、リンクＬ１〜Ｌ６，Ｌ８，Ｌ１２〜Ｌ１７に対応する道路が県道で、それ以外のリンクに対応する道路が市道であるとして以下では説明する。
領域選択部１４は、最適経路ＯＣに含まれるノード（ノードＮ１，Ｎ７〜Ｎ１０）のうち、道路レベルが高い道路（例えば県道以上の道路）であってかつ最適経路ＯＣに含まれない道路に接続しているノード（ノードＮ１，Ｎ９）を抽出する。そして、領域選択部１４は抽出されたノードが複数の場合、最も出発地点ＳＴ側に位置するノード（ノードＮ９）及び最も目的地点ＧＬ側に位置するノード（ノードＮ１）の間に存在するリンク（リンクＬ６，Ｌ１３，Ｌ１４）を領域選択基準リンクとして設定する。
【００４２】
領域選択基準リンクの設定方法は、これに限られることはなく、他の方法を採用してもよい。例えば、最適経路ＯＣにおいて、右左折する地点（ノードＮ７やノードＮ１０）の前後のリンク（リンクＬ６，Ｌ１３及びリンクＬ１５，Ｌ１７）を領域選択基準リンクとして設定してもよい。また、最適経路ＯＣにおいて、直進する経路に対応するリンク（リンクＬ１３〜Ｌ１５）を領域選択基準リンクとして設定してもよい。
以下では、連続するリンク列（リンクＬ６，Ｌ１３，Ｌ１４）を領域選択基準リンクとして説明する。
【００４３】
次に、領域選択部１４は、領域選択基準リンクの進入側（出発地点ＳＴに近い方の端部）に接続しているノードＮ９（進入側ノード）から最適経路ＯＣには属さない他のリンク及びノードを経由し、領域選択基準リンクの退出側（目的地点ＧＬに近い方の端部）に接続しているノードＮ１（退出側ノード）を終点とする道路レベルが高い道路（図５では県道）からなるリンクのつながりを探す。図６の例では、リンク列Ｌ１２，Ｌ８，Ｌ３，Ｌ２が抽出される。
なお、以下では、領域選択基準リンクの退出側ノードＮ１を、「回帰ノード」ともいう。
【００４４】
そして、領域選択部１４は、上記の抽出結果のうち、進入側ノードＮ９から発し回帰ノードＮ１に帰着するリンクの合計コストが、進入側ノードＮ９から回帰ノードＮ１までの、最適経路における合計コストに許容コストを加算した値以下という条件を満たす経路（迂回経路）が存在する否かを判別する（ステップＳ４０３）。
具体的には、図６に示すように、侵入側ノードＮ９から回帰ノードＮ１までの最適経路上のコストは４２である。また、許容コストは３であることから、領域選択部１４は、侵入側ノードＮ９から回帰ノードＮ１まで合計コスト４５以内でたどり着けるリンクのつながりを探すことになる。図６の例では、リンクＬ１２，Ｌ８，Ｌ３，Ｌ２をたどる経路が合計コスト４４であるため、条件を満たす。
なお、コストはノードに対しても付与されている場合もあるが、ここではリンクのコストのみを考慮して処理を実行することとする。当然、ノードのコストを考慮した処理であってもよい。
【００４５】
判別の結果、上記条件を満たす経路が存在するという判別結果が得られなかった場合（ステップＳ４０３：ＮＯ）とは、許容コストの制限範囲内で、進入側ノードＮ９から回帰ノードＮ１に帰着するリンクのつながりを求めることができなかった場合である。この場合、以降に詳述する第二段階経路探索部１５の処理によって、所定領域の範囲内で、最適経路を構成するノードから発する迂回経路を求めようとしても、許容コストの制約条件を満たして最適経路に回帰できるルートを求めることができない可能性もある。そこで、領域選択部１４は、領域処理が完了しているのか否かを判断する（ステップＳ４０６）。領域選択部１４は、領域処理が完了していないと判断した場合には、新たに他の領域選択基準リンクを設定するところから処理を繰り返す（ステップＳ４０２）。
【００４６】
一方、領域選択部１４は、上記条件を満たす経路が１つ以上存在するという判別結果が得られた場合（ステップＳ４０３：ＹＥＳ）、次の処理を実行する。
【００４７】
領域選択部１４は、進入側ノードＮ９を発して、最適経路ＯＣには属さないノードを経由し、回帰ノードＮ１を終点とする複数のリンクのつながりを求める。その上で、領域選択部１４は、領域選択基準リンク（リンクＬ６，Ｌ１３，Ｌ１４）と、得られたリンクコストの累計値が最も大きい値をとりつつ許容コスト内におさまるリンク列（リンクＬ１２，Ｌ８，Ｌ３，Ｌ２）とで規定される領域を所定領域ＰＤに設定する（ステップＳ４０４）。
【００４８】
領域選択部１４は、所定領域ＯＣが予め決められている数（例えば２）だけ選択されたか否かを判断する（ステップＳ４０５）。なお、所定領域ＯＣの数は、あらかじめユーザにより設定されているものとする。
領域選択部１４は、所定領域ＯＣが予め決められている数だけ選択されていると判断した場合には（ステップＳ４０５：ＹＥＳ）、領域選択処理を終了する。
一方、所定領域ＯＣが予め決められている数だけ選択されていないと判断した場合には（ステップＳ４０５：ＮＯ）、領域選択部１４は、領域選択処理が完了条件を満たすか否かを判断する（ステップＳ４０６）。領域選択部１４は、完了条件を満たしていないと判断した場合には、領域選択処理（ステップＳ４０２〜Ｓ４０４）を繰り返す。一方、領域選択処理が完了条件を満たすと判断した場合には、領域選択部１４は、処理を終了する。
ここで、領域選択処理の完了条件としては、領域選択部１４によって、最適経路ＯＣを構成するノードのうち、進入側ノードあるいは回帰ノードとして設定可能なすべてのノードについて、迂回経路の有無に関するすべての確認処理が実行された場合等があげられる。
【００４９】
（３）第二段階経路探索処理（図２：ステップＳ５０）
第二段階経路探索部１５が探索する類似経路の探索範囲は、最適経路に対応するリンクデータ及びノードデータ、並びに領域選択部１４により選択された所定領域内に存在するリンクデータ及びノードデータに制限される。そのため、第二段階経路探索部１５における探索時の処理負荷が軽減される。
【００５０】
図７に示すように、まず、第二段階経路探索部１５は、領域選択処理の結果得られた所定領域内に存在する道路を表わすリンクデータ及びノードデータ、並びに最適経路に対応するリンクデータ及びノードデータをハードディスク１１から読み出す（ステップＳ５０１）。なお、読み出されたリンクデータ及びノードデータは、図示しないＤＲＡＭ等のメモリに記憶される。
【００５１】
次に、第二段階経路探索部１５は、最適経路に含まれるノードである各最適ノードを起点として、領域選択部１４で設定を受けた所定領域に含まれるとして抽出されたリンクデータ及びノードデータのみを用いて、確定ラベルと負けラベルとの差（以下、「経路別コスト差」ともいう。）が許容コスト以下である非最小コスト経路があるか否かを判定する（ステップＳ５０２）。ここで、確定ラベルとは出発地点からあるノードまでの最小コスト経路のコスト累計値である。また、負けラベルとは出発地点からあるノードまでの非最小コスト経路のコスト累計値である。
【００５２】
図８の例において、経路探索時にノードＮ５に到達する際の確定ラベルはリンクＬ１７，Ｌ１５、Ｌ１２，Ｌ１０のコストを加算した４４となる。一方、負けラベルはリンクＬ１７、Ｌ１５，Ｌ１４，Ｌ１１のコストを加算した４５となる。すなわち、ノードＮ５には確定ラベルとして４４が、負けラベルとして４５が付与されることになる。このように、第二段階経路探索部１５は通常のダイクストラ法で算出する確定ラベルに加えて負けラベルについても算出する。
【００５３】
経路別コスト差が許容コスト以下である非最小コスト経路を有する最適ノードがないと判定された場合（ステップＳ５０２：ＮＯ）、第二段階経路探索部１５は、類似経路がないと決定して、第二段階経路探索を終了する。一方、ある最適ノードにおいて、経路別コスト差が許容コスト以下である非最小コスト経路があると判定された場合（ステップＳ５０２：ＹＥＳ）、第二段階経路探索部１５は、当該最適ノードにおける類似経路を探索する。
【００５４】
第二段階経路探索部１５は、経路別コスト差が３以下である非最小コスト経路を探索すると、図８に示すように、最適経路ＯＣに含まれる最適ノードのうち、ノードＮ１，Ｎ８，Ｎ９とにおいて、経路別コスト差が３以下である非最小コスト経路を抽出する。ノードＮ１において経路別コスト差が２である非最小コスト経路は、出発地点ＳＴからノードＮ９までは最適経路と同じ経路を通過し、ノードＮ９からリンクＬ１２、ノードＮ６、リンクＬ８、ノードＮ３、リンクＬ３、ノードＮ２、リンクＬ２を通過してノードＮ１へと到達し、ノードＮ１から目的地ＧＬまでは最適経路と同じ経路を通過する経路（以下、「第１経路」ともいう）である。
【００５５】
なお、ノードＮ９において経路別コスト差が１である非最小コスト経路としては、出発地点ＳＴからリンク１８を通過してノードＮ９へと入り、ノードＮ９から最適経路と同じ経路を通過する経路（以下、「第２経路」ともいう）がある。しかしながら、リンクＬ１８は、所定領域ＰＤ内に存在するリンク、最適経路を構成するリンクのいずれのリンクにも該当しない。したがって、第２経路について第二段階経路探索部１５が探索の対象とすることはない。結果として、第二段階経路探索部１５は、第１経路を類似経路ＲＣとして決定する（ステップＳ５０３）。
【００５６】
次に、第二段階経路探索部１５は、最適経路には含まれずに類似経路にのみ含まれる各準最適ノードにおいて、経路別コスト差が最適経路と類似経路とにおけるコスト累計値の差を許容コストから差し引いた値（以下、「差分許容コスト」ともいう）以下である非最小コスト経路があるか否かを判定する（ステップＳ５０４）。準最適ノードにおいて、経路別コスト差が差分許容コスト以下である非最小コスト経路がないと判定された場合（ステップＳ５０４：ＮＯ）、第二段階経路探索部１５は、第二段階経路探索を終了する。ある準最適ノードにおいて、経路別コスト差が差分許容コスト以下である非最小コスト経路があると判定された場合（ステップＳ５０４：ＹＥＳ）、第二段階経路探索部１５は、当該準最適ノードにおいて準類似経路を探索する。
【００５７】
図９に示すように、第二段階経路探索部１５は、第１経路における準最適ノードであるノードＮ２，Ｎ３，Ｎ６において、経路別コスト差が差分許容コスト以下である非最小コスト経路を抽出する。ノードＮ６において経路別コスト差がゼロである非最小コスト経路は、出発地点ＳＴからノードＮ６までは第１経路と同じ経路を通過し、ノードＮ６からリンクＬ１０、ノードＮ５、リンクＬ７、ノードＮ２へと到達し、ノードＮ２からは第１経路と同じ経路を通過する経路（以下、「第１準経路」ともいう）である。
【００５８】
第二段階経路探索部１５は、第１準経路ＳＲＣを準類似経路として決定する（図７のステップＳ５０５）。
【００５９】
次に、第二段階経路探索部１５は、準類似経路を類似経路として設定し（ステップＳ５０６）、新たに設定された類似経路における準最適ノードにおいて、準類似経路存在判定処理（ステップＳ５０４）を準類似経路がないと判定されるまで繰り返す。経路別コスト差が差分許容コスト以下である非最小コスト経路を有する準最適ノードがないと判定されると（ステップＳ５０４：ＮＯ）、第二段階経路探索部１５は、準類似経路がないと決定して、類似経路探索処理を終了する。
【００６０】
＜実施例の効果＞
以上説明した本実施例によれば、経路探索装置が最適経路とは別の類似経路を探索する処理において、最適経路並びに所定範囲内のリンク及びノードのみを用いて類似経路を探索するため、ダイクストラ法に基礎を置く経路探索法を用いたとしても、探索枝が四方八方に延びることを抑止できる。このため、経路探索装置がアルゴリズムとしてダイクストラ法を用いたとしてもその処理負荷が過重になることなく、経路探索結果を複数提示することが可能になる。
【００６１】
また、本実施例では、探索範囲を規定する所定領域を求めるために、道路種別が都道府県道を表わすリンクを外周とする領域を選択する処理を行なう。これにより、所定領域の選択処理において、都道府県道に比べ多数存在する一般道を表わすリンクを処理の対象とせず、効率的に所定領域を選択することが可能になる。
【００６２】
また、本実施例では、所定領域選択の指標として許容コストを用いることによって、最適経路上のノードから類似経路を求めることのできる蓋然性のあるリンク及びノードのみを対象とした類似経路探索の処理を可能としている。さらに、本実施例では、所定領域の候補が複数存在する場合において、出発地点から目的地点の方向に沿った領域候補を所定領域に設定するという処理基準を適用することで、最適経路からの迂回経路をなるべく多く含むようにして類似経路を探索することを可能にしている。
【００６３】
＜変形例１＞
上記実施例において、領域選択部１４は、進入側ノードから発し回帰ノードに帰着するリンクのつながりのリンクコストの累計値と最適経路における進入側ノードから回帰ノードまでのリンクコストの累計値との乖離が、許容コスト以下となっているリンクのつながりが存在するか否かを判別する。
しかしながら、所定領域を選択する手法は、道路ネットワークデータを利用する手法に限られない。他の例として、道路を表現した道路ポリゴンや河川などの水系を表現した河川ポリゴン等の地図表示のための情報を利用する手法が挙げられる。領域選択部１４は、最適経路を構成するリンクに対応する道路ポリゴン及び他の道路ポリゴンや河川ポリゴン等で規定される閉じた領域を所定領域として設定してもよい。
【００６４】
＜変形例２＞
上記実施例において、領域選択部１４は、進入側ノードから発し回帰ノードに帰着するリンクのつながりであって、最適経路から乖離した部分のリンクコストの累計値が許容コスト以下となっているリンクのつながりが存在するかを判別する。
ここで、最適経路に含まれる領域選択基準リンクと同じ道路属性情報（例えば県道）を有するリンクのみを用いた場合、進入側ノードから回帰ノードに帰着するリンクのつながりが得られない場合がありうる。具体的には、最適経路の付近に県道以上の大きな道路が存在していない場合などである。こうした場合においては、道路レベルの低い（例えば市道）道路に対応するリンクを利用して所定領域を選択してもよい。
【００６５】
＜変形例３＞
領域選択部１４は、所定領域を他の方法によって選択してもよい。
例えば、図１０に示すように、領域選択部１４は、３次メッシュ（ＴＭ１〜４）の区画を所定領域として選択する。なお、メッシュとは、地図を緯度・経度に基づいて網の目状に区画する方法である。２次メッシュとは、緯度差５分、経度差７分３０秒で、一辺の長さが約１０ｋｍのメッシュデータである。３次メッシュとは、２次メッシュを緯度方向及び経度方向に１０等分してできる区域であり、緯度差３０秒、経度差４５秒で、一辺の長さが約１ｋｍの矩形状の領域である。
【００６６】
３次メッシュを選択する方法としては、様々な方法がある。具体的には以下のような３次メッシュを選択対象とすることが考えられる。
・出発地点ＳＴに対応するノードが含まれる３次メッシュ（ＴＭ４）
・目的地点ＧＬに対応するノードが含まれる３次メッシュ（ＴＭ１）
・出発地点ＳＴと目的地点ＧＬとの中間地点に対応するリンクまたはノードが含まれる３次メッシュ
・最適経路ＯＣを構成するリンク、ノードを含むすべての３次元メッシュ（ＴＭ１，ＴＭ２，ＴＭ４）
・最適経路ＯＣを構成するリンク、ノードを最も多く含む３次元メッシュ（ＴＭ１）
・出発地点ＳＴから目的地点ＧＬに仮想直線を引いた場合における、当該仮想直線が通過する３次メッシュ
【００６７】
＜変形例４＞
所定領域選択処理において、最適経路を構成する特定のノードに対応する交差点から脇道に逸れて再び当該交差点に帰る経路が選択されるようにしてもよい。具体的には、領域選択部１４は、領域選択基準リンクの代わりに、最適経路を構成する何れかのノードを領域選択基準ノードとして設定する。そして、領域選択部１４は、当該域選択基準ノードから出発して許容コスト以内で戻る経路が含まれ得る領域を選択する。図１１の場合、例えば、最適経路ＯＣを構成するノードＮ７からリンクＬ２０，ノードＮ１１，リンクＬ２１，ノードＮ１２，リンクＬ２２を経由して再びノードＮ７へと戻る経路で規定される領域が選択されることになる。
【００６８】
＜変形例５＞
上記実施例において、所定領域選択処理において所定領域を選び取る基準となる領域基準リンクとして歩道属性情報が付与されたリンクを用いてもよい。
道路ネットワークデータには、リンクに対応する道路に歩道がある場合に、歩道があることを示す情報としての歩道属性情報が付与されている。領域選択部１４は、最適経路を構成する少なくとも１つのリンクと、そのリンクにノードを介して直接的又は間接的に接続されており歩道属性情報が付与されている複数のリンクとを外周辺とする領域を所定領域として選択する。具体的には、領域選択部１４は、最適経路に含まれており歩道属性情報が付与されたリンクを、領域選択基準リンクとして設定する。そして、領域選択部１４は、当該領域選択基準リンクに接続している進入側ノードから最適経路には属さない他のリンク及びノードを経由し、回帰ノードに至る経路で規定される領域を所定領域として選択する。
その前提として、第一段階経路探索部１２は、歩道属性情報が付与された道路を表わすリンクを用いて最適経路を探索する。
【００６９】
＜変形例６＞
上記実施例において、第一段階経路探索部１２は、出発地点から目的地点までのリンクコストの累計値が最小となる経路のみを最適経路として決定した。しかし、第一段階経路探索部１２によって決定される最適経路は複数であってもよい。例えば、リンクコストの累計値が同一である経路が複数ある場合には、当該複数の経路を最適経路としてもよい。また、リンクコストの累計値が最小ではないが、最小の累計値との乖離が一定の許容限度を超えない経路もまた最適経路に含めてもよい。
【符号の説明】
【００７０】
１０…経路探索装置としてのサーバ、
１１…道路ネットワークデータ記憶部としてのハードディスク、
１２…第一段階経路探索部、
１３…許容コスト設定部、
１４…領域選択部、
１５…第二段階経路探索部、
ＳＴ…出発地点、
ＧＬ…目的地点。
【図１】
2015125065.tif 000003
【図２】
2015125065.tif 000004
【図３】
2015125065.tif 000005
【図４】
2015125065.tif 000006
【図５】
2015125065.tif 000007
【図６】
2015125065.tif 000008
【図７】
2015125065.tif 000009
【図８】
2015125065.tif 000010
【図９】
2015125065.tif 000011
【図１０】
2015125065.tif 000012
【図１１】
2015125065.tif 000013