近傍探索法 (VNS)

近傍探索法 (VNS: Variable Neighborhood Search) は、1997年にMladenovićとHansenによって導入されたメタヒューリスティック最適化フレームワークです。これは、事前に定義された近傍構造のセットを体系的に切り替えることで、局所最適解からの脱却を図ります。具体的には、まず現在の解を摂動させ（shaking）、探索空間の異なる領域に到達させます。次に、その領域内で局所探索を適用し、最後に、新しい解が既存の最良解を改善する場合にのみ、その解を受け入れます。この手法は、組み合わせ最適化問題（ルーティング、スケジューリング、グラフ問題）だけでなく、連続最適化問題にも対応できる柔軟性を持ち、オペレーションズリサーチにおいて最も広く使用されている近傍ベースのメタヒューリスティクスの一つとなっています。