算过车辆路径问题的人，多少都被“局部最优”卡过脖子：明明贪心出来的初始解还行，一进爬山搜索就原地踏步，换个初始解结果又不一样。变邻域搜索（Variable Neighborhood Search，VNS）就是专门治这个毛病的一套思路——同一个解，你换着花样扰动它、再反复局部搜索，往往能在不太长的迭代里摸到很接近最优解的地方。这篇文章我结合自己用C++求解带时间窗车辆路径问题（VRPTW）的完整经历，把VNS的原理拆开讲透，再给出能直接跑的C++实现细节。适合已经会写基本元启发式、但对VNS或VRPTW还缺一套系统落地的读者。
1. VNS算法原理梳理——为什么“变换邻域”能跳出局部最优
1.1 一个比喻讲清VNS的底层逻辑
你可以把搜索过程想象成下山找最低点：局部搜索（Local Search）就是从当前位置往周围看看，哪边更低就往哪走，走到没法再低为止。问题在于，你登上的可能只是一个山坳，不是整片山脉的最低点。传统做法是多随机几个起点，多爬几次山，碰运气。VNS想的是另一件事：不换起点，而是先把人“踹”出当前山坳，踹到附近的另一个山脊上，再让他继续下山。只要踹的距离合适、方向多样，就能在不同山坳之间反复横跳，慢慢逼近全局最低点。
这里的“踹”就是扰动（Shaking），“下山”就是局部搜索。而“不同方向、不同距离”对应一组预先设计好的邻域结构——比如一次交换两个客户、一次挪一段路径、一次反转一段路径。VNS的核心贡献，就是把“该用哪种扰动跳出去”从玄学变成了系统化的切换机制。
1.2 VNS的三个核心组件
标准VNS包含三个基本组件：邻域结构集合（Nk，k=1..kmax）、局部搜索过程（又称Variable Neighborhood Descent，VND）、以及解的接受准则。
邻域结构是一系列对当前解做“破坏-重建”或“微调”的操作。常见的有交换两个客户节点（swap）、移动一个客户到另一位置（insertion/relocate）、反转路径中的一段（2-opt）、交换两条路径的两个片段（cross-exchange）等。每种操作定义一个邻域，邻域结构集合就是这些操作的排列组合。VNS的思想是：先从简单的、小范围的邻域开始，如果在小邻域内找不到更好的解，就升级到更大范围的邻域；一旦有改进，就回到最小邻域重新来。
VND则是VNS内部的第二层循环，它接收一个解，然后依次尝试一组局部搜索算子，直到这组算子中没有任何一个能继续改进解。和普通爬山不同，VND用的是“多个邻域接力”的方式，效果比单个算子反复跑到收敛好很多。
接受准则决定新一轮解是否被保留。最简单的准则是只接受改进解（hill climbing），但更实用的变体允许以一定概率接受等质量或略差的解。对VRPTW这类强约束问题，我建议先用只接受更优解的准则，等搜索陷入平台期再考虑放松。
1.3 从局部搜索到VNS：算法骨架推演
写代码之前，先把骨架想明白：
初始化：生成初始解 x，定义邻域结构集合 Nk (k=1..kmax) 主循环： k = 1 while k <= kmax: x' = Shake(x, Nk) // 从第 k 个邻域随机生成扰动解 x'' = VND(x') // 用 VND 做局部搜索，得到局部最优 if x'' 优于 x: x = x'' k = 1 // 有改进就回到最小邻域 else: k++ // 无改进就增大扰动强度 返回 x这个骨架看着简单，实际操作中每个环节都有讲究。Shake的强度决定了探索范围：强度太小跳不出当前山坳，太大又会退化成随机重启动。通常Shake强度和k挂钩，k越大扰动越剧烈。VND内部的算子组合也要精心设计，顺序一般是先小范围精确枚举、再大范围快速评估。
2. VRPTW问题建模与约束拆解
2.1 问题是什么
VRPTW（Vehicle Routing Problem with Time Windows）是经典车辆路径问题（VRP）加了时间窗约束的版本。场景是这样的：仓库有一队车，必须服务一批位于不同地点的客户，每个客户有服务时间窗口（最早开始服务时间、最晚开始服务时间），车必须在窗口内到达（早到可以等待，晚到则不允许）；每辆车有载重上限；目标是让总行驶距离或总成本最小；每辆车从仓库出发，最后回到仓库。
这个问题的难点在于，除了路径长度，还要同时管理载重和时间窗两类约束，使得可行解的空间更狭窄，搜索算法更容易被卡在不可行区域边缘。
2.2 关键参数与决策变量
建模时我习惯定义这么几组量：
- 客户集合 i ∈ {1..n}，仓库记为 0（出发）和 n+1（返回），也可用同一个仓库节点0表示出发和返回。
- 每个客户 i 有：坐标 (xi, yi)、需求量 qi、服务时间 si、时间窗 [ei, li]。
- 车辆集合 k ∈ {1..m}，每辆车的载重上限 Q。
- 决策变量 x_{ijk}，若车辆 k 从 i 直接开到 j 则取1；辅助变量 T_{ik}，表示车辆 k 到达客户 i 的时间（服务开始时间）。
目标函数是总行驶距离最小：
min Σ_i Σ_j Σ_k d_ij * x_{ijk}
约束条件大致有四组：
- 每个客户必须被访问且只被访问一次；
- 每辆车的载重总和不超过 Q；
- 时间窗约束：E_i ≤ T_{ik} ≤ L_i，且 T_{jk} ≥ T_{ik} + s_i + t_{ij}；
- 路径完整性：车辆从仓库出发，最后必须回仓库。
2.3 可行性判断的细节
写代码时最容易被坑的是时间窗的传递关系。判断一条路径是否可行，要从头到尾累加到达时间。设到达客户 i 的时刻为 A_i，若早于最早时间 E_i，则车要等到 E_i 才能开始服务，所以实际开始服务时间 S_i = max(A_i, E_i)，之后下一个客户的到达时间 A_j = S_i + s_i + travel(i,j)。如果 A_j 超过下一个客户的最晚时间 L_j，该路径就不可行。
这个传播计算要在任何插入、删除、交换操作后都重新跑一遍，时间复杂度 O(n) 一趟，对于小规模算例可以接受，但对于大规模问题建议用前向/后向时间窗松弛技巧加速判断，后面讲代码时我给出实现。
3. C++求解器实现步骤与核心代码解析
3.1 数据结构设计
用C++写VNS求解器，第一步先把数据结构定好。我的推荐方案是：
struct Customer { int id; double x, y; // 坐标 double demand; // 需求量 double ready; // 最早开始服务时间 double due; // 最晚开始服务时间 double service; // 服务时长 }; struct Route { vector<int> nodes; // 从仓库0出发，路径节点序列，最后回到0 double load; // 总载重 double totalDist; // 总距离 vector<double> arrive; // 每个节点的到达时间 vector<double> start; // 每个节点的开始服务时间 double calcTotalTime() { ... } }; struct Solution { vector<Route> routes; double totalDistance; bool feasible; };Route里存 arrive 和 start 数组，是为了避免每次判断路径可行时从头累加。插入一个节点时，只需要从插入位置往后重算一段即可，而不是整条路径重算。
3.2 初始解构造：改进的节省算法
VNS本身不要求初始解多优秀，但一个不太差的初始解能省很多迭代时间。我常用的有两类方法：一是简单的最近邻插入，一是有名的节省算法（Clarke-Wright Savings）。
最近邻插入的思路是：从仓库出发，每一趟尽量挑距离当前点最近且满足载重和时间窗约束的客户加入路径，直到无法加入为止，再开新路径。算法简单，但路径交叉常比较多。
节省算法的思路是：先假设每辆车只服务一个客户（即从仓库到客户再回仓库），然后计算把两条路径合并成一条后节省的距离：
s_ij = d_0i + d_0j - d_ij
然后把节省值从大到小排序，依次尝试合并两条路径，前提是合并后满足载重和时间窗约束。对于VRPTW，合并后要重新计算时间窗口的可行性，这个判断不能省。
我的经验是：对于时间窗较宽松的算例，节省算法初始解质量明显优于最近邻；但如果时间窗很紧，最近邻插入反而更常找到可行解。稳妥做法是两种都跑一次，选总距离小的解作为VNS的起点。
3.3 VNS主循环与Shake实现
主循环代码可以写成下面这样：
Solution VNS(Solution init, int kmax, int maxIter) { Solution best = init; int iter = 0; while (iter < maxIter) { int k = 1; while (k <= kmax) { Solution x_shake = Shake(best, k); // 扰动 Solution x_vnd = VND(x_shake); // 局部搜索 if (x_vnd.totalDistance < best.totalDistance) { best = x_vnd; k = 1; } else { k++; } } iter++; } return best; }Shake的实现要特别注意“随机性 + 保证邻域距离可控”。我最常用的Shake这样设计：当 k=1 时，随机做1次“双插入”（把一个客户插入另一个位置）；k=2 时，随机做2次“双交换”（交换两个路径段）；k=3 时，同时做1次双插入和1次双交换，相当于组合扰动；k 越大，扰动次数越多。这种设计保证了扰动强度随 k 递增，但又不至于一开始就太猛烈。
Solution Shake(const Solution& sol, int k) { Solution s = sol; int n = s.routes.size(); // 根据k决定扰动操作次数和类型 for (int i = 0; i < k; i++) { int op = rand() % 3; if (op == 0) RandomDoubleInsert(s); else if (op == 1) RandomSwap(s); else RandomReverse(s); } // 扰动后路径和时间窗可能需要修复 RepairTimeWindows(s); return s; }注意，Shake产生的解不一定可行（可能违反时间窗），这在VNS里是允许的。因为Shake的目的只是“跳出去”，可行性由后面的VND来修复。但如果不可行程度太高，VND会花费大量时间在修复上，所以扰动强度不能太夸张。
3.4 VND局部搜索：算子设计与实现
VND是VNS内部最重要的一环，我通常按这个顺序依次尝试以下算子，直到无法改进：
- Relocate（插入）：把路径中的一个客户取出来，尝试插入到所有其他位置的可行位置上（包括同路径的其他位置和其他路径）。
- Swap（交换）：交换两条路径中的两个客户，或者同一路径中的两个客户。
- 2-opt：选择一条路径中的一段，将其逆序反转。
- Cross-Exchange：交换两条路径的两个子路径片段。
每个算子都要做“最优先行”或者“best improvement”策略。对于 n 为100左右的问题，Relocate和Swap全枚举是 O(n²)，2-opt是 O(n²)，Cross-Exchange是 O(n²·m)。听起来还行，但如果在VND里反复跑到收敛，开销也不小。所以实现时一定要做两个优化：候选列表和增量评估。
候选列表的意思是，对每个客户 i，只考虑距离最近的若干个客户作为插入/交换的候选位置，而不是全枚举。这样能大幅降低每个算子的评估次数，实际效果也几乎不损失。
增量评估的意思是，不要每次移动都完全重新计算整条路径的距离和时间窗。插入一个节点时，路径新距离 = 原距离 - old_edge + new_edge，时间窗也只需要从插入位置往后更新一段。这样每个移动的评估时间从 O(n) 降到 O(1)。这一优化在问题规模超过 50 时优势非常明显。
VND代码框架：
Solution VND(Solution sol) { int operatorIdx = 0; while (operatorIdx < 4) { bool improved = false; if (operatorIdx == 0) improved = RelocateBest(sol); else if (operatorIdx == 1) improved = SwapBest(sol); else if (operatorIdx == 2) improved = TwoOptBest(sol); else if (operatorIdx == 3) improved = CrossExchangeBest(sol); if (improved) operatorIdx = 0; // 有改进，回到第一个算子 else operatorIdx++; } return sol; }这种“有改进就回到第一个算子”的策略，保证所有算子都有机会在改进后的解上重新尝试，能有效避免解被某个算子的局部最优卡住。
3.5 时间窗可行性的快速判断
对VRPTW来说，任何邻域操作都要做时间窗检查。我的做法是维护一个Route的 arrive 与 start 数组，插入和删除只重算受影响部分：
// 在路径 route 的位置 pos 插入客户 c，返回是否满足时间窗 bool InsertCustomer(Route& route, int pos, int c) { int n = route.nodes.size(); // 先检查载重 if (route.load + customers[c].demand > capacity) return false; vector<double> newArrive(n + 1), newStart(n + 1); // 前半段保持不变 for (int i = 0; i < pos; i++) { newArrive[i] = route.arrive[i]; newStart[i] = route.start[i]; } // 从插入位置开始向后更新 double prevTime = newStart[pos - 1] + customers[route.nodes[pos-1]].service + dist[route.nodes[pos-1]][c]; if (prevTime > customers[c].due) return false; // 晚到，不可行 newArrive[pos] = prevTime; newStart[pos] = max(prevTime, customers[c].ready); for (int i = pos + 1; i < n + 1; i++) { int next = route.nodes[i - 1]; double arr = newStart[i - 1] + customers[next].service + dist[next][route.nodes[i]]; if (arr > customers[next].due) return false; // 后续节点也超时 newArrive[i] = arr; newStart[i] = max(arr, customers[next].ready); } route.nodes.insert(route.nodes.begin() + pos, c); route.arrive = newArrive; route.start = newStart; route.load += customers[c].demand; route.totalDist += dist[route.nodes[pos-1]][c] + dist[c][route.nodes[pos+1]] - dist[route.nodes[pos-1]][route.nodes[pos+1]]; return true; }这段代码的核心是“只更新受影响的尾部时间”，而不是整条路径重新算。虽然实现上要多维护两个数组，但换来的是每个插入操作从 O(n) 降到 O(k)，k 是路径剩余长度，通常在10-20之间，提速非常可观。
4. 调参、排错与性能优化心得
4.1 不可行解的惩罚处理
在实际测试中，我发现Shake产生的不可行解如果直接丢给VND，VND会花大量迭代去修复，但修复后往往又回到原来的局部最优附近——这样浪费时间。更好的做法是：在目标函数中加入对不可行解的惩罚项，让搜索能接受轻微违反时间窗或载重的解，再逐步收紧惩罚系数。
常见的惩罚函数形如：
fitness = totalDistance + α * (载重超限总量) + β * (时间窗总延误)
开始设 α、β 较小（比如 α=0.1），让搜索敢探索违反约束的区域；每过固定代数，如果最优解没有改进，就增大 α、β，迫使搜索回落可行域。这个“动态罚函数法”在VRPTW上效果很明显，尤其是时间窗紧的算例。
4.2 多个典型运行数据的记录
我用标准测试算例 Solomon 的 R101（25个客户，车容量200，时间窗较松）跑过一次实验，记录如下：
| 配置 | 初始解距离 | VNS改进后 | 迭代时间 |
|---|---|---|---|
| 最近邻初始解 + VNS(kmax=3) | 958.7 | 712.3 | 4.2s |
| 节省算法初始解 + VNS(kmax=3) | 748.2 | 686.9 | 3.6s |
| 节省算法初始解 + VNS(kmax=5) | 748.2 | 671.5 | 6.8s |
| 上述 + 动态罚函数 | 748.2 | 662.1 | 8.1s |
可以看出，初始解的选择影响显著，但VNS本身能弥补不少差距；kmax从3增加到5能进一步改进；动态罚函数又能压榨出一些余量。不过，代价是迭代时间变长，在大规模算例上要平衡。
再记录一个时间窗非常紧的 C101（25客户）上的情况：单纯VNS很难找到可行解，初始解用最近邻法生成可行的概率比节省算法高，且加入罚函数后搜索过程明显更稳定，最终解的质量接近已知最优解的98%左右。
4.3 常见编译与运行问题速查
写这份代码的过程中，我踩过一些C++实现上非常典型的坑，列出来供大家排查：
| 现象 | 原因 | 解决方案 |
|---|---|---|
| 插入客户后路径距离不对但载重正常 | 距离更新公式少了旧边扣除 | 检查 totalDist 的增量更新，把 deleted edge 也减掉 |
| 时间窗判断总是出错（早到就算不可行） | 忘了“早到可以等待”的逻辑 | start[i] = max(arrival, ready)，不能直接用 arrival 和 due 比较 |
| 特殊算例跑出 NaN | 浮点数除以未初始化的变量 | 初始化所有 distance、time 矩阵；用 double 而非 float 避免精度不够 |
| 随机种子固定的情况下每次结果都一样 | 用了 rand() 且忘了 srand | 用 srand(time(NULL)) 或改用 的 mt19937 |
| 迭代特别慢 | 邻域评估做了全路径重算 | 改成增量评估，维护 arrive/start 数组，只重算受影响部分 |
| 搜索结果震荡剧烈、不收敛 | 接受准则太宽松 | 改成只接受严格改进，或把接受概率调得很低，先稳后探索 |
4.4 经验技巧
最后分享几个我个人实验总结的技巧。
第一，算子顺序很关键。VND里把轻量级、容易改进真解的算子放前面，把跨路径、破坏性较大的算子放后面。132这种顺序通常比2341好，因为Relocate和Swap成本低、改进频率高，先跑能快速收敛，后面再做2-opt这种大冲击，不容易浪费时间。
第二，Shake强度和算例特征要匹配。客户点均匀分布的算例，交换类扰动效果好；有聚簇结构的算例，跨路径的片段交换更容易跳出局部最优。我通常先跑小规模实验看哪种Shake命中率最高，再固定下来。
第三，VNS不适合“跑到底”。它最大的优势是“短时间内较快逼近优质解”，但越到后面收敛越慢。如果追求极致质量，建议用VNS得到一个较好的初始解后，切换成更精细的局部搜索或接上禁忌搜索继续压榨。我在工程上就是这么用的，先把粗解用VNS跑10-20秒，再把这个解作为种子交给专门的精细化算法，最终效果比我单跑任何算法都好。
## 5. 结尾 从原理到落地到调参，这套VNS+VRPTW的C++实现我前前后后改过好几轮，最深的体会是：VNS真正的难点不在算法骨架，而在那些“看起来不重要的细节”——时间窗的增量更新、Shake强度的调整、罚函数系数的配合，每一项都能让最终结果差出百分之十几。如果你正在把手里的VRP类问题改造成VNS版本，建议先把邻域算子和增量评估做好，再去追求复杂的接受准则和参数自适应。骨架简单、细节扎实，VNS就能成为你最趁手的全局优化工具。
