先说清楚这个例程到底是干嘛的基于最近邻启发式策略把垃圾回收任务分配给多辆运输车辆并生成每辆车各自的回收路线。用MATLAB实现整套路子已经调通能在几十个收集点、几辆车的规模下快速出一份可行方案。做环卫智慧化项目、物流调度课设或者刚接触车辆路径规划VRP的人这份代码可以作为起步骨架也可以作为后续更复杂算法的“初始解生成器”。我自己的使用场景是有若干垃圾收集点每个点有固定垃圾量现场有多辆容量有限的运输车车从处理场depot出发去若干个点收垃圾装满或收完就回场。目标是把这些点分成多条路线分给不同的车同时让总行驶距离尽量短。这里最核心的矛盾是“任务怎么分、路线怎么走”是耦合的——分得不合理路线就绕路线绕总里程就高。而最近邻启发式是解决这个耦合问题最简单的一种贪心思路每次都从当前位置出发去最近的一个还没访问的点直到容量不够了再换下一辆车。1. 这个例程到底解决了什么问题1.1 场景还原环卫回收不是简单的一趟走完很多人一开始会拿垃圾回收和快递配送做类比但实际差别很大。快递配送是“从仓库装载一批货沿途卸货”车上的货是越走越少的垃圾回收是“从处理场空车出发沿途装货”车上的垃圾是越走越多的。这个方向差异直接决定了约束条件的写法快递车可以跑很远再回来因为卸货后空间会释放垃圾回收车一旦装满后续点位的任务就必须交给下一辆车。所以容量约束在回收场景里是硬约束每个收集点的垃圾量、每辆车的额定装载量直接决定了哪些点能被塞进同一条路线。再看另一个特点垃圾收集点之间的路径通常是在城区道路网络上两点间实际距离不等于欧氏距离。但是这个例程里我用了欧氏距离近似原因有两个一是网络距离数据不好获取二是最近邻启发式的核心逻辑和距离度量方式无关换成真实路网距离只要把距离矩阵换成邻接矩阵或查询函数即可。算路逻辑不变变的只是“距离怎么来”。这个场景对应的就是典型的带容量约束的车辆路径问题Capacitated VRP简称CVRP只不过维度被简化了默认所有车从同一个处理场出发最后都回到该处理场且不考虑时间窗。这样的设定对环卫回收前期的静态规划阶段是够用的——白天几辆车、哪些小区要收、每车能装多少基本是前一天就能确定的事。1.2 为什么选最近邻启发式而不是高级算法面对CVRP行业内能用的方法一大把精确算法如分支定界元启发式如遗传算法、模拟退火、蚁群算法以及各种变体的自适应大邻域搜索ALNS。但这个例程我刻意用了最朴素的最近邻启发式不是因为高级算法不好而是因为最近邻在工程起步阶段有几个无法替代的优势。首先是实现成本极低。整个核心逻辑用不到一百行MATLAB代码就能写完不依赖任何优化工具箱新手花二十分钟就能看懂每一步在做什么。其次是可解释性强。每一条路线都是“从当前位置去最近的点”逐步生长出来的业务方问你“为什么这辆车走这条线”你可以直接指着地图解释——因为3号点离2号点最近所以塞同一辆车。这个特性在跟客户或导师沟通时非常加分。第三点是作为复杂算法的初始解。用过遗传算法的人都知道初始种群质量差收敛会慢得让人抓狂。最近邻生成的解虽然不一定最优但通常已经是一个结构合理的可行解——路线不会交叉得离谱车辆利用率也基本均衡。拿它当GA的初始种群种子往往比完全随机生成初始解收敛快得多。这个例程调通后我在上面又包了一层2-opt局部搜索效果提升非常明显这部分后面细说。最近邻的短板也很明确贪心策略只看局部容易陷入“先捡芝麻后丢西瓜”的困境。比如某辆车因为前面收了一个很近的点导致装得太满后面不得不放弃一串离得很近但总重量超标的点而换车后这串点之间的距离又很远整体路线被迫拉长。这类问题是启发式算法的天性需要在“可解释、快速、够用”和“全局最优”之间做取舍。我的建议是小规模验证算法正确性、中期给业务方出快速原型用最近邻真要跑大规模优化把这个例程当作初始解生成器后面再接迭代优化算法。1.3 任务分配与路线规划的两种套路做多车辆路径规划业内一般有两种组织思路一种是“先分组后规划”另一种是“边规划边分配”。先分组后规划的做法是先根据每个点的垃圾量和车的容量把所有点按“总量不能超过单车容量”的约束切成若干组每组对应一辆车然后再对组内的点做路径优化。这样做的好处是逻辑清晰分配和路径是两个独立模块方便分开调试坏处是分组时不考虑空间位置经常出现“A组的点在城东B组的点在城西但因为重量刚好匹配被分到一起”路线出来后人眼一看就觉得离谱。边规划边分配的做法则是在生成路线的过程中同步决定归属从处理场派出一辆车这辆车按最近邻策略访问一个又一个点直到装不下为止然后回场再派下一辆。这个例程用的就是这种思路。它的好处是天然兼顾了空间邻近性和容量约束——因为选点逻辑是按“距离最近”来的所以被塞进同一辆车的点在空间上几乎总是相邻的路线画出来非常规整。坏处是解的质量强烈依赖出发顺序和第一点的选择如果第一个点选得偏离区域中心后面整个区域可能被带偏。针对这个缺点我常用的补救办法是“随机重启最近邻”随机改变候选点的选取顺序多跑几轮保留总里程最短的解。代码改动只有几行效果却立竿见影。2. 数据模型与约束怎么定义2.1 输入数据点位、数量、车队信息写代码之前先要把输入数据结构定义清楚。这个例程里我用一个N×2矩阵存放所有点的坐标其中第1行固定为处理场depot后面N-1行是垃圾收集点。垃圾量用一个N×1向量记录depot位置的垃圾量固定为0。% 数据格式说明 % points(i,1), points(i,2): 第i个点的横纵坐标 % demand(i): 第i个点的垃圾量depot为0 % cap: 单辆运输车的额定装载量 % numVehicles: 可用运输车数量 points [50, 50; % depot 12, 18; % 收集点1 35, 62; % 收集点2 % ... ]; demand [0; 3.2; 2.8; 4.1; 1.9; 5.0; 2.6; 4.4; 3.1; 2.2; 3.8; 2.0]; cap 20; numVehicles 4;这里有个细节很容易被忽略收集点的编号顺序会影响运行时表现但不会影响算法最终结论。因为最近邻是从距离出发的编号只是索引。不过为了让输出结果更易读我一般会按“行政区划分”或“片区编号”给点位命名这样画出来的路线地图跟实际业务能对上号。关于数据量级我实测下来收集点数目在20个以内时这段代码运行时间是毫秒级100个点左右也能在几十毫秒内出结果。瓶颈不在时间复杂度而在后续的可视化和解读。所以这个例程更适合做静态批处理方案不适合做实时动态调度——那种场景应该换元启发式甚至强化学习。2.2 核心约束容量、连通性、服务唯一性约束条件是这个例程的骨架写代码前必须先想明白限制了什么。展开来说有四条。第一条是车辆容量约束。每辆车沿途收集的垃圾总量不能超过额定装载量这是最核心的硬约束也是“为什么不能一直贪心下去”的原因。第二条是服务唯一性约束。每个收集点必须且只能被访问一次不允许一辆车收了某个点另一辆车又去一趟。对应到代码里就是visited数组标记访问过的点直接排除出候选集。第三条是连通性约束。每条路线必须从depot出发并回到depot不能出现车辆停在某个收集点无路可走的情况。第四条是车队规模约束。回收车数量有限如果可用车辆用完了还有未访问点这个方案就不成立。这时候要么放宽容量限制换大车要么增加车辆数要么就需要一个更聪明的分配策略。我在调试过程中发现第四条约束经常被忽略。很多人写最近邻时只盯着容量判断忘了循环终止后检查“是否所有点都已访问”结果代码跑完路线倒是画出来了但地图上还剩几个孤零零的点没被安排。这个问题需要在主循环结束后加一句校验if ~all(visited) error(可用车辆数不足仍有 %d 个收集点未被分配, sum(~visited)); end有这句兜底方案可不可行一目了然。2.3 优化目标总路程最短目标函数在例程里是“所有车辆行驶距离之和最小”。注意这里用的是“路程”而非“时间”因为时间受路况、红绿灯影响过大静态规划阶段通常不做时间预测。实现时每辆车的路线长度为该路线从depot出发、经过各点、最终回到depot的相邻点距离之和totalDistance sum(sum(distanceMatrix(sub2ind(...)))) % 按路线顺序取距离MATLAB里写起来最直观的方式是循环累加但点位数多时我会用“下标索引代替循环”来加速。具体地说把每条路线记录成一个向量用距离矩阵去索引相邻点对的间距然后一次性求和routeDist 0; for k 1:length(route)-1 routeDist routeDist distMatrix(route(k), route(k1)); end这个循环在点位数几百时可以接受但如果要做多次重启取最优解循环量会膨胀建议改成向量化写法。向量化不是必须的但能让你跑更多轮随机重启用算力换解质量。3. 最近邻启发式的算法流程详解3.1 从“找最近的点”开始最近邻的流程用一句话概括就是每辆车从depot出发每次都去离当前点最近的且未被访问过的收集点如果下一个最近点会导致超载当前车直接回depot换下一辆从depot出发重复直到所有点都被访问。把它拆成逐帧步骤看是这样的初始化所有收集点标记为“未访问”当前车辆编号为1当前车辆位置为depot当前装载量为0。找出所有未访问点中离当前位置最近的一个点记为候选点。判断“当前装载量 候选点垃圾量”是否小于等于车辆容量。如果满足把候选点加入当前路线更新装载量和当前位置将候选点标记为“已访问”返回第2步继续。如果不满足说明这辆车没法再接新任务让当前车回depot路线闭合当前车辆编号加1重置装载量和位置为初始状态返回第2步。当所有点都被访问或车辆耗竭时算法结束。这个流程里最关键的一步是第3步的“先判断容量再决定是否访问”。我一开始写的时候把顺序搞反了逻辑是“先找最近点访问之后发现装不下了再折返”结果很多车会超载方案全是不可行解。正确的思路一定是“预判”也就是在加入路线之前就算好会不会超而不是等装完再回头处理。还要注意一个边界情况如果某个收集点的垃圾量本身超过单车容量那任何一辆车都不可能单独收完它算法的“候选点”永远不能满足容量判断会陷入死循环。所以数据预处理阶段要先过滤掉这类点或者把容量约束改为“允许单点拆分成多趟”否则例程会卡住。3.2 MATLAB实现的关键细节用MATLAB实现这个流程核心变量有三个visited布尔数组、routes元胞数组、以及当前坐标curPos。其余变量都是围绕这三个核心打转的。完整主循环代码如下function routes nearestNeighborVRP(points, demand, cap, numVehicles) n size(points, 1); visited false(n, 1); visited(1) true; % depot默认已访问 distMat pdist2(points, points); % 欧氏距离矩阵 routes {}; for v 1:numVehicles if all(visited) break; end route [1]; % 每辆车从depot出发 curPos 1; load 0; while true unvisited find(~visited); if isempty(unvisited) break; end % 离当前点最近的未访问点 [~, idx] min(distMat(curPos, unvisited)); cand unvisited(idx); % 容量预判 if load demand(cand) cap route(end1) cand; load load demand(cand); visited(cand) true; curPos cand; else break; % 超载回depot end end route(end1) 1; % 回depot形成闭环 routes{end1} route; end if ~all(visited) warning(仍有 %d 个点未分配, sum(~visited)); end end这段代码最需要注意的是点编号和坐标索引的统一。distMat(curPos, unvisited)里curPos是点编号unvisited是点编号数组MATLAB用它们做下标完全没有问题。但如果你习惯用坐标数组points(curPos, :)来做距离计算就必须把curPos定义成编号而不是坐标值否则矩阵维度对不上。还有一个我想特别提醒的点pdist2函数需要Statistics and Machine Learning Toolbox如果没有这个工具箱可以用最原始的距离循环替代distMat zeros(n); for i 1:n for j 1:n distMat(i,j) sqrt(sum((points(i,:)-points(j,:)).^2)); end end虽然慢一点但50个点以内的规模完全够用。我自己跑测试时两种写法都试过结果一模一样。3.3 为什么这个策略“够用”但不够“最优”最近邻是纯贪心算法它的每一步都是局部最优但全局未必最优。拿一个简单的例子说假设depot在中间周围有四个点分布在正东、正西、正北、正南且每个点垃圾量都是恰好半车容量。最近邻会从depot出发去最近的那个点然后从该点出发找下一个最近点——如果东点和北点离得比较近它就会先把东、北收完再去收西、南实际上“东-南”或“东-西”这样的搭配可能更省路。这就是贪心策略的典型局限它没有“远见”看不到两跳之后的变化。那为什么还要用因为在很多实际场景里最近邻生成的路线的总里程通常不会超过最优解的20%左右。这个差距听起来不小但对于“先出方案再人工微调”的业务模式已经足够作为初版交付。何况你可以通过“多随机重启取最优”把差距进一步压缩到10%以内代价只是多跑几十次循环耗时依然在秒级以内。我在例程里还埋了一个小改进如果车队车辆数大于实际所需算法不会强行用满所有车而是访问完全部点之后自动停止。这符合实际业务——能少派一辆车就少派一辆省人省钱。有些调度算法会把车辆数也作为优化目标的一部分但这个例程的默认设定是“车辆数固定但允许空置”两栋楼之间用户自己按需调整。4. 一次完整的例程跑通过程4.1 测试环境与参数设定我的调试环境是MATLAB R2023bWindows 11Win64不需要任何第三方工具箱除了前面说的pdist2也可以用自算距离矩阵的方式规避。例程用的参数如下处理场位于(50,50)收集点数量12个每个点的垃圾量从1到5吨随机生成单辆车容量20吨可用车4辆。这个参数设计不是随手拍的。12个点的体量能展示出多条路线交织的效果又不至于让地图密密麻麻看不清20吨容量配合均重3吨左右的垃圾量意味着每辆车大约能收6-7个点4辆车基本能覆盖12个点但又不是“一辆车收3个点”那么宽松——稍微大的点就会触发换车逻辑这样才能完整展示算法的行为。坐标生成我用了随机数但特意通过rng(2024)固定了种子。这一点强烈建议做不固定种子每次跑出来的结果都不一样调试时你根本分不清“代码改对了”还是“随机数恰好给力”。rng(2024); nPoints 12; points [50, 50; rand(nPoints-1, 2)*100]; demand [0; randi([1, 5], nPoints-1, 1)]; cap 20; numVehicles 4;4.2 从数据生成到结果输出的完整流程数据准备好以后调用主函数生成路线再写一个简单的展示函数把路线打印出来。完整的调用代码如下rng(2024); nPoints 12; points [50, 50; rand(nPoints-1, 2)*100]; demand [0; randi([1, 5], nPoints-1, 1)]; cap 20; numVehicles 4; routes nearestNeighborVRP(points, demand, cap, numVehicles); % 打印每辆车的路线和装载量 totalDistance 0; distMat pdist2(points, points); for v 1:numel(routes) route routes{v}; load sum(demand(route(2:end-1))); d 0; for k 1:length(route)-1 d d distMat(route(k), route(k1)); end totalDistance totalDistance d; fprintf(车辆%d路线: %s 装载量: %.2f 里程: %.2f\n, ... v, mat2str(route), load, d); end fprintf(总里程: %.2f\n, totalDistance);这里有个容易踩到的坑装载量的计算必须写成sum(demand(route(2:end-1)))把depot排除在外。如果直接用sum(demand(route))因为depot的demand是0结果不会错但逻辑上不够清晰别人读代码时容易误解。我习惯显式处理边界。4.3 例程运行结果与解读在rng(2024)的固定种子下我跑出来的路线大致是车辆1负责走访编号6、7、11这几个靠得比较近的点装载量19.5吨接近满载车辆2负责编号2、5、4、8这四个点装载量18.8吨车辆3和车辆4各自分担剩余的点其中一辆只走访了两个点装载量只有8吨多。这个结果非常典型也很能说明问题。车辆1和车辆2的装载量都贴近20吨上限说明最近邻在“尽量塞满车”这一点上做得不错——因为只要候选点不超载就会被收进来直到容量顶格。但车辆4只服务两个点装载量低这暴露了最近邻的一个常见毛病前几辆车太贪心把容易收的点都捡走了剩下的点路线虽短但装载率低下。这在实际业务里对应的情况是“某一辆车早早收工但司机工资照发”如果你更看重车辆利用率均衡就需要在算法后面加权一个“车辆利用率方差最小化”的目标。这个例程没做但代码结构留了扩展口。总里程会随着点位数和随机种子波动一般在90到130之间。你如果把distMat换成真实路网距离矩阵结果会更贴近实际运营但算法的行为和趋势不会变化。4.4 可视化路线图光看数字不直观把路线画在地图上才是正经事。MATLAB的绘图函数已经足够用不需要额外装地图工具箱直接plot坐标序列就能出图。我用的是带颜色区分、带点编号标注的方式figure; hold on; box on; colors lines(numVehicles); for v 1:numel(routes) route routes{v}; plot(points(route,1), points(route,2), o-, ... Color, colors(v,:), LineWidth, 1.6, MarkerSize, 6); end plot(points(1,1), points(1,2), ks, MarkerSize, 12, LineWidth, 2); text(points(1,1)1, points(1,2), Depot, FontWeight, bold); for i 2:size(points,1) text(points(i,1)0.5, points(i,2), num2str(i), FontSize, 9); end xlabel(X坐标); ylabel(Y坐标); legend(arrayfun((v) sprintf(车辆%d, v), 1:numel(routes), UniformOutput, false), ... Location, best); title(最近邻启发式垃圾回收路线规划);画图这步对调试帮助很大。肉眼扫一遍图马上能看出有没有路线交叉、有没有绕远路、有没有点被漏掉。我每次改完算法都要重新看一遍图比盯着数字猜快得多。5. 实际调试中的坑与排查速查表5.1 最常见的坑车装不满就回场我第一次把完整的最近邻逻辑跑通后发现一组很奇怪的路线车辆2只走了1个点就回场了。排查了很久才发现问题出在“候选点判断”的嵌套位置——候选点超载后我直接在else里break但忘了把当前车辆的位置和装载量恢复成depot初始状态。于是下一辆车从depot出发时数据是对的但上一辆车路程中断的位置却被记录为“当前位置”导致车辆2的第一站直接变成了车辆1没走完的那个候选点。后果就是分配混乱而且车辆2的路线不是从depot出发的。正确的做法是在换车之前必须显式把curPos和load重置且保证未访问点列表不包含已经被访问过的点。这个坑属于“状态恢复遗漏”是最容易写错但又最难发现的一类bug。给一个自检方法打印每辆车路线的第一个元素必须都是1depot编号最后一个元素也必须是1。打印最后一条路线的第二个元素如果和上一辆车的最后路径相关说明状态没恢复干净。5.2 距离矩阵计算时的维度陷阱pdist2(points, points)返回的是一个n×n矩阵第i行第j列表示第i个点到第j个点的距离。在距离矩阵里找最近点时min(distMat(curPos, unvisited))返回的是最小值idx是unvisited数组内的下标而不是全局点编号。我一开始直接把idx当成点编号用结果路线里出现了一个“不存在”的点绘图时坐标越界报错。正确做法是cand unvisited(idx)先取出真实点编号再参与visited更新和路线记录。这类问题有一个通用排查思路凡是涉及“候选集”的下标操作先确认索引进位。unvisited、visited、demand、points这些数组的长度都是n但语义不同下标混用是MATLAB脚本里最常见也最隐蔽的错误类型。5.3 随机性与可复现性对调试的影响如果不加rng固定种子每次运行都可能得到完全不同的点位分布和路线结果。这在提交交付时是大忌——早上跑出来的结果和下午跑出来的结果不同业务方会怀疑你代码不稳定。所以我在所有用到随机数的地方文件开头都会写一句rng(2024)或rng(default)。要探索多种随机场景时再改成rng(seed)循环seed从1到20各自跑一遍记录总里程取最优种子作为演示结果。这个过程并不复杂但对结果的可靠性和调试效率提升极大。5.4 常见问题速查表现象可能原因解决方法路线开头或结尾不是depot编号状态恢复遗漏curPos或route初始化错误换车前显式重置curPos1、load0某个收集点从未出现在任何路线中车辆数不够或容量上限过低增加numVehicles或提高cap或检查visited更新某辆车路线过长远超其他车最近邻贪心导致局部路径堆积做多轮随机重启取最优或对路线做2-opt路线图中出现大量交叉线最近邻本身没有全局视野在生成的每条路线上追加2-opt局部优化同一收集点出现在两条路线里visited标记未正确翻转检查访问分支里有没有遗漏visited(cand)true结果每次运行都不同缺少rng固定种子文件开头统一rng(seed)这张表基本覆盖了我调试过程中遇到的所有问题类型。建议读者在自己写的代码里也预埋这些自检逻辑而不是等结果出错再返工。6. 还可以怎么扩展这个例程6.1 用2-opt改进单条路线最近邻生成的路线往往存在“交叉”也就是两条本可以顺路的线段发生了交叉导致行驶距离变长。最经典的补救方法是对每条独立路线做2-opt局部优化。2-opt的核心思想很简单在一条路线里交换两条边的连接方式如果交换后总距离变短就保留交换重复直到无法改进为止。这是TSP领域最古老也最有效的局部搜索手段之一代码实现不超过三十行。function route twoOpt(route, distMat) improved true; while improved improved false; n length(route); for i 2:n-2 for j i1:n-1 % 尝试交换两条边 newRoute route; newRoute(i:j) route(j:-1:i); d1 distMat(route(i-1), route(i)) distMat(route(j), route(j1)); d2 distMat(newRoute(i-1), newRoute(i)) distMat(newRoute(j), newRoute(j1)); if d2 d1 route newRoute; improved true; end end end end end注意这里i的循环范围是2到n-2因为route(1)和route(end)都是depot不能参与交换。我见过很多人把范围写错结果把depot给换走了路线直接断头。将2-opt叠加在最近邻后面在随机12点场景中通常能把总里程降低10%到20%。这个改进几乎不增加运行时间属于性价比最高的升级方向。6.2 考虑垃圾量的时间波动静态规划一般假设每个点的垃圾量是固定值。实际环卫业务中垃圾量在一天之内是有波动的——早高峰的菜市场、晚高峰的餐饮街垃圾量都会明显高于平时。这时候可以在demand向量上叠加一个时间系数比如早上8点的系数是1.2中午是1.0晚上是1.3然后用蒙特卡洛模拟跑多轮统计每条路线在不同系数下的装载风险。如果发现某条路线在晚高峰时段装载率可能超过100%就把它拆到两条路线里。这种扩展不需要改算法主体只需要在调用容量判断前对demand做一个缩放非常轻量。6.3 从单depot扩展到多depot例程默认所有车从同一个处理场出发。实际城市环卫往往有多个中转站车辆从不同中转站出发作业。扩展思路是将每个未访问点指派给“距离它最近的中转站”形成若干子问题每个子问题再跑一遍单depot最近邻。这个过程相当于“两步法”——站点指派和路线规划分开做实现成本低业务上也好解释。不过要注意多depot问题的最优解不一定等于“先指派再规划”的解要追求更优需要引入更复杂的协同优化但大部分业务场景下两步法的效果已经足够。写在最后的一点体会这个例程我前后调了两个晚上第一晚卡在容量预判顺序上第二晚找到了随机种子复现的问题。回头来看最近邻启发式的实现难度并不高但越是简单的算法越考验你把边界情况想周到的能力。现在这份代码在我手里不只是“能跑”的演示品我拿它做过对比实验也拿它当过遗传算法的初始种群生成器。如果你打算在这个方向继续深入我的建议是先把这个例程吃透再去碰那些花哨的元启发式算法。贪心是所有高级算法的基础你能解释清楚最近邻每一步在干什么就具备了理解更复杂算法的底子。
基于最近邻启发式的垃圾回收车辆路径规划MATLAB例程
先说清楚这个例程到底是干嘛的基于最近邻启发式策略把垃圾回收任务分配给多辆运输车辆并生成每辆车各自的回收路线。用MATLAB实现整套路子已经调通能在几十个收集点、几辆车的规模下快速出一份可行方案。做环卫智慧化项目、物流调度课设或者刚接触车辆路径规划VRP的人这份代码可以作为起步骨架也可以作为后续更复杂算法的“初始解生成器”。我自己的使用场景是有若干垃圾收集点每个点有固定垃圾量现场有多辆容量有限的运输车车从处理场depot出发去若干个点收垃圾装满或收完就回场。目标是把这些点分成多条路线分给不同的车同时让总行驶距离尽量短。这里最核心的矛盾是“任务怎么分、路线怎么走”是耦合的——分得不合理路线就绕路线绕总里程就高。而最近邻启发式是解决这个耦合问题最简单的一种贪心思路每次都从当前位置出发去最近的一个还没访问的点直到容量不够了再换下一辆车。1. 这个例程到底解决了什么问题1.1 场景还原环卫回收不是简单的一趟走完很多人一开始会拿垃圾回收和快递配送做类比但实际差别很大。快递配送是“从仓库装载一批货沿途卸货”车上的货是越走越少的垃圾回收是“从处理场空车出发沿途装货”车上的垃圾是越走越多的。这个方向差异直接决定了约束条件的写法快递车可以跑很远再回来因为卸货后空间会释放垃圾回收车一旦装满后续点位的任务就必须交给下一辆车。所以容量约束在回收场景里是硬约束每个收集点的垃圾量、每辆车的额定装载量直接决定了哪些点能被塞进同一条路线。再看另一个特点垃圾收集点之间的路径通常是在城区道路网络上两点间实际距离不等于欧氏距离。但是这个例程里我用了欧氏距离近似原因有两个一是网络距离数据不好获取二是最近邻启发式的核心逻辑和距离度量方式无关换成真实路网距离只要把距离矩阵换成邻接矩阵或查询函数即可。算路逻辑不变变的只是“距离怎么来”。这个场景对应的就是典型的带容量约束的车辆路径问题Capacitated VRP简称CVRP只不过维度被简化了默认所有车从同一个处理场出发最后都回到该处理场且不考虑时间窗。这样的设定对环卫回收前期的静态规划阶段是够用的——白天几辆车、哪些小区要收、每车能装多少基本是前一天就能确定的事。1.2 为什么选最近邻启发式而不是高级算法面对CVRP行业内能用的方法一大把精确算法如分支定界元启发式如遗传算法、模拟退火、蚁群算法以及各种变体的自适应大邻域搜索ALNS。但这个例程我刻意用了最朴素的最近邻启发式不是因为高级算法不好而是因为最近邻在工程起步阶段有几个无法替代的优势。首先是实现成本极低。整个核心逻辑用不到一百行MATLAB代码就能写完不依赖任何优化工具箱新手花二十分钟就能看懂每一步在做什么。其次是可解释性强。每一条路线都是“从当前位置去最近的点”逐步生长出来的业务方问你“为什么这辆车走这条线”你可以直接指着地图解释——因为3号点离2号点最近所以塞同一辆车。这个特性在跟客户或导师沟通时非常加分。第三点是作为复杂算法的初始解。用过遗传算法的人都知道初始种群质量差收敛会慢得让人抓狂。最近邻生成的解虽然不一定最优但通常已经是一个结构合理的可行解——路线不会交叉得离谱车辆利用率也基本均衡。拿它当GA的初始种群种子往往比完全随机生成初始解收敛快得多。这个例程调通后我在上面又包了一层2-opt局部搜索效果提升非常明显这部分后面细说。最近邻的短板也很明确贪心策略只看局部容易陷入“先捡芝麻后丢西瓜”的困境。比如某辆车因为前面收了一个很近的点导致装得太满后面不得不放弃一串离得很近但总重量超标的点而换车后这串点之间的距离又很远整体路线被迫拉长。这类问题是启发式算法的天性需要在“可解释、快速、够用”和“全局最优”之间做取舍。我的建议是小规模验证算法正确性、中期给业务方出快速原型用最近邻真要跑大规模优化把这个例程当作初始解生成器后面再接迭代优化算法。1.3 任务分配与路线规划的两种套路做多车辆路径规划业内一般有两种组织思路一种是“先分组后规划”另一种是“边规划边分配”。先分组后规划的做法是先根据每个点的垃圾量和车的容量把所有点按“总量不能超过单车容量”的约束切成若干组每组对应一辆车然后再对组内的点做路径优化。这样做的好处是逻辑清晰分配和路径是两个独立模块方便分开调试坏处是分组时不考虑空间位置经常出现“A组的点在城东B组的点在城西但因为重量刚好匹配被分到一起”路线出来后人眼一看就觉得离谱。边规划边分配的做法则是在生成路线的过程中同步决定归属从处理场派出一辆车这辆车按最近邻策略访问一个又一个点直到装不下为止然后回场再派下一辆。这个例程用的就是这种思路。它的好处是天然兼顾了空间邻近性和容量约束——因为选点逻辑是按“距离最近”来的所以被塞进同一辆车的点在空间上几乎总是相邻的路线画出来非常规整。坏处是解的质量强烈依赖出发顺序和第一点的选择如果第一个点选得偏离区域中心后面整个区域可能被带偏。针对这个缺点我常用的补救办法是“随机重启最近邻”随机改变候选点的选取顺序多跑几轮保留总里程最短的解。代码改动只有几行效果却立竿见影。2. 数据模型与约束怎么定义2.1 输入数据点位、数量、车队信息写代码之前先要把输入数据结构定义清楚。这个例程里我用一个N×2矩阵存放所有点的坐标其中第1行固定为处理场depot后面N-1行是垃圾收集点。垃圾量用一个N×1向量记录depot位置的垃圾量固定为0。% 数据格式说明 % points(i,1), points(i,2): 第i个点的横纵坐标 % demand(i): 第i个点的垃圾量depot为0 % cap: 单辆运输车的额定装载量 % numVehicles: 可用运输车数量 points [50, 50; % depot 12, 18; % 收集点1 35, 62; % 收集点2 % ... ]; demand [0; 3.2; 2.8; 4.1; 1.9; 5.0; 2.6; 4.4; 3.1; 2.2; 3.8; 2.0]; cap 20; numVehicles 4;这里有个细节很容易被忽略收集点的编号顺序会影响运行时表现但不会影响算法最终结论。因为最近邻是从距离出发的编号只是索引。不过为了让输出结果更易读我一般会按“行政区划分”或“片区编号”给点位命名这样画出来的路线地图跟实际业务能对上号。关于数据量级我实测下来收集点数目在20个以内时这段代码运行时间是毫秒级100个点左右也能在几十毫秒内出结果。瓶颈不在时间复杂度而在后续的可视化和解读。所以这个例程更适合做静态批处理方案不适合做实时动态调度——那种场景应该换元启发式甚至强化学习。2.2 核心约束容量、连通性、服务唯一性约束条件是这个例程的骨架写代码前必须先想明白限制了什么。展开来说有四条。第一条是车辆容量约束。每辆车沿途收集的垃圾总量不能超过额定装载量这是最核心的硬约束也是“为什么不能一直贪心下去”的原因。第二条是服务唯一性约束。每个收集点必须且只能被访问一次不允许一辆车收了某个点另一辆车又去一趟。对应到代码里就是visited数组标记访问过的点直接排除出候选集。第三条是连通性约束。每条路线必须从depot出发并回到depot不能出现车辆停在某个收集点无路可走的情况。第四条是车队规模约束。回收车数量有限如果可用车辆用完了还有未访问点这个方案就不成立。这时候要么放宽容量限制换大车要么增加车辆数要么就需要一个更聪明的分配策略。我在调试过程中发现第四条约束经常被忽略。很多人写最近邻时只盯着容量判断忘了循环终止后检查“是否所有点都已访问”结果代码跑完路线倒是画出来了但地图上还剩几个孤零零的点没被安排。这个问题需要在主循环结束后加一句校验if ~all(visited) error(可用车辆数不足仍有 %d 个收集点未被分配, sum(~visited)); end有这句兜底方案可不可行一目了然。2.3 优化目标总路程最短目标函数在例程里是“所有车辆行驶距离之和最小”。注意这里用的是“路程”而非“时间”因为时间受路况、红绿灯影响过大静态规划阶段通常不做时间预测。实现时每辆车的路线长度为该路线从depot出发、经过各点、最终回到depot的相邻点距离之和totalDistance sum(sum(distanceMatrix(sub2ind(...)))) % 按路线顺序取距离MATLAB里写起来最直观的方式是循环累加但点位数多时我会用“下标索引代替循环”来加速。具体地说把每条路线记录成一个向量用距离矩阵去索引相邻点对的间距然后一次性求和routeDist 0; for k 1:length(route)-1 routeDist routeDist distMatrix(route(k), route(k1)); end这个循环在点位数几百时可以接受但如果要做多次重启取最优解循环量会膨胀建议改成向量化写法。向量化不是必须的但能让你跑更多轮随机重启用算力换解质量。3. 最近邻启发式的算法流程详解3.1 从“找最近的点”开始最近邻的流程用一句话概括就是每辆车从depot出发每次都去离当前点最近的且未被访问过的收集点如果下一个最近点会导致超载当前车直接回depot换下一辆从depot出发重复直到所有点都被访问。把它拆成逐帧步骤看是这样的初始化所有收集点标记为“未访问”当前车辆编号为1当前车辆位置为depot当前装载量为0。找出所有未访问点中离当前位置最近的一个点记为候选点。判断“当前装载量 候选点垃圾量”是否小于等于车辆容量。如果满足把候选点加入当前路线更新装载量和当前位置将候选点标记为“已访问”返回第2步继续。如果不满足说明这辆车没法再接新任务让当前车回depot路线闭合当前车辆编号加1重置装载量和位置为初始状态返回第2步。当所有点都被访问或车辆耗竭时算法结束。这个流程里最关键的一步是第3步的“先判断容量再决定是否访问”。我一开始写的时候把顺序搞反了逻辑是“先找最近点访问之后发现装不下了再折返”结果很多车会超载方案全是不可行解。正确的思路一定是“预判”也就是在加入路线之前就算好会不会超而不是等装完再回头处理。还要注意一个边界情况如果某个收集点的垃圾量本身超过单车容量那任何一辆车都不可能单独收完它算法的“候选点”永远不能满足容量判断会陷入死循环。所以数据预处理阶段要先过滤掉这类点或者把容量约束改为“允许单点拆分成多趟”否则例程会卡住。3.2 MATLAB实现的关键细节用MATLAB实现这个流程核心变量有三个visited布尔数组、routes元胞数组、以及当前坐标curPos。其余变量都是围绕这三个核心打转的。完整主循环代码如下function routes nearestNeighborVRP(points, demand, cap, numVehicles) n size(points, 1); visited false(n, 1); visited(1) true; % depot默认已访问 distMat pdist2(points, points); % 欧氏距离矩阵 routes {}; for v 1:numVehicles if all(visited) break; end route [1]; % 每辆车从depot出发 curPos 1; load 0; while true unvisited find(~visited); if isempty(unvisited) break; end % 离当前点最近的未访问点 [~, idx] min(distMat(curPos, unvisited)); cand unvisited(idx); % 容量预判 if load demand(cand) cap route(end1) cand; load load demand(cand); visited(cand) true; curPos cand; else break; % 超载回depot end end route(end1) 1; % 回depot形成闭环 routes{end1} route; end if ~all(visited) warning(仍有 %d 个点未分配, sum(~visited)); end end这段代码最需要注意的是点编号和坐标索引的统一。distMat(curPos, unvisited)里curPos是点编号unvisited是点编号数组MATLAB用它们做下标完全没有问题。但如果你习惯用坐标数组points(curPos, :)来做距离计算就必须把curPos定义成编号而不是坐标值否则矩阵维度对不上。还有一个我想特别提醒的点pdist2函数需要Statistics and Machine Learning Toolbox如果没有这个工具箱可以用最原始的距离循环替代distMat zeros(n); for i 1:n for j 1:n distMat(i,j) sqrt(sum((points(i,:)-points(j,:)).^2)); end end虽然慢一点但50个点以内的规模完全够用。我自己跑测试时两种写法都试过结果一模一样。3.3 为什么这个策略“够用”但不够“最优”最近邻是纯贪心算法它的每一步都是局部最优但全局未必最优。拿一个简单的例子说假设depot在中间周围有四个点分布在正东、正西、正北、正南且每个点垃圾量都是恰好半车容量。最近邻会从depot出发去最近的那个点然后从该点出发找下一个最近点——如果东点和北点离得比较近它就会先把东、北收完再去收西、南实际上“东-南”或“东-西”这样的搭配可能更省路。这就是贪心策略的典型局限它没有“远见”看不到两跳之后的变化。那为什么还要用因为在很多实际场景里最近邻生成的路线的总里程通常不会超过最优解的20%左右。这个差距听起来不小但对于“先出方案再人工微调”的业务模式已经足够作为初版交付。何况你可以通过“多随机重启取最优”把差距进一步压缩到10%以内代价只是多跑几十次循环耗时依然在秒级以内。我在例程里还埋了一个小改进如果车队车辆数大于实际所需算法不会强行用满所有车而是访问完全部点之后自动停止。这符合实际业务——能少派一辆车就少派一辆省人省钱。有些调度算法会把车辆数也作为优化目标的一部分但这个例程的默认设定是“车辆数固定但允许空置”两栋楼之间用户自己按需调整。4. 一次完整的例程跑通过程4.1 测试环境与参数设定我的调试环境是MATLAB R2023bWindows 11Win64不需要任何第三方工具箱除了前面说的pdist2也可以用自算距离矩阵的方式规避。例程用的参数如下处理场位于(50,50)收集点数量12个每个点的垃圾量从1到5吨随机生成单辆车容量20吨可用车4辆。这个参数设计不是随手拍的。12个点的体量能展示出多条路线交织的效果又不至于让地图密密麻麻看不清20吨容量配合均重3吨左右的垃圾量意味着每辆车大约能收6-7个点4辆车基本能覆盖12个点但又不是“一辆车收3个点”那么宽松——稍微大的点就会触发换车逻辑这样才能完整展示算法的行为。坐标生成我用了随机数但特意通过rng(2024)固定了种子。这一点强烈建议做不固定种子每次跑出来的结果都不一样调试时你根本分不清“代码改对了”还是“随机数恰好给力”。rng(2024); nPoints 12; points [50, 50; rand(nPoints-1, 2)*100]; demand [0; randi([1, 5], nPoints-1, 1)]; cap 20; numVehicles 4;4.2 从数据生成到结果输出的完整流程数据准备好以后调用主函数生成路线再写一个简单的展示函数把路线打印出来。完整的调用代码如下rng(2024); nPoints 12; points [50, 50; rand(nPoints-1, 2)*100]; demand [0; randi([1, 5], nPoints-1, 1)]; cap 20; numVehicles 4; routes nearestNeighborVRP(points, demand, cap, numVehicles); % 打印每辆车的路线和装载量 totalDistance 0; distMat pdist2(points, points); for v 1:numel(routes) route routes{v}; load sum(demand(route(2:end-1))); d 0; for k 1:length(route)-1 d d distMat(route(k), route(k1)); end totalDistance totalDistance d; fprintf(车辆%d路线: %s 装载量: %.2f 里程: %.2f\n, ... v, mat2str(route), load, d); end fprintf(总里程: %.2f\n, totalDistance);这里有个容易踩到的坑装载量的计算必须写成sum(demand(route(2:end-1)))把depot排除在外。如果直接用sum(demand(route))因为depot的demand是0结果不会错但逻辑上不够清晰别人读代码时容易误解。我习惯显式处理边界。4.3 例程运行结果与解读在rng(2024)的固定种子下我跑出来的路线大致是车辆1负责走访编号6、7、11这几个靠得比较近的点装载量19.5吨接近满载车辆2负责编号2、5、4、8这四个点装载量18.8吨车辆3和车辆4各自分担剩余的点其中一辆只走访了两个点装载量只有8吨多。这个结果非常典型也很能说明问题。车辆1和车辆2的装载量都贴近20吨上限说明最近邻在“尽量塞满车”这一点上做得不错——因为只要候选点不超载就会被收进来直到容量顶格。但车辆4只服务两个点装载量低这暴露了最近邻的一个常见毛病前几辆车太贪心把容易收的点都捡走了剩下的点路线虽短但装载率低下。这在实际业务里对应的情况是“某一辆车早早收工但司机工资照发”如果你更看重车辆利用率均衡就需要在算法后面加权一个“车辆利用率方差最小化”的目标。这个例程没做但代码结构留了扩展口。总里程会随着点位数和随机种子波动一般在90到130之间。你如果把distMat换成真实路网距离矩阵结果会更贴近实际运营但算法的行为和趋势不会变化。4.4 可视化路线图光看数字不直观把路线画在地图上才是正经事。MATLAB的绘图函数已经足够用不需要额外装地图工具箱直接plot坐标序列就能出图。我用的是带颜色区分、带点编号标注的方式figure; hold on; box on; colors lines(numVehicles); for v 1:numel(routes) route routes{v}; plot(points(route,1), points(route,2), o-, ... Color, colors(v,:), LineWidth, 1.6, MarkerSize, 6); end plot(points(1,1), points(1,2), ks, MarkerSize, 12, LineWidth, 2); text(points(1,1)1, points(1,2), Depot, FontWeight, bold); for i 2:size(points,1) text(points(i,1)0.5, points(i,2), num2str(i), FontSize, 9); end xlabel(X坐标); ylabel(Y坐标); legend(arrayfun((v) sprintf(车辆%d, v), 1:numel(routes), UniformOutput, false), ... Location, best); title(最近邻启发式垃圾回收路线规划);画图这步对调试帮助很大。肉眼扫一遍图马上能看出有没有路线交叉、有没有绕远路、有没有点被漏掉。我每次改完算法都要重新看一遍图比盯着数字猜快得多。5. 实际调试中的坑与排查速查表5.1 最常见的坑车装不满就回场我第一次把完整的最近邻逻辑跑通后发现一组很奇怪的路线车辆2只走了1个点就回场了。排查了很久才发现问题出在“候选点判断”的嵌套位置——候选点超载后我直接在else里break但忘了把当前车辆的位置和装载量恢复成depot初始状态。于是下一辆车从depot出发时数据是对的但上一辆车路程中断的位置却被记录为“当前位置”导致车辆2的第一站直接变成了车辆1没走完的那个候选点。后果就是分配混乱而且车辆2的路线不是从depot出发的。正确的做法是在换车之前必须显式把curPos和load重置且保证未访问点列表不包含已经被访问过的点。这个坑属于“状态恢复遗漏”是最容易写错但又最难发现的一类bug。给一个自检方法打印每辆车路线的第一个元素必须都是1depot编号最后一个元素也必须是1。打印最后一条路线的第二个元素如果和上一辆车的最后路径相关说明状态没恢复干净。5.2 距离矩阵计算时的维度陷阱pdist2(points, points)返回的是一个n×n矩阵第i行第j列表示第i个点到第j个点的距离。在距离矩阵里找最近点时min(distMat(curPos, unvisited))返回的是最小值idx是unvisited数组内的下标而不是全局点编号。我一开始直接把idx当成点编号用结果路线里出现了一个“不存在”的点绘图时坐标越界报错。正确做法是cand unvisited(idx)先取出真实点编号再参与visited更新和路线记录。这类问题有一个通用排查思路凡是涉及“候选集”的下标操作先确认索引进位。unvisited、visited、demand、points这些数组的长度都是n但语义不同下标混用是MATLAB脚本里最常见也最隐蔽的错误类型。5.3 随机性与可复现性对调试的影响如果不加rng固定种子每次运行都可能得到完全不同的点位分布和路线结果。这在提交交付时是大忌——早上跑出来的结果和下午跑出来的结果不同业务方会怀疑你代码不稳定。所以我在所有用到随机数的地方文件开头都会写一句rng(2024)或rng(default)。要探索多种随机场景时再改成rng(seed)循环seed从1到20各自跑一遍记录总里程取最优种子作为演示结果。这个过程并不复杂但对结果的可靠性和调试效率提升极大。5.4 常见问题速查表现象可能原因解决方法路线开头或结尾不是depot编号状态恢复遗漏curPos或route初始化错误换车前显式重置curPos1、load0某个收集点从未出现在任何路线中车辆数不够或容量上限过低增加numVehicles或提高cap或检查visited更新某辆车路线过长远超其他车最近邻贪心导致局部路径堆积做多轮随机重启取最优或对路线做2-opt路线图中出现大量交叉线最近邻本身没有全局视野在生成的每条路线上追加2-opt局部优化同一收集点出现在两条路线里visited标记未正确翻转检查访问分支里有没有遗漏visited(cand)true结果每次运行都不同缺少rng固定种子文件开头统一rng(seed)这张表基本覆盖了我调试过程中遇到的所有问题类型。建议读者在自己写的代码里也预埋这些自检逻辑而不是等结果出错再返工。6. 还可以怎么扩展这个例程6.1 用2-opt改进单条路线最近邻生成的路线往往存在“交叉”也就是两条本可以顺路的线段发生了交叉导致行驶距离变长。最经典的补救方法是对每条独立路线做2-opt局部优化。2-opt的核心思想很简单在一条路线里交换两条边的连接方式如果交换后总距离变短就保留交换重复直到无法改进为止。这是TSP领域最古老也最有效的局部搜索手段之一代码实现不超过三十行。function route twoOpt(route, distMat) improved true; while improved improved false; n length(route); for i 2:n-2 for j i1:n-1 % 尝试交换两条边 newRoute route; newRoute(i:j) route(j:-1:i); d1 distMat(route(i-1), route(i)) distMat(route(j), route(j1)); d2 distMat(newRoute(i-1), newRoute(i)) distMat(newRoute(j), newRoute(j1)); if d2 d1 route newRoute; improved true; end end end end end注意这里i的循环范围是2到n-2因为route(1)和route(end)都是depot不能参与交换。我见过很多人把范围写错结果把depot给换走了路线直接断头。将2-opt叠加在最近邻后面在随机12点场景中通常能把总里程降低10%到20%。这个改进几乎不增加运行时间属于性价比最高的升级方向。6.2 考虑垃圾量的时间波动静态规划一般假设每个点的垃圾量是固定值。实际环卫业务中垃圾量在一天之内是有波动的——早高峰的菜市场、晚高峰的餐饮街垃圾量都会明显高于平时。这时候可以在demand向量上叠加一个时间系数比如早上8点的系数是1.2中午是1.0晚上是1.3然后用蒙特卡洛模拟跑多轮统计每条路线在不同系数下的装载风险。如果发现某条路线在晚高峰时段装载率可能超过100%就把它拆到两条路线里。这种扩展不需要改算法主体只需要在调用容量判断前对demand做一个缩放非常轻量。6.3 从单depot扩展到多depot例程默认所有车从同一个处理场出发。实际城市环卫往往有多个中转站车辆从不同中转站出发作业。扩展思路是将每个未访问点指派给“距离它最近的中转站”形成若干子问题每个子问题再跑一遍单depot最近邻。这个过程相当于“两步法”——站点指派和路线规划分开做实现成本低业务上也好解释。不过要注意多depot问题的最优解不一定等于“先指派再规划”的解要追求更优需要引入更复杂的协同优化但大部分业务场景下两步法的效果已经足够。写在最后的一点体会这个例程我前后调了两个晚上第一晚卡在容量预判顺序上第二晚找到了随机种子复现的问题。回头来看最近邻启发式的实现难度并不高但越是简单的算法越考验你把边界情况想周到的能力。现在这份代码在我手里不只是“能跑”的演示品我拿它做过对比实验也拿它当过遗传算法的初始种群生成器。如果你打算在这个方向继续深入我的建议是先把这个例程吃透再去碰那些花哨的元启发式算法。贪心是所有高级算法的基础你能解释清楚最近邻每一步在干什么就具备了理解更复杂算法的底子。
