Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP

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.

Weakness 1: example of SDMDP

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

Weakness 2: empirical improvement

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

Weakness 3: theorem proofs and assumptions

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

Question 1: SDMDP expressions

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

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

Question 2: large-scale problems

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.

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

Questions 3: assumptions

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

Limitation: time overhead

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

[1] Simulation-guided Beam Search for Neural Combinatorial Optimization, NeurIPS 2022.

[2] BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization, NeurIPS 2023.

[3] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization, NeurIPS 2023.

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

As we approach the end of the Reviewer–Author Discussion phase, we would like to confirm whether our responses have sufficiently addressed your concerns and questions. If you have any remaining questions or need further clarification, we remain actively engaged and are happy to provide additional explanations. If we have addressed your concerns, we would be grateful if you could kindly consider adjusting the rating of our paper.

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.

Weakness 1: applicability to other problems

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

Question 1: VRP variant details

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

Question 2: linear task-specific experts

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

Question 3: Gated-LoRA

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

Question 4: activation function

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

Furthermore, 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.

Question 5: application beyond VRP

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

Limitation: transferability to other problems

Firstly, 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.

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

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.

Weakness 1： performance and time overhead

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

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

[1] Simulation-guided Beam Search for Neural Combinatorial Optimization, NeurIPS 2022.

[2] BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization, NeurIPS 2023.

[3] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization, NeurIPS 2023.

Weakness 2: gating mechanism

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

Weakness 3: transferability to other domains

Firstly, 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.

Question 1: task descriptors

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

Question 2: robustness to poorly trained basis solver

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

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

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.

Weakness 1: assumptions

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

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

Weakness 2: OOD evaluation

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

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

[2] Simulation-guided Beam Search for Neural Combinatorial Optimization, NeurIPS 2022.

[3] BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization, NeurIPS 2023.

[4] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization, NeurIPS 2023.

Question 1: data augmentation

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

Additionally, 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.

Question 2: expert interaction

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

Question 3: frozen and trainable experts

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

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