使用 k-means++ 分层聚类与神经组合网络求解多仓封闭路径多旅行商问题

为众多司机设计更聪明的路线

从包裹货车到配送无人机和灾后救援车队，规划者常面临一道难题：多辆从不同地点出发的车辆如何分担拜访数百或数千个站点的工作，同时不浪费燃料或时间？本文提出了一种新的分而治之方法，结合了经典聚类技巧和现代神经网络，使计算机能在几秒钟而不是几分钟或几小时内规划出高效路线。

多仓多司机的挑战

研究聚焦于旅行商问题的一个更复杂版本：不再是单个旅行者，而是多个旅行者，每个旅行者都有自己的起点和终点。他们必须共同且各自只访问每个城市一次，同时尽量缩短总行程距离。这种设置模拟了协调卡车车队、机器人群或无人机在区域内分工的任务。由于城市和司机数量增加时可选路线组合数呈爆炸式增长，精确方法会变得过慢，传统的试错搜索方法也常常力不从心，或必须在解的质量和速度之间做出妥协。

经典搜索和简单划分的局限

多年来，工程师们依赖诸如遗传算法、蚁群算法和粒子群等“元启发式”方法。这些方法模拟自然过程来探索大量候选路线并逐步改进。它们灵活但有两个主要缺点：无法给出解的质量保证，而且在大规模地图上可能非常缓慢，尤其是每次新任务都得重新开始搜索时。一个常用的加速手段是先用 k-means 等工具将城市聚成若干区域，然后在每个簇内解决规模更小的问题。尽管这种先划分再求解的策略有帮助，但最终质量仍受限于底层搜索方法，要想得到更好的路径通常要付出更长的运行时间。

先教网络如何规划，再帮它扩展规模

近年出现了不同的思路：训练神经网络直接输出好路线。经过对大量示例城市布局的学习后，这类网络可以在一次前向传递中提出完整的巡回路线，就像语言模型生成一句话一样。这些神经解算器在中等规模的单司机问题上表现令人印象深刻，但在需要协调多名司机或城市数量远超训练规模时会遇到瓶颈。作者的关键举措是将这种神经解算器包裹在一个谨慎的两步流程中，将巨大的多司机任务重塑为许多较小且网络熟悉的子问题，从而让网络能够轻松处理。

两阶段方法如何运作

所提出的方法称为 KHC-NCN，首先使用改进版的 k-means 聚类将城市分配到不同的仓库和司机。如果某个区域包含的城市过多而超出神经解算器的可靠处理能力，该方法会自动将该区域进一步拆分为更小的片段，每片段的规模接近网络训练时看到的大小。然后将每个片段的坐标缩放到标准方形内，使其更类似训练数据。神经网络随后为每个小片段生成一条路线。最后，一个合并步骤将这些子路线缝合成每位司机的单一回路，采用简单的几何规则在增加最少额外距离的地方连接各片段。

在真实基准地图上的速度与质量

作者在一组广泛的标准地图上测试了他们的方法，这些地图来自路由研究中广泛使用的公开基准集。他们将方法与多种成熟的搜索技术、一流的手工设计解算器以及另一种神经方法进行了比较。在包含不同地图规模和司机数量的 44 个测试案例中，他们的方法在近四分之三的案例中找到更短的总路径，同时速度显著更快，常常快一个或多个数量级。随着城市数量攀升到数百或数千，他们的方法表现尤为稳健，而许多经典方法要么变慢、要么给出较差的路线。

对现实世界路径规划的意义

简而言之，该研究表明让快速的神经网络处理许多小且形状良好的子问题，往往优于在一个巨大问题上花费大量时间。通过以符合网络“舒适区”的方式聚类城市，然后巧妙地合并部分解，该方法既能给出较短的路径，又能迅速计算完成。对于物流、多机器人规划和应急响应等应用场景，这指向了一种实用路径，可以实现近实时的路线规划，从而比许多现有工具更好地利用车辆与能源。

引用: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

关键词: 车辆路径规划, 神经网络, 聚类, 优化, 物流