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

• URL: http://arxiv.org/abs/2605.09301v1
• Date: Sun, 10 May 2026 03:53:59 GMT
• Title: Neural Cluster First, Route Second: One-Shot Capacitated Vehicle Routing via Differentiable Optimal Transport
• Abstract summary: We introduce Neural CFRS, the first purely non-autoregressive one-shot neural CFRS framework for the Capacitated Vehicle Routing Problem (CVRP)<n>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 solver.<n>By equipping the framework with a pre-trained vocabulary, we unlock extreme parameter efficiency and zero-shot scaling.
• Score: 3.248584983235657
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization [40.74618635552097]
  We propose a geometric self-supervised pre-training framework for routing graphs.<n>The framework learns robust structural representations prior to the policy optimization phase.<n>The proposed model exhibits remarkable computational efficiency, delivering speedups of up to two orders of magnitude over the exact solver Concorde.
  arXiv  Detail & Related papers  (2026-07-31T20:23:21Z)
• Complexity-Balanced Diffusion Splitting [20.558008394592097]
  Complexity-Balanced Splitting (CBS) is a principled framework for temporal capacity allocation.<n>CBS partitions the diffusion timeline into segments of equal approximation burden.<n>CBS consistently improves quality without increasing per-step inference cost.
  arXiv  Detail & Related papers  (2026-06-04T17:57:15Z)
• Scaling Parallel Sequence Models to Foundation-Scale Vision Encoders [123.58723804218151]
  Vision foundation models are bottlenecked by the quadratic cost of self-attention.<n>We present C-GSPN based on 2D spatial propagation propagation.
  arXiv  Detail & Related papers  (2026-05-30T14:29:43Z)
• OScaR: The Occam's Razor for Extreme KV Cache Quantization in LLMs and Beyond [50.440302567029654]
  Multi-modal intelligence has made the Key-Value cache a dominant memory bottleneck for efficient deployment.<n>In this work, we revisit the inherent limitations of the per-channel quantization paradigm.<n>We propose OScaR, an accurate and lightweight KV cache compression framework for X-LLMs.
  arXiv  Detail & Related papers  (2026-05-19T10:53:03Z)
• Alternating Gradient Flow Utility: A Unified Metric for Structural Pruning and Dynamic Routing in Deep Networks [52.153950303594684]
  We propose a decoupled kinetic paradigm inspired by Alternating Gradient Flow (AGF)<n>AGF accurately captures the network's structural "kinetic utility"<n>We design a hybrid routing framework that decouples AGF-guided offline structural search from online execution via zero-cost physical priors.
  arXiv  Detail & Related papers  (2026-03-12T18:19:21Z)
• RaBiT: Residual-Aware Binarization Training for Accurate and Efficient LLMs [5.782015253162346]
  Residual binarization enables matmul-free inference by stacking binary layers.<n>We propose RaBiT, a novel quantization framework that resolves coadaptation by algorithmically enforcing a residual hierarchy.<n>RaBiT achieves state-of-the-art performance, rivals even hardware-intensive Vector Quantization (VQ) methods, and delivers a $4.49times$ inference speed-up over full-precision models.
  arXiv  Detail & Related papers  (2026-02-05T06:41:11Z)
• CoCo-Fed: A Unified Framework for Memory- and Communication-Efficient Federated Learning at the Wireless Edge [50.42067935605982]
  We propose a novel Compression and Combination-based Federated learning framework that unifies local memory efficiency and global communication reduction.<n>CoCo-Fed significantly outperforms state-of-the-art baselines in both memory and communication efficiency while maintaining robust convergence under non-IID settings.
  arXiv  Detail & Related papers  (2026-01-02T03:39:50Z)
• Rethinking Autoregressive Models for Lossless Image Compression via Hierarchical Parallelism and Progressive Adaptation [75.58269386927076]
  Autoregressive (AR) models are often dismissed as impractical due to prohibitive computational cost.<n>This work re-thinks this paradigm, introducing a framework built on hierarchical parallelism and progressive adaptation.<n> Experiments on diverse datasets (natural, satellite, medical) validate that our method achieves new state-of-the-art compression.
  arXiv  Detail & Related papers  (2025-11-14T06:27:58Z)
• Flow-Opt: Scalable Centralized Multi-Robot Trajectory Optimization with Flow Matching and Differentiable Optimization [2.4149533870085174]
  Flow-Opt is a learning-based approach towards improving the computational tractability of centralized multi-robot trajectory optimization.<n>We show that we can generate trajectories of tens of robots in cluttered environments in a few tens of milliseconds.<n>Our approach also generates smoother trajectories orders of magnitude faster than competing baselines.
  arXiv  Detail & Related papers  (2025-10-10T09:43:18Z)
• Deep Hierarchical Learning with Nested Subspace Networks [53.71337604556311]
  We propose Nested Subspace Networks (NSNs) for large neural networks.<n>NSNs enable a single model to be dynamically and granularly adjusted across a continuous spectrum of compute budgets.<n>We show that NSNs can be surgically applied to pre-trained LLMs and unlock a smooth and predictable compute-performance frontier.
  arXiv  Detail & Related papers  (2025-09-22T15:13:14Z)
• Neural Combinatorial Optimization for Real-World Routing [15.136899433821894]
  Vehicle Routing Problems (VRPs) are a class of NP-hard problems ubiquitous in several real-world logistics scenarios.<n>NCO has emerged as a promising alternative to classical approaches to solve VRPs.<n>This work introduces RRNCO (Real Routing NCO) to bridge the gap of NCO between synthetic and real-world VRPs.
  arXiv  Detail & Related papers  (2025-03-20T13:57:33Z)
• Iterative Soft Shrinkage Learning for Efficient Image Super-Resolution [91.3781512926942]
  Image super-resolution (SR) has witnessed extensive neural network designs from CNN to transformer architectures. This work investigates the potential of network pruning for super-resolution iteration to take advantage of off-the-shelf network designs and reduce the underlying computational overhead. We propose a novel Iterative Soft Shrinkage-Percentage (ISS-P) method by optimizing the sparse structure of a randomly network at each and tweaking unimportant weights with a small amount proportional to the magnitude scale on-the-fly.
  arXiv  Detail & Related papers  (2023-03-16T21:06:13Z)
• Only Train Once: A One-Shot Neural Network Training And Pruning Framework [31.959625731943675]
  Structured pruning is a commonly used technique in deploying deep neural networks (DNNs) onto resource-constrained devices. We propose a framework that DNNs are slimmer with competitive performances and significant FLOPs reductions by Only-Train-Once (OTO) OTO contains two keys: (i) we partition the parameters of DNNs into zero-invariant groups, enabling us to prune zero groups without affecting the output; and (ii) to promote zero groups, we then formulate a structured-Image optimization algorithm, Half-Space Projected (HSPG) To demonstrate the effectiveness of OTO, we train and
  arXiv  Detail & Related papers  (2021-07-15T17:15:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.