Aug, 2023

求解大规模旅行推销员问题的分层销毁和修复方法

PDF
TL;DR对于庞大规模的旅行推销员问题（TSP），现有算法在计算效率和解决方案质量方面面临巨大挑战。为了解决这个问题，我们提出了一种分层销毁和修复（HDR）方法，通过一系列精心设计的销毁和修复操作来改进初始解。一个关键创新概念是分层搜索框架，它递归地修复部分边缘，并将输入实例压缩成小规模的 TSP，在某种等价保证下。这个巧妙的搜索框架能够在合理的时间内提供极具竞争力的解决方案。基于 19 个著名的大规模实例（城市数量从 10,000 到 10,000,000 个），公平比较显示 HDR 在计算效率和解决方案质量方面与现有最先进的 TSP 算法高度竞争。值得注意的是，在 3,162,278 个和 10,000,000 个城市的两个大型实例中，HDR 打破了 LKH 及其变体先前创下的世界纪录（即无论计算时间如何，都是最好的已知结果），而 HDR 完全独立于 LKH。最后，通过消融研究来证明分层搜索框架的重要性和有效性。
发现论文，激发创造
  • H-TSP：层次化解决大规模旅行推销员问题

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

    Apr, 2023

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

    本研究提出了 Variable Strategy Reinforced LKH (VSR-LKH) 与 VSR-LKH-3 算法，分别引入了三种强化学习方法与 LKH 算法相结合，以解决 TSP 问题和 TSP 变体（包括 TSPTW 和 CTSP），经 236 个 TSP 基准测试表明，这些算法具有显著的性能优势。

    Jul, 2022

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

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

    Aug, 2023

  • 将小型预训练模型推广到任意大的 TSP 实例

    本文针对旅行商问题，通过训练一个能够根据图形采样、转化和热力图合并等技术建立任意规模的热力图的小型模型，并采用强化学习算法进行高质量解的搜索，显著提高了该模型的泛化能力和性能。该方法优于现有基于机器学习的 TSP 算法。

    Dec, 2020

  • 将强化学习与 Lin-Kernighan-Helsgaun 算法相结合解决旅行商问题

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

    Dec, 2020

  • 时变旅行商问题的割、原始启发和学习分支

    本研究探讨了时间依赖旅行商问题（TDTSP），证明了其为 NP-hard 和 APX-hard，并针对该问题提出了两个 IP 公式以及不同的定价算法、割平面和基于 LP 的凸先发方法、传播方法和分支规则。同时，开展了计算实验以评估这些方法的有效性，并首次尝试学习 TDTSP 的强分支决策，但该方法目前并未改善运行时间。

    May, 2018

  • 重新思考后置搜索式神经方法解决大规模旅行商问题

    针对大规模旅行推销员问题，研究了热力图引导的蒙特卡罗树搜索模型，发现机器学习方法生成的热力图的有效性存在疑问，提出了一个简单基准方法可以胜过复杂的机器学习方法；同时，热力图引导的蒙特卡罗树搜索模型在实践中表现不如 LKH-3 启发式方法；未来建议基于更具理论支撑的热力图生成方法和探索自主、具有普适性的机器学习方法解决组合问题。

    Jun, 2024

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

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

    Jan, 2022

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

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

    May, 2022

  • 旅行商问题的 Transformer 网络

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

    Mar, 2021