注意力学习解决路径规划问题!
本文提出一种基于 self-attention 的深度强化学习框架,以学习解决旅行商问题(TSP)和有容量车辆路径问题(CVRP)的改进启发式算法,实验表明该方法性能优于现有的深度学习方法,并且具有良好的泛化能力。
Dec, 2019
本研究提出使用强化学习训练的图指针网络(Graph Pointer Networks,GPNs)来解决旅行商问题。我们使用 GPNs 对输入图进行嵌入并通过学习分层策略来优化城市排列。实验结果表明,GPNs 对小规模的 TSP50/100 问题的泛化性能不错,且在 TSP500/1000 问题中获得了更短的旅行路径和更快的计算时间,同时当问题涉及时间窗口约束时,支持最优解的分层强化学习训练优于以往的基准方法。
Nov, 2019
本文提出了一种利用神经网络和强化学习解决组合优化问题的框架,特别关注旅行推销员问题和背包问题,证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果,并且可以得到具有多达 200 个项目实例的最优解。
Nov, 2016
本文介绍了强化学习在处理 NP-Hard 组合优化问题,特别是车辆路径问题方面的应用。作者将问题建模成一个马尔科夫决策过程,并采用了 Actor-Critic 类的 PPO 方法和基于卷积神经网络的神经架构。尽管与最先进的 OR-TOOLS 解算器相比略逊一筹,但该算法具有较好的泛化能力和较短的解答时间。未来的研究方向是提高算法的性能表现。
Jul, 2022
本文提出了一种基于深度神经网络和注意力机制的学习启发式算法的大邻域搜索框架,用于解决车辆路径问题,该方法在性能方面优于现有的机器学习方法,也接近于现有优化方法的性能。
Nov, 2019
本文旨在通过改善现有的模型,提高机器学习在车辆路径规划中的泛化能力,首先通过改进注意力机制模型及其损失函数,接着采用混合实例训练方法和推理级数据增强技术解决了问题固有差异和模型架构弱点的问题,最终达到了提高性能的效果。
Jul, 2022
本文提出了一个端到端的框架,使用强化学习来解决车辆路径问题 (VRP),我们训练一个单一的模型,仅通过观察奖励信号和遵守可行性规则,就可以找到给定分布采样的问题实例的近最优解。通过将策略梯度算法应用于优化其参数,我们的模型在实时中以连续操作序列的形式生成解决方案,无需为每个新问题实例重新训练,我们的方法在解决负载容量 VRP 的中等规模实例时,在解决质量上优于经典的启发式算法和 Google 的 OR-Tools,同时具有可比较的计算时间,在本文中还探讨了分裂交付对解决质量的影响。我们的提出的框架可以应用于其他 VRP 变体,例如随机 VRP,并具有应用于组合优化问题的潜力。
Feb, 2018
本文提出了一种元学习框架,通过元学习可以有效地训练出初始化的模型,并具有快速适应新任务的能力,在旅行商问题和车辆路径问题的综合实验中,证明了方法的有效性。
May, 2023
本文提出一种基于注意力机制、可同时开展多个路径,并能在路径和客户之间进行艰难的权衡的政策模型 ——JAMPR,通过对三个不同工具路由问题的全面实验,表明该模型对不同问题规模均有效,并且优于现有的基于构造算法方法,对于其中两个问题类型,甚至优于相应比较方法。
Jun, 2020
本文提出了一种神经组合优化方法,将学习算法与模型架构相结合,以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究,控制实验提供了第一手数据,并提供了深度学习的新方向。
Jun, 2020