特許

J-GLOBAL ID：200903019427754721

経路探索システム及び経路探索方法

発明者： 岡野 裕之
出願人/特許権者： インターナショナル・ビジネス・マシーンズ・コーポレーション
代理人 (1件)： 山崎 隆 (外3名)
公報種別：公開公報
出願番号（国際出願番号）：特願2000-348459
公開番号（公開出願番号）：特開2002-154612
出願日： 2000年11月15日
公開日（公表日）： 2002年05月28日
要約：

【要約】【課題】 各経由地にソフト時間枠を設定し、経路全体のソフト時間枠コストと経路長のコスト換算値とを含む総コストにより経路を評価する場合に、経路部分としてのパス移動に伴うコスト計算を合理化する。【解決手段】 各経由地に静的ソフト時間枠関数及び動的ソフト時間枠関数を対応付ける。各経由地の動的ソフト時間枠関数=該経由地の静的ソフト時間枠関数+後ろ方向へ次の経由地の動的ソフト時間枠関数とする。パスを移動してコストの増減を調べる場合、移動対象パスの最前及び最後の経由地P1,P2、元経路における後ろ方向へP2の次の経由地P3に対して、該パスの動的ソフト時間枠関数=P1の動的ソフト時間枠関数-P3の動的ソフト時間枠関数とする。ただし、動的ソフト時間枠関数は到着時刻変数tの関数であり、右辺第2項のtは第1項のtより到着時刻差だけ増大させてある。

請求項（抜粋）：

各経由地には、到着時刻変数tについてのコスト関数でありかつペナルティコスト算出の基礎となる静的ペナルティ関数fが設定され、静的ペナルティ関数fは、各経由地の静的ペナルティ関数同士が加算可能なものとして定義されており、元経路及び試し経路を各経路についての少なくともペナルティコストCS及び長さに係る長さコストCLとを含む総コストCTに基づいて評価する経路問題における経路探索システムにおいて、経路先頭の方及び後尾の方をそれぞれ前及び後ろと呼ぶことにし、各経由地には動的ペナルティ関数が対応付けられ、経路における各経由地の動的ペナルティ関数Fを経路における最も後ろのPzから前方向へ順番に伝播形式で算出する動的ペナルティ関数加算手段を有し、該動的ペナルティ関数加算手段は、任意の経由地をP1、及びP1に対して後ろ方向へ次の経由地をP2と呼ぶことにすると、P1の動的ペナルティ関数Fは、P1の静的ペナルティ関数fにP2の動的ペナルティ関数Fを加算したものに基づいたものとして算出し、ただし、該動的ペナルティ関数加算において、P1の静的ペナルティ関数fのtに対して各P2の動的ペナルティ関数Fのtは、P2の到着時刻とP1の到着時刻との差分だけ増大させたtとされ、元経路における、或る変更対象経路部分の最も前及び最も後ろの経由地をそれぞれP1,P2(P2=P1の場合もあり得る。)、及び元経路における後ろ方向へP2の次の経由地をP3と呼ぶことにすると、動的ペナルティ関数有効判別手段により元経路におけるP1以後の経由地の動的ペナルティ関数が有効と判断されたときは、経路部分用動的ペナルティ関数算出手段は、該変更対象経路部分の動的ペナルティ関数を、P1の動的ペナルティ関数からP3の動的ペナルティ関数の減算した結果に基づいて算出し、ただし、経路部分用動的ペナルティ関数算出手段は、P3の動的ペナルティ関数のtを、P1の動的ペナルティ関数のtに対して、P3の到着時刻とP1の到着時刻との差分だけ大きいものにして算出処理を行い、元経路及び試し経路おける該変更対象経路部分のペナルティコストを、該経路部分の最も前の経由地をP1とすると、該経路部分用動的ペナルティ関数算出手段により算出した該経路部分の動的ペナルティ関数の到着時刻変数tに、それぞれ元経路及び試し経路におけるP1の到着時刻を代入して算出する経路部分用ペナルティコスト算出手段を有し、元経路及び試し経路おける変更対象経路部分のペナルティコストの対比に基づいて両経路を評価する経路評価手段を有していることを特徴とする経路探索システム。

IPC (3件)：

B65G 1/137 ,  G06F 17/60 516 ,  G06F 19/00 120

FI (3件)：

B65G 1/137 A ,  G06F 17/60 516 ,  G06F 19/00 120

Fターム (6件)：

3F022AA15 ,  3F022LL05 ,  3F022MM02 ,  3F022MM11 ,  3F022MM42 ,  3F022NN31