LinとKernighanの方法

【 りんかーにはんほう 】

巡回セールスマン問題に対する局所探索法の一つ． 巡回路の枝たかだか$k$本を別の枝に置き換えることにより得られる解集合を $k$-opt近傍と呼ぶが，この近傍において$k$を可変にし， 連鎖的な枝交換操作によって生成され得る解集合を近傍とする． このような解は指数通りあるため， 改善解を逃さぬように探索の候補を絞るために巧妙なルールが組み込まれている． なお，上述の局所探索をLinとKernighanの方法と呼ぶことが多いが， 元論文は多スタート局所探索法の枠組みに基づいており， 探索の集中化や効率化に対する種々の工夫も盛り込まれている．