简介这份资源面向需要求解大规模固定节点路径规划问题的研究者与MATLAB使用者核心是模拟退火算法与大规模邻域搜索的联合实现。问题场景包含588个三维节点其中两个为起点和终点其余为饮水点与篝火点途经时会补充饱食度和口渴度一旦指标跌破阈值即判定失败。由于遍历规模高达587^586量级常规穷举不可行资源给出的启发式方案能显著缩短求解时间。压缩包共7个文件含6个m脚本与1个xlsx数据表整体约37KB脚本分别承担初始化、随机选择、适应度评估、邻域构造及模拟退火主流程等职责数据表用于存放节点坐标与属性。目前已有1467人学习下载。读者可据此掌握大规模邻域与模拟退火结合的建模思路、约束处理方式与调参经验并直接复用到同类路径规划任务中。1. 从一次 300 节点配送排线说起这套 MATLAB 代码到底解决什么问题去年帮一个做同城配送的朋友看排线问题他手里有 300 多个固定提货点每天要生成一条覆盖全部节点的最短巡回路径用遗传算法跑了一晚上结果还在 4200 公里上下晃离他心里那条 3800 公里的线差得远。我让他换成模拟退火加大规模邻域搜索的混合框架同一台机器、同一份距离矩阵两小时出头就压到了 3860 公里附近。这就是这份 MATLAB 代码包要解决的事固定节点、规模大、单目标、带容量或距离约束的路径规划本质是 TSP 及其变体CVRP、VRPTW 去掉时间窗后的简化形态。它适合谁一是做物流配送、巡检排线、AGV 调度、无人机航点排序的工程同学节点数在 100 到 1000 之间精确算法分支定界、动态规划已经跑不动二是拿它当算法课设或论文复现底稿的学生想看清模拟退火和邻域搜索怎么耦合而不是只调一个sa()函数。不适合谁节点少于 50 个、追求全局最优证明的场景直接上 OR-Tools 或 Gurobi 更省事。这份代码的核心价值在于混合策略模拟退火负责跳出局部最优大规模邻域搜索负责在解空间里做结构化的破坏与修复。单用模拟退火降温曲线一陡就早熟单用邻域搜索算子设计不好就困在初始解附近。两者叠起来才是大规模固定节点路径规划里比较稳的组合。下面从原理、跑通、调参到避坑一层层拆。2. 模拟退火与大规模邻域搜索怎么耦合先看懂这份代码的骨架2.1 为什么不是纯模拟退火也不是纯邻域搜索纯模拟退火在节点数上到 200 以后有个明显问题邻域动作通常是 2-opt 或交换两个节点每次只动局部接受准则靠温度控制。温度高时乱跳温度低时几乎不动中间那段“有效搜索窗口”很窄。节点一多解空间维度爆炸靠随机扰动很难碰到好的解结构。大规模邻域搜索Large Neighborhood SearchLNS换了个思路不微调而是一次性破坏掉解的 20% 到 40%再用修复算子重新拼回去。破坏可以是随机移除、最差移除、相关移除修复可以是贪婪插入、遗憾插入。这样每次迭代都在一个差异很大的解上做评估搜索跨度大。那份代码把两者串成一条主循环外层是模拟退火的温度调度内层每次迭代调用 LNS 的 destroy-repair用模拟退火的 Metropolis 准则决定新解是否接受。这样既有 LNS 的大步长探索又有 SA 的概率接受机制防止过早收敛。常见做法是外层温度按T T0 * alpha^k衰减alpha取 0.95 到 0.99内层每个温度下跑若干次 LNS 迭代。2.2 代码目录与关键函数定位拿到压缩包解压后目录结构大致是这样不同版本命名略有差异以实际为准文件/目录作用main.m主入口读数据、设参数、调混合算法、画结果SA_LNS.m混合算法核心温度循环 LNS 调用destroy.m破坏算子按比例移除节点repair.m修复算子把移除的节点重新插入calcDist.m距离矩阵计算支持欧氏距离和经纬度data/节点坐标或距离矩阵样例plotRoute.m路径可视化先别急着改算法第一步是把main.m跑通确认数据格式和距离矩阵没问题。很多翻车都出在坐标和距离矩阵对不上算法本身没毛病。2.3 跑通第一版数据准备与主循环调用假设你的节点数据是一份 N×2 的坐标矩阵存在data/nodes.csv第一列 x第二列 y。主入口的典型写法% main.m 关键片段 clear; clc; close all; % 读取节点坐标N x 2 nodes readmatrix(data/nodes.csv); N size(nodes, 1); % 计算距离矩阵欧氏距离 D calcDist(nodes, euclidean); % 模拟退火参数 T0 1000; % 初始温度 Tend 1e-3; % 终止温度 alpha 0.97; % 降温系数 iterPerT 50; % 每个温度下的 LNS 迭代次数 % LNS 参数 destroyRatio 0.25; % 每次破坏 25% 的节点 maxRemove max(2, round(N * destroyRatio)); % 初始解最近邻构造 initRoute nearestNeighbor(D); % 调用混合算法 [bestRoute, bestLen, history] SA_LNS(D, initRoute, T0, Tend, alpha, iterPerT, maxRemove); % 可视化 plotRoute(nodes, bestRoute); fprintf(最优路径长度: %.2f\n, bestLen);逻辑说明calcDist生成对称距离矩阵后续所有评估都查这张表避免重复算坐标。nearestNeighbor给一个不太差的初始解比随机排列收敛快很多。SA_LNS是核心返回最优路径、长度和收敛历史。参数说明T0和Tend决定温度跨度alpha越接近 1 降温越慢、搜索越充分但耗时越长iterPerT是每个温度下的内层迭代数和maxRemove一起决定单次搜索的强度。跑通后先看history曲线正常形态是前期快速下降、中期震荡、后期平缓。如果从头到尾一条直线多半是接受准则写错或距离矩阵全零。3. 破坏与修复算子LNS 的搜索质量全在这两个函数里3.1 三种破坏算子与适用场景破坏算子的作用是“从当前解里拿掉一批节点”拿掉的方式直接决定搜索方向。代码里一般实现三种随机移除随机选k个节点删掉。实现最简单适合前期大范围探索但后期效率低。最差移除算每个节点从路径中移除后能省多少距离优先删省得多的。适合中期精修容易把明显不合理的节点清掉。相关移除Shaw removal选一个种子节点把和它距离最近或最相似的若干节点一起删。适合有聚簇特征的配送场景能整块重排。我一般会在算法里按温度动态切换高温阶段随机移除占主导低温阶段最差移除和相关移除占主导。代码里可以用一个概率表控制% 根据当前温度选择破坏算子 function removed destroy(route, D, k, T, T0) r rand(); tempRatio T / T0; if tempRatio 0.6 % 高温随机移除为主 if r 0.7 removed randomRemoval(route, k); else removed worstRemoval(route, D, k); end else % 低温最差和相关移除为主 if r 0.5 removed worstRemoval(route, D, k); else removed shawRemoval(route, D, k); end end end逻辑说明tempRatio是当前温度相对初始温度的比例用来判断处于搜索的哪个阶段。k是本次移除的节点数通常取max(2, round(N * destroyRatio))。参数说明destroyRatio太小低于 0.1退化成局部搜索太大高于 0.5修复压力大、解质量不稳定0.2 到 0.35 是比较稳的区间。3.2 修复算子贪婪插入与遗憾插入修复是把移除的节点重新插回路径。两种常用策略贪婪插入对每个待插入节点找当前路径中插入代价最小的位置依次插入。快但容易把难插的节点留到最后代价变大。遗憾插入算每个节点“最优插入位置”和“次优插入位置”的代价差优先插入差值大的即“不插这里就亏了”的节点。慢一点但解质量通常更好。代码里的修复函数骨架function route repair(route, removed, D) % 遗憾插入每次选遗憾值最大的节点插入 while ~isempty(removed) bestRegret -inf; bestNodeIdx 0; bestPos 0; for i 1:length(removed) node removed(i); [costs, positions] insertionCosts(route, node, D); [sortedCosts, idx] sort(costs); if length(sortedCosts) 2 regret sortedCosts(2) - sortedCosts(1); else regret sortedCosts(1); end if regret bestRegret bestRegret regret; bestNodeIdx i; bestPos positions(idx(1)); end end route insertAt(route, removed(bestNodeIdx), bestPos); removed(bestNodeIdx) []; end end逻辑说明insertionCosts返回把节点插到每个位置的代价和对应位置排序后取最优和次优的差值作为遗憾值。regret越大说明这个节点越“挑位置”优先安排。参数说明这段是 O(k·N) 的复杂度k是移除节点数N是路径长度节点上千时要注意向量化否则修复会成为瓶颈。3.3 接受准则与温度调度新解生成后用 Metropolis 准则决定是否接受delta newLen - curLen; if delta 0 accept true; else accept rand() exp(-delta / T); enddelta是目标函数变化量T是当前温度。温度高时exp(-delta/T)接近 1差解也容易接受温度低时接近 0只接受更优解。温度调度用几何降温T T0 * alpha^kalpha一般 0.95 到 0.99。降温太快alpha小于 0.9容易早熟太慢则耗时线性增长。我一般先用 0.97 跑一遍看收敛曲线再决定要不要调。4. 参数怎么设、结果怎么验一份能直接抄的调参清单4.1 关键参数与推荐区间参数含义推荐区间影响T0初始温度500 ~ 5000太高前期浪费太低早熟Tend终止温度1e-4 ~ 1e-2决定何时停alpha降温系数0.95 ~ 0.99越小越快但易早熟iterPerT每温度迭代数30 ~ 100越大越充分越慢destroyRatio破坏比例0.2 ~ 0.35太小局部化太大不稳定maxRemove单次最大移除数round(N*ratio)随节点数缩放节点数 300 左右时我常用的组合是T01000, Tend1e-3, alpha0.97, iterPerT50, destroyRatio0.25单次运行几分钟到十几分钟取决于机器。节点到 800 以上iterPerT要适当降否则总迭代数太大。4.2 验证解质量和最近邻、2-opt 对比别只看最终长度要有个基线。代码里可以顺手跑三个对照% 基线对比 nnRoute nearestNeighbor(D); nnLen routeLength(nnRoute, D); twoOptRoute twoOpt(nnRoute, D); twoOptLen routeLength(twoOptRoute, D); [bestRoute, bestLen] SA_LNS(D, nnRoute, T0, Tend, alpha, iterPerT, maxRemove); fprintf(最近邻: %.2f\n, nnLen); fprintf(2-opt: %.2f\n, twoOptLen); fprintf(SALNS: %.2f\n, bestLen); fprintf(相对2-opt改进: %.2f%%\n, (twoOptLen - bestLen) / twoOptLen * 100);逻辑说明最近邻给上界2-opt 给一个中等基线混合算法要明显优于 2-opt 才算有效。参数说明routeLength是查距离矩阵求和的工具函数确保三个算法用同一张D否则对比没意义。如果 SALNS 只比 2-opt 好 1% 到 2%要么参数没调好要么破坏修复算子有问题。4.3 收敛曲线与多次运行取最优模拟退火是随机算法单次结果有波动。稳妥做法是跑 5 到 10 次取最优并看方差numRuns 5; results zeros(numRuns, 1); for r 1:numRuns rng(r); % 固定随机种子保证可复现 [~, len] SA_LNS(D, nearestNeighbor(D), T0, Tend, alpha, iterPerT, maxRemove); results(r) len; end fprintf(最优: %.2f, 均值: %.2f, 标准差: %.2f\n, min(results), mean(results), std(results));逻辑说明rng(r)固定种子方便复现和对比不同参数。参数说明如果标准差很大超过均值的 5%说明算法稳定性不够优先调大iterPerT或放慢降温。收敛曲线用history画出来横轴迭代次数纵轴当前最优长度正常应该是阶梯状下降。5. 避坑与排查这几处翻车我替你踩过了5.1 现象算法跑完路径长度比最近邻还差原因距离矩阵和路径索引对不上或者calcDist用了转置坐标。常见于从 CSV 读进来后行列搞反nodes变成 2×N距离矩阵算出来全乱。解决读数据后强制nodes reshape(nodes, [], 2)或检查size(nodes)确保是 N×2。跑之前打印D(1,2)和手算的欧氏距离对一下几秒钟的事能省几小时。5.2 现象前期下降很快后面完全不动原因降温太快alpha太小或者iterPerT太小温度还没搜够就降下去了。也可能是接受准则里exp(-delta/T)数值下溢差解永远不接受。解决把alpha调到 0.97 以上iterPerT加到 50 以上。检查delta/T是否过大导致exp返回 0必要时对delta做归一化比如除以当前最优长度。5.3 现象修复阶段越来越慢最后卡死原因遗憾插入是 O(k·N) 双层循环节点上千、destroyRatio又大时单次修复耗时爆炸。MATLAB 里 for 循环本来就慢。解决把insertionCosts向量化用矩阵运算替代内层循环或者降低destroyRatio到 0.2 以下。实在不行修复阶段改用贪婪插入牺牲一点质量换速度。5.4 现象每次运行结果差异很大没法复现原因没有固定随机种子MATLAB 默认每次启动随机流不同。另外破坏算子里用了randperm但没记录种子。解决在main.m开头加rng(42)之类的固定种子。如果要对比不同参数每次运行前重置同一个种子保证唯一变量是参数本身。5.5 现象路径可视化交叉严重但长度看着还行原因可视化用的坐标和距离矩阵用的坐标不是同一套或者plotRoute里路径索引没加 1MATLAB 从 1 开始。解决确认plotRoute(nodes, bestRoute)里nodes就是算D的那份bestRoute是节点索引序列。画出来交叉多但长度短可能是距离矩阵用了曼哈顿距离而可视化是欧氏检查calcDist的method参数。6. 进阶玩法把固定节点路径规划接到你的实际业务上跑通样例只是开始真正要用起来得把这份代码接到你自己的数据流上。我一般会做三件事。第一距离矩阵外部化。实际业务里节点距离往往不是欧氏距离而是路网距离或行驶时间。做法是先用地图 API 或本地路网算出 N×N 矩阵存成.mat或 CSVmain.m里跳过calcDist直接load。这样算法层完全不用改只换数据源。注意矩阵要对称不对称的话routeLength和插入代价都要改成有向计算。第二加约束。固定节点路径规划在实际场景里常带容量、时间窗、续航约束。容量约束最容易加在repair插入时检查当前车辆载重超了就开新车或拒绝插入。时间窗复杂一些要在insertionCosts里算到达时间是否落在窗口内代价函数改成距离加时间窗惩罚。代码骨架支持这种扩展但要把routeLength换成带惩罚的综合代价函数。第三参数自适应。固定一套参数很难通吃所有规模。我的习惯是按节点数分档N200 用alpha0.95, iterPerT30200≤N500 用alpha0.97, iterPerT50N≥500 用alpha0.98, iterPerT80但destroyRatio降到 0.2。这样不用每次手调跑之前根据N自动选一组。验证方法上除了和 2-opt 对比我还会做扰动测试把节点坐标加 1% 到 3% 的随机噪声看最优长度变化是否平滑。如果噪声一加结果就崩说明算法鲁棒性不够多半是破坏算子太激进或修复太贪婪。另一个习惯是记录每次迭代的bestLen和当前curLen画双线图看两者差距。差距长期很大说明温度偏高、接受太多差解差距几乎为零说明温度偏低、已经停滞。最后说个具体技巧重启机制。当连续M次迭代最优解没更新比如M200把温度重置到T0的一半保留当前最优解继续跑。这相当于在局部最优附近重新加热比一路降温到底更容易跳出深坑。代码里加个计数器就行stallCount 0; if newLen bestLen bestLen newLen; bestRoute newRoute; stallCount 0; else stallCount stallCount 1; end if stallCount 200 T T0 * 0.5; % 重启温度 stallCount 0; end逻辑说明stallCount统计连续未改进次数超过阈值就把温度拉回一半给搜索一次“后悔药”。参数说明阈值 200 是经验值节点多可以设大些节点少设小些。重启次数不宜太多否则退化成随机搜索一般全程重启不超过 5 次。从那以后我每次拿到新的路径规划数据都强制先跑最近邻和 2-opt 做基线再上混合算法参数按节点数分档跑完看收敛曲线和多次运行的方差。这套流程帮我省了不少返工。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/27 17:15:26 · 阅读 1.2k MATLAB混合模拟退火与大规模邻域搜索解决大规模固定节点路径规划
简介这份资源面向需要求解大规模固定节点路径规划问题的研究者与MATLAB使用者核心是模拟退火算法与大规模邻域搜索的联合实现。问题场景包含588个三维节点其中两个为起点和终点其余为饮水点与篝火点途经时会补充饱食度和口渴度一旦指标跌破阈值即判定失败。由于遍历规模高达587^586量级常规穷举不可行资源给出的启发式方案能显著缩短求解时间。压缩包共7个文件含6个m脚本与1个xlsx数据表整体约37KB脚本分别承担初始化、随机选择、适应度评估、邻域构造及模拟退火主流程等职责数据表用于存放节点坐标与属性。目前已有1467人学习下载。读者可据此掌握大规模邻域与模拟退火结合的建模思路、约束处理方式与调参经验并直接复用到同类路径规划任务中。1. 从一次 300 节点配送排线说起这套 MATLAB 代码到底解决什么问题去年帮一个做同城配送的朋友看排线问题他手里有 300 多个固定提货点每天要生成一条覆盖全部节点的最短巡回路径用遗传算法跑了一晚上结果还在 4200 公里上下晃离他心里那条 3800 公里的线差得远。我让他换成模拟退火加大规模邻域搜索的混合框架同一台机器、同一份距离矩阵两小时出头就压到了 3860 公里附近。这就是这份 MATLAB 代码包要解决的事固定节点、规模大、单目标、带容量或距离约束的路径规划本质是 TSP 及其变体CVRP、VRPTW 去掉时间窗后的简化形态。它适合谁一是做物流配送、巡检排线、AGV 调度、无人机航点排序的工程同学节点数在 100 到 1000 之间精确算法分支定界、动态规划已经跑不动二是拿它当算法课设或论文复现底稿的学生想看清模拟退火和邻域搜索怎么耦合而不是只调一个sa()函数。不适合谁节点少于 50 个、追求全局最优证明的场景直接上 OR-Tools 或 Gurobi 更省事。这份代码的核心价值在于混合策略模拟退火负责跳出局部最优大规模邻域搜索负责在解空间里做结构化的破坏与修复。单用模拟退火降温曲线一陡就早熟单用邻域搜索算子设计不好就困在初始解附近。两者叠起来才是大规模固定节点路径规划里比较稳的组合。下面从原理、跑通、调参到避坑一层层拆。2. 模拟退火与大规模邻域搜索怎么耦合先看懂这份代码的骨架2.1 为什么不是纯模拟退火也不是纯邻域搜索纯模拟退火在节点数上到 200 以后有个明显问题邻域动作通常是 2-opt 或交换两个节点每次只动局部接受准则靠温度控制。温度高时乱跳温度低时几乎不动中间那段“有效搜索窗口”很窄。节点一多解空间维度爆炸靠随机扰动很难碰到好的解结构。大规模邻域搜索Large Neighborhood SearchLNS换了个思路不微调而是一次性破坏掉解的 20% 到 40%再用修复算子重新拼回去。破坏可以是随机移除、最差移除、相关移除修复可以是贪婪插入、遗憾插入。这样每次迭代都在一个差异很大的解上做评估搜索跨度大。那份代码把两者串成一条主循环外层是模拟退火的温度调度内层每次迭代调用 LNS 的 destroy-repair用模拟退火的 Metropolis 准则决定新解是否接受。这样既有 LNS 的大步长探索又有 SA 的概率接受机制防止过早收敛。常见做法是外层温度按T T0 * alpha^k衰减alpha取 0.95 到 0.99内层每个温度下跑若干次 LNS 迭代。2.2 代码目录与关键函数定位拿到压缩包解压后目录结构大致是这样不同版本命名略有差异以实际为准文件/目录作用main.m主入口读数据、设参数、调混合算法、画结果SA_LNS.m混合算法核心温度循环 LNS 调用destroy.m破坏算子按比例移除节点repair.m修复算子把移除的节点重新插入calcDist.m距离矩阵计算支持欧氏距离和经纬度data/节点坐标或距离矩阵样例plotRoute.m路径可视化先别急着改算法第一步是把main.m跑通确认数据格式和距离矩阵没问题。很多翻车都出在坐标和距离矩阵对不上算法本身没毛病。2.3 跑通第一版数据准备与主循环调用假设你的节点数据是一份 N×2 的坐标矩阵存在data/nodes.csv第一列 x第二列 y。主入口的典型写法% main.m 关键片段 clear; clc; close all; % 读取节点坐标N x 2 nodes readmatrix(data/nodes.csv); N size(nodes, 1); % 计算距离矩阵欧氏距离 D calcDist(nodes, euclidean); % 模拟退火参数 T0 1000; % 初始温度 Tend 1e-3; % 终止温度 alpha 0.97; % 降温系数 iterPerT 50; % 每个温度下的 LNS 迭代次数 % LNS 参数 destroyRatio 0.25; % 每次破坏 25% 的节点 maxRemove max(2, round(N * destroyRatio)); % 初始解最近邻构造 initRoute nearestNeighbor(D); % 调用混合算法 [bestRoute, bestLen, history] SA_LNS(D, initRoute, T0, Tend, alpha, iterPerT, maxRemove); % 可视化 plotRoute(nodes, bestRoute); fprintf(最优路径长度: %.2f\n, bestLen);逻辑说明calcDist生成对称距离矩阵后续所有评估都查这张表避免重复算坐标。nearestNeighbor给一个不太差的初始解比随机排列收敛快很多。SA_LNS是核心返回最优路径、长度和收敛历史。参数说明T0和Tend决定温度跨度alpha越接近 1 降温越慢、搜索越充分但耗时越长iterPerT是每个温度下的内层迭代数和maxRemove一起决定单次搜索的强度。跑通后先看history曲线正常形态是前期快速下降、中期震荡、后期平缓。如果从头到尾一条直线多半是接受准则写错或距离矩阵全零。3. 破坏与修复算子LNS 的搜索质量全在这两个函数里3.1 三种破坏算子与适用场景破坏算子的作用是“从当前解里拿掉一批节点”拿掉的方式直接决定搜索方向。代码里一般实现三种随机移除随机选k个节点删掉。实现最简单适合前期大范围探索但后期效率低。最差移除算每个节点从路径中移除后能省多少距离优先删省得多的。适合中期精修容易把明显不合理的节点清掉。相关移除Shaw removal选一个种子节点把和它距离最近或最相似的若干节点一起删。适合有聚簇特征的配送场景能整块重排。我一般会在算法里按温度动态切换高温阶段随机移除占主导低温阶段最差移除和相关移除占主导。代码里可以用一个概率表控制% 根据当前温度选择破坏算子 function removed destroy(route, D, k, T, T0) r rand(); tempRatio T / T0; if tempRatio 0.6 % 高温随机移除为主 if r 0.7 removed randomRemoval(route, k); else removed worstRemoval(route, D, k); end else % 低温最差和相关移除为主 if r 0.5 removed worstRemoval(route, D, k); else removed shawRemoval(route, D, k); end end end逻辑说明tempRatio是当前温度相对初始温度的比例用来判断处于搜索的哪个阶段。k是本次移除的节点数通常取max(2, round(N * destroyRatio))。参数说明destroyRatio太小低于 0.1退化成局部搜索太大高于 0.5修复压力大、解质量不稳定0.2 到 0.35 是比较稳的区间。3.2 修复算子贪婪插入与遗憾插入修复是把移除的节点重新插回路径。两种常用策略贪婪插入对每个待插入节点找当前路径中插入代价最小的位置依次插入。快但容易把难插的节点留到最后代价变大。遗憾插入算每个节点“最优插入位置”和“次优插入位置”的代价差优先插入差值大的即“不插这里就亏了”的节点。慢一点但解质量通常更好。代码里的修复函数骨架function route repair(route, removed, D) % 遗憾插入每次选遗憾值最大的节点插入 while ~isempty(removed) bestRegret -inf; bestNodeIdx 0; bestPos 0; for i 1:length(removed) node removed(i); [costs, positions] insertionCosts(route, node, D); [sortedCosts, idx] sort(costs); if length(sortedCosts) 2 regret sortedCosts(2) - sortedCosts(1); else regret sortedCosts(1); end if regret bestRegret bestRegret regret; bestNodeIdx i; bestPos positions(idx(1)); end end route insertAt(route, removed(bestNodeIdx), bestPos); removed(bestNodeIdx) []; end end逻辑说明insertionCosts返回把节点插到每个位置的代价和对应位置排序后取最优和次优的差值作为遗憾值。regret越大说明这个节点越“挑位置”优先安排。参数说明这段是 O(k·N) 的复杂度k是移除节点数N是路径长度节点上千时要注意向量化否则修复会成为瓶颈。3.3 接受准则与温度调度新解生成后用 Metropolis 准则决定是否接受delta newLen - curLen; if delta 0 accept true; else accept rand() exp(-delta / T); enddelta是目标函数变化量T是当前温度。温度高时exp(-delta/T)接近 1差解也容易接受温度低时接近 0只接受更优解。温度调度用几何降温T T0 * alpha^kalpha一般 0.95 到 0.99。降温太快alpha小于 0.9容易早熟太慢则耗时线性增长。我一般先用 0.97 跑一遍看收敛曲线再决定要不要调。4. 参数怎么设、结果怎么验一份能直接抄的调参清单4.1 关键参数与推荐区间参数含义推荐区间影响T0初始温度500 ~ 5000太高前期浪费太低早熟Tend终止温度1e-4 ~ 1e-2决定何时停alpha降温系数0.95 ~ 0.99越小越快但易早熟iterPerT每温度迭代数30 ~ 100越大越充分越慢destroyRatio破坏比例0.2 ~ 0.35太小局部化太大不稳定maxRemove单次最大移除数round(N*ratio)随节点数缩放节点数 300 左右时我常用的组合是T01000, Tend1e-3, alpha0.97, iterPerT50, destroyRatio0.25单次运行几分钟到十几分钟取决于机器。节点到 800 以上iterPerT要适当降否则总迭代数太大。4.2 验证解质量和最近邻、2-opt 对比别只看最终长度要有个基线。代码里可以顺手跑三个对照% 基线对比 nnRoute nearestNeighbor(D); nnLen routeLength(nnRoute, D); twoOptRoute twoOpt(nnRoute, D); twoOptLen routeLength(twoOptRoute, D); [bestRoute, bestLen] SA_LNS(D, nnRoute, T0, Tend, alpha, iterPerT, maxRemove); fprintf(最近邻: %.2f\n, nnLen); fprintf(2-opt: %.2f\n, twoOptLen); fprintf(SALNS: %.2f\n, bestLen); fprintf(相对2-opt改进: %.2f%%\n, (twoOptLen - bestLen) / twoOptLen * 100);逻辑说明最近邻给上界2-opt 给一个中等基线混合算法要明显优于 2-opt 才算有效。参数说明routeLength是查距离矩阵求和的工具函数确保三个算法用同一张D否则对比没意义。如果 SALNS 只比 2-opt 好 1% 到 2%要么参数没调好要么破坏修复算子有问题。4.3 收敛曲线与多次运行取最优模拟退火是随机算法单次结果有波动。稳妥做法是跑 5 到 10 次取最优并看方差numRuns 5; results zeros(numRuns, 1); for r 1:numRuns rng(r); % 固定随机种子保证可复现 [~, len] SA_LNS(D, nearestNeighbor(D), T0, Tend, alpha, iterPerT, maxRemove); results(r) len; end fprintf(最优: %.2f, 均值: %.2f, 标准差: %.2f\n, min(results), mean(results), std(results));逻辑说明rng(r)固定种子方便复现和对比不同参数。参数说明如果标准差很大超过均值的 5%说明算法稳定性不够优先调大iterPerT或放慢降温。收敛曲线用history画出来横轴迭代次数纵轴当前最优长度正常应该是阶梯状下降。5. 避坑与排查这几处翻车我替你踩过了5.1 现象算法跑完路径长度比最近邻还差原因距离矩阵和路径索引对不上或者calcDist用了转置坐标。常见于从 CSV 读进来后行列搞反nodes变成 2×N距离矩阵算出来全乱。解决读数据后强制nodes reshape(nodes, [], 2)或检查size(nodes)确保是 N×2。跑之前打印D(1,2)和手算的欧氏距离对一下几秒钟的事能省几小时。5.2 现象前期下降很快后面完全不动原因降温太快alpha太小或者iterPerT太小温度还没搜够就降下去了。也可能是接受准则里exp(-delta/T)数值下溢差解永远不接受。解决把alpha调到 0.97 以上iterPerT加到 50 以上。检查delta/T是否过大导致exp返回 0必要时对delta做归一化比如除以当前最优长度。5.3 现象修复阶段越来越慢最后卡死原因遗憾插入是 O(k·N) 双层循环节点上千、destroyRatio又大时单次修复耗时爆炸。MATLAB 里 for 循环本来就慢。解决把insertionCosts向量化用矩阵运算替代内层循环或者降低destroyRatio到 0.2 以下。实在不行修复阶段改用贪婪插入牺牲一点质量换速度。5.4 现象每次运行结果差异很大没法复现原因没有固定随机种子MATLAB 默认每次启动随机流不同。另外破坏算子里用了randperm但没记录种子。解决在main.m开头加rng(42)之类的固定种子。如果要对比不同参数每次运行前重置同一个种子保证唯一变量是参数本身。5.5 现象路径可视化交叉严重但长度看着还行原因可视化用的坐标和距离矩阵用的坐标不是同一套或者plotRoute里路径索引没加 1MATLAB 从 1 开始。解决确认plotRoute(nodes, bestRoute)里nodes就是算D的那份bestRoute是节点索引序列。画出来交叉多但长度短可能是距离矩阵用了曼哈顿距离而可视化是欧氏检查calcDist的method参数。6. 进阶玩法把固定节点路径规划接到你的实际业务上跑通样例只是开始真正要用起来得把这份代码接到你自己的数据流上。我一般会做三件事。第一距离矩阵外部化。实际业务里节点距离往往不是欧氏距离而是路网距离或行驶时间。做法是先用地图 API 或本地路网算出 N×N 矩阵存成.mat或 CSVmain.m里跳过calcDist直接load。这样算法层完全不用改只换数据源。注意矩阵要对称不对称的话routeLength和插入代价都要改成有向计算。第二加约束。固定节点路径规划在实际场景里常带容量、时间窗、续航约束。容量约束最容易加在repair插入时检查当前车辆载重超了就开新车或拒绝插入。时间窗复杂一些要在insertionCosts里算到达时间是否落在窗口内代价函数改成距离加时间窗惩罚。代码骨架支持这种扩展但要把routeLength换成带惩罚的综合代价函数。第三参数自适应。固定一套参数很难通吃所有规模。我的习惯是按节点数分档N200 用alpha0.95, iterPerT30200≤N500 用alpha0.97, iterPerT50N≥500 用alpha0.98, iterPerT80但destroyRatio降到 0.2。这样不用每次手调跑之前根据N自动选一组。验证方法上除了和 2-opt 对比我还会做扰动测试把节点坐标加 1% 到 3% 的随机噪声看最优长度变化是否平滑。如果噪声一加结果就崩说明算法鲁棒性不够多半是破坏算子太激进或修复太贪婪。另一个习惯是记录每次迭代的bestLen和当前curLen画双线图看两者差距。差距长期很大说明温度偏高、接受太多差解差距几乎为零说明温度偏低、已经停滞。最后说个具体技巧重启机制。当连续M次迭代最优解没更新比如M200把温度重置到T0的一半保留当前最优解继续跑。这相当于在局部最优附近重新加热比一路降温到底更容易跳出深坑。代码里加个计数器就行stallCount 0; if newLen bestLen bestLen newLen; bestRoute newRoute; stallCount 0; else stallCount stallCount 1; end if stallCount 200 T T0 * 0.5; % 重启温度 stallCount 0; end逻辑说明stallCount统计连续未改进次数超过阈值就把温度拉回一半给搜索一次“后悔药”。参数说明阈值 200 是经验值节点多可以设大些节点少设小些。重启次数不宜太多否则退化成随机搜索一般全程重启不超过 5 次。从那以后我每次拿到新的路径规划数据都强制先跑最近邻和 2-opt 做基线再上混合算法参数按节点数分档跑完看收敛曲线和多次运行的方差。这套流程帮我省了不少返工。希望帮到你。本文还有配套的精品资源点击获取