Neural Cluster First, Route Second: One-Shot Capacitated Vehicle Routing via Differentiable Optimal Transport

Researchers introduce Neural CFRS, a non-autoregressive neural network framework that solves the Capacitated Vehicle Routing Problem by clustering nodes first, then routing—departing from sequential autoregressive methods. The approach uses differentiable optimal transport to enforce capacity constraints and achieves competitive results on benchmarks while scaling robustly to large, out-of-distribution instances.

Neural CFRS represents a meaningful shift in how machine learning approaches classical combinatorial optimization. Rather than following the dominant autoregressive paradigm that sequentially constructs solutions token-by-token, this framework resurrects the Cluster-First-Route-Second (CFRS) methodology from operations research—a mathematically proven approach that had been largely abandoned by the neural combinatorial optimization community. This architectural choice matters because it aligns problem structure with neural network strengths: global pattern recognition and assignment rather than sequential decision chains.

The technical innovation centers on differentiable optimal transport, which enables the network to enforce fleet-capacity constraints as a learned, differentiable operation rather than a post-hoc constraint. This allows end-to-end training while maintaining feasibility guarantees. The framework's ability to abstract away multiple symmetries—spatial invariance, inter-route permutations, and intra-route traversals—is formally guaranteed, reducing the learning burden compared to methods that must discover these invariances empirically.

For the logistics and optimization community, this work demonstrates practical viability at scale. The framework maintains a sub-4% optimality gap on 1,000-node out-of-distribution instances using a lightweight single-layer architecture, suggesting genuine robustness rather than benchmark overfitting. Parameter efficiency and zero-shot scaling via pre-trained spatial vocabularies open paths toward deployment on real-world problems where data scarcity and computational constraints are binding.

Looking forward, this approach could influence how the community frames neural optimization problems—prioritizing architectural alignment with problem structure over raw autoregressive scaling. Hybrid classical-neural methods may gain renewed attention in vehicle routing, supply chain optimization, and related domains where capacitated assignment remains central.

• →Neural CFRS achieves non-autoregressive one-shot solving of capacitated vehicle routing with formally guaranteed symmetry abstraction
• →Differentiable optimal transport layer enables end-to-end learning while enforcing capacity constraints without post-hoc feasibility repairs
• →Framework demonstrates sub-4% optimality gap on 1,000-node out-of-distribution instances, suggesting genuine robustness beyond benchmark performance
• →Pre-trained spatial vocabularies unlock zero-shot scaling and extreme parameter efficiency with single-layer architectures
• →Research revives classical operations research methodology (CFRS) overlooked by modern neural combinatorial optimization, proving algorithmic paradigm choice matters