COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space
Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun
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 and 44\% at 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.
AI Impact Assessments
(1 model)Scientific Impact Assessment: COAgents
1. Core Contribution
COAgents introduces a cooperative multi-agent framework for navigating the combinatorial search space of Vehicle Routing Problems. The key conceptual contribution is the Partial Search Graph (PSG), a dynamically constructed graph where nodes represent visited solutions and edges represent either local refinement moves or large perturbations ("jumps"). Three learned agents operate over this structure: a Node Selection Agent (which solution to expand next), a Move Selection Agent (which operator to apply), and a Jump Agent (when and how to escape local minima via learned restarts). This decomposition maps naturally onto the three fundamental decisions in iterative local search, replacing handcrafted heuristic rules with learned policies.
The paper distinguishes itself from prior hyper-heuristic and learn-to-search work by explicitly maintaining and reasoning over search history via the PSG, rather than making decisions based solely on the current solution state. The separation of problem-agnostic search control (GGCN + Transformer backbone) from problem-specific encoding (E2E modules) is a clean architectural choice that facilitates transferability.
2. Methodological Rigor
Architecture design is reasonable: GGCN layers capture local PSG structure, Transformers model long-range dependencies across the search history, and problem-specific E2E modules handle domain details. The weight-sharing across agents is justified for data efficiency.
Training methodology raises some concerns. The Node and Move Selection Agents are trained via supervised learning on labels derived from known near-optimal solutions, which means training quality is dependent on the quality of the reference solver (HGS). This is a somewhat circular dependency — the framework learns to mimic patterns from a strong classical solver rather than discovering genuinely novel search strategies. The Jump Agent is similarly trained against precomputed near-optimal targets. This supervised approach, while stable, limits the potential for the system to discover search strategies that surpass its training signal.
Experimental evaluation is mixed in rigor:
The ablation study (Table 3) is informative: removing the Jump Agent nearly doubles the optimality gap, confirming its importance. However, removing the Node Selection Agent has negligible effect (3.691% → 3.705%), questioning whether this agent genuinely contributes.
3. Potential Impact
The PSG concept is the most impactful idea — formalizing search history as a graph that agents can reason over is a general principle applicable beyond VRPs. If the framework scales and generalizes, it could influence how metaheuristics are designed across combinatorial optimization.
However, several factors limit near-term impact:
The open-source code release is a positive for reproducibility and community adoption.
4. Timeliness & Relevance
The paper addresses a genuine need: bridging the gap between handcrafted metaheuristics and neural approaches for combinatorial optimization. The multi-agent formulation is timely given the broader AI community's interest in agent-based systems. The focus on VRPTW, which has received less attention from neural methods compared to CVRP/TSP, fills a relevant gap.
However, the field is moving rapidly toward methods that scale to larger instances and achieve near-optimal performance with reasonable compute. COAgents' limitations on both fronts temper its timeliness.
5. Strengths & Limitations
Strengths:
Limitations:
Additional Observations
The formalization in Section 3, while interesting, is somewhat disconnected from the actual method. The paper defines jumps as edges making the search space connected and seeks shortest paths, but the actual training procedure uses supervised learning rather than optimizing any path-related objective. The gap between the theoretical framing and practical implementation is notable.
The comparison with ALNS (Section 5.3, Figure 5) is one of the paper's strongest empirical contributions, directly demonstrating the value of learned policies over handcrafted ones with the same underlying operators.
Generated May 21, 2026
Comparison History (28)
Paper 2 is likely to have higher scientific impact due to its broad relevance to AI alignment/safety and cognitive science: it introduces a generally applicable evaluation paradigm (using implausible category members) that can be reused across models and tasks, exposes systematic concept-boundary failures, and links them to downstream safety-relevant behaviors. This is timely and cross-disciplinary, potentially influencing benchmarking, interpretability, and safety practices. Paper 1 is innovative and rigorous for VRP optimization and may yield strong applied impact in logistics, but its influence is more domain-specific to routing/CO compared to the wider implications of concept alignment.
Paper 1 targets a widely used, community-facing regulatory science infrastructure (AOP-Wiki) and proposes data model expansions plus an evaluation framework to enable AI-ready evidence structuring, qAOPs, and tighter integration with NAMs—directly supporting policy-relevant risk assessment and animal-testing replacement. Its potential real-world and cross-field impact spans toxicology, biomedicine, One Health, data stewardship/FAIR standards, and AI-assisted knowledge modeling, making it timely and broadly influential. Paper 2 is methodologically strong and impactful within VRP optimization, but its breadth and downstream societal/regulatory leverage are narrower.
Paper 1 addresses the highly practical and widely studied domain of vehicle routing problems with a novel multi-agent framework (COAgents) that achieves state-of-the-art results on established benchmarks. Its combination of cooperative agents with a graph-based search representation is innovative and demonstrates strong empirical results (14-44% gap reductions). The framework's modularity and applicability across VRP variants gives it broad appeal. Paper 2 addresses a more niche problem (optimal observability/sensor selection for POMDPs) with impressive computational speedups but narrower applicability. Paper 1's practical relevance to logistics and operations research, plus code availability, suggests wider adoption and citation potential.
Paper 1 addresses a major limitation of current LLMs—their inherent passivity—by introducing a novel training paradigm that leverages latent user concerns. The ability to create proactive, goal-driven conversational agents has massive, immediate applications across industries like sales, education, and healthcare. While Paper 2 offers an impressive methodological advance for Vehicle Routing Problems, Paper 1's focus on unlocking new fundamental capabilities in foundational LLMs gives it a broader potential impact across the broader AI and NLP communities.
Paper 2 addresses KV cache compression for LLMs, a critical bottleneck affecting the entire LLM ecosystem. Its novel meta-token approach with dynamic composition and attention-flow integration for preserving evicted information tackles a widely relevant problem with broad applications. Paper 1, while solid work on VRP with multi-agent search, operates in a more specialized optimization niche. The LLM efficiency problem has far greater breadth of impact across fields, higher timeliness given explosive LLM adoption, and the proposed mechanisms (learnable orthogonal basis, Gumbel-Softmax selection, attention redistribution) offer more generalizable innovations.
Paper 1 addresses the Vehicle Routing Problem, a fundamental and economically critical combinatorial optimization challenge, with clear quantitative improvements over strong baselines. Its methodology is rigorously benchmarked on established datasets. In contrast, Paper 2 presents a niche dataset of food ingredient embeddings without demonstrating downstream task performance in the abstract, leading to a narrower scope of potential real-world applications and scientific impact.
Paper 1 is likely to have higher scientific impact due to its broader cross-domain relevance and timely contribution to evaluating when multi-agent AI adds value in real scientific inference settings. It introduces a benchmark spanning multiple scientific tasks with explicit baselines, ablations/null controls, frozen panels, and provenance/auditability—supporting methodological rigor and generalizable conclusions about coordination regimes. Paper 2 is strong and application-relevant (VRP) with promising performance, but its impact is narrower to combinatorial optimization and incremental within an active area of learning-based routing solvers.
Paper 1 offers a more technically novel and generalizable algorithmic contribution: a cooperative multi-agent learn-to-search framework with a dynamic partial search graph, validated with strong benchmark results and open-source code. Its rigor (quantitative SOTA comparisons on CVRP/VRPTW) and applicability to a broad class of combinatorial optimization problems suggest wider cross-field impact (OR, ML, logistics). Paper 2 presents a useful industry-relevant architecture for circular manufacturing, but architectural proposals typically yield narrower, harder-to-generalize scientific impact and less standardized evaluation than benchmarked algorithmic advances.
LACO addresses a timely and high-impact problem at the intersection of collaborative autonomous driving, foundation models, and multi-agent communication. Its training-free paradigm for adapting pretrained driving models to collaborative settings is highly novel, tackling fundamental challenges (latency, information loss) in V2V communication. The breadth of impact spans autonomous driving, multi-agent systems, and efficient communication. Paper 2, while solid with strong VRPTW results, addresses a more established optimization problem with incremental improvements. LACO's novelty in latent communication and its relevance to the rapidly growing autonomous driving field give it higher potential impact.
Paper 2 presents a concrete, implemented multi-agent framework (COAgents) with rigorous experimental evaluation, state-of-the-art results on established benchmarks, and available code. It offers a novel approach to combinatorial optimization with clear methodological contributions (PSG, separation of search control from domain encoding) and demonstrated improvements. Paper 1, while addressing an important topic (AI-native 6G), is a vision/position paper without concrete implementations or experimental validation, making its actual scientific impact more speculative and harder to measure.