Oct, 2023

学习使用灵活的神经 k-Opt 搜索可行和不可行路由问题的区域

PDF
TL;DR本文介绍了一种用于路径规划问题的新型学习 - 搜索（L2S）求解器 NeuOpt，通过定制的行动因子分解方法和自定义的双流递归解码器，学习实现柔性的 k-opt 交换。我们提出了引导式非可行区域探索（GIRE）策略，通过补充带有可行性相关特征的 NeuOpt 策略网络和利用奖励塑形更有效地引导增强学习，在规避纯可行性屏蔽方案的基础上，使得求解器能够自主地进行可行和不可行区域的探索。此外，我们在推理过程中为 NeuOpt 配备了动态数据增强（D2A），以实现更多样化的搜索。大量在旅行推销员问题（TSP）和车辆路径规划问题（CVRP）上的实验证明，我们的 NeuOpt 不仅明显优于现有的（基于屏蔽的）L2S 求解器，还表现出优于学习 - 构建（L2C）和学习 - 预测（L2P）求解器的优势。值得注意的是，我们提供了关于神经求解器如何处理 VRP 约束的新视角。我们的代码可在此 URL 找到：[URL]
neuoptrouting problemslearning-to-searchfeasibility masking schemetraveling salesman problem
发现论文，激发创造
  • 电容车辆路径问题的神经大邻域搜索

    本文提出了一种基于深度神经网络和注意力机制的学习启发式算法的大邻域搜索框架，用于解决车辆路径问题，该方法在性能方面优于现有的机器学习方法，也接近于现有优化方法的性能。

    Nov, 2019

  • 注意力学习解决路径规划问题！

    我们提出了一种基于注意力层的模型来解决组合优化问题，并使用基于确定性贪心策略的简单基线进行训练，在解决旅行商问题（TSP）和车辆路径问题（VRP）方面取得了很好的结果。

    Mar, 2018

  • 面向全方位可推广的神经网络方法解决车辆路径问题

    本文提出了一种元学习框架，通过元学习可以有效地训练出初始化的模型，并具有快速适应新任务的能力，在旅行商问题和车辆路径问题的综合实验中，证明了方法的有效性。

    May, 2023

  • 用于提升和配送问题的高效神经邻域搜索

    我们提出了一种高效的神经邻域搜索（N2S）方法，用于解决提取和交付问题（PDPs），并针对路线解决方案设计了强大的合成注意力，以便综合各种类型的特征。此外，我们利用了两个自定义的解码器自动学习执行去除和重新插入拾取 / 交货节点对以解决优先顺序约束，并利用多样性增强方案进一步改善性能，N2S 可产生针对现有神经方法的最先进的结果。

    Apr, 2022

  • 通过可传递的本地策略集成实现面向可广泛应用的神经求解器车辆路径问题

    为了提高神经车辆路径问题（VRP）求解器在实际环境中的可行性，我们设计了一个辅助策略，通过学习本地可转移的拓扑特征来改善神经 VRP 求解器的表现，将其与典型的建构策略相结合，形成一个集成策略。经过联合训练，这个集成策略使得各个策略相互协作和互补，从而提高了泛化能力。实验证明，与最先进的构造方法相比，这个集成策略在两个著名的基准测试中（TSPLIB 和 CVRPLIB）表现出更好的泛化性能，并且在数千个节点的真实世界问题上也能工作得很好。

    Aug, 2023

  • 强化学习的神经组合优化

    本文提出了一种利用神经网络和强化学习解决组合优化问题的框架，特别关注旅行推销员问题和背包问题，证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果，并且可以得到具有多达 200 个项目实例的最优解。

    Nov, 2016

  • 学习局部改写以进行组合优化

    本论文提出了一种基于 NeuRewriter 的方法，该方法使用 actor-critic 强化学习来指导启发式搜索，并成功地解决了三个复杂的组合问题。

    Sep, 2018

  • 学习协作策略以解决 NP-hard 路径规划问题

    本论文提出了一种新的层次化问题求解策略，称为学习协作策略，它使用两个迭代的深度强化学习策略：播种机和修订机，旨在有效地找到近似最优解，扩展了深度强化学习框架在解决 NP-hard 路由问题方面的应用。

    Oct, 2021

  • 基于神经构造启发式算法的大邻域搜索

    本文提出了一种基于神经网络学习的建造启发式方法的大邻域搜索 (LNS) 方法，用于解决具有时间窗口的车辆路径问题 (VRPTW)。方法采用图形神经网络来编码问题，并通过强化学习在不需要监督标签的情况下训练构造任务。神经修复运算符与局部搜索例程、启发式销毁运算符和选择过程相结合，应用于小型人口来到达一个复杂的解决方案。关键思想是使用学习模型重新构造部分破坏的解决方案，并通过破坏启发式 (或随机策略本身) 引入随机性，以有效地探索大邻域。

    May, 2022

  • 解决路径规划问题学习改进启发式方法

    本文提出一种基于 self-attention 的深度强化学习框架，以学习解决旅行商问题（TSP）和有容量车辆路径问题（CVRP）的改进启发式算法，实验表明该方法性能优于现有的深度学习方法，并且具有良好的泛化能力。

    Dec, 2019