Lin-Kernighanアルゴリズムをカオス駆動する巡回セールスマン問題の解法

摘要

巡回セールスマン問題に対して，最も単純な局所探索法である2-opt法にカオスダイナミクスを導入することで，良好な解が効率的に得られることが報告されている．そこで本報では，最も優れた局所探索法と考えられているLin-Kernighanアルゴリズムにカオスダイナミクスを導入した新たな巡回セールスマン問題の解法を提案する．提案手法の性能評価のた捌こTSPLIBのベンチマーク問題を用いた．その結果，提案手法は従来の2-opt法にカオスダイナミクスを導入した手法よりも優れた性能を有することを確認した．