最短経路探索方法
【課題】 幾何学的な構造を用いた前処理を行い、探索を速め、スケーラビリティとグラフの疎化に優れた最短経路探索方法を提供する。
【解決手段】 最短経路探索方法において、第１の外部記憶装置から地図情報を主記憶装置に読み込み、前記地図情報に基づきメッシュの形状、各メッシュを含む領域である外領域の設定を行い、前記メッシュの疎化ネットワークの構築を行い、第２の外部記憶装置に記憶し、始点と終点の位置情報を入力し、前記始点と前記終点の両者を外領域に含まないメッシュを集め、このメッシュの中で、他のものに含まれない極大なメッシュのみを残し、残りのメッシュを捨て、前記残った極大なメッシュの境界をまたぐ利用枝を探索し、この探索した利用枝で前記メッシュをつなぎ、前記第２の外部記憶装置に記憶された前記メッシュの疎化ネットワークを読み出して、求解用疎化ネットワークを構築し、この求解用疎化ネットワーク内での始点から終点への最短経路を求めて、この最短経路を出力する。
【解決手段】 最短経路探索方法において、第１の外部記憶装置から地図情報を主記憶装置に読み込み、前記地図情報に基づきメッシュの形状、各メッシュを含む領域である外領域の設定を行い、前記メッシュの疎化ネットワークの構築を行い、第２の外部記憶装置に記憶し、始点と終点の位置情報を入力し、前記始点と前記終点の両者を外領域に含まないメッシュを集め、このメッシュの中で、他のものに含まれない極大なメッシュのみを残し、残りのメッシュを捨て、前記残った極大なメッシュの境界をまたぐ利用枝を探索し、この探索した利用枝で前記メッシュをつなぎ、前記第２の外部記憶装置に記憶された前記メッシュの疎化ネットワークを読み出して、求解用疎化ネットワークを構築し、この求解用疎化ネットワーク内での始点から終点への最短経路を求めて、この最短経路を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、人・車による道路上の移動や電車の経路を求める、最短経路探索方法に関するものであり、特に、カーナビゲーションやＷｅｂでの最短経路探索方法に関するものである。
【背景技術】
【０００２】
従来、２点間を結ぶ最短の経路を求める問題は、古来より人間の行動に深く関わってきた最適化問題である。特に、人や車による道路上の移動や電車の経路を求める問題は、ネットワーク上の問題としてモデル化でき、ダイクストラ（Ｄｉｊｋｓｔｒａ）法を始めとする多くのアルゴリズムが提案されてきた。
【０００３】
近年情報技術（ＩＴ）の発達により、大規模な地図情報をコンパクトにコンピュータ上に格納することが可能となり、最短経路問題を解くソフトをつけた上で、ナビゲーションシステムという形で自動車に搭載できるようになってきた。
【０００４】
上記ダイクストラ法は、計算量理論の意味からするとほぼ最適なアルゴリズムである。しかし、現実問題に適用する場合には、遠い点を結ぶ最短経路を求めるときに、地図情報（地図データ）の多くの部分にアクセスする必要があり、現実的な時間で解くことができない。
【０００５】
この問題を解決するために、いくつかのアプローチが取られてきた。
【０００６】
一つは、最適性を犠牲にして、発見的な手法を導入する方法である。例えば、ある離れた地域間を移動する際には、ある種の決まったルートを通るという仮定をおき、途中の探索を省くというものである。また、道路を高速道路・主要道といった遠距離の移動に使う道からなるネットワークと、それ以外の道からなるネットワークに階層を分け、まず現在地・目的地から最寄りの主要道までの最短経路を求めた後に、主要道上での最短経路問題を解くという、階層化を行うアプローチもある。
【０００７】
他に、最適性を犠牲にしないアプローチもある。ダイクストラ法を始点終点両方から行い探索範囲を狭める方法、目的地までの距離の直線距離が短くなる方向を優先して探索するＡ* アルゴリズムなどである。
【０００８】
近年、地図情報（地図データ）にある種の前処理を行い、後で最短経路を求める場合に短時間で解けるようにする、というアプローチがとられ始めている。これには、計算機技術の進歩により、大規模な地図情報に対しても、ある程度複雑な前処理が現実的な時間内にできるようになってきたという理由もあると考えられる。この手法は、比較的成功を収めており、大規模な地図情報上でも短時間で最短経路を求めることに成功している。
【０００９】
前処理を行うアルゴリズムにもいくつかのバリエーションがある。
【００１０】
一つはビットベクトル法と呼ばれるもので、地図をいくつかのエリアに分割し、各頂点とエリアの組に対して、その頂点に接続する枝の中で、その頂点からエリア内の頂点への最短経路が使う利用枝を選び出しておく手法である。最短経路探索時には、各頂点から探索を行う際に、目的地を含むエリアに向かう最短経路が使用する利用枝の方向のみへ、探索の腕を伸ばすことで探索を省略する。直感的には、目的地に向かわない方向の枝への探索は全て省略されるため、探索の範囲を大幅に減らすことができる。しかし、前処理では基本的に全点間の最短経路問題を解かなければいけないため、高速化を行っても非常に長い時間がかかるという欠点がある。また、各枝について、エリアの数だけのビットが保存領域として必要となる。
【００１１】
もう一つはハイウェイ階層法と呼ばれるもので、遠距離の移動の中間で使われる利用枝のみからなるネットワークを構築しておき、遠い点を結ぶ最短経路を求める場合には、近距離移動用の枝を無視することで高速化を行う手法である。閾値ｋを用いて、遠距離の移動を２ｋ＋１本以上の枝を使う移動と定義し、最短経路が２ｋ＋１本以上の枝を含むような場合に、始点からも終点からもｋ歩以上離れている最短経路上の枝を遠距離移動用の枝と定義する。逆にいえば、遠距離移動用の枝とは、最短経路がその枝を通過するような、最短経路上でｋ歩以上離れた始点終点の組が存在するような枝のことである。遠距離移動用の枝のみを集めたハイウェイネットワークを構築し、始点終点からｋ歩のところまでは通常のネットワークを、それ以後はハイウェイネットワークを移動することで、高速化を行う。現実のネットワークでは遠距離移動用の枝の数はそれほど多くないため、階層的・再帰的にハイウェイネットワークを構築することで探索すべき枝の数を少なくすることができる。この手法の利点は、各点から２ｋ＋１歩以内にある点に対してのみ最短経路を求めることで前処理が終わることであり、それゆえに前処理時間が他の手法と比べて短いことである。
【００１２】
また、この分野の先行技術としては、以下に示すような提案がなされている。
【００１３】
（１）全ての道路を複数の不定形の地域に分割して記憶すると共に、地域間の接続関係も別に記憶しておき、出発地と目的地が属する二つの地域間を結ぶ地域を選定した後に、選定した地域に属する道路について経路探索を行う経路探索方法（下記特許文献１参照）。
【００１４】
（２）高速道路、国道及び主要地方道といったように、道路を複数の階層に分類し、各階層は交差点情報、道路情報を備えており、それに基づいて経路探索を行う経路探索方法（下記特許文献２参照）。
【００１５】
（３）道路地図情報を、主要道路を対象とする主要道路レイヤと、主要道路と主要でない道路とを共に対象とする一般道路レイヤとに分け、かつ、複数のメッシュに区分して記憶すると共に、各メッシュの道路の接続情報も記憶するようにした経路計算方法（下記特許文献３参照）。
【特許文献１】特許第３２４４５１７号公報
【特許文献２】特許第３１８６７９４号公報
【特許文献３】特許第３０８５０５４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、上記した経路探索方法では、膨大な地図情報を必要とするので、処理時間が長くなり、経路探索時間が長くなるといった問題があった。
【００１７】
本発明は、上記問題点を除去し、幾何学的な構造を用いた前処理を行い、探索を速め、スケーラビリティとグラフの疎化に優れた最短経路探索方法を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明は、上記目的を達成するために、
〔１〕最短経路探索方法において、第１の外部記憶装置から地図情報を主記憶装置に読み込み、前記地図情報に基づきメッシュの形状、各メッシュを含む領域である外領域の設定を行い、前記メッシュの疎化ネットワークの構築を行い、第２の外部記憶装置に記憶し、始点と終点の位置情報を入力し、前記始点と前記終点の両者を外領域に含まないメッシュを集め、このメッシュの中で、他のものに含まれない極大なメッシュのみを残し、残りのメッシュを捨て、前記残った極大なメッシュの境界をまたぐ利用枝を探索し、この探索した利用枝で前記メッシュをつなぎ、前記第２の外部記憶装置に記憶された前記メッシュの疎化ネットワークを読み出して、求解用疎化ネットワークを構築し、この求解用疎化ネットワーク内での始点から終点への最短経路を求めて、該最短経路を出力することを特徴とする。
【００１９】
〔２〕上記〔１〕記載の最短経路探索方法において、前記メッシュの疎化ネットワークの構築は、前記メッシュＭ内にある交差点に接続する道路を全て探索して、前記メッシュに関するネットワークを構築し、前記メッシュからある程度の距離にある領域を外領域とし、該外領域の境界上にある道路を全て探索し、この探索した道路のそれぞれに対して、接続する交差点を１つ選定し、この選定された交差点の各ペアについて、その点間の最短経路を求め、前記メッシュに関するネットワークで、前記最短経路のいずれにも含まれないものを消去することを特徴とする。
【００２０】
〔３〕上記〔１〕記載の最短経路探索方法において、前記始点の周辺及び前記終点の周辺に対しても外行き疎化ネットワークと内行き疎化ネットワークを用いることを特徴とする。
【発明の効果】
【００２１】
本発明によれば、次のような効果を奏することができる。
【００２２】
地図情報に基づいてメッシュの大きさを設定し、各最小メッシュを含む大きな外領域を設定し、その外領域の外側の２点を結ぶ最短経路に含まれるメッシュの枝を利用枝とし、この利用枝を全てのメッシュについて求める。２点間の最短経路を求めるときは、２点の両方から遠い部分では利用枝のみを探索することで高速化を行う。また、複数の階層的な大きさのメッシュに対して、利用枝を用意し、始点と終点の両方から遠い領域ほど、より大きなメッシュを使えるようにする。利用枝が作るネットワークは、次数２の頂点を多く含み、このような頂点を縮約すると、メッシュの大きさによらず、利用枝の本数は同程度となるので、階層的にメッシュを用意することにより、始点と終点間が遠くてもネットワークの枝数は多くならずに最短経路を検索することができる。
【発明を実施するための最良の形態】
【００２３】
本発明の最短経路探索方法は、第１の外部記憶装置から地図情報を主記憶装置に読み込み、前記地図情報に基づきメッシュの形状、該メッシュを含む領域である外領域の設定を行い、前記メッシュの疎化ネットワークの構築を行い、第２の外部記憶装置に記憶し、始点と終点の位置情報を入力し、前記始点と前記終点の両者を外領域に含まないメッシュを集め、このメッシュの中で、他のものに含まれない極大なメッシュのみを残し、残りのメッシュを捨て、前記残った極大なメッシュの境界をまたぐ利用枝を探索し、この探索した利用枝で前記メッシュをつなぎ、前記第２の外部記憶装置に記憶された前記メッシュの疎化ネットワークを読み出して、求解用疎化ネットワークを構築し、この求解用疎化ネットワーク内での始点から終点への最短経路を求めて、該最短経路を出力する。
【実施例】
【００２４】
以下、本発明の実施の形態について詳細に説明する。
【００２５】
本発明の階層メッシュ疎化法（Ｌｅｖｅｌ−ｗｉｓｅ Ｍｅｓｈ Ｓｐａｒｓｉｆｉｃａｔｉｏｎ）は、従来技術で説明した従来の手法とは異なる新しい手法である。従来の手法を使って言い表すならば、ハイウェイ階層法を幾何学的な構造の上に落としたものだと言える。
【００２６】
まず、平面上の地図情報に対し、それをある大きさのメッシュに分割する。そして、そのメッシュを含む一回り大きな外領域を考え、外領域の外側の２点を結ぶ最短経路に含まれるメッシュの枝を、利用枝と定義する。外領域が十分大きければ、メッシュの中で利用枝となる枝の数は少なくなる。この利用枝を全てのメッシュに対して求め、２点間の最短経路を求めるときには、２点両方から遠い部分では利用枝のみを探索することで高速化を行う。さらに、複数の大きさのメッシュに対して利用枝ネットワークを作っておくことで、始点と終点の両方から遠い領域ほど、より大きなメッシュを使えるようにする。実験的には、利用枝が作るネットワークは、次数２の頂点を多く含み、このような頂点を縮約した後では、メッシュの大きさによらず利用枝の本数は同程度となる。そのため、階層的にメッシュを用意することで、地図の規模が大きくなっても、始点と終点の両方から遠い部分のネットワークはそれほど枝数が大きくならず、地図の大きさに対して安定的なアルゴリズムが実現できる。
【００２７】
従来のハイウェイ階層法では、このような次数２の頂点を縮約することによる効率化の恩恵にあずかることは難しい。なぜならハイウェイ階層法では、階層間の接続が全ての場所で行われているため、ハイウェイネットワーク上で次数２の頂点を消去してしまうと、その点に接続していた通常のネットワークの枝からハイウェイネットワークへの移動ができなくなってしまうからである。
【００２８】
その反面、本発明の階層メッシュ疎化法では、階層の違うネットワークの接続部分はメッシュの縁の部分だけであるので、内側に関しては頂点の縮約を行える。これは階層メッシュ疎化法の大きな利点である。実験の結果、階層メッシュ疎化法を用いて構築したネットワークは、もとのネットワークに比べてはるかに少ない数の枝しか含まないことがわかった。しかも、ほぼすべての枝は始点と終点付近に集中しており、これは他の手法でも網羅的に探索が行われる領域である。その結果、通常のダイクストラ法を用いただけで、既存の最速のアルゴリズムとほぼ同等の性能を出すことに成功した。そのうえ、本発明の階層メッシュ疎化法は、ビットベクトル法やＡ* アルゴリズムとも併用できるため、これらの手法を用いることでより一層の高速化が行える。
【００２９】
以下、階層メッシュ疎化法について説明する。
【００３０】
まず、〔１〕で用語の定義を行い、〔２〕で階層メッシュ疎化法の基礎となる疎化ネットワークとその性質を説明する。また、〔３〕で疎化ネットワークを始点終点に近いエリアに適用する外行き・内行きの疎化ネットワークの説明を行い、〔４〕では前処理を高速に行う手法を説明する。
〔１〕定義
Ｇ＝（Ｖ, Ａ）を頂点集合Ｖ、枝集合Ａからなる有向ネットワークとし、ｄ：Ａ→Ｒを枝の距離関数とする。特に本発明では、地図情報を仮定するため、距離関数は正、つまり、ｄ：Ａ→Ｒ+ であるとする。頂点集合Ｖの各点は２次元ユークリッド空間上に置かれているものとし、頂点ｖのｘ座標、ｙ座標をそれぞれｘ（ｖ）, ｙ（ｖ）と表記する。一般性を失うことなく、あるＭに対して０≦ｘ（ｖ）, ｙ（ｖ）＜Ｍが成り立つとし、０≦ｘ, ｙ＜Ｍである領域を地図領域と呼ぶ。また、始点ｖと終点ｕに対して、〔ｖ，（ｖ，ｗ１），ｗ１，（ｗ１，ｗ２），…，ｗｋ，（ｗｋ，ｕ），ｕ）〕となっている頂点と枝の列をパスと呼ぶ。パスは、頂点の列あるいは枝の列から一意的に導かれるため、隣接する頂点の列、あるいは隣接する枝の列もパスと呼ぶ。ｖ, ｕはこのパスの端点と呼ばれる。パスの長さは、パスに含まれる枝の距離和で定義する。ｕ, ｖを結ぶパスの中で最も長さの短いものをｕ, ｖを結ぶ最短経路と呼び、その長さをｄu （ｖ）と表記する。最短経路は唯一的であるとは限らないが、ここでは摂動を加えることで唯一的になると仮定しておく。頂点ｒに対して、頂点ｒを根とする木で、頂点ｒから木の各頂点ｕへのパスが、頂点ｒから木の各頂点ｕへの最短経路となっているようなものを頂点ｒの最短経路木と呼ぶ。通常、最短経路木は全ての頂点を含む全張木で定義するが、ここでは、一部の頂点のみを含むものもよしとする。頂点集合Ｕと始点ｒに対して、頂点集合Ｕの頂点を全て含むｒの最短経路木の中で極小なものをＴr （Ｕ）と表記する。Ｔr （Ｕ）は、頂点ｒから頂点集合Ｕの各頂点への最短経路の和集合である。頂点ｒと枝ｅ＝（ｕ, ｖ）に対して、ｄr （ｖ）−ｄr （ｕ）をｅの縮退コストと呼び、ｃr （ｅ）で定義する。このｃr （ｅ）は負にはならず、ｃr （ｅ）が０となるとき、またそのときに限り枝ｅは最短経路木に含まれる。
【００３１】
メッシュ粒度ｋに対して、ｋレベルのメッシュを、ある整数０≦ｉ，ｊ≦ｋに対してｉＭ／ｋ≦ｘ＜（ｉ＋１）Ｍ／ｋ，ｊＭ／ｋ≦ｙ＜（ｊ＋１）Ｍ／ｋとなるような領域で定義し、ｉＭ／ｋ，（ｉ＋１）Ｍ／ｋ，ｊＭ／ｋ，（ｊ＋１）Ｍ／ｋをこのメッシュの左、右、上、下と呼ぶ。地図領域は、ｋレベルのメッシュｋ2 個によって分割される。連結な領域Ｓに対して、端点の１つがＳに含まれる枝をＳに含まれる枝と呼び、Ｅ（Ｓ）と表記する。また、端点の１つがＳに含まれ、もう１つがＳに含まれないような枝を、Ｓの境界枝と呼び、その集合をＣ（Ｓ）と表記する。このＣ（Ｓ）の枝の端点でＳに含まれない点を、Ｓの境界頂点と呼び、その集合をＢ（Ｓ）と表記する。
【００３２】
〔２〕階層メッシュ疎化法
ここで、階層メッシュ疎化法の基礎となる疎化ネットワークとその性質について説明する。
【００３３】
ｋレベルのメッシュｍに対して、メッシュｍの外領域Ｓを、メッシュｍを完全に含むような連結な領域で定義する。このとき、メッシュｍの外領域Ｓの境界頂点ｒに対してＴr 〔Ｂ（Ｓ）〕の枝でＥ（ｍ）に含まれるものを、全ての境界頂点ｒに対して求めて和をとった枝集合をＳＥ（ｍ）と表記する。さらに、ＳＥ（ｍ）の枝が導くグラフＲに対して以下の縮約操作を行って得られるグラフを、ｍの疎化ネットワークと呼び、ＳＧ（ｍ）と表記する。疎化ネットワークはメッシュｍの外領域Ｓにより変化することを注意しておく。
アルゴリズム縮約操作（領域Ｒ）：
（１）グラフＲに次数２の頂点ｖが含まれるならば、頂点ｖに隣接する頂点ｕ，ｗに対して、ｕ，ｗ間に枝がなければ枝（ｕ，ｗ）で結び、そのコストをｄ（ｕ，ｖ）＋ｄ（ｖ，ｗ）とし、枝（ｕ，ｗ）が存在するならば、そのコストをｄ（ｕ，ｗ）とｄ（ｕ，ｖ）＋ｄ（ｖ，ｗ）の小さい方にする。そして、頂点ｖと枝（ｕ，ｖ），（ｖ，ｗ）を除去する。
【００３４】
（２）グラフＲに次数１の頂点が含まれ、それに隣接する頂点がＢ（ｍ）に含まれないならば、その次数１の頂点と接続する枝を除去する。
【００３５】
（３）上記（１），（２）の条件が成り立たなくなるまで、上記（１），（２）を繰り返す。
【００３６】
この操作は、Ｏ（｜ＳＥ（ｍ）｜）時間で実行できることを注意しておく。
【００３７】
Ｍ上に頂点集合を持つネットワークＧ＝（Ｖ，Ａ）と、Ｇから得られたｍの疎化ネットワークＳＧ（ｍ）＝（Ｖ’⊆Ｖ，Ａ’）に対して、Ｇからｍ上に端点を持つ枝を取り除き、Ａ’を枝集合に加えてできるネットワークＧ’をＧに埋め込んだネットワークと呼ぶ。
【００３８】
疎化ネットワークに対しては、以下の補助定理１が成り立つ。
【００３９】
補助定理１：
ｕ，ｖをｍの外領域に含まれないＧの頂点とする。このとき、Ｇでの頂点ｕ，ｖ間の最短経路長とＳＧ（ｍ）をＧに埋め込んだネットワークでの頂点ｕ，ｖ間の最短経路長は等しい。特にＧでの最短経路は、埋め込んだネットワークでの最短経路の、縮約された枝を元に戻すことにより得られる。
【００４０】
ここで、メッシュｍの外領域を、メッシュｍを中心とし、ｘ径がｈ倍、ｙ径がｈ倍であるような四角い領域とする。つまり、メッシュｍがｉＭ／ｋ≦ｘ＜（ｉ＋１）Ｍ／ｋ，ｊＭ／ｋ≦ｙ＜（ｊ＋１）Ｍ／ｋとなる領域であれば、外領域は（ｉ−（ｈ−１）／２）Ｍ／ｋ≦ｘ＜（ｉ＋（ｈ＋１）／２）Ｍ／ｋ，（ｊ−（ｈ−１）／２）Ｍ／ｋ≦ｙ＜（ｊ＋（ｈ＋１）／２）Ｍ／ｋであるようなｘ、ｙからなる領域となる。このとき、ｈを外領域の倍率と呼ぶ。
【００４１】
今、１，２，４，８，…，２g レベルのメッシュの集合をＺとし、Ｚの各メッシュの外領域の倍率をｈとする。地図領域上のネットワークＧの２点ｕ，ｖに対して、Ｚのメッシュの中で、ｕ，ｖ両点が外領域の外側にあるメッシュをアクティブなメッシュと呼び、アクティブなメッシュの中で、他のＺのアクティブなメッシュに含まれないものを極大アクティブメッシュと呼ぶ。レベルが２のべき乗で与えられていることから、極大なアクティブメッシュは互いに共通部分を持たず、ｕ，ｖの周り以外の領域を完全に覆う。今、Ｇに対して、各極大アクティブメッシュの疎化ネットワークを逐次的に埋め込んで得られるネットワークを、ｕ，ｖの疎化ネットワークと呼ぶ。このとき、補助定理１より以下の定理が成り立つ。
【００４２】
その定理は、「任意のｇ、ｈと地図領域上に定義されたネットワークＧの任意の２点ｕ，ｖに対して、Ｇでのｕ，ｖ間の最短経路長とｕ，ｖの疎化ネットワークでのｕ，ｖ間の最短経路長は等しい。特にネットワークＧでの最短経路は、疎化ネットワークでの最短経路の、縮約された枝を元に戻すことにより得られる。」ということである。
【００４３】
上記定理より、各メッシュに対して疎化ネットワークを構築する、という前処置を行っておけば、ｕ，ｖ間の最短経路を求める際に、まずｕ，ｖの疎化ネットワークを構築し、そのうえで最短経路を解く、というアプローチが行える。
【００４４】
通常、遠距離を移動するために使う枝は限られており、縮約操作によってネットワークを縮小できると予想される。この効果については、後述の説明を参照されたいが、基本的に大きなメッシュほど疎化ネットワークが小さくなる傾向がある。極大アクティブメッシュの数は、ネットワークの大きさに対してあまり大きくならない。例えば、ｈ＝３とした場合、最大でも２７個である。そのため、たとえ地図領域が２倍になり、ｇを一つ大きくして、最小のメッシュの大きさを揃えたとしても、２つの頂点に対する極大アクティブメッシュの総数の最大値は、たかだか２７しか大きくならないのである。
【００４５】
疎化ネットワークが疎であることは、メモリ使用量の少なさにも貢献する。メッシュの数は、レベルの減少に従って指数的に少なくなるので、レベル毎の疎化ネットワーク保存にかかるメモリも指数的に小さくなる。そのため、全ての疎化ネットワークをメモリに保存しても、元のネットワークの定数倍程度のメモリしか使用しない。
【００４６】
また、ネットワークが変化した時に、前処理を行うタイプのアルゴリズムは前処理をし直さなければならないが、階層メッシュ疎化法はその時間が少なくてすむという長所がある。ある枝が追加・削除されたとき、あるいは枝の距離が変わったときに、作り直さなければいけない疎化ネットワークは、外領域がその枝を含むようなメッシュだけである。これは、例えば外領域の倍率ｈが３であるとき、各レベルで９個までである。
〔３〕外行き疎化ネットワーク
上記により定義した疎化ネットワークでは、始点と終点の周りに関してはネットワークの疎化が行われなかった。これは疎化ネットワークの発想の基本が、遠距離移動を行う際の中間部分の探索を高速化しようという発想に基づいているからで、ある意味で当然である。しかし、似たようなアイデアを用いると、始点終点の周りに関しても、ある種の疎なネットワークを構築することができる。ここでは、疎化ネットワークを始点や終点に近いエリアに適用する外行き及び内行きの疎化ネットワークについて説明する。
【００４７】
ｋレベルのメッシュｍに対して、メッシュｍに含まれる各頂点ｒからメッシュｍの外領域の境界頂点Ｂ（Ｓ）への最短経路木Ｔr 〔Ｂ（Ｓ）〕の枝を集めて得られるネットワークを考える。メッシュｍに含まれる任意の頂点ｒから、メッシュｍの外領域Ｓに含まれない頂点への最短経路のｍに含まれる部分は、必ずこのネットワークに含まれる。そこで、このネットワークに上述した縮約操作を行って得られるネットワークをｍの外行き疎化ネットワークと定義すれば、以下の補助定理２が成り立つ。
【００４８】
補助定理２：
ｕをメッシュｍの外領域に含まれない頂点、ｖをメッシュｍに含まれる頂点とする。このとき、Ｇでのｕ，ｖ間の最短経路長と、メッシュｍの外行き疎化ネットワークをＧに埋め込んだネットワークでのｕ，ｖ間の最短経路長は等しい。
【００４９】
外行き疎化ネットワークは、メッシュの中の全ての端点を始点とする最短経路木の和集合であるので、あまり疎になるとは考えられない。メッシュｍの内部での袋小路的な構造、あるいは通過速度の遅い道からなる部分に関しては、そこから出て行く枝が外行き疎化ネットワークに含まれることはあっても、そこに入る枝が含まれることは考えにくい。そうなると、メッシュｍに含まれる頂点ｒに対して、メッシュｍの中で枝を順向きにたどって頂点ｒから到達可能な頂点・枝は、非常に少ないと考えられる。
【００５０】
同様に、終点に対しても内行き疎化ネットワークを定義することができ、以下の補助定理３が成り立つ。
【００５１】
補助定理３：
ｕをメッシュｍの外領域に含まれない頂点、ｖをメッシュｍに含まれる頂点とする。このとき、Ｇでのｕ，ｖ間の最短経路長と、メッシュｍの内行き疎化ネットワークをＧに埋め込んだネットワークでのｕ，ｖ間の最短経路長は等しい。
【００５２】
外行き・内行き疎化ネットワークは、通常の疎化ネットワークと異なりあまり疎にはならない。そのため、全てのレベルについて外行き疎化ネットワークを求めメモリに保存すると、メモリ使用量が元のネットワークが使用するメモリに対して、レベル数ｇの値だけ倍化されてしまう。そのため実用上は、ある程度以上大きな定数個のレベルに対してのみ、外行き・内行き疎化ネットワークを求める、という手法が望ましい。
〔４〕疎化ネットワークの再帰的な利用による前処理の高速化
疎化ネットワークを求めるためには、基本的に外領域の境界頂点の全対に対して最短経路を求める必要がある。これは時間のかかる作業である。メッシュが大きくなるにつれ、メッシュの数自体は減るが、ネットワーク規模が大きくなるため、計算時間はそれほど短縮されず、逆に増加する可能性もある。ここでは、疎化ネットワークを求める高速アルゴリズムについて説明する。
【００５３】
高速化手法の一つ目は、疎化ネットワークを求める際に疎化ネットワークを用いるという手法である。これは、疎化ネットワークをレベルの大きなメッシュから順に求めていき、あるレベルのメッシュの疎化ネットワークを求める際に、それより大きなレベルの疎化ネットワークを用いて最短経路を求めるというものである。メッシュｍとその外領域Ｓに対して、Ｂ（Ｓ）のどの頂点も外領域に含まれないメッシュをアクティブなメッシュと呼び、メッシュｍ以外の他のアクティブなメッシュに含まれないメッシュを極大アクティブメッシュと呼ぶ。前述での議論同様、極大アクティブメッシュは非交差的であり、外領域Ｓ上のネットワークに全ての極大アクティブメッシュを逐次的に埋め込んだネットワークでは、最短経路の長さは保存され、メッシュｍの疎化ネットワークを求める際に利用できるのである。これにより、最短経路問題を解く時間は大幅に短くなる。同様に、外行き疎化ネットワーク、内行き疎化ネットワークを用いることもできる。まず、外領域Ｓの境界頂点を含むメッシュに対し、その中の１つメッシュｍ’の外行き疎化ネットワークを埋め込み、メッシュｍ’が外領域Ｓの外側にあるメッシュの内行き疎化ネットワークを埋め込む。このネットワークでは、メッシュｍ’内の頂点ｒを始点とする最短経路の長さが保存されるため、頂点ｒの最短経路木Ｔr 〔Ｂ（Ｓ）〕を求める際に利用できる。
【００５４】
このように本発明によれば、幾何学的な構造を用いた前処理を行うことで最短経路問題を効率的に解く、階層メッシュ疎化法を提供することができる。
【００５５】
本発明の階層メッシュ疎化法の基本的なアイデアは、各メッシュ内で遠距離の移動の中間で使われる枝のみを選別し、縮約操作でネットワークを疎化・単純化するものである。同時に、始点の周辺・終点の周辺に対しても外行き疎化ネットワークと内行き疎化ネットワークを提供するようにした。両者ともに、計算実験の結果、ネットワークのサイズの縮小に大きく貢献することがわかった。また、前処理に再帰的に階層メッシュ疎化法を用いることで高速化を行う方法を提供することができる。
【００５６】
図１は本発明の最短経路探索方法を実施する全体システムの構成図である。
【００５７】
この図において、１は最短経路演算手段であり、この最短経路演算手段１はメッシュ設定手段２と、メッシュ疎化ネットワーク構築手段３と、始点と終点の設定手段４と、極大なメッシュの設定手段５と、その境界をまたぐ利用枝を探索し、その探索した利用枝でメッシュをつなぐ手段６と、メッシュ疎化ネットワーク構築手段３からのデータを利用した求解用疎化ネットワーク構築手段７と、最短経路探索手段８とを備えている。また、１１は最短経路演算手段１に取り込まれる地図情報、１２は最短経路演算手段１に情報を入力する入力手段、１３は最短経路演算手段１からの最短経路出力が提供される出力手段（表示・記憶・プリントアウトなどの報知手段）である。
【００５８】
まず、階層メッシュ疎化法を概観する。
【００５９】
図２は本発明の最短経路探索の基本的説明図（その１）である。
【００６０】
この図において、２１はメッシュ、２２はその外領域、２３はその外領域の境界、２４は始点、２５は終点であり、ここでは、外領域２２の外側に始点２４と終点２５がある。ここで、始点２４と終点２５の最短経路を求める場合には、メッシュ２１内の疎化ネットワークは、外領域２２の外側の任意の２点を結ぶ最短経路の枝を含んでいるため、疎化ネットワークの線２６のみを使っても最短経路を求めることができる。つまり、最短経路計算で使われる情報（データ）が少なくなる。
【００６１】
図３は本発明の最短経路探索の基本的説明図（その２）である。
【００６２】
この図に示すように、位置をずらしたメッシュ２１′の疎化ネットワークも合わせて使用すると、最短経路計算で使われる情報（データ）がさらに少なくなる。ここで、２２′はメッシュ２１′の外領域、２３′は外領域２２′の境界である。また、２４′は始点、２５′は終点である。
【００６３】
図４は本発明の最短経路探索の基本的説明図（その３）であり、上記した個別のものがまとめられている。
【００６４】
いろいろな大きさのメッシュ３１，３２で、遠いところ同士の最短経路で使われる道を覚え、始点３３と終点３４が指定されたら、なるべく道数の少ないネットワークを構成し（大きいメッシュ３２を優先的に使う）、最短経路を計算する。
【００６５】
図５は本発明の始点と終点が与えられたときの極大なメッシュの例を示す図である。
【００６６】
この図において、始点４２と終点４３が与えられたときの極大なメッシュ４１が示されている。
【００６７】
Ｗｅｓｔ Ｖｉｒｇｉｎｉａ州の道路ネットワークに対する適用例を用いて説明する。
【００６８】
図６はＷｅｓｔ Ｖｉｒｇｉｎｉａの地図情報（データ）を示す図であり、３００１４６ノード、６５７７１６枝を有している。Ｄｉｊｋｓｔｒａ法とｂｉｎａｒｙ ｈｅａｐ法ではデータをメモリにした格納後、計算に約１秒かかる。なお、Ｄｉｊｋｓｔｒａ法の計算時間は枝数にほぼ比例する。
【００６９】
図７は図６における階層メッシュ疎化法で用意するネットワークの一部を示す図である。
【００７０】
図８は図６における始点と終点が指定された場合の極大なメッシュの疎化ネットワークを組み合わせてできるネットワークとその上での最短経路探索例を示す図（その１）である。
【００７１】
この図８において、５１が最短経路（白線）であり、枝の数は約１００００（元のグラフの約１／６０）、計算時間は約１５ミリ秒であり、約６０倍の高速化を図ることができる。
【００７２】
図９は図６における始点と終点が指定された場合の最短経路探索例を示す図（その２）である。
【００７３】
この図において、５２が最短経路（白線）である。
【００７４】
図８と対比すると明らかなように、指定される始点と終点が異なれば、計算に使われるネットワークも異なることが分かる。
【００７５】
以下、より具体的に説明する。
【００７６】
図１０は本発明の疎化ネットワーク構築システムの構成図である。
【００７７】
この図において、６１は第１の外部記憶装置であり、メモリドライブ６１Ａに地図情報記憶装置６１Ｂが装着されることにより地図情報を主記憶装置６２に読み込むことができる。この主記憶装置６２に読み込まれた情報を用いて領域設定手段６３で領域が設定される。その領域設定が行われるとメッシュ設定手段６４でメッシュが設定される。各メッシュに基づいて疎化ネットワーク構築手段６５によって疎化ネットワークが構築される。そこで、構築されたメッシュの疎化ネットワークを第２の外部記憶装置６６に記憶する。
【００７８】
図１１は本発明のデータ縮小法である疎化ネットワーク作成フローチャート、図１２は図１１のステップＳ４のサブフローチャートを示す図である。
【００７９】
図１１に示すように、データ縮小法のフローチャートは、以下のようである。
（１）まず、第１の外部記憶装置６１から地図情報を主記憶装置６２に読み込む（ステップＳ１）。
（２）次に、その地図情報に基づいて領域設定を行う（ステップＳ２）。
（３）次に、領域設定に基づいて各メッシュの設定を行う（ステップＳ３）。
（４）次に、各メッシュの疎化ネットワークの構築を行う（ステップＳ４）。
（５）最後に、そのメッシュの疎化ネットワークを第２の外部記憶装置６６に記憶する（ステップＳ５）。
【００８０】
上記（３）においては、不要に細かすぎるメッシュまで生成しないよう決定する。
【００８１】
ここで、上記（４）の各メッシュの疎化ネットワークにおいては、図１２に示すように、各レベルの各メッシュに対して以下の操作を行い、メッシュの疎化ネットワークを構築する。
【００８２】
（４−１）メッシュ内にある交差点に接続する道路を全て探索して、メッシュに関するネットワークを構築する（ステップＳ１１）。
【００８３】
（４−２）メッシュからある程度の距離にある領域を外領域とし、その境界上にある道路を全て探索する（ステップＳ１２）。
【００８４】
（４−３）探索した全ての道路それぞれに対して、接続する交差点を１つ選定する（ステップＳ１３）。
【００８５】
（４−４）選定された交差点の各ペアについて、その点間の最短経路を求める（ステップＳ１４）。
【００８６】
（４−５）メッシュに関するネットワークで、上記（４−４）で得られた最短経路いずれにも含まれないものを消去する（ステップＳ１５）。
【００８７】
なお、上記（４）においては、地図をある方向にスキャンしながら順にメッシュを調べることで、メッシュに関するネットワークの構築にかかるための時間を減らしても良い。
【００８８】
上記（４−３）においては、地図をスキャンし、各交差点を得てもよい。
【００８９】
また、上記（４−４）においては、外領域上に制限した地図情報上において、各点から必要な点への１対多最短経路や、全点間の最短経路を求めることで、各交差点ペアの最短経路を求めても良い。
【００９０】
上記（５）においては、上記（４−５）にて各疎化ネットワークを構築するごとに第２の外部記憶装置６６に書き込むことで、主記憶装置６２の節約を行っても良い。
【００９１】
図１３は地図情報から構築した道路ネットワークデータと、メッシュ（実線の四角）とそのメッシュの外領域（破線の四角）を示す図である。
【００９２】
以下、アルゴリズムの動作を具体的に説明する。
【００９３】
上記（４−１）で構築されたネットワークは、例えば、図１３のような、交差点を頂点とし、交差点を接続する道路を枝とするようなネットワークとなり、各枝に、その道路の区間距離、あるいはその道路を通過するのにかかる所要時間のデータがある。
【００９４】
上記（４−２）で探索する道は、図１３の破線の四角と交わりを持つ道（ネットワークの枝）である。
【００９５】
上記（４−３）で選定する交差点は、例えば、図１３に示される黒丸で示したものになる。
【００９６】
上記（４−４）では、図１３に示される黒丸で示した交差点の全てのペアについて、両者を結ぶ最短経路を求める。例えば、図１３では、黒丸ａから残りの黒丸ｂ，ｃ，…，ｈへの最短経路の例を、図１４では、黒丸ｇから残りの黒丸ａ，ｂ，…，ｈへの最短経路の例を示した。枝の距離と図中の枝を示す線分の距離は対応しないため、見かけ上最短である経路が選定されていないことに留意しておく。
【００９７】
上記（４−５）では、上記（４−４）で得られた最短経路全てを重ね合わせたネットワークを求め、メッシュに含まれる部分のみを取り出す。上記の例では、図１５のようになる。
【００９８】
図１５はａ，ｂ，…，ｈの全対間の最短経路を重ね合わせた図である。
【００９９】
この中の、実線の四角内のネットワークが、対応するメッシュの疎化ネットワークになる。
【０１００】
メッシュの大きさ・形状の決定は、例えば以下のように行う。
【０１０１】
まず、レベル０のメッシュを地図の領域全てとし、レベル１のメッシュを、レベル０のメッシュを４分割して得られるものとする。以下、レベルｋのメッシュは、レベルｋ−１のメッシュを４分割して得るものとする。各レベルのメッシュは、地図領域全体を分割したものになっている。
【０１０２】
メッシュＭの外領域は、たとえば、Ｍに隣接するメッシュを全て集めて、Ｍを包含する大きな四角い領域を作ることで作成する。
【０１０３】
実際に２点ａ，ｂ間の最短経路を求める際には、疎化ネットワークを組合せて、最短経路求解用のネットワークを構築する。２点ａ，ｂの両点を外領域の外側とするようなメッシュを集め、その中で極大なもの、つまり、他の、そのようなメッシュに含まれないもののみを集める。図１６にその例を示した。
【０１０４】
図１６はａ，ｂ点間の最短経路を求めるためのネットワークを示す図である。
【０１０５】
図１６に示される四角は、２点ａ，ｂを含むもの以外が上記で述べたメッシュに対応し、それらは、外領域に２点ａ，ｂを含まない。
【０１０６】
最短経路を求める際には、これらのメッシュのネットワークを接続して、最短経路求解用疎化ネットワークを構築し、最短経路アルゴリズムを実行する。
【０１０７】
以下に、最短経路を求める際に構築する疎化ネットワークの構築方法を、図１７を参照しながら説明する。
【０１０８】
（１）始点（現在地）と終点（目的地）の位置情報を入力する（ステップＳ２１）。これは、図１６に示した２点ａ，ｂを入力することに対応する。
【０１０９】
（２）始点（現在地）と終点（目的地）の両者を外領域に含まないメッシュを集める（ステップＳ２２）。これは、図１６に示される２点ａ，ｂを含まない四角、およびそれらに含まれる四角を集めることに相当する。
【０１１０】
（３）上記（２）で集めたメッシュの中で、他のものに含まれない極大なもののみを残し、残りを捨てる（ステップＳ２３）。図１６では、この作業は、上記（２）で集めたメッシュの中で極大なもの、つまり、図１６の四角い領域で２点ａ，ｂを含まないものの中で、そのような他のメッシュに含まれないものを集めることに等しい。
【０１１１】
（４）残ったメッシュの境界をまたぐ枝を調べ上げる（ステップＳ２４）。これは、図１６でのメッシュ、および２点ａ，ｂを含む四角い領域をつなげるために使う枝を調べ上げている。
【０１１２】
（５）探索した枝でメッシュをつなぎ、求解用疎化ネットワークを構築する（ステップＳ２５）。
【０１１３】
（６）求解用疎化ネットワーク内での始点（現在地）から終点（目的地）への最短経路を求める（ステップＳ２６）。
【０１１４】
（７）求めた最短経路を出力する（ステップＳ２７）。
【０１１５】
本発明は、地図情報を有するカーナビゲーションやＷｅｂでの最短経路探索方法に限られるものではなく、地図情報を有する鉄道経路や航路での最短経路探索方法にも適用することができる。
【０１１６】
なお、本発明は上記実施例に限定されるものではなく、本発明の趣旨に基づいて種々の変形が可能であり、これらを本発明の範囲から排除するものではない。
【産業上の利用可能性】
【０１１７】
本発明の最短経路探索方法は、地図情報を有するカーナビゲーションやＷｅｂでの最短経路探索方法として利用可能である。
【図面の簡単な説明】
【０１１８】
【図１】本発明の最短経路探索方法を実施する全体システムの構成図である。
【図２】本発明の最短経路探索の基本的説明図（その１）である。
【図３】本発明の最短経路探索の基本的説明図（その２）である。
【図４】本発明の最短経路探索の基本的説明図（その３）である。
【図５】本発明の始点と終点が与えられたときの極大なメッシュの例を示す図である。
【図６】Ｗｅｓｔ Ｖｉｒｇｉｎｉａの地図情報（データ）を示す図である。
【図７】図６における階層メッシュ疎化法で用意するネットワークの一部を示す図である。
【図８】図６における始点と終点が指定された場合の最短経路探索例を示す図（その１）である。
【図９】図８における始点と終点が指定された場合の最短経路探索例を示す図（その２）である。
【図１０】本発明の疎化ネットワーク構築システムの構成図である。
【図１１】本発明の本発明のデータ縮小法である疎化ネットワーク作成フローチャートである。
【図１２】図１１のステップＳ４のサブフローチャートを示す図である。
【図１３】本発明にかかる黒丸ａから残りの黒丸ｂ，ｃ，…，ｈへの最短経路の例を示す図である。
【図１４】本発明にかかる黒丸ｇから残りの黒丸ａ，ｂ，…，ｈへの最短経路の例を示す図である。
【図１５】本発明にかかるａ，ｂ，…，ｈの全対間の最短経路を重ね合わせた図である。
【図１６】本発明にかかるａ，ｂ点間の最短経路を求めるためのネットワークを示す図である。
【図１７】本発明にかかる最短経路探索方法のフローチャートである。
【符号の説明】
【０１１９】
１ 最短経路演算手段
２，６４ 最小のメッシュ設定手段
３，６５ メッシュ疎化ネットワーク構築手段
４ 始点と終点の設定手段
５ 極大なメッシュの設定手段
６ 探索した利用枝でメッシュをつなぐ手段
７ 求解用疎化ネットワーク構築手段
８ 最短経路検索手段
１１ 地図情報
１２ 入力手段
１３ 出力手段
２１，２１′，３１，４１ 最小のメッシュ
２２，２２′ 外領域
２３，２３′ 外領域の境界
２４，２４′，３３，４２ 始点
２５，２５′，３３，３４，４３ 終点
２６ 最小のメッシュ内で覚えた線
３２ 大きなメッシュ
４１ 始点と終点が与えられたときの極大なメッシュ
５１，５２ 最短経路
６１ 第１の外部記憶装置
６１Ａ メモリドライブ
６１Ｂ 地図情報記憶装置
６２ 主記憶装置
６３ 領域設定手段
６６ 第２の外部記憶装置
【技術分野】
【０００１】
本発明は、人・車による道路上の移動や電車の経路を求める、最短経路探索方法に関するものであり、特に、カーナビゲーションやＷｅｂでの最短経路探索方法に関するものである。
【背景技術】
【０００２】
従来、２点間を結ぶ最短の経路を求める問題は、古来より人間の行動に深く関わってきた最適化問題である。特に、人や車による道路上の移動や電車の経路を求める問題は、ネットワーク上の問題としてモデル化でき、ダイクストラ（Ｄｉｊｋｓｔｒａ）法を始めとする多くのアルゴリズムが提案されてきた。
【０００３】
近年情報技術（ＩＴ）の発達により、大規模な地図情報をコンパクトにコンピュータ上に格納することが可能となり、最短経路問題を解くソフトをつけた上で、ナビゲーションシステムという形で自動車に搭載できるようになってきた。
【０００４】
上記ダイクストラ法は、計算量理論の意味からするとほぼ最適なアルゴリズムである。しかし、現実問題に適用する場合には、遠い点を結ぶ最短経路を求めるときに、地図情報（地図データ）の多くの部分にアクセスする必要があり、現実的な時間で解くことができない。
【０００５】
この問題を解決するために、いくつかのアプローチが取られてきた。
【０００６】
一つは、最適性を犠牲にして、発見的な手法を導入する方法である。例えば、ある離れた地域間を移動する際には、ある種の決まったルートを通るという仮定をおき、途中の探索を省くというものである。また、道路を高速道路・主要道といった遠距離の移動に使う道からなるネットワークと、それ以外の道からなるネットワークに階層を分け、まず現在地・目的地から最寄りの主要道までの最短経路を求めた後に、主要道上での最短経路問題を解くという、階層化を行うアプローチもある。
【０００７】
他に、最適性を犠牲にしないアプローチもある。ダイクストラ法を始点終点両方から行い探索範囲を狭める方法、目的地までの距離の直線距離が短くなる方向を優先して探索するＡ* アルゴリズムなどである。
【０００８】
近年、地図情報（地図データ）にある種の前処理を行い、後で最短経路を求める場合に短時間で解けるようにする、というアプローチがとられ始めている。これには、計算機技術の進歩により、大規模な地図情報に対しても、ある程度複雑な前処理が現実的な時間内にできるようになってきたという理由もあると考えられる。この手法は、比較的成功を収めており、大規模な地図情報上でも短時間で最短経路を求めることに成功している。
【０００９】
前処理を行うアルゴリズムにもいくつかのバリエーションがある。
【００１０】
一つはビットベクトル法と呼ばれるもので、地図をいくつかのエリアに分割し、各頂点とエリアの組に対して、その頂点に接続する枝の中で、その頂点からエリア内の頂点への最短経路が使う利用枝を選び出しておく手法である。最短経路探索時には、各頂点から探索を行う際に、目的地を含むエリアに向かう最短経路が使用する利用枝の方向のみへ、探索の腕を伸ばすことで探索を省略する。直感的には、目的地に向かわない方向の枝への探索は全て省略されるため、探索の範囲を大幅に減らすことができる。しかし、前処理では基本的に全点間の最短経路問題を解かなければいけないため、高速化を行っても非常に長い時間がかかるという欠点がある。また、各枝について、エリアの数だけのビットが保存領域として必要となる。
【００１１】
もう一つはハイウェイ階層法と呼ばれるもので、遠距離の移動の中間で使われる利用枝のみからなるネットワークを構築しておき、遠い点を結ぶ最短経路を求める場合には、近距離移動用の枝を無視することで高速化を行う手法である。閾値ｋを用いて、遠距離の移動を２ｋ＋１本以上の枝を使う移動と定義し、最短経路が２ｋ＋１本以上の枝を含むような場合に、始点からも終点からもｋ歩以上離れている最短経路上の枝を遠距離移動用の枝と定義する。逆にいえば、遠距離移動用の枝とは、最短経路がその枝を通過するような、最短経路上でｋ歩以上離れた始点終点の組が存在するような枝のことである。遠距離移動用の枝のみを集めたハイウェイネットワークを構築し、始点終点からｋ歩のところまでは通常のネットワークを、それ以後はハイウェイネットワークを移動することで、高速化を行う。現実のネットワークでは遠距離移動用の枝の数はそれほど多くないため、階層的・再帰的にハイウェイネットワークを構築することで探索すべき枝の数を少なくすることができる。この手法の利点は、各点から２ｋ＋１歩以内にある点に対してのみ最短経路を求めることで前処理が終わることであり、それゆえに前処理時間が他の手法と比べて短いことである。
【００１２】
また、この分野の先行技術としては、以下に示すような提案がなされている。
【００１３】
（１）全ての道路を複数の不定形の地域に分割して記憶すると共に、地域間の接続関係も別に記憶しておき、出発地と目的地が属する二つの地域間を結ぶ地域を選定した後に、選定した地域に属する道路について経路探索を行う経路探索方法（下記特許文献１参照）。
【００１４】
（２）高速道路、国道及び主要地方道といったように、道路を複数の階層に分類し、各階層は交差点情報、道路情報を備えており、それに基づいて経路探索を行う経路探索方法（下記特許文献２参照）。
【００１５】
（３）道路地図情報を、主要道路を対象とする主要道路レイヤと、主要道路と主要でない道路とを共に対象とする一般道路レイヤとに分け、かつ、複数のメッシュに区分して記憶すると共に、各メッシュの道路の接続情報も記憶するようにした経路計算方法（下記特許文献３参照）。
【特許文献１】特許第３２４４５１７号公報
【特許文献２】特許第３１８６７９４号公報
【特許文献３】特許第３０８５０５４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、上記した経路探索方法では、膨大な地図情報を必要とするので、処理時間が長くなり、経路探索時間が長くなるといった問題があった。
【００１７】
本発明は、上記問題点を除去し、幾何学的な構造を用いた前処理を行い、探索を速め、スケーラビリティとグラフの疎化に優れた最短経路探索方法を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明は、上記目的を達成するために、
〔１〕最短経路探索方法において、第１の外部記憶装置から地図情報を主記憶装置に読み込み、前記地図情報に基づきメッシュの形状、各メッシュを含む領域である外領域の設定を行い、前記メッシュの疎化ネットワークの構築を行い、第２の外部記憶装置に記憶し、始点と終点の位置情報を入力し、前記始点と前記終点の両者を外領域に含まないメッシュを集め、このメッシュの中で、他のものに含まれない極大なメッシュのみを残し、残りのメッシュを捨て、前記残った極大なメッシュの境界をまたぐ利用枝を探索し、この探索した利用枝で前記メッシュをつなぎ、前記第２の外部記憶装置に記憶された前記メッシュの疎化ネットワークを読み出して、求解用疎化ネットワークを構築し、この求解用疎化ネットワーク内での始点から終点への最短経路を求めて、該最短経路を出力することを特徴とする。
【００１９】
〔２〕上記〔１〕記載の最短経路探索方法において、前記メッシュの疎化ネットワークの構築は、前記メッシュＭ内にある交差点に接続する道路を全て探索して、前記メッシュに関するネットワークを構築し、前記メッシュからある程度の距離にある領域を外領域とし、該外領域の境界上にある道路を全て探索し、この探索した道路のそれぞれに対して、接続する交差点を１つ選定し、この選定された交差点の各ペアについて、その点間の最短経路を求め、前記メッシュに関するネットワークで、前記最短経路のいずれにも含まれないものを消去することを特徴とする。
【００２０】
〔３〕上記〔１〕記載の最短経路探索方法において、前記始点の周辺及び前記終点の周辺に対しても外行き疎化ネットワークと内行き疎化ネットワークを用いることを特徴とする。
【発明の効果】
【００２１】
本発明によれば、次のような効果を奏することができる。
【００２２】
地図情報に基づいてメッシュの大きさを設定し、各最小メッシュを含む大きな外領域を設定し、その外領域の外側の２点を結ぶ最短経路に含まれるメッシュの枝を利用枝とし、この利用枝を全てのメッシュについて求める。２点間の最短経路を求めるときは、２点の両方から遠い部分では利用枝のみを探索することで高速化を行う。また、複数の階層的な大きさのメッシュに対して、利用枝を用意し、始点と終点の両方から遠い領域ほど、より大きなメッシュを使えるようにする。利用枝が作るネットワークは、次数２の頂点を多く含み、このような頂点を縮約すると、メッシュの大きさによらず、利用枝の本数は同程度となるので、階層的にメッシュを用意することにより、始点と終点間が遠くてもネットワークの枝数は多くならずに最短経路を検索することができる。
【発明を実施するための最良の形態】
【００２３】
本発明の最短経路探索方法は、第１の外部記憶装置から地図情報を主記憶装置に読み込み、前記地図情報に基づきメッシュの形状、該メッシュを含む領域である外領域の設定を行い、前記メッシュの疎化ネットワークの構築を行い、第２の外部記憶装置に記憶し、始点と終点の位置情報を入力し、前記始点と前記終点の両者を外領域に含まないメッシュを集め、このメッシュの中で、他のものに含まれない極大なメッシュのみを残し、残りのメッシュを捨て、前記残った極大なメッシュの境界をまたぐ利用枝を探索し、この探索した利用枝で前記メッシュをつなぎ、前記第２の外部記憶装置に記憶された前記メッシュの疎化ネットワークを読み出して、求解用疎化ネットワークを構築し、この求解用疎化ネットワーク内での始点から終点への最短経路を求めて、該最短経路を出力する。
【実施例】
【００２４】
以下、本発明の実施の形態について詳細に説明する。
【００２５】
本発明の階層メッシュ疎化法（Ｌｅｖｅｌ−ｗｉｓｅ Ｍｅｓｈ Ｓｐａｒｓｉｆｉｃａｔｉｏｎ）は、従来技術で説明した従来の手法とは異なる新しい手法である。従来の手法を使って言い表すならば、ハイウェイ階層法を幾何学的な構造の上に落としたものだと言える。
【００２６】
まず、平面上の地図情報に対し、それをある大きさのメッシュに分割する。そして、そのメッシュを含む一回り大きな外領域を考え、外領域の外側の２点を結ぶ最短経路に含まれるメッシュの枝を、利用枝と定義する。外領域が十分大きければ、メッシュの中で利用枝となる枝の数は少なくなる。この利用枝を全てのメッシュに対して求め、２点間の最短経路を求めるときには、２点両方から遠い部分では利用枝のみを探索することで高速化を行う。さらに、複数の大きさのメッシュに対して利用枝ネットワークを作っておくことで、始点と終点の両方から遠い領域ほど、より大きなメッシュを使えるようにする。実験的には、利用枝が作るネットワークは、次数２の頂点を多く含み、このような頂点を縮約した後では、メッシュの大きさによらず利用枝の本数は同程度となる。そのため、階層的にメッシュを用意することで、地図の規模が大きくなっても、始点と終点の両方から遠い部分のネットワークはそれほど枝数が大きくならず、地図の大きさに対して安定的なアルゴリズムが実現できる。
【００２７】
従来のハイウェイ階層法では、このような次数２の頂点を縮約することによる効率化の恩恵にあずかることは難しい。なぜならハイウェイ階層法では、階層間の接続が全ての場所で行われているため、ハイウェイネットワーク上で次数２の頂点を消去してしまうと、その点に接続していた通常のネットワークの枝からハイウェイネットワークへの移動ができなくなってしまうからである。
【００２８】
その反面、本発明の階層メッシュ疎化法では、階層の違うネットワークの接続部分はメッシュの縁の部分だけであるので、内側に関しては頂点の縮約を行える。これは階層メッシュ疎化法の大きな利点である。実験の結果、階層メッシュ疎化法を用いて構築したネットワークは、もとのネットワークに比べてはるかに少ない数の枝しか含まないことがわかった。しかも、ほぼすべての枝は始点と終点付近に集中しており、これは他の手法でも網羅的に探索が行われる領域である。その結果、通常のダイクストラ法を用いただけで、既存の最速のアルゴリズムとほぼ同等の性能を出すことに成功した。そのうえ、本発明の階層メッシュ疎化法は、ビットベクトル法やＡ* アルゴリズムとも併用できるため、これらの手法を用いることでより一層の高速化が行える。
【００２９】
以下、階層メッシュ疎化法について説明する。
【００３０】
まず、〔１〕で用語の定義を行い、〔２〕で階層メッシュ疎化法の基礎となる疎化ネットワークとその性質を説明する。また、〔３〕で疎化ネットワークを始点終点に近いエリアに適用する外行き・内行きの疎化ネットワークの説明を行い、〔４〕では前処理を高速に行う手法を説明する。
〔１〕定義
Ｇ＝（Ｖ, Ａ）を頂点集合Ｖ、枝集合Ａからなる有向ネットワークとし、ｄ：Ａ→Ｒを枝の距離関数とする。特に本発明では、地図情報を仮定するため、距離関数は正、つまり、ｄ：Ａ→Ｒ+ であるとする。頂点集合Ｖの各点は２次元ユークリッド空間上に置かれているものとし、頂点ｖのｘ座標、ｙ座標をそれぞれｘ（ｖ）, ｙ（ｖ）と表記する。一般性を失うことなく、あるＭに対して０≦ｘ（ｖ）, ｙ（ｖ）＜Ｍが成り立つとし、０≦ｘ, ｙ＜Ｍである領域を地図領域と呼ぶ。また、始点ｖと終点ｕに対して、〔ｖ，（ｖ，ｗ１），ｗ１，（ｗ１，ｗ２），…，ｗｋ，（ｗｋ，ｕ），ｕ）〕となっている頂点と枝の列をパスと呼ぶ。パスは、頂点の列あるいは枝の列から一意的に導かれるため、隣接する頂点の列、あるいは隣接する枝の列もパスと呼ぶ。ｖ, ｕはこのパスの端点と呼ばれる。パスの長さは、パスに含まれる枝の距離和で定義する。ｕ, ｖを結ぶパスの中で最も長さの短いものをｕ, ｖを結ぶ最短経路と呼び、その長さをｄu （ｖ）と表記する。最短経路は唯一的であるとは限らないが、ここでは摂動を加えることで唯一的になると仮定しておく。頂点ｒに対して、頂点ｒを根とする木で、頂点ｒから木の各頂点ｕへのパスが、頂点ｒから木の各頂点ｕへの最短経路となっているようなものを頂点ｒの最短経路木と呼ぶ。通常、最短経路木は全ての頂点を含む全張木で定義するが、ここでは、一部の頂点のみを含むものもよしとする。頂点集合Ｕと始点ｒに対して、頂点集合Ｕの頂点を全て含むｒの最短経路木の中で極小なものをＴr （Ｕ）と表記する。Ｔr （Ｕ）は、頂点ｒから頂点集合Ｕの各頂点への最短経路の和集合である。頂点ｒと枝ｅ＝（ｕ, ｖ）に対して、ｄr （ｖ）−ｄr （ｕ）をｅの縮退コストと呼び、ｃr （ｅ）で定義する。このｃr （ｅ）は負にはならず、ｃr （ｅ）が０となるとき、またそのときに限り枝ｅは最短経路木に含まれる。
【００３１】
メッシュ粒度ｋに対して、ｋレベルのメッシュを、ある整数０≦ｉ，ｊ≦ｋに対してｉＭ／ｋ≦ｘ＜（ｉ＋１）Ｍ／ｋ，ｊＭ／ｋ≦ｙ＜（ｊ＋１）Ｍ／ｋとなるような領域で定義し、ｉＭ／ｋ，（ｉ＋１）Ｍ／ｋ，ｊＭ／ｋ，（ｊ＋１）Ｍ／ｋをこのメッシュの左、右、上、下と呼ぶ。地図領域は、ｋレベルのメッシュｋ2 個によって分割される。連結な領域Ｓに対して、端点の１つがＳに含まれる枝をＳに含まれる枝と呼び、Ｅ（Ｓ）と表記する。また、端点の１つがＳに含まれ、もう１つがＳに含まれないような枝を、Ｓの境界枝と呼び、その集合をＣ（Ｓ）と表記する。このＣ（Ｓ）の枝の端点でＳに含まれない点を、Ｓの境界頂点と呼び、その集合をＢ（Ｓ）と表記する。
【００３２】
〔２〕階層メッシュ疎化法
ここで、階層メッシュ疎化法の基礎となる疎化ネットワークとその性質について説明する。
【００３３】
ｋレベルのメッシュｍに対して、メッシュｍの外領域Ｓを、メッシュｍを完全に含むような連結な領域で定義する。このとき、メッシュｍの外領域Ｓの境界頂点ｒに対してＴr 〔Ｂ（Ｓ）〕の枝でＥ（ｍ）に含まれるものを、全ての境界頂点ｒに対して求めて和をとった枝集合をＳＥ（ｍ）と表記する。さらに、ＳＥ（ｍ）の枝が導くグラフＲに対して以下の縮約操作を行って得られるグラフを、ｍの疎化ネットワークと呼び、ＳＧ（ｍ）と表記する。疎化ネットワークはメッシュｍの外領域Ｓにより変化することを注意しておく。
アルゴリズム縮約操作（領域Ｒ）：
（１）グラフＲに次数２の頂点ｖが含まれるならば、頂点ｖに隣接する頂点ｕ，ｗに対して、ｕ，ｗ間に枝がなければ枝（ｕ，ｗ）で結び、そのコストをｄ（ｕ，ｖ）＋ｄ（ｖ，ｗ）とし、枝（ｕ，ｗ）が存在するならば、そのコストをｄ（ｕ，ｗ）とｄ（ｕ，ｖ）＋ｄ（ｖ，ｗ）の小さい方にする。そして、頂点ｖと枝（ｕ，ｖ），（ｖ，ｗ）を除去する。
【００３４】
（２）グラフＲに次数１の頂点が含まれ、それに隣接する頂点がＢ（ｍ）に含まれないならば、その次数１の頂点と接続する枝を除去する。
【００３５】
（３）上記（１），（２）の条件が成り立たなくなるまで、上記（１），（２）を繰り返す。
【００３６】
この操作は、Ｏ（｜ＳＥ（ｍ）｜）時間で実行できることを注意しておく。
【００３７】
Ｍ上に頂点集合を持つネットワークＧ＝（Ｖ，Ａ）と、Ｇから得られたｍの疎化ネットワークＳＧ（ｍ）＝（Ｖ’⊆Ｖ，Ａ’）に対して、Ｇからｍ上に端点を持つ枝を取り除き、Ａ’を枝集合に加えてできるネットワークＧ’をＧに埋め込んだネットワークと呼ぶ。
【００３８】
疎化ネットワークに対しては、以下の補助定理１が成り立つ。
【００３９】
補助定理１：
ｕ，ｖをｍの外領域に含まれないＧの頂点とする。このとき、Ｇでの頂点ｕ，ｖ間の最短経路長とＳＧ（ｍ）をＧに埋め込んだネットワークでの頂点ｕ，ｖ間の最短経路長は等しい。特にＧでの最短経路は、埋め込んだネットワークでの最短経路の、縮約された枝を元に戻すことにより得られる。
【００４０】
ここで、メッシュｍの外領域を、メッシュｍを中心とし、ｘ径がｈ倍、ｙ径がｈ倍であるような四角い領域とする。つまり、メッシュｍがｉＭ／ｋ≦ｘ＜（ｉ＋１）Ｍ／ｋ，ｊＭ／ｋ≦ｙ＜（ｊ＋１）Ｍ／ｋとなる領域であれば、外領域は（ｉ−（ｈ−１）／２）Ｍ／ｋ≦ｘ＜（ｉ＋（ｈ＋１）／２）Ｍ／ｋ，（ｊ−（ｈ−１）／２）Ｍ／ｋ≦ｙ＜（ｊ＋（ｈ＋１）／２）Ｍ／ｋであるようなｘ、ｙからなる領域となる。このとき、ｈを外領域の倍率と呼ぶ。
【００４１】
今、１，２，４，８，…，２g レベルのメッシュの集合をＺとし、Ｚの各メッシュの外領域の倍率をｈとする。地図領域上のネットワークＧの２点ｕ，ｖに対して、Ｚのメッシュの中で、ｕ，ｖ両点が外領域の外側にあるメッシュをアクティブなメッシュと呼び、アクティブなメッシュの中で、他のＺのアクティブなメッシュに含まれないものを極大アクティブメッシュと呼ぶ。レベルが２のべき乗で与えられていることから、極大なアクティブメッシュは互いに共通部分を持たず、ｕ，ｖの周り以外の領域を完全に覆う。今、Ｇに対して、各極大アクティブメッシュの疎化ネットワークを逐次的に埋め込んで得られるネットワークを、ｕ，ｖの疎化ネットワークと呼ぶ。このとき、補助定理１より以下の定理が成り立つ。
【００４２】
その定理は、「任意のｇ、ｈと地図領域上に定義されたネットワークＧの任意の２点ｕ，ｖに対して、Ｇでのｕ，ｖ間の最短経路長とｕ，ｖの疎化ネットワークでのｕ，ｖ間の最短経路長は等しい。特にネットワークＧでの最短経路は、疎化ネットワークでの最短経路の、縮約された枝を元に戻すことにより得られる。」ということである。
【００４３】
上記定理より、各メッシュに対して疎化ネットワークを構築する、という前処置を行っておけば、ｕ，ｖ間の最短経路を求める際に、まずｕ，ｖの疎化ネットワークを構築し、そのうえで最短経路を解く、というアプローチが行える。
【００４４】
通常、遠距離を移動するために使う枝は限られており、縮約操作によってネットワークを縮小できると予想される。この効果については、後述の説明を参照されたいが、基本的に大きなメッシュほど疎化ネットワークが小さくなる傾向がある。極大アクティブメッシュの数は、ネットワークの大きさに対してあまり大きくならない。例えば、ｈ＝３とした場合、最大でも２７個である。そのため、たとえ地図領域が２倍になり、ｇを一つ大きくして、最小のメッシュの大きさを揃えたとしても、２つの頂点に対する極大アクティブメッシュの総数の最大値は、たかだか２７しか大きくならないのである。
【００４５】
疎化ネットワークが疎であることは、メモリ使用量の少なさにも貢献する。メッシュの数は、レベルの減少に従って指数的に少なくなるので、レベル毎の疎化ネットワーク保存にかかるメモリも指数的に小さくなる。そのため、全ての疎化ネットワークをメモリに保存しても、元のネットワークの定数倍程度のメモリしか使用しない。
【００４６】
また、ネットワークが変化した時に、前処理を行うタイプのアルゴリズムは前処理をし直さなければならないが、階層メッシュ疎化法はその時間が少なくてすむという長所がある。ある枝が追加・削除されたとき、あるいは枝の距離が変わったときに、作り直さなければいけない疎化ネットワークは、外領域がその枝を含むようなメッシュだけである。これは、例えば外領域の倍率ｈが３であるとき、各レベルで９個までである。
〔３〕外行き疎化ネットワーク
上記により定義した疎化ネットワークでは、始点と終点の周りに関してはネットワークの疎化が行われなかった。これは疎化ネットワークの発想の基本が、遠距離移動を行う際の中間部分の探索を高速化しようという発想に基づいているからで、ある意味で当然である。しかし、似たようなアイデアを用いると、始点終点の周りに関しても、ある種の疎なネットワークを構築することができる。ここでは、疎化ネットワークを始点や終点に近いエリアに適用する外行き及び内行きの疎化ネットワークについて説明する。
【００４７】
ｋレベルのメッシュｍに対して、メッシュｍに含まれる各頂点ｒからメッシュｍの外領域の境界頂点Ｂ（Ｓ）への最短経路木Ｔr 〔Ｂ（Ｓ）〕の枝を集めて得られるネットワークを考える。メッシュｍに含まれる任意の頂点ｒから、メッシュｍの外領域Ｓに含まれない頂点への最短経路のｍに含まれる部分は、必ずこのネットワークに含まれる。そこで、このネットワークに上述した縮約操作を行って得られるネットワークをｍの外行き疎化ネットワークと定義すれば、以下の補助定理２が成り立つ。
【００４８】
補助定理２：
ｕをメッシュｍの外領域に含まれない頂点、ｖをメッシュｍに含まれる頂点とする。このとき、Ｇでのｕ，ｖ間の最短経路長と、メッシュｍの外行き疎化ネットワークをＧに埋め込んだネットワークでのｕ，ｖ間の最短経路長は等しい。
【００４９】
外行き疎化ネットワークは、メッシュの中の全ての端点を始点とする最短経路木の和集合であるので、あまり疎になるとは考えられない。メッシュｍの内部での袋小路的な構造、あるいは通過速度の遅い道からなる部分に関しては、そこから出て行く枝が外行き疎化ネットワークに含まれることはあっても、そこに入る枝が含まれることは考えにくい。そうなると、メッシュｍに含まれる頂点ｒに対して、メッシュｍの中で枝を順向きにたどって頂点ｒから到達可能な頂点・枝は、非常に少ないと考えられる。
【００５０】
同様に、終点に対しても内行き疎化ネットワークを定義することができ、以下の補助定理３が成り立つ。
【００５１】
補助定理３：
ｕをメッシュｍの外領域に含まれない頂点、ｖをメッシュｍに含まれる頂点とする。このとき、Ｇでのｕ，ｖ間の最短経路長と、メッシュｍの内行き疎化ネットワークをＧに埋め込んだネットワークでのｕ，ｖ間の最短経路長は等しい。
【００５２】
外行き・内行き疎化ネットワークは、通常の疎化ネットワークと異なりあまり疎にはならない。そのため、全てのレベルについて外行き疎化ネットワークを求めメモリに保存すると、メモリ使用量が元のネットワークが使用するメモリに対して、レベル数ｇの値だけ倍化されてしまう。そのため実用上は、ある程度以上大きな定数個のレベルに対してのみ、外行き・内行き疎化ネットワークを求める、という手法が望ましい。
〔４〕疎化ネットワークの再帰的な利用による前処理の高速化
疎化ネットワークを求めるためには、基本的に外領域の境界頂点の全対に対して最短経路を求める必要がある。これは時間のかかる作業である。メッシュが大きくなるにつれ、メッシュの数自体は減るが、ネットワーク規模が大きくなるため、計算時間はそれほど短縮されず、逆に増加する可能性もある。ここでは、疎化ネットワークを求める高速アルゴリズムについて説明する。
【００５３】
高速化手法の一つ目は、疎化ネットワークを求める際に疎化ネットワークを用いるという手法である。これは、疎化ネットワークをレベルの大きなメッシュから順に求めていき、あるレベルのメッシュの疎化ネットワークを求める際に、それより大きなレベルの疎化ネットワークを用いて最短経路を求めるというものである。メッシュｍとその外領域Ｓに対して、Ｂ（Ｓ）のどの頂点も外領域に含まれないメッシュをアクティブなメッシュと呼び、メッシュｍ以外の他のアクティブなメッシュに含まれないメッシュを極大アクティブメッシュと呼ぶ。前述での議論同様、極大アクティブメッシュは非交差的であり、外領域Ｓ上のネットワークに全ての極大アクティブメッシュを逐次的に埋め込んだネットワークでは、最短経路の長さは保存され、メッシュｍの疎化ネットワークを求める際に利用できるのである。これにより、最短経路問題を解く時間は大幅に短くなる。同様に、外行き疎化ネットワーク、内行き疎化ネットワークを用いることもできる。まず、外領域Ｓの境界頂点を含むメッシュに対し、その中の１つメッシュｍ’の外行き疎化ネットワークを埋め込み、メッシュｍ’が外領域Ｓの外側にあるメッシュの内行き疎化ネットワークを埋め込む。このネットワークでは、メッシュｍ’内の頂点ｒを始点とする最短経路の長さが保存されるため、頂点ｒの最短経路木Ｔr 〔Ｂ（Ｓ）〕を求める際に利用できる。
【００５４】
このように本発明によれば、幾何学的な構造を用いた前処理を行うことで最短経路問題を効率的に解く、階層メッシュ疎化法を提供することができる。
【００５５】
本発明の階層メッシュ疎化法の基本的なアイデアは、各メッシュ内で遠距離の移動の中間で使われる枝のみを選別し、縮約操作でネットワークを疎化・単純化するものである。同時に、始点の周辺・終点の周辺に対しても外行き疎化ネットワークと内行き疎化ネットワークを提供するようにした。両者ともに、計算実験の結果、ネットワークのサイズの縮小に大きく貢献することがわかった。また、前処理に再帰的に階層メッシュ疎化法を用いることで高速化を行う方法を提供することができる。
【００５６】
図１は本発明の最短経路探索方法を実施する全体システムの構成図である。
【００５７】
この図において、１は最短経路演算手段であり、この最短経路演算手段１はメッシュ設定手段２と、メッシュ疎化ネットワーク構築手段３と、始点と終点の設定手段４と、極大なメッシュの設定手段５と、その境界をまたぐ利用枝を探索し、その探索した利用枝でメッシュをつなぐ手段６と、メッシュ疎化ネットワーク構築手段３からのデータを利用した求解用疎化ネットワーク構築手段７と、最短経路探索手段８とを備えている。また、１１は最短経路演算手段１に取り込まれる地図情報、１２は最短経路演算手段１に情報を入力する入力手段、１３は最短経路演算手段１からの最短経路出力が提供される出力手段（表示・記憶・プリントアウトなどの報知手段）である。
【００５８】
まず、階層メッシュ疎化法を概観する。
【００５９】
図２は本発明の最短経路探索の基本的説明図（その１）である。
【００６０】
この図において、２１はメッシュ、２２はその外領域、２３はその外領域の境界、２４は始点、２５は終点であり、ここでは、外領域２２の外側に始点２４と終点２５がある。ここで、始点２４と終点２５の最短経路を求める場合には、メッシュ２１内の疎化ネットワークは、外領域２２の外側の任意の２点を結ぶ最短経路の枝を含んでいるため、疎化ネットワークの線２６のみを使っても最短経路を求めることができる。つまり、最短経路計算で使われる情報（データ）が少なくなる。
【００６１】
図３は本発明の最短経路探索の基本的説明図（その２）である。
【００６２】
この図に示すように、位置をずらしたメッシュ２１′の疎化ネットワークも合わせて使用すると、最短経路計算で使われる情報（データ）がさらに少なくなる。ここで、２２′はメッシュ２１′の外領域、２３′は外領域２２′の境界である。また、２４′は始点、２５′は終点である。
【００６３】
図４は本発明の最短経路探索の基本的説明図（その３）であり、上記した個別のものがまとめられている。
【００６４】
いろいろな大きさのメッシュ３１，３２で、遠いところ同士の最短経路で使われる道を覚え、始点３３と終点３４が指定されたら、なるべく道数の少ないネットワークを構成し（大きいメッシュ３２を優先的に使う）、最短経路を計算する。
【００６５】
図５は本発明の始点と終点が与えられたときの極大なメッシュの例を示す図である。
【００６６】
この図において、始点４２と終点４３が与えられたときの極大なメッシュ４１が示されている。
【００６７】
Ｗｅｓｔ Ｖｉｒｇｉｎｉａ州の道路ネットワークに対する適用例を用いて説明する。
【００６８】
図６はＷｅｓｔ Ｖｉｒｇｉｎｉａの地図情報（データ）を示す図であり、３００１４６ノード、６５７７１６枝を有している。Ｄｉｊｋｓｔｒａ法とｂｉｎａｒｙ ｈｅａｐ法ではデータをメモリにした格納後、計算に約１秒かかる。なお、Ｄｉｊｋｓｔｒａ法の計算時間は枝数にほぼ比例する。
【００６９】
図７は図６における階層メッシュ疎化法で用意するネットワークの一部を示す図である。
【００７０】
図８は図６における始点と終点が指定された場合の極大なメッシュの疎化ネットワークを組み合わせてできるネットワークとその上での最短経路探索例を示す図（その１）である。
【００７１】
この図８において、５１が最短経路（白線）であり、枝の数は約１００００（元のグラフの約１／６０）、計算時間は約１５ミリ秒であり、約６０倍の高速化を図ることができる。
【００７２】
図９は図６における始点と終点が指定された場合の最短経路探索例を示す図（その２）である。
【００７３】
この図において、５２が最短経路（白線）である。
【００７４】
図８と対比すると明らかなように、指定される始点と終点が異なれば、計算に使われるネットワークも異なることが分かる。
【００７５】
以下、より具体的に説明する。
【００７６】
図１０は本発明の疎化ネットワーク構築システムの構成図である。
【００７７】
この図において、６１は第１の外部記憶装置であり、メモリドライブ６１Ａに地図情報記憶装置６１Ｂが装着されることにより地図情報を主記憶装置６２に読み込むことができる。この主記憶装置６２に読み込まれた情報を用いて領域設定手段６３で領域が設定される。その領域設定が行われるとメッシュ設定手段６４でメッシュが設定される。各メッシュに基づいて疎化ネットワーク構築手段６５によって疎化ネットワークが構築される。そこで、構築されたメッシュの疎化ネットワークを第２の外部記憶装置６６に記憶する。
【００７８】
図１１は本発明のデータ縮小法である疎化ネットワーク作成フローチャート、図１２は図１１のステップＳ４のサブフローチャートを示す図である。
【００７９】
図１１に示すように、データ縮小法のフローチャートは、以下のようである。
（１）まず、第１の外部記憶装置６１から地図情報を主記憶装置６２に読み込む（ステップＳ１）。
（２）次に、その地図情報に基づいて領域設定を行う（ステップＳ２）。
（３）次に、領域設定に基づいて各メッシュの設定を行う（ステップＳ３）。
（４）次に、各メッシュの疎化ネットワークの構築を行う（ステップＳ４）。
（５）最後に、そのメッシュの疎化ネットワークを第２の外部記憶装置６６に記憶する（ステップＳ５）。
【００８０】
上記（３）においては、不要に細かすぎるメッシュまで生成しないよう決定する。
【００８１】
ここで、上記（４）の各メッシュの疎化ネットワークにおいては、図１２に示すように、各レベルの各メッシュに対して以下の操作を行い、メッシュの疎化ネットワークを構築する。
【００８２】
（４−１）メッシュ内にある交差点に接続する道路を全て探索して、メッシュに関するネットワークを構築する（ステップＳ１１）。
【００８３】
（４−２）メッシュからある程度の距離にある領域を外領域とし、その境界上にある道路を全て探索する（ステップＳ１２）。
【００８４】
（４−３）探索した全ての道路それぞれに対して、接続する交差点を１つ選定する（ステップＳ１３）。
【００８５】
（４−４）選定された交差点の各ペアについて、その点間の最短経路を求める（ステップＳ１４）。
【００８６】
（４−５）メッシュに関するネットワークで、上記（４−４）で得られた最短経路いずれにも含まれないものを消去する（ステップＳ１５）。
【００８７】
なお、上記（４）においては、地図をある方向にスキャンしながら順にメッシュを調べることで、メッシュに関するネットワークの構築にかかるための時間を減らしても良い。
【００８８】
上記（４−３）においては、地図をスキャンし、各交差点を得てもよい。
【００８９】
また、上記（４−４）においては、外領域上に制限した地図情報上において、各点から必要な点への１対多最短経路や、全点間の最短経路を求めることで、各交差点ペアの最短経路を求めても良い。
【００９０】
上記（５）においては、上記（４−５）にて各疎化ネットワークを構築するごとに第２の外部記憶装置６６に書き込むことで、主記憶装置６２の節約を行っても良い。
【００９１】
図１３は地図情報から構築した道路ネットワークデータと、メッシュ（実線の四角）とそのメッシュの外領域（破線の四角）を示す図である。
【００９２】
以下、アルゴリズムの動作を具体的に説明する。
【００９３】
上記（４−１）で構築されたネットワークは、例えば、図１３のような、交差点を頂点とし、交差点を接続する道路を枝とするようなネットワークとなり、各枝に、その道路の区間距離、あるいはその道路を通過するのにかかる所要時間のデータがある。
【００９４】
上記（４−２）で探索する道は、図１３の破線の四角と交わりを持つ道（ネットワークの枝）である。
【００９５】
上記（４−３）で選定する交差点は、例えば、図１３に示される黒丸で示したものになる。
【００９６】
上記（４−４）では、図１３に示される黒丸で示した交差点の全てのペアについて、両者を結ぶ最短経路を求める。例えば、図１３では、黒丸ａから残りの黒丸ｂ，ｃ，…，ｈへの最短経路の例を、図１４では、黒丸ｇから残りの黒丸ａ，ｂ，…，ｈへの最短経路の例を示した。枝の距離と図中の枝を示す線分の距離は対応しないため、見かけ上最短である経路が選定されていないことに留意しておく。
【００９７】
上記（４−５）では、上記（４−４）で得られた最短経路全てを重ね合わせたネットワークを求め、メッシュに含まれる部分のみを取り出す。上記の例では、図１５のようになる。
【００９８】
図１５はａ，ｂ，…，ｈの全対間の最短経路を重ね合わせた図である。
【００９９】
この中の、実線の四角内のネットワークが、対応するメッシュの疎化ネットワークになる。
【０１００】
メッシュの大きさ・形状の決定は、例えば以下のように行う。
【０１０１】
まず、レベル０のメッシュを地図の領域全てとし、レベル１のメッシュを、レベル０のメッシュを４分割して得られるものとする。以下、レベルｋのメッシュは、レベルｋ−１のメッシュを４分割して得るものとする。各レベルのメッシュは、地図領域全体を分割したものになっている。
【０１０２】
メッシュＭの外領域は、たとえば、Ｍに隣接するメッシュを全て集めて、Ｍを包含する大きな四角い領域を作ることで作成する。
【０１０３】
実際に２点ａ，ｂ間の最短経路を求める際には、疎化ネットワークを組合せて、最短経路求解用のネットワークを構築する。２点ａ，ｂの両点を外領域の外側とするようなメッシュを集め、その中で極大なもの、つまり、他の、そのようなメッシュに含まれないもののみを集める。図１６にその例を示した。
【０１０４】
図１６はａ，ｂ点間の最短経路を求めるためのネットワークを示す図である。
【０１０５】
図１６に示される四角は、２点ａ，ｂを含むもの以外が上記で述べたメッシュに対応し、それらは、外領域に２点ａ，ｂを含まない。
【０１０６】
最短経路を求める際には、これらのメッシュのネットワークを接続して、最短経路求解用疎化ネットワークを構築し、最短経路アルゴリズムを実行する。
【０１０７】
以下に、最短経路を求める際に構築する疎化ネットワークの構築方法を、図１７を参照しながら説明する。
【０１０８】
（１）始点（現在地）と終点（目的地）の位置情報を入力する（ステップＳ２１）。これは、図１６に示した２点ａ，ｂを入力することに対応する。
【０１０９】
（２）始点（現在地）と終点（目的地）の両者を外領域に含まないメッシュを集める（ステップＳ２２）。これは、図１６に示される２点ａ，ｂを含まない四角、およびそれらに含まれる四角を集めることに相当する。
【０１１０】
（３）上記（２）で集めたメッシュの中で、他のものに含まれない極大なもののみを残し、残りを捨てる（ステップＳ２３）。図１６では、この作業は、上記（２）で集めたメッシュの中で極大なもの、つまり、図１６の四角い領域で２点ａ，ｂを含まないものの中で、そのような他のメッシュに含まれないものを集めることに等しい。
【０１１１】
（４）残ったメッシュの境界をまたぐ枝を調べ上げる（ステップＳ２４）。これは、図１６でのメッシュ、および２点ａ，ｂを含む四角い領域をつなげるために使う枝を調べ上げている。
【０１１２】
（５）探索した枝でメッシュをつなぎ、求解用疎化ネットワークを構築する（ステップＳ２５）。
【０１１３】
（６）求解用疎化ネットワーク内での始点（現在地）から終点（目的地）への最短経路を求める（ステップＳ２６）。
【０１１４】
（７）求めた最短経路を出力する（ステップＳ２７）。
【０１１５】
本発明は、地図情報を有するカーナビゲーションやＷｅｂでの最短経路探索方法に限られるものではなく、地図情報を有する鉄道経路や航路での最短経路探索方法にも適用することができる。
【０１１６】
なお、本発明は上記実施例に限定されるものではなく、本発明の趣旨に基づいて種々の変形が可能であり、これらを本発明の範囲から排除するものではない。
【産業上の利用可能性】
【０１１７】
本発明の最短経路探索方法は、地図情報を有するカーナビゲーションやＷｅｂでの最短経路探索方法として利用可能である。
【図面の簡単な説明】
【０１１８】
【図１】本発明の最短経路探索方法を実施する全体システムの構成図である。
【図２】本発明の最短経路探索の基本的説明図（その１）である。
【図３】本発明の最短経路探索の基本的説明図（その２）である。
【図４】本発明の最短経路探索の基本的説明図（その３）である。
【図５】本発明の始点と終点が与えられたときの極大なメッシュの例を示す図である。
【図６】Ｗｅｓｔ Ｖｉｒｇｉｎｉａの地図情報（データ）を示す図である。
【図７】図６における階層メッシュ疎化法で用意するネットワークの一部を示す図である。
【図８】図６における始点と終点が指定された場合の最短経路探索例を示す図（その１）である。
【図９】図８における始点と終点が指定された場合の最短経路探索例を示す図（その２）である。
【図１０】本発明の疎化ネットワーク構築システムの構成図である。
【図１１】本発明の本発明のデータ縮小法である疎化ネットワーク作成フローチャートである。
【図１２】図１１のステップＳ４のサブフローチャートを示す図である。
【図１３】本発明にかかる黒丸ａから残りの黒丸ｂ，ｃ，…，ｈへの最短経路の例を示す図である。
【図１４】本発明にかかる黒丸ｇから残りの黒丸ａ，ｂ，…，ｈへの最短経路の例を示す図である。
【図１５】本発明にかかるａ，ｂ，…，ｈの全対間の最短経路を重ね合わせた図である。
【図１６】本発明にかかるａ，ｂ点間の最短経路を求めるためのネットワークを示す図である。
【図１７】本発明にかかる最短経路探索方法のフローチャートである。
【符号の説明】
【０１１９】
１ 最短経路演算手段
２，６４ 最小のメッシュ設定手段
３，６５ メッシュ疎化ネットワーク構築手段
４ 始点と終点の設定手段
５ 極大なメッシュの設定手段
６ 探索した利用枝でメッシュをつなぐ手段
７ 求解用疎化ネットワーク構築手段
８ 最短経路検索手段
１１ 地図情報
１２ 入力手段
１３ 出力手段
２１，２１′，３１，４１ 最小のメッシュ
２２，２２′ 外領域
２３，２３′ 外領域の境界
２４，２４′，３３，４２ 始点
２５，２５′，３３，３４，４３ 終点
２６ 最小のメッシュ内で覚えた線
３２ 大きなメッシュ
４１ 始点と終点が与えられたときの極大なメッシュ
５１，５２ 最短経路
６１ 第１の外部記憶装置
６１Ａ メモリドライブ
６１Ｂ 地図情報記憶装置
６２ 主記憶装置
６３ 領域設定手段
６６ 第２の外部記憶装置
【特許請求の範囲】
【請求項１】
（ａ）第１の外部記憶装置から地図情報を主記憶装置に読み込み、
（ｂ）前記地図情報に基づきメッシュの形状、該メッシュを含む領域である外領域の設定を行い、
（ｃ）各メッシュの疎化ネットワークの構築を行い、
（ｄ）第２の外部記憶装置に記憶し、
（ｅ）始点と終点の位置情報を入力し、
（ｆ）前記始点と前記終点の両者を外領域に含まないメッシュを集め、
（ｇ）該メッシュの中で、他のものに含まれない極大なメッシュのみを残し、残りのメッシュを捨て、
（ｈ）前記残った極大なメッシュの境界をまたぐ利用枝を探索し、
（ｉ）該探索した利用枝で前記メッシュをつなぎ、前記第２の外部記憶装置に記憶された前記メッシュの疎化ネットワークを読み出して、求解用疎化ネットワークを構築し、
（ｊ）該求解用疎化ネットワーク内での始点から終点への最短経路を求めて、該最短経路を出力することを特徴とする最短経路探索方法。
【請求項２】
請求項１記載の最短経路探索方法において、前記メッシュの疎化ネットワークの構築は、（ａ）前記メッシュＭ内にある交差点に接続する道路を全て探索して、前記メッシュに関するネットワークを構築し、（ｂ）前記メッシュからある程度の距離にある領域を外領域とし、該外領域の境界上にある道路を全て探索し、（ｃ）該探索した道路のそれぞれに対して、接続する交差点を１つ選定し、（ｄ）該選定された交差点の各ペアについて、その点間の最短経路を求め、（ｅ）前記メッシュに関するネットワークで、前記最短経路のいずれにも含まれないものを消去することを特徴とする最短経路探索方法。
【請求項３】
請求項１記載の最短経路探索方法において、前記始点の周辺及び前記終点の周辺に対しても外行き疎化ネットワークと内行き疎化ネットワークを用いることを特徴とする最短経路探索方法。
【請求項１】
（ａ）第１の外部記憶装置から地図情報を主記憶装置に読み込み、
（ｂ）前記地図情報に基づきメッシュの形状、該メッシュを含む領域である外領域の設定を行い、
（ｃ）各メッシュの疎化ネットワークの構築を行い、
（ｄ）第２の外部記憶装置に記憶し、
（ｅ）始点と終点の位置情報を入力し、
（ｆ）前記始点と前記終点の両者を外領域に含まないメッシュを集め、
（ｇ）該メッシュの中で、他のものに含まれない極大なメッシュのみを残し、残りのメッシュを捨て、
（ｈ）前記残った極大なメッシュの境界をまたぐ利用枝を探索し、
（ｉ）該探索した利用枝で前記メッシュをつなぎ、前記第２の外部記憶装置に記憶された前記メッシュの疎化ネットワークを読み出して、求解用疎化ネットワークを構築し、
（ｊ）該求解用疎化ネットワーク内での始点から終点への最短経路を求めて、該最短経路を出力することを特徴とする最短経路探索方法。
【請求項２】
請求項１記載の最短経路探索方法において、前記メッシュの疎化ネットワークの構築は、（ａ）前記メッシュＭ内にある交差点に接続する道路を全て探索して、前記メッシュに関するネットワークを構築し、（ｂ）前記メッシュからある程度の距離にある領域を外領域とし、該外領域の境界上にある道路を全て探索し、（ｃ）該探索した道路のそれぞれに対して、接続する交差点を１つ選定し、（ｄ）該選定された交差点の各ペアについて、その点間の最短経路を求め、（ｅ）前記メッシュに関するネットワークで、前記最短経路のいずれにも含まれないものを消去することを特徴とする最短経路探索方法。
【請求項３】
請求項１記載の最短経路探索方法において、前記始点の周辺及び前記終点の周辺に対しても外行き疎化ネットワークと内行き疎化ネットワークを用いることを特徴とする最短経路探索方法。
【図１】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００８−３０９６６５（Ｐ２００８−３０９６６５Ａ）
【公開日】平成２０年１２月２５日（２００８．１２．２５）
【国際特許分類】
【出願番号】特願２００７−１５８１７６（Ｐ２００７−１５８１７６）
【出願日】平成１９年６月１５日（２００７．６．１５）
【出願人】（５０４１９６３００）国立大学法人東京海洋大学 (83)
【Ｆターム（参考）】
【公開日】平成２０年１２月２５日（２００８．１２．２５）
【国際特許分類】
【出願日】平成１９年６月１５日（２００７．６．１５）
【出願人】（５０４１９６３００）国立大学法人東京海洋大学 (83)
【Ｆターム（参考）】
[ Back to top ]