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

# COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space
Source: [https://arxiv.org/html/2605.20618](https://arxiv.org/html/2605.20618)
11institutetext:Huawei Technologies Canada, 4321 Still Creek Dr, Burnaby, BC, Canada V5C 6S722institutetext:Huawei Technologies, ChinaMahdi MostajabdavehCheikh AhmedAbdullah Ali SivasXiaorui LiZirui ZhouMao 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 occasionaljumpsto escape local minima, but often struggle to generalize across diverse instances\. We introduceCOAgents, 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\)\. APartial 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% atN=100N\\\!=\\\!100and 44% atN=50N\\\!=\\\!50relative to the strongest neural solver \(POMO\), and by 21% and 40% respectively relative to ALNS\.

Code is available at[https://github\.com/mahdims/COAgents](https://github.com/mahdims/COAgents)\.

## 1Introduction

Combinatorial optimization problems are central to many real\-world decision\-making scenarios, including finance, e\-commerce, logistics, and manufacturing\[[27](https://arxiv.org/html/2605.20618#bib.bib59)\]\. 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](https://arxiv.org/html/2605.20618#bib.bib63)\]\. 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 solutionbecomes the next incumbent? 2\)Which operatorshould be applied next? 3\)When and howshould 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](https://arxiv.org/html/2605.20618#bib.bib13)\]\. 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 theCOAgentsframework, 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](https://arxiv.org/html/2605.20618#S1.F1)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\.

![Refer to caption](https://arxiv.org/html/2605.20618v1/fig/algorithm.png)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\.

## 2Related Works

Hyper\-heuristicsare automated methods for selecting or generating heuristics to solve combinatorial problems, first introduced in the 1990s\[[6](https://arxiv.org/html/2605.20618#bib.bib10)\]\. Interest in hyper\-heuristics has grown due to their potential to reduce development overhead and advances in machine learning\[[7](https://arxiv.org/html/2605.20618#bib.bib11)\]\. They are broadly classified into*selection*and*generation*approaches\[[2](https://arxiv.org/html/2605.20618#bib.bib12)\]\. 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](https://arxiv.org/html/2605.20618#bib.bib61)\]\. Generation hyper\-heuristics, by contrast, create new heuristics by combining building blocks or identifying patterns in existing ones\[[37](https://arxiv.org/html/2605.20618#bib.bib60)\]\. 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](https://arxiv.org/html/2605.20618#bib.bib14)\]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](https://arxiv.org/html/2605.20618#bib.bib15)\]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](https://arxiv.org/html/2605.20618#bib.bib8)\]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 context\.

ALNS operator selection\.Recent studies have applied Deep Reinforcement Learning \(DRL\) to improve operator selection in Adaptive Large Neighborhood Search \(ALNS\)\.\[[11](https://arxiv.org/html/2605.20618#bib.bib55)\]and\[[14](https://arxiv.org/html/2605.20618#bib.bib17)\]used multi\-layer perceptron architectures, relying only on high\-level search features \(e\.g\., iteration count, temperature, and optimality gap\) and ignoring solution\-specific details\. This omission may limit operator\-selection effectiveness\. To address this,\[[13](https://arxiv.org/html/2605.20618#bib.bib16)\]use a Graph Neural Network \(GNN\) that embeds the current solution graph to guide operator selection from a large pool \(28 destroy and 7 repair operators\), achieving consistent gains across five routing problems\. Building on these ideas,\[[30](https://arxiv.org/html/2605.20618#bib.bib18)\]introduced DR\-ALNS, a DRL framework that jointly learns operator selection and dynamically tunes algorithm parameters\. Evaluated on the orienteering problem, DR\-ALNS outperformed both traditional and Bayesian\-tuned ALNS of\[[22](https://arxiv.org/html/2605.20618#bib.bib62)\]\. Unlike these approaches, COAgents explicitly models the entire search trajectory as a PSG, enabling richer context for its solution selection, operator selection, and jump agents\.

## 3Problem Statement

We define thecombinatorial solution spaceof a VRP variant as a directed graphGPC​O​\(𝒮,E\)G^\{CO\}\_\{P\}\(\\mathcal\{S\},E\)where each nodes∈𝒮s\\in\\mathcal\{S\}represents a distinct solution to the VRP problemPPandEEis a collection ofneighbourhood movesfor the problemPP\. An edgeei​j∈Ee\_\{ij\}\\in Econnects two nodessis^\{i\}andsjs^\{j\}if there exists a move that convertssis^\{i\}intosjs^\{j\}\. An example of a move that corresponds to an edge is the 2\-opt heuristic for the Traveling Salesman \(Sub\-\)Problem\.

Any global optimums∗s^\{\\ast\}of the problem P is a node in the graphGPC​O​\(𝒮,E\)G^\{CO\}\_\{P\}\(\\mathcal\{S\},E\)\. However, there is no guarantee that an arbitrary solutionsscan be transformed intos∗s^\{\\ast\}via a sequence of moves\. Equivalently,GPC​O​\(𝒮,E\)G^\{CO\}\_\{P\}\(\\mathcal\{S\},E\)may be a disconnected graph\. Additionally, for each local optimal solutionsi∗s^\{\\ast\}\_\{i\}, there exists an induced subgraphGPC​O​\(si∗;𝒮,E\)G^\{CO\}\_\{P\}\(s^\{\\ast\}\_\{i\};\\mathcal\{S\},E\)such that ifssis a node ofGPC​O​\(si∗;𝒮,E\)G^\{CO\}\_\{P\}\(s^\{\\ast\}\_\{i\};\\mathcal\{S\},E\)then sequences of moves fromssare likely to lead tosi∗s^\{\\ast\}\_\{i\}\. We call these induced subgraphsbasins of attraction\. Hence, the graph traversal is biased, and neighborhood moves may lead to a local optimum even when a path to a global optimum exists\.

In practical scenarios, only a subset of all possible moves are available and/or cheap\. Therefore, we introduce thesearch spaceas the subgraphGPS​S​\(𝒮,Eℳ\)⊂GPC​O​\(𝒮,E\)G^\{SS\}\_\{P\}\(\\mathcal\{S\},E\_\{\\mathcal\{M\}\}\)\\subset G^\{CO\}\_\{P\}\(\\mathcal\{S\},E\), whereℳ\\mathcal\{M\}denotes the set of available moves, andEℳE\_\{\\mathcal\{M\}\}is the corresponding set of edges\. From now on, we refer to these spaces asGS​SG^\{SS\}andGC​OG^\{CO\}, respectively\. Observe that edges ofGS​SG^\{SS\}are a subset of edges ofGC​OG^\{CO\}and the optimal solutions∗s^\{\\ast\}is a node inGS​SG^\{SS\}\.

Now, we cast the problem of finding an optimal solutions∗∈𝒮s^\{\\ast\}\\in\\mathcal\{S\}of a given VRP problemPPto

- •finding a set of edgesEJE\_\{J\}, not necessarily corresponding to any legitimate move, such thatGPS​S\(ℳ;𝒮,Eℳ⋃EJ\)\)G^\{SS\}\_\{P\}\(\\mathcal\{M\};\\mathcal\{S\},E\_\{\\mathcal\{M\}\}\\bigcup E\_\{J\}\)\)is connected,
- •and finding the shortest path between an initial solutions\(0\)∈𝒮s^\{\(0\)\}\\in\\mathcal\{S\}ands∗∈𝒮s^\{\\ast\}\\in\\mathcal\{S\}over the graphGPS​S\(ℳ;𝒮,Eℳ⋃EJ\)\)G^\{SS\}\_\{P\}\(\\mathcal\{M\};\\mathcal\{S\},E\_\{\\mathcal\{M\}\}\\bigcup E\_\{J\}\)\)\.

We name the setEJE\_\{J\}jumps\. Note that jumps do not have to improve the objective value; hence, they are not affected by basins of attraction\. See[fig\.˜3](https://arxiv.org/html/2605.20618#S3.F3)for an illustration\.

Explicit representation ofGS​SG^\{SS\}is not available due to space and time constraints\. Instead, we will aim to train our model to implicitly construct the search space during inference\. We achieve this by constructing a set ofPartial Search Graphsand using this set as an additional input to the model\. A partial search graph is anexploredsubspace of the entire search space\. Nodes represent solutions encountered during the search process\. Edges represent either the moves or the jumps\. As a result, a PSG captures a trajectory of the search within the search spaceGS​SG^\{SS\}, showing the parts of the space that have been visited and how they are connected\.[fig\.˜3](https://arxiv.org/html/2605.20618#S3.F3)demonstrates how a PSG evolves between iterations\.

![Refer to caption](https://arxiv.org/html/2605.20618v1/fig/paper_image_pes_edited.png)Figure 2:Moves\(black\) andjumps\(orange\) work together in the search of the global optimum\.
![Refer to caption](https://arxiv.org/html/2605.20618v1/fig/PSG.png)Figure 3:Evolution of a PSG during the algorithm\.ssdenotes solutions andmmare moves\.

In this study, we propose a method that learns how to guide the exploration of the search space from previous experiences and how to generatejumpsduring exploration\. We will use PSGs to identify patterns in solution exploration and to guide further exploration, improving search efficiency by focusing on unexplored or promising regions\. We discuss our approach in theMethodssection\.

## 4Solution Method: COAgents

COAgents consists of three agents—the NSA, MSA, and JA, which interact as shown in Fig\.[1](https://arxiv.org/html/2605.20618#S1.F1)\. Each agent is implemented as a graph\-neural\-network–based policy trained to maximize long\-term progress toward the optimum\. In this section, we discuss the data representation, model architecture, and training procedures for these three agents\.

### 4\.1Search History Data Representation

Navigating the non\-convex combinatorial solution space of VRPs is a challenging task\. To enhance agents’ understanding of the solution space, it is crucial to integrate information about the problem, the solution, and the exploration history\. While problem and solution encodings are inherently problem\-specific, the history exhibits a consistent structure across many variants of combinatorial optimization problems\. Next, we discuss the problem\-independent representation of the exploration history in detail\.

##### Partial Search Graph

The presented framework is built upon the PSG data structure, which represents the search history\. As described above, the PSG is essentially a directed, disjointed graph\. Each node in the PSG corresponds to a single solutionsis\_\{i\}of a combinatorial optimization problem, and each directed edge\(si→sj\)\(s\_\{i\}\\to s\_\{j\}\)indicates thatsjs\_\{j\}was reached by applying a neighborhood move operator tosis\_\{i\}\. The PSG naturally decomposes into connected components—which we call*samples*—each of which explores the neighborhood of a local optimumsk∗s^\{\\ast\}\_\{k\}\. In turn, each sample is a flattened collection of embeddings of individual solutionssis\_\{i\}together with their connectivity information\.

##### Node Features

Each solution embedding is represented by a fixed\-size vector𝐮𝐢\\mathbf\{u\_\{i\}\}which encodes global solution\-specific attributes, including objective value, feasibility, and graph\-level aggregates such as the gap relative to its parent in PSG, the number of derived solutions and their objectives, etc\. Additionally, each solution is accompanied by a dynamically sized matrix𝐕𝐢\\mathbf\{V\_\{i\}\}\(which varies across batches\) that encapsulates its internal structure\. Bothuiu\_\{i\}andViV\_\{i\}are constructed by concatenating thestructuralandpositionalembeddings of a CO solutionsis\_\{i\}\. The detailed computation of these embeddings is discussed next, while the complete set of per\-problem features utilized in our experiments is provided inAppendix A

##### Input Embeddings

Our agents operate on node embeddings of the PSG introduced above\. Since all PSG edges \(moves and jumps\) are provided explicitly, we compute each node’s positional embeddinguposu\_\{\\mathrm\{pos\}\}via a simple random\-walk encoder\[[28](https://arxiv.org/html/2605.20618#bib.bib24)\]\. The structural embedding of the local and global features is then obtained by

ustr=Linear​\(xu\)∈ℝdu,Vstr=Linear​\(xV\)∈ℝdV\.\\begin\{split\}u\_\{\\mathrm\{str\}\}&=\\mathrm\{Linear\}\(x\_\{u\}\)\\;\\in\\mathbb\{R\}^\{d\_\{u\}\},\\\\ V\_\{\\mathrm\{str\}\}&=\\mathrm\{Linear\}\(x\_\{V\}\)\\;\\in\\mathbb\{R\}^\{d\_\{V\}\}\.\\end\{split\}\(1\)
Each solution also carries a problem\-specific positional embeddingVposV\_\{\\mathrm\{pos\}\}; details for its construction in each domain are given inAppendix B\. Finally, we concatenate structural and positional embeddings:

ui​n​p=ustr⌢​upos,Vi​n​p=Vstr⌢​Vpos\.\\displaystyle u\_\{inp\}=u\_\{\\mathrm\{str\}\}\\ ^\{\\frown\}u\_\{\\mathrm\{pos\}\},\\quad V\_\{inp\}=V\_\{\\mathrm\{str\}\}\\ ^\{\\frown\}V\_\{\\mathrm\{pos\}\}\.\(2\)whereui​n​p∈ℝdu\+dposu\_\{inp\}\\in\\mathbb\{R\}^\{\\,d\_\{u\}\+d\_\{\\mathrm\{pos\}\}\}andVi​n​p∈ℝdV\+dpos′V\_\{inp\}\\in\\mathbb\{R\}^\{\\,d\_\{V\}\+d^\{\\prime\}\_\{\\mathrm\{pos\}\}\}\.

### 4\.2Agent Architectures

All the agents are composed of the same core blocks, with only minor differences in functionality\. We employ a combination of Gated Graph Convolution \(GGCN\), Transformer, and problem\-specific modules as the universal core block of the agents’ networks\. GGCN layers propagate and filter messages among each node’s immediate neighbors in PSG to capture local structural patterns, while Transformer layers apply global self\-attention across all nodes to model long\-range dependencies\. Given GGCN’s graph\-specialized capabilities, we opted for a standard Transformer architecture rather than a graph attention mechanism\. Figure[4](https://arxiv.org/html/2605.20618#S4.F4)illustrates the general architecture of agents\.

![Refer to caption](https://arxiv.org/html/2605.20618v1/fig/architecture.png)Figure 4:Agents model architectureOur network comprises a stack of interleavedCoreBlocks, each consisting of a Gated Graph Convolutional Network \(GGCN\), followed by a Transformer layer, and finally an augmented problem\-specific layer\. Letui\(l−1\)∈ℝduu\_\{i\}^\{\(l\-1\)\}\\in\\mathbb\{R\}^\{d\_\{u\}\}be the global embedding of nodeiiand letvi​k\(l−1\)∈ℝdvv\_\{ik\}^\{\(l\-1\)\}\\in\\mathbb\{R\}^\{d\_\{v\}\}denote thekk\-th row of its internal structure matrixVi​k\(l−1\)=\[v0,0l−1,v0,1l−1,…,v0,kl−1,v1,0l−1,…,vM,Nl−1\]V\_\{ik\}^\{\(l\-1\)\}=\[v\_\{0,0\}^\{l\-1\},v\_\{0,1\}^\{l\-1\},\\ldots,v\_\{0,k\}^\{l\-1\},v\_\{1,0\}^\{l\-1\},\\ldots,v\_\{M,N\}^\{l\-1\}\]whereNNis the size of the problem andMMis the amount of trial solutions in the scope of an agent\. The CoreBlock transformation is then:

\(u^i\(l\),V^i\(l\)\)=GGCN​\(ui\(l−1\),Vi\(l−1\),E\),\(u~i\(l\),V~i\(l\)\)=Transformer​\(u^i\(l\),V^i\(l\)\),V¯i\(l\)=E2E​\(Vi\(l−1\),V~i\(l\)\),ui\(l\)=ui\(l−1\)\+u~i\(l\),Vi\(l\)=Vi\(l−1\)\+V¯i\(l\)\.\\begin\{split\}\(\\hat\{u\}\_\{i\}^\{\(l\)\},\\,\\hat\{V\}\_\{i\}^\{\(l\)\}\)&=\\mathrm\{GGCN\}\(u\_\{i\}^\{\(l\-1\)\},\\,V\_\{i\}^\{\(l\-1\)\},\\,E\),\\\\ \(\\tilde\{u\}\_\{i\}^\{\(l\)\},\\tilde\{V\}\_\{i\}^\{\(l\)\}\)&=\\mathrm\{Transformer\}\(\\hat\{u\}\_\{i\}^\{\(l\)\},\\hat\{V\}\_\{i\}^\{\(l\)\}\),\\\\ \\bar\{V\}\_\{i\}^\{\(l\)\}&=\\mathrm\{E2E\}\(V\_\{i\}^\{\(l\-1\)\},\\tilde\{V\}\_\{i\}^\{\(l\)\}\),\\\\ u\_\{i\}^\{\(l\)\}&=u\_\{i\}^\{\(l\-1\)\}\+\\tilde\{u\}\_\{i\}^\{\(l\)\},\\quad V\_\{i\}^\{\(l\)\}=V\_\{i\}^\{\(l\-1\)\}\+\\bar\{V\}\_\{i\}^\{\(l\)\}\.\\end\{split\}\(3\)

### 4\.3Core Block of COAgents

##### CoreBlock: Gated Graph Convolution Network\.

We process the immediate neighborhood of each node in the PSG with the Gated Graph Convolutional Network \(GGCN\)\[[1](https://arxiv.org/html/2605.20618#bib.bib20),[29](https://arxiv.org/html/2605.20618#bib.bib19)\]\. The GGCN part learns to gate and propagate information along edges of the PSG\. It transforms the input representation \(details provided inAppendix C1\) intou^l\\hat\{u\}^\{l\}andV^l\\hat\{V\}^\{l\}\(the first line of[eq\.˜3](https://arxiv.org/html/2605.20618#S4.E3)\) using a variant of message passing mechanism\.

##### CoreBlock: Transformer\.

To capture the long–range dependencies across the PSG, we apply a standard Transformer self‐attention block \(the second line in[eq\.˜3](https://arxiv.org/html/2605.20618#S4.E3)\)\. The M\-by\-M attention matrix of the transformer encodes \(as it is described inAppendix C2\) pairwise attention weights across all PSG nodes\. Each of the attention weights uniformly scales all the internal featuresVi~\\tilde\{V\_\{i\}\}of a PSG nodeii\. Since the inner dimensionNN\(e\.g\., VRP customers\) can be arbitrarily large, we delegate the row‐wise attention overVi~\\tilde\{V\_\{i\}\}to problem‐specific modules due to computational overhead\. Approximate Transformers implementations, such as Linformer\[[34](https://arxiv.org/html/2605.20618#bib.bib26)\]or Performer\[[5](https://arxiv.org/html/2605.20618#bib.bib27)\], can mitigate this computational burden to near\-linear complexity\. Their application, however, would introduce additional errors in a problem‐dependent manner, making seamless integration into our generic framework challenging without further problem\-specific tuning\.

##### CoreBlock: Problem\-Specific End\-to\-End Modules\.

The problem\-specific layers neither possess any intrinsic knowledge about our framework nor operate at the PSG level\. Consequently, they can be trivially outsourced from existing literature and updated to enhance framework efficiency as domain\-specific SOTA evolves\. The E2E module focuses exclusively on the internal structure of the combinatorial problemV~\\tilde\{V\}\(as it is shown in the last line of[eq\.˜3](https://arxiv.org/html/2605.20618#S4.E3)\), refining it independently from the rest of the framework by leveraging both previous and current local embeddings\. It is the framework’s responsibility to adapt to the problem\-specific layer and inject meaningful correcting dependencies directly into the latent space of an E2E module\.Appendix C3lists the architectures that we used for each problem type\.

### 4\.4Decoders

##### Node & Move Selection Decoders

Both the Node Selection Agent and Move Selection Agent use the same decoder head\. Given each node’s final embeddings\(ui,Vi\)\(u\_\{i\},V\_\{i\}\), we first aggregate:

zi=1N​∑k=1NGELU​\(G​\(ui⌢​vi​k\)\),z\_\{i\}\\;=\\;\\frac\{1\}\{N\}\\sum\_\{k=1\}^\{N\}\\mathrm\{GELU\}\\bigl\(G\\,\(u\_\{i\}\\ ^\{\\frown\}v\_\{ik\}\)\\bigr\),whereG∈ℝdz×\(du\+dv\)G\\in\\mathbb\{R\}^\{d\_\{z\}\\times\(d\_\{u\}\+d\_\{v\}\)\}\. Then, lettingU∈ℝ1×dzU\\in\\mathbb\{R\}^\{1\\times d\_\{z\}\},W∈ℝ1×\(dz\+de\)W\\in\\mathbb\{R\}^\{1\\times\(d\_\{z\}\+d\_\{e\}\)\}, and\{em\}m=1M⊂ℝde\\\{e\_\{m\}\\\}\_\{m=1\}^\{M\}\\subset\\mathbb\{R\}^\{d\_\{e\}\}be move embeddings\. Denotingσ\\sigmaas the sigmoid function, we compute

pi=σ​\(U​zi\),pi,m=σ​\(W​\(zi⌢​em\)\),p\_\{i\}\\;=\\;\\sigma\\bigl\(U\\,z\_\{i\}\\bigr\),\\qquad p\_\{i,m\}\\;=\\;\\sigma\\bigl\(W\\,\(z\_\{i\}\\ ^\{\\frown\}e\_\{m\}\)\\bigr\),

##### Jump Decoder

The Jump Decoder decodes the final local embeddingVi\(L\)∈ℝN×dvV\_\{i\}^\{\(L\)\}\\in\\mathbb\{R\}^\{N\\times d\_\{v\}\}of a selected solution into a stochastic adjacency matrixY∈ℝN×NY\\in\\mathbb\{R\}^\{N\\times N\}\. Concretely:

Yi=\(Vi\(L\)​WQ​WK⊤​Vi\(L\)⊤dk\)Y\_\{i\}=\\bigl\(\\frac\{V\_\{i\}^\{\(L\)\}W\_\{Q\}W\_\{K\}^\{\\top\}V\_\{i\}^\{\(L\)\\top\}\}\{\\sqrt\{d\_\{k\}\}\}\\bigr\)We then mask self‐decisions by setting\(Yi\)k​k=−∞\(Y\_\{i\}\)\_\{kk\}=\-\\inftyfor allkk, and apply a row‐wise softmax:

Pi=softmax⁡\(Yi\)∈\[0,1\]N×N\.P\_\{i\}=\\operatorname\{softmax\}\(Y\_\{i\}\)\\;\\in\[0,1\]^\{N\\times N\}\.Each row ofPiP\_\{i\}is a probability distribution over decisions \(e\.g\., edges or arcs\) for one component of the solution\. Sampling fromPiP\_\{i\}yields a completely new solution in one shot\. In our implementation, we apply this decoder to the local optimal solution from the previous jump; alternatively, it can be run on any or all PSG nodes to generate diverse candidates\.

### 4\.5Training

Let𝒟=\{𝒢1,…,𝒢N\}\\mathcal\{D\}=\\\{\\mathcal\{G\}\_\{1\},\\dots,\\mathcal\{G\}\_\{N\}\\\}be our dataset of PSGs\. Each PSG𝒢\\mathcal\{G\}has a set of solutions𝒮\\mathcal\{S\}and, for eachs∈𝒮s\\in\\mathcal\{S\}, a set of candidate movesℳ\\mathcal\{M\}\.

We treatnode and move selectionas two binary classification tasks trained jointly\. For each solutions∈𝒮s\\in\\mathcal\{S\}, we assignys∈\{0,1\}y\_\{s\}\\in\\\{0,1\\\}, which is 1 ifssis closest to the optimal solution in and 0 otherwise\. For each movem∈ℳm\\in\\mathcal\{M\}, we assignys,m∈\{0,1\}y\_\{s,m\}\\in\\\{0,1\\\}, which will be 1 if applyingmmtossyields the best next candidate in𝒮\\mathcal\{S\}, and 0 otherwise\. Given the predicted probabilitiespsp\_\{s\}andps,mp\_\{s,m\}\(see sectionDecoder\), we minimize the joint binary cross‐entropy:

ℒselect=−∑i\[yi​log⁡pi\+\(1−yi\)​log⁡\(1−pi\)\]−∑i,m\[yi,m​log⁡pi,m\+\(1−yi,m\)​log⁡\(1−pi,m\)\]\.\\begin\{split\}\\mathcal\{L\}\_\{\\mathrm\{select\}\}=\-\\sum\_\{i\}\\Bigl\[y\_\{i\}\\log p\_\{i\}\+\(1\-y\_\{i\}\)\\log\(1\-p\_\{i\}\)\\Bigr\]\\\\ \-\\sum\_\{i,m\}\\Bigl\[y\_\{i,m\}\\log p\_\{i,m\}\+\(1\-y\_\{i,m\}\)\\log\(1\-p\_\{i,m\}\)\\Bigr\]\.\\end\{split\}\(4\)At inference, we sample the node indexi∼\{pi\}ii\\sim\\\{p\_\{i\}\\\}\_\{i\}and then sample the movem∼\{pi,m\}mm\\sim\\\{p\_\{i,m\}\\\}\_\{m\}according to these distributions\.

TheJump Agentis trained separately\. For each CO instance, we precompute a set ofKKtarget solutions\{δ\(1\),…,δ\(K\)\}\\\{\\delta^\{\(1\)\},\\dots,\\delta^\{\(K\)\}\\\}, comprising the optimal solution and near‐optimal neighbors that can be converted to optimal with given heuristics\.

Letℐ\\mathcal\{I\}be the set of all atomic decisions \(e\.g\., edges or arcs\)\. The Jump Decoder outputs probabilitiesPi∈\[0,1\]P\_\{i\}\\in\[0,1\]for eachi∈ℐi\\in\\mathcal\{I\}\. For eachδ\(k\)\\delta^\{\(k\)\}, we compute labelsy\(k\)∈\{0,1\}\|ℐ\|y^\{\(k\)\}\\in\\\{0,1\\\}^\{\|\\mathcal\{I\}\|\}\. Then, we pick the closest reference viak∗=arg⁡mink⁡12​∑i∈ℐ\|yi\(k\)−Pi\|,k^\{\*\}=\\arg\\min\_\{k\}\\tfrac\{1\}\{2\}\\sum\_\{i\\in\\mathcal\{I\}\}\\bigl\|y\_\{i\}^\{\(k\)\}\-P\_\{i\}\\bigr\|,sety∗=y\(k∗\)y^\{\*\}=y^\{\(k^\{\*\}\)\}, and minimize

ℒjump=−∑i∈ℐ\[yi∗​log⁡Pi\+\(1−yi∗\)​log⁡\(1−Pi\)\]\.\\mathcal\{L\}\_\{\\mathrm\{jump\}\}=\-\\sum\_\{i\\in\\mathcal\{I\}\}\\bigl\[y^\{\*\}\_\{i\}\\log P\_\{i\}\+\(1\-y^\{\*\}\_\{i\}\)\\log\(1\-P\_\{i\}\)\\bigr\]\.\(5\)At inference, decisionsiiare sampled according toPPto form a complete solution in one shot\.

##### Training stability\.

Across training, the node and move selection agents exhibited stable convergence because each sampled subgraph contains a single positive move label\. The jump agent was more sensitive, since multiple structurally different solutions can be near\-optimal and therefore valid jump targets\. To reduce label ambiguity, we train the jump model against a set of near\-optimal references and select the closest target during training\. We did not observe a collapse in the reported runs\.

##### Computational overhead\.

LetKKdenote the number of retained nodes per PSG subgraph,\|EPSG\|\|E\_\{\\mathrm\{PSG\}\}\|the number of PSG edges,NNthe problem size \(e\.g\., number of customers\),\|ℳ\|\|\\mathcal\{M\}\|the number of candidate moves, andddthe hidden dimension\. Each GGCN layer scales as𝒪​\(\|EPSG\|​d\)\\mathcal\{O\}\(\|E\_\{\\mathrm\{PSG\}\}\|\\,d\), the PSG\-level Transformer as𝒪​\(K2​d\)\\mathcal\{O\}\(K^\{2\}d\), the node and move decoders as𝒪​\(K​d\+K​\|ℳ\|​d\)\\mathcal\{O\}\(Kd\+K\|\\mathcal\{M\}\|d\), and the jump decoder as𝒪​\(N2​d\)\\mathcal\{O\}\(N^\{2\}d\)per invocation\. The dominant per\-iteration costs are therefore PSG\-level self\-attention, quadratic inKK, and jump decoding, quadratic inNN\. Because the PSG grows unboundedly with search length, we cap each subgraph atK≤64K\\\!\\leq\\\!64nodes, evicting the oldest entry once the limit is exceeded, while leaving the number of subgraphs in the history pool unrestricted\. This bounds the𝒪​\(K2​d\)\\mathcal\{O\}\(K^\{2\}d\)attention term to a small constant and preserves long\-horizon historical context, keeping per\-iteration latency low\. The𝒪​\(N2​d\)\\mathcal\{O\}\(N^\{2\}d\)jump\-decoder cost remains problem\-dependent and is the only term that grows with instance size\.

## 5Experimental Setup and Results

In this section, we evaluate our COAgents framework on two variants of VRP: \(1\) the Capacitated Vehicle Routing Problem and \(2\) the Vehicle Routing Problem with Time Windows\. Detailed problem definitions are given inAppendix D, and the training data generation procedure is described inAppendix E\. All methods are implemented in Python 3\.11 using PyTorch 2\.4\.1 and trained on a machine with six NVIDIA P100\-PCIE 16 GB GPUs under CUDA 12\.2\. Full reproducibility details, including framework configuration, training data, and per\-agent hyperparameters, are provided inAppendix F\. Runtimes in Tables 1–2 report total wall\-clock time over the full test set \(following prior work\), whereas Table 3 reports average per\-instance inference time\.

### 5\.1Experimental Test on the VRPTW

To train our agents, we generate 10K VRPTW instances with 100 customers using a random instance generator\. Table[1](https://arxiv.org/html/2605.20618#S5.T1)compares COAgents against state\-of\-the\-art solvers including heuristics \(LKH\[[8](https://arxiv.org/html/2605.20618#bib.bib33)\], HGS\[[32](https://arxiv.org/html/2605.20618#bib.bib32)\], OR\-Tools\) and L2C models \(MVMoE\[[38](https://arxiv.org/html/2605.20618#bib.bib54)\], POMO\[[20](https://arxiv.org/html/2605.20618#bib.bib37)\]\)\. We evaluate on the 1K test instances introduced by\[[38](https://arxiv.org/html/2605.20618#bib.bib54)\]\. All baseline results are taken from\[[38](https://arxiv.org/html/2605.20618#bib.bib54)\]unless otherwise specified\. COAgents achieves the best performance across all neural solvers, OR\-Tools, and ALNS, reducing the optimality gap by 14% \(NN=100\) and 44% \(NN=50\) relative to the strongest neural solver \(POMO\), and by 21% and 40%, respectively, relative to ALNS\.

Table 1:VRPTW: Average objective \(Obj\.\), gap vs\. HGS, and runtime on 1k test instances\. \(H: heuristic, C: learn\-to\-construct, S: learn\-to\-search\.\) Times are total wall\-clock time over the full test set\.
### 5\.2Experimental Test on CVRP

We used the 10K CVRP instances with 100 customers introduced by\[[25](https://arxiv.org/html/2605.20618#bib.bib31)\]to train our agents\. Table[2](https://arxiv.org/html/2605.20618#S5.T2)benchmarks our COAgents against the main families of neural VRP solvers on 10k test instances introduced in\[[25](https://arxiv.org/html/2605.20618#bib.bib31)\]: 1\.L2P \(learning\-to\-predict\):CVAE\-Opt\-DE\[[9](https://arxiv.org/html/2605.20618#bib.bib34)\], DPDP\[[19](https://arxiv.org/html/2605.20618#bib.bib40)\]\(state\-of\-the\-art\) 2\.L2C \(learning\-to\-construct\):AM\+LCP\[[17](https://arxiv.org/html/2605.20618#bib.bib35)\], POMO\[[20](https://arxiv.org/html/2605.20618#bib.bib37)\], Sym\-NCO\[[18](https://arxiv.org/html/2605.20618#bib.bib36)\], POMO\+EAS\(\+SGBS\)\[[10](https://arxiv.org/html/2605.20618#bib.bib38),[4](https://arxiv.org/html/2605.20618#bib.bib39)\]3\.L2S \(learning\-to\-search\):NLNS\[[12](https://arxiv.org/html/2605.20618#bib.bib56)\], NCE\[[16](https://arxiv.org/html/2605.20618#bib.bib57)\], Wu et al\.\[[36](https://arxiv.org/html/2605.20618#bib.bib58)\], DACT\[[24](https://arxiv.org/html/2605.20618#bib.bib21)\]\(state\-of\-the\-art\)\. Unless stated otherwise, all baseline numbers are taken from\[[25](https://arxiv.org/html/2605.20618#bib.bib31)\]\. For a fair comparison, we evaluate inference on a single GPU/CPU using a neural processing unit comparable to an A100 GPU\[[25](https://arxiv.org/html/2605.20618#bib.bib31)\]\. Following prior work\[[10](https://arxiv.org/html/2605.20618#bib.bib38),[24](https://arxiv.org/html/2605.20618#bib.bib21),[25](https://arxiv.org/html/2605.20618#bib.bib31)\], we report: \(i\) average tour cost, \(ii\) optimality gap relative to the state\-of\-the\-art solver HGS\[[32](https://arxiv.org/html/2605.20618#bib.bib32)\], and \(iii\) total wall\-clock time\.

Table 2:CVRP: Average Obj\., gap vs\. HGS, and runtime on 10k test instances\. \(H: heuristic, C: learn\-to\-construct, S: learn\-to\-search, P: learn\-to\-predict, RL: reinforcement learning, SL: supervised learning, UL: unsupervised learning, DE: dynamic encoding, DP: dynamic programming, AS: active search, BS: beam search\.\)\. Times are total wall\-clock time over the full test set\.MethodTypePostN=20N=20N=50N=50N=100N=100Obj\.Gap↓\\downarrowTime↓\\downarrowObj\.Gap↓\\downarrowTime↓\\downarrowObj\.Gap↓\\downarrowTime↓\\downarrowHGS\[[32](https://arxiv.org/html/2605.20618#bib.bib32)\]H–6\.13\*2\.3m10\.37\*15m15\.56\*4\.2hLKH3\[[8](https://arxiv.org/html/2605.20618#bib.bib33)\]H–6\.140\.08%4\.7m10\.380\.09%35m15\.650\.54%9\.8hALNS\(1k\)\[[13](https://arxiv.org/html/2605.20618#bib.bib16)\]H–6\.191\.09%1\.3d10\.783\.93%5\.5d16\.546\.01%18\.3dCVAE\-Opt\-DEP/ULDE6\.140\.16%1\.5h10\.400\.33%6\.1h–––DPDP\(1M\)P/SLDP––––––15\.630\.41%1\.2dAM\+LCPC/RL–6\.150\.33%23m10\.521\.48%52m16\.002\.81%2\.1hSym\-NCOC/RL–––––––15\.670\.70%7\.2hPOMOC/RL–6\.140\.09%1\.7m10\.400\.30%11m15\.670\.70%7\.2hPOMO\+EASC/RLAS6\.130\.04%6\.8m10\.380\.13%38m15\.610\.30%16hPOMO\+EAS\+SGBS\(short\)C/RLAS\+BS––––––15\.590\.15%1dPOMO\+EAS\+SGBS\(long\)C/RLAS\+BS––––––15\.580\.10%4\.1dNLNS\(5k\)S/RL–6\.180\.73%12m10\.511\.35%48m15\.922\.26%2\.4hNCE\(CROSS\)S/SL–6\.130\.00%11h10\.410\.42%2\.3d15\.811\.59%10\.4dWu et al\.S/RL––––10\.541\.72%4\.2h16\.173\.87%5hDACTS/RL–6\.130\.01%3m10\.380\.16%16h15\.741\.11%1\.7dNeuOpt\(D2A=1,1k\)S/RL–6\.130\.03%2m10\.430\.61%12m15\.871\.94%28mCOAgents\(1k\)S/SL–6\.180\.34%22\.2h10\.601\.44%1\.2d16\.052\.72%1\.9d

### 5\.3Comparison with ALNS

In this section, we compare against a strong ALNS baseline that includes all local improvement moves available to COAgents, together with 27 additional destroy\-and\-repair pairs from\[[13](https://arxiv.org/html/2605.20618#bib.bib16)\]\. This makes the comparison conservative: ALNS has access to a larger pool of handcrafted operators, while COAgents differs mainly in its learned node selection, move selection, and jump policies\. Both algorithms are run for 1000 iterations, and we evaluate the quality of their best\-found objective values at ten checkpoints during the search on the 1k VRPTW test set from\[[38](https://arxiv.org/html/2605.20618#bib.bib54)\]\. COAgents consistently outperforms ALNS\. Despite using the same local improvement heuristics, COAgents outperforms ALNS by replacing static destroy\-and\-repair operators with a learned Jump Agent\. When combined with the NSA’s solution selection and the MSA’s operator choice, this learned diversification provides far more robust and effective guidance than ALNS’s handcrafted policies\.

![Refer to caption](https://arxiv.org/html/2605.20618v1/fig/gap_evolution.png)Figure 5:Comparison of optimality gap for a test set of VRPTW instances\.
### 5\.4Ablation Study

To assess the contribution of each component in COAgents, we conducted an ablation study on VRPTW instances\. We evaluated three variants: removing the node selection agent \(fallback to hill climbing\), removing the move selection agent \(fallback to the standard ALNS adaptive mechanism\), and removing the jump agent\. Table[3](https://arxiv.org/html/2605.20618#S5.T3)reports the average gap to HGS solutions and runtime\. Removing the Jump Agent nearly doubles the gap \(from 3\.7% to 7\.8%\), making it the most impactful component of COAgents\. Nonetheless, the other agents also contribute to the algorithm’s success\.

Table 3:Ablation study on VRPTW instances\.

## 6Discussion and Future Directions

Our empirical results demonstrate that COAgents is a compelling alternative to classical heuristics as well as learn\-to\-construct and learn\-to\-search methods\. On the VRPTW \(Table[1](https://arxiv.org/html/2605.20618#S5.T1)\), COAgents outperforms all neural baselines, OR\-Tools, and ALNS, narrowing the gap to HGS by 14–44% over the strongest neural solver and by 21–40% over ALNS across N=50 and N = 100\. On the CVRP \(Table[2](https://arxiv.org/html/2605.20618#S5.T2)\), it remains competitive with learn\-to\-search baselines despite relying solely on a compact, problem\-specific domain\-encoding module\. Moreover, in every case COAgents surpasses a pure ALNS implementation, which uses the same local improvement heuristics plus 27 additional destroy–repair pairs, demonstrating that our multi\-agent system delivers more robust and effective guidance than ALNS’s handcrafted policies\.

Strengths\.We attribute our superior performance on harder problems, such as the VRPTW, to the PSG, which persistently stores high\-quality solutions and feeds them back into our agents\. By using this historical information, our agents can drive targeted intensification or diversification more efficiently\. In contrast, existing learning\-to\-search approaches make all their decisions solely based on the current state and their policy weights\[[13](https://arxiv.org/html/2605.20618#bib.bib16),[21](https://arxiv.org/html/2605.20618#bib.bib8)\], without ever exploiting accumulated search history\. Furthermore, COAgents’ modular design isolates domain\-specific logic in the E2E blocks, so transferring to a new problem requires only swapping or tuning that module while the GGCN–Transformer core stays unchanged\.

Limitations\.COAgents’ runtime is not as competitive as some baseline methods\. This is due to two factors: \(1\) COAgents uses an iterative improvement search that repeatedly generates and modifies solutions, making it slower than constructive methods \(i\.e,\. L2C\) that build a solution only once, and \(2\) our heuristic implementations are in Python, whereas traditional heuristics such as LKH3 and HGS are implemented in C and C\+\+, respectively\. However, our execution time is comparable to L2S methods and, in some cases \(e\.g\., NCE\), even faster\. The current implementation is evaluated up toN=100N=100\. Scaling to substantially larger or strict real\-time VRP settings remains open\. The main bottlenecks are PSG\-level attention, which grows quadratically with the retained PSG size, and the jump decoder, which constructs anN×NN\\times Ndecision matrix\. Sparse PSG attention, more aggressive history pruning, batched move evaluation, and lighter jump decoders are promising directions for reducing this overhead\.

\{credits\}

#### 6\.0\.1\\discintname

The authors have no competing interests to declare that are relevant to the content of this article\.

## References

- \[1\]X\. Bresson and T\. Laurent\(2023\)Residual gated graph convnets\.arXiv:1711\.07553\(\),pp\.\.External Links:[Document](https://dx.doi.org/https%3A//doi.org/10.48550/arXiv.1711.07553)Cited by:[§4\.3](https://arxiv.org/html/2605.20618#S4.SS3.SSS0.Px1.p1.2)\.
- \[2\]E\. K\. Burke, M\. R\. Hyde, G\. Kendall, G\. Ochoa, E\. Özcan, and J\. R\. Woodward\(2019\)A classification of hyper\-heuristic approaches: revisited\.Handbook of metaheuristics,pp\. 453–477\.Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p1.1)\.
- \[3\]X\. Chen and Y\. Tian\(2019\)Learning to perform local rewriting for combinatorial optimization\.Advances in neural information processing systems32\.Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p2.1)\.
- \[4\]J\. Choo, Y\. Kwon, J\. Kim, J\. Jae, A\. Hottung, K\. Tierney, and Y\. Gwon\(2022\)Simulation\-guided beam search for neural combinatorial optimization\.Advances in Neural Information Processing Systems35,pp\. 8760–8772\.Cited by:[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[5\]K\. Choromanski, V\. Likhosherstov, D\. Dohan, X\. Song, A\. Gane, T\. Sarlos, P\. Hawkins, J\. Davis, A\. Mohiuddin, L\. Kaiser, D\. Belanger, L\. Colwell, and A\. Weller\(2021\)Rethinking attention with performers\.InInternational Conference on Learning Representations \(ICLR\),External Links:[Link](https://arxiv.org/abs/2009.14794)Cited by:[§4\.3](https://arxiv.org/html/2605.20618#S4.SS3.SSS0.Px2.p1.4)\.
- \[6\]J\. Denzinger, M\. Fuchs, and M\. Fuchs\(1997\)High performance ATP systems by combining several AI methods\.InProceedings of the 15th International Joint Conference on Artifical Intelligence \- Volume 1,IJCAI’97,San Francisco, CA, USA,pp\. 102–107\.External Links:ISBN 15558604804Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p1.1)\.
- \[7\]J\. H\. Drake, A\. Kheiri, E\. Özcan, and E\. K\. Burke\(2020\)Recent advances in selection hyper\-heuristics\.European Journal of Operational Research285\(2\),pp\. 405–428\.Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p1.1)\.
- \[8\]K\. Helsgaun\(2017\)An extension of the lin\-kernighan\-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems\.Roskilde: Roskilde University12,pp\. 966–980\.Cited by:[§5\.1](https://arxiv.org/html/2605.20618#S5.SS1.p1.2),[Table 2](https://arxiv.org/html/2605.20618#S5.T2.9.9.11.2.1)\.
- \[9\]A\. Hottung, B\. Bhandari, and K\. Tierney\(2021\)Learning a latent search space for routing problems using variational autoencoders\.InInternational Conference on Learning Representations,Cited by:[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[10\]A\. Hottung, Y\. Kwon, and K\. Tierney\(2021\)Efficient active search for combinatorial optimization problems\.International Conference on Learning Representations\.Cited by:[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[11\]A\. Hottung and K\. Tierney\(2020\)Neural large neighborhood search for the capacitated vehicle routing problem\.InECAI 2020 – 24th European Conference on Artificial Intelligence,G\. D\. Giacomoet al\.\(Eds\.\),Frontiers in Artificial Intelligence and Applications, Vol\.325,pp\. 443–450\.External Links:[Document](https://dx.doi.org/10.3233/FAIA200124),[Link](https://doi.org/10.3233/FAIA200124)Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p3.1)\.
- \[12\]A\. Hottung and K\. Tierney\(2022\)Neural large neighborhood search for routing problems\.Artificial Intelligence313,pp\. 103786\.Cited by:[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[13\]S\. Johnn, V\. Darvariu, J\. Handl, and J\. Kalcsics\(2024\)A graph reinforcement learning framework for neural adaptive large neighbourhood search\.Computers & Operations Research172,pp\. 106791\.Cited by:[Appendix 0\.E](https://arxiv.org/html/2605.20618#Pt0.A5.SS0.SSS0.Px2.p1.4),[§2](https://arxiv.org/html/2605.20618#S2.p3.1),[§5\.3](https://arxiv.org/html/2605.20618#S5.SS3.p1.1),[Table 2](https://arxiv.org/html/2605.20618#S5.T2.9.9.12.3.1),[§6](https://arxiv.org/html/2605.20618#S6.p2.1)\.
- \[14\]J\. Kallestad, R\. Hasibi, A\. Hemmati, and K\. Sörensen\(2023\)A general deep reinforcement learning hyperheuristic framework for solving combinatorial optimization problems\.European Journal of Operational Research309\(1\),pp\. 446–468\.Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p3.1)\.
- \[15\]E\. Khalil, H\. Dai, Y\. Zhang, B\. Dilkina, and L\. Song\(2017\)Learning combinatorial optimization algorithms over graphs\.Advances in neural information processing systems30\.Cited by:[§1](https://arxiv.org/html/2605.20618#S1.p3.1)\.
- \[16\]M\. Kim, J\. Park, and J\. Park\(2023\)Learning to cross exchange to solve min\-max vehicle routing problems\.InThe Eleventh International Conference on Learning Representations,Cited by:[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[17\]M\. Kim, J\. Park,et al\.\(2021\)Learning collaborative policies to solve np\-hard routing problems\.Advances in Neural Information Processing Systems34,pp\. 10418–10430\.Cited by:[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[18\]M\. Kim, J\. Park, and J\. Park\(2022\)Sym\-nco: leveraging symmetricity for neural combinatorial optimization\.Advances in Neural Information Processing Systems35,pp\. 1936–1949\.Cited by:[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[19\]W\. Kool, H\. van Hoof, J\. Gromicho, and M\. Welling\(2022\)Deep policy dynamic programming for vehicle routing problems\.InInternational conference on integration of constraint programming, artificial intelligence, and operations research,pp\. 190–213\.Cited by:[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[20\]Y\. Kwon, J\. Choo, B\. Kim, I\. Yoon, Y\. Gwon, and S\. Min\(2020\)Pomo: policy optimization with multiple optima for reinforcement learning\.Advances in Neural Information Processing Systems33,pp\. 21188–21198\.Cited by:[§5\.1](https://arxiv.org/html/2605.20618#S5.SS1.p1.2),[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[21\]F\. Lagos and J\. Pereira\(2024\)Multi\-armed bandit\-based hyper\-heuristics for combinatorial optimization problems\.European Journal of Operational Research312\(1\),pp\. 70–91\.Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p2.1),[§6](https://arxiv.org/html/2605.20618#S6.p2.1)\.
- \[22\]M\. Lindauer, K\. Eggensperger, M\. Feurer, A\. Biedenkapp, D\. Deng, C\. Benjamins, T\. Ruhkopf, R\. Sass, and F\. Hutter\(2022\)SMAC3: a versatile bayesian optimization package for hyperparameter optimization\.Journal of Machine Learning Research23\(54\),pp\. 1–9\.External Links:[Link](http://jmlr.org/papers/v23/21-0888.html)Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p3.1)\.
- \[23\]H\. Lu, X\. Zhang, and S\. Yang\(2019\)A learning\-based iterative method for solving vehicle routing problems\.InInternational conference on learning representations,Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p2.1)\.
- \[24\]Y\. Ma, J\. Li, Z\. Cao, W\. Song, L\. Zhang, Z\. Chen, and J\. Tang\(2021\)Learning to iteratively solve routing problems with dual\-aspect collaborative transformer\.Advances in Neural Information Processing Systems34\(\),pp\. 11096–11107\.Cited by:[Appendix 0\.A](https://arxiv.org/html/2605.20618#Pt0.A1.SS0.SSS0.Px1.p2.1),[Appendix 0\.B](https://arxiv.org/html/2605.20618#Pt0.A2.SS0.SSS0.Px1.p1.2),[§0\.C\.3](https://arxiv.org/html/2605.20618#Pt0.A3.SS3.p1.1),[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[25\]Y\. Ma, Z\. Cao, and Y\. M\. Chee\(2023\)Learning to search feasible and infeasible regions of routing problems with flexible neural k\-opt\.Advances in Neural Information Processing Systems36,pp\. 49555–49578\.Cited by:[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[26\]M\. Mostajabdaveh, F\. S\. Salman, and W\. J\. Gutjahr\(2025\)A branch\-and\-price algorithm for fast and equitable last\-mile relief aid distribution\.European Journal of Operational Research324\(2\),pp\. 522–537\.Cited by:[§1](https://arxiv.org/html/2605.20618#S1.p1.1)\.
- \[27\]F\. Petropoulos, G\. Laporte, E\. Aktas, S\. A\. Alumur, C\. Archetti, H\. Ayhan, M\. Battarra, J\. A\. Bennell, J\. Bourjolly, J\. E\. Boylan, M\. Breton, D\. Canca, L\. Charlin, B\. Chen, C\. T\. Cicek, L\. A\. C\. Jr, C\. S\.M\. Currie, E\. Demeulemeester, L\. Ding, S\. M\. Disney, M\. Ehrgott, M\. J\. Eppler, G\. Erdoğan, B\. Fortz, L\. A\. Franco, J\. Frische, S\. Greco, A\. J\. Gregory, R\. P\. Hämäläinen, W\. Herroelen, M\. Hewitt, J\. Holmström, J\. N\. Hooker, T\. Işık, J\. Johnes, B\. Y\. Kara, Ö\. Karsu, K\. Kent, C\. Köhler, M\. Kunc, Y\. Kuo, A\. N\. Letchford, J\. Leung, D\. Li, H\. Li, J\. Lienert, I\. Ljubić, A\. Lodi, S\. Lozano, V\. Lurkin, S\. Martello, I\. G\. McHale, G\. Midgley, J\. D\.W\. Morecroft, A\. Mutha, C\. Oğuz, S\. Petrovic, U\. Pferschy, H\. N\. Psaraftis, S\. Rose, L\. Saarinen, S\. Salhi, J\. Song, D\. Sotiros, K\. E\. Stecke, A\. K\. Strauss, İ\. Tarhan, C\. Thielen, P\. Toth, T\. V\. Woensel, G\. V\. Berghe, C\. Vasilakis, V\. Vaze, D\. Vigo, K\. Virtanen, X\. Wang, R\. Weron, L\. White, M\. Yearworth, E\. A\. Yıldırım, G\. Zaccour, and X\. Zhao\(2024\)Operational research: methods and applications\.Journal of the Operational Research Society75\(3\),pp\. 423–617\.Cited by:[§1](https://arxiv.org/html/2605.20618#S1.p1.1)\.
- \[28\]L\. Rampášek, M\. Galkin, V\. P\. Dwivedi, A\. T\. Luu, G\. Wolf, and D\. Beaini\(2022\)Recipe for a general, powerful, scalable graph transformer\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 14501–14515\.External Links:[Link](https://arxiv.org/abs/2205.12454)Cited by:[§4\.1](https://arxiv.org/html/2605.20618#S4.SS1.SSS0.Px3.p1.1)\.
- \[29\]L\. Rampášek, M\. Galkin, V\. P\. Dwivedi, A\. T\. Luu, G\. Wolf, and D\. Beaini\(2024\)Recipe for a general, powerful, scalable graph transformer\.InProceedings of the 36th International Conference on Neural Information Processing Systems,NIPS ’22,Red Hook, NY, USA\.External Links:ISBN 9781713871088Cited by:[§4\.3](https://arxiv.org/html/2605.20618#S4.SS3.SSS0.Px1.p1.2)\.
- \[30\]R\. Reijnen, Y\. Zhang, H\. C\. Lau, and Z\. Bukhsh\(2024\)Online control of adaptive large neighborhood search using deep reinforcement learning\.InProceedings of the International Conference on Automated Planning and Scheduling,Vol\.34,pp\. 475–483\.Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p3.1)\.
- \[31\]J\. A\. Soria\-Alcaraz, G\. Ochoa, M\. A\. Sotelo\-Figeroa, and E\. K\. Burke\(2017\)A methodology for determining an effective subset of heuristics in selection hyper\-heuristics\.European Journal of Operational Research260\(3\),pp\. 972–983\.External Links:ISSN 0377\-2217,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.ejor.2017.01.042)Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p1.1)\.
- \[32\]T\. Vidal, T\. G\. Crainic, M\. Gendreau, and C\. Prins\(2013\)A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time\-windows\.Computers & operations research40\(1\),pp\. 475–489\.Cited by:[§5\.1](https://arxiv.org/html/2605.20618#S5.SS1.p1.2),[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1),[Table 2](https://arxiv.org/html/2605.20618#S5.T2.9.9.10.1.1)\.
- \[33\]T\. Vidal\(2022\)Hybrid genetic search for the cvrp: open\-source implementation and swap\* neighborhood\.Computers & Operations Research140,pp\. 105643\.External Links:ISSN 0305\-0548,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.cor.2021.105643),[Link](https://www.sciencedirect.com/science/article/pii/S030505482100349X)Cited by:[Appendix 0\.E](https://arxiv.org/html/2605.20618#Pt0.A5.SS0.SSS0.Px1.p1.8)\.
- \[34\]S\. Wang, B\. Z\. Li, M\. Khabsa, H\. Fang, and H\. Ma\(2020\)Linformer: self\-attention with linear complexity\.arXiv preprint arXiv:2006\.04768\.External Links:[Link](https://arxiv.org/abs/2006.04768)Cited by:[§4\.3](https://arxiv.org/html/2605.20618#S4.SS3.SSS0.Px2.p1.4)\.
- \[35\]N\. A\. Wouda, L\. Lan, and W\. Kool\(2024\)PyVRP: a high\-performance VRP solver package\.INFORMS Journal on Computing36\(4\),pp\. 943–955\.External Links:[Document](https://dx.doi.org/10.1287/ijoc.2023.0055),[Link](https://doi.org/10.1287/ijoc.2023.0055)Cited by:[Appendix 0\.E](https://arxiv.org/html/2605.20618#Pt0.A5.SS0.SSS0.Px1.p1.8)\.
- \[36\]Y\. Wu, W\. Song, Z\. Cao, J\. Zhang, and A\. Lim\(2021\)Learning improvement heuristics for solving routing problems\.IEEE transactions on neural networks and learning systems33\(9\),pp\. 5057–5069\.Cited by:[§5\.2](https://arxiv.org/html/2605.20618#S5.SS2.p1.1)\.
- \[37\]H\. Ye, J\. Wang, Z\. Cao, F\. Berto, C\. Hua, H\. Kim, J\. Park, and G\. Song\(2024\)ReEvo: large language models as hyper\-heuristics with reflective evolution\.InProceedings of the 38th Conference on Neural Information Processing \(NeurIPS 2024\),Vancouver, Canada,pp\. 10–15\.Cited by:[§2](https://arxiv.org/html/2605.20618#S2.p1.1)\.
- \[38\]J\. Zhou, Z\. Cao, Y\. Wu, W\. Song, Y\. Ma, J\. Zhang, and C\. Xu\(2024\)MVMoE: multi\-task vehicle routing solver with mixture\-of\-experts\.InInternational Conference on Machine Learning,Cited by:[§5\.1](https://arxiv.org/html/2605.20618#S5.SS1.p1.2),[§5\.3](https://arxiv.org/html/2605.20618#S5.SS3.p1.1)\.

## Appendix 0\.AProblem\-Specific Feature Definitions

Below we summarize the global and local features used for each problem domain in our experiments\.

##### Vehicle Routing Problem variants

Global feature vectorxux\_\{u\}for each CVRP solution includes:

- •Objective value of the solution\.
- •Number of vehicles\.
- •Number of customers\.
- •Vehicle capacity\.
- •Improvement in objective relative to the parent solution in the PSG\.
- •Sum of objective values of offspring solutions \(graph\-level aggregate\)\.
- •Sum of squares of objective values of offspring solutions \(graph\-level aggregate\)\.
- •Number of offspring solutions \(graph\-level aggregate\)\.

Local structural matrixxVx\_\{V\}for each VRP solution is a matrix of customer coordinates, demand, time windows \(if applicable\), and their positions in the route, encoded using cyclic positional encodings\[[24](https://arxiv.org/html/2605.20618#bib.bib21)\]\.

## Appendix 0\.BSolutions Positional Embeddings

##### Positional Feature Embedding for CVRP and VRPTW\.

Cyclic positional embeddings\[[24](https://arxiv.org/html/2605.20618#bib.bib21)\]were adopted to implicitly encode the edges of VRP solution\. For each dimensionddwith frequencyωd\\omega\_\{d\},

vp​o​s=\{sin⁡\(ωd⋅\|\(z​\(i\)mod4​πωd\)−2​πωd\|\),if​d​is even,cos⁡\(ωd⋅\|\(z​\(i\)mod4​πωd\)−2​πωd\|\),if​d​is odd\.v\_\{pos\}=\\begin\{cases\}\\sin\\\!\\Bigl\(\\omega\_\{d\}\\cdot\\Bigl\|\\Bigl\(z\(i\)\\bmod\\frac\{4\\pi\}\{\\omega\_\{d\}\}\\Bigr\)\-\\frac\{2\\pi\}\{\\omega\_\{d\}\}\\Bigr\|\\Bigr\),&\\text\{if \}d\\text\{ is even\},\\\\\[2\.84526pt\] \\cos\\\!\\Bigl\(\\omega\_\{d\}\\cdot\\Bigl\|\\Bigl\(z\(i\)\\bmod\\frac\{4\\pi\}\{\\omega\_\{d\}\}\\Bigr\)\-\\frac\{2\\pi\}\{\\omega\_\{d\}\}\\Bigr\|\\Bigr\),&\\text\{if \}d\\text\{ is odd\}\.\\end\{cases\}\(6\)wherez​\(i\)z\(i\)represents an evenly spaced position for the nodes over a cycle\.

## Appendix 0\.CArchitecture of a Core Block

### 0\.C\.1CoreBlock: GGCN

Define the outgoing neighbor set𝒩\+​\(i\)\\mathcal\{N\}^\{\+\}\(i\)and incoming set𝒩−​\(i\)\\mathcal\{N\}^\{\-\}\(i\)\.

First, we merge global and local features and compute theaggregated solution embeddingsas follows

zi\(l\)=1N∑k=1NGELU\(𝐆\(ui\(l−1\)vi​k\(l−1\)⌢\)\)∈ℝdzz\_\{i\}^\{\(l\)\}=\\frac\{1\}\{N\}\\sum\_\{k=1\}^\{N\}\\mathrm\{GELU\}\\bigl\(\\mathbf\{G\}\\,\(u\_\{i\}^\{\(l\-1\)\}\\ \{\}^\{\\frown\}v\_\{ik\}^\{\(l\-1\)\}\)\\bigr\)\\quad\\in\\mathbb\{R\}^\{d\_\{z\}\}where N is the size of a problem andG∈ℝdz×\(du\+dv\)G\\in\\mathbb\{R\}^\{d\_\{z\}\\times\(d\_\{u\}\+d\_\{v\}\}\)\. Next, we compute edge‐conditioned gates in both directions:

gatei​j\(l\)=\\displaystyle\\mathrm\{gate\}\_\{ij\}^\{\(l\)\}=tanh⁡\(1\|𝒩\+​\(i\)\|​∑j∈𝒩\+​\(i\)\(𝐖K​zi\(l\)\+𝐖Q​zj\(l\)\+𝐖E​ei​j\)\),\\displaystyle\\quad\\tanh\\\!\\Bigl\(\\frac\{1\}\{\|\\mathcal\{N\}^\{\+\}\(i\)\|\}\\sum\_\{j\\in\\mathcal\{N\}^\{\+\}\(i\)\}\\bigl\(\\mathbf\{W\}\_\{K\}\\,z\_\{i\}^\{\(l\)\}\+\\mathbf\{W\}\_\{Q\}\\,z\_\{j\}^\{\(l\)\}\+\\mathbf\{W\}\_\{E\}\\,e\_\{ij\}\\bigr\)\\Bigr\),gatej​i\(l\)=\\displaystyle\\mathrm\{gate\}\_\{ji\}^\{\(l\)\}=tanh⁡\(1\|𝒩−​\(i\)\|​∑j∈𝒩−​\(i\)\(𝐖K​zj\(l\)\+𝐖Q​zi\(l\)\+𝐖E​ej​i\)\),\\displaystyle\\quad\\tanh\\\!\\Bigl\(\\frac\{1\}\{\|\\mathcal\{N\}^\{\-\}\(i\)\|\}\\sum\_\{j\\in\\mathcal\{N\}^\{\-\}\(i\)\}\\bigl\(\\mathbf\{W\}\_\{K\}\\,z\_\{j\}^\{\(l\)\}\+\\mathbf\{W\}\_\{Q\}\\,z\_\{i\}^\{\(l\)\}\+\\mathbf\{W\}\_\{E\}\\,e\_\{ji\}\\bigr\)\\Bigr\),where𝐖K,𝐖Q,𝐖E\\mathbf\{W\}\_\{K\},\\mathbf\{W\}\_\{Q\},\\mathbf\{W\}\_\{E\}are learnable keys, queries andei​je\_\{ij\}encodes the heuristic on edge\(i→j\)\(i\\\!\\to\\\!j\)\.

We then update each hidden feature row via gated message passing:

hi​k\(l\)=\\displaystyle h\_\{ik\}^\{\(l\)\}=hi​k\(l−1\)\+1\|𝒩\+​\(i\)\|​∑j∈𝒩\+​\(i\)gatei​j\(l\)​hj​k\(l−1\)\\displaystyle h\_\{ik\}^\{\(l\-1\)\}\+\\frac\{1\}\{\|\\mathcal\{N\}^\{\+\}\(i\)\|\}\\sum\_\{j\\in\\mathcal\{N\}^\{\+\}\(i\)\}\\mathrm\{gate\}\_\{ij\}^\{\(l\)\}\\,h\_\{jk\}^\{\(l\-1\)\}\+\\displaystyle\+1\|𝒩−​\(i\)\|​∑j∈𝒩−​\(i\)gatej​i\(l\)​hj​k\(l−1\)\.\\displaystyle\\frac\{1\}\{\|\\mathcal\{N\}^\{\-\}\(i\)\|\}\\sum\_\{j\\in\\mathcal\{N\}^\{\-\}\(i\)\}\\mathrm\{gate\}\_\{ji\}^\{\(l\)\}\\,h\_\{jk\}^\{\(l\-1\)\}\.Hereh\(l−1\)=V\(l−1\)​Hh^\{\(l\-1\)\}=V^\{\(l\-1\)\}Hprojects the local matrix viaHH\.

Finally, we fuse these updates back into the node embeddings with residual connections:

u^i\(l\)=ui\(l−1\)\+𝐖u​\(zi\(l\)\+1N​∑k=1Nhi​k\(l\)\),\\hat\{u\}\_\{i\}^\{\(l\)\}=u\_\{i\}^\{\(l\-1\)\}\+\\mathbf\{W\}\_\{u\}\\Bigl\(z\_\{i\}^\{\(l\)\}\+\\frac\{1\}\{N\}\\sum\_\{k=1\}^\{N\}h\_\{ik\}^\{\(l\)\}\\Bigr\),
v^i​k\(l\)=vi​k\(l−1\)\+𝐖v​hi​k\(l\),\\hat\{v\}\_\{ik\}^\{\(l\)\}=v\_\{ik\}^\{\(l\-1\)\}\+\\mathbf\{W\}\_\{v\}\\,h\_\{ik\}^\{\(l\)\},where𝐖u\\mathbf\{W\}\_\{u\}and𝐖v\\mathbf\{W\}\_\{v\}are learnable projections andu^\\hat\{u\}andV^=\[v^i​k\]\\hat\{V\}=\[\\hat\{v\}\_\{ik\}\]are output representations of global and local embeddings, respectively\.

### 0\.C\.2CoreBlock: Transformer

The attention and features matrices are treated separately\. The attention is computed from globalu^\\hat\{u\}and internalV^\\hat\{V\}features using condensed solution\-wide representations:

zi\(l\)=1N∑k=1NGELU\(𝐆\(u^i\(l−1\)v^i​k\(l−1\)⌢\)\)∈ℝdzz\_\{i\}^\{\(l\)\}=\\frac\{1\}\{N\}\\sum\_\{k=1\}^\{N\}\\mathrm\{GELU\}\\bigl\(\\mathbf\{G\}\\,\(\\hat\{u\}\_\{i\}^\{\(l\-1\)\}\\ \{\}^\{\\frown\}\\hat\{v\}\_\{ik\}^\{\(l\-1\)\}\)\\bigr\)\\quad\\in\\mathbb\{R\}^\{d\_\{z\}\}A\(l\)=softmax\(\(Zl−1​Q\)​\(Z\(l−1\)​K\)⊤D\)∈ℝN×N,A^\{\(l\)\}=\\operatorname\{softmax\}\\\!\\Bigl\(\\tfrac\{\(Z^\{l\-1\}Q\)\\,\(Z^\{\(l\-1\)\}K\)^\{\\top\}\}\{\\sqrt\{D\}\}\\Bigr\)\\quad\\in\\mathbb\{R\}^\{N\\times N\},whereZ∈ℝN×dzZ\\in\\mathbb\{R\}^\{N\\times d\_\{z\}\}is the matrix of allziz\_\{i\}in a PSG,Q∈ℝD×dzQ\\in\\mathbb\{R\}^\{D\\times d\_\{z\}\}is the queries matrix andK∈ℝD×dzK\\in\\mathbb\{R\}^\{D\\times d\_\{z\}\}is the matrix of keys\.

In contrast, internal featuresV^\\hat\{V\}are updated in a more granular manner using the unrolled attention\-weighted summation over allMMsolutions in the PSG:

V~att\(l\)=A\(l\)⊗\(V^\(l−1\)WV\)∈ℝM×N×dv,\\tilde\{V\}\_\{\\mathrm\{att\}\}^\{\(l\)\}=A^\{\(l\)\}\\,\\otimes\\bigl\(\\hat\{V\}^\{\(l\-1\)\}W\_\{V\}\\bigr\)\\quad\\in\\mathbb\{R\}^\{M\\times N\\times d\_\{v\}\},for whichA∈ℝM×1×MA\\in\\mathbb\{R\}^\{M\\times 1\\times M\}is broadcasted over N internal dimensions andWV∈ℝ1×dv×dvW\_\{V\}\\in\\mathbb\{R\}^\{1\\times d\_\{v\}\\times d\_\{v\}\}is just a learnable linear projector into the layers latent space\.

Eventually, theV~\\tilde\{V\}is updated in a rather typical manner for transformer layers:

V~\(l\)=V^\(l−1\)\+V~att\(l\),\\tilde\{V\}^\{\(l\)\}=\\hat\{V\}^\{\(l\-1\)\}\+\\tilde\{V\}\_\{\\mathrm\{att\}\}^\{\(l\)\},
V~\(l\)=LayerNorm​\(V~\(l\)\+FFN​\(V~\(l\)\)\),\\tilde\{V\}^\{\(l\)\}=\\mathrm\{LayerNorm\}\\\!\\bigl\(\\tilde\{V\}^\{\(l\)\}\+\\mathrm\{FFN\}\(\\tilde\{V\}^\{\(l\)\}\)\\bigr\),whereFFN\\mathrm\{FFN\}is a two‐layer feed‐forward network with GELU activation, andLayerNorm\\mathrm\{LayerNorm\}denotes layer normalization\. This block aggregates information globally — irrespective of graph distance — while residual connections and normalization stabilize training\.

### 0\.C\.3CoreBlock: Problem\-Specific End\-to\-End Modules

For CVRP, we adopt the dual\-aspect Transformer architecture from\[[24](https://arxiv.org/html/2605.20618#bib.bib21)\], which combines global instance\-level representations with a local GCN/GAN module\. We use the same for VRPTW\.

### 0\.C\.4Beam search

The beam search algorithm is described as[algorithm˜1](https://arxiv.org/html/2605.20618#alg1)\. Constrained beam search operates on the initial set of sequences denoted asS0S\_\{0\}\. For each item in a sequence, probabilitiesPPare computed using theJumpAgent\. Within each route, displacement probabilities are averaged to estimate the route’s overall optimality\. The three least probable routes are identified and discarded\. The remaining routes, retained fromS0S\_\{0\}, serve as the starting point for the constrained beam search\.

Beam search begins with an empty set of completed candidatesFF\. At each iteration, every unassigned unique consumer is systematically added to every candidate sequence in the poolSS, each of length\|S0\|\+i​t​e​r​a​t​i​o​n\|S\_\{0\}\|\+iteration\. To account for route splits or merges, the depot is also included among the possible consumers\. Such extension generates up toNB​e​a​m×\|s∉Routes\|N\_\{Beam\}\\times\|s\\notin\\text\{Routes\}\|new candidate sequences of length\|S0\|\+i​t​e​r​a​t​i​o​n\+1\|S\_\{0\}\|\+iteration\+1\. To maintain the constant beam search width,NB​e​a​m−\|F\|N\_\{Beam\}\-\|F\|candidates are randomly selected from this expanded pool, using the probability distribution inPPas the sampling weight\. When any of the new candidate solutionSiS\_\{i\}incorporates all the consumers, it is transferred from the candidate poolSSto the pool of finished solutionsFF\.

The iteration process terminates when the objective value of the worst completed solution,max⁡F\\max\{F\}, exceeds the best theoretically achievable score among all incomplete candidates,min⁡S\\min\{S\}\. The algorithm returns the solution fromFFwith the most favorable objective value\.

Algorithm 1Constrained Beam SearchS0S\_\{0\}\{Initial sequence\}

R​o​u​t​e​s←max⁡P​\(S0\)Routes\\leftarrow\\max\{P\(S\_\{0\}\)\}\{Most probable routes\}

for

i=1i=1to

NB​e​a​mN\_\{Beam\}do

Si←∀s∈S0s∉R​o​u​t​e​sS\_\{i\}\\leftarrow\\forall s\\in S\_\{0\}\\quad s\\notin Routes

endfor

F←∅F\\leftarrow\\emptyset

while

S≠∅​and​min⁡S<max⁡FS\\neq\\emptyset\\text\{ and \}\\min\{S\}<\\max\{F\}do

B←∅B\\leftarrow\\emptyset

for

i=1i=1to

\|S\|\|S\|do

for

j=1j=1to

\|R​o​u​t​e​s\|\|Routes\|do

Bi​j←Si∪R​o​u​t​e​sjB\_\{ij\}\\leftarrow S\_\{i\}\\cup Routes\_\{j\}

endfor

endfor

S←Sample​\(B,P,NBeam−\|F\|\)S\\leftarrow\\text\{Sample\}\(B,P,N\_\{\\text\{Beam\}\}\-\|F\|\)

for

i=1i=1to

\|S\|\|S\|do

if

∀r∈R​o​u​t​e​sr∈Si\\forall r\\in Routes\\quad r\\in S\_\{i\}then

F←F∪SiF\\leftarrow F\\cup S\_\{i\}

endif

endfor

endwhile

return

min⁡F\\min\{F\}

## Appendix 0\.DBenchmark Problems

##### Capacitated Vehicle Routing Problem \(CVRP\)

is defined as follows\. LetG=\(V,E\)G=\(V,E\)be a complete graph with vertex setV=\{0\}∪CV=\\\{0\\\}\\cup C, where0denotes the depot andCCthe set of customers\. Each customeri∈Ci\\in Chas demandδi\\delta\_\{i\}, and each arc\(i→j\)∈E\(i\\to j\)\\in Ecarries weightdi​jd\_\{ij\}, the Euclidean distance betweeniiandjj\. A solution is a collection of routes—each route is a cycle beginning and ending at the depot, visiting its assigned customers exactly once, subject to the vehicle capacity constraint\. The objective is to minimize the sum of all route distances\.

##### Vehicle Routing Problem with Time Window \(VRPTW\)

is a common extension of the CVRP\. Each customeriihas a time window\[ei,ℓi\]\[e\_\{i\},\\,\\ell\_\{i\}\]that specifies the earliest and latest allowable service times\. A vehicle may begin service atiino earlier thaneie\_\{i\}and no later thanℓi\\ell\_\{i\}; otherwise, the delivery is infeasible\.

## Appendix 0\.ETraining Dataset Generation

##### Node & Move Selection Dataset

For each problem instance in training set, we first compute a near‐optimal solutions∗s^\{\*\}using a state‐of‐the‐art solver \(e\.g\., HGS for VRP variants\[[33](https://arxiv.org/html/2605.20618#bib.bib49),[35](https://arxiv.org/html/2605.20618#bib.bib48)\]\)\. We then perturbs∗s^\{\*\}to generate a set𝒮P\\mathcal\{S\}^\{P\}of solutions whose objective values lie within controlled gaps of 0\.1 %, 1 %, 2 %, 3 %, 4 %, 5% and 10 % froms∗s^\{\*\}\. To ensure diversity in the perturbed nodes while maintaining the target gap, we add a sufficiently large constant penalty on the decisions present ins∗s^\{\*\}\(denotedI​\(s∗\)I\(s^\{\*\}\)\) to the objective function, and repeatedly apply random moves from the move setℳ\\mathcal\{M\}until the perturbed solution meets the desired gap threshold\. Next, we restore the original objective function and apply random moves to each perturbed solutionsPs^\{P\}, keeping only those moves that successfully improve the objective\. We repeat this “perturb\-and\-improve” process many times per instance to collect a large set of training PSGs\.

To form training samples, we then randomly sample subgraphs from these PSGs, selecting at most one move pair from each independent PSG\. Let𝒢s=\{𝒢1s,𝒢2s,…,𝒢ks\}\\mathcal\{G\}^\{s\}=\\\{\\mathcal\{G\}^\{s\}\_\{1\},\\mathcal\{G\}^\{s\}\_\{2\},\\dots,\\mathcal\{G\}^\{s\}\_\{k\}\\\}be the set of sampled subgraphs for one problem instance\. Within each𝒢i\\mathcal\{G\}\_\{i\}, we label every candidate move as 0, except for the single move that brings us closest to the original solutions∗s^\{\*\}that move is labeled 1\. Any sample in which multiple moves tie for the best improvement is discarded, ensuring exactly one positive move per subgraph\. Fig\.[6](https://arxiv.org/html/2605.20618#Pt0.A5.F6)illustrate an example on how a training sample is generated using the training PSGs\.

![Refer to caption](https://arxiv.org/html/2605.20618v1/fig/Sampling.png)Figure 6:Node & Move Selection training sample\.Left:Three PSGs converging from distinct perturbed solutions\.Right:A training sample with three sub\-graphs sampled from the PSGs on the left with labels\.
##### Jump Agent Dataset

For our jump model, using the same training instances, we generate multiple trajectories per instance by running ALNS\[[13](https://arxiv.org/html/2605.20618#bib.bib16)\]from different random starts until convergence to a local optimum\. We record each trajectory as a PSG \(a sequence of solutionssks\_\{k\}and movesmm\)\. Then, we sample a subgraph𝒢\\mathcal\{G\}as in the node–move dataset and pair each solutionsk∈𝒢ss\_\{k\}\\in\\mathcal\{G\}^\{s\}with the known global optimum as the prediction target\.

## Appendix 0\.FReproducibility

This appendix documents the configuration used to produce all results in the main paper\. Framework\-level settings shared across agents are listed in Table[4](https://arxiv.org/html/2605.20618#Pt0.A6.T4); per\-agent training hyperparameters appear in Table[5](https://arxiv.org/html/2605.20618#Pt0.A6.T5)\. Both the Selection Agents and the Jump Agent use a step learning\-rate scheduler with step size100100andγ=0\.998\\gamma=0\.998\. All values are held fixed across VRPTW and CVRP\.

Table 4:Framework\-level configuration shared across all agents\.Table 5:Training hyperparameters for the Node/Move Selection Agents and the Jump Agent\.