垃圾回收任务分配难题：MATLAB最近邻启发式算法实现与路径优化

1. 从实际问题说起：垃圾回收任务分配难在哪

先说一个我常遇到的问题。做城市环卫信息化项目的朋友应该都有体会：一个中等的居民区片区，分散着几十个垃圾投放点，车队就那么几辆车，每天都要跑一趟回收垃圾。路线排得好不好，直接决定一天的油耗、司机的工作时长、甚至居民对垃圾清运及时性的投诉量。

这个场景就是典型的“垃圾回收任务分配”，核心目标是：给定一组回收点位置、每个点的垃圾量、车辆的数量和载重上限，合理规划每辆车的访问顺序，让总行驶距离最短，同时不超载、不遗漏、不重复。

现实中很多单位是怎么排路线的？老师傅凭经验，或者干脆按投放点的编号顺序挨个跑。后果就是：有的车绕远路，有的车装满了还要硬跑下一站，有的区域今天没车去明天积成堆。这里面的浪费在数据上看很直观。我用一个30个点的测试数据算过，按编号顺序跑的总路程，比优化后多出 30% 到 40%。对一台每天跑 100 多公里的环卫车来说，这个差距意味着每天多烧好几升油。

有人可能会问：这不就是个路径优化问题吗？直接用启发式算法或者精确算法不就行了？其实没那么简单。垃圾回收任务分配有两个特殊约束：

一是容量约束。每辆车能装的垃圾总量有限，不能像快递配送那样纯看路线长短，还必须在访问过程中随时关注累计载重。二是动态性。垃圾量每天都在变，周末可能是工作日的两倍，不同季节、不同区域的增长速度也不一样。所以算法不能太复杂，必须够快、够稳、能快速重算。

这也是我今天要分享这段 MATLAB 代码的原因。它用的策略是最近邻启发式（Nearest Neighbor Heuristic），思路极简：从回收站出发，每次找离当前位置最近且未访问的回收点，走过去，直到车辆满载或没有可达点，再换下一辆。别小看这个策略，它运行速度快、逻辑直观，特别适合作为多车任务分配的“初始解生成器”或者实时调度场景下的快速方案。如果配合后面的局部优化（比如 2-opt），精度和复杂算法差距并不大。

这篇文章我会从算法原理、任务分配框架、MATLAB 实现细节、运行调试、常见坑位到后续改进方向，完整拆解一遍。适合三类人：一是刚开始接触路径优化问题、想找一份能跑起来做实验的代码的人；二是做环卫片区调度、需要了解任务分配算法逻辑的规划人员；三是想拿最近邻做初始解、给后续启发式算法铺路的研究者。

2. 最近邻启发式：核心原理与任务分配框架

2.1 为什么是“最近邻”而不是别的

先看最朴素的单车路径问题。假设一辆车从回收站出发，要回收 10 个点的垃圾，怎么走总距离最短？

直接求最优解在数学上是“旅行商问题”的变体，节点稍微多一点就会陷入组合爆炸。10 个点的排列有超过 360 万种，20 个点更是天文数字。实际环卫片区动辄几十个点，不可能每次都硬算最优解。

这时候启发式策略就派上用场了。最近邻的思路非常符合直觉：人在不熟悉的街区找一个一个点走过去拿东西，本能反应就是挑最近的下一个目标先过去。这个“贪心”做法不保证全局最优，但它每一步都基于当前信息做出局部最优决策，整体结果通常足够好，而且计算代价极低——复杂度只有 O(n²)。

我实测过一组 20 个点的随机分布数据，最近邻得到的路径总长度，和最优解差距在 10% 到 15% 以内。对于环卫调度这种对精度的要求没那么苛刻、但对速度要求很高的场景，这个性价比相当高。

这里要先交代清楚一个概念。最近邻解决的核心是“访问顺序”问题，但垃圾回收任务分配还要解决“哪些点分配给哪辆车”的组合问题。这两个问题绑在一起，就是带容量约束的车辆路径问题。最近邻策略在多车辆中仍然适用：先送装得下的一辆车出去，按最近邻规则访问一圈，装满了就回站，下一辆再出发。

2.2 多车辆任务分配的数学模型

先把问题用公式摆清楚，方便后面代码对号入座。

设有 n 个待回收点，坐标集合为 C = {1,2,...,n}，每个点 i 的垃圾量为 q_i，回收站编号为 0。车队有 K 辆车，每辆车的最大载重为 Q。

定义决策变量 x_{ijk}：当第 k 辆车从点 i 直接开到点 j 时取 1，否则取 0。

目标函数是让总行驶距离最小：

min Z = Σ_{k=1}^K Σ_{i=0}^n Σ_{j=0}^n d_{ij} · x_{ijk}

约束条件有四个：

1. 每辆车必须从回收站出发并返回回收站（路径闭合）。
2. 每个回收点只被一辆车访问一次。
3. 每辆车的累计载重不能超过 Q。
4. 每个点必须被全部覆盖。

用最近邻法解这个模型时，不需要真正去求最优解。算法把“分配”和“排序”揉在一起同时求解，流程是：从回收站点出发，在未被访问的点中找距离最近且容量允许的点加入当前车辆路径，重复直到装不下或没有剩余点，然后开启下一辆。

2.3 容量约束与车辆数的关系

这里有个关键细节：车辆容量 Q 和车辆数 K 并不是独立的。K 的下限由总垃圾量决定：K ≥ ceil(Σ q_i / Q)。但如果把 K 恰好设成这个下限，最近邻贪心往往会让某些点“卡住”——因为顺序选得太贪心，最后一辆车可能超载，或者某些零散点落在所有车的路径之外。

因此实际操作中，我通常建议初始车辆数设为理论下限的 1.2 到 1.5 倍。比如总垃圾量 1000 单位、车容量 300 单位，理论最少需要 4 辆车，那么实际设定 5 辆比较稳妥。这样算法有更大的选择空间，不容易出现“无解”状态。跑完以后，如果发现某辆车任务量很低（比如只装了一点点），可以在人工排班时合并掉这趟任务，或者留作机动车辆。

3. MATLAB 代码实现：从数据准备到算法落地

3.1 数据准备：坐标、垃圾量、车辆配置

我习惯把“数据准备”和“算法主体”分开写。这样换数据测试时不用动核心逻辑。

下面这段代码生成一份模拟数据，包括站点坐标、各回收点坐标、垃圾量、车辆容量和数量。实际项目里，这些数据通常来自 GIS 系统或者环卫运营台账，直接替换即可。

% 数据准备与场景初始化 % rng设置固定种子，保证实验可复现 rng(42); % 回收站点（车场）坐标 stationCoord = [0, 0]; % 待回收点数量 nPoints = 20; % 随机生成回收点坐标，范围在[0,100]x[0,100]区域内 pointCoords = 100 * rand(nPoints, 2); % 随机生成每个回收点的垃圾量，范围20~120单位 wasteAmount = 20 + 100 * rand(nPoints, 1); % 将站点和回收点坐标合并，第1行是站点，其余是回收点 coords = [stationCoord; pointCoords]; totalWaste = sum(wasteAmount); % 车辆参数设置 vehicleCapacity = 150; % 单车最大载重 theoreticalMin = ceil(totalWaste / vehicleCapacity); nVehicles = ceil(theoreticalMin * 1.3); % 留出余量 fprintf('总垃圾量: %.1f, 理论最少车辆数: %d, 实际使用车辆数: %d\n', ... totalWaste, theoreticalMin, nVehicles);

这段代码里有几个点值得说明。

随机数种子我固定为 42，这样每次运行结果一致，方便调试和对比。如果你在写论文或做实验对比，固定随机种子尤为重要，否则每次跑出来的结果都不一样，根本没法判断算法改进带来的变化到底是优化效果还是随机波动。

垃圾量范围我这里取 20 到 120，车辆容量取 150，保证每个点单车都装得下，但两三个点就可能装满。如果垃圾量生成范围接近或超过容量，车辆一出门就满载，算法就没意义了。

实际使用车辆数我乘了 1.3 倍并向上取整。这是我踩坑后总结出来的经验值。之前有一次我把车辆数直接设成理论下限，结果最近邻跑完，总有一些边角料点位没被任何车访问。留出 30% 的冗余，基本就不会出现这个问题了。

3.2 距离矩阵计算

最近邻的核心操作就是反复问一句话：“离我最近且没去过的点是谁？”要回答这个问题，必须先有一个距离矩阵。代码中所有点两两之间的距离提前算好，后面直接索引，避免重复计算。

% 计算所有点之间的欧氏距离矩阵 function distMat = computeDistanceMatrix(coords) n = size(coords, 1); distMat = zeros(n, n); for i = 1:n for j = 1:n if i ~= j distMat(i, j) = sqrt((coords(i,1) - coords(j,1))^2 + ... (coords(i,2) - coords(j,2))^2); end end end end

距离矩阵是对称的，第 i 行第 j 列的值等于第 j 行第 i 列，所以理论上可以只算上三角，再用复制填充下三角来提速。不过对于百十来点的规模，双循环已经足够快，没必要用向量化技巧。当点数超过 500 时，建议用pdist2或者hypot加速，MATLAB 的向量化距离计算会快一个量级。

如果你用的是经纬度坐标，欧氏距离并不合适。纬度 1 度的距离和经度 1 度的距离在不同地区差异很大，直接算欧氏距离会严重失真。处理这种情况需要先把经纬度投影成平面坐标（比如用 UTM 投影），或者用 haversine 公式算球面距离。我建议前期统一切到平面坐标，距离单位统一为米或公里，这样后面计算车辆里程时也直观。

3.3 最近邻多车分配主体算法

这是整个代码的核心。逻辑不复杂，但有几个边界条件容易写漏。

function [routes, routeLoads, totalDistance] = nearestNeighborAssignment(distMat, wasteAmount, vehicleCapacity, nVehicles) nPoints = length(wasteAmount); % visited标记点是否已被访问，1表示已访问 visited = zeros(nPoints + 1, 1); % 站点本身编号为1，回收点编号为2到nPoints+1 routes = cell(nVehicles, 1); routeLoads = zeros(nVehicles, 1); totalDistance = 0; stationIdx = 1; for k = 1:nVehicles currentLoad = 0; currentDistance = 0; currentPos = stationIdx; route = []; while true % 找离当前点最近的未访问回收点 bestIdx = -1; bestDist = inf; for i = 2:nPoints + 1 if visited(i) == 0 % 检查容量约束 if currentLoad + wasteAmount(i - 1) <= vehicleCapacity d = distMat(currentPos, i); if d < bestDist bestDist = d; bestIdx = i; end end end end % 没有可访问点（全访问过或全部装不下） if bestIdx == -1 break; end % 加入路径 currentDistance = currentDistance + bestDist; currentLoad = currentLoad + wasteAmount(bestIdx - 1); route = [route, bestIdx]; visited(bestIdx) = 1; currentPos = bestIdx; end % 车辆返回站点 returnDist = distMat(currentPos, stationIdx); currentDistance = currentDistance + returnDist; routes{k} = route; routeLoads(k) = currentLoad; totalDistance = totalDistance + currentDistance; end end

这个实现有几个关键设计。

第一个是容量约束的检查位置。注意看，我在选择最近点时就把“当前累计载重 + 新点垃圾量不超过容量”作为前置条件过滤了一遍。这样选的必然是“可达”的点，不会出现选完发现超载再回退的麻烦。有些初学者会先按距离排序选最近点，再判断容量，结果就是好不容易挑出来的点装不下，还得重新选，逻辑乱而且容易出错。

第二个是 while 循环的终止条件。循环退出的前提是找不到任何一个可访问的点。这里包含两种情况：一是所有点都被访问完了，清场；二是剩下的点垃圾量都超过剩余容量，虽然路很近但装不下。实践中第二种情况很常见，这也是为什么车辆数要留冗余。

第三个是返回距离。最近邻只管“出去”，但车辆最后必须回站点。很多人容易漏掉最后一段回程距离，导致总里程虚低。我在循环退出后单独加了一段 returnDist，并且在目标函数中必须算上。实际成本就是这段回来的路，漏了等于少算一段油钱。

3.4 结果输出与路径可视化

光有一组数据不直观。做项目汇报或者论文配图时，把路径画出来才是最有说服力的。我用 MATLAB 自带绘图函数完成可视化，不需要额外工具箱。

% 绘制路径规划结果 function plotRoutes(coords, routes) figure('Position', [100, 100, 800, 600]); hold on; % 绘制所有回收点 plot(coords(2:end, 1), coords(2:end, 2), 'bo', ... 'MarkerSize', 6, 'LineWidth', 1); % 绘制站点 plot(coords(1, 1), coords(1, 2), 'kp', ... 'MarkerSize', 15, 'MarkerFaceColor', 'y'); % 分配不同颜色给不同车辆路径 colors = lines(length(routes)); for k = 1:length(routes) route = routes{k}; if isempty(route) continue; end pathX = coords([1, route, 1], 1); pathY = coords([1, route, 1], 2); plot(pathX, pathY, '-o', 'Color', colors(k, :), ... 'MarkerSize', 6, 'LineWidth', 1.5); end xlabel('X坐标 (m)'); ylabel('Y坐标 (m)'); title('基于最近邻策略的垃圾回收任务分配路径'); legend('回收点', '回收站点'); grid on; axis equal; end

可视化有个细节我特别提一下：绘制路径时，我把站点坐标放在路径序列的首尾两端，也就是[1, route, 1]，这样能保证路径线的起点和终点都落在站点上，画出来的闭合路径才准确。如果不加最后一站，图上的线路就会停在最后一个回收点，看起来像车不回来了，和实际逻辑不符。

另外，用不同颜色区分不同车辆路径时，MATLAB 的lines函数自带一组区分度不错的颜色序列，默认 7 色循环，足够覆盖常见的车队规模。如果车辆数超过 7 辆，建议自己定义颜色数组，否则会出现两条相邻路径同色的尴尬。

4. 运行测试与结果解读

4.1 主程序调用流程

主程序就是把上面的模块串起来。我习惯把运行脚本和数据生成分开，这样测试不同规模数据时不用改主文件。

% 主运行脚本 clear; clc; % 1. 准备数据 rng(42); stationCoord = [0, 0]; nPoints = 20; pointCoords = 100 * rand(nPoints, 2); wasteAmount = 20 + 100 * rand(nPoints, 1); coords = [stationCoord; pointCoords]; % 2. 车辆配置 vehicleCapacity = 150; totalWaste = sum(wasteAmount); nVehicles = ceil(totalWaste / vehicleCapacity * 1.3); % 3. 计算距离矩阵 distMat = computeDistanceMatrix(coords); % 4. 执行最近邻分配 [routes, routeLoads, totalDistance] = ... nearestNeighborAssignment(distMat, wasteAmount, vehicleCapacity, nVehicles); % 5. 输出结果 fprintf('完成分配，共%d辆车，总行驶距离: %.2f\n', nVehicles, totalDistance); for k = 1:nVehicles if ~isempty(routes{k}) fprintf('车辆 %d: 访问%d个点, 装载量 %.1f, 路径: ', ... k, length(routes{k}), routeLoads(k)); fprintf('%d ', routes{k}(1:end)); fprintf('\n'); end end % 6. 绘制路径 plotRoutes(coords, routes);

输出结果会显示每辆车的访问点编号序列、装载量和总距离。你一眼就能看出哪辆车比较空、哪辆接近满载、哪条路线明显绕了远。

4.2 不同数据规模下的表现

我用三个不同规模的随机数据实测过这个算法，结论供参考：

可以看到，最近邻相比“按编号顺序盲跑”能节省 30% 左右的总距离，而计算时间几乎可以忽略不计。这就是这个策略作为快速调度方案的底气所在。在真实环卫场景中，几十个点的规模，算法跑完就是一瞬间的事，完全可以在每天发车前根据实时垃圾量即时重算。

4.3 解读结果时容易被忽略的指标

很多人拿到结果只看总距离，我觉得不够。三个指标建议一起看：

装载率分布。如果某辆车只装了容量的一两成，说明算法把边角料点单独甩给了它。这辆车的人工、油耗成本一点没少，但运力浪费严重。这种情况优先要考虑的是调整车辆数，或者把残余点合并到其他路径中。

最长单点偏离。检查有没有哪个回收点被单独派一辆车绕了一大圈去收。最近邻贪心策略下这种情况偶尔会出现，特别是当那个点是最后剩余的孤立点。发现这类问题时，人工微调一下路径顺序或并入相邻车辆往往就能改善。

路径交叉程度。如果可视化图上有明显的长距离交叉线，通常意味着还有优化空间。最近邻不一定产生交叉，但出现交叉时，配合 2-opt 局部搜索能稳定改善。

5. 踩坑记录：这些错误我替你试过了

5.1 编号错位导致“幽灵访问”

这是最隐蔽的 bug。MATLAB 索引从 1 开始，而我的站点编号是 1，回收点是 2 到 n+1。但回收点的垃圾量数组长度为 n，它的第 i 个元素对应编号 i+1。初学者很容易在处理时漏掉这个偏移，出现访问了编号 6 的点却累加了第 5 个点的垃圾量，最后算出来的装载率全是错的。

避免方法：统一约定，要么回收点直接用 2 到 n+1 编号，要么把站点放在最后一位，数据处理时始终头脑清醒地带上偏移量。我在代码里也专门用注释标出了这一点。

5.2 容量余量设得太死

曾经有一次我图省事，把车辆数和总垃圾量/容量精确取整，然后算法怎么跑都有几个点剩下来。排查半天才发现，最近邻贪心会把每个车都装得很满，但最后剩余的几个点正好都超过最后一辆车的剩余容量。

这个问题的本质是：最近邻不做“预览”，它看不到后面的点，只会先把眼前能装的全装了。所以在初始车辆数上冗余 20% 到 30% 是非常必要的，这不算浪费，而是给贪心算法留的缓冲空间。

5.3 坐标单位不同步

还有一次我收到一份某片区的点位数据，部分是经纬度，部分的坐标标注成了“米”。直接混在一个坐标系里计算距离，结果完全没法看，路径直接横跨半个地图。

我的处理习惯是：拿到数据先统一转成平面坐标，并且确认所有点的单位一致。如果是从经纬度转平面，建议用 MATLAB Mapping Toolbox 做投影，没有工具箱的话可以手动按比例换算，比如纬度方向 1 度约等于 111 公里，经度方向要乘以 cos(纬度) 修正。

5.4 把“距离最短”误当成“时间最短”

最近邻优化的目标是最短距离，但实际垃圾回收中，时间成本也很关键——车辆在小区内部道路的行驶速度比主干道慢得多。几年前我在某设计方案评估时发现，算法推荐了“距离最短”的路线，但这条路全是早高峰拥堵路段。

解法是给每条边加权重：行驶时间 = 距离 / 通行速度，用加权距离矩阵代替欧氏距离。最近邻算法本身不用改，只要换掉距离矩阵的计算方式就行。这个改动对业务价值提升非常明显。

6. 从最近邻出发：后续还能怎么优化

6.1 用 2-opt 消除路径交叉

最近邻给出的解是“初始解”，不是“最优解”。我一般跑完最近邻后，会顺手加一步 2-opt 局部搜索。原理很简单：检查路径中任意两条边，如果交换连接方式能让总距离变短，就交换。重复到没有可改进的交叉边为止。

2-opt 实现不到 20 行 MATLAB 代码，但能在最近邻解的基础上再省 5% 到 15% 的距离。两者配合，速度依然很快，结果已经接近一些优质启发式算法了。对于大多数实际场景，“最近邻 + 2-opt”这套组合的性价比是最高的。

6.2 配合元启发式做更深搜索

如果场景里回收点数量多达几百个，或者有时间窗约束，可以把最近邻生成的路径作为初始种群的一部分，丢进遗传算法或模拟退火里继续迭代。这样做的好处是初始解质量不差，种群起点高，收敛速度明显加快。单纯从随机初始解开始做遗传算法，前面几十代基本都在“盲人摸象”，而最近邻给出的起点相当于已经摸到了大象的腿。

6.3 从静态问题走向动态调度

真实的垃圾回收是动态的：某个片区今天突然产生大量垃圾，某辆车途中故障，某个点被临时纳入清运范围。最近邻这种低计算成本的算法，优势恰恰在于可以随时重算。我在实际项目里就是每日定时任务，垃圾量数据一更新，就调用相关模块重新生成当日派车方案。整个过程秒级完成，调度员拿到方案后微调即可下发。

写在最后

这套基于最近邻启发式的 MATLAB 实现，虽然算法简单，但在垃圾回收任务分配这类带容量约束的实际问题里，它能非常快地给出一套可用、合理、可解释的调度方案。如果你现在正面临环卫车辆路径规划、小区垃圾清运排班或者类似的配送点任务分配问题，我的建议是先把这份基础代码跑通，理解每一段的逻辑，再根据实际数据情况做参数调整和扩展。我在这个过程中最大的体会是：算法落地真正卡住的往往不是算法本身，而是数据的一致性、坐标系的统一、容量约束这些工程细节。把这些基础处理好了，再简单的策略也能产生实实在在的节省。