SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy
Authors: Yong Liang Goh
Zhiguang Cao
Yining Ma
Jianan Zhou
Mohammed Haroon Dupty
Wee Sun Lee
Venue: ICML 2025 poster (2025)
Keywords: vehicle routing problem
learning to optimize
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We present SHIELD, a model that leverages sparsity and hierarchy for the more realistic Multi-Task Multi-Distribution VRP setting, a step towards foundation models for routing problems.

Abstract: Recent advances toward foundation models for routing problems have shown great potential of a unified deep model for various VRP variants. However, they overlook the complex real-world customer distributions. In this work, we advance the Multi-Task VRP (MTVRP) setting to the more realistic yet challenging Multi-Task Multi-Distribution VRP (MTMDVRP) setting, and introduce SHIELD, a novel model that leverages both *sparsity* and *hierarchy* principles. Building on a deeper decoder architecture, we first incorporate the Mixture-of-Depths (MoD) technique to enforce sparsity. This improves both efficiency and generalization by allowing the model to dynamically select nodes to use or skip each decoder layer, providing the needed capacity to adaptively allocate computation for learning the task/distribution specific and shared representations. We also develop a context-based clustering layer that exploits the presence of hierarchical structures in the problems to produce better local representations. These two designs inductively bias the network to identify key features that are common across tasks and distributions, leading to significantly improved generalization on unseen ones. Our empirical results demonstrate the superiority of our approach over existing methods on 9 real-world maps with 16 VRP variants each.

SHIELD: Multi-task Multi-distributio Vehicle Routing Solver with Sparsity and Hierarchy
Yong Liang Goh 1234 Zhiguang Cao
Yining Ma
Jianan Zhou?
Mohammed Haroon Dupty' Wee Sun Lee!
Abstract
1. Introduction
Combinatorial optimization problems (COPs) appear in many real-world applications, such as logistics (Cattaruzza et al., 2017) and DNA sequencing (Caserta & VoB, 2014), and have historically attracted significant attention (Bengio et al., 2021). I). A key example of COPs is the Vehicle Routing Problem (VRP), which asks: Given a set of customers, what is the optimal set of routes for a fleet of vehicles to minimize overall costs while satisfying all constraints? ? Traditionally, they are solved with exact approximate solvers. However, these solvers rely heavily expert-designed heuristic rules which limit its efficiency. Recently, the emerging Neural Combinatorial Optimization (NCO) community has been increasingly focused on developing novel neural solvers for VRPs based on deep (reinforcement) learning (Kool et al., 2018; Kwon et al., 2020; Bogyrbayeva et al., 2024). These solvers learn construct solutions autoregressively, improv- ing efficiency and reducing the need for domain knowledge.
Recent advances toward foundation models for routing problems have shown great potential of a unified deep model for various VRP variants. However, they overlook the complex real-world customer distributions. In this work, we advance the Multi-Task VRP (MTVRP) setting to the more realistic yet challenging Multi-Task Multi- Distribution VRP (MTMDVRP) setting, and in- troduce SHIELD, novel model that leverages both sparsity and hierarchy principles. Build- ing on a deeper decoder architecture, we first incorporate the Mixture-of-Depths (MoD) tech- nique to enforce sparsity. This improves both effi- ciency and generalization by allowing the model to dynamically select nodes to or skip each decoder layer, providing the needed capacity to adaptively allocate computation for learning the task/distribution specific and shared representa- tions. We also develop a vontext-based clustering layer that exploits the presence of hierarchical structures in the problems to produce better local representations. These two designs inductively bias the network identify key features that are common across tasks and distributions, leading to significantly improved generalization on unseen ones. Our empirical results demonstrate the supe- riority of our approach over existing methods on real-world maps with 16 VRP variants each.
Motivated by the recent breakthroughs in foundation mod- els (Floridi & Chiriatti, 2020; Touvron et al., 2023; Achiam et al., 2023), a notable trend in the NCO community is the push towards developing a unified neural solver for han- dling multiple VRP variants, known as the Multi-Tane VRP (MTVRP) setting (Liu al., 2024; Zhou et al., 2024; Berto et al., 2024). These solvers are trained multiple VRP variants and show impressive zero-shot generalization to new tasks. Compared to single-task solvers, unified solvers offer key advantage: there is no longer a need to construct different solvers or heuristics for each specific problem vari- ant. However, despite the importance of the MTVRP setup, it does fully capture real-world industrial applications, the underlying distributions are assumed be uniform, lacking the structural properties of real-world data.
'School of Computing, National University of Singapore, Singa- pore *Institute of Data Science, National University of Singapore, Singapore 'Grabtaxi Holdings Pte Ltd, Singapore *Grab-NUS AI Lab, Singapore "School of Computing and Information Sys- tems, Singapore Management University, Singapore "Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge MA, United States "College of Computing and Data Science, Nanyang Technological University, Singapore. Correspondence to: Yong Liang Goh <gyl@u..mm u...uuu.u.ddu...
This work extends the MTVRP framework to real-world scenarios by incorporating realistic distributions (Goh et al., 2024). Consider logistics company operating across mul- tiple cities/countries. each with fixed set of M locations governed by its geographical layout. When subset of V orders arises, the problem is reduced to serving only those customers. To model this, we generate realistic distribu- tions by selecting smaller subsets of V from the fixed set of M locations such that the geographical characteristics
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
of M are retained. This transforms MTVRP into the Multi- Task Multi-Distributionn VRP (MTMDVRPP) novel and challenging setting that, to our knowledge, has not been explored in the literature.
leading to more generalizable neural VRP solver.
We demonstrate SHIELD's impressive in-distribution and generalization benefits via extensive experiments across 9 real-world maps and 16 VRP variants, achiev- ing state-of the--hhernn art performance compared to existing unified neural VRP solvers.
Nevertheless, MTMDVRP poses unique challenges for learning unified neural VRP models. First, beyond man- aging the diverse constraints of MTVRP, the model must further learn to handle arbitrary, distribution-ssecifie lay- outs. Unfortunately, task-related contexts are often interde- pendent with distribution-related contexts during decision- making (e.g., selecting the next node), adding further com- plexity. Meanwhile, beyond traditional cross- doos-diistibution setups, our approach samples instances from an underlying distribution that captures more practical, real-world patterns. To perform well in the MTMDVRP setting, the model must capture both task- task-specific and distribution-relates contexts when selecting the next node. One promising way to achieve this is to enable the model to dynamically process nodes, al- lowing it to allocate computational focus to the most critical nodes. Additionally, to be generalizable, the model must be sufficiently regularized to prevent over-fitting.
2. Preliminaries
CVRP and its Variants. The CVRP is defined as an in- stance of N nodes in a graph G {V. where the de- pot node is denoted as uo, customer nodes are denoted as {ur)/² E V, and edges are defined as e(v;, tween nodes Uy and Vy such that i * j. Every customer node has demand 6; and each vehicle has a maximum capacity limit Q. For a given problem, the final solution (tour) can be presented as sequence of nodes with multiple sub-tours. Each sub-tour represents a vehicle's path, starting and ending at the depot. As a vehicle visits customer node, the demand is fulfilled and subtracted from the vehicle's capacity. A solution is considered feasible if each customer node is visited exactly once, and the total demand in a sub- tour does not exceed the capacity limit of the vehicle. In this paper, we consider the nodes defined in Euclidean space within a unit square [0. 1). and the overall cost of solution, c(-), is calculated via the total Euclidean distance of all sub- tours. The objective is to find the optimal tour T such that the cost is minimized, given by T" = rggmi ( where t defines the set of all possible solutions.
& be-
To this end, we introduce Sparsity & Hierarchy in Efficiently Layered Decoder (SHIELD) to address the above challenges with two key innovations. First, SHIELD leverages sparsity by incorporating a customized Mixture-of- offpure-of-Depths (MoD) approach (Raposo et al., 2024) to the NCO decoders. While adding more decoder layers can improve predictive power, the autoregressive nature of neural VRP solver significantly hampers efficiency. In contrast, our MoD is designed to dynamically adjust the proper computational depth (number of decoder layers) based on the decision context. This al- lows it to adaptively allocate computation for learning the task/distribution specific and shared representations while acting as a regularization mechanism to prevent over-fitting by possibly reducing redundant computations. Secondly, we employ a clustering mechanism that considers hierarchy during node selection by forcing the learning of a small set of key representations of unvisited nodes, enabling sparse and compact modelling of the complex decision-make makinn information. Together, these two designs encourage the model to learn compact, simple, generalizable representa- tions by limiting computational budgets, effectively enhane- ing generalization across tasks and distributions. This paper highlights the following contributions:
We define the following practical constraints that are inte- grated with CVRP: (1) Open route (O): The vehicle is no longer required to return to the depot after visiting the cus- tomers; (2) Backhaud (B): The demand some nodes can be negative, indicating that goods are loaded into the vehi- cle. Practically, this mimics the pick-up scenario. Nodes with positive demand 6; > 0 are known as linehauls, and nodes with negative demand 5g < 0 are known as back- hauls. Routes can have a mixed sequence of linehauls and backhauls without strict precedence; (3) Duration Limit (L): Each sub-tour is upper bounded by threshold limit on the total length; (4) Time Window (TW): Each node U; is defined with a time window [w], w.]. signifying the open and close times of the window, and s; the service time at a node. A customer can only be served if the vehicle arrives within the time window, and the total time taken at the node is the service time. If a vehicle arrives earlier, it has to wait until wp All vehicles have to return to the depot before wi-
We propose Multi-Task Multi Distrrbbtttbinnn VRP (M'T MDVRP), novel, more realistic, yet challenging sce- nario that better represents the real-world industry.
Neural Constructive Solvers. Neural constructive solvers are typically parameterized by a neural network, where a policy, Te, is trained by reinforcement learning to con- struct a solution sequentially (Kool et al., 2018; Kwon et al., 2020). Generally, these solvers employ an encoder-decoden architecture and are trained as soquence-to-sqqeenee mod-
We present SHIELD, neural solver that leverages sparsity through a customized NCO decoder with MoD layers and hierarchy through context- based cluster rep- resentation. Both contributions reduce computation and parameters, acting as effective regularizers, thereby
2

---

SHIELD: Multi-task Multi-distribation Vehiele Routing Solver with Sparsity and Hierarchy
els (Sutskever, 2014). The probability of a sequence can be factorized ()( II= Po(Tel mTt-1) The coder stacks multiple transformer layers to extract node em- beddings, while the decoder generates solutions autoreges- sively using a contextual embedding h(c)- To decide on the next node, the attention mechanism produces attention scores used for decision-making (Vaswani, 2017). The con- textual vectors h(c) serves as query vectors Q, while the keys, K, is the set of N node embeddings. This is mathe- matically represented as
where IC is the set of all tasks, S the set of all sub-tours in an instance, p; the i-th node in the sequence of 8, and d(; .) the Euclidean distance function. For the MTMDVRP in this paper, we expand on the MTVRP scenarios in (Liu et al., 2024; Zhou et al., 2024). The 2; and yi coordinates for the instances are now sampled from a known underlying distribution of points. This enables the samples to mimic most of the structural distributions and patterns available in the problem. The optimization objective is now given by
dips Peta) ]]
U. . TANH QK VDIM
T
VI' <t
min(c(XX) = Ey ERNK
ΣΣ LIES P.E.
(3)
0j
otherwise
where Q is the set of all distributions. The following prac- tical scenario can visualize our MTMDVRP: assume a lo- gistics company X deploys a deep learning model to solve multiple known variants for its current business. In an ideal world, it would have access all forms of logisties prob- lems generated across all possible structured distributions in the world, whereby a country map q Q. Realistically, company X only has historical data in some tasks and pres- ence in a handful of countries, such that g' E Q', whereby O' C Q, meaning that it only has data drawn from a subset of distributions in Q. Likewise, it has only faced a subset of tasks such that k' E K'', C K. Based on this historical data, company X can train single model using Q' and K', Now, if company X wishes to expand its presence to other parts of the world, it would see new data samples from new distributions and meet new tasks that were not present in the training set. Thus, it would be highly beneficial for com- pany X to be able to apply its model readily. To do so, the model has to be robust to the task and distribution deviation simultaneously, suggesting strong generalization properties across these two aspects.
where U is a clipping function and DIM the dimension of the latent vector. These attention scores are then normal- ized using a softmax function to generate the probability distribution: Ps- = (T ilss, T1=-1) c In- valid moves, such as previously visited nodes, are man- aged using a mask during this process. Finally, given a baseline function b(-), the policy is trained with the RE- INFORCE algorithm (Williams, 1992) and gradient as- cent, with the expected return J and the reward of each solution R. (i.e., the negative length of the solution tour): (g)( ~ E (R(r') ot (s))V log (T() We leave additional details about the architecture in Appendix C.
e"s
Mixture-of-Experrt. Previous work (Liu et al., 2024) demonstrated the ability of state-of-the-art transformers such as POMO (Kwon al., 2020) to generalize across MTVRP instances. More recently. Zhou et al. improved upon this architecture using Mixture-off of of-Experts (MoE). An MoE layer consists of m experts {E1, E,,.., Em J. whereby each expert is a feed-forward MLP. A gating net-
Challenges of MTMDVRP. While adding distributions may seem straightforward it introduces significant complexity. The model must learn representations that capture task and distribution contexts when selecting the next node to visit. Unfortunately, these are often interdependent, which compli- cates decision-making. For example, in skewed map such as EG71 1 46 in Figure 4 of Appendix S, the task complexity is closely tied to the geographic layout. The depot's 's position significantly impacts the solution; a depot near clustered customer nodes is less complex to solve than one located in a sparse region with distant customer nodes. Balancing shared and sttd/disrriuutio-sppeifff representations is more complicated, as the model must generalize across a broader space to be useful across tasks and distributions.
work G produces a scalar score based on an input token x, which decides how the inputs are distributed to the ex- perts. The layer's output can be defined MOE(x) = ", (z). The gating network selects the top-k experts to prevent computation from exploding. For MV- MoE, MoE layers are inserted in each transformer block, allowing each token to use k experts. Additionally, a hierar- chical gate is introduced in the decoder at the problem level to learn whether or not to use experts at each decoding step.
3. Methodology
3.1. MTVRP and MTMDVRP Setup
Formally, the optimization objective of an MTVRP instance is given by
For our setup, we adopt the following feature set. At each epoch, we are faced with problem instance i such that S, = (x. Vt, 5,, wo, wf], where &; and y are the respective (2) coordinates, 8, the demand, wp and w the respective open- ing and closing times of the time window. This is passed
min(c(X)) = EEnK
ΣΣ
d(pr, 1(+1)
SES PLEP PL
3

---

SHIELD: Multi-task Multi-distribution Vehiele Routing Solver with Sparsity and Hierarchy
indditribution map uniformly
Decoder
Out-distribution Mape
kawell
xL
Update Centers
Sample point set from
Combine->
Ang
Cx
In-lask/Dul-taek Out-distribttion
Sample In-lask uniformly
CVRP
VRPB
OVAP
VRPTW
VRPL
OVAPTW
Construct Problem Instance
Th
B
To
MoE Encoder
Ag
Soft Clustering Layer
Tour Lengt
Opt. Gap
Data Generation
Model Training
Inference and Eveluation
Figure/ 1. Overall proposed approach for MTMDVRP. First, in-distribution maps are sampled uniformly, and set of points is sampled from the map. Next, a task is sampled uniformly from the in-task set. These form a batch of problem instances and are passed to the network. SHIELD encompasses an MoE encoder. a context- based clustering layer, and the MoD decoder. The decoder is applied autoregressively to in-task/out-task out-distribution instances where the optimality gap is calculated using known solvers.
through the encoder, resulting in set H of d-dimensional embeddings. At the (-th decoding step, the decoder receives this set of embeddings H, the clustering embeddings C, and set of dynamic features D, = {ze, 4e, tr, oz), where 2; denotes the remaining capacity of the vehicle, le the length of the current partial route, 4 the current time step, and Ot indicates if the route an open route or not.
constant time. Then VC-dim(Ci,.)) =(kt).
The above theorem (taken from Theorem 2.3 (Goldberg & Jerrum, 1993)) shows that for algorithms consisting of mul- tivariate polynomials, such as neural nets, the VC-dim of the algorithm Ar... where k is the number of parameters and n the number of input features, is polynomial in terms of its compute runtime and number parameters, giving us a complexity of (kt). While the Theorem is not strictly applicable to networks containing exponential functions, it suggests that the amount of compute can potentially serve as a regularizer. Based on these observations, we hypothe- size that one can alter the generalization performance of a neural network by adjusting the number of parameters and the total computation used (and hence its runtime).
3.2. Regularization by compute and generalization
To further address the generalization aspect of foundation models for NCO, we present the perspective of adaptive computing motivated by the Vapnik-Chervonenkis (VC) di- mension concept. The VC dimension is a traditional analysis in statistical learning that aims to quantify the complexity of an algorithm (e.g. a neural network) and its learning capacity. In particular, a high VC-dim indicates a more complex model, allowing for greater capacity for represen- tation at the expense of greater sample complexity and a higher tendency for over-fitting Likewise, a low VC-dim indicates simpler model, suggesting inadequate represen- tation power or possibly more substantial generalization due to its simplicity.
We propose an adaptive learning approach that regulates the complexity of the network an appropriate architec- ture for generalization. Our customized MoD approach en- forces sparsity through learning reduced network depths and lighter computation per token. We regularize the model to learn generalizable representations across tasks/distributtins by constraining the network's 's total compute. Additionally, a clustering mechanism forces the network to condense infor- mation. By limiting the number of parameters (and hence the number of clusters) to handful, we enforce sparsity the mechanism. In Multi-Task Multi-Distribution scenario, we posit that these encourage the network to efficiently generalize by balancing the computational budget for task- specific information while leaving common information to be learned across other tasks distributions, allowing for
Theorem. Let {Ck.n k E N} be a set of concept classes where the test of membership of an instance e a concept C' consists of an algorithm Ak.n taking k + n real inputs representing C and whose runtime is I. = 1(k: n), and which returns the truth value E C. The algorithu Arn is allowed to perform conditional jumps (conditioned on equality and inequality of real values) and execute the stan- dard arithmetic operations on real numbers (+,-, x/)) in

---

SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy
to summarize the set of unvisited cities into a handful of representations. This is then used to guide agents, providing crucial information about the groups of nodes left in the problem, which is highly useful for structured distributions.
Rozarm
MDD
Pouler
MGD
MCD
In addition to structured distributions, the MTMDVRP has underlying commonalities among its tasks. As such, we hypothesize that nodes and their associated task features can be grouped. While spatial structure can typically be measured in Euclidean space, it is not straightforward for tasks and its features. Thus, an EM-inspired soft clustering algorithm in latent space provides a sensible approach to this problem. We first define a set of C E R N.xx represen- tations, such that Nº of these denote the number of cluster centers. The soft clustering algorithm poses the forward pass of the attention layer as an estimation of the E-step. and the re-estimation of C using the weighted sum of the learnt attention weights as the M-step. Repeated passes through this layer simulate a roll-out of a pseudo-EN EerudoM-MMMa algo- rithm. Effectively, the network learns to transform the initial cluster centroids into the final centroid embeddings.
MOD
MCD
MOD
Figure 2. Token is routed differently for each agent depending on
the router.
efficient generalization across tasks and distributions.
3.3. Going deeper but sparser
Our proposed architecture is shown in Figure 1. To increase the predictive power of the MVMoï, one can easily hypoth- esize that increasing the number of parameters would be necessary. However, due to the autoregressive nature of de- coding, this quickly becomes computationally expensive. In- stead, we propose the integration of the Soaturr-of-DDpthhi (MoD) (Raposo et al., 2024) approach into the decoder. Given a dense transformer layer and N tokens, MoD se- lects the top 8-th percentile of tokens to pass through the transformer layer. In contrast, the remaining unselected tokens are routed around the layer with residual connec- tion around the layers, avoiding the need to compute all N attentional scores. Formally, the layer can be represented as
In this work, we introduce context prompts to capture the task dependencies for the soft clustering algorithm. Ideally, for the same spatial graph, if the task at hand is different, the clustering mechanism should be sufficiently flexible to accommodate the various intricacies of the task. Prompts are a reasonable approach, as they provide helpful task in- formation for LLMs (Radford et al., 2019). Specifically, we construct contextual prompts as latent representations given by a W 7% where W a set of learnable parame- ters that transform the constraints latent representations, and 7he is one-hot encoded vector of constraints for task k, such that each feature corresponds to a constraint. In this work, we have * = Ink, 72 n 7/1, where 7/. denotes open, 22 denotes time- windww 7 denotes route length, and o denotes backhaul constraints. By designing prompts to operate in the latent space, we thus enable the model to learn to stitch together these constraints, allowing for flex- ible modeling of tasks that it has not seen during training. Now, this vector is passed onto the clustering layer:
h. = (FH) + h if Po(t')
if > Pa(r')
(4)
h/
where r, W is router score given for token at layer 1, Wo is learnable parameters in the router that converts d-dimensional embedding into scalar score, r' the set of all router scores at layer I, (r') the 3-th percentile of router scores, and H the subset of tokens in the 3-th percentile. In this work, we apply token-level routing on contextual vectors h(cj. whereby each token is passed through the router, and the top 3-th percentile tokens are selected and form the query embeddings. Each transformer layer still receives all N node embeddings that serve as key and value embeddings, and mask to determine whether a node has been visited. By controlling B, we control the sparsity of the architecture by limiting the total number of query tokens that are processed. This means that the network must learn to identify which current locations are more important to be processed, as shown in Figure 2.
h, = WW Cj = Welc;,ad)
(5)
t/. = SOFTMAX C.c, VDIM ).c, = ..,,),,,, Σ Wiyh,
(6)
whereby WH and We c are weight matrices, [-] denotes the concatenation operation, &i the set of all mixing coefficients d éj the learnable initial cluster center representation, h, the input node embeddings, and c the final cluster represen- tation as a weighted sum of input embeddings after multiple passes. Essentially, Equation 5 is repeated B-times. The overall process can be viewed in Algorithm 1 in Appendix D. The output of these cluster centroids is fed to the decoder and serves as additional information for the decoding pro-
3.4. Contextual clustering
Apart from sparsity in compute, we introduce hierarchy and sparsity in the form of representation. Goh et al. (2024) first showed that one can apply a form of soft-clusterng
5

---

SHIELD: Multi-task Multi-distribution Vehiele Routing Solver with Sparsity and Hierarchy
cess. At each step, we update clusters by taking a weighted subtraction of visited nodes, given by
provide full details of the hyperparameters in Appendix I.
Performance Metries. We sample 1,000 test examples per (7) problem for each country map and solve them using tradi- tional solvers We use HGS (Vidal, 2022) for CVRP and VRPTW instances and Google's OR-tools routing solver (Furnon & Perron) for the rest. For neural solving, each sample is augmented times following Kwon et al. (2020), and we report the tour length and optimality gap (compared to the traditional solver) of the best solution found across these augmentations, whereby smaller values indicate better performance. We provide details of solver settings, augmen- tation, and optimality gap in Appendix H.
h(c) = WCOMBINE| LAST: C1, c2,-.,, + HRSTT: cj = C2- - (+h. h.). Vj E No.
4. Experiments
We conform to a similar problem setup in (Liu et al., 2024; Zhou et al., 2024), using a total of 16 VRP variants with 5 constraints, as described in section 2. All experiments run on a single A100-80Gb GPU.
Datasets. We utilize nine country maps': USA13509, JA9847, BMM33708, K79976, SW24978, EG7 KG7146, F110639, GR9882. Dataset details are in Appendix E.
4.1. Empirical Results
Main Results. Table 1 presents the average tour length (Obj) and optimality gap (Gap) across the respective tasks (in-task/out-task) and distributions (in-dist/out-dist), with details in Tables 14 to 22. SHIELD demonstrates signifi- cantly stronger predictive capabilities and outperforms all other neural solvers across all tasks and distributions.
Task Setups. We define the following: (1) in-task refers to the six tasks that the models are trained on: CVRP, OVRP, VRPB, VRPL, VRPTW, OVRPTW; (2) out-task refers to the ten tasks that the models are not trained on: OVRPB, OVRPL, VRPBL, VRPBTW, VRPLTW, OVRPBL, OVRPETW, OVRPLTW, VRPBLTW, OVRP- BLTW; (3) in-distribution refers to the three distribu- tions that the models observe during training: USA13509, JA9847, BM33708; (4) out-distribution refers to the six distributions that the models do not observe during train- ing: KZ9976, SW24978, VM22775, EG7146, FI10639, GR9882.
We can view HVMoF-Deeppe as a model that processes each token heavily with multiple layers, while MVMoE is a model that processes each token only once. SHIELD is thus a middle point that learns how to adapt the processing according to the token and problem state. Consequently, this suggests that overprocessing (MVMoE-Deeper)) and under- processing (MVMoE) nodes can be problematic in building an efficient foundation model. As shown, increasing the depth of the decoder to MVMoE- improves its over- all performance, especially in the in-task in-distribution case. Unfortunately, the autoregressive nature quickly renders the model untrainable on MTMDVRP100. Instead, if we re- place these dense layers with sparse ones (as in SHIELD), the model is now trainable on larger problems and sees significant improvement in task and distribution generaliza- tion. These aspects also highlight the positive effects of regularization by reducing compute and parameters.
Neural Constructive Solvers. We compare the follow- ing unified solvers focused on generalization: (1) POMO- MTVRP which applies POMO to the MTVRP setting (Liu et al., 2024); (2) MVMoE that extends POMO to include MoE layers (Zhou et al., 2024); (3) MVMoE-Light, a vari- ant of MVMoE with an additional hierarchical gate in the decoder (Zhou al., 2024): (4) MVMoE- whereby we increase the depth of MVMoE to have the same number of layers in the decoder SHIELD so that both models have similar capacity: (5) SHIELD- MMD where we train our model only with MoD layers and without the clustering; (6) SHIELD, our proposed model of MoD and clustering.
Table also highlights the positive effect of contextual clus- tering, particularly in problems with 100 nodes. The benefits are most evident in the model's generalization across tasks and distributions. Summarizing the larger set of points helps the model identify key points in route construction.
Hyperparameters. We use the ADAM optimizer to train all neural solvers from scratch on 20, 000 instances per epoch for 1, 000 epochs. All models plateau this epoch, and the relative rankings do not change with further training. At each training epoch, we sample a country from the in- distribution set, followed by a subset of points from the distribution and a problem from the in-task set, as shown in Figure 1. For SHIELD, we use 3 MoD layers in the decoder and only allow 10% of tokens per layer. The number of clusters is set to N₂ = 5, with B 5 iterations of soft clustering. The encoder consists of 6 MoE layers. We
Model Complexities. Table 4 in Appendix F displays each model's total number of parameters. To quantify complex- ity, we measure the average number of floating operations (FLOPs) for single-pass through the encoder and one de- coding step. Note that we use only one decoding step as inferior neural solvers will require more steps to solve the problem and thus increase its overall compute budget. As shown, MVMoE has an increased number of FLOPs com- pared to the original POMO-MTVRP. For our model, both
htttps:://wwwwttt/ www.wwwwwwwoooooo.. wttp://o....../////ooaeeeeeeeo countries, html
6

---

SHIELD: Multi-task Multi-distribation Vehiele Routing Solver with Sparsity and Hierarchy
Table 1. Overall performance of models trained on 50 node and 100 node problems. Bold scores indicate best performing models in their respective groups. The scores and optimality gaps presented are averaged across their respective groups. Underlined results indicate the SHllELD-equivalen model for MVMoE, while italicized results indicate the -equiveDeeuivaeent model of MVMoo-Deeper.
MTMDVRP50
MTMDVRP100
Model
In-dist
Out-dist Gap
In-dist Gap
Out-dist
Obj
Gap
Time
Obj
Time
Obj
Time
Obj
Gap
Time
Solver
5,8773
74.72s
6.1866
72.89
9.0468
194.00s
9.6506
187.
POMO-MTVRP
6,0778
3.5079%
2.65s
6.4261
3,991
2.76s
9.4123
4.0824%
8.13s
10.1147
5.0253%
8.20s
MVMoE
6.0557
3.1479%
3.658
6.3924
3.5071
3.67s
9.3722
3.5969%
10.97s
10.0827
4.6855%
11.30s
MVMoE--Light
6.0666
3.3595%
3.41s
6,4045
3.6860%
3.43s
9.3987
3.9088%
10.04s
10.1027
4 4.8979%
10.46s
In-task
DeMoFeDeeper
6,0337
2.7343%
9.03s
6,3677
3. 1333%
9.033
0OM
0OM
00M
00M
00M
0OM
SHIELD-MoD
6,0220
1.5041%
5.40s
6,2933
2.9517%
5.38s
9,3453
2.5443%
17.59s
9,9800
3,5255%
17.66s
SHIELD-400Ep
6,0597
3.1495%
6.14s
6,3830
3.2730%
6.11s
9.3785
3.5993%
19,90s
10,0559
4.3562%
20.27s
6,8333
2.7089%
6.x
6.1653
2,9993%
6.09%
9.1194
2.9498%
79.8Kv
10.01
3. 3.8262%
20.28x
SHIELD
6.01336
2.3747% %
6.138
6,2784
2.7376%
6.11s
9.2743
2.4397% %
19.93s
9,9501
3,1638 %
20.25s
Solver
5,4513
78.00s
5.7941
75.70x
8.7852
160.90s
9.4545
160.44s
POMO MTVRP
5,8611
7.6284%
2.83s
6,2556
8.03 11%
2.70s
9.4304
8.1068%
8.39
10.2056
8.8907%
8.46s
MVMoE
5.8328
7.1553%
3.81s
6.2196
7.5174%
3.73s
9.3811
7.4092%
11.13s
10.1665
8,5140%
11.448
-Lghht
5,8466
7.4996%
3.46s
6,2346
7.8236%
3.50s
9.4173
7.9100%
10.27s
10.1945
8.8620%
10.75s
Out-task
MVMoE-Deeper
5,8207
6.7924%
9,40s
6.2136
7.2962%
9,45s
0OM
00M
00M
00M
00M
0OM
SHIELD-MoD
5.7902
6.2672%
5.47%
6.2238
6.6155%
5.48s
9,2740
6.0296%
17.75s
10.0349
6.9029%
17.79%
SHIELD-400E)
5.8290
7.1064%
6.23s
6,2085
7.2927%
6.21s
9.3499
6.9578%
19.88s
10,2
7,8332%
20.15s
SHIELD-600Ep
5.8039
6.6539%
6.19s
6.1823
6. 6,87666
6.22s
9.3105
6.4308%
19.91s
10.0765
7.2549%
20.1
SHIELD
S,7779
6.0810%
6.20s
6,1570
6.3520%
6.20s
9,2400
5.6104%%
19.92s
9.9867
6.2727%
20.18s
SHIELD-MoD and SHIELD have increased parameters and FLOPs due to the number of decoder layers. Interestingly, compared to MVMoE-Deeper (which also has three layers of decoder), we reduce the FLOP budget per step by impos- ing sparsity on the network. By constraining the compute budget, we effectively regularize the model and improve its generalization capabilities.
degradation continues with the 40% model, where overall performance deteriorates. The results indicate that sparsity is crucial in generalization across task and distribution.
Effect of Clustering. In the latent space, the soft clus- tering mechanism facilitates information exchange among dynamic clusters, enabling the model to capture high-level, generalizable features from neighboring hidden representa- tions. This improves the model's ' understanding of the node selection process and enhances decision-making Limiting the number of clusters reduces the number of parameters and promotes abstraction, which encourages the model to focus on broadly applicable patterns rather than overfitting task-specific details. In contrast, too many clusters dilute this effect, leading to over-segmentation and reduced gen- eralization as the model prioritizes more complex patterns over shared structures. Table supports this, whereby we vary the number of cluster centers the model. Thus, main- taining sparsity in this aspect is crucial as well.
Generalization of SHIELD, To further evaluate the gener- alization capability of SHIELD, Table shows its perfor- mance at earlier checkpoints, epochs 400 SSHEELD-400F and epochs 600 (SHIELD-600Ep), that match the In-Task In- Distribution performance of MVMoE and MVMoE- -Deeper, respectively. Our SHIELD counterparts show superior gen- cralization across tasks and distributions, cementing its ca- pability and flexibility as a general foundation model.
4.2. A Ablation and Analyses
We discuss key observations and ablation studies here, and provide full tables and further details in Appendices J to R.
Importance of chitecture improves overall, we trained and tested all models on the conventional MTVRP setting using the uniform distri- bution. Table 13 in Appendix Q showcases the performance of all models. Here, we see that while the gaps between the models are less significant once we remove the varied distributions, SHIELD is still clearly the better-performing model. This indicates the difficulty of a multi-distribution scenario having varied structures with multiple tasks is more complex. Since our architecture is more flexible, it generalizes better in the MTMDVRP scenario.
To verify that ar-
Effect of Sparsity. To examine the effect of sparsity, we train models with varying capacities of the MoD layer on MTMDVRP50. The results are shown in Table 2. Specifi- cally, the sparsity moves from 10% to 20%, the model's bias improves-the the in-task performance improves slightly, while the out-distribution performs begins to degrade. In- creasing the number of tokens further improves the in-task in-distribution optimality gaps, but we see a decline in per- formance for tus-task and out-distribution settings. This
7

---

SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy
Table 2. Performance of SHIELD with varying levels of sparsity on MTMDVRPSO. As more nodes are processed the model's 's bias improves, but generalization degrades.
Table 3. Ablation study for the number of clusters in SHIELD on MTMDVRP50. Keeping the number of clusters low, and thus having sparser approach, is beneficial to the model.
In-dist
Out-dist
In-dist
Out-dist
Model
Ohj
Gap
Obj
Gap
Model
Obj
Gap
Obj
Cap
SHIELD (10%)
6.0136
2.3747%
6.2784
2.7376%
SHIELD
6.01366
2.3747%
6.2784
2.73766
SHHELD (20%)
6.0055
2.2268%
6.3578
2.8442%
In-task
SHIELD (N. 10)
6.0100
2.3166%
6.3400
3.7522%
In-task
SHIELD (30%)
6.0033
2.1948%
6.3656
2,9608%
SHIEL D (N,- 20)
6.0124
2.3272%
6.3437
3.8127%
SHIFLI D (40%)
6.0131
2.3450%
6.3718
3.0507%
SHIELD
5,7779
6.0810%
6.1570
6.3620
MVMoE-Deeper Deeper (100%)
6.0337
2.7343%
6,3677
3.1333%
Out-task
SHIELD (N. 10)
5,8019
6.9521%
6.1740
7.0129%
STWELD (10%)
5.7779
6.0810%
6.1570
6,3520%
SHIELD (N. 20)
5,9824
11,3457%
6.3369
10.80448
SHIELD (20%)
5.7772
6.0327%
6,1671
6.4654%
Out-task
SHIFL D (30%)
5.7991
6.4241%
6,1732
6.5603%
SHIELD (40%)
5,8068
6.5770%
6.1862
6.7831%
MVMoE-Deeper (100%)
5,8206
6.7924%
6,2136
7.2962%
Next, we apply the trained models to the MTMDVRP test set and tabulate the results in Table 11 in Appendix O. Since all models are only trained on uniform data, they are unsuitable to be applied to more structured forms of data. Instead, if the model is exposed to some structure during training, it performs better in generalization to new distributions.
Figure 3. Left two panels: Plot of routes for OVRPBTW between SHIELD (left) and MVMoE (middle). Points denoted with a star are the top few points that SHIELD identified for more processing. Note that the initial routes from the depot are masked away for a better view. Right panel: Average number of layers used as the demand is being met for CVRP.
Sparse Encoder. Table 7 in Appendix K studies the impact of sparsity in the encoder. We replace encoder layers with MoD layers of capacity of 10% and find that the model's performance degrades significantly, even after doubling the number of layers.
feet, which confuses the decoder, resulting in poor decision- making. Only attending to the k-NN nodes effectively re- duces the number of interactions amongst the nodes and thus introduces sparsity into the attention mechanism, a somewhat similar approach to SHIELD. A key difference between the approaches is that INVIT's reduction is based on heuristic, the k-NN, while in SHIELD, we opt to learn which nodes to focus on based on MoD.
This shows that the MoF encoder plays a crucial role in the architecture. 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 inputs.
We adapt and train INVIT on the MTMDVRP scenario; the results are shown in Table 6 in Appendix J. INVIT struggles with the multi multi-task dynamics of the problem, likely because the sparse attention mechanism relies on selecting the k-NN nodes based on spatial distance. This is highly inflexible and poorly suited for dynamic MTMDVRP setting. As such, essential nodes are possibly pruned away, leading to inferior neural solver
In contrast, the decoder in MTMDVRP focuses on sequen- tial solution construction with adaptive computation. While some node selections are straightforward, others require finer granularity and greater compurational/reasoning capac- -y-esppe especially when dealing with clustered distributions or complex constraint-distributie interactions in MTMD- VRP. 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 ss ability to capture context- dependent, adaptive fine-grained decisions for MTMDVRP.
Patterns of Layer Selection. Figure 3 shows the output of SHIELD and MVM0E for OVRPBTW on VM22775 The starred points indicate that SHIELD selects these points more frequently when solving problems. Consider route R5 for SHIELD and route R8 for MVMoE. SHIELD can recognize that such points are far away from the depot and that visiting other points route is more advantageous, whereas MVMoE only visited one node before returning. Likewise, for route R4 in SHIELD and route R6 in MVMOE, SHIELD identifies the two starred points to be better served as connecting points instead of making an entire loop, which results in back-tracking to a similar area. Since the problem
Alternative Sparse Attention Approaches. Apart from studying the effect of sparsity in the encoder, we investigate similar sparse attention approaches such as INViT (Fang et al., 2024). Essentially, INVIT proposes to only attend to the k-Nearest Neighbors (k-NN) during solution con- struction, as attention to all nodes introduces an aliasing ef-
8

---

SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity and Hierarchy
an open problem, we can see that SHIELD favors ending routes at faraway locations, whereas MVMoE tends loop back and forth in many occurrences.
tecture, motivated by regularization via compute and pa- rameters, is designed to handle generalization across task and distribution dimensions, making it robust solver for practical problems. Extensive experiments and thorough analysis of the empirical results demonstrate that sparsity and hierarchy, two key techniques in SHIELD, substantially influence the model's generalization ability. This forms a stepping stone towards other foundation models, such as generalizing across various sizes.
The right panel of Figure 3 illustrates how the use of layers is distributed as the agent starts to address the demands of the problem. The x-axis represents the percentage of the sub- tour solved, while the y-axis denotes the average number of MoD layers used by the agent. The model initially uses some processing power to find good starting node set. In the middle, fewer layers are being used, and finally, as the problem ends, more layers are activated to select effective ending points. Additional qualitative analysis in Figure 5 in Appendix L shows that for maps with similar top density and right bias, the model behaves somewhat similarly regarding its overall layer usage.
A Acknowledgements
This work is funded by the Grab-NUS AI Lab, a joint collab- oration between GrabTaxi Holdings Pte. Ltd. and National University of Singapore, and the Industrial Postgraduate Program (Grant: Development Board of Singapore. This research is also sup- ported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (A-80018 180001814-000 (0000000)---0)..... This research is also supported by the National Research Founda- tion, Singapore under its AI Singapore Programme (AISG Award No: AISG3-RP-2022-033
funded by the Economic
Size Generalization. To explore how our model behaves problem sizes beyond what it was trained on, we generate and label an additional dataset with 200 nodes each. For the MTMDVRP200, we increased the time allowed to solve each instance to 80 seconds. Table in Appendix M illus- trates the zero-shot generalization performance of trained MTMDV 1000 models on the MTMDVRP200. SHIELD is still the superior model to the other baselines, showing size- able performance gap on problems larger than it was trained on. Additionally, note that the inference time of SHIELD is comparable to MVMoEE and MVMoF-LLight. This is be- cause in the MTMDVRP200, inference on the MVMoE models requires smaller batch sizes, whereas SHIELD's sparsity allows it to process larger batches.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
We also investigate the performance of all models zero- shot size generalization setting to the CVRPLib Set-X. Ta- bles 9 and 10 in Appendix N show that SHIELD outperfoms all models considerably in the Large setting (101 & N < 251) and the Extra Large setting (502 S N < 1001). We attribute the flexibility of dynamic processing in SHIELD to the strong zero-shot performance.
References
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
Bdeir, A., Falkner, K., and Schmidt-Thieme, L. Atten- tion, filling in the gaps for generalization in routing prob- lems. In Joint European Conference Machine Learn- ing and Knowledge Discovery in Databases, pp. 2pp5005-55 505-520. Springer, 2022.
Single-Taste Task Multi-Distribuute
Table 12 in Appendix P showcases the performances of models trained on single task, CVRP, across our various distributions. As SHIELD is still the top-perfone pop-performing model, the results suggest our architecture not catered only to the MTMDVRP scenario its flexibility allows for strong generalization across distri- butions for the single task case.
Bello. I. Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. Neural combinatorial optimization with reinforcement learning. In International Conference on Learning Rep- resentations Workshop Track, 2017.
5. Conclusion
Bengio, Y., Lodi, A., and Prouvost, A. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 290(2)405--211 2021.
The push toward unified generic solvers is essential in build- ing foundation models for neural combinatorial optimiza- tion. In this paper, we propose to extend such solvers to the Multi-Task Multi-Distribution VRP, a significantly more practical representation of industrial problems. With this problem setting, we propose SHIELD. This neural archi-
Berto, F., Hua, C., Park, J., Luttmann, L.,, Ma, Y., Bu, F,, Wang, J., Ye, H., Kim, M., Choi, S., Zepeda, N. G., Hottung, A., Zhou, J., Bi, J., Hu, Y., Liu, F,, Kim, H.,

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
Son, J., Kim, H., Angioni, D., Kool, W., Cao, Z., Zhang, J., Shin, K., Wu, C., Ahn, S., Song, G., Kwon, C., Xie, L.,, and Park, J. R14co: an extensive reinforcement learning for combinatorial optimization benchmark, arXiv preprint arXiv:2306. 17100, 2023.
Fang, H., Song, Z., Weng, P., and Ban, Y. Invit: A general- izable routing problem solver with invariant nested view transformer. In International Conference on Machine Learning, 2024.
Floridi, L. and Chiriatti, M. Gpt-3: Its nature, scope, limits, and consequences. Minds and Machines, 2020.
Berto, F., Hua, C., Zepeda, N. G., Hottung, A., Wouda, N., Lan, I.,, Tierney, K., and Park, J. Routefinder: Towards foundation models for vehicle routing problems. arXiv preprint arXiv:2406. 5007, 2024.
Fu, Z.-H., Qiu, K.-B., and Zha, H. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 35, pp. 7474 7482, 2021.
Bi, J., Ma, Y. Wang. J., Cao, Z., Chen, J.. Sun, Y., and Chee, Y. M. Learning generalizable models for vehicle routing problems via knowledge distillation. In Advances in Neural Information Processing Systems, volume 35, pp. 3 31226-1222111 02226-11238, 1238, 2022.
Furnon, and Perron, brary. URL https://dett https://developers..oom google com/ optimitimmiimmmmm. mamiiiziiorrrttingg
Or-tools routing li-
Bi, J., Ma. Y. Zhou, J., Song, W. Cao, Z., Wu, Y., and Zhang, J. Learning to handle complex constraints for vehicle routing problems. In Advances in Neural Infor- mation Processing Systems, 2024.
Geisler, S., Sommer, J., Schuchardt, J., Bojchevski, A., and Günnemann, S. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference on Learning Representations, 2022.
Bogyrbayeva, A., Meraliyev, M., Mustakhov, T., and Daulet- bayev, B. Machine learning to solve vehicle routing problems: A survey. IEEE Transactions on Intelligent Transportation Systems, 2024.
Goh, Y. L., Cao, Z., Ma, Y., Dong, Y., Dupty, M. H., and Lee, W. S. Hierarchical neural constructive solver for real-world tsp scenarios. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 884-895, 2024.
Caserta, M. and VoB, S. A hybrid algorithm for the dna sequencing problem. Discrete Applied Mathematics, 163: 87-99, 2014.
Goldberg. P. and Jerrum, M. Bounding the vapnik- chervonenkis dimension of concept classes parameterized by real numbers. In Proceedings of the sixth annual con- ference on Computational learning theory, pp. 361-369, 1993.
Cattaruzza, D., Absi, N., Feillet, D., and Gonzâlez-Feliu, Vehicle routing problems for city logistics. EURO Journal on Transportation and Logistics, 6(1):51-79, 2017. 2017.
Chalumeau, F., Surana, S., Bonnet, C., Grinsztajn, N., Pre- torius, A., Laterre, A., and Barrett, T. D. Combinatorial optimization with policy adaptation using latent space search. In Advances in Neural Information Processing Systems, 2023.
Grinsztajn, N., Purelos-Blanco, D., Surana, S., Bonnet, C., and Barrett, T. D. Winner takes it all: Training performant RL populations for combinatorial optimization. In Ad- vances in Neural Information Processing Systems, 2023.
Chen, X. and Tian, Y. Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, pp. 6281- 6292, 2019.
Hottung, A. and Tiemny,, K. Neural large neighborhood search for the capacitated vehicle routing problem. In European Conference on Artificial Intelligence, pp. 443- 450. IOS Press, 2020.
Costa, P. d., Rhuggenaath, J., Zhang, Y., and Akçay, A. E. Learning 2-opt heuristics for the traveling salesman prob- lem via deep reinforcement learning. In Asian Conference on Machine Learning, pp. 460, 2020.
Hottung, A., Mahajan, M., and Tierney, K. PolyNet: Learn- ing diverse solution strategies for neural combinatorial optimization. arXiv preprint 2rXiv:2402.14048. 2024.
Hou, Q., Yang, J., Su, Y., Wang, X., and Deng, Y. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In International Conference on Learning Representations, 2023.
Drakulic, D., Michel, S., Mai, F., Sors, A., and Andreoli, J.- M. BQ-NCO: Bisimulation quotienting for generalizable neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Huang, Z., Zhou, J., Cao, Z., and XU, Y. Rethinking light decoder- based solvers for vehicle routing problems. In International Conference on Learning Representations, 2025.
Drakulic, D., Michel, S., and Andreoli, J.MM. Goal: A generalist combinatorial optimization agent learner. arXiv preprint arXiv:2406. /5079, 2024.
10

---

SHIELD: Multi-task Multi-distribution Vehiele Routing Solver with Sparsity and Hierarchy
Hudson, B., Li, Q., Malencia, M., and Prorok, A. Graph neural network guided local search for the traveling sales- person problem. In International Conference on Learning Representations. 2022.
Liu, F., Lin, X., Wang, Z., Zhang, Q. Xialiang, T., and Yuan, M. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1898-1908, 2024.
Jiang, Y., Wu, Y., Cao, Z., and Zhang, J. Learning to solve routing problems via distributionally robust optimization. In Proceedings of the AAAI Conference on Artificial In- felligence, volume 36, pp. 9786-9794, 2022.
Lu, H., Zhang, X., and Yang. S. A learning- based iter- ative method for solving vehicle routing problems. In International Conference on Learning Representations, 2020.
Joshi, C. K., Laurent, T., and Bresson. X. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.
Lu, H., Li, Z.,, Wang, R., Ren, Q., Li, X., Yuan, M., Zeng, J., Yang, X., and Yan, J. ROCO: A general framework for evaluating robustness of combinatorial optimization solvers on graphs In International Conference on Learn- ing Representations, 2023.
Joshi, C. K., Cappart, Q., Rousseau, L.-M., and Laurent, T. Learning tsp requires rethinking generalization. In International Conference on Principles and Practice of Constraint Programming, 2021.
Luo, F., Lin, X., Liu, F., Zhang, Q., and Wang. Z. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Infor- mation Processing Systems, 2023.
Kim, M., Park, J., and Park, J. Sym-NCO: Leveraging sym- metricity for neural combinatorial optimization. In Ad- vances in Neural Information Processing Systems, 2022.
Ma, Y., Li, J., Cao, Z., Song, W. Zhang, I.., Chen, Z., and Tang. J. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neural Information Processing Systems, volume 34, pp. 1 11096-11107, 2021.
Kim, M., Choi, S., Son, J., Kim, H., Park, J., and Bengio, Y. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arXiv:2403.0m
2024.
Kool, W., van Hoof, H., and Welling, M. Attention, learn to solve routing problems! In International Conference on
Ma, Y., Cao, Z., and Chee, Y. M. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In sevethh Conference on Neural Information Processing Systems, 2023.
Learning Representations, 2018.
Kool, W., van Hoof, H., Gromicho, J., and Welling, M. Deep policy dynamic programming for vehicle routing problems. In International Conference Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 190-213. Springer, 2022.
Mao, X., Wen, H., Zhang, H., Wan, H., Wu, L.,, Zheng, J., Hu, H., and Lin, Y. Drl4route: A deep reinforce- ment learning framework for pick-up and delivery route prediction. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 4628 4637, 2023.
Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. Pomo: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Infor- mation Processing Systems, volume 33, pp. 21 21188-2111 21198, 2020.
Min, Y., Bai, Y., and Gomes, C. P. Unsupervised learning for solving the travelling salesman problem. In Advances in Neural Information Processing Systems, 2023.
Kwon, Y.-D., Choo, J., Yoon, I., Park, M., Park, D., and Gwon, Y. Matrix encoding networks for neural combina- torial optimization. In Advances in Neural Information Processing Systems, volume 34, 2021.
Nazari, M., Oroojlooy, A., Takáč, M., and Snyder, L. V. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9861-9871. 2018
Li, S., Yan, Z., and Wu, C. Learning delegate for large- scale vehicle routing. In Advances in Neural Information Processing Systems, volume 34, pp. 26198-26211. 2021.
Qiu, R., Sun, Z., and Yang, Y. Dimes: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems, vol- ume 35, pp. 25531-25546, 2022.
Lin, Z., Wu, Y., Zhou, B., Cao, Z. Song, W., Zhang, Y., and Senthilnath, J. Cross-problent learning for solving vehicle routing problems. In International Joint Conference on Artificial Intelligence, 2024.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenAl blog, 188)9, 2019.

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
Raposo, D., Ritter, S., Richards, B., Lillicrap. T., Humphreys, P. C., and Santoro, A. Mixture-of-depths: Dynamically allocating compute in transformer-based lan- guage models. arXiv preprint arXiv:2404.02255, 2024.
Xia, Y., Yang, X., Liu, Z., Liu, Z.. Song, L.,, and Bian, J. Position: Rethinking post-hoc search-based neural ap- proaches for solving large-scale traveling salesman prob- lems. In International Conference on Machine Learning, 2024.
Son, J., Kim, M., Kim, H., and Park, J. Meta-SAGE: Scale meta-learning scheduled adaptation with guided exploration for mitigating scale shift on combinatorial optimization. In International Conference on Machine Learning, 2023.
Xin, I.., Song, W., Cao, Z., and Zhang, J. Neurolkh: Com- bining deep learning model with thernighan-helguue heuristic for solving the traveling salesman problem. In Advances in Neural Information Processing Systems, vol- ume 34, pp. 7472-7483, 2021.
Son, J., Zhao, Z., Berto, F., Hua, C., Kwon, C., and Park, Neural combinatorial optimization for real-world routing. arXiv preprint arXiv:2503.16/53 2025.
Ye, H., Wang, J., Cao, Z., Liang, H., and Li, Y. Deep- ACO: Neural-enhanced ant systems for combinatorial optimization. In Advances in Neural Information Pro- cessing Systems, 2023.
Sun, Z. and Yang, Y. Difusco: Graph- diffusion solvers for combinatorial optimization. In NeurIPS, volume 36, pp. 1706-3731, 2023.
Ye, H. Wang. J., Liang, H., Cao, Z., Li, Y., and Li, F. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelli gence, 2024.
Sutskever, I. Sequence to sequence learning with neural networks. arXiv preprint arXiv: 1409.321,, 2014.
Touvron, H., Martin, L.., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine- tuned chat models. arXiv preprint arXiv:2307.09280 099288. 2023.
Zhang. Z., Zhang. Z., Wang, X., and Zhu, W. Learning to solve travelling salesman problem with hardness hardness-adaptiiee curriculum. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9136-911111111 9944, 2022.
Vaswani, A. Attention is all you need. In Advances in Neural Information Processing Systems, 2017.
Zhou, J., Wu, Y., Song, W., Cao, Z., and Zhang, J. Towards omni ummi-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learn- ing. pp. 42769-47722 42789. PMLR, 2023.
Vidal, T. Hybrid genetic search for the evrp: Open-source implementation and swap neighborhood. Computers & Operations Research, 140:105643, 2022.
Zhou, J., Cao, Z., Wu, Y., Song, W., Ma, Y., Zhang, J., and Xu, C. Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. In International Conference on Machine Learning, 2024.
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, pp. 2692-2700, 2015.
Wang, C. and Yu, T. Efficient training multi-tase com- binarotial neural solver with multi-armed bandits. arXiv preprint ar XrXiv22355.6680
2023.
Wen, H., Lin, Y., Mao, x., Wu, F., Zhao, Y., Wang, H., Zheng, J., Wu, L., Hu, H., and Wan, H. Graph2route: A dynamic spatial-temporal graph neural network for pick- up and delivery route prediction. In Proceedings of the 28th ACM SIGKDD conference knowledge discovery and data mining, pp. 4143-4152. 2022.
Williams, J. Simple statistical madieettffollwing algo- rithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992.
Wu, Y., Song, W., Cao, Z., Zhang, J., and Lim, A. Learn- ing improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 330))5007-5009, 2021.
12

---

SHIELD: Multi-task Multi-disttibation Vehiele Routing Solver with Sparsity and Hierarchy
A. Related Work
Generalization Study. Joshi et al. (2021) highlighted the generalization challenge faced by neural solvers, where their performance drops significantly on out-of-distribution (OOD) instances. Numerous studies have sought to improve generalization performance in cross-size (Bdeir et al., 2022: Son al., 2023; Huang et al., 2025), cross-distribution (Fang et al., 2024; Jiang al., 2022: Bi et al., 2022; Zhang et al., 2022; Zhou et al., 2023), and cross-task (Lin et al., 2024; Liu et al., 2024; Zhou et al., 2024; Berto et al., 2024) settings. However, their methods are tailored to specific settings and cannot handle our MTMDVRP setup, which considers crossing tasks and realistic customer distributions. While a recent work Goh et al. (2024) explores more realistic TSPs, their approach struggles with complex cross-problem scenarios. In this paper, we take a step further by exploring generalization across both different problems and real-world distributions in VRPs.
Multi-task VRP Solver. Recent work in (Liu et al., 2024) explored the training of Multi-Tash VRP solver across a range of VRP variants sharing a set of common features indicating the presence or absence of specific constraints. Zhou et al. (2024) enhanced the model architecture by introducing Mixture-of Expertsss within the transformer layers, allowing the model to capture representations tailored to different tasks effectively. These studies focus on zero-shot generalization, where models are trained on a subset of tasks and evaluated on unseen tasks that combine common features. Other studies (Wang & Yu, 2023; Drakulic et al., 2024) investigate this promising direction, but with different problem settings. Alternatively, Berto et al. (2024) improved convergence robustness by training on all tasks within a batch using a mixed environment.
Single-task VRP Solver. Most research focuses on developing single-task VRP solvers, which primarily follows two key paradigms: constructive solvers and improvement solvers. Consiructive solvers learn policies that generate solutions from scratch in end-to-end fashion. Early works proposed Pointer Networks (Vinyals et al., 2015) to approximate optimal solutions for TSP (Bello et al., 2017) and CVRP (Nazari et al., 2018) in an autoregressive (AR) way. A major breakthrough in AR-based methods came with the Attention Model (AM) (Kool et al., 2018), which became a foundational approach for solving VRPs. The policy optimization with multiple optima (POMO) (Kwon et al., 2020) improved upon AM by considering the symmetry property of VRP solutions. More recently, a wave of studies has focused on further boosting either the performance (Kim et al., 2022; Drakulic al., 2023; Chalumeau et al., 2023; Grinsztajn al., 2023; Luo et al., 2023; Hottung et al., 2024) versatility (Kwon et al., 2021; Berto al., 2023; Son et al., 2025) of these solvers to handle more complex and varied problem instances. Beyond AR methods, non-autoregressivee (NAR) constructive approaches (Joshi et al., 2019; Fu et al., 2021; Kool et al., 2022: Qiu et al., 2022: Sun & Yang, 2023; Min et al., 2023; Ye et al., 2023; Kim et al., 2024; Xia et al., 2024) construct matrices, such as heatmaps representing the probability of each edge being part of the optimal solution, to solve VRPs through complex post-hoc search. In contrast, improvement solvers (Chen & Tian, 2019; Lu et al., 2020; Hottung& & Tierney, 2020; Costa et al., 2020; Wu et al., 2021; Ma et al., 2021; Xin et al., 2021; Hudson et al., 2022; Ma et al., 2023) typically learn more efficient and effective search components, often within the framework of classic heuristics or meta-heuristies, to iteratively refine an initial solution. While constructive solvers can efficiently achieve desirable performance, improvement solvers have the potential find near-optimal solutions given longer time. There are also studies that focus on the scalability (Li et al., 2021; Hou et al., 2023; Ye et al., 2024), robustness (Geisler et al., 2022; Lu et al., 2023), and constraint handling (Bi et al., 2024) of neural VRP solvers, which are less related to our work. For those interested, we refer readers to Bogyrbayeva et al. (2024). Apart from such single-task VRP solvers, there are alternative approaches to complex routing problems, such as the PDP, where travel times change over time (Wen et al., 2022; Mao et al., 2023). These problems present additional dynamics that further increase the realism of VRPs.
B. Generation of VRP Variants
As mentioned in Section 2, we consider four additional constraints on top of the CVRP, resulting in 16 different variants in total. Note that unlike (Liu et al., 2024; Zhou et al., 2024), we do not generate node coordinates from a uniform distribution. Instead, we sample a set of fixed points from a given map. Here, we detail the generation of the five total constraints.
Capacity (C): We adopt the settings from (Kool et al., 2018), whereby each node's demand 6, randomly sampled from a discrete distribtution set, 21, .... 9}. For N 50, the vehicle capacity Q is set to 40, and for N 100, the vehicle capacity is set 50. All demands are first normalized to their vehicle capacities, that 8 = /./Q.
Open route (0): For open routes, we set o = 1 in the dynamic feature set received by the decoder. Apart from this, we remove the constraint that the vehicle has to return to the depot when it has completed the route or is unable to proceed further due to other constraints. Suppose the problem has both open routes (O) and duration limit (L.), then we mask all nodes i, such that 4 + di, > L, whereby dij is the distance between node U; and the potentially masked node vy. and L is
13

---

SHIELD: Multi-task Multi-distribttion Vehiele Routing Solver with Sparsity and Hierarchy
the duration limit constraint. For problems with both open routes (O) and time windows (TW), we mask all nodes vy such that l, + dij wef, where is the current time after servicing the current node. Finally, suppose route has both open routes (O) and backhauls (B), no special masking considerations are required as the vehicle does not return to the origin.
Backhaul (B): We udopt the approach from (Liu et al., 2024) by randomly selecting 20% of customer nodes to be backhauls, thus changing their demand to be negative instead. We also follow the same setup as (Zhou et al., 2024) whereby routes can have a mix of linehauls and backhauls without any strict precedence. To ensure feasible solutions, we ensure that all starting points are linehauls only unless all remaining nodes are backhauls.
Duration limit (L.: The duration limit is fixed such that the maximum length of the vehicle, I. 3, which ensures that feasible route can be found as all points are normalized unit square.
Time window (TW): For time windows, we follow the methodology in (Li et al., 2021). The depot node up has a time window [0, 3] with no service time. As for other nodes, each node has a service time of 8; = 0.2, and the time windows are obtained as following: (1) first we sample time window center given by 7/8 (wz + doz, wf - dzo -t), whereby dus = dæo the distance or travel time between depot Up and node vi (2) then we sample time window half-width h2 uniformly from [s./2, 2, w6/3 [0.1, 1], (3) then we set the time window as [uo, wf] = [MAX(uR, 74 h4), MIN 7: + h:)].
C. Neural Combinatorial Optimization Model Details
Neural constructive solvers are typically parameterized by neural network, whereby policy, me, is trained by reinforcement learning so as to construct a solution sequentially (Kool et al., 2018; Kwon et al., 2020). The attention-baun mechanism (Vaswani, 2017) is popularly used, whereby attention scores govern the terision-maaing process in an autoregressive fashion. The overall feasibility of solution can be managed by the use of masking, whereby invalid moves are masked away during the construction process. Classically, neural constructive solvers employ an encoder-decoder architecture and trained as tor-nece-----eueneee models (Sutskever, 2014). The probability of sequence can be factorized using the chain-rule of probability, such that
T
(r(
II po( 1,, 71--1)
(9)
The encoder tends employ a typical transformer layer, whereby
n= LN' (b) 11 + (H) "..,,""")
(10)
h/ = LN (b. FF(..)
(11)
where hy is the embedding of the i-th node at the 1-th layer, MHA is the multi-headed attention layer, LN the layer normalization function, and FF a feed-forward multi-layer perceptron (MLP). All embeddings are passed through L layers before reaching the decoder.
The decoder produces the solutions autoregressively, whereby contextual embedding combines the embeddings from the starting and current location as follows
h(c)
hAST + START
(12)
Then, the attention mechanism is used to produce the attention scores. Notably, the context vectors h(c) are denoted as query vectors, while keys and values are the set of N node embeddings. This mathematically represented as
U TANH
OK VDI
j i Te, <
aj
(13)
00
otherwise
whereby U is clipping function and DIM the dimension of the latent vector. These attention scores are then normalized using a softmax function generate the following selection probability
e
P Po (1)-) = E, ea
(14)
14

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
Finally, given baseline function b(-), the policy trained with the REINFORCE algorithm (Williams, 1992) and gradient ascent, with the expected return J
Vo)(O)
Vo
(15)
The reward of each solution R is the length of the solution tour.
D. Soft-clustering Algorithm Details
Algorithm Psuedo code of soft clustering algorithm
1: function CLUSTER
Require: encoder embeddings H, constraints vector yk, number of centers Ne, number of iterations B, initial embeddings
C, embedding size d
2: ad = W 7
3: for f- to do
4:
H WH(H)
5:
C f WollC, aal)
= SOFTMAX( HCT) CCompute attention scores) Va
6:
7:
C Es Nh, {Update the centers with data)
8:
CoUr = C+C C (Residual connection)
9:
C = NORM(CoUT) [Layer normalization)
10:
end for
11: return C
12: end function
15

---

SHIELD: Multi-task Muliidisttribttion Vehicle Routing Solver with Sparsity and Hierarchy
E. Dataset Details
USA13509
BM33708
Map of all points for K29976
Map all points for SW24978
Map of points for VM22275
for EG7146
Map points for F106339
Map all points GR3882
Figure 4, Plot of all 9 World Maps and their points
We utilize the following country maps² shown Figure 4: (1) U3593509: USA containing 13,509 cities; (2) JA9847: Japan containing 9,847 cities; (3) BM33708: Burma containing 33,708 cities; (4) KZ9976: Kazakhstan containing 9,976; (5) SW24978: Sweden containing 24,978 cities; (6) VM22775: Vietnam containing 22,775 cities; (7) EG7146: Egypt containing 7.146 cities; (8) F110639: Finland containing 10,639 cities; (9) GR9882: Greece containing 9,882 cities.
Pottps://wwee math. wwater 1oo wtt.oo//t.///o.//.//////////ooot wowp://rrs....ooor.......... html
16

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
F. Model sizes and average runtimes
Table 4. Overall number of parameters and average runtimes for all models.
Model
Num. Parameters
FLOPs VRP50
Runtime on VRP50
Runtime VRPI00
POMO-MTVRP
1.25M
52.88 GFLOPs
2.74s
8.30s
MVMoF.
3.68M
84.41 GFLOPs
3.72s
11.21s
MVMoE-Light
3.70M
84.03 GFLOPs
3,45s
10.38s
MVMoE-Deeper
4.46M
114.99 GFLOPs
9.23s
OOM
SHIELD-MoD
4.37M
95.76 GFLOPs
5.43s
17.70s
SHIELD
4.59M
106.72 GFLOPs
6.16s
20.07s
Table 4 showcases the number of parameters per model, the number of floating operations MTMDVRP50, and the runtimes on MTMDVRP50 and MTMDVRPI00. Note that the total FLOPs is calculated based on single pass through the encoder and one decoding step. The FLOPs is also a sum of the forward and backward passes for gradient updates. We only use one decoding step as inferior solvers will require more steps to solve the problem, and thus would also require more FLOPs.
G. Mathematical Notations
S
problem instance i
D.
Set of dynamic features at decoding time-step {
t
Decoding time-step
r-coordinate of problem instance i
y-coordinate of problem instance
Demand of node
mc
Opening timing of time-window for node
Closing timing of time-window for node i
Capacity of vehicle at decoding time-step
4
Current time-step
Oc
Presence of open route at time-step
Current length of partial route at time-step Set of all possible VRP tasks
KC
Q
Set of all possible distributions
8
The percentage of tokens allowed through a MoD layer Router score for node i
r
One-hot encoded vector of constraints for task k
Presence of open route at time-step &
B
Number of iterations of clustering
No
Number of cluster centers
Mixing coefficient between node and cluster j
17

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
H. Solver and Metric Details
use HGS (Vidal, 2022) for CVRP and VRPTW instances, and Google's OR-tools routing solver (Furnon Perron) for the rest. For HGS, we use the default hyperparameters, while for OR-tools, we apply parallel cheapest insertion the initial solution strategy and guided local search as the local search strategy. The time limit is 20s and 40s for solving single instance of size N 50, 100, respectively. For neural solving, utilize 8x augmentations the (æ, coordinaatss for the test set proposed by (Kwon et al., 2020). The following table details the various transformations applied.
Table 5. List of augmentations suggested by (Kwon et al., 2020)
f(x,,) 2)
(x, v)
(y, x)
(x, - y)
(y, 1 - x)
(1 - v, y)
(1 y, x)
(1 x, y)
(1 - y: x)
The optimality gap measured as the percentage gap between the neural solver's tour length and the traditional solver. This defined as
V R 1)
0
100
(16)
Σ
L,
where L3 is the tour length of test instance computed by the traditional solver, HGS or OR-Tools.
Detailed hyperparameter and training settings
Number of MoE encoder layers:
Total number of experts: 4
Number of experts used per layer:
Number of MoD decoder layers: 3
Capacity of MoD layer (number of tokens allowed): 10%
Number of single-heade attention decision-makinn layer:
Latent dimension size: 128
Number of heads per transformer layer: 8
Feedforward MI.P size: 512
Logit clipping U: 10
Learning rate: 14
Number of clustering layers:
Number of iterations for clustering:
Number of learnable cluster embeddings: 5
Number of episodes per epoch: 20,000
Number of epochs: 1,000
Batch size: 128
18

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
J. Additional Experiments AAlternative sparse approaches in Encoder
Table Performance of INVIT and SHIELD on the MTMDVRPSO and MTMDVRPIO0 scenarios. INVIT struggles with the complexity
of the MTMDVRP compared SHIELD despite using some form of sparse attention.
MTMDVRP50
MTMDVRPI00
In-dist
Out-dist
In-dist
Out-dist
Model
Obj
Gap
Time
Obj
Gap
Time
Obj
Gap
Time
Obj
Gap
Time
6.4082
9.1437%
66.48s
6.7462
9.09929%
66.84s
10.6057
17.2425%
66.65s
11.4286
18.4235%
68.06s
In-task
SHIELD
6.0136
2.3747%
6.13s
6.2784
2.7376%
6.11s
9.2743
2.4397%
19.93s
9.9501
3.1638%
20.25s
INVIT 6,2996
15.3570%
69.43s
6.6932
15.2064%
70.11s
11.1489
26.8217%
68.00s
12.1012
27.9947%
69.98s
Our-task
SHIELD
5.7779
6.0810%
6.20s
6.1570
6.3520%
6.20s
9.2400
5.6104%
19.92s
9.9867
6.2727%
20.18s
A similar sparse attention approach would be INViT (Fang et al., 2024). Essentially, INVIT proposes to only attend to the k-Nearest Neighbors (k-NN) during solution construction, as attention to all nodes introduces an aliasing effect, which confuses the decoder, resulting in poor srcision-making Only attending to the k-NN nodes effectively reduces the number of interactions amongst the nodes and thus introduces sparsity into the attention mechanism, a somewhat similar approach SHIELD. A key difference between the approaches is that INVIT's reduction is based on heuristic, the k-NN, while in SHIELD, opt to learn which nodes to focus on based MoD.
Results shown in compares SHIELD and a trained INVIT model. We utilize the same training and hyperparameter settings as INViT-3 on our data and environment setup. As shown, INVIT struggles with the multi-task dynamics of the problem, likely because the sparse attention mechanism relies on selecting the k-NN nodes based on spatial distance. This is highly inflexible and poorly suited for dynamic MTMDVRP setting. As such, essential nodes are possibly pruned away, leading inferior neural solver.
K. Additional experiments Effect of sparsity in Encoder
Table 7. Experimental study for the impacts of using MoD layers in the encoder on MTMDVRP50. Even by increasing the number of layers, the model's performance unsatisfactory.
In-dist
Out-dist
Model
Obj
Gap
Obj
Gap
SHIELD
6.0136
2.3747%
6.2784
2.7376%
In-task
SHIELD (MoDEnc-6)
6.2271
6.2578%
6.6213
7.6650%
SHIELD (MoDEnc-Ie 12)
6.1838
5.4944%
6.5817
7.1229%
SHIELD
5.7779
6.0810%
6.7570
6.3520%
Out-task
SHIELD (MoDEnc-6)
6.0432
11,5021 %
6.4894
12.9905%
SHIELD (MoDEne-12 12)
5,9846
10.3009%
6.4322
12.0432%
Table 7 studies the impact of sparsity in the encoder. We replace encoder layers with MoD layers of capacity of 10% and find that the model's performance degrades significantly, even after doubling the number of layers. This shows that the MoE encoder plays crucial role in the architecture it enables the model to leverage various experts capture broad range of representations for effective encoding. In contrast, the MoD introduces greater flexibility in the decoder, allowing the model to dynamically select layers for decision decision-making, which helps it adapt effectively to varying outputs.
19

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
L. Additional experiments Average layer usage per token for CVRP on various distributions
CMRP Batch from BM33708
Map
T4
10
Byenk
from VM22775
VM42275
5V/24979
kyer
Figure 5. Plot of layer usage for CVRP samples across three maps, with the z-axis node IDs, y-axis layer numbers, and values average usage frequency during decoding.
We conduct further analysis the simpler CVRP examine how the model generalizes across tasks and distributions. Figure presents a heat map where we average the number of times a layer is used when the agent is positioned on node. Note that the z-axis denotes the node ID, while the y-axis denotes the layer number, with the value indicating the average number times that combination called. For this analysis, we sort the nodes anticlockwise order based on their x and y coordinates to impose a spatial ordering. We observe that for maps with similar top density and curved shapes, such as BM33708 and VM22775, the MoD layers tend exhibit similar pattern layer usage, whereas map like SW24978 has much different sort of distribution.
M. Additional experiments Size Generalization to MTMDVRP200
Table 8. Performance of trained MTMDVRP100 models on MTMDVRP200. SHIELD is the superior model even when tested on prohlem sizes larger than those was trained on.
MTMDVRP200
In-dist Gap
Out-dist Gap
Model
Obj
Time
Obj
Time
Solver
13.7525
943.23s
14.8228
921.81s
POMO-MTVRP
14.5695
5.4613%
19,80s
15.9036
7.0430%
20.01s
MVMoE
14.6137
5.8753%
44.25s
15.9391
7.3486%
44.40s
In-task
MVMoE-Light
14.6420
6.0924%
40.87s
15,9581
7.4784%
41.92s
SHIELD-MoD
14.4123
4.7980%
37.89s
15.7342
6. 6.1487%
38.01s
SHIELD
14.3648
3.7939%
42.24s
15.6536
5.0516%
40.04s
Solver
14.4622
973.11s
15.7897
959.09s
POMO-MTVRP
15.5735
8.5203%
21.31s
17.1759
10.2531% %
26.78s
MVMoE
15.6040
8.8840%
45.49s
17.2145
10.5085%
45.23
Out-task
MVMoF-LLight
15.6412
9.1470%
43.22s
17.2423
10.7143%
43.94s
SHIELD-MoD
15.5373
7.4336%
39.13s
17.1948
8,8987%
39.06s
SHIELD
15.3896
6.4856%
42.86s
16.9555
7.8179%
47.92s
We generate and label additional dataset with 200 nodes each. For the MTMDVRP200, increased the time allowed to solve each instance to 80 seconds. Table 8 illustrates the zero-shot generalization performance of trained MTMDVRP100 models on the MTMDVRP200, SHIELD is still the superior model to the other baselines, showing sizeable performance gap on problems larger than it was trained on. Additionally, note that the inference time SHIELD comparable to MVMoE and MVMoE-Light, This is because in the MTMDVRP200, inference on the MVMoE models requires smaller batch sizes, whereas SHIELD's sparsity allows to process larger batches.
20

---

SHIELD: Multi-task Multi-distribation Vehiele Routing Solver with Sparsity and Hierarchy
N. Additional experiments - Generalization to CVRPLib
Table 9. Performance on CVRPLib data Sct-X-11
Instances vary from 101 to 251 nodes.
Set-X-1
POMO-MTI.
MoM
MiMot--Light
SHIHL
D-MMl)
SHIELD
SHIELDD-33400
Instanee
Opt.
Obj.
Gap
Obj
Gap
Obj.
Gup
Obj.
Gap
Obj.
Gap
Obj.
Gap
X-101-225
27591
29875
8.2781%
29189
5.7917%
29445
6.7196%
28967
4.9871%
28678
3.9397%
29346
6.3608%
X-n106k114
26362
27158
3.0195%
27061
2.6515%
27356
3.7706%
26909
2.0750%
27076
2.7084%
27192
3.1485%
X-1100113
14971
15420
2.9991%
15379
2.7153%
15387
2.7787%
15450
3.1995%
15316
2.3015%
15312
2.2777%
X-n1154410
12747
13680
7.3194%
13368
4.8717%
13536
6.1897%
13245
3. 3.9068%
13290
4,2598%
13472
5.6876%
X-n120-16
13332
13939
4.5%
14082
5.6256%
13980
4.8605%
13911
4 4.267995
18724
2.9400%%
13971
4.7900
X-n1254:30
55539
58929
6.1038%
58443
5.2288%
S9056
6.3325%
S8648
5.5979%
57426
3.3976%
58277
4,999%
X-n129418
28340
30114
4.0567%
29905
3.3345%
29970
3.55911%
298012
2.977666
29540
2.0733%
29695
2.6088%
X-m134-x13
10916
11637
6.6050%
11658
6.7974%
11612
6.3760%
11519
5.5240%
11274
3.27966%
114477
4, 86644%
X-139*100
13590
14295
5.1876%
14155
4.1575%
14121
3.9073%
13988
2.9286%
14004
3.046.%%
14152
4.1354%
X-n143-27
15700
17091
8,8599%
16710
6.43311%
16744
6.6497%
16621
5.866 5.86622
16548
5.4013%
16792
6.9554%
X-148-k466
43448
47317
8,9019%
15621
5.0014%%
15794
5.3996
45728
5.2477%
44739
2.9714%
45082
3.7608%
X-153-422
21220
23689
11.6352%
2
9. 8.64666
23510
10.791756
23541
10.9378%
23252
9.5755%%
23392
10.2356%
X-117-k133
16876
17730
5.0604%
17698
4.8708%
17713
4.9597%
17386
3.0220%
17366
2.9035%
17583
4.1894%
X-1624:111
14138
14845
5.0007%
14884
5.2766%
14746
4.3005%
14703
3.996246
14767
4.4490%
14804
4.7107%
X-n167-k10
20557
21863
6,35311
21898
6,5233%
21827
6.1779%
21664
5.2877%
21326
3.7408%
21566
4.90839
X-17245511
45607
50381
10.4677%
48863
7.1393%
48686
6.7512%
48434
6. 19864
48091
5.4468%
48613
6.5911%
X-n176-k26
47812
53848
12.62444%
52,02
9.3900%
91433
7.5734%
52313
9:4140%
S1811
8.36640
50887
6.3114%
X-n181-223
25569
26480
3.5629%
26661
4.2708%
264990
3.60200%
26155
2.2957%%
26237
2,6125%
26333
2.9880%
X-n186-k15
24145
25900
7,268668
25695
6.1195%
25613
6.0799%
25409
5.2350%
25503
5.621-4%
25372
5.0818%
X-n190-18
16980
17826
4,962399
18121
6.7197%
18125
6,7432%
17417
2.57366%
17802
4,84110%
17846
5,1001%
X-n195-k51
44225
49703
12.38679
47834
8.1605%
17704
7.8666%
47660
7.6495%
46509
5.1615%%
47731
7.9276%
X-2200-336
58578
61857
5.5977%
62039
5.9084%
61871
5.6216%
61384
4.7902%
61375
4,7748%
61729
5,3792%
X-n209-k16
30656
32754
6.8437%
32725
6.7491%
32605
6.3576%
32157
4.8963%
52214
5.18011
32083
4.6549%
X-22194733
117995
120795
2.72122%
119924
1,9805%
121201
3.0665%
119679
L.7711%
119847
1.9150%
119560
1.6710%
X-m2284c23
25742
30042
16.7042%
28629
11.2151%
28754
11.7007%
282066
9.571196
28118
9.2301%
28119
9.2339%
X-1237-414
27042
29217
8.0430%%
29252
8.1725%
7.2517%
28560
5.6135%
28743
6.29012%
6.7968%
X-n247-4:0
37274
43111
15.6997%
40868
9.6421%
41735
11 11.96815
41556
1 4879%
40676
9.12700
41266
10.7099%
X-n251-428
38684
41321
688168%
40874
5.6613%
40854
6096%
40316
4.2188%%
4,4618%
40602
4.9581%
Averages
31280
33601
7.1148%
35111
6,0845%
33174
6.1773%
32902
5.1979%
32703
4.6437%%
32897
5,3961
Table 10. Performance on CVRPLib data Set-X-2,
Instances vary from 502 to 1001 nodes.
Sei-X-2
POMO-MII
MVMoE
MVMots-Ligt
SHIELD-MoD)
SHIELD
SHIHLD-EP-H
Instance
Opt.
Obj.
Gup
Obj.
Gap
Obj.
Gap
Obj.
Gup
Obj.
Gap
Obj.
Gap
X-1502-339
69226
73599
6.3170%
75113
8.5040%
75679
9.3216%
73184
5.7175%
73062
5.5413%
73445
6.0945%
X-1513-121
24201
27955
15.5118%
29114
21.6644%
28/133
17.6935%
27478
13.5408%
27217
12/1623%
27373
13.1069%
X-9524-k153
154593
175923
13.7975%
174409
12.8182%
170334
1822%
167380
8.2714%
169715
9.7818%
166660
7,8057%
X-n536-156
91816
101866
10.5645%
105896
11.6505%
104-08
10.0816%
102157
7.7083%
102337
7.7926%
103042
8.6114%
X-1548-150
86700
94290
8.7543%
93623
7,98509
92798
7.0334%
91483
5.5167%
91726
5.7970%
92055
6.17655
X-n561-k112
12717
45781
14.1988%
19953
16.9394%
48678
13.951668
47328
10.7943%
47639
11.5223%
47485
11.618%
X-1573-130
50673
57151
12.7839%
55796
10. 10.10
55870
10.2560%
54064
7.8760%
S3936
6.493%%
55204
89416%
X-1586-k159
191316
208217
9.40599
209038
9.81733%
208510
9.5599%
208408
7.9300%
205487
7.9715%
208175
9.38399
X-n599-192
106451
118994
9.73144
119879
10.5375%
118864
9.601668
117615
X.4409%
116950
7.8367%
118514
9. 9727W
X-n613-462
59535
68882
15.7000%%
72992
22.6035%
69091
16.0511%
66657
11 11.9627%
66715
12.0601% 96
66419
11 16.9%
X-1627-443
62164
69756
12.2129%
69197
11.31369
68302
9.8739
67125
7 7
67494
8.5741%
67059
7.87435
X-3641-k35
63682
72638
14.06.66%
72348
13.608256
71041
11 11.5889%
69425
9.0182%
69156
8.5958%
69617
9.3197%
X-665-k1311
105780
115083
7.7758%
113186
5.9993%
113610
6.3963%
111711
4.6179%
110808
3.4913%
111542
4.4596%
X--670-k130
146312
177344
21. 19.9%
173046
18.25575
170128
16. 3983%
164820
12,63338
166737
13.9443%
164140
12. 1696%
X-m685.k75
68205
79362
16.3580%
84485
23.869256
79502
16.5633%
76224
11.7572%
12.4199% 76676
76195
11.7147%
X-1701-kM1
81923
90163
10.058206
92522
12.9378%
89812
9.6298%
88608
8.1601 %
$7959
7. 7.3679%
83603
8. 1,404%
X-7716.335
43373
50636
16.7454%
$1003
17.591666
49429
13.96268
47821
10.2552%
47996
10.6587%
47586
9.7134%
X-a733-k159
136187
L58691
16.5265%
156545
14.9186%
156747
15.0969%
118203
8. 8.8232%
149217
9 9.5677%
L53661
12.8331%
X-a749.198
77269
88333
14.3158%
91569
18.5068%
88438
14.4547%
84651
9.5536%
85367
10.4803%
85824
11.0717%%
X-1766-k71
114117
135772
18. 18.664126
133725
16.8751%
129996
13.61607%
128128
11. 11.96349
128052
11.91699
127179
L1.1539%
X-1783-448
72386
84162
16.2683%
85094
17.5559%
82690
14.23488
80855
11 11.6998%
80521
11.2388PP
80358
11.0132%6
X-1801-k10
73305
85008
1.. 15.96-18%
6-1025
14.6238%
83210
13.51200%
81070
10.5927%
80637
10.0020%
81015
10.5177%
X-a819-A17
158121
177282
12.1179%
178389
12.9445%
175340
171630
H.5435%
172020
8.7901%
175820
1933%
X-2837-k112
193737
213908
10.1115%
211165
10.5442%
211521
9.1795%
208552
7.64
209350
8.0589%
210164
8,63. 8.6339%
X-n856-195
88965
99911
10.3037%
102485
19.0%
98990
11.2665%
99014
11. 11.2955%
96889
890695
97602
9,7083%
X-8876-199
99299
110191
10.9689%%
111857
12.64679
111044
1 82799
106826
7. 7.58011 %
106180
6.929655
107710
8.47049%
X-0895-337
53860
21.1975%
66353
23.1953%
64716
20.15607%
62114
15.3349%
62101
15.3008
61552
14.2815%
X-1066-2007
329179
3600152
9. 375888
$625966
10.15164
359144
9.1941%
354793
7.78122%
353567
7. 404775
355423
7.97266%
X5936-k151
132715
173297
30.5783%
167723
26.378346
163193
22.9650%
158308
19, 19.2842%
159965
20.5327%
156897
18.2210%
X-99574487
85465
981.92
148213%
99442
16.3541%
97109
13.6243%
94209
10.2311%
93672
9.6028%
94118
10. 1246%
X-97991588
118976
132128
11 (0544%
132449
11.3241%
131752
10.7383%
128765
8.2277%
129968
9.2388%
127952
7.5444%
X-11001-k43
72355
87428
20.%
87802
21. 21.34895
862885
19.2523%
825666
14.5270%
82407
15 892899
N2253
13.6799%
Averages
101874
[15725
14.0802%
116136
14,9631%
114225
12.7539%
111.54
9.8527%
111598
9.81647
111905
10.0618%
Tables 9 and 10 showcase various models trained on MTMDVRP100 applied to data from the CVRPLib Set-X-1 (Large) and Set-X-2 (Extra Large). These instances have varying sizes from 101 to 1001 nodes. Additionally, we include SHIELD -E4400, the 400th epoch of training SHIELD, which has similar in task in-dist performance compared to MVMoE. SHIELD is a s
significantly superior model in terms of zero-shot size generalization.
21

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
O, Additional experiments Importance of Varied Distributions
Table 11. Performance of all models when trained on only Uniform data. We retain similar layout to Table 1 but all distributions
considered out-of-distriiution in this case.
MTMDVRP50
MTMDVRP100
Model
In-dist
Out-dist
In-dist
Out-dist
Obj
Gap
Obj
Gap
Obj
Gap
Obj
Gap
POMO-MTVRP (Uniform)
6.0932
3,8834%
6,4104
4.0007%
9.5517
5.7774%
10.1878
6.1687%
MVMoE (Uniform)
6.0779
3.6000%
6.3930
3.6710%
9.5065
5.2291%
10.1454
5.7632%
MVMoF:-Ligh (Uniform)
6.0926
3.8418%
6.4061
3.8254%
9.5116
5.3037%
10.1407
5.7016%
In-task
MVMoF-Deeper (Uniform)
6.0580
3. 3.1964%
6.3822
3.5062%
OOM
OOM
OOM
OOM
SHIELD-MoD (Uniform)
6.0482
3.0379%
6.3666
3.2037%
9,4120
4.1218%
10.0525
4.7131 %
SHIELD (Uniform)
6.0414
2.9223%
6.3596
3.0832%
9.3956
3.9280%
10.0373
4.6271 %
IRMO-MTVRP (Uniform)
5,8762
8.1526%
6,2457
8,3681 1%
9,5947
10.1253%
10,3081
10.6234%
MVMoE (Uniform)
5.8602
7.7505%
6.2251
7.8788%
9.5514
9.4994%
10.2716
10.2298%
MVMoE-Ligght (Uniform)
5.8802
8.1328%
6,2414
8.0983%
9.5490
9.5566%
10.2555
10.1128%
Out-task
MVMoE-Deepee -Deeper (Uniform)
5.8292
7.0524%
6.2034
7.4642%
OOM
OOM
OOM
OOM
SHIELD-MoD (Uniform)
5.8103
6.7257%
6.1769
6.9455%
9.3977
7.6183%
10.1111
8.3284%
SHIELD (Uniform)
5.8035
6.6394%
6.1712
6.8616%
9.3721
7.2676%
10.0889
8.1911 %
Table 11 displays the performance of models when trained purely on uniform data. Note that while we retain the same table layout as Table I, all distributions are considered as out-of-distribution in such case as the model does not see them all. Evidently, all models degrade in their predictive performance, even though SHIELD still retains its overall superior performance.
P. Additional Experiments Single-task Multi-distribution
Table 12. Performance of various models trained on the CVRP task with multiple distributions.
CVRP50
CVRP100
Model
In-dist
Out-dist
In-dist
Out-dist
Obj
Gap
Obj
Gap
Obj
Gap
Obj
Gap
POMO-MTVRP
6.6511
1.2260%
6.9763
1.4699%
9.9795
2.3587%
10.6194
3.3445%
MVMoF
6.6454
1.1401%
6.9709
1.3858%
9.9733
2.2932%
10.6189
3.2974%
MVMoE-Light
6.6482
1.1814%
6.9723
1.4112%
9.9681
2.2398%
10.6237
3,4012%
AVMoE-Deeppl
6.6313
0.9207%
6.9628
1.2731%
OOM
OOM
OOM
OOM
SHIELD-MoD
6.6284
0.8798%
6.9552
1.1623%
9.9346
1.8948%
10.5545
2.6917%
SHIELD 6.6269
0.8570%
6.9474
1.0338%
9.9278
1.8203%
10.5579
2.6541 %
Table 12 displays the performance of various models when trained in a single-task multi-distribution setting. Here, we choose CVRP to be the task at hand. SHIELD remains the best- pesst-erforming model in such a scenario, suggesting that its architecture not catered purely multi-task multi-distribution problem only.
22

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
Q. Additional Experiments Multi-Task VRP
Table 13. Performance of all models on the MTVRP scenario where all models are trained on the Uniform distribution.
MTVRP50
MTVRP100
Model
Obj
Gap
Obj
Gap
POMO-MTVRP
10.0470
2.9086%
13.9662
4.2795%
MVMoE
10.0213
2.6279%
15.8868
3.7400%
MVMoE-Light
10.0436
2.8539%
15.9182
3.9825%
In-task
MVMoE-Decpee
10.0020
2.4281%
OOM
OOM
SHIELD-MoD
9.9865
2.2522%
15,8134
3.2617%
SHIELD
9.9732
2.1252%
15.7754
3.0124%
POMO-MTVRP
10.3023
7.1085%
16.9683
8.2123%
MVMoE
10.2705
6.7095%
16,8697
7.4778%
MVMoF-LLigt
10.3004
7.0367%
16.9036
7.81 880
Out-task
MVMoE-Deeper
10.2342
6.3488%
OOM
OOM
SHIELD-MoD
10.2135
6.0721 %
16.7268
6.5004%
SHIELD
10.1985
5.9522%
16.6817
6.2304%
To verify that our architecture improves overall, we trained all models on the MTVRP setting using the uniform distribution. that SHIELD still clearly the better-performing model.
Table 13 showcases the performance of all models. Here, Additionally, the gaps between the models are less significant once remove the varied distributions. This indicates the difficulty of multi-distribution scenario having varied structures with multiple tasks is more complex. Since our architecture is more flexible, it generalizes better in the MTMDVRP scenario.
23

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
R. Additional Experiments Behavior of Scaling During Inference
In-Task In-Distribution
In-Task Out-Distribution
2.50%
---00003 0.0232
6.50%
y 0.003in()) 0.0596
6.00%
2.20%
5.50%
Opt: Gap
2.00%
1.80%
5.00%
1.60%
4.50%
1.40%
4.00%
1.00%
3.50%
20
40
60
80
100
20
40
60
80
100
Sampling Width
Sampling Width
Out-Task In-Distribution
Out-Task Out-Distribution
2.80%
-3003.003 0.C2E1
7.00%
>m-0.005mn(s) +.00633
2.40%
6.50%
2.20%
Opt. G89
2.00%
Opt.
1.80%
5.30%
1.60%
5.00%
1.4%%
4.50%
1.20%
20
40
60
80
100
20
40
60
80
100
Sampling
Sampling Width
Figure 6. Overall performance of SHIELD with varying sampling widths.
For NCO solvers, we can allocate more test time perform sampling and find better solutions during inference, this experiment, reduced 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 are shown in Figure 6. As shown, increase the sampling width, the general performance of the model increases (lower gap is better) in logarithmic fashion. This suggests that while we can allocate more test time for inference, its effectiveness eventually saturates.
24

---

SHIELD: Multi-task Multi-distribation Vehiele Routing Solver with Sparsity and Hierarchy
S. Detailed experimental results
Tabl
Table 14. Performance of models on USA13509
of
Time
2m 40%
7.96
10.71s
9.825
17.29s
19.700 20.70s
6m 368
9.14s
12.07s
11.37%
19.06s
21.02s
8.82x
11.80s
10.85%
19.04s
21.678
2m 39%
7.41s
9
9,05s
16.12s
18.05%
2m 45
8.58
11,218
10.418
18.34s
20.58s
9.24%
12.23%
11.34s
19.54s
22.05%
2m 4%%
9.20s
11.82s
11.26s
18:61s
20.744 70.744
2m11 386
8.92%
11.57s
10.84s
18.648
20.80s
2m
2m
MTMDVRPI0N
Gop
-1.14908
-1.8885%
-1.253668
-1.89959%
-2.01788
7.7828%
7.3912%
7.691
198
6.579498
6.1796%
6.7325%
6.3105%
6.6435%
4.8700%
4.8972%
10.52718
9.20855%
10.30825
7.61098
12.0111%
11.1622%
11.7195%
10.033%%
9.5019%
6.6966%
6.26998
6.5819%
4.8210%
4,54168
8.099%
7.8168%
8.0151%
6.98728
11 11.90999
11.3 11.39033%
11.7672
9.99 1
9.5539%
Oh)
11:5478
11.4109
11 11.3828
11,3988
11,3256
11.3108
140699
16,1244
16.0672
16.1132
15,9441
15,8602
9.138
10,0576
10.0188
100450
9.8820
98557
5.1119
6.5330
6.4591
6.2117
6.3605
6.1191
9.38188
10.5023
19,4119
10.4753
10.3176
10,2672
9.364
10.0586
10.0215
10.012
9.8844
9.5500
13.4033
16.6092
16.5711
16,6005
16.4395
9.4629
10.5841
10-5339
10.5717
10.4016
10.36 10.3608
15
Time
mm 10s
5.28%
30075
6.58
5.025
5.7%
1m 19s
2.5%%
3.77%
3.53%
9.97%
5.71
6.50%
2.75%
3.91s
3.56%
10.522
6.74
Im: 9N
3.39%
3.12s
8.32
5.05
5.77
Jm 12
2.83%
3.75%
10.0%%
5.8%
6.72%
3.15
4.0%%
746
10.6
6.0%
6.9%
mm 225
3.9%
3.64
9.85%
5.73%
Jm 185
3.18%
3.97
3.8%
10.256
5.99
6.82
Jm
mm
MTMDVRRPS
0.6848%
0. 1899
0.2923%
0.0221
-0.1102%
0.1943%
5.4400%
5.1344%
5.3042%
4.6368%
4.3588
5.201
5,19538
5.4410%
4,5388%
4.1838%
7.8395%
7.4030%
8.0245%
6.7854%
6.29848
6.2536%
10.6484%
10.3199%
10.6996%
10.08366
9,6962%
9.4721
5.174%
5.0931%
5.2840%
4.7727%
4,2439
4. 4.1655%
9.4717%
8.9333
8.9361
8.8499
8.4543%
10662
10.3227%
10.4245%
9.9740%
9.6
9.431%%
Gop
Ob)
7,57
7.6238
7.5835
7.5922
7,5709
7.5612
7.5547
9,2000
POMO MTVR 9,7027
9.6755
9.6911
9.6401
9,6332
9.609S
5.9178
6,2255
6.2274
6,2421
6. 6,7870
6, 6,16656
4,0895
4,3940
4.4193
4,3668
4,3469
4.4464
5,8937
6.5213
6,5206
6,5279
6,1880
6.4776
6.4546
5.8.19
6.1357
6,1313
6,1102
6,011
6,0750
91061S
991196
9,8671
9,8627
SHIELD- 9,8222
9,7819
3,8173
POMO MTVRP 6.4355
6.4230
6,4289
6,3975
6,3813
6.3687
6.
6.
POMO-MIV MTVRP
MVMoE- Light
MVM Deeper
SHIELD-MOD
MVM Light Light
MVMoE- Doeper
SHIELD MoD
POMO MTVRP
MVM Light
E
POMO MTVRP
MV Light
MVM Deepey
SHIELD-N MoD
POMO MTVRP
MVM Light
MVM MVMME--Duepe DARRAT
SHIELD MoD
POMO-MI MTVRP
MVMoE-Ligh Light
MVM RIMMoEDDepe Deeper
POMO MTVRP
MVM Light
MVMOE Denger
MVMoE Light
MVM DoejAY
SHIELD MoD
OR-cools
MVMoE
SHIELD
OR-500S
MVM
SHIELD
MVM
SHIELD
OR-cools
MVMoB
SHIELD
OR-toos
MVM
SHIELD
coOls
MVMME
SHIELD-MO
SHIEL
OR-c0ols
MYMM
SHIELD
OR-00os
MVM36
SHIELD
VIPL
VRETW
OVRPTW
OVRPBL
OVRPATW T
OVRPLIW
VRPBLIW
OVRPELIW
Time
2m 30s
11.32s
10.655
17,9F3
20.33x
2m 385
7.46%
10.24h
9.38%
17. .7.00s
19 19,4
6.71s
8 966
8 6.28
15.12s
16.95%
2m 25s
6.9%
9
8.69%
15.75%
17.70s
2m1266 264
7.91%
10.73s
9.79%
17.5%
19,8%
2m 22
7.40%
9.64s
8.91s
15.81
17.60s
11 39%
10.69
17.99%
2m 36s
9.90%
12.93s
12.05%
20.01s
22,488
2m
2m
MTMDVRP100
Cap
3.09AU%
2.8201
2
2.309885
5.9345%
5.1600%
5.5529%
3.8935%
3.31
1.7366%
1.2943'%
1.4965
0.5298%
0.2755%
10.55368
9.3 9.3825%
10.3667%
7.5796/8
6.9218%
5.983 1%%
5.2231
5.6141%
3.90509
3.4500%
1.7249%
1.2302
1.4510%
0.5440%
0,2555%
8.0943
7.9169%
8.080/3
6.9561
3.0087%
2.6499%
1.91
1.8171%
1.5234%
110081
11.3655
1133352
11,3403
11,27/7
11.2701
6,8227
7,2755
7.2222
7.2498
7.1316
7.0944
8,5712
8.783
8.6799
8.9976
R6145
8,5929
3.484
6.5687
6.9899
6.524
63393
6,335
6.9599
7,3699
7.3770
7,3444
7,2277
7.1917
R.5009
8,7249
8.6277
8
8.6288
3,5988
13,4009
1666466
16.6193
16,6460
16.4699
15,8230
16.2667
16.2003
16,2552
16,0760
16.0317
Ohj
Time
mm 24h
166
3.885
9.2s
6.0%
6.69%
Im 10s
2.7
3.35s
3.16s
8.07s
5.21
6155
36
2.164
3.03
2.90
7.37%
4.69
5,26s
1m 76
2.28
3
3.33s
8,31s
1.9%
5.00
Im 12
2.37%
3.174
913s
5.274
6.33%
2.31s
3.24%
3.06s
7.78%
4.77%
5.37%
Fm 145
3.88s
3.61s
9.58s
5.63s
6.24s
Imn 145
2.81s
3.92s
3.70%
10.2s
5.74s
6.2%s
1m
MTMDVRESD
Cap
2.0132%
1.50086%
1.5887%
1.5839%
1.2313%%
4.2675%
3.9312%
4.20139%
3.2923%
29355%
2.670%%
21771%
1.7267%
1.9970%
1.6146%
1.366%%
1.210%%
7.9311%
7.4408%
806448
6.7749%
6.3291
6.2802%
4.534%
4.082%%
4.4275%
3,79799
16566
29169%
2.5288%
19965%
21643%
2.06145
1.473%
1,259V%
9.6432%
8.89428
9.1353%
8,8750%
8.49709
4.0016
3,5599%
3.6970%
3.5322
3,06155
2,8639%
OKj
7,522
7.55007
7.5570
1.5411
7.5295
4,5943
4,7914
4.7759
4.7868
4,7453
4.7290
4,7 168
5,9595
5.932
5.9474
5.9275
5.9091
5,9019
OR-00ols 4,0952
4,4023
4,4276
4.3726
4.354L
4.3542
4,5923
4,8005
4.7809
4,7959
4,7667
4.7383
4,7261
5.9697
5.9382
5.9479
5,9425
5-0058
5.8952
9.221
10,0372
10.0612
10.0-60
10.0014
9,2840
9.6555
9.6052
9.62112
9.6122
9.5665
9.5422
10.
POMO-MIVAR MTV-
MV Light
MVM MVMoe-Deeper Deeper
SHIELD-MOD
SHIELD
OR--0001s
POMO MIVRP
MVMOE
MYMaE-Ligg Light
MVMoE-DOO Deeper
SHIELD DE MAD
SHIELD
POMO-MT MTVRP
MYMOE
MVMOF. M.g Light
MV MVM.E-D.C MoMoe-DDaper Decper
SHIFLD MaD
SHIELD
POMO MTVVP
VMME
MYMeE-LAE Light
MVMOE- MOME--Dspp Deeper
SHIELD WELLD-M M&D
SHIELD
OR 500ls
POMO- STVRR
MYMOE
MVMoF-Ligh Light
MVMEE- WVMEE-DegRE Deyper
SHIELD D.D.DD MAD
SHIELD
toods
POMO-MIT RTP
MVMOE
MV MOE-
MYM Desper
SHIELD-MODD
STEEDD
OK--00lS
POMO-MPT MIVRP
VMME
MV MOM- Light
MVMOE DVMoeeDeeper Deeper
SHIELD-MO M-D
SHIELD
OR--0005
POMO-MTT MTVRP
MYME
MVMoE-Ligh Light
MVMOE-DeypS
SHIEL LD MaD
SHIELD
HGS
USA13509
Problem
CVRP
OVRP
VRPB
OVRPB
OVRPI
VRPBL
YRPBEW
VRPLIW
In In-
Our-toak
25

---

SHIELD: Multi-task Multi-distribation Vehicle Routing Solver with Sparsity and Hierarchy
Fable 15. Performance of models on JA9847
Time
2m 39%
8.00%
11.07
9.86s
17.32s
19.60%
6m 3.3
9.14
12.19%
11:346
19:06s
21 21,62s
2m
8.79%
12.29
10.92%
18.80s
21.3%
2m 35g
7.40%
10.00s
8,94%
16.27
18.05
2m
8.45%
11.200
10.45
17.94
20.13%
2m
9.15%
12,62s
11.48k
19.20k
21 11.00%
2m 46:
9:23s
12.0%%
11 11.2%
18.09
20.94s
2m 35x
8.822s
11 11.62s
10.79
18:30s
20.45%
MTMDVEPION
-1.233898
11.56709
-1.3629%
-.0387
-2.0540%
7.98 17%%
7.48289
7.8991%
6.6742%
6.4377%
7,05536
6.7570%
7.2667%
4,947666
4.9260%
15.0175%
13 53.509%
14,82588
10.26005
9.4704%
11.7303%
11.1125%
11.5058%
9,3009%
8.75188
7.307398
6,001186
7.16145
4.8308%
4.75%%
68330%
6.39739
6.832%
5.5222%
5.1504%
11 102666
10.9459%
9.1647%
8,79849
Gap
0k)
8.9500
8,8637
8,8337
8.8521
8.7924
8,7904
11.3101
12. 12.1846
12.1740
12,038
12,0109
6.7764
7,2570
7.2159
7.2521
7,0928
7.0919
3.8700
4,5780
45206
4,5720
4,3889
4.35%
6,8126
7,5900
7.5476
7,759
74264
7.78%6
6,3440
7.3216
7,2802
7,3130
7.1516
7,1484
12,1613
12.518
12.8821
12,9771
12.7737
12,7383
68237
7,6099
7.5505
7.5902
7.4267
7.4043
Thme
mm 9'
3.58
3.07%
8.34
5.02%
5.79
16
2,80s
3.535
9.88%
5.66%
6.43
mm 125
2.69
4,255
10:29s
5.71
6.5%
mm 7s
2.37
3.6%
3.11s
8.22s
5.04
5.70%
2
4,20%
3.67%
9.91s
5,74
6.52
mm 176
4,20%
3.68%
10.39s
5.8%
6.75%
1m 22
2.9%
3.5%
9.76k
6.26%
mm 198
2,8.5
4.33
10.058
5,82%
MTMDVVIESS
0.6312%
0. 1612%
0.2571
0.0022
0.1350%
402034%
59169%
5.5424%
4.903S
4.7889%
4.7112%
6.895
6
5.8712
5.6412%
5.880%
11.2299%
10,8999
12. 12.4295%
1647%
871638
11,7626%
11. 11.3687%
11.53399
10.5600%
10.01525
9.9572
6.8511
6.6381
7.0211%
6.0241%
5.5133%
877784
8 8.2867
7.9577%
7.540%%
7.243%
11.96.22%
11 11.3344%
11.719%%
10.7374%
10. 10.1687%
Gop
Obly
5.9291
5,9550
5.9391
5.9257
5.9177
5.9140
6,9905
7.2449
7.2174
7.17U8
7. 7.1688
7.1 715
4,1882
4.4770
4,4652
4,4289
4.4245
4,4182
2.7264
3.0326
3,0226
3
2.9763
2.9640
2,9638
4,5988
4.5813
4.5493
4,5299
4.5 4.5198
4,1520
4,4265
4.4221
4.7809
4.3734
6,8945
7.4997
7.4476
7.4418
7.3976
7,3750
4.0711
4.5.57
4,5427
4.5.00
4,5088
4.4880
4, 4,4808
MTVV
MV Light
SHIED MaD M&D
POMO POMO-MTVE MO-MTVRE RP
MV MOE- MoE-Lighht Light
MYM Deeguer
SHIEL SHIELD D-D
POMO MTTVR RRP
M MVMOE- MMME--DDee Dosger
SHIELD MaD
POMO OTTVRR
MVMoE-LiE Light
MYM Despeet
STIEL D. MaD
POMO MTT RP
MY MOE- Light
MYMEE MVMoE--Degue Deeeger
SHIELD-MO DELD
POMO MTTV
MVM Lig-Light Light
SHIELD M&D
POMO POMO-MIV MO-TTVR RU
MV MVV- MoE-Light Light
MVMOE. MYMoE-Desgu Desper
SHIEL SHIELD-MON D-D
POMO METVR VRP
Light
M MMMEE-- Desgeet
SHIEELD MoD
OR-toels
MVMoE
SHIELD
OR tonis
MVMoE
SHEEL
OR -ools
MYMoE
MV
SHIELD
OR -2--oool
MVMOE
SHIELD
MYMOE
SHEELD
ORC-DoeS
MYMOE
SHIELD
OR lonis
MYMOE
SHIELD
OR A0ol
MYMoE
SHIELD
MVM
MV
VRPL
VRPTW
OVRPTW
OVRPBL
OVRPBIN
OVRPLTW
VRPBLIW TW
OVRPAETW
Time
2m 12s
11.60s
10.59
18,024
20.42
2m 40s
7.55%
10.99
9:31s
17.31s
19.51s
2m 308
6.6%
8.9%%
8.25%
15.08%
16.93s
2m 39'
7.02%
9.56s
8.6
15.83
17 17.64s
8.00s
11.59
9.7%
17.21s
19.93x
2m 49%
7.38s
8.87%
15.77%
17 64.
2m 42x
8.52s
11.42
10 10.59s
17.90s
20. 18
2r0 50s
9.92%
12.99
19.96%
22.5
MTMDVRP100
Cap
2.7145%
2.3673%
2.5692%
1.89002
18824%
6.9041%
6.4637%
3 36667%
3.2637%
1.6225%
1.135%%
1.477%
0.3003%
1.1965%%
15.0151%
13.2704%%
14.6921 98
10. 18SU3
9.5759%
7.1472%
6.1290%
6.4924%
3.2500
3.5944%
1.1785%
1.6473%
1.975%
0.3668%
0.0026600
6.8000%
6.2745%
6.7859%
5.4695%%
5.0097%
2.5.99%%
2.1590%%
2.4-00%
1.2312%
1.0937%
Ok)
8,7045
8.9352
8,0055
8,9223
8.8645
868
5,1676
5.5171
5.4055
5.3115
S,3300
6.448
6,5417
65100
6.4567
6,4294
3,9796
4.5683
4,5028
4.5577
4,5780
4,3530
5,4586
5,0084
5,4262
5.2866
5,2775
6:4000
6,6699
6,4997
6.9901
6,4182
6,4115
11.3462
12.0045
12.5412
12,3954
12.4460 2244660
12,3966
12088
12.3506
12.3045
12.3385
12.1935
12.1775
Tane
mm 21s
1.288
4.445
9.06s
3,966
6.63%
Im 8
2.33s
3
8.54s
5.32s
6.08
1m 36
113
3:33
2918
7025
4.6%
5.28
mm 11s
2.25%
3,63s
3,01
8.
4.918
5.65%
2.36s
3.78%
3.17%
9.01
5.258
6.12s
mm 1m
3.638
3.02s
8.09%
4.7%%
5.35%
Im 20x
2.73%
3.59
9.44s
5.578
6.12%
1m 24h
1.84s
4.228
10.028
5.71%
MTMDVRPSS
1.8009%
133%
1.466 9%
1.2084%
1.0679%
5.0325
6.4499%
4,08985
3.7566%
3.611%
2.1878%
1.8598%
2.01
1.6420%
1.38225
1,2035%
11.5013%
10.9755%
12.5473%
9.28
8.657%
8.7000%
6.0070%
5.6644%%
6.40905%
4.4067%
3.705256
3.6483%
2.1667%
1.78412%
1.9700%
1.900%%
1.3514%
1.004%
86621
8 8.3462%
7.8732%
7.4631%
7.1440%
4.09H66%
3.5074%
3.5980%
3.3901%
2.8305%
2.7590%
Gap
0bj
5.0347
5,9686
5.04
5.9479
5,9528
5,9249
5,9207
3,3709
3,5699
3,5610
3,5800
3,3076
3,4963
3,49
4,4164
4.5219
4,4959
MVMoE-Ligg 4,5026
4,4856
4,4747
4,4667
2,0854
2,9943
2
3.0230
2,9348
2,9243
2.0195
3,5789
3.5694
3,5995
3.5249
3,5010
3,4964
4,3894
4.4933
4.4657
4,4737
4,4728
4.4469
4.4357
6,7862
7.374U
7.3203
7,3267
7,3205
7.2766
7,2522
7,0420
7.3305
7.2767
7,2805
7,2766
7,2300
7,2230
HOS
POMO STNVP
MVMOE
MVMoE-Ligh
MYMoE-Des
SHIELD McD
SHIELD
OR took
POMO-MIN MINRR
MVMoEE
M MVMOE-LLgHE Ligh
MVM McE--Deperr Desper
SHIEL SHIELD-MOD
SHIELD D
OR-t0ols
POMO POMO-MTV MTVR
MYMEE
MV MoE- MoE-Deeee Desper
SHIELD MaD
SHIELD
OR-tools
POMO-ME MTVRP
MVMOE
MVMoE-LLggh Lighh
MVMoE-De MoE--Dooper Deoper
SHIELD MaD
SHIELD D
POMO-MIN MEVRP
MVMOE
MVMOE-L
MVM Deopes Desper
SHIELD-MOD
SHIEL D
OR-400ls
POMO MTVRP
MVMOE
MVMeE-Light
MV MOE-EEDEE
SHIELD MEILDMMl MaD
SHIELD
OR took
POMO-MI MIVRR
MYMOE
MVMBE-LURE Lig
MVMGE- EVMoEE-Deper Desper
SHIELD SHIELD-MO) D-M
SHIELD D
OR OR-Gools
POMO MTVRR
MYMEE
MVMoE.L.g Light
MVM Moggeer Deoper
SHIELD McD
JA9847
CVRP
OVRP
OVRPS
OVREL
VRPBL
TRPBTW
VRPLIW
In-tosk
Out task
26

---

BIELLD Multi-task Multi-distribation Vehiele Routing Solver with Sparsity and Hierarchy
Table 16. Performance of models BM33708
Time
10.715
9,83x
17.31x
19.70s
6m 25x
9.00s
12.20.
11.18%
18:725
21.21s
2m455
8,82+
11:72s
10.85.
19.04.
21.625
2m
7.38%
9,815
9.02s
16.09s
18.04s
2m
8.53s
11.16x
10.34s
18.19%
20.42
2m
12.145
11.32
19443
22.07s
2ms41s
9.07s
11.85
11.09s
18.27s
20.34s
8,91s
11:44s
18.62
20.86s
2m
2m
MTMDVRPIO
-1.1388%
-14515%
-1.23813
-1,86888
-2.00149%
8
7.62218
7.85 7.857296
6.78009
6.4508%
6.6527
6.119%%
6.5587%
4.874%%
4.6225%
10.52638
9. 1010
10.20149
7.389008
6.7607%
11.7278%
11.2500P5
11,55068
9.94988
9.56638
6.7651
6.25
6.6407%
4.221
4.311%%
8.2643%
7,83068
8 82257
7.01
6.5421%
11,61809
11.1516%
11.5117%
9.9594%
9.6122%
Cap
Oh)
9.9236
9.7744
9,7952
9.7327
9,7200
12,0249
12.9875
12.9415
12.9098
12,890
12.7998
84465
8.5785
8,5368
8.5722
8.4346
8,4135
5.1136
5.6544
5.58
5.6376
5,6931
5.4609
7.9731
8,9031
8.3646
8
8,7285
80416
8,5122
8.5730
R.4399
8418
12.4970
13:5021
13.4496
13:4871
13.3430
13.3439
13.2892
8,023
8. 9,900
8,222
8.8254
8.7979
Time
101 155
3.35%
3.59
8
5,02
5.766
lm 22:
2.966
3.766
9.80s
6.3%
Im 16s
2.00%
3.89%
3.73
10.235
588%
6
Im 20s
3.10c
3.4ss
3.1
8.33
5,04s
5.77%
3.4%
3.94
3.75
10.01s
5
6.64s
Im 30s
4.04s
3.7%
10.5
6.0
6.8%
1m 40s
3.75%
3.62%
9
5.67%
6.2%
Im 32:
3,57%
4
10.215
5.95
6.75
1m
MTMDVRPS0
0,5091
0,0282%
0.1420%
-0,2635%
5.7045%
5,5481
5,0955
4.8166%
4,6212%
5.0035%
5. 5.007%%
5,3632%
4.6315%%
4.2077%
4,2263%
7.2984%
7.9910%
6.9246%
6,5012
6.33-9%
10:42866
10. 10.10%5%
10.00%0%%%
9,9856%
9.4633
9
5.3405%
5.2144%
5.4492%
5.0438%
4.3630%
9.6728%
90085%
9,1229
8.5104%
8.0833
10.6725%
10. 10.3009%
10.5132%
10.2162%%
9
9.558%%
Gap
-0.1
Ob)
6,5389
6,5382
6,5439
6.5280
6,5195
6.5148
7.6658
7.9788
7,97US
7.9357
7.9158
7.90004
3
5,2763
5.2834
5,2542
5,2383
5,2333
3,5357
3.8204
3.7958
3.8201
3.7805
3,7655
3 16
4,9702
5,4885
S.4754
3.4791
5.4665
5.4432
5.4534
4D822
5.2483
5.2644
5.2563
5.2335
5,2019
7.4144
8.1315
8.0827
8.0907
8.0423
8,0099
40600
5.4895
5.4732
5. 5.4668
S.4426
5.4346
POMO-MIE MTVRP
MVM Light
SHIELD WIELD-MMr MoD
POMO- POMO-MIVVE -TTVR
MVM A.MME--Deper Despee
SHIELD-NN D-MM
POMO POMO-MTVRE MTVRP RRP
MVMME- Light
MVMOE- TYMEE-DappN Deppe
SHIELD MoD
POMO- POMO-MTVRE -T-VP
MVMME-LLig Light
MVMOE- DappS
SHIELD L. MoD
POMO-MTVRE MTVRP
MVMQE: Desper Desper
SHIELD SHEED--MA D-MoD
POMO POMO-MTVRI MTVRP
MVM Light
SHIELD MoD
POMO- -TTVI
MV Ligh-
MVMoE- AiMoE--Despe Despee
SHIELD- D-MD
POMO POMO-MTVRE MTVRP TRP
MVMoE-Dor Desper
OR-40ols
MVMoE
MVMoE-Derye
SHIBLD
OR mools
MV MVMoE-Ligg
SHIELD D
OR NNN--ooos
MVMOE
SHIELD
OR 400ls
MVMoE
SHIELD D
POMO MVMoE
MVM
SHIELD
UR--00lS
MVMoE
SHIELD
OR mools
SHIELD D
OR- -Oo-s
MVMOE
MVMoF.L
MVMoD
MVMoE-
VRPL
VRPTW
OVRPTW
OVRPSL
OVRPBIW
OVRPLTW
VRPBLIW
OVRPELTW
Time
2an 11s
11.448
10.58%
18.39%
20.45%
2m 30p
7.47s
10.38%
9.39s
17.05s
19:51s
2m 376
6.72
8.96s
8.274
15.07%
16.9%s
2mn 40%
6.9%
9.62s
8.66s
15.71s
17.08%
7.87%
10.72%
9.83s
17.4%
19.90%
2m 355
7.38%
9.59s
8.90s
15.75%
17.67
2m 35c
8.46s
11.23
10.47s
17.61s
19.68%
2m
9.72
12.71s
11.81s
19.45%
21.88%
MTMDVRPION
Goo
2.9725%
2.6616%
2.999%
2.2300%%
5.9008%
5.09929
5.574%%
3.9269%
3.3706%
1.541%%
000429
1.3498%
04521
0.211%
16.5679%
9.108
10.2535%
7.4002%
6.759%
5.939-9%
5.10598
5.5449%
38838
3.407
1.5939%
1.44%%%%
1.380
0,250%
8.26339
7.9318
8.2289%
7.1352%
6.57466
3.49689
3.1971
239399
2,084499
Oly
9.5205
9.8019
9.7728
9,7950
9.7312
9,7160
5,9998
6. 354599
6.3316
6.2323
1.1989
7.331
7.6426
7.6019
7.6283
7.5605
7.5432
5.1150
5.6545
5.5002
5,6390
5.4924
3-4591
5.9857
6.2854
6.2359
62222
6.1003
6,1466
1.3768
7.6932
7.6563
7.6777
7.6094
7,5088
12,4088
13:407
13.3707
13,4078
13,2089
13,2026
1244766
12,89012
12,8550
12,8826
12,7513
12.7150
Time
1m 255
4.465
3.874
9.58
5.76
6.4%
2.59s
3.08
8,6
5.1
5.94s
Im 85
2.30
3.08s
7.035
4.70s
5
1m 14s
2.45.
3.30s
3.23%
7.98
4.96
5.5%
2553
3,46s
3.5
9.04s
521
6.02
mm 16
3.265
3.06%
881
4.74
5.34
2l
3.175
3.59s
9.53x
6.17%
1m 338
3.50
3.91
10.15
5.68
6.43s
1m
MTMDVRP50
Gap
1.98338
1.2219%
1.266.%
13445%
250.9
1.464%
43105%
3.985
4.265%%
3.3616
296099
2.7202%
2.1699%
1.7189%
1.9479
1.1129
1.2899%
1.1022%
7.84839
7.1879%
7.7261%
6.6925%
6.25633
6. 12228
4.002%
3,5879
42170%
3.75709
203100
2.6877%
2.473%
1.7541%
1.969888
20373
1.3226%
1.1250%
9
9.2211
9.18
9.2568
8.574%%
8.26398
43739%
388700%
4.0994%
4.0089%
3.3677%
1.1990%
Obj
6,5032
6.5373
6.5072
6.5137
6,4984
6.8897
6.4843
3.9920
POMO-MTVRE 4,1641
4.1634
4.1270
4,1012
5.2114
5.3321
5.2088
5,1985
5,1872
5.1774
3.5304
3.8075
3.7854
3.8041
3.7667
3,7513
3,9476
4,1679
4.1430
4.1379
1.5544
4.0957
S,1312
5.2568
5,2191
5,2303
5.2357
5.1972
51873
7,4439
8.811
8. 1267
8,12 8,1258
8. 8.1340
3.0782
8,0844
76381
7.9617
7,9210
7.9339
7,8088
76867
POMO-MTVR
MVMoE
MV
MVMoE-Dese
SHIEL SHIELD-MaD M-
SHIELD
OR lonis
MVMoE
MV MoE-Liglh
MVMOE: MVMoE-Desgu Deeper
SHIEL D-M
SHIED
OR -ools
POMO MTTVP RP
MVMoE
MVMoF.Ligh
MVMOE--eSS Dosprer
SHIEL D MaD
SHIELD
OR -ool
POMO-MITI MTMV
MVMOE
MVMoE-Liggtt Light
MYMOE- DesgeDe Desper
STIEL D M&D
SHIELD
POMO POMO-MITVE MT RP
MYMoE
MY MoE-Liighht
MYMoE-Deege Deeget
SHIEL D-D
SHEED
POMO MTVRP
MYMoE
MVMeE-Lin Light
MVMOE- DesgeD Desger
SH D McD
SHIELD
OR lonis
POMO-MT POMO-MTVRE RPP
MYMOE
MV MoE-Lighh gig
MVMOE- MVMoE-Despi Deeper
SHIELD D-D
SHIED
OR -000s
POMO MTTVR RRP
AYMoE
MV Light
M MYMOE--DOO Deegget
Deegeet
SHIEEL D MoD
SHIELD
HGS
BM33708
CVRP
OVRP
OVRFB
OVRPL
VRPBL
VRPBTW
VRPLTW
lo-nnsk
Out task
27

---

SHIELD: Multi-task Multi-distribation Vehiele Routing Solver with Sparsity and Hierarchy
Table 17. Performance of models on K79976
Time
2m 39s
8.018
10.71s
9.84s
17.34s
19.60s
32x
9.10s
11.95
11:31s
19.07s
21
2m.42s
8.79%
11,6%s
10.7
19,00%
21,61s
2m 315
7.35x
9,76s
9,0Ms
16.1
17.06s
2m.44
8.50s
11.34s
10:308
18.00%
20.3
2m 54s
9.223
12.12s
11.17%
19.42s
21.0%
2m 47
9:255
11.78s
11:225
18.54s
20.70s
2m 335
8.811
11.41s
10.65s
18.46%
20.71s
MTMDVEPION
-0.783668
1.1352%
-0.95 1898
-1,5891%
-1.71
8.115%
8.2241%
8.3233%
7.1926%
6.7691%
6.8257%
6-0039%
6.5555%
4,8610%
4.516%%
11,47388
9.6704%
10.92718
8.0347%
7.1246%
12.481
12.0447%
12.1569%
10-4973%
9,98229
6,7992%
6.4918%
6.64199
4,5005%
4,5534%
8.35819
8.10266
8.2802%
7.1332%
6.6791%
12.39 12.3982%
11 11.96679%
10.1568%
9.92099
Gap
0k)
12.8868
12.7791
12,7344
12,7500
12,6752
12,6599
17.3625
188316
18.7844
18.0030
18.0051
18 18,5330
10.0608
11,5865
11.3429
11,1768
11.1398
6,1967
6,9034
6,7926
6.8705
6
6.655
10.6121
11,9287
11,8841
11.8949
11,7189
11,6645
10.3746
11.2864
11,2550
11,2703
11.0853
11.080
18,3014
19.7894
19.7494
19.7794
19.5707
19,4922
10,0400
11.9586
11.9137
11,7414
11,6052
Time
1m 106
3.35%
3.05%
5.01s
5.715
19
2.82s
3.9%%
3.50%
9.9%
5.74
6.46
mm 1.6
2.73%
3.91s
10.228
5,8%%
mm 6
2.34
3.36s
3.07%
8.29
5.0%
5.65%
2.77
3.92
3.69
10.04s
5.84s
6.5%
mm 176
4,111
3,70k
10.468
5.97
6.7%
Jm 22
2.94s
3.63%
9.7%
5.74
6.32s
1m 19%
2.90
4.05
10,248
5.9%
km
MTMDVRRS0
0.7927%
0. 1676%
0.2478%
-0.037%
1.1117%
-0.118%
6.198%
5.9973%
5.18858
5153%%
4.833
5.884%%
5. 3.0048%
4.100%%
4.338%
4.442%
8.67998
7.6726%
8.5157%
7.1562%
6.889%
6.8880%
11 11,7856%
11 11.410%%
11.57166
11 11.0056%
10.7090%
10.31 966%
6.009%
5.550%
5.7811%
5.249%%
4.8220%
10.5025%
8387%
9.49993
90007%
8.6 8.6889%
11.8922%
11 11.66%%%
11.561
10.925%%
10.7710%
Gop
Obj
8,4633
5.5304
8,4747
8,4820
8,4577
8,4511
8,4423
10.6491
11.1016
11 11.0857
10.99993
10.990
10.9675
6.4017
6.8737
68558
6
6.0099
6,7798
4,2813
4,6503
4.112
4,6186
4
4.5117
4,5086
7,2019
7.1797
7.1893
7.1516
7.1353
7.1020
6.004
6.8985
6,8964
6
6,8490
6,8213
01.5947
11.7074
11.6 62660
11.601 11.8011
11.5585
11 11.5051
6-4313
7.1%6
7.1622
7.1340
7.1239
7.0845
POMO MTVRP
MV Lightt
MVMOE- Desger
SHIELD D. MoD
POMO-M -T-MMTVRP
MV Light
MVMoL Desper
SHIEL SHIELD-MoD D-M
POMO MTVRP
MVMOE- Desper Desper
SHIELD MoD
POMO MTVRP
MVM-E- M-ME---eopp Despee
SHIELD D. MoD
POMO MTVRR
MVMoE-Liu Light
MVMOE INMoEE-Deppe Deeper
SHIELD-MA D-LD
POMO MTVRP
MV Light
MVMOE- Desger
SHIELD D. MoD
POMO-ME MTVV
MVM Light
MVMME MVMMo--Degee Desper
S SHIELD-MoD D-M
POMO MTVRP
MVM Despper
DR-Toolss
MVMOE
SHIELD
OR tools
MVMBE
SHIELD
OR -oooo
MVM
MVM
SHIELD
OR- Rools
MVMOE
MVM
SHIELD
MVMME
SHIELD D
OR-Roolds
MYMOE
SHIELD
OR tools
MVMBE
SHIELD
OR Rools
MVM
MVM6E.
MVMoD
Problem
VRPL
VRPTW
ONRPTW
OVRPBL
OVRPBTI TW
OVRPLTW
VRPBLTON W
OVRPBEIW
Time
2m 146
11.31s
10.98.
18,03
20-42
2m,376
7.44%
10.16s
9.338
17.04s
19.49.
2m 398
6.74%
8.965
8.30s
15.04
16.92s
2m 39%
6.98%
9.40s
R.66s
15.67%
17.61s
7.888
10.76
9.786
17.51s
19,85s
2m 338
7.43%
9.59s
8.91s
15,72%
17.63
2m 4.6
8.63s
11.26%
10.65
17.94s
20.06s
9
12.71s
19,89
210
22.
MIMDVRPIO
Cap
3.3197%
2.9664096
3.1223
2.484668
2.3912%
5.835%
5.0610S
5.3313%
32022%
3.03415
1.2055%
L55266
0.5879%
0.2961
11.48739
965666
10.710388
2.912698
7.2445%
5,2422/6
4.8769%
5.285496
3.05 11%
10505%%
1.3777%
1,992'
0.7505%
0.4835%
8.08
7.99 18%
6.769449
6.3436%
3.0163%
28171%
2.95
1.7581%
1.4410%
0bl
12.4181
12,8288
12,78466
12,041
12.7248
12,7058
7.6637
10447
8,0602
7,9500
7 7,8900
3879
9.55KS
9-4946
9.5275
94464
94417
6,2087
6.9177
6.990
6.8691
6.696
6.6557
7.6885
8 1227
8.0500
8,0883
7.6544
7.9175
94149
9,5380
9.5682
9.4991
94541
18.3619
198107
19.7718
19,7959
19.3695
19.4954
1822887
18,08T
18.7728
18,0008
18.5787
18.5216
Time
101 17s
4.36s
4.13%
9.56s
5.7%
6-46s
1m 56
2.3%
3.4%
3.04s
8.6
5.13s
5.924
1m
2.20%
3.02
7.04s
4.7
5.25%
Im 10x
2.25
3.36s
2.9%
7.9%
4.91
5.5%
2.36s
3.48
3.16s
9.03%
5.23%
6.0h
I0 135
2.26s
3,28
3.024
8.8
4,76%
5.32%
Im 28
2.77
3,61s
9,52%
5.62s
6.22%
Im 23%
2.82x
3.95
3.68
108
5,78
6,50s
MTMDVRRSSD
2.1707%
1.60%%%
1.7004%
399
27745%
1.166%
46202%
42863%
3.395VS
31536%
29232%
24023%
1.7619%
2.00019
15232%
1.3139%
1.100%%
8.7721/
7.747%%
8.69109%
7.2939%
6.9517%
6.7822%
4.326%
40808%
4.500%%
3.8422
3.046286
2.56609
2.77266
1.8865%
2.1453%
2.327%
1.419%%
12310%
10 2922%
9.6440%%
9.2771
89121%
8.504%%
4.4476%
3.5996
3.9295%
3
3.18709
2.8804P
Gap
Obly
8 0.421
8 4:334
8,441
8. 4054
3991
5,079K
5.3
5 2,2966
5.2511
5,239
5 5,2274
6,332
6.4841
6.4416
6.4264
6.4131
6 624203
4 2824
1.6591
4 1.6559
4. 4.5588
4
4.5343
5 6.2216
S.2428
5 2545
S 5,2318
5 1909
5. 1
6. 3024
6.477
6.4204
5.4364
4-4305
6. 1999904
6 3788
10.6457
11.7415
11 166477
11 13333
11 1424
10,6050
11.1 7077
11 06600
008888
11 102222
09.9488
8
POMO- -TVRP
MVM Light
MVMoE- EVMOE-Despor
SHIELD WHELD-Mo MoD
POMO-MI MIVRR
MVMMEE-LUN Mii----Ligh Light
MVMaE: DespeeDDpper Desper
SHIELD DOLDD-MR MoD
POMO-MTE MTVRP RRP
MVMoE- Light
MVMOE- M-ME--Dpppr Desper
SHIELD FOLDD-Mo MeD
POMO POMO-MIVRE -TVRP
MVMME- Light Light
MVMOE-I Depper
SHIELD DD MoD
POMO-MTVRE MTVRP
MVMMEELLO Light
MYMEE Desper
SHIELD BELDD-MOD MeD
POMO POMO-MTVRI MTVRP
MVM Light
MVM Meppy
SHIELD McD
POMO-MIL -TVVI
MVMoE-Liggn Light
MVMoE: Deeper Deeper
SHIELDS DELDDOOO MOD
POMO POMO-MTVRE MTVRP
MVM Light
MYMME- MeEepa Desper
SHIELD MeD
HGS
MVMoE
SHIBLD
OR mooks
SHIELD D
DR-sools
MYMME
SHIBLD
OR 4001s
MVMoE
SHIELD D
POMO MVMoE
SHIELD D
OR-400lS
MVM
SHIBLD
OR mooks
MVMoE
SHIELD
OR -0o0s
MYMOE
K29976
Problem
CVRP
OVRP
OVRPS
OVRPL
VRPBL
VRPBTT WW
VRPETW
In-task
Out task
28

---

MIELLD Multi-task Multi-disribbttion Vehiele Routing Solver with Sparsity and Hierarchy
Table 18, Performance of models on SW24978
Lable
Time
2mn 58s
5.00s
11.64s
9.87s
17.44s
19.74s
2%
9.26s
13,26s
11.655
19.336
22.05%
2m 2m-42
8.81
12.81s
10,96%
18.90s
21.56s
2m 366
7.40s
10.78s
9.04s
16,07s
18.05%
41x
8.48%
11.52%
10.30s
17.09s
20..7%
2m 2014%%
9.20s
12.92s
11.48%
19.38%
22.00s
2m 49
9.288
12,80s
11.41s
18.09s
20.92%
2m 316
8,87.
12.13s
10.84s
18.44x
20,744. 20.746
MTMDVRPISS
-0,0558
-0,67118
-04486
-1,4005%
-1.5678%
8.540%%
8.1659
8.5005%
7.23269
6.9055%
7.6533%
7.1596%
7.7730%
5.72269
5.29879
12.97898
11.6128%
12.7548%
9.18289
8.1570%
12. 12.56875
11.98-5%%
12.6198%
10.6609
10.00075
7.4029
6.0011%
7.9299
5.5065%
5.10099
8.3795%
8.085W
8,5020%
7.322666
6.7412
12.594698
11 8818
12.5619%
10.6239%
10.0939%
Oly
10. 00.3234
10.2491
10.2727
70,1749
10.1589
13.3551
14,4825
14.4277
14,8899
14.3061
14,2664
8-4200
9.0652
9.0238
9,0742
8.9004
8,8643
5,209%
5.8816
5.1117
5,8700
5.6836
5.6304
9.4775
9.4291
9.4815
9.3156
9.2617
8.4292
9,0423
9,0008
9,0501
8.8812
8.8487
13.6276
14,7188
14,7363
14.5700
14,5032
8-4572
9.5106
9-4532
9.5087
9.3427
9.3013
Time
1m 10s
3.325
3.00s
8.45
5.04s
5.785
176
2,88s
3,975
9.91s
581s
6.55
1 11s
2.77
3.84s
10.39s
5,85%
6.6%
Im 8
2.36x
3
3.21s
8.34
5,084
5.68%
2,80s
3,88%
3.8
10.0%
5
6.64
mm 15s
4.015
3
10.5
6.01
6,84
1m 224
2.96s
3,79
9.87
6.43%
1an 185
2,88
4.08%
5.95
6.75
10.3
1m
MTMDVRPS
Cap
0.3497%
0.2730%
0.3548%
0.0947%
0.1166%
-0.21
6
5 5.8055%
5.248488
5.0838%
4.3000
5 5.86299
5 3,8508%
5.0649%
5, 1083%
4.333%%
4.630%
9.07328
5.55%%
9.1 9.1395
7.8550%
9921
6.928%
11 2855%
10.91448
11.0877%
10.6357%
10.118%%
9.797%%
6.1352%
5.9274%
6.0997%
5.687%
49193%
4.115%
9.7182%
9.0142%
9.0086%
8.4141%
79995%
11.4524%
11 234444
1126699
10.9230%
10.221.4
Oity
6.7221
6,788
6,7941
6.7762
6,7623
6
8 8.3232
8
8 6542
8.6881
8.5945
855229
3,2037
5.5109
5,511
5.522
5.4697
5.4527
5.4455
3 3.5320
3.8526
3
3.8561
3 3,995
3,7870
3
5.1779
5.7623
5,7434
5,7527
5.7286
5 69896
5 5,682
3. 11469
5-4512
5.4605
5.439
5.4001
5 1.604
8. 1677
8.9615
8 8890
8410
8. 8.0013
1124
5,7114
5. 3.6997
5 3.6842
5.6483
3
8.
DR--oolls
POMO MTVRP
MVMoE
MV Light
MVMOE- Desger
SHIELD D. MoD
SHIELD
OR fools
POMO-ME -T-MMTVRP
MVMBE
MV Light
MVMoE Desper
SHIEL SHIELD-MoD D-M
SHIELD
OR -oo-ools
POMO MTVRP
MVM
MVM
MVMOE- Desper Desper
SHIEL MoD
SHIELD D
OR- Roolo
POMO MTVRP
MVMOE
MVM Light
MVM-E- MoME--eepp Despee
SHIELD D. MoD
SHIELD
POMO- MTVRP
MVMME
MVMoE-Liu light
MVMOE EWMoE--Deppe Deeperr
SHIELD SHIELD-Mol D-D
SHIELD D
OR-Rools
POMO MTVRP
MYMo
MVMO5- MV Light
SHIELD D MoD
SHIELD
OR tools
POMO-MO MTVVI
MVMBE
MVM Light
MVMoE MVMME--Dese Desper
SHIEL SHIELD-MOD D-M
SHIELD
OR Rools
POMO MTVRP
MVM
MVM6F.1.
MVM
MVMoD
Problem
VRPL
VRPTW
ONRPTW
OVRPBL
OVRPBTT
OVRPLTW
VRPBLTIN W
OVRRBETW
Time
2m 1
12. 22.50s
10.58
18.11s
20.3 20.38%
2m 386
7.4%%
9.36s
17.16s
19.49.
2m 366
6.73%
10.36s
8.30s
15.13
16,94s
2m 408
7,00%
10.34s
8.70s
15.71
17.62s
7,91s
12.37
9.79
17.65%
19,85
2m 338
10.92s
8.95%
15.88s
17. 17.58
2m 4%
8.73s
12.06x
10.93s
18.25
20.5 20.56s
2m0 525
10.13x
14.01s
12.49h
20.38
2m
23
MTMDVRPION
3.7N7605
3. 1.5600006
3.7725008
2.79912098
2.60 2.621
7.1 1.12210
6.8 618880%
4.62700%
3.751 3.75130% 30%
2.772.008
2.2488398
2.6458995
1.21340%
0.956-09%
13,03900%
12.87330
9,24450PS
8 8.33
7. 1.3622066
6.3 6.3785508
7.01370%
774400%
4 4.001 2.0012008
2096
2.757309
2 2373330
2.642005
1.201 ROSS
30%
8. 6122299
7.470009%
6.7722096
3.634605
3. 3.269909
3.6894055
2.45880%
2,050699%
Goo
6.335
0.9055400
8.491
8.
Obj
9.8826
10,2519
10:22000
10.2507
10.1538
1866
6,1626
6,5952
6.5766
6.4400
6. 6,3878
7,6890
7,8945
7.8535
7.8847
7.7733
7.7549
5.1907
5.8645
5.7911
5.8531
5,6699
3,6244
666124
6.5529
6,595
64430
6.4068
7.6894
7,8236
7.8552
7.7445
7
14.1676
153142
153333
15.1656
15,0922
130065
14.445
143385
144490
142713
142191
15
Time
1m1 185
4.43s
3.8%%
9.75
5.81
6.54
1m
2.39s
3
8.73%
6.05%
1m 25
2.18%
3.30s
7.02s
4.70%
5.27s
1m 12:
2.30%
3.288
3.25%
8,0
4.95
3.69
2,40s
3.44s
3.44
9
5.25%
6.088
mm 13
3.224
3.24s
8.85
4.80N
3.354
1m 1%
2.77%
3.92%
3.83s
9.49
5.6%
6.29
13:
2.85%
3.95
10.088
5.84s
6.55%
MTMDVRPSS
Cap
2.2739%
1.7444%
1.8566%
1.583 1%
1 1336369
1.2160%
5.441%
4. 6:8
3 3.8866%
3 3.390%%
3.01
2.8184%
2.52649
2.4519%
2.0 2.0248%
1.6618%
1.4189%
9.1129%
8.47618 1%
9.1 9.1296
7.11668%
6.975%%
5.1319%
4.7335%
51919%
4.2 4.2921%
3.2000%
3.0814%
2.8163%
2.2667%
2.4299%
2.3187%
1.5530%
1.36%%%
9. 9.7679%
9. 1606%%%
9. 131366%
8.4928%
8. 1860%
4.4146%
4.0004%
4.0737%%
3. 3.965556
3.2956%
3.0792%
Obj
6,6979
6.7538
6,7181
6.7260
6,7072
6.6937
6,6842
4.0521
42254
4.2382
4,2492
4,2075
4.1888
4.1733
3.2139
3,3608
5.3351
5.3995
5.3
5,2987
5.2861
3,5427
3.8655
3.8442
3,8671
3,8229
3,7960
3,7010
4.0512
4,2591
4,2415
4.2554
4,2251
4,1890
4.1754
5,1009
5.3571
5.3057
5.3141
5.3113
5.2689
5.2597
S,0SS6
8333
8,3
8.8276
8.7607
8,7359
8.153
8.5131
8.600
8.4753
8,4764
8.4117
9,3926
POMO-MTVEE -TVMM
MVM Lighh
MVM HIMOE--Dsppr
SHIELD McD
ROMO-MIVAN MI
MYMOE-LLON Light
MVMGE: MrMM--DDeeee Desper
POMO POMO-MTTX MTVRP
MYMME-IDS MYVMEE-Dasper Desper
SHIELD MoD
POMO- POMO-MTVRI -TTVR
MYMEE--LEE -iE--LLigtt Light
MVM WVMOE-Despes Dosper
SHIELD MAELD--MMI MoD
POMO POMO-MTVRY MTVRP
MYMOE-L Light
MVMGE Desper Desper
POMO MIVRP
MVMME- Light
MVM LIMOE-Desper
SHEELD MaD
POMO-MI VIRP
NYMOE-LICN Light Light
MVMGE- DiVME-DDeperr Desper
SHIELD-MO D-MOD
POMO POMO-MTVRE MTVRP
MVM Light
MVM Masjer Desper
SHIELD MeD
HGS
MVM
SHIELD
OR toolss
MVMOE
SHIELD-MON
SHIELD
DR- DR-tools
MVME
MYMAE-Light
SHIELD
OR Aools
MYM
SHIELD D
MVMoE
SHIELD-Mol
SHIEL
OR--8ols
MEM
SHIELD
OR toolss
MVMBE
SHIELD
OR Tools
MVME
SW24978
Problem
CVRP
OVRP
VRPB
OVRPB
OVRPL
VRPBL
VRPBET W
VRPLITW
In-took
Out-task
29

---

SHIELD: Malki-task Multi-distribation Vehiele Routing Solver with Sparsity and Hierarchy
Table 19, Performance of models on VM22775
Time
10 00.84s
9.88%
17.29%
19:71x
6m 34.
9.17s
12.038
11:34s
19.14s
21.64s
2m
8,74x
11.72s
10.73x
18.91
21.43s
2m,35s
7.39%
9.918
9.06s
16.066
18.05s
2m 4m.
8.495
11.10s
10.30s
18.06x
20. 10.30ls
9.17%
12.17%
11.20k
19.33x
21.874
2m 4.555
9.27%
11.88s
11.22s
18.70s
20.76s
2m 338
8,80s
11:48s
10.65%
18:44x
20.64
2m.
2m
MTMDVRPIN
4.3508
-0,6200%
40.5008
-1.2047%
-1.3374%
8.4620%
8.44915 56
7.0508%
6.7445%
7.11
6.7774%
6.7987%
4.8878%
4.4416%
11,966688
10.6523%
11.7448%
7.96559
7.1334%
12.3227%
11,90739
11,8808%
10.1297%
9.4637%
7.1771%
6.9019%
6.8768
4.99869
4.563%%
7.1626%
7.04999:
7.09975
87%6
5.56.5%
12.3540%
11.9733%
11.9919%
10.15945%
9.4527%
Cap
0b)
12,5283
12.0811
12,4472
12
12.3739
12,3579
17,3378
192257
19,207
19,2231
18.9766
18.9211
101562
10,8685
10.83-8
10,369
10,6427
10,5970
5,7679
6.4539
6.3792
6.4121
6.2237
6.1758
11.3495
11.3082
11,3072
11,1283
11,0622
1013%6
10,5730
10,8447
10.827
10,6515
10,0008
18,5622
19.422
19,8255
19,8335
19.5935
19.5566
10
11,3098
11 11.2734
11.0888
11.01
Time
101 11s
3,33
3,12s
8.45
5.034
5.73
Imi 16x
3.03
3.5%
9.87%
5.7%
6.50c
1m 19
2.93x
3,8%
3.53%
10.32s
5.7%
5m
2.1
3.41s
3,08
8.33
5,024
5.67%
2,8%
3.90
3.0%
10.01s
5.7%
6,5%
1m 18s
2.92
4.02%
3.73
10.45
5.95
6.79
1m 19
3.0%
3.64s
9.76s
6.32%
1m 20N
2.95
4.0%s
10.1 10.1%
5.904
6.66s
Jm
Im
MTMDVVRPSD
Gap
1.12798
0.318%%
0.5735%
03507
0.18369
00535%
6.447%
5.739S
5.884%%
5.1622
5
43547%
6.8769%
63126%
6.7157
5.6127%
54647%
49268%
9.1193%
8.004%
92892%
7.6044%%
7.2144
7.046%%
12.4186%
12.0617
12.0%%5%%
11.5 11.5779%
11 1773%
10. 096996
6.72898
6.222%%
6.5993%
5.533
5.4425%
4.88
9.610%
1.94999
9.200%%
9.0243%
8.685%
B.0243%
12.3155%
11.9893%
11.5 11.5511%
11.0334%
12
Oity
8.2151
8 8,2539
2595
8,241
2,222
2167
10,5525
10.9940
10.9546
10.8784
10.8471
6,0966
6.5159
6-8816
6, 6,3464
6,4294
6.3982
3 8999
4.2454
4.219
4,2518
18888
4.1716
4. 4,1646
6 6045
6.7815
6,7538
6.227
6.6794
6.0821
6.4399
6.4508
6. 6.3882
6. 6,3805
6 3456
10.6434
11 11.6674
11.1111
11 116009
11,5523
11,4789
6,0333
6. 8095
6. 6.7884
6.7635
6,731
6856
10
POMO POMO-MTVRI MTVRP
MVM Light
SHIELD MoD
POMO- POMO-MIVVE MTVRR
MVM Light
MVMoE: EVMME-DDeper Decper
SHIELD BELDD-MI M--
POMO POMO-MTVRE MTVRP VRP
MVMME Light
MVM0E- MMME--D-pN Deppor
SHIELD MoD
POMO- POMO-MIVVE -TVVR
MVMME- Light
MVMOE-1 Dapper
SHIELD .D MoD
POMO POMO-MTVRE MTVRP
MVM Light
MYMGE: Desper
SHIELD DILDD-MA MoD
POMO MTVRP
MVM Light
SHIELD MoD
POMO- -TTVI
MVM Light
MVMoE- UVMoE-Deepes Deeper
SHIELD DELDD-MO M-D
POMO POMO-MTVRE MTVRP VRP
MVMOE- Desper
OR-40ols
MVMoE
MVMOE-Deee
SHIBLD
OR mools
SHIELD D
OR -oo-sooos
MYMOE
SHIBLD
OR 400ls
MVMoE
SHIELD D
MVMoE
SHIELD
OR OR--00lS
MVMOE
SHIBLD
OR mools
SHIELD D
OR- 4oO-s
MVMoE
MVMoF.I.
MVMD
MV
VRPL
VRPTW
OVRPTW
OVRPSL
OVRPB
OVRPLTW
VRPBLIW
OVRPBLTW
Time
2an 15s
11:37s
10.62s
1R.05%
20. 00.388
2m 36
7.49%
10.39%
9.385
17.11s
19:63%
2m 355
6.74.
9.18s
8.27
15.08%
16.99
2m 39%
7.05
9.52s
8.69s
15.65%
17.6%
7.94s
10.32s
9.785
17.53
19.97%
2m 45%
7.42s
9.63%
8.91s
1.5.3%%
17.66s
2m 45
8.63%
11.29%
10.65s
17.96s
20.13s
2m 45%
9.93c
12.81s
12.0%%
20.02s
22.38
MTMDVRPION
Gop
3.4193%
30442%
3.2645%
2.5224
6.440%
5.7257%
3.897%
3.28996
2.3584
L8153%
2.173%
DR220%
05547%
11.92838
10.6831%
11662748
7.597%
7.072%%
6.1 6.1984%
5.7154
5.82239
30467%
3.2589%
2261
1.762%
1.9399
0.7K32
04507%
7.3516%
7.0465
7.400%%
6.1625%
5.7595%
2.45168
2.3953%
2.7818
1.19808
0.44445
Oly
12.1714
12. 12.5450
1255657
12.4767
12.4608
7.3689
1.8238
7.7843
7.7975
76502
7604
9/447
9.201
922099
92190
9.1118
9
5.7522
6.4344
63647
6,1183
6,2023
611588
73550
78841
7.7679
7.7777
7.6389
7.5899
80724
9.1213
9.1414
90030
90043
18.7523
20.0852
0570
19 9.98
19. 79.9
18 69299
19. 221
19. 122
18.8883
18 8343
19.1
Time
1m 355
4.29
4.00s
9,66s
5.7%
6.48%
2.388
3.04s
8.65%
5.55%
5.9%
1m 1s
2.2%
3.118
6.9%
4.6%
5.2%
Im 85
2.1%%
3.35
3.0%%
7.94
4.9%
5.5%
2.54
3.48%
3.17
8,98%
5.208
6.0%
mm 16s
2.4%
3,2%
3,05%
888%
4.7%
5.34
1m 23
2,9%
3.90s
3.63s
9.4%%
6.25%
1m 255
2.98
3.95%
10.05s
5,80
6.50%
1m
MTMDVRRSS
2.245.8
1.6115%
1.7229%
1.43
1.320598
121193%
5.6669
4.7899
5.7009%
3,89005
3.625%
3.2797%
2.8022%
2.118%%
25749%
1.9115
LA3679
151739
9.315
8.402%%
9.3333
7.6443%
7.1677%
7.035%
5. 5.1971%
4.7188%
5.020%%
428378
3.4199%
3. 3.1907%
2.868668
2.104-9%
2.38448
24228%
1.6499%
1.4679%
9.324%
N.7550P
8.968%
8.89748
18
4.099.%
3.4150%
3.8246%%
3.62966%
3,18988
2
Gap
8.399
7.8871
Obj
120
8.2459
8.2554
8.2352
8.2229
8,2143
1.8
5.0672
5.0557
4,9992
4,9870
4,9697
6,022
6.2125
6.1094
6,1576
6. 6.1402
6.1326
3,8870
4,2005
4.2141
4,2512
4.1841
4.1656
4,1613
4,8097
5.0397
5.332
5.0494
5.0157
49793
4,9624
60258
6.1987
6,1500
6.1670
6,1722
6.1227
6.1111
10.7055
11.7035 11.7038
11 1399
11 11.65H0
19
1 126564
10.67
11.1114
11 1.0020
1 11
1.002.1
POMO MTVR?
MVMo Light
MVMOE- Desper
SHIELD McD
POMO-M -TVRI
MVMoE- light
MVMME Desper
SHIEL SHEELD-MoD L-M
POMO MTVRP
MVMaF Light
MVMoE--DeN Decper
SHEEL MoD
POMO MTVRR
MVMoE-Ligh Light
MVM Desjer
SHIELD MoD
POMO- MTVRR
MVMoE-Ligh Light
MVMOE AVMo---Deeee Desper
SHIELD-MoL MED
POMO MTVRP
MVM Light
SHIELD MoD
POMO-MI MTVII
MVMoE-Ling Light
MVMOE- MVVMo--Depse Desper
SHIE SHIELD-MOD L-D
POMO MTVRP
MVMaF. Light
MVMME--LLOO Dicepet
SHIELD MoD
MVM3B
SHIELD
OR tools
MVMBE
SHIELD
OR Rools
MVM
SHIELD
OR- fools
MVMOE
SHIELD
MVMEE
SHIEL
DR--ools
MYMOB
SHIELD
OR foolss
MVMBE
SHIELD
OR Rools
MVM
SHIELD
HGS
MVMO5-
VM22775
CVRP
OVRP
OVRPB
OVRPL
VEPBL
VRPBIN
VRPLTW
In-trsk
Out Qut-task
30

---

BIELLD Mulki-task Multi-distribation Vehiele Routing Solver with Sparsity and Hierarchy
Table 20,
Performance of models on EG7146
Time
2mn-11s
11.30s
11.48%
17.47s
21,766
6mi 3..
9.299
13.574
15:44s
19.75
23.82s
2m150
9.20s
14.07s
13,98s
20.05x
23.675
3.5
7.70%
10.665
10.34s
16,31s
18.12s
2m.49
8.85%
13.05
12.825
18.52s
22,24
201
9.66s
14,57s
14.39.
20.35s
24.35%
9.288
13.11s
14,685
18.95s
22.41s
2m 395
9.19
13.285
13.35%
19.02x
22.03s
MTMDVRPI0
1.3993
1.4500%
1.7299%
0,60228
30.3
10.5592%
9.1747%
8.7913
10.95888
11.55368
11.53049
9.1835
8.5811%
17.93808
18 18.33
17.5421%
13 13.3099%
10.8413%
15 14.1401%
15.5221%
1594%
13 11858
12.2104%
11,22899
11 11,64266
11.7726%
9.4200
9.8474%
9,8200
10.063698
8.9862%
H.2720%
1.5. 15.29990S
15.4365%
15.4145%
13.475%%
72.4%%%%%
Gap
0.361
6,5015
6.5822
6,5808
6,005
6,5317
6.171
7.5872
83441
8,3413
8 863668
8.2620
8,2334
43335
5,4417
5.4753
5,4714
5,5584
5.3254
3.0685
3.5984
3,0028
3.5800
3.4627
3,5874
4.8008
5,5019
5.5239
5,5144
54285
5,3650
43134
5.5255
5.5475
5.3524
5,2409
5,2088
7.9676
66880
8.7020
8.7208
866340
8.5772
434-7
5.5503
5,5638
5.4697
5.4196
Ohl
Time
1m 25
5.39%
3.20s
8.4%
5.07
5.59
1m 28%
3,36s
3,665
10.01s
5.74s
6.69%
1m
3.22
3.99
3.56s
10,52s
5,784
6.7%
mm 9/
2.63
3.4%
3.13s
8.34;
5,01
5.50s
3.09
3,93%
3715
10.15
5,00s
6.67
1m
4,14s
3,72,
10,71s
5.95.
6.9%
1m 25
3.23
3,70s
9.83s
5,65
6.38%
1 256
3.12
4.02s
10,3%s
5,86%
6.79
1m
MTMDVRRSS
1.0675%%
1.0892%
1.1400%
0,6455%%
0.43
67783%
6.19
6.0413%
5.4674%
5 5.6905%
140%%
8. 17666
7.7094%
7.01 12%
6.8535%
10. 19.99
9,849 1
10.56399
1323%
8. 1623%
7.5294%
12:2321
12.1102%
12.008
12. 12.16525
10.84108
10.7363%
8.1519%
2,221
2.2613%
8.7700%
7.2411%
69771%
9.6299%
9. 119%%%
9.5805%
8.4985%
8 3.390
12.3089
12.3 12.3844%
12.5136%%
12.34015 155
11. 11.127688
1099949
Cap
Olty
4. 4.2562
4. 4,2966
4.2979
4 4.2990
4 4,2801
2212
4.8840
5.1345
5.1049
5.0940
1510
5,0787
3.0238
3,2700
3,2627
3.2479
3,2360
3,2229
2.0523
2.2616
2.2526
2.2652
2.2397
2.2165
2 2,3057
2
3 3.2772
3.2692
3 3,2664
3,2752
2366
3,2274
2.9926
3.2366
3,2305
3,2343
3,2433
3.3099
3 1930
4,7699
5,2290
3.1899
5.2269
16000
5.15-2
2.9427
3.3029
3. 3,3005
3. 3,3061
3,2702
3. 3.2579
POMO MTVRP
MV Light
MVM Desger
SHIELD MoD
POMO STTMPTVR RP
MVMoE--Ligh Light
MVMME Desper
SHIELD-MO D-M
POMO MTVRP RP
MVMOE- Desper
SHIELD MoD
POMO MTVRP RPP
MVMeE- Light Light
MVM McE-DDeppp Desper
SHIELD D. McD
POMO MTVR RP
MV Light
MVMSE: HIMaE-DDepee Deeper
SHIELD M-D
POMO MTVRP
MVM Light
SHIELD D MoD
POMO-MO MTTRR RP
MVM Light
MVMME: MVMoE-Despe Desper
SHIELI- M-D
POMO MTVRP RRP
MVM Deseper
OR-Tools
MYMoE
SHIELD
OR fools
MVMBE:
SHIELD
OR -ooooo
MVMOE
MVM
SHIELD
OR- fools
MYMOE
SHIELD
MVMME
SHIELD D
OR-Rools
MYMEE
SHIELD
OR tools
MYMBE
SHIELD
OR Rools
MVMME
MVM6F.
MVMcD
MVM
Problem
VRPL
VRPTW
ONRPTW
OVREBL
OVRPBTW
OVRPLTW
VRPBLTW W
ONR
Time
2m 15s
12. 39,
11.98s
18.16s
22.95%
2m 4.6
8.09%
11.08s
10.74s
17.25s
19 88k
7.01%
9.74s
9.44
15.18%
17.34s
2m 4s
7.32%
10.33s
9.81s
15.74s
17 60
8.44s
11.71x
11.30s
17.64s
20.22%
10.50s
10.31s
15.87%
18.12
2m 4.36
8.67%
12.47%
13.6 13.64s
18.31s
21 800
2m0 35
10. 10s
14.30%
16.238
20.45%
24.946
2m
2m
2m
MTMDVRPIOR
4.7559%
4 8078886
5,0781 %
3.93663
65.66%
11 11.8018%%
11.1306%
8.44-49
6.7276%
4.6788%
4.4185%
4.8007
3.2931%
3.192%
17,70236
18.0985%
17.6061%
13.1146%
10.9531%
11,8376%
11,83368
10,9600%
8.1549
6.7257%
4.9025
1.5591%
5.0288%
3.3937%
10.1123%
10.03000
10.1730%
9.0841%
8.32806
5,80
5.85 10%
4.8426%
4.401%%
Cap
0bj
6.3233
6,5029
6,0175
6.6246
6,5535
6.366
3,7510
4,1644
4.1673
4,1427
4,0474
3.849
4.5504
5.1741
S1694
51815
5,1777
5,0930
3.0546
3.5751
35857
3,5722
3,4462
3,3731
3,7500
4,1693
4.1683
4.3360
4,0433
3.8788
4.950
5.1859
S,1710
5,1441
5.1138
5,082
7.9075
865547
86641
8,6629
8.5744
8:5188
S10066
8.4523
8:4420
8,4599
8.35%0
8.3220
Tane
1m 21s
4.528
4.17%
9.08s
5.83%
6.49
mm 20x
2.91s
3.268
8.8%
3.55%
6. 168
1m ls
2,62s
3.038
3.02%
7.1
4.70%
3.50%
mm 20s
2.768
3.52s
3.0%%
7.97%
4,90s
3.59
2
3.54s
3.338
9.0%
5.248
6. 12s
mm 19%
3,52%
3.21%
8.91N
4.7%
5.33%
Im 234
3.03s
3.67s
9.5
5.5%
6.15%
Im 315
3.11
1.128
10.22 10.228
5.80%
6.94%
1m
MTMDV
2.6537%
2.0324%
2. 1268
2. 2,165%
1. 1.6642%
1.4550%
6.750%%
6.8360%
6.1488
4.7885%
4.118%%
3.4424%
2.8546%
2.9629%
2.8093%
2,269255
1 1391%%%
33%
10 10.14915
9.75RG%
10. 10.7739%
9.2368%
&.1000%
7.530%%
6.5748%
6.27346%
6.5720%
6.5254%
4.7895%
4.05%5%
3.4311%
2.88-7%
2.9699%
3.540%
2,25644%
1.929%%
9.4734%
8.9711%
8.2844%
9.52125
8.3411%
8.242%
5.2845%
4.6517%
4.005%
5.0999%%
4.3019%
4.1259%
Gap
Obj
4.2661
4.5315
4.30
4.3061
4,306]
4,2876
4,28/02
2.4397
2,0045
2,5995
2.5787
2.5514
2.5357
3,3931
3,4892
3.4641
3,4652
3.4455
3.4547
208669
2.2657
2.2547
2,2747
2,24000
2.2204
2,2098
2.4504
2.1115
2.5969
2,0128
26103
2,5630
2,5450
3,2054
3,4085
3.3857
3,5891
3.4121
3,3661
3,3562
4,7375
5.1863
14448
5.1886
5.1189
5.1109
4.8841
1422
5,0992
5.0994
1307
5.0942
SA0728
POMO -TVRP
MVMeE- Light
SHIELD M&D
POMO-MIN MIVRP
M Light
MV MaE- MoE-D-Deper Desper
SHIELD DoM
POMO POMO-MTV MTVRP
MVM Light
MoM MoEpeeeer Deoper
SHIELD MaD
POMO MOO-MMVVP
MVMOE-LLE Light Light
MV MOM-E--A MoE-Deaper Deoper
SHIEEL LLDD-MM MoD
POMO- MEVRP
MV MaE- MiE-Deppe Despet
SHIELD- D--MoD
POMO MTVPP
MVMeE- Light
SHIELD BEDDDN M&D
POMO-MM MIVR
MVMOE-Ligl Light
MVMoE- MoM-D-Deeer Desper
SHIELD D-MO
POMO MEVRP
MVMOF. Light
MY MOE MoEgDegeer
Deqper
SHIELD MoD
HOS
MVMOE
MoM
SHIELD
OR took
MVMoEE
SHIELD DI
OR--ools
MYMOE
SHIELD
OR-tools
MVMOE
SHIELD DD
MVMOE
MVMOE-
SHIELD D
OR-400lS
MVMOE
MV MVM
SHIELD
OR took
MVMoE
SHIELD ID
OR-cool
MYMEE
EG7146
Problem
CVRP
OVRP
OVRIS
OVREP
VRPBL
VRPBTW TW
VRPEIW
In-tosk
Out task
31

---

BHELLD. Multi-task Multi-distribation Vehiele Routing Solver with Sparsity and Hierarchy
of
Table 21. Performance of models on F110639
Time
10.90s
9.84.
17,38%
19.71x
32,
9.10s
12.12%
12.44s
18.93s
21 21,86s
2m 2--44
8.81s
11.85s
11.19%
18.86s
21.82%
2m 35%
7.36s
9,77s
9.01s
16,03s
17.97s
8.48%
11.14s
10.965
18.01s
201.5%
31s
9.2.1s
12.31s
11.58
19.32%
22.25%
2m 41s
9.20s
11.78
12.02s
18:51s
20.90s
2m 336
8.87.
11.52s
10.88%
18.30%
20,80s
2mn
MTMDVRPISS
00,33918
-0,992096
-0.0622
-1.58568
-1.64199%
84109%
8.13688
8.3111%
7.2670%
6.8488
7.2001%
6.8319
7.1204%
5.28228
5.0130%
11. 11.3928%
10.1709%
11.08918
8.19569
733109
12. 12.18915:
11.76318
12.0410%
10.2390%
9.7187%
7.17468
6,7480%
7.00688
5.2071S.
48348%
844426
8.07448
8.3871%
721121%
6.7035%
12.2402%
11 10.8088%
12.11
10.3847%
9.1049
Gio
11 11.06447
10:9764
10,9476
10.9619
10.8826
10,8762
13,83013
14,9811
14,9553
14,8289
14.7707
9,0260
9.6772
9.6439
9
9.4766
5,6060
6.3443
6,1755
6,2369
6,0646
60163
9.0376
108
10,0940
10.1391
9.9550
9.9070
9,0627
9.7068
9.6680
9.6930
9.5282
9
14,3715
155583
15.5111
15,3800
15.3116
9:0148
10. 0094
10.07U6
9.9412
Oby
Time
1m 11s
3,285
5,10s
8
5.03
5.74s
21s
2.92s
3.63
9.11
5.70%
6.40s
1m 14s
2.76:
3
10.41s
588%
6.65
mm 68
2.37
3.40s
3.11s
8.35
5.04
5.69
2,25
3,8%
3.3%
10.07%
5
6.57
mm 16s
4.09
3,72,
10.65
5.97
6.40s
1m 23
2.94s
3,74s
9.59
5.72%
6.28%
2,86.
4.02s
10.31s
5,94
6.69s
1m
1
MTMDVRPSS
Cap
0.7427%
0. 1525%
0.2467%
-0.0743%
-0.1881%
68144
5 5.8825%6
5.2897%
5.0787%
4.859/
5.7348%
5.6378%
4.99066
4.756%%
1.56
8.627%
130%%
8
6.9563%
6,74
11 02244%
10.79688
109503%
10.35718
9.9325%
9.7035%
5.7846%
5. 5.365%%
5.8436%
5 3.90%
4.59905
9.7539%
9.06139
9. 18088%
8.9457%
5W00%
8.09
1LD8855
10.8055%
10.92099
10.4445%%
9.9658%
Olty
7.2655
7.2732
7.2799
7.2567
7.2485
7
8 6076
8 8,9835
8 8.9575
8 9
8 8903
8 8.8706
5.5667
5.8542
3.8494
5.8129
5.8005
5. 78889
3. 3.7945
4.1217
4 4.4002
4,1345
4.0922
4,6743
4.06
6.0902
6,0783
6.0859
6.0537
6,0311
6.0170
331178
5,8370
5 3.8256
5.8413
588088
5.7726
5.7644
8 4898
9.3172
9.2484
9.25 9.2586
9.2484
9.207'
9. 9,1680
3.4777
6,085
6.0701
6.0498
6.0241
6.0146
DR-Tools
POMO MTVRP
MYMoE
MVM Light
MVMOE-
SHIELD D. MoD
SHIEL
OR fools
POMO -TVRIP
MVMBE
MV Light
MVMoE Desper
S SHIELD-MoD D-M
SHIELD
OR -ooooo
POMO MTVRP
MVM
MVM
MVMOE- Desper Desper
SHIEL MoD
SHIELD D
OR- -oolo
POMO MTVRP
MVMOE
MVM Light
MVM-E- MoEE--eppp Despee
SHIELD D. MoD
SHIELD
POMO- MTVRP
MVM
MVMoE-Liu light
MVMOE AVMoE--Deppe Deeper
SHIELD-Mol
SHIELD
OR-RoolS
POMO MTVRP
MYMoE
MVMO5- MV Light
SHIELD D MoD
SHIELD
OR tools
POMO-MO MTVVI
MVMBE
MVMoE-Ligh Light
MVMoE MVMMo--Desee Desper
SHIEL SHIELD-MoD D-M
SHIELD
OR Rools
POMO MTVRP
MVM
MVM6F.
MVMOE- Despper
MVMoD
Problem
VRPL
VRPTW
ONRPTW
OVRPBL
OVRPBTT
OVRPLTW
VRPBLTON W
OV
Time
2m 18
11.5%
10.52x
18,05:
20.48
2m,375 37s
7.44%
9.356
17.02s
1942s
2m 356
6.73%
9.21s
8.20
15.16
16.92
2m 386
6.99%
9.40s
8.70s
15.65
17 17.60s
7.88s
10.77%
9.7%
17.40s
19,82
2m 35.358
9.92s
8.92%
15.88 15.80h
17.63
2m 4.6
8:55%
11.25%
17.85
20.27%
9,85%
12.90%
19.73
2m
210
MIMDVRIIO
3.4421%
3.21 00%%
3.3535%
2.58-008
2.5115%
6.0555
5.88-256
4.0124%
3 3.2150% 50%
2.21148
1.7773%
1.9777%
0.9074
0.692666
11.4105%
10,2748%
11.09479
7. 7.3669%
6.08-255
5.1155
5.6736%
3.9477
3. 3.3699'
2.2005
1.81 51.5%%
1.9562
0.94095
0.7540%
8.1334%
7.934405
138000
7.0071%
6.5168%
3. 3.5072%
3.2597%
2.3365%
2.01
Cap
0b)
10,6055
10,9689
10,94.3
10.9590
10,878
108700
6.67199
7.0708
7.0384
6.9334
6. 6.9809
2319
844955
8 8,3929
3038
5.6014
6.2596
61759
6,2219
6,0640
6.0
7.0341
7.0483
7.0665
69520
6.9121
8252
8 8.3967
8.4099
8,3250
3000
14,0940
15.6433
156160
13.6476
15.4787
15,4095
14,5048
12
15.0478
15,0779
14,9107
14,8641
Time
101 215
4.09%
4.07%
9.66s
5.9%
64%
mm 76
2.32%
3.295
8.8
5.2%
5.96s
1m 3m
2.1%
3,02s
2.9%
7.05
4.70
5.24s
im 11s
2.2%
3,32s
3,03s
8.01s
4,98
5.6%%
2.38
3.45
3.18
9.01s
5.24s
6.02s
Im 135
3,25
3,0%%
8.88
4,76%
3.34g
Im 21
2.74
3,64s
9.4%
5.61s
6.1%
Im 23%
2.7%
3.90s
3.76x
10.12s
5.7
6.43
MTMDVRR50
2253668
1.6553%
1.7537%
1.4944%
1.35148
12110%
46148%
4.700%%
45205%
3.9038
3.2448
2.8598
258188
19525%
2.1099%
1.736%%
14523%
12169%
8
8.339%
8.3749%
7.9930%
6.9982%
68295%
4.592%
4.1388
44587%
3.8684
3.14918
2873399
26583
2.0085%
2229998
2.090%%%
1.5040
13200%
10.0057%
9.1122
9.3735%
92522
8.854-P
833385%
4.50R 1S
4.091.%
4.3500
3.9766
3.4955
32202
Cap
Obj
7.1789
7.1891
7,1959
7.1775
7.1675
7.1578
4,5654
4,5099
4.5476
4,5643
4,5261
4.5059
4,4901
5,3089
5.6511
5.6148
5,6260
5.6155
5.5876
5.5745
3,8078
4.1457
4.1234
4.1
4,0009
4,0743
4,0077
4.5703
4,5739
4,5514
4.5653
4.5394
4,500
4.4958
5
5.6251
5.586
5.9922
5,5920
5,5587
5.5422
5,5979
9.2380
9.1749
9.1749
9.1328
9
8,3228
8.9
8.8754
9.8878
8,8705
8.8237
S.00
POMO-MTVRR -TVRM
MVM Light
MVM LIMGE-1Dsper
SHIELD McD
DMM-MTVVR MIVRR
MYMOE-LLON Light Light
MVMGE: MWMMa-DDegee Desper
SHIELD-MON MDD
POMO POMO-MTTX MTVRP
MVMOE- MYVMEE-Dasper Dasper
SHIELD MoD
POMO- POMO-MTVVI -TVRR
MYMEE-- -ig--Liihht Light
MVM TVMEE-Doppe Doeper
SHIELD FOILD-MMil MoD
POMO POMO-MTVRY MTVRP
MVMGE Desper
POMO MIVRP
MVM Light
MVM EVMGE-Desper
SHEELD MaD
Light Light
MVMGE- EIVMEE-Depper Desper
POMO POMO-MTVRS MTVRP
MVMEE Light
MVM Masjer Desper
SHIELD McD
HGS
MVM
SHIELD
OR toolss
MVMOE
SHIELD
DR- tools
MEME
MYMAE-Ligh
SHIELD
OR Aools
MYME
SHIELD D
MVMoE
MYMOE-L
SHIELD-Mol
SHIEL
OR--tols
MEM
SHIELD
OR toolss
POMO-MIVEE
MVMBE
NYMoE-LIGN
SHIELD-MOL
SHIELD
OR Tools
MVME
SHIELD
F11039
Problem
CVRP
OVRP
VRPB
OVRPB
OVRPL
VRPBL
VRPBET W
VRPLITW
In-took
Out-task
32

---

BIELLD Mulki-task Multi-distribation Vehiele Routing Solver with Sparsity and Hierarchy
Table 22,
Performance of models GR9882
Time
10.86s
9,87%
17.28:
19.25
6m
9.146
12,73x
11.40s
18.96s
21.64s
8,855
11:24s
10.87s
1881
21.63%
2m
7.43s
9,80s
9.05%
16.03x
18.07s
2m 30.38%
8.55%
11.11s
10.40s
18:04s
30.40s
2m
9,20%
12.16s
11.28:
19.31s
22.02s
2m.436
9.19%
11.49s
18-45
20.62s
8,90%
11.47s
18.44
20.745
2m
2m
2m
MTMDVRPIO
-0.5707%
-1.174%%
-1,02538
-1,86478
-1.9215%
8 600099
8.2577%
8. 8.395698
7.18569
6.8274%
7.5389%
7.04608
7.4403%
5.3396%
5.0239%
12.52208
10
12,188598
8.1741%
7.6776%
12.5485%
12.06518
12.37968
104030%
9.9189%
7.5557%
7.06449%
7.5816%
5.4452%
0.009%
7.72618
7.9140%
6.6217%
6.2376%
12.45188
11.900%%
12.2460%
10.2885
Cap
5.
Obl
10.962
10,8673
10.8343
10.8499
10.7588
10:7533
14.1579
15 15.3550
15. 15,3400
15 16369
15. 11.1141
8,223
9.3763
9.5344
1844
1566
5 5,3628
6.0290
5.9425
6,0122
5.7983
5,77
9.82116
9.7838
9.9000
9:6345
9. 9,5922
8.7677
9.3965
9.3546
9.5821
9.21
1826
14,8707
16.0056
16.0050
15 8090
15 15,7599
8,7657
9,8478
9.8019
9.6544
15
Time
1m 86
3.424
3.13s
8.46
5.00
5.73
Im 18:
281s
3,56s
9.93x
6.59%
Im 1m
2.74s
3.86s
10:44
5.81
6.65
2.5%%
3.42s
3,12%
8.33
5.02%
3.69s
2.79%
3.87%
3.766
10.09s
368
6.57s
Im 17s
4.01s
3.74k
10.62:
5.97%
6.81
mm 22:
2.94s
3,66s
9.64s
6.30%
Im 13:
2.90%
4.00%
10.35
5.97%
6.6%
mm
1m
MTMDVRPS0
Gap
0.6507%
0,0804%
0.1778%
-0. 0.1270%
-0.2962%
-0-4024%
6
5.5408%
3,7197%
5.0722%
4.9821%
4,757
6,0840%
5.9100%
6.2520%
4.0754%
4,8490%
4,5997%
9,0419%
8.3113%
9.3004
7.484%%
7.1102%
6.925%
11 11.0402%6
10. 10.78957%
10.9458%
10.2 10.25365
9,7525%
9,5448
6.09K6
5.0032%
6.2420%
5.3321
4,827
4.6124%
9,8331%
9.1785
9,350%%
9,0618%
8.7144%
8.2500
11.2345%
11.0920%
11-1131%
10.0965%
9,7509%
Ob)
7,0306
7.1025
7,0583
7.0674
7.0458
7.0342
7.0267
8.7191
9
9.0580
9.0011
8.9555
8,9728
3.5713
5.6981
5.6898
5.7075
5,6333
5,6333
3,6489
3.9788
3.9540
3,9894
3.02119
3,9083
3.00396
5.3443
5,9343
5.9228
5.93U7
5.8931
8600))
5,8538
3.4180
5.7484
5.7388
5.7578
7,00
5.68
3,007S
5,5652
9-4066
9.3566
9.3414
9.3011
9.26 14
3.3472
5.94
5.9443
5.00966
5,89 12
POMO POMO-MTVRI MTVRP
MVM Light
SHIELD WIELD-MM MoD
POMO- POMO-MIVVE -TMVRR
MVM Light
MVMeE: EiMeE-DDeper Desper
SHIELD BELDD-MO M--
POMO POMO-MTVRE MTVRP VRP
MVM Light
MVMOE- MMEE-Dppp Depper
SHIELD MeD
POMO- POMO-MIVRE -TVVP
MVMME- Light
MVMOE-1 DappN
SHIELD LD McD
POMO-MTVRE MTVRP
MVMoE-LLUe Light
MYMQE: Desper
SHIELD DILDD-MA MoD
POMO MTVRP
MVM Light
SHIELD FEELD-MM McD
POMO- -ITVI
MVM Light
MVMOE- MiMoE--Depps Desper
SHIELD BELDD-MO M-D
POMO POMO-MTVRE MTVRP VRP
MVMOE-DNe Desper
OR-40ols
MVMoE
MVMoE-Deve
SHIBLD
OR mools
SHIELD D
OR DR--0ooS
MYMOE
SHIBLD
OR 400ls
MVM0E
SHIELD D
POMO MVMoE
SHIELD
OR- OR--000S
MVMOE
SHIELD
OR mools
SHIELD D
OR- AoR--
MVMoE
MVMoF.I.
MVMDD
MV
Problem
VRPL
VRPTW
OVRPTW
OVRPSL
OVRPB
OVRPLTW
VRPBLTW
OVRPELTW
Time
2an 1.5
11:51s
10.66%
1R.03s
20.47
2m 37,
7.50s
10.23
9.45
17.09s
19.54%
2m 355
6.73c
9.1
14.99
16.985
2m 40%
7.0%
9.42s
8.69s
15.666
17.64%
7.98%
10.83s
9.81s
17.468
19.89
2m 468
7.4ss
9.60s
8,91s
1.5.70s
17.65
2m 42
8.55
11.38%
10.30s
17.77s
20.07%
2m 40%
9.87
13:51s
12.0%%
19.73%
22.28
MTMDVRPION
3.6221
3.3953%
3.5564%
2.6-449
2.620%%
6.885%
6.5072%
4.265%
3.5776%
2.5155
L9936%
2.1470%
0.758%
0.7073%
12 55995%
10.782696
12.335008
7.692%%
70166%
6.8978
6.6897%
44000%
3.77988
22328%
1.784%
20334
DAR15
0.5610%
22220
7.8985%
8.1885
6.7998%
6.3992%
3.4003%
3.1988%
3.5100%
22352
1.85569
Goo
8.507
Oly
10 3936
10.7649
10. 14.7400
10.7575
10,6632
6622
6.4873
60236
68992
6.7528
6.7
70488
R.1316
8.1051
R.1145
ROIS
800033
533117
5.9619
58707
5,508
5.7386
5.7054
6.4665
69109
6.517
68892
6,7470
6.7033
19259
N.0977
8.022
BOR25
7.9556
7.6677
14,7076
15
8744
15.6726
15.6150
14,6818
1.5115577
15.119%
14.9741
14.9220
10
Time
Im 175
4.728
5,8%
9.65
5.76%
6.4%
9
2.32s
3,08s
8.84%
5.9%
1m 25
2.12%
3,22s
7.04
4.6%
5.2%
mm 136
2.2%
3.3
3.06
8.04
4.9%
566
2.30 2,38
3.4hs
325
9.0%%
5.24
6.05%
mm 15
3,268
3.07
8.9
4.74
5.3%
1m 23
2.7%
3,6%
9.47%
6.16%
1m
2
3.9%s
10.08%
5,7%
6.40%
1m
MTMDVRP50
2.19138
1.3660%
1.725338
14537%
1.2799%
1.156%%
40486%
4.5528
49079%
3.77058
33587%
3.0665%
2.648%
20273%
22479%
1.7840%
146922
1.2939%
8.7288
8.362
9.307%
752889%
6.5855
684011
5.062%
46183%
4.6660%
4.13708
344658%
3.1457%
263109
20221
233168
2.0785%
1.4988%
12376%
9.117%
9.0631
9.238.%
8.9607%
8.5275%
8.1688%
43377%%
3.8812%
4.024%%
3.6702%
3.28902
3,092298
Cap
Obj
6.9560
7.0647
7.0754
7,0866
7.0445
7,0360
4,3741
4.4856
4.4670
4,4821
4.4342
65
1,4039
5.3678
5.5305
5.9960
5,4825
5.4659
5,4500
3 3,6601
3.9844
3 3.967
4.0022
3.9129
3,9116
4.2759
4,4924
4.4725
4,4528
4.4226
4099
3,4044
5,1124
5.5290
5.167
5,4844
5.4701
8.5591
9.3818
9.34 9.3489
9.3261
9,2801
9,2497
8,7717
9,1521
9.1039
9.0936
9
9.0343
4
POMO MTVRP
MV Light
MVMoE-Dese Desper
SHIEL D MoD
POMO-M MO-MTTV RE
MV MoE--iggt Light
MVMOE: MVMoE-Desgu Deegee
SHIELD D-M
POMO MTTRP RRP
MV Light
MVMoE-DeSpE Desper
SHIEL D MoD
POMO MTTV
MVMoE-Liggt Light
MVM DeggDe Desper
SHIEL D McD
POMO POMO- MT RP
MY MoE-Liggn Light
MVM.EE-D MVMoE-DDegue Deeget
SHIEL SHIELD-MoD D-M
POMO MTVRP
MVM Light
SH D MoD
POMO-MITY COMO-MTVR REP
MV MoE-Lighht Light
MVMOE- MVMoE-DespC Desper
SHIELD D-O
POMO MTTRR RRP
MV Light Light
MYMOE--DON Desgget Desgeet
SHIELL D MoD
HGS
MVMoE
SHIELD
OR lonis
MVMBE
SHIED
OR -oool
MVMoE
SHIELD
OR -ools
MVMOE
SHIELD
MYMOE
SHEED D
MYMOE
MVMoE-Dest
SHIELD
OR lnnis
MYMBE
SHIEL
OR 4000
AYM&E
GRO
CVRP
OVRP
OVRFB
OVRPL
VRPBL
VRPBTW
VRPLTW
In-inkk
Out dank
33


Reviews:
[{"review_id": "LPxqqOuGnP", "reviewer": "Reviewer_7L8M", "summary": "This paper introduces the Multi-Task Multi-Distribution Vehicle Routing Problem (MTMDVRP), an extension of the MTVRP. The MTMDVRP effectively captures the complexities inherent in real-world industrial applications by incorporating various realistic customer distributions. To address these challenges, the authors propose a neural solver, SHIELD, which integrates soft clustering, Mixture of Experts, and Mixture-of-Depths (MoD). The authors further conducted experiment on 9 real-world maps with 16 VRP variants each.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**[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.\n\nSpecifically, 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**.\n\nMoreover, 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.\n\n**[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.\n\n**[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.\n\nAdditionally, 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.\n\nAs 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.\n\n[1] Multi-task learning for routing problem with cross-problem zero-shot generalization. SIGKDD, 2024\n\n[2] Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. ICML, 2024", "claims_and_evidence": "The paper's claim is supported by their numerical experiments, in both time and suboptimality gap. Although I'm not an expert in VRP problems, it seems that MTMDVRP is hard to solve since multi-distributions are considered.", "methods_and_evaluation_criteria": "The authors proposed the innovative network learning architecture SHIELD, introduced the clustering layer to enhance the hierarchical expression ability of the model, and added the MoD layer in the decoding to take into account the sparsity, which is impressive in the field of machine learning to solve combinatorial optimization problems.\n\nHowever, the introduction of MoD and soft clustering are meant to enhance generalization; but in this paper, the generalization capabilities for larger-scale problems have not yet been tested. All experiments are conducted on relatively small data, namely 50 nodes and 100 nodes problems. How the model behave on larger data (>= 200) should be tested.", "theoretical_claims": "The theorem in the main paper was excerpted from Theorem 2.3 in Goldberg & Jerrum, 1993. Although I didn't check the book, I'm prone to believe it's correct.", "experimental_designs_or_analyses": "See Methods And Evaluation Criteria.", "relation_to_broader_scientific_literature": "VRP is closely related to operation research. That said, MTMDVRP seems to be a novel problem, though I can hardly evaluate how important it is to OR community.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strength:\n1. By combining MoE and MoD, and soft clustering, the proposed neural solver SHIELD outperform existing methods across a range of VRP variant tasks.\n2. The authors conducted solid experiments that involve nearly all modules, including MoD, MoE, and soft clustering, with detailed descriptions of the experimental procedures and results.\n\n\nWeakness:\nAlthough the paper studied a difficult question, I feel the contribution of adapting clustering nodes/MoE/MoD is limited, as it has already been thoroughly explored in previous works, therefore it's barely innovative.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Is the proposed method SHIELD designed for the scenario of multi-task multi-distribution? What about its performance on the scenario of multi-distribution?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VRxGAGxxe3", "reviewer": "Reviewer_Q6ps", "summary": "This paper introduces SHIELD, a framework with sparsity and hierarchy principles to address MTMDVRP problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**[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:**\n* 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.\n* 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.\n* **Together, their synergy enhances the model's ability to capture context-dependent, adaptive fine-grained decisions for MTMDVRP.**\n\nTo 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.\n\n**[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.\n\nTo 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.\n\n|||MTMDVRP50||||||MTMDVRP100||||||\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|||In-dist|||Out-dist|||In-dist|||Out-dist|||\n||Model|Obj|Gap|Time|Obj|Gap|Time|Obj|Gap|Time|Obj|Gap|Time|\n|In-task|INVIT|6.4082|9.1437%|66.48s|6.7462|9.0992%|66.84s|10.6057|17.2425%|66.65s|11.4286|18.4235%|68.06s|\n||SHIELD|6.0136|2.3747%|6.13s|6.2784|2.7376%|6.11s|9.2743|2.4397%|19.93s|9.9501|3.1638%|20.25s|\n|Out-task|INVIT|6.2996|15.3570%|69.43s|6.6932|15.2064%|70.11s|11.1489|26.8217%|68.00s|12.1012|27.9947%|69.98s|\n||SHIELD|5.7779|6.0810%|6.20s|6.1570|6.3520%|6.20s|9.2400|5.6104%|19.92s|9.9867|6.2727%|20.18s|\n\n[1] Linear attention is (maybe) all you need (to understand transformer optimization). ICLR, 2024\n\n[2] INViT: A generalizable routing problem solver with invariant nested view transformer. ICML, 2024\n\n[3] Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. ICML, 2024", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "This paper advances the Multi-Task VRP (MTVRP) setting to the more realistic yet challenging Multi-Task MultiDistribution VRP (MTMDVRP) setting.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n1. This paper is well-written and easy to follow.\n2. The experimental results are solid.\n3. The integration of MoD to reduce computation overhead is interesting.\n\nQuestions:\n1. Why does the proposed framework utilize a MoE encoder?\n2. Why the authors choose to use MoD to reduce computation overhead instead of other techniques such as linear attention.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7O9msCtyNK", "reviewer": "Reviewer_yZkq", "summary": "This paper proposes a novel problem, the Multi-Task Multi-Distribution Vehicle Routing Problem (MTMDVRP), which is an extension of the traditional Multi-Task Vehicle Routing Problem (MTVRP). The problem focuses on different node distributions of different geographical regions in the real world, further considering the generalizability. For this problem, the paper introduces SHIELD, a novel neural combinatorial optimization solver, which leverages sparsity and hierarchy principles through the Mixture-of-Depths (MoD) technique and a context-based clustering layer to improve efficiency and generalization. Experiments demonstrate that SHIELD outperforms existing methods across 9 real-world maps and 16 VRP variants, showing strong generalization capabilities, especially in cross-task and cross-distribution settings.\n\n## update after rebuttal\n\nIn the rebuttal, authors have addressed most of my concerns with experiments. I believe this is a promising work to solve MTMDVRP. I would like to keep my postive rating. It would be beneficial if the code could be further made public.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**[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.\n\nTo 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.\n\n**[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](https://imgur.com/a/ihDUR0v) that includes the solver's performance across tasks and distributions.\n\n**[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.\n\n**[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.\n\nNevertheless, 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.\n\nAdditionally, 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.\n\n|||MTMDVRP200||||\n|:-:|:-:|:-:|:-:|:-:|:-:|\n|||In-dist||Out-dist||\n||Model|Obj|Gap|Obj|Gap|\n|In-task|POMO-MTVRP|14.5695|5.4613%|15.9036|7.0430%|\n||MVMoE|14.6137|5.8753%|15.9391|7.3486%|\n||MVMoE-Light|14.6420|6.0924%|15.9581|7.4784%|\n||SHIELD-MoD|14.4123|4.7980%|15.7342|6.1487%|\n||SHIELD|14.3648|3.7939%|15.6536|5.0516%|\n|Out-task| POMO-MTVRP|15.5735|8.5203%|17.1759|10.2531%|\n||MVMoE|15.6040|8.8840%|17.2145|10.5085%|\n||MVMoE-Light|15.6412|9.1470%|17.2423|10.7143%|\n||SHIELD-MoD|15.5373|7.4336%|17.1948|8.8987%|\n||SHIELD|15.3896|6.4856%|16.9555|7.8179%|\n\n**[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**.\n\n[1] Boosting Neural Combinatorial Optimization for Large-Scale Vehicle Routing Problems. ICLR, 2025\n\n[2] UDC: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems. NeurIPS, 2024\n\n[3] Multi-task learning for routing problem with cross-problem zero-shot generalization. SIGKDD, 2024\n\n[4] Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. ICML, 2024\n\n[5] Multi-type attention for solving multi-depot vehicle routing problems. ITS, 2024\n\n[6] Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem. Cybernetics, 2021", "claims_and_evidence": "The main claims made in the paper are supported by extensive experiments. The authors demonstrate the superior performance of the SHIELD model across 9 real-world maps and 16 VRP variants, showing its effectiveness in multi-task and multi-distribution scenarios. The experimental results highlight SHIELD's strengths in terms of optimization objectives (e.g., tour length) and generalization capabilities (e.g., cross-task and cross-distribution performance). Additionally, the ablation studies provide insights into the contributions of the sparsity and hierarchy designs.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria in the paper are largely reasonable and closely related to the research problem. The MTMDVRP problem aims to further consider the complexity of node distributions in the real world. The authors selected a range of tasks and distributions for training, and then tested on previously unseen tasks and distributions, achieving better performance than other baseline methods. This effectively demonstrates the generalization capability of the solver.", "theoretical_claims": "The paper only contains one theorem related to the VC (Vapnik-Chervonenkis) dimension, which is widely acknowledged. The idea derived from this theorem is relatively intuitive.", "experimental_designs_or_analyses": "I have checked the validity of the experiment for SHIELD. The experiments are divided into in-task, out-task, in-distribution, and out-distribution categories. This setting allows for a comprehensive evaluation of the model's generalization capabilities.", "relation_to_broader_scientific_literature": "The paper expands current the MTVRP problem to the MDMTVRP problem. As part of the problem, the multi-task learning (MTL) has been an active research area in machine learning and deep learning, particularly in improving model generalization and reducing overfitting. Also, the Mixture-of-Depths (MoD) technique in the paper has also been widely used in other domains to improve generalization and reduce model complexity.", "essential_references_not_discussed": "The paper has correctly cited the relevant prior work.", "other_strengths_and_weaknesses": "Strengths:\n\nS1. The MTMDVRP setting proposed is a novel and practical extension of the MTVRP, addressing the limitations of uniform distribution assumptions in prior works. This makes the problem formulation more relevant to real-world applications.\n\nS2. The SHIELD model incorporates Mixture-of-Depths (MoD) and context-based clustering layers, which effectively balance computational efficiency and generalization.\n\nS3. The authors conduct thorough experiments including in-distribution, out-distribution, in-task, out-task settings, demonstrating the model's generalization capability.\n\nWeaknesses:\n\nW1. The use of real-world maps, though diverse, primarily focuses on national-scale distributions. The inclusion of more granular urban or local distributions could provide a more comprehensive evaluation of the model’s adaptability. The paper mentions that the observed distribution differences are due to the company’s business expansion. However, the realistic scenario is better captured by the expansion of business across cities.\n\nW2. Lack of comparison with non-neural solvers. This omission makes it difficult to assess how SHIELD performs relative to well-established non-neural methods.\n\nW3. The code is not released, which may affect the reproducibility of this work.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "Q1. Can SHIELD scale to very large problem instances (e.g., >1000 nodes)?\n\nQ2. The article tests SHIELD on 16 VRP variants, but some real-world problems may involve more complex constraints (e.g., multi-depot, heterogeneous fleets, stochastic demands). Can SHIELD handle such scenarios, or are there inherent limitations?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "myUnuZR3ku", "reviewer": "Reviewer_SpW1", "summary": "This paper proposes a foundation model for vehical route problem with multi-task and multi-distribution. The model contains the mixture-of-depth decoder, which dynamically selects nodes at each decoding step, thus improving the efficiency and generalization ability of the model. A context-based clustering layer is proposed for modeling the spatial hierarchy of different cities. Extensive experiments on 9 real-world maps with 16 VRP variants show the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**[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.\n\nAlternatively, 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.\n\n**[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.\n\n**[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.\n\nNevertheless, 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](https://imgur.com/a/Dwo4EbE). 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.\n\n**[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**. \n\n[1] Graph2Route: A Dynamic Spatial-Temporal Graph Neural Network for Pick-up and Delivery Route Prediction. SIGKDD, 2022\n\n[2] DRL4Route: A Deep Reinforcement Learning Framework for Pick-up and Delivery Route Prediction. SIGKDD, 2023\n\n[3] SED2AM: Solving Multi-Trip Time-Dependent Vehicle Routing Problem using Deep Reinforcement Learning. TKDD, 2025", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have gone through most of the theoretical claims, and all of them are correct.", "experimental_designs_or_analyses": "The experiment design is sound, and the results are convincing.", "relation_to_broader_scientific_literature": "The  contribution of this paper is related to two research communities:  (1) the first is VRP-related research, which aims to solve routing problems with different constraints. (2) the second is foundation model-related research, which aims to build general models that can solve multiple tasks in a zero-shot way.", "essential_references_not_discussed": "In terms of related work, it would be better to discuss route planning methods such as:\n\nGraph2route: A dynamic spatial-temporal graph neural network for pick-up and delivery route prediction\nDRL4Route: A Deep Reinforcement Learning Framework for Pick-up and Delivery Route Prediction\nwhich are both learning-based solutions for solving the routing problem", "other_strengths_and_weaknesses": "As for strengths, this paper solves a practical problem and is well-written. In terms of the methodology perspective, the idea of \"using the amount of compute to potentially serve as a regularization for the model\" is quite interesting and seems to help the model save the computation and generalize well at inference. The extensive experiments also show the effectiveness of the method.\n\nHowever, in terms of the drawbacks,  each city in this paper is only associated with (x, y)  for its location. However, in the real world, each city can have various spatio-temporal attributes. How can we effectively deal with that by the proposed model?", "other_comments_or_suggestions": "please see the strengths and weakness", "questions_for_authors": "Is there any experiment to show how much computational resources can be saved at the inference time?\n\nIs there any scale-law observed at inference time by the proposed decoder?\n\nHow would beta in the decoder influence the performance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents SHIELD, a novel neural combinatorial optimization solver for the Multi-Task Multi-Distribution Vehicle Routing Problem. 

SHIELD incorporates sparsity and hierarchy principles, effectively balancing computational efficiency and generalization.    
The model is evaluated on 9 real-world maps with 16 VRP variants each, showing strong generalization. However, the paper lacks a comparison with non-neural solvers, making it difficult to assess SHIELD's performance relative to well-established methods.    

Despite the cons, the reviewers acknowledge the novelty of the problem setting, the effectiveness of the SHIELD model, and the extensive experimental validation.  The authors also provide rebuttals addressing the reviewer concerns and providing additional experimental results.    

Considering the overall assessment and the authors' efforts to address the concerns, the decision is a weak accept.
Decision: Accept (poster)