Jul, 2022

针对旅行商问题的强化 Lin-Kernighan-Helsgaun 算法

PDF
TL;DR本研究提出了 Variable Strategy Reinforced LKH (VSR-LKH) 与 VSR-LKH-3 算法，分别引入了三种强化学习方法与 LKH 算法相结合，以解决 TSP 问题和 TSP 变体（包括 TSPTW 和 CTSP），经 236 个 TSP 基准测试表明，这些算法具有显著的性能优势。
发现论文，激发创造
  • 将强化学习与 Lin-Kernighan-Helsgaun 算法相结合解决旅行商问题

    本文提出了一个基于增强学习的启发式算法 VSR-LKH，它运用 Q-learning、Sarsa、Monte Carlo 三种方法改进了已有的 TSP 算法 Lin-Kernighan-Helsgaun (LKH)，将其高效应用于 111 个 TSP 基准测试，结果表明，该方法表现出具有良好的性能。

    Dec, 2020

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

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

    Oct, 2021

  • 旅行商问题的并行元启发式求解器集成

    旅行推销员问题（TSP）是文献中研究充分的 NP 困难问题之一。该论文研究了涵盖从 2,000 到 85,900 个城市的问题，并发现人工组合多个求解器的算法能够在解决 10,000 个城市以上的问题时超越现有的最先进求解器的表现。

    Aug, 2023

  • H-TSP：层次化解决大规模旅行推销员问题

    本研究提出了一种基于层次强化学习的端到端学习框架，称为 H-TSP，用于解决大规模 TSP 问题，通过选择子集并使用深度学习模型直接生成解决方案，具有可扩展和高效性。

    Apr, 2023

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

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

    Nov, 2019

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

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

    Aug, 2023

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

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

    Mar, 2024

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

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

    Nov, 2016

  • 多旅行商问题的有效迭代二阶段启发式算法

    本文研究了旅行商问题的扩展 —— 多旅行商问题（mTSP），并提出了一个双阶段的迭代式启发式算法 ITSHA 来解决带有 minsum 和 minmax 目标的 mTSP 问题。实验结果表明，该算法在多目标下均优于现有启发式算法。

    Jan, 2022

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

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

    Oct, 2022