用专家策略指导对抗路由，高效解决超大规模车辆路径问题。
OD-Gear: Online Decomposition and Group Sampling for Expert-Guided Adversarial Routing in Scalable Capacitated Vehicle Routing
- 结合遗传搜索与在线聚类分解，实现动态分组优化。
- 在10,000节点规模上达到当前最优性能，推理低延迟。
- 适合需要快速生成高质量解的工业级物流调度场景。
求解大规模容量受限车辆路径问题（CVRP）受限于传统启发式算法复杂度高、神经求解器泛化能力弱。本文提出OD-Gear，一种专家引导的对抗框架，融合混合遗传搜索（HGS）与在线重心聚类（BCC）分解，结合组内相对优化。通过高保真知识蒸馏，将专家启发式嵌入图注意力网络（GAT）策略中。最小最大对抗训练将分治策略转化为密集代理奖励，组采样策略利用相对解优势提升解的多样性与质量。该架构可在大规模图上实现无聚类高质量推理，有效规避传统分解开销。实验表明，OD-Gear在多数基准上达到最先进水平，在10,000节点规模仍具竞争力。该方法以低延迟提供启发式级解，为大规模CVRP提供了鲁棒且可扩展的解决方案。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。