跳转至

基于记忆增强的神经求解器用于路径优化问题

文章背景与核心概要

路径优化问题（Routing Problems）是众多现实世界应用的核心，但由于其属于 NP-hard（非多项式难解）问题，长期以来极难求解。虽然启发式算法在解的质量和可扩展性之间提供了最佳平衡，而强化学习（RL）为其设计提供了灵活的框架，但现有的学习型方法仍难以适应特定算例（Instance），也无法充分利用可用的计算预算。

为了解决这些局限性，作者引入了 MEMENTO，这是一种在推理阶段利用记忆来改进神经求解器的方法。MEMENTO 利用在多次尝试中收集的在线数据，根据过去决策的结果动态调整动作分布。在旅行商问题（TSP）和带容量限制的车辆路径问题（CVRP）上进行测试时，MEMENTO 表现出优于传统树搜索和策略梯度微调的性能，成功在 12 个评估任务中的 11 个上刷新了最新技术水平（SOTA）。

Summary

Routing problems are central to numerous real-world applications but remain notoriously difficult to solve due to their NP-hard nature. While heuristics offer the best trade-off between solution quality and scalability, and Reinforcement Learning (RL) provides a flexible framework for designing them, current learned methods struggle to adapt to specific instances and fully utilize available computational budgets.

To address these limitations, the authors introduce MEMENTO, an inference-time approach that utilizes memory to improve neural solvers. MEMENTO leverages online data gathered across repeated attempts to dynamically adjust action distributions based on the outcomes of past decisions. Tested on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP), MEMENTO demonstrates superior performance compared to traditional tree-search and policy-gradient fine-tuning, successfully pushing the state-of-the-art on 11 out of 12 evaluated tasks.

Paper Metadata

  • arXiv ID: 2406.16424 [cs.AI]
  • Subjects: Artificial Intelligence (cs.AI); Machine Learning (cs.LG)
  • Conference/Version: NeurIPS '25 version (v4, revised August 2026)
  • DOI: 10.48550/arXiv.2406.16424

Authors

  • Felix Chalumeau
  • Refiloe Shabe
  • Noah De Nicola
  • Arnu Pretorius
  • Thomas D. Barrett
  • Nathan Grinsztajn

Abstract

路径优化问题是许多现实世界应用的核心，但由于其（NP）难解的本质，依然充满挑战。在现有方法中，启发式算法通常在解的质量与可扩展性之间提供最佳平衡，使其非常适合工业应用。虽然强化学习（RL）为设计启发式算法提供了灵活的框架，但其在手工设计启发式算法之上的普及仍未完全实现。现有的学习型方法仍然缺乏适应特定算例以及充分利用可用计算预算的能力。

Routing Problems are central to many real-world applications, yet remain challenging due to their (NP-)hard nature. Amongst existing approaches, heuristics often offer the best trade-off between quality and scalability, making them suitable for industrial use. While Reinforcement Learning (RL) offers a flexible framework for designing heuristics, its adoption over handcrafted heuristics remains incomplete. Existing learned methods still lack the ability to adapt to specific instances and fully leverage the available computational budget.

当前最佳的方法要么依赖于预训练策略的集合，要么依赖于 RL 微调；因此未能充分利用预算约束内新获得的信息。为此，我们提出了 MEMENTO，这是一种在推理阶段利用记忆来改进神经求解器搜索的方法。MEMENTO 利用在多次尝试中收集的在线数据，根据先前决策的结果动态调整动作分布。

Current best methods either rely on a collection of pre-trained policies, or on RL fine-tuning; hence failing to fully utilize newly available information within the constraints of the budget. In response, we present MEMENTO, an approach that leverages memory to improve the search of neural solvers at inference. MEMENTO leverages online data collected across repeated attempts to dynamically adjust the action distribution based on the outcome of previous decisions.

我们在旅行商问题和带容量限制的车辆路径问题上验证了其有效性，证明了它优于树搜索和策略梯度微调；并展示了它可以与基于多样性的求解器进行零样本（zero-shot）组合。我们成功在大规模算例上训练了所有 RL 自回归求解器，并验证了 MEMENTO 的可扩展性与数据效率：在 12 个评估任务中的 11 个上刷新了最新技术水平（SOTA）。

We validate its effectiveness on the Traveling Salesman and Capacitated Vehicle Routing problems, demonstrating its superiority over tree-search and policy-gradient fine-tuning; and showing that it can be zero-shot combined with diversity-based solvers. We successfully train all RL auto-regressive solvers on large instances, and verify MEMENTO's scalability and data-efficiency: pushing the state-of-the-art on 11 out of 12 evaluated tasks.

Full-Text & Resources

Submission History

  • [v1] Mon, 24 Jun 2024 08:18:19 UTC (942 KB)
  • [v2] Mon, 7 Oct 2024 15:33:37 UTC (1,228 KB)
  • [v3] Mon, 3 Nov 2025 15:37:49 UTC (1,171 KB)
  • [v4] Mon, 24 Aug 2026 11:27:54 UTC (1,166 KB) — (Current Version)