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

Computer Science > Artificial Intelligence [Submitted on 20 May 2026] 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 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 this https URL. Comments: Accepted at LION 2026, The Learning and Intelligent Optimization Conference Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2605.20618 [cs.AI]   (or arXiv:2605.20618v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2605.20618 Focus to learn more Submission history From: Cheikh Ahmed [view email] [v1] Wed, 20 May 2026 02:07:10 UTC (2,314 KB) Access Paper: HTML (experimental) view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-05 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)