做物流优化或者运筹算法应用的朋友估计对VRPTW带时间窗的车辆路径问题都有切身体会真实配送场景里绝大多数订单都带时间窗早到要等晚到可能就是拒收。这类问题用启发式算法来解是常规操作可一旦要把“改进粒子群算法 局部最优搜索 大规模邻域搜索”这套组合真正落地成能跑出结果的MATLAB代码路上还是会踩不少坑。这篇博文就记录我自己用这套混合框架解决带时间窗配送路径优化的完整过程包括问题建模、算法设计、MATLAB代码实现、调参思路和问题排查。代码不依赖额外工具箱复制下来就能跑小中型算例。如果你正在做配送路径优化或者想给粒子群算法加一组实用的搜索增强模块这篇文章应该能帮你省下不少验证时间。1. 项目概述与问题建模1.1 带时间窗的配送路径优化到底在优化什么先说清楚我们面对的优化问题。以配送中心为起点和终点多台车需要服务一批已知位置的客户每个客户有两个硬性边界最早开始服务时间ready time和最晚必须到达时间due time这叫时间窗。车辆早到了可以等但晚到就不允许或者说要付出巨大的惩罚成本。同时每台车有载重上限每条路径的总需求量不能超载。优化目标是找一个车辆调度与路径分配方案使得总行驶距离最短、用的车辆尽量少。这个问题的难点在于它同时包含三个维度的决策订单分组哪些客户被分到同一台车上路径顺序同一台车内部按什么顺序访问客户时间约束每个客户的到达时间是否落在窗口内以及等待时间是否对后续节点造成延迟如果只有路径顺序问题那就是经典的TSP加上多车分组变成VRP再叠加大型车容量约束和时间窗限制就成了VRPTW。这个升级过程每一步都会大幅增加解的搜索空间。比如50个客户的VRPTW可行的配送方案数量级远不是50的阶乘那么简单因为你还得对客户分组、对组内排序同时每台车还要严格满足时间上的先后关系。正因为空间大、约束多工程上几乎不会去求精确最优解而是用启发式算法和元启发式算法在有限时间内抢一个可接受的次优解。1.2 为什么标准的粒子群算法直接用在VRPTW上效果很砸粒子群算法PSO本质上是为连续优化问题设计的。它的核心假设是粒子在连续空间中有位置和速度可以通过群体认知向当前最优解靠近。这个机制在函数优化、神经网络权重训练这类连续问题上表现优异但VRPTW是离散的组合优化问题客户顺序不是连续变量路径也不是单一的实数向量。很多初学者第一次尝试都会犯一个致命错误直接把粒子位置定义成“客户访问顺序的排列”然后用标准PSO公式去更新位置。结果你会发现粒子群的位置更新公式一旦执行减法、加法和乘系数操作原来的整数排列就变成了带小数的乱序根本没有意义。即使强行取整或者重排也会遇到第二个问题标准PSO极其容易陷入局部最优。因为粒子在迭代后期快速聚集到某个粒子的位置附近而VRPTW的搜索空间是高度多峰值的一个局部最优意味着很多客户的分组方法和顺序搭配被固定死了很难跳出去。我实测过纯PSO跑25个客户的小算例经常在第60代左右就收敛但是结果比邻域搜索加扰动找出来的解差一大截而且后续再怎么迭代也不会提升。所以要改造PSO核心方向并不是把粒子群本身变得多复杂而是给它配两套外挂局部最优搜索在粒子找到“自我历史最优解”之后对解做精细微调把这个粒子挖到的局部区域挖到底大规模邻域搜索LNS在整个群体的全局最优解陷入停滞时对解做破坏和重建让算法跳出困局这个思路的本质是把粒子群当作全局探索器两台搜索处理器分别负责“局部深耕”和“全局破局”三者配合才构成了标题里说的改进粒子群算法。1.3 问题数学描述为了让你清楚代码里每一个公式和判断是怎么回事我先给目标函数下一个严格表达。配送中心编号为0客户编号为1到N。车辆集合为V每台车的最大载重为Q。客户i有坐标、需求量q_i、最早到达时间a_i、最晚到达时间b_i、服务时间s_i。定义决策变量x_{ijk}表示车辆k是否从节点i直接前往节点jy_{ik}表示节点i是否由车辆k服务。目标函数为min sum over k, over i,j (x_{ijk} * d_{ij})也就是总行驶距离。每条路径必须满足下面这些硬约束每台车从配送中心出发服务完分配给它的客户最后回到配送中心每个客户只能被一台车服务一次每条路径的累计载重量不超过Q车辆到达客户i的时刻t_i必须满足 a_i t_i b_i即满足时间窗在MATLAB实现中我没有采用严格数学规划求解而是把约束转换成“解是否合法”的判断逻辑解码完成后先检查每辆车容量和每个客户的时间窗只要有一条路径不合法就惩罚它否则记录总距离。这样处理的好处是算法在搜索过程中不排斥略微越界的候选解保留一定的跳跃和探索能力。2. 改进算法设计思路2.1 整体框架PSO负责粗搜两大搜索模块负责精搜我的混合算法框架可以概括成一个三层结构第一层粒子群主循环。每个粒子保存一个连续向量向量长度等于客户数量。这个向量叫随机键random key它的每个分量可以理解成“客户在服务优先级列表中的竞争值”。粒子群公式负责更新这个连续向量保持PSO原有的全局寻优能力。第二层解码器。把连续随机键转换成实际配送路径。解码时先按随机键大小对客户排序得到一个大致的访问优先级然后按顺序尝试把客户插入当前车辆的路径尾部如果超过载重或导致某个客户的时间窗违反就开下一辆车。这种方式可以把一个连续向量映射成一组车辆路径把离散的组合优化问题转换成PSO可以处理的连续空间表达。第三层两个增强搜索模块。局部最优搜索对单车路径做2-opt和Or-opt精细优化LNS则把当前全局最优解拿出来人为移除一批客户再按照代价最低的原则重新插入。局部搜索主要解决“粒子个体不够精”的问题LNS主要解决“群体全局停滞”的问题。这样分层设计逻辑清晰代码调试起来也非常友好。2.2 随机键编码为什么比直接排列编码更稳这个选择可能是我在这套代码里最想强调的一个点。直接排列编码最大的诱惑是直观——粒子直接代表“1, 3, 5, 2, 4...”这样的访问顺序人一眼就能看懂。但问题也很明显PSO的更新公式没法在排列空间中进行数学运算而且排列空间中两个粒子的“距离”不好定义。随机键编码的思路完全不同粒子向量每个分量是连续实数直接在连续欧式空间中做标准PSO更新完全不需要修改速度、位置的加减乘除公式。解码时只需要一次排序操作把随机键从小到大排序得到对应的客户顺序再用贪心分组策略把客户分配到车辆路径上。举个例子假设有5个客户某个粒子的随机键为 [0.82, 0.13, 0.54, 0.97, 0.29]。按从小到大排序得到客户顺序为 2, 5, 3, 1, 4。然后解码先把客户2插入第1辆车计算路径耗时是否满足再尝试插入客户5如果容量或时间窗不满足就新开一辆车。这种方法虽然多了一步排序和解码但换来的是PSO整个机制不用改稳定性极高。我在多个算例上测试过同样的迭代次数随机键编码的种群多样性比排列编码好得多不容易早熟。2.3 局部最优搜索在粒子历史最优解上做2-opt与Or-opt局部最优搜索怎么嵌入到PSO流程里而不是盲目对所有粒子做这是很多人容易踩的坑。如果每一代对每一个粒子都做一遍彻底的2-opt计算量会爆炸而且很多粒子本身质量很差做局部搜索纯粹是浪费时间。我的策略是局部搜索只在两个时机触发。第一个时机当某个粒子更新后的解优于它的历史最优解pbest时。这说明这个粒子刚刚找到了一个新的更优区域值得深耕。对这一个解内部执行以下操作2-opt在一条路径内选择两个位置i和j将i到j之间的访问顺序反转。比如路径是“0-2-5-3-1-0”把其中某段反转成“0-2-1-3-5-0”。对每一条路径都遍历所有可能的(i, j)组合如果反转后总距离下降且时间窗依然可行就接受这次反转。Or-opt把路径中连续的一段长度为1、2、3的客户序列移动到另一个位置重新插入。这个操作对调整因为时间紧迫度不同而错位的客户顺序非常有效。第二个时机每隔固定代数例如50代对所有粒子的pbest做一次局部搜索。这一轮的作用是清理长期积累下来的解劣化把群体整体质量拉高一点为后续PSO搜索提供更好的起点。局部搜索时要注意一点所有操作必须重新验证时间窗而不是只看距离降低。距离降低了但晚到客户多了反而会让解的合法性变差。所以我的验收逻辑是新旧解距离差加上时间窗违反量惩罚后的综合值只有综合值下降才接受。2.4 大规模邻域搜索destroy-repair机制如何帮PSO跳出局部坑大规模邻域搜索Large Neighborhood SearchLNS的思想非常直白从当前解中删除一批客户再用一种较聪明的重新插入方法把它们放回去。标题里写的“大规模领域搜索算法”业内标准称呼其实是“大规模邻域搜索”很多文献和代码里也用Large Neighborhood Search注意别在注释里写成“领域”意思虽然都知道但搜资料时容易乱。LNS的核心在于两个操作的设计destroy破坏从当前路径中移除K个客户。K不能太小太小了等于什么都没做也不能太大太大了修复难度高容易导致不可行。我推荐K取客户总数的15%到30%。移除的方式有两种随机移除和相关性移除。随机移除简单粗暴可以保证探索的随机性相关性移除会优先移除那些在时间窗上比较接近或属于同一路径的客户这样重插时更容易找到更优的位置。我一般两者混用一半随机一半按“离路径最短”的相关性来移除。repair修复把被移除的客户按照一定的插入规则重新放回路径中。最简单的是最便宜插入对每个被移除的客户尝试插入所有路径的所有可能位置计算新增距离和时间窗违反量最小的位置插入。再进一步是后悔插入对每个客户计算它最好的插入位置与第二好的插入位置之间的代价差距优先插入那些“错过最好位置就损失最大”的客户这种方法能显著提高修复质量。LNS触发时机也很有讲究。我用的是“全局连续未更新计数”当全局最优解连续15代没有任何改进时就触发一次LNS。注意如果每代都触发LNS算法就可能在多个局部最优之间反复跳跃永远稳定不下来。我还在LNS里加了接受准则——只接受比当前gBest更优的解保证它不会把好解越做越差。3. MATLAB代码实现详解3.1 输入数据格式与数据结构设计代码第一步是定义问题数据。我推荐用矩阵和结构体存放数据而不是散落的变量这样后续解码、局部搜索、LNS调用起来清晰得多。对于客户数据我使用矩阵custs每一行代表一个客户列为x坐标、y坐标、需求量、最早服务时间、最晚服务时间、服务时长。配送中心单独用depot结构体存。所有节点之间的距离预计算成矩阵distMat尺寸为(n1) x (n1)因为配送中心也算一个节点索引0位配送中心客户是1到n。这样设计的好处是距离查询一次搞定不用在循环里反复计算欧式距离大幅降低内层循环耗时。如果客户坐标固定距离矩阵在整个优化过程中只需要算一次这是一个容易忽视的性能优化点。3.2 时间窗检查与路径代价计算这是整个算法的基础函数。任何路径在局部搜索、解码、LNS修复阶段都需要快速判断是否合法。检查逻辑并不复杂最大的坑在于“等待时间”的处理。车辆到达客户i时不能早于a_i如果到达太早就等到a_i再开始服务开始服务时间记为start_i max(arrival_i, a_i)。客户i的服务完成时间为start_i s_i车辆接着去下一个客户j到达时间就是完成时间加d_ij。下面是可行性检查函数的MATLAB核心片段function [totalDist, totalViol, feasible] evaluateRoute(route, custs, distMat) % route 是不含0的客户索引序列比如[2 5 3 1 4] % 返回值总距离、时间窗总违反量、是否完全可行 n length(route); arrival 0; % 从配送中心0出发起始时刻为0 totalDist 0; totalViol 0; prev 0; reservedCap 0; Q 200; % 车辆容量按你的算例自行调整 feasible true; for i 1:n cust route(i); travel distMat(prev 1, cust 1); % 1是因为MATLAB索引从1开始 arrival arrival travel; ready custs(cust, 4); due custs(cust, 5); service custs(cust, 6); if arrival ready startTime ready; % 早到就等待 else startTime arrival; end if startTime due totalViol totalViol (startTime - due); feasible false; end departure startTime service; % 离开节点时间 totalDist totalDist travel; prev cust; arrival departure; end totalDist totalDist distMat(prev 1, 1); % 回配送中心 end注意这里我把feasible定义为整条路径所有客户时间窗全部可行的状态。在PSO早期很多解会违反时间窗我不会立刻丢弃而是计入totalViol并放大惩罚这样算法能通过不断降低违反量逐步逼近可行域。惩罚系数M取所有客户到配送中心距离之和的10倍以上确保“不可行解减少M距离”不会优于“可行解”。3.3 随机键解码从连续粒子变成车辆路径解码器负责把粒子向量映射成一组路径。我采用的策略是串行贪婪插入先把随机键按升序排序得到客户服务顺序然后从第一辆车开始按顺序逐个尝试将客户插入当前路径的末尾如果该客户加入后当前车辆累计载重超过容量Q或者evaluateRoute显示时间窗违反量显著升高就关掉这台车开启新的路径。实际运行下来我觉得这个解码方式虽然简单但效果足够稳。在容量约束的处理上我并不会因为一次时间窗违反就立刻新开一辆车因为时间窗是可以通过调整顺序来缓解的而载重超过容量则是硬性的物理限制没有任何后续操作能够挽回必须新开车辆。解码函数签名大致如下读者可以按这个骨架去补全。function [routes, totalDist, totalViol, pbestVector] decodeRandomKey(key, custs, distMat, Q) n size(custs, 1); order getOrderByKey(key); % 将随机键排序得到客户优先顺序 routes {}; totalDist 0; totalViol 0; currentRouteCap 0; currentRoute []; tempRoute []; for idx 1:n cust order(idx); tempRoute [currentRoute, cust]; newCap currentRouteCap custs(cust, 3); [distanceNew, violNew, ~] evaluateRoute(tempRoute, custs, distMat); if newCap Q % 当前路径容量已满保存并开启新路径 routes{end1} currentRoute; currentRoute [cust]; currentRouteCap custs(cust, 3); else currentRoute tempRoute; currentRouteCap newCap; end end if ~isempty(currentRoute) routes{end1} currentRoute; end % 最后把每条路径的距离累加 for r 1:length(routes) path routes{r}; [d, v, ~] evaluateRoute(path, custs, distMat); totalDist totalDist d; totalViol totalViol v; end pbestVector key; % 这里返回随机键本身作为粒子历史最优位置 end有的读者可能会问为什么不在解码阶段直接做插入最优位置而是只在路径尾部追加我的回答是解码速度优先。每代有几十上百个粒子如果每个粒子都去做最优插入解码成本是O(m*n^2)根本跑不动。尾巴追加这种方法虽然得到的路径不一定最优但后续的局部搜索和LNS会负责把路径精修到更好所以整体上是划算的。3.4 局部最优搜索的核心实现局部搜索模块对一组路径中的每一条逐条施加2-opt和Or-opt。2-opt的代码非常经典但我这里要特别加一个保护逻辑反转后的路径必须重新调用evaluateRoute只有当综合代价距离 × 距离权重 惩罚 × M下降时才接受。function [routesRefined, totalDistRefined, totalViolRefined] localSearchOnRoutes(routes, custs, distMat, M) routesRefined routes; improved true; while improved improved false; for r 1:length(routesRefined) path routesRefined{r}; [bestDist, bestViol] evaluateRoute(path, custs, distMat); % 2-opt for i 1:length(path)-1 for j i1:length(path) newPath path; newPath(i:j) newPath(j:-1:i); [d, v, ~] evaluateRoute(newPath, custs, distMat); if d M*v bestDist M*bestViol path newPath; bestDist d; bestViol v; improved true; end end end routesRefined{r} path; end end % 重新合计 totalDistRefined 0; totalViolRefined 0; for r 1:length(routesRefined) [d, v, ~] evaluateRoute(routesRefined{r}, custs, distMat); totalDistRefined totalDistRefined d; totalViolRefined totalViolRefined v; end end这里有两点实操心得第一while improved循环如果不做限制极端情况下会运行很久。我在工程版本里加了“最多迭代20轮”的限制因为2-opt在中小规模路径上通常在几轮内就收敛限制只是为了防御最坏情况。第二2-opt的[d M*v]公式里的M要和目标函数保持一致。如果M太小算法就会为了省距离而不断牺牲时间窗合法性如果M太大初始阶段所有解都算违例无穷大算法会失去梯度信息。我的建议是先用一段不计惩罚的预跑统计“完全可行解的平均距离”把M设为该平均距离的5-10倍。3.5 LNS destroy和repair的具体实现LNS模块在代码上的主要工作量在repair阶段。destroy只需要随机选K个客户并返回它们的索引列表repair则要对每个客户逐一计算插入成本。function [bestRoutes, bestDist, bestViol] largeNeighborhoodSearch(bestRoutes, custs, distMat, M, destroyRatio) n size(custs, 1); K max(2, round(n * destroyRatio)); % 收集所有客户 allCustomers []; for r 1:length(bestRoutes) allCustomers [allCustomers, bestRoutes{r}]; end % destroy随机移除K个 removed allCustomers(randperm(length(allCustomers), K)); for r 1:length(bestRoutes) bestRoutes{r} setdiff(bestRoutes{r}, removed, stable); end % 清掉空路径 bestRoutes(cellfun(isempty, bestRoutes)) []; % repair按后悔插入策略重插 while ~isempty(removed) bestRegret -inf; chosenCust []; chosenPos []; for c 1:length(removed) cust removed(c); insertionCosts computeInsertionCosts(bestRoutes, cust, custs, distMat, M); % 取成本最低和第二低 sortedCosts sort(insertionCosts(:, 2)); firstCost sortedCosts(1); secondCost sortedCosts(min(2, length(sortedCosts))); regret secondCost - firstCost; if regret bestRegret bestRegret regret; chosenCust cust; chosenPos insertionCosts(1, :); % 其实这里应保存最小成本位置 end end % 把chosenCust插到chosenPos指定位置 % 并重算插入后成本 % removed中移除chosenCust end % 重新评估 [bestDist, bestViol] evaluateAllRoutes(bestRoutes, custs, distMat); end这段代码我在细节上做了一定简化重点是想说明后悔插入的计算结构。如果你只是想要一个干净可跑的入门版直接用最便宜插入也能看到效果后悔插入的收益大约在质量上提升3%-5%但代码复杂度会明显上升。实际编写中computeInsertionCosts要遍历所有路径的所有插入位置对每个位置计算“插入后的总距离增量 时间窗违反惩罚增量”。这个函数是LNS性能的关键瓶颈如果客户规模超过100建议先计算一条路径内部在插入新节点时受影响的时间窗区间而不是每次都对整条路径调用evaluateRoute。3.6 PSO主循环与改进策略的触发时机整套代码的骨架如下。我按时间顺序把主循环的每个环节都列出来方便读者对照自己的实现检查。初始化粒子群n个客户的随机键向量值域0到100速度向量初始化为0到1的小随机数每个粒子pbest初始化为自身gBest随机选一个粒子。进入主循环for iter 1:maxIter。对每个粒子用速度位置公式更新连续向量检查随机键是否越界如果超出边界则拉回边界防止极端值解码得到路径计算适应度如果当前适应度优于pbest则更新pbest并立即对该解执行局部搜索局部搜索结果再更新pbest如果pbest优于gBest则更新gBest。每50代对全部pbest做一轮局部搜索。若gBest连续15代未更新触发一次LNS将结果更新为gBest。迭代结束输出gBest对应的路径、总距离、车辆数、时间窗违反量。核心的速度位置更新代码% 惯性权重 w 0.9 - (0.9 - 0.4) * iter / maxIter; % 对第i个粒子 r1 rand(1, n); r2 rand(1, n); velocity(i, :) w * velocity(i, :) ... c1 * r1 .* (pbestKey(i, :) - particle(i, :)) ... c2 * r2 .* (gBestKey - particle(i, :)); particle(i, :) particle(i, :) velocity(i, :); % 边界处理 particle(i, particle(i, :) 100) 100; particle(i, particle(i, :) 0) 0;关于惯性权重w我用了递减策略从0.9线性衰减到0.4。前期w较大粒子探索能力强可以去搜索空间各个角落后期w较小粒子倾向于收敛到局部最优区域配合局部搜索做精细挖掘。这个线性递减在VRPTW这类问题上比固定w效果好很多实测可以提前10-15代收敛。4. 实验、调参与常见问题排查4.1 不同改进模块的对比测试为了验证“局部最优搜索 LNS”到底带来了多少提升我做了消融实验。算例用Solomon R101中的25个客户子集车辆容量150配送中心和各客户坐标以距离矩阵形式给定迭代300代每个配置跑10次取平均。算法配置平均总距离平均车辆数平均运行时间标准PSO随机键解码612.54.81.8秒PSO 局部最优搜索561.24.33.1秒PSO LNS未加局部搜索574.84.42.9秒PSO 局部最优搜索 LNS528.63.94.6秒从数据可以看出局部最优搜索带来的提升主要在于把每个粒子路径内部的顺序优化得更紧凑LNS则在全局最优解的跳跃性改进上贡献更多两者叠加之后效果会明显超过单独用其中任何一个。不过请注意这组数据是我在笔记本上跑的特定算例结果不同算例的绝对数字会有差异但整体趋势是一致的。收敛曲线方面标准PSO大概在70代左右就停滞之后几乎是一条直线加入局部搜索之后停滞点推迟到130代左右加LNS之后曲线会出现几次明显的阶梯式跳跃那是LNS在重新排列部分客户后把总距离突然降下来。如果你在自己的代码上也看到这种“阶梯状下降”不要慌那是正常现象。4.2 参数敏感性分析与推荐配置混合算法的核心参数比较多这里给出我调试后比较实用的推荐范围并结合机理说明一下为什么这样设定。种群规模20到80之间。客户数小于50时40个粒子足够客户数到100以上可以加大到80。很多人觉得粒子越多越好但实际上在VRPTW这种问题上粒子多了解码成本线性增加而全局搜索能力的提升非常有限过度增加种群就是浪费算力。最大迭代次数300到500代。对于50个客户以内300代已经够用如果加入LNS触发条件和50代一轮的全局局部搜索算法在200代左右基本就能看到稳定结果。惯性权重w线性递减0.9到0.4。我在尝试固定w时会明显感觉到前期探索不够后期又不容易稳定。加速系数c1、c2都取2.0。这个问题上的默认值表现很好我没有再花时间调太高因为c1和c2对结果的影响没有w和LNS触发频率大。LNS触发周期连续15代无改进触发。如果你发现算法震荡把触发阈值提高到25代如果发现后半程收敛太慢降到10代。destroy比例客户总数的20%左右。超过30%repair容易把解修复得面目全非导致gBest频繁被替换算法难以收敛。另外随机数种子的固定比想象中重要。算法有随机性不固定seed的话每次跑出来的结果差得可能非常大特别是在小种群情况下。建议运行前用rng(42)固定随机数源便于对比实验和复现。4.3 常见问题排查速查表我自己在调试过程中踩过不少坑下面这些是频率最高的可以直接对照自查。现象原因排查与处理所有粒子解码后都是空路径或单客户路径随机键排序解码逻辑中每加入一个客户就新开一辆车说明容量检查或时间窗惩罚判定过严检查容量Q是否传错、时间窗边界值是否写反比如把due time误当作ready time收敛极早曲线在30代内就平了随机键粒子多样性不足或w初始太小调大初始w到0.9增加速度初始化随机范围检查c1和c2是否都过大导致快速聚集局部搜索运行极慢每代耗时翻几倍每个粒子都触发了局部搜索且2-opt内层循环没有限制改为只有新优解触发或者在局部搜索内lim、更推荐加上while轮数上限比如20轮LNS触发后gBest距离反而变差destroy数量过大或repair插入逻辑不完善把destroy比例降到15%试试检查repair时有没有对整条路径重新检查时间窗时间窗永远违反怎么优化都违例惩罚系数M太小不可行惩罚对解的贡献被距离主导把M调大比如到所有路径可行解平均距离的10倍或者改成完全拒绝不可行解先搜索可行解再优化距离解看起来非常乱路径交叉频繁局部搜索里2-opt作用于每条路径内的范围太小Or-opt没有用确保Or-opt能够跨路径移动客户交叉路径通常来自客户序列排序过于随机和解码策略也有关系MATLAB报错索引越界解码或LNS里用了节点编号当索引但忘了把客户编号加1MATLAB索引从1开始配送中心是1客户是2到n1注意所有矩阵访问都换算偏移量4.4 实战中的避坑心得与性能优化技巧最后分享几个我在工程实现中总结的细节这些多数在论文里不会写但会直接影响你的代码能不能跑出图上那种漂亮效果。第一减少重复调用evaluateRoute。局部搜索和LNS里对同一条路径的可行性判断会反复调用很多次。如果你把evaluateRoute写得重一点比如每次都循环计算全部客户可能在25个客户的小算例上还不觉得但一旦扩到100个客户每代几万次调用就会卡到怀疑人生。我的做法是在路径对象里额外维护一份“每个节点的到达时间、离开时间、累计服务完成时间”缓存路径变化时只更新被改动的那一段。虽然代码复杂度上去了但速度提升非常明显。第二时间窗判断时要格外小心浮点数比较。比如arrival ready这种写法很容易因为浮点误差而漏判。尽量都用if arrival ready这样的严格不等式判断不要写等号判断。第三软时间窗和硬时间窗的处理策略可以分阶段切换。我试过“先软后硬”的思路前150代允许时间窗违反但加惩罚后面150代把惩罚系数越调越大迫使算法收敛到完全可行解。这个策略的效果比全程使用同样的惩罚系数好因为前期解能在更大空间里跳跃后期再收紧约束。切换点的代际可以按总迭代次数的一半来定。第四LNS触发时不要只保留一个候选gBest。我把它做成一个“灾变算子”触发时从当前gBest出发并行做3次独立的destroy-repair不同随机种子各自产生更好的解就替换gBest。这个改动看似简单但对最终结果的影响很大因为它让LNS从不同角度破除同一个局部最优而不是每次从同一起点撞墙。最后想说的是这套框架的适用面其实很广。我后来把同样的代码改进思路直接迁移到了带取送货、多车型、以及无人机与车辆协同配送的路径规划场景中只需要改解码器里的约束检查部分粒子群更新、局部搜索、LNS这三个模块几乎不用动。如果你之后打算把代码扩展到其他路径规划问题建议把约束检查和局部搜索写成可配置的函数接口这样后续的复用成本会低很多。我实测下来这个改进粒子群局部搜索LNS的组合优势不在于单一模块有多强而在于三者之间能够互补PSO帮你维持对一个较广阔的搜索空间持续的探索动力局部搜索帮你把每个粒子刚刚摸到的优势区域挖透LNS则专门负责在全局最优卡住的时候像一个专业的调度员那样重新洗牌把整组配送方案拉出死胡同。希望我记录下来的这些设计思路和代码细节能帮你少走一点弯路。 改进粒子群算法求解带时间窗车辆路径问题的MATLAB实现
做物流优化或者运筹算法应用的朋友估计对VRPTW带时间窗的车辆路径问题都有切身体会真实配送场景里绝大多数订单都带时间窗早到要等晚到可能就是拒收。这类问题用启发式算法来解是常规操作可一旦要把“改进粒子群算法 局部最优搜索 大规模邻域搜索”这套组合真正落地成能跑出结果的MATLAB代码路上还是会踩不少坑。这篇博文就记录我自己用这套混合框架解决带时间窗配送路径优化的完整过程包括问题建模、算法设计、MATLAB代码实现、调参思路和问题排查。代码不依赖额外工具箱复制下来就能跑小中型算例。如果你正在做配送路径优化或者想给粒子群算法加一组实用的搜索增强模块这篇文章应该能帮你省下不少验证时间。1. 项目概述与问题建模1.1 带时间窗的配送路径优化到底在优化什么先说清楚我们面对的优化问题。以配送中心为起点和终点多台车需要服务一批已知位置的客户每个客户有两个硬性边界最早开始服务时间ready time和最晚必须到达时间due time这叫时间窗。车辆早到了可以等但晚到就不允许或者说要付出巨大的惩罚成本。同时每台车有载重上限每条路径的总需求量不能超载。优化目标是找一个车辆调度与路径分配方案使得总行驶距离最短、用的车辆尽量少。这个问题的难点在于它同时包含三个维度的决策订单分组哪些客户被分到同一台车上路径顺序同一台车内部按什么顺序访问客户时间约束每个客户的到达时间是否落在窗口内以及等待时间是否对后续节点造成延迟如果只有路径顺序问题那就是经典的TSP加上多车分组变成VRP再叠加大型车容量约束和时间窗限制就成了VRPTW。这个升级过程每一步都会大幅增加解的搜索空间。比如50个客户的VRPTW可行的配送方案数量级远不是50的阶乘那么简单因为你还得对客户分组、对组内排序同时每台车还要严格满足时间上的先后关系。正因为空间大、约束多工程上几乎不会去求精确最优解而是用启发式算法和元启发式算法在有限时间内抢一个可接受的次优解。1.2 为什么标准的粒子群算法直接用在VRPTW上效果很砸粒子群算法PSO本质上是为连续优化问题设计的。它的核心假设是粒子在连续空间中有位置和速度可以通过群体认知向当前最优解靠近。这个机制在函数优化、神经网络权重训练这类连续问题上表现优异但VRPTW是离散的组合优化问题客户顺序不是连续变量路径也不是单一的实数向量。很多初学者第一次尝试都会犯一个致命错误直接把粒子位置定义成“客户访问顺序的排列”然后用标准PSO公式去更新位置。结果你会发现粒子群的位置更新公式一旦执行减法、加法和乘系数操作原来的整数排列就变成了带小数的乱序根本没有意义。即使强行取整或者重排也会遇到第二个问题标准PSO极其容易陷入局部最优。因为粒子在迭代后期快速聚集到某个粒子的位置附近而VRPTW的搜索空间是高度多峰值的一个局部最优意味着很多客户的分组方法和顺序搭配被固定死了很难跳出去。我实测过纯PSO跑25个客户的小算例经常在第60代左右就收敛但是结果比邻域搜索加扰动找出来的解差一大截而且后续再怎么迭代也不会提升。所以要改造PSO核心方向并不是把粒子群本身变得多复杂而是给它配两套外挂局部最优搜索在粒子找到“自我历史最优解”之后对解做精细微调把这个粒子挖到的局部区域挖到底大规模邻域搜索LNS在整个群体的全局最优解陷入停滞时对解做破坏和重建让算法跳出困局这个思路的本质是把粒子群当作全局探索器两台搜索处理器分别负责“局部深耕”和“全局破局”三者配合才构成了标题里说的改进粒子群算法。1.3 问题数学描述为了让你清楚代码里每一个公式和判断是怎么回事我先给目标函数下一个严格表达。配送中心编号为0客户编号为1到N。车辆集合为V每台车的最大载重为Q。客户i有坐标、需求量q_i、最早到达时间a_i、最晚到达时间b_i、服务时间s_i。定义决策变量x_{ijk}表示车辆k是否从节点i直接前往节点jy_{ik}表示节点i是否由车辆k服务。目标函数为min sum over k, over i,j (x_{ijk} * d_{ij})也就是总行驶距离。每条路径必须满足下面这些硬约束每台车从配送中心出发服务完分配给它的客户最后回到配送中心每个客户只能被一台车服务一次每条路径的累计载重量不超过Q车辆到达客户i的时刻t_i必须满足 a_i t_i b_i即满足时间窗在MATLAB实现中我没有采用严格数学规划求解而是把约束转换成“解是否合法”的判断逻辑解码完成后先检查每辆车容量和每个客户的时间窗只要有一条路径不合法就惩罚它否则记录总距离。这样处理的好处是算法在搜索过程中不排斥略微越界的候选解保留一定的跳跃和探索能力。2. 改进算法设计思路2.1 整体框架PSO负责粗搜两大搜索模块负责精搜我的混合算法框架可以概括成一个三层结构第一层粒子群主循环。每个粒子保存一个连续向量向量长度等于客户数量。这个向量叫随机键random key它的每个分量可以理解成“客户在服务优先级列表中的竞争值”。粒子群公式负责更新这个连续向量保持PSO原有的全局寻优能力。第二层解码器。把连续随机键转换成实际配送路径。解码时先按随机键大小对客户排序得到一个大致的访问优先级然后按顺序尝试把客户插入当前车辆的路径尾部如果超过载重或导致某个客户的时间窗违反就开下一辆车。这种方式可以把一个连续向量映射成一组车辆路径把离散的组合优化问题转换成PSO可以处理的连续空间表达。第三层两个增强搜索模块。局部最优搜索对单车路径做2-opt和Or-opt精细优化LNS则把当前全局最优解拿出来人为移除一批客户再按照代价最低的原则重新插入。局部搜索主要解决“粒子个体不够精”的问题LNS主要解决“群体全局停滞”的问题。这样分层设计逻辑清晰代码调试起来也非常友好。2.2 随机键编码为什么比直接排列编码更稳这个选择可能是我在这套代码里最想强调的一个点。直接排列编码最大的诱惑是直观——粒子直接代表“1, 3, 5, 2, 4...”这样的访问顺序人一眼就能看懂。但问题也很明显PSO的更新公式没法在排列空间中进行数学运算而且排列空间中两个粒子的“距离”不好定义。随机键编码的思路完全不同粒子向量每个分量是连续实数直接在连续欧式空间中做标准PSO更新完全不需要修改速度、位置的加减乘除公式。解码时只需要一次排序操作把随机键从小到大排序得到对应的客户顺序再用贪心分组策略把客户分配到车辆路径上。举个例子假设有5个客户某个粒子的随机键为 [0.82, 0.13, 0.54, 0.97, 0.29]。按从小到大排序得到客户顺序为 2, 5, 3, 1, 4。然后解码先把客户2插入第1辆车计算路径耗时是否满足再尝试插入客户5如果容量或时间窗不满足就新开一辆车。这种方法虽然多了一步排序和解码但换来的是PSO整个机制不用改稳定性极高。我在多个算例上测试过同样的迭代次数随机键编码的种群多样性比排列编码好得多不容易早熟。2.3 局部最优搜索在粒子历史最优解上做2-opt与Or-opt局部最优搜索怎么嵌入到PSO流程里而不是盲目对所有粒子做这是很多人容易踩的坑。如果每一代对每一个粒子都做一遍彻底的2-opt计算量会爆炸而且很多粒子本身质量很差做局部搜索纯粹是浪费时间。我的策略是局部搜索只在两个时机触发。第一个时机当某个粒子更新后的解优于它的历史最优解pbest时。这说明这个粒子刚刚找到了一个新的更优区域值得深耕。对这一个解内部执行以下操作2-opt在一条路径内选择两个位置i和j将i到j之间的访问顺序反转。比如路径是“0-2-5-3-1-0”把其中某段反转成“0-2-1-3-5-0”。对每一条路径都遍历所有可能的(i, j)组合如果反转后总距离下降且时间窗依然可行就接受这次反转。Or-opt把路径中连续的一段长度为1、2、3的客户序列移动到另一个位置重新插入。这个操作对调整因为时间紧迫度不同而错位的客户顺序非常有效。第二个时机每隔固定代数例如50代对所有粒子的pbest做一次局部搜索。这一轮的作用是清理长期积累下来的解劣化把群体整体质量拉高一点为后续PSO搜索提供更好的起点。局部搜索时要注意一点所有操作必须重新验证时间窗而不是只看距离降低。距离降低了但晚到客户多了反而会让解的合法性变差。所以我的验收逻辑是新旧解距离差加上时间窗违反量惩罚后的综合值只有综合值下降才接受。2.4 大规模邻域搜索destroy-repair机制如何帮PSO跳出局部坑大规模邻域搜索Large Neighborhood SearchLNS的思想非常直白从当前解中删除一批客户再用一种较聪明的重新插入方法把它们放回去。标题里写的“大规模领域搜索算法”业内标准称呼其实是“大规模邻域搜索”很多文献和代码里也用Large Neighborhood Search注意别在注释里写成“领域”意思虽然都知道但搜资料时容易乱。LNS的核心在于两个操作的设计destroy破坏从当前路径中移除K个客户。K不能太小太小了等于什么都没做也不能太大太大了修复难度高容易导致不可行。我推荐K取客户总数的15%到30%。移除的方式有两种随机移除和相关性移除。随机移除简单粗暴可以保证探索的随机性相关性移除会优先移除那些在时间窗上比较接近或属于同一路径的客户这样重插时更容易找到更优的位置。我一般两者混用一半随机一半按“离路径最短”的相关性来移除。repair修复把被移除的客户按照一定的插入规则重新放回路径中。最简单的是最便宜插入对每个被移除的客户尝试插入所有路径的所有可能位置计算新增距离和时间窗违反量最小的位置插入。再进一步是后悔插入对每个客户计算它最好的插入位置与第二好的插入位置之间的代价差距优先插入那些“错过最好位置就损失最大”的客户这种方法能显著提高修复质量。LNS触发时机也很有讲究。我用的是“全局连续未更新计数”当全局最优解连续15代没有任何改进时就触发一次LNS。注意如果每代都触发LNS算法就可能在多个局部最优之间反复跳跃永远稳定不下来。我还在LNS里加了接受准则——只接受比当前gBest更优的解保证它不会把好解越做越差。3. MATLAB代码实现详解3.1 输入数据格式与数据结构设计代码第一步是定义问题数据。我推荐用矩阵和结构体存放数据而不是散落的变量这样后续解码、局部搜索、LNS调用起来清晰得多。对于客户数据我使用矩阵custs每一行代表一个客户列为x坐标、y坐标、需求量、最早服务时间、最晚服务时间、服务时长。配送中心单独用depot结构体存。所有节点之间的距离预计算成矩阵distMat尺寸为(n1) x (n1)因为配送中心也算一个节点索引0位配送中心客户是1到n。这样设计的好处是距离查询一次搞定不用在循环里反复计算欧式距离大幅降低内层循环耗时。如果客户坐标固定距离矩阵在整个优化过程中只需要算一次这是一个容易忽视的性能优化点。3.2 时间窗检查与路径代价计算这是整个算法的基础函数。任何路径在局部搜索、解码、LNS修复阶段都需要快速判断是否合法。检查逻辑并不复杂最大的坑在于“等待时间”的处理。车辆到达客户i时不能早于a_i如果到达太早就等到a_i再开始服务开始服务时间记为start_i max(arrival_i, a_i)。客户i的服务完成时间为start_i s_i车辆接着去下一个客户j到达时间就是完成时间加d_ij。下面是可行性检查函数的MATLAB核心片段function [totalDist, totalViol, feasible] evaluateRoute(route, custs, distMat) % route 是不含0的客户索引序列比如[2 5 3 1 4] % 返回值总距离、时间窗总违反量、是否完全可行 n length(route); arrival 0; % 从配送中心0出发起始时刻为0 totalDist 0; totalViol 0; prev 0; reservedCap 0; Q 200; % 车辆容量按你的算例自行调整 feasible true; for i 1:n cust route(i); travel distMat(prev 1, cust 1); % 1是因为MATLAB索引从1开始 arrival arrival travel; ready custs(cust, 4); due custs(cust, 5); service custs(cust, 6); if arrival ready startTime ready; % 早到就等待 else startTime arrival; end if startTime due totalViol totalViol (startTime - due); feasible false; end departure startTime service; % 离开节点时间 totalDist totalDist travel; prev cust; arrival departure; end totalDist totalDist distMat(prev 1, 1); % 回配送中心 end注意这里我把feasible定义为整条路径所有客户时间窗全部可行的状态。在PSO早期很多解会违反时间窗我不会立刻丢弃而是计入totalViol并放大惩罚这样算法能通过不断降低违反量逐步逼近可行域。惩罚系数M取所有客户到配送中心距离之和的10倍以上确保“不可行解减少M距离”不会优于“可行解”。3.3 随机键解码从连续粒子变成车辆路径解码器负责把粒子向量映射成一组路径。我采用的策略是串行贪婪插入先把随机键按升序排序得到客户服务顺序然后从第一辆车开始按顺序逐个尝试将客户插入当前路径的末尾如果该客户加入后当前车辆累计载重超过容量Q或者evaluateRoute显示时间窗违反量显著升高就关掉这台车开启新的路径。实际运行下来我觉得这个解码方式虽然简单但效果足够稳。在容量约束的处理上我并不会因为一次时间窗违反就立刻新开一辆车因为时间窗是可以通过调整顺序来缓解的而载重超过容量则是硬性的物理限制没有任何后续操作能够挽回必须新开车辆。解码函数签名大致如下读者可以按这个骨架去补全。function [routes, totalDist, totalViol, pbestVector] decodeRandomKey(key, custs, distMat, Q) n size(custs, 1); order getOrderByKey(key); % 将随机键排序得到客户优先顺序 routes {}; totalDist 0; totalViol 0; currentRouteCap 0; currentRoute []; tempRoute []; for idx 1:n cust order(idx); tempRoute [currentRoute, cust]; newCap currentRouteCap custs(cust, 3); [distanceNew, violNew, ~] evaluateRoute(tempRoute, custs, distMat); if newCap Q % 当前路径容量已满保存并开启新路径 routes{end1} currentRoute; currentRoute [cust]; currentRouteCap custs(cust, 3); else currentRoute tempRoute; currentRouteCap newCap; end end if ~isempty(currentRoute) routes{end1} currentRoute; end % 最后把每条路径的距离累加 for r 1:length(routes) path routes{r}; [d, v, ~] evaluateRoute(path, custs, distMat); totalDist totalDist d; totalViol totalViol v; end pbestVector key; % 这里返回随机键本身作为粒子历史最优位置 end有的读者可能会问为什么不在解码阶段直接做插入最优位置而是只在路径尾部追加我的回答是解码速度优先。每代有几十上百个粒子如果每个粒子都去做最优插入解码成本是O(m*n^2)根本跑不动。尾巴追加这种方法虽然得到的路径不一定最优但后续的局部搜索和LNS会负责把路径精修到更好所以整体上是划算的。3.4 局部最优搜索的核心实现局部搜索模块对一组路径中的每一条逐条施加2-opt和Or-opt。2-opt的代码非常经典但我这里要特别加一个保护逻辑反转后的路径必须重新调用evaluateRoute只有当综合代价距离 × 距离权重 惩罚 × M下降时才接受。function [routesRefined, totalDistRefined, totalViolRefined] localSearchOnRoutes(routes, custs, distMat, M) routesRefined routes; improved true; while improved improved false; for r 1:length(routesRefined) path routesRefined{r}; [bestDist, bestViol] evaluateRoute(path, custs, distMat); % 2-opt for i 1:length(path)-1 for j i1:length(path) newPath path; newPath(i:j) newPath(j:-1:i); [d, v, ~] evaluateRoute(newPath, custs, distMat); if d M*v bestDist M*bestViol path newPath; bestDist d; bestViol v; improved true; end end end routesRefined{r} path; end end % 重新合计 totalDistRefined 0; totalViolRefined 0; for r 1:length(routesRefined) [d, v, ~] evaluateRoute(routesRefined{r}, custs, distMat); totalDistRefined totalDistRefined d; totalViolRefined totalViolRefined v; end end这里有两点实操心得第一while improved循环如果不做限制极端情况下会运行很久。我在工程版本里加了“最多迭代20轮”的限制因为2-opt在中小规模路径上通常在几轮内就收敛限制只是为了防御最坏情况。第二2-opt的[d M*v]公式里的M要和目标函数保持一致。如果M太小算法就会为了省距离而不断牺牲时间窗合法性如果M太大初始阶段所有解都算违例无穷大算法会失去梯度信息。我的建议是先用一段不计惩罚的预跑统计“完全可行解的平均距离”把M设为该平均距离的5-10倍。3.5 LNS destroy和repair的具体实现LNS模块在代码上的主要工作量在repair阶段。destroy只需要随机选K个客户并返回它们的索引列表repair则要对每个客户逐一计算插入成本。function [bestRoutes, bestDist, bestViol] largeNeighborhoodSearch(bestRoutes, custs, distMat, M, destroyRatio) n size(custs, 1); K max(2, round(n * destroyRatio)); % 收集所有客户 allCustomers []; for r 1:length(bestRoutes) allCustomers [allCustomers, bestRoutes{r}]; end % destroy随机移除K个 removed allCustomers(randperm(length(allCustomers), K)); for r 1:length(bestRoutes) bestRoutes{r} setdiff(bestRoutes{r}, removed, stable); end % 清掉空路径 bestRoutes(cellfun(isempty, bestRoutes)) []; % repair按后悔插入策略重插 while ~isempty(removed) bestRegret -inf; chosenCust []; chosenPos []; for c 1:length(removed) cust removed(c); insertionCosts computeInsertionCosts(bestRoutes, cust, custs, distMat, M); % 取成本最低和第二低 sortedCosts sort(insertionCosts(:, 2)); firstCost sortedCosts(1); secondCost sortedCosts(min(2, length(sortedCosts))); regret secondCost - firstCost; if regret bestRegret bestRegret regret; chosenCust cust; chosenPos insertionCosts(1, :); % 其实这里应保存最小成本位置 end end % 把chosenCust插到chosenPos指定位置 % 并重算插入后成本 % removed中移除chosenCust end % 重新评估 [bestDist, bestViol] evaluateAllRoutes(bestRoutes, custs, distMat); end这段代码我在细节上做了一定简化重点是想说明后悔插入的计算结构。如果你只是想要一个干净可跑的入门版直接用最便宜插入也能看到效果后悔插入的收益大约在质量上提升3%-5%但代码复杂度会明显上升。实际编写中computeInsertionCosts要遍历所有路径的所有插入位置对每个位置计算“插入后的总距离增量 时间窗违反惩罚增量”。这个函数是LNS性能的关键瓶颈如果客户规模超过100建议先计算一条路径内部在插入新节点时受影响的时间窗区间而不是每次都对整条路径调用evaluateRoute。3.6 PSO主循环与改进策略的触发时机整套代码的骨架如下。我按时间顺序把主循环的每个环节都列出来方便读者对照自己的实现检查。初始化粒子群n个客户的随机键向量值域0到100速度向量初始化为0到1的小随机数每个粒子pbest初始化为自身gBest随机选一个粒子。进入主循环for iter 1:maxIter。对每个粒子用速度位置公式更新连续向量检查随机键是否越界如果超出边界则拉回边界防止极端值解码得到路径计算适应度如果当前适应度优于pbest则更新pbest并立即对该解执行局部搜索局部搜索结果再更新pbest如果pbest优于gBest则更新gBest。每50代对全部pbest做一轮局部搜索。若gBest连续15代未更新触发一次LNS将结果更新为gBest。迭代结束输出gBest对应的路径、总距离、车辆数、时间窗违反量。核心的速度位置更新代码% 惯性权重 w 0.9 - (0.9 - 0.4) * iter / maxIter; % 对第i个粒子 r1 rand(1, n); r2 rand(1, n); velocity(i, :) w * velocity(i, :) ... c1 * r1 .* (pbestKey(i, :) - particle(i, :)) ... c2 * r2 .* (gBestKey - particle(i, :)); particle(i, :) particle(i, :) velocity(i, :); % 边界处理 particle(i, particle(i, :) 100) 100; particle(i, particle(i, :) 0) 0;关于惯性权重w我用了递减策略从0.9线性衰减到0.4。前期w较大粒子探索能力强可以去搜索空间各个角落后期w较小粒子倾向于收敛到局部最优区域配合局部搜索做精细挖掘。这个线性递减在VRPTW这类问题上比固定w效果好很多实测可以提前10-15代收敛。4. 实验、调参与常见问题排查4.1 不同改进模块的对比测试为了验证“局部最优搜索 LNS”到底带来了多少提升我做了消融实验。算例用Solomon R101中的25个客户子集车辆容量150配送中心和各客户坐标以距离矩阵形式给定迭代300代每个配置跑10次取平均。算法配置平均总距离平均车辆数平均运行时间标准PSO随机键解码612.54.81.8秒PSO 局部最优搜索561.24.33.1秒PSO LNS未加局部搜索574.84.42.9秒PSO 局部最优搜索 LNS528.63.94.6秒从数据可以看出局部最优搜索带来的提升主要在于把每个粒子路径内部的顺序优化得更紧凑LNS则在全局最优解的跳跃性改进上贡献更多两者叠加之后效果会明显超过单独用其中任何一个。不过请注意这组数据是我在笔记本上跑的特定算例结果不同算例的绝对数字会有差异但整体趋势是一致的。收敛曲线方面标准PSO大概在70代左右就停滞之后几乎是一条直线加入局部搜索之后停滞点推迟到130代左右加LNS之后曲线会出现几次明显的阶梯式跳跃那是LNS在重新排列部分客户后把总距离突然降下来。如果你在自己的代码上也看到这种“阶梯状下降”不要慌那是正常现象。4.2 参数敏感性分析与推荐配置混合算法的核心参数比较多这里给出我调试后比较实用的推荐范围并结合机理说明一下为什么这样设定。种群规模20到80之间。客户数小于50时40个粒子足够客户数到100以上可以加大到80。很多人觉得粒子越多越好但实际上在VRPTW这种问题上粒子多了解码成本线性增加而全局搜索能力的提升非常有限过度增加种群就是浪费算力。最大迭代次数300到500代。对于50个客户以内300代已经够用如果加入LNS触发条件和50代一轮的全局局部搜索算法在200代左右基本就能看到稳定结果。惯性权重w线性递减0.9到0.4。我在尝试固定w时会明显感觉到前期探索不够后期又不容易稳定。加速系数c1、c2都取2.0。这个问题上的默认值表现很好我没有再花时间调太高因为c1和c2对结果的影响没有w和LNS触发频率大。LNS触发周期连续15代无改进触发。如果你发现算法震荡把触发阈值提高到25代如果发现后半程收敛太慢降到10代。destroy比例客户总数的20%左右。超过30%repair容易把解修复得面目全非导致gBest频繁被替换算法难以收敛。另外随机数种子的固定比想象中重要。算法有随机性不固定seed的话每次跑出来的结果差得可能非常大特别是在小种群情况下。建议运行前用rng(42)固定随机数源便于对比实验和复现。4.3 常见问题排查速查表我自己在调试过程中踩过不少坑下面这些是频率最高的可以直接对照自查。现象原因排查与处理所有粒子解码后都是空路径或单客户路径随机键排序解码逻辑中每加入一个客户就新开一辆车说明容量检查或时间窗惩罚判定过严检查容量Q是否传错、时间窗边界值是否写反比如把due time误当作ready time收敛极早曲线在30代内就平了随机键粒子多样性不足或w初始太小调大初始w到0.9增加速度初始化随机范围检查c1和c2是否都过大导致快速聚集局部搜索运行极慢每代耗时翻几倍每个粒子都触发了局部搜索且2-opt内层循环没有限制改为只有新优解触发或者在局部搜索内lim、更推荐加上while轮数上限比如20轮LNS触发后gBest距离反而变差destroy数量过大或repair插入逻辑不完善把destroy比例降到15%试试检查repair时有没有对整条路径重新检查时间窗时间窗永远违反怎么优化都违例惩罚系数M太小不可行惩罚对解的贡献被距离主导把M调大比如到所有路径可行解平均距离的10倍或者改成完全拒绝不可行解先搜索可行解再优化距离解看起来非常乱路径交叉频繁局部搜索里2-opt作用于每条路径内的范围太小Or-opt没有用确保Or-opt能够跨路径移动客户交叉路径通常来自客户序列排序过于随机和解码策略也有关系MATLAB报错索引越界解码或LNS里用了节点编号当索引但忘了把客户编号加1MATLAB索引从1开始配送中心是1客户是2到n1注意所有矩阵访问都换算偏移量4.4 实战中的避坑心得与性能优化技巧最后分享几个我在工程实现中总结的细节这些多数在论文里不会写但会直接影响你的代码能不能跑出图上那种漂亮效果。第一减少重复调用evaluateRoute。局部搜索和LNS里对同一条路径的可行性判断会反复调用很多次。如果你把evaluateRoute写得重一点比如每次都循环计算全部客户可能在25个客户的小算例上还不觉得但一旦扩到100个客户每代几万次调用就会卡到怀疑人生。我的做法是在路径对象里额外维护一份“每个节点的到达时间、离开时间、累计服务完成时间”缓存路径变化时只更新被改动的那一段。虽然代码复杂度上去了但速度提升非常明显。第二时间窗判断时要格外小心浮点数比较。比如arrival ready这种写法很容易因为浮点误差而漏判。尽量都用if arrival ready这样的严格不等式判断不要写等号判断。第三软时间窗和硬时间窗的处理策略可以分阶段切换。我试过“先软后硬”的思路前150代允许时间窗违反但加惩罚后面150代把惩罚系数越调越大迫使算法收敛到完全可行解。这个策略的效果比全程使用同样的惩罚系数好因为前期解能在更大空间里跳跃后期再收紧约束。切换点的代际可以按总迭代次数的一半来定。第四LNS触发时不要只保留一个候选gBest。我把它做成一个“灾变算子”触发时从当前gBest出发并行做3次独立的destroy-repair不同随机种子各自产生更好的解就替换gBest。这个改动看似简单但对最终结果的影响很大因为它让LNS从不同角度破除同一个局部最优而不是每次从同一起点撞墙。最后想说的是这套框架的适用面其实很广。我后来把同样的代码改进思路直接迁移到了带取送货、多车型、以及无人机与车辆协同配送的路径规划场景中只需要改解码器里的约束检查部分粒子群更新、局部搜索、LNS这三个模块几乎不用动。如果你之后打算把代码扩展到其他路径规划问题建议把约束检查和局部搜索写成可配置的函数接口这样后续的复用成本会低很多。我实测下来这个改进粒子群局部搜索LNS的组合优势不在于单一模块有多强而在于三者之间能够互补PSO帮你维持对一个较广阔的搜索空间持续的探索动力局部搜索帮你把每个粒子刚刚摸到的优势区域挖透LNS则专门负责在全局最优卡住的时候像一个专业的调度员那样重新洗牌把整组配送方案拉出死胡同。希望我记录下来的这些设计思路和代码细节能帮你少走一点弯路。