(57)【特許請求の範囲】
【請求項１】
コンピュータによって実行される経路探索方法であって、
複数の分類パターンの各々が、複数のレベルのうち１つのレベルに分類された複数の道路種別を含み、前記複数の分類パターンの各々が、前記複数のレベルと前記複数の道路種別との対応付けを表し、前記複数の分類パターンの各々が、複数の距離範囲のうち１つの距離範囲に対応する、前記複数の分類パターンの中から、出発地と目的地との距離に基づいて１つの分類パターンを決定し、
決定した分類パターンに基づいて、より下位のレベルの道路種別からより上位のレベルの道路種別へ探索対象を変更しつつ、前記出発地から前記目的地へ向かう第１の経路探索と該目的地から該出発地へ向かう第２の経路探索とを行い、
前記第１の経路探索により得られた道路リンク群からなる第１のネットワークと、前記第２の経路探索により得られた道路リンク群からなる第２のネットワークと、最上位レベルの道路種別の道路リンク群からなる第３のネットワークとを含む道路ネットワークを対象として、前記出発地から前記目的地へ向かう第３の経路探索を行い、
前記第３の経路探索の結果に基づく経路情報を生成する
ことを特徴とする経路探索方法。
【請求項２】
前記１つの分類パターンを決定する処理は、前記距離が前記複数の距離範囲のうちいずれに属するかに応じて、同一の道路種別を前記複数のレベルのうち異なるレベルに属すると決定することを特徴とする請求項１記載の経路探索方法。
【請求項３】
前記コンピュータは、前記距離が前記複数の距離範囲のうちの特定の距離範囲に属し、前記複数のレベルのうち特定のレベル以外に対応づけられた道路が、該特定のレベルに対応付けられた２つの道路の間に存在するとき、該特定のレベル以外に対応づけられた道路のレベルを該特定のレベルに変更することを特徴とする請求項１又は２記載の経路探索方法。
【請求項４】
複数の分類パターンの各々が、複数のレベルのうち１つのレベルに分類された複数の道路種別を含み、前記複数の分類パターンの各々が、前記複数のレベルと前記複数の道路種別との対応付けを表し、前記複数の分類パターンの各々が、複数の距離範囲のうち１つの距離範囲に対応する、前記複数の分類パターンの中から、出発地と目的地との距離に基づいて１つの分類パターンを決定する決定部と、
前記決定部が決定した分類パターンに基づいて、より下位のレベルの道路種別からより上位のレベルの道路種別へ探索対象を変更しつつ、前記出発地から前記目的地へ向かう第１の経路探索と該目的地から該出発地へ向かう第２の経路探索とを行い、該第１の経路探索により得られた道路リンク群からなる第１のネットワークと、該第２の経路探索により得られた道路リンク群からなる第２のネットワークと、最上位レベルの道路種別の道路リンク群からなる第３のネットワークとを含む道路ネットワークを対象として、前記出発地から前記目的地へ向かう第３の経路探索を行う探索部と、
前記第３の経路探索の結果に基づく経路情報を生成する生成部と
を有することを特徴とする経路探索装置。
【請求項５】
複数の分類パターンの各々が、複数のレベルのうち１つのレベルに分類された複数の道路種別を含み、前記複数の分類パターンの各々が、前記複数のレベルと前記複数の道路種別との対応付けを表し、前記複数の分類パターンの各々が、複数の距離範囲のうち１つの距離範囲に対応する、前記複数の分類パターンの中から、出発地と目的地との距離に基づいて１つの分類パターンを決定し、
決定した分類パターンに基づいて、より下位のレベルの道路種別からより上位のレベルの道路種別へ探索対象を変更しつつ、前記出発地から前記目的地へ向かう第１の経路探索と該目的地から該出発地へ向かう第２の経路探索とを行い、
前記第１の経路探索により得られた道路リンク群からなる第１のネットワークと、前記第２の経路探索により得られた道路リンク群からなる第２のネットワークと、最上位レベルの道路種別の道路リンク群からなる第３のネットワークとを含む道路ネットワークを対象として、前記出発地から前記目的地へ向かう第３の経路探索を行い、
前記第３の経路探索の結果に基づく経路情報を生成する
処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索方法、経路探索装置、及びプログラムに関する。
【背景技術】
【０００２】
地図情報に基づいて出発地から目的地までの経路を探索する際に、各道路を道路種別に応じて複数のレベルのいずれかに分類し、１つのレベルを選択して経路探索を行う技術が知られている。この技術では、選択されたレベルの道路網上の仮の出発地及び仮の目的地を求め、その道路網上の最短経路、出発地から仮の出発地までの接続経路、及び仮の目的地から目的地までの接続経路を組み合わせて、出発地から目的地までの経路が求められる。探索対象を１つのレベルの道路に限定することで、経路探索時間が短縮される。
【０００３】
コストに基づく経路探索アルゴリズムとしては、ダイクストラ（Dijkstra）法及びＡ*アルゴリズムを含む幾つかのものが知られている。
ダイクストラ法では、ノード間のエッジにコストを設定し、始点ノードから終点ノードへ向けてコストが相対的に小さいエッジの組み合わせを経路候補として求めることで、最小コストの経路を効率的に求めることができる。
【０００４】
Ａ*アルゴリズムは、ダイクストラ法をさらに効率的になるように改良したアルゴリズムである。このアルゴリズムでは、ダイクストラ法のコストに終点ノードまでのコストの推定値（ヒューリスティック値）を付加して最小コストの経路を探索することで、探索範囲を狭めて処理を効率化することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平６−５２２３７号公報
【非特許文献】
【０００６】
【非特許文献１】E. W. Dijkstra, “ HYPERLINK "http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf" A Note on Two Problems In Connexion with Graphs”, Numerische Mathematik 1, pp. 269-271, 1959.
【非特許文献２】P. E. Hart, N. J. Nilsson, B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions of Systems Science and Cybernetics, Vol. SSC-4, No. 2, pp. 100-107, 1968.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述した従来の経路探索技術には、以下のような問題がある。
各道路を道路種別に応じた１つのレベルに分類する方法では、道路種別ごとにそれぞれが属するレベルが固定的に決定される。したがって、出発地と目的地との距離が長いか短いかにかかわらず、常に同じ種別の道路は同じグループ（レベル）に分類されて経路探索が行われる。
【０００８】
発明者は、出発地と目的地との距離に応じて道路のグルーピングを動的に変更できれば、距離が長いか短いかに応じて探索対象の道路をより柔軟に変更（コントロール）できることに気がついた。
【０００９】
本発明の課題は、出発地から目的地までの経路を探索する際に、出発地と目的地との距離に応じて探索対象となる道路をより柔軟に変更することである。
【課題を解決するための手段】
【００１０】
コンピュータによって実行される経路探索方法は、まず、出発地と目的地との距離に基づいて、経路探索の対象となる複数の道路種別の各々が複数のレベルのいずれに対応するかを決定する。次に、経路探索方法は、上記複数のレベルのうち第１レベルに対応づけられた道路種別を対象とし出発地から目的地へ向かう第１の経路探索と、第１レベルに対応づけられた道路種別を対象とし目的地から出発地へ向かう第２の経路探索とを行う。次に、上記複数のレベルのうち第２レベルに対応づけられた道路種別を対象とし、第１の経路探索により得られた地点と第２の経路探索により得られた地点とに基づく第３の経路探索を行う。そして、第１の経路探索、第２の経路探索、及び第３の経路探索の結果に基づく経路情報を生成する。
【発明の効果】
【００１１】
上述した経路探索方法によれば、出発地から目的地までの経路を探索する際に、出発地と目的地との距離に応じて探索対象となる道路をより柔軟に変更することができる。
【図面の簡単な説明】
【００１２】
【図１】経路探索システムの構成図である。
【図２】経路探索装置の機能的構成図である。
【図３】経路探索処理のフローチャートである。
【図４Ａ】動作パラメータを示す図（その１）である。
【図４Ｂ】動作パラメータを示す図（その２）である。
【図５】レベル決定処理のフローチャートである。
【図６】第１の部分経路探索処理のフローチャートである。
【図７】第２の部分経路探索処理のフローチャートである。
【図８】最上位レベル経路探索処理のフローチャートである。
【図９】近距離探索における第１の部分経路探索を示す図である。
【図１０】近距離探索における第２の部分経路探索を示す図である。
【図１１】近距離探索における最上位レベル経路探索を示す図である。
【図１２】遠距離探索における第１の部分経路探索を示す図である。
【図１３】遠距離探索における第２の部分経路探索を示す図である。
【図１４】遠距離探索における最上位レベル経路探索を示す図である。
【図１５】道路網を示す図である。
【図１６】部分経路を示す図である。
【図１７】２つの高速道路の間の下位レベルの道路を示す図である。
【図１８】２つの高速道路と下位レベルの道路とを経由する経路を示す図である。
【図１９】２つの高速道路の間の下位レベルの道路に接続する別の道路を示す図である。
【図２０】２つの高速道路の間の下位レベルの道路に接続する２つの道路を示す図である。
【図２１】種別変更処理のフローチャートである。
【図２２】情報処理装置の構成図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照しながら、実施形態を詳細に説明する。
図１は、複数の経路探索装置を含む経路探索システムの構成例を示している。図１の経路探索システムは、インタフェース１０３、ロードバランサ１０４、経路探索装置１０５−１〜１０５−４、地図情報データベース１０６、及び交通情報データベース１０７を含む。
【００１４】
端末１０１は、ユーザが利用するサーバ、パーソナルコンピュータ、携帯端末等の情報処理装置であり、有線又は無線の通信ネットワーク１０２を介して、インタフェース１０３にアクセスする。端末１０１は、出発地及び目的地の情報を含む経路探索要求をインタフェース１０３へ送信する。
【００１５】
インタフェース１０３は、経路探索要求を受け付ける情報処理装置であり、受信した経路探索要求をロードバランサ１０４に転送する。ロードバランサ１０４は、複数の経路探索要求を分散させる処理を行う情報処理装置であり、インタフェース１０３から転送された経路探索要求を、所定の負荷分散アルゴリズムに基づいて経路探索装置１０５−１〜１０５−４のいずれかへ送信する。
【００１６】
地図情報データベース１０６は、複数の道路の道路情報を含む地図情報を格納する。各道路の道路情報は、その道路に含まれる複数のノードの位置情報と、ノード間のエッジに対応する道路リンクの情報とを含む。
【００１７】
ノードとは、交差点のように道路が分岐する点を含む、道路を分割する区切りとなる点である。１本の道路がノードにより区切られた各部分が道路リンクである。地図上の１本の道路が、上り線と下り線のように対向する部分に分かれている場合、それぞれに対して独立な、かつ方向を定義したリンクを対応させて考えることもできる。また、１本の道路に対して、方向を定義しないリンクを対応させて考えることもできる。また、各道路の道路情報は、道路種別に関する情報を含む。以下、道路リンクを単にリンクと記載する場合がある。なお、数学のグラフ理論においては、頂点（Ｖｅｒｔｅｘ）と辺（Ｅｄｇｅ）という用語を用いるが、以下においては、ノードとリンクという表現を用いる。
【００１８】
交通情報データベース１０７は、各リンクのコストを含む交通情報を格納する。各リンクのコストとしては、例えば、リンクの両端点間の道程（即ちリンク長）、リンクの両端点間をリンクに沿って移動するのに要する時間、又はリンク長と移動するのに要する時間とを組み合わせたコストが用いられる。リンク長が同じであっても、リンクが属する道路の種別、リンクの位置、リンク上を移動する日時等の条件に応じて移動に要する時間は変化し得る。
【００１９】
経路探索装置１０５−１〜１０５−４のそれぞれは、経路探索処理を行う情報処理装置であり、受信した経路探索要求、地図情報データベース１０６の地図情報、及び交通情報データベース１０７の交通情報に基づいて出発地から目的地への経路を求める。そして、その経路を示す経路情報を生成し、ロードバランサ１０４へ送信する。経路情報は、インタフェース１０３及び通信ネットワーク１０２を介して端末１０１へ送信される。
【００２０】
端末１０１は、受信した経路情報が示す経路を表示するための情報を、他の情報処理装置へ送信したり、その経路を画面上に表示したりする。
【００２１】
図２は、図１の経路探索装置１０５−１〜１０５−４の機能的構成例を示している。経路探索装置１０５−１〜１０５−４は、それぞれが同じ機能を有する情報処理装置であり、それらを代表したものを経路探索装置１０５とする。図２の経路探索装置１０５は、決定部２０１、探索部２０２、生成部２０３、及び動作パラメータ格納部２０４を含む。
【００２２】
動作パラメータ格納部２０４は、決定部２０１及び探索部２０２により参照される動作パラメータを格納する。動作パラメータは、複数の距離範囲の情報、及び各距離範囲に対応する道路のグルーピングの情報を含む。道路種別のグルーピングは、各道路種別と複数のレベルのうち１つのレベルとの対応関係を表す。
【００２３】
図１の経路探索システムは、１つの端末１０１を含んでいるが、実施形態の経路探索システムに含まれる端末の数は２つ以上の場合もある。また、図１の経路探索システムは４台の経路探索装置を含んでいるが、実施形態の経路探索システムに含まれる経路探索装置の数は３台以下の場合もあり、５台以上の場合もある。実際には、システムへの負荷に合わせて経路探索装置の台数が決定される。クラウドコンピューティングでは、経路探索装置の台数が柔軟に増減される場合もある。
【００２４】
経路探索装置を個別の情報処理装置として実装する代わりに、同一の情報処理装置又は異なる情報処理装置上で動作する仮想マシンとして実装しても構わない。また、複数の経路探索要求を各々リアルタイムで処理する代わりに、バッチ処理で処理しても構わない。
【００２５】
さて発明者らは、経路探索システムを開発するにあたり、ダイクストラ法やＡ*アルゴリズムなどのアルゴリズムを利用することを考えた。そして、ダイクストラ法やＡ*アルゴリズムをシステムに実装した場合、経路探索の対象とする範囲が広くなるほど、探索対象とするノードやリンクの数が増加し、その結果、処理時間が長期化することに気づいた。そこで、現実的な処理時間内で解を得るために、２つの考えを導入する必要があることに気づいた。
【００２６】
１つ目は、上記従来技術に記載されている技術である。即ち、各道路を道路種別に応じて複数のレベルに分類し、まず、最下位レベルの道路網を利用して出発地点からより上位のレベルの道路網上の仮の出発地点までの経路を探索し、同様にして、目的地点からより上位のレベルの道路網上の仮の目的地店までの経路を探索する。その上で、仮の出発地点と仮の目的地点をつなぐ経路を該上位のレベルの道路網上で探索する。上位のレベルの道路網に含まれるノードやリンクの数は、より下位のレベルの道路網に含まれるノードやリンクの数よりも一般的には少ない。従って、この技術を利用すれば、上位のレベルを探索対象とすることで、処理時間が長期化することを抑止できよう。また、出発地点から仮の出発地点、目的地点から仮の目的地点までは最下位レベルの道路網を利用し、仮の出発地点から仮の目的地点まではより上位レベルの道路網を利用するという経路は、人が実際に運転する際の行動と類似している。
【００２７】
２つ目は、上記従来技術に記載されている技術である。即ち、上記のような探索の仕方を行なう場合に、行政上の道路種別を、複数まとめて同一レベルとみなすという考え方である。
【００２８】
さらに発明者らは、現実的な処理時間内で解を得るために、これらの考え方を踏まえ、さらなる仕組が必要であることに気づいた。まず、道路種別を複数のレベルに分類する際に、探索処理の対象とする範囲に応じて、分類の仕方を変更するという観点である。ここで、道路を複数のレベルに分類する際には、行政上の道路種別によって決定する必要はなく、それぞれの道路に対して、どのレベルに対応付けるかをそれぞれ決定しても当然構わない。
【００２９】
また別の観点は、探索処理の対象とする距離範囲を何段階かに分け、距離範囲ごとに、探索の仕方を変化させるという観点である。
【００３０】
図３は、図２の経路探索装置１０５の各処理部が協同することにより実行される経路探索処理の例を示すフローチャートである。なお、本実施例における経路探索の処理においては、２地点間の経路を探索する処理であれば、該２地点は、端末１０１のユーザが実際に出発する地点や実際に到着する地点でなくても構わないことは言うまでもない。以降の説明において、出発地もしくは出発地ノード、目的地もしくは目的地ノードと記載する場合があるが、これらは、探索処理の起点となる第１のノードと、探索処理の終点となる第２のノードとの一例である。
【００３１】
まず、決定部２０１は、経路探索要求に含まれる出発地と目的地との距離を、動作パラメータに含まれる複数の距離範囲と比較し、経路探索の対象となる複数の道路種別の各々が複数のレベルのいずれに属するかを決定する（ステップ３０１）。このとき、出発地と目的地との距離を含む距離範囲に対応するグルーピングに基づいて、各道路種別に対応付けるレベルが決定される。距離の算出の仕方としては、例えば出発地の緯度経度と目的地の緯度経度とから、両地点間の直線距離を算出することが考えられる。
【００３２】
次に、探索部２０２は、決定された各道路種別のレベルに基づいて、第１のレベルに対応付けられた道路種別を対象とし出発地ノードから目的地ノードへ向かう第１の経路探索と、第１のレベルに対応付けられた道路種別を対象とし目的地ノードから出発地ノードへ向かう第２の経路探索とを行う（ステップ３０２）。そして、第２のレベルに対応付けられた道路種別を対象とし、第１の経路探索により得られた地点（即ち、経路探索上の中間到達地点であるノード）と第２の経路探索により得られた地点（即ち、経路探索上のもう１つの中間到達地点であるノード）とに基づく第３の経路探索を行う（ステップ３０３）。
【００３３】
次に、生成部２０３は、第１の経路探索、第２の経路探索、及び第３の経路探索の結果に基づく経路情報を生成する（ステップ３０４）。生成された経路情報は、出発地から目的地への経路を示すノード及び道路リンクの情報を含む。
【００３４】
ステップ３０１における処理は、道路種別を複数のレベルに分類する際に、探索処理の対象とする範囲に応じて、分類の仕方を変更するという考え方に相当する処理である。このような経路探索システムによれば、出発地と目的地との距離に応じて道路種別のグルーピングを動的に変更できるため、第１の経路探索、第２の経路探索、及び第３の経路探索において探索対象となる道路種別をより柔軟かつ的確に変更することができる。
【００３５】
なおここで、第１の経路探索、第２の経路探索、および第３の経路探索のそれぞれで探索対象とする道路種別のレベルは、１つのレベルに限る必要はない。また、第１の経路探索と第２の経路探索とで探索対象とする道路種別のレベルは、同一でなくても構わない。またさらに、出発地と目的地との距離に基づいて、ステップ３０２やステップ３０３における探索方法を変更しても構わない。
【００３６】
図５は、図３のステップ３０１において、図４Ａ及び図４Ｂの動作パラメータを用いてレベルを決定する、レベル決定処理の例を示すフローチャートである。図４Ａ及び図４Ｂについての説明は、後述する。
【００３７】
決定部２０１は、地図情報を用いて、例えば出発地の緯度経度と目的地の緯度経度とから、両地点間の距離Ｄを求める。距離Ｄとしては、両地点間の直線距離を利用することが考えられる。そして、距離Ｄを複数の閾値と比較して、Ｄがいずれの距離範囲に含まれるかを判定する（ステップ５０１）。
【００３８】
Ｄが閾値Ｔ１以下の場合（Ｄ≦Ｔ１）即ち第１の距離範囲に含まれる場合、探索方法を至近距離探索に決定し、至近距離探索と対応付けられたグルーピングに基づいて各道路のレベルを決定する（ステップ５０２）。Ｄが閾値Ｔ１より大きく閾値Ｔ２以下の場合（Ｔ１＜Ｄ≦Ｔ２）即ち第２の距離範囲に含まれる場合、探索方法を近距離探索に決定し、近距離探索と対応付けられたグルーピングに基づいて各道路のレベルを決定する（ステップ５０３）。
【００３９】
Ｄが閾値Ｔ２より大きく閾値Ｔ３以下の場合（Ｔ２＜Ｄ≦Ｔ３）即ち第３の距離範囲に含まれる場合、探索方法を中距離探索に決定し、中距離探索と対応付けられたグルーピングに基づいて各道路のレベルを決定する（ステップ５０４）。Ｄが閾値Ｔ３より大きい場合（Ｔ３＜Ｄ）即ち第４の距離範囲に含まれる場合、探索方法を遠距離探索に決定し、遠距離探索と対応付けられたグルーピングに基づいて各道路のレベルを決定する（ステップ５０５）。
【００４０】
図４Ａ及び図４Ｂは、図２の動作パラメータ格納部２０４に格納される動作パラメータの例を示している。図４Ａの例では、出発地と目的地との距離Ｄが属する距離範囲に応じて、至近距離探索、近距離探索、中距離探索、及び遠距離探索の４つの探索方法が定義されている。
【００４１】
また、図４Ｂの例では、道路の種類とレベルとの対応付けの仕方が複数パターン定義されている。図４Ｂにおける高速道路、国道、主要地方道、一般都道府県道、政令市の一般市道、一般道、及びその他道路は、道路法等の規定に基づく道路種別を表す。高速道路には、高速自動車国道のみならず、都市高速道路も含まれる。国道は、例えば一般国道、即ち高速道路ではない一般道路の国道が相当する。道路種別は、経路探索の対象とする国において用いられている種別を利用すればよい。地図情報データベース１０６に格納されている、各道路に対応付けられた道路種別に関する情報は、これらの道路種別のいずれかである。それぞれの探索方法に対応する距離範囲は、以下の通りである。
（１）至近距離探索：距離Ｄが閾値Ｔ１以下である第１の距離範囲。
（２）近距離探索：距離Ｄが閾値Ｔ１より大きく閾値Ｔ２以下である第２の距離範囲。
（３）中距離探索：距離Ｄが閾値Ｔ２より大きく閾値Ｔ３以下である第３の距離範囲。
（４）遠距離探索：距離Ｄが閾値Ｔ３より大きい第４の距離範囲。
【００４２】
また、道路のグルーピングとして例えば以下のような分類の仕方が考えられる。
（１）パターンＡ
第１レベル：国道、主要地方道、一般都道府県道、政令市の一般市道、一般道、その他道路
（２）パターンＢ
第３レベル：高速道路、国道、主要地方道
第２レベル：一般都道府県道、政令市の一般市道
第１レベル：一般道、その他道路
（３）パターンＣ
第４レベル：高速道路、国道
第３レベル：主要地方道
第２レベル：一般都道府県道、政令市の一般市道
第１レベル：一般道、その他道路
（４）パターンＤ
第４レベル：高速道路
第３レベル：国道、主要地方道
第２レベル：一般都道府県道、政令市の一般市道
第１レベル：一般道、その他道路
【００４３】
そして、距離範囲とグルーピングのパターンとの対応付けとして、例えば、至近距離探索にパターンＡを、近距離探索にパターンＢを、中距離探索にパターンＣを、遠距離探索にパターンＤを、それぞれ対応付けることが考えられる。なお、例えば、出発地と目的地との距離に応じた探索処理を行う際に、探索の仕方をいくつかのフェーズに分けて行なうことが考えられ、さらに、該フェーズに応じて、いずれのパターンを利用するかを変化させることも考えられる。
【００４４】
図４Ａの閾値Ｔ１としては、例えば、５００ｍ〜１５００ｍの範囲のいずれかの値が用いられ、閾値Ｔ２としては、例えば、３０００ｍ〜１０ｋｍの範囲のいずれかの値が用いられ、閾値Ｔ３としては、例えば、３０ｋｍ〜１００ｋｍの範囲のいずれかの値が用いられる。図４Ａの例では、距離範囲が４つに分割されているが、距離範囲を３つ以下に分割してもよく、５つ以上に分割してもよい。また図４Ｂに例示した、各グルーピングにおけるレベルの数は、図４Ｂより少なくてもよく、多くてもよい。距離範囲の閾値及び各グルーピングにおけるレベル毎の道路種別は、動作パラメータとして設定される。
【００４５】
図５のようなレベル決定処理によれば、例えば、上述の例では、国道は、遠距離探索においては第３レベルに、中距離探索においては第４レベルに、近距離探索においては第３レベルに、そして至近距離探索においては、第１レベルにグルーピングされる。即ち、このようなレベル決定処理によれば、同一の道路種別のレベルを、出発地と目的地との距離に応じて動的に変更できるため、経路を距離に応じて適切に求め易くなる。
【００４６】
さて、上述のそれぞれの探索方法として、以下のような探索の仕方を適用することが考えられる。
（１）至近距離探索
出発地ノードから目的地ノードに向って、高速道路を除く全道路種別の道路を同一レベル（第１レベル）に分類して、即ち、全道路を対象として、ダイクストラ法またはＡ*アルゴリズム等を利用して経路探索を行う。ただし、出発地又は目的地が高速道路に含まれる場合は、高速道路を第１レベルに追加して経路探索を行う。
【００４７】
（２）近距離探索
まず、第１の経路探索として、出発地ノードから目的地ノードを目指しながら、道路レベル階層上を、上位レベルに向って探索し、或る道路レベル迄到達する。説明のために、このレベルをΛ（ラムダ）とする。第１の経路探索処理の途中では、Λよりも下位の道路レベルが探索対象となるが、Λ以下の道路レベルの中において、より上位レベルのノードｘ１に到達した場合には、以降の探索処理においては、該ノードｘ１からは該上位レベルのリンクを探索対象とする。
【００４８】
第１の経路探索処理の間に、１本以上の候補部分経路を得るが、その候補部分経路群を、ここではＰ１と呼ぶ。また、Ｐ１の各部分経路候補を構成する道路リンクの、Ｐ１全体に亘る集合で構成される道路ネットワークをここではＵ１とする。さらに、Ｐ１がレベルΛの道路と接続するノード群をここではＮ１とする。
【００４９】
次に、第２の経路探索として、目的地ノードから出発地ノードを目指しながら、道路レベル階層上を、上位レベルに向って探索し、レベルΛ迄到達する。第２の経路探索においても、第１の経路探索と同様に、経路探索処理の途中では、Λよりも下位の道路レベルが探索対象となるが、Λ以下の道路レベルの中において、より上位レベルのノードｘ２に到達した場合には、以降の探索処理においては、該ノードｘ２からは該上位レベルのリンクを探索対象とする。
【００５０】
第２の経路探索処理の間に、１本以上の候補部分経路を得るが、その候補部分経路群をここではＰ３と呼ぶ。また、Ｐ３の各部分経路候補を構成する道路リンクの、Ｐ３全体に亘る集合で構成される道路ネットワークをここではＵ３とする。さらに、Ｐ３がレベルΛの道路と接続するノード群をここではＮ３とする。
【００５１】
次に、第３の経路探索として、「Ｎ１、Ｎ３と繋がる、レベルΛの道路」から成るネットワークをＵ２とし、Ｕ１、Ｕ２、Ｕ３から成るネットワーク全体をＵとして、出発地ノードからＵ上のリンク群を通って目的地ノードに至る経路ｐを求める。
【００５２】
第１の経路探索、第２の経路探索、及び第３の経路探索のそれぞれにおいては、ダイクストラ法またはＡ*アルゴリズム等を利用することができる。また、それぞれの経路探索において対象とする道路レベルは、複数レベルであって構わない。
【００５３】
（３）中距離探索
複数フェーズに分けて、経路探索を行うことが考えられる。即ち、出発地ノードから目的地ノードに至る概略経路を求める第１の経路探索と、第１の経路探索の結果に基づいて限定した探索範囲内で詳細経路を求める第２の経路探索の２つのフェーズにわけて経路探索を行うことが考えられる。
【００５４】
まず、第１の経路探索では、上位レベル（典型的には最上位レベル）に対応付ける道路種別を、数少ない種別（例えば高速道路と国道のみ）に絞る。
次に、第２の経路探索では、第1の経路探索の結果得た経路を含む領域を設定する。設定する領域として例えば、「第１の経路探索の結果得た経路を覆う、空間的に連続する１つ以上の矩形領域の集合」、或いは、「出発地と目的地を結ぶ線分を覆う、空間的に連続する１つ以上の矩形領域の集合」、或いは、「これらの矩形集合の和集合」、さらには、「該和集合と、該和集合を空間展開した時に生じる『その部分自体該矩形領域に覆われていないが、該矩形領域に囲まれている部分』を覆う矩形領域の集合との和集合」が考えられる。そして、その設定した領域内に限定して、経路探索を行う。第２の経路探索においては、上位レベル（典型的には最上位レベル）に対応付ける道路種別を、第１の経路探索よりも増やしたものとする。そして、第２の経路探索の結果の経路を以って、中距離経路探索全体の探索結果とする。
【００５５】
（４）遠距離探索
まず、出発地ノードに近い、高速道路の入口候補群Ｅを求める。候補群Ｅとして例えば、「出発地ノードから最も近い方から幾つかの入口」、「出発地ノードから最も近い方から幾つかの入口の中で、『出発地ノードと１つの入口との直線距離  ＋  該１つの入口と目的地ノードとの直線距離』の値が最も小さい方の幾つか」の内の、幾つかを選ぶことができる。
【００５６】
そして、出発地ノードからＥに向って、上述の至近距離探索または近距離探索を行う。その結果、遠距離探索全体の一部としての、候補部分経路群が得られる。ここでは説明のため、この候補部分経路群のことをＲ１とする。また、Ｒ１の各部分経路候補を構成する道路リンクの、Ｒ１全体に亘る集合で構成される道路ネットワークをＷ１とする。Ｒ１が高速道路と接続するノード群はＥである。
【００５７】
次に、目的地ノードに近い、高速道路の出口候補群Ｓを求める。候補群Ｓとして例えば、「目的地ノードから最も近い方から幾つかの出口」、「目的地ノードから最も近い方から幾つかの出口の中で、『出発地ノードと１つの出口との直線距離  ＋  該１つの出口と目的地との直線距離』の値が最も小さい方の幾つか」の内の、幾つかを選ぶことができる。
【００５８】
そして、目的地ノードからＳに向って、上述の至近距離探索または近距離探索を行う。その結果、遠距離探索全体の一部としての、候補部分経路群が得られる。ここでは説明のため、この候補部分経路群のことをＲ３とする。また、Ｒ３の各部分経路候補を構成する道路リンクの、Ｒ３全体に亘る集合で構成される道路ネットワークをＷ３とする。Ｒ３が高速道路と接続するノード群はＳである。
【００５９】
次に、「Ｅ、Ｓと繋がる高速道路」から成るネットワークをＷ２とし、Ｗ１、Ｗ２、Ｗ３から成るネットワーク全体をＷとして、出発地ノードからＷ上のリンク群を通って目的地ノードに至る経路ｒを、Dijkstra法、A*アルゴリズム等を用いて求める。そして、この結果をもって、遠距離探索全体の探索結果とする。
【００６０】
上記の距離別の経路探索方法について別の表現をするならば、近距離探索、中距離探索、及び遠距離探索においては、まず、出発地に繋がる最下位レベルの道路を対象とする経路探索が行われる。そして、下位レベルの道路を対象とする経路探索中に上位レベルの道路に到達した場合、それ以降は上位レベルの道路を対象とする経路探索に切り替える処理を繰り返すことで、出発地ノードから最上位レベルの道路に到達する部分経路として出発地側部分経路を求めることができる。同様にして、目的地ノードから最上位レベルの道路に到達する部分経路として目的地側部分経路を求めることができる。さらに、出発地側部分経路と目的地側部分経路の間に挟まれて存在し、両部分経路を繋ぐ、最上位レベルの道路を通る経路として中間部分経路を求めることができる。最終的には、出発地を起点として、出発地側部分経路、目的地側部分経路、中間部分経路を繋ぎ、出発地から目的地に至る経路全体が求められる。
【００６１】
ここで、目的地側部分経路を、独立したステップとして、中間部分経路を求める前に、予め求めるのは、出発地側部分経路、中間部分経路、目的地側部分経路の順に経路を求めようとしても、目的地側部分経路への入口が分からない、即ち中間部分経路がどこ迄到達した時点で目的地側部分経路を求め始めればよいか、分かり難いからである。
【００６２】
なお、下位のレベルの道路種別を対象とした経路探索を行っている場合に、複数段階以上上位のレベルの道路上のノードが探索される場合があってもよい。例えば、第１レベルの道路種別を対象として経路探索を行っている最中に第３レベルの道路上のノードが探索された場合、以降の探索処理においては、第３レベルの道路上のノードを探索対象とすればよい。
【００６３】
また、出発地ノードや目的地ノードが面する道路は、第１レベルに相当する道路に限る必要は無く、第２レベル以上に相当する道路種別であってもよい。
【００６４】
図６−図８は、図３のステップ３０２及び３０３において、図４の動作パラメータを用いてレベルを切り替えながら経路探索を行う切替探索処理の例を示すフローチャートである。図６は、ステップ３０２の第１の経路探索に相当し、出発地から、処理対象とする距離範囲における最上位レベルの道路に到達する部分経路を求める第１の部分経路探索処理のフローチャートである。図７は、ステップ３０２の第２の経路探索に相当し、目的地から、処理対象とする距離範囲における最上位レベルの道路に到達する部分経路を求める第２の部分経路探索処理のフローチャートである。図８は、ステップ３０３に相当し、処理対象とする距離範囲における最上位レベルの道路を対象とする最上位レベル経路探索処理のフローチャートである。
【００６５】
第１の部分経路探索処理において求められる部分経路の数ｎ（ｎは１以上の整数）と、第２の部分経路探索処理において求められる部分経路の数ｍ（ｍは１以上の整数）は、動作パラメータとして設定される。経路探索アルゴリズムとしては、例えば、ダイクストラ法又はＡ*アルゴリズムが用いられ、探索中に経由ノード候補（ここでは、正解経路の候補が通るノード）となるノードの情報はオープンリストに保持される。オープンリストとは、正解経路の候補である経路候補が通るノードの情報と、その経路候補のコスト値とが対応づけられた情報である。
【００６６】
第１の部分経路探索処理において、探索部２０２は、まず、動作パラメータ値として与えられている、決定された探索方法に対応する道路のグルーピングを参照して、出発地から最上位レベルの道路に到達する部分経路を探索する（図６のステップ６０１）。部分経路の探索では、地図情報に含まれる複数の道路のうち、最下位レベルから、最上位レベルより下位のレベルまでの道路が対象となる。部分経路の探索中に、より上位レベルの道路に到達した場合、それ以降は該到達したレベルの道路を対象とする探索に切り替える処理が繰り返される。ステップ６０１では、このような探索の１ステップとして、対象とする道路に沿って各隣接ノード対間の１つの道路リンクを辿る処理が行われる。
【００６７】
次に、探索部２０２は、道路リンクを辿ることで目的地に到達したか否かをチェックする（ステップ６０２）。目的地に到達した場合は（ステップ６０２，Ｙｅｓ）、出発地から目的地への経路が見つかったため、切替探索処理を終了する。
【００６８】
目的地に到達していない場合（ステップ６０２，Ｎｏ）、次に、これまでの処理により最上位レベルの道路に到達した回数がｎ回か否かをチェックする（ステップ６０３）。最上位レベルの道路に到達した回数がｎ回未満の場合は（ステップ６０３，Ｎｏ）、ステップ６０１以降の処理を繰り返し、最上位レベルの道路に到達した回数がｎ回の場合は（ステップ６０３，Ｙｅｓ）、第１の部分経路探索処理を終了する。これにより、ｎ本の部分経路と、それぞれの部分経路の端点であり、最上位レベルの道路上の到達地点（但し、経路探索全体の中では、中間到達地点に相当する）であるｎ個のノードが求められる。これらのノードは、最上位レベルの道路のいずれかのリンクの端点である。
【００６９】
第２の部分経路探索処理において、探索部２０２は、まず、動作パラメータ値として与えられている、決定された探索方法に対応する道路のグルーピングを参照して、目的地から最上位レベルの道路に到達する部分経路を探索する（図７のステップ７０１）。部分経路の探索では、地図情報に含まれる複数の道路のうち、最下位レベルから、最上位レベルより下位のレベルまでの道路が対象となる。部分経路の探索中に、より上位レベルの道路に到達した場合、それ以降は該到達した上位レベルの道路を対象とする探索に切り替える処理が繰り返される。ステップ７０１では、このような探索の１ステップとして、対象とする道路に沿って各隣接ノード対間の１つの道路リンクを辿る処理が行われる。
【００７０】
次に、探索部２０２は、道路リンクを辿ることで出発地に到達したか否かをチェックする（ステップ７０２）。出発地に到達した場合は（ステップ７０２，Ｙｅｓ）、出発地から目的地への経路が見つかったため、切替探索処理を終了する。
【００７１】
出発地に到達していない場合（ステップ７０２，Ｎｏ）、次に、これまでの処理により最上位レベルの道路に到達した回数がｍ回か否かをチェックする（ステップ７０３）。最上位レベルの道路に到達した回数がｍ回未満の場合は（ステップ７０３，Ｎｏ）、次に、これまでの処理により第１の部分経路探索処理で得られたｎ個のノードのいずれかに到達したか否かをチェックする（ステップ７０４）。ｎ個のノードのいずれにも到達していない場合は（ステップ７０４，Ｎｏ）、ステップ７０１以降の処理を繰り返す。ｎ本の部分経路のいずれかの上の、いずれかのノードに到達した場合は（ステップ７０４，Ｙｅｓ）、到達地点のノードを最上位レベルの経路探索の開始点の１つとして、開始点リストに登録し（ステップ７０５）、その後、ステップ７０１以降の処理を繰り返す。
【００７２】
ステップ７０３において最上位レベルの道路に到達した回数がｍ回の場合は（ステップ７０３，Ｙｅｓ）、第２の部分経路探索処理を終了する。これにより、ｍ本の部分経路と、それぞれの部分経路の端点であり、最上位レベルの道路上の到達地点であるｍ個のノードが求められる。
【００７３】
最上位レベルを中心とした経路探索処理において、探索部２０２は、まず、動作パラメータ値として与えられている、決定された探索方法に対応する道路のグルーピングを参照して、地図情報に含まれる複数の道路のうち最上位レベルの道路を中心とする経路探索を行う（図８のステップ８０１）。
【００７４】
この経路探索では、第１の部分経路探索処理で得られた、出発地からｎ個のノードそれぞれまでの経路を構成している道路網に相当するリンクと、第２の部分経路探索処理で得られた、目的地からｍ個のノードそれぞれまでの経路を構成している道路網に相当するリンクと、該ｎ個のノードおよび該ｍ個のノードに繋がる最上位レベルの道路網に相当するリンクとを対象として、出発地から目的地までの経路探索を行う。ここで、出発地からｎ個のノードまでの経路としては、第１の部分経路探索処理で得られた経路を利用しても構わない。
【００７５】
ステップ８０１では、このような探索の１ステップとして、対象とする道路に沿って各隣接ノード対間の１つの道路リンクを辿る処理が行われる。
【００７６】
次に、探索部２０２は、道路リンクを辿ることで目的地に繋がるノードに到達したか否かをチェックする（ステップ８０２）。目的地に繋がるノードに到達していない場合は（ステップ８０２，Ｎｏ）、ステップ８０１以降の処理を繰り返す。目的地に繋がるノードに到達した場合は（ステップ８０２，Ｙｅｓ）、出発地から目的地への経路が見つかったため、最上位レベルを中心とした経路探索処理を終了する。
【００７７】
最上位レベルを中心とした経路探索処理では、第１の部分経路探索処理で得られたｎ個のノードと第２の部分経路探索処理で得られたｍ個のノードの間の経路探索を個別に行ってもよい。しかし、より効率的に処理するには、第１の部分経路探索で得た部分経路を探索済みの経路候補とみなして、１回の経路探索により出発地から目的地への経路を求める方が好ましい。
【００７８】
例えば、近距離探索の場合は、第１の部分経路探索処理において、図９に示すように、図中の細線で示す第１レベルの道路９１１〜９１４を対象として経路探索が行われ、出発地９０１から、図中太線で示す第２レベルの道路９３１に到達する部分経路として、図中点線で示す部分経路９２１及び９２２が求められる。
【００７９】
なおここで、探索範囲を探索する前に、道路９１１〜９１４を探索対象と決めるわけではない。出発地９０１から目的地９０２に向かって経路探索を行うと、その結果、道路９１１〜９１４を探索することになる。またここで、部分経路９２１及び９２２は、第１の部分経路探索の場合、出発地から始まることになる。このようなことは、第２の部分経路探索処理についても同様である。
【００８０】
また、第２の部分経路探索処理において、図１０に示すように、図中の細線で示す第１レベルの道路１００１〜１００５を対象として経路探索が行われ、目的地９０２から、図中太線で示す第２レベルの道路１０２１に到達する部分経路として、図中点線で示す部分経路１０１１及び１０１２が求められる。
【００８１】
そして、最上位レベル経路探索処理において、図１１に示すように、部分経路９２１、第２レベルの道路９３１及び１１２１（１１０１）、及び部分経路１０１１を経由する、出発地９０１から目的地９０２への経路として、図中点線で示す経路１１０２が求められる。
【００８２】
中距離探索の場合は、図９の道路９１１〜９１４及び図１０の道路１００１〜１００５のレベルが第２レベル又は第１レベルとなる。
【００８３】
遠距離探索の場合は、第１の部分経路探索処理において、例えば図１２に示すように、図中細線で示す第３レベル〜第１レベルの道路１２１１〜１２１５を対象として経路探索が行われる。そして、出発地１２０１から、図中太線で示す第４レベルの高速道路１２３１上の出入口１２４１に到達する部分経路として、図中点線で示す部分経路１２２１が求められる。また、第２の部分経路探索処理において、図１３に示すように、図中細線で示す第３レベル〜第１レベルの道路１３０１〜１３０４を対象として経路探索が行われる。そして、目的地１２０２から、図中太線で示す第４レベルの高速道路１３２１上の出入口１３３１に到達する部分経路として、図中点線で示す部分経路１３１１が求められる。
【００８４】
次に、最上位レベル経路探索処理において、図１４に示すように、部分経路１２２１、高速道路１２３１及び１３２１（１４０１）、及び部分経路１３１１を経由する、出発地１２０１から目的地１２０２への経路として、図中点線で示す経路１４０２が求められる。
【００８５】
図６−図８の切替探索処理において、最上位レベルの道路の代わりに、最上位から数レベルの幅の複数のレベルの道路を用いてもよい。この場合、図８の最上位レベル経路探索処理では、複数のレベルの道路を対象とする経路探索が行われる。
【００８６】
また、図６−図８の切替探索処理では、出発地から最上位レベルの道路に到達するｎ個の部分経路を求めた後に、目的地から最上位レベルの道路に到達するｍ個の部分経路を求めているが、別の部分経路探索方法を用いても構わない。例えば、部分経路を探索する処理を出発地側と目的地側で交互に行う方法も考えられる。この方法では、出発地から１つ上のレベルの道路に到達する部分経路を見つけると、次に、目的地から１つ上のレベルの道路に到達する部分経路を見つけ、再び出発地側の部分経路探索に戻って同様の処理が繰り返される。また例えば、目的地から最上位レベルの道路に到達するｍ個の部分経路を求た後に、出発地から最上位レベルの道路に到達するｎ個の部分経路を求めても構わない。
【００８７】
ところで、第２の部分経路探索処理では、第１の部分経路探索処理とは異なり、目的地を始点ノードとし、出発地を終点ノードとする経路探索が行われる。例えば、図１５のような道路網において、ノードａを出発地とし、ノードｚを目的地とすると、ノードｚからノードａへ向けて経路探索が行われ、ノードｘ、ｙ、又はｖを経由して最上位レベルの道路上のノードｓ、ｔ、ｕ、又はｗに到達する部分経路が探索される。そして、最上位レベルの道路上のノードに到達する部分経路のうち、コスト値が低い順にｍ個の部分経路が求められる。
【００８８】
図１５のノード間の道路リンクのコスト値は、以下の通りである。
ノードｔとノードｗの間の道路リンク：２
ノードｗとノードｙの間の道路リンク：１
ノードｔとノードｙの間の道路リンク：４
ノードｓとノードｖの間の道路リンク：１
ノードｖとノードｙの間の道路リンク：２
ノードｖとノードｘの間の道路リンク：１
ノードｕとノードｘの間の道路リンク：５
ノードｙとノードｚの間の道路リンク：３
ノードｘとノードｚの間の道路リンク：６
【００８９】
例えば、ｍ＝３としてダイクストラ法を適用した場合、図１６に示すような３つの経路候補が部分経路として求められる。経路候補“ｚ−ｙ−ｗ”は、ノードｚからノードｙを経由してノードｗに到達する部分経路であり、そのコスト値は３＋１＝４である。経路候補“ｚ−ｙ−ｖ−ｓ”は、ノードｚからノードｙ及びｖを経由してノードｓに到達する部分経路であり、そのコスト値は３＋２＋１＝６である。経路候補“ｚ−ｙ−ｔ”は、ノードｚからノードｙを経由してノードｔに到達する部分経路であり、そのコスト値は３＋４＝７である。
【００９０】
この場合、最上位レベル経路探索処理において図１６のいずれかの経路候補が最上位レベルの道路に接続するノードｗ、ｓ、ｔに接続する経路が見つかった場合、そのノードがオープンリストに追加される。
【００９１】
その後、ノードｗ、ｓ、ｔからｚにかけての部分については、図１６の挙がっている経路候補に含まれるノードとリンクから成る道路ネットワーク、即ち、ノードｚ、ｙ、ｗ、ｖ、ｓ、ｔ及びリンクｚ−ｙ、ｙ−ｗ、ｙ−ｖ、ｖ−ｓ、ｙ−ｔから成る道路ネットワーク上で、探索を進める。なお、探索は、この部分と最上位レベルの道路の部分とをつないだネットワーク全体に対してなされる。また、最上位レベルの道路上の探索のいずれかが、ｗ、ｓ、ｔのいずれかに達したら、最上位レベルの道路上の探索は止めると言ったことはしない。
【００９２】
第１の部分経路探索処理においても、同様にして、出発地を始点ノードとし、目的地を終点ノードとする経路探索が行われ、最上位レベルの道路上のノードに到達する部分経路のうち、コスト値が低い順にｎ個の部分経路が求められる。得られた部分経路は、最上位レベル経路探索処理において経路候補として用いられる。
【００９３】
次に、図１７から図２１までを参照しながら、一部の道路の道路種別を変更することで、その道路が属するレベルを変更する処理について説明する。
【００９４】
発明者らは、特定の種類の道路網間をつなぐ別の種類の道路網について、対応付けるレベルを変更するという考え方に気づいた。上位レベルの道路を対象とする経路探索では、それより下位のレベルの道路を対象としないため、出発地側のノードから目的地側のノードに到達する経路が必ず見つかるとは限らない。その経路が見つかったとしても、著しく遠回りで非現実的な経路である場合もあり得る。そこで、上位レベルの２つ以上の道路が、下位レベルの道路を介して接続しているとき、その下位レベルの道路を一時的に、あるいは恒久的に上位レベルの道路とみなす処理を追加することで、その下位レベルの道路を経由する現実的な経路を求めることが可能になる。
【００９５】
例えば、遠距離探索において、図１７に示すように、高速道路１９０１と高速道路１９０３の間に下位レベルの道路１９０２が存在する場合について説明する。高速道路１９０１は、道路リンク１９１１及び１９１２を含み、道路１９０２は、道路リンク１９２１〜１９２３を含み、高速道路１９０３は、道路リンク１９３１及び１９３２を含む。この場合、図１８に示すように、道路リンク１９２１〜１９２３を高速道路のリンクとみなして経路探索を行うことで、道路１９０２を経由する経路２００１を見つけることができる。
【００９６】
高速道路１９０１と高速道路１９０３を接続する別の高速道路を経由するより、道路１９０２を経由した方がコストが小さいとすると、経路２００１が最小コストの経路である可能性が高い。
【００９７】
例えば、新潟から静岡へ向かう経路を探索するとき、高速道路である関越自動車道と東名高速道路を通過する経路が最小コストの経路であるものとする。この場合、関越自動車道は東名高速道路に直接接続していないため、最上位レベル経路探索において高速道路のみを対象とすると、経路が見つからないか、又は遠回りで非現実的な経路を見つけることになる。しかし、関越自動車道と東名高速道路を接続する主要地方道である環状八号線を高速道路とみなせば、関越自動車道と環状八号線と東名高速道路とを通過する現実的な経路を見つけることができる。
【００９８】
次に、図１９に示すように、道路１９０２に接続する別の道路２１０１が存在し、出発地２１２０が道路２１０１上に存在する場合について説明する。道路２１０１は、道路リンク２１１１及び２１１２を含む。この場合でも、道路リンク１９２１〜１９２３を高速道路のリンクとみなして経路探索を行うことで、出発地２１２０から道路１９０２上のノード２１２１に到達する部分経路を含む経路２１３１を見つけることができる。
【００９９】
なおここで、出発地や目的地は、リンクやノード上に存在するとは限らない。そこで、出発地または目的地から、最寄のリンクに対しておろした垂線のリンク上の交点を出発地に相当するノード、または目的地に相当するノードと考え、他のノードと同等に扱って探索処理を行うことができる。出発地や目的地に相当するノードの設定の仕方については、他の方法を取っても構わない。
【０１００】
また、出発地や目的地に相当するノードを生成したことにより、もとは１本のリンクであったものが、複数のリンクに分割されてもよい。その場合には、元のリンクに対応付けられていた道路種別を分割後のリンク群にも適用することが考えられる。
【０１０１】
これに対して、遠距離探索以外の探索方法では、探索の結果、高速道路を全く含まない経路を得たり、高速道路を含む経路であるとしても道路１９０２周辺では高速道路を通らない経路を得ることもできなければならない。そのため、道路１９０２を元の下位レベルの道路として扱う方が好ましい。一例として、図２０に示すように、道路１９０２に接続する別の道路２２０１及び２２０２が存在し、出発地２２５１が道路２２０１上に存在し、目的地２２５２が道路２２０２上に存在する場合について説明する。道路２２０１は、道路リンク２２１１及び２２１２を含み、道路２２０２は、道路リンク２２２１及び２２２２を含む。
【０１０２】
この場合、道路リンク１９２１〜１９２３を高速道路のリンクとみなすのではなく、元のレベルの道路のリンクとして扱うことで、出発地２２５１から道路１９０２上のノード２２３１及び２２３２を経由して目的地２２５２に到る経路２２４１を見つけることができる。
【０１０３】
図２１は、道路種別を変更する種別変更処理の例を示すフローチャートである。この種別変更処理は、例えば、図６−図８の各処理の最初のステップで行われる。探索部２０２は、まず、レベル決定処理により決定された探索方法が遠距離探索か否かをチェックする（ステップ２３０１）。探索方法が遠距離探索の場合（ステップ２３０１，Ｙｅｓ）、次に、経路探索が最上位レベル経路探索処理であるか否かをチェックする（ステップ２３０２）。
【０１０４】
経路探索が最上位レベル経路探索処理の場合（ここでは、最上位レベルは高速道路だけから成るものとする）（ステップ２３０２，Ｙｅｓ）、２つの高速道路の間をつなぐ形で存在し、それらの高速道路を接続する下位レベルの道路の道路種別を高速道路に変更する、即ち、高速道路に変更したものとみなしてその後の探索処理を行う（ステップ２３０４）。
【０１０５】
経路探索が最上位レベル経路探索処理以外の場合（ステップ２３０２，Ｎｏ）、次に、２つの高速道路の間に存在し、それらの高速道路を接続する下位レベルの道路を高速道路とみなした経路探索の対象とするか否かをチェックする（ステップ２３０３）。例えば、それら高速道路のいずれかに入っていく場合は、高速道路とみなした経路探索の対象とする。また、それら高速道路の何れにも入っていこうとはせず、他の高速道路の入口を目指して経路探索を進めている場合は、高速道路とみなした経路探索の対象とはしない。
【０１０６】
下位レベルの道路を対象とする場合（ステップ２３０３，Ｙｅｓ）、その道路の道路種別を高速道路に変更する（ステップ２３０４）。
【０１０７】
一方、探索方法が遠距離探索以外の場合（ステップ２３０１，Ｎｏ）、又は２つの高速道路を接続する下位レベルの道路を高速道路とみなした経路探索の対象としない場合は（ステップ２３０３，Ｎｏ）、道路種別を変更しない。
【０１０８】
なお、上位レベルの道路が高速道路以外の国道、主要地方道等である場合も、それらの道路の間に下位レベルの道路が存在するときは、その下位レベルの道路を上位レベルの道路とみなすことができる。これにより、高速道路の場合と同様に、現実的な経路が見つかる可能性が高くなる。
【０１０９】
各探索方法において高速道路を使用するか否かをユーザが指定することも可能である。この場合、端末１０１は、至近距離探索、近距離探索、中距離探索、及び遠距離探索のそれぞれにおいて高速道路の使用可否を示す使用可否情報を経路探索システムに送信する。そして、経路探索装置１０５−１〜１０５−４は、その使用可否情報を動作パラメータ格納部２０４に格納し、あるいは、動作パラメータ格納部２０４には格納せずに直接受け取るだけで、探索部２０２は、使用可否情報が使用不可を示すとき、対応する探索方法において高速道路を除外した経路探索を行う。
【０１１０】
遠距離探索において高速道路使用不可が指定されている場合は、探索方法を中距離探索に変更してもよい。
【０１１１】
図５、図６−図８、及び図２１に示した各フローチャートは一例に過ぎず、経路探索システムの構成や条件に応じて一部の処理を省略又は変更してもよい。経路探索アルゴリズムとして、ダイクストラ法又はＡ*アルゴリズム以外のものを用いることも可能である。例えば、分岐限定法、山登り法、最良優先探索等のアルゴリズムを用いてもよい。
【０１１２】
また、道路種別に基づいて道路を分類する代わりに、道路リンクの長さ、幅、走行速度上限等の属性に基づいて道路を分類しても構わない。道路リンクの長さに基づく場合は、長い道路ほど上位のレベルに分類され、道路の幅に基づく場合は、幅が広い道路ほど上位のレベルに分類される。道路の上限走行速度に基づく場合は、上限走行速度が大きい道路ほど上位のレベルに分類される。いずれの場合も、上位レベルの道路になるほど自動車がより走行し易くなるグルーピングが採用される。
【０１１３】
図１の端末１０１、インタフェース１０３、ロードバランサ１０４、経路探索装置１０５−１〜１０５−４、地図情報データベース１０６、及び交通情報データベース１０７は、例えば、図２２に示すような情報処理装置（コンピュータ）を用いて実現可能である。
【０１１４】
図２２の情報処理装置は、Central Processing Unit （ＣＰＵ）２４０１、メモリ２４０２、入力装置２４０３、出力装置２４０４、外部記憶装置２４０５、媒体駆動装置２４０６、及びネットワーク接続装置２４０７を備える。これらはバス２４０８により互いに接続されている。
【０１１５】
メモリ２４０２は、例えば、Read Only Memory（ＲＯＭ）、Random Access Memory（ＲＡＭ）、フラッシュメモリ等の半導体メモリであり、処理に用いられるプログラム及びデータを格納する。例えば、ＣＰＵ２４０１は、メモリ２４０２を利用してプログラムを実行することにより、端末１０１、インタフェース１０３、ロードバランサ１０４、及び経路探索装置１０５−１〜１０５−４の処理を行う。
【０１１６】
情報処理装置が経路探索装置１０５−１〜１０５−４として使用される場合は、メモリ２４０２は、図２の動作パラメータ格納部２０４としても使用でき、地図情報、交通情報、及びオープンリストを格納することもできる。
【０１１７】
入力装置２４０３は、例えば、キーボード、ポインティングデバイス等であり、ユーザ又はオペレータからの指示や情報の入力に用いられる。出力装置２４０４は、例えば、表示装置、プリンタ、スピーカ等であり、ユーザ又はオペレータへの問い合わせや処理結果の出力に用いられる。端末１０１の処理結果には、経路情報が示す経路を表示する画面も含まれる。
【０１１８】
外部記憶装置２４０５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。この外部記憶装置２４０５には、ハードディスクドライブも含まれる。情報処理装置は、外部記憶装置２４０５にプログラム及びデータを格納しておき、それらをメモリ２４０２にロードして使用することができる。
【０１１９】
情報処理装置が地図情報データベース１０６又は交通情報データベース１０７として使用される場合は、外部記憶装置２４０５は、地図情報又は交通情報を格納する。
【０１２０】
媒体駆動装置２４０６は、可搬型記録媒体２４０９を駆動し、その記録内容にアクセスする。可搬型記録媒体２４０９は、メモリデバイス、フレキシブルディスク、光ディスク、光磁気ディスク等である。この可搬型記録媒体２４０９には、Compact Disk Read Only Memory （ＣＤ−ＲＯＭ）、Digital Versatile Disk（ＤＶＤ）、Universal Serial Bus（ＵＳＢ）メモリ等も含まれる。ユーザ又はオペレータは、この可搬型記録媒体２４０９にプログラム及びデータを格納しておき、それらをメモリ２４０２にロードして使用することができる。
【０１２１】
このように、各種処理に用いられるプログラム及びデータを格納するコンピュータ読み取り可能な記録媒体には、メモリ２４０２、外部記憶装置２４０５、及び可搬型記録媒体２４０９のような、物理的な（非一時的な）記録媒体が含まれる。
【０１２２】
ネットワーク接続装置２４０７は、Local Area Network（ＬＡＮ）、インターネット等の通信ネットワークに接続され、通信に伴うデータ変換を行う通信インタフェースである。情報処理装置は、プログラム及びデータを外部の装置からネットワーク接続装置２４０７を介して受け取り、それらをメモリ２４０２にロードして使用することもできる。
【０１２３】
なお、情報処理装置が図２２のすべての構成要素を含む必要はなく、用途や条件に応じて一部の構成要素を省略することも可能である。例えば、情報処理装置がインタフェース１０３、ロードバランサ１０４、経路探索装置１０５−１〜１０５−４、地図情報データベース１０６、又は交通情報データベース１０７として使用される場合は、入力装置２４０３及び出力装置２４０４を省略してもよい。
【０１２４】
また、図１に示すインタフェース１０３、ロードバランサ１０４、経路探索装置１０５−１〜１０５−４、地図情報データベース１０６、又は交通情報データベース１０７は、それぞれが個別に、互いに通信可能に接続された情報処理装置上に実装されても構わないし、１台の情報処理装置に実装されても構わない。何台の情報処理装置により図１の端末１０１以外の各処理部を実装するかは、システムの運用者が適宜決定できる。
【０１２５】
以上、開示の実施形態とその利点について詳しく説明したが、当業者は、特許請求の範囲に明確に記載した本発明の範囲から逸脱することなく、様々な変更、追加、省略をすることができるであろう。
【符号の説明】
【０１２６】
１０１  端末
１０２  通信ネットワーク
１０３  インタフェース
１０４  ロードバランサ
１０５−１〜１０５−４  経路探索装置
１０６  地図情報データベース
１０７  交通情報データベース
２０１  決定部
２０２  探索部
２０３  生成部
２０４  動作パラメータ格納部
９０１、１２０１、２１２０、２２５１  出発地
９０２、１２０２、２２５２  目的地
９１１〜９１４、９３１、１００１〜１００５、１０２１、１２１１〜１２１５、１２３１、１３０１〜１３０４、１３２１、１９０１〜１９０３、２１０１、２２０１、２２０２  道路
９２１、９２２、１０１１、１０１２、１２２１、１３１１  部分経路
１１０２、１４０２  経路
１２４１、１３３１  インターチェンジ
１９１１、１９１２、１９２１〜１９２３、１９３１、１９３２、２１１１、２１１２、２２１１、２２１２、２２２１、２２２２  道路リンク
２１２１、２２３１、２２３２  ノード
２４０１  ＣＰＵ
２４０２  メモリ
２４０３  入力装置
２４０４  出力装置
２４０５  外部記憶装置
２４０６  媒体駆動装置
２４０７  ネットワーク接続装置
２４０８  バス
２４０９  可搬型記録媒体
【図１】
0005895630.tif 000002
【図２】
0005895630.tif 000003
【図３】
0005895630.tif 000004
【図４Ａ】
0005895630.tif 000005
【図４Ｂ】
0005895630.tif 000006
【図５】
0005895630.tif 000007
【図６】
0005895630.tif 000008
【図７】
0005895630.tif 000009
【図８】
0005895630.tif 000010
【図９】
0005895630.tif 000011
【図１０】
0005895630.tif 000012
【図１１】
0005895630.tif 000013
【図１５】
0005895630.tif 000014
【図１６】
0005895630.tif 000015
【図１７】
0005895630.tif 000016
【図１８】
0005895630.tif 000017
【図１９】
0005895630.tif 000018
【図２０】
0005895630.tif 000019
【図２１】
0005895630.tif 000020
【図２２】
0005895630.tif 000021
【図１２】
0005895630.tif 000022
【図１３】
0005895630.tif 000023
【図１４】
0005895630.tif 000024