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

Abstract

The Capacitated Vehicle Routing Problem (CVRP) underpins modern last-mile logistics, where routing decisions recur over the same fixed service area, like a city. In this setting, routing problems share a fixed set of potential customer locations, while active customers and demands vary between instances. We study how this spatial support can be exploited through reusable learned representations and design our method around three symmetries of the symmetric Euclidean CVRP: $E(2)$ transformations, vehicle-route permutations, and tour reversal. We introduce Neural Cluster-First--Route-Second (CFRS), a neural extension of the Fisher--Jaikumar framework that predicts seed-selection scores and customer-to-cluster assignment costs non-autoregressively and respects the three symmetries. A differentiable entropic optimal transport layer provides capacity-aware supervision and guides discrete capacitated assignment, followed by independent traveling salesman subproblems for route recovery. Component ablations show consistent benefits from learned seed selection, while learned assignment costs perform best near the training size and classical FJ costs perform better at larger sizes under exact decoding. On the fixed-support distribution with constant capacity, a model trained on $N=100$ achieves a $3.77\%$ routing gap relative to HGS at $N=1000$ without retraining. A shallow variant with one attention layer in each transformer achieves a $5.08\%$ gap at this scale, with spatial embeddings consistently improving routing quality over raw coordinates. Embedding interpolation further accommodates entirely unseen customer locations without retraining. On standard CVRP benchmarks, a separately trained model achieves a $2.73\%$ routing gap relative to LKH-3 at $N=100$.