OD-Gear: Online Decomposition and Group Sampling for Expert-Guided Adversarial Routing in Scalable Capacitated Vehicle Routing

arXiv:2602.00488v3 Announce Type: replace Abstract: Solving large-scale capacitated vehicle routing problems (CVRP) is hindered by the high complexity of classical heuristics and the limited generalization of neural solvers. To bridge this gap, we propose OD-Gear, an expert-guided adversarial framework that integrates hybrid genetic search (HGS) and online barycenter clustering (BCC) decomposition with group-relative optimization. OD-Gear internalizes expert heuristics into a graph attention network (GAT)-based policy via high-fidelity knowledge distillation. Our minimax adversarial training distills divide-and-conquer strategies into dense surrogate rewards, while a group-sampling strategy exploits relative solution advantages to promote both diversity and quality. This architecture enables high-quality, clustering-free inference on massive graphs, effectively bypassing the overhead of traditional decomposition. Empirical results demonstrate that OD-Gear achieves state-of-the-art (SOTA) performance across most benchmarks, remaining highly competitive at the 10,000-node scale. By providing heuristic-quality solutions with low-latency, OD-Gear offers a robust and scalable framework for large-scale CVRP.

Source: arXiv cs.LG | 2026-08-11