RouteFinder: Towards Foundation Models for Vehicle Routing Problems

## Abstract

Abstract This paper introduces RouteFinder , a comprehensive foundation model framework to tackle different Vehicle Routing Problem (VRP) variants. Our core idea is that a foundation model for VRPs should be able to represent variants by treating each as a subset of a generalized problem equipped with different attributes. We propose a unified VRP environment capable of efficiently handling any attribute combination. The RouteFinder model leverages a modern transformer-based encoder and global attribute embeddings to improve task representation. Additionally, we introduce two reinforcement learning techniques to enhance multi-task performance: mixed batch training, which enables training on different variants at once, and multi-variant reward normalization to balance different reward scales. Finally, we propose efficient adapter layers that enable fine-tuning for new variants with unseen attributes. Extensive experiments on 24 VRP variants show RouteFinder achieves competitive results. Our code is openly available at https://github.com/ai4co/routefinder .

## 1 Introduction

Vehicle Routing Problems (VRPs) are an important class of Combinatorial Optimization (CO) problems that have received much attention in Operations Research (OR) and Computer Science.
Since the VRP is an NP-hard problem, finding an optimal solution by exhaustively exploring the solution space is often computationally expensive and impractical for large instances.
Instead, heuristic methods that quickly generate good (but possibly suboptimal) solutions are commonly used. The OR community has developed many heuristics over the year, including the well-known Lin-Kernighan-Helsgaun (LKH) heuristic (Helsgaun, ), Fast Iterated Local Optimization (FILO) (Accorsi & Vigo, ; ) and Hybrid Genetic Search (HGS) (Vidal, ; Wouda et al., ).
While these algorithms are state-of-the-art on a range of VRP variants, they often require careful consideration of the problem specifics, algorithm parameters, and computational resources to achieve the best results, and thus require considerable expert knowledge to be applied in practice.

Recently, Neural Combinatorial Optimization (NCO) approaches have been developed to solve CO problems. By leveraging deep learning, these approaches seek to learn and generalize from data, potentially providing more flexible and scalable solutions (Kool et al., ; Hottung & Tierney, ; Kwon et al., ; Kim et al., ; Berto et al., ; Hottung et al., ).
In this way, optimization problems essentially become data science problems, making them more accessible.

Similar to how the developments in natural language processing have resulted in Large Language Models (LLMs), research efforts in solving CO problems through machine learning are also trending toward foundation models (Liu et al., ; Ye et al., ; Liu et al., ; Zhou et al., ). However, despite the recent progress made in learning VRP variants, there is a lack of a unified approach that can effectively tackle a wide range of tasks without needing high-quality labeled datasets, which is crucial for real-world impact. Such an approach would additionally provide a platform for effectively finetuning unseen variants (Lin et al., ). A foundation model for VRPs would have important implications in terms of cost savings for companies and organizations as it can be easily adapted to new business requirements (constraints) outside of the training distribution.

In this work, we introduce RouteFinder, a comprehensive foundation model framework for solving VRPs. We summarize our key contributions, including problem formulation, modeling, training, and finetuning, as follows:

- •
We introduce a general framework to solve different VRP variants via a unified VRP environment that can handle any number of attributes.
- •
We propose a modern Transformer-based model architecture and introduce Global Attribute Embeddings to enable the model to better understand and differentiate VRPs.
- •
We introduce two novel reinforcement learning techniques, Mixed Batch Training and Multi-Variant Reward Normalization, to ensure stable and effective training across multiple VRP variants.
- •
We present Efficient Adapter Layers, a lightweight yet powerful mechanism for finetuning pre-trained RouteFinder models to tackle new variants with unseen attributes.

We evaluate RouteFinder through extensive experiments on 24 VRP variants, assessing the impact of each novel component on performance. RouteFinder significantly outperforms recent multi-task learning models by reducing optimality gaps by more than $10\%$ across all variants.

## 2 Related Works

##### Neural combinatorial optimization for VRPs

NCO has emerged as a pivotal solution approach for VRPs and other CO problems, leveraging advancements in machine learning and neural network architectures (Bengio et al., ; Peng et al., ; Mazyavkina et al., ; Bogyrbayeva et al., ).
The seminal work of Vinyals et al. () using pointer networks paved the way to apply these techniques to CO problems, where they now routinely find near-optimal solutions for VRPs through further developments by Bello et al. () and Nazari et al. ().
Subsequent innovations, including the transformer-based encoder with self-attention of Kool et al. (), POMO (Kwon et al., ) and Sym-NCO (Kim et al., ), have significantly enhanced solution generation and improvement strategies for VRPs.
These advancements have been complemented by novel training algorithms, including learning with (partial) problem re-encoding at each step (Bdeir et al., ; Drakulic et al., ; Luo et al., ; ) and population-based approaches (Grinsztajn et al., ; Hottung et al., ; Chalumeau et al., ).

Despite this progress, challenges remain in the form of requiring manual tuning for inductive bias, the need for problem-specific models, and lack of generalization, which impact deployment and generalizability (Liu et al., ; Thyssens et al., ).
The field has also explored non-autoregressive solution construction methods that allow for better generalization, such as predicting promising edges (Joshi et al., ; Fu et al., ; Kool et al., ; Sun & Yang, ), improvement methods iteratively refining solutions through local adjustments or sequential rewriting (Hottung & Tierney, ; Ma et al., ; ; ), and test-time adaptation methods (Hottung et al., ; Choo et al., ) which allow for solution improvement given larger time budgets.
Recent works additionally explore alternative ways of solving VRPs, such as learning heuristics for Ant Colony Optimization (Ye et al., ; Kim et al., ) and divide-and-conquer methods (Kim et al., ; Li et al., ; Hou et al., ; Ye et al., ; Chen et al., ; Zheng et al., ).

##### Multi-task learning for VRPs

In this work, we develop a unified VRP solver that can be generalized to any number of VRP variants. This issue of generalization has garnered much attention recently. Wang & Yu () introduces a multi-armed bandit method that solves several VRP variants with limited training budgets. Lin et al. () proposes training a backbone model (i.e., deep layers) for VRPs that can then be adapted via low-dimensional layers such as linear projections to fine-tune different problems efficiently. Drakulic et al. () propose a multi-task model for CO problems trained via supervised learning, akin to LLMs. Jiang et al. () introduce UNCO, a method to transfer different problems to the embedding space via textual description through an LLM; however, UNCO still falls short in terms of performance compared to state-of-the-art NCO methods. Most related to this work are the works of Liu et al. () and Zhou et al. (), which use attribute composition (Ruis et al., ) to achieve (zero-shot) generalization on several VRP variants. Liu et al. () builds on the Reinforcement-Learning-based POMO (Kwon et al., ), on top of which Zhou et al. () employ a mixture-of-experts model to improve generalization.

## 3 Preliminaries

### 3.1 Vehicle Routing Problems

We first formulate the Capacitated VRP (CVRP), the base of several more complex VRPs. The CVRP is formulated on a graph $G=(N,E)$, where $N=\{0,1,\ldots,n\}$ represents the set of nodes, with 0 0 denoting the depot and $N_{c}=\{1,\ldots,n\}$ representing the customers. Each customer $i\in N_{c}$ has a demand $q_{i}$. The edges $E$ connect pairs of nodes, and each edge $(i,j)\in E$ has a travel cost $c_{ij}$ (e.g., distance or travel duration). A fleet of vehicles, each with a capacity $Q$, departs from the depot to serve each of the customers exactly once and returns, with the objective of minimizing the total travel cost.

Figure: Figure 3.1: Different VRP attributes. Open routes (O) and duration limits (L) are global attributes, whereas time windows (TW), capacitated vehicles for linehaul demands (C), backhaul demands (B) and mixed (M) backhaul demands are node attributes. Attributes may be combined in different ways to define VRP variants.
Refer to caption: x1.png

Following Vidal et al. (), we consider a collection of VRP variants that each consist of one or more attributes, resulting in a rich set of routing problems with practical relevance.
Each of these variants offers a unique generalization task for RouteFinder.
Table A.1 in the provides a list of all 24 VRP variants we consider in this paper.
We divide the attributes we consider into node attributes, global attributes, and edge attributes.
Node attributes are specific to the depot and customer nodes and local to specific nodes, such as (linehaul) demands, backhaul demands, and time windows.
Global attributes represent structural aspects of the problem as a whole, e.g., open vs. closed routes, distance limits, and the type of backhaul.
In this work, the relevant edge attribute we consider is the cost of each edge, representing a distance or travel duration depending on the problem definition.
Fig. 3.1 describes node and global attributes modeled in this work.

#### Node attributes

##### Demand and Vehicle Capacity (C)

[$q\in[0,Q]$]: Every customer $i\in N_{c}$ has a linehaul demand $q_{i}$ that needs to be served using vehicles with a homogeneous fixed capacity $Q>0$. The total customer demand in the vehicle must not exceed its capacity at any point of the route.

##### Time Windows (TW)

[$e,s,l\in[0,T]^{3}$]:
Every customer $i\in N_{c}$ has a time window $[e_{i},l_{i}]$ during which service must begin.
Service takes $s_{i}$ time.
The depot has a time window $[e_{0},l_{0}]=[0,T]$, and a service duration of $s_{0}=0$.
Vehicles must reach node $i$ before the end of its time window at $l_{i}$, but any early arrivals must wait at the node location until time $e_{i}$ before service may start.

##### Backhauls (B)

[$p\in[0,Q]$]:
Backhauls generalize demand to also account for return shipments. Customers are either linehaul or backhaul customers.
Linehaul customers require delivery of a demand $q_{i}$ that needs to be transported from the depot to customer $i$ (as in the CVRP), whereas backhaul customers need a pickup of an amount $p_{i}$ that is transported from the client back to the depot.
It is possible for vehicles to serve a combination of linehaul and backhaul customers in a single route, but then any linehaul customers must precede the backhaul customers in the route.
An application with returnable bottles is presented in Ropke & Pisinger (): full bottles need to be delivered from the depot to customers, while empty bottles are returned to the depot via backhaul. We remark that our definition of backhauls follows the generally accepted definition in the OR community, originally due to Goetschalckx & Jacobs-Blecha ().
This definition differs from the routing problems with backhaul considered in several recent papers in the machine learning (e.g., Liu et al. (); Zhou et al. ()), who define backhaul customers as having a negative demand of the same commodity used for linehaul, and do not consider the precedence constraint that all linehaul must be completed before backhaul may start on the route.
The problem setting with a single commodity is not commonly studied in the OR literature since it implies pickups may be used for deliveries at later customers, while the relaxation of the precedence constraint is more properly referred to as a mixed backhaul problem (Koç & Laporte, ).

#### Global attributes

##### Open Routes (O)

[$o\in\{0,1\}$]: Vehicles are not required to return to the depot after serving all customers.
Open routes can be found in applications with third-party drivers, who are often only compensated until they have completed their last delivery (Li et al., ).

##### Duration Limits (L)

[$l\in[0,L]$]: Imposes a limit on the total travel duration (or length) of each route, balancing the workload across vehicles. This limit is uniformly applied to all routes.

##### Mixed (M) Backhauls

[$m\in\{0,1\}$]:
Relaxes the strict precedence constraint of linehaul customers preceeding backhaul customers: with mixed backhauls, linehaul and backhaul customers may be mixed along a route in any configuration. The vehicle’s capacity must, of course, still be respected at any point along the route. Since both the current carried linehaul and backhaul demand need to be tracked for each vehicle, this variant requires careful planning.

### 3.2 Learning Neural Solvers for VRPs

##### Solving VRPs using Autoregressive Sequence Generation

Autoregressive (AR) methods address CO problems by constructing solutions sequentially. The process begins with encoding the problem instance $\bm{x}$ (e.g., node and global attributes) using a trainable encoder $f_{\theta}$ that maps $\bm{x}$ to an embedding $\bm{h}=f_{\theta}(\bm{x})$. The solution $\bm{a}$ is then decoded based on $\bm{h}$ through a series of actions, where each action determines the next step in the solution based on the current partial sequence. This is achieved using a decoder $g_{\theta}$. The encoding and decoding process can be formalized as follows:

$$ $\displaystyle a_{t}$ $\displaystyle\sim g_{\theta}(a_{t}|a_{t-1},...,a_{0},\bm{h}),$ (1a) $\displaystyle\pi_{\theta}(\bm{a}|\bm{x})$ $\displaystyle\triangleq\prod_{t=1}^{T-1}g_{\theta}(a_{t}|a_{t-1},...,a_{0},\bm {h}),$ (1b) $$

where $\bm{a}=(a_{1},...,a_{T})$ represents a feasible solution to the CO problem, $T$ denotes the steps in solution construction, and $\pi_{\theta}$ is the stochastic solver mapping problem instance $\bm{x}$ to a solution $\bm{a}$.

##### Training VRP Solvers via Reinforcement Learning

The solver $\pi_{\theta}$ can be trained using either supervised learning (SL) or reinforcement learning (RL). This paper focuses on RL due to its ability to train solvers independent of optimal solutions. Under the RL framework, the training objective for neural combinatorial optimization solvers is defined as:

$$ $\theta^{*}=\underset{\theta}{\text{argmax}}\left[\mathbb{E}_{\bm{x}\sim P(\bm{ x})}\left[\mathbb{E}_{a\sim\pi_{\theta}(\bm{a}|\bm{x})}[R(\bm{a},\bm{x})] \right]\right],$ (2) $$

where $P(\bm{x})$ is the distribution of problem instances, and $R(\bm{a},\bm{x})$ represents the reward (i.e., the negative cost), associated with the solution $\bm{a}$ for the given $\bm{x}$. The above training problem can be tackled using various RL algorithms such as REINFORCE and its modern variants (Sutton et al., ; Kool et al., ; Kwon et al., ).

## 4 The RouteFinder Recipe

Figure: Figure 4.1: Overview of RouteFinder.
Refer to caption: x2.png

RouteFinder leverages attribute composition from Liu et al. (); Zhou et al. () to solve multiple VRP variants. Attribute composition treats different variants of the VRP as combinations of fundamental attributes from Section 3.1, using a common network to learn their representations. We go one step further than previous works and consider different combinations of attributes within training batches (see Section 4.3.1). Fig. 4.1 provides an overview of RouteFinder’s architecture.

### 4.1 Unified VRP Environment

In previous works proposing multi-task learning across VRP variants, like MTPOMO (Liu et al., ) and MVMoE (Zhou et al., ), the training scheme samples an instance variant (CVRP, VRPTW, etc.) out of the set of available variants during training. Every instance within that batch, therefore, is of the same problem category. This can, however, bias the optimization at each gradient step toward a specific task, potentially hindering stable and effective training for a foundation model. We thus propose to learn across problems throughout training and include problem instances of various attributes within each training batch.

We define an environment capable of modeling all of the previously discussed VRP attributes (see Section 3.1) simultaneously, essentially building an OVRPBLTW environment: an open route vehicle routing problem with linehauls, backhauls, distance limit, and time windows.
The environment supports subsets of the OVRPBLTW defining other VRP variants, i.e., some attributes can be “turned off.”
For example, if an instance does not have time window constraints, the time windows attribute of each customer is set to $[0,\infty]$, rendering them irrelevant during solution construction. In this way, all attributes characterizing a VRP variant can simply be turned “on” and “off”, allowing us to model up to 16 different problem types with one single environment. This approach can be easily extended – for instance, by including different location sampling mechanisms and new constraints – allowing for even more future problem variants to be modeled with the same environment.

### 4.2 Model

#### 4.2.1 Transformer-based Architecture

Figure: Figure 4.2: Attention model structure v.s. RouteFinder transformer structure.
Refer to caption: x3.png

The RouteFinder transformer encoder architecture, shown in Fig. 4.2, introduces key enhancements to the standard Attention Model (AM) from Kool et al. (), which is the de-facto standard in recent works (Liu et al., ; Zhou et al., ).
Firstly, the RouteFinder transformer encoder employs RMS (Root Mean Square) normalization (Zhang & Sennrich, ), improving stability and training speed by reducing the impact of outliers. Secondly, we transition from post-norm to pre-norm in transformer layers, applying normalization before the residual connections, which enhances gradient flow and promotes faster convergence (Jiang et al., ). Thirdly, RouteFinder uses a Feed Forward SwiGLU, (Shazeer, ), an extension of the Gated Linear Unit (GLU) (Dauphin et al., ), instead of the AM’s ReLU-based feed-forward network, enhancing the model’s capacity to capture complex relationships in the data. Finally, we employ FlashAttention (Dao et al., ; Dao, ) in the Multi-Head Attention layer of all models to enhance overall performance. These improvements build on recent advances in foundation models in areas such as language modeling and biology (Dubey et al., ; Nguyen et al., ), aiming to create a robust foundation model for VRPs building on modern architectures.
Further details on modeling are provided in Appendix B.

#### 4.2.2 Global Attribute Embeddings

Global attributes as outlined in Section 3.1 are essential for modeling VRPs; for instance, given an open (O) attribute, the solver may find optimal routes that do not necessarily loop back to the starting depot. Previous multi-task learning models for VRPs (Liu et al., ; Zhou et al., ) project such features on the shallow decoder as dynamic features. However, such a design can be suboptimal since the deep transformer layers carry out most of the learning and, importantly, can enable effective attribute mixing, which is essential in understanding a (new) problem. We thus design Global Attribute Embeddings for effective problem representation, which incorporate problem variants and help the deep layers understand which problem is being faced. Global attributes $\phi_{0},\dots,\phi_{k}$ are projected via a projection layer:

$$ $h_{g}^{0}=f_{\theta}([\phi_{0},\dots,\phi_{k}]),\quad f_{\theta}:\mathbb{R}^{k }\rightarrow\mathbb{R}^{d}$ (3) $$

into $d$-dimensional space. Given our unified VRP representation, some attributes, such as the duration limit $l$ for unconstrained VRPs, might be $\infty$. Such attributes are padded as 0 0s before being processed by the deep transformer layers.

### 4.3 Training

#### 4.3.1 Variant Sampling for Mixed Batch Training

Optimizing a neural solver for tackling multiple tasks requires careful consideration of its training scheme, which needs to be robust against different variant distributions. We introduce a flexible approach which we coin Mixed Batch Training (MBT) to efficiently reuse a single dataset to generate multiple problem variants, optimizing data storage and processing capabilities. We observe that the OVRPBLTW problem variant is the most general problem variant we study in this paper, and can be used to generate any of the other variants by selectively removing the (O), (B), (L), or (TW) attributes (note that for zero-shot generalization and few-shot learning, we will additionally sample with the mixed (M) backhaul attribute in Section 5.3 and obtain the OVRPMBLTW).
Let $\bm{X}$ be a dataset of OVRPBLTW problem instances, and let $V$ be the set of attributes, where each attribute $\nu\in V$ is associated with a sampling probability $\mathbf{p}_{\nu}$.
For each instance $x\in\bm{X}$, we can write $x((\mathbf{1}_{1})_{\nu\in V})$ to conveniently express using indicator functions $\mathbf{1}_{1}$ for each attribute $\nu\in V$ that the instance $x$ is equipped with $\nu$.
The sampling procedure of MBT can be defined as follows:

$$ $\bm{X}_{\text{subsampled}}=\{x((\mathbf{1}_{\text{rand}(0,1)<\mathbf{p}_{\nu}} )_{\nu\in V})\}_{x\in\bm{X}},$ $$

where $\text{rand}(0,1)$ draws an independent sample from $U[0,1]$.
For example, to sample uniformly across all problem variants, we could set $\mathbf{p}_{\nu}=\frac{1}{2}$ for each $\nu\in V$.
MBT is flexible and scalable, capable of adapting to any problem where different constraints or features might be selectively activated or deactivated. Fig. 4.3 provides an overview of MBT.

Figure: Figure 4.3: [Left] Training without MBT may lead to instability since at each step the optimization is biased toward a single task. [Right] Training RouteFinder with MBT allows for more stable training.
Refer to caption: x4.png

#### 4.3.2 Multi-task Reward Normalization

As explained in Section 3.2, the objective for RL-based NCO solvers is to maximize the expected reward. However, in multi-task learning settings, different problems can yield rewards on different scales.
To counteract potential biases during learning, we propose to apply reward normalization per problem variant.
We implement four normalization techniques to calculate the normalized rewards $r_{\text{norm},t}^{(k)}$ for all problem variants $k\in[1,...,K]$ at training steps $t\geq 1$:
1) subtraction of the simple mean reward, 2) division through the simple mean reward, 3) subtraction of the exponentially smoothed mean, and 4) division through the exponentially smoothed mean.
We calculate the average reward $\hat{r}_{t}^{(k)}$ up to training step $t$, using the average reward $\bar{r}_{t}^{(k)}$ at step $t$.
The simple mean reward at step $t$ is calculated as:

$$ $\hat{r}_{t}^{(k)}=\left((t-1)\cdot\hat{r}_{t-1}^{(k)}+\bar{r}_{t}^{(k)}\right) /t,\quad t\geq 1.$ (4) $$

For the exponential moving average we set $\hat{r}_{1}^{(k)}=\bar{r}_{1}^{(k)}$ and calculate the values for $t>1$ based on Hunter () using a smoothing factor $\alpha$:

$$ $\hat{r}_{t}^{(k)}=(1-\alpha)\cdot\hat{r}_{t-1}^{(k)}+\alpha\cdot\bar{r}_{t}^{( k)},\quad 0<\alpha<1,\quad t>1.$ (5) $$

The normalized rewards 1)—4) can be calculated from the original rewards $r_{t}^{(k)}$ according to $r_{\text{norm},t}^{(k)}=r_{t}^{(k)}-\hat{r}_{t}^{(k)}$ and $r_{\text{norm},t}^{(k)}=r_{t}^{(k)}/|\hat{r}_{t}^{(k)}|$ for subtraction and division variants, respectively.
Let $\xi(\bm{a},\bm{x})=r_{\text{norm}}^{(k)}(\bm{a},\bm{x})$ be a function calculating the normalized reward for instance $\bm{x}$ that additionally maps instance $\bm{x}$ to variant $k$. The multi-task reward-normalized gradient becomes:

$$ $\nabla_{\theta}J(\theta)\approx\frac{1}{N}\sum_{i=1}^{N}\left(\xi(\bm{a}^{i}, \bm{x})-\frac{1}{N}\sum_{j=1}^{N}\xi(\bm{a}^{j},\bm{x})\right)\nabla_{\theta} \log p_{\theta}(\bm{a}^{i}|\bm{x}),$ (6) $$

i.e., we employ the REINFORCE loss function with the POMO (Kwon et al., ) shared mean baseline (right side of the parenthesis) to improve convergence, where both the reward and the shared baseline are normalized by $\xi$ to calculate the policy gradients advantage.

### 4.4 Efficient Adapter Layers: Finetuning to Unseen Attributes

Previous multi-task learning works (Liu et al., ; Zhou et al., ) train in an environment of single-attribute VRP variants and, using compositionality (Ruis et al., ), achieve promising results on zero-shot generalization to VRP variants combining these individual attributes. In RouteFinder, we go a step further and investigate how to efficiently generalize our pre-trained foundation model to variants with unseen attributes outside of the training set. Lin et al. () propose pretraining a backbone model, on top of which specific Adapter Layers (AL) can be applied for more efficient finetuning to new problems – with the rationale being that the backbone (i.e., the encoder layers) may capture transferable knowledge. However, doing so excludes previous information accumulated in the projection layers from the raw attribute features to the hidden space, complicating optimization. For instance, if the first two out of $k$ dimensions encoded the Euclidean locations of nodes as $(x,y)$, re-initializing a new adapter layer from scratch will eliminate such transferable knowledge. Therefore, we propose Efficient Adapter Layers (EAL), an effective approach to learning few-shots for VRP foundation models.

Consider a linear projection layer $\mathbf{W}\in\mathbb{R}^{k\times d}$ as the original weight matrix for the projection from the raw attribute to latent space, where $k$ is the number of attributes and $d$ is the hidden dimension.
In this work, for simplicity, we consider unbiased linear projections to the latent space.
This can be readily extended to general affine projections using a bias term.
To accommodate $l$ new attributes, EAL augments $\mathbf{W}$ with zeros. The new matrix $\mathbf{W}^{\prime}\in\mathbb{R}^{(k+l)\times d}$ can be written as:

$$ ${\mathbf{W}^{\prime\top}=\begin{bmatrix}\mathbf{W}\\ \mathbf{0}\end{bmatrix}^{\top}}=\leavevmode\hbox to470.02pt{\vbox to73.01pt{ \pgfpicture\makeatletter\hbox{\hskip 242.89595pt\lower-28.5pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont \pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope } \pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } {}{}{}{{}}{{}}{{}}{{}}{ {}}{{}}{{}}\hbox{\hbox{\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{ \offinterlineskip{}{}{{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}} {{}}{{}}{{}}{{}}}{{{}}}{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-223.12508pt}{-23.0pt}\pgfsys@invoke{ }\hbox{\vbox{\halign{ \pgf@matrix@init@row\pgf@matrix@step@column{\pgf@matrix@startcell# \pgf@matrix@endcell}&#\pgf@matrix@padding&&\pgf@matrix@step@column{ \pgf@matrix@startcell#\pgf@matrix@endcell}&#\pgf@matrix@padding\cr\hfil\hskip 6 1.4601pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{\hbox{{ \pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-61.4601pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\tikzmarkin[kwad= stylecyan]{Bis}w_{00}}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip 61.4601pt\hfil& \hfil\hskip 18.0pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{\hbox{{ \pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-3.75pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\hbox{${\cdots}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip 10.0pt\hfil& \hfil\hskip 18.0pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{\hbox{{ \pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-6.65996pt}{-1.18056pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor }{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${w_{0k}}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip 10.0pt\hfil& \hfil\hskip 74.25389pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{ \hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-66.25389pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\tikzmarkin[kwad= stylegreen]{Prime}0}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip 66.25389pt\hfil& \hfil\hskip 31.02467pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{ \hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-23.02467pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\tikzmarkend{Prime} \cdots}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}}}&\hskip 23.02467pt\hfil& \hfil\hskip 29.77469pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{ \hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-21.77469pt}{-3.41666pt}\pgfsys@invoke{ }\hbox{{\definecolor{ pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\tikzmarkend{Prime}0}$ } }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 21.77469pt\hfil\cr \vskip 8.0pt\cr\hfil\hskip 10.0pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{} }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-3.75pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\hbox{${\vdots}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 10.0pt\hfil&\hfil \hskip 18.0pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{\hbox{{ \pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-3.75pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\hbox{${\ddots}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 10.0pt\hfil&\hfil \hskip 18.0pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{\hbox{{ \pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-3.75pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\hbox{${\vdots}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 10.0pt\hfil&\hfil \hskip 31.02467pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{\hbox{{ \pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-23.02467pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\tikzmarkend{Prime} \vdots}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 23.02467pt\hfil& \hfil\hskip 31.02467pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{ \hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-23.02467pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\tikzmarkend{Prime} \ddots}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 23.02467pt\hfil& \hfil\hskip 31.02467pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{ \hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-23.02467pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\tikzmarkend{Prime} \vdots}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 23.02467pt\hfil\cr \vskip 8.0pt\cr\hfil\hskip 10.0pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{} }\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-6.57149pt}{-1.18056pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor }{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${w_{d0}}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 10.0pt\hfil&\hfil \hskip 18.0pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{\hbox{{ \pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-3.75pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb}{ 0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill {0}{0}{0}\pgfsys@invoke{ }\hbox{${\cdots}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 10.0pt\hfil&\hfil \hskip 27.36174pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{\hbox{{ \pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-19.36174pt}{-2.44444pt}\pgfsys@invoke{ }\hbox{{\definecolor{ pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${w_{dk}\tikzmarkend{Bis }}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 19.36174pt\hfil& \hfil\hskip 29.77469pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{ \hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-21.77469pt}{-3.41666pt}\pgfsys@invoke{ }\hbox{{\definecolor{ pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\tikzmarkend{Prime}0}$ } }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 21.77469pt\hfil& \hfil\hskip 31.02467pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{ \hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-23.02467pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${\tikzmarkend{Prime} \cdots}$} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 23.02467pt\hfil& \hfil\hskip 29.77469pt\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}}\hbox{ \hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-21.77469pt}{-3.41666pt}\pgfsys@invoke{ }\hbox{{\definecolor{ pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{${0\tikzmarkend{Prime}}$ } }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}&\hskip 21.77469pt\hfil\cr }}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}{{{{}}}{{}}{{}}{{}}{{} }{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}{{}}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope \pgfsys@invoke{ }{{}{}{{ }}{ } {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-226.18065pt}{-26.0pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor} {rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{\nullfont{{{ {}{}{}}}{{ {}{}{}}}}}$\left[\vbox{\hrule height=28.5pt,depth=28.5pt,width=0.0pt}\right.$} } }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}\hbox{{\pgfsys@beginscope \pgfsys@invoke{ }{{}{}{{}}{} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{220.62508pt}{-26.0pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{{\nullfont{{{ {}{}{}}}{{ {}{}{}}}}}$\left.\vbox{\hrule height=28.5pt,depth=28.5pt,width=0.0pt}\right]$} } }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{ {}}{}{ {}{}{}}{}}{}{{}}{}{{{}}{}{ {}{}{}}{}} {}{}{}{}{{{}{}}}{{}} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}}{{{{}{}{{}} }}{{}} {} {}{}{} { {{}} {} {}{}{} {}{}{} } { {{}} {} {}{}{} } }{{}{}}{{}{}}{{{{}{}{{}} }}{{}}} \pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{ }{}\pgfsys@moveto{-223.12508pt}{28.5pt}\pgfsys@moveto{-223.12508pt}{28.5pt} \pgfsys@curveto{-222.75009pt}{29.25pt}{-221.87508pt}{29.75pt}{-220.62508pt}{29 .75pt}\pgfsys@lineto{-131.48412pt}{29.75pt}\pgfsys@curveto{-130.23412pt}{29.75 pt}{-129.3591pt}{30.24998pt}{-128.98412pt}{31.0pt}\pgfsys@curveto{-128.60913pt }{30.24998pt}{-127.73412pt}{29.75pt}{-126.48412pt}{29.75pt}\pgfsys@lineto{-37. 34314pt}{29.75pt}\pgfsys@curveto{-36.09314pt}{29.75pt}{-35.21812pt}{29.25pt}{- 34.84314pt}{28.5pt}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{ \pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-131.74454pt}{34.233pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor }{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$k$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope {{ {}}{}{ {}{}{}}{}}{}{{}}{}{{{}}{}{ {}{}{}}{}} {}{}{}{}{{{}{}}}{{}} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}}{{{{}{}{{}} }}{{}} {} {}{}{} { {{}} {} {}{}{} {}{}{} } { {{}} {} {}{}{} } }{{}{}}{{}{}}{{{{}{}{{}} }}{{}}} \pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{ }{}\pgfsys@moveto{-17.4814pt}{28.5pt}\pgfsys@moveto{-17.4814pt}{28.5pt} \pgfsys@curveto{-17.10641pt}{29.25pt}{-16.2314pt}{29.75pt}{-14.9814pt}{29.75pt }\pgfsys@lineto{99.69684pt}{29.75pt}\pgfsys@curveto{100.94684pt}{29.75pt}{101. 82185pt}{30.24998pt}{102.19684pt}{31.0pt}\pgfsys@curveto{102.57182pt}{30.24998 pt}{103.44684pt}{29.75pt}{104.69684pt}{29.75pt}\pgfsys@lineto{219.37509pt}{29. 75pt}\pgfsys@curveto{220.62509pt}{29.75pt}{221.5001pt}{29.25pt}{221.87509pt}{2 8.5pt}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{\pgfsys@beginscope \pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{100.60655pt}{34.233pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor} {rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$l$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope {{ {}{}{}}{}{{}}{}}{}{{}}{}{{ {}{}{}}{}{ {}}{}} {}{}{}{}{{{}{}}}{{}} {}{{}{}}{}{}{}{{}}{{}}{{}{}}{{}{}}{{{{}{}{{}} }}{{}} {} {}{}{} { {{}} {} {}{}{} {}{}{} } { {{}} {} {}{}{} } }{{}{}}{{}{}}{{{{}{}{{}} }}{{}}} \pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{ }{}\pgfsys@moveto{-228.62508pt}{-28.0pt}\pgfsys@moveto{-228.62508pt}{-28.0pt} \pgfsys@curveto{-229.37508pt}{-27.62502pt}{-229.87508pt}{-26.75pt}{-229.87508 pt}{-25.5pt}\pgfsys@lineto{-229.87508pt}{-7.5pt}\pgfsys@curveto{-229.87508pt}{ -6.25pt}{-230.37506pt}{-5.37498pt}{-231.12508pt}{-5.0pt}\pgfsys@curveto{-230.3 7506pt}{-4.62502pt}{-229.87508pt}{-3.75pt}{-229.87508pt}{-2.5pt}\pgfsys@lineto {-229.87508pt}{15.5pt}\pgfsys@curveto{-229.87508pt}{16.75pt}{-229.37508pt}{17. 62502pt}{-228.62508pt}{18.0pt}\pgfsys@stroke\pgfsys@invoke{ }\hbox{\hbox{{ \pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{{}{}}}{{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-239.56294pt}{-8.47221pt}\pgfsys@invoke{ }\hbox{{\definecolor{ pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$d$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}$ $$

where $\mathbf{0}\in\mathbb{R}^{l\times d}$ is a matrix of zeros. The augmented matrix $\mathbf{W}^{\prime}$ retains the original $k$ attributes and adds $l$ new attributes, which are initialized to zero. Doing so does not affect the model for seen attributes like AL does, as the new $l$ dimensions are "muted" until fine-tuning on new variants occurs, enabling new attributes to be included in any part of the model via EAL as shown in Fig. 4.1.

## 5 Experiments

In this section, we empirically demonstrate the state-of-the-art performance of RouteFinder in extensive experiments(^1^11We open-source the code at: [https://github.com/ai4co/routefinder](https://github.com/ai4co/routefinder)). We address the following research questions:

- (RQ1)
Does RouteFinder outperform state-of-the-art foundation models for routing problems on many different VRP variants?
- (RQ2)
How do the novel components of RouteFinder contribute to its performance?
- (RQ3)
Is the proposed EAL effective in RouteFinder finetuning to unseen VRP variants?

##### Hardware

All training runs are conducted on NVIDIA A100 GPUs and take between 9 to 48 hours per model. Evaluation runs are conducted on an AMD Ryzen Threadripper 3960X 24-core CPU with a single RTX 3090 GPU.

##### Baselines

Traditional solvers:
We use PyVRP (Wouda et al., ), an open-source, state-of-the-art heuristic VRP solver built on top of HGS-CVRP (Vidal, ).
PyVRP can solve all VRP variants considered in this study.
We also use Google’s OR-Tools (Perron & Furnon, ), an open-source exact and heuristic solver that relies on constraint programming and commonly used in the ML community for its versatility to solve a large number of VRP variants. We use OR-Tools’ guided local search procedure in this work.
Both baseline methods solve each instance on a single CPU core with a time limit of 10 and 20 seconds for instances with 50 and 100 nodes, respectively. We parallelize traditional solvers across 16 CPU cores as in Kool et al. (); Zhou et al. ().

Neural solvers:
We consider recent multi-task learning baselines for the VRP, including the recent MTPOMO (Liu et al., ), based on POMO (Kwon et al., ), and MVMoE (Zhou et al., ), which introduces mixture-of-experts (Fedus et al., ) to improve the model performance as baselines for multi-task learned models. RouteFinder variants, denoted as RF in the tables, are trained with all components proposed in the methodology section. We use Reward Normalization with division through the exponentially smoothed mean with $\alpha=0.25$. We consider three versions of RouteFinder: one version considering the (MT)POMO encoder (RF-POMO), one with the MVMoE model with four experts and hierarchical gating (RF-MoE), and one with our modern Transformer-based Encoder (RF-TE). Further details are available in Appendix B.

##### Training

We follow the setup in Kwon et al. () and the recent works on MTPOMO (Liu et al., ) and MVMoE (Zhou et al., ). Each model is trained for 300 epochs, each containing $100,000$ instances generated on the fly. We use the Adam optimizer (Kingma & Ba, ) with a learning rate of $3\times 10^{-4}$ and batch size of $256$. At epochs 270 and 295, the learning rate is multiplied by $0.1$.
Note that our setup differs from the one in Liu et al. () and Zhou et al. () in that we do not artificially restrict the variants with single attributes (such as only (B) or (TW)), but train on all available data – similarly to how LLMs are trained on all available data, which is readily available through our unified VRP environment (more details in Appendix A).

##### Evaluation

For all ML approaches, we roll out greedy solutions using multi-starts and $8\times$ symmetric dihedral augmentations of Kwon et al. (), resulting in $n\times 8$ solutions per instance.

**Table 5.1: Performance on 1000 test instances of trained VRPs. * represents the best-known solutions. RouteFinder (RF) models improve gaps up to $20\%$ compared to MVMoE.**
| Solver | $n=50$ | $n=100$ | Solver | $n=50$ | $n=100$ |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Obj. | Gap | Time | Obj. | Gap | Time | Obj. | Gap | Time | Obj. | Gap | Time |  |  |  |  |
| CVRP | HGS-PyVRP | 10.372 | * | 10.4m | 15.628 | * | 20.8m | VRPTW | HGS-PyVRP | 16.031 | * | 10.4m | 25.423 | * | 20.8m |
| OR-Tools | 10.572 | 1.907% | 10.4m | 16.280 | 4.178% | 20.8m | OR-Tools | 16.089 | 0.347% | 10.4m | 25.814 | 1.506% | 20.8m |  |  |
| MTPOMO | 10.518 | 1.411% | 2s | 15.934 | 1.988% | 7s | MTPOMO | 16.410 | 2.364% | 1s | 26.412 | 3.873% | 7s |  |  |
| MVMoE | 10.501 | 1.242% | 2s | 15.888 | 1.694% | 9s | MVMoE | 16.404 | 2.329% | 2s | 26.389 | 3.788% | 9s |  |  |
| RF-POMO | 10.508 | 1.314% | 2s | 15.908 | 1.826% | 7s | RF-POMO | 16.367 | 2.094% | 1s | 26.336 | 3.575% | 7s |  |  |
| RF-MoE | 10.499 | 1.226% | 2s | 15.876 | 1.622% | 9s | RF-MoE | 16.389 | 2.234% | 2s | 26.322 | 3.519% | 9s |  |  |
| RF-TE | 10.504 | 1.274% | 2s | 15.857 | 1.505% | 7s | RF-TE | 16.364 | 2.077% | 1s | 26.235 | 3.178% | 7s |  |  |
| OVRP | HGS-PyVRP | 6.507 | * | 10.4m | 9.725 | * | 20.8m | VRPL | HGS-PyVRP | 10.587 | * | 10.4m | 15.766 | * | 20.8m |
| OR-Tools | 6.553 | 0.686% | 10.4m | 9.995 | 2.732% | 20.8m | OR-Tools | 10.570 | 2.343% | 10.4m | 16.466 | 5.302% | 20.8m |  |  |
| MTPOMO | 6.718 | 3.209% | 1s | 10.210 | 4.965% | 6s | MTPOMO | 10.775 | 1.734% | 1s | 16.149 | 2.434% | 7s |  |  |
| MVMoE | 6.702 | 2.965% | 2s | 10.177 | 4.621% | 9s | MVMoE | 10.751 | 1.505% | 2s | 16.099 | 2.115% | 9s |  |  |
| RF-POMO | 6.698 | 2.904% | 1s | 10.180 | 4.659% | 6s | RF-POMO | 10.751 | 1.523% | 1s | 16.107 | 2.174% | 6s |  |  |
| RF-MoE | 6.697 | 2.886% | 2s | 10.139 | 4.229% | 9s | RF-MoE | 10.737 | 1.388% | 2s | 16.070 | 1.941% | 9s |  |  |
| RF-TE | 6.684 | 2.687% | 1s | 10.121 | 4.055% | 6s | RF-TE | 10.749 | 1.502% | 1s | 16.051 | 1.827% | 6s |  |  |
| VRPB | HGS-PyVRP | 9.687 | * | 10.4m | 14.377 | * | 20.8m | OVRPTW | HGS-PyVRP | 10.510 | * | 10.4m | 16.926 | * | 20.8m |
| OR-Tools | 9.802 | 1.159% | 10.4m | 14.933 | 3.853% | 20.8m | OR-Tools | 10.519 | 0.078% | 10.4m | 17.027 | 0.583% | 20.8m |  |  |
| MTPOMO | 10.033 | 3.564% | 1s | 15.082 | 4.922% | 6s | MTPOMO | 10.668 | 1.479% | 1s | 17.420 | 2.892% | 7s |  |  |
| MVMoE | 10.005 | 3.270% | 2s | 15.023 | 4.508% | 8s | MVMoE | 10.669 | 1.492% | 2s | 17.416 | 2.872% | 10s |  |  |
| RF-POMO | 9.996 | 3.174% | 1s | 15.016 | 4.468% | 6s | RF-POMO | 10.657 | 1.378% | 1s | 17.391 | 2.720% | 7s |  |  |
| RF-MoE | 9.980 | 3.015% | 2s | 14.973 | 4.164% | 8s | RF-MoE | 10.674 | 1.539% | 2s | 17.387 | 2.697% | 10s |  |  |
| RF-TE | 9.977 | 2.989% | 1s | 14.942 | 3.952% | 6s | RF-TE | 10.652 | 1.326% | 1s | 17.327 | 2.346% | 7s |  |  |
| VRPBL | HGS-PyVRP | 10.186 | * | 10.4m | 14.779 | * | 20.8m | VRPBLTW | HGS-PyVRP | 18.361 | * | 10.4m | 29.026 | * | 20.8m |
| OR-Tools | 10.331 | 1.390% | 10.4m | 15.426 | 4.338% | 20.8m | OR-Tools | 18.422 | 0.332% | 10.4m | 29.830 | 2.770% | 20.8m |  |  |
| MTPOMO | 10.672 | 4.697% | 1s | 15.712 | 6.251% | 7s | MTPOMO | 18.990 | 2.128% | 1s | 30.898 | 3.624% | 7s |  |  |
| MVMoE | 10.637 | 4.354% | 2s | 15.640 | 5.758% | 9s | MVMoE | 18.985 | 2.100% | 2s | 30.892 | 3.608% | 10s |  |  |
| RF-POMO | 10.593 | 3.942% | 1s | 15.628 | 5.695% | 6s | RF-POMO | 18.937 | 1.851% | 1s | 30.796 | 3.284% | 7s |  |  |
| RF-MoE | 10.575 | 3.765% | 2s | 15.541 | 5.121% | 9s | RF-MoE | 18.957 | 1.960% | 2s | 350.808 | 3.323% | 10s |  |  |
| RF-TE | 10.578 | 3.803% | 1s | 15.528 | 5.039% | 6s | RF-TE | 18.941 | 1.877% | 1s | 30.688 | 2.923% | 7s |  |  |
| VRPBTW | HGS-PyVRP | 18.292 | * | 10.4m | 29.467 | * | 20.8m | VRPLTW | HGS-PyVRP | 16.356 | * | 10.4m | 25.757 | * | 20.8m |
| OR-Tools | 18.366 | 0.383% | 10.4m | 29.945 | 1.597% | 20.8m | OR-Tools | 16.441 | 0.499% | 10.4m | 26.259 | 1.899% | 20.8m |  |  |
| MTPOMO | 18.639 | 1.878% | 1s | 30.437 | 3.285% | 7s | MTPOMO | 16.824 | 2.823% | 1s | 26.891 | 4.368% | 7s |  |  |
| MVMoE | 18.640 | 1.883% | 2s | 30.436 | 3.281% | 9s | MVMoE | 16.811 | 2.750% | 2s | 26.868 | 4.277% | 9s |  |  |
| RF-POMO | 18.601 | 1.670% | 1s | 30.341 | 2.961% | 7s | RF-POMO | 16.750 | 2.382% | 1s | 26.783 | 3.948% | 7s |  |  |
| RF-MoE | 18.616 | 1.757% | 2s | 30.341 | 2.954% | 9s | RF-MoE | 16.777 | 2.550% | 2s | 26.774 | 3.912% | 9s |  |  |
| RF-TE | 18.600 | 1.676% | 1s | 30.241 | 2.619% | 7s | RF-TE | 16.762 | 2.454% | 1s | 26.689 | 3.579% | 7s |  |  |
| OVRPB | HGS-PyVRP | 6.898 | * | 10.4m | 10.335 | * | 20.8m | OVRPBL | HGS-PyVRP | 6.899 | * | 10.4m | 10.335 | * | 20.8m |
| OR-Tools | 6.928 | 0.412% | 10.4m | 10.577 | 2.315% | 20.8m | OR-Tools | 6.927 | 0.386% | 10.4m | 10.582 | 2.363% | 20.8m |  |  |
| MTPOMO | 7.108 | 3.005% | 1s | 10.878 | 5.224% | 7s | MTPOMO | 7.112 | 3.055% | 1s | 10.884 | 5.276% | 6s |  |  |
| MVMoE | 7.089 | 2.741% | 2s | 10.840 | 4.861% | 9s | MVMoE | 7.098 | 2.846% | 2s | 10.847 | 4.928% | 9s |  |  |
| RF-POMO | 7.086 | 2.688% | 1s | 10.836 | 4.821% | 7s | RF-POMO | 7.087 | 2.693% | 1s | 10.837 | 4.830% | 6s |  |  |
| RF-MoE | 7.080 | 2.513% | 2s | 10.805 | 4.522% | 9s | RF-MoE | 7.083 | 2.635% | 2s | 10.806 | 4.534% | 9s |  |  |
| RF-TE | 7.071 | 2.479% | 1s | 10.772 | 4.208% | 6s | RF-TE | 7.074 | 2.508% | 1s | 10.778 | 4.262% | 6s |  |  |
| OVRPBLTW | HGS-PyVRP | 11.668 | * | 10.4m | 19.156 | * | 20.8m | OVRPBTW | HGS-PyVRP | 11.669 | * | 10.4m | 19.156 | * | 20.8m |
| OR-Tools | 11.681 | 0.106% | 10.4m | 19.305 | 0.767% | 20.8m | OR-Tools | 11.682 | 0.109% | 10.4m | 19.303 | 0.757% | 20.8m |  |  |
| MTPOMO | 11.817 | 1.260% | 1s | 19.637 | 2.496% | 7s | MTPOMO | 11.814 | 1.229% | 1s | 19.635 | 2.485% | 7s |  |  |
| MVMoE | 11.822 | 1.301% | 2s | 19.641 | 2.518% | 10s | MVMoE | 11.819 | 1.271% | 2s | 19.638 | 2.503% | 10s |  |  |
| RF-POMO | 11.805 | 1.157% | 1s | 19.609 | 2.344% | 8s | RF-POMO | 11.804 | 1.148% | 1s | 19.607 | 2.339% | 7s |  |  |
| RF-MoE | 11.824 | 1.312% | 2s | 19.607 | 2.334% | 10s | RF-MoE | 11.823 | 1.304% | 2s | 19.606 | 2.328% | 10s |  |  |
| RF-TE | 11.805 | 1.150% | 1s | 19.551 | 2.048% | 7s | RF-TE | 11.805 | 1.151% | 1s | 19.550 | 2.042% | 7s |  |  |
| OVRPL | HGS-PyVRP | 6.507 | * | 10.4m | 9.724 | * | 20.8m | OVRPLTW | HGS-PyVRP | 10.510 | * | 10.4m | 16.926 | * | 20.8m |
| OR-Tools | 6.552 | 0.668% | 10.4m | 10.001 | 2.791% | 20.8m | OR-Tools | 10.497 | 0.114% | 10.4m | 17.023 | 0.728% | 20.8m |  |  |
| MTPOMO | 6.719 | 3.227% | 1s | 10.214 | 5.002% | 6s | MTPOMO | 10.670 | 1.500% | 1s | 17.420 | 2.889% | 7s |  |  |
| MVMoE | 6.707 | 3.030% | 2s | 10.184 | 4.696% | 9s | MVMoE | 10.671 | 1.511% | 2s | 17.419 | 2.885% | 10s |  |  |
| RF-POMO | 6.701 | 2.949% | 1s | 10.180 | 4.659% | 6s | RF-POMO | 10.657 | 1.375% | 1s | 17.393 | 2.731% | 7s |  |  |
| RF-MoE | 6.696 | 2.864% | 2s | 10.140 | 4.249% | 9s | RF-MoE | 10.673 | 1.532% | 2s | 17.386 | 2.693% | 10s |  |  |
| RF-TE | 6.686 | 2.721% | 1s | 10.120 | 4.052% | 6s | RF-TE | 10.653 | 1.341% | 1s | 17.327 | 2.347% | 7s |  |  |

### 5.1 (RQ1) Main Results

Table 5.1 compares RouteFinder to the previously discussed baselines. We note that RouteFinder variants consistently outperform other baselines across all variants by more than $10\%$. While changing the encoder to the MVMoE’s structure (RF-MoE) may slightly improve the performance in limited settings, this comes with a higher inference cost (around $50\%$ more) due to the more complex structure of mixture-of-experts. Conversely, the proposed Transformer Encoder (RF-TE) outperforms baselines in virtually all metrics, including low evaluation latency. Training and testing for these results are performed on the same uniform location distribution of 50 and 100 nodes; we also include results on large-scale CVRPLIB instances in Section C.3. Remarkably, our RouteFinder does not only improve in distribution performance but can also scale better than the neural baselines in real-world settings.

### 5.2 (RQ2) Ablation Studies

We conduct ablation studies to evaluate the impact of newly introduced components. On the left of Fig. 5.1, we compare the performance of the full RouteFinder (RF-TE) against its variants with ablated components, using the results for MTPOMO as a baseline. The following components are removed in the ablation studies: 1) Transformer Encoder (Section 4.2.1), 2) Global Attribute Embeddings (Section 4.2.2), 3) Mixed Batch Training (Section 4.3.1) and 4) Reward Normalization (Section 4.3.2). All components contribute to the performance of RouteFinder. On the right of Fig. 5.1, we show the effect of different Reward Normalizations, i.e., 1)—4) from Section 4.3.2, with different values of $\alpha$ for the exponential moving averages. The best setting is the division through the exponentially smoothed mean with $\alpha=0.25$. We note that future reward normalization research may further improve performance.

Figure: Figure 5.1: [Left] Ablation study on RouteFinder components. [Right] Effect of Reward Normalization.
Refer to caption: x5.png

### 5.3 (RQ3) Generalization with EAL

We finally evaluate RouteFinder (RF-TE) in few-shot learning settings to unseen attributes, namely the mixed (M) backhauls variants. Unlike classical backhauls, this setting allows picking up items before delivering, but the model needs to keep track of the current number of picked-up items and remaining deliverables as context and a new global attribute to learn to plan effectively. We initialize a new EAL that results in a global embedding $\mathbf{W}^{\prime}_{0}$ adding $l=1$ features, i.e., the mixed backhaul flag. Moreover, we encode the available load accounting for the backhaul demand picked up as a dynamic context during decoding, resulting in another EAL $\mathbf{W}^{\prime}_{c}$, also adding one dimension. We compare against traditional baselines and 1) zero-shot performance of RouteFinder, 2) training from scratch a new model, 3) AL from Lin et al. (), which adds new layers while keeping the pre-trained backbone, and 4) our proposed EAL. We train baselines and EAL with the same setup as the full training, but for only $10$ epochs, $10$K instances are sampled for each.

**Table 5.2: Finetuning performance on 1000 mixed backhaul (MB) variants. RouteFinder’s EAL maintains the zero-shot performance and performs significantly better than other methods.**
|  | VRPMB | OVRPMB | VRPMBL | VRPMBTW | OVRPMBL | OVRPMBTW | VRPMBLTW | OVRPMBLTW |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Method | Cost | Gap | Cost | Gap | Cost | Gap | Cost | Gap | Cost | Gap | Cost | Gap | Cost | Gap | Cost | Gap |
| HGS-PyVRP | 13.54 | * | 9.01 | * | 13.78 | * | 25.51 | * | 9.01 | * | 16.97 | * | 25.85 | * | 16.97 | * |
| OR-Tools | 14.93 | $10.27\%$ | 10.59 | $17.54\%$ | 15.42 | $11.90\%$ | 29.97 | $17.48\%$ | 10.59 | $17.54\%$ | 19.31 | $13.78\%$ | 30.44 | $17.76\%$ | 19.31 | $13.78\%$ |
| Zero-shot | 14.88 | $10.13\%$ | 10.72 | $19.02\%$ | 15.18 | $10.32\%$ | 28.29 | $10.87\%$ | 10.72 | $19.01\%$ | 18.45 | $8.68\%$ | 28.65 | $10.82\%$ | 18.45 | $8.69\%$ |
| Train (scratch) | 15.18 | $12.13\%$ | 10.40 | $15.38\%$ | 15.48 | $12.37\%$ | 28.11 | $10.17\%$ | 10.46 | $16.08\%$ | 18.85 | $11.09\%$ | 28.69 | $10.95\%$ | 18.86 | $11.19\%$ |
| AL (step 0) | 43.15 | $221.25\%$ | 37.98 | $323.23\%$ | 32.81 | $139.84\%$ | 59.17 | $133.55\%$ | 29.15 | $224.37\%$ | 39.03 | $131.09\%$ | 66.62 | $158.21\%$ | 40.92 | $141.51\%$ |
| AL | 14.91 | $10.10\%$ | 10.14 | $12.53\%$ | 15.12 | $9.73\%$ | 27.79 | $8.92\%$ | 10.18 | $12.95\%$ | 18.52 | $9.13\%$ | 28.33 | $9.56\%$ | 18.51 | $9.05\%$ |
| EAL (step 0) | 14.88 | $10.13\%$ | 10.72 | $19.02\%$ | 15.18 | $10.32\%$ | 28.29 | $10.87\%$ | 10.72 | $19.01\%$ | 18.45 | $8.68\%$ | 28.65 | $10.82\%$ | 18.45 | $8.69\%$ |
| EAL | 14.59 | 7.89$\%$ | 9.66 | 7.19$\%$ | 14.78 | 7.39$\%$ | 26.69 | 4.61$\%$ | 9.65 | 7.13$\%$ | 17.60 | 3.70$\%$ | 27.13 | 4.90$\%$ | 17.59 | 3.65$\%$ |

Table 5.2 shows that EAL consistently outperforms baselines in few-shot learning with strong performance. We additionally compare both AL and EAL at the “step 0”, i.e., after replacing the new adapter layers. Notably, while AL with the untrained new layers can greatly degrade the performance unless optimization is performed, EAL maintains the zero-shot performance even without training, providing a much better starting point.

## 6 Conclusion

In this work, we presented RouteFinder, a comprehensive framework to develop foundation models for VRPs. We introduced a unified VRP environment to represent any combination of attributes. We proposed a new Transformer Encoder and Global Attribute Embeddings to enhance learning representations of diverse VRPs. We introduced Mixed Batch Training and Multi-variant Reward Normalization to allow for effective training with RL in a multi-task setting with different tasks and reward scales. Finally, we introduced Efficient Adapter Layers, a lightweight and powerful technique to finetune RouteFinder to unseen attributes. Our extensive evaluations on 24 VRP variants showed RouteFinder outperforms SOTA neural baselines for VRPs.

RouteFinder represents an early attempt to learn a foundation model across problem variants. While demonstrating strong generalization, it does so at a slight expense in solution quality compared to techniques trained on specific problem variants, at least for in-distribution results, as also noted by prior works (Liu et al., ; Zhou et al., ). For future work, we intend to extend RouteFinder to support further variants of the vast VRP literature. We also intend to improve the model performance to eventually outperform state-of-the-art traditional OR solvers – exciting directions include decomposition methods (Ye et al., ; Zheng et al., ) and end-to-end construction and improvement (Kong et al., ).

## Acknowledgements

We thank people in the AI4CO open research community who have contributed to RouteFinder and more including RL4CO. Furthermore, we thank OMELET for supporting us with additional computing.

## Funding

This work was supported by the Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korean government(MSIT)[2022-0-01032, Development of Collective Collaboration Intelligence Framework for Internet of Autonomous Things]. Nayeli Gast Zepeda and André Hottung were supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Grant No. 521243122. We also gratefully acknowledge the funding of this project by computing time provided by the Paderborn Center for Parallel Computing (PC2).

## Appendix A Unified VRP Environment Details

We consider the six attributes from Section 3.1 for instance, generation through our environment definition explained in Section 4.1. Leveraging our environment’s modular structure, we build the same 16 VRP variants as used in MVMoE (Zhou et al., ), but by differentiating between traditional (B) and mixed (MB) backhauls, as defined in the (Avci & Topaloglu, ), we extend that number to 24, as shown in Table A.1. We describe additional details of the Unified VRP environment, including data generation in Section A.1 and environment logic in Section A.2. For a better understanding, we invite the reader to look at the source code, which we tried our best to comment on for clarity, at [https://github.com/ai4co/routefinder](https://github.com/ai4co/routefinder).

### A.1 Data generation

We now explain the individual steps in the data generation process we use for our modular VRP environment.

##### Locations

We generate $n+1$ locations randomly with $x_{i}$ and $y_{i}\sim U(0,1),\forall i\in\{0,...,n\}$, where $[x_{0},y_{0}]$ denotes the depot and $[x_{i},y_{i}],i\in\{1,...,n\}$, the $n$ customer nodes. Note that this setting can be expanded to consider more realistic distributions as in (Bi et al., ; Zhou et al., ; Gao et al., ), and our implementation is already set up in such a way to allow for different distributions in the future via the get_sampler method.

##### Vehicle capacity (C)

The vehicle capacity $C$ is a fixed value applied to all vehicles and calculated according to:

$$ $C=\begin{cases}30+\left\lfloor\frac{1000}{5}+\frac{n-1000}{33.3}\right\rfloor& \text{if }1000<n\\ 30+\left\lfloor\frac{n}{5}\right\rfloor&\text{if }20<n\leq 1000\\ 30&\text{otherwise}\end{cases}$ $$

which is commonly used in NCO for VRP approaches (Kool et al., ; Kwon et al., ).

##### Linehaul and backhaul demands (C) / (B) / (MB)

We generate demands according to the following scheme:

- 1.
Generate linehaul demands $q_{i}$ for all customers $i\in N_{c}$ by sampling uniformly from the set of integers $\{1,2,...,9\}$.
- 2.
Generate backhaul demands $p_{i}$ for all customers $i\in N_{c}$ by sampling uniformly from the set of integers $\{1,2,...,9\}$.
- 3.
For each customer $i\in N_{c}$, generate a temporary decision variable $z_{i}\in\{0,1\}$ with probabilities $\mathbb{P}(z_{i}=0)=0.8$ and $\mathbb{P}(z_{i}=1)=0.2$.
•
If $z_{i}=0$, keep the linehaul demand $q_{i}$ and set the backhaul demand $p_{i}=0$.
•
If $z_{i}=1$, set the linehaul demand $q_{i}=0$ and keep the backhaul demand $p_{i}$.

This demand generation scheme ensures that each customer has either a linehaul demand or a backhaul demand, but not both. With a probability of 0.8, a customer will have only a linehaul demand, and their backhaul demand will be set to 0. Conversely, with a probability of 0.2, a customer will have only a backhaul demand, and their linehaul demand will be set to 0. It is important to note that not all customers are typically backhaul customers, even in a backhaul setting. Therefore, this scheme allows for the consideration of both linehaul and backhaul demands in backhaul problem settings while ensuring that each customer has only one type of demand.

We note that this can be easily extended to the case of VRP with simultaneous pickup and delivery (VRPSPD), in which a customer can have both linehaul and backhaul demand (Ai & Kachitvichyanukul, ; Koç et al., ). In such a case, we could duplicate the customer node into two nodes with the same attributes, such as locations, but different values for linehaul (pickup) and backhaul (delivery) in the current VRP environment or allow for both linehaul and backhaul to be present at the same time in a single node with small modifications of the action masking.

##### Backhaul class (B) / (MB)

For testing the few-shot setting described in Section 5.3, we generate instances with mixed backhauls. The instances themselves are actually identical to instances with the traditional backhaul, and we use a global attribute in the instance to differentiate between them. For this purpose, we allow either setting a fixed value $\in\{1,2\}$ or sampling from $\{1,2\}$ for every customer with equal probabilities $p(1)=p(2)=0.5$, allowing for different backhaul settings within one batch, if needed (see the batching procedure described in Section 4.3.1). Note that we sample from $\{1,2\}$ instead of boolean sampling because we plan to extend the number of backhaul settings in the future.

##### Open routes (O)

For open routes, we generate a boolean vector with all True values. During sampling (see Section 4.3.1), the actual ratio of open route instances is defined, not at the initial instance generation (i.e., we temporarily change the True value to False for every batch element with a certain probability).

##### Time Windows (TW)

We generate the time windows $[e_{i},l_{i}]$ and service times $s_{i}$ in several steps for all customers $i\in N_{c}$:

- 1.
Generate service times $s_{i}\in[0.15,0.18]$.
- 2.
Generate time window lengths $t_{i}\in[0.18,0.2]$.
- 3.
Calculate distances $d_{0i}$ from the depot to the customer.
- 4.
Calculate upper bounds for time window start times $h_{i}=\frac{t_{\mathit{max}}-s_{i}-t_{i}}{d_{0i}}-1$.
- 5.
Calculate time window start times as $e_{i}=(1+(h_{i}-1)\cdot u_{i})\cdot d_{0i}$ with $u_{i}\sim U(0,1)$.
- 6.
Calculate time window end times as $l_{i}=e_{i}+t_{i}$.

When calculating the action mask, we have the constraint that the expected arrival time should be earlier than the end time of nodes; if the problem is a close problem, we should also consider the time back to the depot, i.e., $\max(t_{\mathrm{curr}}+d_{ij},e_{j})+s_{j}+d_{j0}<l_{0}$. We note that for simplicity, we set the vehicle speed to $1.0$ in equations and normalize time windows accordingly so that travel time from two nodes is the same numerically as the distance between them. This can be easily modified in the code.

We mention as an alternative TW generation procedure the one from the Solomon benchmark (Solomon, ; Li et al., ), which may perform better in that benchmark, as done in Zhou et al. ().

##### Distance limit (L)

The distance limit is sampled from a uniform distribution to ensure meaningful and feasible constraints. Specifically, we sample $L$ from $U((2\cdot\max(d_{0i}),l_{\text{max}}),l_{\text{max}})$, where $d_{0i}$ is the distance from the depot to customer $i$, and $l_{\text{max}}=3.0$ is a predefined upper bound. This approach ensures that $L$ is always greater than the round trip to the farthest customer $(2\cdot\max(d_{0i}))$, making all customers reachable, while also allowing for variation in the constraint tightness. This sampling method produces more variation than previous works Liu et al. (); Zhou et al. () (where there was virtually no difference in solutions of (L) and non-(L) variants), as it guarantees feasible instances while still providing a range of challenging scenarios.

**Table A.1: The 24 VRP variants we consider. All variants include the base Capacity (C). The $k=4$ features O, B, L, and TW can be combined into any subset, including the empty set and itself (i.e., a power set) with $2^{k}=16$ possible combinations. Finally, we study the additional Mixed (M) global feature that creates new Backhaul (B) variants in generalization studies, adding 8 more variants.**
| VRP Variant | Capacity<br>(C) | Open Route<br>(O) | Backhaul<br>(B) | Mixed<br>(M) | Duration Limit<br>(L) | Time Windows<br>(TW) |
| --- | --- | --- | --- | --- | --- | --- |
| CVRP | ✓ |  |  |  |  |  |
| OVRP | ✓ | ✓ |  |  |  |  |
| VRPB | ✓ |  | ✓ |  |  |  |
| VRPL | ✓ |  |  |  | ✓ |  |
| VRPTW | ✓ |  |  |  |  | ✓ |
| OVRPTW | ✓ | ✓ |  |  |  | ✓ |
| OVRPB | ✓ | ✓ | ✓ |  |  |  |
| OVRPL | ✓ | ✓ |  |  | ✓ |  |
| VRPBL | ✓ |  | ✓ |  | ✓ |  |
| VRPBTW | ✓ |  | ✓ |  |  | ✓ |
| VRPLTW | ✓ |  |  |  | ✓ | ✓ |
| OVRPBL | ✓ | ✓ | ✓ |  | ✓ |  |
| OVRPBTW | ✓ | ✓ | ✓ |  |  | ✓ |
| OVRPLTW | ✓ | ✓ |  |  | ✓ | ✓ |
| VRPBLTW | ✓ |  | ✓ |  | ✓ | ✓ |
| OVRPBLTW | ✓ | ✓ | ✓ |  | ✓ | ✓ |
| VRPMB | ✓ |  | ✓ | ✓ |  |  |
| OVRPMB | ✓ | ✓ | ✓ | ✓ |  |  |
| VRPMBL | ✓ |  | ✓ | ✓ | ✓ |  |
| VRPMBTW | ✓ |  | ✓ | ✓ |  | ✓ |
| OVRPMBL | ✓ | ✓ | ✓ | ✓ | ✓ |  |
| OVRPMBTW | ✓ | ✓ | ✓ | ✓ |  | ✓ |
| VRPMBLTW | ✓ |  | ✓ | ✓ | ✓ | ✓ |
| OVRPMBLTW | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |

##### Attribute Normalization and Scaling

All demands, both linehauls and backhauls, are scaled to lie in $[0,1]$ through division by the vehicle capacity. $q^{\prime}_{i}=q_{i}/C,p^{\prime}_{i}=p_{i}/C$. All other features are already sampled from a normalized range. Note that during loading instances from e.g. CVRPLib, we normalize features before passing them to the policy - for instance, locations are normalized between 0 and 1.

### A.2 Environment Logic

To determine available actions for the Unified VRP environment formulation, the constraints for the individual problems have to be combined in the action mask (action_mask in the code following RL4CO, where True means that the action is feasible (Berto et al., )). We build a logical test structure, essentially separating the checks in the action mask according to the individual VRP problem types and then bringing them all together again. The individual action_mask checks are the following:

- a)
Can reach in time: depending on the current time and the travel distance to every node not yet visited, can we reach that node before its service time window ends? $t_{\mathrm{curr}}+d_{ij}<l_{j}$, where $t_{\mathrm{curr}}$ is the current time.
- b)
Does not exceed distance limit: depending on the current length of the route, if we travel to any available node, will we exceed the total distance limit for the route? $l_{\mathrm{curr}}+d_{ij}<L$, where $l_{\mathrm{curr}}$ is the current length.
- c)
Can reach depot: there are two types of constraints from time windows (TW) and distance limit (L):
•
If we need to ensure we can reach the depot in time, i.e., the current time plus traveling time to the depot must be smaller than the system end time. $\max(t_{\mathrm{curr}}+d_{ij},e_{j})+s_{j}+d_{j0}<l_{0}$.
•
If we need to ensure we can reach the depot in the limitation of the depot, i.e., the current distance plus the traveling distance to the depot must be smaller than the distance limit. $l_{\mathrm{curr}}+d_{ij}+d_{j0}<L$.
For open routes, this will always be set to True, and doesn’t have these constraints.
- d)
Demand constraints for backhaul problems:
•
Checks for all backhauls problems:
–
Does the linehaul demand exceed vehicle capacity if we add a node’s demand to the current vehicle? $c_{\mathrm{curr}}+q_{j}<C$, where $c_{\mathrm{curr}}$ is the used capacity.
–
Does the backhaul demand exceed vehicle capacity if we add a node’s demand to the current vehicle? $c_{\mathrm{curr}}+p_{j}<C$, where $c_{\mathrm{curr}}$ is the used capacity.
•
Checks for traditional backhaul settings:
–
Carrying backhaul: if we are already picking up backhaul demands, we cannot service any linehaul demands on this route anymore.
–
If we are not carrying backhaul demands yet, are there any unserved linehaul demands left?
–
If there are no linehaul demands left or we are already carrying backhauls, are there still unserved backhaul demands?
•
Checks for mixed backhaul settings:
–
Cannot service linehaul demands: depending on the backhaul demands currently loaded in the vehicle, do we have space left for further linehaul demands?
- e)
Already visited: every customer node needs to be visited exactly once.

We bring together checks a) to e) and introduce an additional check for the depot: if we are currently in the depot and there are still unserved customers, we cannot select the depot as the next action to ensure the model cannot get stuck during decoding. Combining these checks in this way allows us to meticulously check for individual VRP settings while at the same time maintaining the necessary flexibility the unified environment formulation requires.

## Appendix B RouteFinder Model Details

RouteFinder follows the encoder-decoder architecture from the Attention Model (Kool et al., ), a transformer-like architecture based on the attention mechanism (Vaswani et al., ). We additionally improve the encoder architecture in RF-TE as explained in Section 4.2.

### B.1 Multi-Head Attention

At the core of RouteFinder lies the Multi-Head Attention (MHA) mechanism, proposed by Vaswani et al. (). MHA concurrently attends to information from various representation subspaces, facilitating the capture of diverse relationships between input elements. Notably, MHA is capable of handling a variable number of elements.

The MHA operation starts by linearly projecting the input sequences of queries $Q$, keys $K$, and values $V$ to $H$ distinct subspaces using learned projection matrices $W_{i}^{Q}$, $W_{i}^{K}$, and $W_{i}^{V}$, respectively, where $H$ denotes the number of attention heads: $Q_{i}=QW_{i}^{Q}$, $K_{i}=KW_{i}^{K}$, $V_{i}=VW_{i}^{V}$ for $i=1,\dots,H$. Subsequently, the attention weights for each head are computed by performing a scaled dot product between the projected queries and keys, followed by a softmax operation:

$$ $A_{i}=\text{Softmax}\left(\frac{Q_{i}K_{i}^{T}}{\sqrt{d_{k}}}+M\right)$ (7) $$

where $d_{k}$ represents the dimension of the keys, acting as a scaling factor to prevent the dot products from growing too large, $\text{Softmax}(x_{i})=\frac{\exp(x_{i})}{\sum_{j=1}^{N}\exp(x_{j})}$ and $M$ is an optional attention mask that can be used to prevent attending to certain positions (e.g., infeasible actions), which can be done by setting elements to $-\infty$. The output of each attention head is then calculated as a weighted sum of the projected values, using the attention weights: $Z_{i}=A_{i}V_{i}$.

Lastly, the outputs from all attention heads are concatenated and linearly projected using a learned matrix $W^{O}$ to yield the final output of the MHA operation:

$$ $\text{MHA}(Q,K,V)=\text{Concat}(Z_{1},\dots,Z_{H})W^{O}$ (8) $$

While the MHA grows quadratically, i.e., with sequence length (i.e., number of nodes) $N$, it grows as $O(N^{2})$, several efficient implementations have been proposed over the years, and we use FlashAttention (Dao et al., ; Dao, ) to speed up the model.

### B.2 Encoder

The Encoder transforms an input instance $\bm{x}$ into a hidden embedding $\bm{h}$. The Encoder architecture consists of the following main components: 1) Global Embedding 2) Node Embedding, and 3) a series of Encoder Layers (^2^22Note that the following description might slightly differ from the code implementation due to minor differences - for instance, we erroneously did not implement $l_{0}$ for the depot in the main experiments, where $l_{0}$ however was kept constant.). We consider a VRP instance of $N$ location as having $N+1$ nodes, where $n_{0}$ is the depot, and $n_{1},\dots,n_{N}$ are $N$ customers.

##### Global Embedding

The global embedding $f$ captures problem-level attributes and is projected onto the depot node. These attributes include Open Routes $o\in\{0,1\}$, Duration Limits $l\in[0,L]$, (with EAL only), Mixed Backhauls flag $m\in\{0,1\}$, $l_{0}$ as the late Time Window for the problem, and the location of the depot node $[x_{0},y_{0}]\in\mathbb{R}^{2}$. In RouteFinder, the global embedding $f$ is a linear projection layer $\mathbf{W}_{g}\in\mathbb{R}^{k\times d}$ where $k=5$ features and $d=128$ is the hidden dimension. The initial projected global hidden embedding can be written as $\bm{h}^{(0)}_{g}=\mathbf{W}_{g}[o,l,m,l_{0},x_{0},y_{0}]^{\top}$.

##### Node Embedding

The node embeddings, on the other hand, capture customer-specific attributes and are projected onto the remaining $N$ nodes. These attributes include for nodes $i\in 1,\dots,N$: Demand and Vehicle Capacity $q_{i}\in[0,Q]$], Time Windows parameters $e_{i},s_{i},l_{i}\in[0,T]^{3}$] where $e$ and $l$ are early and late time windows and $s$ is the service time, and $p_{i}\in[0,Q]$ are Backhaul demands, and finally locations $[x_{i},y_{i}]\in\mathbb{R}^{2}$. In RouteFinder this a linear projection layer $\mathbf{W}_{n}\in\mathbb{R}^{k\times d}$ where $k=7$ features and $d=128$ is the hidden dimension. The initial projected node hidden embedding can be written for each node $n_{i}$ as $\bm{h}^{(0)}_{n_{i}}=\mathbf{W}_{n}[q_{i},e_{i},s_{i},l_{i},p_{i},x_{i},y_{i}]
^{\top}$.

##### Raw Features to Hidden States

The projected global embedding and node embeddings are concatenated to obtain the initial hidden representation $\bm{h}^{(0)}\in\mathbb{R}^{N\times d}$, where $N$ is the total number of nodes (depot + customers) and $d$ is the hidden dimension:

$$ $\displaystyle\bm{h}^{(0)}=\text{Concat}(\bm{h}^{(0)}_{g},\bm{h}_{n_{1}}^{(0)}, \dots,\bm{h}_{n_{N}}^{(0)})$ (9) $$

The initial hidden representation $\bm{h}^{(0)}$ is then passed through a series of Encoder Layers to refine and enrich the representation. Each Encoder Layer consists of a Multi-Head Attention (MHA) layer and a Multi-Layer Perceptron (MLP) layer, as described in Eq. 11 and Eq. 12, respectively.

The Encoder can be represented as:

$$ $\displaystyle\bm{h}=\text{EncoderBlocks}(\bm{h}^{(0)})$ (10) $$

Each EncoderBlock consists of two sub-layers: a Multi-Head Attention (MHA) layer and a Multi-Layer Perceptron (MLP) layer (or SwiGLU as we propose). The MHA layer allows the model to capture dependencies between different positions in the input sequence, while the MLP layer applies non-linear transformations to the features at each position. The input to each EncoderBlock is first passed through the MHA layer, which computes the self-attention using the input as queries, keys, and values:

$$ $\displaystyle\hat{\bm{h}}$ $\displaystyle=\text{Norm}\left(\bm{h}^{(\ell-1)}+\text{MHA}(\bm{h}^{(\ell-1)}, \bm{h}^{(\ell-1)},\bm{h}^{(\ell-1)})\right)$ (11) $$

where $\bm{h}^{(\ell-1)}$ represents the input to the $\ell$-th EncoderBlock, and Norm denotes a normalization operation, in RouteFinder we employ Instance Normalization (IN). The output of the MHA layer, $\hat{\bm{h}}$, is then passed through the MLP layer, which applies a series of linear transformations with non-linear activations:

$$ $\displaystyle\bm{h}^{(\ell)}$ $\displaystyle=\text{Norm}\left(\hat{\bm{h}}+\text{MLP}(\hat{\bm{h}})\right)$ (12) $$

The pointwise MLP layer consists of two linear layers with a non-linear activation function as ReLU, between them.

##### Transformer-based Encoder

We further explicit our proposed Transformer-based encoder. Each EncoderBlock consists of two sub-layers: a Multi-Head Attention (MHA) layer and a Feed Forward SwiGLU layer (Shazeer, ). The MHA layer captures dependencies between different positions in the input sequence, while the SwiGLU layer applies non-linear transformations to the features. We employ RMS normalization (Zhang & Sennrich, ) and pre-norm architecture for improved stability and faster convergence:

$$ $\displaystyle\hat{\bm{h}}$ $\displaystyle=\bm{h}^{(\ell-1)}+\text{MHA}(\text{RMSNorm}(\bm{h}^{(\ell-1)}), \text{RMSNorm}(\bm{h}^{(\ell-1)}),\text{RMSNorm}(\bm{h}^{(\ell-1)}))$ (13) $\displaystyle\bm{h}^{(\ell)}$ $\displaystyle=\hat{\bm{h}}+\text{SwiGLU}(\text{RMSNorm}(\hat{\bm{h}}))$ (14) $$

where $\bm{h}^{(\ell-1)}$ represents the input to the $\ell$-th EncoderBlock. The SwiGLU activation function is defined as:

$$ $\displaystyle\text{SwiGLU}(\bm{x})$ $\displaystyle=\bm{x}\odot\sigma(\bm{W}_{1}\bm{x}+\bm{b}_{1})\otimes\text{SiLU} (\bm{W}_{2}\bm{x}+\bm{b}_{2})$ (15) $$

where $\odot$ denotes element-wise multiplication, $\otimes$ is matrix multiplication, $\sigma$ is the sigmoid function, SiLU is the Sigmoid Linear Unit (Swish) activation function, and $\bm{W}_{1},\bm{W}_{2},\bm{b}_{1},\bm{b}_{2}$ are learnable parameters. We use FlashAttention (Dao et al., ; Dao, ) in the MHA layer for enhanced performance.

### B.3 Decoder

The Decoder autoregressively constructs the solution based on the Encoder output $\bm{h}$ and the state at the current step $t$, $s_{t}$.

##### Context Embedding

The context embedding is used to modify the query embedding of the problem node of the current partial solution. It consists of a linear layer that projects the concatenated current node embedding and state embedding to the embedding space. The state embedding is computed by projecting the following: the current node embedding $\bm{}t$ and a set of dynamic features from state $s_{t}$, i.e. the available load $c_{t}$, current time $t_{t}$ and current distance traveled $d_{t}$.

##### Attention and Pointer Mechanism

The query $q_{t}$ is then obtained by projecting the concatenated current node embedding and state embedding using a linear layer:

$$ $\displaystyle q_{t}=\mathbf{W}_{c}\text{Concat}([\bm{h}_{t};[c_{t},t_{t},d_{t} ]])^{\top}$ (16) $$

where $\mathbf{W}_{c}\in\mathbb{R}^{d\times(d+k)}$ is the linear projection matrix, $d=128$ is the hidden dimension, and $k=3$ is the number of state features (available load, current time, and remaining distance). Note that with EAL, we additionally add another feature so that $k=4$, namely the difference between the vehicle capacity and the used backhaul capacity. This is necessary because if we pick up items, the deliverable quantity must exceed the remaining capacity after pick up. The query $q_{t}$ is then passed into a masked MHA layer and final single-head attention to obtain logits $\bm{z}$:

$$ $\displaystyle h^{c}_{t}$ $\displaystyle=\text{MHA}(q_{t},{K}^{g}_{t},{V}^{g}_{t},M_{t}),$ (17) $\displaystyle\bm{z}$ $\displaystyle=\frac{{V}_{t}^{p}h^{c}_{t}}{\sqrt{d_{k}}}$ (18) $$

where $M_{t}$ is the set of feasible actions (i.e., the action_mask), and projections ${K}^{g}_{t},{V}^{g}_{t},{V}_{t}^{p}=W_{k}^{g}\bm{h},W_{v}^{g}\bm{h},W_{v}^{p}
\bm{h}$ are precomputed once as cache. We note that Eq. 18 is usually referred to as the pointer mechanism (Vinyals et al., ).

##### Logits processing

Finally, logits $\bm{z}$ are transformed into a probability distribution:

$$ $p=\text{Softmax}\left(C\cdot\text{tanh}(\bm{z})\right)$ (19) $$

where logits for infeasible actions can be masked, and $C$ is the tanh clipping that serves in improving the exploration, which we set to 10 according to Bello et al. ().

##### Action selection

During training, we use the POMO multistart sampling which forces the first action to start from all nodes to enhance diversity. During testing, we also employ multistart but with greedy selection (i.e., selecting the maximum probability). Prior to the selection, a dihedral augmentation is also performed prior to encoding instance $\bm{x}$ in the encoder, which enables exploring $8\times$ as many solutions with 4 rotations $\times$ 2 flips. We note that additional augmentations and techniques can be performed during inference, which can further boost evaluation performance (Kim et al., ; Ma et al., ; Choo et al., ; Luo et al., ), which we do not use for fairness of comparison but could greatly boost RouteFinder performance.

### B.4 Hyperparameter Details

We report in Table B.1 the hyperparameter details common across all experiments. RouteFinder variants additionally employ the proposed contributions as outlined in the main text.

**Table B.1: Experiment hyperparameters. Values with “/” indicate different choices depending on the model, i.e., on the right are values for the Transformer-Based encoder.**
| Hyperparameter | Value |
| --- | --- |
| Model |  |
| Embedding dimension | 128 |
| Number of attention heads | 8 |
| Number of encoder layers | 6 |
| Use Pre-norm | False / True |
| Normalization | Instance / RMSNorm |
| Feedforward hidden dimension | 512 |
| Feedforward structure | MLP / Gated MLP |
| Feedforward activation | ReLU / SwiGLU |
| Tanh clipping | 10.0 |
| Mask logits | True |
| Training |  |
| Train decode type | multistart sampling |
| Val & Test decode type | multistart greedy |
| Augmentation function | dihedral |
| Batch size | 256 |
| Train data per epoch | 100,000 |
| Optimization |  |
| Optimizer | Adam |
| Learning rate | 3e-4 |
| Weight decay | 1e-6 |
| LR scheduler | MultiStepLR |
| LR milestones | [270, 295] |
| LR gamma | 0.1 |
| Gradient clip value | 1.0 |
| Max epochs | 300 |

## Appendix C Additional Material

### C.1 Additional Discussion

##### Motivation

Foundation models have been successful in several areas in recent years, including large language models (Achiam et al., ), computer vision (Kirillov et al., ) as well as other domains such as biology (Abramson et al., ; Nguyen et al., ). However, foundation models for discrete decision-making, such as CO and our target VRPs, are still under-explored as an area - one reason being the lack of large, high-quality open datasets that can effectively be employed to train such models - which motivates our use of RL. Such foundation models may not only obtain solutions faster than traditional OR counterparts but also avoid the requirement of possibly decades of research and resources to tackle a single task, while a foundation model may automatically learn heuristics without supervision.

##### Generalist, or specialized?

Another open question is the idea of generality behind the model. In RouteFinder, we argue that a model might not need to be extremely complex and be specialized for a specific application (such as routing). One such reason is that with larger model capabilities comes larger size and inference time, which is crucial for real-world deployment. An interesting future direction would be to attempt to generalize a model as a "foundation model for CO", for instance, based on a general formulation (Boisvert et al., ), and see whether the additional training and inference costs are worth a (possible) boost in optimality gaps and generalization ability. Such a model may be able to attain a better few-shot generalization to totally unseen attributes, either with adapter layers (Lin et al., ) or with our proposed EAL. However, we believe that tailored, specialized foundation models as RouteFinder for VRPs may be more practical and efficient. We note that an orthogonal direction to ours is the use of LLMs as hyper-heuristics (Romera-Paredes et al., ; Liu et al., ; Ye et al., ), which starts from a generalist LLM agent to generate algorithms that can be used to improve the optimization of CO problems as VRPs. However, such models are not used at inference time due to the inefficiency of using billions of parameters that are not tailored for the problem at hand.

##### Going forward

in specialized foundation models for VRPs, there are several challenges yet to be addressed. One such challenge is the still sub-par performance compared to state-of-the-art solvers (Wouda & Lan, ; Wouda et al., ), which may be offset on a larger scale by several means, including decompositions. Another way to attain better performance would be to integrate with local search (Ye et al., ; Kim et al., ) and hybridize constructive (the current policy paradigm) with improvement methods (Ma et al., ; ) to guarantee monotonic improvements given larger time budgets. Finally, given the robust cross-task performance even compared to single-task models, we believe expanding to more VRP variants (and their attribute distributions) may further improve overall performance.

### C.2 Licenses for used assets

Table C.1 lists the used assets and their licenses. Our code is licensed under the MIT License.

**Table C.1: Used assets and their licenses.**
| Type | Asset | License | Usage |
| --- | --- | --- | --- |
| Code | POMO (Kwon et al., ) | MIT License | Evaluation |
| MTPOMO (Liu et al., ) | MIT License | Evaluation |  |
| MVMoE (Zhou et al., ) | MIT License | Evaluation |  |
| RL4CO (Berto et al., ) | MIT License | Evaluation |  |
| AL (Lin et al., ) | MIT License | Evaluation |  |
| ORTools (Perron & Didier, ) | Apache-2.0 | Evaluation |  |
|  | PyVRP (Wouda et al., ) | MIT License | Evaluation |
| Dataset | CVRPLib (Lima et al., ) | Available for any non-commercial use | Testing |

### C.3 CVRPLIB Evaluation

**Table C.2: Results on large-scale CVRPLIB instances from the X set. All models are only trained on the uniformly distributed data with the size $n=100$ and evaluated via greedy rollouts. Results for methods with $\dagger$ are drawn from Zhou et al. (), models trained with single features excluding feature compositions (except for OVRPTW). Training on multiple variants enhances generalization across models.**
| Set-X | POMO^† | MTPOMO ^† | MVMoE^† | MVMoE-L^† | MTPOMO | MVMoE | RF-TE |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Instance | Opt. | Obj. | Gap | Obj. | Gap | Obj. | Gap | Obj. | Gap | Obj. | Gap | Obj. | Gap | Obj. | Gap |
| X-n502-k39 | 69226 | 75617 | 9.232% | 77284 | 11.640% | 73533 | 6.222% | 74429 | 7.516% | 69226 | 9.410% | 76338 | 10.274% | 71791 | 3.705% |
| X-n513-k21 | 24201 | 30518 | 26.102% | 28510 | 17.805% | 32102 | 32.647% | 31231 | 29.048% | 24201 | 42.511% | 32639 | 34.866% | 28465 | 17.619% |
| X-n524-k153 | 154593 | 201877 | 30.586% | 192249 | 24.358% | 186540 | 20.665% | 182392 | 17.982% | 154593 | 14.771% | 170999 | 10.612% | 174381 | 12.800% |
| X-n536-k96 | 94846 | 106073 | 11.837% | 106514 | 12.302% | 109581 | 15.536% | 108543 | 14.441% | 94846 | 16.109% | 105847 | 11.599% | 103272 | 8.884% |
| X-n548-k50 | 86700 | 103093 | 18.908% | 94562 | 9.068% | 95894 | 10.604% | 95917 | 10.631% | 86700 | 27.851% | 104289 | 20.287% | 100956 | 16.443% |
| X-n561-k42 | 42717 | 49370 | 15.575% | 47846 | 12.007% | 56008 | 31.114% | 51810 | 21.287% | 42717 | 30.770% | 53383 | 24.969% | 49454 | 15.771% |
| X-n573-k30 | 50673 | 83545 | 64.871% | 60913 | 20.208% | 59473 | 17.366% | 57042 | 12.569% | 50673 | 20.210% | 61524 | 21.414% | 55952 | 10.418% |
| X-n586-k159 | 190316 | 229887 | 20.792% | 208893 | 9.761% | 215668 | 13.321% | 214577 | 12.748% | 190316 | 19.125% | 212151 | 11.473% | 205575 | 8.018% |
| X-n599-k92 | 108451 | 150572 | 38.839% | 120333 | 10.956% | 128949 | 18.901% | 125279 | 15.517% | 108451 | 21.098% | 126578 | 16.714% | 116560 | 7.477% |
| X-n613-k62 | 59535 | 68451 | 14.976% | 67984 | 14.192% | 82586 | 38.718% | 74945 | 25.884% | 59535 | 30.523% | 73456 | 23.383% | 67267 | 12.987% |
| X-n627-k43 | 62164 | 84434 | 35.825% | 73060 | 17.528% | 70987 | 14.193% | 70905 | 14.061% | 62164 | 23.193% | 70414 | 13.271% | 67572 | 8.700% |
| X-n641-k35 | 63682 | 75573 | 18.672% | 72643 | 14.071% | 75329 | 18.289% | 72655 | 14.090% | 63682 | 30.321% | 71975 | 13.023% | 70831 | 11.226% |
| X-n655-k131 | 106780 | 127211 | 19.134% | 116988 | 9.560% | 117678 | 10.206% | 118475 | 10.952% | 106780 | 12.731% | 119057 | 11.497% | 112202 | 5.078% |
| X-n670-k130 | 146332 | 208079 | 42.197% | 190118 | 29.922% | 197695 | 35.100% | 183447 | 25.364% | 146332 | 24.809% | 168226 | 14.962% | 168999 | 15.490% |
| X-n685-k75 | 68205 | 79482 | 16.534% | 80892 | 18.601% | 97388 | 42.787% | 89441 | 31.136% | 68205 | 36.550% | 82269 | 20.620% | 77847 | 14.137% |
| X-n701-k44 | 81923 | 97843 | 19.433% | 92075 | 12.392% | 98469 | 20.197% | 94924 | 15.870% | 81923 | 13.319% | 90189 | 10.090% | 89932 | 9.776% |
| X-n716-k35 | 43373 | 51381 | 18.463% | 52709 | 21.525% | 56773 | 30.895% | 52305 | 20.593% | 43373 | 37.657% | 52250 | 20.467% | 49669 | 14.516% |
| X-n733-k159 | 136187 | 159098 | 16.823% | 161961 | 18.925% | 178322 | 30.939% | 167477 | 22.976% | 136187 | 28.910% | 156387 | 14.833% | 148463 | 9.014% |
| X-n749-k98 | 77269 | 87786 | 13.611% | 90582 | 17.229% | 100438 | 29.985% | 94497 | 22.296% | 77269 | 32.182% | 92147 | 19.255% | 85171 | 10.227% |
| X-n766-k71 | 114417 | 135464 | 18.395% | 144041 | 25.891% | 152352 | 33.155% | 136255 | 19.086% | 114417 | 16.692% | 130505 | 14.061% | 129935 | 13.563% |
| X-n783-k48 | 72386 | 90289 | 24.733% | 83169 | 14.897% | 100383 | 38.677% | 92960 | 28.423% | 72386 | 50.140% | 96336 | 33.087% | 83185 | 14.919% |
| X-n801-k40 | 73305 | 124278 | 69.536% | 85077 | 16.059% | 91560 | 24.903% | 87662 | 19.585% | 73305 | 24.536% | 87118 | 18.843% | 86164 | 17.542% |
| X-n819-k171 | 158121 | 193451 | 22.344% | 177157 | 12.039% | 183599 | 16.113% | 185832 | 17.525% | 158121 | 22.148% | 179596 | 13.581% | 174441 | 10.321% |
| X-n837-k142 | 193737 | 237884 | 22.787% | 214207 | 10.566% | 229526 | 18.473% | 221286 | 14.220% | 193737 | 19.429% | 230362 | 18.904% | 208528 | 7.635% |
| X-n856-k95 | 88965 | 152528 | 71.447% | 101774 | 14.398% | 99129 | 11.425% | 106816 | 20.065% | 88965 | 33.103% | 105801 | 18.924% | 98291 | 10.483% |
| X-n876-k59 | 99299 | 119764 | 20.609% | 116617 | 17.440% | 119619 | 20.463% | 114333 | 15.140% | 99299 | 15.240% | 114016 | 14.821% | 107416 | 8.174% |
| X-n895-k37 | 53860 | 70245 | 30.421% | 65587 | 21.773% | 79018 | 46.710% | 64310 | 19.402% | 53860 | 96.818% | 69099 | 28.294% | 64871 | 20.444% |
| X-n916-k207 | 329179 | 399372 | 21.324% | 361719 | 9.885% | 383681 | 16.557% | 374016 | 13.621% | 329179 | 18.134% | 373600 | 13.494% | 352998 | 7.236% |
| X-n936-k151 | 132715 | 237625 | 79.049% | 186262 | 40.347% | 220926 | 66.466% | 190407 | 43.471% | 132715 | 50.654% | 161343 | 21.571% | 163162 | 22.942% |
| X-n957-k87 | 85465 | 130850 | 53.104% | 98198 | 14.898% | 113882 | 33.250% | 105629 | 23.593% | 85465 | 48.127% | 123633 | 44.659% | 102689 | 20.153% |
| X-n979-k58 | 118976 | 147687 | 24.132% | 138092 | 16.067% | 146347 | 23.005% | 139682 | 17.404% | 118976 | 16.711% | 131754 | 10.740% | 129952 | 9.225% |
| X-n1001-k43 | 72355 | 100399 | 38.759% | 87660 | 21.153% | 114448 | 58.176% | 94734 | 30.929% | 72355 | 82.677% | 88969 | 22.962% | 85929 | 18.760% |
| Avg. Gap | 29.658% | 16.796% | 26.408% | 19.607% | 30.202% | 18.795% | 12.303% |  |  |  |  |  |  |  |  |

We report in Table C.2 the results for large-scale CVRPLIB (Lima et al., ) with sizes greater than $500$ as done in MVMoE (Zhou et al., ). We report the original POMO (Kwon et al., ) alongside versions of MTPOMO and MVMoE that were initially trained on mixtures of only CVRP, OVRP, VRPL, VRPB, VRPTW, and OVRPTW for more than $3\times$ longer than our setting with all variants. Interestingly, training on all variants improves the generalization performance of MVMoE compared to the original setting, while it decreases the MTPOMO one (possibly due to the fact several more CVRP instances were sampled in MVMoE’s setting). Notably, RouteFinder vastly outperforms other SOTA single and multi-task RL baselines.

### C.4 T-SNE Visualization

We additionally study the representations learned from the model across different variants. Given their high dimensionality, we employ t-SNE (Van der Maaten & Hinton, ) to project them in 2D space. We employ the implementation from scikit-learn with the default perplexity of $30$ and use $100$ instances of size $100$ for each of the 16 variants of the main experiments. As shown in Fig. C.1, distinct clusters emerge at different model layers, indicating that the model progressively separates the problem variants with increasing depth. Early layers (Layer 1) exhibit high overlap between different variants, suggesting shared feature extraction. However, as we proceed to deeper layers (Layer 6), the clusters become more distinct, particularly for more complex variants such as OVRPB, VRPBLTW, and VRPBTW, signifying the model’s capacity to capture and differentiate intricate problem structures.

Figure: Figure C.1: Visualization of RouteFinder’s Transformer Encoder layers by t-SNE.
Refer to caption: x6.png

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. It seems there is not yet a neural method that could be trained on a single VRP variant or task and outperform the strong traditional method like LKH, HGS or SISR on that task, then what is the point in training a unified model across multiple tasks with much performance drop?
2. This paper is quite similar to 'RouteFinder: Towards Foundation Models for Vehicle Routing Problems, ICML Workshop'. And what is the major difference?
3. In the main body, only O, L and M are considered as the global attribute. However, in appendix, late time window and depot location are also considered as global attribute. Why there is such an inconsistence?
4. The authors claim that RMS Norm could speed up convergence, SwiGLU could help model the data relationship. However, those claims are not fully supported in the paper.
5. In Table 5.1, the objective value of VRPBLTW is 350.808. Please elaborate what happened to the model that leads to such an inferior result.
soundness: 2
strengths: 1. The introduction of RouteFinder as a foundation model for various VRP variants is a significant step forward, offering flexibility and reducing the need for specialized models for each variant. This can lead to more accessible and scalable VRP solutions across diverse scenarios.

2. The model employs a transformer-based encoder with Global Attribute Embeddings, improving the understanding and differentiation of VRP tasks, which translates to better adaptability and solution quality.

3.  Mixed Batch Training (MBT) allows RouteFinder to train on multiple VRP variants simultaneously, supporting diverse distributions and ensuring model stability. The Multi-Variant Reward Normalization further strengthens robustness, addressing reward scale differences effectively across VRP types.

4.  EAL enables fine-tuning of the pre-trained RouteFinder model to handle new VRP variants, providing a lightweight and promising solution for unseen attributes. This feature is especially advantageous in real-world applications, where new constraints may arise.

5. Extensive experimentation on 24 VRP variants showcases the competitive performance of RouteFinder, indicating its effectiveness and superior performance compared to recent baselines in multi-task VRP solutions.
summary: This paper proposes a unified approach called RouteFinder to model different Vehicle Routing Problem (VRP) scenarios using a transformer-based encoder and global attribute embeddings. This approach provides a scalable solution for diverse routing challenges. Mixed Batch Training (MBT) and Multi-Variant Reward Normalization are introduced to enable efficient training across multiple problem variants. Specifically, Multi-Variant Reward Normalization balances reward scales to ensure stable learning. Efficient Adapter Layers (EAL) enhance the model's adaptability, allowing it to handle new VRP variants with unseen attributes without full retraining. This paper includes extensive experiments that demonstrate the competitive performance of RouteFinder compared to state-of-the-art baselines.
weaknesses: 1.  Although RouteFinder demonstrates strong generalization across VRP variants, some performance trade-offs arise when compared to models designed for specific problem variants. Additional analysis could help address these trade-offs, especially in large-scale deployments.
2.  While MBT is an efficient training method, the paper could provide a more detailed examination of its limitations, particularly in cases of significantly imbalanced attribute distributions. Including more ablation studies might clarify MBT’s optimal conditions.

3.The ablation studies primarily focus on individual components. Exploring potential interactions among these components might offer insights into possible synergistic or conflicting effects, which could enhance the model's overall efficiency.

4. The use of transformers and attribute composition may make RouteFinder somewhat of a "black box." Adding interpretability methods, like attention visualization, could improve the practical usability and trustworthiness of the model by shedding light on its decision-making processes.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Could authors explain their rationale for selecting the mixed backhaul (M) constraint for zero-shot validation, rather than other practical constraints like multiple depots? Please discuss any other choices of validation task related to real-world VRP applications.

2. What is training time of the foundation model, MTPOMO, MVMoE? MTPOMO and MVMoE are retrained by the same data and same training resource, including dataset and training duration? 

3. How does the difference of AL and EAL influence outcome, as EAL keeping a predefined zero matrix seems not to influence AL that puts in the matrix in later phase? It's better to include empirical results or visualizations showing the effects of these different approaches at various stages of training.

4. Please discuss any potential trade-offs between the two methods and situations where one might be preferable over the other.
soundness: 3
strengths: The foundation model is better than MTPOMO, MVMoE and AL in uniform data. The normalization of rewards and layers makes a lot of sense to standardize the training of different vehicle routing problems that take on different features. Extending zero-shot and few-shot capabilities of a foundation model advances the frontier of large optimization models.
summary: A foundation model for vehicle routing problems was presented in the manuscript. Mixed training, global feature embedding in a transformer were proposed to increase the training advantage. The foundation model is better than MTPOMO, MVMoE and AL in uniform data, while the improvement in CVRPLIB is quite marginal.
weaknesses: The foundation model is not validated comprehensively. The zero-shot validation for a mere M constraint is not convincing as it is very relevant to constraints in training batch. More constraints in zero-shot validation are supposed to make a more solid work. The zero-shot didn't account for MTPOMO, MVMoE that were only compared in Table 1. Besides uniform data, the foudanation model is validated in CVRPLIB ignoring more practical vehicle routing problems like soloman VRPTW data. The improvement is incremental and still fall behind HGS-VRP.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. The design of Global Attribute Embeddings, such as Open and Limit attributes, is a notable feature. However, in MTPOMO and MVMoE, these attributes are already considered in decoder. What is the significance of redundantly including these embeddings in the encoder as well in this work?
2. The meaning of $l_l$ is unclear. Does $l_{rand(0,1)}<1/2$ represent random sampling of half of the attributes?
3. The explanation of why encountering different problem variants in a single batch leads to more stable training (as shown in Figure 4.3) is not well substantiated. Additional evidence is needed to support this claim.
4. The computation of the average reward $\bar{r}^{(k)}_t$ needs to be explained in more detail.
soundness: 2
strengths: 1. The authors propose a unified VRP environment that can handle multiple VRP variants efficiently, demonstrating a strong attempt at generalization in a complex combinatorial optimization domain.
2. The introduction of Efficient Adapter Layers (EAL) presents a lightweight yet powerful method to fine-tune the model for unseen attributes, which is crucial for practical applications that require adaptability.
summary: The paper introduces ROUTEFINDER, a foundation model designed to tackle various Vehicle Routing Problem (VRP) variants through a unified framework. It presents several key components, including a Transformer-based model architecture, Global Attribute Embeddings, Mixed Batch Training, and Efficient Adapter Layers for fine-tuning unseen attributes. While the paper proposes an interesting approach and demonstrates competitive experimental results across multiple VRP variants, there are concerns regarding the depth of innovation in the proposed methods and the clarity of explanations in some sections.
weaknesses: 1. Figure 4.1 lacks sufficient explanation. There is a need for a more detailed description of Figure 4.1. 
2. The proposed unified VRP environment and attribute dynamic composition approach, while having some differences compared to MTPOMO and MVMoE in handling different attributes, does not present substantial changes. In fact, MTPOMO and MVMoE can also achieve similar functionality.
3. The improvements to the Transformer architecture are mainly module-level substitutions, such as the use of RMS Normalization, SwiGLU activation, and FlashAttention. While these changes enhance training stability and convergence, they largely involve the application of existing techniques rather than introducing significant innovation. 
4. Lack of evaluation on large-scale.

---

confidence: 2
contribution: 2
initial_rating: 6
presentation: 3
questions: 1.How does the difference between AL and EAL affect the outcome, given that EAL, by maintaining a predefined zero matrix, doesn't seem to have an impact on AL, which later fills in the matrix during training? It would be helpful to include empirical results or visualizations that demonstrate the effects of these two approaches at different stages of training.

2.Could you discuss the potential trade-offs between the two methods and scenarios where one might be more advantageous than the other?
soundness: 2
strengths: 1.RouteFinder is a significant step toward a general model for VRP, reducing the need for separate models for each variant and improving scalability.

2.The use of Global Attribute Embeddings and a transformer-based encoder helps the model differentiate between VRP variants and adapt effectively.

3.Mixed Batch Training (MBT) improves stability by training on multiple variants at once.
summary: This paper introduces RouteFinder, a foundation model for multiple VRP variants, using a transformer-based encoder with Global Attribute Embeddings. Key innovations include Mixed Batch Training (MBT), Multi-Variant Reward Normalization, and Efficient Adapter Layers (EAL) for adaptability to new problem variants. While it shows competitive results across 24 VRP variants, some limitations remain in performance on certain benchmarks.
weaknesses: 1.Despite generalization, RouteFinder lags behind specialized models on certain VRP variants, such as LKH, HGS, or SISR. A deeper analysis of these trade-offs is needed.

2.The limitations of MBT in highly imbalanced datasets are not well explored. More ablation studies would be helpful to understand its optimal conditions.

3.There is a lack of discussion on how the different model components interact. Further exploration of these interactions would be valuable.

Meta-review: The submission proposes RouteFinder, a framework for training netural networks for Vehical Routing Problems (VRPs). Key claimed contributions include - 1) Transformer encoder and global attribute embeddings, 2) Mixed batch training, 3) Multi-variant reward normalization, and 4) efficient adapter layers for finetuning models for new problems.

The submission initially received ratings of 5, 5, 5, and one reviewer increased their rating to 6 after the rebuttal. The ACs have taken into account the concerns of the authors regarding certain reviews. 

Based on the reviews, discussions, and readings of all submitted material by the ACs, the claimed contributions fall short, as they heavily borrow from prior work:
- The transformer architecture is borrowed from prior work including the Llama LLM, and is not novel in its design. All the described components are commonly used (MHA, RMSNorm, SwiGLU, Flash attention, etc.) and there are no novel findings here.
- Mixed Batch training: Authors claim that prior work samples a particular instance of the VRP problem in each training batch, potentially hindering training. A natural baseline would be gradient accumulation across multiple batches, where each batch contains a single variant. Note that transformer architectures do not have batchnorms and different samples never interact with each other. By accumulating gradients across multiple varied batches, you can simulate a mixed batch. This was however not compared against.
- The efficient adapter layers (EAL) in this work expand linear projection layers by appending the matrix with 0s corresponding to the new dimensions. This is however, not novel. Zero initialization of new weights is a well known technique in neural network surgery and expansion/inflation.  

The above reasons greatly reduce the novelty of this work, bringing it below the bar for acceptance. The ACs do not find sufficient cause to overturn the negative consensus of the reviewers.

Decision: Reject