Variable Neighborhood Search (VNS)

Variable Neighborhood Search (VNS) adalah sebuah kerangka kerja optimasi metaheuristik yang diperkenalkan oleh Mladenović dan Hansen pada tahun 1997. Metode ini keluar dari optimum lokal dengan secara sistematis beralih di antara sekumpulan struktur lingkungan yang telah ditentukan sebelumnya — pertama-tama mengganggu solusi saat ini (shaking) untuk mencapai wilayah lain dari ruang pencarian, kemudian menerapkan pencarian lokal di dalam wilayah tersebut, dan akhirnya menerima solusi baru hanya jika solusi tersebut memperbaiki solusi yang ada (incumbent). Metode ini cukup fleksibel untuk menangani masalah kombinatorial (masalah rute, penjadwalan, graf) serta optimasi kontinu, menjadikannya salah satu metaheuristik berbasis lingkungan yang paling banyak digunakan dalam riset operasi.