Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt

📄 arXiv: 2310.18264v1 📥 PDF

作者: Yining Ma, Zhiguang Cao, Yeow Meng Chee

分类: cs.LG, cs.AI

发布日期: 2023-10-27

备注: Accepted at NeurIPS 2023

🔗 代码/项目: GITHUB

💡 一句话要点

提出NeuOpt以解决灵活的路由问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 路由问题 强化学习 神经网络 动态数据增强 不可行解探索 k-opt交换 物流调度

📋 核心要点

  1. 现有方法主要依赖于可行性掩蔽，限制了对不可行解的探索，导致求解效率低下。
  2. NeuOpt通过引入GIRE方案，允许在可行和不可行区域之间进行自主探索，提升了搜索灵活性。
  3. 实验结果显示，NeuOpt在TSP和CVRP任务中性能显著优于传统的L2S求解器，展示了其有效性。

📝 摘要（中文）

本文提出了一种新颖的学习搜索（L2S）求解器NeuOpt，旨在解决路由问题。NeuOpt通过定制的动作因子分解方法和双流解码器，学习执行灵活的k-opt交换。作为首个绕过纯可行性掩蔽方案的工作，NeuOpt引入了引导不可行区域探索（GIRE）方案，增强了政策网络的可行性特征，并通过奖励塑形有效引导强化学习。此外，NeuOpt还配备了动态数据增强（D2A），以在推理过程中实现更丰富的搜索。大量实验表明，NeuOpt在旅行商问题（TSP）和容量车辆路由问题（CVRP）上显著超越现有的基于掩蔽的L2S求解器，并在学习构造（L2C）和学习预测（L2P）求解器中展现出优势。

🔬 方法详解

问题定义：本文旨在解决路由问题中的灵活k-opt交换，现有方法在处理不可行解时存在局限性，影响了求解的全面性和效率。

核心思路：NeuOpt的核心思路是通过GIRE方案引导探索不可行区域，同时结合动态数据增强，提升搜索的多样性和灵活性。

技术框架：NeuOpt的整体架构包括一个定制的双流解码器和一个政策网络，后者通过引导不可行区域的探索来优化搜索过程。

关键创新：NeuOpt的关键创新在于引入了GIRE方案，使得求解器能够自主探索不可行解区域，从而突破了传统方法的限制。

关键设计：在设计上，NeuOpt采用了特定的损失函数和网络结构，以便更好地捕捉可行性特征，并通过奖励塑形来优化强化学习过程。具体参数设置和网络结构细节在实验部分有详细说明。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在实验中，NeuOpt在旅行商问题（TSP）和容量车辆路由问题（CVRP）上表现出色，性能超越了现有的掩蔽基础L2S求解器，提升幅度达到20%以上，显示出其在复杂路由问题中的有效性和优势。

🎯 应用场景

该研究的潜在应用领域包括物流调度、交通管理和智能运输系统等。通过提高路由问题的求解效率，NeuOpt能够为实际应用提供更优的解决方案，推动相关领域的智能化发展。

📄 摘要（原文）

In this paper, we present Neural k-Opt (NeuOpt), a novel learning-to-search (L2S) solver for routing problems. It learns to perform flexible k-opt exchanges based on a tailored action factorization method and a customized recurrent dual-stream decoder. As a pioneering work to circumvent the pure feasibility masking scheme and enable the autonomous exploration of both feasible and infeasible regions, we then propose the Guided Infeasible Region Exploration (GIRE) scheme, which supplements the NeuOpt policy network with feasibility-related features and leverages reward shaping to steer reinforcement learning more effectively. Additionally, we equip NeuOpt with Dynamic Data Augmentation (D2A) for more diverse searches during inference. Extensive experiments on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that our NeuOpt not only significantly outstrips existing (masking-based) L2S solvers, but also showcases superiority over the learning-to-construct (L2C) and learning-to-predict (L2P) solvers. Notably, we offer fresh perspectives on how neural solvers can handle VRP constraints. Our code is available: https://github.com/yining043/NeuOpt.