最適経路探索装置及び最適経路探索装置並びにプログラム
【課題】ネットワークにおける各リンクの通過時間が変化するような場合でも効率よく最適経路を計算することが可能な最適経路探索方法の提供。
【解決手段】ネットワーク内の２つのノードを起点ノードｏ，目的点ノードｄに設定する。ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、該ノードｉから該ノードｊを通って目的点ノードｄへ行くときの、目的点ノードｄへの最小の移動時間であるＱ値Ｑｄ（ｉ，ｊ）＝ｔｉｊ＋ｍｉｎｋ［Ｑｄ（ｊ，ｋ）］を幅優先探索順に計算する。最後に、起点ノードｏから開始して目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、起点ノードｏから目的点ノードｄへの最適経路を選択する。
【解決手段】ネットワーク内の２つのノードを起点ノードｏ，目的点ノードｄに設定する。ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、該ノードｉから該ノードｊを通って目的点ノードｄへ行くときの、目的点ノードｄへの最小の移動時間であるＱ値Ｑｄ（ｉ，ｊ）＝ｔｉｊ＋ｍｉｎｋ［Ｑｄ（ｊ，ｋ）］を幅優先探索順に計算する。最後に、起点ノードｏから開始して目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、起点ノードｏから目的点ノードｄへの最適経路を選択する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路ネットワーク、コンピュータネットワーク等の複数のノードと各ノード間を結ぶ複数のリンクとから構成され各リンクに重みが与えられたネットワークにおいて、重みが最も小さい経路やｎ番目に小さい経路を探索する最適経路探索技術に関する。
【背景技術】
【０００２】
近年、移動車輛において道路交通情報通信システム（Vehicle Information and Communication System：ＶＩＣＳ）によりリアルタイムに交通情報を取得し、該交通情報に基づいて目的地への最適経路を得るカーナビゲーションシステムが開発されている。目的地への最適経路は、ドライバーの選択にも依るが、通常は、現在地から目的地までの旅行時間（traveling time）が最小の経路が「最適経路（optimal route）」とされる。
【０００３】
また、インターネット等のコンピュータネットワークにおいては、ネットワーク上のあるコンピュータから別のコンピュータへ情報を送信するため、コンピュータネットワーク上での経路を見つけだすルーティングという処理が行われる。このルーティングにおいては、情報の転送時間を短縮するため、コンピュータ間の転送時間が最小となる「最適経路」の探索が行われる。
【０００４】
このような、最適経路の探索には、従来からダイクストラ（Dijkstra）法が広く用いられている（非特許文献１，２，３参照）。
【０００５】
上記道路ネットワークやコンピュータネットワークは、複数のノードと各ノード間を結ぶ複数のリンクとから構成され各リンクに重み（移動時間や転送時間等を）が与えられた重み付き有向グラフＧ＝（Ｎ，Ｅ）として抽象化される。ダイクストラ法では、有向グラフＧ＝（Ｎ，Ｅ）の各リンクの重みがすべて非負の場合に、起点ノードｏから目的点ノードｄに至るリンクの重みの和が最小となる最適経路を計算する。
【０００６】
ネットワーク内のすべてのノードの集合をＮ、起点ノードｏからの最終的な最短路重みが既に定まっているノードの集合をＳ、Ｓの補集合をＴ、ノードｉからノードｊへ向かうリンクをｌｉ，ｊ、リンクｌｉ，ｊの重みをｔｉ，ｊとする。一般的なダイクストラ法では、次のようにして最適経路が演算される（例えば、非特許文献３参照）。
【０００７】
まず初期設定として、
【０００８】
【数１】
とし、更に、起点ノードｏ以外の各ノードｉ（∈Ｔ）に対して、
【０００９】
【数２】
とする。次に、以下の操作を、Ｔが空集合となるまで反復演算する。
【００１０】
【数３】
【００１１】
以上の反復計算が終了すると、ｐ（ｊ）は起点ノードｏからノードｊへの最小重みになっている。また、点列｛ｊ，ｑ（ｊ），ｑ（ｑ（ｊ）），…｝は、その最短経路での経由点を逆順にしたものになっている。
【非特許文献１】E. Dijkstra, "A note on Two Problems in Connexion with Graphs", Numerische Malhematik 1 ,pp. 269-271, 1959.
【非特許文献２】B. Golden, "Shortest-Path Algorithms: A Companion'", Operations Research, Vol. 24, No.6. pp.1164-1168, 1976.
【非特許文献３】Ｔ．コルメン、他２名，「アルゴリズム・イントロダクション 第２巻 アルゴリズムの設計と解析手法」，近代科学社，１９９５年１２月３０日，pp.219-223.
【非特許文献４】R. Bellman, "The Theory of Dynamic Programming", Bull. Amer. Math. Soc. 60, pp.503-515. 1954.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、道路ネットワークやコンピュータネットワークでは、各リンクを通る際の旅行時間は、一定ではなく、時々刻々に動的に変化する。このように各リンクの旅行時間が動的な場合、上記ダイクストラ法では、リンクの旅行時間が変化する毎に、初期解を削除しスクラッチ（(scratch)データを削除するかラベルをつけ直すかして新しいデータを書き込めるようにすること。）してから、すべてを再計算する必要が生じるため効率が悪い。
【００１３】
また、上記ダイクストラ法では、起点ノードｏから目的点ノードｄまでの旅行時間が最小となる最適経路を求めることは可能であるが、旅行時間が２番目に小さくなる経路や、３番目に小さくなる経路のような次善経路を求めることができない。
【００１４】
そこで、本発明の第１の目的は、ネットワークにおける各リンクの重みが変化するような場合でも効率よく最適経路を計算することが可能な最適経路探索装置及び最適経路探索方法を提供することにある。
【００１５】
また、本発明の第２の目的は、起点ノードから目的点ノードまでの重みが最小となる最適経路以外に、重みがｎ番目（ｎ＝２，３，…）に小さくなる次善経路を求めることが可能な最適経路探索装置及び最適経路探索方法を提供することにある。
【課題を解決するための手段】
【００１６】
本発明に係る最適経路探索装置の第１の構成は、複数のノード及び前記各ノード間を結ぶ複数のリンクとから構成されたネットワークにおいて、当該ネットワーク内の任意の２つのノードが起点ノードｏ及び目的点ノードｄに設定されたとき、前記起点ノードｏから前記目的点ノードｄに至る経路のうち、重みが小さい経路を探索する最適経路探索装置であって、
前記ネットワークの各ノード及び各リンクの接続情報を、グラフ表現のデータとして記憶するネットワーク記憶手段と、
前記ネットワークの各リンクｌｉ，ｊ（ｉ，ｊは、それぞれ該リンクの始点ノード、終点ノードの添数）の重みｔｉ，ｊを記憶する重み記憶手段と、
前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、該ノードｉから該ノードｊを通って前記目的点ノードｄへ行くときの、前記目的点ノードｄへの最小の重みであるＱ値Ｑｄ（ｉ，ｊ）を記憶するＱ値記憶手段と、
前記ネットワーク内の各ノードの中から前記起点ノードｏ及び前記目的点ノードｄを設定する起終点対設定手段と、
前記ネットワーク内の隣接する２つのノードｉ，ｊを結ぶリンクｌｉ，ｊの該ノードｉから該ノードｊへの重みをｔｉ，ｊとしたとき、前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、ノードｉが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化し、ノードｊが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）をｔｉ，ｊに初期化し、それ以外の場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化するとともに、初期化した該Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するＱ値初期化手段と、
前記起点ノードｏから開始して、幅優先探索順に、前記ネットワークのすべてのリンクｌｉ，ｊを順次選択し、選択された該リンクｌｉ，ｊに対応する前記Ｑ値Ｑｄ（ｉ，ｊ）を、前記Ｑ値記憶手段に保存された各Ｑ値を用いて（数４）の演算により更新し、更新した前記Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するという更新演算処理を、すべての前記Ｑ値の値が収束するまで反復実行するＱ値更新手段と、
前記Ｑ値更新手段により前記Ｑ値記憶手段の前記各Ｑ値が更新された後、前記起点ノードｏから開始して前記目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、前記起点ノードｏから前記目的点ノードｄへの最適経路を選択する最適経路選択手段と、
を備えたことを特徴とする。
【００１７】
【数４】
【００１８】
この構成によれば、最適化の原理（非特許文献４参照）により、起点ノードｏから開始して目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、最終的に起点ノードｏから目的点ノードｄまで選択されるノードとリンクの列が、重みが最小となる最適経路になる。
【００１９】
また、ネットワーク内における一部のリンクの重みが変化した場合、既にＱ値記憶手段に保存された計算済みのＱ値を初期値として、Ｑ値更新手段によって上記反復計算を行えば、重みが変化したリンクに関係するＱ値のみが更新されるため、少ない反復回数で反復演算が収束する。そして、計算収束後に最適経路選択手段により最適経路の選択を行えば、最適経路の最計算結果を得ることができる。この場合、すべてのＱ値を更新する必要がないため、従来のダイクストラ法に比べ、効率よく最適経路の再計算を行うことが可能となる。
【００２０】
また、一度Ｑ値を計算してＱ値記憶手段に保存しておけば、起点ノードが変更された場合に於いても、最適経路選択手段によって、目的点ノードｄまでの最小重みと最適経路を容易に計算することができる。
【００２１】
ここで、「重み」とは、各リンクや経路に対して与えられる量であって、最適経路探索において最小化すべき量をいう。「重み」は、本発明を適用する対象によって様々なものが考えられる。例えば、道路ネットワークにおいて目的地までの最適経路の探索に本発明を適用する場合には、「重み」として、旅行時間、燃料コスト、運転の快適さの指標、その他交通に関する量（例えば、道幅、道路の勾配、通学路かどうかなどを総合した上で数値化して表現したもの）などが用いられる。
【００２２】
本発明に係る最適経路探索装置の第２の構成は、前記第１の構成に於いて、前記最適経路選択手段により選択された前記最適経路内の目的点ノードｄを除く各ノードｉ（ｉは最適経路内の各ノードの添数）に対して、前記Ｑ値Ｑｄ（ｉ，ｊ）がｎ番目（ｎ≧２）に小さいＱ値を抽出するとともに、抽出されたそれらの各Ｑ値と対応する各ノードまでの重みの和について最小値を与えるＱ値を選択する次善Ｑ値選択手段と、
前記最適経路内のリンクの内、前記次善Ｑ値選択手段により選択されたＱ値に対応するリンクｌｐ，ｑの始点ノードｐの次のリンクを該リンクｌｐ，ｑに置換するとともに、該リンクｌｐ，ｑの終点ノードｑから前記目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、次善経路を選択する次善経路選択手段と、
を備えたことを特徴とする。
【００２３】
この構成によれば、次善Ｑ値選択手段及び次善経路選択手段によって、起点ノードから目的点ノードまでの重みが最小となる最適経路以外に、重みがｎ番目（ｎ＝２，３，…）に小さくなる次善経路を容易に求めることが可能となる。
【００２４】
また、本発明に係る最適経路探索方法の第１の構成は、複数のノード及び前記各ノード間を結ぶ複数のリンクとから構成されたネットワークがグラフ表現のデータとして記憶されたネットワーク記憶手段、
前記ネットワークの各リンクｌｉ，ｊ（ｉ，ｊは、それぞれ該リンクの始点ノード、終点ノードの添数）の重みｔｉ，ｊを記憶する重み記憶手段、
及び前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、該ノードｉから該ノードｊを通って前記目的点ノードｄへ行くときの、前記目的点ノードｄへの最小の重みであるＱ値Ｑｄ（ｉ，ｊ）を記憶するＱ値記憶手段を備えたコンピュータにおいて、
前記ネットワーク内の任意の２つのノードが起点ノードｏ及び目的点ノードｄに設定されたとき、前記起点ノードｏから前記目的点ノードｄに至る経路のうち、重みが小さい経路を探索する最適経路探索方法であって、
ネットワーク記憶手段に記憶された前記ネットワークの各ノードの中から、２つのノードを選択して、前記起点ノードｏ及び前記目的点ノードｄとして設定する起終点対設定ステップと、
前記ネットワーク内の隣接する２つのノードｉ，ｊを結ぶリンクｌｉ，ｊの該ノードｉから該ノードｊへの重みをｔｉ，ｊとしたとき、前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、ノードｉが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化し、ノードｊが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）をｔｉ，ｊに初期化し、それ以外の場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化するとともに、初期化した該Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するＱ値初期化ステップと、
前記起点ノードｏから開始して、幅優先探索順に、前記ネットワークのすべてのリンクｌｉ，ｊを順次選択し、選択された該リンクｌｉ，ｊに対応する前記Ｑ値Ｑｄ（ｉ，ｊ）を、前記Ｑ値記憶手段に保存された各Ｑ値を用いて（数４）の演算により更新し、更新した前記Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するという更新演算処理を、すべての前記Ｑ値の値が収束するまで反復実行するＱ値更新ステップと、
前記Ｑ値更新手段により前記Ｑ値記憶手段の前記各Ｑ値が更新された後、前記起点ノードｏから開始して前記目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、前記起点ノードｏから前記目的点ノードｄへの最適経路を選択する最適経路選択ステップと、を有することを特徴とする。
【００２５】
本発明に係る最適経路探索方法の第２の構成は、前記第１の構成に於いて、前記最適経路選択ステップにおいて選択された前記最適経路内の目的点ノードｄを除く各ノードｉ（ｉは最適経路内の各ノードの添数）に対して、前記Ｑ値Ｑｄ（ｉ，ｊ）がｎ番目（ｎ≧２）に小さいＱ値を抽出するとともに、抽出されたそれらの各Ｑ値のうち最小のＱ値を選択する次善Ｑ値選択ステップと、
前記最適経路内のリンクの内、前記次善Ｑ値選択ステップにおいて選択されたＱ値に対応するリンクｌｐ，ｑの始点ノードｐの次のリンクを該リンクｌｐ，ｑに置換するとともに、該リンクｌｐ，ｑの終点ノードｑから前記目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、次善経路を選択する次善経路選択ステップと、を備えたことを特徴とする。
【００２６】
また、本発明に係るプログラムは、コンピュータに読み込ませて実行することによって、コンピュータを請求項１又は２に記載の最適経路探索装置として機能させることを特徴とする。
【発明の効果】
【００２７】
以上のように、本発明によれば、ネットワーク内における一部のリンクの重みが変化した場合、既にＱ値記憶手段に保存された計算済みのＱ値を初期値として、Ｑ値更新のための反復計算を行えば、Ｑ値記憶手段に記憶されたＱ値のうち重みが変化したリンクに関係するＱ値のみが更新されるため、少ない反復回数で反復演算が収束する。従って、すべてのＱ値を更新する必要がないため、従来のダイクストラ法に比べ、効率よく最適経路の再計算を行うことが可能となる。
【００２８】
また、一度Ｑ値を計算してＱ値記憶手段に保存しておけば、起点ノードが変更された場合に於いても、最適経路選択手段によって、目的点ノードｄまでの最小重みと最適経路を容易に計算することができる。
【００２９】
また、次善Ｑ値選択手段及び次善経路選択手段によって、起点ノードから目的点ノードまでの重みが最小となる最適経路以外に、重みがｎ番目（ｎ＝２，３，…）に小さくなる次善経路を容易に求めることが可能となる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００３１】
実施例１では、一例として、道路ネットワークにおいて、起点ノードｏから目的点ノードｄまでの重みが最小となる最適経路を演算する最適経路探索装置について説明する。
【００３２】
図１は、道路ネットワークの一例を表す図である。一般に、道路ネットワークは、交差点をノードとし２つの交差点間を結ぶ道路をリンクとし、各リンクの重みをそのリンクの重みとする、重み付き有向グラフＧ＝（Ｎ，Ｅ，ｔ）で表すことができる。ここで、Ｎはすべてのノードの集合、Ｅはすべてのリンクの集合、ｔはすべてのリンクの重みの集合である。
【００３３】
尚、この場合「重み」としては、旅行時間や燃料コストなどの交通に関する量が用いられる。
【００３４】
今、道路ネットワーク内のノード（交差点）から、起終点対（Origin-Destination pair：ＯＤ対）を選び、その起点ノード（origin node）をｏ、目的点ノード（destination node）をｄと記す。ノードｉからノードｊへのリンク（有向リンク）をｌｉ，ｊと記す。道路リンクｌｉ，ｊの重みをｔｉ，ｊと記す。また、重みが変化したとき、変化後の重みをｔ’ｉ，ｊと記す。
【００３５】
また、本明細書において、「Ｑ値」を以下のように定義する。
【００３６】
〔定義１〕
重み付き有向グラフＧ＝（Ｎ，Ｅ，ｔ）に於いて目的点ノードｄ（∈Ｎ）が与えられているとき、互いに隣接する任意のノードｉ，ｊ（∈Ｎ）に対して、ノードｉを起点ノードとしてノードｊを通って目的点ノードｄに行くときの、目的点ノードｄへの最小重みを「Ｑ値（Q value）」といい、Ｑｄ（ｉ，ｊ）と記す。
〔定義終り〕
【００３７】
図１において、「●」は起点ノード及び目的点ノードを表す。「○」は起点ノード及び目的点ノード以外のノードを表す。また、各ノード間を繋ぐ矢印はリンクを表す。
【００３８】
図２は、実施例１に係る最適経路探索装置１のハードウェア構成を表す図である。最適経路探索装置１は、マイクロコントローラ２、入力装置３、記憶装置４、表示装置５、及びＶＩＣＳ受信装置６により構成される。
入力装置３には、キーボタンやタッチパネル等が使用される。記憶装置４は、ＲＯＭ，ＲＡＭなどの内部記憶装置やハードディスク，ＤＶＤ−ＲＯＭなどの外部記憶装置が使用される。表示装置５は、液晶ディスプレイ等が使用される。これらの構成は、一般のカーナビゲーション装置を構成するコンピュータと同様である。
【００３９】
図３は、実施例１に係る最適経路探索装置１の機能構成を表した図である。
【００４０】
最適経路探索装置１は、表示装置５、ＶＩＣＳ受信装置６、ネットワーク記憶部１０、重み記憶部１１、Ｑ値記憶部１２、最適経路記憶部１３、重み更新部１４、起終点対設定部１５、Ｑ値初期化部１６、Ｑ値更新部１７、最適経路選択部１８、次善Ｑ値選択部１９、及び次善経路選択部２０を備えている。
【００４１】
尚、表示装置５及びＶＩＣＳ受信装置６は図２と同様である。ネットワーク記憶部１０、重み記憶部１１、及びＱ値記憶部１２は、記憶装置４によって実現される。また、重み更新部１４、最適経路記憶部１３、起終点対設定部１５、Ｑ値初期化部１６、Ｑ値更新部１７、最適経路選択部１８、次善Ｑ値選択部１９、及び次善経路選択部２０は、マイクロコントローラ２、入力装置３、及び記憶装置４が協働することにより実現される。
【００４２】
ＶＩＣＳ受信装置６は、道路交通情報通信システムにより無線送信される交通情報（ＶＩＣＳ情報）を受信する装置である。表示装置５は、地図情報や最適経路の情報を表示する装置であり、液晶ディスプレイ装置等によって構成される。
【００４３】
ネットワーク記憶部１０は、道路ネットワークの各ノード及び各リンクの接続情報を、グラフ表現のデータとして記憶する。グラフ表現のデータとは、例えば、図４（ｂ）に示したようなデータをいう（非特許文献３，ｐｐ．１６３−１６５参照）。図４（ｂ）は、図４（ａ）の道路ネットワークＧ＝（Ｎ，Ｅ）の各ノード及び各リンクの接続情報を、隣接リスト表現によりリスト化したデータである。この場合、接続情報は、ノード集合Ｎの各ノードに対して１つずつ、全部で｜Ｎ｜個（｜Ｎ｜は集合Ｎの要素数）のリストＡｄｊの配列からなる。各ノードｉ（∈Ｎ）に対して、隣接リストＡｄｊ［ｉ］は、リンクｌｉ，ｊ（∈Ｅ）が存在するすべてのノードｊへのポインタを含んでいる。
【００４４】
尚、グラフ表現のデータとしては、隣接リスト表現以外に隣接行列表現（非特許文献３，ｐ．１６４参照）を用いてもよい。
【００４５】
重み記憶部１１は、ネットワーク記憶部１０に記憶された道路ネットワークＧ＝（Ｎ，Ｅ）の各リンクｌｉ，ｊ（∈Ｅ）に対応して、そのリンクｌｉ，ｊの重みｔｉ，ｊが記憶される。
【００４６】
Ｑ値記憶部１２は、道路ネットワークＧ＝（Ｎ，Ｅ）内の隣接する２つのノードｉ，ｊ（∈Ｎ）の各組に対して、該ノードｉから該ノードｊを通って目的点ノードｄへ行くときの、目的点ノードｄへの最小の重みであるＱ値Ｑｄ（ｉ，ｊ）を記憶する。
【００４７】
最適経路記憶部１３は、計算された起点ノードｏから目的点ノードｄまでの最適経路や次善最適経路を記憶する。
【００４８】
重み更新部１４は、道路ネットワークＧ＝（Ｎ，Ｅ）内の各リンクｌｉ，ｊ（∈Ｅ）に対して、重みｔｉ，ｊの初期値を設定し重み記憶部１１に保存する。また、重み更新部１４は、ＶＩＣＳ受信装置６においてＶＩＣＳ情報が受信された場合に、そのＶＩＣＳ情報に含まれる情報から、該情報で指定される所定のリンクｌｉ，ｊ（∈Ｅ）の重みｔｉ，ｊを変更し、重み記憶部１１の記憶内容の更新を行う。
【００４９】
起終点対設定部１５は、道路ネットワーク内の各ノードの中から起点ノードｏ及び目的点ノードｄを設定する。起点ノードの設定は、例えば、ＧＰＳ受信装置（図示せず）により得られる現在位置に最も近いノードに設定したり、使用者が入力装置３により地図上で指定する地点に最も近いノードなどに設定される。また、目的点ノードｄは、使用者が入力装置３により地図上で指定する地点に最も近いノードなどに設定される。
【００５０】
Ｑ値初期化部１６は、道路ネットワーク内の隣接する２つのノードｉ，ｊ（∈Ｎ）の各組に対して、ノードｉが目的点ノードｄの場合にはＱ値Ｑｄ（ｉ，ｊ）を０に初期化する。ノードｊが目的点ノードｄの場合にはＱ値Ｑｄ（ｉ，ｊ）をｔｉ，ｊに初期化する。また、それ以外の場合にはＱ値Ｑｄ（ｉ，ｊ）を０に初期化する。そして、初期化した該Ｑ値Ｑｄ（ｉ，ｊ）をＱ値記憶部１２に保存する。
【００５１】
Ｑ値更新部１７は、起点ノードｏから開始して、幅優先探索順に、ネットワークのすべてのリンクｌｉ，ｊを順次選択し、選択された該リンクｌｉ，ｊに対応するＱ値Ｑｄ（ｉ，ｊ）を、Ｑ値記憶部１２に保存された各Ｑ値を用いて式（４ａ），（４ｂ）の演算により更新し、更新したＱ値Ｑｄ（ｉ，ｊ）をＱ値記憶部１２に保存するという更新演算処理を、すべてのＱ値の値が収束するまで反復実行する。
【００５２】
最適経路選択部１８は、Ｑ値更新部１７によりＱ値記憶部１２の各Ｑ値が更新された後、起点ノードｏから開始して目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、起点ノードｏから目的点ノードｄへの最適経路を選択する。選択された最適経路のノード列の情報及び最短重み（最適経路を辿ったときの起点ノードｏから目的点ノードｄに至る経路の各リンクの重みの和）は、最適経路記憶部１３に保存されるとともに、表示装置５に表示された地図上に表示される。
【００５３】
次善Ｑ値選択部１９は、最適経路記憶部１３に記憶された最適経路内の目的点ノードｄを除く各ノードｉ（ｉは最適経路内の各ノードの添数）に対して、Ｑ値Ｑｄ（ｉ，ｊ）がｎ番目（ｎ≧２）に小さいＱ値を抽出するとともに、抽出されたそれらの各Ｑ値のうち最小のＱ値を選択する。
【００５４】
次善経路選択部２０は、最適経路内のリンクのうち、次善Ｑ値選択部１９により選択されたＱ値に対応するリンクｌｐ，ｑの始点ノードｐの次のリンクを該リンクｌｐ，ｑに置換するとともに、該リンクｌｐ，ｑの終点ノードｑから目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、次善経路を選択する。選択された次善経路は、表示装置５に表示された地図上に表示される。
【００５５】
尚、最適経路探索装置１のこれらの機能は、プログラムとして提供され、該プログラムを記憶装置４に読み込み、マイクロコントローラ２によって実行することによって実現される。
【００５６】
以上のように構成された本実施例の最適経路探索装置１において、以下その動作を説明する。
【００５７】
図５は、最適経路探索装置１による最適経路探索方法の流れを表すフローチャートである。
【００５８】
まず、ステップＳ１０において、重み更新部１４は、ネットワーク記憶部１０に記憶された道路ネットワークＧ＝（Ｎ，Ｅ）の各リンクｌｉ，ｊ（∈Ｅ）に対して、重みの初期値ｔｉ，ｊを設定し、Ｑ値記憶部１２に保存する。尚、重みの初期値ｔｉ，ｊは、予め記憶装置４に地図情報と共に記憶されているものが使用される。
【００５９】
また、起終点対設定部１５は、道路ネットワークＧ＝（Ｎ，Ｅ）の各ノードの中から、起点ノードｏと目的点ノードｄを設定する。起点ノードｏと目的点ノードｄの設定は、上述したように、ＧＰＳ受信装置（図示せず）により得られる現在位置に最も近いノードを設定したり、使用者が入力装置３により地図上で指定する地点に最も近いノードを設定する。
【００６０】
次に、ステップＳ２０において、Ｑ値初期化部１６は、Ｑ値記憶部１２のＱ値の初期化を行う。いま、Ｑ値Ｑｄ（ｉ，ｊ）の初期値をＱｄ（０）（ｉ，ｊ）で表す。尚、上付添字「（０）」は、Ｑ値更新部１７における反復処理のイタレーション（iteration）の回数を表している（初期状態では反復処理は行われていないので、イタレーションの回数は０である）。Ｑ値初期化部１６によるＱ値初期化の初期化処理は、次式により表される。
【００６１】
【数５】
【００６２】
ここで、Ａ（ｉ）は、ノードｉに接続するノードの添数の集合を表す。Ｂ（ｄ）は、目的点ノードｄへ直接移動することが可能なノードの添数の集合である。Ｎｄは、目的点ノードの交差点の添数の集合である。
【００６３】
次に、ステップＳ３０において、Ｑ値更新部１７は、起点ノードｏから開始して、幅優先探索順に、前記ネットワークのすべてのリンクｌｉ，ｊを順次選択する。そして、選択された該リンクｌｉ，ｊに対応するＱ値Ｑｄ（ｉ，ｊ）を、Ｑ値記憶部１２に保存された各Ｑ値を用いて式（４ａ），（４ｂ）の演算により更新し、更新したＱ値Ｑｄ（ｉ，ｊ）をＱ値記憶部１２に保存する。この処理を「更新演算処理」と呼ぶ。尚、幅優先探索順とは、一般的な幅優先探索（breadth-first search）における探索順序をいう（非特許文献３，ｐ．１６６−１６８参照）。
【００６４】
次に、ステップＳ４０において、Ｑ値更新部１７は、更新演算処理が収束したか否かを判定する。「更新演算処理が収束した」とは、ステップＳ３０の更新演算処理において、すべてのＱ値Ｑｄ（ｉ，ｊ）が更新前の値と更新後の値の差が所定の判定閾値ε以下となったことをいう。すなわち、
【００６５】
【数６】
のときに「更新演算処理が収束した」と判定される。ここで、判定閾値εは充分小さな正の数値に設定される。
【００６６】
更新演算処理が収束していない場合には、再びステップＳ３０に戻り、収束した場合には、次のステップＳ５０に進む。
【００６７】
ステップＳ５０において、最適経路選択部１８は、起点ノードｏから開始して目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、起点ノードｏから目的点ノードｄへの最適経路を選択する。これにより、最適経路として、ノードの配列（ｉ０（＝ｏ），ｉ１，ｉ２，…，ｉｎ（＝ｄ））と、起点ノードｏから目的点ノードｄまでの最小重みｔｍｉｎ（ｏ，ｄ）が得られる。
【００６８】
【数７】
【００６９】
ここで、Ｑｄ（ｉ，ｊ）は、上述のように、目的点ノードがｄである場合に、ノードｉにおいて次の移動先としてノードｊを選んだときの、ノードｉから目的点ノードｄまでの最小重みを示している。従って、ノードｉから移動するノードは、ｊ（∈Ａ（ｉ））の中でＱｄ（ｉ，ｊ）が最小となるノードとなる。同様にして、ノードｊでは、ノードｊから移動可能なノードｋ（∈Ａ（ｊ））の中でＱｄ（ｉ，ｊ）が最小となるノードが選ばれる。このような原理によって、起点ノードｏから目的点ノードｄまでの最適経路が求まるのである。
【００７０】
最適経路選択部１８は、得られた最適経路（ｉ０（＝ｏ），ｉ１，ｉ２，…，ｉｎ（＝ｄ））と最小重みｔｍｉｎ（ｏ，ｄ）を最適経路記憶部１３に保存するとともに、表示装置５に表示した地図上に最適経路と最小重みを表示する。
【００７１】
尚、本実施例の最適経路探索装置１では、Ｑｄ（ｉ，ｊ）の定義から、起点ノードｏのみならず、すべてのノードから目的点ノードｄまでの最適経路を計算することが可能となる。従って、目的点ノードｄがそのままで起点ノードｏが変化した場合でも、即座に目的点ノードｄまでの最適経路を再計算することができる。
【００７２】
次に、一部のリンクの重みが変化した場合の動作について説明する。
【００７３】
図６は、重みが変化した場合の最適経路探索装置１による最適経路探索方法の流れを表すフローチャートである。
【００７４】
まず、ステップＳ６０において、重み記憶部１１に保存された重みのうちの一乃至複数が更新されて変化する。重みの更新は、ＶＩＣＳ受信装置６がＶＩＣＳ情報を受信し、当該ＶＩＣＳ情報の中に、渋滞や工事などにより一部のリンクの重みが変更される情報が含まれている場合、重み更新部１４はそのＶＩＣＳ情報に従って、特定のリンクの重みｔｉ，ｊをｔ’ｉ，ｊに更新し、重み記憶部１１に保存する。
【００７５】
次に、ステップＳ７０において、Ｑ値更新部１７は、Ｑ値記憶部１２に既に保存されている各Ｑ値を初期値として、重み記憶部１１に更新・保存された重みを用いて、前述の更新演算処理を実行する。
【００７６】
次に、ステップＳ８０において、Ｑ値更新部１７は、更新演算処理が収束したか否かを判定する。更新演算処理が収束していない場合には、再びステップＳ７０に戻り、収束した場合には、次のステップＳ９０に進む。
【００７７】
最後に、ステップＳ９０において、最適経路選択部１８は、起点ノードｏから開始して目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、起点ノードｏから目的点ノードｄへの最適経路を選択する。そして、得られた最適経路と最小重みを最適経路記憶部１３に保存するとともに、表示装置５に表示した地図上に最適経路と最小重みを表示する。
【００７８】
このように、Ｑ値記憶部１２に既に保存されている各Ｑ値を初期値として、更新演算処理を実行することで、重みが変化したリンクに関係するＱ値のみが更新され、それ以外のＱ値は更新されないので、更新演算処理は速やかに収束し、短時間で新たな最適経路を算出することができる。
【００７９】
最後に、最適経路以外の次善経路を探索する処理について説明する。
【００８０】
図７は、最適経路探索装置１による次善経路探索の流れを表すフローチャートである。
【００８１】
まず、ステップＳ１００において、図５又は図６で説明した処理により、最適経路の探索が行われ、各Ｑ値がＱ値記憶部１２に保存されるとともに、最適経路（ｉ０（＝ｏ），ｉ１，ｉ２，…，ｉｎ（＝ｄ））が最適経路記憶部１３に保存される。ここで、最適経路のパスの長さ（最適経路を構成するリンクの数）をｎとする。
【００８２】
次に、ステップＳ１１０において、入力装置３から使用者によりｍ番目の次善経路の探索指示が入力されると、次善Ｑ値選択部１９は、インデックスｋを０に設定する。
【００８３】
次に、ステップＳ１２０において、次善Ｑ値選択部１９は、最適経路上のｋ番目のノードｉｋに対して、起点ノードｏからｋ番目のノードｉｋまでの重みの合計値と、当該ノードｉｋを起点とするＱ値のうちｍ番目に小さいＱ値（以下「次善Ｑ値」という。）の和を計算する。得られた重みの和を「候補次善重み」と呼びＴｔｅｍｐ（ｉｋ）と記す。
【００８４】
例えば、ノードｉｋを始点とするリンクが｛ｌｉｋ，ｉｐ，ｌｉｋ，ｉｑ，ｌｉｋ，ｉｒ｝であり、それぞれのリンクに対応するＱ値がＱｄ（ｉｋ，ｉｐ），Ｑｄ（ｉｋ，ｉｑ），Ｑｄ（ｉｋ，ｉｒ）（Ｑｄ（ｉｋ，ｉｐ）＜Ｑｄ（ｉｋ，ｉｑ）＜Ｑｄ（ｉｋ，ｉｒ））とする。この場合、ｍ＝２であれば、次善Ｑ値選択部１９は、候補次善重みＴｔｅｍｐ（ｉｋ）を、
【００８５】
【数８】
により算出する。
【００８６】
次に、ステップＳ１３０において、次善Ｑ値選択部１９は、ｋがｎ−１以下であればｋを１だけインクリメント（ステップＳ１４０）してステップＳ１２０に戻り、ｋ＞ｎ−１となったときに、次のステップＳ１５０に移行する。これにより、ｎ個の候補次善重みＴｔｅｍｐ（ｉｋ）が算出される。
【００８７】
ステップＳ１５０において、次善Ｑ値選択部１９は、ｎ個の候補次善重みＴｔｅｍｐ（ｉｋ）（ｋ＝０，１，…，ｎ−１）のうち、ｍ番目に小さい候補次善重みＴｔｅｍｐ（ｉｋ）（以下「次善重み」という。）に対応するノードｉξを選出する。そして、次善経路選択部２０は、ノードｉξの次善Ｑ値Ｑｄ（ｉξ，ｊη）に対応するリンクｌｉξ，ｊηの終点ノードｊを最初のノードとして、ノードｊηから目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、最適経路を選択する。そして、既に求められている起点ノードｏからノードｉξまでの最適経路と、前記リンクｌｉξ，ｊηと、ノードｊηから目的点ノードｄまでの最適経路とを結合して次善経路（ｉ０（＝ｏ），ｉ１，ｉ２，…，ｉξ，ｊη，…，ｉｎ（＝ｄ））を生成する。最後に、次善経路選択部２０は、生成された次善経路を、表示装置５に表示した地図上に最適経路と次善重みを表示する。
【００８８】
以上の処理により、本実施例の最適経路探索装置１によれば、次善経路を容易に計算することができる。
【００８９】
尚、本実施例では、本発明の最適経路探索装置を道路ネットワークにおける最適経路を演算する場合に適用した例について説明したが、本発明の最適経路探索装置は道路ネットワークに限らず、コンピュータネットワーク、その他、複数のノードと各ノード間を結ぶ複数のリンクとから構成され各リンクに重みが与えられたネットワークに対して同様に適用することが可能である。
【図面の簡単な説明】
【００９０】
【図１】道路ネットワークの一例を表す図である。
【図２】実施例１に係る最適経路探索装置のハードウェア構成を表す図である。
【図３】実施例１に係る最適経路探索装置の機能構成を表す図である。
【図４】道路ネットワークのグラフ表現のデータの例を説明する図である。
【図５】最適経路探索装置１による最適経路探索方法の流れを表すフローチャートである。
【図６】重みが変化した場合の最適経路探索装置１による最適経路探索方法の流れを表すフローチャートである。
【図７】最適経路探索装置１による次善経路探索の流れを表すフローチャートである。
【符号の説明】
【００９１】
１ 最適経路探索装置
２ マイクロコントローラ
３ 入力装置
４ 記憶装置
５ 表示装置
６ ＶＩＣＳ受信装置
１０ ネットワーク記憶部
１１ 重み記憶部
１２ Ｑ値記憶部
１３ 最適経路記憶部
１４ 重み更新部
１５ 起終点対設定部
１６ Ｑ値初期化部
１７ Ｑ値更新部
１８ 最適経路選択部
１９ 次善Ｑ値選択部
２０ 次善経路選択部
【技術分野】
【０００１】
本発明は、道路ネットワーク、コンピュータネットワーク等の複数のノードと各ノード間を結ぶ複数のリンクとから構成され各リンクに重みが与えられたネットワークにおいて、重みが最も小さい経路やｎ番目に小さい経路を探索する最適経路探索技術に関する。
【背景技術】
【０００２】
近年、移動車輛において道路交通情報通信システム（Vehicle Information and Communication System：ＶＩＣＳ）によりリアルタイムに交通情報を取得し、該交通情報に基づいて目的地への最適経路を得るカーナビゲーションシステムが開発されている。目的地への最適経路は、ドライバーの選択にも依るが、通常は、現在地から目的地までの旅行時間（traveling time）が最小の経路が「最適経路（optimal route）」とされる。
【０００３】
また、インターネット等のコンピュータネットワークにおいては、ネットワーク上のあるコンピュータから別のコンピュータへ情報を送信するため、コンピュータネットワーク上での経路を見つけだすルーティングという処理が行われる。このルーティングにおいては、情報の転送時間を短縮するため、コンピュータ間の転送時間が最小となる「最適経路」の探索が行われる。
【０００４】
このような、最適経路の探索には、従来からダイクストラ（Dijkstra）法が広く用いられている（非特許文献１，２，３参照）。
【０００５】
上記道路ネットワークやコンピュータネットワークは、複数のノードと各ノード間を結ぶ複数のリンクとから構成され各リンクに重み（移動時間や転送時間等を）が与えられた重み付き有向グラフＧ＝（Ｎ，Ｅ）として抽象化される。ダイクストラ法では、有向グラフＧ＝（Ｎ，Ｅ）の各リンクの重みがすべて非負の場合に、起点ノードｏから目的点ノードｄに至るリンクの重みの和が最小となる最適経路を計算する。
【０００６】
ネットワーク内のすべてのノードの集合をＮ、起点ノードｏからの最終的な最短路重みが既に定まっているノードの集合をＳ、Ｓの補集合をＴ、ノードｉからノードｊへ向かうリンクをｌｉ，ｊ、リンクｌｉ，ｊの重みをｔｉ，ｊとする。一般的なダイクストラ法では、次のようにして最適経路が演算される（例えば、非特許文献３参照）。
【０００７】
まず初期設定として、
【０００８】
【数１】
とし、更に、起点ノードｏ以外の各ノードｉ（∈Ｔ）に対して、
【０００９】
【数２】
とする。次に、以下の操作を、Ｔが空集合となるまで反復演算する。
【００１０】
【数３】
【００１１】
以上の反復計算が終了すると、ｐ（ｊ）は起点ノードｏからノードｊへの最小重みになっている。また、点列｛ｊ，ｑ（ｊ），ｑ（ｑ（ｊ）），…｝は、その最短経路での経由点を逆順にしたものになっている。
【非特許文献１】E. Dijkstra, "A note on Two Problems in Connexion with Graphs", Numerische Malhematik 1 ,pp. 269-271, 1959.
【非特許文献２】B. Golden, "Shortest-Path Algorithms: A Companion'", Operations Research, Vol. 24, No.6. pp.1164-1168, 1976.
【非特許文献３】Ｔ．コルメン、他２名，「アルゴリズム・イントロダクション 第２巻 アルゴリズムの設計と解析手法」，近代科学社，１９９５年１２月３０日，pp.219-223.
【非特許文献４】R. Bellman, "The Theory of Dynamic Programming", Bull. Amer. Math. Soc. 60, pp.503-515. 1954.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、道路ネットワークやコンピュータネットワークでは、各リンクを通る際の旅行時間は、一定ではなく、時々刻々に動的に変化する。このように各リンクの旅行時間が動的な場合、上記ダイクストラ法では、リンクの旅行時間が変化する毎に、初期解を削除しスクラッチ（(scratch)データを削除するかラベルをつけ直すかして新しいデータを書き込めるようにすること。）してから、すべてを再計算する必要が生じるため効率が悪い。
【００１３】
また、上記ダイクストラ法では、起点ノードｏから目的点ノードｄまでの旅行時間が最小となる最適経路を求めることは可能であるが、旅行時間が２番目に小さくなる経路や、３番目に小さくなる経路のような次善経路を求めることができない。
【００１４】
そこで、本発明の第１の目的は、ネットワークにおける各リンクの重みが変化するような場合でも効率よく最適経路を計算することが可能な最適経路探索装置及び最適経路探索方法を提供することにある。
【００１５】
また、本発明の第２の目的は、起点ノードから目的点ノードまでの重みが最小となる最適経路以外に、重みがｎ番目（ｎ＝２，３，…）に小さくなる次善経路を求めることが可能な最適経路探索装置及び最適経路探索方法を提供することにある。
【課題を解決するための手段】
【００１６】
本発明に係る最適経路探索装置の第１の構成は、複数のノード及び前記各ノード間を結ぶ複数のリンクとから構成されたネットワークにおいて、当該ネットワーク内の任意の２つのノードが起点ノードｏ及び目的点ノードｄに設定されたとき、前記起点ノードｏから前記目的点ノードｄに至る経路のうち、重みが小さい経路を探索する最適経路探索装置であって、
前記ネットワークの各ノード及び各リンクの接続情報を、グラフ表現のデータとして記憶するネットワーク記憶手段と、
前記ネットワークの各リンクｌｉ，ｊ（ｉ，ｊは、それぞれ該リンクの始点ノード、終点ノードの添数）の重みｔｉ，ｊを記憶する重み記憶手段と、
前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、該ノードｉから該ノードｊを通って前記目的点ノードｄへ行くときの、前記目的点ノードｄへの最小の重みであるＱ値Ｑｄ（ｉ，ｊ）を記憶するＱ値記憶手段と、
前記ネットワーク内の各ノードの中から前記起点ノードｏ及び前記目的点ノードｄを設定する起終点対設定手段と、
前記ネットワーク内の隣接する２つのノードｉ，ｊを結ぶリンクｌｉ，ｊの該ノードｉから該ノードｊへの重みをｔｉ，ｊとしたとき、前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、ノードｉが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化し、ノードｊが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）をｔｉ，ｊに初期化し、それ以外の場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化するとともに、初期化した該Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するＱ値初期化手段と、
前記起点ノードｏから開始して、幅優先探索順に、前記ネットワークのすべてのリンクｌｉ，ｊを順次選択し、選択された該リンクｌｉ，ｊに対応する前記Ｑ値Ｑｄ（ｉ，ｊ）を、前記Ｑ値記憶手段に保存された各Ｑ値を用いて（数４）の演算により更新し、更新した前記Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するという更新演算処理を、すべての前記Ｑ値の値が収束するまで反復実行するＱ値更新手段と、
前記Ｑ値更新手段により前記Ｑ値記憶手段の前記各Ｑ値が更新された後、前記起点ノードｏから開始して前記目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、前記起点ノードｏから前記目的点ノードｄへの最適経路を選択する最適経路選択手段と、
を備えたことを特徴とする。
【００１７】
【数４】
【００１８】
この構成によれば、最適化の原理（非特許文献４参照）により、起点ノードｏから開始して目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、最終的に起点ノードｏから目的点ノードｄまで選択されるノードとリンクの列が、重みが最小となる最適経路になる。
【００１９】
また、ネットワーク内における一部のリンクの重みが変化した場合、既にＱ値記憶手段に保存された計算済みのＱ値を初期値として、Ｑ値更新手段によって上記反復計算を行えば、重みが変化したリンクに関係するＱ値のみが更新されるため、少ない反復回数で反復演算が収束する。そして、計算収束後に最適経路選択手段により最適経路の選択を行えば、最適経路の最計算結果を得ることができる。この場合、すべてのＱ値を更新する必要がないため、従来のダイクストラ法に比べ、効率よく最適経路の再計算を行うことが可能となる。
【００２０】
また、一度Ｑ値を計算してＱ値記憶手段に保存しておけば、起点ノードが変更された場合に於いても、最適経路選択手段によって、目的点ノードｄまでの最小重みと最適経路を容易に計算することができる。
【００２１】
ここで、「重み」とは、各リンクや経路に対して与えられる量であって、最適経路探索において最小化すべき量をいう。「重み」は、本発明を適用する対象によって様々なものが考えられる。例えば、道路ネットワークにおいて目的地までの最適経路の探索に本発明を適用する場合には、「重み」として、旅行時間、燃料コスト、運転の快適さの指標、その他交通に関する量（例えば、道幅、道路の勾配、通学路かどうかなどを総合した上で数値化して表現したもの）などが用いられる。
【００２２】
本発明に係る最適経路探索装置の第２の構成は、前記第１の構成に於いて、前記最適経路選択手段により選択された前記最適経路内の目的点ノードｄを除く各ノードｉ（ｉは最適経路内の各ノードの添数）に対して、前記Ｑ値Ｑｄ（ｉ，ｊ）がｎ番目（ｎ≧２）に小さいＱ値を抽出するとともに、抽出されたそれらの各Ｑ値と対応する各ノードまでの重みの和について最小値を与えるＱ値を選択する次善Ｑ値選択手段と、
前記最適経路内のリンクの内、前記次善Ｑ値選択手段により選択されたＱ値に対応するリンクｌｐ，ｑの始点ノードｐの次のリンクを該リンクｌｐ，ｑに置換するとともに、該リンクｌｐ，ｑの終点ノードｑから前記目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、次善経路を選択する次善経路選択手段と、
を備えたことを特徴とする。
【００２３】
この構成によれば、次善Ｑ値選択手段及び次善経路選択手段によって、起点ノードから目的点ノードまでの重みが最小となる最適経路以外に、重みがｎ番目（ｎ＝２，３，…）に小さくなる次善経路を容易に求めることが可能となる。
【００２４】
また、本発明に係る最適経路探索方法の第１の構成は、複数のノード及び前記各ノード間を結ぶ複数のリンクとから構成されたネットワークがグラフ表現のデータとして記憶されたネットワーク記憶手段、
前記ネットワークの各リンクｌｉ，ｊ（ｉ，ｊは、それぞれ該リンクの始点ノード、終点ノードの添数）の重みｔｉ，ｊを記憶する重み記憶手段、
及び前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、該ノードｉから該ノードｊを通って前記目的点ノードｄへ行くときの、前記目的点ノードｄへの最小の重みであるＱ値Ｑｄ（ｉ，ｊ）を記憶するＱ値記憶手段を備えたコンピュータにおいて、
前記ネットワーク内の任意の２つのノードが起点ノードｏ及び目的点ノードｄに設定されたとき、前記起点ノードｏから前記目的点ノードｄに至る経路のうち、重みが小さい経路を探索する最適経路探索方法であって、
ネットワーク記憶手段に記憶された前記ネットワークの各ノードの中から、２つのノードを選択して、前記起点ノードｏ及び前記目的点ノードｄとして設定する起終点対設定ステップと、
前記ネットワーク内の隣接する２つのノードｉ，ｊを結ぶリンクｌｉ，ｊの該ノードｉから該ノードｊへの重みをｔｉ，ｊとしたとき、前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、ノードｉが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化し、ノードｊが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）をｔｉ，ｊに初期化し、それ以外の場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化するとともに、初期化した該Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するＱ値初期化ステップと、
前記起点ノードｏから開始して、幅優先探索順に、前記ネットワークのすべてのリンクｌｉ，ｊを順次選択し、選択された該リンクｌｉ，ｊに対応する前記Ｑ値Ｑｄ（ｉ，ｊ）を、前記Ｑ値記憶手段に保存された各Ｑ値を用いて（数４）の演算により更新し、更新した前記Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するという更新演算処理を、すべての前記Ｑ値の値が収束するまで反復実行するＱ値更新ステップと、
前記Ｑ値更新手段により前記Ｑ値記憶手段の前記各Ｑ値が更新された後、前記起点ノードｏから開始して前記目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、前記起点ノードｏから前記目的点ノードｄへの最適経路を選択する最適経路選択ステップと、を有することを特徴とする。
【００２５】
本発明に係る最適経路探索方法の第２の構成は、前記第１の構成に於いて、前記最適経路選択ステップにおいて選択された前記最適経路内の目的点ノードｄを除く各ノードｉ（ｉは最適経路内の各ノードの添数）に対して、前記Ｑ値Ｑｄ（ｉ，ｊ）がｎ番目（ｎ≧２）に小さいＱ値を抽出するとともに、抽出されたそれらの各Ｑ値のうち最小のＱ値を選択する次善Ｑ値選択ステップと、
前記最適経路内のリンクの内、前記次善Ｑ値選択ステップにおいて選択されたＱ値に対応するリンクｌｐ，ｑの始点ノードｐの次のリンクを該リンクｌｐ，ｑに置換するとともに、該リンクｌｐ，ｑの終点ノードｑから前記目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、次善経路を選択する次善経路選択ステップと、を備えたことを特徴とする。
【００２６】
また、本発明に係るプログラムは、コンピュータに読み込ませて実行することによって、コンピュータを請求項１又は２に記載の最適経路探索装置として機能させることを特徴とする。
【発明の効果】
【００２７】
以上のように、本発明によれば、ネットワーク内における一部のリンクの重みが変化した場合、既にＱ値記憶手段に保存された計算済みのＱ値を初期値として、Ｑ値更新のための反復計算を行えば、Ｑ値記憶手段に記憶されたＱ値のうち重みが変化したリンクに関係するＱ値のみが更新されるため、少ない反復回数で反復演算が収束する。従って、すべてのＱ値を更新する必要がないため、従来のダイクストラ法に比べ、効率よく最適経路の再計算を行うことが可能となる。
【００２８】
また、一度Ｑ値を計算してＱ値記憶手段に保存しておけば、起点ノードが変更された場合に於いても、最適経路選択手段によって、目的点ノードｄまでの最小重みと最適経路を容易に計算することができる。
【００２９】
また、次善Ｑ値選択手段及び次善経路選択手段によって、起点ノードから目的点ノードまでの重みが最小となる最適経路以外に、重みがｎ番目（ｎ＝２，３，…）に小さくなる次善経路を容易に求めることが可能となる。
【発明を実施するための最良の形態】
【００３０】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００３１】
実施例１では、一例として、道路ネットワークにおいて、起点ノードｏから目的点ノードｄまでの重みが最小となる最適経路を演算する最適経路探索装置について説明する。
【００３２】
図１は、道路ネットワークの一例を表す図である。一般に、道路ネットワークは、交差点をノードとし２つの交差点間を結ぶ道路をリンクとし、各リンクの重みをそのリンクの重みとする、重み付き有向グラフＧ＝（Ｎ，Ｅ，ｔ）で表すことができる。ここで、Ｎはすべてのノードの集合、Ｅはすべてのリンクの集合、ｔはすべてのリンクの重みの集合である。
【００３３】
尚、この場合「重み」としては、旅行時間や燃料コストなどの交通に関する量が用いられる。
【００３４】
今、道路ネットワーク内のノード（交差点）から、起終点対（Origin-Destination pair：ＯＤ対）を選び、その起点ノード（origin node）をｏ、目的点ノード（destination node）をｄと記す。ノードｉからノードｊへのリンク（有向リンク）をｌｉ，ｊと記す。道路リンクｌｉ，ｊの重みをｔｉ，ｊと記す。また、重みが変化したとき、変化後の重みをｔ’ｉ，ｊと記す。
【００３５】
また、本明細書において、「Ｑ値」を以下のように定義する。
【００３６】
〔定義１〕
重み付き有向グラフＧ＝（Ｎ，Ｅ，ｔ）に於いて目的点ノードｄ（∈Ｎ）が与えられているとき、互いに隣接する任意のノードｉ，ｊ（∈Ｎ）に対して、ノードｉを起点ノードとしてノードｊを通って目的点ノードｄに行くときの、目的点ノードｄへの最小重みを「Ｑ値（Q value）」といい、Ｑｄ（ｉ，ｊ）と記す。
〔定義終り〕
【００３７】
図１において、「●」は起点ノード及び目的点ノードを表す。「○」は起点ノード及び目的点ノード以外のノードを表す。また、各ノード間を繋ぐ矢印はリンクを表す。
【００３８】
図２は、実施例１に係る最適経路探索装置１のハードウェア構成を表す図である。最適経路探索装置１は、マイクロコントローラ２、入力装置３、記憶装置４、表示装置５、及びＶＩＣＳ受信装置６により構成される。
入力装置３には、キーボタンやタッチパネル等が使用される。記憶装置４は、ＲＯＭ，ＲＡＭなどの内部記憶装置やハードディスク，ＤＶＤ−ＲＯＭなどの外部記憶装置が使用される。表示装置５は、液晶ディスプレイ等が使用される。これらの構成は、一般のカーナビゲーション装置を構成するコンピュータと同様である。
【００３９】
図３は、実施例１に係る最適経路探索装置１の機能構成を表した図である。
【００４０】
最適経路探索装置１は、表示装置５、ＶＩＣＳ受信装置６、ネットワーク記憶部１０、重み記憶部１１、Ｑ値記憶部１２、最適経路記憶部１３、重み更新部１４、起終点対設定部１５、Ｑ値初期化部１６、Ｑ値更新部１７、最適経路選択部１８、次善Ｑ値選択部１９、及び次善経路選択部２０を備えている。
【００４１】
尚、表示装置５及びＶＩＣＳ受信装置６は図２と同様である。ネットワーク記憶部１０、重み記憶部１１、及びＱ値記憶部１２は、記憶装置４によって実現される。また、重み更新部１４、最適経路記憶部１３、起終点対設定部１５、Ｑ値初期化部１６、Ｑ値更新部１７、最適経路選択部１８、次善Ｑ値選択部１９、及び次善経路選択部２０は、マイクロコントローラ２、入力装置３、及び記憶装置４が協働することにより実現される。
【００４２】
ＶＩＣＳ受信装置６は、道路交通情報通信システムにより無線送信される交通情報（ＶＩＣＳ情報）を受信する装置である。表示装置５は、地図情報や最適経路の情報を表示する装置であり、液晶ディスプレイ装置等によって構成される。
【００４３】
ネットワーク記憶部１０は、道路ネットワークの各ノード及び各リンクの接続情報を、グラフ表現のデータとして記憶する。グラフ表現のデータとは、例えば、図４（ｂ）に示したようなデータをいう（非特許文献３，ｐｐ．１６３−１６５参照）。図４（ｂ）は、図４（ａ）の道路ネットワークＧ＝（Ｎ，Ｅ）の各ノード及び各リンクの接続情報を、隣接リスト表現によりリスト化したデータである。この場合、接続情報は、ノード集合Ｎの各ノードに対して１つずつ、全部で｜Ｎ｜個（｜Ｎ｜は集合Ｎの要素数）のリストＡｄｊの配列からなる。各ノードｉ（∈Ｎ）に対して、隣接リストＡｄｊ［ｉ］は、リンクｌｉ，ｊ（∈Ｅ）が存在するすべてのノードｊへのポインタを含んでいる。
【００４４】
尚、グラフ表現のデータとしては、隣接リスト表現以外に隣接行列表現（非特許文献３，ｐ．１６４参照）を用いてもよい。
【００４５】
重み記憶部１１は、ネットワーク記憶部１０に記憶された道路ネットワークＧ＝（Ｎ，Ｅ）の各リンクｌｉ，ｊ（∈Ｅ）に対応して、そのリンクｌｉ，ｊの重みｔｉ，ｊが記憶される。
【００４６】
Ｑ値記憶部１２は、道路ネットワークＧ＝（Ｎ，Ｅ）内の隣接する２つのノードｉ，ｊ（∈Ｎ）の各組に対して、該ノードｉから該ノードｊを通って目的点ノードｄへ行くときの、目的点ノードｄへの最小の重みであるＱ値Ｑｄ（ｉ，ｊ）を記憶する。
【００４７】
最適経路記憶部１３は、計算された起点ノードｏから目的点ノードｄまでの最適経路や次善最適経路を記憶する。
【００４８】
重み更新部１４は、道路ネットワークＧ＝（Ｎ，Ｅ）内の各リンクｌｉ，ｊ（∈Ｅ）に対して、重みｔｉ，ｊの初期値を設定し重み記憶部１１に保存する。また、重み更新部１４は、ＶＩＣＳ受信装置６においてＶＩＣＳ情報が受信された場合に、そのＶＩＣＳ情報に含まれる情報から、該情報で指定される所定のリンクｌｉ，ｊ（∈Ｅ）の重みｔｉ，ｊを変更し、重み記憶部１１の記憶内容の更新を行う。
【００４９】
起終点対設定部１５は、道路ネットワーク内の各ノードの中から起点ノードｏ及び目的点ノードｄを設定する。起点ノードの設定は、例えば、ＧＰＳ受信装置（図示せず）により得られる現在位置に最も近いノードに設定したり、使用者が入力装置３により地図上で指定する地点に最も近いノードなどに設定される。また、目的点ノードｄは、使用者が入力装置３により地図上で指定する地点に最も近いノードなどに設定される。
【００５０】
Ｑ値初期化部１６は、道路ネットワーク内の隣接する２つのノードｉ，ｊ（∈Ｎ）の各組に対して、ノードｉが目的点ノードｄの場合にはＱ値Ｑｄ（ｉ，ｊ）を０に初期化する。ノードｊが目的点ノードｄの場合にはＱ値Ｑｄ（ｉ，ｊ）をｔｉ，ｊに初期化する。また、それ以外の場合にはＱ値Ｑｄ（ｉ，ｊ）を０に初期化する。そして、初期化した該Ｑ値Ｑｄ（ｉ，ｊ）をＱ値記憶部１２に保存する。
【００５１】
Ｑ値更新部１７は、起点ノードｏから開始して、幅優先探索順に、ネットワークのすべてのリンクｌｉ，ｊを順次選択し、選択された該リンクｌｉ，ｊに対応するＱ値Ｑｄ（ｉ，ｊ）を、Ｑ値記憶部１２に保存された各Ｑ値を用いて式（４ａ），（４ｂ）の演算により更新し、更新したＱ値Ｑｄ（ｉ，ｊ）をＱ値記憶部１２に保存するという更新演算処理を、すべてのＱ値の値が収束するまで反復実行する。
【００５２】
最適経路選択部１８は、Ｑ値更新部１７によりＱ値記憶部１２の各Ｑ値が更新された後、起点ノードｏから開始して目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、起点ノードｏから目的点ノードｄへの最適経路を選択する。選択された最適経路のノード列の情報及び最短重み（最適経路を辿ったときの起点ノードｏから目的点ノードｄに至る経路の各リンクの重みの和）は、最適経路記憶部１３に保存されるとともに、表示装置５に表示された地図上に表示される。
【００５３】
次善Ｑ値選択部１９は、最適経路記憶部１３に記憶された最適経路内の目的点ノードｄを除く各ノードｉ（ｉは最適経路内の各ノードの添数）に対して、Ｑ値Ｑｄ（ｉ，ｊ）がｎ番目（ｎ≧２）に小さいＱ値を抽出するとともに、抽出されたそれらの各Ｑ値のうち最小のＱ値を選択する。
【００５４】
次善経路選択部２０は、最適経路内のリンクのうち、次善Ｑ値選択部１９により選択されたＱ値に対応するリンクｌｐ，ｑの始点ノードｐの次のリンクを該リンクｌｐ，ｑに置換するとともに、該リンクｌｐ，ｑの終点ノードｑから目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、次善経路を選択する。選択された次善経路は、表示装置５に表示された地図上に表示される。
【００５５】
尚、最適経路探索装置１のこれらの機能は、プログラムとして提供され、該プログラムを記憶装置４に読み込み、マイクロコントローラ２によって実行することによって実現される。
【００５６】
以上のように構成された本実施例の最適経路探索装置１において、以下その動作を説明する。
【００５７】
図５は、最適経路探索装置１による最適経路探索方法の流れを表すフローチャートである。
【００５８】
まず、ステップＳ１０において、重み更新部１４は、ネットワーク記憶部１０に記憶された道路ネットワークＧ＝（Ｎ，Ｅ）の各リンクｌｉ，ｊ（∈Ｅ）に対して、重みの初期値ｔｉ，ｊを設定し、Ｑ値記憶部１２に保存する。尚、重みの初期値ｔｉ，ｊは、予め記憶装置４に地図情報と共に記憶されているものが使用される。
【００５９】
また、起終点対設定部１５は、道路ネットワークＧ＝（Ｎ，Ｅ）の各ノードの中から、起点ノードｏと目的点ノードｄを設定する。起点ノードｏと目的点ノードｄの設定は、上述したように、ＧＰＳ受信装置（図示せず）により得られる現在位置に最も近いノードを設定したり、使用者が入力装置３により地図上で指定する地点に最も近いノードを設定する。
【００６０】
次に、ステップＳ２０において、Ｑ値初期化部１６は、Ｑ値記憶部１２のＱ値の初期化を行う。いま、Ｑ値Ｑｄ（ｉ，ｊ）の初期値をＱｄ（０）（ｉ，ｊ）で表す。尚、上付添字「（０）」は、Ｑ値更新部１７における反復処理のイタレーション（iteration）の回数を表している（初期状態では反復処理は行われていないので、イタレーションの回数は０である）。Ｑ値初期化部１６によるＱ値初期化の初期化処理は、次式により表される。
【００６１】
【数５】
【００６２】
ここで、Ａ（ｉ）は、ノードｉに接続するノードの添数の集合を表す。Ｂ（ｄ）は、目的点ノードｄへ直接移動することが可能なノードの添数の集合である。Ｎｄは、目的点ノードの交差点の添数の集合である。
【００６３】
次に、ステップＳ３０において、Ｑ値更新部１７は、起点ノードｏから開始して、幅優先探索順に、前記ネットワークのすべてのリンクｌｉ，ｊを順次選択する。そして、選択された該リンクｌｉ，ｊに対応するＱ値Ｑｄ（ｉ，ｊ）を、Ｑ値記憶部１２に保存された各Ｑ値を用いて式（４ａ），（４ｂ）の演算により更新し、更新したＱ値Ｑｄ（ｉ，ｊ）をＱ値記憶部１２に保存する。この処理を「更新演算処理」と呼ぶ。尚、幅優先探索順とは、一般的な幅優先探索（breadth-first search）における探索順序をいう（非特許文献３，ｐ．１６６−１６８参照）。
【００６４】
次に、ステップＳ４０において、Ｑ値更新部１７は、更新演算処理が収束したか否かを判定する。「更新演算処理が収束した」とは、ステップＳ３０の更新演算処理において、すべてのＱ値Ｑｄ（ｉ，ｊ）が更新前の値と更新後の値の差が所定の判定閾値ε以下となったことをいう。すなわち、
【００６５】
【数６】
のときに「更新演算処理が収束した」と判定される。ここで、判定閾値εは充分小さな正の数値に設定される。
【００６６】
更新演算処理が収束していない場合には、再びステップＳ３０に戻り、収束した場合には、次のステップＳ５０に進む。
【００６７】
ステップＳ５０において、最適経路選択部１８は、起点ノードｏから開始して目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、起点ノードｏから目的点ノードｄへの最適経路を選択する。これにより、最適経路として、ノードの配列（ｉ０（＝ｏ），ｉ１，ｉ２，…，ｉｎ（＝ｄ））と、起点ノードｏから目的点ノードｄまでの最小重みｔｍｉｎ（ｏ，ｄ）が得られる。
【００６８】
【数７】
【００６９】
ここで、Ｑｄ（ｉ，ｊ）は、上述のように、目的点ノードがｄである場合に、ノードｉにおいて次の移動先としてノードｊを選んだときの、ノードｉから目的点ノードｄまでの最小重みを示している。従って、ノードｉから移動するノードは、ｊ（∈Ａ（ｉ））の中でＱｄ（ｉ，ｊ）が最小となるノードとなる。同様にして、ノードｊでは、ノードｊから移動可能なノードｋ（∈Ａ（ｊ））の中でＱｄ（ｉ，ｊ）が最小となるノードが選ばれる。このような原理によって、起点ノードｏから目的点ノードｄまでの最適経路が求まるのである。
【００７０】
最適経路選択部１８は、得られた最適経路（ｉ０（＝ｏ），ｉ１，ｉ２，…，ｉｎ（＝ｄ））と最小重みｔｍｉｎ（ｏ，ｄ）を最適経路記憶部１３に保存するとともに、表示装置５に表示した地図上に最適経路と最小重みを表示する。
【００７１】
尚、本実施例の最適経路探索装置１では、Ｑｄ（ｉ，ｊ）の定義から、起点ノードｏのみならず、すべてのノードから目的点ノードｄまでの最適経路を計算することが可能となる。従って、目的点ノードｄがそのままで起点ノードｏが変化した場合でも、即座に目的点ノードｄまでの最適経路を再計算することができる。
【００７２】
次に、一部のリンクの重みが変化した場合の動作について説明する。
【００７３】
図６は、重みが変化した場合の最適経路探索装置１による最適経路探索方法の流れを表すフローチャートである。
【００７４】
まず、ステップＳ６０において、重み記憶部１１に保存された重みのうちの一乃至複数が更新されて変化する。重みの更新は、ＶＩＣＳ受信装置６がＶＩＣＳ情報を受信し、当該ＶＩＣＳ情報の中に、渋滞や工事などにより一部のリンクの重みが変更される情報が含まれている場合、重み更新部１４はそのＶＩＣＳ情報に従って、特定のリンクの重みｔｉ，ｊをｔ’ｉ，ｊに更新し、重み記憶部１１に保存する。
【００７５】
次に、ステップＳ７０において、Ｑ値更新部１７は、Ｑ値記憶部１２に既に保存されている各Ｑ値を初期値として、重み記憶部１１に更新・保存された重みを用いて、前述の更新演算処理を実行する。
【００７６】
次に、ステップＳ８０において、Ｑ値更新部１７は、更新演算処理が収束したか否かを判定する。更新演算処理が収束していない場合には、再びステップＳ７０に戻り、収束した場合には、次のステップＳ９０に進む。
【００７７】
最後に、ステップＳ９０において、最適経路選択部１８は、起点ノードｏから開始して目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、起点ノードｏから目的点ノードｄへの最適経路を選択する。そして、得られた最適経路と最小重みを最適経路記憶部１３に保存するとともに、表示装置５に表示した地図上に最適経路と最小重みを表示する。
【００７８】
このように、Ｑ値記憶部１２に既に保存されている各Ｑ値を初期値として、更新演算処理を実行することで、重みが変化したリンクに関係するＱ値のみが更新され、それ以外のＱ値は更新されないので、更新演算処理は速やかに収束し、短時間で新たな最適経路を算出することができる。
【００７９】
最後に、最適経路以外の次善経路を探索する処理について説明する。
【００８０】
図７は、最適経路探索装置１による次善経路探索の流れを表すフローチャートである。
【００８１】
まず、ステップＳ１００において、図５又は図６で説明した処理により、最適経路の探索が行われ、各Ｑ値がＱ値記憶部１２に保存されるとともに、最適経路（ｉ０（＝ｏ），ｉ１，ｉ２，…，ｉｎ（＝ｄ））が最適経路記憶部１３に保存される。ここで、最適経路のパスの長さ（最適経路を構成するリンクの数）をｎとする。
【００８２】
次に、ステップＳ１１０において、入力装置３から使用者によりｍ番目の次善経路の探索指示が入力されると、次善Ｑ値選択部１９は、インデックスｋを０に設定する。
【００８３】
次に、ステップＳ１２０において、次善Ｑ値選択部１９は、最適経路上のｋ番目のノードｉｋに対して、起点ノードｏからｋ番目のノードｉｋまでの重みの合計値と、当該ノードｉｋを起点とするＱ値のうちｍ番目に小さいＱ値（以下「次善Ｑ値」という。）の和を計算する。得られた重みの和を「候補次善重み」と呼びＴｔｅｍｐ（ｉｋ）と記す。
【００８４】
例えば、ノードｉｋを始点とするリンクが｛ｌｉｋ，ｉｐ，ｌｉｋ，ｉｑ，ｌｉｋ，ｉｒ｝であり、それぞれのリンクに対応するＱ値がＱｄ（ｉｋ，ｉｐ），Ｑｄ（ｉｋ，ｉｑ），Ｑｄ（ｉｋ，ｉｒ）（Ｑｄ（ｉｋ，ｉｐ）＜Ｑｄ（ｉｋ，ｉｑ）＜Ｑｄ（ｉｋ，ｉｒ））とする。この場合、ｍ＝２であれば、次善Ｑ値選択部１９は、候補次善重みＴｔｅｍｐ（ｉｋ）を、
【００８５】
【数８】
により算出する。
【００８６】
次に、ステップＳ１３０において、次善Ｑ値選択部１９は、ｋがｎ−１以下であればｋを１だけインクリメント（ステップＳ１４０）してステップＳ１２０に戻り、ｋ＞ｎ−１となったときに、次のステップＳ１５０に移行する。これにより、ｎ個の候補次善重みＴｔｅｍｐ（ｉｋ）が算出される。
【００８７】
ステップＳ１５０において、次善Ｑ値選択部１９は、ｎ個の候補次善重みＴｔｅｍｐ（ｉｋ）（ｋ＝０，１，…，ｎ−１）のうち、ｍ番目に小さい候補次善重みＴｔｅｍｐ（ｉｋ）（以下「次善重み」という。）に対応するノードｉξを選出する。そして、次善経路選択部２０は、ノードｉξの次善Ｑ値Ｑｄ（ｉξ，ｊη）に対応するリンクｌｉξ，ｊηの終点ノードｊを最初のノードとして、ノードｊηから目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、最適経路を選択する。そして、既に求められている起点ノードｏからノードｉξまでの最適経路と、前記リンクｌｉξ，ｊηと、ノードｊηから目的点ノードｄまでの最適経路とを結合して次善経路（ｉ０（＝ｏ），ｉ１，ｉ２，…，ｉξ，ｊη，…，ｉｎ（＝ｄ））を生成する。最後に、次善経路選択部２０は、生成された次善経路を、表示装置５に表示した地図上に最適経路と次善重みを表示する。
【００８８】
以上の処理により、本実施例の最適経路探索装置１によれば、次善経路を容易に計算することができる。
【００８９】
尚、本実施例では、本発明の最適経路探索装置を道路ネットワークにおける最適経路を演算する場合に適用した例について説明したが、本発明の最適経路探索装置は道路ネットワークに限らず、コンピュータネットワーク、その他、複数のノードと各ノード間を結ぶ複数のリンクとから構成され各リンクに重みが与えられたネットワークに対して同様に適用することが可能である。
【図面の簡単な説明】
【００９０】
【図１】道路ネットワークの一例を表す図である。
【図２】実施例１に係る最適経路探索装置のハードウェア構成を表す図である。
【図３】実施例１に係る最適経路探索装置の機能構成を表す図である。
【図４】道路ネットワークのグラフ表現のデータの例を説明する図である。
【図５】最適経路探索装置１による最適経路探索方法の流れを表すフローチャートである。
【図６】重みが変化した場合の最適経路探索装置１による最適経路探索方法の流れを表すフローチャートである。
【図７】最適経路探索装置１による次善経路探索の流れを表すフローチャートである。
【符号の説明】
【００９１】
１ 最適経路探索装置
２ マイクロコントローラ
３ 入力装置
４ 記憶装置
５ 表示装置
６ ＶＩＣＳ受信装置
１０ ネットワーク記憶部
１１ 重み記憶部
１２ Ｑ値記憶部
１３ 最適経路記憶部
１４ 重み更新部
１５ 起終点対設定部
１６ Ｑ値初期化部
１７ Ｑ値更新部
１８ 最適経路選択部
１９ 次善Ｑ値選択部
２０ 次善経路選択部
【特許請求の範囲】
【請求項１】
複数のノード及び前記各ノード間を結ぶ複数のリンクとから構成されたネットワークにおいて、当該ネットワーク内の任意の２つのノードが起点ノードｏ及び目的点ノードｄに設定されたとき、前記起点ノードｏから前記目的点ノードｄに至る経路のうち、重みが小さい経路を探索する最適経路探索装置であって、
前記ネットワークの各ノード及び各リンクの接続情報を、グラフ表現のデータとして記憶するネットワーク記憶手段と、
前記ネットワークの各リンクｌｉ，ｊ（ｉ，ｊは、それぞれ該リンクの始点及び終点の添数）の重みｔｉ，ｊを記憶する重み記憶手段と、
前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、該ノードｉから該ノードｊを通って前記目的点ノードｄへ行くときの、前記目的点ノードｄへの最小の重みであるＱ値Ｑｄ（ｉ，ｊ）を記憶するＱ値記憶手段と、
前記ネットワーク内の各ノードの中から前記起点ノードｏ及び前記目的点ノードｄを設定する起終点対設定手段と、
前記ネットワーク内の隣接する２つのノードｉ，ｊを結ぶリンクｌｉ，ｊの該ノードｉから該ノードｊへの重みをｔｉ，ｊとしたとき、前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、ノードｉが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化し、ノードｊが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）をｔｉ，ｊに初期化し、それ以外の場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化するとともに、初期化した該Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するＱ値初期化手段と、
前記起点ノードｏから開始して、幅優先探索順に、前記ネットワークのすべてのリンクｌｉ，ｊを順次選択し、選択された該リンクｌｉ，ｊに対応する前記Ｑ値Ｑｄ（ｉ，ｊ）を、前記Ｑ値記憶手段に保存された各Ｑ値を用いて（数１）の演算により更新し、更新した前記Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するという更新演算処理を、すべての前記Ｑ値の値が収束するまで反復実行するＱ値更新手段と、
前記Ｑ値更新手段により前記Ｑ値記憶手段の前記各Ｑ値が更新された後、前記起点ノードｏから開始して前記目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、前記起点ノードｏから前記目的点ノードｄへの最適経路を選択する最適経路選択手段と、
を備えたことを特徴とする最適経路探索装置。
【数１】
【請求項２】
前記最適経路選択手段により選択された前記最適経路内の目的点ノードｄを除く各ノードｉ（ｉは最適経路内の各ノードの添数）に対して、前記Ｑ値Ｑｄ（ｉ，ｊ）がｎ番目（ｎ≧２）に小さいＱ値を抽出するとともに、抽出されたそれらの各Ｑ値と対応する各ノードまでの重みの和について最小値を与えるＱ値を選択する次善Ｑ値選択手段と、
前記最適経路内のリンクの内、前記次善Ｑ値選択手段により選択されたＱ値に対応するリンクｌｐ，ｑの始点ノードｐの次のリンクを該リンクｌｐ，ｑに置換するとともに、該リンクｌｐ，ｑの終点ノードｑから前記目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、次善経路を選択する次善経路選択手段と、
を備えたことを特徴とする請求項１記載の最適経路探索装置。
【請求項３】
複数のノード及び前記各ノード間を結ぶ複数のリンクとから構成されたネットワークがグラフ表現のデータとして記憶されたネットワーク記憶手段、
前記ネットワークの各リンクｌｉ，ｊ（ｉ，ｊは、それぞれ該リンクの始点ノード、終点ノードの添数）の重みｔｉ，ｊを記憶する重み記憶手段、
及び前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、該ノードｉから該ノードｊを通って前記目的点ノードｄへ行くときの、前記目的点ノードｄへの最小の重みであるＱ値Ｑｄ（ｉ，ｊ）を記憶するＱ値記憶手段を備えたコンピュータにおいて、
前記ネットワーク内の任意の２つのノードが起点ノードｏ及び目的点ノードｄに設定されたとき、前記起点ノードｏから前記目的点ノードｄに至る経路のうち、重みが小さい経路を探索する最適経路探索方法であって、
ネットワーク記憶手段に記憶された前記ネットワークの各ノードの中から、２つのノードを選択して、前記起点ノードｏ及び前記目的点ノードｄとして設定する起終点対設定ステップと、
前記ネットワーク内の隣接する２つのノードｉ，ｊを結ぶリンクｌｉ，ｊの該ノードｉから該ノードｊへの重みをｔｉ，ｊとしたとき、前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、ノードｉが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化し、ノードｊが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）をｔｉ，ｊに初期化し、それ以外の場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化するとともに、初期化した該Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するＱ値初期化ステップと、
前記起点ノードｏから開始して、幅優先探索順に、前記ネットワークのすべてのリンクｌｉ，ｊを順次選択し、選択された該リンクｌｉ，ｊに対応する前記Ｑ値Ｑｄ（ｉ，ｊ）を、前記Ｑ値記憶手段に保存された各Ｑ値を用いて（数２）の演算により更新し、更新した前記Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するという更新演算処理を、すべての前記Ｑ値の値が収束するまで反復実行するＱ値更新ステップと、
前記Ｑ値更新手段により前記Ｑ値記憶手段の前記各Ｑ値が更新された後、前記起点ノードｏから開始して前記目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、前記起点ノードｏから前記目的点ノードｄへの最適経路を選択する最適経路選択ステップと、
を有することを特徴とする最適経路探索方法。
【数２】
【請求項４】
前記最適経路選択ステップにおいて選択された前記最適経路内の目的点ノードｄを除く各ノードｉ（ｉは最適経路内の各ノードの添数）に対して、前記Ｑ値Ｑｄ（ｉ，ｊ）がｎ番目（ｎ≧２）に小さいＱ値を抽出するとともに、抽出されたそれらの各Ｑ値と対応する各ノードまでの重みの和について最小値を与えるＱ値を選択する次善Ｑ値選択ステップと、
前記最適経路内のリンクの内、前記次善Ｑ値選択ステップにおいて選択されたＱ値に対応するリンクｌｐ，ｑの始点ノードｐの次のリンクを該リンクｌｐ，ｑに置換するとともに、該リンクｌｐ，ｑの終点ノードｑから前記目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、次善経路を選択する次善経路選択ステップと、
を備えたことを特徴とする請求項３記載の最適経路探索方法。
【請求項５】
コンピュータに読み込ませて実行することによって、コンピュータを請求項１又は２に記載の最適経路探索装置として機能させることを特徴とするプログラム。
【請求項１】
複数のノード及び前記各ノード間を結ぶ複数のリンクとから構成されたネットワークにおいて、当該ネットワーク内の任意の２つのノードが起点ノードｏ及び目的点ノードｄに設定されたとき、前記起点ノードｏから前記目的点ノードｄに至る経路のうち、重みが小さい経路を探索する最適経路探索装置であって、
前記ネットワークの各ノード及び各リンクの接続情報を、グラフ表現のデータとして記憶するネットワーク記憶手段と、
前記ネットワークの各リンクｌｉ，ｊ（ｉ，ｊは、それぞれ該リンクの始点及び終点の添数）の重みｔｉ，ｊを記憶する重み記憶手段と、
前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、該ノードｉから該ノードｊを通って前記目的点ノードｄへ行くときの、前記目的点ノードｄへの最小の重みであるＱ値Ｑｄ（ｉ，ｊ）を記憶するＱ値記憶手段と、
前記ネットワーク内の各ノードの中から前記起点ノードｏ及び前記目的点ノードｄを設定する起終点対設定手段と、
前記ネットワーク内の隣接する２つのノードｉ，ｊを結ぶリンクｌｉ，ｊの該ノードｉから該ノードｊへの重みをｔｉ，ｊとしたとき、前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、ノードｉが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化し、ノードｊが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）をｔｉ，ｊに初期化し、それ以外の場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化するとともに、初期化した該Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するＱ値初期化手段と、
前記起点ノードｏから開始して、幅優先探索順に、前記ネットワークのすべてのリンクｌｉ，ｊを順次選択し、選択された該リンクｌｉ，ｊに対応する前記Ｑ値Ｑｄ（ｉ，ｊ）を、前記Ｑ値記憶手段に保存された各Ｑ値を用いて（数１）の演算により更新し、更新した前記Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するという更新演算処理を、すべての前記Ｑ値の値が収束するまで反復実行するＱ値更新手段と、
前記Ｑ値更新手段により前記Ｑ値記憶手段の前記各Ｑ値が更新された後、前記起点ノードｏから開始して前記目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、前記起点ノードｏから前記目的点ノードｄへの最適経路を選択する最適経路選択手段と、
を備えたことを特徴とする最適経路探索装置。
【数１】
【請求項２】
前記最適経路選択手段により選択された前記最適経路内の目的点ノードｄを除く各ノードｉ（ｉは最適経路内の各ノードの添数）に対して、前記Ｑ値Ｑｄ（ｉ，ｊ）がｎ番目（ｎ≧２）に小さいＱ値を抽出するとともに、抽出されたそれらの各Ｑ値と対応する各ノードまでの重みの和について最小値を与えるＱ値を選択する次善Ｑ値選択手段と、
前記最適経路内のリンクの内、前記次善Ｑ値選択手段により選択されたＱ値に対応するリンクｌｐ，ｑの始点ノードｐの次のリンクを該リンクｌｐ，ｑに置換するとともに、該リンクｌｐ，ｑの終点ノードｑから前記目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、次善経路を選択する次善経路選択手段と、
を備えたことを特徴とする請求項１記載の最適経路探索装置。
【請求項３】
複数のノード及び前記各ノード間を結ぶ複数のリンクとから構成されたネットワークがグラフ表現のデータとして記憶されたネットワーク記憶手段、
前記ネットワークの各リンクｌｉ，ｊ（ｉ，ｊは、それぞれ該リンクの始点ノード、終点ノードの添数）の重みｔｉ，ｊを記憶する重み記憶手段、
及び前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、該ノードｉから該ノードｊを通って前記目的点ノードｄへ行くときの、前記目的点ノードｄへの最小の重みであるＱ値Ｑｄ（ｉ，ｊ）を記憶するＱ値記憶手段を備えたコンピュータにおいて、
前記ネットワーク内の任意の２つのノードが起点ノードｏ及び目的点ノードｄに設定されたとき、前記起点ノードｏから前記目的点ノードｄに至る経路のうち、重みが小さい経路を探索する最適経路探索方法であって、
ネットワーク記憶手段に記憶された前記ネットワークの各ノードの中から、２つのノードを選択して、前記起点ノードｏ及び前記目的点ノードｄとして設定する起終点対設定ステップと、
前記ネットワーク内の隣接する２つのノードｉ，ｊを結ぶリンクｌｉ，ｊの該ノードｉから該ノードｊへの重みをｔｉ，ｊとしたとき、前記ネットワーク内の隣接する２つのノードｉ，ｊの各組に対して、ノードｉが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化し、ノードｊが前記目的点ノードｄの場合には前記Ｑ値Ｑｄ（ｉ，ｊ）をｔｉ，ｊに初期化し、それ以外の場合には前記Ｑ値Ｑｄ（ｉ，ｊ）を０に初期化するとともに、初期化した該Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するＱ値初期化ステップと、
前記起点ノードｏから開始して、幅優先探索順に、前記ネットワークのすべてのリンクｌｉ，ｊを順次選択し、選択された該リンクｌｉ，ｊに対応する前記Ｑ値Ｑｄ（ｉ，ｊ）を、前記Ｑ値記憶手段に保存された各Ｑ値を用いて（数２）の演算により更新し、更新した前記Ｑ値Ｑｄ（ｉ，ｊ）を前記Ｑ値記憶手段に保存するという更新演算処理を、すべての前記Ｑ値の値が収束するまで反復実行するＱ値更新ステップと、
前記Ｑ値更新手段により前記Ｑ値記憶手段の前記各Ｑ値が更新された後、前記起点ノードｏから開始して前記目的点ノードｄに至るまで、各ノードを始点とするＱ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、前記起点ノードｏから前記目的点ノードｄへの最適経路を選択する最適経路選択ステップと、
を有することを特徴とする最適経路探索方法。
【数２】
【請求項４】
前記最適経路選択ステップにおいて選択された前記最適経路内の目的点ノードｄを除く各ノードｉ（ｉは最適経路内の各ノードの添数）に対して、前記Ｑ値Ｑｄ（ｉ，ｊ）がｎ番目（ｎ≧２）に小さいＱ値を抽出するとともに、抽出されたそれらの各Ｑ値と対応する各ノードまでの重みの和について最小値を与えるＱ値を選択する次善Ｑ値選択ステップと、
前記最適経路内のリンクの内、前記次善Ｑ値選択ステップにおいて選択されたＱ値に対応するリンクｌｐ，ｑの始点ノードｐの次のリンクを該リンクｌｐ，ｑに置換するとともに、該リンクｌｐ，ｑの終点ノードｑから前記目的点ノードｄまで、各ノードにおいてＱ値が最小となるリンクを次のリンクとして選択してゆくことで、次善経路を選択する次善経路選択ステップと、
を備えたことを特徴とする請求項３記載の最適経路探索方法。
【請求項５】
コンピュータに読み込ませて実行することによって、コンピュータを請求項１又は２に記載の最適経路探索装置として機能させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００９−２８８１１８（Ｐ２００９−２８８１１８Ａ）
【公開日】平成２１年１２月１０日（２００９．１２．１０）
【国際特許分類】
【出願番号】特願２００８−１４１９０１（Ｐ２００８−１４１９０１）
【出願日】平成２０年５月３０日（２００８．５．３０）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 社団法人計測自動制御学会九州支部，第２６回計測自動制御学会九州支部学術講演会予稿集，平成１９年１２月１日
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
【公開日】平成２１年１２月１０日（２００９．１２．１０）
【国際特許分類】
【出願日】平成２０年５月３０日（２００８．５．３０）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 社団法人計測自動制御学会九州支部，第２６回計測自動制御学会九州支部学術講演会予稿集，平成１９年１２月１日
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＶＩＣＳ
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
[ Back to top ]