OR事典

LinとKernighanの方法

読み方：りんとかーにはんのほうほう
【英】：Lin and Kernighan's algorithm

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