物流最適化に向けたGAとバックトラックの融合によるTSP近似解法
スポンサーリンク
概要
- 論文の詳細を見る
配送ルートなどの最適化システムでは,数十〜数百拠点 (都市) 以上の最短道順探索問題 (巡回セールスマン問題:TSP) を対話的応答時間 (3 秒程度以下) かつ専門家程度の誤差 (3% 前後以下) で解かなければならない.しかも,シンプルで分かりやすい方法が望まれる.ヒューリスティクスが複雑だとユーザに難しいと嫌われ実用にならない上,開発者,特に顧客担当の技術者も変化の多い現場や配送条件に合わせた修正を容易にしたいためである.これらの要求を満たすために,最近挿入法 (NI) や 2-opt など基本的な方策 (発見的知識) やメタ戦略 (バックトラック & ランダムリスタート法:BR と略す) を遺伝的アルゴリズム GA に組込むシンプルで分かりやすい方法を提案する.提案方式で 1000 回試行した結果,500 都市前後までの TSPLIB の問題を 3 秒以内に最悪誤差が 3% 以下で,解くことができた.本方式は,多忙な現場の人になじみのある分かり易いヒューリスティックスである NI や 2-opt を部分的に適用した突然変異を中心とする GA に BR を融合したシンプルなものであり,上記の柔軟な対応が容易である.
- 2011-02-28
著者
-
櫻井 義尚
東京電機大学
-
塚本 奈津貴
東京電機大学 情報環境学部 情報環境学科
-
高田 考平
東京電機大学 情報環境学部 情報環境学科
-
鶴田 節夫
東京電機大学 情報環境学部 情報環境学科
-
櫻井 義尚
電気通信大学
-
鶴田 節夫
東京電機大 情報環境
-
櫻井 義尚
東京電機大学情報環境学部情報環境学科
-
塚本 奈津貴
東京電機大学情報環境学部情報環境学科
-
鶴田 節夫
東京電機大
-
櫻井 義尚
東京電機大学 情報環境学部 情報環境学科
関連論文
- Web 利用共同開発支援向け先端メディア融合方式の研究
- 個人の主観的イメージを自動学習する検索手法
- 配送ルート最適化のための内部多世界GA
- 配送ルート最適化のための内部多世界GA
- 制約付きTSPを解くための局所利己的遺伝子許容動的制御GA
- 制約付きTSPのための局所利己的遺伝子動的制御GAの提案(セッション2)
- 大規模TSPを対話的応答時間内で最適化するための多段知能型GA(セッション2)
- 制約付きTSPのための局所利己的遺伝子動的制御GAの提案(セッション2)
- 大規模TSPを対話的応答時間内で最適化するための多段知能型GA(セッション2)
- 制約付きTSPのための局所利己的遺伝子動的制御GAの提案
- 大規模TSPを対話的応答時間内で最適化するための多段知能型GA
- 配送問題を対話的時間で実用レベル最適化する多段知能型GA
- 利己的制約充足型GAによる幹線物流網構築手法
- マルチステージGAによる共同物流網における配送計画作成手法
- 利己的制約充足型GAによる幹線物流網構築手法
- セール指向Eコマース商品グループ管理の一方式
- 2R-2 Eコマース向けセール指向商品グループ管理の一方式(文書管理,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- セール指向Eコマース商品グループ管理の一方式
- 最短道順の実時間探索ための複数方策メタ戦略融合GA方式
- 最短道順の実時間探索ための複数方策メタ戦略融合GA方式
- 強化学習を用いた進化的アルゴリズムのパラメータ学習
- 共同作業管理のための文脈利用方式(協調作業(2))
- 進化型計算法の自律協調型開発環境の研究--遺伝的アルゴリズムによる配送ルートの最適化
- 配送スケジュールの進化計算型リアルタイム最適化技術の研究
- 連続な状態行動空間において近傍状態の報酬予測を用いた強化学習(エージェント・学習)
- パターン情報に基づく能動的学習法による非線形システムのモデリングと制御への適用
- 2-401 能動的学習法を用いた制御知識の獲得
- 能動的学習法による鉄棒体操演技知識の獲得
- 物流最適化に向けたGAとバックトラックの融合によるTSP近似解法
- 配送ルート最適化向けランダムリスタート融合GA方式
- 方策を自律学習する進化型計算法による配送ルートの最適化
- 行動・認知モデルに基づく分散共同開発支援用マルチエージェントシステムの研究
- 能動的学習法の制御問題への適用に関する考察
- 配送ルート最適化向けランダムリスタート融合GA方式