Oct, 2021

面向旅行商问题的图神经网络引导局部搜索

PDF
TL;DR提出了一种基于图神经网络和引导局部搜索的 TSP（旅行商问题）混合数据驱动方法，该方法能够在不损失解决方案质量的同时，快速求解大规模 TSP 实例，经实验证明，我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%，将 20 个节点实例推广到 100 个节点问题集时，我们将最优性差从 18.845% 减少到 2.622%，提高了 2 倍和 7 倍。
traveling salesperson problemgraph neural networksguided local searchoptimizationapproximation algorithms
发现论文，激发创造
  • 学习解决 NP 完全问题 - 用图神经网络处理决策 TSP 问题

    本文研究表明图神经网络可以通过可训练的可组装模块来解决含有符号和数值数据结构的 NP 完全问题，提供了一个解决 TSP 问题的高度自主的消息传递算法并且能够使用与目标成本 C 的偏差小于 2% 的决策实例进行训练。

    Sep, 2018

  • 学会解决旅行商问题要重新思考泛化

    本文提出了一种神经组合优化方法，将学习算法与模型架构相结合，以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究，控制实验提供了第一手数据，并提供了深度学习的新方向。

    Jun, 2020

  • 旅行商问题的高效图卷积网络技术

    本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法，通过使用图卷积网络构建 TSP 图表示，并通过高度并行化的 Beam Search 非自回归方法输出巡回路径，我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好，最终平均优化差距从 50 个节点降低到 0.01％，100 个节点从 2.26％降至 1.39％，尽管相较于标准的运筹学求解器，我们的方法还有所欠缺。

    Jun, 2019

  • 解决旅行推销员问题的无监督学习

    我们提出了 UTSP，这是一个用于解决旅行推销员问题（TSP）的无监督学习框架，使用基于图神经网络（GNN）的代理损失。该方法在参数效率和数据效率方面优于目前的数据驱动 TSP 启发式方法。

    Mar, 2023

  • 旅行商问题的 Transformer 网络

    本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法，相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现

    Mar, 2021

  • 图形指针网络和层次强化学习的组合优化

    本研究提出使用强化学习训练的图指针网络（Graph Pointer Networks，GPNs）来解决旅行商问题。我们使用 GPNs 对输入图进行嵌入并通过学习分层策略来优化城市排列。实验结果表明，GPNs 对小规模的 TSP50/100 问题的泛化性能不错，且在 TSP500/1000 问题中获得了更短的旅行路径和更快的计算时间，同时当问题涉及时间窗口约束时，支持最优解的分层强化学习训练优于以往的基准方法。

    Nov, 2019

  • 同行之路：一种新的 TSP 求解策略

    本研究提出了一种基于模仿学习框架的策略来解决旅行商问题，并展示了所训练的图神经网络在大规模的 TSP 实例上的较快求解能力。

    Oct, 2022

  • 无监督学习中旅行商问题的规模和难度泛化

    探讨无监督学习在解决旅行推销员问题中的泛化能力，通过训练图神经网络并使用嵌入来构建边缘的热图，同时研究不同的训练实例大小、嵌入维度和分布对无监督学习方法结果的影响，结果表明使用较大的实例规模和增加嵌入维度可以构建更有效的表示，提高解决旅行推销员问题的能力，并发现在不同分布上进行泛化评估时，选择更困难的实例作为训练数据可以使模型具备更好的泛化能力。

    Mar, 2024

  • 基于强化学习的无自回归旅行商问题求解器

    NAR4TSP 是第一个成功结合强化学习和非循环解码的解决 TSP 问题的算法，通过使用一个特殊设计的图神经网络以非循环的方式生成 TSP 解决方案，实现更快的推理速度，其训练使用了增强型强化学习策略，消除了传统基于监督学习的非循环模型的昂贵标签依赖，实验结果表明 NAR4TSP 在解决质量、推理延迟和泛化能力方面优于四个最先进的模型，此外，我们展示了 NAR4TSP 解码过程和整体路径规划的可行性和有效性的可视化。

    Aug, 2023

  • 提前预计以避免迟到：解决困难约束旅行推销员问题

    使用前瞻信息作为特征，提出一种利用学习方法改善具有时间窗口的 TSP 解决方案合法性的新方法，并构建了具有硬约束条件的 TSPTW 数据集进行准确评估和基准测试。通过对多种数据集进行综合实验，MUSLA 优于现有基线算法且具有一定的泛化能力。

    Mar, 2024