用可微分运输模型一步解决车辆路径问题,效率更高且更鲁棒。
Neural Cluster First, Route Second: One-Shot Capacitated Vehicle Routing via Differentiable Optimal Transport

- 先聚类后路由,通过可微分最优传输实现端到端容量约束。
- 1000个点的实例误差低于4%,轻量模型仍保持5%差距。
- 零样本适配现实分布,适合大规模物流场景部署。
容量受限的车辆路径问题(CVRP)是现代末端配送的核心。当前神经组合优化方法采用自回归方式构建解,存在序列解码瓶颈、对空间对称性敏感及分布外泛化能力差的问题。本文重新审视经典的“聚类-先-路由-后”(CFRS)范式——该方法虽长期被认为渐近最优,却在神经组合优化中被忽视。我们提出 Neural CFRS,首个完全非自回归的一次性神经 CFRS 框架。通过可微分熵最优传输层端到端施加全局车队容量约束,生成连续运输计划以稀疏化精确容量分配求解器。理论证明该架构天然消除 $E(2)$ 空间对称性、路间排列对称性和路内遍历对称性。结合预训练空间词汇表,实现极致参数效率与零样本扩展能力。针对恒定容量下的真实空间分布,Neural CFRS 在 $N=1000$ 的分布外实例上误差小于 4%,即使为超轻量单层结构仍保持约 5% 间隙;在标准基准上无需调参即达 2.73% 优化差距(100规模)。
原文摘要 · Abstract (English)
The Capacitated Vehicle Routing Problem (CVRP) underpins modern last-mile logistics. Current Neural Combinatorial Optimization (NCO) methods construct CVRP solutions autoregressively, inheriting sequential decoding bottlenecks, sensitivity to spatial symmetries, and brittle out-of-distribution behavior. We revisit the classical Cluster-First-Route-Second (CFRS) paradigm -- long known to be asymptotically optimal but largely overlooked by NCO -- and argue that it is structurally aligned with the core strengths of deep learning: similarity and assignment over global context, rather than the construction of long sequential tours. We introduce Neural CFRS, the first purely non-autoregressive one-shot neural CFRS framework for the CVRP. It enforces global fleet-capacity constraints end-to-end via a differentiable entropic Optimal Transport layer, producing a continuous transport plan to sparsify an exact capacitated assignment solver. We provide formal theoretical guarantees that our architecture intrinsically abstracts away $E(2)$ spatial, inter-route permutation, and intra-route traversal symmetries. By equipping the framework with a pre-trained spatial vocabulary, we unlock extreme parameter efficiency and zero-shot scaling. Designed primarily for real-world spatial distributions under a constant capacity setting, Neural CFRS scales robustly to out-of-distribution $N=1000$ instances with a < 4% gap -- retaining an approximate 5% gap at this scale even as an ultra-lightweight, single-layer architecture. Furthermore, when deployed out-of-the-box on standard benchmarks, we achieve a highly competitive 2.73% optimality gap on size-100 problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。