用强化学习优化多人旅行商问题，平衡工作量并提升解的质量。
Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem
- 通过强化学习指导聚类构造多样解，动态更新城市对共现价值。
- 在小规模子问题上求解整数规划，结合路径合并与重排改进解。
- 适合大规模多人旅行商问题，尤其在销售员数量多时表现更优。
多人旅行商问题（mTSP）将单人旅行商问题扩展为从同一出发点开始并结束的m条路径，共同访问所有客户恰好一次。在最坏情况最小化（min-max）变体中，目标是最小化最长路径长度，以实现工作负载均衡。本文提出一种混合方法——基于强化学习的构建、合并、求解与适应（RL-CMSA），用于对称单枢纽min-max mTSP。该方法迭代地利用由学习到的成对q值引导的概率聚类构建多样化解，将路径合并为紧凑池，求解受限集覆盖整数线性规划（MILP），并通过跨路径的删除、移动和交换操作精炼解。q值通过强化高质量解中城市对的共现进行更新，而解池则通过老化与修剪机制自适应调整。该方法结合精确优化与强化学习引导的构造，在随机和TSPLIB实例上的计算结果表明，RL-CMSA始终能获得（近）最优解，且在相同时间限制下优于当前最先进的混合遗传算法，尤其在问题规模和销售员数量增大时优势明显。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。