Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem

📄 arXiv: 2602.23579v1 📥 PDF

作者: Guillem Rodríguez-Corominas, Maria J. Blesa, Christian Blum

分类: cs.AI, cs.LG

发布日期: 2026-02-27

💡 一句话要点

提出基于强化学习的构造-合并-求解-适应算法RL-CMSA，解决最小-最大多旅行商问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 多旅行商问题 强化学习 组合优化 车辆路径问题 工作负载平衡

📋 核心要点

  1. 传统mTSP方法难以平衡工作负载，尤其是在大规模问题中，导致最长旅行时间过长。
  2. RL-CMSA利用强化学习指导解的构造，并结合精确优化方法，在探索和利用之间取得平衡。
  3. 实验表明，RL-CMSA在求解大规模mTSP问题时，性能优于现有遗传算法，能更有效地找到高质量解。

📝 摘要（中文）

本文针对对称单仓库最小-最大多旅行商问题(min-max mTSP)提出了一种混合方法，即基于强化学习的构造、合并、求解与适应算法(RL-CMSA)。该方法迭代地构造多样化的解，利用学习到的成对q值指导概率聚类；将路径合并成一个紧凑的池；求解一个受限的集合覆盖MILP；并通过路线间的移除、移动和交换操作来优化解。q值通过强化高质量解中城市对的共现来更新，同时池通过老化和修剪进行调整。这种精确优化和强化学习引导的构造相结合，平衡了探索和利用。在随机和TSPLIB实例上的计算结果表明，RL-CMSA在可比的时间限制下，始终能找到（接近）最佳解，并且优于最先进的混合遗传算法，尤其是在实例大小和销售员数量增加时。

🔬 方法详解

问题定义：论文旨在解决最小-最大多旅行商问题(min-max mTSP)。该问题是TSP的扩展，要求m个旅行商从同一仓库出发并返回，共同访问所有客户一次，目标是最小化最长旅行商的路线长度，从而平衡工作负载。现有方法，如遗传算法，在大规模问题中可能难以找到高质量的解，尤其是在平衡工作负载方面表现不佳。

核心思路：论文的核心思路是结合强化学习和精确优化，通过强化学习指导解的构造过程，利用精确优化方法改进解的质量。具体来说，使用强化学习学习城市之间的关联性，指导概率聚类，从而构造多样化的解。然后，利用精确优化方法，如集合覆盖MILP，从构造的解中选择最优的路线组合。

技术框架：RL-CMSA算法包含四个主要阶段：构造(Construct)、合并(Merge)、求解(Solve)和适应(Adapt)。 1. 构造阶段：利用学习到的q值，通过概率聚类构造多个初始解。 2. 合并阶段：将构造的路线合并到一个紧凑的路线池中。 3. 求解阶段：使用集合覆盖MILP从路线池中选择最优的路线组合。 4. 适应阶段：通过路线间的移除、移动和交换操作来优化解，并更新q值和路线池。

关键创新：该方法最重要的创新点在于将强化学习与精确优化相结合。强化学习用于指导解的构造，从而提高解的多样性，而精确优化用于改进解的质量，从而提高解的精度。这种结合使得算法能够在探索和利用之间取得平衡，从而更有效地找到高质量的解。

关键设计： 1. Q值更新：使用强化学习更新城市对之间的q值，奖励高质量解中共同出现的城市对。 2. 路线池管理：使用老化和修剪策略来管理路线池，保持池的多样性和质量。 3. 集合覆盖MILP：使用集合覆盖MILP从路线池中选择最优的路线组合，目标是最小化最长路线的长度。 4. 局部搜索：使用路线间的移除、移动和交换操作来进一步优化解。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，RL-CMSA在随机和TSPLIB实例上均表现出色，尤其是在大规模问题和销售员数量较多时，显著优于最先进的混合遗传算法。例如，在某些实例上，RL-CMSA能够找到比遗传算法更好的解，并且在相同的时间限制下，能够更快地收敛到高质量的解。

🎯 应用场景

该研究成果可应用于物流配送、车辆调度、应急救援等领域，尤其适用于需要平衡多个任务执行者工作负载的场景。例如，在快递配送中，可以使用该算法来优化快递员的配送路线，从而减少最长配送时间，提高整体效率和服务质量。未来，该方法可以扩展到更复杂的约束条件和目标函数，以适应更广泛的应用场景。

📄 摘要（原文）

The Multiple Traveling Salesman Problem (mTSP) extends the Traveling Salesman Problem to m tours that start and end at a common depot and jointly visit all customers exactly once. In the min-max variant, the objective is to minimize the longest tour, reflecting workload balance. We propose a hybrid approach, Construct, Merge, Solve & Adapt with Reinforcement Learning (RL-CMSA), for the symmetric single-depot min-max mTSP. The method iteratively constructs diverse solutions using probabilistic clustering guided by learned pairwise q-values, merges routes into a compact pool, solves a restricted set-covering MILP, and refines solutions via inter-route remove, shift, and swap moves. The q-values are updated by reinforcing city-pair co-occurrences in high-quality solutions, while the pool is adapted through ageing and pruning. This combination of exact optimization and reinforcement-guided construction balances exploration and exploitation. Computational results on random and TSPLIB instances show that RL-CMSA consistently finds (near-)best solutions and outperforms a state-of-the-art hybrid genetic algorithm under comparable time limits, especially as instance size and the number of salesmen increase.