経路計算方法

Inventor：
Applicant, Patent owner：
Agent (1)：亀井弘勝 (外1名)
Gazette classification：公開公報
Application number (International application number)：1993178135
Publication number (International publication number)：1995036381
Application date： Jul. 19, 1993
Publication date： Feb. 07, 1995
Summary：

【要約】【目的】経由地点がある場合、出発地点から目的地点に至る経由地点を含むリンクのツリーを用いて1回で経路計算する。【構成】経路計算するときに、経由地点を含むリンクを設定し、そのリンクについてルートコスト値に十分大きな負の値を加えるとともに、当該リンク及び以後これに接続される経路に当該経由地点通過済みのステータスを与え、後に探索されたリンクが経由地点に戻ったときに、当該経由地点通過済みのステータスを有していれば、その接続リンクについての処理を打切る。【効果】経由地点を必ず通過し、しかも1回のみ通過する最適経路が、1回の経路計算により得られる。

Claim (excerpt)：

経路ネットワークを構成する各リンクのコスト及びリンク相互の接続関係を記憶した経路ネットワークメモリと、リンクごとに、リンクコストと、このリンクの次に接続される1つ又は複数の接続リンクと、このリンクの前に接続される計算済の経路上のリンクと、前記計算済の経路のルートコストとを記入する欄を有する第1のテーブルと、現在接続リンクを探索しているリンクを記入する欄を有する第2のテーブルとを用いて、(a) 出発地点、経由地点及び目的地点の設定に応じて、経路ネットワークメモリから一定範囲の経路ネットワークデータを読み出し、(b) 読み出された経路ネットワークデータに基づいて、経路ネットワークを構成する各リンクごとのリンクコスト、接続リンクを特定するとともに、各リンクのルートコストの初期値を十分大きな値に設定して、前記第1のテーブルの該当欄に書込み、(c) 出発地点を含むリンクを第2のテーブルに書込み、この第2のテーブルに書き込まれたリンクに対応する第1のテーブルのルートコスト欄を0に設定し、(d) 第2のテーブルに記入されたリンクについて、第1のテーブルを参照して接続リンクを探索し、探索された接続リンクのリンクコストを前記第2のテーブルに記入されたリンクコストに加え、この加えた値を、第1のテーブルに記入された当該接続リンクのルートコストと比較し、(e) 比較の結果、加えられた値が大きければ、その接続リンクについての処理を打切り、小さければその値を第1のテーブルの当該接続リンクのルートコストに書換えるとともに、前記第2のテーブルに記入されたリンクをこの接続リンクに到る計算済の経路上のリンクとして書込み、(f) 当該接続リンクを第2のテーブルに新たに記入して、前記(d) ,(e) の処理を繰り返し、(g) 第2のテーブルに記入された全てのリンクについて接続リンクの探索が終了したときに、目的地点を含むリンクを第1のテーブルから探し出し、そのリンクに到る計算済の経路上のリンクを順に辿っていくことにより、最適経路を決定する経路計算方法において、前記手順(d) において、探索された接続リンクが経由地点を含むリンクであるときに、前記値に十分大きな負の値を加えて比較するとともに、当該接続リンク及び以後探索されるこれに接続されるリンクに当該経由地点通過済みのステータスを与え、前記手順(d) において、探索された接続リンクが経由地点を含むリンクであるときに、この接続リンクが当該経由地点通過済みのステータスを有していれば、その接続リンクについての探索処理を打切ることを特徴とする経路計算方法。

IPC (5)：

G09B 29/10 , G01C 21/00 , G06T 1/00 , G06T 7/60 , G08G 1/0969

FI (2)：

G06F 15/62 335 , G06F 15/70 365

Return to Previous Page