强化学习赋能“构建-合并-求解-适应”框架：解决最小-最大多旅行商问题
强化学习如何优化经典组合优化难题？
在运筹学和人工智能领域，多旅行商问题（mTSP） 是经典旅行商问题（TSP）的重要扩展。它要求规划 m 条路径，这些路径从一个共同的起点（仓库）出发并返回，共同访问所有客户点各一次。而 最小-最大变体（min-max mTSP） 的目标是最小化最长的那条路径，这在实际应用中直接关系到工作负载的均衡分配——例如，在多辆配送车辆或多名服务人员的调度场景中，避免个别任务过重至关重要。
近日，一篇题为《Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem》的论文在arXiv上发布（编号：2602.23579），提出了一种名为 RL-CMSA（强化学习引导的构建-合并-求解-适应） 的混合方法，专门针对对称单仓库的最小-最大mTSP。该方法巧妙地将精确优化与强化学习（RL） 引导的启发式构造相结合，旨在平衡探索与利用，以高效求解这一NP难问题。
RL-CMSA的核心四步流程
该方法的核心是一个迭代的四阶段循环：
- 构建（Construct）：利用基于学习的成对q值进行概率聚类，生成多样化的初始解。q值反映了城市对在高质量解中共同出现的“好感度”，引导构造过程偏向更有潜力的组合。
- 合并（Merge）：将构建阶段产生的多条路径合并到一个紧凑的路径池中。
- 求解（Solve）：对路径池应用一个受限的集合覆盖混合整数线性规划（MILP），精确地选出能覆盖所有客户且最小化最长路径的最优路径组合。这一步是方法的“精确”核心。
- 适应（Adapt）：此阶段包含两个层面的动态调整：
- 强化学习更新：根据当前产生的高质量解，更新城市对的q值，强化那些经常在好解中同时出现的城市对的关联。
- 路径池管理：通过老化（ageing）和剪枝（pruning） 机制来维护路径池，淘汰旧或低质量的路径，保持池的多样性和质量。
此外，在适应阶段后，还会通过跨路径的移除、移位和交换等局部搜索操作来进一步精化解的质量。
方法优势与实验结果
RL-CMSA 的创新之处在于它并非单纯依赖启发式或精确求解器。其混合架构让强化学习负责智能探索和引导构造（解决“搜什么”的问题），而MILP负责在优质候选集中进行精确筛选和优化（解决“怎么选最好”的问题）。这种分工协作有效缓解了组合爆炸问题，并提升了找到全局优质解的概率。
论文报告了在随机生成实例和标准测试库 TSPLIB 实例上的计算结果。数据显示，RL-CMSA 能够稳定地找到（接近）最优的解。更重要的是，在可比的时间限制下，其性能超越了一种先进的混合遗传算法，并且随着问题规模（客户点数量）和旅行商数量 m 的增加，这种优势尤为明显。这表明该方法在处理大规模、复杂的现实世界调度问题时具有更好的可扩展性和鲁棒性。
AI在组合优化领域的深远影响
这项研究是AI，特别是强化学习，深度赋能传统运筹优化问题的一个典型范例。将学习能力嵌入到优化框架中，使算法不仅能求解问题，还能从求解过程中学习问题结构，从而越解越聪明。这为物流配送、电路板钻孔、无人机巡检、甚至芯片设计布线等众多需要高效路径规划和资源平衡的领域，提供了更强大的自动化工具。
随着计算能力的提升和算法融合的深入，类似 RL-CMSA 这样的“学习+优化”混合范式，有望成为解决各类复杂组合优化问题的标准工具箱之一，推动智能制造与智慧物流向更高效率迈进。