Problem

Traditional methods for Vehicle Routing Problems (VRPs), such as exact algorithms and heuristics, often face challenges with scalability, computational complexity, and limited generalization, particularly when dealing with large or varied instances. Existing neural network-based solvers, including autoregressive models and diffusion models, also present significant limitations. Autoregressive solvers often lack the ability to effectively distinguish between similar nodes, struggle to integrate problem-specific constraints, and can suffer from "oversmoothing" in attention mechanisms, which leads to performance degradation on complex tasks or long decision sequences. Diffusion models, while promising, typically require high-quality labeled data and extensive post-processing to generate valid solutions, limiting their application primarily to simpler problems like the Traveling Salesman Problem (TSP) rather than the more constraint-rich VRP variants. Furthermore, improvement heuristics, while effective, are often computationally expensive and not suitable for real-time applications. A core issue identified across many learning-based VRP solvers is their "weak constraint awareness," making them brittle when small, compounded errors can lead to invalid or suboptimal solutions.

Method

The authors propose a novel "constraint-mask guided fusion framework" that integrates a discrete noise graph diffusion model with an autoregressive encoder-decoder. The method begins with data augmentation, employing both geometric transformations (axial symmetries) and demand variations (inversion, random reassignment, cyclic permutations) to create diverse instances that map to consistent optimal solutions, thereby improving the model's robustness. A graph diffusion model is then trained to generate a binary "constraint matrix." This matrix indicates which nodes belong to the same vehicle tour and is learned by corrupting optimal solution-derived matrices with discrete noise in a forward process, then training the model to reconstruct the original matrices in a reverse denoising process. Discrete Bernoulli noise is favored for its suitability with binary data. The generated constraint matrix acts as a "learned topological mask" within a GAT-based encoder, helping to mitigate oversmoothing by restricting message passing to only plausible subpath relationships. This encoder fuses global node representations (from a pre-trained GNN) with local representations (from a GAT guided by the sparse constraint mask). The decoding process uses a dual-pointer fusion decoder, combining a local pointer, restricted by the constraint matrix, and a global pointer, which attends to all nodes. This dual approach provides a targeted bias, balancing exploration and exploitation during decision-making. An auxiliary perception layer and a heuristic savings term are also incorporated into the decoder's attention mechanism to further refine solution generation. The training regimen involves a supervised pre-training phase for the graph diffusion model using labels generated by Hybrid Genetic Search (HGS), followed by an unsupervised reinforcement learning phase for the encoder-decoder using REINFORCE with a self-critic baseline and multi-start strategies.

Results

On synthetic benchmarks matching the training distribution (20, 50, and 100 nodes), the proposed model achieved state-of-the-art performance among learning-based solvers, showing a 2.52% gain without inference augmentation and an additional 0.19% with augmentation. It also demonstrated a competitive efficiency advantage. For out-of-distribution generalization on CVRPLIB instances, the model delivered superior solution quality and competitive inference speed on in-distribution data, and better generalized to problems up to 100 nodes (0.35% gain) compared to contemporaries. However, performance deteriorated for larger instances (e.g., 200+ nodes). A comprehensive evaluation on the complex XML100 dataset (10,000 instances, 100 nodes), which features diverse distributions, revealed an average gap of approximately 5.77% from the optimal solution. The model achieved smaller gaps and lower variability than existing state-of-the-art models like LEHD, outperforming it in 82.2% of instances, particularly in scenarios with tight customer clustering and limited demand heterogeneity, where it showed an average improvement of 1.2%. Ablation studies confirmed the effectiveness of the graph-diffusion prior masks in both the encoder and decoder. Discrete Bernoulli noise proved more suitable for constraint matrix generation than continuous Gaussian noise. Fine-tuning the pre-trained GAT encoder improved synthetic data performance but harmed OOD generalization, leading to freezing the GAT in the final model for robustness. Hyperparameter analysis suggested 50 diffusion inference steps as an optimal trade-off between accuracy and efficiency, and highlighted that moderate GAT depth is beneficial, while excessive depth can cause oversmoothing.

Implications

The proposed Constraints Matrix Diffusion based Generative Neural Solver significantly advances the field of neural combinatorial optimization by effectively capturing and leveraging VRP constraints. This framework achieves state-of-the-art performance on synthetic datasets and public benchmarks, notably mitigating the issue of oversmoothing in node embeddings, especially in tightly clustered or low-demand heterogeneity scenarios. The research exposes the inherent performance limitations of current autoregressive models in VRPs, demonstrating that while supervised constraint priors enhance performance, they do not guarantee instance-level optimality. Future research directions suggested include exploring Mixture of Experts (MOE) neural solvers, which could be tailored to specific instance-level structures, and developing more robust methods for small to medium-scale VRP settings that can handle heterogeneous feature distributions more effectively. The findings underscore the ongoing challenge of achieving robust zero- or few-shot generalization in neural combinatorial optimization and call for continued innovation in this area.