OD-Gear: 온라인 분해 및 그룹 샘플링을 활용한 전문가 지향적 적대적 라우팅 - 확장 가능한 용량 제약 차량 경로 문제

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

대규모 용량 제약 차량 경로 문제(CVRP)를 해결하는 데 있어, 기존 휴리스틱 방법의 높은 복잡성과 신경망 기반 솔버의 제한적인 일반화 성능은 큰 걸림돌이었습니다. 이러한 문제를 해결하기 위해, 우리는 전문가 지향적 적대 학습 프레임워크인 OD-Gear를 제안합니다. OD-Gear는 하이브리드 유전 알고리즘(HGS)과 온라인 배리센터 클러스터링(BCC) 분해를 그룹 상대 최적화와 통합합니다. 또한, 고정밀 지식 증류를 통해 전문가 휴리스틱을 그래프 어텐션 네트워크(GAT) 기반 정책에 내재화합니다. 우리의 미니맥스 적대 학습은 나눗셈 및 정복 전략을 밀집된 보상으로 변환하며, 그룹 샘플링 전략은 상대적인 솔루션 장점을 활용하여 다양성과 품질을 모두 향상시킵니다. 이러한 아키텍처는 전통적인 분해 방식의 오버헤드를 효과적으로 우회하면서 대규모 그래프에 대한 고품질 클러스터링-프리 추론을 가능하게 합니다. 실험 결과, OD-Gear는 대부분의 벤치마크에서 최고 성능(SOTA)을 달성했으며, 10,000 노드 규모에서도 높은 경쟁력을 유지합니다. OD-Gear는 낮은 지연 시간으로 휴리스틱 수준의 솔루션을 제공함으로써, 대규모 CVRP를 위한 강력하고 확장 가능한 프레임워크를 제시합니다.

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.