单仓多旅行商问题中基于聚类的多任务均衡选址优化方法

《Mathematics》：A Clustering-Based Multi-Task Balancing Method for Depot Optimization in Single-Depot Multiple Traveling Salesman Problems

　　

在单仓多旅行商问题（Single-Depot Multiple Traveling Salesman Problem，SD-MTSP）中，传统选址方法常忽视旅行商间任务均衡，导致部分单元过载并损害整体运营效率。为此，研究人员提出一种基于聚类与多任务均衡的选址优化方法，其核心贡献在于设计多权重自适应选址优化方法（Multi-weight Adaptive Depot Optimization，MADO）。该方法通过聚类分析将城市节点划分为多组，并利用各簇样本数与凸包周长等信息动态合成方向向量，迭代优化选址，在最小化总路径长度的同时提升各旅行商路径的工作负载均衡性。此外，采用“分治”策略将复杂MTSP分解为多个并行TSP子问题，并使用Or-Tools高效求解。研究人员引入涵盖总距离（Total-Sum distance）、最大最小距离（Min-Max distance）、工作负载均衡（Workload Balance）、簇可分离性（Cluster separability）、鲁棒性（Robustness）与运行时间（Running time）的综合评估框架。基于TSPLIB标准数据集的实验表明，相较多种传统聚类算法，所提方法在路径优化与路径均衡上均具显著优势，验证了有效性与实用性，为物流配送等实际应用提供可靠方案。

研究背景方面，随着全球供应链融合与电商爆发增长，单仓多旅行商问题（SD-MTSP）在物流配送、应急调度与多机器人巡检等场景价值凸显。传统选址策略如启发式法与中点法多聚焦总行程最短，忽视旅行商间任务均衡，易致部分单元闲置而另一些过载；且均衡优化依赖初始划分、缺乏大规模节点下的统一框架。为解决路径效率与负载均衡协同优化、动态校正初始划分及大规模可扩展性三大挑战，研究人员开展本研究，提出MADO方法，构建“聚类—选址优化—TSP求解”联合框架，论文发表于《Mathematics》。

关键技术方法上，研究人员以TSPLIB基准实例（att48、eil76、gr229、pr299、dsj1000等）为样本队列，采用K-means、Bisecting K-means、Agglomerative等八种聚类算法单次划分固定簇；设计MADO迭代：以全体节点质心投影最近样本为初始仓，按簇节点数占比与凸包周长占比合成加权方向向量更新仓位置，引入状态哈希、拒绝阻尼与最大迭代终止保障；各簇以公共仓起止调用Or-Tools求解TSP子问题；以总距离、最大最小距离、负载变异系数等构成字典序接受准则，并以轮廓系数评聚类质量，以六指标综合评估。

研究结果部分，引言指出SD-MTSP现存三限并明确MADO四项贡献。相关工作综述了MTSP启发式/智能优化、负载均衡AHP-mTSP与Equity Transformer、选址RRT法等，指出需联合优化。预备工作中给出符号表与SD-MTSP形式化定义。方法论中，4.1定义仓为公共起止点；4.2阐述MADO四步（质心初仓、聚类求凸周、加权方向向量V=Σ(N(C_i)/N·L_i/L)·vec_i、更新Last+αV并投影最近样本、收敛判据‖Updated?Last‖<ε）；4.3给出整体八阶段框架与复杂度O(nk+T(n+k·f(m)))，伪代码含拒绝阻尼与循环检测。实验与结果中，5.1选五数据集覆盖48–1000节点；5.2定义六指标公式；5.3单指标比较显示Bisecting K-means在eil76/pr299/dsj1000总距最优，Agglomerative在gr229/pr299最小最大距最优，平均负载均衡0.95、鲁棒0.81；5.4雷达图与热力图显示K-means综合占优、Agglomerative均衡强但分离弱；5.5以pr299+K-means为例，MADO使总距由55145.51降至54533.97、最大最小距21130.08降至20624.04、均衡0.98升至0.99，Full MADO在六实例总距全优、五实例最大最小距最优，消融证明节点数项与路线长项互补。

讨论与结论翻译总结：研究人员结论为，所提基于聚类的多任务均衡选址法在TSPLIB上同时提升路径效率与负载均衡；MADO通过聚类与向量合成动态优仓，分治+Or-Tools解子问题，在总距、最大最小距、均衡、轮廓、鲁棒性上表现优良。局限在于未含实时交通、动态增删点及异构旅行商；未来可融强化学习、扩至多车型容量约束、优聚类—路径协同。该研究解决SD-MTSP“如何选好仓”关键问题，为物流与应急提供多目标协同实用方案，推动MTSP从理论可行走向工程可靠。