EFormer: An Effective Edge-based Transformer for Vehicle Routing Problems

1 Introduction

The vehicle routing problem (VRP), a fundamental NP-hard combinatorial optimization problem (COP), appears in numerous real-world contexts, including logistics [Konstantakopoulos et al., 2022], navigation systems [Elgarej et al., 2021], and circuit design [Brophy and Voigt, 2014]. Despite extensive research across various fields, VRPs remain notably challenging due to their inherent computational complexity [Ausiello et al., 2012]. Approaches to solving VRPs can be divided into exact algorithms and heuristic algorithms [Helsgaun, 2017]. Exact algorithms, although theoretically robust, often face scalability issues when applied to large instances because of their high computational demands. In contrast, heuristic algorithms are generally more practical yet depend heavily on manually crafted rules and domain-specific knowledge, which restricts their applicability and generalizability.

* Yaqing Hou is the Corresponding author.

Recently, there has been a surge in neural heuristics that leverage deep (reinforcement) learning to solve VRPs. These methods learn problem-solving strategies end-to-end from data, offering a novel and efficient perspective on VRPs [Kool et al., 2019]. Compared to traditional heuristics, neural heuristics typically provide higher solution efficiency and stronger generalization capabilities [Zhang et al., 2025].

Nevertheless, most existing neural heuristics rely heavily on node coordinates (or their embeddings) as a crucial input to the model, with many methods generating problem instances from these coordinates to train neural networks. The core assumption is that the relationship between coordinates and distance can be readily learned by the network when searching for the shortest path, particularly in classical Euclidean spaces. In these approaches, each iteration selects a node from the problem instance, and the encoded information of the remaining nodes is then used to incrementally construct the solution by inferring the corresponding Euclidean distance. However, this prevalent focus on node coordinates often lacks the robustness and generalizability required in practical applications. When distances cannot be easily inferred from coordinates alone, such methods tend to struggle, reducing their effectiveness in solving VRPs-especially in scenarios where the input space deviates from idealized conditions.

To address this issue, we propose a neural heuristic featuring an Edge-based Transformer (EFormer) model that exclusively relies on edge information as the original input. Specifically, we introduce a precoder module that employs a multi-head mixed-score attention mechanism to convert edge information into temporary node embeddings. We then design a parallel encoding strategy comprising two encoders: a graph encoder and a node encoder. The graph encoder employs a residual gated graph convolution network (GCN) to process sparse graph embeddings, while the node encoder leverages attention mechanisms to independently process temporary node embeddings. By encoding these two embedding types in separate feature spaces, the model achieves a more comprehensive representation of global edge relationships. Finally, parallel context embedding and multiple-query integration are used to decode the two types of encoded features, facilitating the effective construction of a complete path. The EFormer is trained using reinforcement learning in an autoregressive manner and achieves favorable performance on the TSP and CVRP. Accordingly, our contributions can be summarized as follows:

• Novel Edge-based Transformer (EFormer). We propose a new and practical edge-based Transformer model designed to leverage the edge information for solving VRPs. The introduction of a multi-head mixed-score attention mechanism enables the extraction of temporary node features directly from edge weights.
• Parallel Encoding Strategy. We develop a parallel encoding strategy that utilizes residual gated graph convolution networks to encode graph embeddings and attention mechanisms to process node embeddings. By encoding graph and node embeddings in separate feature spaces, the model generates more comprehensive global edge relationship embeddings. A multiple-query integration method is then used to decode the embeddings, facilitating complete path construction.
• Favorable Performance and Versatility. Our purely edge-based method demonstrates strong performance on TSP and CVRP, surpassing other edge-based neural methods. Its robust generalization is evident in its performance on real-world instances from TSPLib and CVRPLib across diverse scales and distributions. The edge-based nature of EFormer also allows us to apply it to Asymmetric TSP (Appendix D). Furthermore, we demonstrate its versatility by adapting it to solve VRPs using only node information as input (Appendix C) 1 .

2 RelatedWork

2.1 Node-based Neural Heuristics for VRP

Graph neural network-based methods. Graph neural networks (GNNs) [Scarselli et al., 2008] provide a flexible framework for learning message-passing strategies among nodes, making them applicable to graphs of arbitrary size. In the context of routing problems, GNNs typically predict edge probabilities or scores, which are then leveraged by search algorithms (e.g., beam search, tree search, or guided local search) to produce approximate solutions [Khalil et al., 2017; Li et al., 2018; Nowak et al., 2017; Joshi et al., 2019; Fu et al., 2021; Xin et al., 2021; Hudson et al., 2021; Kool et al., 2022; Min et al., 2024]. [Khalil et al., 2017] proposed one of the earliest unified frameworks that combine reinforcement learning with graph embeddings to solve various combinatorial optimization (CO) problems on graphs. In another line of work, [Li et al., 2018] incorporated advanced Graph Convolutional Networks (GCNs) [Kipf and Welling, 2016] alongside tree search to explore the solution space for CO problems. [Nowak et al., 2017] applied supervised learning to train a GNN and employed beam search to obtain feasible solutions. [Joshi et al., 2019] designed a GCN model to predict a "heatmap" of edge probabilities in TSP instances, which guides beam search to produce feasible solutions.

1 http://arxiv.org/abs/2506.16428

Transformer-based constructive methods. Among various neural construction heuristics, the Transformer [Vaswani, 2017] represents a major breakthrough and has progressively become the leading approach for solving VRPs. These methods typically construct solutions incrementally by selecting one node at a time from the problem instance. Representative methods in this category include [Nazari et al., 2018; Kim et al., 2021; Kool et al., 2019; Kwon et al., 2020; Jin et al., 2023b; Drakulic et al., 2023; Luo et al., 2023; Huang et al., 2025; Lin et al., 2024]. Specifically, [Kool et al., 2019] is the first to leverage the Transformer architecture in a method called Attention Model (AM), thereby introducing a more powerful neural heuristic for VRPs. One notable variant of AM is POMO [Kwon et al., 2020], which applies multiple optimal policies to significantly enhance AM's learning and inference capabilities. More recently, [Luo et al., 2023] proposed the Light Encoder and Heavy Decoder (LEHD) model, trained via supervised learning on 100-node instances. LEHD not only achieves higher-quality solutions but also demonstrates strong generalization capabilities.

Transformer-based improvement methods. Neural improvement heuristics iteratively refine an initial feasible solution until a stopping criterion (e.g., convergence) is reached. Drawing inspiration from classical local search algorithms, they can optimize sub-problems or apply improvement operators (e.g., k-opt) to enhance solution quality. Representative improvement-based approaches include [Lu et al., 2019; Barrett et al., 2020; Wu et al., 2021; Ma et al., 2021; Li et al., 2021; Wang et al., 2021; Kim et al., 2023; Cheng et al., 2023].

2.2 Edge-based Neural Heuristics for VRP

Most neural heuristics, typically based on GNNs or Transformers, capture the structure of routing problems by treating the coordinates of problem instances as node features (Figure 1, (a)). However, encoding edge features rather than relying solely on node features more closely aligns with practical applications. Early works incorporating edge features include variants of Graph Attention Networks (GAT) [Veliˇckovi´c et al., 2017]. For example, [Chen and Chen, 2021] introduced Edge-featured Graph Attention Networks (EGAT), which consider edge features during message-passing, while [Shi et al., 2020] integrated edge features into attention-based GNNs using "Graph Transformers" for semi-supervised classification. In addition, [Jin et al., 2023a] proposed EdgeFormers, an architecture that processes text edge networks to enhance GNNs for better utilization of edge (text) features.

In the context of routing problems, several edge-based approaches have been explored, such as MatNet [Kwon et al., 2021] and GREAT [Lischka et al., 2024]. Specifically, [Kwon et al., 2021] proposed a Matrix Encoding Network (MatNet) that accepts an encoded distance matrix to solve complex asymmetric traveling salesman (ATSP) and flexible flow shop (FFSP) problems. Meanwhile, [Lischka et al., 2024] introduced the Graph Edge Attention Network (GREAT), an edgebased neural model related to GNNs, which uses highly sparse graphs to achieve high-quality solutions. Following this line of research, our work also focuses on edge-based methods and proposes a neural network model architecture that improves the solution quality for solving VRPs (Figure 1, (b)).

3 Methodology: EFormer

We introduce the EFormer, a model for solving VRPs that comprises four main components: a precoder, a graph encoder, a node encoder, and a decoder. Given a set of edge information, EFormer first applies the precoder to generate temporary node embeddings. To mitigate the heavy computation arising from dense graphs, we adopt a k-nearest neighbor (k-nn) heuristic to sparsify them. It then employs parallel graph and node encoders to process graph and node embeddings in distinct feature spaces, respectively. Finally, the decoder constructs a path by integrating parallel context embeddings and a multi-query mechanism. Figure 2 shows the overall framework of EFormer, while a more detailed version is provided in Appendix A.1.

3.1 Precoder

The precoder processes externally provided edge information to generate node embeddings, effectively serving as a preencoding step in EFormer. It comprises a multi-head mixedscore attention layer and a feed-forward (FF) layer, as shown in Figure 2. We introduce its key steps below.

The input's initial representations. Along with the edge weights, we also incorporate a zero vector, a one-hot vector, and the edge weight matrix. This approach is crucial because the one-hot vector is randomly selected from a predefined matrix pool, ensuring that each iteration generates unique embeddings. Consequently, we can supply the same problem instances along with the zero embedding multiple times, enabling flexible instance augmentation.

We generally follow the graph attention networks (GATs) framework [Veliˇckovi´c et al., 2017], which is described in detail in Appendix A.2. Nevertheless, unlike the classic GATs, the attention score for a pair of nodes (i, j) in our method depends not only on ˆhi and ˆhj, but also on the edge weight e(i, j). The precoder's update function is defined as:

where the learnable update function F leverages multi-head attention (MHA). Its aggregation process uses attention scores for each node pair (i, j), which are determined by ˆhi and ˆhj . Here, R denotes the set of adjacent nodes of i, and M denotes the set of adjacent nodes of j.

Mixed-score attention. For inputs containing only edge information, it is crucial to incorporate edge weights e(i, j) ≡ Dij in the attention mechanism. Drawing inspiration from [Kwon et al., 2021], we adopt a "Multi-Head Mixed-Score Attention" block to process the edge weight matrix. This block closely follows the MHA module in Transformer, except that the scaled dot-product attention in each head is replaced with mixed-score attention. Specifically, the block integrates the externally provided edge distance matrix Dij with the internally generated attention scores. A small Multilayer Perceptron (MLP) with two inputs and one output determines the optimal way to combine these scores. The resultant mixed scores then pass through a "softmax" stage, thereby retaining matrix-based representation crucial to attention mechanisms.

By performing mixed-score attention on the given edge information, it produces an encoded relationship matrix h(P) i , which acts as the node embeddings for both the graph and node encoders. This process is given by:

where Dij is edge weight matrix, hr is zero-vector embedding, and hc is one-hot vector embedding.

Instance augmentation. Since we initialize each run with a random sequence of one-hot vectors, the weight matrix Dij is encoded differently each time. As a result, the precoder can yield diverse representations of the same problem instance and generate distinct solutions. By providing a new one-hot vector sequence for each run, a multitude of different solutions can be readily obtained simply by repeatedly executing the model. Moreover, this random one-hot embedding strategy naturally aligns with the "instance augmentation" technique proposed in POMO [Kwon et al., 2020]. However, whereas POMO provides ×8 instance augmentation, EFormer can achieve ×N

augmentation. The trade-off is that while this approach yields higher-quality solutions, it also increases runtime.

3.2 Graph Encoder

The graph encoder is a pivotal component of our parallel strategy, comprising residual gated GCN layers and MLP layers. It processes a sparse graph formed by the edge embeddings and node embeddings produced by the precoder.

Graph sparsification. To mitigate the computational burden arising from dense graphs, we employ a k-nn heuristic, in which each node is connected to its k nearest neighbors. The choice of k and its impact on training efficiency are evaluated in the experimental section, where we demonstrate the importance of sparsity for improving training efficiency.

Input layer. The precoder's output h(P) i , serves as the graph encoder's node embedding. We project h(P) i into hdimensional feature as xl=0 i = A1h(P) i with A1 ∈ Rh .

We define an edge adjacency matrix function δKNN ij , which has a value of 1 if nodes i and j are k-nearest neighbors, a value of 2 if they are self-connected, and a value of 0 otherwise. The edge adjacency matrix δKNN ij and the edge weight matrix Dij are embedded as h2 -dimensional feature vectors. Then we concatenate the two together to get the edge input feature as el=0 ij = A2Dij + b3||A3 · δKNN ij , where A2 ∈ R h2 , A3 ∈ R h2 , b3 is the bias, and ·||· is the concatenation operator.

Residual gated Graph Convolution layer. Let xli and elij represent the node and edge embedding associated with the node i and edge (i, j) at layer l, respectively. In our method, we employ the GCN architecture introduced in [Bresson and Laurent, 2017], to produce the node embedding xl+1 i and edge embedding el+1 ij at the next layer as follows:

where W l∗ ∈ Rh , σ is the sigmoid function, ξ is a small value, ReLU is the rectified linear unit, and BN stands for batch normalization [Ioffe, 2015]. Meanwhile, GCN exploits the additive edge feature representation and dense attention map ηij , to make the diffusion process anisotropic on the graph.

MLP layer. In the final layer, MLP modules process both the node and edge embeddings derived from the GCN layers. Here, we specifically focus on the node embedding xli , which inherently incorporates the relevant edge and node information. The MLP outputs hGij in [0, 1]2 defined as hGij = MLP(xli ), where the number of MLP layers is denoted by lmlp.

3.3 Node Encoder

Node encoder processes the node embeddings generated by precoder, using attention mechanisms to embed them into the distinct feature space and produce encoded representations.

Input layer. Unlike the traditional approach [Kool et al., 2019] that relies on node coordinates, the node encoder uses the temporary node embedding h(P ) i derived from the precoder as the input to its attention layer. Let H(0) denote the input to the first layer, then it will be given as H(0) = h(P) i .

Attention layer. Node encoder comprises n attention layers. Each attention layer consists of two sublayers: a MHA sublayer and a FF sublayer [Vaswani, 2017]. Each sublayer incorporates a residual connection [He et al., 2016] and batch normalization (BN). We denote the embedding obtained from each layer as h(l) i , and let H(l-1) = (h(l-1) 1 , h(l-1) 2 , . . . , h(l-1) n ) be the input to the l-th attention layer when l = {1, ..., L}. The output of the attention layer for the embedding of the i-th node is calculated as follows:

where the FF sublayer includes one hidden sublayer and ReLU activation. The above process and the final output can be summarized as follows:

Note. we employ two parallel encoding components-the graph encoder and node encoder-both of which take node embeddings as (one of the) inputs. One might wonder why the node encoder is needed if the graph encoder can already handle node embeddings. Although using multiple GCN layers can yield powerful encoding representations, it often increases model complexity. By contrast, the node encoder uses fewer layers and leverages attention mechanisms, allowing the model to remain lightweight while still delivering strong performance. Moreover, the attention mechanisms have been shown to be highly effective for encoding node embeddings. Empirically, this parallel architecture outperforms approaches that rely solely on GCNs or a single attention-based encoder.

3.4 Decoder

During the decoding phase, the edge embeddings and node embeddings produced by the graph encoder and node encoder, respectively, are processed in parallel. We use superscripts to differentiate the sources of information: G denotes edge embeddings, while N denotes node embeddings. Initially, two separate sets of keys and values are extracted from the edge and node embeddings. In parallel, the current contextual embedding is derived from the current state in combination with these two sets of embeddings.

The embeddings of all the starting nodes hGfirst , hNfirst (i.e., the nodes selected in the first step) and the embeddings of the target nodes hGlast , hNlast (i.e., the currently selected nodes) are concatenated to form two sets of temporary queries (i.e., qG, qN ). Afterwards, the two sets of context embeddings are merged to create the final query as follows:

where the subscript first denotes the fixed start node, and the subscript last denotes the current target node. W G 1 ,W G 2 ,W N 1 and W N 2 are learnable matrices used to recast the start node embeddings hGfirst , hNfirst and the current target node embeddings hGlast , hNlast , respectively.

Next, we apply the MHA mechanism to each set of context embeddings separately, producing two outputs, AG and AN :

We then apply two linear layers W G 3 andW N 3 to map AG and AN , respectively. Subsequently, we compute a score via two sets of single-head attention layers, apply the tanh function to clip the score, and mask any visited nodes. The resulting score uj for node j is given by:

where W G 3 and W N 3 are learnable matrices, uj is the score for node j, and dk is determined by the embedding dimension.

We then apply the softmax function to calculate the probability pj of selecting node j. At each decoding step j, the next node is selected based on its probability pj . Repeating this process n times yields the complete solution τ = {τ 1 , · · · , τ n }T :

3.5 Training

Since EFormer can be easily integrated into a variety of autoregressive solvers, we adopt the same reinforcement learning training method as POMO. We train the EFormer model using the REINFORCE algorithm [Williams, 1992]. We sample a set of n trajectories {τ 1 , · · · , τ n }, calculate the reward f(τ i ) for each, and employ approximate gradient ascent to maximize the expected return L. The gradient of the total training loss L can be approximated as follows:

where bi (s) is commonly set as the average reward of those m trajectories, serving as a shared baseline:

4 Experiment

We empirically evaluate our proposed EFormer model on TSP and CVRP of various sizes and distributions, comparing it against both learning-based and classical solvers. Our code is publicly available 2 .

Basic Settings. We compare EFormer with: (1) Classical solvers: Concorde [Cook et al., 2011], LKH3 [Helsgaun, 2017], HGS [Vidal, 2022], and OR-Tools [Perron and Furnon, 2023]; (2) Heatmap-based method: GCN-BS [Joshi et al., 2019]; (3) Edge-based neural heuristics: MatNet [Kwon et al., 2021] and GREAT [Lischka et al., 2024]. We follow the standard data generation procedures from prior work [Kool et al., 2019] to create training and testing datasets for TSP and CVRP, where distances between nodes are calculated and provided as inputs accordingly. Each training epoch samples 100,000 random instances, while a separate set of 10,000 uniformly generated instances is used for testing. Optimal solutions for TSP are obtained via the Concorde solver, and those for CVRP using LKH3. We adopt the POMO inference algorithm [Kwon et al., 2020] and report both the optimality gap and inference time. For EFormer specifically, we present results for greedy inference (×1) and instance augmentation (×8 and ×128). Details of the experimental setup and additional baseline information can be found in Appendix B.1.

Table 1 presents our main results on uniformly distributed TSP and CVRP instances. For TSP, our proposed EFormer achieves excellent greedy inference (x1) performance across various instance sizes, all within a relatively reasonable inference time. Additionally, we perform inferences with instance augmentation (×8, ×128), which significantly outperform other neural heuristics. Notably, our x8 augmentation even surpasses MatNet's x128 augmentation. For TSP100, the optimality gap can be as low as 0.0453% when using x128 augmentation. EFormer thus clearly outperforms other edge-based methods, whether using greedy inference or instance augmentation.

2 https://github.com/Regina921/EFormer

For CVRP, we extend and refine the two learning-based baselines from their original formulations while retaining their model structure and parameters to ensure effective CVRP solutions. Regardless of whether greedy inference (×1) or instance augmentation (×8 or ×128) is employed, our EFormer consistently outperforms other edge-based methods. With ×128 augmentation, EFormer achieves an optimality gap of 0.5633% on CVRP100. Thus, EFormer demonstrates superior performance over competing approaches under both greedy inference and augmented settings. Given a larger time budget, EFormer can leverage additional instance augmentation to further enhance performance across all instances.

Generalization to larger-scale instances. Appendix B.2 shows the performance of EFormer on TSP and CVRP instances with up to 500 nodes. Despite device limitations, EFormer significantly surpasses other edge-based methods, highlighting its robust generalization even when only edge information is available.

Generalization across different distributions. We further evaluate EFormer on TSP and CVRP instances from explosion, grid, and implosion distributions. Appendix B.3 presents the results, indicating that EFormer consistently outperforms GCN-BS and MatNet across all three distributions. Moreover, it maintains strong performance not only on the uniform distribution but also under varying distribution scenarios, underscoring its solid generalization capabilities.

4.3 Node-based EFormer

Our EFormer architecture is highly flexible, enabling it to address VRPs using node coordinates as the only inputs. To compare the performance of EFormer-based solvers with other established methods, we introduce a variant called EFormernode, which is tested on the traditional node-coordinate setting. Experimental results indicate that EFormer-node delivers competitive performance compared to other established neural heuristics. For further details on the model architecture and experimental findings, please refer to Appendix C. Additionally, we also solve ATSP based on our EFormer framework, and the detailed experimental results are presented in Appendix D.

5 Conclusion

In this paper, we introduce a novel Edge-based Transformer (EFormer) model designed to solve VRPs in an autoregressive way that utilizes edge information as input. Our integrated architecture employs three encoders that work in concert to efficiently capture and process edge information. By adopting a parallel encoding approach, we encode different types of information in separate feature spaces, thereby enhancing the global strategy. Extensive experiments on both uniformly generated synthetic instances and real-world benchmarks demonstrate EFormer's strong performance. Compared to node-based approaches, edge-based methods exhibit greater flexibility and applicability to real-world scenarios. Looking ahead, we plan to investigate lightweight architectural designs for EFormer to improve its scalability across a broader range of problem sizes. Another promising direction is to develop a unified learning-based framework that can operate effectively on both edge and node, where both are available as inputs.

4.1 Ablation Study

We conduct two sets of ablation studies to clarify essential design choices in our method. Specifically, we focus on: (1) the selection of the hyperparameter K = 20 for the k-nn graph sparsification, and (2) the necessity of using three encoders.

K value selection. In the classic knn-based sparsification approach, the hyperparameter K determines how many edges are retained for each node (K ×N, where N is the TSP size). We compare various K values (10, 20, 30, 40, and 50) on TSP50 and CVRP50; the results are shown in Table 2. For TSP50, the optimality gaps for K = 10, 20, and 30 are similar, with K = 20 performing slightly better. For CVRP50, K = 20 produces the highest solution quality. Overall, K = 20 appears to capture nearly all the best solutions for TSP50 and CVRP50, so we set K = 20 in all subsequent experiments.

The necessity of three encoders. Table 2 shows the ablation results for EFormer and four variants. The first variant removes the precoder, retaining only the node encoder and graph encoder (denoted by w.o. precoder in the table). Without precoder, the model cannot re-encode the same problem instance multiple times; hence, no additional instance augmentation is performed. The second variant removes the node encoder, keeping only the precoder and graph encoder (denoted by w.o. node encoder). The third variant removes the graph encoder, retaining the precoder and node encoder (denoted by w.o. graph encoder). The fourth variant removes the GCN module from the graph encoder but retains the precoder, node encoder, and MLP module of graph encoder (denoted by w.o. gcn). Comparing the third and fourth variants highlights the effectiveness of our parallel dual-encoder structure. As shown in Table 2, EFormer outperforms all variants, indicating that each component contributes positively to the model.

4.2 Generalization

We assess the generality of our proposed EFormer from three perspectives: 1) real-world TSPLIB and CVRPLIB benchmarks, 2) larger-scale instances, and 3) different distributions.

Generalization to TSPLIB and CVRPLIB. Table 3 summarizes the results on real-world TSPLIB [Reinelt, 1991] and CVRPLIB [Uchoa et al., 2017] instances of various sizes and distributions. EFormer performs best on instances with up to 100 nodes and ranks second for 101-300 nodes, demonstrating excellent generalization on both TSPLIB and CVRPLIB. It also outperforms GCN-BS and MatNet on all instances.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant 62372081, the Young Elite Scientists Sponsorship Program by CAST under Grant 2022QNRC001, the Liaoning Provincial Natural Science Foundation Program under Grant 2024010785-JH3/107, the Dalian Science and Technology Innovation Fund under Grant 2024JJ12GX020, the Dalian Major Projects of Basic Research under Grant 2023JJ11CG002 and the 111 Project under Grant D23006. This research is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG3-RP-2022-031).