RouteFinder: Towards Foundation Models for Vehicle Routing Problems

Dear Reviewer p8aH,

We noticed that the review you provided seems to be for a different paper. Could you kindly share your review content specific to our submission?

Thank you very much for your time and effort in helping us improve our work.

Best regards, RouteFinder Authors

Thank you for providing the updated review. We will provide detailed responses, where W denotes weaknesses and Q denotes questions.

W1. Performance trade-offs when compared to models designed for specific problem variants are not studied.

Indeed, training a model on a single variant may yield better results in-distribution. However, RouteFinder is much more robust than models trained on single variants when evaluated on out-of-distribution cases. For instance, in large-scale CVRPLIB (Table D.8 in Appendix), RouteFinder is much better than POMO trained specifically for CVRP. We added new experiments in Section D.4, where we compare the single-variant POMO trained on specific variants such as CVRP, VRPL and VRPTW and compare the results with RouteFinder on out-of-distribution cases for capacities, time windows, and distance limits. Interestingly, we find that while POMO trained on specific variants, as expected, can perform better close to the training distribution, it performs worse out-of-distribution, whereas RouteFinder demonstrates exceptional generalization.

W2. Missing analysis on MBT limitations for significantly imbalanced distributions.

To address this, we ran new experiments to analyze MBT's performance under significantly imbalanced attribute distributions available in Section D.2 of the Appendix. Using our RouteFinder model with and without MBT, we ran training runs at different sampling probabilities of time-window attributes $p_\text{tw} = \{ 0.5, 0.25, 0.10\}$ to examine different levels of imbalance. The results (Figure D.5) show that as $p_\text{tw}$ decreases, convergence slows for challenging variants like VRPTW, while majority-dominant variants (e.g., CVRP) converge faster. Crucially, MBT stabilizes training across all settings, particularly benefiting minority variants by mitigating instability and ensuring smoother, faster convergence. This demonstrates that MBT is a robust strategy for improving training stability and convergence in imbalanced scenarios.

W3. Ablation studies do not show the interaction among components.

Figure 5.1 shows the ablation studies of several RouteFinder components alongside a sensitivity analysis on Reward Normalization. All the proposed components significantly improve the performance of our model. We also added additional ablation studies, especially regarding the Transformer Encoder components in Appendix D.1. Here, we compare RouteFinder with no SwiGLU and no RMSNorm, with SwiGLU only, with RMSNorm only, and with both (full Transformer Encoder). The results demonstrate that the Transformer Encoder performs best.

Q1. How do AL and EAL differ?

EAL differs from AL because it keeps the first initial $k$ linear projection rows the same, hence inheriting them from the pretrained model. To ensure compatibility with a new task with $k+l$ raw features (with $l$ new features) we add $l$ new rows initialized with zeros. This has an important property. Suppose we trained the model on a multitude of variants, including CVRP. If we use AL, we lose the information of the pretrained linear projections for CVRP, hence the model will not be able to construct CVRP solutions unless finetuning is applied. On the contrary, EAL keeps this information, which can be transferred for new tasks - for example, for a multi-depot VRP, we would like to keep the learned information about depot locations, since they are important for VRPs.

This means that EAL, in practice, can keep the zero-shot performance of a pretrained model when applied to a new task. We added more evidence for this phenomenon throughout new experiments in Tables D1 to D3, and also show the importance of EAL in new Figure D.6 across epochs where it can be seen how EAL yields fast finetuning to new variants.

Q2. What are the potential trade-offs between AL and EAL?

AL might be preferable to EAL only if the new tasks do not share any raw feature with the previously seen tasks. However, in the context of VRPs, this would rarely happen since features like locations and demands are required in the very definition of VRPs. Thus, in Foundation Models for VRPs, EAL finetuning would almost always be preferable to AL.

We thank you for your effort and for providing constructive feedback in reviewing our paper! We will provide detailed responses, where W denotes weaknesses and Q denotes questions.

W1. Insufficient explanation for Figure 4.1.

We agree that our previous caption was very brief and potentially insufficient. We provided a better explanation in the revised paper that we report here: "Overview of RouteFinder. The unified VRP environment is used for generating data and performing rollouts (Section 4.1). Our Transformer-based encoder (Section 4.2.1) is employed to process node and global embeddings (Section 4.2.2) of problem instances. During training, we sample multiple variants in the same batch (Section 4.3.1) whose multi-task reward is then normalized (Section 4.3.2). Efficient Adapter Layers (EAL) can be employed for efficient fine-tuning to new variants (Section 4.4)".

W2. RouteFinder does not present substantial changes.

RouteFinder is an end-to-end approach that greatly enhances existing models. Our contributions go beyond a single change; they span the entire pipeline, from the environment setup to fine-tuning, and include several novel components. In particular: 1) Environment: new unified VRP environment 2) Model: new Transformer Encoder and Global Attribute Embeddings 3) Training: new Mixed Batch Training and Multi-Variant Reward Normalization 4) new Efficient Adapter Layers finetuning method for VRPs. During the rebuttal, we also added several new experiments, including doubling the number of variants modeled by the unified VRP environment: as such, our RouteFinder is the first neural method to the best of our knowledge to model 48 VRP variants, while previous approaches as MTPOMO and MVMoE modeled 16. Finally, we remark that our contributions achieve SOTA in learning foundation models for VRPs.

W3. The improvements to the transformer architecture employ existing techniques.

The Transformer Encoder layers improvements are inspired by recent research in LLMs. In this sense, the single components are not our innovation. However, we would like to note that RouteFinder is the first model, to the best of our knowledge, to bring such components to learned methods for VRPs — that mostly still use architectures introduced several years ago — and we believe our adoption will advance this field. Moreover, we studied the combination of these components in new experimental results, which are available in Appendix D.1. Single components such as the SwiGLU MLP might actually degrade performance initially, as shown in Figure D.2, if not coupled with, e.g., the RMSNorm. Their combination reveals synergistic behavior, which greatly improves baseline encoder performance and motivates the development of new Transformer Encoder layers.

W4. Lack of evaluation on large-scale.

We studied the large-scale real-world CVRPLIB with up to 1000 nodes in Appendix D.5. Notably, RouteFinder not only outperforms other SOTA multi-task RL baselines but also single-task RL solvers dedicated to the CVRP, underpinning the importance of training on a diverse set of tasks for generalizing to larger scales.

We thank you for your effort in reviewing our paper and providing insightful feedback! We will provide detailed responses, where W denotes weaknesses and Q denotes questions.

W1/Q1. Why did you choose mixed backhauls to evaluate unseen variants? Adding new variants such as multi-depots would make for a more solid work.

The rationale behind initially choosing mixed backhauls is that mixed backhauls substantially change the solution generation process: The model needs to keep track of the available backhaul load at each step, i.e., the difference between the vehicle capacity and the used backhaul capacity and carefully plan to have enough capacity to load the backhauls.

However, we do agree with you that adding new variants would make for a much more interesting experiment. Thanks to your suggestion, we have added multi-depot variants during the rebuttal, doubling the number of variants studied in our paper from 24 to 48 (see updated Table A.1, with updated environment details throughout Appendix A). To the best of our knowledge, ours is the first method whose environment and model can represent this many VRP variants.

We then studied both the zero-shot generalization and finetuning performance across three different settings: 1) unseen mixed backhauls (MB), which is the setting from the main text and adds 8 new variants 2) unseen multi-depots (MD), which adds 16 new variants and 3) unseen mixed backhauls and multi-depots (MB+MD) which is the hardest setting for zero-shot generalization and finetuning, adding 8 additional variants. In total, from the original 16 variants we pretrained our models on, we generalize and finetune to 32 new variants.

The newly added Appendix D.3 shows our results. RouteFinder models perform the best in zero-shot generalization across all experiments; moreover, EAL finetuning achieves the same zero-shot performance as the backbone RouteFinder model thanks to the zero-padded initialization, while AL does not due to the introduction of untrained embedding layers. Notably, experiments with multiple depots are much harder than mixed backhaul variants since they require the model to understand multiple starting (and returning) point locations and to schedule vehicle assignments to their respective depots efficiently. EAL performs the best across all variants in finetuning performance. Remarkably, EAL’s performance compared to AL and retraining a model from scratch is more prominent with the increasing difficulty of the finetuning task from MB to MB+MD, indicating it is a suitable method for efficient deployment in finetuning to new tasks.

W2. MTPOMO and MVMoE were not compared in zero-shot.

We have added the zero-shot results for MTPOMO and MVMoE on new tasks according to our above answer to W1 in Tables D1, D2 and D3. Overall, RouteFinder shows the best zero-shot generalization performance on unseen tasks.

W3. Lacking comparisons in non-uniform data.

As you mentioned, we compared RouteFinder and multi-task as well as the single-variant POMO in CVRPLIB, which demonstrates exceptional generalization ability of our model across real-world large-scale datasets. We also added new out-of-distribution comparisons for single-variant POMO, multi-task baselines, and RouteFinder models across three different scenarios: 1) unseen values of capacities 2) unseen values of time windows and 3) unseen values of distance limits. Overall, we can see that RouteFinder is robust, and its advantage compared to single-variant models is more pronounced the further we get from the training distribution.

W4. The model still falls behind HGS.

This is true, at least for the studied VRP variants. However, a motivation for our work is that not all VRP variants have strong traditional solvers available. HGS results from decades of VRP research on heuristic methods, and outstanding efforts are required to model new variants outside of the studied ones. RouteFinder is a promising direction because it is not only generally faster but can also automatically discover heuristics, unlike traditional solvers, essentially transforming a complex VRP into a data science problem. Given its strong finetuning ability, we expect practitioners to be able to model new VRPs that cannot be easily modeled by traditional solvers. Another motivation is that usually, especially on larger scales, HGS is much slower than learned VRP solvers, which motivates the creation of models such as ours. Neural combinatorial optimization is a quickly evolving field, and we believe that learning-based methods will eventually surpass traditional solvers and/or work alongside them to solve complex VRPs. In this sense, we believe RouteFinder is a notable step towards this final goal.

We sincerely thank you for your time and thoughtful feedback in reading our paper! We will provide detailed responses, where W denotes weaknesses and Q denotes questions.

W1. Performance trade-offs when compared to models designed for specific problem variants are not studied.

Indeed, training a model on a single variant may yield better results in-distribution. However, RouteFinder is much more robust than models trained on single variants when evaluating out-of-distribution cases. For example, on large-scale CVRPLIB instances (Table D.8 in Appendix), RouteFinder is much better than POMO trained specifically for CVRP. We added new experiments in Section D.4, where we compare the single-variant POMO trained on specific variants such as CVRP, VRPL and VRPTW and compare the results with RouteFinder on out-of-distribution cases for instances with capacities, time windows, and distance limits. Interestingly, we find that while POMO trained on specific variants can perform better close to the training distribution as expected, it performs worse out-of-distribution, whereas RouteFinder demonstrates exceptional generalization.

W2. Missing analysis on MBT limitations for significantly imbalanced distributions.

To address this, we conducted new experiments to analyze MBT's performance under significantly imbalanced attribute distributions available in Section D.2 of the Appendix. Using our RouteFinder model with and without MBT, we ran training runs at different sampling probabilities of time-window attributes $p_\text{tw} = \{ 0.5, 0.25, 0.10\}$ to examine different levels of imbalance. The results (Figure D.5) show that as $p_\text{tw}$ decreases, convergence slows for challenging variants like VRPTW, while majority-dominant variants (e.g., CVRP) converge faster. Crucially, MBT stabilizes training across all settings, particularly benefiting minority variants by mitigating instability and ensuring smoother, faster convergence. This demonstrates that MBT is a robust strategy for improving training stability and convergence in imbalanced scenarios.

W3. The paper does not show the interaction among components.

Figure 5.1 shows the ablation studies of several RouteFinder's components alongside a sensitivity analysis on Reward Normalization. All the proposed components significantly improve the performance of our model. We also added additional ablation studies, especially regarding the Transformer Encoder components in Appendix D.1. Here, we compare RouteFinder with no SwiGLU and no RMSNorm, with SwiGLU only, with RMSNorm only, and with both (full Transformer Encoder). The results demonstrate that the Tranformer Encoder performs best (more in the answer to Q4).

W4. Issues in interpretability due to transformers.

We agree that understanding a model’s decision-making process is critical for practical usability and trustworthiness. While we currently focus on addressing the core research challenges of learning and optimization in complex combinatorial tasks, integrating interpretability methods like attention visualization is indeed a promising direction. To shed some light on this, we added new experiments visualizing the hidden space via t-SNE between transformer layers across all models, to understand how RouteFinder and previous models understand different attributes (Figures D.7 and D.8 in Appendix). We note that RouteFinder exhibits more complex patterns the deeper the layers. Interestingly, when analyzing the hidden space on a per attribute basis, our model yields well-defined, tightly grouped, and distinct clusters on all variants, which is a strong indicator of its capability to generalize and specialize effectively in solving diverse VRP variants. For example, in contrast to the baselines, RouteFinder effectively separates time window variants into two distinct clusters — those with open routes and those without — enabled by the Global Attribute Embeddings.