VNS算法实战：用C++搞定VRPTW问题的5个关键优化技巧

VNS算法实战用C搞定VRPTW问题的5个关键优化技巧如果你已经对变邻域搜索VNS的基本框架有所了解甚至尝试过用一些开源代码解决简单的旅行商问题那么当你面对带时间窗的车辆路径问题VRPTW时可能会感到一阵头疼。VRPTW不仅要求总行驶距离最短还要满足每个客户的服务时间窗、车辆容量等复杂约束这让传统的VNS实现很容易陷入局部最优或者收敛速度慢得让人失去耐心。我在实际项目中处理过不少大规模的物流配送优化问题从最初的简单VNS实现到后来逐步加入各种优化技巧最终形成了一套相对稳定高效的解决方案。今天分享的这5个关键优化技巧都是经过大量测试验证、能够显著提升算法性能的实战经验希望能帮你少走弯路。1. 邻域结构的设计与组合策略VNS的核心思想就是通过系统性地改变邻域结构来跳出局部最优。对于VRPTW这种复杂问题邻域结构的设计直接决定了算法的搜索能力和效率。很多初学者会直接套用TSP问题的邻域算子结果发现效果并不理想因为VRPTW有额外的时间窗和容量约束。1.1 针对VRPTW的专用邻域算子在VRPTW中除了经典的2-opt、relocate、exchange等算子还需要考虑时间窗的可行性。我常用的几个专用算子包括时间窗敏感的插入算子这个算子在插入客户点时不仅考虑距离成本还会评估对后续客户时间窗的影响。实现时需要对插入点后的所有客户进行时间可行性检查。// 时间窗可行性检查函数示例 bool checkTimeWindowFeasibility(const Route route, int insertPos, Customer newCustomer) { double currentTime route.departureTime; for (int i 0; i route.customers.size(); i) { if (i insertPos) { // 计算新客户的服务开始时间 double arrivalTime currentTime distance(route.customers[i-1], newCustomer); if (arrivalTime newCustomer.readyTime) { arrivalTime newCustomer.readyTime; } if (arrivalTime newCustomer.dueTime) { return false; // 违反时间窗 } currentTime arrivalTime newCustomer.serviceTime; } if (i route.customers.size()) { Customer cust route.customers[i]; double arrivalTime currentTime distance(prevCustomer, cust); // ... 原有客户的时间窗检查 } } return true; }路径内时间窗优化算子专门优化单条路径内的时间窗约束违反通过调整客户访问顺序来减少等待时间或延迟。跨路径容量平衡算子当某些路径负载过重而其他路径负载较轻时通过客户转移来平衡各车辆的负载同时考虑时间窗约束。1.2 邻域结构的动态选择机制固定顺序执行邻域算子往往不是最优策略。我推荐使用自适应权重选择机制根据每个算子的历史表现动态调整其被选中的概率。算子类型初始权重成功改进次数失败次数当前权重选择概率2-opt intra1.015101.20.25Relocate1.02081.50.31Exchange1.012150.90.19Time-window opt1.01851.80.25注意权重的更新需要设置合理的衰减机制避免某个算子因为早期表现好而长期占据主导地位。我通常采用指数衰减每次迭代后所有权重乘以0.99然后根据本次迭代的表现进行奖励或惩罚。实现代码框架如下class AdaptiveNeighborhoodSelector { private: struct OperatorInfo { double weight; int successCount; int totalAttempts; double score; // 成功改进的平均幅度 }; std::vectorOperatorInfo operators; std::discrete_distribution dist; public: int selectOperator() { // 根据权重计算选择概率 std::vectordouble probabilities; for (const auto op : operators) { probabilities.push_back(op.weight); } std::discrete_distribution dist(probabilities.begin(), probabilities.end()); return dist(rng); } void updateWeight(int opIndex, bool improved, double improvement) { OperatorInfo op operators[opIndex]; op.totalAttempts; if (improved) { op.successCount; op.score (op.score * (op.successCount - 1) improvement) / op.successCount; // 奖励权重增加 op.weight * (1.0 0.1 * (improvement / op.score)); } else { // 惩罚权重减少 op.weight * 0.95; } // 权重边界控制 op.weight std::max(0.1, std::min(5.0, op.weight)); } };2. Shaking阶段的智能扰动策略Shaking阶段的目标是将当前解扰动到另一个区域避免陷入局部最优。但简单的随机扰动往往效率低下特别是对于VRPTW这种约束严格的问题随机扰动很容易产生不可行解。2.1 基于问题特征的定向扰动我发现在VRPTW中以下几种扰动策略效果显著关键路径破坏识别当前解中的瓶颈路径——那些时间窗约束紧张或负载过重的路径优先对这些路径进行破坏。可以通过计算每条路径的松弛度来评估double calculateRouteTightness(const Route route) { double totalSlack 0; double currentTime route.startTime; for (int i 0; i route.customers.size(); i) { const Customer cust route.customers[i]; double travelTime (i 0) ? distance(depot, cust) : distance(route.customers[i-1], cust); double arrivalTime currentTime travelTime; double waitTime std::max(0.0, cust.readyTime - arrivalTime); double delay std::max(0.0, arrivalTime - cust.dueTime); // 松弛度计算等待时间越小、延迟越大路径越紧张 totalSlack waitTime - delay; currentTime std::max(arrivalTime, cust.readyTime) cust.serviceTime; } return totalSlack / route.customers.size(); // 平均松弛度 }客户聚类破坏将地理位置相近的客户作为一个整体进行移除和重新插入这比随机移除单个客户更有效。可以使用K-means或基于距离的聚类算法std::vectorstd::vectorint clusterCustomersByProximity( const std::vectorCustomer customers, int k, const Solution currentSolution) { // 基于当前解中客户的位置关系进行聚类 // 返回k个客户簇 }2.2 扰动强度的自适应调整扰动强度移除客户的数量需要根据搜索进程动态调整。我的经验是初期阶段使用较小的扰动强度移除5-10%的客户专注于局部精细搜索中期阶段逐渐增加扰动强度10-20%扩大搜索范围后期阶段当长时间没有改进时使用较大扰动20-30%尝试跳出当前区域实现时可以记录无改进迭代次数并据此调整扰动强度class AdaptiveShaking { private: int noImproveCount 0; int minRemove 3; // 最少移除客户数 int maxRemove 15; // 最多移除客户数 int currentRemove 5; // 当前移除数量 public: Solution shake(Solution current, const ProblemInstance instance) { // 根据无改进次数调整扰动强度 if (noImproveCount 50) { currentRemove std::min(maxRemove, currentRemove 2); } else if (noImproveCount 10) { currentRemove std::max(minRemove, currentRemove - 1); } // 选择要移除的客户 auto customersToRemove selectCustomersToRemove(current, currentRemove); // 从解中移除这些客户 Solution perturbed removeCustomers(current, customersToRemove); // 使用贪心或 regret 启发式重新插入 perturbed reinsertCustomers(perturbed, customersToRemove, instance); return perturbed; } void update(bool improved) { if (improved) { noImproveCount 0; currentRemove std::max(minRemove, currentRemove - 1); } else { noImproveCount; } } };3. 局部搜索的加速技巧VNS算法中局部搜索是最耗时的部分。对于VRPTW这种复杂问题朴素的局部搜索可能需要检查所有可能的邻域移动计算量巨大。下面分享几个我常用的加速技巧。3.1 候选列表策略不是所有可能的移动都值得评估。通过预计算和筛选只评估那些有潜力的移动。基于距离的候选列表对于每个客户只考虑与其最近的k个客户之间的交换或重定位。这个k值可以根据问题规模调整通常取10-20。class CandidateList { private: std::vectorstd::vectorint nearestNeighbors; // 每个客户的最近邻列表 public: void build(const std::vectorCustomer customers, int k) { nearestNeighbors.resize(customers.size()); #pragma omp parallel for for (int i 0; i customers.size(); i) { std::vectorstd::pairdouble, int distances; for (int j 0; j customers.size(); j) { if (i ! j) { double dist calculateDistance(customers[i], customers[j]); distances.emplace_back(dist, j); } } // 按距离排序取前k个 std::sort(distances.begin(), distances.end()); for (int idx 0; idx std::min(k, (int)distances.size()); idx) { nearestNeighbors[i].push_back(distances[idx].second); } } } const std::vectorint getNeighbors(int customerIdx) const { return nearestNeighbors[customerIdx]; } };基于时间窗兼容性的筛选两个客户如果时间窗完全不重叠那么交换它们很可能不会产生可行解。可以预先计算客户间的时间窗兼容性bool areTimeWindowsCompatible(const Customer c1, const Customer c2) { // 如果c1的最早开始时间 服务时间 旅行时间 c2的最晚结束时间 // 或者反过来那么这两个客户在路径中不能相邻 double earliestAtC2 c1.readyTime c1.serviceTime distance(c1, c2); if (earliestAtC2 c2.dueTime) return false; double earliestAtC1 c2.readyTime c2.serviceTime distance(c2, c1); if (earliestAtC1 c1.dueTime) return false; return true; }3.2 增量计算与缓存在评估邻域移动时很多计算是重复的。通过增量计算和缓存可以大幅减少计算量。路径评估缓存对于每条路径缓存其总距离、总时间、负载等信息。当进行客户移动时只需要更新受影响的部分。class RouteCache { private: struct CachedRoute { double totalDistance; double totalTime; int totalDemand; bool feasible; std::vectordouble arrivalTimes; std::vectordouble departureTimes; }; std::unordered_mapint, CachedRoute cache; // 路径ID到缓存数据的映射 public: bool isMoveBeneficial(const Move move, const Solution solution) { // 检查缓存中是否有受影响路径的最新评估 if (!cacheValid(move.route1) || !cacheValid(move.route2)) { // 重新计算并更新缓存 updateCache(move.route1, solution); updateCache(move.route2, solution); } // 使用缓存数据快速评估移动 return evaluateMoveUsingCache(move, cache[move.route1], cache[move.route2]); } void applyMove(const Move move, Solution solution) { // 应用移动 applyMoveToSolution(move, solution); // 更新缓存 invalidateCache(move.route1); invalidateCache(move.route2); } };距离矩阵预计算这是最基础的优化但很多人忽略了对距离矩阵的优化存储和访问。对于大规模问题使用float而不是double存储距离使用对称矩阵只存储一半等方法都能提升性能。class DistanceMatrix { private: std::vectorfloat data; int n; public: DistanceMatrix(int size) : n(size) { data.resize(n * (n 1) / 2); // 三角矩阵存储 } float get(int i, int j) const { if (i j) std::swap(i, j); return data[i * n - i * (i - 1) / 2 (j - i)]; } void set(int i, int j, float value) { if (i j) std::swap(i, j); data[i * n - i * (i - 1) / 2 (j - i)] value; } };4. 针对VRPTW约束的特殊处理VRPTW的约束处理是算法实现中的难点。简单的时间窗检查可能让算法陷入可行解很少的区域需要更智能的约束处理策略。4.1 松弛时间窗的引导搜索在搜索过程中可以暂时放宽时间窗约束引导搜索向有希望的区域进行最后再修复解的可行性。自适应惩罚函数将时间窗违反作为惩罚项加入目标函数并动态调整惩罚权重。class AdaptivePenalty { private: double timeWindowPenalty 1.0; double capacityPenalty 1.0; int feasibleIterations 0; int infeasibleIterations 0; public: double evaluateSolution(const Solution solution) { double totalCost solution.totalDistance; // 计算时间窗违反总量 double twViolation calculateTimeWindowViolation(solution); totalCost timeWindowPenalty * twViolation; // 计算容量违反总量 double capacityViolation calculateCapacityViolation(solution); totalCost capacityPenalty * capacityViolation; return totalCost; } void updateWeights(const Solution current, const Solution best) { // 如果当前解可行而历史最优解不可行降低惩罚权重 // 如果当前解不可行而历史最优解可行增加惩罚权重 bool currentFeasible isFeasible(current); bool bestFeasible isFeasible(best); if (currentFeasible !bestFeasible) { timeWindowPenalty * 0.9; capacityPenalty * 0.9; } else if (!currentFeasible bestFeasible) { timeWindowPenalty * 1.1; capacityPenalty * 1.1; } // 权重边界控制 timeWindowPenalty std::max(0.1, std::min(10.0, timeWindowPenalty)); capacityPenalty std::max(0.1, std::min(10.0, capacityPenalty)); } };4.2 时间窗约束的快速检查技巧完全的时间窗可行性检查需要遍历整条路径计算量大。可以设计一些快速检查规则提前排除明显不可行的移动。时间窗冲突预检测在进行客户移动前先检查一些简单条件bool quickTimeWindowCheck(const Customer c1, const Customer c2, double arrivalTimeAtC1, double serviceTimeC1) { // 检查c1服务完成后能否及时到达c2 double departureFromC1 arrivalTimeAtC1 serviceTimeC1; double travelTime distance(c1, c2); double earliestArrivalAtC2 departureFromC1 travelTime; // 如果最早到达时间已经晚于c2的最晚服务时间直接拒绝 if (earliestArrivalAtC2 c2.dueTime) { return false; } // 检查c2服务完成后能否回到仓库如果有时间限制 double departureFromC2 std::max(earliestArrivalAtC2, c2.readyTime) c2.serviceTime; double travelToDepot distance(c2, depot); if (departureFromC2 travelToDepot depotDueTime) { return false; } return true; }路径时间窗特征缓存为每条路径缓存最早可能开始时间和最晚必须结束时间用于快速判断客户插入的可行性。struct RouteTimeWindowProfile { double earliestStart; // 路径能开始的最早时间 double latestFinish; // 路径必须结束的最晚时间 std::vectordouble slackAtPosition; // 每个位置的时间松弛度 }; bool canInsertCustomer(const RouteTimeWindowProfile profile, const Customer newCustomer, int insertPosition) { // 使用缓存的特征快速判断插入可行性 if (insertPosition 0) { // 插入路径开头 double arrivalTime profile.earliestStart distance(depot, newCustomer); if (arrivalTime newCustomer.dueTime) return false; double newEarliestStart std::max(arrivalTime, newCustomer.readyTime) newCustomer.serviceTime; // 检查是否影响后续客户 if (newEarliestStart profile.slackAtPosition[0]) { return false; } } else { // 插入路径中间 // 类似逻辑但需要考虑前后客户的影响 } return true; }5. 算法参数的自适应调整与并行化最后一个关键技巧是关于算法整体的调优。VNS有很多参数需要设置手动调参既费时又难以找到最优组合。我推荐使用自适应参数调整和并行化搜索来提升算法性能。5.1 关键参数的自适应调整VNS中最重要的几个参数包括邻域结构数量、shaking强度、局部搜索深度、接受劣解的概率等。这些参数都可以根据搜索进程动态调整。基于搜索状态的参数调整class AdaptiveVNSParameters { private: struct SearchState { double improvementRate; // 近期改进率 double diversity; // 解空间的多样性 int stagnationCount; // 停滞迭代次数 double temperature; // 模拟退火温度用于接受劣解 }; SearchState currentState; public: Parameters getCurrentParameters() { Parameters params; // 根据当前状态调整参数 if (currentState.stagnationCount 100) { // 长期停滞增加扰动强度 params.shakingStrength std::min(0.3, 0.1 0.01 * currentState.stagnationCount); params.acceptWorseProbability 0.2; // 增加接受劣解的概率 } else if (currentState.improvementRate 0.1) { // 改进较快加强局部搜索 params.localSearchDepth deep; params.shakingStrength 0.05; // 减小扰动 } else { // 正常搜索状态 params.localSearchDepth medium; params.shakingStrength 0.1; params.acceptWorseProbability 0.05; } // 根据解多样性调整 if (currentState.diversity 0.1) { // 解过于集中需要增加多样性 params.useDiversification true; params.shakingStrength * 1.5; } return params; } void updateState(const Solution current, const Solution best, const std::vectorSolution recentSolutions) { // 计算改进率 currentState.improvementRate calculateImprovementRate(recentSolutions); // 计算解多样性 currentState.diversity calculateDiversity(recentSolutions); // 更新停滞计数 if (current.cost best.cost * 0.999) { // 几乎没有改进 currentState.stagnationCount; } else { currentState.stagnationCount 0; } // 更新温度模拟退火机制 currentState.temperature * 0.995; // 缓慢降温 } };5.2 并行VNS实现策略对于大规模VRPTW问题单线程的VNS可能需要很长时间才能找到满意解。通过并行化可以显著加速搜索过程。多起点并行搜索启动多个VNS线程每个线程从不同的初始解开始搜索定期交换信息。class ParallelVNS { private: std::vectorVNSThread threads; std::shared_ptrSolutionPool solutionPool; std::mutex poolMutex; public: void run(int numThreads, const ProblemInstance instance) { // 创建线程 for (int i 0; i numThreads; i) { threads.emplace_back([this, i, instance]() { VNSSolver solver; Solution localBest generateInitialSolution(instance, i); // 不同的初始解 while (!shouldTerminate()) { // 执行VNS迭代 Solution newSolution solver.iterate(localBest); // 更新本地最优 if (newSolution.cost localBest.cost) { localBest newSolution; // 将改进的解加入共享池 std::lock_guardstd::mutex lock(poolMutex); solutionPool-addSolution(localBest); } // 定期从共享池获取其他线程的好解 if (iteration % 100 0) { std::lock_guardstd::mutex lock(poolMutex); Solution borrowed solutionPool-getBestDiverseSolution(localBest); if (borrowed.cost localBest.cost * 1.01) { // 接受稍差的解增加多样性 localBest borrowed; } } } }); } // 等待所有线程完成 for (auto thread : threads) { thread.join(); } } };异步信息交换机制线程间不需要严格同步通过共享内存或消息队列交换优秀解片段。class SolutionPool { private: std::vectorSolution solutions; std::unordered_setsize_t solutionHashes; // 用于去重 const size_t maxSize 100; public: void addSolution(const Solution sol) { size_t hash calculateSolutionHash(sol); if (solutionHashes.find(hash) solutionHashes.end()) { std::lock_guardstd::mutex lock(mutex); if (solutions.size() maxSize) { // 移除最旧的解 solutions.erase(solutions.begin()); } solutions.push_back(sol); solutionHashes.insert(hash); } } Solution getBestDiverseSolution(const Solution reference) { std::lock_guardstd::mutex lock(mutex); if (solutions.empty()) return reference; // 寻找与参考解差异较大但质量较好的解 double bestScore -std::numeric_limitsdouble::max(); Solution bestSolution reference; for (const auto sol : solutions) { if (sol reference) continue; double diversity calculateDiversity(sol, reference); double quality 1.0 / (1.0 sol.cost); // 综合考虑质量和多样性 double score 0.7 * quality 0.3 * diversity; if (score bestScore) { bestScore score; bestSolution sol; } } return bestSolution; } };GPU加速的邻域评估对于需要评估大量相似移动的操作如评估一个客户所有可能的插入位置可以使用GPU并行计算。// CUDA示例并行评估所有可能的插入位置 __global__ void evaluateInsertionsKernel(const Customer* customers, const Route* routes, double* insertionCosts, int numCustomers, int numRoutes) { int idx blockIdx.x * blockDim.x threadIdx.x; if (idx numCustomers * numRoutes) { int customerIdx idx / numRoutes; int routeIdx idx % numRoutes; // 评估将customerIdx插入routeIdx的每个可能位置 double bestCost INFINITY; for (int pos 0; pos routes[routeIdx].size(); pos) { double cost evaluateInsertion(customers[customerIdx], routes[routeIdx], pos); bestCost min(bestCost, cost); } insertionCosts[idx] bestCost; } }在实际项目中我通常先实现一个完整的单线程VNS确保算法逻辑正确然后再逐步添加这些优化技巧。从邻域算子的精心设计到shaking策略的智能化再到局部搜索的加速和约束处理的优化最后通过参数自适应和并行化提升整体性能——这样一个循序渐进的过程既能保证代码质量又能逐步提升算法效果。记得在实现过程中要添加详细的日志和性能统计这样在调优时才能知道每个改动带来的实际影响。我习惯为每个关键组件添加性能计数器比如记录每个邻域算子被调用的次数、成功改进的次数、平均改进幅度等这些数据对于后续的参数调整和算法改进至关重要。