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 · 2026

Read COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space by Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-20618.txt.

Introduction

Oleksandr Yakovenko and six colleagues present COAgents, a team of agents that learn to search vehicle-routing problems. Routing is vital yet hard at scale, and hand-built rules often fail to generalize. Their search graph treats solutions as nodes and links them by small tweaks or large jumps to new regions. Separate agents pick nodes, pick moves, and trigger jumps, cleanly splitting search control from problem-specific encoding.

Catalog record

CREATOROleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47398
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.20618

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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 jumps to escape local minima, but often struggle to generalize across diverse instances. We introduce 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 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 N\!=\!100 and 44% at N = 50 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 . 1 Introduction Combinatorial optimization problems are central to many real-world decision-making scenarios, including finance, e-commerce, logistics, and manufacturing [ 27 ] . Despite breakthroughs in generic solvers, the inherently discrete nature of these problems means that even state-of-the-art solvers often fall short on practical-sized instances, particularly in real-world large-scale logistics and routing applications [ 26 ] . Consequently, there is a demand for fast, reliable heuristic methods that can produce high-quality solutions within limited computation times. Numerous variants of the Vehicle Routing Problem (VRP) offer a solid yet diverse playground for prototyping and testing such OR methods. Many traditional heuristics for VRPs are built on iterative local search: at each step, they (i) select a current solution, (ii) apply one or more neighborhood moves, and (iii) accept or reject the resulting solution via a heuristic rule. To avoid getting stuck, the VRP solvers augment this process with diversification, randomized constructions, or large perturbations that “jump” to new regions. The local search algorithms are repeatedly answering three core questions: 1) Which solution becomes the next incumbent? 2) Which operator should be applied next? 3) When and how should the search be redirected to escape a local minimum? Despite their widespread success, classic methods rely on handcrafted, problem-specific rules for each decision, demanding extensive domain expertise and costly trial-and-error tuning [ 15 ] . Even minor shifts in problem formulation or input data can invalidate the tuned parameters, forcing expert intervention and comprehensive re-engineering. Moreover, static rule sets cannot accumulate or adapt from past search experience, nor adjust online to evolving instance distributions. This brittleness and maintenance burden motivate our shift to the COAgents framework, where learned agents replace fixed heuristics to deliver adaptive, data-driven decision policies with minimal manual tuning. COAgents is a general multi-agent framework that leverages search history to orchestrate local improvement heuristics via three learned agents, the Node Selection Agent (NSA), the Move Selection Agent (MSA), and the Jump Agent (JA), operating over a Partial Search Graph (PSG). A PSG is the visited subgraph of the entire search space, with nodes representing explored solutions and edges representing moves or jumps, thereby encoding the search history. Starting from an initial solution, NSA selects a candidate node and MSA predicts the most promising improvement heuristic, driving local exploration. When repeated failed attempts signal stagnation, JA generates a new solution from scratch based on the search history, steering the search into previously unexplored or unreachable regions. This jump transformation is not a standard operator but a learned restart that escapes local minima and resumes downhill search from a fresh point. Control then returns to NSA and MSA for renewed local search. Figure 1 outlines this top - level loop: NSA, MSA, move application, PSG update, and conditional invocation of JA. The loop is executed until the computational budget (for example, time limits or number of explored nodes) is reached. Figure 1: The COAgents which defines how our three agents are collaborating to orchestrate the search. Contributions COAgents is the first multi-agent framework that models and learns a combinatorial search space of VRPs via collaborative decision-making over a Partial Search Graph. Our key contributions are: (1) Novel learned agents. We introduce two new agents, the Node Selection Agent, which prioritizes promising regions of the search, and the Jump Agent, which predicts learned restarts to escape stagnation—alongside a learned Move Selection Agent, collectively replacing handcrafted rules. (2) Unified, weight-shared architecture. Agents share a common neural backbone, yielding data-efficient training, easy transfer to new problem variants, and reduced expert tuning. (3) Partial Search Graph representation. We formalize the PSG as a general, history-aware state encoding that drives agent decisions. (4) Solver- and problem-adaptive framework. COAgents wraps around a existing local search routines and neural solvers to enhance them with adaptive decision policies that seamlessly adapts to different variants of VRP problems. Empirically, COAgents establishes a new state of the art among learning-based methods on VRPTW, reducing the gap to the best-known solutions by up to 44% over the strongest neural baseline. 2 Related Works Hyper-heuristics are automated methods for selecting or generating heuristics to solve combinatorial problems, first introduced in the 1990s [ 6 ] . Interest in hyper-heuristics has grown due to their potential to reduce development overhead and advances in machine learning [ 7 ] . They are broadly classified into selection and generation approaches [ 2 ] . Selection hyper-heuristics choose from a set of low-level heuristics to apply to the current solution and then decide whether to accept the new solution [ 31 ] . Generation hyper-heuristics, by contrast, create new heuristics by combining building blocks or identifying patterns in existing ones [ 37 ] . COAgents differs from these methods as it is a multi-agent framework that not only selects heuristics but also makes decisions on solution selection and diversification jumps. Learn-to-Search methods. [ 23 ] introduced a learn-to-search (L2S) framework for VRPs that iteratively improves an initial solution by selecting customized operators through a reinforcement learning (RL) controller. Building on this idea, [ 3 ] proposed a deep RL approach that iteratively modifies local solution components until convergence, successfully addressing problems such as the Capacitated Vehicle Routing Problem (CVRP), scheduling, and Traveling Salesperson Problem (TSP). More recently, [ 21 ] formulated operator selection in hyper-heuristics as a Multi-Armed Bandit (MAB) problem, leveraging Thompson Sampling and EXP3 to adaptively handle adversarial and non-stationary settings. These online MAB algorithms dynamically tune parameters during runtime, and were tested on the Vehicle Routing Problem with Time Windows (VRPTW). COAgents differs fundamentally from these methods by going beyond operator selection. It introduces a multi-agent framework that simultaneously decides which solution to expand, which operator to apply, and when and where to diversify, while explicitly modeling the search space as a graph for richer

Read the complete text