COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space

Although Vehicle Routing Problems (VRP) are essential to many real-world systems, they remain computationally intractable at scale due to their combinatorial complexity. Traditional heuristics rely on handcrafted rules for local improvements and occasional \textit{jumps} to escape local minima, but often struggle to generalize across diverse instances. We introduce \textbf{COAgents}, a cooperative multi-agent framework that models the search process as a graph: nodes represent solutions, and edges correspond to either local refinements or large perturbations for diversification (i.e., jumps). A \textit{Partial Search Graph} (PSG) is dynamically constructed during search, enabling COAgents to train a Node Selection Agent and a Move Selection Agent to guide intensification, and a Jump Agent to trigger well-timed explorations of new regions. Unlike end-to-end learning approaches, COAgents cleanly separates problem-agnostic search control from compact domain-specific encoding, facilitating adaptability across tasks. Extensive experiments on the CVRP and VRPTW benchmarks show that COAgents remains competitive with several learn-to-search baselines on CVRP and sets a new state of the art among learning-based methods on the more challenging VRPTW instances, reducing the gap to the best-known solutions by 14\% at $N\!=\!100$ and 44\% at $N\!=\!50$ relative to the strongest neural solver (POMO), and by 21\% and 40\% respectively relative to ALNS. Code is available at https://github.com/mahdims/COAgents.

한 줄 요약

**[Vehicle Routing / Multi-Agent RL]** COAgents는 search 공간을 그래프로 모델링하고 Node·Move·Jump 3 에이전트가 협력 탐색, VRPTW에서 학습 기반 방법 SOTA, N=100 14%·N=50 44%로 POMO 대비 best-known 격차 단축.

핵심 기여도

VRP가 많은 실세계 시스템에 필수지만 조합 복잡성으로 대규모에서 계산 불가능 — 전통 heuristic은 local 개선과 local minima 탈출 jump에 손수 만든 규칙 사용, instance 일반화 어려움 진단.
COAgents 도입 — 협력적 멀티에이전트 프레임워크, search 과정을 그래프로 모델링(노드=해, 엣지=local refinement 또는 large perturbation jump).
Partial Search Graph(PSG)를 search 중 동적 구성 — Node Selection Agent·Move Selection Agent로 intensification 안내, Jump Agent로 well-timed exploration 트리거 학습.
종단 학습과 달리 problem-agnostic search control과 compact 도메인 특화 인코딩을 깔끔 분리, task 간 adaptability 촉진.

핵심 아이디어

VRP 등 조합 최적화의 학습 기반 가속은 종단 솔버 학습 대신, search 공간 자체를 그래프로 모델링하고 intensification과 diversification을 별도 학습 모듈로 분리해 problem-agnostic·도메인-specific 인코딩을 깔끔 분리하는 것이 일반화 핵심이다.

기술적 접근법

**방법론**: COAgents — 협력 멀티에이전트 search 프레임워크.
**핵심 기법**: (1) Search 공간 그래프 모델링(노드=해·엣지=local 또는 jump), (2) Partial Search Graph 동적 구성, (3) Node Selection Agent·Move Selection Agent로 intensification, (4) Jump Agent로 well-timed exploration, (5) Problem-agnostic search control과 compact 도메인 인코딩 분리.

주요 결과

CVRP에서 여러 learn-to-search baseline과 경쟁력 유지.
VRPTW에서 학습 기반 방법 중 new SOTA.
가장 강한 신경 솔버 POMO 대비 best-known 격차: N=100 14% 축소, N=50 44% 축소.
강력한 metaheuristic ALNS 대비: N=100 21% 축소, N=50 40% 축소.
코드 공개: github.com/mahdims/COAgents.

의의 및 한계

**의의**: VRP의 학습 기반 search에 멀티에이전트 분업 원리 적용, intensification/diversification 분리로 일반화 향상, VRPTW SOTA로 실용 가치, problem-agnostic search control의 다른 조합 문제 확장 잠재. **한계**: CVRP·VRPTW 중심으로 다른 routing variant(pickup-and-delivery, multi-depot)는 추가 검증, PSG 동적 구성의 메모리 비용, 매우 큰 instance 일반화는 후속.

실용적 활용

물류·택배·승차공유 라우팅 최적화.
조합 최적화의 학습 기반 search 일반 프레임워크.
도메인-specific encoding과 분리된 학습 가능 search.