OD-DEAL: Dynamic Expert-Guided Adversarial Learning with Online Decomposition for Scalable Capacitated Vehicle Routing Dongbin Jiao, Zisheng Chen, Xianyi Wang, Jintao Shi, Shengcai Liu, Shi Yan Abstract Solving large-scale capacitated vehicle routing problems (CVRP) is hindered by the high complexity of heuristics and the limited generalization of neural solvers on massive graphs. We propose OD-DEAL, an adversarial learning framework that tightly integrates hybrid genetic search (HGS) and online barycenter clustering (BCC) decomposition, and leverages high-fidelity knowledge distillation to transfer expert heuristic behavior. OD-DEAL trains a graph attention network (GAT)–based generative policy through a minimax game, in which divide-and-conquer strategies from a hybrid expert are distilled into dense surrogate rewards. This enables high-quality, clustering-free inference on large-scale instances. Empirical results demonstrate that OD-DEAL achieves state-of-the-art (SOTA) real-time CVRP performance, solving 10000-node instances with near-constant neural scaling. This uniquely enables the sub-second, heuristic-quality inference required for dynamic large-scale deployment. 1 Introduction The capacitated vehicle routing problem (CVRP) is a fundamental NP-hard challenge in modern logistics and supply chain management ( 33 ; 21 ; 39 ) . Due to the combinatorial explosion of the search space, traditional exact and heuristic solvers encounter prohibitive computational overhead on large-scale instances ( 22 ; 7 ) . Neural combinatorial optimization (NCO) has recently emerged as a transformative paradigm, leveraging deep learning to approximate optimal routing policies with end-to-end neural inference ( 38 ) . Despite their speed, current neural solvers face a critical scalability-optimality bottleneck: supervised approaches are often restricted by static, expensive labels, while reinforcement learning (RL) methods typically suffer from sparse reward signals and poor generalization ( 2 ; 11 ; 23 ) . Furthermore, standard Transformer-based architectures frequently are prone to mode collapse, limiting solution diversity and structural integrity on massive graphs. To address these limitations, generative flow networks (GFlowNets) ( 3 ; 42 ) have been proposed to sample diverse trajectories with probabilities proportional to a reward function. Recent flow-based models, such as AGFN ( 44 ) improves solution diversity, but it lacks the structural inductive biases and expert regularization required for large-scale optimization. By neglecting local signals in favor of holistic objectives, such solvers fail to capture fine-grained structures, resulting in suboptimal performance ceilings and reduced training stability. In this work, we propose OD-DEAL, an expert-guided adversarial learning framework with online decomposition. Grounded in the GFlowNet paradigm, OD-DEAL bridges the gap between the inference efficiency of neural methods and the solution quality of state-of-the-art (SOTA) heuristics. Unlike standard RL, OD-DEAL reformulates route construction as a stochastic flow matching problem. By utilizing the trajectory balance (TB) objective, the model learns a policy that ensures precise distributional alignment with a high-performance expert manifold. At the core of our framework is a graph attention network (GAT) generator, specifically designed to capture the intricate, non-linear dependencies between long-range spatial proximity, heterogeneous customer demands, and residual vehicle capacity. To overcome reward sparsity, we introduce a dynamic expert oracle that synergizes hybrid genetic search (HGS) ( 35 ) with online barycenter clustering (BCC) decomposition ( 31 ) . This oracle provides high-fidelity demonstrations of “divide-and-conquer” logic, which are distilled into the generator via an adversarial minimax framework. Through a minimax game against a learned discriminator, the generator distills this decomposition logic into dense surrogate rewards, allowing the policy to internalize strategic partitioning and local search without explicit clustering at runtime. Empirical results demonstrate that OD-DEAL achieves SOTA real-time CVRP performance through near-constant neural scaling to large-scale instances. Our contributions are as follows: (i) We propose OD-DEAL, which integrates a GAT within an adversarial GFlowNet framework to model complex spatial-demand dependencies for end-to-end VRP inference. (ii) We introduce a hybrid expert oracle synergizing HGS with online BCC decomposition. This “divide-and-conquer” strategy enables the generator to implicitly internalize complex topological logic. (iii) Experimental results show that OD-DEAL achieves a real-time CVRP SOTA through GAT-based modeling and expert distillation of decomposition-augmented heuristics. It scales near-constantly to 10000 nodes, providing the sub-second, heuristic-quality inference essential for dynamic large-scale deployment. 2 Related Work Heuristics and Decomposition for Large-scale VRP. The SOTA in VRP is currently defined by heuristics such as HGS ( 35 ; 36 ) and LKH-3 ( 13 ) . These solvers achieve near-optimal accuracy through sophisticated local search and population-based diversity management. However, they encounter a “scalability wall” as the combinatorial search space expands, rendering global optimization on massive instances computationally prohibitive. To mitigate this, research has shifted toward decomposition strategies ( 48 ; 31 ; 41 ; 46 ; 15 ; 47 ) , specifically clustering-based approaches that partition global problems into tractable sub-problems. OD-DEAL leverages these high-performance heuristics not as standalone solvers, but as a dynamic expert oracle to provide high-fidelity supervisory signals for neural training. Neural Combinatorial Optimization (NCO). NCO reframes the VRP as a data-driven policy approximation problem ( 5 ; 45 ) . Constructive neural solvers typically utilize graph neural networks (GNNs) or Transformers to generate solutions end-to-end ( 18 ; 19 ; 9 ; 25 ) . While architectures like GAT effectively capture heterogeneous node features and spatial dependencies ( 8 ; 9 ; 24 ) , most solvers rely on policy gradient methods (e.g., REINFORCE ( 37 ) ) that struggle with sparse reward signals and poor generalization to large-scale distributions ( 5 ; 38 ; 40 ) . Furthermore, standard architectures often suffer from mode collapse, failing to represent the multimodal nature of optimal routing for large-scale CVRP. We address these limitations by adopting the GFlowNet paradigm ( 4 ) , which facilitates robust exploration and better represents the solution distribution through flow consistency. Adversarial Learning and Knowledge Distillation Knowledge distillation (KD) via imitation learning is a common approach to bridge the gap between heuristic precision and neural speed ( 6 ; 32 ; 7 ) . However, pure imitation often suffers from exposure bias and fails to generalize when the student deviates from expert trajectories. GflowNets mitigates this by framing optimization as a distribution matching task rather than point-wise replication, compelling the model to internalize the underlying structural manifold of expert-like solutions ( 16 ; 17 ) . Recent advancements, such as AGFN ( 44 ; 43 ) , integrate adversarial objectives with flow-based sampling to provide denser training signals. OD-DEAL differentiates itself by integrating a decomposition-augmented expert directly into the adversarial loop. By coupling the structural discriminative power of generative adversarial networks (GANs) with the scalability of clustering-based heuristics, our framework internalizes high-level “divide-and-conquer” logic, ensuring both inference efficiency and near-optimal performance at large-scale. 3 Preliminaries CVRP Definition. The CVRP is generally defined over a complete graph G(V,E) , where V=\{v_{0}\}\cup V_{c} consists of a single depot v_{0} and N customer nodes V_{c}=\{v_{1},\dots,v_{N}\} . Each edge (i,j)\in E is associated with a non-negative travel cost c_{ij} , and each customer i\in V_{c} has a non-negative demand d_{i} . A fleet of K identical vehicles, each with capacity Q , is available to service the customers. The CVRP seeks to identify a set of optimal vehicle trajectories that minimize the aggregate cost \sum c_{ij} subject to: (i) each customer is assigned to exactly one route, (ii) the sum of demands on every route does not exceed the vehicle capacity Q , and (iii) all routes starting and ending at the depot. A comprehensive integer linear programming (ILP) formulation, is provided in Appendix Sections A.1 and E.1 . Learning to Solve CVRPs. NCO models the CVRP as an autoregressive process where a policy P_{\theta}(\boldsymbol{a}|s)=\prod_{t=1}^{T}p_{\theta}(a_{t}|s,\boldsymbol{a}_{