CARSS: 合作注意力引导的强化子路径综合在解决旅行商问题中的应用
NAR4TSP 是第一个成功结合强化学习和非循环解码的解决 TSP 问题的算法,通过使用一个特殊设计的图神经网络以非循环的方式生成 TSP 解决方案,实现更快的推理速度,其训练使用了增强型强化学习策略,消除了传统基于监督学习的非循环模型的昂贵标签依赖,实验结果表明 NAR4TSP 在解决质量、推理延迟和泛化能力方面优于四个最先进的模型,此外,我们展示了 NAR4TSP 解码过程和整体路径规划的可行性和有效性的可视化。
Aug, 2023
本文提出了一种基于离线多智能体强化学习(MARL)的多机器人社交感知和高效协同规划方法,使用时间 - 空间图(TSG)进行社交编码,引入 K 步先见奖励设置,并改进了传统的集中式批判者网络,从而在多群组实验中验证了该方法的有效性。
Nov, 2022
提出一种基于深度强化学习的经理 - 工作人员框架来解决一种复杂但非常重要的旅行商问题的变体(即具有时间窗口和拒绝的多车 TSP),其中不能在截止日期前提供服务的客户可能被拒绝。经过实验结果证明,该框架在解决大型问题时具有高质量的解决方案和更短的计算时间。
Sep, 2022
本文提出了一个基于增强学习的启发式算法 VSR-LKH,它运用 Q-learning、Sarsa、Monte Carlo 三种方法改进了已有的 TSP 算法 Lin-Kernighan-Helsgaun (LKH),将其高效应用于 111 个 TSP 基准测试,结果表明,该方法表现出具有良好的性能。
Dec, 2020
本研究提出了一种基于层次强化学习的端到端学习框架,称为 H-TSP,用于解决大规模 TSP 问题,通过选择子集并使用深度学习模型直接生成解决方案,具有可扩展和高效性。
Apr, 2023
我们提出了 UTSP,这是一个用于解决旅行推销员问题(TSP)的无监督学习框架,使用基于图神经网络(GNN)的代理损失。该方法在参数效率和数据效率方面优于目前的数据驱动 TSP 启发式方法。
Mar, 2023
通过多分辨率和对称性保持,我们提出了一种新的数据驱动方法来解决旅行推销员问题和车辆路径问题。实验证明,我们的模型超过了现有的基准线,并证明了对称性保持和多分辨率对于解决组合问题的重要性。
Oct, 2023
本研究提出使用强化学习训练的图指针网络(Graph Pointer Networks,GPNs)来解决旅行商问题。我们使用 GPNs 对输入图进行嵌入并通过学习分层策略来优化城市排列。实验结果表明,GPNs 对小规模的 TSP50/100 问题的泛化性能不错,且在 TSP500/1000 问题中获得了更短的旅行路径和更快的计算时间,同时当问题涉及时间窗口约束时,支持最优解的分层强化学习训练优于以往的基准方法。
Nov, 2019
我们提出了一种基于注意力层的模型来解决组合优化问题,并使用基于确定性贪心策略的简单基线进行训练,在解决旅行商问题(TSP)和车辆路径问题(VRP)方面取得了很好的结果。
Mar, 2018
本文提出了一种利用神经网络和强化学习解决组合优化问题的框架,特别关注旅行推销员问题和背包问题,证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果,并且可以得到具有多达 200 个项目实例的最优解。
Nov, 2016