Pat

J-GLOBAL ID：200903018460411060

最適経路探索装置及び最適経路探索装置並びにプログラム

Inventor： 平澤 宏太郎 ,  嶋田 香
Applicant, Patent owner： 学校法人早稲田大学
Agent (1)： 石田 和人
Gazette classification：公開公報
Application number (International application number)：2008141901
Publication number (International publication number)：2009288118
Application date： May. 30, 2008
Publication date： Dec. 10, 2009
Summary：

【課題】ネットワークにおける各リンクの通過時間が変化するような場合でも効率よく最適経路を計算することが可能な最適経路探索方法の提供。【解決手段】ネットワーク内の2つのノードを起点ノードo,目的点ノードdに設定する。ネットワーク内の隣接する2つのノードi,jの各組に対して、該ノードiから該ノードjを通って目的点ノードdへ行くときの、目的点ノードdへの最小の移動時間であるQ値Qd(i,j)=tij+mink[Qd(j,k)]を幅優先探索順に計算する。最後に、起点ノードoから開始して目的点ノードdに至るまで、各ノードを始点とするQ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、起点ノードoから目的点ノードdへの最適経路を選択する。【選択図】図3

Claim (excerpt)：

複数のノード及び前記各ノード間を結ぶ複数のリンクとから構成されたネットワークにおいて、当該ネットワーク内の任意の2つのノードが起点ノードo及び目的点ノードdに設定されたとき、前記起点ノードoから前記目的点ノードdに至る経路のうち、重みが小さい経路を探索する最適経路探索装置であって、 前記ネットワークの各ノード及び各リンクの接続情報を、グラフ表現のデータとして記憶するネットワーク記憶手段と、 前記ネットワークの各リンクli,j(i,jは、それぞれ該リンクの始点及び終点の添数)の重みti,jを記憶する重み記憶手段と、 前記ネットワーク内の隣接する2つのノードi,jの各組に対して、該ノードiから該ノードjを通って前記目的点ノードdへ行くときの、前記目的点ノードdへの最小の重みであるQ値Qd(i,j)を記憶するQ値記憶手段と、 前記ネットワーク内の各ノードの中から前記起点ノードo及び前記目的点ノードdを設定する起終点対設定手段と、 前記ネットワーク内の隣接する2つのノードi,jを結ぶリンクli,jの該ノードiから該ノードjへの重みをti,jとしたとき、前記ネットワーク内の隣接する2つのノードi,jの各組に対して、ノードiが前記目的点ノードdの場合には前記Q値Qd(i,j)を0に初期化し、ノードjが前記目的点ノードdの場合には前記Q値Qd(i,j)をti,jに初期化し、それ以外の場合には前記Q値Qd(i,j)を0に初期化するとともに、初期化した該Q値Qd(i,j)を前記Q値記憶手段に保存するQ値初期化手段と、 前記起点ノードoから開始して、幅優先探索順に、前記ネットワークのすべてのリンクli,jを順次選択し、選択された該リンクli,jに対応する前記Q値Qd(i,j)を、前記Q値記憶手段に保存された各Q値を用いて(数1)の演算により更新し、更新した前記Q値Qd(i,j)を前記Q値記憶手段に保存するという更新演算処理を、すべての前記Q値の値が収束するまで反復実行するQ値更新手段と、 前記Q値更新手段により前記Q値記憶手段の前記各Q値が更新された後、前記起点ノードoから開始して前記目的点ノードdに至るまで、各ノードを始点とするQ値が最小であるリンクを該ノードの次のリンクとし、該リンクの終点ノードを該ノードの次のノードとして順次選択してゆくことで、前記起点ノードoから前記目的点ノードdへの最適経路を選択する最適経路選択手段と、 を備えたことを特徴とする最適経路探索装置。

IPC (4)：

G01C 21/00 ,  G08G 1/096 ,  G09B 29/00 ,  G09B 29/10

FI (4)：

G01C21/00 G ,  G08G1/0969 ,  G09B29/00 A ,  G09B29/10 A

F-Term (29)：

2C032HB22 ,  2C032HB23 ,  2C032HB24 ,  2C032HC22 ,  2C032HD16 ,  2C032HD23 ,  2F129AA03 ,  2F129DD02 ,  2F129DD21 ,  2F129DD24 ,  2F129DD62 ,  2F129DD63 ,  2F129FF04 ,  2F129FF07 ,  2F129FF41 ,  2F129HH02 ,  2F129HH12 ,  2F129HH19 ,  2F129HH20 ,  5H180AA01 ,  5H180BB02 ,  5H180BB04 ,  5H180BB13 ,  5H180CC12 ,  5H180EE18 ,  5H180FF05 ,  5H180FF22 ,  5H180FF27 ,  5H180FF33