简介面向学习组合优化与智能算法的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作为主求解器配合随机重启来避免陷入局部最优。下面这个表是我在对比方案时常用的简化对照维度TSPMTSP决策变量一条路径的访问顺序客户点分组 各组内路径顺序约束每个点一次一条闭合回路每个点一次m 条闭合回路求解难度NP 难NP 难且分组和排序互相影响常见解法LKH、GA、模拟退火先聚类后 TSP或联合编码 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: (n1) x (n1) 距离矩阵第一行/列为车场 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 : idxsegLen-1); idx idx segLen; routes{k} [0 seg 0]; % 车场在首尾 for j 1:segLen1 totalDist totalDist distMatrix(routes{k}(j)1, routes{k}(j1)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 版通常会拆成函数便于逐段调试。这四个文件的职责可以看下面这个表文件作用运行时可能出现的错误main_MTSP.m加载数据、设置参数、调用算法变量名冲突、路径未设置distMatrix.m计算欧氏距离矩阵输入维度不对、未考虑车场节点decodeChromosome.m把染色体拆成多车路径数组越界、空路径plotRoutes.m绘制多车路径图索引从 0 开始导致下标错误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 b1; 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 b1; 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大小应为(n1) x (n1)如果代码里节点编号从 0 开始而 Matlab 矩阵下标从 1 开始处理不好就会越界。第二空路径导致 NaN均分时如果剩余客户点不够分最后一辆车可能分到 0 个点计算距离时出现 0/0。第三绘图时数组下标不对原始代码直接用plot(x(r), y(r))但r里包含车场编号 0而数组下标不能是 0。修复版通常会把路径绘制函数单独封装。下面这个表总结了常见错误和处理方式错误现象典型原因处理方式Index exceeds array bounds编号从 0 开始但矩阵下标从 1 开始统一加 1用idx1访问NaN 出现在总距离里空车辆路径或均分 splits 出现 0增加空路径判断Undefined function main当前路径未包含函数文件使用addpath或cd到解压目录如果你运行后看到类似Index exceeds matrix dimensions先检查距离矩阵是多少行多少列再检查解码函数里的节点索引。加一个assert(size(distMatrix,1) n1, 距离矩阵维度错误)能帮你快速定位。4. 结果怎么读从收敛曲线到路径约束的验证4.1 绘制路径图看车流是否分散跑完算法后不能只看总距离数字先画图检查路径是否合理。下面这个函数用不同颜色绘制每辆车的路径function plotRoutes(routes, cityXY) figure; hold on; cmap lines(length(routes)); for k 1:length(routes) r routes{k}; plot(cityXY(r1,1), cityXY(r1,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(r1,:)是因为车场在坐标矩阵第一行所有节点下标加 1。颜色用lines函数自动区分车辆。如果发现两条不同颜色的路径交叉非常严重说明分组不太合理可以增加迭代次数或适当提高变异概率。注意图中车场用黑色方块标记不要和客户点混淆。4.2 验证约束的三行断言在实验报告中证明结果有效性的一个技巧是加自动断言。下面这三行代码能发现重复访问、漏访问等常见问题allVisited sort(unique([routes{:}])); assert(allVisited(1) 0, 车场必须出现在路径中); assert(length(allVisited) n1, 访问节点数不对); 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%说明参数设置偏敏感需要调整变异概率或增加种群规模。下表是常见参数调整方向现象调整方向收敛过快且结果差增大popSize或pm收敛太慢运行时间长减小popSize或增大pc最优与平均之间差距大增加精英保留比例多次运行结果波动大固定随机种子并增加maxGen5. 让 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 i1: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不要在循环里用普通数组反复覆盖路径结构否则画图时不同车辆的数据会互相混叠。本文还有配套的精品资源点击获取