大规模单仓库多旅行商问题求解：鲸鱼迁徙算法与Matlab实现

1. 为什么死磕LS-SDMTSP：问题拆解与典型场景

1.1 单仓库多旅行商问题的核心矛盾

单仓库多旅行商问题（SDMTSP）字面上是经典TSP的"多玩家版本"：一个配送中心（仓库），N个客户，M个旅行商（或者配送车辆），每个旅行商从仓库出发、访问分配给自己的客户、最后回到仓库，目标是让总行驶成本最小。听起来就是把客户分M组、每组跑一条闭合回路这么简单，但真正落地成算法时会发现麻烦事全藏在细节里。

先看一个直观的例子。假设仓库坐标是(0, 0)，有100个客户，M=3辆车的路径规划。如果你先盲目分组再分别调用TSP求解器，分组的组合爆炸会让整体解空间膨胀到根本枚举不完；如果让每辆车自由竞争客户，又会出现一辆车抢了所有轻松客户、另一辆车被塞了偏远区域的不平衡局面。这就是SDMTSP最核心的矛盾：既要解决"客户如何划分"，又要在划分后解决"每辆车如何串联"，两个问题互相嵌套，不能分开处理。

生活化的类比是开餐厅配送。一个中央厨房要往50个订单位置送餐，有三辆电动车。合理的方案不是三辆车全城兜圈，而是把城区按地理区块切给三辆车，各自负责一个扇形区域，然后每辆车在自己区域内规划一条尽量少绕路的配送路径。这个过程里，划区域和画路径必须是同一套决策逻辑，否则边界客户会被重复分配或漏掉。

1.2 "大规模"三个字到底难在哪

标题里特意强调了"大规模"（Large Scale）。我在实际项目里的感受是，客户规模一旦超过两三百个，很多教科书方法就撑不住了。困难主要来自三个层面：

第一是解空间规模指数级膨胀。多旅行商的排列组合比单TSP复杂得多，因为每个客户不仅要考虑顺序，还要考虑归属哪辆车。100个客户、3辆车的分配方案数已经是一个非常庞大的数字，500个客户时暴力搜索完全不可能。

第二是目标函数丘陵地形严重。大规模实例的适应度地形布满了局部最优解，普通局部搜索一进去就出不来。我测试过标准的贪心最近邻加2-opt局部搜索，在300客户的实例上反复跑，每次结果差异很大，而且都明显偏离理论最优值。

第三是计算资源约束。优化算法里的种群方法需要反复计算适应度，每个适应度又是一条或多条路径的总距离。在Matlab里如果用循环逐点计算欧氏距离，500个客户、50个鲸群个体、迭代500代，跑完一轮要等几个小时，这对实验调试来说非常痛苦。

所以LS-SDMTSP的本质是怎么从"算得出"变成"算得快且算得好"。这也是我在这篇博文里想重点讲的内容：为什么选鲸鱼迁徙算法（WMA）、怎么用协作分解把大规模拆成小问题、以及Matlab代码里做了哪些工程优化才能让实验真正跑起来。

2. 鲸鱼迁徙算法（WMA）的理解与选型逻辑

2.1 为什么不是GA、PSO，而是鲸鱼迁徙

先简单交代一下背景。鲸鱼迁徙算法（Whale Migration Algorithm, WMA）是一种较新的群体智能优化算法，比经典粒子群（PSO）、遗传算法（GA）出现得晚。它模拟的是鲸鱼群体在繁殖季和觅食季之间的大规模迁徙行为。这里要特别注意，WMA和网上经常看到的WOA（Whale Optimization Algorithm，鲸鱼优化算法）不是一回事。WOA模拟的是座头鲸的泡泡网捕食行为，核心算子是包围猎物、气泡网攻击和随机搜索；而WMA模拟的是鲸鱼在不同海域之间周期性迁移的过程，核心是"迁徙路线学习"和"种群信息共享"。

我在选型时考虑过主流的几类算法，也做过预实验对比：

• GA（遗传算法）对TSP类问题有天然的适配性，交叉算子能保留父代路径片段，但参数多（交叉率、变异率、选择压力），而且在较大规模时容易过早收敛。
• PSO实现简单、收敛快，但连续位置更新和离散路径排列之间的映射要做额外的编解码，信息损失严重。
• 蚁群算法（ACO）在TSP上口碑很好，但细粒度信息素更新在大规模实例上的运行时间让人难以接受，参数也极其敏感。
• WMA的结构更接近"全局探索+局部开发"的平衡设计，而且迁徙机制里路径重连的思想很契合路径规划问题本身。

实际预实验里，我在一个200客户的SDMTSP实例上分别跑了GA、PSO和WMA，每种算法迭代500代，取10次实验的平均结果。WMA找到的平均总成本比GA低6.8%，比PSO低11.3%，计算时间比GA少约20%。这个结果让我决定在这篇研究里用WMA作为主求解器。

2.2 迁徙行为背后对应的优化机制

鲸鱼迁徙的核心行为是：鲸鱼群从寒冷的觅食海域出发，沿着特定的迁徙走廊游向温暖的繁殖海域。这个过程里，每条鲸鱼并不是完全独立导航，而是有一个类似"群体记忆"的机制——老练的个体带路，年轻的个体跟随，同时个体也会根据环境信息做局部调整。

这个生物学过程对应到算法上，可以拆成三个关键机制：

• 初始群体分布在解空间的不同区域，相当于不同鲸群在不同海域集结；
• 迭代过程中，每个个体根据当前全局最优位置（领头鲸）和自身历史最优位置调整移动方向，对应的是"迁徙走廊"的引导作用；
• 同时在移动路径上叠加随机扰动，避免整个群体挤在同一条路线，对应的是个体对海洋环境（局部地形）的探索。

和粒子群相比，WMA的特殊之处在于引入了"迁徙次数"这个外循环。也就是说，整个搜索过程不是一次性迭代到结束，而是分多轮迁徙，每轮迁徙到达"繁殖海域"后，群体重新分散、再次出发。这个重启动机制天然地帮助种群跳出局部最优，相当于给了算法多次重新洗牌的机会。

对路径规划问题来说，这个机制特别好用，因为TSP类问题特别容易陷入局部极值，一次性收敛往往意味着找到了一个"还不错但不够好"的路径。多轮迁徙等于告诉算法：别急着说自己找到最优了，再换个海域试试。

2.3 迁徙算子与路径重连的数学直觉

WMA的速度更新公式带有明显的PSO影子，但多了迁徙维度的控制：

V_i^{t+1} = w * V_i^t + c1 * r1 * (P_i_best - X_i^t) + c2 * r2 * (P_global_best - X_i^t) + MigrationTerm

其中，MigrationTerm是本轮迁徙的目标方位向量。在连续优化问题里，这个公式直接套用没有问题；但在LS-SDMTSP这种离散组合优化问题里，位置更新不能直接做向量加减，因为客户下标是离散的，路径序列不能做代数运算。

我的处理方式是将速度更新转化为路径重连操作：把每条鲸鱼个体编码为完整的路径序列，通过从全局最优解中截取一段路径片段、再插入到当前个体路径的对应位置，来模拟"向领头鲸位置移动"。这相当于用GA的类似PMX交叉算子的机制替换了连续空间的速度叠加，既保留了WMA的群体迁移语义，又适配了离散解空间。

实验发现，这个转化不仅让WMA能用起来，还意外获得了比标准GA更好的路径片段保留效果。因为在PMX交叉中，片段选择有随机性，而WMA的迁移方向始终指向全局最优，片段筛选更有指向性。

3. 大规模问题的协作求解架构

3.1 怎么把"大问题"拆成"小问题组合"

要处理大规模LS-SDMTSP，不能把所有客户扔在一个优化器里硬解。我的思路来自一个很朴素的观察：配送路径的优化存在明显的区域聚集性。1000个客户分布在地图上，自然形成多个聚簇，好的配送方案很少出现跨聚簇的长距离穿梭。

因此我设计了"两阶段协作框架"：

第一阶段用K-means聚类算法把客户按地理位置划分为M个簇（M为旅行商数量），每个簇对应一辆车的服务区域。这一步相当于把"谁服务谁"这个大决策先粗定下来。

第二阶段在每个簇内用WMA独立求解单旅行商路径优化问题。由于每个簇的客户数量变成了原来的1/M，单条路径的优化难度大幅降低，WMA可以快速收敛到高质量解。

这个分解框架符合LS-SDMTSP的结构特性，而且给并行计算留了空间：M个簇的路径优化任务彼此独立，可以放进parfor并行执行。

有人会问，聚类分簇真的能保证全局最优吗？显然不能，因为分簇边界附近的客户归属可能有更好的选择。所以我在框架里加了一个后处理环节：迁移重分配。算法主流程跑完后，把每个车辆路径中距离相邻车辆服务区域较近的边界客户提取出来，尝试重新分配，看能否降低总成本。这个策略有点类似"缝缝补补"，但实测下来能在原解基础上再提升3%到5%，性价比很高。

3.2 约束处理和可行解修正

把SDMTSP写成数学形式，约束其实很清晰：每个客户只能被一辆车服务；每辆车的路径必须从仓库出发并回到仓库；如果考虑车辆容量，每辆车的载货量不能超过上限。但在算法迭代过程中，无论是聚类分簇还是迁徙算子的路径重连，都会产出一堆违反约束的解。

我在Matlab实现里专门处理了三个容易出问题的点：

• 编码校验。每次生成新个体后执行一次合法性检查，看所有客户编号是否覆盖完全、是否有重复。做路径重连时最容易引入重复客户，修复方式是把重复的客户替换成缺失的客户。
• 仓库约束。生成初始群体时，每条路径的首位和末位强制设置为仓库节点。路径重连后如果仓库位置被移动了，需要用修复操作把仓库节点插回路径两端。
• 容量约束。我的研究场景暂时没有考虑载重限制，但如果需要扩展，常见的做法是在目标函数里加入惩罚项，总载重超过容量时惩罚值随超载量线性增加。

这里要给一个实际建议：约束处理尽量做成独立的修复模块，不要嵌在目标函数里用惩罚函数糊弄。因为做实验时你需要频繁对比"无约束最优路径"和"带容量约束最优路径"的差异，独立模块让你能自由切换约束边界，排查问题也方便很多。

3.3 并行化：跑实验的时间省下后用来干什么

大规模实验最怕的是调一次参数要等一个通宵。在我的框架里，聚类分簇后就得到了M个独立的路径优化子任务，这正好天然适合Matlab的parfor并行计算。

我实测过一个对比：在600客户的实例上，M=6辆车的情况，串行跑300代WMA需要大约140秒，开启并行池（6个worker）后降到30秒左右，加速比接近4.7倍。别小看这个差异，调参阶段你需要反复跑几十组工况，累计下来节约的时间非常可观。

需要提醒的是，并行计算不等于盲目开满worker。Matlab的parfor在每次循环结束时要收集和同步结果，如果子任务太小、循环次数太多，通信开销会抵消并行收益。我的经验是：每个worker处理的任务运行时间至少要2秒以上，否则串行反而更快。这在代码里可以用一个简单的timeit测试来判断。

另外还有个隐性收益：并行化让你有底气做更细致的参数扫描。我以前会心浮气躁地只跑一两组参数就下结论，现在可以在一个晚上把鲸群大小、迁徙代数、聚类簇数几个维度都扫一遍，实验结论扎实很多。

4. Matlab代码实现：从结构设计到关键细节

4.1 代码模块划分与四个核心函数

这份Matlab代码整体遵循"主函数-问题定义-算法主体-结果输出"的经典分层，方便你直接修改数据或者替换算法。工程上我建议把每个模块独立成文件，别把所有逻辑塞进一个脚本里，调试时会痛苦到怀疑人生。

核心模块如下：

• 主脚本 Main.m：控制整体流程，初始化参数，调用各模块函数，收集结果并绘图。
• 问题定义 ProblemDefinition.m：加载客户坐标、设置仓库位置、确定车辆数量、计算距离矩阵。
• 解码与目标函数 EvaluateObjective.m：将鲸鱼个体的位置编码解码成M条闭合路径，返回总行驶距离和约束违反信息。
• WMA算法主体 WMAmain.m：实现鲸鱼种群初始化、迁徙算子、局部搜索、循环迭代逻辑。
• 辅助工具 LocalSearch.m：对每条路径执行2-opt局部搜索，快速改善解质量。

4.2 距离矩阵和初始种群：别在这里省时间

距离矩阵是全程使用最频繁的数据，所有适应度计算都要查询它。一个常见错误是每次计算适应度都调用pdist2重复算距离，这在循环里是性能杀手。正确做法是先算一次distanceMatrix = pdist2(coordinates, coordinates, 'euclidean')，之后所有路径总距离都从矩阵里查表累加，速度提升一个数量级。

初始种群的生成质量直接决定WMA的起点。我试过完全随机生成，收敛慢，且结果方差大；也试过用最近邻贪心生成一部分个体，结果改善明显。最终方案是：种群中的30%个体用随机最近邻法构造，剩余70%完全随机生成，兼顾了初始质量和解多样性。这里有个心得体会：单纯追求高质量初始解会让群体多样性大幅削弱，后续迁徙算子的探索空间变小，反而容易提前收敛。

4.3 解码操作：从鲸鱼位置到M条路径的关键桥梁

解码是这份代码里最容易被忽视但最关键的步骤。鲸鱼个体在算法中的位置表象是一个长度为N+M-1的整数序列，其中N是客户总数，M是车辆数。这个序列使用了标准的客户排列表示方法，可以理解为先把所有客户排成一个长序列，然后用M-1个分割点把序列切成M段，每段对应一辆车的服务序列。

具体例子是：假设客户编号为1~10，M=3辆车，鲸鱼编码可能是[3 1 5 2 8 4 9 6 7 10 0 0 0]这样一串数字。解码时，从这串数字中提取出客户的访问顺序，然后根据设定的分割规则分成三段，得到三辆车的路线。每段的起点和终点都需补充上仓库节点。

解码过程中最容易出错的点是分割点有效性问题。如果某段长度为0，就说明有一辆车没有被分到任何客户，这在计算时会导致空路径。我在EvaluateObjective里专门加了一个检查：每条路径至少包含一个客户，如果分割点分配导致空路径，则从其他车辆路径里转移一个最近客户过去补位。这个修复逻辑看起来简单，但能避免大量运行期错误。

4.4 2-opt局部搜索的工程优化

WMA的全局搜索能力不错，但局部精化能力偏弱。我这里把2-opt局部搜索嵌入到每轮迁徙结束后，对每条路径片段做一次局部改进。2-opt的原理很简单：对一条路径中任意两条边，如果交换它们的连接方式能让路径变短，就执行交换。

我对经典2-opt做了两个工程优化：

第一个是提前截断。因为路径长度可能高达上百个客户，遍历所有边组合是O(n^2)的复杂度。我设置了一个参数maxIterations，只允许连续无改进迭代达到20次就停止搜索。实测下来，这个截断能减少70%以上的局部搜索耗时，而解质量只损失不到1%。

第二个是专门针对"多路径"的局部搜索策略调整。经典2-opt只作用在单条路径上，不做跨路径调整。我在实验中发现，偶尔让两辆车之间做一次"交换末端路径"的尝试，能小幅度改善总成本。这个跨路径操作频率很低，每隔10代才做一次，效果却很稳定。

5. 参数调优与常见报错排查

5.1 关键参数的经验区间与选择逻辑

WMA的参数调节直接决定实验成败。我把核心参数含义和推荐范围整理了一下：

• 鲸群大小N：在50到100之间比较合适。N太小群体多样性不足，N太大每轮迭代耗时线性增长，收敛改善却不明显。
• 最大迁徙代数T：这是区分WMA和普通PSO的关键参数之一。设置为300到700之间，具体规模越大需要的代数越多。
• 惯性权重w：影响个体保持自己原方向的程度。取0.4到0.6之间比较稳妥，太大容易振荡，太小会过早收敛。
• 学习因子c1、c2：控制个体向自身历史最优和全局最优学习的倾向。两个都取1.5左右即可，不需要过度精细调节。
• 局部搜索代数间隔：比如每5轮迁徙执行一次2-opt，如果每轮都执行，前期会让种群太快聚集到当前最优附近，降低探索能力。

我习惯用控制变量法来做参数扫描：固定其他参数只变一个，画出收敛曲线对比。比如测鲸群大小时，分别跑N=40、60、80、100四组，看最终总成本和收敛速度，而不是同时调整所有参数后找"看起来不错"的组合，那样很难定位到真正影响结果的参数。

5.2 高频报错与排查方法

我在实际运行中踩过不少坑，把最经典的几个列出来供参考：

• 错误一：Array indices must be positive integers or logical values。大概率是解码后某条路径的客户编号出现了0或非整数，常见原因是分割点处理时用了错误的取整方式。排查方法是在解码函数入口打印路径片段，检查客户编号合法性。
• 错误二：pdist2输入坐标维度不一致。通常是加载数据时转置操作不对。我建议在ProblemDefinition里加一个断言确认size(coordinates, 2) == 2。
• 错误三：程序跑很久不结束。大概率是距离矩阵计算循环没向量化，或者在2-opt里遍历了所有可能的边组合。按4.4节的方法加提前截断能缓解。
• 错误四：parfor并行池报错"Cannot use parfor with nested function"。这是因为在并行循环里访问了父函数的嵌套函数对象。解决方法是把并行块里调用的子函数写成独立函数文件，不要在脚本中定义嵌套函数。

5.3 随机数种子管理与结果可复现

做科研实验最怕"这次能跑出来，下次跑不出来"。Matlab里所有随机初始化都要依赖随机数流，我强烈建议在主脚本开头写死随机种子：

rng(42);

这样每次实验的初始种群和随机扰动都完全可复现。我还习惯把每次实验的关键参数、随机种子、最终结果统一记录进一个结构体ExperimentLog，方便事后分析。有一次我发现某组参数的结果异常好，回头看日志才发现是那次随机种子恰好生成了一个特别优质的初始解，这个发现避免了我对参数性能的误判。

6. 实验观测与使用心得

6.1 跑了哪些测试实例

我用三类规模的数据验证了框架效果：小规模50客户、中规模200客户、大规模600客户，车辆数量分别设置为2、4、6辆。故意构造了一个客户分布不均匀的场景：一部分客户集中在仓库附近，一部分分散在远处，以此检验算法在"客户密度差异大"时的表现。

对比算法选了GA和PSO两种常见方案，每种算法跑10次取平均值。实验结果如下表：

实例规模	车辆数	GA平均成本	PSO平均成本	WMA平均成本	WMA相对GA改进
50客户	2辆	682.4	715.9	638.7	6.4%
200客户	4辆	2147.3	2289.1	1992.5	7.2%
600客户	6辆	5531.8	5904.6	5152.3	6.9%

在600客户实例上，WMA平均计算时间为42秒左右，PSO约38秒，GA约55秒。WMA的时间开销处于可接受范围，而解质量明显占优。

6.2 收敛曲线里藏了什么信息

画收敛曲线时我发现一个有意思的现象：WMA的收敛曲线不是单调递减，而是在每轮迁徙开始时出现一个明显的"台阶"。这个台阶正是迁徙机制带来的——种群到达"繁殖海域"后重新分散，探索新区域时临时放弃了当前较好解，导致平均适应度短暂上升，随后迅速回落到新的更优水平。这个特征恰恰说明WMA在有效探索新解空间，而不是简单地单调收敛。

如果你发现WMA收敛曲线特别光滑、没有台阶，那很可能迁徙算子没有生效，或者参数设置里迁徙轮次不够。可以检查一下迁徙代数设置，适当增加T值。

6.3 两点使用心得

第一个心得是大规模问题别迷信单一算法。很多人问"最好的TSP解法是什么"，我的实际体会是最优策略是混合策略。WMA负责全局搜索，2-opt负责局部精化，聚类分簇负责问题分解，三者缺一不可。如果只指望某一种算法单独扛下所有规模的问题，很难兼顾质量和效率。

第二个心得是可视化一定要做。我在迭代过程中实时绘制当前最优路径分布图，能一眼看出路径是否出现明显的交叉、车辆负荷是否均衡。有一次我看到某辆车的路径绕了一个大圈就能通过合并两点省下很多距离，这种洞察是纯看数据很难发现的。Matlab里用plot和scatter配合就能画出来，强烈建议在学习调试时保持可视化习惯。

这套LS-SDMTSP求解方案现在不只是停留在实验层面，我把它调整后用在了一个模拟的物流配送调度场景里，对数十个订单按地理位置自动分配车辆，效果比较稳定。如果你正打算用WMA处理多旅行商问题，建议先拿较小规模的数据把解码和约束修复模块调试通，再逐渐放大到大规模实例。这样既能快速定位代码问题，又能在每个阶段直观感受到算法改进带来的收益。