變鄰域搜尋算法（Variable Neighborhood Search，簡稱VNS）是一種用於解決組合最佳化問題的啟發式搜尋算法。該算法由Mladenović和Hansen於1997年提出，旨在通過不斷變化問題的鄰域結構來尋找更好的解決方案。VNS通常用於NP困難問題，如旅行商問題（TSP）、車輛路徑問題（VRP）等。
VNS的基本思想和步驟包括：
初始解。算法從一個初始解開始，這可以是隨機生成的或基於其他啟發式算法得到的解。
鄰域結構。VNS使用一系列不同的鄰域結構來探索潛在的解空間。每個鄰域結構定義了一種改變當前解的方式，如交換兩個元素、插入一個元素、反轉一部分元素等。
鄰域搜尋。在每個疊代中，算法選擇一個當前鄰域結構，並在該結構下搜尋一個新的解，可能使用局部搜尋方法如模擬退火、爬山法等。如果找到了一個更好的解，則更新當前解為新的解。
鄰域切換。如果在當前鄰域結構下無法找到更好的解，算法切換到下一個鄰域結構，並繼續搜尋。這個過程可能會在一系列不同的鄰域結構之間進行多次疊代。
停止條件。算法可以根據一定的停止條件來終止，如達到最大疊代次數、運行時間超過限制或者找到了一個滿足要求的解。
VNS的關鍵思想是通過變化鄰域結構來增加搜尋的多樣性，從而有更大的機會找到更優的解決方案。通過不斷地切換鄰域結構，VNS可以跳出局部最優解，進一步搜尋解空間。然而，VNS的性能高度依賴於如何選擇和切換鄰域結構，以及在每個鄰域中進行的局部搜尋策略。