Matlab求解多旅行商问题：遗传算法与2-opt优化实践

简介：面向学习组合优化与智能算法的Matlab用户，这是一份聚焦多旅行商问题（MTSP）的遗传算法实现集合。资源包共7个文件，包含5个zip压缩包（对应mtspofs_ga、mtspf_ga、mtspv_ga、mtsp_ga等多个GA变体）、1个Matlab脚本（mtsp_ga.m）与1个说明文件，整体大小仅25KB，便于快速获取代码框架。描述中详细展示了不同GA版本在数据预处理、种群初始化、遗传算子、适应度函数及防止早熟策略上的差异，适合已有一定TSP基础并希望对比多种求解思路的学习者。目前已有145人学习，通过该资源可快速获得经过修复的MTSP代码与多版本GA实现，辅助理解算法参数调整、收敛性能优化以及局部最优问题的改进方向。

1. 多旅行商问题并不等于 TSP 的简单叠加

先想一个场景：车辆从同一个车场出发，要覆盖几十个客户点。如果一辆车全部跑完，就是经典 TSP；但你手里只有 3 辆车，每辆车访问属于它的客户子集再返回车场，这就变成了多旅行商问题（MTSP）。MTSP 的难点不在“多辆车”，而在于两个决策同时存在：一是把客户点分给哪辆车，二是每辆车内部的访问顺序。两者互相耦合，如果先分区再排序，很容易得到次优解。在 Matlab 里做 MTSP 实验，很多人会搜索到“Matlab多旅行商实验.zip_FIX_MTSP”这类修复版代码包，它能直接跑通一个带约束的 MTSP 实例，但打开后往往不知道怎么改数据、怎么看结果。我按自己的处理流程，从建模、编码、参数调到结果验证，讲一套能在 Matlab 中复现的 MTSP 方案，适合正在做物流调度课程设计、机器人路径规划，或者刚从 TSP 转向 MTSP 的工程师参考。

2. MTSP 建模与 Matlab 求解的算法选型

2.1 MTSP 的数学模型：先写约束，再写目标

用数学语言描述 MTSP，我习惯写成“多车辆、单车场、闭合回路”。假设有 1 个车场（编号 0）和 n 个客户点（编号 1 到 n），共有 m 辆车。每辆车从车场出发，访问若干客户点后回到车场，每个客户点必须被一辆车访问且仅访问一次，目标是最小化所有车辆的总行驶距离。

用一个二维 0-1 变量 x_ij^k 表示第 k 辆车是否从节点 i 直接开到节点 j。目标函数是：

min sum_k sum_i sum_j d_ij * x_ij^k

其中 d_ij 是节点 i 到 j 的距离。约束包括：每个客户点入度出度都等于 1；每辆车的路径是连续的；起点终点都是车场；如果客户点数量少于车辆数，允许部分车辆不出行。实际在 Matlab 里实现时，我不会直接用整数规划去解精确模型，因为 MTSP 是 NP 难问题，客户点超过 20 个时枚举约束就会非常慢。我一般用遗传算法（GA）作为主求解器，配合随机重启来避免陷入局部最优。

下面这个表是我在对比方案时常用的简化对照：

从表里能看出，TSP 只需要排一个序列，MTSP 还要同时决定“哪些点属于哪辆车”。如果客户点分布在几个很独立的簇里，先聚类后 TSP 是可行的；但如果客户点分布均匀，这种两阶段方法就会损失质量。后面我会专门对比这两种思路。

2.2 为什么用遗传算法：染色体能同时编码分组和排序

遗传算法适合 MTSP，根本原因是染色体可以同时承载“分组”和“排序”两层信息。我常用的编码方式是“排列 + 分隔符”：染色体是一个 1 到 n 的随机排列，解码时按分隔符拆成 m 段，每段对应一辆车的访问顺序。这样一条染色体就完整表达了 m 条路径的集合，GA 的交叉和变异只需要作用在这个排列上，逻辑清晰。

下面是一个染色体解码函数，输入随机排列的客户序列，输出每辆车的路径和总距离。注意这是示意代码，实际使用时要根据你的数据格式调整：

function [routes, totalDist] = decodeChromosome(chrom, m, distMatrix) % chrom: 1 x n 的客户点排列，n 为客户点数量 % m: 车辆数 % distMatrix: (n+1) x (n+1) 距离矩阵，第一行/列为车场 n = length(chrom); % 均分：前 m-1 辆车各分配 floor(n/m) 个点，剩余归最后一辆 splits = floor(n/m) * ones(1, m-1); splits(m) = n - sum(splits); routes = cell(1, m); totalDist = 0; idx = 1; for k = 1:m segLen = splits(k); seg = chrom(idx : idx+segLen-1); idx = idx + segLen; routes{k} = [0 seg 0]; % 车场在首尾 for j = 1:segLen+1 totalDist = totalDist + distMatrix(routes{k}(j)+1, routes{k}(j+1)+1); end end end

这段代码把客户点均匀切分到每辆车。注意两个位置：一是distMatrix的下标从 1 开始，而车场编号是 0，所以访问时全部加 1；二是当segLen为 0 时，routes{k}会变成[0 0]，距离累加会重复计算一段 0 长度，虽不报错但会影响统计。FIX 版代码通常会在这里增加空车辆判断，这也是从原始版本升级到修复版后能看到的一个典型变化。实际项目中我不会用均分，而是根据每辆车当前累积距离动态分割，那样更接近最优分配，但初学者先用均分把框架跑通是合理的。

2.2.1 适应度函数与惩罚项怎么写

适应度函数通常取总距离的倒数。为了惩罚非法解，我习惯在总距离上叠加惩罚项，比如客户点重复访问或漏访问，这样 GA 会主动淘汰非法染色体。简单做法是在距离计算函数里统计集合的重复和缺失，给一个很大的惩罚系数，比如总距离的 10 倍。注意惩罚系数不能太大，否则种群会过早收敛到只有惩罚项为零的少数个体，失去多样性。我在实验里经常取 100 作为惩罚基数，然后根据结果微调。

2.3 分区排序联合编码 vs 先聚类后 TSP

常见的简化做法是先用 k-means 把客户点分成 m 簇，然后对每簇单独跑 TSP。这种两阶段法在 Matlab 里很容易实现，但有一个明显缺陷：k-means 只基于位置聚类，没有考虑车辆路径的连贯性，两个簇之间的边界可能交错，导致路径总长度明显增加。而联合编码的 GA 把分组和排序放在同一条染色体上一起进化，理论上能获得更优的折中。

我做过一个对比实验：用随机生成的 30 个点、3 辆车，分别跑“kmeans + TSP”和“联合 GA”，记录总距离。联合 GA 平均比两阶段法低 8% 到 12%。这个数字不是普适定理，但能直观说明问题。如果你在写课程报告，可以用同一组数据跑两种方法，把收敛曲线和路径图画出来做对比，结论会很有说服力。需要说明的是，两阶段法并非全无价值，当客户点天然形成紧凑簇时，它计算更快，稳定性和可解释性也更好。

3. 从“Matlab多旅行商实验.zip”跑通一次 MTSP 实验

3.1 解压后先找这四个关键文件

拿到Matlab多旅行商实验.zip_FIX_MTSP这类压缩包，解压后我不会急着运行，而是先找到四个关键文件：main_MTSP.m入口脚本、distMatrix.m距离矩阵计算、decodeChromosome.m解码函数、plotRoutes.m路径绘图函数。有些码包把功能全部放在一个.m文件里，FIX 版通常会拆成函数，便于逐段调试。

这四个文件的职责可以看下面这个表：

3.2 最小可运行命令：三个参数改到能跑

假设你用的是 FIX 包，进入 Matlab 后先用cd切换到解压目录，然后直接运行入口脚本：

cd('你的解压路径'); main_MTSP

如果一切正常，会弹出路径图。要换成自己的数据，通常需要改三处：第一，客户点坐标矩阵cityXY，它是一份N x 2的数据，N 为客户点数量；第二，车辆数m，注意m必须小于等于N，否则初始化群体时可能出现空路径；第三，算法参数种群大小popSize、最大迭代次数maxGen、交叉概率pc、变异概率pm。下面是一个典型的修改块：

cityXY = load('my_cities.txt'); % 你的客户坐标，两列分别 x, y m = 4; popSize = 200; maxGen = 500; pc = 0.8; pm = 0.1;

这里load读入的是纯文本，如果你的数据是经纬度，需要先转成平面坐标，比如用deg2km之类的函数做墨卡托投影，再计算距离。如果你不想改算法，只想看效果，也可以保留代码自带的随机生成函数，把cityXY换成rand(n,2)*100之类的临时值。注意修改后要重新计算distMatrix，否则解码时矩阵维度对不上。

3.3 遗传算子怎么选：顺序交叉与交换突变

MTSP 染色体本质是一条排列，所以交叉算子不能用二进制 GA 的均匀交叉或单点交叉，那样会产生重复节点的非法染色体。常用的是顺序交叉（OX）和部分映射交叉（PMX）。我一般用 OX，因为它天然保持排列合法性。下面是一个 Matlab 的 OX 实现：

function [child1, child2] = oxCrossover(p1, p2) % p1, p2: 1 x n 的排列，n 为长度 n = length(p1); a = randi([1 n]); b = randi([1 n]); if a > b, t = a; a = b; b = t; end child1 = -1 * ones(1, n); child2 = -1 * ones(1, n); child1(a:b) = p1(a:b); child2(a:b) = p2(a:b); idx = b+1; for i = 1:n j = b + i; if j > n, j = j - n; end if ~ismember(p2(j), child1) child1(idx) = p2(j); idx = idx + 1; if idx > n, idx = 1; end end end idx = b+1; for i = 1:n j = b + i; if j > n, j = j - n; end if ~ismember(p1(j), child2) child2(idx) = p1(j); idx = idx + 1; if idx > n, idx = 1; end end end end

这段代码先随机选两个交叉点a、b，子代先继承父代中被选中的片段，然后从另一个父代中按顺序填补剩余位置。ismember检查元素是否已经出现，从而保证每个客户点只出现一次。参数方面没有额外控制项，但交叉点位置随机性很大，如果a和b靠得太近，产生的子代会和父代非常接近，降低搜索能力。一般建议片段长度不小于染色体长度的三分之一，你可以通过先随机生成a，再取b = a + floor(n/3)的方式来控制。

3.3.1 一个容易踩的坑：初始化时用错 randperm

初始化种群时，正确做法是循环生成多个排列：

pop = zeros(popSize, n); for i = 1:popSize pop(i, :) = randperm(n); end

这里randperm(n)每次调用返回一个 1 到 n 的随机排列，循环popSize次就能得到足够的个体。但如果你写成randperm(n, popSize)，它返回的是从 1 到 n 中随机抽取popSize个不同数字，并不是一个排列，群体里每个个体只有几个数，解码立刻报错。修复版代码通常已经改对，但你自己扩展时很容易犯这个错误。

注意：randperm的第二个参数表示“抽取数量”，除非你需要一个子集，否则不要用在初始化完整染色体上。

3.4 修复版代码常见的三个运行时错误及对策

FIX 包主要修的是三类运行问题，我在调试其他 MTSP 代码时也经常遇到。第一，矩阵维度不匹配：distMatrix大小应为(n+1) x (n+1)，如果代码里节点编号从 0 开始，而 Matlab 矩阵下标从 1 开始，处理不好就会越界。第二，空路径导致 NaN：均分时如果剩余客户点不够分，最后一辆车可能分到 0 个点，计算距离时出现 0/0。第三，绘图时数组下标不对：原始代码直接用plot(x(r), y(r))，但r里包含车场编号 0，而数组下标不能是 0。修复版通常会把路径绘制函数单独封装。

下面这个表总结了常见错误和处理方式：

如果你运行后看到类似Index exceeds matrix dimensions，先检查距离矩阵是多少行多少列，再检查解码函数里的节点索引。加一个assert(size(distMatrix,1) == n+1, '距离矩阵维度错误')，能帮你快速定位。

4. 结果怎么读：从收敛曲线到路径约束的验证

4.1 绘制路径图看车流是否分散

跑完算法后，不能只看总距离数字，先画图检查路径是否合理。下面这个函数用不同颜色绘制每辆车的路径：

function plotRoutes(routes, cityXY) figure; hold on; cmap = lines(length(routes)); for k = 1:length(routes) r = routes{k}; plot(cityXY(r+1,1), cityXY(r+1,2), 'o-', 'Color', cmap(k,:), 'LineWidth', 1.5); end plot(cityXY(1,1), cityXY(1,2), 'ks', 'MarkerSize', 10, 'MarkerFaceColor', 'k'); hold off; end

这里的routes{k}是解码后的路径，包含车场 0 和客户点。cityXY(r+1,:)是因为车场在坐标矩阵第一行，所有节点下标加 1。颜色用lines函数自动区分车辆。如果发现两条不同颜色的路径交叉非常严重，说明分组不太合理，可以增加迭代次数或适当提高变异概率。注意图中车场用黑色方块标记，不要和客户点混淆。

4.2 验证约束的三行断言

在实验报告中，证明结果有效性的一个技巧是加自动断言。下面这三行代码能发现重复访问、漏访问等常见问题：

allVisited = sort(unique([routes{:}])); assert(allVisited(1) == 0, '车场必须出现在路径中'); assert(length(allVisited) == n+1, '访问节点数不对'); assert(isequal(sort(allVisited(2:end)), 1:n), '存在重复或遗漏客户点');

第一行把所有路径的节点合并、去重、排序，得到实际访问过的节点列表。第二行检查列表第一个元素是不是 0，保证车场在路径里。第三行检查除车场外的节点是否正好覆盖 1 到 n。如果断言失败，说明解码或遗传操作破坏了染色体的合法性。修复版代码一般会在绘图前执行这三行验证，你可以在自己的脚本里也加上。

4.3 收敛曲线：判断是否早熟

GA 跑完后，我习惯记录每一代的最优距离和平均距离，绘制成收敛曲线。这个图能判断算法是否过早陷入局部最优。画图代码很简单：

plot(1:maxGen, bestHistory, 'b-', 1:maxGen, avgHistory, 'r--'); xlabel('迭代次数'); ylabel('总距离'); legend('最优距离','平均距离'); grid on;

参数说明：bestHistory是每个迭代步历史中最小的总距离，avgHistory是所有个体距离的均值。如果最优曲线在 100 代内就变平，同时平均曲线也很快靠下来，说明种群多样性不足，容易早熟。这时可以增大变异概率，或者把精英保留数量调小，给种群更多探索空间。

4.3.1 用多个随机种子测稳定性

单次运行有随机性，实验结论不能只跑一次。我会用rng控制随机种子，连续跑 10 次，统计最优值、平均值和标准差：

numRuns = 10; results = zeros(1, numRuns); for s = 1:numRuns rng(s); [best, ~] = runMTSP(cityXY, m, popSize, maxGen); results(s) = best; end fprintf('mean=%.2f, std=%.2f, best=%.2f\n', mean(results), std(results), min(results));

这里的runMTSP是把主流程封装好的函数，内部每次独立初始化种群。如果标准差超过平均值的 5%，说明参数设置偏敏感，需要调整变异概率或增加种群规模。下表是常见参数调整方向：

5. 让 MTSP 实验更快：并行计算与 2-opt 局部精炼

5.1 用 parfor 并行评估适应度

当客户点数量超过 50，适应度评估会成为整个 GA 的瓶颈。Matlab 的parfor可以让多个个体同时计算适应度，前提是适应度函数只依赖当前个体和只读参数。下面是一个示例：

parpool('local', 4); % 启用 4 核并行 fitnessValues = zeros(popSize, 1); parfor i = 1:popSize fitnessValues(i) = fitnessFunction(pop(i,:), m, distMatrix); end delete(gcp('nocreate')); % 释放并行池

这里的fitnessFunction是独立的函数，内部只读取pop(i,:)、m和distMatrix，不会修改其他变量，所以适合并行。注意parfor要求循环体内不能对pop等外部变量做写操作，迭代之间不能有依赖。并行池大小根据机器核数设置，4 核已经能带来明显加速，但启动并行池本身有开销，如果种群只有 50 个个体，可能反而更慢，建议在popSize大于 200 时再使用。

5.2 用 2-opt 对最终解做一次精炼

遗传算法结束后的解往往还有局部改进空间，最常见的是 2-opt：取一条路径中的两条边，反转中间的一段，看总距离是否下降。下面是一个针对单条路径的 2-opt 实现：

function route = twoOpt(route, distMatrix) improved = true; while improved improved = false; for i = 2:length(route)-2 for j = i+1:length(route)-1 newRoute = route; newRoute(i:j) = fliplr(route(i:j)); delta = calcDist(route, distMatrix) - calcDist(newRoute, distMatrix); if delta > 0 route = newRoute; improved = true; end end end end end

这段代码从路径第二个点开始到倒数第二个点，逐对尝试反转。fliplr是 Matlab 自带的反转函数。注意i从 2 开始，避免把车场位置也反转；j最大取到length(route)-1，保证路径首尾仍然是车场。calcDist是计算一条路径总距离的辅助函数。2-opt 的复杂度是 O(L^2)，其中 L 是每个客户点数量，只对最终解跑一次，不会花太多时间。它对消除路径交叉很有效，通常能让总距离再下降 5% 到 10%。

在实际工程中，我会把 2-opt 放在 GA 结束后，对每辆车的路径分别调用一次，然后合并总距离。如果你想追求更稳定的结果，可以在 GA 的每一代里对最优个体做一次轻量 2-opt，但那样会显著增加耗时。更实用的做法是保存每一代精英，最终从精英池里选几个候选解做 2-opt 精炼，再取其中最好的。

最后补充一个操作细节：当你把上述所有代码整合成一个完整脚本时，注意把routes以 cell 数组的形式传递给plotRoutes，不要在循环里用普通数组反复覆盖路径结构，否则画图时不同车辆的数据会互相混叠。

本文还有配套的精品资源，点击获取