CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention

Thank you very much for your time and effort in reviewing our work. We are very glad to know you find the paper is well-structured and easy to follow. We address your concerns as follows.

E1. Prompt Ablation Study

To address your concern, we conduct the ablation study on adding prompt to both branches. The results below confirm that CaDA’s design (prompt on the global branch) achieves optimal performance:

W1,Q1. Explanation about Sparse Branch: The motivation and function of the key components, e.g., the sparse branch,need further explaination. In the proposed method, the sparse branch is introduced to focus on "more related node pairs." Could you clarify why this is important?

The sparse branch is introduced to enhance the sequential decoding process in VRP by addressing the limitations of standard attention. In VRP, selecting the next node from a small subset of nearby nodes is crucial, but standard attention assigns nonzero scores to all node pairs, diluting focus on critical decisions. The sparse branch employs Top-k sparse attention, allowing the model to concentrate on the most promising candidates based on learnable attention scores, rather than just Euclidean distances. This enables the model to automatically identify and focus on highly relevant node pairs, improving decision-making. We will add the discussion into the revised manuscript.

W2,Q2. Fine-Tune Performance

Thank you for your valuable comment. As suggested, we conduct fine-tuning experiments, and due to the character limit, please refer to our response in E1 & Q2 to reviewer KzHG for experimental results. In summary, CaDA achieved the best zero-shot performance on two new constraints. After the first fine-tuning epoch, CaDA's gap reduced by 72% on Multi-Depot tasks (compared to 61–66% for baselines), demonstrating strong generalization capabilities.

C1. Clarification on Sparse Branch Data Flow

The final outputs of the sparse branch are fused with those of the global branch through a fusion layer. The data from the sparse branch flows into the final node embedding $H^{(L)}$. We will revise Figure 2 to clarify this data flow.

C2, C4, C7, C8: The formula in line 270, The explanations for Figures 5(a) and 5(b), "Kernel density estimation (KDE)" in lines 394 and 490, Equation (19) in line 758.

We appreciate your careful review. We will revise them accordingly in the revised manuscript.

C3. Clarification on Runtime Comparisons

1)While all neural solvers show comparable runtime performance, our key contribution is enhanced solution quality, not runtime reduction. 2) For HGS-PyVRP and OR-Tools, we set maximum runtimes (10s for VRP50, 20s for VRP100) following RF-TE (Berto et al., 2024), resulting in similar overall runtimes.

C5, C6. Top-k Gap Values and Top-k Parameter Range

As suggested, the table below provides the specific average gaps for Figure 6, along with additional ablation studies using a wider range of $k$ values. We will include the following table in the revised manuscript:

Q3. Explantion about Ablation Study

Thank you for your question. Here we further explain the role of the sparse branch.

• As detailed in our responses to W1 and Q1, sparse attention is beneficial for addressing the limitations of standard attention mechanisms when solving VRPs.
• Additionally, our visualization (see Figure 4 in PDF) shows that CaDA without Sparse exhibits dispersed attention, making it difficult to focus on relevant information, whereas CaDA effectively concentrates attention on key nodes, which aligns with its better performance.

Q4. Paper to be Cited

Thank you for your feedback. We will add this paper (UniCO, ICLR 2025) in the revised manuscript.

Q5. Explantion about Ablation Study

Thank you for raising this point. For constraints "O", "B", and "L", it is challenging for the encoder w/o prompt to distinguish whether these constraints are "on" or "off" for a given problem instance. This is because instances with or without these constraints share identical input structures.

Consequently, the encoder cannot infer which specific problem variant it is solving, leading to suboptimal node embeddings. The introduction of task-specific prompts addresses this limitation, thereby significantly improving performance.

Thank you for your thoughtful review of our manuscript. We are pleased to hear that you found the paper to be well-written and clear. Below, we address your concerns and questions point by point.

E1, Q2. Generalization Capability

Thank you for raising this valuable point. We conduct experiments to evaluate zero-shot and fine-tuning performance on two unseen constraints.

Unseen Constraints:

1. Multi-Depot (MD), vehicles can start from any depot but must return to their respective starting depot. The evaluation includes 16 VRPs.
2. Mixed Backhaul (MB), linehaul and backhaul customers can be mixed along a route. The evaluation includes 8 VRPs.

Results:

1. Zero-Shot: Given the relatively poor zero-shot performance across all evaluated models, generalization to the MD constraint appears to be more challenging. For MD, CaDA achieves a gap of 39.34% (vs. 41.93–45.56% for other baselines); for MB, 8.46% (vs. 8.74–9.28%).

2. Fine-Tuning: After the first epoch, CaDA’s gap reduces by 72% (39.34% $\to$ 11.01%), outperforming baselines’ improvements of 61–66% .

We will add the results and discussion into the revised manucript.

C1,Q1.Training Process Clarification

1. Mixed Batch Training: Yes, we employ this to stabilize convergence.
2. Reward Normalization: No reward normalization is applied.

We will include these explanations in Section 4 of the revised manuscript.

C2. Discussion of Model Sizes

MvMoE has the largest model size(3.7M), followed by CaDA(3.4M), RF-TE(1.7M), and MTPOMO(1.3M). We will add this result to the Appendix of the revised manuscript.

C3. Hyperparameters Clarification

Yes, we confirm that for each baseline, the hyperparameters suggested by its authors were used.

C4. Ablation Study About Sparse Branch

We respectfully clarify that:

• In our paper, CaDA w/o Sparse retains the two-branch structure, but both use global attention.

• The sparse attention consistently improved performance across all 16 VRPs (0.003–0.209%, see Figure 4).

• The sparse attention yields notable gains on variants such as VRPBL (0.209%), OVRP (0.173%), OVRPL (0.163%).

C5. Removing the Global Branch

Thank you for your suggestion. We conduct ablation experiments (GA denotes global attention and SA denotes sparse attention) which show that the dual-branch model outperforms its single-branch version, and optimal performance is achieved by integrating both global and sparse attention, as in CaDA.

C6. Comparison of k = N/2 and N/4

N/2 has better results than N/4. However, choosing N/4 could result in reduced computational costs. We will include this discussion in the Section 4.4 of the revised manuscript.

C7. CaDA$\times$32 on 16 VRPs

Thank you for this valuable point. Below, we provide the performance results of CaDA $\times 32$ on the 16 VRPs , which further improves the performance.

R1. References to be Discussed

Thank you for your valuable suggestion. We will incorporate the papers in the revised paper. Gao et al. (2023) propose global and local policies for CVRP and TSP, defining "local" by Euclidean distance. Fang et al. (2024) suggest learning from multiple nested local views, both focusing on generalization across distributions and scales. In contrast, CaDA addresses 16 VRP variants using a learnable mechanism (Top-k sparse attention) to dynamically select related nodes based on attention scores.

W1: In (1), \tau_t may be a partial sub-tour.

W3: In (14), should it be H_c^{(L)}? W_t should be W_c?

W4: Below (16), what is the index g of \pi_g? u should be bolded.

Thank you very much for your careful checks. We will correct these notational issues as follows:

• W1: Yes. We will correct K in (1) to K_t, where K_t denotes the number of sub-tours up to the current step.
• W3: The H_c in (14) is correct. We will correct H_c^{(L)} to H_c in (15). Yes, it should be W_c.
• W4: Below (16), the g should be t. We will bold u.

W2. LayerNorm and SwiGLU Design

Thank you for the feedback. Below we clarify these design choices:

• LayerNorm in (5): Since the first MLP layer's outputs vary in scale across VRPs (e.g., OVRPBLTW yields larger-scale embeddings due to more active constraints), we apply instance-level LayerNorm to normalize inputs to the second MLP.
• SwiGLU: Following Berto et al. (2024), we use SwiGLU to improve convergence.

Thank you very much for your time and effort in reviewing our work. We are very glad to know that you find our proposed method efficient and interesting. We address your concerns as follows.

W1&Q1. Results on Other Distribution

Thank you for raising this point. To evaluate cross-distribution generalization, we conduct additional experiments using the six distributions from [1]. The results below show that CaDA consistently outperforms all baselines across all distributions.

W2. Code Availability

Thank you for your feedback. We confirm that the code will be made public immediately upon the paper's acceptance, with a link provided in the final version.

C1-C3: Some symbols are confusing, V in line 163, H_c^{(L)} in line 261.

Thank you very much for your careful review. We will revise our notation accordingly: 1) Use distinct symbols to clearly differentiate between sub-solutions and complete solutions. 2) Change the notation from $V$ to $v$ to represent vectors. 3) Correct the symbol $H_c^{(L)}$ to $H_c$ in line 261.

Q2. Explanation of Attention Distributions: Could you further explain Figure 7? Why does CaDA w/o the prompt show the same attention distribution for CVRP and OVRP?

Thank you for raising this point. When no task-specific prompt is provided, the encoder cannot distinguish between CVRP and OVRP instances, because both variants share identical input structures ($\mathcal{V} = \{v_i\}_{i=1}^{N}$, where $v_i = \{\vec{X}_i, A_i\}$ and $A_i = \{\delta_i\}$) , with values sampled from the same distribution. This limitation leads the encoder to view instances of different variants as the same and process them with the same attention patterns.

Q3. Clarification of Implementation

In the "Different Sparse Functions" section, "Softmax+Top-$k$" refers to the computation of sparse attention scores ${M}( \mathbf{A} )$ in Equation (11). This involves first calculating standard attention scores via Softmax, then applying a Top-$k$ selection operation to sparsify the scores. "A standard Softmax and α-entmax" indicates replacing the Top-$k$ operation with alternative methods (e.g., α-entmax). Both approaches produce sparse attention scores but differ in their sparsification mechanisms. We will clarify this explanation in the revised manuscript.

Q4. Training Settings

Problem variants are uniformly sampled from 16 VRPs during training (follow RouteFinder). Each batch contains a mix of variants. Therefore, each variant has roughly the same number of training instances. We will clarify this in the revised manuscript.

Q5.Explanation of Attention Distributions

Figure 8 exhibits symmetry: larger |P_ij| corresponds to lower attention scores. This is because for P_ij > 0, a larger |P_ij| implies that including edge (i,j) in the solution might result in longer waiting times. For P_ij < 0, a larger |P_ij| indicates a smaller l_j - e_i, and node v_j's time window likely precedes v_i's, making edge (j,i) inefficient due to longer waiting times. Overall, the larger the value of |P_ij|, the less likely the two nodes should be consecutive in the solution.

For cases where P_ij < 0 but |P_ij| is small, although (i,j) is illegal, (j,i) may remain feasible without excessive waiting time, so there are still many A_ij with high values.

Thank you for your time and effort in reviewing our manuscript. We are glad to know that you find our method innovative and it addresses potential weaknesses in existing methods, and the paper well written and well structured. Point-to-point responses to your concerns and questions are presented below. Some visualizations are provided in the PDF .

C1,E2,W3,S4,Q4. Computational Efficiency Analysis

We compare RF-TE (single-branch) with CaDA (dual-branch) on VRP200. CaDA remains efficient for 100+ instances. Since the encoder runs once while the decoder runs repeatedly (~100x longer), the dual-branch structure adds minimal overhead.

C2,E3,Q3. Generalization to Unseen Problems

We conduct a zero-shot and fine-tuning study (see E1, Q2 in KzHG for results), and CaDA achieves the best performance on two new constraints.

E1. Statistical Significance Testing

We conduct a one-sided Wilcoxon rank-sum test comparing CaDA with RF-TE, and the result confirms CaDA’s superiority with >95% confidence.

W1. How CaDA Addresses Limitations

We use prompt to enhance constraint awareness and a dual-branch model with global and sparse attention to better focus on key nodes.

Our additional ablation experiments on on the position of the prompt (E1 to 9jwN) and global-sparse fusion (C1 to KzHG) confirm that our current integration is most effective. Moreover, attention visualizations (S3) show that sparse attention reduces dispersion.

W2. Actual Operational Settings

We validate our model on 64 real-world industrial insatnces from MTPOMO. The table shows the average objective values.

W4. Interaction Visualizations:

Figure 1 in the PDF illustrates the interaction mechanism: the prompt is concatenated with the initial node embeddings and fed into the global branch.

W5. How Attention Weights are Visualized

We randomly select 100 VRP50 instances and collect global branch attention scores from CaDA and CaDA w/o Prompt. For Figure 7, KDE and a heatmap are used. For Figure 8, a hexbin plot is used.

S1. Clarification of Parameters

The dimensions of these parameters are provided in line 194 of the manuscript, $W_a \in \mathbb{R}^{5 \times d_h}$, $b_a \in \mathbb{R}^{d_h}$, $W_b \in \mathbb{R}^{d_h \times d_h}$, and $b_b \in \mathbb{R}^{d_h}$.

S2. Discussion of Practical Significance

CaDA outperforms the second-best learning-based methods by 0.26% for VRP50 and 0.32% for VRP100. These differences could accumulate over numerous daily routes and long-term operations, resulting in reduced transportation costs.

S3. Ablation Visualizations for Sparse Attention

Thank you for your valuable suggestion. Figure 4 in the PDF shows the attention patterns: CaDA w/o Sparse exhibits dispersed attention, while CaDA effectively concentrates its attention on fewer nodes, aligning with its performance gains.

S5. Qualitative Analysis of Real-World Solutions

We provide a qualitative analysis in Figure 3 of the PDF, which shows that CaDA's solution is more similar to the best-known solution.

S6 Standardization of Formatting and Grammar

Thank you for your suggestion. We will review the entire manuscript and standardize the formatting and grammar in the mentioned sections.

Q1. Design of the MLP in the Prompt

1. The multi-hot vector (dimension 5) must be projected to match the node embedding dimension. An MLP achieves this effectively. And MLPs are commonly used as prompt generators.
2. Ablation tests show that MLP modifications result in slight performance drops, the current design performs best.

Q2. Fusion Strategy Design

Thank you for your question. Our fusion strategy in CaDA follows classical multi-branch architectures in computer vision. We test two alternatives：Concat and Cross-Attention. Our current design yielded the best performance.

Q5. Systematic Interpretation of Attention Patterns

The attention analysis remains qualitative, but we acknowledge the need for systematic interpretation across VRPs and will highlight this as critical future work in the revision.

Q6. Sensitivity to k Parameter

Thank you for raising this point. We test a wider range of k (refer to C5,C6 for 9jwN for results), and the model's performance is robust to k.

Q7. Training Stability

No, the training of CaDA is stable. The loss curves for CaDA are shown in Figure 2 of the PDF.