变邻域搜索（Variable Neighborhood Search, VNS）
变邻域搜索由 Mladenović 与 Hansen 等系统化提出：在单点搜索框架下，预备一组由弱到强（或由近到远）的邻域结构，在局部最优处通过「换邻域」或「抖动 + 再局部搜索」跳出当前吸引域。与固定单邻域的下降法相比，显式利用多邻域的互补性，属单解、基于邻域的元启发式，见 元启发式总览。
全文默认目标 最小化， 为可行解（许多文献记作 ，含义相同）。
记号与邻域结构（两套邻域宜分开命名）
实现经典基本 VNS 与 VND 时，通常准备两套邻域族，避免下标混用：
- 抖动邻域 ，：用于 Shaking。从当前解 出发，在 内随机抽一个新起点 （不要求立刻改进 ），扰动强度常随 增大而增强。
- VND 邻域 ，：用于 Variable Neighborhood Descent。在 上做确定性邻域搜索（找改进或找邻域内最优）， 通常从「最细」排到「最粗」。
对点 ，、 分别表示在该邻域结构下一步（或约定好的多步）可达的集合；实现上可对集合采样或部分枚举。
抖动（Shaking）
作用：当当前 在某一局部搜索下已是局优时，若只在同一套确定性邻域里下降，会反复落回同一片吸引域。抖动的目标不是让单步 变小，而是利用随机性从 里取新起点 ，使随后的局部搜索有机会进入新的谷地。 可以明显劣于 ，也无需在 上对 做任何最优化；这与 VND 在 内「找改进步」的取向相反。
与下标 的关系： 标定「这一次抖动用哪一级邻域算子/步幅」。内层循环中若「抖动 → VND → 接受」未改进当前 ，则 ，等价于小抖不动就逐步加大扰动；改进成功则 ，回到最弱抖动重新开始。
从 中生成 的常见方式（实现上可择一或组合）：
- 一步随机邻居：在 的枚举/候选集合中等概率或加权抽一点。
- 多步随机游走：对固定 连续做 次「在 中抽随机邻步并前进一步」， 可常数、与 成比例或上界内均匀随机，相当于用同一 工具堆出更强扰动而不另建一套邻域结构。
- 逆移与有偏：若仅防「立刻逆回上一步」即可减轻短循环，可与极轻量禁忌同用；若引入复杂记忆则更接近混合 TS，已超出「纯 VNS 抖动」的朴素表述，实现时需单独定稿。
可行性与修复：若 一步得到不可行 ，可丢弃后重试、限次重采样，或用问题相关修复将 投回可行集再进入局搜。
与内层局搜的分工：抖动只负责把点扔到新区域；内层 VND 把新起点收敛到其邻域意义下的局部最优。重复「抖—搜」便于控制随机性与计算量。
变邻域下降（VND）
定位：基本 VNS 的局部搜索一步常采用 VND。在邻域族 上无随机、按 从细到粗切换：在当前 下若在 内仍能改进则立即强化 并把 重置为 ；否则 。全部 都无能为力时，输出当前 ，作为相对这组 的局部最优。
邻域内怎么走：在 中可取「首个改进」（first improvement）或「最优改进」（best improvement，在邻域内枚举/搜索 最小的一点）——二者都是常见实现，下框用抽象语句「求邻域内用于比较的候选最优点」概括。
VND 仍可能停在多邻域意义下的强局优，那时需要靠外层再抖动换起点，而不是在 VND 里无限加邻域。
在基本 VNS 中，VND 的输入是抖动得到的 ，输出 再参与最外层的接受与 的更新。
▶ 子过程：变邻域下降（VND）
1. 输入与初始化
输入：起点 ；VND 邻域结构 ，。
，。
2. VND 主循环
当 时重复：
在邻域 中求一点 （实现上可为「第一个使 下降的邻解」，或「 上使 最小的邻解」等与邻域定义配套的搜索策略）。
若 ：令 ，（改进后回到最细邻域继续搜）。
否则：（当前邻域结构已无法改进，换下一级）。
3. 输出
返回 ，作为相对 的局部最优解。
主循环（基本 VNS：抖动 + VND）
外层反复执行「重置 → 在内层依次尝试 的抖动强度」，直到满足全局终止条件（最大迭代次数、CPU 时间、连续无改进上限等）。下面给出与经典教材一致的逻辑骨架（最小化）。
▶ 主算法：变邻域搜索（VNS）
1. 输入与初始化
输入：抖动邻域 ，；VND 邻域 ，；初始可行解 。
，（ 为迄今为止最优解）。
2. 外层循环
当未达到全局终止条件时重复：
令 。
3. 内层循环（抖动强度）
当 时重复：
（抖动）在邻域 中按随机规则生成可行解 （见上文「抖动」一节）。
（局部搜索），即调用上一框以 为起点、邻域族 做变邻域下降。
（接受与 的更新）若 ：令 ；若 则 ；令 （改进则重置抖动级别）。
否则：（未改进则加大抖动强度）。
4. 输出
返回 。
说明：内层 while k ≤ k_max 结束后，外层进入下一轮会再次执行 k ← 1，无需再写「 时强行赋 1」一类易混淆分支。第 4 步局部搜索也可替换为其它下降过程，但默认叙述与 VND 配套。