ネットワーク経路探索装置、方法及びプログラム
【課題】経路探索時の処理負荷の小さいネットワーク表現のためのデータ構造と、それを用いた経路探索手法を提供する。
【解決手段】ネットワークの各リンクのリンク番号に対して、リンクの片方のノードのノード番号と、そのノードに接続された他のリンクのリンク番号である片方のノードの接続先リンク番号と、リンクのもう一方のノードのノード番号と、そのノードに接続された他のリンクのリンク番号であるもう一方のノードの接続先リンク番号と、を格納したリンク接続先テーブルにより、相互に接続されたリンクを辿ることで経路探索を行う。
【解決手段】ネットワークの各リンクのリンク番号に対して、リンクの片方のノードのノード番号と、そのノードに接続された他のリンクのリンク番号である片方のノードの接続先リンク番号と、リンクのもう一方のノードのノード番号と、そのノードに接続された他のリンクのリンク番号であるもう一方のノードの接続先リンク番号と、を格納したリンク接続先テーブルにより、相互に接続されたリンクを辿ることで経路探索を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク経路探索装置、方法及びプログラムに関し、特にネットワークを表現する新規なデータ構造に基づくネットワーク経路探索装置、方法及びプログラム、さらにはネットワークを表現する新規なデータ構造を作成する手法に関する。
【背景技術】
【０００２】
道路網、通信網、あるいは配管ネットワーク等の物理的ネットワークを論理的なネットワークで表現し、コンピュータ上で最適経路を求めたり配送コストを計算したりすることが行われている。そのようなネットワーク関連の技術を適用した車両走行案内装置が下記特許文献１に開示されている。
従来の論理的ネットワーク（以下、単にネットワークという。）は、特許文献１の表１及び表２に記載されているように、ネットワーク要素としてノードとノード間を接続するリンクのそれぞれが定義されているとみることができる。そして、ノードとリンクの属性に関するデータによりネットワークが表現され、そのネットワーク表現に基づいて、経路探索等が行われている。
【０００３】
図１は、ネットワーク構成例とそれを表現する従来のデータ構造を説明する図である。図１の（ａ）に示すのは、道路網をモデル化したノード１０（Ｎ１〜Ｎ６）と各ノード間を接続するリンク１２（Ｌ１〜Ｌ８）からなるネットワークの構成例である。ノードの符号１０は、ノードＮ１にのみ付され、他は省略している。リンクの符号１２についても、リンクＬ５にのみ付され、他は省略している。図に示すように、リンクＬ１はノードＮ１とノードＮ２を接続し、リンクＬ２はノードＮ２とノードＮ３を、リンクＬ３はノードＮ２とノードＮ４を接続している。リンクＬ４はノードＮ３とノードＮ４を接続し、リンクＬ５はノードＮ３とノードＮ５を接続している。また、リンクＬ６はノードＮ４とノードＮ５を、リンクＬ７はノードＮ４とノードＮ６を、リンクＬ８はノードＮ５とノードＮ６を接続している。
【０００４】
図１の（ｂ）に示すのは、図１の（ａ）に示すネットワークを表現する従来のデータ構造の例であり、交差点テーブル１１１、リンクテーブル１２１及びノードテーブル１３１を備えている。
交差点テーブル１１１は、交差点であるノードとそれに接続された道路であるリンクを関係づけたものであり、ノードのノード番号１１２に対応してノードに接続されたリンクのリンク番号１１４が格納されている。図の例では、ノード番号Ｎ１に対してリンク番号Ｌ１が、ノード番号Ｎ２に対してリンク番号Ｌ１、Ｌ２、Ｌ３が、記載されている。以下同様に、Ｎ３に対してＬ２、Ｌ４、Ｌ５が、Ｎ４に対してＬ３、Ｌ４、Ｌ６、Ｌ７が、Ｎ５に対してＬ５、Ｌ６、Ｌ７が、Ｎ６に対してＬ７、Ｌ８が格納されている。なお、メモリ上に存在するのはＮ１の行からＮ６の行にかけての部分であることは当然である。以下で説明する他のテーブルについても同様である。
【０００５】
リンクテーブル１２１は、リンクとその両端のノードを関係づけたものであり、リンク番号１２２に対して該リンク番号１２２のリンクに接続された片方のノードのノード番号１２３ともう一方のノードのノード番号１２４が格納されている。図の例では、リンク番号Ｌ１に対してノード番号Ｎ１とノード番号Ｎ２が、リンク番号Ｌ２に対してノード番号Ｎ２とノード番号Ｎ３が片方のノード番号１２３ともう一方のノード番号１２４として格納されている。以下同様に、Ｌ３に対してＮ２とＮ４が、Ｌ４に対してＮ３とＮ４が、Ｌ５に対してＮ３とＮ５が、Ｌ６に対してＮ４とＮ５が、Ｌ７に対してＮ４とＮ６が、Ｌ８に対してＮ５とＮ６が格納されている。
【０００６】
ノードテーブル１３１は、ノード番号１３２とノード情報１３３の項目からなり、各ノードのノード番号Ｎ１〜Ｎ６毎に各ノードの位置等のノード情報を格納したものである。なお、ノード情報の具体例については省略されている。
【特許文献１】特開平７−１４６１５５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来のネットワーク表現においては、ノードとリンクの双方をネットワークの構成要素とし、複数のテーブルを備えており、経路探索を行うとき、これらの複数のテーブルを順次参照することが必要となるため、経路探索を行うときの処理コストが高いという欠点を有する。
【０００８】
そこで本発明が解決しようとする課題は、経路探索時の処理負荷の小さいネットワーク表現のためのデータ構造と、それを用いた経路探索手法を提供することである。
【課題を解決するための手段】
【０００９】
本発明によれば、ネットワークの各リンクのリンク番号に対して、リンクの片方のノード（以下、Ａ端のノードということがある。）のノード番号と、そのノードに接続された他のリンクのリンク番号である片方のノードの接続先リンク番号と、リンクのもう一方のノード（以下、Ｂ端のノードということがある。）のノード番号と、そのノードに接続された他のリンクのリンク番号であるもう一方のノードの接続先リンク番号と、を格納したリンク接続先テーブルを、ネットワークを表現するデータ構造として提供する。
【００１０】
リンク接続先テーブルは、さらに各リンクのＡ端のノードからＢ端のノードへのコスト及びＢ端のノードからＡ端のノードへのコスト、すなわちリンクのコストを備える。さらに、本発明の好適な実施の形態によれば、リンク接続先テーブルは、各リンクからＡ端及びＢ端のノードの接続先リンク番号に格納されたリンク番号のリンクに接続するコストを格納することができる。リンク接続先テーブルに格納されたリンクとその接続先リンクをたどることにより始点から終点への経路を探索し、各経路のコストを計算して最適経路探索を行う。
【００１１】
すなわち、始点側のノードをＡ端のノードとすると、経路探索は、始点側のノードに係るリンクからスタートし、そのリンク番号の行に格納されたリンク接続先テーブルのＢ端のノードの接続先リンク番号のリンクに分岐し、さらにリンク接続先テーブルの、それらの分岐したリンクのリンク番号の行に格納されたＢ端のノードの接続先リンク番号のリンクに分岐することを終点のノードをＢ端のノードとするリンクまで、コストを計算しながら繰り返すことで行う。そして、始点から終点までの経路のうち、最適な経路を探索結果として出力する。
【発明の効果】
【００１２】
本発明のネットワーク表現のためのデータ構造によれば、リンク接続先テーブルを用いるだけであり、経路探索における経路の分岐はリンク番号のみを参照して行うことができるので、処理コストを小さくすることができる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明を実施するための最良の形態を、図面を参照しながら説明する。
図２Ａは、本発明の一実施の形態におけるネットワーク表現用のデータ構造を作成するための機能ブロックを説明する図である。図１に示す従来のデータ構造を有するデータをデータ構造読取手段２０１で読み取り、リンク接続先テーブル生成手段２０２がそのデータに基づきリンク接続先テーブルを生成する。
【００１４】
図２Ｂは、本発明の一実施の形態におけるネットワークの経路探索のための機能ブロックを説明する図である。ネットワークの経路探索要求に基づき、経路条件設定手段２０５が経路探索要求されたネットワークに対応するリンク接続先テーブル、始点ノード、終点ノード等の経路条件を設定する。経路探索手段２０６は、経路条件設定手段で設定された条件に基づいて経路を探索するとともに、それらの経路のコストを計算する。最適経路出力手段２０７は、経路探索手段２０６で探索された経路のうち、最適なコストの経路を探索結果として出力する。
【００１５】
図３は、本発明の一実施の形態におけるハードウェア構成例を説明する図である。
本発明のネットワーク経路探索装置による経路探索処理及びネットワーク表現用のデータ構造生成処理は中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。リンク接続テーブル３０９を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。
【００１６】
図２Ａ及び図２Ｂを参照して説明したデータ構造取出手段２０１等の各機能ブロックは、図３に例示するハードウェアと後に説明するステップを備えたソフトウェアにより実現可能である。
【００１７】
図３の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできる。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられることは当然である。以下の説明では、一時記憶領域に格納されたあるいは設定された値を一時記憶領域の名前で呼ぶことがある。
【００１８】
図４Ａは、本発明の一実施の形態におけるネットワークを表現するデータ構造を説明する図である。コストについては省略している。図に示すように、リンク接続先テーブル３０９ａは、リンク番号２３２、片方のノードのノード番号２３４、片方のノードの接続先リンク番号２３５、もう一方のノードのノード番号２３７及びもう一方のノードの接続先リンク番号２３８の項目を有している。
【００１９】
各項目の値は、図１の（ａ）に示すネットワーク構成例に対応するものである。リンク番号２３２のＬ１に対応して、片方のノードのノード番号２３４にＮ１、もう一方のノードのノード番号２３７にＮ２、もう一方のノードの接続先リンク番号２３８にＬ２とＬ３が格納され、片方のノードの接続先リンク番号２３５には何も格納されていない。
【００２０】
リンク番号２３２のＬ２に対応しては、片方のノードのノード番号２３４にＮ２、片方のノードの接続先リンク番号２３５にＬ１とＬ３、もう一方のノードのノード番号２３７にＮ３、もう一方のノードの接続先リンク番号２３８にＬ４とＬ５が格納されている。
【００２１】
以下同様に、各リンク番号２３２のＬ３、Ｌ４、Ｌ５、Ｌ６、Ｌ７、Ｌ８にそれぞれ対応して、片方のノードのノード番号２３４にＮ２、Ｎ３、Ｎ３、Ｎ４、Ｎ４、Ｎ５が、片方のノードの接続先リンク番号２３５にＬ１とＬ２、Ｌ２とＬ５、Ｌ２とＬ４、Ｌ３とＬ４とＬ７、Ｌ３とＬ４とＬ６、Ｌ５とＬ６が、もう一方のノードのノード番号２３７にＮ４、Ｎ４、Ｎ５、Ｎ５、Ｎ６、Ｎ６が、もう一方のノードの接続先リンク番号２３８にＬ４とＬ６とＬ７、Ｌ３とＬ６とＬ７、Ｌ６とＬ８、Ｌ５とＬ８、Ｌ８、Ｌ７が、格納されている。
【００２２】
図４Ｂは、従来のネットワーク表現データから本発明の一実施形態におけるネットワーク表現データを生成する概念を説明する図である。図に示す従来のデータ構造１００は、図１の（ｂ）に示すリンクテーブル１２１と交差点テーブル１１１の関連する一部の行を取り出して示している。図４Ｂに示す例では、矢印４０３で示すリンク番号１２２がＬ２である行をリンクテーブル１２１から取り出している。
【００２３】
本発明の一実施の形態におけるデータ構造２００は、図４Ａに示すリンク接続テーブル３０９ａのリンク番号２３２がＬ２の行である。従来のデータ構造１００のリンク番号１２２からの点線の矢印（Ａ）で示すように、従来のデータ構造１００のリンク番号１２２と同じリンク番号が、本発明の一実施の形態におけるデータ構造２００のリンク番号２３２に設定される。
【００２４】
矢印４０４で示すように、従来のデータ構造１００の片方のノード番号１２３のＮ２の行が交差点テーブル１１１から読み出され、点線の矢印（Ｂ）で示すように、ノード番号１１２ａのＮ２、点線の矢印（Ｄ）で示すようにリンク番号１１４ａのうちリンク番号１２２と同一でないＬ１とＬ３が、それぞれ本発明の一実施の形態におけるデータ構造２００の片方のノード番号２３４と片方のノードの接続先リンク番号２３５に設定される。
【００２５】
同様に、矢印４０５で示すように、従来のデータ構造１００のもう一方のノード番号１２４のＮ３の行が交差点テーブル１１１から読み出され、点線の矢印（Ｃ）で示すように、ノード番号１１２ｂのＮ３、点線の矢印（Ｅ）で示すようにリンク番号１１４ｂのうちリンク番号１２２と同一でないＬ４とＬ５が、それぞれ本発明の一実施の形態におけるデータ構造２００のもう一方のノード番号２３７ともう一方のノードの接続先リンク番号２３８に設定される。
【００２６】
図５は、本発明の一実施の形態におけるネットワーク表現のためのデータ構造を作成する処理フローを説明する図である。以下において、図１、図４Ａ及び図４Ｂの例示を参照しながら説明する。
【００２７】
まず、ステップＳ５０１でリンク接続先テーブル書込位置に、リンク接続先テーブルの先頭位置を設定する。図４Ａの例示では、リンク接続先テーブル３０９ａのリンク番号２３２がＬ１の行の先頭位置が設定される。ここでリンク接続先テーブル書込位置は、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域」の１つであり、リンク接続先テーブルの書込位置を設定する図示しない一時記憶領域である。以下の説明において、上述のリンク接続先テーブル書込位置と同様に、図示しない一時記憶領域をそこに格納されあるいは設定されるデータの内容により呼ぶことがある。
【００２８】
次にステップＳ５０２で、リンクテーブル読出位置に、リンクテーブルの先頭位置を設定する。図１の例示では、リンクテーブル１２１のリンク番号１２２がＬ１の行の先頭位置が設定される。
【００２９】
次にステップＳ５０３に進み、リンクテーブル読出位置の指すリンクテーブルよりリンク番号を取り出し、一時記憶領域であるリンク番号（以下、図５の説明に限り、Ａという。）に設定する。図４Ｂの例示では、矢印４０３で示すようにリンクテーブル読出位置のリンク番号１２２はＬ２であり、ＡにはＬ２が設定される。
【００３０】
次にステップＳ５０４に進み、リンクテーブル読出位置の指すリンクテーブルより片方のノード番号を読み出し、一時記憶領域である片方のノード番号（以下、図５の説明に限り、Ｂという。）に設定する。図４Ｂの例示では、リンクテーブル読出位置の片方のノード番号１２３はＮ２であり、ＢにはＮ２が設定される。
【００３１】
次にステップＳ５０５に進み、リンクテーブル読出位置の指すリンクテーブルよりもう一方のノード番号を読み出し、一時記憶領域であるもう一方のノード番号（以下、図５の説明に限り、Ｃという。）に設定する。図４Ｂの例示では、リンクテーブル読出位置のもう一方のノード番号１２４はＮ３であり、ＣにはＮ３が設定される。
【００３２】
次にステップＳ５０６に進み、Ｂの指す交差点テーブルよりＡを除いたリンク番号を読み出し、一時記憶領域である片方のノードの接続リンク番号（以下、図５の説明に限り、Ｄという。）に設定する。図４Ｂの例示では、矢印４０４で示すように、Ｂに設定されたＮ２の指す交差点テーブルのリンク番号はＬ１、Ｌ２、Ｌ３であり、Ａに設定されたＬ２を除くＬ１とＬ３がＤに設定される。
【００３３】
次にステップＳ５０７に進み、Ｃの指す交差点テーブルよりＡを除いたリンク番号を読み出し、一時記憶領域であるもう一方のノードの接続リンク番号（以下、図５の説明に限り、Ｅという。）に設定する。図４Ｂの例示では、矢印４０５で示すように、Ｃに設定されたＮ３の指す交差点テーブルのリンク番号はＬ２、Ｌ４、Ｌ５であり、Ａに設定されたＬ２を除くＬ４とＬ５がＥに設定される。
【００３４】
次にステップＳ５０８において、リンク接続先テーブル書込位置の指すリンク接続先テーブルの、リンク番号にＡを、片方のノード番号にＢを、もう一方のノード番号にＣを、片方のノードの接続先リンク番号にＤを、もう一方のノードの接続リンク先番号にＥを、それぞれ設定する。図４Ｂの例示では、矢印４０３と対応するリンク接続先テーブル書込位置のリンク番号２３２にＡに設定されたＬ２が、片方のノード番号２３４にＢに設定されたＮ２が、片方のノードの接続先リンク番号２３５にＤに設定されたＬ１とＬ３が、もう一方のノード番号２３７にＣに設定されたＮ３が、もう一方のノードの接続リンク先番号２３８にＥに設定されたＬ４とＬ５が、それぞれ設定されている。
【００３５】
次にステップＳ５０９において、リンクテーブル読出位置はリンクテーブルの末尾の位置か判定する。末尾の位置でなければ、ステップＳ５１０でリンク接続先テーブル書込位置に次の書込位置を設定し、ステップＳ５１１でリンクテーブル読出位置に次の読出位置を設定してステップＳ５０３に戻ってステップＳ５０３〜ステップＳ５０９の処理を繰り返す。
【００３６】
一方、ステップＳ５０９で、リンクテーブル読出位置はリンクテーブルの末尾の位置であると判定されると、リンク接続先テーブルは完成しているので処理を終了する。上述の処理フローのうち、ステップＳ５０２〜ステップＳ５１１を図２Ａに示すデータ構造読取手段２０１により実行し、ステップＳ５０１とステップＳ５０８をリンク接続先テーブル生成手段２０２により実行するもととすることができる。なお、上述の処理フローと各ステップの実行手段の対応は単なる一例であり、種々の変更が可能なことは明らかである。
【００３７】
以上の処理でリンク接続先テーブルが生成されるので、リンク接続先テーブルの生成に用いたデータは消去することも可能であるが、次に説明するネットワーク探索処理において、経路探索の始点に接続されたリンクを探す処理の便宜のために、交差点テーブルを残しておくことが好適である。
【００３８】
図６は、本発明の一実施の形態におけるネットワーク探索におけるコスト設定例を説明する図である。図６の（ａ）に示すのは、図１の（ａ）に示すネットワーク構成例のうち、ノードＮ２とＮ３及びそれらに接続されるリンクＬ１、Ｌ２、Ｌ３、Ｌ４、Ｌ５に関係する本発明の一実施の形態におけるコストの概念である。
【００３９】
図に示すように、リンク接続先テーブルのリンク番号２３２がＬ２であるとすると、片方のノード（Ａ端のノード）のノード番号２３４はＮ２、もう一方のノード（Ｂ端のノード）のノード番号２３７はＮ３である。このとき、リンクＬ２に対して、ノードＮ２からノードＮ３へのもう一方のノードへのコスト［２３４ａ］と、ノードＮ３からノードＮ２への片方のノードへのコスト［２３７ａ］が定義される。これらのコストを区間コストという。
【００４０】
本発明の一実施の形態においては、上述の区間コストに加えて、リンクのＡ端側とＢ端側のリンクへの接続コストを定義する。以下の実施の形態の説明では、接続コストが定義されるものとして説明する。図に示すように、Ａ端側において、リンク番号２３２がＬ２のリンクから、片方のノードの接続先リンク番号２３５ａがＬ１の接続先リンクへの接続コスト［２３６ａ］と片方のノードの接続先リンク番号２３５ｂがＬ３の接続先リンクへの接続コスト［２３６ｂ］が定義される。同様に、Ｂ端側において、もう一方のノードの接続先リンク番号２３８ａがＬ４の接続先リンクへの接続コスト［２３９ａ］ともう一方のノードの接続先リンク番号２３８ｂがＬ５の接続先リンクへの接続コスト［２３９ｂ］が定義される。
【００４１】
図６の（ｂ）に示すのは、図４Ａに例示したリンク接続先テーブル３０９ａに上述の区間コストと接続コストを付加したリンク接続先テーブル３０９ｂである。リンク番号２３２がＬ１〜Ｌ８のリンクに対して、Ｂ端へのコスト２３４ａの例として１、２、３、１、２、２、３、１が設定され、Ａ端へのコスト２３７ａの例として２、１、２、３、１、２、２、３が設定されている。
【００４２】
また、Ａ端のノードの接続先リンク情報として、リンク２３５ａへの接続コスト２３６ａ、リンク２３５ｂへの接続コスト２３６ｂ及びリンク２３５ｃへの接続コスト２３６ｃが設定されている。同様に、Ｂ端のノードの接続先リンク情報として、リンク２３８ａへの接続コスト２３９ａ、リンク２３８ｂへの接続コスト２３９ｂ及びリンク２３８ｃへの接続コスト２３９ｃが設定されている。
【００４３】
ただし、リンクＬ１のＡ端のノードであるＮ１はネットワーク上の片接続の端点であるので、図４Ａに示すリンク接続先テーブル３０９ａのリンクＬ１についての片方のノードの接続先リンク番号２３５には何も設定されておらず、したがって、リンク接続先テーブル３０９ｂのリンク番号Ｌ１に対応するＡ端のノードの接続先リンク情報は設定されていない。リンクＬ１のＢ端のノードの接続先リンク情報については、リンクＬ２への接続コストに１、リンクＬ３への接続コストに１が設定されている。
【００４４】
リンクＬ２については、Ａ端のノードの接続先リンク情報としてリンクＬ１への接続コストに２、リンクＬ３への接続コストに１が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ４への接続コストに１、リンクＬ５への接続コストに１が設定されている。
【００４５】
リンクＬ３については、Ａ端のノードの接続先リンク情報としてリンクＬ１への接続コストに３、リンクＬ２への接続コストに２が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ４への接続コストに２、リンクＬ６への接続コストに２、リンクＬ７への接続コストに２が設定されている。
【００４６】
リンクＬ４については、Ａ端のノードの接続先リンク情報としてリンクＬ２への接続コストに１、リンクＬ５への接続コストに１が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ３への接続コストに２、リンクＬ６への接続コストに３、リンクＬ７への接続コストに３が設定されている。
【００４７】
リンクＬ５については、Ａ端のノードの接続先リンク情報としてリンクＬ２への接続コストに２、リンクＬ４への接続コストに２が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ６への接続コストに１、リンクＬ８への接続コストに２が設定されている。
【００４８】
リンクＬ６については、Ａ端のノードの接続先リンク情報としてリンクＬ３への接続コストに２、リンクＬ４への接続コストに３、リンクＬ７への接続コストに２が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ５への接続コストに２、リンクＬ８への接続コストに３が設定されている。
【００４９】
リンクＬ７については、Ａ端のノードの接続先リンク情報としてリンクＬ３への接続コストに３、リンクＬ４への接続コストに４、リンクＬ６への接続コストに１が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ８への接続コストに１が設定されている。
【００５０】
リンクＬ８については、Ａ端のノードの接続先リンク情報としてリンクＬ５への接続コストに２、リンクＬ６への接続コストに２が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ７への接続コストに２が設定されている。
【００５１】
上述のように、コストを区間コストと接続コストに分離して設定可能とすることにより、よりきめ細かく現実の物理ネットワークを模擬することができる。例えば道路網をモデル化する場合、道幅や速度制限等の比較的道路に固有の条件を区間コストに反映し、右折禁止や右折信号の有無など、道路と道路の間の通行条件を接続コストに反映することなどができる。
【００５２】
図７は、本発明の一実施の形態におけるネットワークの経路探索の概念を説明する図である。図７の（ａ）に示すのは、図１の（ａ）に例示するネットワークのノードＮ１を始点とし、ノードＮ６を終点とする経路探索において展開されるすべての経路であり、図７の（ｂ）に示すのは、上述の経路探索において作成される経路情報テーブルである。
始点ノードから終点ノードまでの経路は、その間を接続するリンク列で表現できることから、経路展開は、最初のリンクＬ１をルートとし、その接続先リンクを下位のノードとするツリーの形状で表すことができる。このツリーを経路展開ツリーと呼ぶことにすると、図７の（ａ）に示すものは、経路中のリンクに対して、Ａ端のノード番号２３４、リンク番号２３２、Ｂ端へのコスト２３４ａ及びＢ端のノード番号２３７を備えるノード（経路展開ノードということがある。）と下位の経路展開ノードに含まれるリンクへの接続コストを備えたブランチ（経路展開ブランチということがある。）を備えた経路展開ツリーである。したがって、ネットワークの経路探索は、経路展開ツリーを生成し、生成された経路から最適経路を探すことに相当する。
【００５３】
図に示すように、始点２４１としてノードＮ１が指定され、リンク接続先テーブル３０９ｂから、ノード番号Ｎ１を片方のノード（Ａ端のノード）のノード番号２３４とするリンク番号２３２としてＬ１が選ばれ、リンク番号Ｌ１の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ２が読み出され、経路展開ツリーのルートノードが生成される。Ｂ端のノードＮ２には、Ｎ２までの経路コスト２４２ａ［接続数、累積コスト］として「０、１」が計算されて付随している。
【００５４】
次にリンク番号Ｌ１の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報の先頭から、リンクＬ２への接続コスト２３９ａとしての１が読み出され、実線の矢印で示すように接続コストＬ２［１］が付随した経路展開ブランチが生成される。そして、リンク番号Ｌ２の指すリンク接続先テーブル３０９ｂからＡ端のノード番号２３４としてのＮ２とＢ端へのコスト２３４ａとして２が読み出され、さらにＢ端のノードのノード番号２３７としてＮ３が読み出され、Ｎ３までの経路コスト２４２ｂとして［１、４］が計算され、リンクＬ２に対応する経路展開ノードが生成される。ここで累積コスト４は、ノードＮ２までの累積コスト１にリンクＬ１からリンクＬ２への接続コスト１とリンク２の区間コスト２を加えたものである。
【００５５】
また同じく、リンク番号Ｌ１の指すリンク接続先テーブル３０９ｂからＢ端のノードの次の接続先リンク情報として、リンクＬ３への接続コスト２３９ｂとしての１が読み出され、さらにリンク番号Ｌ３の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして３が取り出され、さらにＢ端のノードのノード番号２３７としてＮ４が読み出され、Ｎ４までの経路コスト２４２ｃとして［１、５］が計算される。
【００５６】
リンクＬ２側の経路では、リンク番号Ｌ２の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ４への接続コスト２３９ａとしての１が読み出され、さらにリンク番号Ｌ４の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ４が読み出され、Ｎ４までの経路コスト２４２ｄとして［２、６］が計算される。
【００５７】
また同じくリンクＬ２側の経路では、リンク番号Ｌ２の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ５への接続コスト２３９ｂとしての１が読み出され、さらにリンク番号Ｌ５の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出され、Ｎ５までの経路コスト２４２ｅとして［２、７］が計算される。
【００５８】
一方リンクＬ３側の経路では、リンク番号Ｌ３の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ４への接続コスト２３９ａとしての２が読み出され、さらにリンク番号Ｌ４の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ４が読み出される。
【００５９】
このリンクＬ４への接続については、経路展開なし２４４ａの点線の矢印で示しているように、リンク番号Ｌ４の指すリンク接続先テーブル３０９ｂのＢ端のノード番号２３７に設定されているノード番号がＮ４であって、接続元のリンクＬ３のＢ端のノードＮ４に戻るので、最小コスト計算に不要な経路であることは自明であるから、ここでは経路展開を打ち切る。なお、接続先のリンクのＡ端のノードかＢ端のノードのどちらか一方は接続元もリンクのＢ端のノードと一致し、同一のリンクのＡ端のノードとＢ端のノードが一致することはないから、経路展開の打ち切りの判定は、接続先のリンクのＡ端のノードが接続元のリンクのＢ端のノードと一致するかにより行うことができる。
【００６０】
同じくリンクＬ３側の経路では、リンク番号Ｌ３の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ６への接続コスト２３９ｂとしての２が読み出され、さらにリンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出され、Ｎ５までの経路コスト２４２ｆとして［２、９］が計算される。
【００６１】
さらに同じくリンクＬ３側の経路では、リンク番号Ｌ３の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ７への接続コスト２３９ｃとしての２が読み出され、さらにリンク番号Ｌ７の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして３が取り出され、さらにＢ端のノードのノード番号２３７としてＮ６が読み出され、Ｎ６までの経路コスト２４２ｇとして［２、１０］が計算される。図に示すように、ノードＮ６はリンクＬ１、Ｌ３、Ｌ７の経路による終点２４７ｇである。
【００６２】
また、リンクＬ２、Ｌ４の経路では、リンク番号Ｌ４の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ３への接続コスト２３９ａとしての２が読み出され、さらにリンク番号Ｌ３の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして３が取り出され、さらにＢ端のノードのノード番号２３７としてＮ４が読み出される。したがって、リンクＬ４のＢ端のノードＮ４に戻るので、経路コストの計算は行わず、経路の展開も打ち切る。
【００６３】
同じくリンクＬ２、Ｌ４の経路では、リンク番号Ｌ４の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ６への接続コスト２３９ｂとしての３が読み出され、さらにリンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出され、Ｎ５までの経路コスト２４２ｈとして［３、１１］が計算される。
【００６４】
さらに同じくリンクＬ２、Ｌ４の経路では、リンク番号Ｌ４の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ７への接続コスト２３９ｃとしての３が読み出され、さらにリンク番号Ｌ７の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして３が取り出され、さらにＢ端のノードのノード番号２３７としてＮ６が読み出され、Ｎ６までの経路コスト２４２ｉとして［３、１２］が計算される。図に示すように、ノードＮ６はリンクＬ１、Ｌ２、Ｌ４、Ｌ７の経路による終点２４７ｉである。
【００６５】
また、リンクＬ２、Ｌ５の経路では、リンク番号Ｌ５の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ６への接続コスト２３９ａとしての１が読み出され、さらにリンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出される。したがって、リンクＬ５のＢ端のノードＮ５に戻るので、経路コストの計算は行わず、経路の展開も打ち切る。
【００６６】
同じくリンクＬ２、Ｌ５の経路では、リンク番号Ｌ５の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ８への接続コスト２３９ｂとしての２が読み出され、さらにリンク番号Ｌ８の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ６が読み出され、Ｎ６までの経路コスト２４２ｊとして［３、１０］が計算される。図に示すように、ノードＮ６はリンクＬ１、Ｌ２、Ｌ５、Ｌ８の経路による終点２４７ｊである。
【００６７】
また、リンクＬ３、Ｌ６の経路では、リンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ５への接続コスト２３９ａとしての２が読み出され、さらにリンク番号Ｌ５の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出される。したがって、リンクＬ６のＢ端のノードＮ５に戻るので、経路コストの計算は行わず、経路の展開も打ち切る。
【００６８】
同じくリンクＬ３、Ｌ６の経路では、リンク番号Ｌ８の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ８への接続コスト２３９ｂとしての３が読み出され、さらにリンク番号Ｌ８の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ６が読み出され、Ｎ６までの経路コスト２４２ｋとして［３、１３］が計算される。図に示すように、ノードＮ６はリンクＬ１、Ｌ３、Ｌ６、Ｌ８の経路による終点２４７ｋである。
【００６９】
また、リンクＬ２、Ｌ４、Ｌ６の経路では、リンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ５への接続コスト２３９ａとしての２が読み出され、さらにリンク番号Ｌ５の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出される。したがって、リンクＬ６のＢ端のノードＮ５に戻るので、経路コストの計算は行わず、経路の展開も打ち切る。
【００７０】
同じくリンクＬ２、Ｌ４、Ｌ６の経路では、リンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ８への接続コスト２３９ｂとしての３が読み出され、さらにリンク番号Ｌ８の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ６が読み出され、Ｎ６までの経路コスト２４２ｍとして［４、１５］が計算される。図に示すように、ノードＮ６はリンクＬ１、Ｌ２、Ｌ４、Ｌ６、Ｌ８の経路による終点２４７ｍである。
【００７１】
以上により、ノードＮ１からノードＮ６への経路がすべて展開され、その接続数と累積コスト、及び経路リストを格納したものが、図７の（ｂ）に示す経路情報テーブル２８１である。経路情報テーブルは図７の（ａ）に示す終点２４７ｍ、２４７ｉ、２４７ｊ、２４７ｋ、２４７ｇに対応して、接続数として４、３、３、３、２が、累積コストとして１５、１２、１０、１３、１０が格納されている。また、Ａ端のノードのノード番号とリンク番号を組み合わせた経路リストには、図７の（ａ）に展開された経路に対応するものが格納されている。
なお、上述の経路展開の説明では、経路展開ツリーを上位の階層から説明したが、経路展開ツリーはリンク接続先テーブル３０９ｂに格納されたＢ端のノードの接続先リンク情報の位置（経路展開ツリー上では上側（右側））を優先させて生成させることができる。図７の（ｂ）に示す経路情報テーブルに格納された経路情報は、この順番で生成された経路展開ツリーによるものである。
【００７２】
以下、図８Ａ〜図８Ｃを参照して本発明の一実施の形態におけるネットワークの最適経路を探索する処理を説明する。この説明においては、経路展開ツリーの右側を優先させて生成するものとする。
図８Ａは、本発明の一実施の形態におけるネットワークの最適経路を探索する処理の概略フローを説明する図である。以下において、図１の（ａ）に示すネットワーク構成例、図６の（ｂ）に示すリンク接続先テーブル３０９ｂ、図７の（ｂ）に示す経路情報テーブル２８１等の具体例を適宜参照しながら説明する。その際、「具体例では、・・・」等の表記をすることがある。
【００７３】
まず、ステップＳ８０１において、リンク接続先テーブル、経路探索の始点ノード番号と始点リンク番号、及び終点ノード番号を設定する。リンク接続先テーブルの設定では、例えばリンク接続先テーブルの名称をシステム外部から指定することによりその先頭アドレスとサイズを設定する。また始点リンク番号の設定では、先に述べたように交差点テーブルから始点ノードに接続されたリンクのリンク番号を設定してもよい。
具体例では、始点ノード番号にＮ１、始点リンク番号にＬ１、終点ノード番号にＮ６、リンク接続先テーブルにリンク接続先テーブル３０９ｂが設定される。
【００７４】
次にステップＳ８０２において、経路情報の接続数に値“−１”を、累積コストに値“０”を設定し、ステップＳ８０３で次のノード番号に、始点ノード番号を設定する。
さらにステップＳ８０４で、接続先リンク番号に始点リンク番号を設定するとともに、接続コストに値“０”を設定し、ステップＳ８０４ａでリンク情報の読出位置を初期化してステップＳ８０５に進む。具体例では、次のノード番号にＮ１が、接続先リンク番号にＬ１が設定される。
【００７５】
ステップＳ８０５では、接続先リンク番号の指すリンク接続先テーブルを基に経路を探索し、ステップＳ８０６に進む。ステップＳ８０５の処理の詳細は、後に図８Ｂを参照して説明する。
ステップＳ８０６では、ステップＳ８０５で求めた探索結果より最適経路を出力し、処理を終了する。ステップＳ８０６の処理の詳細は、後に図８Ｃを参照して説明する。
なお、始点ノードに接続されたリンクが複数ある場合は、上述の処理によりそれぞれのリンクを始点リンクとした最適経路を求め、それらの最適経路からさらに最適経路を求めることができることは、当業者に明らかである。
【００７６】
図８Ｂは、図８Ａに示すステップＳ８０５の詳細な処理フローを示すものであり、本発明の一実施の形態におけるネットワークの経路探索の処理フローを説明する図である。
図に示すように、ステップＳ８１０において、スタックに、経路情報及びリンク情報をプッシュする。ここで経路情報とは、接続数、累積コスト、経路リスト及びその書込位置であり、リンク情報とは、次のノード番号、接続先リンク番号、接続コスト、接続先リンク番号の指すリンク接続先テーブルの内容及びリンク接続先テーブルのリンク情報の読出位置である。ステップＳ８１０の最初の処理では、図８Ａに示すステップＳ８０１〜ステップＳ８０４ａで設定された内容がスタックにプッシュされる。
【００７７】
次にステップＳ８１１で、接続先リンク番号の指すリンク接続先テーブルの内容を読み出す。具体例における最初の処理では、図８Ａに示すステップＳ８０４において、接続先リンク番号に始点リンク番号であるＬ１が設定されているので、リンク接続先テーブル３０９ｂの先頭の行であるリンク番号２３２がＬ１の行の内容が読み出される。
【００７８】
次にステップＳ８１２において、次のノード番号はステップＳ８１１で読み出したリンク接続先テーブルのＡ端のノード番号と一致するか判定する。一致すればステップＳ８１３に進み、一致しなければ、ステップＳ８２１へ分岐する。具体例における最初の処理では、Ａ端のノード番号２３４はＮ１であり、次のノード番号には図８Ａに示すステップＳ８０３で始点ノード番号であるＮ１が設定されているので、一致すると判定され、ステップＳ８１３に進む。一致しないと判定されるのは、図７の（ａ）に示す経路展開のうち、点線の矢印で示す経路展開なしとなる場合である。
【００７９】
ステップＳ８１３では、経路情報の接続数に１を加え、累積コストに接続コストとステップＳ８１１で読み出したリンク接続先テーブルのＢ端へのコストを加えると共に、経路情報の経路リストの書込位置に次のノード番号と接続先リンク番号を書き込み、書込位置を更新する。ここで接続コストは、図８Ａに示すステップＳ８０４で初期設定されているか、あるいは後記ステップＳ８１８で設定されたものである。また、経路情報は、図７の（ｂ）に示す経路情報テーブル２８１の１行分の項目を持つ一次記憶領域である。具体例における最初の処理では、経路情報の接続数と累積コストには、図８Ａに示すステップＳ８０２で値“−１”と“０”がそれぞれ初期設定されており、リンク接続先テーブルの初期化されたリンク情報の読出位置のＢ端へのコスト２３４ａには１が格納されているので、経路情報の接続数と累積コストは、それぞれ０と１になる。また、経路情報の経路リストの先頭位置に、図８Ａに示すステップＳ８０２とステップＳ８０３で初期設定されている次のノード番号Ｎ１と接続先リンク番号Ｌ１が書き込まれる。
【００８０】
次にステップＳ８１４に進み、ステップＳ８１１で読み出したリンク接続先テーブルのＢ端のノード番号が終点ノード番号と一致するか判定し、Ｂ端のノード番号は終点ノード番号と一致しないと判定されると、ステップＳ８１５に分岐する。ステップＳ８１５では、Ｂ端のノードの接続先リンク情報は存在するか判定する。この判定を行うのは、経路に行き止まりのリンクがあるとそのＢ端のノードの接続先リンク情報は存在しないことから、前に述べたように経路の展開ができないので、その場合には後記ステップＳ８２１に分岐するためである。
【００８１】
一方、ステップＳ８１５で接続先リンク情報が存在すると判定されるとステップＳ８１６に進み、次のノード番号にＢ端のノード番号を設定し、ステップＳ８１７において、リンク情報の読出位置に、リンク接続先テーブルのＢ端のノードの接続先リンク情報の先頭位置を設定する。このリンク情報の読出位置の設定により、経路探索の優先順位が決定され、具体例の経路探索ツリーについて説明したように、ツリーの右側優先で経路が探索される。
ステップＳ８１７に続いてステップＳ８１８で、リンク情報の読出位置の指すステップＳ８１１で読み出したリンク接続先テーブルのＢ端のノードの接続先リンク情報より、接続先リンク番号と接続コストを取り出して設定する。具体例における最初の処理では、Ｂ端のノードの接続先リンク情報からリンク２３８ａとコスト２３９ａとして格納されているＬ２と１が取り出され、接続先リンク番号と接続先コストに設定され、ステップＳ８１０に戻る。
【００８２】
以上のステップＳ８１０〜ステップＳ８１８のループ処理を、ステップＳ８１２での判定結果が次のノード番号はＡ端のノード番号と一致しない（以下、枝刈り判定ということがある。）となるか、ステップＳ８１４での判定結果が終点ノード番号はＢ端のノード番号と一致する（以下、終点判定ということがある。）となる、あるいはステップＳ８１８での判定結果が接続先リンク情報は存在しない（以下、行き止まり判定ということがある。）となるまで繰り返す。
【００８３】
ステップＳ８１４での判定結果が終点判定であるとステップＳ８２０に進み、経路情報の経路リストの書込位置に終点ノード番号を書き込むと共に、経路情報テーブルに経路情報を順次書き込み、ステップＳ８２１に進む。ここで経路情報テーブルに経路情報を順次書き込むとは、終点ノードまでの経路情報を、終点毎に順次行を変えながら経路情報テーブルに書き込むことである。
【００８４】
ステップＳ８２１では、スタックから、経路情報及びリンク情報をポップしてステップＳ８２２に進む。スタックには、ステップＳ８１０〜ステップＳ８１８のループ処理において、ステップＳ８１０で、スタックに経路情報及びリンク情報をプッシュしている。つまり、経路展開ツリーの経路展開ノードを生成する毎に生成された経路展開ノードについての経路情報とリンク情報をスタックにプッシュしている。
【００８５】
そして、上述のループ処理のうちステップＳ８１１以降では、経路情報とリンク情報をスタックにプッシュした経路展開ノードの下位の経路展開ノードについての処理を行っており、枝刈り判定、終点判定あるいは行き止まり判定も下位の経路展開ノードについて行っているので、上記ループ処理から分岐して実行されるステップＳ８２１の処理でポップされる経路情報及びリンク情報は、枝刈り判定、終点判定あるいは行き止まり判定が行われた経路展開ノードの上位の経路展開ノードについてのものである。
【００８６】
ステップＳ８２２では、スタックが空であるか判定し、スタックが空であれば経路展開は完了しているので処理を終了し、空でなければステップＳ８２３に進む。ステップＳ８２２でスタックが空と判定されるのは、図７の（ａ）の例示では、経路が終点２４７ｇまで展開されたときである。
【００８７】
ステップＳ８２３では、ステップＳ８２１でポップされたリンク接続先テーブルのＢ端のノードの接続先リンク情報は全て処理済みか判定する。全て処理済みであればステップＳ８２１に戻りさらにスタックから、もう一段上位の経路展開ノードについての経路情報及びリンク情報をポップする。全て処理済みでなければステップＳ８２４に進み、リンク情報の読出位置に次の読出位置を設定してステップＳ８１８に進み、上述のループ処理に合流する。
【００８８】
以上の処理により、始点ノードから終点ノードへの全ての経路が展開され、終点ノードに至る経路情報が生成される。
なお、上述の説明は、始点ノードをリンク接続先テーブルのＡ端のノードのノード番号のものとしたが、始点ノードをＢ端のノードのノード番号のものとする場合には、上述の説明のＡ端をＢ端と、Ｂ端をＡ端と読み替えればよいことは明らかである。
また、経路展開中の経路情報及びリンク情報をスタックにより保持するとして説明したが、経路展開中の経路情報及びリンク情報をどの段階のものであるか識別可能な形式で記憶するものであれば、経路展開中の経路情報及びリンク情報の保持はスタックに限るものではない。
【００８９】
図８Ｃは、本発明の一実施の形態における最適経路を決定する処理フローを説明する図である。図７の（ｂ）に例示した経路情報テーブル２８１を適宜参照しつつ説明する。
図に示すように、ステップＳ８３１で最小接続数と最小累積コストの値にそれぞれ最大値（ビット値でいえばオール１）を設定する。またステップＳ８３２で経路情報テーブルの先頭位置を経路情報の読出位置に設定する。次にステップＳ８３３で、経路情報テーブルの先頭位置を最適経路情報の読出位置に設定する。図７の（ｂ）の例示では、終点２４７ｍに対応する経路情報の位置が経路情報の読出位置と最適経路情報の読出位置に初期設定される。
【００９０】
次にステップＳ８３４に進み、経路情報テーブルは全て処理済みか判定する。処理済みでなければ、ステップＳ８３５において、経路情報の読出位置の指す経路情報テーブルより、接続数と累積コストを読み出す。次にステップＳ８３６で、読み出した累積コストと最小累積コストとの大小関係を判定し、累積コストが最小累積コストより小さければステップＳ８３７に分岐して、最小累積コストにステップＳ８３５で読み出した累積コストを設定する。ステップＳ８３６の最初の判定処理においては、最小累積コストにはステップＳ８３１において最大値が設定されていることからステップＳ８３７に分岐し、最小累積コストに経路情報テーブルの先頭位置の累積コストを設定し、ステップＳ８４０に進む。
【００９１】
一方、累積コストが最小累積コストと等しければステップＳ８３６からステップＳ８３８に進み、さらに接続数は最小接続数より小さいか判定する。ステップＳ８３８での判定結果が「はい」であれば、ステップＳ８３９で最小接続数に接続数を設定してステップＳ８４０に進む。
ステップＳ８４０では、最適経路情報の読出位置に、経路情報の読出位置を設定してステップＳ８４１に進む。
ステップＳ８３８での判定結果が「いいえ」であれば、ステップＳ８４１に進む。
また、ステップＳ８３６で、累積コストが最小累積コストより大きいと判定されるとステップＳ８４１に進む。
ステップＳ８４１では、経路情報の読出位置を、次の読出位置に設定してステップＳ８３４に戻る。
【００９２】
上述のステップＳ８３４で、経路情報テーブルは全て処理済みと判定されるとステップＳ８４２において、最適経路情報の読出位置の指す経路情報テーブルを読み出し、最適経路情報として出力して処理を終了する。
【００９３】
以上本発明を実施するための最良の形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
また、本発明のネットワーク経路探索装置が、リンク接続先テーブルを格納する記憶手段と図８Ａ〜図８Ｃに示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。
【００９４】
さらに、図５に示した経路探索のためのデータ構造を作成する処理とその均等物をコンピュータに実行させるプログラムにより、本発明のデータ構造作成方法が実現可能であることも明らかである。そして、それらのプログラムにより、本発明のデータ構造を作成する手段等がコンピュータ上に実現される。
したがって、上記プログラム、及びプログラムを記録したコンピュータ読み取り可能な記録媒体は、本発明の実施の形態に含まれる。さらに、本発明の経路探索のためのデータ構造及びそのデータ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体も、本発明の実施の形態に含まれる。
以上詳細に説明した本発明が提供する新しいデータ構造であるリンク接続先テーブルを用いることにより、効率的にネットワークの経路探索を行うことが可能となる。
本発明は、それに限るわけではないが、カーナビゲーション装置のような小型のコンピュータを搭載した装置の最適経路探索に適用すると効果が大きいものである。
【図面の簡単な説明】
【００９５】
【図１】ネットワーク構成例とそれを表現する従来のデータ構造を説明する図である。
【図２Ａ】本発明の一実施の形態におけるネットワーク表現用のデータ構造を作成するための機能ブロックを説明する図である。
【図２Ｂ】本発明の一実施の形態におけるネットワークの経路探索のための機能ブロックを説明する図である。
【図３】本発明の一実施の形態におけるハードウェア構成例を説明する図である。
【図４Ａ】本発明の一実施の形態におけるネットワークを表現するデータ構造を説明する図である。
【図４Ｂ】従来のネットワーク表現データから本発明の一実施形態におけるネットワーク表現データを生成する概念を説明する図である。
【図５】本発明の一実施の形態におけるネットワーク表現のためのデータ構造を作成する処理フローを説明する図である。
【図６】本発明の一実施の形態におけるネットワーク探索におけるコスト設定例を説明する図である。
【図７】本発明の一実施の形態におけるネットワークの経路探索の概念を説明する図である。
【図８Ａ】本発明の一実施の形態におけるネットワークの最適経路を探索する処理の概略フローを説明する図である。
【図８Ｂ】本発明の一実施の形態におけるネットワーク経路探索の処理フローを説明する図である。
【図８Ｃ】本発明の一実施の形態における最適経路を決定する処理フローを説明する図である。
【符号の説明】
【００９６】
１０ ノード
１２ リンク
１１１ 交差点テーブル
１２１ リンクテーブル
１３１ ノードテーブル
２０１ データ構造読取手段
２０２ リンク接続先テーブル生成手段
２０５ 経路条件設定手段
２０６ 経路探索手段
２０７ 最適経路出力手段
３０１ データ処理装置
３０２ 中央処理装置
３０３ キャッシュメモリ
３０４ バス
３０５ 主記憶装置
３０６ 外部記憶装置
３０７ 通信装置
３０８ データ格納装置
３０９ リンク接続先テーブル
【技術分野】
【０００１】
本発明は、ネットワーク経路探索装置、方法及びプログラムに関し、特にネットワークを表現する新規なデータ構造に基づくネットワーク経路探索装置、方法及びプログラム、さらにはネットワークを表現する新規なデータ構造を作成する手法に関する。
【背景技術】
【０００２】
道路網、通信網、あるいは配管ネットワーク等の物理的ネットワークを論理的なネットワークで表現し、コンピュータ上で最適経路を求めたり配送コストを計算したりすることが行われている。そのようなネットワーク関連の技術を適用した車両走行案内装置が下記特許文献１に開示されている。
従来の論理的ネットワーク（以下、単にネットワークという。）は、特許文献１の表１及び表２に記載されているように、ネットワーク要素としてノードとノード間を接続するリンクのそれぞれが定義されているとみることができる。そして、ノードとリンクの属性に関するデータによりネットワークが表現され、そのネットワーク表現に基づいて、経路探索等が行われている。
【０００３】
図１は、ネットワーク構成例とそれを表現する従来のデータ構造を説明する図である。図１の（ａ）に示すのは、道路網をモデル化したノード１０（Ｎ１〜Ｎ６）と各ノード間を接続するリンク１２（Ｌ１〜Ｌ８）からなるネットワークの構成例である。ノードの符号１０は、ノードＮ１にのみ付され、他は省略している。リンクの符号１２についても、リンクＬ５にのみ付され、他は省略している。図に示すように、リンクＬ１はノードＮ１とノードＮ２を接続し、リンクＬ２はノードＮ２とノードＮ３を、リンクＬ３はノードＮ２とノードＮ４を接続している。リンクＬ４はノードＮ３とノードＮ４を接続し、リンクＬ５はノードＮ３とノードＮ５を接続している。また、リンクＬ６はノードＮ４とノードＮ５を、リンクＬ７はノードＮ４とノードＮ６を、リンクＬ８はノードＮ５とノードＮ６を接続している。
【０００４】
図１の（ｂ）に示すのは、図１の（ａ）に示すネットワークを表現する従来のデータ構造の例であり、交差点テーブル１１１、リンクテーブル１２１及びノードテーブル１３１を備えている。
交差点テーブル１１１は、交差点であるノードとそれに接続された道路であるリンクを関係づけたものであり、ノードのノード番号１１２に対応してノードに接続されたリンクのリンク番号１１４が格納されている。図の例では、ノード番号Ｎ１に対してリンク番号Ｌ１が、ノード番号Ｎ２に対してリンク番号Ｌ１、Ｌ２、Ｌ３が、記載されている。以下同様に、Ｎ３に対してＬ２、Ｌ４、Ｌ５が、Ｎ４に対してＬ３、Ｌ４、Ｌ６、Ｌ７が、Ｎ５に対してＬ５、Ｌ６、Ｌ７が、Ｎ６に対してＬ７、Ｌ８が格納されている。なお、メモリ上に存在するのはＮ１の行からＮ６の行にかけての部分であることは当然である。以下で説明する他のテーブルについても同様である。
【０００５】
リンクテーブル１２１は、リンクとその両端のノードを関係づけたものであり、リンク番号１２２に対して該リンク番号１２２のリンクに接続された片方のノードのノード番号１２３ともう一方のノードのノード番号１２４が格納されている。図の例では、リンク番号Ｌ１に対してノード番号Ｎ１とノード番号Ｎ２が、リンク番号Ｌ２に対してノード番号Ｎ２とノード番号Ｎ３が片方のノード番号１２３ともう一方のノード番号１２４として格納されている。以下同様に、Ｌ３に対してＮ２とＮ４が、Ｌ４に対してＮ３とＮ４が、Ｌ５に対してＮ３とＮ５が、Ｌ６に対してＮ４とＮ５が、Ｌ７に対してＮ４とＮ６が、Ｌ８に対してＮ５とＮ６が格納されている。
【０００６】
ノードテーブル１３１は、ノード番号１３２とノード情報１３３の項目からなり、各ノードのノード番号Ｎ１〜Ｎ６毎に各ノードの位置等のノード情報を格納したものである。なお、ノード情報の具体例については省略されている。
【特許文献１】特開平７−１４６１５５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来のネットワーク表現においては、ノードとリンクの双方をネットワークの構成要素とし、複数のテーブルを備えており、経路探索を行うとき、これらの複数のテーブルを順次参照することが必要となるため、経路探索を行うときの処理コストが高いという欠点を有する。
【０００８】
そこで本発明が解決しようとする課題は、経路探索時の処理負荷の小さいネットワーク表現のためのデータ構造と、それを用いた経路探索手法を提供することである。
【課題を解決するための手段】
【０００９】
本発明によれば、ネットワークの各リンクのリンク番号に対して、リンクの片方のノード（以下、Ａ端のノードということがある。）のノード番号と、そのノードに接続された他のリンクのリンク番号である片方のノードの接続先リンク番号と、リンクのもう一方のノード（以下、Ｂ端のノードということがある。）のノード番号と、そのノードに接続された他のリンクのリンク番号であるもう一方のノードの接続先リンク番号と、を格納したリンク接続先テーブルを、ネットワークを表現するデータ構造として提供する。
【００１０】
リンク接続先テーブルは、さらに各リンクのＡ端のノードからＢ端のノードへのコスト及びＢ端のノードからＡ端のノードへのコスト、すなわちリンクのコストを備える。さらに、本発明の好適な実施の形態によれば、リンク接続先テーブルは、各リンクからＡ端及びＢ端のノードの接続先リンク番号に格納されたリンク番号のリンクに接続するコストを格納することができる。リンク接続先テーブルに格納されたリンクとその接続先リンクをたどることにより始点から終点への経路を探索し、各経路のコストを計算して最適経路探索を行う。
【００１１】
すなわち、始点側のノードをＡ端のノードとすると、経路探索は、始点側のノードに係るリンクからスタートし、そのリンク番号の行に格納されたリンク接続先テーブルのＢ端のノードの接続先リンク番号のリンクに分岐し、さらにリンク接続先テーブルの、それらの分岐したリンクのリンク番号の行に格納されたＢ端のノードの接続先リンク番号のリンクに分岐することを終点のノードをＢ端のノードとするリンクまで、コストを計算しながら繰り返すことで行う。そして、始点から終点までの経路のうち、最適な経路を探索結果として出力する。
【発明の効果】
【００１２】
本発明のネットワーク表現のためのデータ構造によれば、リンク接続先テーブルを用いるだけであり、経路探索における経路の分岐はリンク番号のみを参照して行うことができるので、処理コストを小さくすることができる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明を実施するための最良の形態を、図面を参照しながら説明する。
図２Ａは、本発明の一実施の形態におけるネットワーク表現用のデータ構造を作成するための機能ブロックを説明する図である。図１に示す従来のデータ構造を有するデータをデータ構造読取手段２０１で読み取り、リンク接続先テーブル生成手段２０２がそのデータに基づきリンク接続先テーブルを生成する。
【００１４】
図２Ｂは、本発明の一実施の形態におけるネットワークの経路探索のための機能ブロックを説明する図である。ネットワークの経路探索要求に基づき、経路条件設定手段２０５が経路探索要求されたネットワークに対応するリンク接続先テーブル、始点ノード、終点ノード等の経路条件を設定する。経路探索手段２０６は、経路条件設定手段で設定された条件に基づいて経路を探索するとともに、それらの経路のコストを計算する。最適経路出力手段２０７は、経路探索手段２０６で探索された経路のうち、最適なコストの経路を探索結果として出力する。
【００１５】
図３は、本発明の一実施の形態におけるハードウェア構成例を説明する図である。
本発明のネットワーク経路探索装置による経路探索処理及びネットワーク表現用のデータ構造生成処理は中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。リンク接続テーブル３０９を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。
【００１６】
図２Ａ及び図２Ｂを参照して説明したデータ構造取出手段２０１等の各機能ブロックは、図３に例示するハードウェアと後に説明するステップを備えたソフトウェアにより実現可能である。
【００１７】
図３の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできる。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられることは当然である。以下の説明では、一時記憶領域に格納されたあるいは設定された値を一時記憶領域の名前で呼ぶことがある。
【００１８】
図４Ａは、本発明の一実施の形態におけるネットワークを表現するデータ構造を説明する図である。コストについては省略している。図に示すように、リンク接続先テーブル３０９ａは、リンク番号２３２、片方のノードのノード番号２３４、片方のノードの接続先リンク番号２３５、もう一方のノードのノード番号２３７及びもう一方のノードの接続先リンク番号２３８の項目を有している。
【００１９】
各項目の値は、図１の（ａ）に示すネットワーク構成例に対応するものである。リンク番号２３２のＬ１に対応して、片方のノードのノード番号２３４にＮ１、もう一方のノードのノード番号２３７にＮ２、もう一方のノードの接続先リンク番号２３８にＬ２とＬ３が格納され、片方のノードの接続先リンク番号２３５には何も格納されていない。
【００２０】
リンク番号２３２のＬ２に対応しては、片方のノードのノード番号２３４にＮ２、片方のノードの接続先リンク番号２３５にＬ１とＬ３、もう一方のノードのノード番号２３７にＮ３、もう一方のノードの接続先リンク番号２３８にＬ４とＬ５が格納されている。
【００２１】
以下同様に、各リンク番号２３２のＬ３、Ｌ４、Ｌ５、Ｌ６、Ｌ７、Ｌ８にそれぞれ対応して、片方のノードのノード番号２３４にＮ２、Ｎ３、Ｎ３、Ｎ４、Ｎ４、Ｎ５が、片方のノードの接続先リンク番号２３５にＬ１とＬ２、Ｌ２とＬ５、Ｌ２とＬ４、Ｌ３とＬ４とＬ７、Ｌ３とＬ４とＬ６、Ｌ５とＬ６が、もう一方のノードのノード番号２３７にＮ４、Ｎ４、Ｎ５、Ｎ５、Ｎ６、Ｎ６が、もう一方のノードの接続先リンク番号２３８にＬ４とＬ６とＬ７、Ｌ３とＬ６とＬ７、Ｌ６とＬ８、Ｌ５とＬ８、Ｌ８、Ｌ７が、格納されている。
【００２２】
図４Ｂは、従来のネットワーク表現データから本発明の一実施形態におけるネットワーク表現データを生成する概念を説明する図である。図に示す従来のデータ構造１００は、図１の（ｂ）に示すリンクテーブル１２１と交差点テーブル１１１の関連する一部の行を取り出して示している。図４Ｂに示す例では、矢印４０３で示すリンク番号１２２がＬ２である行をリンクテーブル１２１から取り出している。
【００２３】
本発明の一実施の形態におけるデータ構造２００は、図４Ａに示すリンク接続テーブル３０９ａのリンク番号２３２がＬ２の行である。従来のデータ構造１００のリンク番号１２２からの点線の矢印（Ａ）で示すように、従来のデータ構造１００のリンク番号１２２と同じリンク番号が、本発明の一実施の形態におけるデータ構造２００のリンク番号２３２に設定される。
【００２４】
矢印４０４で示すように、従来のデータ構造１００の片方のノード番号１２３のＮ２の行が交差点テーブル１１１から読み出され、点線の矢印（Ｂ）で示すように、ノード番号１１２ａのＮ２、点線の矢印（Ｄ）で示すようにリンク番号１１４ａのうちリンク番号１２２と同一でないＬ１とＬ３が、それぞれ本発明の一実施の形態におけるデータ構造２００の片方のノード番号２３４と片方のノードの接続先リンク番号２３５に設定される。
【００２５】
同様に、矢印４０５で示すように、従来のデータ構造１００のもう一方のノード番号１２４のＮ３の行が交差点テーブル１１１から読み出され、点線の矢印（Ｃ）で示すように、ノード番号１１２ｂのＮ３、点線の矢印（Ｅ）で示すようにリンク番号１１４ｂのうちリンク番号１２２と同一でないＬ４とＬ５が、それぞれ本発明の一実施の形態におけるデータ構造２００のもう一方のノード番号２３７ともう一方のノードの接続先リンク番号２３８に設定される。
【００２６】
図５は、本発明の一実施の形態におけるネットワーク表現のためのデータ構造を作成する処理フローを説明する図である。以下において、図１、図４Ａ及び図４Ｂの例示を参照しながら説明する。
【００２７】
まず、ステップＳ５０１でリンク接続先テーブル書込位置に、リンク接続先テーブルの先頭位置を設定する。図４Ａの例示では、リンク接続先テーブル３０９ａのリンク番号２３２がＬ１の行の先頭位置が設定される。ここでリンク接続先テーブル書込位置は、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域」の１つであり、リンク接続先テーブルの書込位置を設定する図示しない一時記憶領域である。以下の説明において、上述のリンク接続先テーブル書込位置と同様に、図示しない一時記憶領域をそこに格納されあるいは設定されるデータの内容により呼ぶことがある。
【００２８】
次にステップＳ５０２で、リンクテーブル読出位置に、リンクテーブルの先頭位置を設定する。図１の例示では、リンクテーブル１２１のリンク番号１２２がＬ１の行の先頭位置が設定される。
【００２９】
次にステップＳ５０３に進み、リンクテーブル読出位置の指すリンクテーブルよりリンク番号を取り出し、一時記憶領域であるリンク番号（以下、図５の説明に限り、Ａという。）に設定する。図４Ｂの例示では、矢印４０３で示すようにリンクテーブル読出位置のリンク番号１２２はＬ２であり、ＡにはＬ２が設定される。
【００３０】
次にステップＳ５０４に進み、リンクテーブル読出位置の指すリンクテーブルより片方のノード番号を読み出し、一時記憶領域である片方のノード番号（以下、図５の説明に限り、Ｂという。）に設定する。図４Ｂの例示では、リンクテーブル読出位置の片方のノード番号１２３はＮ２であり、ＢにはＮ２が設定される。
【００３１】
次にステップＳ５０５に進み、リンクテーブル読出位置の指すリンクテーブルよりもう一方のノード番号を読み出し、一時記憶領域であるもう一方のノード番号（以下、図５の説明に限り、Ｃという。）に設定する。図４Ｂの例示では、リンクテーブル読出位置のもう一方のノード番号１２４はＮ３であり、ＣにはＮ３が設定される。
【００３２】
次にステップＳ５０６に進み、Ｂの指す交差点テーブルよりＡを除いたリンク番号を読み出し、一時記憶領域である片方のノードの接続リンク番号（以下、図５の説明に限り、Ｄという。）に設定する。図４Ｂの例示では、矢印４０４で示すように、Ｂに設定されたＮ２の指す交差点テーブルのリンク番号はＬ１、Ｌ２、Ｌ３であり、Ａに設定されたＬ２を除くＬ１とＬ３がＤに設定される。
【００３３】
次にステップＳ５０７に進み、Ｃの指す交差点テーブルよりＡを除いたリンク番号を読み出し、一時記憶領域であるもう一方のノードの接続リンク番号（以下、図５の説明に限り、Ｅという。）に設定する。図４Ｂの例示では、矢印４０５で示すように、Ｃに設定されたＮ３の指す交差点テーブルのリンク番号はＬ２、Ｌ４、Ｌ５であり、Ａに設定されたＬ２を除くＬ４とＬ５がＥに設定される。
【００３４】
次にステップＳ５０８において、リンク接続先テーブル書込位置の指すリンク接続先テーブルの、リンク番号にＡを、片方のノード番号にＢを、もう一方のノード番号にＣを、片方のノードの接続先リンク番号にＤを、もう一方のノードの接続リンク先番号にＥを、それぞれ設定する。図４Ｂの例示では、矢印４０３と対応するリンク接続先テーブル書込位置のリンク番号２３２にＡに設定されたＬ２が、片方のノード番号２３４にＢに設定されたＮ２が、片方のノードの接続先リンク番号２３５にＤに設定されたＬ１とＬ３が、もう一方のノード番号２３７にＣに設定されたＮ３が、もう一方のノードの接続リンク先番号２３８にＥに設定されたＬ４とＬ５が、それぞれ設定されている。
【００３５】
次にステップＳ５０９において、リンクテーブル読出位置はリンクテーブルの末尾の位置か判定する。末尾の位置でなければ、ステップＳ５１０でリンク接続先テーブル書込位置に次の書込位置を設定し、ステップＳ５１１でリンクテーブル読出位置に次の読出位置を設定してステップＳ５０３に戻ってステップＳ５０３〜ステップＳ５０９の処理を繰り返す。
【００３６】
一方、ステップＳ５０９で、リンクテーブル読出位置はリンクテーブルの末尾の位置であると判定されると、リンク接続先テーブルは完成しているので処理を終了する。上述の処理フローのうち、ステップＳ５０２〜ステップＳ５１１を図２Ａに示すデータ構造読取手段２０１により実行し、ステップＳ５０１とステップＳ５０８をリンク接続先テーブル生成手段２０２により実行するもととすることができる。なお、上述の処理フローと各ステップの実行手段の対応は単なる一例であり、種々の変更が可能なことは明らかである。
【００３７】
以上の処理でリンク接続先テーブルが生成されるので、リンク接続先テーブルの生成に用いたデータは消去することも可能であるが、次に説明するネットワーク探索処理において、経路探索の始点に接続されたリンクを探す処理の便宜のために、交差点テーブルを残しておくことが好適である。
【００３８】
図６は、本発明の一実施の形態におけるネットワーク探索におけるコスト設定例を説明する図である。図６の（ａ）に示すのは、図１の（ａ）に示すネットワーク構成例のうち、ノードＮ２とＮ３及びそれらに接続されるリンクＬ１、Ｌ２、Ｌ３、Ｌ４、Ｌ５に関係する本発明の一実施の形態におけるコストの概念である。
【００３９】
図に示すように、リンク接続先テーブルのリンク番号２３２がＬ２であるとすると、片方のノード（Ａ端のノード）のノード番号２３４はＮ２、もう一方のノード（Ｂ端のノード）のノード番号２３７はＮ３である。このとき、リンクＬ２に対して、ノードＮ２からノードＮ３へのもう一方のノードへのコスト［２３４ａ］と、ノードＮ３からノードＮ２への片方のノードへのコスト［２３７ａ］が定義される。これらのコストを区間コストという。
【００４０】
本発明の一実施の形態においては、上述の区間コストに加えて、リンクのＡ端側とＢ端側のリンクへの接続コストを定義する。以下の実施の形態の説明では、接続コストが定義されるものとして説明する。図に示すように、Ａ端側において、リンク番号２３２がＬ２のリンクから、片方のノードの接続先リンク番号２３５ａがＬ１の接続先リンクへの接続コスト［２３６ａ］と片方のノードの接続先リンク番号２３５ｂがＬ３の接続先リンクへの接続コスト［２３６ｂ］が定義される。同様に、Ｂ端側において、もう一方のノードの接続先リンク番号２３８ａがＬ４の接続先リンクへの接続コスト［２３９ａ］ともう一方のノードの接続先リンク番号２３８ｂがＬ５の接続先リンクへの接続コスト［２３９ｂ］が定義される。
【００４１】
図６の（ｂ）に示すのは、図４Ａに例示したリンク接続先テーブル３０９ａに上述の区間コストと接続コストを付加したリンク接続先テーブル３０９ｂである。リンク番号２３２がＬ１〜Ｌ８のリンクに対して、Ｂ端へのコスト２３４ａの例として１、２、３、１、２、２、３、１が設定され、Ａ端へのコスト２３７ａの例として２、１、２、３、１、２、２、３が設定されている。
【００４２】
また、Ａ端のノードの接続先リンク情報として、リンク２３５ａへの接続コスト２３６ａ、リンク２３５ｂへの接続コスト２３６ｂ及びリンク２３５ｃへの接続コスト２３６ｃが設定されている。同様に、Ｂ端のノードの接続先リンク情報として、リンク２３８ａへの接続コスト２３９ａ、リンク２３８ｂへの接続コスト２３９ｂ及びリンク２３８ｃへの接続コスト２３９ｃが設定されている。
【００４３】
ただし、リンクＬ１のＡ端のノードであるＮ１はネットワーク上の片接続の端点であるので、図４Ａに示すリンク接続先テーブル３０９ａのリンクＬ１についての片方のノードの接続先リンク番号２３５には何も設定されておらず、したがって、リンク接続先テーブル３０９ｂのリンク番号Ｌ１に対応するＡ端のノードの接続先リンク情報は設定されていない。リンクＬ１のＢ端のノードの接続先リンク情報については、リンクＬ２への接続コストに１、リンクＬ３への接続コストに１が設定されている。
【００４４】
リンクＬ２については、Ａ端のノードの接続先リンク情報としてリンクＬ１への接続コストに２、リンクＬ３への接続コストに１が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ４への接続コストに１、リンクＬ５への接続コストに１が設定されている。
【００４５】
リンクＬ３については、Ａ端のノードの接続先リンク情報としてリンクＬ１への接続コストに３、リンクＬ２への接続コストに２が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ４への接続コストに２、リンクＬ６への接続コストに２、リンクＬ７への接続コストに２が設定されている。
【００４６】
リンクＬ４については、Ａ端のノードの接続先リンク情報としてリンクＬ２への接続コストに１、リンクＬ５への接続コストに１が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ３への接続コストに２、リンクＬ６への接続コストに３、リンクＬ７への接続コストに３が設定されている。
【００４７】
リンクＬ５については、Ａ端のノードの接続先リンク情報としてリンクＬ２への接続コストに２、リンクＬ４への接続コストに２が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ６への接続コストに１、リンクＬ８への接続コストに２が設定されている。
【００４８】
リンクＬ６については、Ａ端のノードの接続先リンク情報としてリンクＬ３への接続コストに２、リンクＬ４への接続コストに３、リンクＬ７への接続コストに２が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ５への接続コストに２、リンクＬ８への接続コストに３が設定されている。
【００４９】
リンクＬ７については、Ａ端のノードの接続先リンク情報としてリンクＬ３への接続コストに３、リンクＬ４への接続コストに４、リンクＬ６への接続コストに１が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ８への接続コストに１が設定されている。
【００５０】
リンクＬ８については、Ａ端のノードの接続先リンク情報としてリンクＬ５への接続コストに２、リンクＬ６への接続コストに２が設定され、Ｂ端のノードの接続先リンク情報としてリンクＬ７への接続コストに２が設定されている。
【００５１】
上述のように、コストを区間コストと接続コストに分離して設定可能とすることにより、よりきめ細かく現実の物理ネットワークを模擬することができる。例えば道路網をモデル化する場合、道幅や速度制限等の比較的道路に固有の条件を区間コストに反映し、右折禁止や右折信号の有無など、道路と道路の間の通行条件を接続コストに反映することなどができる。
【００５２】
図７は、本発明の一実施の形態におけるネットワークの経路探索の概念を説明する図である。図７の（ａ）に示すのは、図１の（ａ）に例示するネットワークのノードＮ１を始点とし、ノードＮ６を終点とする経路探索において展開されるすべての経路であり、図７の（ｂ）に示すのは、上述の経路探索において作成される経路情報テーブルである。
始点ノードから終点ノードまでの経路は、その間を接続するリンク列で表現できることから、経路展開は、最初のリンクＬ１をルートとし、その接続先リンクを下位のノードとするツリーの形状で表すことができる。このツリーを経路展開ツリーと呼ぶことにすると、図７の（ａ）に示すものは、経路中のリンクに対して、Ａ端のノード番号２３４、リンク番号２３２、Ｂ端へのコスト２３４ａ及びＢ端のノード番号２３７を備えるノード（経路展開ノードということがある。）と下位の経路展開ノードに含まれるリンクへの接続コストを備えたブランチ（経路展開ブランチということがある。）を備えた経路展開ツリーである。したがって、ネットワークの経路探索は、経路展開ツリーを生成し、生成された経路から最適経路を探すことに相当する。
【００５３】
図に示すように、始点２４１としてノードＮ１が指定され、リンク接続先テーブル３０９ｂから、ノード番号Ｎ１を片方のノード（Ａ端のノード）のノード番号２３４とするリンク番号２３２としてＬ１が選ばれ、リンク番号Ｌ１の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ２が読み出され、経路展開ツリーのルートノードが生成される。Ｂ端のノードＮ２には、Ｎ２までの経路コスト２４２ａ［接続数、累積コスト］として「０、１」が計算されて付随している。
【００５４】
次にリンク番号Ｌ１の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報の先頭から、リンクＬ２への接続コスト２３９ａとしての１が読み出され、実線の矢印で示すように接続コストＬ２［１］が付随した経路展開ブランチが生成される。そして、リンク番号Ｌ２の指すリンク接続先テーブル３０９ｂからＡ端のノード番号２３４としてのＮ２とＢ端へのコスト２３４ａとして２が読み出され、さらにＢ端のノードのノード番号２３７としてＮ３が読み出され、Ｎ３までの経路コスト２４２ｂとして［１、４］が計算され、リンクＬ２に対応する経路展開ノードが生成される。ここで累積コスト４は、ノードＮ２までの累積コスト１にリンクＬ１からリンクＬ２への接続コスト１とリンク２の区間コスト２を加えたものである。
【００５５】
また同じく、リンク番号Ｌ１の指すリンク接続先テーブル３０９ｂからＢ端のノードの次の接続先リンク情報として、リンクＬ３への接続コスト２３９ｂとしての１が読み出され、さらにリンク番号Ｌ３の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして３が取り出され、さらにＢ端のノードのノード番号２３７としてＮ４が読み出され、Ｎ４までの経路コスト２４２ｃとして［１、５］が計算される。
【００５６】
リンクＬ２側の経路では、リンク番号Ｌ２の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ４への接続コスト２３９ａとしての１が読み出され、さらにリンク番号Ｌ４の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ４が読み出され、Ｎ４までの経路コスト２４２ｄとして［２、６］が計算される。
【００５７】
また同じくリンクＬ２側の経路では、リンク番号Ｌ２の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ５への接続コスト２３９ｂとしての１が読み出され、さらにリンク番号Ｌ５の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出され、Ｎ５までの経路コスト２４２ｅとして［２、７］が計算される。
【００５８】
一方リンクＬ３側の経路では、リンク番号Ｌ３の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ４への接続コスト２３９ａとしての２が読み出され、さらにリンク番号Ｌ４の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ４が読み出される。
【００５９】
このリンクＬ４への接続については、経路展開なし２４４ａの点線の矢印で示しているように、リンク番号Ｌ４の指すリンク接続先テーブル３０９ｂのＢ端のノード番号２３７に設定されているノード番号がＮ４であって、接続元のリンクＬ３のＢ端のノードＮ４に戻るので、最小コスト計算に不要な経路であることは自明であるから、ここでは経路展開を打ち切る。なお、接続先のリンクのＡ端のノードかＢ端のノードのどちらか一方は接続元もリンクのＢ端のノードと一致し、同一のリンクのＡ端のノードとＢ端のノードが一致することはないから、経路展開の打ち切りの判定は、接続先のリンクのＡ端のノードが接続元のリンクのＢ端のノードと一致するかにより行うことができる。
【００６０】
同じくリンクＬ３側の経路では、リンク番号Ｌ３の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ６への接続コスト２３９ｂとしての２が読み出され、さらにリンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出され、Ｎ５までの経路コスト２４２ｆとして［２、９］が計算される。
【００６１】
さらに同じくリンクＬ３側の経路では、リンク番号Ｌ３の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ７への接続コスト２３９ｃとしての２が読み出され、さらにリンク番号Ｌ７の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして３が取り出され、さらにＢ端のノードのノード番号２３７としてＮ６が読み出され、Ｎ６までの経路コスト２４２ｇとして［２、１０］が計算される。図に示すように、ノードＮ６はリンクＬ１、Ｌ３、Ｌ７の経路による終点２４７ｇである。
【００６２】
また、リンクＬ２、Ｌ４の経路では、リンク番号Ｌ４の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ３への接続コスト２３９ａとしての２が読み出され、さらにリンク番号Ｌ３の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして３が取り出され、さらにＢ端のノードのノード番号２３７としてＮ４が読み出される。したがって、リンクＬ４のＢ端のノードＮ４に戻るので、経路コストの計算は行わず、経路の展開も打ち切る。
【００６３】
同じくリンクＬ２、Ｌ４の経路では、リンク番号Ｌ４の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ６への接続コスト２３９ｂとしての３が読み出され、さらにリンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出され、Ｎ５までの経路コスト２４２ｈとして［３、１１］が計算される。
【００６４】
さらに同じくリンクＬ２、Ｌ４の経路では、リンク番号Ｌ４の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ７への接続コスト２３９ｃとしての３が読み出され、さらにリンク番号Ｌ７の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして３が取り出され、さらにＢ端のノードのノード番号２３７としてＮ６が読み出され、Ｎ６までの経路コスト２４２ｉとして［３、１２］が計算される。図に示すように、ノードＮ６はリンクＬ１、Ｌ２、Ｌ４、Ｌ７の経路による終点２４７ｉである。
【００６５】
また、リンクＬ２、Ｌ５の経路では、リンク番号Ｌ５の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ６への接続コスト２３９ａとしての１が読み出され、さらにリンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出される。したがって、リンクＬ５のＢ端のノードＮ５に戻るので、経路コストの計算は行わず、経路の展開も打ち切る。
【００６６】
同じくリンクＬ２、Ｌ５の経路では、リンク番号Ｌ５の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ８への接続コスト２３９ｂとしての２が読み出され、さらにリンク番号Ｌ８の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ６が読み出され、Ｎ６までの経路コスト２４２ｊとして［３、１０］が計算される。図に示すように、ノードＮ６はリンクＬ１、Ｌ２、Ｌ５、Ｌ８の経路による終点２４７ｊである。
【００６７】
また、リンクＬ３、Ｌ６の経路では、リンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ５への接続コスト２３９ａとしての２が読み出され、さらにリンク番号Ｌ５の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出される。したがって、リンクＬ６のＢ端のノードＮ５に戻るので、経路コストの計算は行わず、経路の展開も打ち切る。
【００６８】
同じくリンクＬ３、Ｌ６の経路では、リンク番号Ｌ８の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ８への接続コスト２３９ｂとしての３が読み出され、さらにリンク番号Ｌ８の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ６が読み出され、Ｎ６までの経路コスト２４２ｋとして［３、１３］が計算される。図に示すように、ノードＮ６はリンクＬ１、Ｌ３、Ｌ６、Ｌ８の経路による終点２４７ｋである。
【００６９】
また、リンクＬ２、Ｌ４、Ｌ６の経路では、リンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ５への接続コスト２３９ａとしての２が読み出され、さらにリンク番号Ｌ５の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして２が取り出され、さらにＢ端のノードのノード番号２３７としてＮ５が読み出される。したがって、リンクＬ６のＢ端のノードＮ５に戻るので、経路コストの計算は行わず、経路の展開も打ち切る。
【００７０】
同じくリンクＬ２、Ｌ４、Ｌ６の経路では、リンク番号Ｌ６の指すリンク接続先テーブル３０９ｂからＢ端のノードの接続先リンク情報として、リンクＬ８への接続コスト２３９ｂとしての３が読み出され、さらにリンク番号Ｌ８の指すリンク接続先テーブル３０９ｂからＢ端へのコスト２３４ａとして１が取り出され、さらにＢ端のノードのノード番号２３７としてＮ６が読み出され、Ｎ６までの経路コスト２４２ｍとして［４、１５］が計算される。図に示すように、ノードＮ６はリンクＬ１、Ｌ２、Ｌ４、Ｌ６、Ｌ８の経路による終点２４７ｍである。
【００７１】
以上により、ノードＮ１からノードＮ６への経路がすべて展開され、その接続数と累積コスト、及び経路リストを格納したものが、図７の（ｂ）に示す経路情報テーブル２８１である。経路情報テーブルは図７の（ａ）に示す終点２４７ｍ、２４７ｉ、２４７ｊ、２４７ｋ、２４７ｇに対応して、接続数として４、３、３、３、２が、累積コストとして１５、１２、１０、１３、１０が格納されている。また、Ａ端のノードのノード番号とリンク番号を組み合わせた経路リストには、図７の（ａ）に展開された経路に対応するものが格納されている。
なお、上述の経路展開の説明では、経路展開ツリーを上位の階層から説明したが、経路展開ツリーはリンク接続先テーブル３０９ｂに格納されたＢ端のノードの接続先リンク情報の位置（経路展開ツリー上では上側（右側））を優先させて生成させることができる。図７の（ｂ）に示す経路情報テーブルに格納された経路情報は、この順番で生成された経路展開ツリーによるものである。
【００７２】
以下、図８Ａ〜図８Ｃを参照して本発明の一実施の形態におけるネットワークの最適経路を探索する処理を説明する。この説明においては、経路展開ツリーの右側を優先させて生成するものとする。
図８Ａは、本発明の一実施の形態におけるネットワークの最適経路を探索する処理の概略フローを説明する図である。以下において、図１の（ａ）に示すネットワーク構成例、図６の（ｂ）に示すリンク接続先テーブル３０９ｂ、図７の（ｂ）に示す経路情報テーブル２８１等の具体例を適宜参照しながら説明する。その際、「具体例では、・・・」等の表記をすることがある。
【００７３】
まず、ステップＳ８０１において、リンク接続先テーブル、経路探索の始点ノード番号と始点リンク番号、及び終点ノード番号を設定する。リンク接続先テーブルの設定では、例えばリンク接続先テーブルの名称をシステム外部から指定することによりその先頭アドレスとサイズを設定する。また始点リンク番号の設定では、先に述べたように交差点テーブルから始点ノードに接続されたリンクのリンク番号を設定してもよい。
具体例では、始点ノード番号にＮ１、始点リンク番号にＬ１、終点ノード番号にＮ６、リンク接続先テーブルにリンク接続先テーブル３０９ｂが設定される。
【００７４】
次にステップＳ８０２において、経路情報の接続数に値“−１”を、累積コストに値“０”を設定し、ステップＳ８０３で次のノード番号に、始点ノード番号を設定する。
さらにステップＳ８０４で、接続先リンク番号に始点リンク番号を設定するとともに、接続コストに値“０”を設定し、ステップＳ８０４ａでリンク情報の読出位置を初期化してステップＳ８０５に進む。具体例では、次のノード番号にＮ１が、接続先リンク番号にＬ１が設定される。
【００７５】
ステップＳ８０５では、接続先リンク番号の指すリンク接続先テーブルを基に経路を探索し、ステップＳ８０６に進む。ステップＳ８０５の処理の詳細は、後に図８Ｂを参照して説明する。
ステップＳ８０６では、ステップＳ８０５で求めた探索結果より最適経路を出力し、処理を終了する。ステップＳ８０６の処理の詳細は、後に図８Ｃを参照して説明する。
なお、始点ノードに接続されたリンクが複数ある場合は、上述の処理によりそれぞれのリンクを始点リンクとした最適経路を求め、それらの最適経路からさらに最適経路を求めることができることは、当業者に明らかである。
【００７６】
図８Ｂは、図８Ａに示すステップＳ８０５の詳細な処理フローを示すものであり、本発明の一実施の形態におけるネットワークの経路探索の処理フローを説明する図である。
図に示すように、ステップＳ８１０において、スタックに、経路情報及びリンク情報をプッシュする。ここで経路情報とは、接続数、累積コスト、経路リスト及びその書込位置であり、リンク情報とは、次のノード番号、接続先リンク番号、接続コスト、接続先リンク番号の指すリンク接続先テーブルの内容及びリンク接続先テーブルのリンク情報の読出位置である。ステップＳ８１０の最初の処理では、図８Ａに示すステップＳ８０１〜ステップＳ８０４ａで設定された内容がスタックにプッシュされる。
【００７７】
次にステップＳ８１１で、接続先リンク番号の指すリンク接続先テーブルの内容を読み出す。具体例における最初の処理では、図８Ａに示すステップＳ８０４において、接続先リンク番号に始点リンク番号であるＬ１が設定されているので、リンク接続先テーブル３０９ｂの先頭の行であるリンク番号２３２がＬ１の行の内容が読み出される。
【００７８】
次にステップＳ８１２において、次のノード番号はステップＳ８１１で読み出したリンク接続先テーブルのＡ端のノード番号と一致するか判定する。一致すればステップＳ８１３に進み、一致しなければ、ステップＳ８２１へ分岐する。具体例における最初の処理では、Ａ端のノード番号２３４はＮ１であり、次のノード番号には図８Ａに示すステップＳ８０３で始点ノード番号であるＮ１が設定されているので、一致すると判定され、ステップＳ８１３に進む。一致しないと判定されるのは、図７の（ａ）に示す経路展開のうち、点線の矢印で示す経路展開なしとなる場合である。
【００７９】
ステップＳ８１３では、経路情報の接続数に１を加え、累積コストに接続コストとステップＳ８１１で読み出したリンク接続先テーブルのＢ端へのコストを加えると共に、経路情報の経路リストの書込位置に次のノード番号と接続先リンク番号を書き込み、書込位置を更新する。ここで接続コストは、図８Ａに示すステップＳ８０４で初期設定されているか、あるいは後記ステップＳ８１８で設定されたものである。また、経路情報は、図７の（ｂ）に示す経路情報テーブル２８１の１行分の項目を持つ一次記憶領域である。具体例における最初の処理では、経路情報の接続数と累積コストには、図８Ａに示すステップＳ８０２で値“−１”と“０”がそれぞれ初期設定されており、リンク接続先テーブルの初期化されたリンク情報の読出位置のＢ端へのコスト２３４ａには１が格納されているので、経路情報の接続数と累積コストは、それぞれ０と１になる。また、経路情報の経路リストの先頭位置に、図８Ａに示すステップＳ８０２とステップＳ８０３で初期設定されている次のノード番号Ｎ１と接続先リンク番号Ｌ１が書き込まれる。
【００８０】
次にステップＳ８１４に進み、ステップＳ８１１で読み出したリンク接続先テーブルのＢ端のノード番号が終点ノード番号と一致するか判定し、Ｂ端のノード番号は終点ノード番号と一致しないと判定されると、ステップＳ８１５に分岐する。ステップＳ８１５では、Ｂ端のノードの接続先リンク情報は存在するか判定する。この判定を行うのは、経路に行き止まりのリンクがあるとそのＢ端のノードの接続先リンク情報は存在しないことから、前に述べたように経路の展開ができないので、その場合には後記ステップＳ８２１に分岐するためである。
【００８１】
一方、ステップＳ８１５で接続先リンク情報が存在すると判定されるとステップＳ８１６に進み、次のノード番号にＢ端のノード番号を設定し、ステップＳ８１７において、リンク情報の読出位置に、リンク接続先テーブルのＢ端のノードの接続先リンク情報の先頭位置を設定する。このリンク情報の読出位置の設定により、経路探索の優先順位が決定され、具体例の経路探索ツリーについて説明したように、ツリーの右側優先で経路が探索される。
ステップＳ８１７に続いてステップＳ８１８で、リンク情報の読出位置の指すステップＳ８１１で読み出したリンク接続先テーブルのＢ端のノードの接続先リンク情報より、接続先リンク番号と接続コストを取り出して設定する。具体例における最初の処理では、Ｂ端のノードの接続先リンク情報からリンク２３８ａとコスト２３９ａとして格納されているＬ２と１が取り出され、接続先リンク番号と接続先コストに設定され、ステップＳ８１０に戻る。
【００８２】
以上のステップＳ８１０〜ステップＳ８１８のループ処理を、ステップＳ８１２での判定結果が次のノード番号はＡ端のノード番号と一致しない（以下、枝刈り判定ということがある。）となるか、ステップＳ８１４での判定結果が終点ノード番号はＢ端のノード番号と一致する（以下、終点判定ということがある。）となる、あるいはステップＳ８１８での判定結果が接続先リンク情報は存在しない（以下、行き止まり判定ということがある。）となるまで繰り返す。
【００８３】
ステップＳ８１４での判定結果が終点判定であるとステップＳ８２０に進み、経路情報の経路リストの書込位置に終点ノード番号を書き込むと共に、経路情報テーブルに経路情報を順次書き込み、ステップＳ８２１に進む。ここで経路情報テーブルに経路情報を順次書き込むとは、終点ノードまでの経路情報を、終点毎に順次行を変えながら経路情報テーブルに書き込むことである。
【００８４】
ステップＳ８２１では、スタックから、経路情報及びリンク情報をポップしてステップＳ８２２に進む。スタックには、ステップＳ８１０〜ステップＳ８１８のループ処理において、ステップＳ８１０で、スタックに経路情報及びリンク情報をプッシュしている。つまり、経路展開ツリーの経路展開ノードを生成する毎に生成された経路展開ノードについての経路情報とリンク情報をスタックにプッシュしている。
【００８５】
そして、上述のループ処理のうちステップＳ８１１以降では、経路情報とリンク情報をスタックにプッシュした経路展開ノードの下位の経路展開ノードについての処理を行っており、枝刈り判定、終点判定あるいは行き止まり判定も下位の経路展開ノードについて行っているので、上記ループ処理から分岐して実行されるステップＳ８２１の処理でポップされる経路情報及びリンク情報は、枝刈り判定、終点判定あるいは行き止まり判定が行われた経路展開ノードの上位の経路展開ノードについてのものである。
【００８６】
ステップＳ８２２では、スタックが空であるか判定し、スタックが空であれば経路展開は完了しているので処理を終了し、空でなければステップＳ８２３に進む。ステップＳ８２２でスタックが空と判定されるのは、図７の（ａ）の例示では、経路が終点２４７ｇまで展開されたときである。
【００８７】
ステップＳ８２３では、ステップＳ８２１でポップされたリンク接続先テーブルのＢ端のノードの接続先リンク情報は全て処理済みか判定する。全て処理済みであればステップＳ８２１に戻りさらにスタックから、もう一段上位の経路展開ノードについての経路情報及びリンク情報をポップする。全て処理済みでなければステップＳ８２４に進み、リンク情報の読出位置に次の読出位置を設定してステップＳ８１８に進み、上述のループ処理に合流する。
【００８８】
以上の処理により、始点ノードから終点ノードへの全ての経路が展開され、終点ノードに至る経路情報が生成される。
なお、上述の説明は、始点ノードをリンク接続先テーブルのＡ端のノードのノード番号のものとしたが、始点ノードをＢ端のノードのノード番号のものとする場合には、上述の説明のＡ端をＢ端と、Ｂ端をＡ端と読み替えればよいことは明らかである。
また、経路展開中の経路情報及びリンク情報をスタックにより保持するとして説明したが、経路展開中の経路情報及びリンク情報をどの段階のものであるか識別可能な形式で記憶するものであれば、経路展開中の経路情報及びリンク情報の保持はスタックに限るものではない。
【００８９】
図８Ｃは、本発明の一実施の形態における最適経路を決定する処理フローを説明する図である。図７の（ｂ）に例示した経路情報テーブル２８１を適宜参照しつつ説明する。
図に示すように、ステップＳ８３１で最小接続数と最小累積コストの値にそれぞれ最大値（ビット値でいえばオール１）を設定する。またステップＳ８３２で経路情報テーブルの先頭位置を経路情報の読出位置に設定する。次にステップＳ８３３で、経路情報テーブルの先頭位置を最適経路情報の読出位置に設定する。図７の（ｂ）の例示では、終点２４７ｍに対応する経路情報の位置が経路情報の読出位置と最適経路情報の読出位置に初期設定される。
【００９０】
次にステップＳ８３４に進み、経路情報テーブルは全て処理済みか判定する。処理済みでなければ、ステップＳ８３５において、経路情報の読出位置の指す経路情報テーブルより、接続数と累積コストを読み出す。次にステップＳ８３６で、読み出した累積コストと最小累積コストとの大小関係を判定し、累積コストが最小累積コストより小さければステップＳ８３７に分岐して、最小累積コストにステップＳ８３５で読み出した累積コストを設定する。ステップＳ８３６の最初の判定処理においては、最小累積コストにはステップＳ８３１において最大値が設定されていることからステップＳ８３７に分岐し、最小累積コストに経路情報テーブルの先頭位置の累積コストを設定し、ステップＳ８４０に進む。
【００９１】
一方、累積コストが最小累積コストと等しければステップＳ８３６からステップＳ８３８に進み、さらに接続数は最小接続数より小さいか判定する。ステップＳ８３８での判定結果が「はい」であれば、ステップＳ８３９で最小接続数に接続数を設定してステップＳ８４０に進む。
ステップＳ８４０では、最適経路情報の読出位置に、経路情報の読出位置を設定してステップＳ８４１に進む。
ステップＳ８３８での判定結果が「いいえ」であれば、ステップＳ８４１に進む。
また、ステップＳ８３６で、累積コストが最小累積コストより大きいと判定されるとステップＳ８４１に進む。
ステップＳ８４１では、経路情報の読出位置を、次の読出位置に設定してステップＳ８３４に戻る。
【００９２】
上述のステップＳ８３４で、経路情報テーブルは全て処理済みと判定されるとステップＳ８４２において、最適経路情報の読出位置の指す経路情報テーブルを読み出し、最適経路情報として出力して処理を終了する。
【００９３】
以上本発明を実施するための最良の形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
また、本発明のネットワーク経路探索装置が、リンク接続先テーブルを格納する記憶手段と図８Ａ〜図８Ｃに示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。
【００９４】
さらに、図５に示した経路探索のためのデータ構造を作成する処理とその均等物をコンピュータに実行させるプログラムにより、本発明のデータ構造作成方法が実現可能であることも明らかである。そして、それらのプログラムにより、本発明のデータ構造を作成する手段等がコンピュータ上に実現される。
したがって、上記プログラム、及びプログラムを記録したコンピュータ読み取り可能な記録媒体は、本発明の実施の形態に含まれる。さらに、本発明の経路探索のためのデータ構造及びそのデータ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体も、本発明の実施の形態に含まれる。
以上詳細に説明した本発明が提供する新しいデータ構造であるリンク接続先テーブルを用いることにより、効率的にネットワークの経路探索を行うことが可能となる。
本発明は、それに限るわけではないが、カーナビゲーション装置のような小型のコンピュータを搭載した装置の最適経路探索に適用すると効果が大きいものである。
【図面の簡単な説明】
【００９５】
【図１】ネットワーク構成例とそれを表現する従来のデータ構造を説明する図である。
【図２Ａ】本発明の一実施の形態におけるネットワーク表現用のデータ構造を作成するための機能ブロックを説明する図である。
【図２Ｂ】本発明の一実施の形態におけるネットワークの経路探索のための機能ブロックを説明する図である。
【図３】本発明の一実施の形態におけるハードウェア構成例を説明する図である。
【図４Ａ】本発明の一実施の形態におけるネットワークを表現するデータ構造を説明する図である。
【図４Ｂ】従来のネットワーク表現データから本発明の一実施形態におけるネットワーク表現データを生成する概念を説明する図である。
【図５】本発明の一実施の形態におけるネットワーク表現のためのデータ構造を作成する処理フローを説明する図である。
【図６】本発明の一実施の形態におけるネットワーク探索におけるコスト設定例を説明する図である。
【図７】本発明の一実施の形態におけるネットワークの経路探索の概念を説明する図である。
【図８Ａ】本発明の一実施の形態におけるネットワークの最適経路を探索する処理の概略フローを説明する図である。
【図８Ｂ】本発明の一実施の形態におけるネットワーク経路探索の処理フローを説明する図である。
【図８Ｃ】本発明の一実施の形態における最適経路を決定する処理フローを説明する図である。
【符号の説明】
【００９６】
１０ ノード
１２ リンク
１１１ 交差点テーブル
１２１ リンクテーブル
１３１ ノードテーブル
２０１ データ構造読取手段
２０２ リンク接続先テーブル生成手段
２０５ 経路条件設定手段
２０６ 経路探索手段
２０７ 最適経路出力手段
３０１ データ処理装置
３０２ 中央処理装置
３０３ キャッシュメモリ
３０４ バス
３０５ 主記憶装置
３０６ 外部記憶装置
３０７ 通信装置
３０８ データ格納装置
３０９ リンク接続先テーブル
【特許請求の範囲】
【請求項１】
ノードとノード間を結ぶリンクからなるネットワークの経路を探索し最適経路を出力するネットワーク経路探索装置において、
ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と、該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、前記各リンクのもう一方のノードを識別するもう一方のノード番号と、該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストを格納するリンク接続先テーブルと、
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号を設定する経路条件設定手段と、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索手段と、
前記経路探索手段が展開した全ての経路から前記経路のコストに基づいて最適経路を選択して出力する最適経路出力手段と、
を備えることを特徴とするネットワーク経路探索装置。
【請求項２】
請求項１に記載のネットワーク経路探索装置において、
前記リンク接続先テーブルは、前記片方のノードの接続先リンク番号と前記もう一方のノードの接続先リンク番号のそれぞれに対応して前記ネットワークの各リンクから前記片方のノードの接続先リンク番号のリンクあるいは前記もう一方のノードの接続先リンク番号のリンクに接続するコストである接続コストを格納するものであり、
前記経路探索手段は、経路のコストの計算において前記区間コストに加えて該経路の接続コストを累積することを特徴とするネットワーク経路探索装置。
【請求項３】
請求項２に記載のネットワーク経路探索装置において、
前記経路探索手段は、前記経路の展開において、前記始点リンクに接続されるリンク数である接続数を累積し、
前記最適経路出力手段は最適経路として同一のコストの経路が複数展開された場合には、該複数展開された経路から前記接続数に基づいて最適経路を選択して出力することを特徴とするネットワーク経路探索装置。
【請求項４】
請求項２に記載のネットワーク経路探索装置において、
経路探索手段は、前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照してさらに前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことに加えて片方のノード番号を読み出すものであり、該片方のノード番号が先に読み出した前記もう一方のノード番号と一致しないときには、前記さらに読み出されたもう一方のノードの接続先リンク番号による経路展開は行わないことを特徴とするネットワーク経路探索装置。
【請求項５】
請求項４に記載のネットワーク経路探索装置において、
前記接続先リンク番号により参照したリンク接続先テーブルに前記もう一方のノードの接続先リンク番号が存在しないとき、該接続先リンク番号による経路展開は行わないことを特徴とするネットワーク経路探索装置。
【請求項６】
請求項２に記載のネットワーク経路探索装置において、
前記ネットワークは道路網をモデル化したものであることを特徴とするネットワーク経路探索装置。
【請求項７】
請求項６記載のネットワーク経路探索装置を備えたことを特徴とするカーナビゲーション装置。
【請求項８】
請求項７記載のカーナビゲーション装置を備えたことを特徴とする車両。
【請求項９】
ノードとノード間を結ぶリンクからなるネットワークの経路を探索し最適経路を出力するネットワーク経路探索装置であって、ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と、該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、前記各リンクのもう一方のノードを識別するもう一方のノード番号と、該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストを格納するリンク接続先テーブルを備えたネットワーク経路探索装置によるネットワーク経路探索方法おいて、
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号を設定する経路条件設定ステップと、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索ステップと、
前記経路探索ステップで展開した全ての経路から前記経路のコストに基づいて最適経路を選択して出力する最適経路出力ステップと、
を備えることを特徴とするネットワーク経路探索方法。
【請求項１０】
請求項９に記載のネットワーク経路探索方法において、
前記リンク接続先テーブルは、前記片方のノードの接続先リンク番号と前記もう一方のノードの接続先リンク番号のそれぞれに対応して前記ネットワークの各リンクから前記片方のノードの接続先リンク番号のリンクあるいは前記もう一方のノードの接続先リンク番号のリンクに接続するコストである接続コストを格納するものであり、
前記経路探索ステップは、経路のコストの計算において前記区間コストに加えて該経路の接続コストを累積することを特徴とするネットワーク経路探索方法。
【請求項１１】
ノードとノード間を結ぶリンクからなるネットワークの経路を探索し最適経路を出力するネットワーク経路探索装置であって、ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と、該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、前記各リンクのもう一方のノードを識別するもう一方のノード番号と、該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストを格納するリンク接続先テーブルを備えたネットワーク経路探索装置の機能をコンピュータに実現させるネットワーク経路探索プログラムにおいて、
コンピュータに
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号を設定する経路条件設定機能、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索機能、
前記経路探索機能が展開した全ての経路から前記経路のコストに基づいて最適経路を選択して出力する最適経路出力機能、
を実現させるためのネットワーク経路探索プログラム。
【請求項１２】
請求項１１に記載のネットワーク経路探索プログラムにおいて、
前記リンク接続先テーブルは、前記片方のノードの接続先リンク番号と前記もう一方のノードの接続先リンク番号のそれぞれに対応して前記ネットワークの各リンクから前記片方のノードの接続先リンク番号のリンクあるいは前記もう一方のノードの接続先リンク番号のリンクに接続するコストである接続コストを格納するものであり、
前記経路探索機能は、経路のコストの計算において前記区間コストに加えて該経路の接続コストを累積することを特徴とするネットワーク経路探索プログラム。
【請求項１３】
請求項１１又は１２に記載のネットワーク経路探索プログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１４】
ノードとノード間を結ぶリンクからなるネットワークを表現するリンク接続先テーブルのデータ構造において、
前記リンク接続先テーブルは、
ネットワークの各リンクを識別するリンク番号に対して、
該各リンクの片方のノードを識別する片方のノード番号と、
該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、
前記各リンクのもう一方のノードを識別するもう一方のノード番号と、
該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、
前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストと
を格納するものであり、
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号が設定されると、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索の実行を可能とするリンク接続先テーブルのデータ構造。
【請求項１５】
請求項１４に記載のリンク接続先テーブルのデータ構造において、
前記リンク接続先テーブルは、前記片方のノードの接続先リンク番号と前記もう一方のノードの接続先リンク番号のそれぞれに対応して前記ネットワークの各リンクから前記片方のノードの接続先リンク番号のリンクあるいは前記もう一方のノードの接続先リンク番号のリンクに接続するコストである接続コストを格納するものであり、
前記経路のコストの計算において前記区間コストに加えて該経路の接続コストの累積を可能とすることを特徴とするリンク接続先テーブルのデータ構造。
【請求項１６】
ノードとノード間を結ぶリンクからなるネットワークを表現するデータ構造を有するリンク接続先テーブル作成装置において、
ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と該各リンクのもう一方のノードを識別するもう一方のノード番号を格納したリンクテーブルと、
ネットワークの各ノードを識別するノード番号に対して、該各ノードに接続されるすべてのリンクを識別するリンク番号を格納した交差点テーブルと、
前記リンクテーブル及び前記交差点テーブルからデータを読み取るデータ構造読取手段と、
前記データ構造読取手段で読み取った前記リンクテーブルに格納された各リンク番号に対応して、前記片方のノード番号と前記もう一方のノード番号を格納すると共に、該片方のノードの接続先リンク番号として、交差点テーブルから読み取られた該片方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納し、さらに、該もう一方のノードの接続先リンク番号として、交差点テーブルから読み取られた該もう一方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納することにより、リンク番号、片方のノードのノード番号、片方のノードの接続先リンク番号、もう一方のノード番号、もう一方のノードの接続先リンク番号の項目からなるリンク接続先テーブル生成手段と、
を備えることを特徴とするリンク接続先テーブル作成装置。
【請求項１７】
ノードとノード間を結ぶリンクからなるネットワークを表現するデータ構造を有するリンク接続先テーブル作成装置であって、ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と該各リンクのもう一方のノードを識別するもう一方のノード番号を格納したリンクテーブルと、ネットワークの各ノードを識別するノード番号に対して、該各ノードに接続されるすべてのリンクを識別するリンク番号を格納した交差点テーブルを備えたリンク接続先テーブル作成装置によるンク接続先テーブル作成方法において、
前記リンクテーブル及び前記交差点テーブルからデータを読み取るデータ構造読取ステップと、
前記データ構造読取ステップで読み取った前記リンクテーブルに格納された各リンク番号に対応して、前記片方のノード番号と前記もう一方のノード番号を格納すると共に、該片方のノードの接続先リンク番号として、交差点テーブルから読み取られた該片方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納し、さらに、該もう一方のノードの接続先リンク番号として、交差点テーブルから読み取られた該もう一方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納することにより、リンク番号、片方のノードのノード番号、片方のノードの接続先リンク番号、もう一方のノード番号、もう一方のノードの接続先リンク番号の項目からなるリンク接続先テーブル生成ステップと、
を備えることを特徴とするリンク接続先テーブル作成方法。
【請求項１８】
ノードとノード間を結ぶリンクからなるネットワークを表現するデータ構造を有するリンク接続先テーブル作成装置であって、ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と該各リンクのもう一方のノードを識別するもう一方のノード番号を格納したリンクテーブルと、ネットワークの各ノードを識別するノード番号に対して、該各ノードに接続されるすべてのリンクを識別するリンク番号を格納した交差点テーブルを備えたリンク接続先テーブル作成装置の機能をコンピュータに実現させるリンク接続先テーブル作成プログラムにおいて、
コンピュータに、
前記リンクテーブル及び前記交差点テーブルからデータを読み取るデータ構造読取機能、
前記データ構造読取機能で読み取った前記リンクテーブルに格納された各リンク番号に対応して、前記片方のノード番号と前記もう一方のノード番号を格納すると共に、該片方のノードの接続先リンク番号として、交差点テーブルから読み取られた該片方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納し、さらに、該もう一方のノードの接続先リンク番号として、交差点テーブルから読み取られた該もう一方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納することにより、リンク番号、片方のノードのノード番号、片方のノードの接続先リンク番号、もう一方のノード番号、もう一方のノードの接続先リンク番号の項目からなるリンク接続先テーブルを生成する機能、
を実現させるためのリンク接続先テーブル作成プログラム。
【請求項１９】
請求項１８に記載のリンク接続先テーブル作成プログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１】
ノードとノード間を結ぶリンクからなるネットワークの経路を探索し最適経路を出力するネットワーク経路探索装置において、
ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と、該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、前記各リンクのもう一方のノードを識別するもう一方のノード番号と、該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストを格納するリンク接続先テーブルと、
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号を設定する経路条件設定手段と、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索手段と、
前記経路探索手段が展開した全ての経路から前記経路のコストに基づいて最適経路を選択して出力する最適経路出力手段と、
を備えることを特徴とするネットワーク経路探索装置。
【請求項２】
請求項１に記載のネットワーク経路探索装置において、
前記リンク接続先テーブルは、前記片方のノードの接続先リンク番号と前記もう一方のノードの接続先リンク番号のそれぞれに対応して前記ネットワークの各リンクから前記片方のノードの接続先リンク番号のリンクあるいは前記もう一方のノードの接続先リンク番号のリンクに接続するコストである接続コストを格納するものであり、
前記経路探索手段は、経路のコストの計算において前記区間コストに加えて該経路の接続コストを累積することを特徴とするネットワーク経路探索装置。
【請求項３】
請求項２に記載のネットワーク経路探索装置において、
前記経路探索手段は、前記経路の展開において、前記始点リンクに接続されるリンク数である接続数を累積し、
前記最適経路出力手段は最適経路として同一のコストの経路が複数展開された場合には、該複数展開された経路から前記接続数に基づいて最適経路を選択して出力することを特徴とするネットワーク経路探索装置。
【請求項４】
請求項２に記載のネットワーク経路探索装置において、
経路探索手段は、前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照してさらに前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことに加えて片方のノード番号を読み出すものであり、該片方のノード番号が先に読み出した前記もう一方のノード番号と一致しないときには、前記さらに読み出されたもう一方のノードの接続先リンク番号による経路展開は行わないことを特徴とするネットワーク経路探索装置。
【請求項５】
請求項４に記載のネットワーク経路探索装置において、
前記接続先リンク番号により参照したリンク接続先テーブルに前記もう一方のノードの接続先リンク番号が存在しないとき、該接続先リンク番号による経路展開は行わないことを特徴とするネットワーク経路探索装置。
【請求項６】
請求項２に記載のネットワーク経路探索装置において、
前記ネットワークは道路網をモデル化したものであることを特徴とするネットワーク経路探索装置。
【請求項７】
請求項６記載のネットワーク経路探索装置を備えたことを特徴とするカーナビゲーション装置。
【請求項８】
請求項７記載のカーナビゲーション装置を備えたことを特徴とする車両。
【請求項９】
ノードとノード間を結ぶリンクからなるネットワークの経路を探索し最適経路を出力するネットワーク経路探索装置であって、ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と、該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、前記各リンクのもう一方のノードを識別するもう一方のノード番号と、該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストを格納するリンク接続先テーブルを備えたネットワーク経路探索装置によるネットワーク経路探索方法おいて、
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号を設定する経路条件設定ステップと、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索ステップと、
前記経路探索ステップで展開した全ての経路から前記経路のコストに基づいて最適経路を選択して出力する最適経路出力ステップと、
を備えることを特徴とするネットワーク経路探索方法。
【請求項１０】
請求項９に記載のネットワーク経路探索方法において、
前記リンク接続先テーブルは、前記片方のノードの接続先リンク番号と前記もう一方のノードの接続先リンク番号のそれぞれに対応して前記ネットワークの各リンクから前記片方のノードの接続先リンク番号のリンクあるいは前記もう一方のノードの接続先リンク番号のリンクに接続するコストである接続コストを格納するものであり、
前記経路探索ステップは、経路のコストの計算において前記区間コストに加えて該経路の接続コストを累積することを特徴とするネットワーク経路探索方法。
【請求項１１】
ノードとノード間を結ぶリンクからなるネットワークの経路を探索し最適経路を出力するネットワーク経路探索装置であって、ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と、該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、前記各リンクのもう一方のノードを識別するもう一方のノード番号と、該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストを格納するリンク接続先テーブルを備えたネットワーク経路探索装置の機能をコンピュータに実現させるネットワーク経路探索プログラムにおいて、
コンピュータに
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号を設定する経路条件設定機能、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索機能、
前記経路探索機能が展開した全ての経路から前記経路のコストに基づいて最適経路を選択して出力する最適経路出力機能、
を実現させるためのネットワーク経路探索プログラム。
【請求項１２】
請求項１１に記載のネットワーク経路探索プログラムにおいて、
前記リンク接続先テーブルは、前記片方のノードの接続先リンク番号と前記もう一方のノードの接続先リンク番号のそれぞれに対応して前記ネットワークの各リンクから前記片方のノードの接続先リンク番号のリンクあるいは前記もう一方のノードの接続先リンク番号のリンクに接続するコストである接続コストを格納するものであり、
前記経路探索機能は、経路のコストの計算において前記区間コストに加えて該経路の接続コストを累積することを特徴とするネットワーク経路探索プログラム。
【請求項１３】
請求項１１又は１２に記載のネットワーク経路探索プログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１４】
ノードとノード間を結ぶリンクからなるネットワークを表現するリンク接続先テーブルのデータ構造において、
前記リンク接続先テーブルは、
ネットワークの各リンクを識別するリンク番号に対して、
該各リンクの片方のノードを識別する片方のノード番号と、
該片方のノードに接続された全ての他のリンクを識別するリンク番号である片方のノードの接続先リンク番号と、
前記各リンクのもう一方のノードを識別するもう一方のノード番号と、
該もう一方のノードに接続された全ての他のリンクを識別するリンク番号であるもう一方のノードの接続先リンク番号と、
前記各リンクの片方のノードから前記各リンクのもう一方のノードへのコスト及び前記各リンクのもう一方のノードから前記各リンクの片方のノードへのコストであるそれぞれの区間コストと
を格納するものであり、
経路探索の始点となる始点ノードを識別する始点ノード番号と始点リンクを識別する始点リンク番号及び経路探索の終点となる終点ノードを識別する終点ノード番号が設定されると、
前記始点リンク番号により前記リンク接続先テーブルを参照して該始点リンクの前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出し、該読み出されたもう一方のノードの接続先リンク番号によりさらに前記リンク接続先テーブルを参照して前記もう一方のノード番号と前記もう一方のノードの接続先リンク番号のうちの１つを読み出すことを、該もう一方のノード番号が前記終点ノード番号と一致するまで、前記区間コストを累積しながら繰り返し、さらに該繰り返しを、前記もう一方のノードの接続先リンク番号の読み出しを前記リンク接続先テーブルに格納されたすべてのもう一方のノードの接続先リンク番号について行うことで前記始点ノードから前記終点ノードまでの全ての経路を展開し、該全ての経路のコストを計算する経路探索の実行を可能とするリンク接続先テーブルのデータ構造。
【請求項１５】
請求項１４に記載のリンク接続先テーブルのデータ構造において、
前記リンク接続先テーブルは、前記片方のノードの接続先リンク番号と前記もう一方のノードの接続先リンク番号のそれぞれに対応して前記ネットワークの各リンクから前記片方のノードの接続先リンク番号のリンクあるいは前記もう一方のノードの接続先リンク番号のリンクに接続するコストである接続コストを格納するものであり、
前記経路のコストの計算において前記区間コストに加えて該経路の接続コストの累積を可能とすることを特徴とするリンク接続先テーブルのデータ構造。
【請求項１６】
ノードとノード間を結ぶリンクからなるネットワークを表現するデータ構造を有するリンク接続先テーブル作成装置において、
ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と該各リンクのもう一方のノードを識別するもう一方のノード番号を格納したリンクテーブルと、
ネットワークの各ノードを識別するノード番号に対して、該各ノードに接続されるすべてのリンクを識別するリンク番号を格納した交差点テーブルと、
前記リンクテーブル及び前記交差点テーブルからデータを読み取るデータ構造読取手段と、
前記データ構造読取手段で読み取った前記リンクテーブルに格納された各リンク番号に対応して、前記片方のノード番号と前記もう一方のノード番号を格納すると共に、該片方のノードの接続先リンク番号として、交差点テーブルから読み取られた該片方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納し、さらに、該もう一方のノードの接続先リンク番号として、交差点テーブルから読み取られた該もう一方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納することにより、リンク番号、片方のノードのノード番号、片方のノードの接続先リンク番号、もう一方のノード番号、もう一方のノードの接続先リンク番号の項目からなるリンク接続先テーブル生成手段と、
を備えることを特徴とするリンク接続先テーブル作成装置。
【請求項１７】
ノードとノード間を結ぶリンクからなるネットワークを表現するデータ構造を有するリンク接続先テーブル作成装置であって、ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と該各リンクのもう一方のノードを識別するもう一方のノード番号を格納したリンクテーブルと、ネットワークの各ノードを識別するノード番号に対して、該各ノードに接続されるすべてのリンクを識別するリンク番号を格納した交差点テーブルを備えたリンク接続先テーブル作成装置によるンク接続先テーブル作成方法において、
前記リンクテーブル及び前記交差点テーブルからデータを読み取るデータ構造読取ステップと、
前記データ構造読取ステップで読み取った前記リンクテーブルに格納された各リンク番号に対応して、前記片方のノード番号と前記もう一方のノード番号を格納すると共に、該片方のノードの接続先リンク番号として、交差点テーブルから読み取られた該片方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納し、さらに、該もう一方のノードの接続先リンク番号として、交差点テーブルから読み取られた該もう一方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納することにより、リンク番号、片方のノードのノード番号、片方のノードの接続先リンク番号、もう一方のノード番号、もう一方のノードの接続先リンク番号の項目からなるリンク接続先テーブル生成ステップと、
を備えることを特徴とするリンク接続先テーブル作成方法。
【請求項１８】
ノードとノード間を結ぶリンクからなるネットワークを表現するデータ構造を有するリンク接続先テーブル作成装置であって、ネットワークの各リンクを識別するリンク番号に対して、該各リンクの片方のノードを識別する片方のノード番号と該各リンクのもう一方のノードを識別するもう一方のノード番号を格納したリンクテーブルと、ネットワークの各ノードを識別するノード番号に対して、該各ノードに接続されるすべてのリンクを識別するリンク番号を格納した交差点テーブルを備えたリンク接続先テーブル作成装置の機能をコンピュータに実現させるリンク接続先テーブル作成プログラムにおいて、
コンピュータに、
前記リンクテーブル及び前記交差点テーブルからデータを読み取るデータ構造読取機能、
前記データ構造読取機能で読み取った前記リンクテーブルに格納された各リンク番号に対応して、前記片方のノード番号と前記もう一方のノード番号を格納すると共に、該片方のノードの接続先リンク番号として、交差点テーブルから読み取られた該片方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納し、さらに、該もう一方のノードの接続先リンク番号として、交差点テーブルから読み取られた該もう一方のノード番号のノードに接続されるリンクのリンク番号から自リンクのリンク番号を除いたリンク番号を格納することにより、リンク番号、片方のノードのノード番号、片方のノードの接続先リンク番号、もう一方のノード番号、もう一方のノードの接続先リンク番号の項目からなるリンク接続先テーブルを生成する機能、
を実現させるためのリンク接続先テーブル作成プログラム。
【請求項１９】
請求項１８に記載のリンク接続先テーブル作成プログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【図１】
【図２Ａ】
【図２Ｂ】
【図３】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図２Ａ】
【図２Ｂ】
【図３】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【公開番号】特開２０１０−７１７６７（Ｐ２０１０−７１７６７Ａ）
【公開日】平成２２年４月２日（２０１０．４．２）
【国際特許分類】
【出願番号】特願２００８−２３８５３９（Ｐ２００８−２３８５３９）
【出願日】平成２０年９月１７日（２００８．９．１７）
【出願人】（５０３００２１６７）株式会社高速屋 (4)
【Ｆターム（参考）】
【公開日】平成２２年４月２日（２０１０．４．２）
【国際特許分類】
【出願日】平成２０年９月１７日（２００８．９．１７）
【出願人】（５０３００２１６７）株式会社高速屋 (4)
【Ｆターム（参考）】
[ Back to top ]