特許
J-GLOBAL ID：200903082791415600
N分割巡回経路探索システム、経路探索サーバ、N分割巡回経路探索方法
発明者：
出願人/特許権者：
代理人 (1件)：
特許業務法人ウィンテック
公報種別：公開公報
出願番号（国際出願番号）：特願2006-058717
公開番号（公開出願番号）：特開2007-241340
出願日： 2006年03月03日
公開日（公表日）： 2007年09月20日
要約：
【課題】巡回すべき多数の地点を複数の分割グループに分け、各分割グループ内の各地点を巡回する分割巡回経路のコストがほぼ均等になるように、同時に各分割巡回経路を探索する。【解決手段】地点分割手段210が分割数に従って巡回対象の各地点を分割グループに分け、巡回対象の全ての2地点間の最短経路を探索し記憶しておき、GA処理手段155が遺伝アルゴリズムを用いて分割グループ内の各地点の巡回経路の評価値を経路コストの和として算出し、評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて分割巡回経路探索を進め、SA処理手段211がシミュレーテッドアニーリング法により、所定の試行回数に達するか、指定試行回数の間、前記最良解が更新されなくなるまで、任意の複数の分割グループ内の任意の各1つの地点を選択して分割グループを入れ換え、GA処理手段155が探索した評価値を評価して前記最良解を更新する。【選択図】図1
請求項（抜粋）：
複数の地点を任意の分割数Nで分割した分割グループごとに当該分割グループ内の地点を巡回する分割巡回経路を探索するN分割巡回経路探索システムであって、
前記分割数、巡回対象の地点の位置情報を入力する入力手段と、2地点間の経路を探索する2地点間経路探索手段と、分割数に基づいて複数の巡回対象の地点を分割数に応じた分割グループに分割する地点分割手段と、分割グループごとに分割グループ内の各地点を巡回する巡回経路を探索する巡回経路探索手段と、巡回経路探索手段が探索した評価値をシミュレーテッドアニーリング法により評価して最良解を更新するSA処理手段と、を備え、
前記2地点間経路探索手段は、巡回対象の2地点間全ての最短経路を探索してその最適経路および経路コストを記憶し、
前記巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に基づく評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進め、
前記SA処理手段は、所定の試行回数に達するか、指定試行回数の間、前記最良解が更新されなくなるまで、前記地点分割手段により任意の複数の分割グループ内の任意の各1つの地点を選択して分割グループを入れ換えて分割グループを再設定し、前記巡回経路探索手段が探索した評価値を評価して前記最良解を更新することを特徴とするN分割巡回経路探索システム。
IPC (5件)：
G06N 3/00
, G01C 21/00
, G09B 29/00
, G09B 29/10
, G08G 1/096
G06N3/00 550C
, G01C21/00 G
, G09B29/00 A
, G09B29/10 A
, G08G1/0969
2C032HB08
, 2C032HB22
, 2C032HB25
, 2C032HC08
, 2C032HD18
, 2F129AA03
, 2F129AA06
, 2F129BB03
, 2F129BB33
, 2F129BB46
, 2F129CC15
, 2F129CC16
, 2F129CC26
, 2F129CC28
, 2F129CC29
, 2F129DD02
, 2F129DD20
, 2F129DD62
, 2F129DD64
, 2F129DD66
, 2F129DD80
, 2F129EE02
, 2F129EE52
, 2F129EE54
, 2F129FF12
, 2F129FF20
, 2F129FF32
, 2F129HH01
, 2F129HH04
, 2F129HH12
, 2F129HH17
, 5H180AA15
, 5H180BB05
, 5H180FF04
, 5H180FF05
, 5H180FF11
, 5H180FF13
, 5H180FF22
, 5H180FF27
, 5H180FF33
出願人引用 (3件)
審査官引用 (5件)
全件表示
引用文献：
前のページに戻る
