简介：这是一份基于MATLAB的节约里程法（节约算法）例程包，面向物流配送、车辆路径规划（VRP）问题的学习者与算法入门者。资源仅2个文件，由1个m脚本（核心算法与主程序）和1个xlsx数据文件（客户坐标与需求量）组成，压缩包只有63KB，轻量易上手。例程系统覆盖数据预处理、初始路线生成、节约值计算、迭代优化与结果输出等完整环节，并借助MATLAB矩阵运算和绘图功能直观展示各车辆行驶路径，便于对照理解每次合并路线的距离节省。通过运行主程序，可逐行读懂节约算法的实现逻辑，利用示例数据快速验证，也可替换为自己的客户坐标和需求量进行扩展演练，甚至在此基础上向带时间窗VRPTW、多容量车辆等变种延伸。目前已有319人学习浏览，适合物流工程、运筹优化方向的初学者，以及希望用MATLAB动手实现启发式算法的开发者。
1. 节约里程法：一个贪心算法凭什么仍被当成车辆路径问题的课代表
我第一次在《物流系统规划》课程里看到节约里程法时，觉得这名字听起来绕口，算法逻辑却简单得不像话——按“合并两条配送路线能省多少路程”从大到小一路合下去，本质上是个贪心。后来真正要交一个 matlab 例程作业，四处找压缩包里的代码时才发现，值得注意的从来不是那个公式，而是数据怎么往代码里塞、容量约束怎么判断、路线用什么结构维护。这些细节才是从纸面定理变成能跑通脚本的分水岭。节约里程法至今仍是很多商用运输管理系统生成初始解的算法，也在车辆路径问题和运筹学课程里占着固定位置。本文不猜任何现成压缩包里的内容，只按最常见、最可靠的一套做法，给你一份从读取客户坐标、计算节约值矩阵、并行合并路径到绘制配送路线的完整 matlab 例程，并把参数怎么改、失败时先看哪里一次讲透。
2. 节约里程法的核心：距离矩阵、节约值排序与两种合并策略
实现节约里程法表面上是写合并循环，真正决定代码质量的是三件事：距离矩阵怎么组织、节约值怎么排序、合并时用顺序扫描还是并行扫描。下面把这三件事分开说清。
2.1 距离矩阵为什么必须以配送中心为第 1 行
绝大多数初写节约里程法例程的人，都会先在“距离矩阵怎么构造”上栽跟头。节约里程法的输入不是客户坐标，而是配送中心与客户两两之间的最短路程。配送中心在公式里是基准点，不能把客户坐标矩阵直接拿去做距离计算后就开循环，中心点必须占住一个固定索引位。
常见做法是把配送中心编成 0 号点，客户从 1 编到 n，完整距离矩阵大小为 (n+1)×(n+1)。下面是构造它的最小 matlab 代码：
center = [50, 50]; % 配送中心坐标 coords = center + randn(20, 2) * 10; % 20个客户坐标，围绕中心生成 n = size(coords, 1); allPts = [center; coords]; % 第1行是配送中心 D = zeros(n+1, n+1); for i = 1:n+1 for j = i+1:n+1 D(i,j) = norm(allPts(i,:) - allPts(j,:)); D(j,i) = D(i,j); end end这段代码里D(i+1,1)就是客户 i 到中心的距离，D(i+1,j+1)是客户 i 到客户 j 的距离。为什么不用pdist2？因为pdist2默认只算客户之间，中心点不在距离矩阵里，后面所有索引都要位移一次，容易乱。把中心放在第 1 行，合并循环里对路径做距离累加时，直接按route(1:end-1)+1取索引，能少写很多调试时间。
提示：如果实际业务用的是路网距离而不是直线距离，这里需要替换成弗洛伊德或 Dijkstra 算出的最短路径矩阵，但矩阵结构和索引逻辑不变。
2.2 节约值矩阵 S(i,j) 与排序列表的三列结构
节约值的定义是：如果把客户 i 和客户 j 分别用两辆车单独配送，总路程是 d(i,0)+d(0,j)。如果合并到同一辆车，直接走 i 到 j，总路程变为 d(i,0)+d(0,j)-d(i,j)。后面的 d(i,j) 就是被“省下来”的那段路程，也就是节约值：
S = zeros(n, n); for i = 1:n for j = i+1:n S(i,j) = D(i+1,1) + D(1,j+1) - D(i+1,j+1); S(j,i) = S(i,j); end end sv = []; for i = 1:n for j = i+1:n sv = [sv; S(i,j), i, j]; % 每行：节约值、客户i、客户j end end sv = sortrows(sv, -1); % 按第一列降序sv是三列结构：第一列是节约值，第二、三列是客户编号。后面做并行合并时，逐个取sv的行判断能否合并即可。sortrows(sv,-1)表示只对第一列降序，后两列仍按升序，这样节约值相同的候选对会优先选编号小的客户，保持输出稳定。
2.3 顺序式与并行式：matlab 例程里选哪一种合并
合并有两种扫描方式。顺序式先挑一条最大节约值路线，不断向它加客户，直到满载或无法再加入，再换下一条；并行式则是对所有路线同时扫描，每次从全局最大节约值开始判断。两者结果差异明显：
| 特征 | 顺序扫描 | 并行扫描 |
|---|---|---|
| 路线构造方式 | 一条路线扩展到饱和再取下一条 | 所有路线同时争抢客户 |
| 结果倾向 | 路线数偏多、单条路线偏短 | 总里程更低、路线数偏少 |
| matlab 实现 | 需要 while 内层循环，逻辑更绕 | for 遍历节约值列表即可 |
| 适用场景 | 车辆数量紧张，想尽量少出车 | 车辆充足，追求总行驶里程最小 |
我一般写例程默认用并行扫描，因为它的循环结构和上面排好序的sv列表天然匹配，逻辑也直观。下面一章的完整例程就是并行方式。
3. 可运行的 matlab 例程：从坐标输入、容量约束到路径绘制
这一章给一份在 R2016b 及以上版本都能直接跑的完整脚本，包含了随机数据生成、节约值计算、并行合并、容量检查和最终输出。把坐标和需求量换成你的真实数据就能用于小规模问题。
3.1 主脚本 saving_main.m：最小实现
%% saving_main.m % 节约里程法（并行扫描）matlab 例程 clc; clear; close all; % ---------- 1. 数据准备 ---------- center = [50, 50]; % 配送中心坐标 rng(1); % 固定随机种子，便于结果复现 n = 20; % 客户数 coords = center + randn(n, 2) * 10; % 客户坐标 demand = randi([1, 8], n, 1); % 每个客户需求量 capacity = 40; % 单车最大载重 allPts = [center; coords]; D = zeros(n+1, n+1); for i = 1:n+1 for j = i+1:n+1 D(i,j) = norm(allPts(i,:) - allPts(j,:)); D(j,i) = D(i,j); end end % ---------- 2. 计算节约值并排序 ---------- S = zeros(n, n); for i = 1:n for j = i+1:n S(i,j) = D(i+1,1) + D(1,j+1) - D(i+1,j+1); S(j,i) = S(i,j); end end sv = []; for i = 1:n for j = i+1:n sv = [sv; S(i,j), i, j]; end end sv = sortrows(sv, -1); % ---------- 3. 初始化：每个客户单独一条路线 ---------- routes = num2cell(1:n); % 每个cell是一条路线，初始只装一个客户 loads = demand(:)'; % 每条路线的累计载重 % ---------- 4. 并行合并 ---------- for k = 1:size(sv, 1) i = sv(k, 2); j = sv(k, 3); if sv(k, 1) <= 0 continue; % 节约值为负，合并反而增加里程 end posI = find(cellfun(@(r) ismember(i, r), routes)); posJ = find(cellfun(@(r) ismember(j, r), routes)); if isempty(posI) || isempty(posJ) || posI == posJ continue; % 两客户已在同一路线或已被合并掉 end ri = routes{posI}; rj = routes{posJ}; if ~(ri(1) == i || ri(end) == i) continue; % i 必须是所在路线的端点 end if ~(rj(1) == j || rj(end) == j) continue; % j 必须是所在路线的端点 end if loads(posI) + loads(posJ) > capacity continue; % 容量约束 end % 将 i 翻转到 ri 末尾，将 j 翻转到 rj 开头，再拼接 if ri(1) == i ri = fliplr(ri); end if rj(end) == j rj = fliplr(rj); end routes{posI} = [ri, rj]; loads(posI) = loads(posI) + loads(posJ); routes{posJ} = []; % 原 posJ 路线被合并进 posI end % 删除空路线 routes(cellfun(@isempty, routes)) = []; % ---------- 5. 输出结果 ---------- for r = 1:length(routes) routes{r} = [0, routes{r}, 0]; % 首尾补配送中心 end totalDist = 0; for r = 1:length(routes) fprintf('车辆%d: ', r); fprintf('%d ', routes{r}); fprintf(' 载重%.0f\n', sum(demand(routes{r}(2:end-1)))); for seg = 1:length(routes{r}) - 1 totalDist = totalDist + D(routes{r}(seg)+1, routes{r}(seg+1)+1); end end fprintf('总行驶里程: %.2f\n', totalDist);num2cell(1:n)生成{1},{2},...,{n}，每个 cell 是独立路线；loads与routes一一对应，这样判断容量时不用重新累加路线需求。合并循环里先做位置查找，再做端点判断和容量判断，三个条件任意不满足就跳过该候选对，这是并行扫描的标准写法。
端点条件为什么要单独判断？因为节约值只是“局部看两点合并省里程”，但实际路径是有方向性的，路线只能从两端接出去。如果客户 i 在路线中间，合并后 i 就变成“三叉路口”，车辆无法按一条直线走完。
3.2 容量约束和端点条件是怎么被验证的
上面的脚本里，容量判断只有一行：loads(posI) + loads(posJ) > capacity。这里需要注意loads必须始终与routes同步更新。初始loads = demand(:)'，每次合并后，把被合并路线的载重加到loads(posI)，而loads(posJ)不再参与后续比较。有些例程只在最后计算载重，合并过程中不维护，结果会漏掉还没被合并但已经超载的组合。
端点判断的逻辑是：客户 i 必须在它所在路线的首或尾，客户 j 同理。若两者都在端点，通过翻转ri和rj总能让路径变成“i 在 ri 尾部、j 在 rj 头部”，最后直接拼接，中间就是节约值公式里的 i→j 边：
if ri(1) == i ri = fliplr(ri); end if rj(end) == j rj = fliplr(rj); end注意fliplr反转的是一个向量，在 R2016b 以后可以直接操作 cell 内的向量。反转后再拼接，路径在逻辑上等价于“车从中心出发，沿着 ri 走到 i，再从 i 开到 j，沿着 rj 回到中心”，没有产生任何需要折返的断点。
3.3 画路径图：判断结果有没有绕路的最快方式
文字输出只能看到路线序列，看不出几何形状。画图是评估节约里程法结果最直观的手段，特别是检查有没有两条路线交叉、某个客户是否被单独扔在外面。
figure; hold on; grid on; axis equal; plot(center(1), center(2), 'kp', 'MarkerSize', 14, 'MarkerFaceColor', 'k'); plot(coords(:,1), coords(:,2), 'bo', 'MarkerSize', 7); for k = 1:n text(coords(k,1)+1, coords(k,2)+1, num2str(k), 'FontSize', 8); end cols = lines(length(routes)); for r = 1:length(routes) x = allPts(routes{r}+1, 1); y = allPts(routes{r}+1, 2); plot(x, y, '-o', 'Color', cols(r,:), 'LineWidth', 1.6); end xlabel('X 坐标'); ylabel('Y 坐标'); title('节约里程法 matlab 例程 -- 车辆路径结果');allPts(routes{r}+1, :)是把含 0 的路线映射到坐标矩阵：0 对应配送中心，1 对应第一个客户。图中黑色方块是配送中心，彩色线条是不同车辆路径。运行后如果发现两条线路交叉明显，基本可以判断是排序键或合并策略需要调；如果某个客户单独成线，说明它的节约值没能超过容量或端点限制，这类客户在现实中往往需要专车。
4. 例程排错三件事与 2-opt 改良
代码能跑通只是第一步，节约里程法例程真正折磨人的是结果“看起来合理但不够好”。最后一章只讲我最常遇到的三个问题和一种立竿见影的改良手段。
4.1 索引、单位、排序键：例程跑偏的三大来源
第一，索引错位。D(i+1,1)与coords(i,:)之间的对应关系一旦写错，节约值全部偏一位，最终路线会在客户编号上“串位”。排错方法是在合并循环前打印D(2,1)和norm(coords(1,:) - center)是否相等。
第二，单位不一致。坐标用米，需求量用箱，但车辆里程限制可能用公里。例程里D是坐标直接算的欧氏距离，如果实际限制是 50 公里，坐标却是经纬度差值，容量判断没问题，路线可行性判断就会全部失真。
第三，排序键。默认按节约值降序在多数数据上没问题，但遇到客户沿主干道分布的场景，并行扫描容易把“近距离、方向相反”的两条路线先合并，造成回头路。此时把排序键改成优先合并离中心更远的客户，效果更好。实现很简单，排序前对sv减一个带中心距离的小量：
centerDist = D(2:end, 1); w = 0.3; % 权重，一般取 0.2~0.5 sv(:,1) = sv(:,1) + w * (centerDist(sv(:,2)) + centerDist(sv(:,3)));4.2 用 2-opt 把例程结果再拧直一圈
节约里程法合并完的路线，常常存在局部绕路：[0, 2, 5, 3, 0]中 5→3 之间如果绕了个锐角，2-opt 能暴力找出反转哪一段能缩短总里程。思路是枚举一条路径内部任意连续区段，反转后计算新路径长度，若更短就保留。对每辆车循环执行到不再变化即可：
function L = pathLen(D, rt) L = 0; for s = 1:length(rt) - 1 L = L + D(rt(s) + 1, rt(s + 1) + 1); end end for r = 1:length(routes) rt = routes{r}; improved = true; while improved improved = false; for a = 2:length(rt) - 2 for b = a + 1:length(rt) - 1 newRt = [rt(1:a-1), fliplr(rt(a:b)), rt(b+1:end)]; if pathLen(D, newRt) < pathLen(D, rt) - 1e-6 rt = newRt; improved = true; end end end end routes{r} = rt; endpathLen是局部函数，放在脚本末尾，R2016b 之后的 matlab 支持在脚本内定义局部函数。循环里a、b都在去掉首尾 0 的区间内活动，避免把配送中心反转进路线中间。2-opt 在这里是纯后处理，不改动节约里程法本身，但通常能把总里程再压掉 5% 到 15%。
实际应用中，时间窗约束可以在合并前单独判断“到达时间是否落在客户允许窗口内”，多车型问题则先按容量大的车型做节约里程法，剩余客户再跑一轮。这些扩展都不需要改动第 3 章例程的总体结构，只往合并条件里加判断即可。
本文还有配套的精品资源，点击获取
