COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space
Authors: Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed et al.
Summary
arXiv:2605. 20618v1 Announce Type: new Abstract: Although Vehicle Routing Problems (VRP) are essential to many real-world systems, they remain computationally intractable at scale due to their combinatorial complexity.
Relevance
Read next because COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space overlaps with clean result "LoRA persona trained on alone emits at 23.5% when a co-trained partner learns ..., vs 0% control on Qwen2.5-7B-Instruct (MODERATE confidence)", clean result "Leakage rate is a usable signal for recovering trigger-shaped phrases on Gaperon-1125-1B without knowing the hidden trigger itself (MODERATE confidence)", clean result "Language-mismatch LoRA SFT on Qwen2.5-7B leaks the trained completion language into bystander directives the model was never trained on, absent under same-language SFT (LOW confidence)". Matching terms: code, strong, text, line, rate, control, lora, model. Source: arxiv cs.AI (Artificial Intelligence).
Threat model
Potential threat/caveat for clean result "LoRA persona trained on alone emits at 23.5% when a co-trained partner learns ..., vs 0% control on Qwen2.5-7B-Instruct (MODERATE confidence)": this item discusses benchmark.
Abstract
arXiv:2605.20618v1 Announce Type: new Abstract: 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.