Pat

J-GLOBAL ID：200903036291311075

経路探索方法及び経路探索装置

Inventor： 西村 茂樹 ,  香川 浩司
Applicant, Patent owner： 住友電気工業株式会社
Agent (1)： 亀井 弘勝 (外1名)
Gazette classification：公開公報
Application number (International application number)：1994320707
Publication number (International publication number)：1996178682
Application date： Dec. 22, 1994
Publication date： Jul. 12, 1996
Summary：

【要約】【目的】リンクとノードからなる経路ネットワークデータ上で、現在地と目的地とを結ぶ最短経路をより短時間で探索する。【構成】想定される経路コストを複数範囲に区分して、各区分に対応して、探索中のノードを記入する欄を有する複数の探索用ワークメモリを予め用意しておき、経路の探索に連れて、探索用ワークメモリの中に格納されているノードを、より経路コストの大きな探索用ワークメモリに移しかえていく。目的地までの経路が少なくとも1本探索できた時点で、当該目的地までの経路コストが、空になったワークメモリに対応する経路コスト未満のものであれば、これ以上探索をすることなく、当該目的地に至る今まで探索してきた経路を最短経路と決定する。【効果】探索する経路の数を抑えることができ、経路探索に要する時間を短縮することができる。

Claim (excerpt)：

地図上の2つの位置の間の最短経路を計算する場合に、一方の位置に最も近いリンク又はノードを探索開始リンク又はノードとし、他方の位置に最も近いリンク又はノードを探索終了リンク又はノードとし、探索開始リンク又はノードから探索終了リンク又はノードまでを含む経路ネットワークデータを取得し、この道路ネットワーク内において、探索開始リンク又はノードから始まるリンク又はノードを、コストを順次加算しながら接続していって(この加算されたコストを当該リンク又はノードの「経路コスト」という)、リンク又はノードのツリーを構成していき、探索終了リンク又はノードに到達する最もコストの少ない経路を選択する方法であって、(a) 想定される最大の経路コストを複数範囲に区分し、各区分に対応した、探索中のリンク又はノードを記入する欄を有する複数の探索用ワークメモリを用いて、(b) 探索開始リンク又はノードを、最も経路コストの低い区分の探索用ワークメモリに格納し、(c) 探索用ワークメモリの中に格納されている当該リンク又はノードに着目し、当該リンク又はノードから接続されるリンク又はノードの経路コストを求めて、接続されたリンク又はノードをそれぞれ該当する区分の探索用ワークメモリに書入れるとともに探索済の当該リンク又はノードを探索用ワークメモリから消去するという手順を繰り返し、(d) 格納したリンク又はノードが空になった探索用ワークメモリがあり、かつ、探索済のリンク又はノードの中に探索終了リンク又は探索終了ノードが含まれているかどうかを判定し、探索終了リンク又は探索終了ノードが含まれていれば、これ以上探索をすることなく、当該探索終了リンク又はノードに至る今まで探索してきた経路を最短経路として選択することを特徴とする経路探索方法。

IPC (4)：

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