最適経路及び最適巡回経路探索方法

発明者： , ,
出願人/特許権者： ,
代理人 (1件)：斉藤千幹
公報種別：公開公報
出願番号（国際出願番号）：特願平11-153568
公開番号（公開出願番号）：特開2000-172664
出願日： 1999年06月01日
公開日（公表日）： 2000年06月23日
要約：

【要約】【課題】少ない計算量で、かつ、短時間に全指定経由点を通過する最適経路を探索できるようにする。【解決手段】拡張遺伝子型により表現された出発地Sから目的地Gまでの経路(個体)を所定数、初期個体群として用意し、該拡張遺伝子型で表現された個体群に遺伝的アルゴリズムを繰り返し適用して全指定経由点A,Bを通る出発地から目的地までの最適経路を探索する。この場合、個体(経路)に含まれる指定経由点数に応じて重みを決定し、該個体の出発地から目的地までの距離に重みを乗じた値の逆数を遺伝的アルゴリズムにおける評価関数とする。

請求項（抜粋）：

第1の地点から指定されたN個の経由点を通って第2の地点に到る経路を探索する場合、全実ノードにおける最大接続ノード数Mと指定経由点数に1を加えた(N+1)のうち小さい方を仮想ノード数kとし、各実ノードについて戻り経路を可能にするためにk個の仮想ノードを用意し、第1の地点から第2の地点までの全通過実ノードに応じた仮想ノードを遺伝子として有すると共に、遺伝的アルゴリズムにおける交叉処理が可能な構造を有する拡張遺伝子型を設計し、該拡張遺伝子型により表現された第1の地点から第2の地点までの経路(個体)を所定数、初期個体群として用意し、該拡張遺伝子型で表現された個体群に遺伝的アルゴリズムを繰り返し適用して全指定経由点を通る第1の地点から第2の地点までの最適経路を探索する最適経路探索方法において、前記個体(経路)に含まれる指定経由点数に応じて重みを決定し、該個体の第1の地点から第2の地点までの距離に前記重みを乗じた値の逆数を遺伝的アルゴリズムにおける評価関数とする、ことを特徴とする最適経路探索方法。

IPC (3件)：

G06F 15/18 550 , G01C 21/00 , G08G 1/00

FI (3件)：

G06F 15/18 550 C , G01C 21/00 G , G08G 1/00 C

Fターム (15件)：

2F029AA02 , 2F029AB01 , 2F029AB07 , 2F029AB13 , 2F029AC02 , 2F029AC09 , 2F029AC14 , 5H180AA01 , 5H180BB13 , 5H180CC12 , 5H180EE02 , 5H180FF04 , 5H180FF05 , 5H180FF22 , 5H180FF32

前のページに戻る