Pat

J-GLOBAL ID：200903087704768684

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

Inventor： 長谷山 美紀 ,  稲垣 潤 ,  北島 秀夫
Applicant, Patent owner： 長谷山 美紀 ,  アルパイン株式会社
Agent (1)： 斉藤 千幹
Gazette classification：公開公報
Application number (International application number)：1999153568
Publication number (International publication number)：2000172664
Application date： Jun. 01, 1999
Publication date： Jun. 23, 2000
Summary：

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

Claim (excerpt)：

第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-Term (15)：

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