May, 2022

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

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

    将机器学习技术应用于大邻域搜索算法（LNS）以提高解决优化问题的效率和结果质量。

    Mar, 2024

  • 电容车辆路径问题的神经大邻域搜索

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

    Nov, 2019

  • 利用深度强化学习进行自适应大邻域搜索的运算符选择

    本文提出了一种基于深度强化学习算法的算子选择方法，旨在提高 Adaptive Large Neighborhood Search（ALNS）算法的解题质量，实证结果表明，与基于机器学习的算法相比，所述方法训练次数更少，对小型问题与大型问题都能有效提高问题解决效率。

    Nov, 2022

  • 机场地面处理车辆路径问题中的大邻域搜索学习

    该研究提出了一种新的基于深度学习技术的车辆路径问题求解方法，以优化机场地勤中的车队调度，实验结果表明该方法在处理多达 200 个航班和 10 种操作时表现非常优秀，并在不同情况下表现出了很好的鲁棒性和广泛适用性。

    Feb, 2023

  • 混合整数规划的大邻域搜索算法学习

    该论文提出了一种基于学习的大邻域搜索 (LNS) 方法来解决混合整数规划 (MIP)，该方法使用神经潜水模型来表示变量分配的可能性分布，并使用非自用 MIP 求解器生成初始分配，并使用诱导学习来训练神经网络选择在每个步骤中寻找下一个分配的邻域。

    Jul, 2021

  • 使用对比学习技术在大邻域内搜索整数线性规划问题

    本文介绍了一种新的算法 CL-LNS，通过使用正负样本集合学习一个次优解算法并使用图注意力网络和更丰富的特征进一步提高解决 LP 问题的性能。

    Feb, 2023

  • 大领域优先搜索策略在组合优化与答案集编程中的应用

    我们提出了大邻域优先搜索（LNPS）用于解决回答集程序设计中的组合优化问题。LNPS 是一种元启发式方法，通过交替破坏和优先搜索当前解来寻找更好的解决方案。我们基于 ASP 实现了 LNPS，并通过 heulingo 求解器的实验证明了 LNPS 可以显著提高 ASP 在优化方面的求解性能。此外，我们通过与（自适应）大邻域搜索的对比来证明我们 LNPS 方法的竞争力。

    May, 2024

  • NeuroLKH: 结合深度学习模型与 Lin-Kernighan-Helsgaun 启发式算法求解旅行商问题

    NeuroLKH 采用深度学习和 LKH 启发式算法相结合，通过训练 Sparse Graph Network 模型来解决旅行商问题等路由问题，得出实验结果表明能够优于传统启发式算法并泛化到更大范围问题。

    Oct, 2021

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

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

    Apr, 2022

  • 整数线性规划的局部分支松弛启发式算法

    本文探讨了在整数线性规划（ILP）的大邻域搜索（LNS）中设计有效和高效的启发式。 创新性地提出了 LB-RELAX 及其变体，利用线性规划松弛代替 Local Branching 来选择邻居。实验证明相对于 LB，LB-RELAX 及其变体计算出的邻域相同，但是速度更快。在多个 ILP 基准测试中取得了最新的任意时间性能。

    Dec, 2022