[Paper] 神经路由求解器综述

Source: arXiv - 2602.21761v1

概述

Neural Routing Solvers (NRSs) 是一种新型的深度学习模型，旨在通过学习人工设计启发式算法使用的“经验法则”来解决车辆路径问题（VRPs）。本综述论文阐明了 NRS 的启发式本质，将快速增长的文献组织成清晰的分类体系，并提出了一种更为现实的方式来评估这些模型在真实世界中的泛化能力。

关键贡献

• 以启发式为中心的视角： 将 NRS 研究重新定义为经典路径启发式（例如 savings、insertion、local search）的演进，这些启发式现在是通过学习而非手工编码实现的。
• 层次化分类法： 引入一个三层分类（问题范围 → 启发式原理 → 架构族），使得在文献中快速定位任何 NRS 成为可能。
• 面向泛化的评估流程： 设计了一个基准，用于在分布外（OOD）实例上测试模型，涵盖规模、地理和需求模式的变化——解决现有流程的过拟合问题。
• 全面的实证比较： 对代表性 NRS 在传统和新评估流程下进行正面对比研究，揭示隐藏的性能差距和鲁棒性问题。
• 开源工具箱： 发布分类法、数据集生成器和评估脚本的代码，支持可复现的研究和快速原型开发。

方法论

1. 文献映射： 作者收集了 70 多篇 NRS 论文（覆盖 2018‑2024 年），并为每篇论文标注了 (a) 所针对的 VRP 变体，(b) 所模拟的启发式原理（构造、改进或混合），以及 (c) 使用的神经网络架构（图神经网络、Transformer、强化学习代理等）。
2. 分类构建： 基于这些标注，作者构建了类似树状的层级结构：
   • 第 1 级 – 问题范围： CVRP、VRPTW、PDPTW 等。
   • 第 2 级 – 启发式原理： 构造（例如，学习的 savings 方法），改进（学习的局部搜索移动），混合（学习的元启发式）。
   • 第 3 级 – 架构族： 基于 GNN 的编码器、基于注意力的解码器、RL 策略网络、扩散模型等。
3. 评估流程：
   • 传统流程： 在固定的一组实例上训练（通常来自单一分布），并在规模相似、同分布的实例上测试。
   • 通用化流程（本文提出）： 创建多个测试套件，分别在规模（小 → 大）、空间分布（聚类 vs. 均匀）和需求随机性上有所差异。模型仅训练一次，然后在所有套件上进行评估，以模拟实际部署中问题特征会变化的情形。
4. 基准测试： 选取 10 个具有代表性的 NRS（例如 Attention Model、POMO、Neural Large‑Neighbourhood Search、基于图的 RL），在标准 CVRP 数据集（Solomon、Augerat）以及 OOD 套件上运行。度量指标包括解的质量（相对于最优/最佳已知解的百分比差距）、推理速度以及鲁棒性（在 OOD 集合上的方差）。

结果与发现

关键要点

• 许多在传统流水线下看似出色的 NRS，在面对 OOD 实例时质量下降 2‑5 倍。
• 融入 局部搜索 或 邻域探索（例如 NLNS）的架构比纯端到端序列模型具有更好的泛化能力。
• 推理速度仍是 NRS 的显著优势，但在生产使用时必须权衡其鲁棒性。

实际意义

• 对于物流软件供应商： 调查表明，将一个普通的基于注意力的 NRS 插入现有的路径规划引擎，可能在静态、特征明确的路线中快速取得成效，但对于订单模式多变的动态车队而言，需要更为稳健的混合方案（构建 + 学习式改进）。
• 对于构建自定义路由解决方案的开发者： 该分类法帮助你选择起点——例如，如果你已经拥有一个启发式插入算法，可以用基于 GNN 的策略替换其决策规则，而无需从头重建。
• 边缘部署： 由于大多数 NRS 在 GPU/TPU 上的推理时间仅为毫秒级，它们适用于实时调度，但仍需在与城市地理和需求高峰相匹配的 OOD 数据上进行验证。
• 工具与可重复性： 已发布的工具箱只需一条命令即可生成 OOD 基准套件，便于将 NRS 评估集成到 CI 流水线中。

限制与未来工作

• 数据集偏差： 调查的论文主要关注 CVRP 和 VRPTW；其他复杂变体（例如随机需求、多模式车队）仍然研究不足。
• 可扩展性上限： 虽然推理速度快，但训练仍需大量合成数据和 GPU 时长，限制了小公司的可及性。
• 可解释性： 学到的启发式方法常常不透明；调查呼吁开发从 NRS 中提取人类可读规则的方法，以促进信任和合规。
• 未来方向：
  1. 覆盖更广泛 VRP 变体的统一基准套件。
  2. 元学习方法，使单一 NRS 能通过少量微调适应新分布。
  3. 将 NRS 与经典运筹学求解器更紧密结合（例如，使用 NRS 为混合整数规划生成热启动）。

作者

• Yunpeng Ba
• Xi Lin
• Changliang Zhou
• Ruihao Zheng
• Zhenkun Wang
• Xinyan Liang
• Zhichao Lu
• Jianyong Sun
• Yuhua Qian
• Qingfu Zhang

论文信息

• arXiv ID: 2602.21761v1
• 分类: math.OC, cs.AI, cs.LG, cs.NE
• 发表时间: 2026年2月25日
• PDF: 下载 PDF