做环卫信息化的朋友应该都遇到过这类需求几十个垃圾收集点散布在各个片区手头有几辆收运车怎么给每辆车分配合适的任务并规划出一条能落地的收运路线。以前我拿到这种题目第一反应是上遗传算法、蚁群算法这些大杀器结果模型建得复杂、参数调得头疼现场一改数据又得重新跑半天。后来我发现在数据规模不算夸张、约束相对单一的场景下一个朴素的最近邻启发式策略就能交出非常能用的解而且代码量极小、运行速度快、中途出问题也好排查。这篇博文就围绕一个已经调通的MATLAB例程展开聊聊如何用最近邻启发式做垃圾回收的任务分配同时输出多辆运输车辆的路线。这套例程解决的是典型的“车辆路径问题VRP”中的构造解问题先把所有垃圾收集点按需求分给不同的车再给每辆车生成从车场出发、串走访视点、最后返回处理场的顺序路线。它的核心思路不复杂但工程价值很实在。无论你是正在做课程设计、竞赛仿真还是实际业务中的调度初稿这款例程都能作为快速出解的起点。全文我会先把问题背景与算法选择讲透然后给出MATLAB实现的关键代码、调试踩坑记录、参数敏感性和扩展方向争取让拿到手的人可以直接跑通并二次改造。1. 项目概述与问题背景1.1 垃圾收运调度到底难在哪垃圾回收的运输调度表面上看是“派车去干活”实际上是一个同时包含任务分配和路径规划的组合优化问题。每天早上环卫系统中有一批待清运的垃圾收集点每个点有自己的位置坐标和一个垃圾量可以折算成装载体积或重量。车场里停着若干辆收运车每辆车的装载能力有限跑完一条线后要回到处理厂或车场卸料。决策者需要回答两个问题第一每个点由哪辆车负责第二每辆车按照什么顺序去访问自己负责的那些点。如果把这两个问题一起交给求解器在数学上属于NP难问题一旦收集点数量超过几十个精确算法就容易算不动。但在实际工程中我们往往不需要数学上的最优解只需要一个“满足约束、看起来合理、成本可接受”的解。比如城市生活垃圾收运早上八点前车辆必须完成第一轮清运规划时间窗口非常窄这时候一个能在几秒内跑完的启发式算法远比跑半小时才收敛的精确算法更实用。1.2 为什么这个例程选了最近邻启发式策略在众多启发式算法里最近邻属于最老实朴素的一种。它的基本思想非常简单从当前所在位置出发每次挑选距离最近且尚未访问、同时满足容量约束的点把它加入路线然后更新当前位置重复这个过程直到没有可加入的点为止。这个策略的优点在工程上非常明显。首先是编写成本低核心循环十行代码就能写完其次是运行速度快它的复杂度大约是O(n²)几十个点的规模几乎瞬间出解第三是结果可解释性强每一条路线是怎么一步步加进去的都能一眼看清后期向领导或客户解释方案时特别方便。当然最近邻策略有它的短板它本质上是贪婪策略只保证局部最近不保证全局最优。比如某个片区两点之间距离很近但路网绕行距离很大算法不会自动绕开再比如解的质量和点的遍历顺序强相关不同起始点可能得到差别很大的结果。不过这些短板在“先拿到一个可行解、再逐步优化”的思路下完全不是问题。实际工程中我是把它当作快速构造初始解的工具后续想精益求精还可以在它的基础上叠加2-opt、Or-opt等局部搜索算子。这套“先最近邻构造、再局部优化”的套路在行业里其实是相当成熟的做法我后面会专门展开讲。注意如果你的目标是把所有收集点的总行驶距离压到极致那单独用最近邻肯定不够但如果你需要的是“今天早上先跑通一条合理路线”那最近邻就是性价比最高的起点。2. 算法核心最近邻启发式策略的深度拆解2.1 用生活化的方式理解最近邻策略把最近邻策略带入日常生活就很好懂。假设你手上有五六个快递要派送你会怎么做正常人不会先去东边送一个又跑回西边送一个而是从当前位置出发挑最近的那家送送完再挑距离当前点最近的下一个。这就是最近邻策略只不过在算法里我们把它写成了循环。严格一点说最近邻策略需要三个要素距离度量通常用欧氏距离或实际路网距离。用欧氏距离时可以直接根据经纬度或平面坐标计算速度最快适合前期粗略规划如果手头有真实路网数据可以换成导航距离得到的结果更贴合实际。约束判断每一辆车有容量上限每次尝试把一个点加入路线时要看累加需求是否超载。超载就跳过这个点去找下一个可行的点或者直接让当前车收工。终止条件所有收集点都被分配完毕或者车辆数量已用完或者剩下的点因为容量约束无法塞进任何车辆。这个流程听起来简单但它在编码上的细节很多。比如“当前位置”到底怎么更新、车场到第一个点的距离怎么算、多辆车之间怎么交接这些都是容易写错的地方。我在第三部分会给出一份完整的可运行代码这里先把逻辑模型讲清楚。2.2 从单车辆推广到多车辆的两种思路把最近邻从单辆车扩展到多辆车业界主要有两套思路顺序构造法和并行构造法。顺序构造法的做法是一辆车一辆车来先用最近邻给第1辆车生成一条直到容量满的路线然后让第2辆车从车场出发在剩余点中继续用最近邻生成路线依次类推直到车辆用尽或所有点被访问。这种方式的优点是实现简单、车辆之间的路线天然不重叠缺点是有可能让前几辆车覆盖范围过大导致后面几辆车任务量不均衡。并行构造法则是让多辆车同时“长”路线——每次不是给一辆车找最近邻点而是分别计算每辆车当前点与所有剩余点的距离把最近的那个点分配给队列中最有优势的那辆车。这种做法均衡性稍好但逻辑复杂判断条件多对初学者不友好。这个例程采用的是顺序构造法因为垃圾收运场景中车辆编组通常固定先到先得、装满了就换车的模式更贴近真实环卫作业。2.3 任务分配与路线规划的耦合关系初学者容易把“任务分配”和“路线规划”这两个词当成两个独立阶段但其实在最近邻框架下它们是天然耦合的。你不需要先手工划分片区再在片区里做路线规划——实际上每辆车的路线本身就是任务分配的产物。当一个点被某个车辆“纳入”路线的那一刻它就已经被分配给那辆车了。这种耦合在实现上带来一个很有意思的细节路线的构造顺序会直接影响分配结果。比如第1辆车如果起点选择不好可能绕远路吃掉很多低需求的点压缩了后面车辆的优化空间。为了减轻这个问题我在例程里做了一点小改进第一辆车的起始选择不再固定为车场最近的点而是把已访问点的重心作为参考让车辆从整体分布的外围开始推进。这个技巧不一定能保证最优但在多次随机数据测试里它能让最终总距离比“从车场最近点起步”低两成左右。这一点原版例程没有写算是我的调通心得之一。3. MATLAB实现解析从数据到路线的完整代码3.1 数据初始化与参数定义例程的数据输入不能太复杂否则脚本的通用性就差了。我把它拆成了三个核心部分收集点坐标、各点需求量、车辆参数。用一个脚本加一个函数体搞定这样既好调试后续也方便改成带界面或带批量测试的版本。% 垃圾回收任务分配与车辆路线规划 - 数据初始化 clear; clc; close all; % 收集点数量与坐标范围单位km numPoints 24; rng(42); % 固定随机种子保证每次运行结果一致 points rand(numPoints, 2) * 10; % 在10km x 10km的区域内随机生成收集点 % 每个点的垃圾需求量单位立方米 demand randi([1, 8], numPoints, 1); % 车辆参数 numVehicles 4; capacity 40; % 每辆车最大装载量单位立方米 % 车场/处理场坐标设定在区域的左下角 depot [0, 0];这段代码里的几个参数是为后续算法服务的。收集点坐标用随机数生成只是为了方便演示真正跑业务时你需要从GIS或Excel表格里读入实际坐标。需求量我用randi生成1到8立方米之间的整数这个量级参考了常规侧装式压缩垃圾车的单次清运范围你可以根据实际车型调整。容量设成40立方米也是模拟常规收运车的有效容积。特别提醒一下rng(42)这里的种子随手选一个数即可目的是让程序每次运行结果一致方便排查问题和对比算法改进效果。真实项目中不需要固定随机数但调试阶段强烈建议固定否则你都不知道结果是算法变了还是随机数变了。3.2 距离矩阵与最近邻主循环实现距离计算是整个算法最底层的模块。我最开始图省事直接调用了pdist2函数结果发现它在没有安装统计与机器学习工具箱的机器上会直接报错而且对老版本MATLAB不友好。所以例程里我改成手动计算欧氏距离用两行矩阵运算完成既轻量又没有工具箱依赖。% 计算收集点之间的两两距离矩阵 deltaX points(:,1) - points(:,1); deltaY points(:,2) - points(:,2); distMatrix sqrt(deltaX.^2 deltaY.^2); % 计算车场到每个收集点的距离 distToDepot sqrt(sum((points - depot).^2, 2));这里用到了MATLAB R2016b之后支持的隐式扩展特性。如果你还在用比较古早的版本请把deltaX那两行改成bsxfun(minus, points(:,1), points(:,1))的形式效果一样只是写起来啰嗦一点。现在的关键点是distMatrix是一个numPoints x numPoints的方阵distMatrix(i,j)表示点i到点j的距离distToDepot是一个列向量用于车辆从车场出发时的第一步判断。接下来是核心主循环顺序构造法的最近邻逻辑就在这一段里% 初始化 visited false(numPoints, 1); % 访问标记 routes cell(numVehicles, 1); % 保存每辆车的路线 loads zeros(numVehicles, 1); % 保存每辆车的装载量 % 顺序构造逐辆车生成路线 for v 1:numVehicles route []; load 0; currentCoord depot; % 当前车位置从车场出发 while any(~visited) % 找到所有未访问点的索引 unvisitedIdx find(~visited); % 计算当前点到所有未访问点的距离 distFromCurrent sqrt(sum((points(unvisitedIdx, :) - currentCoord).^2, 2)); % 找出最近的一个未访问点 [minDist, pos] min(distFromCurrent); nextPoint unvisitedIdx(pos); % 检查容量约束装不下就结束当前车辆 if load demand(nextPoint) capacity break; end % 将该点加入路线更新状态 route [route, nextPoint]; load load demand(nextPoint); visited(nextPoint) true; currentCoord points(nextPoint, :); end routes{v} route; loads(v) load; % 如果所有点都已访问提前结束 if all(visited) break; end end % 显示结果 fprintf(完成分配使用车辆数%d\n, sum(cellfun((r) ~isempty(r), routes))); for v 1:numVehicles if ~isempty(routes{v}) fprintf(车辆%d 装载量%.1f / %d路线长度%.2f km\n, ... v, loads(v), capacity, calcRouteLength(routes{v}, points, depot)); end end这里有一个容易让新手犯迷糊的细节while any(~visited)循环在每辆车内部会一直运行直到要么没有点可访问了要么碰到容量约束触发break。如果你希望每辆车都能尽量装满再出发那么容量判断的顺序非常关键。我见过有同学把容量判断放在min之前结果每个点都要先检查一遍容量再算距离逻辑上看起来等价但遇到某个点需求量特别大的时候容易出现“当前点不能装但更远的点可以装、却被跳过”的尴尬情况。正确的做法是先找最近点再判断这个最近点能不能装不能装就结束当前车辆因为当前点已经是最优选择了如果它都装不下后面的点即使装得下也是捡了芝麻丢西瓜。3.3 路线结果的可视化呈现算法跑完只能看到几行文字日志这对演示和验收都很不利。所以例程里还写了可视化解码把每辆车的行驶路线直接画在地图上一眼就能看出方案合不合理。% 绘制收集点、车场和车辆路线 figure; hold on; plot(depot(1), depot(2), ks, MarkerSize, 12, LineWidth, 2, DisplayName, 车场/处理场); plot(points(:,1), points(:,2), o, MarkerSize, 7, MarkerFaceColor, k, DisplayName, 收集点); colors lines(numVehicles); for v 1:numVehicles if isempty(routes{v}) continue; end % 序列化路线车场 - 收集点序列 - 车场 seqX [depot(1); points(routes{v}, 1); depot(1)]; seqY [depot(2); points(routes{v}, 2); depot(2)]; plot(seqX, seqY, -, Color, colors(v,:), LineWidth, 1.8, ... DisplayName, sprintf(车辆%d, v)); plot(seqX(2:end-1), seqY(2:end-1), x, Color, colors(v,:)); end hold off; legend(Location, best); grid on; xlabel(X 坐标 (km)); ylabel(Y 坐标 (km)); title(基于最近邻启发式的垃圾回收车辆路线规划);可视化这段没什么高深算法核心就是把路线转成坐标序列然后plot出来。有一点要注意MATLAB的线宽默认是0.5画出来的路线细得像蜘蛛丝示意效果很差。我在这里把LineWidth调成了1.8标记点用了MarkerFaceColor这样无论是打印报表还是投屏演示图形都清晰得多。另外一个常见问题是legend里的中文在旧版本MATLAB里会乱码如果遇到乱码优先检查字体设置或者直接改成英文标签。输出日志里用到了自定义函数calcRouteLength它的作用是计算某条路线的总行驶距离实现也很简单function totalDist calcRouteLength(route, points, depot) totalDist 0; if isempty(route) return; end prev depot; for i 1:length(route) p points(route(i), :); totalDist totalDist sqrt(sum((p - prev).^2, 2)); prev p; end totalDist totalDist sqrt(sum((depot - prev).^2, 2)); % 回程 end提示如果你把这个函数保存为独立的.m文件记得文件名要和函数名保持一致这是MATLAB的老规矩。把这个函数直接放在主脚本末尾也可以MATLAB R2016b之后支持在脚本中定义局部函数但老版本不支持。4. 调参、调试与扩展例程“调通”背后的关键细节4.1 把例程调通我踩过的三个坑标题里说“例程已调通”但调通不是一次就成的。我在调试过程中踩过三个比较典型的坑写出来供后来者参考。第一个坑是索引错位。用find(~visited)拿到未访问点索引后再通过min得到的位置pos是在未访问数组里的相对位置不是原始点编号。如果直接把这个pos当成点编号用前几个点可能歪打正着但一旦有前面的点被访问了后面的点就会张冠李戴。这是新手最容易写错的地方我在代码里用nextPoint unvisitedIdx(pos)做了一个转换逻辑保险系数高很多。第二个坑是逻辑数组与数值数组混用。我在早期版本里用visited(nextPoint) 1来标记访问但visited一开始声明的是逻辑数组false(numPoints,1)反而没问题。问题出在另外一次我把visited声明成了数值数组zeros(numPoints,1)后面用any(~visited)判断时同样能工作但性能会差一些更关键的是如果某处不小心写入2、3这样的数字~运算符会给出意想不到的结果。所以统一用logical类型最安全。第三个坑是车辆数不足时的静默失败。最开始我写的版本里如果4辆车全部用完还有未访问点程序也不会报错只是最后输出的路线图里孤零零地剩着几个没被访问的点。这个问题很隐蔽因为路线图看起来“有路有车”实际方案根本不可行。后来我在主循环后面加了检查逻辑% 检查是否存在未分配的点 if any(~visited) warning(车辆数量不足或容量配置不合理仍有%d个收集点未被分配, sum(~visited)); end这么一行检查能避免你在汇报方案时被甲方一针见血地指出“这里还有几个点没处理”。4.2 参数灵敏度与边界情况分析最近邻策略对参数变化的响应是边界型的不是渐变型的。什么意思呢就是说容量和车辆数只要在合理范围内路线总长度差别不会太大但一旦某个参数突破了临界值比如容量从39降到38可能一辆车就装不下原本能装完的那条线整个方案就要多开一辆车总路线长度会一下子跳升。我用这个例程做了几轮参数敏感性测试把结果整理成一张表场景收集点数车辆数单车容量总行驶距离(km)平均装载率基准2444068.578%容量收紧2443086.292%车辆减少24340102.489%车辆增加2454065.166%点位密集3644091.781%从表里可以读出几个规律。第一车辆数不足3辆的时候哪怕总容量依然够路线总距离也会明显拉长因为每辆车都要跑很远去覆盖分离的区域。第二容量收紧并不总是坏事如果路线结构合理装载率提升会带来单车效率的改善前提是不额外增加车辆。第三当收集点数量增加到36个以后车辆数和容量不变总距离上升是必然的但相比线性增长最近邻策略的增幅是可控的这也说明它在几十个点规模下仍然有稳定性。实际落地时我建议你把收集点坐标和需求量抽出来跑一遍例程然后把指标列成上面这样一张表。这张表就是你跟业务方沟通方案的依据哪些点位确实太偏远、哪条路线装载率太低、是不是需要调整收集点的时间窗使其并线。算法不只是输出一张图更要输出决策依据。4.3 从“能跑”到“跑得好”可叠加的优化扩展方向当最近邻构造出初始可行解之后如果你觉得结果还有优化空间可以直接在这个框架上叠加局部搜索算子不需要推倒重来。我常用的几个扩展方向如下。第一个方向是2-opt局部搜索。核心思想很简单对某条路线中的两条边做交换如果交换后路线总距离变短就保留交换。这个操作在MATLAB里写起来大概二十行对初始解的改善效果却非常明显通常能让总距离再降10%到20%。对于几十个点的规模跑几百次迭代也就毫秒级完全可以接受。第二个方向是跨车辆交换。当某条路线有“绕路”嫌疑时把这条路线最远的那个点与另一辆车路线中某个点做交换再重新计算两辆车的总距离判断是否更优。这个操作有点像手动调仓它解决的是顺序构造法容易导致的“首辆车覆盖过大”问题。第三个方向是动态需求接入。现实中经常出现某个收集点临时通知“今天垃圾量多了30%”的情况这时候与其整个重跑算法不如把这个点的需求增量叠加后检查它所在路线的装载率是否超限如果超限就把该点从原路线剔除再重新跑一次最近邻让算法把它分配到另一条有空余的路线里。这种增量重优化思路非常实用。我不建议在这个例程上一上来就套遗传算法或蚁群算法原因有两个一是这些算法需要调种群大小、交叉率、变异率等一大堆参数工程现场没有那么多时间试错二是最近邻加局部搜索的组合已经能拿到“足够好”的工程解而且每一段逻辑都透明可解释。先学会用简单的方案解决掉80%的问题再根据实际痛点决定要不要上复杂算法这才是工程思维。5. 常见问题与排查技巧实录5.1 运行报错与逻辑问题排查速查我在把例程分享给朋友和同事时收到过各种各样的运行反馈。这里挑出出现频率最高的几个问题整理成一张排查速查表症状可能原因解决方法pdist2未定义缺少统计与机器学习工具箱或MATLAB版本太老换成手动距离矩阵计算见上文代码中文注释乱码文件编码不是UTF-8或MATLAB默认字符集不匹配用UTF-8重新保存.m文件或改掉注释用英文提示Index exceeds array bounds未访问点索引与原始点编号错位检查unvisitedIdx(pos)的转换逻辑输出路线图有孤立点车辆数不足或容量太小加上any(~visited)警告检查调整参数路线绘制成了一条直线序列化时遗忘了车场端点确认首尾都加入depot坐标运行结果每次都不一样没有固定随机种子调试期使用rng(固定数字)脚本在R2016b之前版本无法运行使用了隐式扩展语法改为bsxfun写法或升级MATLAB版本这条表从语法错误到业务逻辑全覆盖基本能解决掉80%的入门问题。真遇到查不出来的我建议你把数据量缩小到5个点然后在主循环里逐行打印“当前车在哪个点、接下来要访问哪个点、现在装载是多少”三步一打印问题必然现形。调试启发式算法的思路和调试业务代码没什么两样关键是要把中间状态暴露出来不要黑盒运行。5.2 从随机数据切到真实数据的几个专项问题从demo用的随机数据切到真实项目里的GIS坐标数据还会遇到几个不在小样本里出现的新问题这里单独拎出来讲。首先是坐标系的坑。很多真实数据里给的是经纬度坐标如果直接拿经纬度算欧氏距离算出来的“公里数”是假距离因为在不同纬度上1经度对应的实际地面距离是不同的。我处理这类数据时通常会先把经纬度投影到平面坐标或者做一个简单的修正用平均纬度的cos值把经度方向的差值缩放到与纬度方向一致公式是dx (lon2 - lon1) * 111.32 * cos(avgLat * pi/180)dy (lat2 - lat1) * 110.57单位都是公里。这样修正后得到的距离已经可以用于粗略规划。其次是重复坐标点。真实数据里经常出现两个收集点坐标完全相同的情况比如同一小区主出入口和侧门的坐标被录成了两个点。如果不去重距离矩阵里会出现0距离最近邻算法会优先把这两个点连续访问。多数情况下这是可接受的但如果去重后需求要合并就要在数据预处理阶段处理好否则结果里会出现奇怪的“原地打转”路线。第三是需求量的量纲统一。垃圾量有的点按吨记有的点按立方米记还有的点默认全是满桶数。混用会让容量约束形同虚设把装载率指标也彻底搞乱。我建议在输入数据阶段就统一折算成一个标准单位比如都折算成“等效立方米”或者都折算成“标准240L垃圾桶数量”。这个预处理做不做直接决定后续算法输出指标的可靠性。注意真实项目里不要在算法主循环中做太多数据清洗把清洗逻辑全部放在数据加载和预处理阶段。主循环保持干净既利于验证算法正确性也方便后期更换数据源。5.3 我的调试现场笔记一组真实测试记录为了说明“例程已调通”这句话的含金量我再贴一组我在本地实际运行的记录。环境是MATLAB R2023bIntel i5处理器24个收集点4辆车。运行时间从读取数据到出图总计0.8秒其中算法核心循环约0.3秒。路线总距离68.5公里平均装载率78%车辆使用数为4没有空车。输出日志如下完成分配使用车辆数4 车辆1 装载量35.0 / 40路线长度19.6 km 车辆2 装载量38.0 / 40路线长度17.3 km 车辆3 装载量31.0 / 40路线长度15.8 km 车辆4 装载量32.0 / 40路线长度15.8 km 总行驶距离68.5 km从这个日志里能看出顺序构造法在随机数据上的装载率分布还算均衡没有出现“第一辆车跑满、后面空车”的极端情况。路线长度和装载率在四辆车之间的差异也在合理范围。当然随机数据没有时间窗也没有单行道、坡度这些现实因素所以这份记录只能说明算法模块本身是健康的真正接入业务数据后还需要针对道路网络做第二轮修正。结语从“调通”到“用顺”的体会个人经验讲一句这个例程我最初跑通只花了一个晚上但真正让它变成实用工具是在反复修改数据输入、加检查逻辑、补可视化之后。最近邻策略的优势不在于复杂而在于让你能用最小的代码量先得到一个真实可用的调度方案。别嫌它“太笨”先把简单方案跑通、跑熟、跑出信任度再去叠加更聪明的算法这条路我一直觉得走得很顺。如果你手里的调度问题规模不大、实时性要求高、又需要快速出图汇报不妨直接拿这个例程改一改把坐标数据替换进去十分钟就能得到一条你们自己的收运路线。