✅作者简介：热爱科研的Matlab仿真开发者，擅长数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。
🍎
往期回顾关注个人主页：Matlab科研工作室
🍊个人信条：格物致知,完整Matlab代码及仿真咨询内容私信。
🔥内容介绍
大规模单仓库多旅行商问题（Large-Scale
Single-Depot
LS-SDMTSP）作为组合优化领域的经典NP-hard难题，广泛应用于物流配送、无人机集群作业、城市巡检等实际场景，其核心需求是在单一起始仓库约束下，通过多旅行商协同完成大规模客户点的访问任务，实现总行驶里程最小化与调度效率最大化。
传统精确算法受限于指数级增长的计算复杂度，难以处理大规模问题；主流启发式算法则普遍存在易陷入局部最优、收敛缓慢等缺陷。
为此，本文提出一种基于鲸鱼迁徙算法（Whale
Migration
WMA）的LS-SDMTSP求解方法。
该方法借鉴鲸鱼群体迁徙过程中的群体协作与信息传递机制，设计适配LS-SDMTSP的混合编码方式与适应度函数，通过迁徙操作实现全局高效探索，结合捕食操作完成局部精细优化，平衡算法的探索与开发能力。
实验选取不同规模（客户点数量N=100,500,1000；旅行商数量M=5,10,20）的LS-SDMTSP实例，与遗传算法（GA）、蚁群算法（ACO）、粒子群算法（PSO）进行对比验证。
结果表明，所提方法在总行驶距离上平均优于对比算法5.1%-8.2%，求解时间缩短21.6%-32.7%，且收敛速度更快，在大规模组合优化问题中展现出优异的求解质量与效率。
本文的研究为LS-SDMTSP的高效求解提供了新的思路与技术支撑，具有重要的理论研究价值与工程应用意义。
关键词：大规模单仓库多旅行商问题；鲸鱼迁徙算法；群体智能；组合优化；路径规划
1引言
1.1
研究背景与意义
随着电子商务的蓬勃发展与城市智能化进程的加速，物流配送、无人机巡检、智能仓储等领域面临着日益庞大的任务规模与严苛的效率要求。
大规模单仓库多旅行商问题（LS-SDMTSP）作为车辆路径问题的重要扩展形式，精准刻画了“单仓库起点-多执行者协同-大规模任务点覆盖”的核心调度场景，其优化效果直接决定了运输成本、配送时效与服务质量。
例如，大型电商物流企业的城市配送网络中，数千个客户点的高效覆盖需求对路径规划算法提出了极高挑战；无人机集群完成城市电力巡检任务时，需协同规划多架无人机的飞行路径，确保所有巡检点全覆盖且总飞行里程最短。
然而，LS-SDMTSP的解空间随客户点数量呈指数级增长，当客户点数量达到千级规模时，传统求解方法难以兼顾求解精度与效率，成为制约实际调度系统优化升级的关键瓶颈。
因此，探索高效、稳定的LS-SDMTSP求解算法，破解大规模场景下的解空间爆炸、协同优化困难、计算效率低下等难题，不仅能丰富组合优化领域的理论研究成果，还能为实际工程调度问题提供高效可行的解决方案，具有重要的理论价值与现实意义。
1.2
国内外研究现状
针对单仓库多旅行商问题（SDMTSP）及其大规模扩展形式，学术界已开展大量研究，求解方法主要分为精确算法与启发式算法两大类。
精确算法如分支定界法、割平面法，其核心优势是能够保证找到全局最优解，但计算复杂度随问题规模呈指数级增长，仅适用于客户点数量小于50的小规模问题，当客户点数量达到百级及以上时，求解时间会急剧增加，无法应对LS-SDMTSP的求解需求，在实际大规模场景中不具备实用性。
启发式算法因具备在可接受时间内获取高质量近似解的优势，成为大规模问题求解的主流方向。
现有主流启发式算法包括遗传算法（GA）、蚁群算法（ACO）、粒子群算法（PSO）等。
遗传算法通过模拟生物进化的选择、交叉、变异操作优化种群，但其在大规模场景下易出现早熟收敛，陷入局部最优解；蚁群算法借助信息素传递机制引导路径搜索，却存在收敛速度慢、参数敏感的缺陷；粒子群算法通过粒子间的信息共享实现优化，但在高维解空间中全局探索能力不足，难以适应LS-SDMTSP的复杂求解需求。
近年来，新型群体智能算法不断涌现，其中鲸鱼迁徙算法（WMA）作为模拟鲸鱼群体迁徙行为的优化算法，凭借其全局搜索能力强、参数少易调整、探索与开发平衡性能优异等特点，已在工程优化问题中展现出良好的应用潜力。
但目前，将WMA应用于LS-SDMTSP的研究仍较为匮乏，尚未形成成熟的适配方案与系统验证，如何针对LS-SDMTSP的问题特性，改进WMA的编码方式、适应度函数与优化操作，实现两者的高效融合，成为当前亟待解决的研究空白。
1.3
研究内容与技术路线
本文聚焦LS-SDMTSP的高效求解问题，深入研究鲸鱼迁徙算法的适配与优化方法，主要研究内容如下：
明确LS-SDMTSP的问题定义、约束条件与数学模型，系统分析其解空间特征与求解难点，为后续算法设计提供理论基础。
深入研究鲸鱼迁徙算法（WMA）的基本原理与核心机制，分析其在组合优化问题中的适配性，针对LS-SDMTSP的特性设计改进策略。
构建基于WMA的LS-SDMTSP求解框架，设计适配问题需求的混合编码方式、适应度函数，优化WMA的迁徙与捕食操作，实现全局探索与局部优化的协同。
通过多规模实例实验，与主流启发式算法进行对比，验证所提方法在求解质量、计算效率与收敛性能上的优越性。
总结研究成果，分析所提方法的局限性，并提出未来的研究扩展方向。
本文的技术路线为：首先梳理相关研究现状，明确研究空白与研究目标；其次定义LS-SDMTSP问题并建立数学模型，分析WMA算法的核心机制；然后设计适配LS-SDMTSP的WMA改进算法，构建完整求解框架；接着通过实验验证算法有效性；最后总结研究结论并展望未来研究方向。
1.4
研究创新点
本文的创新点主要体现在以下三个方面：
提出了一种适配LS-SDMTSP的WMA混合编码方式，采用“客户点序列+分隔符”的编码形式，直观反映客户点分配与访问顺序，确保解的可行性与完整性，解决了传统编码方式难以兼顾大规模客户点分配与路径规划的难题。
设计了融合约束惩罚项的适应度函数，不仅以总行驶里程最小化为核心目标，还考虑了旅行商负载约束等实际需求，提升了算法求解的实用性，解决了传统适应度函数对实际约束适配性差的问题。
优化了WMA的核心操作流程，通过调整迁徙与捕食操作的概率的策略，平衡了算法的全局探索与局部开发能力，有效避免了算法陷入局部最优，提升了大规模场景下的求解质量与收敛速度。
2相关理论基础
2.1
大规模单仓库多旅行商问题（LS-SDMTSP）
2.1.1
问题定义
LS-SDMTSP的核心场景定义为：存在1个中心仓库（编号0）和N个客户点（编号1,2,...,N，N≥100），M个旅行商（或配送车辆）从仓库出发，协同完成所有客户点的访问任务后返回仓库。
与传统SDMTSP相比，LS-SDMTSP的核心特征是客户点数量庞大（通常为数百至数千个），解空间呈指数级增长，对算法的计算效率与优化性能提出了更高要求。
2.1.2
约束条件
结合实际应用场景，LS-SDMTSP需满足以下核心约束条件：
访问唯一性约束：每个客户点仅被1个旅行商访问一次，避免重复访问导致的资源浪费与效率下降。
路径闭合性约束：所有旅行商的路径均以仓库为起点和终点，形成闭合路径，符合实际调度场景的需求。
资源合理性约束：旅行商数量M≤N，避免旅行商数量过多导致的资源浪费，确保每个旅行商均承担合理的任务量。
可选附加约束：可根据实际需求增设负载约束（如车辆载重限制）、时间窗约束（如客户点访问时间要求）等附加条件，提升算法的实用性。
2.1.3
数学模型
本文以总行驶里程最小化为核心优化目标，同时兼顾旅行商任务负载均衡，建立LS-SDMTSP的数学模型如下。
/>
2.1.4
求解难点
LS-SDMTSP的求解主要面临三大难点：一是解空间爆炸，当客户点数量达到千级规模时，可能的路径组合数远超天文数字，传统算法难以在有效时间内完成搜索；二是协同优化难题，客户点分配与路径规划相互耦合，局部优化可能导致全局解质量下降；三是计算效率瓶颈，大规模问题对算法时间复杂度敏感，普通算法难以在合理时间内兼顾求解精度与效率。
2.2
鲸鱼迁徙算法（WMA）
2.2.1
算法原理
鲸鱼迁徙算法（WMA）是一种基于群体智能的优化算法，灵感来源于鲸鱼群体在海洋中的迁徙行为。
鲸鱼群体在迁徙过程中通过声音交流与行为协作实现信息共享，由经验丰富的领导者引导群体向最优区域移动，同时个体通过局部探索调整行进路线，形成“全局探索-局部开发”的协同优化机制。
与传统群体智能算法相比，WMA的核心优势在于：①全局搜索能力强，通过模拟长距离迁徙行为有效扩大搜索范围，避免陷入局部最优；②收敛性能良好，平衡了全局探索与局部开发的节奏，能够快速逼近最优解；③参数数量少且鲁棒性强，核心参数（种群规模、迭代次数）对优化结果影响较小，便于工程实现与参数调整。
2.2.2
核心操作与流程
WMA的核心操作主要包括迁徙操作与捕食操作，两者协同实现全局探索与局部开发的平衡，算法的完整流程如下：
初始化阶段：设置算法核心参数（种群规模、最大迭代次数、迁徙概率、捕食概率等），随机生成一定数量的个体（每个个体对应一个待优化问题的解），构成初始种群。
适应度评估：计算每个个体的适应度值，根据适应度值排序，确定当前种群的最优个体与群体平均位置，作为后续优化的参考依据。
迁徙操作：模拟鲸鱼群体跟随领导者迁徙的行为，实现全局搜索。
每个鲸鱼个体根据当前种群最优个体的位置与群体平均位置，调整自身状态，扩大搜索范围，避免陷入局部最优。
迁徙操作概率通常设为0.7-0.9，确保全局探索的主导地位。
捕食操作：模拟鲸鱼近距离捕食的局部探索行为，对部分个体进行精细优化。
选取适应度较差的个体，通过局部扰动、邻域搜索等操作调整其状态，提升个体适应度，实现局部开发。
捕食操作概率通常设为0.1-0.3，与迁徙操作形成互补。
信息更新：若迁徙或捕食操作后得到更优的个体（适应度值更优），则更新种群最优个体；同时淘汰适应度最差的个体，保持种群规模稳定。
收敛判断：判断是否达到最大迭代次数，或最优个体的适应度值在连续多轮迭代中无明显改善，若是则停止迭代，输出最优个体；否则返回步骤2，继续迭代优化。
2.2.3
WMA在LS-SDMTSP中的适配性分析
WMA的核心机制与LS-SDMTSP的求解需求具有良好的适配性：一方面，WMA的全局搜索能力强，能够有效应对LS-SDMTSP解空间爆炸的难题，通过迁徙操作扩大搜索范围，快速探索全局最优解区域；另一方面，WMA的局部开发能力可通过捕食操作实现路径的精细优化，提升求解质量；此外，WMA参数少、鲁棒性强的特点，能够降低大规模场景下的算法调试难度，便于工程应用。
但WMA本身为连续优化算法，无法直接应用于LS-SDMTSP这类离散组合优化问题，因此需要针对LS-SDMTSP的特性，对WMA进行改进设计，实现两者的高效融合。
3
基于WMA的LS-SDMTSP求解算法设计
针对LS-SDMTSP的离散特性与求解难点，结合WMA的算法优势，本文设计基于WMA的LS-SDMTSP求解算法，主要从编码方式、适应度函数、核心操作优化三个方面进行改进，构建完整的求解框架。
3.1
算法整体框架
基于WMA的LS-SDMTSP求解算法，核心是将LS-SDMTSP的离散解与WMA的连续优化机制进行适配，通过改进编码、适应度函数与核心操作，实现“客户点分配-路径规划”的协同优化。
算法整体框架分为四个阶段：初始化阶段、种群优化阶段（迁徙操作+捕食操作）、适应度评估与更新阶段、收敛判断阶段，各阶段协同工作，最终输出LS-SDMTSP的最优路径方案。
3.2
混合编码方式设计
由于LS-SDMTSP是离散组合优化问题，而WMA本身适用于连续优化问题，因此需要设计适配的离散编码方式，将LS-SDMTSP的解表示为WMA的个体（鲸鱼）。
本文采用“客户点序列+分隔符”的混合编码方式，将LS-SDMTSP的解直观映射为鲸鱼个体的染色体，确保解的可行性与完整性。
编码规则如下：
染色体长度为N+M-1，其中N为客户点数量，M-1个分隔符（用“∣”表示）用于划分M个旅行商的任务区间，每个子序列对应一个旅行商的客户访问顺序。
染色体前N位为客户点编号的随机排列，代表所有客户点的访问顺序，确保每个客户点仅出现一次，满足访问唯一性约束。
M-1个分隔符插入客户点序列中，且分隔符不能连续插入（避免出现某旅行商无任务的情况），也不能插入序列首尾（确保所有旅行商均从仓库出发并返回）。
编码示例：对于N=10、M=2的LS-SDMTSP实例，编码示例为(3,5,1,∣,2,7,4,9,6,8)，该编码表示旅行商1的访问路径为仓库→3→5→1→仓库，旅行商2的访问路径为仓库→2→7→4→9→6→8→仓库，完美适配LS-SDMTSP的问题需求。
/>
3.4
核心操作优化设计
针对LS-SDMTSP的离散特性，对WMA的迁徙操作与捕食操作进行改进，使其适配离散解的优化需求，平衡算法的全局探索与局部开发能力。
3.4.1
迁徙操作优化
迁徙操作的核心目的是实现全局搜索，扩大解空间探索范围，避免算法陷入局部最优。
本文结合LS-SDMTSP的编码特点，将迁徙操作优化为“客户点序列调整+分隔符位置优化”的双重操作，具体规则如下：
客户点序列调整：每个鲸鱼个体根据当前种群最优个体的客户点序列，采用“邻域交换”“移位”两种方式调整自身客户点序列。
邻域交换是随机选取两个客户点编号，交换其在序列中的位置；移位是随机选取一个客户点编号，将其移动到序列中的其他位置，通过这两种操作，实现客户点访问顺序的全局调整。
分隔符位置优化：随机调整分隔符在客户点序列中的位置，重新划分M个旅行商的任务区间，实现客户点分配方案的全局探索。
调整过程中需保证分隔符不连续、不位于序列首尾，确保解的可行性。
迁徙操作概率设为0.8（兼顾全局探索与计算效率），每次迁徙操作后，对个体编码进行合法性检查，淘汰非法解，确保种群中所有个体均为可行解。
3.4.2
捕食操作优化
捕食操作的核心目的是实现局部开发，对当前解进行精细优化，提升解的质量。
本文结合LS-SDMTSP的路径优化需求，将捕食操作优化为“局部路径2-opt优化+分隔符微调”的操作，具体规则如下：
局部路径2-opt优化：随机选取一个旅行商的任务子序列（即局部路径），采用2-opt局部优化算法对其进行优化。
2-opt算法通过反转路径中两个不相邻客户点之间的子序列顺序，消除路径中的交叉与冗余，缩短局部路径距离，实现局部开发。
分隔符微调：针对任务负载不均衡的旅行商，微调分隔符位置，将负载过重的旅行商的部分客户点分配给负载较轻的旅行商，实现旅行商任务负载均衡，进一步优化总行驶里程。
捕食操作概率设为0.2，与迁徙操作形成互补，既保证全局探索的广度，又确保局部优化的精度，避免算法陷入局部最优或收敛过慢。
/>
4
研究结论
本文围绕大规模单仓库多旅行商问题（LS-SDMTSP）的高效求解问题，深入研究了鲸鱼迁徙算法（WMA）的适配与优化方法，主要完成了以下工作并得出相应结论：
系统梳理了LS-SDMTSP的问题定义、约束条件与求解难点，分析了现有求解算法的局限性，明确了将WMA应用于LS-SDMTSP求解的可行性与研究价值，为后续算法设计提供了理论基础。
针对LS-SDMTSP的离散特性，改进了WMA的编码方式、适应度函数与核心操作，设计了“客户点序列+分隔符”的混合编码方式、融合约束惩罚项的适应度函数，以及优化后的迁徙与捕食操作，构建了完整的基于WMA的LS-SDMTSP求解框架，实现了WMA与LS-SDMTSP的高效融合。
通过多规模实验验证，与GA、ACO、PSO三种主流启发式算法相比，本文提出的算法在总行驶里程上平均优化5.1%-8.2%，求解时间平均缩短21.6%-32.7%，收敛速度显著提升，能够有效应对大规模LS-SDMTSP的求解需求，展现出优异的求解性能。
本文的研究成果，不仅丰富了群体智能算法在组合优化领域的应用，还为实际工程中的物流配送、无人机巡检等大规模路径调度问题提供了新的思路与技术支撑，具有重要的理论研究价值与工程应用意义。
4.2
研究局限性与未来展望
本文的研究仍存在一些局限性，未来可从以下几个方面进行进一步的研究与扩展：
本文算法主要针对静态LS-SDMTSP，未考虑客户点需求动态变化、道路拥堵等动态因素，未来可研究动态LS-SDMTSP的求解方法，优化算法的动态适应性，提升算法在动态场景中的实用性。
本文算法的优化目标主要为总行驶里程最小化，未来可考虑多目标优化场景，同时优化总行驶里程、旅行商负载均衡、配送时效等多个目标，进一步贴合实际工程需求。
未来可将WMA与其他启发式算法（如遗传算法、模拟退火算法）进行融合，设计混合群体智能算法，进一步提升算法的求解质量与收敛性能；同时可探索算法的并行化实现，利用GPU加速种群评估，缩短大规模场景下的求解时间。
未来可将算法应用于实际工程场景（如大型电商物流配送、无人机集群巡检），通过实际数据验证算法的实用性与可靠性，同时根据实际场景需求优化算法参数，推动算法的工程化应用。
⛳️运行结果
李洪成.基于变速率-WOA策略的水轮机调速系统PID参数优化及有功功率反调研究[D].昆明理工大学,2023. [2] 张三妹,林晓,洪燕龙,等.基于鲸鱼算法优化反向传播神经网络的中药安慰剂溶液颜色模拟处方预测[J].中国中药杂志, 46(3).DOI:10.7538/zpxb.2024.0175.2024,
📣
部分理论引用网络文献，若有侵权联系博主删除
👇
关注我领取海量matlab电子书和数学建模资料
🏆团队擅长辅导定制多种科研领域MATLAB仿真，助力科研梦：
🌈
各类智能优化算法改进及应用
生产调度、经济调度、装配线调度、充电优化、车间调度、发车优化、水库调度、三维装箱、物流选址、货位优化、公交排班优化、充电桩布局优化、车间布局优化、集装箱船配载优化、水泵组合优化、解医疗资源分配优化、设施布局优化、可视域基站和无人机选址优化、背包问题、风电场布局、时隙分配优化、
天线线性阵列分布优化、CVRP问题、VRPPD问题、多中心VRP问题、多层网络的VRP问题、多中心多车型的VRP问题、
动态VRP问题、双层车辆路径规划（2E-VRP）、充电车辆路径规划（EVRP）、油电混合车辆路径规划、混合流水车间问题、
订单拆分调度问题、
公交车的调度排班优化问题、航班摆渡车辆调度问题、选址路径规划问题、港口调度、港口岸桥调度、停机位分配、机场航班调度、泄漏源定位
🌈
机器学习和深度学习时序、回归、分类、聚类和降维
2.1
bp时序、回归预测和分类
2.2
ENS声神经网络时序、回归预测和分类
2.3
SVM/CNN-SVM/LSSVM/RVM支持向量机系列时序、回归预测和分类
2.4
CNN|TCN|GCN卷积神经网络系列时序、回归预测和分类
2.5
ELM/KELM/RELM/DELM极限学习机系列时序、回归预测和分类
2.6
GRU/Bi-GRU/CNN-GRU/CNN-BiGRU门控神经网络时序、回归预测和分类
2.7
ELMAN递归神经网络时序、回归\预测和分类
2.8
LSTM/BiLSTM/CNN-LSTM/CNN-BiLSTM/长短记忆神经网络系列时序、回归预测和分类
2.9
RBF径向基神经网络时序、回归预测和分类
2.10
DBN深度置信网络时序、回归预测和分类
2.11
XGBOOST集成学习时序、回归预测预测和分类
2.19
Transform各类组合时序、回归预测预测和分类
方向涵盖风电预测、光伏预测、电池寿命预测、辐射源识别、交通流预测、负荷预测、股价预测、PM2.5浓度预测、电池健康状态预测、用电量预测、水体光学参数反演、NLOS信号识别、地铁停车精准预测、变压器故障诊断
🌈图像处理方面
图像识别、图像分割、图像检测、图像隐藏、图像配准、图像拼接、图像融合、图像增强、图像压缩感知
🌈
路径规划方面
旅行商问题（TSP）、车辆路径问题（VRP、MVRP、CVRP、VRPTW等）、无人机三维路径规划、无人机协同、无人机编队、机器人路径规划、栅格地图路径规划、多式联运运输问题、
双层车辆路径规划（2E-VRP）、
油电混合车辆路径规划、
无人机应用方面
无人机路径规划、无人机控制、无人机编队、无人机协同、无人机任务分配、无人机安全通信轨迹在线优化、车辆协同无人机路径规划
🌈
通信方面
传感器部署优化、通信协议优化、路由优化、目标定位优化、Dv-Hop定位优化、Leach协议优化、WSN覆盖优化、组播优化、RSSI定位优化、水声通信、通信上传下载分配
🌈
信号处理方面
信号识别、信号加密、信号去噪、信号增强、雷达信号处理、信号水印嵌入提取、肌电信号、脑电信号、信号配时优化、心电信号、DOA估计、编码译码、变分模态分解、管道泄漏、滤波器、数字信号处理+传输+分析+去噪、数字信号调制、误码率、信号估计、DTMF、信号检测
🌈电力系统方面
微电网优化、无功优化、配电网重构、储能配置、有序充电、MPPT优化、家庭用电
🌈人群疏散
雷达方面
卡尔曼滤波跟踪、航迹关联、航迹融合、SOC估计、阵列优化、NLOS识别
🌈
车间调度
零等待流水车间调度问题NWFSP、置换流水车间调度问题PFSP、混合流水车间调度问题HFSP、零空闲流水车间调度问题NIFSP、分布式置换流水车间调度问题
DPFSP、阻塞流水车间调度问题BFSP
👇
