RouteFinder: Towards Foundation Models for Vehicle Routing Problems

Authors: Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Junyoung Park, Kevin Tierney, Jinkyoo Park
Primary area: foundation or frontier models, including LLMs
Keywords: Vehicle Routing Problems, VRP, Foundation Models, Neural Combinatorial Optimization

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 48 VRP variants show RouteFinder achieves competitive results. Our code is openly available.

Decision: reject
Reviewer scores: 5, 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1730454419051

thread_type:
official_review

<thread_object>
creator: reviewer_p8ah

<content>
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.

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.

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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730607681204

thread_type:
official_review

<thread_object>
creator: reviewer_ktqa

<content>
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.

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730650291004

thread_type:
official_review

<thread_object>
creator: reviewer_kzpo

<content>
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.

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730681676224

thread_type:
official_review

<thread_object>
creator: reviewer_x8vs

<content>
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.

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732523876376

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We would like to thank all reviewers and the Area Chair for their time and effort in evaluating our work!

We are pleased to see that the reviewers recognized RouteFinder as a meaningful step forward in foundation models for VRPs. Specifically, the reviewers highlighted that RouteFinder is a **significant advancement** in modeling VRP variants (`X8vs`, `KZPo`) representing a **strong attempt at generalization** (`kTqa`), introduces **novel methodologies** such as Mixed Batch Training (MBT) and Efficient Adapter Layers (EAL) (`X8vs`, `KZPo`, `p8aH`), and demonstrates **strong empirical results** across a wide range of VRP variants (`X8vs`, `kTqa`, `p8aH`). 

During the rebuttal period, we carefully considered all reviewers' feedback and conducted **extensive new experiments**:

1. The unified VRP environment can now also model multi-depot VRP, **increasing the number of variants from 24 to 48**, making RouteFinder the first neural approach in the literature to model this many variants
2. **New EAL experiments** evaluating zero-shot and fine-tuning performance, including both previous and new multi-depot variants, with a detailed analysis of how the model's performance evolves over fine-tuning epochs
3. **Ablation study on Transformer Encoder** demonstrating the importance of each component
4. **MBT experiments on imbalanced attribute distributions** demonstrating how MBT is important especially for minority samples
5. **New experiments on out-of-distribution attribute values** that show how RouteFinder can outperform  models trained specifically for a single-variant 
6. Experiments on **EAL finetuning on single-variant models** that show RouteFinder achieves better performance in finetuning to unseen variants compared to single-variant models
7. New **t-SNE latent space experiments** demonstating the importance of the Global Attribute Embeddings 
8. More **MBT experiments and plots** that showcase increased training stability and better performance

We have revised multiple sections of the manuscript in response to the reviewers' constructive feedback. For convenience, the new and updated content has been highlighted in blue in the revised PDF.

---

We hope our responses can address all concerns, and we welcome further discussions if any point is unclear.

RouteFinder Authors
</content>
</thread_object>

</thread>
<thread>
creation date:
1733119692627

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Request for Feedback

comment:
Dear Reviewers,

Thank you all for your thoughtful and constructive reviews of our submission. We deeply appreciate the time and effort you have dedicated to providing valuable feedback.

In response to your comments, we have worked hard and made substantial updates to the paper, including conducting extensive additional experiments, such as expanding the paper to 48 VRP variants and providing further clarifications that directly address the concerns raised. We believe these revisions significantly strengthen the work, and we hope that the changes now address the issues raised in your reviews.

Given the extent of the revisions, we kindly ask that you take a moment to re-evaluate the revised version of the paper. If the updates have addressed your concerns, we would greatly appreciate it if you could reconsider your evaluation. Your feedback is crucial in ensuring a fair and thorough review process, and we want to ensure the paper is assessed based on its updated and improved version.

If there are any remaining concerns or if additional clarification is needed, we are more than happy to provide further details or make any necessary adjustments.

Thank you once again for your time, effort, and continued support in this process.

Best regards,

RouteFinder Authors
</content>
</thread_object>

</thread>
<thread>
creation date:
1733313547988

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Final Message

comment:
We thank the reviewers once more for their initial feedback. We will provide a summary of our paper and the rebuttal.


## RouteFinder's Core Contributions

RouteFinder is a foundation model for vehicle routing problems (VRP). Our contributions include:

1. **Unified Framework for Multiple VRP Variants:** We introduce a general framework that can solve various VRP variants by handling any number of attributes, making it applicable to a wide range of problem settings.
   
2. **Transformer-Based Architecture with Global Attribute Embeddings:** Our approach uses a modern Transformer architecture and Global Attribute Embeddings, allowing the model to understand and differentiate between VRP variants more effectively.

3. **Novel RL Techniques:** We propose two novel techniques—**Mixed Batch Training (MBT)** and **Multi-Variant Reward Normalization**—to ensure stable and effective training across multiple VRP variants.

4. **Efficient Adapter Layers (EAL):** We introduce a lightweight yet powerful mechanism for fine-tuning pre-trained models to tackle new variants with unseen attributes.

We evaluated RouteFinder across 48 VRP variants -- the first neural model to do so -- demonstrating that it significantly outperforms recent multi-task learning models.


## Rebuttal Remarks

During the rebuttal period, we carefully considered all comments and conducted extensive additional experiments to address the concerns and provided further evidence of our RouteFinder's effectiveness. 

While we believe we have fully addressed the reviewers' concerns, with extensive experiments and studies that added 10 additional pages to our manuscript, doubled the number of VRP variants, and took almost 2 weeks of full-time work, we regret that 3 out of 4 reviewers did not engage in discussions. While we thank the only reviewer who replied, X8vs, for his/her reply, we respectfully disagree with the assessment that beating the HGS performance for a neural network is the criterion of acceptance. We hope you understand our position.

---

We respectfully request that the reviewers reconsider their decision in light of the clarifications and additional evidence provided. We hope for a fair reevaluation of our work.


Best Regards,

RouteFinder Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.