💻 computer science

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

COAgents introduces a cooperative multi-agent framework that models the Vehicle Routing Problem search space as a dynamically constructed graph to separate problem-agnostic search control from domain-specific encoding, achieving state-of-the-art performance among learning-based methods on VRPTW benchmarks by significantly reducing the gap to best-known solutions.

Original authors: Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a logistics manager trying to figure out the most efficient way for a fleet of delivery trucks to visit 100 different houses. This is a classic "Vehicle Routing Problem." The catch? There are so many possible routes that even the fastest supercomputers can't check them all. It's like trying to find the single best path through a massive, foggy maze where every turn you take might lead to a dead end.

For decades, humans have solved this by writing strict rulebooks: "If you see a house on the left, turn right." But these rulebooks are brittle. If the city layout changes slightly, the rules break, and experts have to spend weeks rewriting them.

Enter COAgents, a new system created by researchers at Huawei. Instead of a rigid rulebook, COAgents uses a team of three "AI detectives" that work together to explore the maze, learn from their mistakes, and find better paths than ever before.

Here is how it works, using simple analogies:

1. The Map of the Maze: The "Partial Search Graph"

Imagine the AI isn't just looking at the current route; it's drawing a map of every path it has ever tried.

Nodes (The Dots): Each dot on the map is a specific delivery route the AI has tested.
Edges (The Lines): The lines connecting the dots show how the AI got from one route to the next (e.g., "We swapped two houses on the route").
The "Partial" part: The AI can't draw the entire infinite maze, so it only keeps a "partial" map of the interesting parts it has visited so far. This map is the team's shared memory.

2. The Three AI Agents

The magic happens because three different AI agents look at this map and make different decisions, just like a sports team with specific roles:

The Scout (Node Selection Agent):
- Role: "Which route should we look at next?"
- Analogy: Imagine you are in a library with thousands of books. The Scout doesn't pick a book at random. It looks at your "reading history" (the map) and says, "Hey, that route over there looks promising; it's close to a good solution. Let's focus on that one." It prevents the team from wasting time on dead ends.
The Mechanic (Move Selection Agent):
- Role: "How do we improve this specific route?"
- Analogy: Once the Scout picks a route, the Mechanic steps in. It has a toolbox of tricks (like swapping two stops or reordering a street). It looks at the current route and says, "If we swap these two houses, the truck saves 5 minutes. Let's do that!" It's the expert at making small, local improvements.
The Explorer (Jump Agent):
- Role: "We're stuck! Let's try something totally new."
- Analogy: Sometimes, the Scout and Mechanic get stuck in a loop, making tiny improvements that don't actually help. They are stuck in a "local valley." The Explorer is the agent that says, "Forget this path. Let's jump to a completely different part of the map." It generates a brand-new route from scratch based on what it learned from the past, helping the team escape the trap and find a better valley.

3. How They Work Together

The process is a continuous loop:

The Scout picks a route from the history map.
The Mechanic tries to tweak it to make it better.
If they keep tweaking and not getting much better, the Explorer jumps in, creates a fresh route, and adds it to the map.
The team repeats this until they run out of time.

Why This is a Big Deal

The paper claims that this team-based approach is a game-changer, especially for difficult problems like VRPTW (where trucks have strict time windows, like "must arrive between 2:00 PM and 2:30 PM").

Beating the Best: On these tough tests, COAgents beat the previous best AI solvers by a significant margin. For example, with 100 stops, it reduced the gap to the perfect solution by 14% compared to the strongest previous AI, and by 44% compared to another top method.
Learning vs. Rules: Unlike old methods that rely on human-written rules, COAgents learns how to search. It doesn't need a human to tell it how to fix a specific problem; it figures out the best strategy by looking at its own history.
Adaptability: Because the "brain" (the agents) is separate from the "rules of the game" (the specific city layout), you can easily swap the game rules (e.g., change from delivery trucks to drone delivery) without rebuilding the whole AI.

The Trade-off

The paper is honest about one downside: Speed.
Because COAgents is constantly drawing its map, checking history, and running three different agents, it takes longer to run than some simpler, faster methods that just build a route once and stop. However, the authors argue that for the hardest problems where finding the best solution matters more than speed, this extra time is worth it.

In summary: COAgents is like a smart, collaborative team of explorers who keep a detailed journal of their journey. Instead of blindly guessing or following a static rulebook, they use their shared history to know when to dig deeper, when to tweak their path, and when to take a giant leap to a new territory, ultimately finding better solutions than anyone else has before.

Technical Summary: COAgents – Multi-Agent Framework for Routing Problems

Problem Statement

Vehicle Routing Problems (VRPs), including the Capacitated Vehicle Routing Problem (CVRP) and the Vehicle Routing Problem with Time Windows (VRPTW), are central to logistics and manufacturing but remain computationally intractable at scale due to their combinatorial complexity. Traditional heuristic methods rely on handcrafted rules for local improvements and diversification (jumps) to escape local minima. However, these static rule sets often lack generalization across diverse instances, require extensive domain expertise for tuning, and cannot adapt to evolving problem distributions. While "Learn-to-Search" (L2S) approaches have emerged, many focus solely on operator selection or current-state decisions without effectively modeling the search history or the broader search space structure.

Methodology: The COAgents Framework

The authors propose COAgents, a cooperative multi-agent framework that models the VRP search process as a graph traversal. The core innovation is the Partial Search Graph (PSG), a dynamically constructed subgraph where nodes represent explored solutions and edges represent either local moves or large perturbations (jumps).

1. The Partial Search Graph (PSG)

The PSG serves as a history-aware state encoding. It is a directed, disjointed graph where:

Nodes: Represent individual solutions encountered during the search.
Edges: Represent neighborhood moves (local refinements) or jumps (large perturbations).
Structure: The graph decomposes into connected components (samples), each exploring the neighborhood of a local optimum. This structure allows the system to track the trajectory of the search and identify patterns in exploration.

2. Multi-Agent Architecture

COAgents employs three learned agents operating over the PSG, all sharing a common neural backbone composed of Gated Graph Convolutional Networks (GGCN) and Transformers:

Node Selection Agent (NSA): Selects a candidate solution (node) from the PSG to serve as the incumbent for the next local search step. It prioritizes promising regions of the search space based on historical data.
Move Selection Agent (MSA): Predicts the most promising neighborhood operator (move) to apply to the selected solution, driving local intensification.
Jump Agent (JA): Triggered when the search stagnates (indicated by repeated failed attempts), this agent generates a completely new solution from scratch based on the search history. Unlike standard operators, the Jump Agent performs a learned restart to escape local minima and steer the search toward unexplored regions.

3. Model Architecture and Training

Encoding: Solutions are encoded into node features ( $u_i$ ) capturing global attributes (objective value, feasibility) and internal structure matrices ( $V_i$ ). Positional embeddings are derived via random-walk encoders for the PSG structure and problem-specific encoders for the solution topology.
Core Blocks: The network uses interleaved GGCN layers to capture local structural patterns within the PSG and Transformer layers to model long-range dependencies across all nodes. Problem-specific End-to-End (E2E) modules refine the internal structure of the combinatorial problem.
Training:
- NSA and MSA: Trained jointly as binary classification tasks to identify the solution closest to the optimum and the best next move, respectively, minimizing joint binary cross-entropy.
- Jump Agent: Trained separately to predict a stochastic adjacency matrix representing a new solution. It is trained against a set of near-optimal reference solutions to reduce label ambiguity.
Inference: The framework executes a loop where NSA selects a node, MSA selects a move, and the PSG is updated. If stagnation occurs, the JA is invoked. This continues until a computational budget (time or node limit) is reached.

Key Contributions

Novel Learned Agents: Introduction of the Node Selection Agent and Jump Agent alongside a Move Selection Agent. These agents collectively replace handcrafted rules, enabling adaptive, data-driven decision policies for solution selection, operator application, and diversification.
Unified, Weight-Shared Architecture: All agents share a common neural backbone, facilitating data-efficient training, transferability to new problem variants, and reduced need for expert tuning.
Partial Search Graph Representation: Formalization of the PSG as a general, history-aware state encoding that drives agent decisions, distinguishing the approach from methods that rely solely on the current state.
Solver- and Problem-Adaptive Framework: COAgents wraps around existing local search routines and neural solvers, enhancing them with adaptive policies that seamlessly adapt to different VRP variants.

Experimental Results

The framework was evaluated on CVRP and VRPTW benchmarks using 10,000 training instances and standard test sets (e.g., 1,000 VRPTW instances).

VRPTW Performance: COAgents set a new state of the art among learning-based methods.
- It reduced the optimality gap to the best-known solutions by 14% (at N=100) and 44% (at N=50) relative to the strongest neural solver (POMO).
- It reduced the gap by 21% (N=100) and 40% (N=50) relative to Adaptive Large Neighborhood Search (ALNS).
- It outperformed all neural baselines, OR-Tools, and ALNS on the VRPTW test set.
CVRP Performance: COAgents remained competitive with state-of-the-art learn-to-search baselines, demonstrating effectiveness even with a compact, problem-specific encoding module.
Ablation Study: Removing the Jump Agent nearly doubled the optimality gap (from 3.7% to 7.8%), highlighting its critical role in escaping local minima. The Node and Move Selection agents also contributed significantly to performance.
Comparison with ALNS: Even when ALNS was granted access to a larger pool of handcrafted operators (including 27 additional destroy-repair pairs), COAgents consistently outperformed it, validating the superiority of learned policies over static heuristics.

Significance and Claims

The paper claims that COAgents represents a significant shift from static, handcrafted heuristics to adaptive, multi-agent systems that learn from search history. By explicitly modeling the search space as a graph and utilizing a Partial Search Graph, the framework enables agents to make informed decisions about intensification and diversification that traditional methods cannot achieve.

The authors position COAgents as a compelling alternative to classical heuristics and existing learning-to-construct/search methods, particularly for complex problems like VRPTW where generalization and adaptability are crucial. While acknowledging that the current Python implementation is slower than C/C++ based heuristics (like LKH3 and HGS) and that scalability to very large instances remains a challenge due to quadratic attention costs, the framework demonstrates that learned, history-aware search control can significantly narrow the gap to best-known solutions in routing problems.