Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP
Authors: Yuxin Pan
Zhiguang Cao
Chengyang GU
Liu Liu
Peilin Zhao
Yize Chen
Fangzhen Lin
Venue: NeurIPS 2025 poster ()
Keywords: vehicle routing problems
combinatorial optimization problems
reinforcement learning
Primary area: reinforcement_learning
TL;DR: We present a unified neural solver for multi-task VRPs using mixture of specialized experts based on the state-decomposable MDP.

Abstract: Existing neural methods for multi-task vehicle routing problems (VRPs) typically learn unified solvers to handle multiple constraints simultaneously. However, they often underutilize the compositional structure of VRP variants, each derivable from a common set of basis VRP variants. This critical oversight causes unified solvers to miss out the potential benefits of basis solvers, each specialized for a basis VRP variant. To overcome this limitation, we propose a framework that enables unified solvers to perceive the shared-component nature across VRP variants by proactively reusing basis solvers, while mitigating the exponential growth of trained neural solvers. Specifically, we introduce a State-Decomposable MDP (SDMDP) that reformulates VRPs by expressing the state space as the Cartesian product of basis state spaces associated with basis VRP variants. More crucially, this formulation inherently yields the optimal basis policy for each basis VRP variant. Furthermore, a Latent Space-based SDMDP extension is developed by incorporating both the optimal basis policies and a learnable mixture function to enable the policy reuse in the latent space. Under mild assumptions, this extension provably recovers the optimal unified policy of SDMDP through the mixture function that computes the state embedding as a mapping from the basis state embeddings generated by optimal basis policies. For practical implementation, we introduce the Mixture-of-Specialized-Experts Solver (MoSES), which realizes basis policies through specialized Low-Rank Adaptation (LoRA) experts, and implements the mixture function via an adaptive gating mechanism. Extensive experiments conducted across VRP variants showcase the superiority of MoSES over prior methods.

Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP
Yuxin Pan
Zhiguang Cao²
Chengyang Gu Liu Liu
Peilin Zhao 4.6
Yize Chen Fangzhen Lin
'The Hong Kong University of Science and Technology
Singapore Management University
The Hong Kong University of Science and Technology (Guangzhou)
*Tencent AI Lab
University of Alberta
Shanghai Jíao Tong University yuxin. parii...nccoontt....mm curpicc...st.ttt ust.uk hk
Abstract
Existing neural methods for multi-task vehicle routing problems (VRPs) typically learn unified solvers to handle multiple constraints simultaneously. However, they often underutilize the compositional structure VRP variants, each derivable from common set of basis VRP variants. This critical oversight causes unified solvers to miss out the potential benefits basis solvers, each specialized for a basis VRP variant. To overcome this limitation, propose framework that enables unified solvers to perceive the shared-component nature across VRP variants by proactively reusing basis solvers, while mitigating the exponential growth of trained neural solvers. Specifically, we introduce a State- sette-Decompssable MDP (SDMDP) that reformulates VRPs by expressing the state space the Cartesian product of basis state spaces associated with basis VRP variants. More crucially, this formulation inherently yields the optimal basis policy for each basis VRP variant. Furthermore, a Latent Space- Space-based SDMDP extension is developed by incorporating both the optimal basis policies and a learnable mixture function to enable the policy reuse in the latent space. Under mild assumptions, this extension provably recovers the optimal unified policy of SDMDP through the mixture function that computes mapping from the basis state embeddings generated by
the state embedding optimal basis policies. For practical implementation, we introduce the Mixture- of- of-Specialized-Expeeee Solver (MoSES), which realizes basis policies through specialized Low-Rank Adaptation (LoRA) experts, and implements the mixture function via adaptive gating mechanism. Extensive experiments conducted across VRP variants showcase the superiority of MoSES over prior methods. The source code is available at https://gitthubb. http:///ithhub.oooo/paayyym/sss/ vrp
Introduction
Vehicle routing problems (VRPs) are a canonical class of combinatorial optimization problems (COPs) with broad applications spanning transportation [19], logistics [6]. and manufacturing [80]
While exact methods are computationally prohibitive [36]. and heuristic methods rely substantial speciff knowledge [23 (66), recent studies craft learning baased neural solvers for empirically
sound performance with lower makespan and marginal domain expertise 667 54 34 35
Prevailing
"This work is done when Yuxin Pan works as an intern in Tencent Al Lab.
t Corresponding Authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

approaches primarily target one specific VRP, with tremendous efforts dedicated to out-of-distriburt (OOD) generalization [4 84 T3
82 56 47.. However, practical applications involve mulriple VRP variants with diverse node attributes and solution constraints, making the development of specialized neural solver costly due to the need for retraining from scratch.
Recent advances in multi-task neural solvers are conscious of inherent partial similarities present among these variants, enabling efficient knowledge transfer via shared embeddings. These methods commonly resort to specialized adaptations of a pretrained backbone model 41 Although these methods perform favorably without requiring training from scratch, they struggle to scale due to the combinatorial explosion of VRP variants. This is because arbitrary combinations of orthogonal attributes can introduce new variants, inevitably leading to costly repetitive tuning and adapter proliferation. As an alternative, unified neural solvers instead are capable of handling numerous VRP variants simultaneously. These methods typically unify VRP variants via attribute composition [42], and propose various architectural innovations { 3 38) Although these methods treat VRP variants as combinations of attributes, they fail to fully exploit this compositional structure inherent in VRP variants. This structure implies that attributes of each VRP variant actually derive from a shared set of basis VRP variants, each characterized by a unique attribute. We argue that there exist basis solvers, each tailored to a specific basis VRP variant, may enjoy experience valuable for unified solvers.
To elucidate the possible valuable insights that basis neural solvers could offer for unified solvers, we exemplify the widely-used pecoder-decoded based neural solver as a case study. The encoder is tasked with yielding static node embeddings for the subsequent step-wise solution decoding. Thus, each basis solver's 's encoder produces embeddings capturing unique attribute of its corresponding basis VRP variant. Since attributes of each VRP variant stem from shared basis variants, the unified solver's encoder possibly perceive both individual attribute information and inter-attribute connections in its embeddings. The decoder gradually builds solutions using static node embeddings and the dynamic context while adhering to constraints. Likewise, two critical properties emerge within each VRP variant: its dynamic context can be broken down into conditionally independent components, each corresponding to distinct basis variant; and its constraints form a superset of those associated with corresponding basis variants. The internal embeddings of the unified solver's 's decoder thus may partially coincide with those of the decoders of basis solvers. Therefore, we argue that the unified solver could benefit from valuable insights of basis solvers. Morcover, the key insights of a neural solver predominantly reside in its continuous embeddings. This motivates us to reformulate VRPs with the aim of reusing basis solvers in the latent space.
In this paper, to seamlessly bridge between VRP variants and basis VRP variants, we propose VRPs reformulation through the novel State Decoppocooee MDP (SDMDP) framework. To be specific, this framework expresses the state space as the Cartesian product of basis state spaces, each associated with a basis VRP variant. As a result, any state admits a decomposition into conditionally independent basis states. Indeed, disclosed above, SDMDP is fundamentally grounded in the observation that both static attributes and dynamic contexts of VRP variants originate from their corresponding basis variants. More importantly, SDMDP not only targets towards optimal unified policy, but also yields optimal basis policies inherently, each tailored to a specific basis variant in cases where a VRP variant comprises only single attribute. To fully reuse optimal basis policies, we operate under the primary assumptions that any unified policy can generate basis state embeddings and a mixture function exists to map these resulting basis state embeddings this, we further develop a Latent Space- SDMDP (LS-SDMDP) extension by incorporating the optimal basis policies and the mixture function. In this extension, each basis state inherent in a state is fed to its corresponding optimal basis policy for the basis state embedding. These embeddings are then transformed into the state embedding through the mixture function, which subsequently informs the action selection. Under mild assumptions. LS-SDMDP provably recovers the optimal unified policy for SDMDP. For practical implementation, we introduce the -f-euralo--Specciiiieee- Exriiiteed-eeetss---e-e Solver (MoSES), which realizes basis policies through specially designed Low-Rank Adaption (LoRA) (26] experts, each fine-tuned for specific basis variant from frozen pretrained backbone model, and implements the mixture function via an adaptive gating mechanism. In addition, we design multiple adaptive gating mechanisms for comparative analysis, and implement MoSES with different backbone networks to show its plug-and-play versatility. Extensive experiments across VRP variants validate the superiority of MoSES against prior methods.
the corresponding state embedding. Built upon
2

---

2 Related Works
This Section reviews recent advances in task-specific neural VRP solvers, multi-task learning ap- proaches for VRPs, and mixxure-ff-ppccializeeeee (MoSE) methods. Please refer to Appendix [ for more detailed reviews.
Task-Specific Neural VRP solvers. Neural solvers, individually developed for each specific VRP.
fall into three main categories:
constructive methods end-to-end infer solutions via autoregressive 4
mechanisms 66
34
35
33
51
60 84
17
22
30
15
46
47
iterative methods refine solutions
via local search operators until convergence 45
24
50
49
and divide-and andele--n--oonueee methods
decompose problem instances into smaller solvable sub- instannttnncs [16
32 g 39 [5] (25 77 82 [56].
However, these methods typically require specialized network architectures and retraining from scratch to handle numerous VRP variants, bringing about excessively high costs.
Multi-Task Learning for VRPs. To cope with practical scenarios involving multiple VRP variants, the efficient transfer learning is leveraged to obtain specialized neural solvers by considering inherent similarities among VRP variants. Current methods predominantly adopt either full- parameeer fine- adapter fine-tuning [4 [4), both built on a pretrained backbone
tuning [ or model. However, these methods struggle with the combinatorial explosion of VRP variants. Notably, although the LoRA adapter is used for problem-speciffe adaptation in [4T], its potential as part of a unified solver to handle the exponential growth of variants remains unexplored. In contrast, unified solvers are designed to handle multiple VRP variants simultaneously. These methods commonly unify VRP variants via attribute compositions [42 and employ various architectural innovations such as mixture of experts (MoE) 83 modified Transformer [3] large language model (LLM) based encoder [29], dual attention model (38, mixture of depths (Mol) (20, specialized decoders [68 40)
diffusion model (37). or mixed-curvatue
based encoder 44). However, the potential benefits of incorporating explicitly specialized basis solvers remain unexplored. Notably, while MoE is employed
in 183y, it learns an implicit and less interpretable specialization rather than incorporating off-the- shelf basis solvers as experts.
Mixture of Specialized Experts. Prevailing MoSE methods can be broadly categorized into two paradigms: merging entire models and module composition. Approaches based on merging entire models seek to combine independently trained models to efficiently achieve the performance compara- 63 61 76). However, these approaches exhibit inferior OOD generalization, compared to layer-wise aggregation of expert models. Our implementation aligns more closely with the module composition paradigm which supports the finer-grained aggregation. These methods primarily include: selective adapter averaging [9] [9] mod-
ble model ensembling multi-task learning 77 52 75
64 12
ule fusion via arithmetic operations 10 gT 28 adapter routing based on task similarity 48 72).
and adaptive mixture of LoRA experts (MoLE) 127 78, 773 44 5 13 58 53 55
79 18). How-
ever, the potential of MoLE methods for unified VRP solvers remains underexplored, and existing
composition methods possibly prove inadequate for multi-task VRP scenarios.
3 Preliminaries
VRP Variants. We adopt the vehicle routing environment from B] A capacitated VRP (CVRP) instance of size N is defined on graph = {V,E) g} with nodes V {vo} U(v:) N (depot and customers) and edges& & = fe(u;, 1,)10 < xi N). Each node ; (i 2 0) has coordinates (z), with each customer 2, (j 2 1) having demand oft > 0. Each vehicle has capacity Q. A feasible solution (i.e.. tour) J consists of subtours, each beginning and ending at the depot while visiting customer subset, with each customer visited exactly once and total demand of each subtour not exceeding Q. The cost function c(-) the total Euclidean length of the tour. The objective is to find the optimal tour r" with the minimal cost. CVRP, as a Basis VRP Variant, features the capacity constraint (C), serving as the foundation for deriving the remaining Basis VRP Variants by adding one of the following constraints. 1) Open Route (O): A binary variable o indicates whether the vehicle needs to return to depot (o = 0) or not (o- = 1); 2) Backhaul (B): Each customer Uy is either a linehaul with of > O or a backhaul with y < 0, where linehauls require deliveries and backhauls require pickups. VRPs with backhaul allow traversing both types in a mixed manner, but linehauls must precede backhauls each subtour 62. In VRPs without backhaul, only linehaul customers are present; 3) Duration Limit (L) Each subtour's 's cost cannot exceed threshold dur, 4) Time Window
3

---

(TW): Each node has time window bog wind) and a service duration w requiring service to begin within this window. Vehicles arriving before wi beg must wait until the window opens, and all vehicles must return to the depot by wgmd. Thus, 16 VRP variants emerge from adding arbitrary combinations of the remaining four constraints to CVRP. Please refer to Appendix A. A.2 for details of the VRP variants.
Learning to Solve vRPs. We adopt the widely-used attention-basee based neural network [34 3 38 to parameterize the VRP policy Re, which generates feasible solutions autoregressively through masked decoding. The encoder generates static node embeddings, which, with the dynamic context of the constructed partial tour 7(5(), are fed to the decoder to output the probabilities of valid nodes for the
next node 7(t), The policy factorizes as TT(T = =II To (((()))((() g), where T is the solution horizon. REINFORCE [69] algorithm with reward -(()) used to optimize the policy.
Mixture of LoRA Experts. LORA 26 is a parameter-efficien fine-tuning method that adapts pretrained frozen LLMs through low-rank matrix factorization. For linear layer with weights Wo E Rd xds, it introduces trainable matrices A E IRrxda and R44 xr (where r < min d2) denotes the LoRA rank), modifying the forward pass as hout Woh'n + "A.""" where h²d Rd and hrut E Rdd are the input and the output, and B E (0, 1]. To enhance the cross-task generalization, K task-specific LoRA experts (B ] are integrated into the L.LM (4). trainable gating function G(hin) softmax(W for LoRA experts, yielding the forward pass as hout = Wnh + Ek=n 0g By Ag
with weights W E Rxda computes coefficients {ax )
4 Methodology
In this Section, we first present the State- Setee-eccomposabee MDP framework to reformulate VRP variants. To efficiently reuse readily available basis neural solvers, we extend it to the Latent space-based SDMDP enable the unified neural solver. Finally, we propose the Sixtur-of-Speciiaizee--xx- Solver which implements basis neural solvers using specialized LoRA experts.
4.1 State-Decomposabe MDP
The State- Derempoaooessleee Markov Decision Process (SDMDP) framework is described by a 7-tuple (S,A, P, R. H4, 7, S), which extends the standard MDP by introducing a Full State Space S. This full state space S can be partitioned into T + disjoint sets over a finite horizon T: U S. For each time step 0 < t < T, the full state space S, can be further represented as the Cartesian product of n + basis state spaces: S. = II S(") This allows any full state 8 E S, to be broken down into n + 1 conditionally independent basis states:
( Please note that the full state 5, is neither observed nor influenced by the agent.
V==o where s( E s(()) for i 0, 0,...,P
Likewise, the State Space S can be partitioned as: S = U._/ St. During each episode, prior to the policy rollout, the initial state space Sg is built by randomly sampling m + 1 basis state spaces, where 0 S m S n. This results in Sn = IT. s!!h))) where VA < i S m, 0 S b, # b, S n. Especially, we stipulate that s(haa = s Please note that the value of may vary across different episodes. The initial state distribution j is thus defined on Sn. The state space S. (0 < 1 < T) is defined as the joint space of m + 1 basis state spaces evolving from the initial sampled basis state spaces, such that
S, = II s(Ob), The state St E St can be decomposed into m + 1 conditionally independent basis
states: St (b((.))
(bx) 1m where s(h)) E Es(")), for i = 0,..., m.
The Action Space A is conditioned on the state 8,, denoted as A, = A(st), indicating that the basis states in the state st jointly define the feasible action space. The Transition Probability Function P returns the probability distribution of the next state $1+1 E S141 given the current state-action pair (st, az) S, A,. Due to the conditional independence of the basis states, the transition probability function P factorizes as: P(5 a)) = - P(s (.(()) aa). The Reward Function R maps the state-action pair (st, 0+) to a scalar reward R. 7 E (0, 1] is the discount factor. Given the state st. the policy π yields the probability distribution over Ar.

---

Enwronment
Baris
(t)
Environment
Action R2
Basis States shal
Action &
Uptimal Boss Policies
Policy
Pollcy a
Embeddings
Basi imbeddings mgs 2
Mixture Function
State Embeddiing
Mixture Function Fo
State Embeddingg
(a) SDMDP framework
(b) LS-SDMDP framework
Figure I: Left: SDMDP employs the policy that incorporates a mixture function. Right: LS-SDMDP
integrates both the optimal basis policies and the mixture function.
We abuse T to denote the trajectory (So, "u...., ST). The objective of the SDMDP framework is to identify Optimal Unified Policy x² arg max, E, (e (E T-1 72 So s) arg max, Es- [VT.P (s)], where VT.P is the value function. This framework defines the 0-th Basis Task using the initial state distribution over s(0) while the i-th Basis Task (1 S i S n) extends this
with initial state distribution over S0)) S The i-th Optimal Basis Policy π (1)* (0 S i S n) is the policy that maximizes the expected cumulative rewards for the i-th basis Task.
Remark. To reformulate VRP variants within the SDMDP framework, we begin by aligning basis states with basis VRP variants. At each step t, the state 9t decomposes into basis states: 0) CVRP: 24)) consists of node coordinates {sra, yi } linehaul demands {u! J==1 and the remaining linehaul capacity Q 1) Open Route: st introduces the binary variable 0; 2) Backhaul: s integrates backhaul demands {
Ti=1 and the remaining backhaul capacity Q. 3) Duration Limit: s(())
encompasses the duration limit ydur and the current traveled length 1çtE along the present subtour; Ji=D, service durations {w N Ji=0, and the current time wffur, Each VRP variant can be formed by composing (m + 1) (0 S. S 4) basis state spaces, using SDMDP's initial sampling mechanism prior to the policy rollout, During rollout, each current basis state evolves conditionally independently from its corresponding previous basis state given the action. The action space is defined by a masking mechanism that filters out nodes according visitation status and VRP constraints. Please refer Appendix [A.3 A.4 for details on VRP constraints and formulation. There exist basis tasks, each associated with a basis VRP variant.
4) Time Window: (4) includes time windows {wibe, w 1.V
Theorem 1. The optimal unified policy πt" and the i-th optimal basis policy (()+ coincide in their
value functions for each state & associated with the i-th basis task: V V=*.P(st) (P(s) = V= Furthermore, if both the optimal unified policy and the optimal basis policy are unique, then for each state-action pair (St, az) corresponding to the i-th basis task, it holds that T² (arls:) = nt (60)* (()))(aa))) st).
,P (se).
Proof. Please refer Appendix foor a detailed proof of Theorem 1
Assumption 1. In the SDMDP framework, any state is composed of m conditionally independent basis states, denoted as = ( Accordingly, we assume that any policy π is capable of extracting the basis state embedding 2(b.) E RRd for each glb.), where this assumption, we further posit that there exists deterministic bijective mixture function fs S IT Rd + Rdd, parameterized by 6, which maps the basis state embeddings (2( 1 the state embedding E TRd for the given state 8, represented as [a(2(b)) (bm); s). Thus, the policy defined over the action space can be rewritten as
O...., .....,,. m. Under
);
=(als)= Σ T(al=)<(=ls)=
Σ
T(a)f((2(0)) (b0)
0m), s)) II m(> 11060))
(1)
2(0a) (bm)
where ITT-p ( (2(be)) = (2(6)) ...., (s)))ss). The second equivalence in Equation hhlds
because fo is assumed to be deterministic.
Assumption 2. For any state s. and for any two policies ा and n', we assume that if Va e A(s), ((ass) = N' ra(a))), then Vz e Rd (2|s)) = T'(2s) and conversely.
Remark. Theorem discloses the partial consensus between the optimal unified policy and each opti- mal basis policy, laying the foundation of the policy reuse. Motivated by the observation that neural
5

---

networks primarily encode knowledge in their embeddings, with distinct features captured at different layers, we develop latent space approach for reusing optimal basis policies. Assumptions T serve as the prerequisites for Theorem Figure [(a) illustrates the SDMDP framework.
4.2 Latent Space-based SDMDP
The Latent Space-based SDMDP (LS-SDMDP) incorporates all elements of SDMDP, and extends SDMDP by introducing (n ..... xr (m))x So). During each episode, each time step 0 < ( T, a state 8, E Se is sampled from either the initial distribution (u())) or the transition probability function (($1411815 (t), both of which are well defined within the SDMDD framework. Following
that, each component s((x) of St (0 S S m) is fed to the corresponding optimal basis policy (b.) R.d Collectively, these embeddings form tuple, denoted as (z) (bn) ,,..,,,,,,,, (. To infer the state embedding 2; for the state 8t. fo takes as input this tuple along with the state, formally expressed as 24 = fa(2; (bb) ..... 2t designed for LS-SDMDP, directly observes the embedding vector and outputs an action distribution, denoted as TT. For brevity, the integration of fo into the policy TT is abbreviated as π f. such that
(0:)= for the embedding 2,
[bm)) st). ; The policy, exclusively
s). Accordingly, the underlying initial distribution over 2g and the transition probability function for 2++1 given 8, and af are written as follows
T=(+|=e)= f (-12,-0) 2t =
Ma (=() = =((80)
II
x
(b,)
1 (40
180 ): Pa ( a=) = P( 8e, ax)
II
x 0.0 (2/41 (.)
(2)
Equation 2 holds due to the deterministic and bijective nature of fo. The reward function remains unchanged. The objective is to discover an optimal unified policy ni. which can maximize the expected discounted cumulative rewards.
Theorem 2.
Let ( P, μ) and ( denote the objective functions (expected re- turns) in SDMDP and LS LS-SDMDP, respectively. By Theorem | and Assumptions 7 it fol- lows that the values of the objective functions equal at their respective optimal policies, for- mally written as J(x", , P.,)) = -JTT, P2,Mks) Moreover, the value functions of SDMDP and
LS-SDMDP at their respective optimal policies satisfy the following relationship V .P P())) P= i (2(00) (0m))
E. (a ... ...... (0m (ho)
Proof. Please refer to Appendix C for a detailed proof of Theorem 2
Remark. Theorem 2 indicates that the optimal unified policy x* of SDMDP can be recovered given both the optimal unified policy xj. of LS-SDMDP and optimal basis policies (7 (U) n (n)*). Figure depiccs the LS-SDMDP framework.
4.3 Enatureof-Speecialize----e
Solver
For the practical implementation, we need to realize both the optimal basis policies and the mixture function to enable the policy reuse in the latent space. If we consider the embedding (bx:) (0 S i S m) generated by the optimal basis policy (+(b)* to encapsulate all layer-wise embeddings, the mixture function would effectively perform entire-model merging. However, disclosed in [55] 53 such entire-model merging leads to inferior OOD generalization. We therefore introduce the Mixture-of- Specialized- Expetss Solver (MoSES), which implements layer-wise and token-wise aggregation approach through three stages: 1) pretraining a shared backbone model; 2) fine-tuning specialized experts, and 3) dynamically aggregating experts.
Pretraining a shared backbone model. Since all the other basis VRP variants are derived from CVRP by adding different constraints, we pretrain the shared backhone model exclusively on CVRP instances and freeze its parameters throughout subsequent stages. Please note the backbone model indeed acts as the 0-th optimal basis policy (0))
Fine-tuning specialized experts. To obtain the optimal basis policy x (()) (i > 0), we employ the specialized LoRA expert that performs parameter-efficient fine-tuning on the frozen backbone model. Problem instances of any basis VRP variant (excluding CVRP) are OOD inputs the frozen

---

backbone model, leading to task- missligeed features in embeddings generated from the backbone model. We thus propose the Gated-LoRa method that uses dynamic gating mechanism with the trainable weights W'9 E IR to suppress these irrelevant features from the backbone. Specifically, for the i-th optimal basis policy ((0)* (i > 0), the forward pass through a frozen backbone linear layer with weights Wo augmented with trainable LoRA matrices B, and A, is computed as:
h yout = sigmoid (W*, " + B.A.h".
(3)
Dynamically aggregating experts. In this stage, we freeze both the backbone weights We and the LoRA weights B, in the unified policy. The adaptive gating function G(h"") = act (W**"))
with weights W E IR [2xd2 computes coefficients {a: Jo. where act(-) is the activation function. Let haut denote the output of the unknown optimal unified solver. The aggregation goal is to determine coefficients {a: satisfying the linear system Σi=o 0: o,W, = hout (where W; = A; for i 2 1). However, this linear system may not be solvable. We thus introduce the trainable LoRA weights BÂ to model the residual. The forward pass of linear layer in the unified policy is written as:
hou Wn +
Σ a, BAA"; (ail G(h²)) act(WCh")).
(4)
We propose three activation functions for the gating mechanism: 1) softmax(() enforces the convex combination; 2) norm -ottttssssssstttt Li-normalizes softplus(W hn" to prevent gradient vanishing; 3) sigmoid(-) expands the coefficient space by relaxing the unit-sum constraint. Additionally, we introduce three routing strategies: 1) Dense Routing activates all optimal basis policies 2) Variant- Aware Routing-/ selects Top-K optimal basis policies, where K is the number basis variants the current VRP variant. 3) Variant-Aware Routing-II selects optimal basis policies corresponding to basis variants present in the current VRP variant;
5 Experiments
In this Section, we empirically validate the superiority of MoSES through evaluations on 16 VRP variants with five constraints, supplemented by hyperparameter and ablation studies. All experiments are conducted on NVIDIA Tesla V100-32GB GPUs on and Intel(R) Xeon(R) Platinum 8255C CPU @ 2.50GHz. Please refer to Appendix B for more empirical results, hyperparameter and ablation studies, along with the analysis.
Baselines. Traditional Solvers: We benchmark against the open-source PR 71 solver built on HGS-CVRP (65, and the widely-used Google OR-Tools [57]. Both solvers process each instance on single CPU core with time limits of 10s for instances with 50 nodes; and 20s for instances with 100 nodes, while we parallelize their execution across 16 CPU cores for efficiency. Neural Solvers: We compare our method with state-of-the-aat unified neural solvers for multi-task VRPs. MTPOMO 42 extends POMO 35 and unifies VRP variants. MVMoE X introduces mixture- of-experts. RouteFinder 3 utilizes the mixed batch training to produce three models: RF-POMO (MTPOMO-based), RF-MoR (MVMoF-based) and RF-TE (modiled Transformer-based) CaDA [X] enhances model capacity through dual attention mechanism. Since CaDA lacks publicly available code, we implement it according to the original paper specifications. Our reproduction of CaDA achieves comparable performance to the reported results.
MoSES Architecture, To demonstrate the plug-and and-play versatility of MoSES, we implement upon both RF-TE and CaDA, denoted as MoSES(RF) and MoSES(CaDA) respectively. MoSES(RF) uses norm softplus(-) activation for its adaptive gating function G(-). while MoSES(CaDA) utilizes sigmoid(-) activation. Both adopt the dense routing strategy, and set LoRA rank as 32 for both frozen modules {BAA), and the trainable module BA.
Training and Evaluation. We consider two problem scales N (50, 100), and adopt the same training settings with prior works 3 38 for baseline models. We optimize MoSES using REIN- FORCE (69. The backbone model is first pretrained on randomly generated CVRP instances. Then, the LoRA adapter fine-tuning produces 4 specialized experts, each optimized for distinct VRP variant: OVRP, VRPB, VRPI., and VRPTW. Finally, the unified solver is trained on all VRP variants. All phases share the training hyperparameters. Each model undergoes 300 training epochs,
7

---

Table 1: Performance comparison of multi-task VRP solvers. The lower, the better (L).
Salver
N
100
100
Cup
Time
Cost
Gap
Cost
Cap
Time
Cost
Gap
HGS PyVRP
10.372
10:4m
15.628
PYVRP
16:031
25,423
20.8m
OR-Tool
10.572
1.907%
10.4m
4.1788%
20.8m
OR-TTol
16089
0.347%
10:4m
25.814
1,50655
30.8m
MIPUMO
10.518
1.408%
24
15,933
1,9869
56
MEROMO
15.419
2.358%6
2-
26.430
3.8635%
96
CNW
RE POMO
MVMoF
10.508
10.501
13315%
1.241%
25
31
15,908
15.655
18800%
1.6925
11s
RF POMO
MVMo
15.365
16.405
2.089%
2.3336
25
3x
26.335
26. 09.901
3,5705%
3.70396
11s
9
RF-MUE
10.499
1.228%
36
15,877
1,62498
11%
RF-MEE
16,390
2.23956
36
36.319
3,50553
11s
RE-TE
10.504
1.27695
26
15.857
1.507%
RF-TH
16.363
2.06995
26.234
3.177%
MuSESORF)
10.465
1.000%
15,808
MoSESSRF))
16.264
1.445%
2.822%
CGUN""
R0388
1.0225
25
158M
1.56%%
"CaUN""
16.297
18528
2.7:57%
MoSES/CADA)
10,622
0.873%
76
15,833
1,3549
24h
MoSES(CHDA)
16.262
1.435%
36.032
2.383%
DIGS PyVRP
6.507
10:4m
9.725
20.8m
JIGS PyVRP
10:387
10:4m
15,756
20.8m
OR-Took
6.553
01686/8
10.4m
9.505
2,752%
20.8m
OR-Tools
10.570
2.34566
40.4m
16.466
5,300%
20.8m
MIPOMO
6.718
3.211%
24
10,210
4,959/5
8-
MIROMO
10.775
1.7326
24
16.151
2.445%
8x
MVMoF
6,702
2.069%
3+
10.176
4,61555
11s
MVMoF
10.251
1.508%
36
16,079
2,117%
11s
RE POMO
6,698
2.506%
25
10.181
4.671%
RF POMO
10.751
1.525%
16.106
2.166%
8s
RI-MOE
6,697
10.129
4.238%
RF-MOE
10.737
1.38896
1,957%
RE-TE
2.605%
24
10.131
4.090%
RF-TR
10.748
1.499%
1.
MISFSURF)
6,32
1,99%
54
10.064
3.49%
MoSESURF)
10,004
1.009%
16,005
1,5325
CSDI
6,562
2.15015
25
10009
3,767%
10%
CaDN
10:722
122525
25
16,052
1.6625
10%
MoSES/CaDA)
6.629
1,857
76
10.054
3.679%
246
MoSES/CADAI
10.704
1.03%
76
16,024
1.65%%
246
PIGS-PyVRP
9.687
10:4m
14.377
20.8m
HGGS-PyRR
10.510
10:4m
16.926
20,8m
Tooks
9,802
1.159%
10.4m
14,933
3.8538
20.8m
OR OR-Tools
10.119
B.078%
10.4m
17,0127
0,583%
20,8tb
MIPOMO
10.085
3.564%
24
15.052
4.917%
MIPOMO
10:667
1.425%
24
17.421
2,8065
9%
MVMoE
10.005
3.268%
35
15,022
4.505%
MVMME
10.669
1.495%
17.416
2,874F6
12s
RE-POMO
4.46%
RT-POMO
10.677
2.725%
RR-M
9.980
3.014%
35
14,973
4.168%
MoE
10.673
1.533%5
12.387
2,6988
12s
9.97%
3,0004
RF-TE
16662
1:338
7.341%
MoSESARD
0.915
2.342%
51
14.884
3.548%
19h
MOSES/RD)
10613
0,939%
65
17.284
2.101%
21s
0.545
25
T4005
16.
"CSTTA"
10
77.85
5t
11.233
7 T.RRRR
15%
MoSES/CaDAA
9.904
2,225
76
14,901
3.60%%
236
MoSES/CADAI
106611
0.946%
85
17.317
1.702%
266
HGS. PYVRP
10.16
10.4m
14,779
20,8m
HUS-PyVRR PYRP
18,361
10.4m
29,1126
20,8m
OR Tools
10.351
1.390%
10.4m
15:426
4.338%
20.8m
OR Tools
18:423
0.332%
10.4m
29.830
2.770%
20.8m
MTPOMO
10672
15.712
6,253%
MIPOMO
18990
2.1
3.616%%
MVMoE
10.67
5.761%
MVMoE
18965
2.108%
1.612%
RE POMO
19,592
3.937%
25
15.628
5.690%
RO-POMO
18937
1.853%
30.794
3.278%
RE Mcl
10.575
3.767%
35
15.541
1.121%
10s
RI MoE
18956
1.958%
35
30, 10.800
3.5219
12s
RF-TE
RJ37K'
5.99R4
25
15552
RR-TE
185641
13777
25
3/.63
1.923%
MoSESIRF)
10.518
1.5%
64
15.409
4.38%%
20
MoSESSIF)
18846
1.370%
65
30.627
2.712%
27s
R.335
5.5799
25
1,713'
16""
"CLEE""
15.577
1331
30.510 "2
30.566
2,5/9/9
15"
MoSES(CaDA)
10.517
3,193%
76
15,478
4.705%
CaDDS
18855
1.425%
2.329%
266
HGS PyVRP
18:292
10.4m
29.067
20.8m
HGS PyPR
16.356
25.757
Km
OR-Took
18:366
0.383%
20.045
1.597%
OR-Tnok
16.441
1.899%
MIPUMO
18639
1,8768
24
30,435
3,27745
MIPUMO
16323
2.818%
36,891
4,3645
MVMoF
18640
1.584%
3+
50,418
3,2877%
MVMaF
16811
2.751%
4.271%
12%
RE POMO
18:601
1.669%
25
30,543
2.967%
96
RF POMO
16:250
2.38396
25
26.754
3.951%
9s
RR-McE
18617
1.760%6
34
30.339
2.947%
12%
RF-MEE
16.776
2.547%
36
26.775
3.9189%
12%
RE-TE
18.001
1.675%
25
30.340
2.6189%
9%
RF-TB
16.763
2.460%5
26
26,691
3.5575
9%
MoSFS/RF)
18,499
1.121%
64
30,148
2.3033
216
MoSES(RF)
16.657
1.11%%
36,620
3.320%
21s
CGUN
[8336
1.002
35
50113
2.24255
"CLLY"
76.641
2,38
"3
26.592
3.2009%
1.6"
MoSES(CaDA)
18.455
30,050
1.969%
MoSES/CUDAT
16.667
2.824%
PyVRP
10.335
PyVRP
OR-Tool
6.288
0.412%
10.4m
10.577
2.315%
20.8m
OR-Tools
6.927
0.386/
10.552
2,36358
20
MTPOMO
7,308
3.006%
25
10.878
5.224%
36
MIPOMO
2,122
30056%
25
10,883
5,272%
8s
MVMoF
7,000
2.745%
36
10.840
4.8995
116
MVMMF
7.0%
285006
3+
10.847
4.938%
11%
RF- ROMO
7,086
2.69%%
25
10,836
4.823%
8c
RF- POMO
7.087
2.695%
2s
10.837
4.835%
8s
RE-MOE
7,000
2.113
36
10,806
4.526%
11s
RF-MOE
7
2.635%
36
10,807
4.540%
11s
RI TÉ
7,071
2.477%
25
10.772
4.512%
RI TE
7.075
2.315%
10.779
4.268%
MuSES(RF)
10.733
38229
MoSES(RF)
7,940
2.014%
3.862%
CaDN
7,040
3.738%
CaDA
7042
3.732%
CaDES/CCDA)
7,834
1.944%
76
10.726
3.760%
24s
CoSES/CHDAL
7,036
1.964%
10.724
3.743%
HOS-PPVRP
11,688
10:4m
19.156
20.8m
HGS-PyNRP
11,669
10:4m
19.156
8m
OR Tools
11.681
0.106%
10.4m
19,305
0.767%
20.8m
OR Toois
11,682
0.109%
10.4m
19,303
0.757%
20.8m
MIPOMO
11,117
1.259%
3+
19.637
2.49455
9%
MTROMO
118114
1.231%
3+
19.635
2.454F
9%
MYMoE
RE-POMO
11,825
11.805
1.305%
1.15%
34
46
19,608
19.641
2.344%
2.516%
12%
10s.
1 MoE
MVMME
RF-POMO
11.804
11,119
1.148%
1.272%6
46
19,630
19,608
2.343%
2.5005%
13%
10s.
RE MoE
11,325
1.307%
19,607
2.334%
11,825
1.300%
2.327%
RA-TE
00064
T.14745
25
19333
7.0444
RF-TH
11:005
1.1.1%
'2
16:.31
1.044
MoSES/RE)
11.762
0.791
65
19.508
1.821%
MoSES(RF)
11.761
0.783%
19.509
1.829%
CaDA
11:771
0.565%
24
19.471
1,636%
CaDA
11:770
0.844
19.472
1.630%
11s
MoSES/CaDA)
11.761
0.781
8s
19,440
1.70%
256
MoSES/CHDAI
11.760
0.773
8s
19.441
1.45%
266
HGS-PyVRP
6.507
10:4m
9.734
20.8m
HUSS-PyVRP
10.510
10:4m
16.936
20.8m 8m
OR Tools
6,552
0.668%
10:4m
10.001
2.791%
20.8m
OR Tools
10.197
0.114%
10.4m
17,023
0.728%
20.8m
MIPOMO
6.719
5.129%
2+
10.214
5.0000
8
MTROMO
10.670
1.5034
2s
17.420
2.892%
9%
OVRR.
MVMoF
6,707
3.009%
34
10.184
4.69%%
MVMoE
10.71
1.111%
34
17.418
2.881%
12s.
REPOMI
REPOMO
10657
2.777%
5,666
10.141
4,253%
MoE
10.67
1.532%
12s
RA-TE
2:11.44
T6122
RETE
16.62
11:527
1,34%
MoSFS/RF)
6,34
1.917%
64
10,063
34635%
20.
MuSES(RF)
10,613
0.962%
64
17.281
2.001%
23s
"STTA" -
6.66
35
1
'6""
"CATEA"
16
70458
17:33
1.512/
16
MoSES(CaDAA
6,629
1.866%
76
10.051
3682%
246
MoSES/CaDA)
18.61
0.940%
8:
17.319
1.714%
266
each containing 100,000 VRP instances generated on the fly. Adam Optimizer is used with learning
rate of 3 x 10-1, 1, weight decay of 10-6, and batch size of 256. We decay the learning rate by a factor of 10 at epochs 270 and 295. During evaluation, each neural solver employs greedy multi-start
8

---

1,2
LoRA
195
LoRA
Oroon 3
Treem 32
GatedLoRA
1.00
GatedLoRA
1.79
Free 32
Gap(%)
Gapf%)
Gap(())
3.73
%
Gap
27-
1.40
02 w0..0005115
26
B
LoRA Rank
LoRA Rank
(a) RF-based
(b) CaDA-based
(c) N 50
(d) N 100
Figure 2: 2(a) 2(b) compare Gated-LoRA against standard LoRA with varying B (0, 1]. 2 2(d)
investigate the effect of LoRA ranks on the model performance.
rollouts with 8x augmentations, selecting the best one from the generated solutions per instance. We report average costs and optimality gaps over 1K test instances, and the total time taken for testing. Gaps are calculated w.r.t. the results of the best heuristic solver (i.e.. in Table
5.1 Empirical Results
We conduct comprehensive benchmarking across all 16 VRP variants, with complete results presented in Table MoSES(RF) consistently outperforms over its baseline RF-TE across all 16 VRP variants, achieving both lower solution costs and reduced optimality gaps for problem scales of N 50 and N = 100. In terms of average optimality gap over 16 VRP variants, RF-TE achieves 2.063%
and 3.5% for N = 50 and N 100, respectively, while MoSES(RF) demonstrates superior performance with gaps of 1.535% and 2.782%, indicating relative improvements of 25.6% and 1 11.0%. MoSES(CaDA) demonstrates consistent improvements over its baseline CaDA across all VRP variants at N = 50. For N = 100, it shows superiority on 13 out of 16 tasks while maintaining comparable performance on CVRP, OVRPB, and OVRPBL tasks, with marginal decreases of S 0.002 in costs and < 0.027% in optimality gaps. MoSES(CaDA) reduces average optimality gaps over 16 VRP tasks from 1.715% to 1.515% (11.7% relative improvement) N 50 and from 2.766% 2.631% (4.9% relative improvement) at N = 100, compared to its baseline CaDA. From the perspective of average optimality gap, MoSES(CaDA) is more preferred than MoSES(RF). In terms the average total time overhead over 16 tasks, MoSES(RF) requires 5.8s and 20.8s for N = 50 and N 100, respectively, compared to 2.0s and 8.4s consumed by RF-TE. MoSES(CaDA) requires 7.4s compared CaDA's 2.3s for N = 50, and 24.8s compared to CaDA's 10.5s for N = 100. Since this time overhead represents the total time for IK instances averaged over tasks, the amortized time per instance remains at the microsecond level for both MoSES(RF) and MoSES(CaDA). Thus, the slightly more computational time of our method, resulting from the layer-wise token- wise routing mechanisms and dynamic aggregation operations, is acceptable given the favorable empirical improvements over prior methods, and may not be a major concern in practical applications.
5.2 Hyperparameter Studies
We also evaluate the impact of LoRA ranks on model performance, using MoSES(CaDA) as case study across both N 50 and N = 100 problem scales. We allow the ranks for frozen modules [B and trainable module BÂ to differ, denoted as Ffrosen and F'ree respectively. Figures 2(d) present the impact of LoRA ranks on the average optimality gap over 16 VRPs, where blue curves fix Trrozen 32 while varying /'ree from 4 to 32, and green curves fix Tiree 32 while varying frrozen from 4 to 32. Figure reveals that reducing the LoRA rank of trainable module BA with fixed Firozen 32 incurs smaller performance degradation than reducing the LoRA rank of frozen modules ( [B.A), Jim with fixed F'ree = 32, suggests that the frozen LoRA experts contribute more significantly to MoSES(CaDA) than the trainable LoRA expert at N 50. F(d) demonstrates an inverse relationship at the scale of = 100 that the trainable
2.0
1:54g
15-
Can/oo
1.0
0.0
Mescspary Scffmar
MosEsi (X)
horo soppler sigmold
norm. softaln sigmold
sofimar
Figure 3: Activations.
LoRA expert contributes more significantly MoSES(CaDA) than the frozen LoRA experts.

---

Before delving into the in-depth analysis of Figure 2 2(d) we first clarify the respective roles of the gating function and the trainable LoRA expert in MoSES. The gating function is primarily designed to extract individual insights from basis VRP solvers by identifying which solvers offer the most relevant experience for a given problem instance. In contrast, the trainable LoRA expert is intended to capture holistic understanding of the given VRP variant, which naturally includes correlations among the basis VRP variants. From Figure 2(c) we observe that for smaller problem instances (N = 50), reducing the LoRA rank of the frozen LoRA experts leads to more significant performance drop than reducing the LoRA rank of the trainable LoRA expert. This suggests that for simpler problems, the basis solvers already contain sufficient useful insights, and the unified solver relies less on the holistic understanding provided by the trainable LoRA expert. Conversely, Figure 2(d) shows that for larger problem instances (NV 100), reducing the LoRA rank of the trainable LoRA expert results in a greater performance drop than reducing that of the frozen experts. This indicates that for more complex problems, the unified solver requires deeper and more holistic understanding of the VRP variant, which the trainable LoRA expert is better suited to provide.
5.3
Ablation Studies
We evaluate our proposed Gated- LoRA against standard LoRA that varies B3 from 0.1 to 1.0, both used in the phase of fine-tuning spe- cialized experts. Figures ((a) [bb demonstrate Gated-LoRA's con- sistent superiority by showing lower average optimality gaps over four basis variants (OVRP, VRPB, VRPL, VRPTW) at N = 50 for both RF-based and CaDA-based backbones. Figure 3 uncovers that MoSES(RF) prefers norm_so softplus(()) as the activation function in the gating mechanism, while MoSES(CaDA)) prefers sigmoid (-). CaDA-based basis solvers may exhibit stronger generalization ca- pability than Ra-ba ones, owing to the two parallel Transformer blocks in each layer. Consequently, MoSES(CaDA), which uses sigmoid(-) as its activation function, tends to prioritize relevant solvers while assigning moderately higher scores to less relevant ones. This behavior suggests that MoSES(CaDA) recognizes that even task-irrelevant solvers can contribute useful insights for solving the current VRP variant. Figure shows that dense routing method achieves best both MoSES(RF) and MoSES(CaDA), and significant performance degrada- tion occurs when the trainable LoRA module B A is ablated. The dense routing strategy in the gating mechanism does not hinder interpretability, as evidenced by Figure 13 of the Appendix B Figure 13 presents behavioral analysis of the gating functions used in our models across 16 VRP variants. In this figure, plot the scores assigned by the gating function to each basis solver. It is clear that for given VRP variant, the gating mechanism tends to assign higher scores to basis solvers associated with the corresponding underlying basis VRPs. The reason the gating function does not completely zero out the remaining tasks is that many VRP variants are inherently correlated and solving instances of one task may benefit from insights learned from others. Since our method reuses only the basis VRP solvers, the number of solvers increases linearly, which is more manageable compared to the exponential growth in neural solver.
Gan/9
frocttg Mpp SE SIRRI
Prone Fousted MogEsiCaDn
wove Mesting
thutes Mustoo
Figure 4: Routing Methods.
6 Conclusions and Limitations
In this paper, our objective is to design a unified neural solver which is capable of handling multiple VRP variants simultancously. To achieve this, we propose the State-Decomposable MDP (SDMDP) to reformulate multi-task VRPs, grounded in observation that each VRP variant derives from a shared set of basis VRP variants. Then, the LS-SDMDP extension is developed to reuse basis neural solvers, each specialized for a basis VRP, in the latent space. We finally implement mixture-off-Lole -expeerrrtss as the unified solver. While our method demonstrates empirical superiority over prior approaches, it incurs mild computational overhead compared to other neural solvers due to its finer merrggranned layer-wise and toien-wise aggregation and adaptive routing mechanisms. This limitation suggests designing more efficient aggregation techniques which preserve decent performance as future research directions. In addition, extending this framework to broader and general decision- decision-making settings also appealing.
10

---

Acknowledgments and Disclosure of Funding
This research supported by generous research grant from Xiaoi Robot Technology Limited, and the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier grant. We appreciate the anonymous reviewers, (S)ACs, and PCs of NeurlPS 2025 for their insightful comments to further improve our paper and their service to the community.
References
[1] Samuel Ainsworth, Jonathan Hayase, and Siddhartha Srinivasa. Git re-basin: modulo permutation symmetries. In The Eleventh International Conference Learning Representations, 2023.
Merging models
[2] Ahmad Bdeir, Jonas K Falkner, and Lars Schmidt-Thieme. Attention, filling in the gaps for generalization in routing problems. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 505-520. Springer, 2022.
[3] Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Leon Lan, Kevin Tiemey. and Jinkyoo Park. Routefinder: Towards foundation models for vehicle routing problems. In ICML 2024 Workshop on Foundation Models in the Wild, 2024.
[4] Jieyi Bi, Yining Ma, Jiahai Wang. Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. Advances in Neural Information Processing Systems, 11311226311233 2022.
[5] Lucas Caccia, Edoardo Ponti, Zhan Su, Matheus Pereira, Nicolas Le Roux, and Alessandro Sordoni. Multi-head adapter routing for cross-task generalization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[6] Diego Cattaruzza, Nabil Absi, Dominique Feillet, and Jesús González-Feliu Vehicle routing problems for city logistics. EURO Journal Transportation and Logistics, 6(1):51-79, 2017.
[7] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in neural information processing systems, 32, 2019.
[8] Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learning to solve large-scale tsp instances. In International Conference on Artificial Intelligence and Statistics, pages 1219-1231. PMLR, 2023.
[9] Alexandra Chronopoulou, Matthew Peters, Alexander Fraser, and Jesse Dodge. Adaptersoup: Weight averaging to improve generalization of pretrained language models, 2023.
[10] Alexandra Chronopoulou, Jonas Pfeiffer, Joshua Maynez, Xinyi Wang, Sebastian Ruder, and Priyanka Agrawal. Language and task arithmetic with parameter-efficieet layers for zero- shot summarization. In Jonne Sälevä and Abraham Owodunni, editors, Proceedings of the Fourth Workshop on Multilingual Representation Learning (MRL 2024), pages 114-126, Miami, Florida, USA, November 2024. Association for Computational Linguistics.
[11] Arthur Corrêa, Cristóvão Silva, Liming Xu, Alexandra Brintrup, and Samuel Moniz. Tunensearch: hybrid transfer learning and local search approach for solving vehicle routing problems. arXiv preprint a5X3v:2503. /2662, 2025.
[12] Nico Daheim, Thomas Möllenhoff, Edoardo Ponti, Iryna Gurevych, and Mohammad Emtiyaz Khan. Model merging by uncertainty- based gradient matching. In The Twelfth International Conference Learning Representations, 2024.
[13] Shihan Dou, Enyu Zhou, Yan Liu, Songyang Gao, Wei Shen, Limao Xiong, Yuhao Zhou, Xiao Wang, Zhiheng Xi, Xiaoran Fan, Shiliang Pu, Jiang Zhu, Rui Zheng, Tao Gui, Qi Zhang, and Xuanjing Huang. LoRAMoE: Alleviating world knowledge forgetting in large language models via MoE-style plugin. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pages 1932-1945, Bangkok, Thailand, August 2024. Association for Computational Linguistics.
11

---

[14] Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. Goal: A generalist combinatorial opti- mization agent learner. In The Thirteenth International Conference on Learning Representations. 2024.
[15] Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024.
[16] Zhang-Hur Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 7482, 2021.
[17] Chengrui Gao, Haopu Shang, Ke Xue, Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In The 33rd International Joint Conference on Artificial Intelligence (IJCAI-24). 2024.
[18] Chongyang Gao, Kezhen Chen, Jinmeng Rao, Baochen Sun, Ruibo Liu, Daiyi Peng, Yawen Zhang, Xiaoyuan Guo, Jie Yang, and VS Subrahmanian. Higher layers need more lora experts, 2024.
[19] Thierry Garaix, Christian Artigues, Dominique Feillet, and Didier Josselin. Vehicle routing problems with alternative paths: An application to on-demand transportation. European Journal of Operational Research, 204(1):62 75, 2010.
[20] Yong Liang Goh, Yining Ma, Jianan Zhou, Zhiguang Cao, Mohammed Haroon Dupty, and Wee Sun Lee. SHIELD: Multi-task multi-distribution vehicle routing solver with sparsity and hierarchy. In Forty-second International Conference on Machine Learning, 2025.
[21] Yunhao Gou, Zhili Liu, Kai Chen, Lanqing Hong, Hang Xu, Aoxue Li, Dit- Yan Yeung, James T Kwok, and Yu Zhang. Mixture of cluster-conditions lora experts for vision- saiion-a instruction tuning. arXiv preprint arXiv:2312. 12379, 2023.
[22] Nathan Grinsztajn, Daniel Furelos- Blanno, Shikha Surana, Clément Bonnet, and Tom Barrett. Winner takes it all: Training performant rl populations for combinatorial optimization. Advances in Neural Information Processing Systems, 36:48485-48509, 2023.
[23] Keld Helsgaun. An extension of the lin-kemighann-helsaan tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966-980, 2017.
[24] André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. In ECA/ 2020, pages 443-450. IOS Press, 2020.
[25] Qingchun Hou, Jingwei Yang. Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics solve large-scale vehicle routing problems in real-time. In The Eleventh International Conference on Learning Representations, 2023.
[26] Edward Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
[27] Chengsong Huang, Qian Liu, Bill Yuchen Lin, Tianyu Pang, Chao Du, and Min Lin. Lorahub: Efficient cross-tast task generalization via dynamic loRA composition. In First Conference on Language Modeling. 2024.
[28] Gabriel Ilharco, Mareo Tulio Ribeiro, Mitchell Wortsman, Ludwig Schmidt, Hannaneh Ha- jishirzi, and Ali Farhadi. Editing models with task arithmetic. In The Eleventh International Conference on Learning Representations, 2023.
[29] Xia Jiang, Yaoxin Wu, Yuan Wang, and Yingqian Zhang. Unco: Towards unifying neural combinatorial optimization through large language model. arXiv preprint arXiv:2408.12214 2024.
[30] Yuan Jiang, Zhiguang Cao, Yaoxin Wu, Wen Song, and Jie Zhang. Ensemble-based deep reinforcement learning for vehicle routing problems under distribution shift. Advances in Neural Information Processing Systems, 36, 2024.
12

---

[31] Xisen Jin, Xiang Ren, Daniel Preotiuc-Pietry and Pengxiang Cheng. Dataless knowledge fusion by merging weights of language models. The Eleventh International Conference on Learning Representations, 2023.
[32] Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34:10418-10430, 2021.
[33] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. Advances in Neural Information Processing Systems, 35:1936 1949, 2022.
[34] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations, 2019.
[35] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21188 19-1188-22198 2020.
[36] Gilbert Laporte and Yves Nobert. A branch and bound algorithm for the capacitated vehicle 5:77-85, 1983.
routing problem. Eperruions-Rexxurrb-SSSeeeee
[37] Haoyu Lei, Kaiwen Zhou, Yinchuan Li. Zhitang Chen, and Farzan Farnia. Boosting generaliza- tion in diffusion-banr based neural combinatorial solver via mnergy-guidedd sampling. arXiv preprint arXiv:25022 /288 2025.
[38] Han Li, Fei Liu, Zhi Zheng, Yu Zhang, and Zhenkun Wang. Cada: Cross-problem routing solver with constraint-aware dual-attention. arXiv preprint arXiv:2412.00346, 2024.
[39] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Advances Neural Information Processing Systems, 34:26198-266 2021.
[40] Yang Li, Jiaxi Liu, Qitian Wu, Xiaohan Qin, and Junchi Yan. Toward learning generalized cross-problem solving strategies for combinatorial optimization, 2025.
[41] Zhuoyi Lin, Yaoxin Wu, Bangjian Zhou, Zhiguang Cao, Wen Song, Yingqian Zhang, and Senthilnath Jayavelu. Cross-problem learning for solving vehicle routing problems. In Pro- ceedings of the Thirty-Thine International Joint Conference on Artificial Intelligence, pages 6958 6966, 2024.
[42] Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Tong Xialiang, and Mingxuan Yuan. 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, pages 1898-1908, 2024.
[43] Suyu Liu, Zhiguang Cao, Shanshan Feng, and Yew-Soon Ong. A mixed-curvature based pre-training paradigm for multi-task vehicle routing solver. In Forty-second International Conference Machine Learning, 2025.
[44] Zefang Liu and Jiahua Luo. AdamoLE: Fine-tuning large language models with adaptive mixture of low-rank adaptation experts. In First Conference on Language Modeling, 2024.
[45] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International conference on learning representations, 2019.
[46] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36, 2024.
[47] Fu Luo, Xi Lin, Yaoxin Wu, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Boosting neural combinatorial optimization for large-scale vehicle routing problems. In The Thirteenth International Conference on Learning Representations, 2025.
13

---

[48] Xingtai Lv, Ning Ding, Yujia Qin, Zhiyuan Liu, and Maosong Sun. Parameter-efficieet weight ensembling facilitates task-level knowledge transfer. In Anna Rogers, Jordan Boyd-Graber and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 270-282, Toronto, Canada, July 2023. Association for Computational Linguistics.
[49] Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In Advances Neural Information Processing Systems, volume 36, 2023.
[50] Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual dual-aspect aspect collaborative transformer. In Advances in Neural Information Processing Systems, volume 34, pages (1096-1117,, 2021.
[51] Sahil Manchanda, Sofia Michel, Darko Drakulic, and Jean-Mare Andreoli. On the generalization of neural combinatorial optimization heuristies. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 426-442. Springer, 2022.
[52] Michael Matena and Colin Raffel. Merging models with fishhr- averaging, In Proceed- ings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2022. Curran Associates Inc.
[53] Mohammed Muqeeth, Haokun Liu, Yufan Liu, and Colin Raffel. Learning to route among specialized experts for zero-shot generalization. In International Conference on Machine Learning, pages 36829-36846. PMLR, 2024.
[54] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
[55] Oleksiy Ostapenko, Zhan Su, Edoardo Ponti, Laurent Charlin, Nicolas Le Roux, Lucas Caccia, and Alessandro Sordoni. Towards modular Iims by building and reusing library of loras. In International Conference on Machine Learning, pages 38835-38904. PMLR, 2024.
[56] Yuxin Pan, Ruohong Liu, Yize Chen, Cao Zhiguang, and Fangzhen Lin, Hierarchical learning- based graph partition for large-scal scale vehicle routing problems. In The 24th International Conference on Autonomous Agents and Multi-Agen Systems, 2025.
[57] Laurent Perron and Vincent Furnon. OR-Tools. Google, 2023.
[58] Jonas Pfeiffer, Aishwarya Kamath, Andreas Rücklé, Kyunghyun Cho, and Iryna Gurevych. AdapterFusion: Non-destructive task composition for transfer learning. In Paola Merlo, Jorg Tiedemann, and Reut Tsarfaty, editors, Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pages 487-503, Online, April 2021. Association for Computational Linguistics.
[59] Edoardo Maria Ponti, Alessandro Sordoni, Yoshua Bengio, and Siva Reddy. Combining parameter-efficient modules for task-level generalisation. In Andreas Vlachos and Isabelle Augenstein, editors, Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguisties, pages 687-702, Dubrovnik, Croatia, May 2023. Association for Computational Linguistics.
[60] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances in Neural Information Processing Systems, volume 35, 2022.
[61] Alexandre Ramé, Kartik Ahuja, Jianyu Zhang, Matthieu Cord, Léon Bottou, and David Lopez- Paz. Model ratatouille: recycling diverse models for out-of-distribution generalization. In Proceedings of the 40th International Conference on Machine Learning, ICMI'23. JML..org, 2023.
14

---

[62] Stefan Ropke and David Pisinger. A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171(3):55--73 2006. Feature Cluster: Heuristic and Stochastic Methods in Optimization Feature Cluster: New Opportunities for Operations Research.
[63] George Stoica, Daniel Bolya, Jakob Brandt Bjorner, Pratik Ramesh, Taylor Hearn, and Judy Hoffman. Zipit! merging models from different tasks without training. In The Twelfth International Conference on Learning Representations, 2024.
[64] Derek Tam, Mohit Bansal, and Colin Raffel. Merging by matching models in task parameter subspaces. Transactions on Machine Learning Research, 2024.
[65] Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neighborhood. Computers Operations Research, 140:105643, 2022.
[66] Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):61 1-244, 2012.
[67] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[68] Chenguang Wang, Zhang- Hua Fu, Pinyan Lu, and Tianshu Yu. Efficient training of multi-task neural solver for combinatorial optimization. Transactions on Machine Learning Research, 2025.
[69] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8:229-256. 1992.
[70] Mitchell Wortsman, Gabriel Ilharco, Samir Ya Gadre, Rebecca Roelofs, Raphael Gontijo- Lopes, Ari S Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Kornblith, and Ludwig Schmidt. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 23965-23998 23998. PMLR, 17-23 Jul 2022.
[71] Niels A. Wouda, Leon Lan, and Wouter Kool. PyVRP: a -eeeforeffom VRP solver package. INFORMS Journal on Computing. 36(4):943 955. 2024.
[72] Chengyue Wu, Teng Wang. Yixiao Ge, Zeyu Lu, Ruisong Zhou, Ying Shan, and Ping Luo. r--tnnin: Transferring multimodal foundation models with optimal multi-task interpolation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 37713-37727. PMLR, 23-29 Jul 2023.
[73] Xun Wu, Shaohan Huang, and Furu Wei. Mixture of loRA experts. In The Twelfth International Conference on Learning Representations, 2024.
[74] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with mn-kemiighan-helgaau heuristic for solving the traveling salesman problem. In Advances in Neural Information Processing Systems, volume 34, 2021.
[75] Prateek Yadav, Derek Tam, Leshem Choshen, Colin Raffel, and Mohit Bansal. TIES-merging Resolving interference when merging models. In Thirty-sevemth Conference on Neural Informa- tion Processing Systems, 2023.
[76] Enneng Yang, Zhenyi Wang, Li Shen, Shiwei Liu, Guibing Guo, Xingwei Wang, and Dacheng Tao. Adamerging: Adaptive model merging for multi-task learning. The Twelfth International Conference Learning Representations, 2024.
15

---

[77] Haoran Ye, Jiarui Wang. Helan Liang, Zhiguang Cao. Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceediggs of the AAAI Conference on Artificial Intelligence, volume 38, pages 20284-20292, 2024.
[78] Qinyuan Ye, Juan Zha, and Xiang Ren. Eliciting and understanding cross-task skills with task-level mixture-of-erxeee of-experts. In Yoav Goldberg. Zornitsa Kozareva, and Yue Zhang. editors, Findings of the Association for Computational Linguistics: EMNLP 2022, pages 2567-2592. Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
[79] Ted Zadouri, Ahmet Üstün, Arash Ahmadian, Beyza Ermis, Acyr Locatelli, and Sara Hooker. Pushing mixture of experts to the limit: Extremely parameter efficient moe for instruction tuning. In The Twelfth International Conference on Learning Representations, 2024.
[80] Cong Zhang, Yaoxin Wu, Yining Ma, Wen Song. Zhang Le, Zhiguang Cao, and Jie Zhang. A review on learning to solve combinatorial optimisation problems in manufacturing, IET Collaborative Intelligent Manufacturing, :( 1072, 2023.
[81] Jinghan Zhang, Shiqi Chen, Junteng Liu, and Junxian He. Composing parameter-efficient modules with arithmetic operations. In Advances in Neural Information Processing Systems, 2023.
[82] Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. UDC: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems. In The eiihth- Annual Conference on Neural Information Processing Systems, 2024.
[83] Jianan Zhou, Zhiguang Cao. Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. Mvmoe: multi-task vehicle routing solver with mixture-of-expper In Proceedings of the 41st International Conference on Machine Learning, pages 61804 61824, 2024.
[84] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni- onni-generalizable neural methods for vehicle routing problems. In International Conference Machine Learning, pages 42769-427877 PMLR, 2023.
[85] Zefang Zong, Hansen Wang, Jingwei Wang. Meng Zheng, and Yong Li. Rbg: Hierarchically solving large-scale routing problems in logistic systems via reinforcement learning. In Proceed- ings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4648 4658, 2022.
16

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We present our key contributions and scope in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this work are discussed in Section 6.
17

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faireess
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions are stated in the main text, with full proofs of theorems provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We present adequate information in both the main text and Appendix for the reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The implementation code is included in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. /ttppp.cc/pblic/guideeee http://oeeesmmiiioooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
19

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Experimental details are presented in both the main text and Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification; Error bars derived from multiple experimental runs do not represent the primary evaluation metric in neural solver research.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-simma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report computational resources in the main text.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
20

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https///wwuurrsscccppppccccccact
Answer: [Yes]
Justification: Our research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: By focusing on practical VRP applications, our work delivers more positive real-world impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses such risks.
Guidelines:
21

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We properly cite the original paper that produced the code package or dataset.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We include the implementation code the supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
22

---

Justification:
Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in our research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our L.M policy http:://eerrrppcccooooooaaarrr// for what should or should be described.
23

---

A Environment Details
A.1 VRP Variants
We adopt the same environment configurations for Vehicle Routing Problems (VRPs) as those described in RouteFinder [3]. In this setting, all VRP variants extend the Capacitated VRP (CVRP)
by incorporating arbitrary combinations of the following four constraints: 1) Open Route (O): A binary variable o indicates whether the vehicle needs to return to depot (o = 0) or not (o 1); 2) Backhaul (B): Customers {U,} are categorized into linehauls with of > 0 or backhauls with
qf < O, where linchauls require deliveries and backhauls require pickups. These are mutually exclusive: of q = 0 for all j E {I...., N}. VRPs with backhaul allow traversing both types in a mixed manner, but linehauls must precede backhauls each subtour [62]. VRPs without backhaul, only linehaul customers are present; 3) Duration Limit (L.: The cost of each subtour within a solution cannot exceed a threshold [dur; 4) Time Window (TW): Each node v; (i (O...., NJ) is associated with a time window [w, beg wufu] and a service duration w requiring that service must begin within the specified window. The vehicle arriving prior to w; w.ee must wait until the window opens, after which the node is occupied for exactly whtr time units. Furthermore, all vehicles are constrained to return to the depot no later than w6nd. CVRP serves as basis VRP variant, from which the remaining four basis VRP variants emerge by individually incorporating one additional constraint: CVRP with open routes (OVRP), CVRP with Backhauls (VRPB), CVRP with Duration Limits (VRPL), and CVRP with Time Windows (VRPTW). The complete combinatorial space of these four constraints results in 16 VRP variants (2 possible combinations): CVRP, OVRP, VRPB, VRPL, VRPTW, OVRPTW, VRPBL, VRPBLTW, VRPBTW, VRPLTW, OVRPB, OVRPBL, OVRPBLTW, OVRPBTW, OVRPL, OVRPLTW.
A.2 Problem Instance Generation
In this section, we present the procedures for creating the problem instances of various VRP variants for both the training and testing phases. As each VRP variant stems from a common set of attributes, we proceed to outline the generation process for each attribute directly.
Locations. In each problem instance, N coordinates are uniformly sampled from a unit square. denoted as { vo). (11, y1),.... (IN, }N)). where 24, ~ (0, 1) for i = O,...,N. (To, yo) represent the depot coordinates, while ((1;, ) denote the coordinates of the customers.
Vehicle Capacity. The vehicle capacity Q remains constant for all vehicles within each problem instance and is calculated follows:
30
1000
1-000 33.3
if N 1000
5
Q
30
+
5
if 20 < N S 1000 otherwise
(5)
30
Linehaul and Backhaul Demands. For the depot node up both linehaul and backhaul demands are set to zero. For each customer Ui (j 2 1), the linehaul demand of is drawn uniformly at random from the integer set (1,2,...,9) .9. while the backhaul demand J. is sampled uniformly from 21..-2....
9}. A binary decision variable d E {0. 1} is then introduced, with probabilities P(á, = 0) 0.8 and P(g, = 1) 0.2. If O O. the customer is designated as linehaul, retaining the customer is treated as backhaul, preserving o, BH and setting g..tt = 0. It is important to note that both linehaul and backhaul demands are present only in VRP variants that incorporate backhauls. In all other VRP variants, only linehaul demands are considered.
the sampled value of I. while setting 9, BH = O. Conversely, a
Open Routes. A binary variable {0, 1} is introduced to indicate whether the vehicle is required to return to the depot. The proportion of VRP instances with open routes is governed by the probability P(o 1), where 1 signifies that the open route constraint is active.
Time Windows. For the depot node vo. the time window is defined as [wber gnd]] where wh and and represents the system's end time. The service duration at the depot, denoted by wglu is set
beg 0
24

---

to zero. For each customer U2 (i E f1...., NY, whth require to be generated. The service duration w is sampled uniformly from the interval [2]. The length of the time window, defined as w wind wy beg is drawn uniformly from the interval [4z Is]- Let Dist( (v, 2/) denote the distance between the depot zhp and customer v/. The upper bound with for the start time of the time window is computed as:
time window [w wind] and a service duration
W
wond w
dur w
W
1.
(6)
Dist Co. v.)
The start time the time window is then determined by:
beg (1 (w? UB 1) u.) Dist e:);
where (O, 1) is uniformly distributed random variable. Finally, the end time of the time window given by:
beg and = W; + wi
Jen
(8)
Additionally, if the time window constraint is not active in given problem instance, for all nodes (i 2 0), the start time beg is set to zero, the end time windd is set to and the service duration w is set to zero.
Distance Limit. The distance limit pdur is sampled from the uniform distribution U max; (Dist((o) u;)), mdxx), where ydur predefined upper bound. This sampling strategy en- sures that every customer node is reachable from the depot. If the distance limit constraint is not enforced, the distance limit ydur is set to oc.
A.3 Feasible Action Space
To derive the feasible action space in the environment, need action mask based on the combined constraints of basis VRP variants. In each time step, we use the following feasibility testing procedures to mask out infeasible actions from the action space. Please note that the vehicle speed is fixed at 1.0, and the time windows are normalized accordingly. As a result, the travel time between any two nodes is numerically equivalent to the Euclidean distance between them.
1) Each eustomer needs be visited exactly once. the vehicle is currently located at the depot and there are still unserved customers, selecting the depot as the next action is not permitted.
2) The vehicle must arrive node 1y from node v; before the end of the service time window: wt (is Uz) S ue7"d where wt is the current time.
3) The cost of subtour, when traveling from node v to node Vy, must not exceed the predefined distance limit: 25ur + (ist U2)= E Idue, where zeue denotes the cumulative distance traveled along
the current subtour.
If the vehicle is required return to the depot and intends to visit node vy from its current location ue it must satisfy both time and distance feasibility conditions: the vehicle must be able to complete the visit and return to the depot before the system's 's end time: max maxxww?" + Dist U2); wy
heg +
Dist to, ui) < wgnd and the total length of the resulting subtour, including travel from 0/ to uy and from By back the depot, must not exceed the distance limit: yeur +Ditt x +Ditt(u. 0y) < pdur
5) If the vehicle intends to visit linehaul customer uj. the corresponding linehaul demand of must not exceed the remaining linchaul capacity Q! Similarly, if the vehicle intends to visit backhaul customer ey. the backhaul demand 93 must not exceed the remaining backhaul capacity
Bif
Q.H Additionally, all linehaul customers must be visited before any backhaul customers within each subtour.
A.4 VRP Formulation
To illustrate the VRP formulation within the SDMDP framework, provide an example for clarification. Under the SDMDP framework, there are five types of basis state spaces: ('")....., Specifically, (0)) encodes node coordinates, linchaul demands, and remaining linchaul capacity, S(1)
25

---

Table 2: Performance comparison of multi-task VRP solvers on OOD CVRP instances.
Vehicle Capacity
30
S0,ID)
110
130
130
200
Cost
Time
Cost
Time
Cost
Time
Cost
Time
Cost
Time
Cost
Time
Cast
Time
Cost
Time
MTROMO
23.455
94
15.933
13.144
86.
11.684
56.
10.835
5x
10.359
8+
10.027
8s
9.566
84
MVMoE
23.162
12s
15.888
11s
13.068
11s
11.534
11s
10.616
11s
10.089
13s
9.727
11s
9.203
11s
RF-MoE
23.251
12s
15,877
11s
13,000
11s
11.580
11s
10.85
11s
10.170
13s
9,802
11s
9.294
11s
RF-POMO
23.220
9+
15,908
13,104
8x
11:607
8x
10.715
8x
10.200
8c
9.846
9.362
84
RF TE
23.085
13.8557
B5"
13.023
9."
11.468
56"
70.51
56'"
-- 8."
"92522"
"5"
"65
RF
23,058
158826
12.999
1L.855
20s
9,550
8.968
20s
M
23,05
15.808
20s
10.107
22,089
21s
13,009
19%
10,49
19%
19%
9,550
CaURY
71.138
10.499
23/066
15884
13.015
454
25%
10.513
25%
9,950
9.502
McSES CaDA lanp
23,031
276
15.835
26s
13,005
264
11.441
25%
10,82
25%
9.906
25
9,537
25:
3,960
25c
MoSES MoSES/CalAN Cal3N)iie
23.044
256
15.835
24s
12.999
246
11.437
246
10.473
246
9.897
256
9.526
25s
8,937
256
represents a binary variable indicating whether the vehicle needs to return to the depot; S(2) captures backhaul demands and remaining backhaul capacity; S(3) includes the duration limit and the current traveled length of the subtour; and ( contains time windows, service times, and the current time. Before each episode begins, the initial state space is constructed by selecting S(0) and any subset of the remaining basis states. this example, we choose S S(3) and S(1), which correspond to the VRP with limited duration and time windows (VRPLTW). At each time step, the policy observes the basis states s(0) 5(3), and s(4), and masking mechanism is applied to filter out infeasible nodes from the set of unvisited nodes, specifically, those whose demands exceed the remaining linehaul capacity, those that would violate the duration limit, and those whose arrival time would exceed the end of their time window, from unvisited nodes. This results in a list of feasible nodes from which the next node is selected. Upon selection, the linehaul capacity, traveled length, and current time are updated accordingly, and the selected node is masked out for subsequent steps. Once a subtour completed, the linehaul capacity is reset to its default value, the traveled length is reset to zero, and the current time is also reset to zero. This reset reflects the assumption in VRP that multiple vehicles can begin their routes concurrently.
B Experiments
B.1 Out-of-distribution Attribute Generalization
In this section, we evaluate the oft-o--distribution (OOD) generalization capabilities of our proposed methods, MoSES(RF) and MoSES(CaDA)), in comparison with existing unified multi-task neural solvers. The evaluation specifically targets generalization to unseen attribute values pertaining to vehicle capacities, time windows, and distance limits. For each evaluation setting, we construct testing dataset consisting of 1,000 problem instances, each with N = 100 nodes. Performance is measured using two metrics: the average cost across the 1,000 problem instances, and the total computational time required to solve all instances, with lower values indicating better performance. Notably, all neural solvers evaluated were trained on problem instances with the same number of nodes (i.e., N 100).
In CVRP, each neural solver is trained on problem instances with a fixed vehicle capacity of Q == 50. To investigate OOD generalization to unseen vehicle capacities, we generate a separate testing dataset for each capacity value in the set (30, 50, 70, 90, 110, 130, 150, 200). The corresponding results are presented in Table Please note that Q = 50 corresponds to the in-distribution (ID) evaluation setting. Both MoSES(RF) and MoSES(CaDA) adopt the dense routing strategy. We use Sftm, Sftp and Sigm to denote the activation functions softanax()). norm_ssooo porm_sof(plus()) and sigmoid(.), respectively. For MoSES(RF), we observe MOSES F)mmm consistently outperforms its baseline, RF-TE, in terms of generalization performance OOD vehicle capacities. However, MoSES(RF)stt) demonstrates superior performance on small-scale problem instances (NV < 90), compared to MoSES sttm MoSES(CaDA) demonstrates stronger OOD generalization than its baseline, CaDA, across all evaluation settings, with the exception of a marginal performance drop observed in the ID case at Q 50. Furthermore, MoSES(CaDA) outperforms MoSES(RF)sHn. across the majority of evaluation scenarios.
In VRPL, the predefined upper bound on the distance limit, denoted as Jdur is set to 2.8 (ap- proximately 2v2) during training. which serves as the ID evaluation setting. To examine 0OD
26

---

Table 3: Performance comparison of multi-task VRP solvers on OOD VRPL instances.
Distrnne Limit
2.7
2.8:ID)
3.0
3.1
3.2
3.3
3,4
Cost
Titte
Cost
Time
Clss
Time
Cost
Time
Cost
Time
Coot
Timee
Cost
Time
Cast
Time
MTPOМO
16, 193
9x
16.151
94
16.121
9%
16.
9%
16.090
94
16.078
9%
16,069
94.
16,050
94
MVMoE
16.142
12s
16,099
12x
15.073
12:
16.054
12s
16,040
12x
16.030
12s
16.017
12s
16,010
12x
RE-MoE
100
16,070
16.017
16.005
12s
15.997
15.991
POMO
16.029
95
RE-TE
16.091
9:
16.051
9,
16,029
16.012
15.997
9.
15.987
%
15.975
9,
15,959
9.
CalA
16,077
10s
16.026
10c
16,002
10s
15.993
10s
15.971
10s
15,900
10s
15.952
10s
15:946
10s
(RSFS(RF))
16,045
216
16,005
214
15.982
216
15.966
216
15,052
214
15,940
216
15.92H
21s
15.923
214
(oSES(CaRA)
15,000
25s
16,024
25s
16,002
25%
15 984
25s
15,971
25c
15.961
25k
15.947
25s
15.942
25g
Table 4: Performance comparison of multi-task VRP solvers on OOD VRPTW instances.
Time Window
[0.05, 0.08, 0.10]
10.15, 0.18, 0.20)(T))
[0.25, 0.28, 0.30)
[0.35,
0.38, 0.40)
[0.45, 0.48, 0.50)
Cost
Time
Cost
Time
Cost
Time
Cost
Time
Cost
Time
МTPOМO
25.549
26.410
9s
28.294
9s
31.339
35.217
10s
MVMoE
25.490
12s
26.391
12s
28.258
12s
31.237
13s
35.041
13s
RF-MOE
25.459
12s
26.319
12s
28.227
12s
31.338
13s
35.251
13s
RF-POMO
25.492
9s
26.335
28.242
9s
31.408
35,315
10s
RF-TE
25.377
26.234
28.156
98
31.268
35.135
10s
CaDA
25.309
11s
26.128
10s
28.095
11s
31.334
11s
35.329
11s
(RFES(RF)
25.271
22s
26.143
22s
28.027
23s
30,943
246
34,500
24s
(oSES(CaDA)
25.255
26s
26.032
26s
28.054
268
31.354
27s
35.223
28s
Time Window
[0.55, 0.58,
0.60]
[0.65, 0.68,
0.70]
[0.75, 0.78,
0.80]
[0.85, 0.88,
0.90]
[0.95, 0.98,
1.00]
Cost
Time
Cost
Time
Cost
Time
Cost
Time
Cost
Time
МTPOМO
39,549
10s
44.035
48.215
11s
$2.295
11s
55.933
11s
MVMoF
39.349
14s
43.781
14s
47.995
156
$2.160
16s
55.903
16s
RF-MoE
39.606
14s
44.026
14s
48.082
15s
$2.029
15s
55.465
15s
RF-POMO
39,668
10s
44.102
11s
48.144
11s
52,090
11s
55.539
11s
RE-TE
39.402
10s
43.783
47.812
51.869
55.424
11s
CaDA
39.697
12s
44.152
12s
48.231
12s
52.122
13s
55.650
13s
(RFES(RF)
38,490
25s
42,600
268
46.770
27s
51.475
28s
55.973
29s
MoSES(CaDA)
39.488
29s
43.864
29s
47.854
30s
51.784
30s
55.172
31s
generalization to unseen distance limits, we evaluate performance across a range of values for ydur max from the set 227,,28, 2,,, 3.0, 3.2, 3.3, 3.4), where gdur 2.8 corresponds to the ID case. The results of this evaluation are summarized in Table 3 MoSES(RF) employs the dense routing strat- egy with the norm_seo (ran__sopllu(s)) activation function, while MoSES(CaDA) utilizes the same routing strategy with sigmid(-) as the activation function. Experimental results indicate that MoSES(RF) consistently outperforms all other methods, including MoSES(CaDA) across all evaluation settings. This demonstrates its superior OOD generalization capability when faced with unseen distance limits.
In VRPTW, each problem instance is primarily defined by both the time window and the service duration. These are generated based on two intervals [2] and Is as de- scribed in Section A.2 Let the triplet [41 12, Is] represent the full configurations. The ting [0.15, 0.18, 0.20j serves as the in-distribution ID evaluation. To assess OOD general- ization to unseen time window configurations, we consider a range of settings from the set (00.55, 0.08, 0.10). 10.15. 0.18, 0.20]. (0.25. 0.28, 0.30)..... (0.95, 0.98, 1.00]]. as reported in Ta- ble 4 Both MoSES(RF) and MoSES(CaDA) adopt the dense routing strategy. MoSES(RF) uses norm noomoooootppllll ssst_susffttstt as the activation function, while MoSES(CaDA) employs sigmoid(-). Exper- imental results show that MoSES(RF) generally outperforms its baseline, RF-TE, across most evaluation settings, with the exception of performance drop observed [0.95, 0.98, 1.00). Sim- ilarly, MoSES(CaDA) surpasses its baseline, CaDA, except for a marginal decline in perfor- mance [0.35, 0.38, 0.40). Overall, MoSES(RF) demonstrates superior performance compared to MoSES(CaDA) in the majority of task settings.
B.2 CVRPLIB Evaluation
We report the performance comparison of our proposed methods, MoSES(RF) and MoSES(CaDA), against baseline approaches on CVRPLIB instances from ranging from 101 to at most 1,001 nodes, as done in [3 3 Both MoSES(RF) and MoSES(CaDA) use the Variant-Aware Routing-T strategy. MoSES(RF) uses norm norm_softpp parm_softplu(-) as the activation function, while MoSES(CaDA) employs sigmoid(-). The detailed results are presented in Table
set, which includes problem sizes
27

---

Table 5: Performance comparison of multi-task VRP solvers on CVRPLIB instances from the X sct.
18.05:31)
13%
Cei
0gg
1ice
Col
G2y
2
Cet
Teu
Del
Tee
Ont
1.41
Cer
18a
Oo
Coe
Cop
30000
3-13
0.51%
1.4
1107%
1.1
2130
1320
871
3.01
016
20.55
3/076
03:
2160
1000
47.55
05:
2500
1.011
1231
68
1%
03
686
470.0
134
1979
4879
47736
1705
5270
1938
196
96.
166
1126
3120
0.0%
18
13
110
616
1554
2015
08
1010
200
60
130
181%
1307
10055
1435
100
15
1006
18
01005
204
540%
06
526
513
130%
66
1366
5463
1985
630
1301
4014
141
400
1009
1209
63
2465
65
4661
1250
3-2 8-24411
1136
150%
14
150
16
100
1304
06
1400
120%
66
1923
103
16
10B
1906
13
740m
18
0130
700m
C7545
4154
-91111
300
5-31
3.7
1.%
2011
18:
2043
6:011
116
to0
15%
2013
158%
-91117
100
1-6
1/06
8-01181
1000
15
1963
3010
5056
11576
18
360
1567
19
065
1705
100
1.30
1906
54
6308
18
1101
100
1905
040
18
2003
216
11390
18.
40.76
26
3.20
1031
18
56
1000
19
1400
16
18
19
11780
76
11396
11210
1181
11h
13815
1898)
136
1.01
1070
60066
11.77%
2013
1360
01085
134
68
1134
7508
5/00
1330
58
2112
1036
1928
880
550
56
195%
100
58
1612
3-
11.0%
14
1984
131155
18
15455
18
1966
16.21
28
163
1966
106
1181
05511
13
107
14001
116
1807
1961
1187
1750
1909
1960
11996
1976
153190
19
1518
20175
1711
111
78
3.076
19915
32636
(960)
1190
11,079
$299 $760
1991 2:0h
To facilitate analysis, we partition the evaluation set based on problem instance size into three subsets: instances with N < 251, 251 < N < 501 and 501 < N < 1001. Across all three subsets. both MoSES(RF) and MOSES(CaDA) consistently outperform their respective baselines. RF-TE and CaDA. On the larger instance sets (251 < N < 501 and 501 < N < 1001), M0SES(RF) demonstrates superior performance compared to MoSESSCaDAA. Conversely, on the smaller instance set (N < 251), MoSESSCaDA)) achieves better results than MoSES(RF). Overall, MoSES(RF) exhibits the best performance among all evaluated methods.
B.3 Hyperparameter Studies
Figure 5 presents an analysis of how varying LoRA ranks influence the performance of MoSES(RF) and MoSES(CaDA) under the settings of N 50 and N =100. We allow the ranks for the frozen modules { BB A,), 1 and the trainable module A. to differ; denoted as I'rouenn and Firee respectively. In Figure 5, the blue curves represent experiments where l'rozen = -32 is fixed while l'roe varies from 4 to 32. Conversely, the green curves fix V'ree 32 while varying Tirozen over the same range. The y-axis indicates the average optimality gap across 16 VRP variants. For MoSES(RF)
28

---

1.725
frozze 32
1,700
frre
3.3
1.675
Gap(%
1.650
3.2
1.625
1,600
1.575
Frrazen 32
2,9
1.550
Fieee 32
2.8
LoRA Rank
LoRA Rank
(a) MoSES(RF), N 50
(b) MoSES(RF), N 100
Trozen 32
12
Frozen = 32
1.75
Free 32
frree 32
3.1
Gap(%)
1.70
Gap(%)
1.65
155
2.7
2.6
16
32
LoRA Rank
LoRA Rank
(c) MoSES(CaDA), N 50
(d) MoSES(CaDA), N 100
Figure 5: This figure investigates the effect of LoRA ranks on MoSES(RF) and MoSES(CaDA)) under
both N 50 and N 100 settings.
under the setting of N 50, observed that reducing the LoRA rank of the trainable module BA while keeping Tfrezen 32 incurs less performance degradation compared reducing the LoRA rank of the frozen modules B, A,) with Firee = 32, shown in Figure 5(a) However, under the setting N 100, the performance decline caused by reducing Tfrozen with Ffree = 32 is generally smaller than that caused by reducing Frree with l'rozen = 32 (see Figure 5(b) This suggests that for smaller-scale problem instances (N 50), MoSES relies more heavily on frozen modules {B; A,) inherited from the basis solvers. In contrast, for larger-scale problem
instances (N 100), the trainable module BA becomes at least as critical the frozen modules in contributing to overall performance. Likewise, similar trends are observed for MoSES(CaDA) under the setting of N 50., as illustrated in Figure ((c) Under the setting of N 100, the performance gap between reducing the LoRA rank Tfrozen of the frozen modules (with fixed trainable module rank rtree) and reducing the LoRA rank Tiree of the trainable module (with fixed frozen module rank Tirozen) becomes more pronounced (see Figure5(dJ). This suggests that at the smaller scale (N = 50), the frozen LoRA experts contribute more sigmificantly the performance of MoSES(CaDA) than the trainable LoRA expert. In contrast, at the larger scale (N = 100). the trainable LoRA expert plays more critical role driving performance than the frozen LoRA experts. We observe similar performance trends across each individual VRP variant, as shown in Figures and
B.4 Ablation studies
We evaluate our proposed Gated-LoRd against standard LoRA that varies 3 from 0.1 1.0, as shown in Figure Since both methods are applied during the fine-tuning phase to produce specialized basis solvers for the basis VRP variants (OVRP, VRPB, VRPL, VRPTW), F the average optimality gap and average cost across these four variants. When built on the RF-based backbone, the standard LoRA expert achieves its best performance at 3 = 0.8 terms of both optimality gap and cost (blue curves in Figures 6(a) and 6(b). However, the noticeable gap between the lowest
29

---

1.90
LoRA
10.91
LoRA
GatedLoRA
GatedLoRA
1.85
10.90
Gap(%)
1.80
Cost
1.75
10.89
1.70
10.98
1.65
1.60
0.5 0.9
0.2 0.3 0.77
B
B
(a) RF-based Backbone
(b) Ra-dd Backbone
LoRA GatedLoRA
LoRA
10.91
GatedLoRA
10.90
())
Cost
1.80
10.89
1.75
1.70
10.88
1.65
1.60
10.87
0.1
0.1...033
0.4
0.8 1.0
0.10.
0.102..30..0055000 0.7 0.9
B
B
(c) CaDA-based Backbone
(d) CaDA-based Backbone
Figure 6: This figure compares the performance of Gated-LoRA with standard LoRA across varying values of B (0, 1), under both RF-based and CaDA-basee backbones.
point of the blue curves and the green dashed line indicates that our proposed Gated-LoRA module outperforms standard LoRA. Similarly, when built on the CaDA-based backbone, the standard LoRA expert performs best
0.9, yet the Gated-LoRA module still achieves superior performance. These experimental results support our hypothesis that problem instances from any basis VRP variant (excluding CVRP) are OOD inputs to the frozen backbone model, resulting in task-misaligned features in the embeddings generated by the backbone.
Figure presents performance comparison of different activation functions used in the adaptive gating mechanism of the mixture of specialized experts, including softmaxx.)) norm_softplus( +), and s.) In both the N 50 and N 100 settings. MoSES(RF) demonstrates superior performance when employing the norm, (ftpluss function, while performance degrades when using sigmoid(-)) This suggests that (RSES(RF) benefits from convex combination of the pretrained, frozen LoRA experts. In contrast, MoSES(CaDA) achieves its best performance with the sigmoid(-) function, indicating preference for selectively reusing or suppressing specific LoRA experts without being constrained by a unit-sum requirement. Figure [1] presents a performance comparison of different activation functions across each VRP variant. As shown in Figure g the dense routing method yields the best performance for both MoSES(RF) and MOSES(CaDA), while significant
performance degradation is observed when the trainable LoRA module BA is ablated. This suggests that, to achieve better in-distribution performance, the unified neural solver should leverage the knowledge encoded in the pretrained specialized LoRA experts, which capture the ability to solve basis VRP variants. At the same time, the new knowledge learned through the trainable LoRA expert is also crucial for enhancing performance. Figure 12 presents comparative result of different routing strategies across each VRP variant.
To investigate the impact of incorporating explicit task descriptors into the gating mechanism on performance, we modified the input the gating mechanism explicitly include constraint flags. This modification is implemented on MoSES(RF) under the N 50 setting. As shown in Table 6
30

---

Table 6: Impact of incorporating task descriptors into the gating mechanism on performance.
Task
w/o Task Descriptors
w/ Task Descriptors
CVRP
0.900%
0.880%
VRPTW
1.445%
1.452%
OVRP
1.892%
1.940%
VRPL
1.089%
1.058%
VRPB
2.342%
2.339%
OVRPTW
0.959%
0.950%
VRPBL
3.185%
3.187%
VRPBLTW
1.370%
1.382%
VRPBTW
1.121 %
1.109%
VRPLTW
1.811%
1.820%
OVRPB
1.979%
1.995%
OVRPBL
2.014%
2.013%
OVRPBLTW
0.791 %
0.786%
OVRPBTW
0.783%
0.789%
OVRPL
1.917%
1.941%
OVRPLTW
0.962%
0.952%
Average
1.535%
1.537%
Table Performance Comparison of LoRA Expert vs.
Linear Expert.
Task
LoRA Expert
Linear Expert
CVRP
0.900%
0.878%
VRPTW
1.445%
1.427%
OVRP
1.892%
1.808%
VRPL
1.089%
1.061%
VRPB
2.342%
2.217%
OVRPTW
0.959
0.938%
VRPBL
3.185%
2.960%
VRPBLTW
1.370%
1.431%
VRPBTW
1.121%
1.145%
VRPLTW
1.811%
1.845%
OУRPВ
1.979%
1.764%
OVRPBL
2.014%
1.775%
OVRPBLIW
0.791%
0.783%
OVRPBTW
0.783%
0.778%
OVRPL
1.917%
1.819%
OVRPLTW
0.962%
0.943%
Average
1.535%
1.473%
observe that including task descriptors in the gating mechanism reduces the optimality gap for some tasks, while increasing it for others. Overall, the performance impact is minimal. We speculate that the gating mechanism is capable of implicitly identifying different VRP variants based solely the problem instance. As a result, the additional task descriptors do not provide a performance gain.
To investigate linear task -sse-ipcc experts VRP solvers for OVRP, VRPB, VRPL, and VRPTW are trained using linear adapters. These linear adapters are then integrated into the unified solver to enable reuse. We implemented this experiment on the MoSES(RF) model under the setting of = 50. The experimental results are presented in We observe that the proposed linear expert contributes performance improvement.
alternative, designed an experiment where the basis
Table 7
Since our method introduces additional time overhead due to the dynamic gating mechanism compared to its direct baseline, apply the 32x data augmentation technique proposed in (2) to the baseline method to examine whether increasing the inference time the baseline method match the runtime of our method can also yicld a performance improvement. We conduct this experiment based on
31

---

Table 8: Impact of data augmentation on performance.
Method
Avg. Gap
Avg. Time
RF w/ 8 8x dihedral
2.063%
2.0s
RF w/ 32x symmetric
3.261 %
6.1s 1.535%
MoSES(RF) w/ 8x dihedral
5.8s
Table 9: Impact of poorly trained basis VRP solver on performance.
Tasks w/ OVRP
Tasks w/o OVRP
Fully Trained OVRP Solver Poorly Trained OVRP Solver
1.4 1.412% 1.524%
1.658% 1.654%
Tasks w/ VRPL
Tasks w/o VRPL
Fully Trained VRPL Solver Poorly Trained VRPL Solver
1.642% 1.660%
1.428% 1.453%
Tasks w/ VRPB
Tasks w/o VRPB
Fully Trained VRPB Solver Poorly Trained VRPB Solver
1.698% 1.722%
1.372% 1.393%
Tasks w/ VRPTW
Tasks w/o VRPTW
Fully Trained VRPTW Solver Poorly Trained VRPTW Solver
1.155%
1.915%
1.378%
1.969%
the RF model in the N = 50 setting. As shown in Table g we observe that RF with 32x data augmentation does not result in a performance improvement, despite the increased inference time. Therefore, we conclude that the additional inference time introduced by our method is justified by the performance gains it delivers.
To evaluate the robustness of our method against poorly trained basis solvers, we conducted exper- iments using MoSES(RF) under the N = 50 setting. In our method, each basis solver typically employs a LoRA rank of 32. We observed that reducing the LoRA rank to 4 significantly degrades performance, so we used basis solvers with a LoRA rank of 4 to simulate poorly trained solvers. Specifically, we trained four such poorly trained solvers, each corresponding to one of the basis VRP variants. We then replaced one of the original high- gegh-performing solvers in MoSES(RF) with corresponding poor solver and retrained the gating mechanism accordingly. In Table 9 'Fully Trained OVRP Solver' and 'Poorly Trained OVRP Solver' refer to cases where MoSES uses fully trained basis solver and poorly trained basis solver for OVRP, respectively, while the remaining basis VRP solvers remain unchanged. We compare their performance separately on VRP variants with and without the open route constraint. Thus, "Tasks w/ OVRP" and "Tasks w/o OVRP' represent the average optimality gap across VRP variants with and without open route constraint, respectively. The same notation is also applied to the remaining constraints in Table 9 From the results, we observe that the optimality gap is more significantly affected for tasks that include the corresponding constraints when the related basis solver is poorly trained.
B.5 Visualizing Adaptive Gating Mechanisms
In Figure 13
we present a visualization of the weights assigned to five basis solvers, each corre- sponding specific constraint: Capacity (C), Open Route (O), Distance Limit (L), Backhaul (B), and Time Window (TW), for both MoSES(RF) and MoSES(CaDA) under the setting N = 100. Each weight is calculated by averaging across layers, time steps, and problem instances, based on evaluations on 1,000 problem instances per model.
We observe that, since each VRP variant is derived from CVRP. the CVRP solver consistently receives a dominant weight allocation in both MoSES(RF) and MoSES(CaDA). Furthermore, when VRP variant incorporates the Time Window constraint, the corresponding VRPTW solver receives
32

---

significantly higher weights compared to other solvers, with the exception of the CVRP solver. Overall, basis solvers associated with the constraints present in the current VRP variant tend to be preferred. Additionally, solvers corresponding to irrelevant basis variants may still receive non- negligible weights, likely due to partial similarities among the basis VRP variants. Due to the use of the sigmoid(.) activation function in MoSES(CaDA),, the model tends to assign weights with greater magnitudes, thereby capturing more informative signals from the basis solvers.
2.0
1.908
2.578 2.782
2.901:2.074
2.631
1.682
1.574
1.535
2.5
1.5
2.0
Gap(%)
Gap(%)
1.0
1.5
0.5
0.5
0.0
0.0
softmax (RSES(RF)
softmax MoSES(CaDA)
softmax (oSES(RF) norm softplus sigmoid
softmax MoSES(CaDA)
norm softpluss
sigmaid
norm_ softplus
sigmoid
norm softplus
sigmoid
(a) N = 50
(b) N 100
Figure 7: This figure compares the performance of activation functions used in the adaptive gating mechanism of the mixture of specialized experts for both MoSES(RF) and MoSES(CaDA) under the settings of N = 50 and N 100.
3
0.993
Gap(%)
2.135
Gap(%)
1.778
1.7221.001
801
1.5251.620
2.782 2.945 3.177
2.631 2.63)2.7812.77
1
Varient Aorant-Awwa Reating? MoSES(RF)
(OSES(CCDDA)
MoSES(RF)
MoSES(CaDA)
Dunes Reaning
Lnviant Aware Routing
wio trainable Lota
Veriant Aaaa Routins)
Dande Rossing
Variant Annre Routing
wio trainuble Latts
Variant fonate- Routing
Danse Roating
Variant Rasting
wio trainable LoRk
Variant Aerare Rostingg
Dems Roating
Varient haaae Rovting
wntn trainable Luga
(a) N 50
(b) 100
Figure 8: This figure compares the performance of routing strategies used in the adaptive gating mechanism of the mixture of specialized experts for both MoSES(RF) and MoSES(CaDA) under the settings of N 50 and N 100.
33

---

Tex 32
99/M
WMW
WAT
VAKEA
(a) MoSES(RF), N 50
Phoaoe 22
0.90
197A
007
400
1000
100
0000
009
O8K
Frw.
1000
0000
0999
0000
(b) MoSES(RF), . 100
Figure 9: This figure illustrates the performance trends of MoSES(RF) across each VRP variant under both 50 and N = 100 settings, as either Tirozen or Firee is varied while keeping the other fixed.
34

---

Feam
044
0.99
28.0
194
002/1
1050
1000
0009
PAA
C1ROW
76m 622
K97W
10.50W 1000W
ONMEDA
0MA
(a) MoSES(CaDA),
(b) MoSES(CaDA), N 100
Figure 10: This figure illustrates the performance trends of MoSES(CaDA) across each VRP variant under both N 50 and N 100 settings, either Tirozen Trre varied while the other is held constant.
35

---

14
NOSESIOVRA)
algradd
(a)
N 50
Fiem dotpais
WARE (R0SSECODA)
softrac EXETT JUTAAA
CURP
108
VEPMEM
000R
(b)
N 100
Figure 11: This figure illustrates the performance comparisons among different activation functions used in the adaptive gating mechanism of both MoSES(RF) and MoSES(CaDA) across various VRP variants under the N 50 and 100 settings.
36

---

RoUTin
Eramasto LORA
(ay
Aetee RAAEES WAS Toaraado 198A
N
50
MUSESK
Unive faamn Kraning
Vnitar FACI Readlng
09EX
Carto RasEno
Vertan-Ane Awwan TRARRO
CAP
WWW
003
08
08
0AFAA
VPPTA
060
(b)
N 100
Figure 12: This figure illustrates the performance comparisons among different routing strategies used in the adaptive gating mechanism of both MoSES(RF) and MoSES(CaDA) across various VRP variants under the N 50 and 100 settings.
37

---

MUSESTCOOM
090
Figure 13: This figure illustrates the behavior of the adaptive gating mechanisms in both MoSES(RF) and MoSES(CaDA) under the setting 100.
38

---

C Proofs
Theorem 3. The optimal unified policy n² and the i-th optimal basis policy (()) coincide in their value functions for each state 8t associated with the i-th basis task: V .P (st) V= ,p (st). Furthermore, if both the optimal unified policy and the optimal basis policy are unique, then each state-action pair (st, at) corresponding to the i-th basis task, it holds that n² (aglsx) x+))) (aglss)
Proof. By definition, the value function V* iP induced by the optimal policy n" greater than or equal to the value function Va.P of any unified policy и for all feasible states 8, at each time step t. Formally, VT, E St, t E {o....,Ty, it holds that V .P (st) 2 (st)) Likewise, the i-the optimal basis policy -(0h (i 2 0) maximizes the value function V ,P, evaluated on states induced by the initial state distribution defined over 5 for i = 0, or over s. xS(²) for 2 1, corresponding the i-th basis task at each time step. That is, for all z()), st
5 and E (O...., ,,,, we have St E ES, x S t (0.............. (O.....T) T).
V= (s( ) 2 V= .P (st (0)) ). Similarly, for all (0()) (s) (0)
(8)
and i 2 holds that y=( .P ((() .t (²)) 2 ( (0) )).
According to the definitions of the SDMDP framework and the basis task, it is evident that, at each time step, the state space associated with a basis task is subset of the state space defined for the unified policy. Specifically, at each time step t, for all st E s("), it holds that s E St.
Sr. As a result, V- (s..)). Similarly, at each time step t, for all st E s! it follows that V (s( (0) = V= 10)-
Likewise, for all (8()) )
E S(
x S(1) and i 2 1 we have (5 ())
for all (ot (0) ( E s(()) x s.O), and i 2 1, we have V= ((o,)( (())
Vall (({! 86 ())))
Moreover, if the i-the basis task (i > 0) admits unique optimal policy x ((),, and the optimal unified policy n² is also unique, then for each state s; associated with the i-th basis task, it holds that T² (acls;) = x (+)* (oulst), where at E A(s)).
Assumption 3. In the SDMDP framework, any state is composed of conditionally independent basis states, denoted as = pm Accordingly, we assume that any policy π is capable of extracting the basis state embedding z (b,) E Id for each glb.), where = -O.... m. Under this assumption, we further posit that there exists deterministic bijective mixture function So S x II R2 > Rd, parameterized by 6, which maps the basis state embeddings (b( J to the state embedding z E IRd for the given state 8, represented as z = fz((( (bm)) s). Thus, the policy defined over the action space can be rewritten
<(als) = Σ {(a))))(2ls)=
Σ
T(alfo(2(0))
(m))
II
7(2 (10)
(9)
where = x (2 (100)))(00)) = x(2 ((, (0m))s) The second equivalence in Equation holds
because f assumed to be deterministic.
Assumption 4. For any state 8, and for any two policies a and n', we assume that if Va e T()s) = =a((ass) then Vz E Rdd (2|s)) (2|ss, and conversely.
Theorem 4. Let [T,, p. and ( Pz) denote the objective functions (expected re- turns) in SDMDP and LS-SDMDD respectively. By Theorem 3 and Assumptions 3 it fol- lows that the values of the objective functions are equal at their respective optimal polictes, for- mally written as J(T", P.H)) J P2,Mz). Moreover, the value functions of SDMDP and
LS-SDMDP at their respective optimal policies satisfy the following relationship V=a PP(s) = Eg0g) E (00m bmn) V Pa (2 (bm)) s).
Proof. By definition, for any given policy ग, the objective function J(T,, P, within the SDMDP
framework can be reformulated as shown in Equation 10 In this reformulation, Equation ! is derived by incorporating Equation Subsequently, Equation (1 is rearranged to yield Equation ②.
39

---

J(T ((). (T.
re 80 s]
T-1
T-1
((s))
I
π (a
Pt)P(s a1)
I'T
t=
1=0
T-1
((s))
II t=
Σ
(ba)
(6m) ;sm)))))))))) st))
3....
$0,00
T(2 (bo)
(bm) (s
PsL4((54 0e)
Σ xr
26
Σ
((0))
II x (aelso(() ,....,2 ;
(ho)
(10) Omee
Obo) Umm)
so R0
Zip p
T-1
[( (2()0) :..., #t
(Bo)
(1m) (1 Pesttttt
Σ
xr.
(10)
J(#",P,)) @ Σ
Σ
((80)= (=}
(b))
:0 _00))0))
ST
20 m0. !....!?mm
(ba)
(6m)
(60) 2
(bm)
T-1
T-1
II
T (0elSo(2(
(bn)
(1m)
86) IT
(=(00)
(24415...5
(bb)
2+41
(bm)
((
r'r
Σ 50
Σ
((so)
(be) (s00))
(ha)
(0m)
(bp)
16m
==0
T-1
T-1
Il
n
(aelSa(=
(bp)
(0m)
8{))
(b:) r+1
Y'
==0
t=0
Σ
Σ
Σ
((so)
π
(w) 13000))) (2)
(b:)
5o 77
(bg)
(6m)
(p))
(mm)
2=0
T
T-1
T-1
II [=0
nh
(aelJol2) (bo)
(0m)
(be) (2 (( 4r)
1=0
Σ
(=()
(bg)
o (bm)
a6m )
T-1
Il
n (a.lSo(=( (60)
s()) ; (F441138 a.)
24
(mm)
Σ
rr
t=0
(11)
As shown in Equation 11 the optimal policy x² is substituted into the expression. Equation I holds
(bm)) = |sT)) does not influence because the action taken at the terminal state 8T, denoted as π ((2(b)) .... based on the conditional inde-
the value of the objective function J(=, P, p). Equation ② is
pendence of the basis states (s ..... 8
(tm)), Based on the conclusion of Theorem 3 we derive the
following results: 1) In the bo basis task, for all s, (1w) E sfhw) and a, E A(s((u)) where 0 S t < T.
it holds that rr' (arls(uu) (ou)) o (r(b)) (a.ls!")) (w0)). Please note that by is fixed to 0 within the SDMDP
40

---

framework. 2) Similarly, in the by-th basis task (i 2 1), for all (s(6)) (b.))) E s! x s(ee) and a, E A((( of (()))) )), where 0 S S T, it holds that x (ael(o) 58 bel)) = =all))aarl0)) (bo) ot (()))) Furthermore, in accordance with Assumption 4 we have It (zels) (bu))
(bu)
(bo) and for all 2 1. According to Assumption 3 for each policy, including the basis policy, there exists mixture function So that provides a bijective and deterministic mapping from the basis state embeddings to the corresponding state embedding. Thus,
((bo) (zels.
St
>=]=:[(s) (x(()) ) = (2((( (b))))
,86 ,)(")))
the state embedding 2, is given by 24 =z) .24 (s(
(b:),
186 (b))) .t ..()))) under both x and π ((())* Con- π (b.)) (2t (bo)
(ho)
sequently, we conclude that x (1t (z( (bu))
)TT" (2. (6.)
(=(b))
166 (bo)
( (b.) (2)
Given the preceding results, we additionally assume that x (2( 1s, (c))) (b())) (b)) (2t 1ss (bc)) which
directly supports the Equation 3) Equation 4 is obtained by incorporating the definitions of the
initial state distribution and the transition probability function within the LS-SDMDP framework.
It is evident that the policy x (a=)
4t ( st)) is the optimal policy for the objective func- tion JTT P2) This because, if this were not the case, n² would not qualify as the optimal pol-
icy for the objective function [ H.) Thus, we conclude that x (as (z (bo)
(bm), st)) =
ji (a, |2|
(bo)
(bm); st) and J(x", , p)) JTT Pa. M2).
By the Bellman equation and the policy decomposition in Equation 9 the value function of SDMDP at the optimal policy, for each time step 0 S t 5 - can be expressed as follows:
V=a PP (sx) = (a (re + 1/Bx411P((
V= ($t+1)l
= E "cma "a (a) ..... (4m) (om)) B2(00) ... .....((m)) (6m) Nn (2 .....e (mm)))))))
"........ ( [re + Beee mm) V (84+1))
(12)
= =R_g00) war (a/(()/)))))))))))) ( (mm) (mm) (sc)
psc) B
"emes Cener (arlfo(s( om
(m))
In +- 7Bees ss.a)) Va (8c+1)l
Likewise, the value function of LS-SDMDP at its optimal policy can be written as:
v Po (0o)
(2t
2 (0m)) 82) = anwaj (acle(")) .....
"oreel.."" (4m)) (It + 7 Preeallee
2t
(hm)) (bm) V (2
(bo) (bm)
2441 s141)l
(ha) 2+41
(bo)) Ftll
(13)
We the inductive method to prove the relationship between the value functions at their respective optimal policies. At the time step T - 1, since the value function at time step T is equal to 0, the value functions defined in Equation 12 and Equation 13 can be expressed as follows:
V P (ST
E wo) ST wn (x1")) (er-1) (6ml our (ofmm) (er-1) 1)
ar 1~r1(as i1fo(= 1 1 (mm)er 1)) (rr-1l
(14)
P: (2)
P: P( (2()))
(bm) 27 (1) 81-)) or 1 (ar 1 2 Smm) 1or [r--1]
It is evident that the two value functions satisfy the relationship time step T --1 We now assume that at any time step + 1, the relationship between these value functions holds. Substituting this assumption into the value function of SDMDP defined Equation 12, yields the following:
V* P (st) = E
(00) (000) (a("0))) Ba (or (2f"m² 0 a oo (oglfo(ee)) w flmm (bm))s))) 2e
Ire BB (ea))) Co) (o
E (bm) E..mm Feat
(15)
Vi P. (2(1e) (Bm) s(+1)]
We thus conclude that the relationship between the value functions at their optimal policies given by V* (s) E (3(( Eg(0m Nug (em) (bm))
/0 P. (z(b)) .... (0m), ;
41

---

D Related Works
In this section, we first survey advances in task-specific neural solvers, which form the foundation for multi-task approaches. Next, we review multi-task learning techniques for VRPs. Finally, we examine recent progress in ooo.turreo--specciiieeeeeepeeeee (MoSE) methods, which inspire key implementation aspects of our method.
Task-Specific Neural VRP Solvers. Learning-based neural solvers, individually developed for each specific VRP, fall into three main categories: constructive methods, iterative methods, and divide-and-conquer methods. Constructive methods craft end-to-end neural solvers to progressively infer solutions through autoregressive mechanisms. Pointer Network [67] pioneers this paradigm by effectively solving the small-scale traveling salesman problem (TSP), while Attention Model (AM) [34] emerges as the dominant architecture for subsequent task lsss-specific neural solvers trained via reinforcement learning (RI.). Some approaches consider properties inherent in TSP and capacitated VRP (CVRP), including the multiple optima [35 and the symmetry [3 to improve the solution quality. To further improve the cross-scale or gross-distribution generalization, advanced techniques, such as meta-learning [5] 60 84), knowledge distillation [4], ensemble learning [1 [2 30), have been successfully transferred from other domains. Additionally, neural solvers trained via supervised learning (SL) also exhibit strong generalization capabilities [1 46 47.. Iterative methods leverage local search operators to consistently refine solutions until convergence. Specifically, L22 [45] and NeuRewriter [7] train RL policies to select among handcrafted operators for solution improvement. NLNS [24] alternates between hcuristic destroy operators and learned repair policies to generate new solution. DACT [50] advances beyond prior works by learning expressive representations for RL. policies, while Neural-LKH (74 and Neural k-opt [49] specialize in k-opt algorithms by using RL policies to guide edge exchanges. However, these methods universally trade inference operators. Divide-and-Come Conquer methods decompose problem instances into smaller sub-instances that are solved independently. Prior works have attempted to solve larger instances using pretrained neural solvers on heuristically sampled sub-instances [16 32 g By comparison, L.D [3] and RGB (85) learn RL policies to select subgraphs from heuristic-generated candidates. Unlike these heuristic-basee methods. TAM (25), GLOP 777. UDC 82). and HLGP (56) opt to learnable RL policies globally partition entire instances into subproblems, which are then solved by pretrained local construction policies. However, these methods critically depend on the partition policy, where even minor performance degradation may significantly impair the overall VRP solution quality.
efficiency for solution quality with the aid of manually-desigue
Multi- Task Learning for VRPs. To cope with practical scenarios involving multiple VRP variants, the efficient transfer learning has been leveraged to obtain specialized neural solvers by considering inherent similarities among these variants. Lin al. 41 propose modular architecture consisting of a backbone pretrained on a canonical VRP and lightweight adapters inserted into the frozen backbone for the mooblem-specife fine-tuning. Likewise, GOAL [4 extend this paradigm to general COPs, along with fewer adapters. Corrêa et al. [I]] adopt full- -al-mmareetter fine-tuning strategy for each downstream VRP variant, yielding multiple problem-specific but parameter-ineffiiien neural solvers. However, these methods struggle with the combinatorial explosion of VRP variants. Notably, although the LoRA adapter is used for problem-specffic adaptations in 41] . its potential as part of a unified solver to handle the exponential growth of variants remains unexplored.
As an alternative, unified solvers are designed to handle multiple VRP variants simultaneously while eliminating the need for adapters or backbone duplications. Liu et al. [42 framework that unifies variants via attribute compositions. MVMoE
pioneer a single-solver
83 enhances capacity with
mixture-of-expert (MoH) layers that implicitly specialize for different variants. RouteFinder [3] em-
ploys modified Transformer model with mixed batch training for stable convergence. UNCO (29 re-
sorts to the large language model (LLM) for the expressive instance and task embeddings. CaDA (38
utilizes dual attention mechanism for superior cross-probles capabilities. Goh et al. 20 consid- ers the more practical multi-task, multi-distribution setting by using mixture-of-depee context-basedd clustering. Liu et al. [43] leverage miixedccuvaature spaces in the feature fusion stage such that the model's 's encoder can capture the geometric structures inherent in VRP instances. Lei et al. 377 strengthen cross-scale and pross-problem generalization capabilities of diffusion- -based solvers during inference, which is orthogonal to our work. In contrast, Wang & Yu (68] decompose the model into a shared encoder, and problem-specific headers and decoders, applying multi-armed bandits for dynamic task sampling during training. Li et al. [40] adopt the same architecture with aligned
(MoD) and
42

---

optimization directions across tasks. However, these methods fail to fully leverage the compositional structure inherent in VRP variants, each derived from a common set of basis VRP variants. Thus, the potential benefits of incorporating explicitly specialized basis solvers remain unexplored. Notably, while MoF. layers are employed in [83] these learn implicit and less interpretable specialization rather than incorporating off-the-shelf basis solvers as experts.
Mixture of Specialized Experts. Prevailing methods focusing on mixture of specialized experts (MoSE) can be broadly categorized into two paradigms: merging entire models and module composi- tion. Approaches based on merging entire models seek to combine independently trained models to efficiently achieve the performance comparable to model ensembling or multi-task learning. Most approaches are developed based on the shared model architecture. Wortsman et al. [70] exhibit averaging the parameters of models trained with different hyperparameter configurations improves accuracy. Matena & Raffel [52] develop a model aggregation framework guided by Fisher informa- tion. Yadav et al. 77 address interference effects in model merging to preserve critical knowledge. Tam et al. (64] formulate model fusion as linear equation system solved through conjugate gradient optimization. Daheim et al. [12] introduce a uncertainty- based merging scheme to reduce the gradient mismatch. In contrast, several approaches enable merging across architecturally distinct models. Ainsworth et al. ( align weights of different models to enable the model merging, Stoica et al. [3] introduce cross-task model fusion through feature-space integration. Additionally, weighted merging strategies have also been extensively explored. Ramé et al. [6]] implement weighted model fusion to enhance out-of -f--isttritttinn generalization, while Jin et al. [I] develop parameter-spee merging optimized for multi-tas task performance through learned weighting schemes. Yang et al. [76] further advance this paradigm by deriving merging coefficients via unsupervised entropy minimization. However, these approaches struggle with achieving precise layer-wise and token-wise aggregation within expert models, limiting their multi-task OOD generalization.
Our implementation aligns more closely with the module composition paradigm which supports the finer-grie finer-grained aggregation. The most straightforward approach involves parameter averaging of task adapters. Chronopoulou et al. [9] demonstrate test-time averaging of relevant adapters for task adaptation, while Ponti et al. [59] propose averaging adapter parameters selected by a routing function for new tasks. Beyond simple averaging, arithmetic operations have proven effective for the adapter composition. Chronopoulou et al. [10] demonstrate that basic arithmetic combinations enhance zero-shot cross-lingual transfer, while Zhang al. [8T) develop specialized arithmetic operations for lightweight adapters to boost generalization. Similarly, Ilharco et al. (8) employ arithmetic combinations of task vectors precisely steer model behavior for novel tasks. Task similarity further
facilitates the effective module composition. Lv et al. [48] develop weighted aggregation of parameter- efficient adapters based on inter-task similarity measures for novel tasks. The MoCLE (21 framework addresses task conflicts and improves generalization by activating task-customized LoRA adapters based on clustered instructions and using a trainable universal adapter. Similarly, Wu al. [72] propose modality- performance on multimodal downstream tasks. Adaptive gating mechanisms have emerged as the predominant approach for dynamic model composition. LoRAHub [27] employs few-shot examples to compute weighting coefficients for pre-trained LoRA modules, enabling competitive performance on novel tasks. Building on this, Ye et al. [78] develop hierarchical routing mechanism that selects optimal Transformer layers for enhanced task generalization. The MoLE 73 framework advances this paradigm through layer-wise gating functions that learn to optimally combine LoRA experts, with these operations being implemented via dedicated Transformer blocks. AdaMoLE 44 further incorporates dynamic threshold adaptation to handle varying task complexities. Caccia et al. [5] introduce multi-head adapter routing, enabling fine- grained routing for the cross-task generalization. Module composition approaches also effectively address catastrophic forgetting. LoRAMoE [13] mitigates world knowledge degradation in frozen backbone LLMs through strategic integration of multiple LoRA modules. Similarly, AdapterFusion (58) combats catastrophic forgetting in multi-task learning scenarios by dynamically combining pretrained adapter modules. Furthermore, module composition techniques have also demonstrated significant potential for zero-shot generalization. PHATGOOSE (53) achieves this through inference-tine -ime aggregation of LoRA adapters via their pretrained gating functions. Similarly, Ostapenko et al. (55) develop zero-shot routing mechanism that dynamically selects the most task-relevant adapters based on task similarity, eliminating the need for retraining. In addition, Zadouri al. (79) advance efficient adaptation through fine-tuning of mixture of lightweight LoRA experts for limited computational cost scenarios. Gao et al. [18
task similarity measures to combine lightweight adapters for enhanced
43

---

uncover important architectural insights: different layers benefit from varying numbers of LoRA modules, and higher network layers particularly require more experts maintain performance.
44


Reviews:
[{"review_id": "wugxX5He6y", "reviewer": "Reviewer_F5K3", "summary": "This paper proposes a framework to address multi-task variants of the Vehicle Routing Problem by leveraging shared structural components. The authors introduce a State-Decomposable MDP formulation that decomposes the state space across basis VRP variants and a Latent-Space SDMDP that enables policy reuse through latent embeddings and a learnable mixture function. The MoSES uses LoRA-based specialized experts and an adaptive gating mechanism to dynamically combine expert outputs. Experimental results on 16 VRP variants suggest that this approach improves solution quality and generalization compared to prior multi-task solvers. Overall, the paper is well-motivated and presents a reasonable balance between theoretical formulation and empirical demonstration.", "questions": "-  How will the framework perform by adding explicit task descriptors (e.g., constraint flags) into the gating mechanism to improve interpretability and performance?\n- If a basis expert is poorly trained, does the mixture mechanism still maintain reasonable performance? Some robustness analysis would be helpful.", "limitations": "None", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### **Strengths**\n\n- The idea of decomposing complex VRP tasks into shared basis variants is intuitive and offers a structured way to think about multi-task combinatorial problems.\n- The latent-space policy mixture through LS-SDMDP is a natural extension that aligns with recent trends in modular learning and policy composition.\n- MoSES is designed with practical considerations in mind (e.g., LoRA for parameter efficiency, compatibility with existing backbones), and experiments demonstrate its general applicability across many VRP types.\n- The theoretical formulation is sound and helps justify the approach, although some assumptions (e.g., deterministic mixture function) may be strong in practice.\n- The experimental section is fairly comprehensive, with comparisons to strong baselines and ablation studies.\n\n### **Weaknesses**\n\n- While the latent reuse framework is promising, the actual gains over baselines (e.g., RF-TE or CaDA) are incremental in some tasks, and come with added inference overhead due to dynamic expert aggregation.\n- The gating mechanism does not explicitly use task-specific features, which may limit its specialization capacity or interpretability, especially when handling more diverse task compositions.\n- The framework is only evaluated in the VRP domain. While the proposed MDP reformulation is general in theory, no empirical evidence is provided for transferability to other problem types.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewers' thoughtful and constructive feedback on our work. We are grateful for the opportunity to address your concerns and clarify any potential misunderstandings.\n\n**Weakness 1： performance and time overhead**\n\nWe would like to clarify that the empirical improvements achieved by our method are sufficiently favorable compared to baseline approaches considered. In terms of average optimality gap across 16 VRP tasks, MoSES(RF) achieves 1.535\\% compared to RF’s 2.063\\% for $N=50$, and 2.782\\% compared to RF-TE’s 3.125\\% for $N=100$. MoSES(CaDA) achieves 1.515\\% versus CaDA’s 1.715\\% for $N=50$, and 2.631\\% versus CaDA’s 2.766\\% for $N=100$. Furthermore, MoSES(RF) outperforms RF on all 16 tasks for both $N=50$ and $N=100$, while MoSES(CaDA) outperforms CaDA on all 16 tasks for $N=50$ and on 13 out of 16 tasks for $N=100$. The detailed comparisons for each task, as presented in Table 1 of our paper, are helpful for identifying potential weaknesses on specific tasks. However, in the multi-task VRP domain, we believe it is fairer and more appropriate to evaluate a method based on its overall improvement and its ability to outperform baselines across the majority of tasks. From this perspective, our method demonstrates favorable empirical performance compared against the baseline approaches.\n\n\nIn terms of the average total time overhead for 1,000 problem instances across 16 tasks, MoSES(RF) requires 5.8s compared to RF’s 2.0s for $N=50$, and 20.8s compared to RF’s 8.4s for $N=100$. MoSES(CaDA) requires 7.4s compared to CaDA’s 2.3s for $N=50$, and 24.8s compared to CaDA’s 10.5s for $N=100$. We would like to emphasize that this time overhead is the total time for 1,000 instances per task; the amortized time per instance remains at the microsecond level for both MoSES(RF) and MoSES(CaDA). Additionally, in the VRP domain, it is generally acceptable to increase inference time in order to achieve better solution quality within a given time budget. In practice, many industrial CO tasks allow for extended computation times to obtain high-quality solutions [1]. Thus, several SOTA VRP methods [2,3] commonly use search-based method or solution refinement. Compared to the time increase introduced by such techniques, the additional overhead from the network architecture changes is relatively minor. We thus believe that the increased time overhead is acceptable given the favorable empirical improvements over prior methods and may not be a major concern in practical applications.\n\n[1] Simulation-guided Beam Search for Neural Combinatorial Optimization, NeurIPS 2022.\n\n[2] BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization, NeurIPS 2023.\n\n[3] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization, NeurIPS 2023.\n\n**Weakness 2: gating mechanism**\n\nWe would like to clarify that the dense routing strategy in the gating mechanism does not hinder interpretability, as evidenced by the analysis in **Figure 9 of the Appendix**. Figure 9 presents a behavioral analysis of the gating functions used in our models across 16 VRP variants. In this figure, we plot the scores assigned by the gating function to each basis solver. It is clear that for a given VRP variant, the gating mechanism tends to assign higher scores to basis solvers associated with the corresponding underlying basis VRPs. For example, in OVRPB, the gating mechanism assigns higher scores to the basis solvers corresponding to CVRP, OVRP, and VRPB. The reason the gating function does not completely zero out the remaining tasks is that many VRP variants are inherently correlated; solving instances of one task may benefit from insights learned from others. Additionally, we would like to emphasize that since our method reuses only the basis VRP solvers, the number of solvers increases linearly, which is more manageable compared to the exponential growth in neural solver. In future work, we plan to explore strategies for pruning basis solvers for specific tasks to further mitigate the potential increase in solver composition. \n\n**Weakness 3: transferability to other domains**\n\nFirstly, we would like to clarify that our work specifically focuses on the multi-task VRP setting, which reflects a more practical demand in real-world applications. Although our primary focus is on multi-task VRP, the proposed theoretical framework still maintains generality and can potentially be extended to other domains. We believe that exploring such extensions represents a promising direction for future research, but they are not the central objective of this work. Then, we would like to consider an example from robotics to illustrate this potential extension beyond multi-task VRPs. To extend our work to a more general multi-task learning setting, one plausible approach would be to define a set of basis tasks, from which all target tasks can be derived. Suppose the goal is to learn a robot policy for washing a cup. The basis tasks might include picking up the cup, filling it with water, and using a cloth to clean it. Notably, the tasks of picking up the cup and filling it with water could also be components of another task, such as watering plants. This example demonstrates how basis tasks can be reused across different target tasks, highlighting the potential of our framework to generalize to broader multi-task learning scenarios. While this may not cover all real-world scenarios, it does encompass a broad spectrum of applications, further highlighting the potential of our framework to be extended beyond multi-task VRPs to more general and practical domains.\n\n**Question 1: task descriptors**\n\nWe appreciate this insightful question, which identifies an important avenue for potential performance improvement. To explore this, we augmented the gating mechanism's input to explicitly include constraint flags (i.e., a binary vector). We implemented this modification on MoSES(RF) under the $N=50$ setting. We hope you understand that we limited our implementation to this setting due to constraints in time and computational resources. In the table below, we observe that incorporating task descriptors into the gating mechanism leads to a decrease in optimality gap for some tasks, while it increases for others. Overall, the performance impact is not significant. We speculate that the gating mechanism is capable of implicitly identifying different VRP variants based solely on the problem instance. As a result, the additional task descriptors do not provide a performance gain.\n\n| VRP Variant | w/o task descriptors | w/ task descriptors |\n|-------------|---------------------|-----------------|\n| CVRP        | 0.900%  | 0.880% |\n| VRPTW       | 1.445%  | 1.452% |\n| OVRP        | 1.892%  | 1.940% |\n| VRPL        | 1.089%  | 1.058% |\n| VRPB        | 2.342%  | 2.339% |\n| OVRPTW      | 0.959%  | 0.950% |\n| VRPBL       | 3.185%  | 3.187% |\n| VRPBLTW     | 1.370%  | 1.382% |\n| VRPBTW      | 1.121%  | 1.109% |\n| VRPLTW      | 1.811%  | 1.820% |\n| OVRPB       | 1.979%  | 1.995% |\n| OVRPBL      | 2.014%  | 2.013% |\n| OVRPBLTW    | 0.791%  | 0.786% |\n| OVRPBTW     | 0.783%  | 0.789% |\n| OVRPL       | 1.917%  | 1.941% |\n| OVRPLTW     | 0.962%  | 0.952% |\n| **Average** | **1.535%** | **%1.537**|\n\n**Question 2: robustness to poorly trained basis solver**\n\nWe appreciate this insightful question regarding the robustness of our method. To explore this, we conducted experiments using MoSES(RF) under the $N=50$ setting. In our method, each basis solver typically uses a LoRA rank of 32. We observed that reducing the LoRA rank to 4 significantly degrades performance, so we used basis solvers with a LoRA rank of 4 to simulate poorly trained basis solvers. Specifically, we trained four such poor basis solvers, each corresponding to one of the basis VRP variants. We then replaced one of the original high-performing solvers in MoSES(RF) with a corresponding poor solver and retrained the gating mechanism accordingly. In the four tables below, the first columns labeled \"O\", \"L\", \"B\", and \"TW\" represent the basis solvers corresponding to the respective basis VRP variants. Similarly, the first row labeled \"O\", \"L\", \"B\", and \"TW\" denotes the eight VRP variant tasks, with or without the associated constraints. From the results, we observe that the optimality gap is more significantly affected for tasks that include the corresponding constraints when the related basis solver is poorly trained. This observation is indeed reasonable and aligns with our expectations.\n\n|Method              | tasks w/ \"O\" | tasks w/o \"O\"|\n|--------------------|--------------|--------------|\n|fully trained       | 1.412% | 1.658% |\n|poorly trained \"O\"  | 1.524% | 1.654% |\n\n|Method              | tasks w/ \"L\" | tasks w/o \"L\"|\n|--------------------|--------------|--------------|\n|fully trained       | 1.642% | 1.428% |\n|poorly trained \"L\"  | 1.660% | 1.453% |\n\n|Method              | tasks w/ \"B\" | tasks w/o \"B\"|\n|--------------------|--------------|--------------|\n|fully trained       | 1.698% | 1.372% |\n|poorly trained \"B\"  | 1.722% | 1.393% |\n\n|Method              | tasks w/ \"TW\" | tasks w/o \"TW\"|\n|--------------------|--------------|--------------|\n|fully trained       | 1.155% | 1.915%  |\n|poorly trained \"TW\" | 1.378% | 1.969%  |\n\nWe sincerely thank the reviewer for the insightful comments and thoughtful questions, which have helped us better understand and refine our method. We will revise our manuscript based on your feedback and include the additional experiments you suggested."}, {"review_id": "fP4Z4Uny2p", "reviewer": "Reviewer_Tp1S", "summary": "The proposed paper tackles the topic of multi-task vehicle routing problem solvers. Specifically, the authors reformulate the problem as a State-Decomposable MDP (SDMDP), where the state space decomposes into basis states, each corresponding to a fundamental VRP variant (e.g., capacitated, open route). They then extend the work to latent space (LS-SDMDP), proving that the mixture of basis policies can recover optimal solutions under certain conditions. Specifically, in their method, the authors assume the most basic variant of the VRP as the capacitated problem aand each subsequent variant has an additional constraint. As such they train a fixed backbone trained on CVRPs, and use LoRA experts adapt the base embeddings to more constrained settings. They call this method the Mixture-of-Specialized-Experts Solver (MoSES) and use a weighted gating mechanism to concatenate the different expert outputs.", "questions": "1. Seeing as the method is slower, have you tried running the direct baseline (the models you adapt) with more than 8x augmentations or using input augmentation like in [1]? The difference seems small enough that for some experiments, matching the runtime might change the model standing.\n\n2. Can experts interact with each other outside of the gated mixing? This would seem to be important for correlated tasks.\n\n3. For different problem sizes, is there any insight on when frozen vs trainable experts? Would this be due to better expert interaction with harder tasks?\n\n[1] Bdeir, Ahmad, Jonas K. Falkner, and Lars Schmidt-Thieme. \"Attention, filling in the gaps for generalization in routing problems.\" ECML, 2022.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe authors suggest the decomposition of state-spaces for the various VRPs, and they then prove that this decomposition enables optimal policy reuse via latent space composition (LS-SDMDP). The approach is relatively novel, and they provide practical applications of the concept through the use of MoSES. The models implemented are not novel in themselves, but this also shows the flexibility of the approach as a general multi-task framework that allows for the use of plug-and-play backbones. The method also achieves convincing empirical results (although at the cost of increased runtime), the experiments are extensive on the datasets that are studied, and a good ablation study is performed for those datasets (this is a point I mention in the weaknesses below).\n\nWeaknesses:\n\nThe proposed method requires some base assumptions to be present. VRP variant constraints need to be easily separated into additional modeled components, and the method assumes the independence of these constraints. Any correlation between them is poorly modelled since there is minimal interaction between the experts, especially when the backbone is frozen. \n\nAdditionally, the paper does not explore the performance of the model in generated out-of-distribution datasets or in generalization to different routing problem sizes. The later is particularly important since attention-based approaches are severely constrained by small problem sizes. The method is already around 4x slower on average than the direct competitor.", "was_revised": false, "final_justification": "", "rebuttal": "We are sincerely grateful to the reviewer for the insightful comments. We hope this response helps to address your concerns and clarify any potential misunderstandings.\n\n**Weakness 1: assumptions**\n\nWe would like to clarify that we do not assume the basis VRP variants, each characterized by a specific attribute or constraint, are independent of each other. Our work is based on the observation that each VRP variant arises from a composition of attributes, with each attribute corresponding to a basis VRP variant. This observation is well-supported and has been recognized in prior works [1]. Building on this, we propose the MoSES framework, which enables a unified solver to leverage the potential benefits of basis solvers, each specialized for a specific basis VRP variant. While we acknowledge that correlations exist among the basis solvers (experts), modeling these correlations is not the focus of our work.\n\n[1] Multi-task learning for routing problem with cross-problem zero-shot generalization.\n\n**Weakness 2: OOD evaluation**\n\nWe apologize for the inconvenience; due to page limitations, the out-of-distribution (OOD) evaluation has been included in the **Appendix**. In the Appendix, we first evaluate our method on CVRP with varying capacities and gain several insights. We observe that MoSES(RF) with the softmax gating function achieves better performance than its baseline RF on both in-distribution (ID) and OOD evaluations (Please note that **Figure 7(a)** in Appendix shows that MoSES(RF) with softmax performs better than RF in the ID evaluation). In contrast, MoSES(RF) with softplus tends to focus more on ID performance. MoSES(CaDA) with sigmoid also outperforms CaDA under the OOD setting. Next, we evaluate our method on VRPL with different distance limits and find that MoSES(RF) demonstrates stronger generalization capability compared to both baselines and MoSES(CaDA). Finally, we assess performance on VRPTW with varying time windows, where both MoSES(RF) and MoSES(CaDA) generally outperform their respective baselines. Importantly, we also evaluate our method on the CVRPLIB dataset, which includes larger problem instances with up to 1,000 nodes. In this setting, both MoSES(RF) and MoSES(CaDA) outperform their baselines. In the table below, we present a performance comparison evaluated on large-scale problem instances from CVRPLIB. Additionally, we would like to emphasize that multi-task VRP is already a highly challenging problem due to the need to address multiple types of VRP variants simultaneously. As a result, current research, including the baseline methods used in our work, primarily focuses on small-scale problem instances. This is a common and necessary step in combinatorial optimization, where improving performance on small-scale problems often serves as a foundation for developing more advanced methods capable of handling large-scale instances. Therefore, the primary focus of our paper remains on solving multi-task VRPs effectively. The extension to large-scale scenarios is an important direction, but we consider it future work.\n\n| graph size | RF-TE | CaDA | MoSES(RF) | MoSES(CaDA) |\n|----------  |---------|---------|---------|---------|\n|N<251  |5.061% |  4.772% | 4.789% | 4.724% |\n|251<=N<501  |8.107% |  8.889% | 7.741% | 7.948% |\n|501<N<=1001 |12.253%|  14.199%|11.509% |12.814% |\n|Avg. |8.428% |  9.230%|7.973%  |8.441% |\n\nIn terms of the average total time overhead for 1,000 problem instances across 16 tasks, MoSES(RF) requires 5.8s compared to RF’s 2.0s for $N=50$, and 20.8s compared to RF’s 8.4s for $N=100$. MoSES(CaDA) requires 7.4s compared to CaDA’s 2.3s for $N=50$, and 24.8s compared to CaDA’s 10.5s for $N=100$. Although our method is generally over 2x slower than the direct baseline methods, we would like to emphasize that this time overhead is the total time for 1,000 instances per task; the amortized time per instance remains at the microsecond level for both MoSES(RF) and MoSES(CaDA). Additionally, in the VRP domain, it is generally acceptable to increase inference time in order to achieve better solution quality within a given time budget. In practice, many industrial CO tasks allow for extended computation times to obtain high-quality solutions [2]. Thus, several SOTA VRP methods [3,4] commonly use search-based method or solution refinement. Compared to the time increase introduced by such techniques, the additional overhead from the network architecture changes is relatively minor. We thus believe that the increased time overhead is acceptable given the favorable empirical improvements over prior methods and may not be a major concern in practical applications. \n\n[2] Simulation-guided Beam Search for Neural Combinatorial Optimization, NeurIPS 2022.\n\n[3] BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization, NeurIPS 2023.\n\n[4] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization, NeurIPS 2023.\n\n**Question 1: data augmentation**\n\nWe thank the reviewer for this valuable suggestion about data augmentation for the baseline methods. We thus incorporated 32x data augmentation techniques using the method you suggested and present the updated performance of RF on N=50 in the table below. We observe that RF with 32× data augmentation does not yield performance improvement despite the increased inference time. Therefore, we believe that the additional inference time introduced by our method is justified by the performance improvement it delivers.\n\n| method | Avg. Gap | Avg. Time|\n|--------|----------|----------|\n|RF w/ 8x dihedral   | 2.063% | 2.0s |\n|RF w/ 32x symmetric | 3.261% | 6.1s |\n|MoSES(RF) w/ 8x dihedral | 1.535% | 5.8s|\n\nAdditionally, we would like to emphasize that the detailed comparisons for each task, as presented in **Table 1** of our paper, are valuable for identifying potential weaknesses on specific tasks. However, in multi-task VRP, we believe it is more fair and appropriate to evaluate a method based on its overall improvement and its ability to outperform baselines across the majority of tasks. Based on this perspective, along with the considerations mentioned above, we believe the increased time overhead is acceptable given the overall favorable empirical improvements over prior methods and is not a major concern in practical applications.\n\n**Question 2: expert interaction**\n\nTo thoroughly address this question, we would first like to clarify that in our method, the primary aim of the gating function is to capture the individual insights of solving basis VRP variants present in a given problem instance. While the gating function does admit interactions among experts, its main purpose is to determine which basis solvers offer the most useful insights for the specific problem instance. Additionally, our MoSES framework incorporates a trainable expert that captures a holistic understanding of VRP variants. This holistic understanding naturally includes the correlations among the basis VRP variants present in the given instance. As a result, both the gating function and the trainable expert play important roles: the gating function facilitates the generation of individual insights through expert interactions, while the trainable expert captures broader correlations and relationships among VRP variants. Therefore, we agree that it is important to consider potential interaction mechanisms beyond the gating function employed in our current approach. Such mechanisms could further enhance either the generation of individual insights from basis solvers or the holistic understanding of the given VRP variants, including their interdependencies. Exploring these directions represents a promising and long-term research opportunity. We sincerely appreciate your suggestion, which highlights a valuable path for future work and potential extensions of our framework.\n\n**Question 3: frozen and trainable experts**\n\nThis is a significant question, and we believe that **Figures 2\\(c) and 2(d)** in the main text of our paper help address it effectively. Before diving into the analysis, we would like to clarify the roles of the gating function and the trainable expert in our method. The gating function is primarily designed to extract individual insights from basis VRP solvers. While it allows for interactions among experts, its main goal is to identify which basis solvers provide the most relevant insights. In contrast, the trainable expert is intended to capture a holistic understanding of the given VRP variant, which naturally includes correlations among the basis VRP variants. It is important to note that we do not employ complex loss functions (e.g., mutual information) to explicitly decouple the features learned by the gating function and the trainable expert. Therefore, the roles described above reflect their primary, though not exclusive, contributions. From Figure 2\\(c), we observe that for smaller problem instances ($N=50$), reducing the LoRA rank of the frozen experts (basis solvers) leads to a more significant performance drop than reducing the LoRA rank of the trainable expert. This suggests that for simpler problems, the basis solvers already contain sufficient useful insights, and the unified solver relies less on the holistic understanding provided by the trainable expert. Conversely, Figure 2(d) shows that for larger problem instances ($N=100$), reducing the LoRA rank of the trainable expert results in a greater performance drop than reducing that of the frozen experts. This indicates that for more complex problems, the unified solver requires a deeper, more holistic understanding of the VRP variant, something the trainable expert is better suited to provide.\n\nWe sincerely appreciate your insightful comments and thoughtful questions. Your feedback has helped us better articulate characteristics of our approach. We will revise our manuscript accordingly to address your suggestions and ensure greater clarity."}, {"review_id": "xlfG8s2alw", "reviewer": "Reviewer_qQzf", "summary": "This work presents a novel approach to training a multi-task NCO model for solving vehicle routing problems using a mixture of specialized experts. It introduces a new State-Decomposable MDP formulation for VRP, where the state space is decomposed into independent basis states and extended with a learnable mixture function to enable policy reuse in the latent space. Through experiments, the authors demonstrate that they can efficiently train optimal policies using specialized experts and adaptive gating mechanisms. This approach can be used in a plug-and-play manner to enhance existing state-of-the-art models.", "questions": "1. Although the main idea is clear, the implementation details and the application to VRP could be explained more thoroughly. For me, only the basic state 0) for the classic VRP is clear, while the others are somewhat confusing. For example, basic state 1)-open route only introduces a binary variable - what would be the basic state for this case, and what exactly does it represent? Next, it is mentioned that 'each VRP variant can be formed by composing basic state spaces,' but isn't it mandatory that state 0) is always present?\n\n2. LoRA originally comes from fine-tuning large language models (LLMs), where low-rank matrix factorization is important due to the heavy computational cost. Did you try using simple linear task-specific experts without projecting to a low-rank space? It seems your model isn't large enough to require low-rank factorization, and avoiding that might improve the results.\n\n3. It is stated that the gated-LoRa method suppresses irrelevant features from the backbone. The backbone is trained on CVRP, and as mentioned in paragraphs 252–255, all the other basic VRP variants are derived from it. So, what exactly would be considered irrelevant features in the backbone?\n\n4. Figure 3 is quite surprising, as it doesn't indicate which activation function performs best in general. Do you have any reasonable explanation for why sigmoid works well with CaDa but completely fails with RF? This is somewhat concerning, as it appears that a universal solution for the activation function does not exist and is dependent on the architecture, which reduces the generality of your method. \n\n5. Have you considered applying the same mechanism to a unified NCO solver beyond routing problems? For such a truly universal solver, there is no clear backbone that can serve as a basis for other variants. Is it possible to apply this method to problems with no common intersection between states? This seems like a real limitation when it comes to extending this work to more general cases.", "limitations": "The motivation for this work comes from making a unified model for solving vehicle routing problems, and the proposed solution is tailored to this class of CO problems. The approach does not seem easily extendable to other classes of CO problems or capable of making significant progress toward a foundation model for CO.\n\nThis appears to be a major limitation, as the work does not open new directions toward that goal - one that seems to be a key future milestone for the NCO research community.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- Unlike other similar works, this approach pretrains the model on a single task (CVRP) and then fine-tunes it on other VRP tasks with new problem attributes.\n- The proposed State-Decomposable MDP framework is architecture-independent and can be applied to any multi-task NCO solver for VRPs.\n- Experiments show that the proposed method clearly improves upon existing state-of-the-art multi-task vehicle routing NCO solvers.\n\nWeaknesses:\n- The proposed method is applicable when all tasks share a common intersection; otherwise, maintaining a shared backbone seems impossible.", "was_revised": true, "final_justification": "This is a technically solid paper, with some original ideas and potential for future work, but it is limited to multi-task VRPs. In my opinion, considering the current state-of-the-art in NCO models - many of which already focus on this area - this topic has a rather narrow research interest.\n\nTherefore, I will maintain my initial score of weak acceptance.", "rebuttal": "We sincerely thank you for your insightful comments and thoughtful questions regarding our work. We appreciate the opportunity to address your concerns and clarify any potential misunderstandings.\n\n**Weakness 1: applicability to other problems**\n\nWe would like to clarify that our work specifically targets the multi-task VRP setting, which reflects a more practical demand in real-world applications. We believe that exploring the extension of our work represents a promising avenue for future research, but they are not the central objective of this work. From the broader perspective of multi-task learning, tasks solved simultaneously by a multi-task model are generally assumed to share underlying structures. This shared structure naturally implies the existence of interactions among tasks, which forms the foundation for positive knowledge transfer. To extend our work, one plausible approach would be to define a set of basis tasks, from which all target tasks can be derived. To illustrate this potential extension beyond multi-task VRPs, we can consider a simple example in the robotics domain. Suppose the goal is to learn a robot policy for washing a cup. The basis tasks might include picking up the cup, filling it with water, and using a cloth to clean it. Notably, the tasks of picking up the cup and filling it with water could also be components of another task, such as watering plants. This example demonstrates the potential of our framework to generalize to broader multi-task learning scenarios.\n\n**Question 1: VRP variant details**\n\nDue to page limitations, we have included detailed descriptions of the VRP variants in the **Appendix**. To clarify, the 0-th basis VRP variant corresponds to the classic CVRP with capacity constraints. The remaining four basis VRP variants are derived by adding one additional constraint to CVRP: open route, backhaul, duration limit, and time window, resulting in OVRP, VRPB, VRPL, and VRPTW, respectively. Specifically, we denote the basis state 0 as $s^{(0)}$, which represents the state of the classic CVRP. The basis state 1, $s^{(1)}$, is a binary variable to indicate whether a vehicle needs to return to the depot. Since OVRP extends CVRP by introducing an open-route constraint, its state consists of both $s^{(0)}$ and $s^{(1)}$. Similarly, basis state 2, $s^{(2)}$, is used in VRPB to represent backhaul demands and remaining backhaul capacity. The state of VRPB includes both $s^{(0)}$ and $s^{(2)}$. Basis state 3, $s^{(3)}$, is used in VRPL to encode the duration limit of a subtour and the current traveled length along the present subtour; thus, the state of VRPL consists of $s^{(0)}$ and $s^{(3)}$. Finally, basis state 4, $s^{(4)}$, is used in VRPTW to represent time windows, service durations, and the current time, making the state of VRPTW a combination of $s^{(0)}$ and $s^{(4)}$. Thus, in each VRP variant, the basis state $s^{(0)}$ is always present, as each variant is derived by adding at least one additional constraint, open route, backhaul, duration limit, or time window, to the classic CVRP.\n\n**Question 2: linear task-specific experts**\n\nWe appreciate the reviewer's insightful suggestion to investigate linear task-specific experts as an alternative. To explore it, we designed an experiment where the basis VRP solvers for OVRP, VRPB, VRPL, and VRPTW are trained using linear adapters. These linear adapters are then integrated into the unified solver to enable reuse. We implemented this experiment on the MoSES(RF) model under the setting of $N=50$. The experimental results are presented below. We observe that the proposed linear expert contributes to performance improvement. We sincerely appreciate this insightful suggestion. Although our network avoids the heavy computational costs typical of LLMs, we use LoRA adapters to explore whether popular LLM techniques can benefit neural solvers for VRPs. Early research has begun applying large models to this area, and our use of LoRA in a smaller model may still yield valuable insights and help pave the way for future large-scale applications.\n\n| VRP Variant | LoRA expert | Linear expert |\n|-------------|----------------------|-------------------|\n| CVRP        | 0.900%  | 0.878%  |\n| VRPTW       | 1.445%  | 1.427%  |\n| OVRP        | 1.892%  | 1.808%  |\n| VRPL        | 1.089%  | 1.061%  |\n| VRPB        | 2.342%  | 2.217%  |\n| OVRPTW      | 0.959%  | 0.938%  |\n| VRPBL       | 3.185%  | 2.960%  |\n| VRPBLTW     | 1.370%  | 1.431%  |\n| VRPBTW      | 1.121%  | 1.145%  |\n| VRPLTW      | 1.811%  | 1.845%  |\n| OVRPB       | 1.979%  | 1.764%  |\n| OVRPBL      | 2.014%  | 1.775%  |\n| OVRPBLTW    | 0.791%  | 0.783%  |\n| OVRPBTW     | 0.783%  | 0.778%  |\n| OVRPL       | 1.917%  | 1.819%  |\n| OVRPLTW     | 0.962%  | 0.943%  |\n| **Average** | **1.535%** | **1.473%** |\n\n**Question 3: Gated-LoRA**\n\nGated-LoRA is used to train adapters for the basis VRP variants. During the fine-tuning of each specialized LoRA adapter, the backbone model, pretrained on CVRP, is frozen, and only the LoRA adapter is updated. Importantly, the problem instances from these basis VRP variants are not seen by the backbone model during its training, as it was trained exclusively on CVRP instances. Each layer in the backbone model must process not only features of the CVRP state but also features of the additional constraints of the new variant. This mismatch can lead to the generation of task-misaligned features by the frozen backbone.We thus introduce a gating function into the backbone layers. Empirical results shown in **Figures 2(a) and 2(b)** demonstrate the effectiveness of the Gated-LoRA design.\n\n**Question 4: activation function**\n\nWe believe **Figure 9 in the Appendix** helps address this concern, as it provides a behavioral analysis of the gating functions. In Figure 9, we plot the scores assigned by the gating function to each basis solver (LoRA expert). Before addressing the concern, we would like to emphasize that RF is a Transformer-based solver, while CaDA uses two parallel Transformer blocks in each layer. This more complex design gives CaDA stronger capacity. The four basis solvers adapted from RF tend to specialize in their respective VRP variants and may not generalize well to others. In contrast, CaDA-based basis solvers, due to CaDA’s stronger capacity, may generalize better across different basis VRP variants. Figure 9(a) shows that MoSES(RF), using L1-normalized softplus as its activation function, tends to assign high scores to relevant basis solvers while keeping scores low for irrelevant ones. Figure 9(b) shows that MoSES(CaDA), using sigmoid as its activation function, also prioritizes relevant solvers but assigns moderately higher scores to less relevant ones. This suggests that MoSES(CaDA) recognizes that even task-irrelevant solvers may still provide useful insights for solving the current VRP variant.\n\nFurthermore, we would like to clarify that the gating function serves as the implementation of the mixture function of LS-SDMDP. Therefore, it is entirely reasonable to have different implementations of the mixture function, and different activation functions simply reflect different design choices. Importantly, our goal is not to identify a universal activation function for all network. Since different network possess varying capacities, they naturally require different activation function designs to align with their inherent characteristics. It is common that different models often benefit from tailored activation functions. Moreover, in LLM, exploring different activation functions in gating function remains an active research direction. We believe that the choice of activation function should be guided by the architecture's design and capacity.\n\n**Question 5: application beyond VRP**\n\nOur current focus is on advancing toward a unified solver for multi-task VRPs. We believe that extending our framework to other CO problems is a promising and long-term direction for future research. To support such an extension, we would like to share a preliminary idea. First, CO problems could be grouped based on structural similarities, allowing tasks within each group to benefit from shared structure. Then, a representative basis task could be selected from each group, forming a set of basis tasks across groups. A shared backbone model could be trained on these selected tasks. This backbone would serve as a common foundation for each group, and adapter modules, along with their compositions, could be integrated into it. Although this idea has not yet been validated, and our current work is specifically designed for multi-task VRPs, we believe it offers a feasible path toward building a unified solver for broader CO domains.\n\n**Limitation: transferability to other problems**\n\nFirstly, we would like to emphasize that our framework is specifically designed for the multi-task VRP domain, which has a wide range of practical applications. Extending it to more general CO scenarios represents a promising and long-term research direction. Then, as illustrated in the robotics example mentioned in \"Weakness 1,\" the observation that certain tasks can be derived from a shared set of basis tasks is common in practice. While this may not cover all real-world scenarios, it does encompass a broad spectrum of applications, further highlighting the potential of our framework to be extended beyond multi-task VRPs to more general and practical domains. Finally, based on the preliminary idea we shared in \"Question 5,\" our work offers a feasible path toward generalizing to broader CO problems. This direction could further demonstrate the value and adaptability of our framework.\n\nWe sincerely appreciate the reviewer's insightful comments and constructive feedback, which have helped us strengthen both the technical presentation and conceptual clarity of our work. We will revise our manuscript accordingly to address your suggestions and ensure greater clarity."}, {"review_id": "h3VPPx0rZ8", "reviewer": "Reviewer_jY9o", "summary": "This paper proposes the State-Decomposable Markov Decision Process(SDMDP) to solve the multi-task vehicle routing problem(VRP). It decomposes the state of the problem into a combination of multiple basic state Spaces and combines the Mixture of Specialized Experts(MoSE) to solve the VRP problem and various VRP variants.", "questions": "1.Could you provide the specific expressions and answers of the SDMDP you proposed in the VRPTW and Generalized TSP problems? If there is not enough space for you, please answer the first one.\n2.Could you provide comparative experiments for more larger-scale problems?\n3.What are the reasons and usages for setting these two assumptions?", "limitations": "The increase in the time cost of MoSES is really too large. It is very important to consider how to maintain the effect while reducing the time cost.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1, The SDMDP proposed in this paper fundamentally provides a unified expression of the variants of the VRP problem, which ensures that the proposed method can solve multiple variants of VRP.\n2.The effectiveness of up to 16 VRP variants was verified, demonstrating the universality of the proposed model. \n3.The proposed MoSEs can be applied to a variety of models, Meanwhile, the calculation method of hyperparameters is given.\nWeaknesses:\n1, The full text only presents the form of SDMDP, which might make it difficult for readers to understand why your SDMDP can summarize the variants of VRP. Maybe you can add specific examples at appropriate positions and explain how to construct its MDP using your model.\n2.At the experimental results level, the model with MoSES took more than twice as long as the model without MoSES to achieve an absolute Gap decrease of less than 0.4\\% on average and a relative decrease ranging from 1/10 to 1/4. It seems that the extent of performance optimization is not necessarily worth using. Perhaps expanding the scale of the problem would be more persuasive.\n3.You didn't provide in the main text how to prove Theorem 1 and Theorem 2. If you prove it in the appendix, providing guidance seems to be a better solution. Besides, the reasons for setting these two assumptions are also unclear. I'm not quite clear about what the functions of these two assumptions are respectively?\n            \nOverall, I think the proposal of SDMDP and LS-SDMDP is interesting and inspiring, but the effect of MoSES is not ideal, which limits the contribution of this article.", "was_revised": true, "final_justification": "Since the concerns have been addressed, I decide to raise my score.", "rebuttal": "We sincerely appreciate the reviewers’ insightful comments and constructive feedback on our work. We would like to take this opportunity to address your concerns and clarify any potential misunderstandings.\n\n**Weakness 1: example of SDMDP**\n\nWe sincerely apologize that, due to page limitations, we were unable to include an example to help readers better understand how SDMDP can be used to unify VRP variants.  Under SDMDP, there are five types of basic state spaces: $\\mathcal{S}^{(0)}, \\ldots, \\mathcal{S}^{(4)}$. $\\mathcal{S}^{(0)}$ encodes node coordinates, linehaul demands, and remaining linehaul capacity, $\\mathcal{S}^{(1)}$ represents a binary variable indicating whether the vehicle needs to return to the depot; $\\mathcal{S}^{(2)}$ captures backhaul demands and remaining backhaul capacity; $\\mathcal{S}^{(3)}$ includes the duration limit and the current traveled length of the subtour; and $\\mathcal{S}^{(4)}$ contains time windows, service times, and the current time. Before each episode begins, the initial state space is constructed by selecting $\\mathcal{S}^{(0)}$ and any subset of the remaining basis states. In this example, we choose $\\mathcal{S}^{(0)}$, $\\mathcal{S}^{(3)}$ and $\\mathcal{S}^{(4)}$, which correspond to the VRP with limited duration and time windows (VRPLTW). At each time step, the policy observes the basis states $s^{(0)}$, $s^{(3)}$, and $s^{(4)}$, and a masking mechanism is applied to filter out infeasible nodes from unvisited nodes, specifically, those whose demands exceed the remaining linehaul capacity, those that would violate the duration limit, and those whose arrival time would exceed the end of their time window, from unvisited nodes. This results in a list of feasible nodes. Upon selection, the linehaul capacity, traveled length, and current time are updated accordingly, and the selected node is masked out for subsequent steps. Once a subtour is completed, the linehaul capacity is reset to its default value, the traveled length is reset to zero, and the current time is also reset to zero. This reset reflects the assumption in VRP that multiple vehicles can begin their routes concurrently.\n\n**Weakness 2: empirical improvement**\n\nWe would like to clarify that the empirical improvements achieved by our method are sufficiently favorable, and it is well-recognized in the multi-task VRP literature that achieving even small improvements across all 16 tasks is highly challenging. In terms of average optimality gap, MoSES(RF) achieves 1.535\\% compared to RF-TE’s 2.063\\% for $N=50$, and 2.782\\% compared to RF-TE’s 3.125\\% for $N=100$. MoSES(CaDA) achieves 1.515\\% versus CaDA’s 1.715\\% for $N=50$, and 2.631\\% versus CaDA’s 2.766\\% for $N=100$. In the context of multi-task VRP for both $N=50$ and $N=100$, the optimality gap is already small in magnitude; therefore, the absolute decreases achieved by MoSES(RF), 0.528\\% for $N=50$ and 0.343\\% for $N=100$, and by MoSES(CaDA), 0.200\\% for $N=50$ and 0.135\\% for $N=100$, already represent noticeable improvements. Thus, to fairly and appropriately evaluate the improvement when the evaluation score is of small magnitude, relative improvement over the baseline method is a more suitable metric. MoSES(RF) achieves relative performance improvements of 25.6\\% and 11.0\\% over its baseline for $N=50$ and $N=100$. MoSES(CaDA) achieves relative improvements of 11.7\\% and 4.9\\% over its baseline for $N=50$ and $N=100$. Thus, based on this clarification, we believe the empirical performance of our method is substantially favorable compared to prior baseline methods, thereby demonstrating a noticeable empirical contribution.\n\n**Weakness 3: theorem proofs and assumptions**\n\nWe sincerely apologize for the inconvenience caused by the omission of detailed theorem proofs in the main text due to page limitations. As noted in the remark following Theorem 2, the proofs are included in **the Appendix**. In the revised version, we will provide clearer guidance for each theorem to explicitly indicate that the corresponding proofs can be found in the Appendix. We also apologize for the confusion arising from the use of the two assumptions. Please refer to our responses in **Question 3**.\n\n**Question 1: SDMDP expressions**\n\nTo formulate VRPTW using SDMDP, we first define the basis state spaces. Please refer to our responses in **Weakness 1** for the definitions. Before each episode begins, the initial state space is constructed by selecting $\\mathcal{S}^{(0)}$ and $\\mathcal{S}^{(4)}$, which correspond to the VRP with time windows (VRPTW). At each time step, the policy observes the basis states $s^{(0)}$ and $s^{(4)}$, and a masking mechanism is applied to filter out infeasible nodes from the set of unvisited nodes, specifically, those whose demands exceed the remaining linehaul capacity and those whose arrival time would exceed the end of their time window. This results in a list of feasible nodes. Upon selection, the linehaul capacity and current time are updated accordingly, and the selected node is masked out. Once a subtour is completed, the linehaul capacity is reset to its default value, and the current time is reset to zero.\n\nTo formulate the Generalized TSP (GTSP) using SDMDP, we need to make adjustments to the formulation presented in our paper, as our work uses CVRP as the basis VRP variant from which other variants are derived by adding constraints. For GTSP, the basis state space $\\mathcal{S}^{(0)}$ is associated with node coordinates, while each additional constraint is represented by one of the basis state spaces $\\mathcal{S}^{(1)}, \\ldots, \\mathcal{S}^{(5)}$, resulting in six basis state spaces in total. Before each episode begins, the initial state space is constructed by selecting only $\\mathcal{S}^{(0)}$. At each time step, the policy observes the basis state $\\mathcal{s}^{(0)}$ and selects one unvisited node from the currently active node groups. Upon selection, the chosen node and all other nodes in the same group are masked out for subsequent steps.\n\n**Question 2: large-scale problems**\n\nWe would like to emphasize that multi-task VRP is already a highly challenging problem due to the need to address multiple types of VRP variants simultaneously. As a result, current research, including the baseline methods used in our work, primarily focuses on small-scale problem instances. This is a common and necessary step in combinatorial optimization, where improving performance on small-scale problems often serves as a foundation for developing more advanced methods capable of handling large-scale instances. Therefore, the primary focus of our paper remains on solving multi-task VRPs effectively. The extension to large-scale scenarios is an important direction, but we consider it future work.\n\nTo demonstrate the generalization capability of our method, we also evaluate it on larger problem instances with up to 1,000 nodes from the CVRPLIB dataset, as presented in the Appendix. In this setting, both MoSES(RF) and MoSES(CaDA) outperform their baselines. In the table below, we present a performance comparison on large-scale problem instances from CVRPLIB. For large-scale instances with 501<N≤1001, MoSES(CaDA) achieves an absolute decrease of 1.385% compared to CaDA. While MoSES(RF) shows a smaller absolute decrease of 0.744% compared to RF, this result is still acceptable when considering that RF itself achieves an absolute decrease of 0.935% compared to its baseline RF-POMO.\n\n| graph size | RF-POMO |RF-TE | CaDA | MoSES(RF) | MoSES(CaDA) |\n|----------  |---------|---------|---------|---------|---------|\n|N<251       |5.905%|5.061% |  4.772% | 4.789% | 4.724% |\n|251<=N<501  |8.339%|8.107% |  8.889% | 7.741% | 7.948% |\n|501<N<=1001 |13.188%|12.253%|  14.199%|11.509% |12.814% |\n|Average     |9.108%|8.428% |   9.230%|7.973%  |8.441%  |\n\n**Questions 3: assumptions**\n\nBoth assumptions are critical for Theorem 2, which guarantees that LS-SDMDP exactly recovers SDMDP’s optimal policy when the assumptions hold. Assumption 1 ensures policy decomposition and mixture function existence, aligning with LS-SDMDP’s structure, while Assumption 2 enforces a unique state-to-embedding mapping, necessary for the theorem’s validity. Together, they provide the theoretical foundation for policy recovery.\n\n**Limitation: time overhead**\n\nIn terms of the average total time overhead for 1,000 problem instances across 16 tasks, MoSES(RF) requires 5.8s compared to RF’s 2.0s for $N=50$, and 20.8s compared to RF’s 8.4s for $N=100$. MoSES(CaDA) requires 7.4s compared to CaDA’s 2.3s for $N=50$, and 24.8s compared to CaDA’s 10.5s for $N=100$. We would like to emphasize that this time overhead is the total time for 1,000 instances per task; the amortized time per instance remains at the microsecond level for both MoSES(RF) and MoSES(CaDA). In the VRP domain, it is generally acceptable to increase inference time for better solution quality within a given time budget. In practice, many industrial CO tasks allow for extended times to obtain high-quality solutions [1]. Thus, several SOTA VRP methods [2,3] commonly use search-based method or solution refinement. Compared to the time increase introduced by such techniques, the additional overhead from the network architecture changes is relatively minor. We thus believe that the increased time overhead is acceptable given the favorable empirical improvements and may not be a major concern in practical applications.\n\n\n[1] Simulation-guided Beam Search for Neural Combinatorial Optimization, NeurIPS 2022.\n\n[2] BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization, NeurIPS 2023.\n\n[3] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization, NeurIPS 2023.\n\nWe sincerely thank the reviewer for the insightful comments and constructive feedback, which have greatly improved conceptual clarity of our work. We will revise the manuscript accordingly to enhance clarity and address all suggestions."}]

Author rebuttal:

Meta-review: This paper introduces the State-Decomposable MDP (SDMDP) and the Mixture-of-Specialized-Experts Solver (MoSES) to address multi-task VRPs. The formulation enables policy reuse across basis VRP variants, and the empirical evaluation over 16 tasks shows consistent improvements compared to strong baselines, supported by ablation studies and larger-scale tests. While reviewers noted concerns about runtime overhead and limited exploration beyond VRPs, the authors provided convincing clarifications that the inference cost remains acceptable and the framework offers a solid foundation for future extensions. Overall, the paper is theoretically sound, original, and demonstrates meaningful impact on multi-task combinatorial optimization.
Decision: Accept (poster)