SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy

We thank the reviewer for acknowledging that our work addresses a practical problem that interests the community and that the extensive experiments are convincing. We hope our response adequately addresses the remaining questions.

[W1: Handling Spatial-Temporal characteristics]: We thank the reviewer for recommending the discussion of Graph2Route [1] and DRL4Route [2]. Both works have presented realistic scenarios of spatial-temporal dynamics of routing problems, and we will add their discussion in the final version. The MTVRP and MTMDVRP scenarios, in their current forms, are focused more on fixed locations governed by spatial coordinates since they reflect the majority of standard vehicle routing problems for effective multi-task model development. In order to handle more complex temporal distributions, it is possible to adapt similar encoding architectures shared in Graph2Route and DRL4Route. Both works discuss the evolution of edge features (such as travel time) as the problem is progressively solved, and present encoding methods such as GRU to capture such nuances. Indeed, this adds realism to the problem scenario, which is an important and exciting future work to expand the capability of SHIELD towards foundation optimization models for VRPs. At the same time, SHIELD works on problems with multiple constraints such as time-windows (e.g. VRPTW, VRPLTW etc), suggesting that it can handle some form of temporal characteristics as well.

Alternatively, orthogonal works, such as [3], utilize POMO-styled architectures to encode the time-dependent VRP, where travel times on edges change as the solution construction progresses. This suggests that it is highly possible to integrate such encoding architectures into SHIELD to encode temporal variations in the data.

[Q1: Compute saved during inference]: Thank you for the question! To answer this, we compare MVMoE-Deeper with SHIELD, as both contain the same number of decoder layers, where SHIELD only allows 10% of tokens while MVMoE-Deeper allows 100% for processing. Table 4 in Appendix F shows the number of parameters, floating operations (FLOPs) and runtime of the models. From the results, SHIELD has almost 10 GFLOPs less and is 30% faster than MVMoE-Deeper during inference, albeit with slightly more parameters. Additionally, MVMoE-Deeper uses ~45Gb of memory, while SHIELD only uses ~6Gb during inference, reducing 87% of memory costs. Finally, MVMoE-Deeper is untrainable on the MTMDVRP100, whereas SHIELD is able due to its sparse property in the decoder. We will clarify the computational savings more explicitly in the revised paper.

[Q2: Scaling laws]: We agree that exploring the scaling laws of learned models would yield valuable insights for the community. However, we would like to clarify that this work focuses on developing more generalizable multitask models, which still remains at an early stage toward building foundation neural combinatorial optimization (NCO) models. As such, investigating scaling laws meaningfully would require training across larger datasets and model scales (e.g., 0.1B, 1B, 10B, 100B parameters), which is beyond the scope of this paper and the time constraints of the rebuttal, as such training demands substantial GPU resources over weeks. We will explore this direction by training models with varying sizes and data availability, and include further discussion in the revised paper. Our work represents a concrete step toward architectures that may underpin future foundation NCO models.

Nevertheless, we opt to discuss the intuition of scaling laws for the inference stage of a trained model. For NCO solvers, we can allocate more test time to perform sampling and find better solutions during inference. Due to time constraints, we reduce the number of test instances to 100 instances per problem and performed inference with sampling widths 1x, 10x, 50x, and 100x. We plot the performance of the various widths here. As shown, as we increase the sampling width, the general performance of the model increases (lower gap is better) in a logarithmic fashion. This suggests that while we can allocate more test time for inference, its effectiveness eventually saturates.

[Q3: Influence of $\beta$]: Sorry for the confusion. $\beta$ controls the number of tokens (or nodes) that is processed by a MoD layer. In Table 2 of the main paper, we highlight how varying $\beta$ influences the performance of the solver. Essentially, increasing the number of tokens processed improves the in-task in-distribution performance at the expense of generalization.

[1] Graph2Route: A Dynamic Spatial-Temporal Graph Neural Network for Pick-up and Delivery Route Prediction. SIGKDD, 2022

[2] DRL4Route: A Deep Reinforcement Learning Framework for Pick-up and Delivery Route Prediction. SIGKDD, 2023

[3] SED2AM: Solving Multi-Trip Time-Dependent Vehicle Routing Problem using Deep Reinforcement Learning. TKDD, 2025

We thank the reviewer for their positive recognition of the work's novelty, effectiveness, practical values, and thorough experimental validation. We hope our responses with new experiments address the remaining concerns.

[W1: Realistic Setup]: While we present a national-level business expansion scenario, the distributional variations studied are also representative of city-level patterns. The national-level data serves as a realistic proxy to show SHIELD’s generalization ability. Our model and training process are agnostic to specific distributions. In practice, a company can train SHIELD on data from existing cities and apply it to new ones, where distributional shifts may occur. Given SHIELD’s flexibility in handling such variations, it is well-suited for the scenario noted by the reviewer.

To illustrate our point that the proposed architecture is inherently generic, we refer the reviewer to Table 1 of the main paper and Table 11 of Appendix O. For Table 11, we trained the model on the Uniform distribution (the MTVRP scenario). The results show that even in a different distribution than the MTMDVRP, SHIELD presents itself as a superior model.

[W2: Comparison to Non-neural Solvers]: Sorry for the confusion, yes, the results are benchmarked with classic solvers. Similar to [3][4], we solved the test instances with known solvers in HGS (for CVRP and VRPTW) and Google's OR-tools (for the rest). This allows us to compute the optimality gap of each solver compared to the best-performed non-neural solvers (run with reasonably longer solving times typical in industrial applications). Please see updated Table 1 here that includes the solver's performance across tasks and distributions.

[W3: Public Code]: We plan to release our code and data upon acceptance of this paper after potential intellectual property review by the employer of our authors. Nevertheless, we have provided detailed descriptions of our architecture in Appendix I to support reproducibility.

[Q1: Scaling to large instances]: Thank you for the question. The primary contribution of this paper is the introduction of a novel MTMDVRP setup and the SHIELD model, which significantly improves performance on small-scale instances. This serves as a foundational step toward future research on scaling to larger problem sizes. For example, several existing techniques orthogonal to our contributions can be integrated to enhance the scalability, such as self-improvement learning [1], and divide-and-conquer strategies (e.g. UDC[2]), all requiring a backbone neural solver for small-scale optimization.

Nevertheless, we have evaluated SHIELD and the baselines on the CVRPLib Set-X containing CVRP instances of larger sizes. These instances range from 101 nodes to 1001 nodes. Tables 7 and 8 in Appendix L showcases their results. In general, SHIELD exhibits stronger generalization capabilities compared to the others.

Additionally, we generated and labelled MTMDVRP200 datasets and performed inference using the trained MTMDVRP100 models. The results below illustrate that our approach is significantly more robust when generalizing beyond the trained problem size.

[Q2: Complex constraints]: In this work, we extend generalization beyond the 16 VRP variants (from [3] and [4]) to include distributional shifts, building upon the POMO framework. The additional constraints, as suggested by the reviewer, can also be solved by POMO-styled neural solvers, such as multi-depot [5] and heteogeneous fleet [6]. This is orthogonal to our focus and represent valuable directions for future work where we can train SHEILD on even more tasks in MTMDVRP setup. To our knowledge, SHEILD is the first to generalize across both task and distribution simultaneously.

[1] Boosting Neural Combinatorial Optimization for Large-Scale Vehicle Routing Problems. ICLR, 2025

[2] UDC: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems. NeurIPS, 2024

[3] Multi-task learning for routing problem with cross-problem zero-shot generalization. SIGKDD, 2024

[4] Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. ICML, 2024

[5] Multi-type attention for solving multi-depot vehicle routing problems. ITS, 2024

[6] Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem. Cybernetics, 2021

We thank the reviewer for the positive comments and for recognizing our paper as solid and easy to follow, with an interesting use of MoD to reduce computational overhead. We hope our responses with new results address the remaining questions.

[Q1: Why MoE Encoder]: Insightful question! In this paper, we find that MoD is more beneficial in the decoder as opposed to the encoder. Meanwhile, an existing work [3] (which only studies MTVRP instead of MTMDVRP in this paper) provides evidence that MoE is more effective in the encoder than in the decoder. We believe this aligns with the distinct functional roles of the encoder and decoder in NCO models:

• In MTMDVRP, the encoder processes diverse multi-task contexts and learns meaningful representations from various task contexts which feature combinations of constraints. For example, CVRPTW combines capacity and time window constraints, while CVRPBLTW further adds backhaul and linehaul constraints. MoE is well-suited for the encoder as it leverages specialized expert subnetworks to handle the shared and combinatorial patterns in the input data.
• In contrast, the decoder in MTMDVRP is focused on sequential solution construction with adaptive computation. While some node selections are straightforward, others require finer granularity and greater computational/reasoning capacity -- especially when dealing with clustered distributions or complex constraint-distribution interactions in MTMDVRP. Thus, dynamic control over depth and computation is essential. MoD naturally addresses this need by adaptively allocating resources across decoder layers.
• Together, their synergy enhances the model's ability to capture context-dependent, adaptive fine-grained decisions for MTMDVRP.

To verify our claims, experiments in Table 6 of Appendix J investigate the impact of MoD in the encoder. Even though we double the number of MoD encoder layers, the network is unable to learn effective representations for the problems.

[Q2: Why not Linear Attention]: We agree with the reviewer that there are multiple alternate approaches for reducing the computational costs, such as linear attention [1]. It is an important direction for future work where such sparse attention methods could further improve the scalability of our SHIELD model. However, to the best of our knowledge, such approaches have not yet been shown to be effective for learning multi-task NCO solvers. This may be because, while sparse attention may work for simpler VRPs (e.g., TSP, CVRP), it can struggle with more complex variants (e.g., OVRPBLTW), where capturing complex dependencies and constraints with a simplified attention mechanism remains nontrivial, particularly in our MTMDVRP setting.

To further support our claims, we add new results by comparing with a recent model, INViT [2], that employs sparse attentions, extending it from simple VRP variants to the more complex MTMDVRP setting. Essentially, INViT proposes to update embeddings by only paying attention to the current node's k-Nearest Neighbors (k-NN). Such a scheme is similar to ours, where the number of interactions amongst the nodes is reduced during decoding. However, a key difference is that in INViT, the reduction is based on a heuristic -- the k-NN nodes, while in SHIELD, we opt to learn which nodes to focus on based on MoD. We train INViT on our dataset and settings; our results are shown in the following table. Here, we see that SHIELD outperforms INVIT. One main reason is that the sparsity in INViT arises from selecting the k-NN nodes based on spatial coordinates, which is potentially unsuitable for MTMDVRP settings. Thus, such an approach prunes possibly important nodes to interact with, restricting the model's capabilities. In contrast, SHIELD offers two key advantages for MTMDVRP: 1) We reduce computational overhead by focusing on a smaller number of nodes; 2) We learn to prioritize task-relevant nodes for decision-making. These features make SHIELD significantly stronger and more generalizable.

[1] Linear attention is (maybe) all you need (to understand transformer optimization). ICLR, 2024

[2] INViT: A generalizable routing problem solver with invariant nested view transformer. ICML, 2024

[3] Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. ICML, 2024

We would like to thank the reviewer for the positive review and recognizing the depth of experiments done to show the benefits of the proposed architecture. We hope our following responses will further address the reviewer's concerns about the work.

[W1: Contributions of Clustering Nodes/MoE/MoD]: While we agree that this paper is not for proposing new general clustering/MoE/MoD techniques, our work represents the first to reveal and verify their unique synergy towards learning foundation models for neural combinatorial optimization (NCO), which holds significant value in both academia and industrial applications.

Specifically, inspired from the VC-dimension perspective, we first pose a key research question for neural VRP solvers: can generalizable multi-task solver be learned by regularizing the model through (1) dynamic compute allocation and (2) parameter size control? We thus bring the MoD and the adaptive clustering approaches to this field which respectively regulates these two aspects. To our knowledge, we are the first to explore these techniques in NCO, showing insights to the community on how dynamic node selection per decoder layer and adaptive clustering enhance both efficiency and generalization.

Moreover, our contribution extends to the introduction and study of the more realistic multi-task, multi-distribution VRP setting (MTMDVRP), which opens new directions and bridges the gap to real-world applications. Up till recently, the NCO community has been focused on single-task solvers on the uniform distribution. The two most recent works in [1] and [2] first addressed the possibility of constructing generalized multi-task models (but still on the uniform distribution). This is similar to how traditional solvers behave - the same solver can be used to solve multiple different tasks by introducing various constraints. A neural version of such a solver is highly important and intriguing to the NCO and OR community, as they are capable of extremely fast problem solving by exploiting modern architecture, and the learning aspect provides possible advantages by exploiting underlying structure. Pushing further toward practical relevance, our work is the first to evaluate multi-task neural solvers under cross-distribution generalization by introducing the MTMDVRP setup, which better reflects real-world settings (see Table 9 in Appendix M). We further demonstrate that our proposed SHIELD architecture enables the learning of robust foundational neural solvers for solving the introduced MTMDVRP.

[W2: Generalization to Larger Instances]: Thanks for suggesting the evaluation on larger problem sizes. We evaluated all models on the CVRPLib Set-X, which contains CVRP instances ranging from 101 nodes to 1001 nodes. The results can be found in Tables 7 and 8 of Appendix L. Additionally, we would like to direct the reviewer to our response to Reviewer yZkq regarding scaling to larger instances. We performed additional experiments of MTMDVRP200 using our trained MTMDVRP100 models. Both results show that SHIELD exhibits stronger generalization capabilities than the other baselines.

[Q1: Performance on MDVRP]: We thank the reviewer for the insightful observation on whether the observation of SHIELD's performance is unique to the MTMDVRP scenario. We observe in our experiments that in both the Multi-Task VRP (MTVRP) and Multi-Distribution (MDVRP) case, SHIELD is still the clear leader. For MTVRP, Table 11 in Appendix O highlights the case where the underlying distribution is Uniform in nature, similar to the works done in [1] and [2]. From Table 11, it is clear that SHIELD has a sizable advantage over its counterparts, especially so when generalization across tasks is required. In the MTVRP100 case, it has a large gap of ~1.2% over the current known state-of-the-art MVMoE.

Additionally, Table 9 in Appendix M showcases the importance of having varied distributions. Here, we trained all models on the MTVRP scenario (meaning we only draw data from the Uniform distribution) but apply them to the same test set in the MTMDVRP scenario (USA, JA, BM are considered "in-distribution", while the rest are considered "out-distribution"). We see that the model's performance on the varied distributions have degraded as compared to Table 1 in the main paper, highlighting the importance of exposing the models to varied distributions in training.

As for MDVRP, Table 10 in Appendix N displays our experiments for this scenario. In this case, we fix the task to CVRP but retain the various distributions. We find that SHIELD still shows a sizable performance improvement over its fellow benchmark models. This exemplifies that our approach is not specific to only the MTMDVRP scenario.

[1] Multi-task learning for routing problem with cross-problem zero-shot generalization. SIGKDD, 2024

[2] Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. ICML, 2024