物流最適化に向けたGAとバックトラックの融合によるTSP近似解法

概要

論文の詳細を見る
配送ルートなどの最適化システムでは,数十〜数百拠点 (都市) 以上の最短道順探索問題 (巡回セールスマン問題:TSP) を対話的応答時間 (3 秒程度以下) かつ専門家程度の誤差 (3% 前後以下) で解かなければならない.しかも,シンプルで分かりやすい方法が望まれる.ヒューリスティクスが複雑だとユーザに難しいと嫌われ実用にならない上,開発者,特に顧客担当の技術者も変化の多い現場や配送条件に合わせた修正を容易にしたいためである.これらの要求を満たすために,最近挿入法 (NI) や 2-opt など基本的な方策 (発見的知識) やメタ戦略 (バックトラック & ランダムリスタート法:BR と略す) を遺伝的アルゴリズム GA に組込むシンプルで分かりやすい方法を提案する.提案方式で 1000 回試行した結果,500 都市前後までの TSPLIB の問題を 3 秒以内に最悪誤差が 3% 以下で,解くことができた.本方式は,多忙な現場の人になじみのある分かり易いヒューリスティックスである NI や 2-opt を部分的に適用した突然変異を中心とする GA に BR を融合したシンプルなものであり,上記の柔軟な対応が容易である.
2011-02-28