Oct, 2023

关于车辆路径规划分支定界统计学习的研究

PDF
TL;DR利用机器学习的分支限界算法，通过比较三个神经网络 —— 图卷积神经网络（GCNN）、GraphSAGE 和图注意力网络（GAT）的结果，在解决有容量限制的车辆路径问题方面展现了潜力。通过训练这些神经网络，以模拟计算代价高昂的 Strong Branching 策略的决策过程。经过严格的实验证明，这种方法可以在较短的计算时间内达到或超过分支限界算法与 Strong Branching 策略的性能，并且所对应的研究结果和方法的源代码在以下网址中可以轻松获得并进行参考。
machine learningneural networkscapacitated vehicle routing problemstrong branching strategybranch and bound algorithm
发现论文，激发创造
  • 图卷积分支与界

    使用深度学习模型在优化流程中的有效性进行了论证，通过将图卷积分支限界与经典的分支限界算法相结合，实现了更快速的解决旅行商问题的路径的识别。

    Jun, 2024

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

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

    Nov, 2019

  • 图卷积网络与引导树搜索的组合优化

    文章提出一种基于深度学习和启发式算法的图卷积网络方法，用于解决某些 NP 困难问题，并在四个 NP 困难问题和五个数据集上进行了评估，结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平，并具有较强的泛化性和扩展性。

    Oct, 2018

  • 使用图卷积神经网络进行精确组合优化

    本文提出了一种基于图卷积神经网络的分支定界变量选择新模型，通过模仿学习和强分支专家规则训练，成功解决了组合优化问题。实验结果表明，该方法不仅在分支机制上优于现有的机器学习方法，而且在大问题上也优于现有的专家设计分支规则。

    Jun, 2019

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

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

    May, 2023

  • 超越 TSP 的神经组合优化：现有架构在图结构下表现不足

    本文研究如何将深度强化学习和图神经网络应用于无线网络中的电力和信道分配问题，研究结果表明现有结构还不能很好地识别图的结构和特征，并且对于对图产生影响的问题不太适用，但研究还是取得了一些积极进展，比如通过距离编码来增强问题的表示方法。

    Jan, 2022

  • 神经网络验证的神经网络分支

    通过训练图神经网络来设计一个有效的分支策略，能够在形式化验证神经网络的过程中减少验证时间并获得更好的验证结果。

    Dec, 2019

  • 一种高效的基于学习的求解器，可与元启发式算法相媲美，用于容量约束弧路线问题

    本文介绍了一种基于神经网络的求解程序，它能够显著缩小与先进元启发式方法之间的差距，并展现出卓越的效率。该求解程序利用方向感知的注意力模型（DaAM）和监督强化学习方案，同时提出了路径优化方法，成功解决了容量限制的弧路由问题，在保持出色效率的同时获得了与最先进的元启发式方法相媲美的决策质量。

    Mar, 2024

  • 用强化学习解决车辆路径规划问题

    本文提出了一个端到端的框架，使用强化学习来解决车辆路径问题 (VRP)，我们训练一个单一的模型，仅通过观察奖励信号和遵守可行性规则，就可以找到给定分布采样的问题实例的近最优解。通过将策略梯度算法应用于优化其参数，我们的模型在实时中以连续操作序列的形式生成解决方案，无需为每个新问题实例重新训练，我们的方法在解决负载容量 VRP 的中等规模实例时，在解决质量上优于经典的启发式算法和 Google 的 OR-Tools，同时具有可比较的计算时间，在本文中还探讨了分裂交付对解决质量的影响。我们的提出的框架可以应用于其他 VRP 变体，例如随机 VRP，并具有应用于组合优化问题的潜力。

    Feb, 2018

  • 运用图指针网络在组合优化中的学习分支

    本文提出了一种聚合图神经网络和指针机制的图指针网络模型来学习分支定界中的变量选择策略，结果表明该模型在求解速度和搜索树大小方面都优于现有的机器学习和专家设计的分支规则。

    Jul, 2023