算过车辆路径问题的人多少都被“局部最优”卡过脖子明明贪心出来的初始解还行一进爬山搜索就原地踏步换个初始解结果又不一样。变邻域搜索Variable Neighborhood SearchVNS就是专门治这个毛病的一套思路——同一个解你换着花样扰动它、再反复局部搜索往往能在不太长的迭代里摸到很接近最优解的地方。这篇文章我结合自己用C求解带时间窗车辆路径问题VRPTW的完整经历把VNS的原理拆开讲透再给出能直接跑的C实现细节。适合已经会写基本元启发式、但对VNS或VRPTW还缺一套系统落地的读者。1. VNS算法原理梳理——为什么“变换邻域”能跳出局部最优1.1 一个比喻讲清VNS的底层逻辑你可以把搜索过程想象成下山找最低点局部搜索Local Search就是从当前位置往周围看看哪边更低就往哪走走到没法再低为止。问题在于你登上的可能只是一个山坳不是整片山脉的最低点。传统做法是多随机几个起点多爬几次山碰运气。VNS想的是另一件事不换起点而是先把人“踹”出当前山坳踹到附近的另一个山脊上再让他继续下山。只要踹的距离合适、方向多样就能在不同山坳之间反复横跳慢慢逼近全局最低点。这里的“踹”就是扰动Shaking“下山”就是局部搜索。而“不同方向、不同距离”对应一组预先设计好的邻域结构——比如一次交换两个客户、一次挪一段路径、一次反转一段路径。VNS的核心贡献就是把“该用哪种扰动跳出去”从玄学变成了系统化的切换机制。1.2 VNS的三个核心组件标准VNS包含三个基本组件邻域结构集合Nkk1..kmax、局部搜索过程又称Variable Neighborhood DescentVND、以及解的接受准则。邻域结构是一系列对当前解做“破坏-重建”或“微调”的操作。常见的有交换两个客户节点swap、移动一个客户到另一位置insertion/relocate、反转路径中的一段2-opt、交换两条路径的两个片段cross-exchange等。每种操作定义一个邻域邻域结构集合就是这些操作的排列组合。VNS的思想是先从简单的、小范围的邻域开始如果在小邻域内找不到更好的解就升级到更大范围的邻域一旦有改进就回到最小邻域重新来。VND则是VNS内部的第二层循环它接收一个解然后依次尝试一组局部搜索算子直到这组算子中没有任何一个能继续改进解。和普通爬山不同VND用的是“多个邻域接力”的方式效果比单个算子反复跑到收敛好很多。接受准则决定新一轮解是否被保留。最简单的准则是只接受改进解hill climbing但更实用的变体允许以一定概率接受等质量或略差的解。对VRPTW这类强约束问题我建议先用只接受更优解的准则等搜索陷入平台期再考虑放松。1.3 从局部搜索到VNS算法骨架推演写代码之前先把骨架想明白初始化生成初始解 x定义邻域结构集合 Nk (k1..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 问题是什么VRPTWVehicle Routing Problem with Time Windows是经典车辆路径问题VRP加了时间窗约束的版本。场景是这样的仓库有一队车必须服务一批位于不同地点的客户每个客户有服务时间窗口最早开始服务时间、最晚开始服务时间车必须在窗口内到达早到可以等待晚到则不允许每辆车有载重上限目标是让总行驶距离或总成本最小每辆车从仓库出发最后回到仓库。这个问题的难点在于除了路径长度还要同时管理载重和时间窗两类约束使得可行解的空间更狭窄搜索算法更容易被卡在不可行区域边缘。2.2 关键参数与决策变量建模时我习惯定义这么几组量客户集合 i ∈ {1..n}仓库记为 0出发和 n1返回也可用同一个仓库节点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 { vectorint nodes; // 从仓库0出发路径节点序列最后回到0 double load; // 总载重 double totalDist; // 总距离 vectordouble arrive; // 每个节点的到达时间 vectordouble start; // 每个节点的开始服务时间 double calcTotalTime() { ... } }; struct Solution { vectorRoute 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这样设计当 k1 时随机做1次“双插入”把一个客户插入另一个位置k2 时随机做2次“双交换”交换两个路径段k3 时同时做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; vectordouble 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[pos1]] - dist[route.nodes[pos-1]][route.nodes[pos1]]; return true; }这段代码的核心是“只更新受影响的尾部时间”而不是整条路径重新算。虽然实现上要多维护两个数组但换来的是每个插入操作从 O(n) 降到 O(k)k 是路径剩余长度通常在10-20之间提速非常可观。4. 调参、排错与性能优化心得4.1 不可行解的惩罚处理在实际测试中我发现Shake产生的不可行解如果直接丢给VNDVND会花大量迭代去修复但修复后往往又回到原来的局部最优附近——这样浪费时间。更好的做法是在目标函数中加入对不可行解的惩罚项让搜索能接受轻微违反时间窗或载重的解再逐步收紧惩罚系数。常见的惩罚函数形如fitness totalDistance α * (载重超限总量) β * (时间窗总延误)开始设 α、β 较小比如 α0.1让搜索敢探索违反约束的区域每过固定代数如果最优解没有改进就增大 α、β迫使搜索回落可行域。这个“动态罚函数法”在VRPTW上效果很明显尤其是时间窗紧的算例。4.2 多个典型运行数据的记录我用标准测试算例 Solomon 的 R10125个客户车容量200时间窗较松跑过一次实验记录如下配置初始解距离VNS改进后迭代时间最近邻初始解 VNS(kmax3)958.7712.34.2s节省算法初始解 VNS(kmax3)748.2686.93.6s节省算法初始解 VNS(kmax5)748.2671.56.8s上述 动态罚函数748.2662.18.1s可以看出初始解的选择影响显著但VNS本身能弥补不少差距kmax从3增加到5能进一步改进动态罚函数又能压榨出一些余量。不过代价是迭代时间变长在大规模算例上要平衡。再记录一个时间窗非常紧的 C10125客户上的情况单纯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. 结尾 从原理到落地到调参这套VNSVRPTW的C实现我前前后后改过好几轮最深的体会是VNS真正的难点不在算法骨架而在那些“看起来不重要的细节”——时间窗的增量更新、Shake强度的调整、罚函数系数的配合每一项都能让最终结果差出百分之十几。如果你正在把手里的VRP类问题改造成VNS版本建议先把邻域算子和增量评估做好再去追求复杂的接受准则和参数自适应。骨架简单、细节扎实VNS就能成为你最趁手的全局优化工具。