企业官网建设流程全解析

年初做一个配送路径规划项目，80个客户、每家都有严格的收货时间窗，原来用精确求解器跑，规模一上去就卡住，Gap怎么都压不下来。后来我换成变邻域搜索（Variable Neighborhood Search, VNS）重新写了求解器，运行时间从几分钟降到几十秒，解质量还比原来的方案更稳定。这篇就把VNS的原理梳理和VRPTW应用细节一次性讲清楚，文末附带C++代码框架，适合正在做路径规划、配送调度，或者想用元启发式解组合优化问题的人参考。

1. 为什么选VNS来啃VRPTW这块硬骨头

带时间窗的车辆路径问题（VRPTW）难在哪？首先它是一个组合爆炸问题，100个客户就有天文数字级别的路线组合；其次时间窗约束让可行解分布非常"破碎"，你稍微调整一个客户的顺序，可能整条路线就不可行了。这种情况下，精确算法和通用求解器只能在中小规模实例上逞能，一旦客户数超过50，求解时间就开始失控。

我当时对比了遗传算法（GA）、模拟退火（SA）、禁忌搜索（TS）和VNS，最终选了VNS，核心原因是它把"逃离局部最优"这件事做成了一套系统化的机制，而不是靠运气。

VNS的基本哲学很有意思：与其设计一个复杂的跳出机制，不如老老实实承认"没有哪个邻域结构是万能的"，然后让多个邻域结构轮番上场。小邻域做精细打磨，大邻域负责跨界搜索，配合一个随机抖动来跳出局部陷阱。这种思路在VRPTW上特别契合，因为时间窗约束让解的可行性很脆弱，一个稍微大一点的邻域操作反而更容易从当前局部区域里逃出去。

2. 变邻域搜索的核心机制：抖动、变邻域下降与接受准则

VNS的完整迭代过程可以浓缩成三个部分：Shaking、VND、Move or Not。很多人把VNS理解成"多邻域随机换着用"，这是不准确的，它其实是有节奏的。

2.1 Shaking：用可控的随机扰动跳出局部最优

给定当前解x，在第k个邻域上随机生成一个新解x'。注意这里是"随机扰动"，不是局部搜索，目的是让解的结构发生一定程度的改变，从而跳到当前局部最优的盆地之外。

抖动强度由参数k控制：k=1时只做一次小扰动（比如随机移动一个客户），k=5时做五次扰动（比如随机交换多个客户、反转一段路径）。k太小逃不出局部，k太大则解被破坏得太厉害，后面VND要花很长时间才能修复。

2.2 VND：系统性的变邻域下降

扰动得到x'之后，在x'上运行一个变邻域下降过程。VND的逻辑是：

l = 1 while l <= l_max: 在 N_l(x') 中寻找改进解 如果找到改进解: 更新 x' l = 1 // 回到第一个邻域重新开始 否则: l = l + 1

关键点在于"找到改进后要回到第一个邻域"。这个回头动作非常重要：小邻域能把解打磨到局部最优，而这个局部最优可能让大邻域有了新的改进机会，所以必须从最小的邻域重新扫。

邻域按什么顺序排？铁律是：计算成本从低到高，扰动强度从轻到重。先跑单点移动这种轻量操作，再跑两点交换，最后才跑2-opt*这类重量级操作。如果一开始就用大邻域，虽然单次改进幅度大，但会破坏小邻域精细优化的机会。

2.3 接受准则：不只是"更好才接受"

经典的VNS采用贪婪接受：只有f(x'') < f(x)时才接受新解，否则留在原解并增大k继续扰动。但在VRPTW实际项目中，我经常加两个变体：

• 等值接受：f(x'') == f(x)时也接受，让搜索有机会从不同方向继续；
• 短期劣化接受：在搜索前期允许接受低于当前解5%以内的解，增加多样性，后期再严格收敛。

另外还有一个实用建议：标准VNS中如果长时间没有改进，把当前解重置到全局最优解，避免解在搜索空间中"漂移"太远。这个操作能显著提升大规模实例上的稳定性。

3. VRPTW的解表达、时间窗审查与评价函数

VRPTW的算法设计，第一步是把解表达清楚。表达方式直接决定邻域操作好不好写、评估快不快。

3.1 路径表达与数据结构

我用的表达方式是"多条路径"：0代表车场，每条路径以0开始、以0结束，中间是客户编号。比如：

Route 1: 0 -> 3 -> 7 -> 9 -> 0 Route 2: 0 -> 5 -> 1 -> 2 -> 0

C++里最直接的结构是vector<vector<int>>，每条路径是一个vector，0是首尾。实际运行时测试下来，对于1000客户以内的实例，这种表达完全够用，不需要上链表结构。

每个客户需要一个结构体来存坐标、需求、时间窗和服务时间。这里有个容易忽略的细节：车场0也要有时间和时间窗定义，通常设ready=0，due=一个很大的数，service=0，这样代码逻辑统一。

3.2 时间窗可行性检查：一个小坑

检查一条路径是否满足时间窗，标准做法是正向递推：

double t = 0; for (int i = 1; i < stops.size(); ++i) { int cur = stops[i]; t += dist(stops[i - 1], cur); if (t > C[cur].due) return false; t = max(t, (double)C[cur].ready) + C[cur].service; }

很多人写这段代码时会漏掉max(t, ready)这一步，或者写成t = t + service不管等待时间。在VRPTW中，车辆早到是允许的，可以等到客户ready时间再开始服务，这个等待时间必须被加进后续的时间轴上。漏掉这一步，算出来的时间窗违反判断全是错的，而且这种错非常隐蔽，不容易被测试发现。

3.3 插入可行性判断与增量评估

邻域操作最常用的就是"把一个客户插入到另一条路径的某个位置"。评估一次插入是否可行，可以直接构造新路径序列，然后完整走一遍时间窗检查。下面的代码是我项目里一直在用的：

// 将客户 v 插入到 r.stops 的 pos 位置之前 // 返回插入后相对于原路径的cost增量，不可行返回INF double evalInsert(const Route& r, int pos, int v) { if (r.load + C[v].demand > vehicleCapacity + EPS) return INF; vector<int> trial; trial.reserve(r.stops.size() + 1); trial.insert(trial.end(), r.stops.begin(), r.stops.begin() + pos); trial.push_back(v); trial.insert(trial.end(), r.stops.begin() + pos, r.stops.end()); double load = 0, t = 0, newCost = 0; for (size_t i = 1; i < trial.size(); ++i) { int prev = trial[i - 1], cur = trial[i]; load += C[cur].demand; newCost += dist(prev, cur); t += dist(prev, cur); if (t > C[cur].due + EPS) return INF; t = max(t, (double)C[cur].ready) + C[cur].service; if (load > vehicleCapacity + EPS) return INF; } return newCost - r.cost; }

注意已经插入了一个点，所以需要同时检查容量约束和时间窗约束，缺一不可。

3.4 评价函数的分层设计

目标函数用"分层最小化"更符合实际业务：第一优先级是最小化车辆数，第二优先级是最小化总行驶距离。这样避免算法为了省一公里路程而多开一辆车，在配送场景中车辆的固定成本可比油耗成本高多了。

工程实现上可以用一个加权和：

f(sol) = 1e6 * vehicleCount + totalDistance

权重设得足够大，这样优化过程中先压车辆数，再压距离。如果初始解不可行，可以给违反容量和时间窗的部分加惩罚项，比如1000 * (超容量总量 + 时间窗违反量)，迭代中逐步增大惩罚系数。

4. C++实现：邻域操作、增量评估与数据结构取舍

VRPTW上常用的邻域结构就那么几个，但实现细节决定成败。我在开发中试过各种组合，最终固定下来一组成熟方案。

4.1 核心邻域操作清单

4.2 增量评估的三个思路

邻域搜索的大头开销在"评估一个候选移动的代价"上。三个办法：

• 局部重算：只重算被修改的路径，其他路径不动；
• 缓存路径费用和载重：路径的cost和load只在应用move后更新；
• 时间轴前缀缓存：对每条路径维护所有站点的最早到达时间，插入时只重算插入位置之后的部分。

初期开发我强烈建议先写完整的O(n)重算版本，逻辑简单不容易出错。等基本功能跑通、确认无误之后，再考虑增量优化。一上来就写前缀缓存，很容易把时间窗等待逻辑搞错。

4.3 数据结构：vector还是list？

单次relocate/swap操作中，vector的插入删除是O(n)，list是O(1)。但list的随机访问是O(n)，而且缓存局部性差。实测下来，100~500客户规模的VRPTW用vector完全没问题，插入删除带来的开销远小于评估阶段的时间窗检查。如果你不想在代码里频繁拼接迭代器，vector<int>就是最合理的默认选择。

4.4 浮点数比较的坑

时间窗比较时，我一开始直接用if (t > due)判断，后来发现两个解明明一样，有时却因为浮点数舍入误差导致重复计算，浪费大量时间。统一改成if (t > due + EPS)后就没再出问题。所有距离、时间用double，EPS设1e-9，这个习惯必须养好。

5. VNS参数实战：抖动强度、邻域顺序与终止条件

VNS参数不多，但每个都直接影响求解质量。下面是我在VRPTW实例上实测下来的推荐配置。

5.1 k_max不是越大越好

我做过一组对比实验：同样数据集，k_max=3和k_max=8分别跑10次，k_max=8不仅解质量更差，运行时间更长。原因是k=7、8的随机抖动等于把路径打散重来，VND要花大量迭代才能把结构修复回来，修复完发现又回到了原来的局部最优区域。对VRPTW来说，k_max=3到5是甜点区。

5.2 邻域顺序直接影响最终质量

邻域顺序我建议按这个顺序排：

1. Relocate（客户重定位）
2. Swap（两点交换）
3. Or-opt（小块移动）
4. 2-opt*（跨路线片段交换）

有一次我把2-opt放在最前面，测试结果反而变差。原因很简单：2-opt每次改动幅度大，直接跳到另一个局部盆地，把relocate和swap能做的精细打磨空间全跳过了。先跑轻量邻域把解往局部最优方向压，再上重量级邻域开辟新方向，这是VNS能同时兼顾"精炼"和"逃逸"的关键。

5.3 终止条件用时间，不用迭代次数

VRPTW的邻域搜索评估成本差异很大，同样的迭代次数，relocate阶段可能几秒跑完，2-opt*阶段可能跑几十秒。所以我直接用chrono::steady_clock做时间控制，外层跑一个while循环，到时间就收敛。这样在工程交付时，可以明确告诉别人"90秒内给出一个可行解"。

5.4 初始解的重要性被低估了

VNS对初始解不算特别敏感，但一个可行的初始解能省大量时间。我最常用的初始解算法是最便宜插入：每次选择一个"插入后导致路径成本增加最少"的客户，放入当前路径最优位置。如果所有客户都无法在不违反约束的情况下插入，就开一条新路径。这个贪婪算法几乎总能快速产出一个可行解，后面VNS再慢慢优化。

6. 可直接改写的C++核心代码框架

下面给出我能直接跑通的核心框架，去掉了很多和算法无关的输入输出，保留主干逻辑。你可以在此基础上补充数据读取、结果打印，或者换成自己的数据结构。

6.1 数据定义与基础函数

#include <bits/stdc++.h> using namespace std; const double INF = 1e18; const double EPS = 1e-9; struct Customer { double x, y, demand; int ready, due, service; }; int N, vehicleCapacity; vector<Customer> C; // C[0] 是 depot struct Route { vector<int> stops; // 首尾是 depot(0) double load = 0.0; double cost = 0.0; }; double dist(int a, int b) { double dx = C[a].x - C[b].x; double dy = C[a].y - C[b].y; return sqrt(dx * dx + dy * dy); }

6.2 路线可行性检查与插入评估

// 检查一条路线是否满足容量和时间窗约束 bool routeFeasible(const Route& r) { double load = 0, t = 0; for (size_t i = 1; i < r.stops.size(); ++i) { int cur = r.stops[i], prev = r.stops[i - 1]; load += C[cur].demand; if (load > vehicleCapacity + EPS) return false; t += dist(prev, cur); if (t > C[cur].due + EPS) return false; t = max(t, (double)C[cur].ready) + C[cur].service; } return true; } // 将客户 v 插入到 r.stops 的 pos 位置之前，返回cost增量，不可行返回INF double evalInsert(const Route& r, int pos, int v) { if (r.load + C[v].demand > vehicleCapacity + EPS) return INF; vector<int> trial; trial.reserve(r.stops.size() + 1); trial.insert(trial.end(), r.stops.begin(), r.stops.begin() + pos); trial.push_back(v); trial.insert(trial.end(), r.stops.begin() + pos, r.stops.end()); double load = 0, t = 0, newCost = 0; for (size_t i = 1; i < trial.size(); ++i) { int prev = trial[i - 1], cur = trial[i]; load += C[cur].demand; newCost += dist(prev, cur); t += dist(prev, cur); if (t > C[cur].due + EPS) return INF; t = max(t, (double)C[cur].ready) + C[cur].service; if (load > vehicleCapacity + EPS) return INF; } return newCost - r.cost; } // 应用插入：需要把evalInsert算出的delta传进来，避免重复计算 void applyInsert(Route& r, int pos, int v, double delta) { r.stops.insert(r.stops.begin() + pos, v); r.load += C[v].demand; r.cost += delta; }

6.3 VND局部搜索框架

这里给出VND的整体骨架，每一类邻域的搜索函数需要按你实现的邻域补充。

struct Move { int type; // 0=insert, 1=swap, 2=twoOptStar ... int r1, i, r2, j; double delta; }; double totalCost(const vector<Route>& sol) { double c = 0; for (const auto& r : sol) c += r.cost; return c; } void applyMove(vector<Route>& sol, const Move& m) { // 按m.type执行对应的操作，并把r.cost, r.load同步更新 } bool searchNeighborhood(vector<Route>& sol, int l, Move& best) { if (l == 0) { /* 在这里遍历所有relocate候选 */ } if (l == 1) { /* 在这里遍历所有swap候选 */ } if (l == 2) { /* 在这里遍历所有Or-opt候选 */ } if (l == 3) { /* 在这里遍历所有2-opt*候选 */ } return false; } void VND(vector<Route>& sol) { const int L = 4; // 使用4个邻域 int l = 0; while (l < L) { Move m; if (searchNeighborhood(sol, l, m) && m.delta < -EPS) { applyMove(sol, m); l = 0; // 回到第一个邻域重新开始 } else { ++l; } } }

6.4 VNS主循环

vector<Route> shake(const vector<Route>& cur, int k) { vector<Route> s = cur; // 执行k次随机扰动：随机选一条或两条路径，做random relocate或random swap // 扰动后不要求是严格改进，但需要保证扰动后的解基本可行。 // 如果扰动后时间窗不可行，简单办法是丢弃这次扰动并重试。 return s; } vector<Route> VNS(vector<Route> init, int kmax, double timeLimit) { vector<Route> cur = init, best = init; auto start = chrono::steady_clock::now(); while (true) { int k = 1; while (k <= kmax) { vector<Route> xp = shake(cur, k); VND(xp); if (totalCost(xp) < totalCost(cur) - EPS) { cur = xp; if (totalCost(cur) < totalCost(best) - EPS) best = cur; k = 1; } else { ++k; } } // 重置到全局最优，防止cur漂移太远 cur = best; double elapsed = chrono::duration<double>( chrono::steady_clock::now() - start).count(); if (elapsed >= timeLimit) break; } return best; }

我不建议把cur = best这一行删掉。在大量实验里，如果不重置，长时间运行cur会逐渐漂移到比较差的区域，虽然best一直保存着最优解，但后续抖动都基于cur，导致寻找更好解的能力变弱。每隔几轮就回到best附近重来，反而更稳定。

6.5 实际运行表现

用这个框架在网关类标准100客户实例上测试，最便宜插入产生初始解后，VNS跑30秒左右能显著改进初始解，再往上加时间解还能继续缓慢下降。性能瓶颈主要集中在VND的候选评估上，如果客户规模到几百上千，建议先做增量评估，否则评估循环会吃掉大部分运行时间。

我最后再分享两个实际踩过的坑。第一个是时间窗检查的EPS，浮点比较不统一会在连续迭代中出现"来回跳"的假象；第二个是VND中"找到改进就回到邻域1"这个动作千万别省，少了它，算法就退化成普通的大邻域搜索，解质量会明显下降。这个框架看起来简单，但每个细节都卡着搜索效率的上限，祝你在自己的VRPTW项目里一把跑通。