学习增强的邻域选择在车辆路径问题中的应用
本文提出了一种基于神经网络学习的建造启发式方法的大邻域搜索 (LNS) 方法,用于解决具有时间窗口的车辆路径问题 (VRPTW)。方法采用图形神经网络来编码问题,并通过强化学习在不需要监督标签的情况下训练构造任务。神经修复运算符与局部搜索例程、启发式销毁运算符和选择过程相结合,应用于小型人口来到达一个复杂的解决方案。关键思想是使用学习模型重新构造部分破坏的解决方案,并通过破坏启发式 (或随机策略本身) 引入随机性,以有效地探索大邻域。
May, 2022
本文提出了一种基于深度神经网络和注意力机制的学习启发式算法的大邻域搜索框架,用于解决车辆路径问题,该方法在性能方面优于现有的机器学习方法,也接近于现有优化方法的性能。
Nov, 2019
本文提出了一种基于深度强化学习算法的算子选择方法,旨在提高 Adaptive Large Neighborhood Search(ALNS)算法的解题质量,实证结果表明,与基于机器学习的算法相比,所述方法训练次数更少,对小型问题与大型问题都能有效提高问题解决效率。
Nov, 2022
该论文提出了一种基于学习的大邻域搜索 (LNS) 方法来解决混合整数规划 (MIP),该方法使用神经潜水模型来表示变量分配的可能性分布,并使用非自用 MIP 求解器生成初始分配,并使用诱导学习来训练神经网络选择在每个步骤中寻找下一个分配的邻域。
Jul, 2021
本文介绍了一种新的算法 CL-LNS,通过使用正负样本集合学习一个次优解算法并使用图注意力网络和更丰富的特征进一步提高解决 LP 问题的性能。
Feb, 2023
通过强化学习方法优化随机车辆路径问题,减少货物运输中的行程成本,提出一种新的模型,用于考虑不确定的行程成本和需求,以及确定的客户时间窗口,通过基于注意力的神经网络进行训练,实现路径成本的最小化,并超越基于蚁群算法的模型,在行程成本上减少了 1.73%,该模型独特地整合了外部信息,展现了在不同环境中的稳健性,对未来随机车辆路径问题研究和产业应用具有价值。
Feb, 2024
该研究提出了一种新的基于深度学习技术的车辆路径问题求解方法,以优化机场地勤中的车队调度,实验结果表明该方法在处理多达 200 个航班和 10 种操作时表现非常优秀,并在不同情况下表现出了很好的鲁棒性和广泛适用性。
Feb, 2023
我们提出了大邻域优先搜索(LNPS)用于解决回答集程序设计中的组合优化问题。LNPS 是一种元启发式方法,通过交替破坏和优先搜索当前解来寻找更好的解决方案。我们基于 ASP 实现了 LNPS,并通过 heulingo 求解器的实验证明了 LNPS 可以显著提高 ASP 在优化方面的求解性能。此外,我们通过与(自适应)大邻域搜索的对比来证明我们 LNPS 方法的竞争力。
May, 2024
使用注意力编码解码结构和一种新颖的插入启发式算法,我们以构造迭代深度学习算法解决带时间窗口的车辆路径问题,并比最佳已知学习解决方案更好地解决了该问题。
Dec, 2022
本文提出一种基于注意力机制、可同时开展多个路径,并能在路径和客户之间进行艰难的权衡的政策模型 ——JAMPR,通过对三个不同工具路由问题的全面实验,表明该模型对不同问题规模均有效,并且优于现有的基于构造算法方法,对于其中两个问题类型,甚至优于相应比较方法。
Jun, 2020