CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
Authors: Han Li
Fei Liu
Zhi Zheng
Yu Zhang
Zhenkun Wang
Venue: ICML 2025 poster (2025)
Keywords: Vehicle Routing Problem
Multi-Task Learning
Task-Specific Prompt
Dual Attention Mechanism
Cross-Problem Learning
Primary area: optimization->discrete_and_combinatorial_optimization

Abstract: Vehicle routing problems (VRPs) are significant combinatorial optimization problems (COPs) holding substantial practical importance. Recently, neural combinatorial optimization (NCO), which involves training deep learning models on extensive data to learn vehicle routing heuristics, has emerged as a promising approach due to its efficiency and the reduced need for manual algorithm design. However, applying NCO across diverse real-world scenarios with various constraints necessitates cross-problem capabilities. Current cross-problem NCO methods for VRPs typically employ a constraint-unaware model, limiting their cross-problem performance. Furthermore, they rely solely on global connectivity, which fails to focus on key nodes and leads to inefficient representation learning. This paper introduces a \underline{C}onstraint-\underline{A}ware \underline{D}ual-\underline{A}ttention Model (CaDA), designed to address these limitations. CaDA incorporates a constraint prompt that efficiently represents different problem variants. Additionally, it features a dual-attention mechanism with a global branch for capturing broader graph-wide information and a sparse branch that selectively focuses on the key node connections. We comprehensively evaluate our model on 16 different VRPs and compare its performance against existing cross-problem VRP solvers. CaDA achieves state-of-the-art results across all tested VRPs. Our ablation study confirms that each component contributes to its cross-problem learning performance. The source code for CaDA is publicly available at \url{https://github.com/CIAM-Group/CaDA}.

CaDA: Cross-Problen Routing Solver with Constraint-Aware Dual-Attention
Han Li Fei Liu
Zhi Zheng'
Yu Zhang'
Zhenkun Wang'
Abstract
1. Introduction
Vehicle routing problems (VRPs) are signifi- cant combinatorial optimization problems (COPs) holding substantial practical importance. Re- cently, neural combinatorial optimization (NCO), which involves training deep learning models on extensive data to learn vehicle routing heuristics, has emerged as promising approach due to its efficiency and the reduced need for manual algo- rithm design. However, applying NCO across diverse real-world scenarios with various con- straints necessitates cross-problem capabilities. Current cross-problem NCO methods for VRPs typically employ constraint-unawar model, lim- iting their cros--problem performance. Further- more, they rely solely on global connectivity, which fails to focus on key nodes and leads to inefficient representation learning. This paper introduces a Constraint-Aware Dual-Attention Model (CaDA), designed to address these lim- itations. CaDA incorporates a constraint prompt that efficiently represents different problem vari- ants. Additionally, it features dual-attention mechanism with a global branch for capturing broader graph-wide information and a sparse branch that selectively focuses on the key node connections. We comprehensively evaluate our model 16 different VRPs and compare its per- formance against existing cross-prolee cross-problem VRP solvers. CaDA achieves state-of-the-ard results across all tested VRPs. Our ablation study con- firms that each component contributes to its cross- problem learning performance. The source code for CaDA is publicly available at https:// github. com/ CIAM-IIAMMMM Group/CaDA.
Vehicle routing problems (VRPs) involve optimizing trans- portation costs for a fleet of vehicles to meet all customers' demands while adhering to various constraints. Numer- ous studies have focused VRPs due to their extensive real-world applications in transportation, logistics, and man- ufacturing (Cattaruzza et al., 2017; Rodrigue, 2020). Tradi- tional methods for solving VRPs include exact solvers and heuristic methods. Exact solvers, however, struggle with the NP-hard nature of the problem, making them prohibitively expensive implement. On the other hand, heuristic meth- ods more cost-effective and provide near-optimal so- lutions but require significant expert input in their design, Recently, learning-based neural solvers have gained con- siderable attention and have been successfully applied to VRPs (Bengio et al., 2021; Kool et al., 2019; Bogyrbayeva et al., 2024; Berto et al., 2025). These solvers train networks to learn a heuristic, reducing the need for extensive manual algorithm design and minimizing computational overhead.
Despite the promising performance of neural solvers on VRPs, the majority of existing works require training a model for each type of routing problem (Kwon et al., 2020; Drori et al., 2020; Duan et al., 2020; Gao et al., 2020; Cap-
part et al., 2021: Zhao al., 2021; Kool et al., 2022: Tyas- nurita al., 2017; Berto al., 2024a). Given the diversity of real-world vehicle routing problems with varying con- straints (Tan & Yeh, 2021), developing distinct model for each routing problem is costly and hinders practical application.
To tackle this challenge, recent efforts have been made to develop cross- cross-problem learning methods that can solve mul- tiple VRPs with single model (Liu et al., 2024; Zhou et al., 2024a; Berto et al., 2024b; Lin et al., 2024). These cross- problem methods typically employ framework and are trained using reinforcement learning. For example, MTPOMO (Liu et al., 2024) jointly trains a unified model across five VRPs, each with one or two constraints, enabling zero-shot generalization to problems that feature combinations of these constraints. MVMoE (Zhou al., cexturre-ofexxpere (MoE) (Shazeer et al.,
encoder-decoder
"qqual contribution 'Guangdong Provincial Key Labora- tory of Fully Actuated System Control Theory and Technol- ogy. School of Automation and Intelligent Manufacturing, South- emn University of Science and Technology. Shenzhen, China 'Department of Computer Science, City University of Hong Kong, Hong Kong, China. Correspondence to: Zhenkun Wang <wangzhenkuns00@ gmm.i@@mmall.......
2024a) employs 2017) structure in the feed-forward layer of a transformer- based model to enhance its cross cross- pooss-problem learning capac- ity. Furthermore, RouteFinder (Berto et al., 2024b) directly
Proceedings of the 4 International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
trains and tests sixteen VRPs using proposed unified re- inforcement learning (RL) environment, which enables the simultaneous handling of different VRPs in the same train- ing batch. Additionally, RouteFinder leverages modern transformer-basee model structure (Dubey et al., 2024), along with global embeddings, to enhance performance.
Despite these advancemenss, existing cross prossee models remain unaware of constraints (Liu et al., 2024; Zhou al., 2024a; Berto et al., 2024b). As different constraints signifi- cantly alter the feasible solution space, this oversight notably limits the models' capabilities in cross cross-problem applications. Furthermore, existing methods employ a transformer en- coder which maintains global connectivity throughout the node encoding process, leading to the inclusion of irrelevant nodes and adversely affecting node representation.
(TW)
(B)
Depot
Linehaul
Backhaul
Feasible
route
windows
Time
Figure I. The feasible solutions for different VRP variants.
(0), backhaul (B), duration limit (L), and time window (TW). The illustrations of the constraints are presented in Figure 1. In this section, begin by outlining general definition of the VRP instance, then introduce the basic CVRP, and proceed to describe four additional constraints.
This study proposes novel Constraint-Awarc Dual- Attention Model (CaDA) to mitigate these challenges. Firstly, we introduce a constraint prompt to enhance the model's awareness of the activated constraints. Further- more, we propose a dual-attention mechanism consisting of a global branch and sparse branch. Since, in the encoder- decoder framework, node pairs with higher attention scores more likely to be adjacent in the solution, the sparse branch with Top-k sparse attention focuses on the more promising connections between these key node pairs. Mean- while, the global branch enhances the model's capacity by capturing information from the entire graph, ensuring that the solution informed globally. The effectiveness and su- periority of CaDA have been comprehensively demonstrated across 16 VRPs and real-world benchmarks.
A VRP instance 9 is a fully-connected graph defined by a set of nodes V = {wb: f1,-... UN} with the total number of nodes given by | N + 1, and edges & V V. Furthermore, U0 represents the depot, while {VI,..., uy represent the N customer nodes. Each node 2s V consists of the pair [X,, A. where X; ~ U 1)² represents the node coordinates, and A, denotes other attributes of the nodes. Additionally, the travel cost between different nodes is defined by their Euclidean distance, which is denoted by the cost matrix D {dr.5, = O..... N. = 0-..,N. N).
In CVRP, the depot node vo has Ag 0, and each cus- tomer node v; is associated with A; {d:}. where å; is the customer's demand at v that the fleet of vehicles must service. This fleet comprises homogeneous vehicles, each with a specific capacity C. Each vehicle leaves the depot uo- visits a subset of customers, and returns to the depot upon completion of deliveries. The solution to CVRP consists of the routes taken by all vehicles, i.e., {a ,,²2 : o ). where K is the total number of sub-routes. Each sub-route *² = (af of......".., ), h E {1, K}. where of is the index of the visited node at step and of t 0. n K
The contributions of this paper are as follows:
We introduce CaDA, an efficient cross- pooss-probem learn- ing method for VRPs that enhances model awareness of constraints and representation learning.
oh.,),
We propose a constraint prompt, which facilitates high- quality constraint-aware learning, and a dual-attention mechanism, which ensures the encoding process is both selectively focused and globally informed.
|oy| represents the number of nodes in it, and Σ n4 T is the total number of visit steps.
The basic CVRP could be easily extended to various VRPs by adding additional constraints. This study explores four additional constraints as discussed in recent studies (Liu et al., 2024; Zhou et al., 2024a; Berto et al., 2024b).
We conduct a comprehensive evaluation of CaDA across 16 VRP variants. CaDA achieves sfate-of-the- art (SOTA) performance, surpassing existing cross- problem learning methods. Additionally, our ablation study validates the effectiveness of both the constraint prompt and the dual-attention mechanism.
Open Route (0) In the OVRP, vehicles do not return to the depot to after completing their sub-route.
2. Preliminaries
Time Window (TW) This constraint requires that each node must be visited within a specific time window, such that each node A, = {6,, e, 4, s where e; is the earliest start time, I, is the latest permissible time, and s; represents the time taken to service this customer. The depot to has
2.1. Problem Definition
In this study, we focus on 16 VRP variants that encompass five different constraints, including capacity (C), open route
2

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
50 0, éq 0, and T. indicating that each sub-tour must be completed within time limit of T. Time window constraints are stringent; if vehicle arrives earlier than 6i, it must wait until the start of the window.
Where b(V) is the shared baseline function used to stabilize learning, r(-) is the reward function and is defined as the negative solution length, detailed in Appendix B.I.
For the structure of policy Ta, existing approaches primarily use transformer-based models.
Backhaul (B) Customers with 6; > O are linehaul cus- tomers, requiring vehicles to load goods at the depot and deliver them to their locations, while those with 6; < 0 are backhaul customers, where vehicles collect [6,] goods from customers and return them to the depot. While all customers in the standard CVRP are linchaul, the VRP with backhauls (VRPB) includes types of customers, and linehaul tasks must precede backhaul tasks to avoid reloading.
2.3. Transformer Layer
The Transformer (Vaswani et al., 2017) comprises multi- head attention layer (MHA) and a feed-forward layer (FFD). In some modern large language models (Chowdhery et al., 2023; Touvron et al., 2023; Naveed al., 2023), the FFD is replaced by gated linear units (GLUs), with detailed introduction to GLUs provided in the Appendix B.2.
Duration Limit (L) In this constraint, the depot vo has Ao = {p), where p is the length limit that each sub-tour must adhere
Attention Layer The classical attention function is:
Attention (X, Y) A (YWv),
2.2. Learning to Construct Solutions for VRPs
XWo(YWk) (3)
where A Softmax
vdl
The process of constructing solutions autoregressively (i.e., decoding) can be modeled as a Markov decision process (MDP), and the policy can be trained using RL methods. As the model sequentially expands each sub-route, for sim- plicity, at any decoding step i, represents the sequence of nodes visited up to that point:
where X E Raxd and Y E Rmaxd represent the input embeddings, The parameters Wo, WK E Rdxd, and Wy E Raxds are trainable matrices for the query, key, and value projections, respectively. After calculating the atten- tion matrix using the query and key matrices, the Sofımax function is applied independently across each row to nor- malize the attention scores. These scores are then rescaled by / /dk, resulting in the scaled attention score matrix A. The eventual output, denoted as Z, a matrix in Raxd.
:: = (Ti
xhe (TI, T2, .......77 Tt),
k=1
where V denotes the concatenation of sequences from dif- ferent sub-routes, K, denotes the number of sub-tours up to the current step. The MDP for the decoding step at time is defined in the Appendix B.I.
Additionally, for efficiency, the MHA projects into Ma. separate sets of queries, keys, and values, upon which the attention function is applied:
MHA(X, Y) Concat( Zi.... MM,,W, where Z: Attention, Y), Vi (1,.... Mr
Subsequently, policy no be optimized using RL methods to maximize the expected reward J. This study employs the REINFORCE algorithm (Williams, 1992) with a shared baseline proposed by Kwon et al. (2020), to update the pol- icy. Specifically, for VRP instance V. N trajectories are generated, starting with the first action {at, [a..af.... af................. .... aN which is always 0. Each of the N trajectories then assigns unique of the N customer nodes as the second point, The policy subse- quently samples actions for each trajectory until all have derived feasible solutions ,7, ,NJ. Finally, the gradient of the policy is approximated by:
(4)
where de = d, Mr in each Attention, W E dxdd x is learnable parameter. For self-attention we have Y = X.
3. Methodology
i.e., {a), og...., a²"} = (1, 2, 2...., .........
3.1. Overall Pipeline
As shown in Figure 2, CaDA follows the general cross- problem learning framework for VRPs which consists of two stages: encoding the instance V to node embeddings (L), and decoding construct solutions based on (L) sequentially. CaDA employs prompt to introduce con- straint information during the encoding process, so that the encoder can identify whether certain constraints are valid. In addition, CaDA utilizes a dual-attention mechanism. The sparse branch uses Top-k sparse attention to concentrate on the most promising adjacent node candidates. This enables
N
1
VoJ(0 V) [))
Σ
(r(7)) - (())((())))))))))) Log [V),
N
1
b'V)
r(T)) for all i.
N
3

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attcntion
Encoding
Decoding
(1) Constraint Prompt
1
Top-K Sparse Attention
Action selection
0
Prompt
Top-k selection
TW
1
p(t)
Softmax
I.
0
B
1
Decoder
Layer
Constraint tag V
Sparse branch f
h
(h) F2
Current node
H(a
H
Node embedding
Ag
Init node embedding
(VRPBTW) Input
p(o)
Loss calculation
Global branch fg
(2) Dual-Attention Model
Solution
Linear layer
Global attention layer
Sparse A ttention layer
Element-wisse Addition
SwiGLU layer
Matrix Multiplication
Action Probabilities
Figure 2. The pipeline of the proposed CaDA for VRPs. CaDA adopts the typical encoder-decoder framework and incorporates two components in the encoder: a dual-attention mechanism and a constraint prompt. The qual-attention mechanism comprises global branch with the standard Softmax function and sparse branch with Top-k selection operation.
the model to identify and focus on highly relevant node pairs based on learnable attention scores.
fuse information at the end of each layer.
Finally, the output from the global branch, H1(²) is used for autoregressive decoding, with the likelihood of node selection being primarily determined by the similarity of the nodes' embeddings.
3.2. Constraint Prompt
To generate prompts that carry the problem's constraint in- formation, we represent the problem as a multi-hot vec- tor V E RR,, corresponding to five distinet constraints. This multi-hot vector is subsequently processed through straightforward multi-layer perceptron (MLP) generate the prompts:
Global Layer Each layer involves an MHA (Vaswani et al., 2017) and SwiGLU (Shazeer, 2020), along with root mean square normalization (RMSNorm) (Zhang & Sennrich, 2019) and residual connections (He et al., 2016). Following Berto et al. (2024b), we employ SwiGLU and RMSNorm to improve convergence. The i-th layer is formulated as follows:
p(0) LayerNorm(VW.. + b.) + bb.
(5)
where Wa E 55xd, b, E Rd W, E xdx, and by E dd are learnable parameters. dn the node's embedding dimension. Then this prompt can be concatenated with the node embeddings.
i1 RMSNNrm (1f--1)+MHH MHA
(H Concat [ pl- 1))
(6)
3.3.
Mechanism
9 RMSNorm (A1 + (HT
(7)
The input instance V with |V| N + 1, is first transformed into high-dimensional initial node embeddings by a linear projection. The initial node embedding is denoted as (0) () [X++1)xd
p() RMSNorm (1) +
(lli-))CConatt Concat (1 pit-))) pli-
(8)
p()) = RRMSNOO (1) (pro) SWiGLU (PO))
(9)
Subsequently, (0) is concatenated with P(U) and processed through global branch fg. which consists of L layers. Each consists of standard MHA layer (Vaswani et al., 2017) and SwiGLU (Shazeer, 2020). The standard attention function with Softmax never allocates exactly zero weight to any node, thereby allowing each node access to the entire graph. Concurrently, to capture information from closely related nodes, a sparse branch denoted as f. with Top-k sparse attention layers is introduced. Both branches adaptively
where H E R[N+1)xd, represents the node embed- dings output from the 1))th global layer.
Sparse Layer In the sparse branch f., each layer also consists of an attention layer and a SwiGLU activation func- tion. However, to focus more precisely on related nodes, we replace the attention function Attention(::)) in MHA(,.)

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
with SparseAtt(:;)) -), which masks attention scores smaller than the Top-k scores by setting them zero. This can be formulated as follows:
233
2.45
3.9
3.7
1.07
22
2.29
3.64
g
2.0
0.3
3.39
SparseAtuX,, Y) Softmax (M(A)) vWv,
(10)
19
3.1
2.9
where A is the attention score calculated shown in Equa-
16
277
281
tion 3. M() is the Top-k selection operation:
1.5
25
MITOMO
ANMM
RF-1MM
Rf Mot
RE-E
C2D4
MTTOMO
MYsbf
nF RF-PoMO
RF-Met
RF-E
Cada
[M[)]] ( Aij
if Af Top-k(A..).
(11)
(a) Average gap of different
(b) Average gap of different
otherwise.
neural solvers on VRPs with 50 nodes.
neural solvers on VRPs with 100 nodes.
where A&. represents the attention scores of the i-th node with all other nodes, i.c., A₁ {Ai E {0, 10. }) and the Top-k operation selects the top lo highest attention scores from this set.
Figure 3. Comparison results of CaDA with SOTA cross- neural solvers, showing the average gap on 16 VRPs.
where is a predefined clipping hyperparameter. Finally, the action probabilities To( = V. - are obtained by applying the Softmax function to u fui Addi- tionally, the feasibility testing process for determining the set of feasible actions I, the current step detailed in Appendix B.3.
Fusion Layer In our model, a simple linear projection is applied at the end of each layer to transform embeddings between two branches. For the i-th layer, the outputs from the global and sparse branches are denoted as Hg and H respectively. The final outputs are given by:
g = H + ( W + b.). H H + ( W + by):
(12)
4. Experiments
(13)
To evaluate the effectiveness of the proposed CaDA for VRPs, we conduct experiments on 16 VRP variants with five constraints. Furthermore, we perform ablation studies to validate the efficiency of the proposed components.
where W., by, Wg. and by are learnable parameters.
3.4. Decoder
After encoding, the output of the global branch, (L)) [h( (Z))
4.1. Baselines
(L)) h // J, is utilized to construct the solution.
During the autoregressive decoding process, at step f, the context embedding is defined as:
We utilize SOTA traditional and neural solvers as base- lines. For the traditional solvers, we use PYP (Wouda et al., 2024), an extension of HGS-CVRP (Vidal, 2022), and Google's OR-Tools. Both baselines run on a single CPU core with time limits of 10s for VRP50 and 20s for VRP100. For the neural solvers, we compare our method against representative multi-task learning models: MT- POMO (Liu et al., 2024), MVMoE (Zhou et al., 2024a), and RouteFinder (Berto et al., 2024b), including RE-POMO, RE- MoE, and RF-TE. We utilize the open-source code published by RouteFinder (Berto et al., 2024b). For each method, train two models from scratch on VRP50 and VRP100 using the same hyperparameters and problem settings as in Berto et al. (2024b). The detailed problem setup can be found in Appendix C.I. However, for RF-MoE and MVMOE, due to their higher memory demands, we utilize the pre-trained parameters provided by RouteFinder (Berto al., 2024b) and test them under the same hardware settings as ours. All neural methods are trained using the same data budget. For CaDA, we train two models on VRP50 and VRP100, with the hyperparameters outlined in Appendix C.2. Mixed-batch training is employed to stabilize the training process (Berto et al., 2024b). Among the neural solvers, MVMoE has the largest model size (3.7 M), followed by CaDA (3.4 M),
(14) where is the partial solution already generated, and is the last node of the partial solution. The terms ei of represent the remaining capacity of the vehicle for linehaul and backhaul customers, respectively. The terms 2t, 4, and or represent the current time, the remaining length of the current partial route (if the problem includes a length limitation), and the presence indicator of the open route, respectively. The matrix W. E (dx++))x x is learnable parameter.
He = Concat [ ,c,, ci 4, ad] W.,
Then the context embeddings are processed through an MHA to generate the final query:
(15) where It represents the set of feasible actions at the current
ge MHA(H,, Concat [h.4 (4) : T.]),
step. The compatibility u; is computed as:
( vdde
E tanh
if It
(16)
otherwise,
5

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
Table 1. Performance on 1K test instances of 16 VRPs. The best learning- hased results are highlighted with gray background.
Solver
n 50
12 100
Solver
1 50
100
Ohj.
Gap
Time
Ohj.
Gap
Time
Ohj.
Gap
Time
Obj.
Gap
Time
HGS-PyVRP
10.372
10.4m
15.628
20.8m
HGS
16.031
10.4m
25.423
20.8m
OR-Tools
10.572
1.907%
10.4m
16.280
4.178%
20.8m
OR-Tools
16.089
0.347%
10.4m
25.814
1.506%
20.8m
CVRP
МТPOМO
10,520
1.423%
2s
15.941
2.030%
8s
МТРOМO
16.419
2.423%
2s
26.433
3.962%
9s
MVMoE
10.499
1.229%
3s
15. 888
1.693%
11s
MVMoE
16,400
2.298%
38
26 390
3,789%
11s
RE-POMO
1.300%
1.833%
8s
RF-POMO
16.363
2.066%
3.675%
RF-MoE
10.499
1 1.225%
38
15.877
1.625%
11s
RF-MoE
16.389
2.2325%
36
26. 321
3,516%
11s
RF-TE
10.502
1.257%
15.860
1.524%
8s
RF-TE
16.341
1.933%
26. 22.
3.154%
CaDA
10:494
1.182%
15.870
1.578%
8s
CaDA
16.278
1.536%
2s
26,070
2.530%
HGS-PyVRP
6.507
10,4m
9.725
20.8m
HGS-PyVRP
10.587
10, 4m
15.766
20.8m
OR-Tools
6.553
0.686/%
10.4m
9,995
2.732%
20.8m
OR-Tools
10.570
2.343%
10.4m
16,466
5.302%
20.8m
OVRP
MTPOMO
6.717
3.194%
2s
10.216
5.028%
86
МТРОМO
10.775
1.733%
2s
16.157
2.483%
8s
MVMoF
6.705
3.003%
10.177
4.617%
11s
MVMoF
10.753
1.525%
2.1133
RF POMO
6.699
2.926%
26
190
4.761
85
RF RF-POMO
10.748
1.498%
28
16.117
2.241
8s
RF-MoE
6.697
2.880%
10.139
4.234%
11s
RF-MoE
10.737
1.390%
16.070
1.937%
RE
6,682
2. 2.658%
28
10.115
3,996
8s
RF-TE
10.747
1.485%
26
16.057
1.858%
8s
CaDA
6,670
2.468%
10.121 28
4,045%
8s
CaDA
10.731
1.333%
16.057 2s
1.847%
8s
HGS-PyVRP
9.687
10.4m
14.377
20.8m
VRP
10.510
10.4m
16.926
20.8m
Tools
9.802
1. 1.159%
10.4m
14.933
3.853%
20.8m
OR Tools
10.519
0.078%
10.4m
17.027
0.583%
20.8m
VRPB
МТРОМO
10.036
3.5966%
15.
5.052%
8s
МТРОМО
10.676
1.558%
2s
17,442
3.022%
9s
MVMoF
10.007
3.292%%
36
15.023
4.505
10s
MVMoF
10.674
1 1.541%
38
17.416
2,870%%
128
RE-POMO
9.992
3.135%
15.025
4.534%
RF-POMO
10.656
1.361%
17,405
2.809%
RF-MoE
9,980
3.017%
38
14.973
4.168%
10s
RF-MoE
10.674
1. 1.540%
3s
17,388
2.704%
128
RF-TE
9.979
3.000%
28
14.935
3,906%
8s
RF-TE
10.645
1.2644%
28
17.328
2.352%
CaDA
9,960
2,800%
14,960 28
4.038%
8s
CaDA
10.613
0.957%
17:226 2s
1.751%
9s
10.186
10.4m
14.779
20.8m
VRP
18.361
10.4m
29.026
20.8m
OR-Tools
10.331
1.390%
10.4m
15.426
4.338%
20.8m
OR-Tools
18,422
0.332%
10.4m
29. 29.830
2.770%
20.8m
VRPBL
MTPOMO
10:679
4.760%
2s
15.718
6.294%
8s
MTPOMO
19.001
2.199%
3s
30,948
3.794%%
95
MVMoE
10.639
4.384%
15.642
5.771
11s
MVMoE
18.983
2.097%
30.892
3.609%
RF-POMO
10,590
3.926%
28
15.632
5.725%
8s
RF-POMO
18,938
1.863%
2s
30.847
3.452%
9s
RF-MoE
10.575
3.765%
15.542
12.2%
10s
RF-MoE
18.957
1.960%
30.809
3.325%
RF-TE
10.569
3.713%
28
15.523
5.008%
86
RF-TE
18,910
1.713%
2s
30.
2.978%
9%
CaDA
10.543
3,461%
2s
15.525
5,001 %
86
CaDA
18.848
1,376%
30,520 2s
2.359%
9s
HGS HVGSP
18.292
10.4m
29:467
20.8m
HGS VRP
16.356
10.4m
25.757
20.8m
OVRPBLTW OVRP VRPBTT
МТРОМО
OR-Tools
18.366
18.649
0.383%
1.938%
10.4m
29.945
30.478
3.426%
1.597%
20.8m
96
IRPLIN 
OR-Tools
МТРOМO
16.441
16,832
0.499%
2.877%
10.4m
2s
26.250
26.913
4.455%
1.899%
20.8m
95
MVMoE
18.632
1.841%
36
30.437
3.284%
12s
MVMoE
16.817
2.783%
3s
26. 26.866
4.272%
12s
RF-POMO
18.603
1.684%
30.384
3.102%
RF-POMO
16.756
2.419%
26.818
4.084%
RF-MoE
18.616
1. 1.757%
38
30.340
2,951
12s
RF-MoE
16.777
2. 2.548%
36
26.773
3.910%
12s
RF-TE
18.573
1.517%
30.249
2.641% '6
9%
RF-TF
16.728
2.2.48%
26. 706
3.645%
CaDA
18.500
1.117%
30.059
1.999%
98
CaDA
16,669
1.879%
2s
26.540
2.995%
95
HGS-PyVRR
6.898
*
10.4m
10.335
20.8m
HGS VRP
6.899
10.4m
10.335
20.8m
OR-Tools
6.928
0,412%
10.4m
10.577
2.315%
20.8m
OR-Tools
6.927
0.386
10, 10,4m
10.582
2.363%
20.8m
МТPОМO
7,105
2.973%
28
10.882
5,264%
8s
МТРОМО
7.112
3,0533
2s
10.888
5.318%
8s
MVMoF
7,089
2.744%
4.86%
11s
MVMoF
7.094
2.799%
4,929%
RF-POMO
7,085
2. 2.686%
25
10.839
4.857%
86
RF-POMO
7,088
2. 2.703%
2s
10.842
4.883%
8s
RF-MoB
7,081
2.617%
10. 806
4.528%
11s
RF-MoE
7,082
2.630%
10.807
4.537%
11s
TE
7.065
2.385%
28
10.774
4.233%
84
RF-TE
7.068
2.417%
28
10.778
4.266
8%
CaDA
7,049
2.159%
28
10.762
4,099%
8s
CaDA
7,051
2.166%
10,762 2s
4,102%
8s
HGS-PyVRP
11.668
10.4m
19.156
20.8m
VRP
11.669
10.4m
19.156
20.8m
OR-Tools
11681
0.106%
10.4m
19.305
0.767%
20.8m
OR-Tools
11.682
0.109%
10.4m
19.303
0.757%
20.8m
MTPOМO
11.823
1.315%
19.658
6.60%
9%
МТPОМО
11,823
1.307%
3s
19.656
2.5925
9s
MVMoE
11.816
1.249%
4s
19.640
2.514%
12s
MVMoF
11,816
1 1.245%
48
19.637
2. 2.499%
138
RF-POMO
11,810
1.192%
19.618
2,393%
10s
RF-POMO
11.809
1.182%
19.620
2. 2,403%
ME.
11.824
1.309'5
19.607
2.334%
12x
RF-MoF
11.823
1. 1.303%
4s
19.605
2.324%
12s
RF-TE
11.789
1.017%
28
19.554
2.061%
9%
RF-TE
11.790
1.027%
2s
19.555
2.062%%
CaDA
11,760
0.771%
19.435
1.439%
98
C&DA
11.761
0.779%
19.436 2s
1.441%
9s
HGS-PyVRP
6.507
10.4m
9.724
20.8m
HGS VRP
10.510
10.4m
16.926
20.8m
OR-Tools
6.552
0.668%
10.4m
10.001
2.791 %
20.8m
OVRP WRRPLTW
OR-Tools
10.497
0.114%
10.4m
17.023
0.728%
20.8m
OVREL
MTPOMO
6.720
3.248%
2s
10:224
5.112%
8s
MTPOMO
10.677
1.572%
2s
17.442
3,0209
9%
MVMoE
6.706
3.028%
10.184
4.693/
11s
MVMoE
10.677
1.564%
17.418
2,880%
REMOOO
6.701
2.944%
28
10.190
4.762%
85
RF-POMO
10.656
1. 1.3625
36
17,404
2. 2.8025%
9%
RF MoB
6.695
2.859%
10.140
4.252%
11s
RF-
10.673
1.531%
17.386
2. 2.696/%
12s
RE-TE
6.683
2. 2.680%
10.121
4.054%
84
RF-TE
10.646
1.267%
2s
17.328
2.352
9s
CaDA
6.671
2.475%
28
10.122
4.052%
86
CaDA
10.613
0.961
2s
17.226
1.752%
95
RF-TE (1.7 M), and MTPOMO (1.3 M).
stances for each VRP variant, at scales of 50 and 100. For all neural solvers, we employ a greedy rollout strategy with x X8au (Kool et al., 2019). This approach conducts equiva- lent transformations to augment the original instance and re- ports the best results among the eight augmented instances.
4.2. Testing and Hardware
We utilize the test dataset published by Routefinder (Berto et al., 2024b), which includes 1K randomly generated in-
6

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
Table Average objective function value and gap across 16 VRPs for ablation models and CaDA.
1.55
1.80
1.00
3,042
1.78
0.790
Obj.
Gap
1.50
1.70
1.77
1.75
1.70
1.72
CaDA w/o Prompt
11.534
1.926%
1.55
A.724
1.70
1714
1.00
1.58
CaDA w/o Sparse
11.521
1.795%
Prompton
Prompt on Sprase Branch
Promot on Global Branch [Ours]
Softmas
15.mam
Sparena
Taps (Purl
CaDA
11.513
1.714%
Both Brunch
(a) CaDA with different prompt positions: concatenated to the input of the global branch, sparse branch, both, where the first the standard setting.
(h) CaDA with different
0.60
sparse operations in the sparse branch
0.50
only standard softmax in both branches;
B CaDA w/o Prompt CaDA Sparse
0.40
Top-k is the standard setting.
dap
0.30
0.20
Figure 5.
The average gap across 16 VRPs for CaDA variants under different model settings.
owp
vppal
vpbiiw
owrp
owrpl
owrl
vrplar
vpll
curple
wpbitw
vrptb
ourpbit
owpbbl
awpite
1,800
Gap 88
1.75
Figure 4. Ablation study the proposed components of CaDA
1.754
1.70
1.733
1.722
across 16 VRPs. The height of the bars represents the increased gap in performance between the model with specific components ablated and the baseline CaDA.
k=N/25
k=/V//
ke/l/5
koN/4
k:N/2 (Ours)
Figure 6. Average gap on 16 VRPs for CaDA variants with differ- ent & values in the Top-k selection operation. where k T is the standard setting.
All experiments are run platform with NVIDIA GeForce RTX 3090 GPUs and Intel(R) Xeon(R) Gold 6348 CPUs at 2.60 GHz. Training our model from scratch takes about 17 hours for VRP50 and 25 hours for VRP100.
"without". In CaDA w/o Sparse, both branches use the standard Softmax with global connectivity. CaDA and its variants are trained and evaluated on VRP50. During testing, x8aug (Kool et al., 2019) is employed.
4.3. Main Results
In Table I, we report the average performances for each dataset and the gaps compared to the best rest-performing tradi- tional VRP solvers, as indicated by asterisks (*). Addition- ally, we present the total time required to solve the dataset. The best learning-baas based results for each dataset are high- lighted with a gray background. Furthermore, we present the comparison results with the average gap on 16 VRPs for both 50-node and 100-node instances in Figure 3.
The results Table 2 show the average gap on 16 VRPs and demonstrate that all components of CaDA make sub- stantial contributions, with the prompt playing particularly important role. Additionally, study the effect of differ- ent components on various problems, we demonstrate the increased gap of these two ablation models compared with CaDA on different VRP datasets Figure 4. These re- sults illustrate that both the prompt and the sparse operation improve performance on all VRP variants.
Results illustrate that the proposed CaDA method can ef- fectively manage various VRP variants at different scales. Specificallyy for VRP50 and VRP100, CaDA surpasses the second-best method by 0.26% and 0.32%, respectively. It ranks first among all neural network- based solvers for all VRP50 variants and for 13 out of 16 VRP100 variants. Sim- ilar to other neural solvers, CaDA significantly reduces the running time compared to SOTA heuristic solvers.
Then, we further explore the influence of different CaDA set- tings. Specifically, using CaDA as the baseline, conduct experiments on VRP50, focusing on the following aspects:
Position of Prompt We consider three positions to intro- duce prompts, as shown in Figure 5(a), which illustrates the average gap across 16 VRP variants for the different models. The results indicate that integrating both sparse and prompt mechanisms within the same branch yields inferior performance, whereas concatenating the prompt only to the input of the global branch achieves the best performance.
4.4. Ablation Study
In this section, we conduct ablation studies to validate the efficacy of the proposed components in CaDA. Specifically, we separately remove the constraint prompt and the Top- operation, resulting in two CaDA variants: CaDA w/o prompt and CaDA w/o Sparse, where "w/o" stands for
Different Sparse Function To validate the efficacy of our Top-k sparse operation, we compare CaDA against three

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
0.24
0.12
99
(a) CaDA on OVRP
6
07
0.3
(b) CaDA w/o Prompt on OVRP
0's
06
67
0.30
Density
0.08
0.06
63
07
03
0.5
06
0.04
(c) CaDA on CVRP
(d) CaDA w/o Prompt on CV RP
0.02
Figure 7. The distribution of attention weights between customers and the depot A.o, (1, } for CaDA and CaDA w/o Prompt on CVRP and OVRP. Kernel density estimation (KDE) with Gaussian kernels is applied to estimate the attention weight distribution. which is visualized using heatmap. CaDA w/o Prompt exhibits similar attention distribution across both problems, leading to increased interference between tasks. In contrast, CaDA shows a significantly lower density of high attention values for OVRP, indicating that the proposed prompt effectively provides constraint information as depot will never be the next action for any customer in OVRP.
variants: 1) removing the Top-k selection in the sparse branch, 2) replacing with 1.5-entmax (Peters al., 2019), and 3) replacing it with sparsemax (Martins & Astudillo, 2016). Figure 5(b) shows the average gap across 16 VRPs. Firstly, CaDA with different sparse functions consistently outperforms the version of CaDA with standard Softmax, which only has global connectivity. This indicates that the model benefits from focusing on promising nodes. Further- more, the Top-k operation outperforms the other two sparse operations, demonstrating its effectiveness for VRPs.
Figure shows the distribution of A for CaDA and CaDA w/o Prompt on CVRP and OVRP. We apply KDE with Gaus- sian kernels to estimate the distribution of attention weights between 0.2 and 0.8. The bandwidth parameter is set to 0, and the KDE is visualized using a heatmap. Firstly, CaDA exhibits a significantly different distribution of atten- tion scores between CVRP and OVRP, whereas CaDA w/o Prompt shows a similar attention distribution across both problems. When no prompt is provided, the encoder cannot distinguish between CVRP and OVRP instances, because both variants share identical input structures, 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.
k for Top-k To explore the different h values' ef- fects on CaDA, we conducted experiments with E (M N
N ( I 3 8 25 and trained these models from scratch respectively. Figure shows the average gap on 16 VRP50 datasets. It indicates that when k N the sparse branch can better cooperate with the global branch. This is the standard setting for CaDA.
Furthermore, when comparing CaDA on CVRP and CaDA on OVRP, we observe a significantly lower density of high attention values for OVRP, indicating that the proposed prompt effectively provides constraint information and helps the model better understand the problem.
4.5. Visualization of Constraint Awareness
To explore the influence of the prompt, conducted fur- ther statistical experiments on the distribution of attention scores within the encoder. While the results related to the influence of the open route constraint are detailed below, the study on the influence of the time window constraint provided in Appendix C.3. All experiments involve 100 VRP50 instances randomly selected from the test dataset, and attention scores were collected from all heads across all global layers.
4.6. Generalization to Unseen Constriants
We further conduct experiments to evaluate both zero-shot and fine-tuning performance on two unseen constraints:
Multi- (MD): Vehicles may start from any of the multiple depots but must return to their respective starting depot. Evaluation involves 16 variants, each created by adding an MD constraint to one of the 16 problems in Table 1. The number of depots is set to three, following Berto et al. (2024b).
Influence on Open Route Constraint In the case of the open route constraint, where the vehicle does not return to the depot vo, the depot will never be the next node for any customer node U,. Whereas in CVRP, the vehicle must return to the depot, making it potential next node for any customer. As a result, the model should exhibit different customer-depot attention patterns for CVRP and OVRP. Specifically, in CVRP, the model should exhibit a greater number of high attention scores Ago compared to OVRP.
Mixed Backhaul (MB): Linehaul and backhaul cus- tomers can be served in any order, subject to vehicle capacity limits. We evaluate variants, each formed by replacing the Backhaul constraint with the MB con- straint the 8 Buckhaul-constrained problems listed in Table 1.
Table shows the zero-shot performance of different mod-
8

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
Acknowledgements
Table Zero-shot results on constraints. Reported values are the average performance gap.
This work was partially supported by the National Natu- ral Science Foundation of China (Grant Nos. 62476118 and 12202472), the Natural Science Foundation of Guang- dong Province (Grant No. 2024A1515011759 the Natural Science Foundation of Shenzhen (Grant No. JCYJ202205301 13013031)) the Guangdong Science and Technology Program (Grant No. 2024B 1212010002), and the Foundation of National Key Laboratory of Aircraft Con- figuration Design (Grant No. ZYTS-202404).
Zero-shot
MD
MB
MTPOMO
42.29%
9.28%
MVMоΣ 45.56%
8.74%
RF-TE 41.93%
9.12%
CaDA
39.34%
8.46%
Ca2Ax32
28.86%
7.40%
17.5
MTPOMO RF-TE
MVMoE CaDA
15.5
Impact Statement
13.5
Cap
11.5
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
9.5
7.5
5.5
1
2
3
4
6
8
10
Epoch
References
Figure 8. Average performance gap 16 MD VRP variants during fine-tuning.
Ainslic, J., Ontanon, S., Alberti, C., Cvicek, V., Fisher, Z., Pham, P., Ravula, A., Sanghai, S., Wang, Q., and Yang, L. Ete: Encoding long and structured inputs in transformers. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing, pp. 268 (68, 2020.
els on VRP50. For CaDA, we initialized the prompt using the "closest" trained task (e.g., MDOVRPBI. OVRPBI, OVRPMB + OVRPB). We additionally provide a x32 data augmentation method for CaDA, which reports the best solu- tion among utilizing 32 prompts. Specifically, we generate all possible combinations of 5-dimensional binary vector V (i.e.,2 25). Given the relatively poor zero-shot performance across all evaluated models, generalization to the MD con- straint appears more challenging. CaDA achieves SOTA results on both MD and MB constraints.
Baevski, A. and Auli, M. Adaptive input representations for neural language modeling. In International Conference on Learning Representations, 2019.
Beltagy, I., Peters, M. E., and Cohan, A. Long-
former: The Long-document transformer. arXiv preprint wrXiv2004.005500 2020.
For the more challenging MD constraint, further com- pare the fine-tuning performance of different models. We use batch size of 128, 10,000 samples per epoch, learn- ing rate of 3 x 10-1, and employ mixed-batch training. Figure shows the convergence curves each model dur- ing fine-tuning, where CaDA consistently achieves SOTA performance.
Bengio, Y., Lodi, A., and Prouvost, A. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
Berto, Hua, C., Park, J., Luttmann, L., Ma, Y., Bu, F., Wang, J., Ye, H., Kim, M., Choi, S., Zepeda, N. G., Hottung, A., Zhou, J., Bi, J., Hu, Y., Liu, F,, Kim, H., Son, J., Kim, H., Angioni, D., Kool, W., Cao, 7.., Zhang, J., Shin, K., Wu, C., Ahn, S., Song, G., Kwon, C., Xie, L., and Park, RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark. arXiv preprint arXiv:2306. 17100, 2024a. https:// gi github. com/ coom/aii 4040o.
5. Conclusion
In this paper, we have proposed the Constraint-Awar Dual- Attention Model (CaDA), a novel cross- pross-problem neural solver for the VRPs. CaDA incorporates constraint prompt and dual-attention mechanism, which consists of global branch and sparse branch, efficiently generate constraint- node embeddings. We have thoroughly evaluated CaDA across 16 VRP variants and real-world benchmark in- stances. CaDA shows superior performance when compared to the current leading neural solvers. Additional ablation studies confirm the effectiveness of the proposed constraint prompt and dual-atten inal-attention mechanism.
Berto, F., Hua, C.,, Zepeda, N. G., Hottung, A., Wouda, N., Lan, L.,, Tierney, K., and Park, Routefinder: Towards foundation models for vehicle routing problems. In ICML 2024 Workshop on Foundation Models the Wild, 2024b.

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
Berto, F., Hua, C.,, Park, J., Luttmann, L.., Ma, Y., Bu, F., Wang, J., Ye, H., Kim, M., Choi, S., al. RI4co: extensive reinforcement learning for combinatorial opti- mization benchmark. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining 2. pp. 5278-5289, 2025.
Dong, X., Bao, J., Chen, D., Zhang, W., Yu, N., Yuan, L., Chen, D., and Guo, B. Cswin transformer: A general vision transformer backbone with cross-shaped windows. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 12124-12134, 2022.
Drakulic, D., Michel, S., and Andreoli, J.-M. Goal: A generalist combinatorial optimization agent learner. In The Thirteenth International Conference on Learning Representations, 2024.
Bi, Ma, Y., Wang. J., Cao, Z., Chen, J., Sun, Y., and Chee, Y. M. Learning generalizable models for vehicle routing problems via knowledge distillation. Advances in Neural Information Processing Systems, 35:31226-31233 2022.
Drori, I., Kharkar, A., Sickinger, W. R., Kates, B., Ma, Q., Ge, S., Dolev, E., Dietrich, B., Williamson, D. P., and Udell, M. Learning to solve combinatorial optimization problems on real-world graphs in linear time, 2020 19th IEEE International Conference on Machine Learn- ing and Applications, pp. 19-24. IEEE, 2020.
Blondel, M., Martins, A., and Niculae, V. Learning classi- fiers with fenchel-young losses: Generalized entropies, margins, and algorithms. In The 22nd International Con- ference on Artificial Intelligence and Statistics, pp. 606- 615. PMLR, 2019.
Bogyrbayeva, A., Meraliyev, M.. Mustakhov, T., and Daulet- bayev, B. Machine learning to solve vehicle routing problems: A survey. IEEE Transactions on Intelligent Transportation Systems, 2024.
Duan, L., Zhan, Y., Hu, H., Gong, Y., Wei, J., Zhang, X., and Xu, Y. Efficiently solving the practical vehicle routing problem: A novel joint learning approach. In Proceed- ings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 3054-3063, 2020.
Cappart, Q. Moisan, T., Rousseau, L.-M., Prémont- Schwarz, I., and Cire, A. A. Combining reinforcement learning and constraint programming for combinatorial optimization. In Proceedings of the AAAI Conference Arlificial Intelligence, volume 35, pp. 3677-3687, 2021.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llama 3 herd of models. arXiv preprint arXi::2407221788 2024.
Cattaruzza, D., Absi, N., Feillet, D., and Gonzâlez-Feliu, Vchicle routing problems for city logisties. EURO Journal on Transportation and Logistics, 6(1):11-79, 2017.
Elfwing. S., Uchibe, E., and Doya, K. linear units for neural network function approximation in reinforcement learning. Neural networks, 107:3-11, 2018.
Chen, X., Li, H., Li, M., and Pan, J. Learning a sparse transformer network for effective image deraining. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pp. 5896-5905, 2023.
Fang, H., Song. Z., Weng, P., and Ban, Y. Invit: A general- izable routing problem solver with invariant nested view transformer. In International Conference on Machine Learning, pp. 12973-12992. PMLR, 2024.
Child, R., Gray, S., Radford, A., and Sutskever, I. Gen- crating long sequences with sparse transformers. arXiv preprint arXiv: /904. 10509, 2019.
Fu, J., Liu, J., Tian, H., Li, Y., Bao, Y., Fang, Z., and Lu, H. Dual attention network for scene segmentation. In Proceedings of the IEFF/CVF conference on computer vision and pattern recognition, pp. 3146-3154, 2019.
Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113, 2023.
Gao, C., Shang, H., Xue, K., Li, D., and Qian, C. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In Proceed- ings of the Thirty-Thin International Joint Conference on Artificial Intelligence, pp. 6914-6922, 2024.
Correia, G. M.. Niculae,
V., and Martins, A. F. Adap- tively sparse transformers. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pp. 2174-2184, 2019.
Gao, I.., Chen, M., Chen, Q., Luo, G., Zhu, N., and Liu, Z. Learn to design the heuristics for vehicle routing problem. arXiv preprint arXiv:2002.0m 02.000....8.9......... 2020.
Dauphin, Y. N., Fan, A., Auli, M., and Grangier, D. Lan- guage modeling with gated convolutional networks. In International conference on machine learning, pp. 933- 941. PMLR, 2017.
Geisler, S., Sommer, J., Schuchardt, J., Bojchevski, A., and Günnemann, S. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In
10

---

CaDA: Cross-Probles Routing Solver with Constraint-Aware Dual-Attention
International Conference on Learning Representations, 2022.
IEEE/CAA Journal of Automatica Sinica, 9(7):1115- 1138, 2022a.
Gu, J., Kwon, H., Wang, D., Ye, W., Li, M., Chen, Y.-H., Lai, L.,, Chandra, V., and Pan, D. Z. Multi-scale high- resolution vision transformer for semantic segmentation. In Proceedings of the IEEF/CVE conference on computer vision and pattern recognition, pp. 12094-12103, 2022.
Li, J., Ma, Y., Gao, R., Cao, Z., Lim, A., Song, W. and Zhang, J. Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem. IEEE Transactions Cybernetics, 52(12): 2022b.
Guo, M.-H.,, Lu, C.-Z.,, Hou, Q., Liu, Z.. Cheng, M.-M., and Hu, S.-M. Segnext: Rethinking convolutional attention design for semantic segmentation. Advances in Neural Information Processing Systems, 35:1 150:1140-156, 2022.
Li, S., Jin, X., Xuan, Y., Zhou, X., Chen, W., Wang, Y.- X., and Yan, X. Enhancing the locality and breaking the memory bottleneck of transformer time series forecast- ing. Advances in neural information processing systems, 32, 2019.
Guo, Q. Qiu, X., Liu, P., Shao, Y., Xue, X., and Zhang, Z. Star-transformer. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolo- gies, Volume I (Long and Short Papers), pp- 1315-1325, 2019.
Lin, Z.,, Wu, Y., Zhou, B., Cao, Z., Song, W., Zhang, Y., and Senthilnath, J. Cross-problem learning for solving vehicle routing problems. In The 33rd International Joint Conference on Artificial Intelligence, 2024.
Liu, F., Lin, X., Wang, Z., Zhang, Q., Tong, X., and Mingx- uan, Y. Multi-task learning for routing problem with cross-problem zero-shot generalization. In The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, 2024.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference computer vision and pultern recognition, pp. 770-778, 2016.
Jiang, Y., Wu, Y., Cao, Z., and Zhang, J. Learning to solve routing problems via distributionally robust optimization. In Proceedings of the AAAI Conference on Artificial In- telligence, volume 36, pp. 9786-9794, 2022.
Martins, A. and Astudillo, R. From softmax to sparsemax: A sparse model of attention and multi-label classification. In International conference on machine learning, pp. 1614- 1623. PMLR, 2016.
Kim, M.. Park, J., et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34:10418-100 104400 2021.
Naveed, H., Khan, A. U., Qiu, S., Saqib, M., Anwar, S., Usman, M., Akhtar, N., Barnes, N., and Mian, A. A comprehensive overview of large language models, arXiv preprint arXiv:2307.06443. 2023.
Kim, M., Park, J., and Park, Sym-nco: Leveraging symmetricity for neural combinatorial optimization. Ad- vances in Neural Information Processing Systems, 35: 1936-1949, 2022.
Nazari, M., Oroojlooy, A., Snyder, L., and Takác, M. Rein- forcement learning for solving the vehicle routing prob- lem. Advances in neural information processing systems, 31, 2018.
Kool, W., van Hoof, H., and Welling, M. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Pan, W., Xiong, H., Ma, J., Zhao, W., Li, Y., and Yan, J. Unico: On unified combinatorial optimization via problem reduction to matrix-encoded general tsp. In The Thirteenth International Conference Learning Represemations, 2025.
Kool, W., van Hoof, H., Gromicho, J., and Welling, M. Deep policy dynamic programming for vehicle routing problems. In International conference on integration of constraint programming, artificial intelligence, and operations research, pp. 190-213. Springer, 2022.
Peng, B., Wang, J., and Zhang. Z. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. In Artificial Intelligence Algo- rithms and Applications: 1 11th International Symposium, ISICA 2019, Guangzhou, China, November 16-17, 2019, Revised Selected Papers 11, pp. 636-650. Springer, 2020.
Kwon, Y.-.., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Informa- tion Processing Systems, 33:21 11111118891... 2020.
Peters, B., Niculae, V., and Martins, A. F. Sparse sequence- to-sequence models. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 1.504-1519 2019.
Li, B,, Wu, G., He, Y., Fan, M., and Pedrycz, W. An overview and experimental study of learning-bast op- timization algorithms for the vehicle routing problem.

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
Rodrigue, J.-P. The geography of transport systems. Rout- ledge, New York, 5 edition, 2020. doi: 10.4324/ 9780429346323.
Wang, C., Yang, Y., Han, C., Guo, T., Zhang, H., and Wang, J. A game-theoretic approach for improving generaliza- tion ability of tsp solvers. In ICLR 2022 Workshop Gamification and Multiagent Solutions, 2022a.
Ronneberger, O., Fischer, P., and Brox, T. U-net: Con- volutional networks for biomedical image segmenta- tion. In Medical image compuling and computer-ussisted intervention-MIICA. 2015: 18th international confer- ence, Munich, Germany, October 5-9, 2015, proceedings, part III 18, pp. 234-241. Springer, 2015.
Wang. H., Shen, J., Liu, Y., Gao, Y., and Gavves, E. Nformer: Robust person re-identification with neighbor transformer. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pp. 7297- 7307, 2022b.
Shazeer, N. Glu variants improve transformer. arXiv preprint arXiv:2002.05202, 2020.
Wang. J., Sun, K., Cheng, T., Jiang, B., Deng, C., Zhao, Y., Liu, D., Mu, Y., Tan, M., Wang, X., al. Deep high-resolution representation learning for visual recogni- tion. IEEE transactions on pattern analysis and machine intelligence, 43(10):3349-3364 2020.
Shazeer, N., Mirhoseini, A., Maziarz, K., Davis, A., Le, Q. Hinton, G., and Dean, J. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. In International Conference on Learning Representations, 2017.
Wang. P. Wang, X., Wang, F,, Lin, M., Chang, S., Li, H., and Jin, R. Kvt: k-nn attention for boosting vision transformers. In European conference on computer vision, pp. 285-302. Springer, 2022c.
Sun, K., Zhao, Y., Jiang, B., Cheng, T., Xiao, B., Liu, D., Mu, Y., Wang, X., Liu, W., and Wang, High-resolutinn representations for labeling pixels and regions. CoRR, abs/1904.04514, 2019.
Wang, W., Chen, W., Qiu, Q., Chen, L.., Wu, B., Lin, B., He, X., and Liu, W. Crossformer++: versatile vision transformer hinging on cross-scale attention. IEEE Trans- actions on Pattern Analysis and Machine Intelligence. 2023.
Tan, S.-Y. and Yeh, W.-C. The vehicle routing problem: State-of-the-art classification and review. Applied Sci- ences, (1(21):00295 2021.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. Llama: Open and efficient foundation lan- guage models. arXiv preprint arXiv:2302. 13971, 2023.
Williams, R. J. Simple statistical gradient-following algo- rithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992.
Tyasnurita, R., Özcan, E.,, and John, R. Learning heuristic selection using time delay neural network for open vehicle routing, In 2017 IEEE Congress on Evolutionary Computation, pp. 1474-1481. Ieee, 2017.
Wouda, N. A., Lan, L.,, and Kool, W. Pyvrp: A high- performance vrp solver package. INFORMS Journal on Computing, 2024.
Xin, L., Song, W., Cao, Z., and Zhang, J. Multi-decoder attention model with embedding glimpse for solving ve- hicle routing problems. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 35, pp. 12042- 12049, 2021.
Uchoa, E., Pecin, D., Pessoa, A., Poggi. M., Vidal, T., and Subramanian, A. New benchmark instances for the ca- pacitated vehicle routing problem. European Journal of Operational Research, 257(3):845 8888888 2017.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, t., and Polosukhin, I. At- tention is all you need. Advances in neural information processing systems, 30, 2017.
Xin, L., Song, W., Cao, Z.., and Zhang, J. Generative ad- versarial training for neural combinatorial optimization models, 2022. URL https: opw.reviee.eeeee//e/ee n forum? -eeeidd-vvvstt 3vs.idd-sssssess.us.
Vidal, T. Hybrid genetic search for the evrp: Open-source implementation and swap* neighborhood. Computers & Operations Research, 140:105643, 2022.
Zhang, B. and Sennrich, R. Root mean square layer nor- malization. Advances in Neural Information Processing Systems, 32, 2019.
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. Advances in neural information processing systems, 28, 2015.
Zhang, H., Dana, K., Shi, J., Zhang, Z., Wang, X., Tyagi, A., and Agrawal, A. Context encoding for semantic segmentation. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 7151 7160, 2018
Wang, C. and Yu, T. Efficient training of multi-task neural solver with multi-armed bandits. CoRR, 2023.
12

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attcntion
Zhang, J., Tu, Z., Yang. Chen, Y., and Yuan, Mixste: Seq2seq mixed spatio-temporal encoder for 3d human pose estimation in video. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 13232-13242, 2022a.
Zhang, Z.., Zhang. Z., Wang, X., and Zhu, W. Learning solve travelling salesman problem with hardness-adaptii curriculum. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9136-9144, 2022b.
Zhao, G., Lin, J., Zhang, Z., Ren, X., Su, Q. and Sun, X. Ex- plicit sparse transformer: Concentrated attention through explicit selection. arXiv preprint arXiv: 1X11:/992..1637.. 2019.
Zhao, H., Gou, Y., Li, B., Peng, D., Lv, and Peng, X. Comprehensive and delicate: An efficient transformer for image restoration. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 114122-14132 2023.
Zhao, J., Mao, M., Zhao, X., and Zou, J. A hybrid of deep reinforcement learning and local search for the vehi- cle routing problems. IEEE Transactions on Intelligent Transportation Systems, 22(11):7208-72 7218, 2021.
Zhou, J., Wu, Y., Song, W., Cao, Z.., and Zhang, J. Towards omni-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learn- ing. pp. 42789. PMLR, 2023.
Zhou, J., Cao, Z., Wu, Y., Song, W. Ma, Y., Zhang, J., and Xu, C. Mvmoe: Multi-task vehicle routing solver with mixture-of-experts In International Conference on Machine Learning, 2024a.
Zhou, S., Chen, D., Pan, J., Shi, J., and Yang. J. Adapt perish: Adaptive sparse transformer with attentive feature refinement for image restoration. In Proceedings of the JEEE/CVF Conference on Computer Vision and Patlern Recognition, pp. 2952-2963, 2024b.
13

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
A. Related Work
A.I. Neural Combinatorial Optimization
Neural combinatorial optimization (NCO) approaches utilize deep reinforcement learning to train a policy that constructs solutions in an autoregressive manner. Nazari et al. (2018) are the first to apply pointer networks (Vinyals et al., 2015) to solve the VRP. Subsequently, the pioneering work attention model (AM) (Kool al., 2019) employs a powerful Transformer- based architecture. This model is optimized using the REINFORCE algorithm (Williams, 1992) with a greedy rollout baseline. Building on this, Kwon et al. (2020) introduce the policy optimization with multiple optima (POMO) method, which leverages solution symmetries and has demonstrated significantly improved performance. Subsequently, numerous studies have further refined both AM and POMO, enhancing Transformer-basee methods (Xin et al., ;021; Kim et al., 2021; Peng et al., 2020; Kim et al., 2022). Given the diverse constraints and attributes in real-world transportation needs, some research focuses on various VRP variants, including heterogeneous capacitated VRP (HCVRP) (Li et al., 2022b), VRP with time windows (VRPTW) (Gao et al.. 2020; Cappart et al.. 2021; Zhao al.. 2021; Kool al., 2022), and open route VRP (OVRP) (Tyasnurita et al., 30. More information can be found in recent reviews (Bogyrbayeva et al., 2024; Li et al., 2022a).
A.2. Cross-Problem Learning for VRPs
Neural methods for solving VRPs typically train and evaluate deep models the same instance distributions. Some studies have explored generalization across multiple distributions (Zhang et al., 2022b; Xin et al., 2022; Geisler et al., 2022; Wang et al., 2022a; Jiang et al., 2022; Bi et al., 2022). Additionally, Zhou et al. (2023) consider both problem size and distribution variations. Recent developments have begun to address cross pross-problem generalization (Wang & Yu, 2023; Lin et al., 2024; Drakulic et al., 2024; Liu et al., 2024; Zhou et al., 2024a; Berto et al., 2024b; Pan et al., 2025). Wang & Yu (2023) use multi-armed bandits to achieve task scheduling. Lin et al. (2024) demonstrate how a model pre-trained on the travelling salesman problem (TSP) could be effectively adapted to targeted VRPs through efficient fine-tuning, e.g., inside tuning, side tuning, and low-rank adaptation (LoRA).
To tackle multiple VRP variants in unified model, MТPOMO (Liu et al., 2024) conceptualizes VRP variants combinations of underlying constraints, enabling the model to achieve zero-shot generalizability to more tasks. MVMoE proposes a new model architecture using the MoE (Shazeer et al., 2017) approach to improve performance. Furthermore, RouteFinder (Berto et al., 2024b) proposes to use a modern transformer encoder structure incorporating SwiGLU (Dauphin et al., 2017), RMSNorm (Zhang& & Sennrich, 2019), and Pre-Norm (Baevski & Auli, 2019; Child et al., 2019), which considerably improves the model's capability. However, these approaches remain unaware of constraints and maintain only global connectivity throughout the encoding process, which limits their cross-problem capabilities.
A.3. Multi-Branch Architecture
Multi- branch architectures have been widely used and have achieved success in computer vision. Some research employs multiple branches to capture both low and high-resolution image information, ultimately producing a comprehensive and powerful semantic representation that can be used for downstream tasks such as image segmentation (Ronneberger et al., 2015; Guo et al., 2022; Gu et al., 2022) or human pose estimation (Sun et al., 2019; Wang et al., 2020). Other studies assign different branches to focus on distinct aspects by utilizing attention mechanisms (Fu et al., 2019; Zhang et al., 2022a; Dong et al., 2022; Wang et al., 2023). For instance, DANet (Fu et al., 2019) proposes a dual attention network for scene segmentation, with one branch responsible for capturing pixel-to-pixel dependencies and another for capturing channel dependencies across different feature maps, thereby capturing global context (Zhang et al., 2018). Similarly, Crossformer++ (Wang et al., 2023) groups image patches in both local and global ways, incorporating short-distance and long-distaned attention to achieve better representation, retaining both small-scale and large-scale features in the embeddings. Recent NCO methods adopt similar strategies for VRPs. Gao et al. (2024) 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. They both focusing on generalization across distributions and scales. In contrast, CaDA addresses 16 VRP variants using a learnable mechanism (Top-k k sparse attention) to dynamically select related nodes based on attention scores.
14

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
A.4. Sparse Attention
Recent studies have proposed using sparse attention to reduce computational complexity and minimize the harmful influence of unnecessary and irrelevant items, thereby improving performance (Zhao et al., 2019; Wang et al., 2022c;b; Chen et al., 2023; Zhao et al., 2023). To achieve this, many researchers utilize pre-defined sparse attention patterns based prior knowledge, such as local or strided attention, or combinations of multiple patterns (Guo et al., 2019; Li et al., 2019; Beltagy et al., 2020; Ainslie et al., 2020). For instance, LogSparse (Li et al., 2019) ensured that each token only attends to itself and its preceding tokens, using an exponential step size. However, these methods can be overly harsh and require well-informed prior knowledge. Another category of methods achieves sparse attention by adding an additive operation that eliminates small attention scores to exactly zero, such as the Top-k operation (Zhao al., 2019; Wang et al., 2022c;b; Chen al., 2023) and the ReLU operation (Zhou et al., 2024b), employs sparsity-inducing alternative Softmax, such as sparsemax (Martins & Astudillo, 2016) and a-entmax (Peters et al., 2019; Blondel al., 2019; Correia et al., 2019). In this study, we use the simple yet efficient Top-k selection operation to achieve sparse attention and enhance the representation learning from the most relevant nodes.
B. Method Details
B.1. MDP for Learning Construct Solutions
When the policy autoregressively builds the VRP solution, the MDP for the decoding step can be defined follows:
State St E S is the ordered tuple (T:-1, V) given by the current partial solution T--1 (ri, . Te-1) and the instance
V. Initially, To- 0. and at the end, 8T contains a feasible solution
Action ag E A is the selected index in the current step, which will be added at the end of the partial solution. If dz O, ie., the vehicle returns to the depot node, signifies the end of the current sub-tour and the start of a new one.
Policy A neural model Ty with learnable parameters 0 is used as a policy to generate solutions sequentially, where the probability of generating the final feasible solution is:
T To T (V) II
T
No (o( = [Imor
Tt-1, 1))
(17)
t=1
1=1
Reward
r E R only be obtained when whole feasible solution Ty is generated and is defined the negative solution
length:
r(Tr)
d
(18)
t=1
B.2. Gated Linear Unit
The standard transformer blocks include an FFD that processes the input X through two learned linear projections, with ReLU activation function applied between them. In many recent modern transformer-based large language models (Chowd- hery et al., 2023; Touvron et al., 2023; Naveed et al., 2023), this configuration has been replaced by GLUs (Dauphin et al., 2017). GLUs consist of a component-wise product of two linear projections, where one projection is first passed through a nonlinear function. We employ SwiGLU (Dauphin al., 2017), which utilizes the sigmoid linear unit (SiLU) (Elfwing al., 2018) as the nonlinear function, as recommended in the RouteFinder(Berto et al., 2024b). The SwiGLU is defined as:
SwiGLU(X) X o (XW; + b,) @ SiLU(XW; + b2),
(19)
where @ denotes element-wis multiplication, @ is matrix multiplication, a is the sigmoid function, and W1, W2, b1, b2 are learnable parameters.
B.3. Feasibility Evaluation
During decoding, at step t, we use the following feasibility testing procedure to identify the set of feasible actions, denoted as T
15

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
1. Each customer node can only be visited once. If the depot is the last action in a partial solution, the next action cannot be the depot (to avoid self-loop).
E TIa-1i
i 4 --1=0 = 0 J.
(20)
(21)
2. For problem without the open route constraint (Vi 0), each sub-route needs to return the depot vo within the given limit. There are two types of constraints that enforce limits on when each sub-route must reach the depot: the time window constraint (V/2 1) with a time limit T, and the Distance Limit constraint (V33 = 1) with a distance limit p.
(Vi = 0) (V22 = 1) A ((z + d + do0) > T)
V ((V = 0) ^ (V3 = 1) A (4 < d + d40)) = i E I..
(22)
3. For problems with a time window constraint (V₂ = 1). each customer node u, has a time window (e,, 4] and a service time 8t. The vehicle must visit iú and complete its service within the specified time window.
(V2 = 1) A (z + d + > 11) = i E.
(23)
4. For the problem with the backhaul constraint (V4 = 1), the backhaul will be masked if there are still linehaul services that have not been completed.
(6. < < (1, NY(6 0) (j & r1a-1)) = ii lt.
(24)
5. For customers, service is available when their demand does not exceed the current available capacity,
((6, > 0) (6 > 4)) ((6, < <0) +)) i It.
(25)
C. Experiment Details
C.1. Problem Setup
Table 4. 16 VRP variants with five constraints.
Capacity
Open Route
Backhaul
Duration Limit
Time Window
CVRP
OVRP
VRPB
VRPL
VRPTW
OVRPTW
OVRPB
OVRPI.
VRPBL
VRPBTW
VRPLTW
OVRPBL
OVRPBTW
OVRPLTW
VRPBLTW
OVRPBLTW
In this section, we provide a detailed description the problem setup used in this study, with the associated constraints summarized in Table
16

---

CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
Locations The nodes' locations represented by two-dimensional vector X E (0,..., N). and are derived from uniform distribution (0, 1).
Capacity In this study, we consider only homogeneous vehicles, with the same vehicle capacity C shared among all vehicles, and the number of vehicles is unlimited. Following the common capacity setup used in previous studies (Kool et al., 2019; Kwon et al., 2020), for N = 50 and N = 100, the vehicle capacity C' is set to 40 and 50 respectively.
Node Demands In our study, there are two types of customers: linehaul customers with demand 6; < 0 and backhaul customers with 6, > 0 (when the backhaul constraint is active). We generate node demands as follows: we generate linehaul demands 6/ for all customers i E , N} by uniform sampling from the set of integers {1, 2, ...,.) 9]. If the backhaul constraint is inactive, each node's true demand 6, is equal to 6%. The demand generation process is now complete. Otherwise, we generate backhaul demands 83 by sampling uniformly from the same set of integers {1, .... 9}. Subsequently, generate
a temporary variable 1/4 (0, 1) for each customer i. The demand 8; for each customer is determined by the following rule:
8 8
if yi 2 0.2,
6;
(26)
otherwise.
For each node, there is a 20% probability that it represents backhaul eustomers in instance.
Furthermore, before passing the demands ò; to the policy, for training stability, we normalize the demand ò; to the range [0, 1] by 8 = 6- We set the normalized capacity to I to ensure that at each step of the decoding process, the remaining capacity 6, also falls within the range [0, 1].
Time Windows For problems with time window constraints, several related factors must be considered: time windows [e,, [4] and service times &t. For the depot, eg = 50 = 0, lo = T = 4.6, where T represents the overall time limit for each sub-route. Additionally, the vehicle speed is 1.0.
For customers i (I. N). service times 8; are uniformly sampled from [0.15, 0.188. Additionally, time window lengths At, are uniformly sampled from [0.18, 0.2]. Moreover, each customer's 's time window must be feasible for the tour (0, i, 0); otherwise, there is no feasible tour to service this customer. Consequently, the upper bounds for the start times of the time windows are calculated as:
T s; At,
up
(27)
do:
Subsequently, the start times the time windows e; are determined as follows:
e = (1 + (e. 1) yi) doi,
(28)
where y: ~ UO, Finally, the end times of the time windows are determined by:
= e: 24,-
(29)
Distance Limit For problems with the Distance Limit constraint, each sub-tour must be completed within a limit p. To ensure each instance has a feasible solution, i.e., the length of the tour (0, i, 0) should remain within this limit, is sampled from (2 max (do)), p,ax), where Pmax = 3.0 is predefined upper bound.
C.2. Hyperparameters
The hyperparameters used for training CaDA are summarized in Table 5.
C.3. Visualization of Constraint Awareness for Time Window Constraints
For the time window constraint, nodes can only be visited within their respective time windows 4), and serving each customer costs s; time. Thus, the relationship between node pairs (v;, U5)) is influenced by their time-related factors and positional distances, i.e., (ei, 4,, st), (e,, 44 8)), and dij.
If an edge (i.j) is legal, then it must satisfy e + s; + drj S 8j. This condition means that if a vehicle starts at time e, spends 8; time servicing U; and takes dy time to reach Uj. must arrive by (l, - 85) at the latest to successfully service "y
17

---

CaDA: Cross-Problent Routing Solver with Constraint-Aware Dual-Attention
Table 5. Experiment hyperparameters.
Hyperparameter
Value
Model
Embedding dimension d,
128
Number of attention heads a
Number of encoder layers L
Top-k
(N)
2
Feedforward hidden dimension do
512
Tanh clipping {
10.0
Training
Batch size
256
Train data per epoch
100,000
Optimizer
AdamW
Learning rate (LR)
3e -4
Weight decay
1e-6
LR scheduler
MultiStepL.R
LR milestones
[270, 295]
LR gamma
0.1
Gradient clip value
1.0
Training epochs
300
Number of tasks used for training
Table 6. Average gap on CVRPLIB datasets for CaDA tested with different values of & E {10, 25, 50, 100).
k:
Obj.
Gap
10
6440.8
4.61 %
25
6431.8
4.17% %
50
6458.6
4.79%
75
6463.7
4.88%
100
6475.7
5.15%
and leave the node within the service window. Accordingly, we derive the following inequality:
6 + + dij (1y e;) - - -sc
S 1 8j
(30)
2 0.
Define Pi. (1g 11y-60 eq) dij (s: + 8;). Figure 9 visualizes the distribution of Aij across varying Psj. Firstly, CaDA exhibits fewer high attention values for Pi.j < O. Additionally, for Pij values that are too high, the vehicle may need to wait long time at ny to wait until the start of the time window éj. For example, consider Pij 4 while the overall time limit for the sub-route is T = 4.6. Including the edge (i,j) in the solution may result in significant time wasted waiting. Compared to the CaDA w/o Prompt, CaDA also exhibits fewer high attention values for Pij > 3, indicating that CaDA more efficiently understands the problem constraints.
C.4. Result on Real- World Instances
To further validate the effectiveness of CaDA in real-world instances, we conducted experiments using five test suites from CVRPLib benchmark datasets. These datasets comprise a total 99 instances from Sets A, B, F, P. and (Uchoa et al., 2017), with graph seales ranging from to 200, various node distributions, and customer demands. CaDA is trained on 16 different VRP types, each with graph size of 100 nodes.
htttp:/vvpp.add- 1ab. www.:iff.uuurirooo rio.br/
18

---

CaDA: Cross-Probies Pross-rooblm Routing Solver with Constraint-Aware Dual-Attcntion
1.0
10
10t
0.8
0.8
10
10
103
leg10100
(og201k)
0.4
0.4
100
10a
0.2
10a
101
10a
10a
(a) CaDA
(b) CaDA w/o Prompt
Figure 9. For 100 VRPTW instances, the distribution of attention scores Aij across varying P..j. where A.j is the attention score from node os to node vj, and P. (l, ex) d.y (s. + sy) represents the surplus time when the vehicle starts from e, at time e, and travels to ny. If Pij 0, the edge (f, is illegal: if P.. becomes too large, including (i,5) in the solution may result in the vehicle having to wait long time for 2 to open. The shade represents the density in that region. For CaDA, attention scores at extremely high and low P.,, values are diminished, indicating that the model successfully comprehends the time window constraint.
Table 7. Results on CVRPLib datasets.
МТРОМО
MVMoE
RF-POMO
RF MolE
RE-E
CaDAgs
CaDAgs x
Opt.
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Obj.
Set. A
1041.9
1087.9
5.07%
1071.3
3.07%
1064.1
2.11%
1072.2
2.83%
1070.3
2.86%
1069.9
2.76%
1062.9
2.00%
Set
963.7
1006.9
4.86%
999.2
3.94%
991.6
2,89%
994.0
3.17%
987.4
2.58%
987.5
2.58%
982.7
2.02%
Set
707.7
820.0
16.23%
791.3
12.16%
804.0
13.93%
813.0
14.31%
794.7
12.95%
748.7
5.74%
745.3
4.99%
Set
587.4
629.3
11.10%
614.0
6.76%
606.4
4.72%
603.3
3.39%
608.7
4.59%
607.9
4.82%
601.2
3.16%
Set 27220.1
28952.5
6.09%
28688.4
5.19%
28825.4
5.54%
29125.2
6.37%
28520.3
4.46%
28745.0
4.97%
28573.9
4.41%
Avg. 6104.2
6499.3
8.67%
919.8
5.29%
6458.3
5.841%
6521.5
6.01%
6396.3
5.49%
6431.8
4.17%
6393.2
3.32%
We initially explore the effect of different & values on the Top-k sparse operation during testing. Table 6 demonstrates the average gap compared to the best-known results from CVRPLIB across all instances when testing CaDA with different A E {10, 25, 50, 100}. The results show that when & 25, CaDA achieves the best performance across different scales.
Furthermore, we compared CaDA with existing cross prosseem neural solvers. Table 7 exhibits the comparison results of five test suites with the average objective function values, and the gap with the best-known solution for each dataset. The best results for each dataset are highlighted in bold. CaDAgs represents CaDA tested with & = 25. Results demonstrate that the proposed CaDAgs x 32 achieves the best performance.
19


Reviews:
[{"review_id": "EouNczTUgj", "reviewer": "Reviewer_BUgi", "summary": "The paper \"CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention\" presents a novel cross-problem learning method for Vehicle Routing Problems (VRPs) that enhances constraint awareness and representation learning through a Constraint-Aware Dual-Attention Model (CaDA). \n\n1.Main Contributions\n\n(1) Constraint-Aware Dual-Attention Model (CaDA): A new cross-problem learning method for VRPs that improves model awareness of constraints and representation learning.\n(2) Constraint Prompt and Dual-Attention Mechanism: A constraint prompt is introduced to facilitate high-quality constraint-aware learning, and a dual-attention mechanism ensures the encoding process is both selectively focused and globally informed.\n(3) Superior Performance: Comprehensive evaluations across 16 VRP variants show CaDA achieves state-of-the-art performance, surpassing existing cross-problem learning methods. Ablation studies confirm the effectiveness of both the constraint prompt and dual-attention mechanism.\n\n2. Main Results\n\n(1) Performance: CaDA outperforms existing neural solvers (e.g., MTPOMO, MVMoE, RouteFinder) on 16 different VRP variants, with significant improvements in solution quality and efficiency.\n(2) Ablation Studies: Removing the constraint prompt or sparse attention mechanism leads to performance drops, highlighting their importance. The prompt's position in the global branch and the Top-k sparse operation's effectiveness are also validated.\n(3) Real-World Validation: CaDA shows strong performance on real-world CVRPLIB datasets, further proving its practical effectiveness.\n\n3. Key Algorithm and Concepts\n\n(1) Constraint Prompt: Represents problem constraints as a multi-hot vector processed through an MLP to generate prompts, which are concatenated with node embeddings to enhance constraint awareness.\n(2) Dual-Attention Mechanism: Comprises a global branch (standard multi-head attention) and a sparse branch (Top-k sparse attention). The global branch captures broad graph information, while the sparse branch focuses on key node connections, improving representation learning.\n(3) Encoding-Decoding Framework: Follows a typical encoder-decoder structure. The encoder uses the dual-attention mechanism and constraint prompt to generate node embeddings, and the decoder constructs solutions autoregressively based on these embeddings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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](https://anonymous.4open.science/api/repo/CaDA_illustration-FC5A/file/Figure.pdf?v=13d844ac) .\n\n> **C1,E2,W3,S4,Q4. Computational Efficiency Analysis**\n\nWe 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.\n\n| |Gap|Time per Instance|\n|-|-|-|\n|HGS-PyVRP| * |40s|\n|RF-TE|5.02% |0.05s|\n|CaDA|4.80% |0.05s|\n\n> **C2,E3,Q3. Generalization to Unseen Problems**\n\nWe 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.\n\n> **E1. Statistical Significance Testing**\n\nWe conduct a one-sided Wilcoxon rank-sum test comparing CaDA with RF-TE, and the result confirms CaDA’s superiority with >95% confidence.\n\n| p-value| Significant(0.05) |\n| ---| ----- |\n| 2.6E-04 | TRUE              |\n\n> **W1. How CaDA Addresses Limitations**\n\nWe use prompt to enhance constraint awareness and a dual-branch model with global and sparse attention to better focus on key nodes.\n\nOur 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.\n\n> **W2. Actual Operational Settings**\n\nWe validate our model on 64 real-world industrial  insatnces from MTPOMO. The table shows the average objective values.\n\n| MTPOMO | MVMoE | RF-TE | CaDA | CaDA x 32 |\n| ------ | ----- | ----- | ---- | -------------- |\n| 4262   | 4260  | 4080  | 4026 | 3983           |\n\n> **W4. Interaction Visualizations:** \n\nFigure 1 in the **PDF** illustrates the interaction mechanism: the prompt is concatenated with the initial node embeddings and fed into the global branch.\n\n> **W5. How Attention Weights are Visualized**\n\nWe 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.\n\n> **S1. Clarification of Parameters**\n\nThe 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}$.\n\n> **S2. Discussion of Practical Significance**\n\nCaDA 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.\n\n> **S3. Ablation Visualizations for Sparse Attention**\n\nThank 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.\n\n>  **S5. Qualitative Analysis of Real-World Solutions**\n\nWe provide a qualitative analysis in Figure 3 of the **PDF**, which shows that CaDA's solution is more similar to the best-known solution.\n\n> **S6 Standardization of Formatting and Grammar**\n\nThank you for your suggestion. We will review the entire manuscript and standardize the formatting and grammar in the mentioned sections.\n\n> **Q1. Design of the MLP in the Prompt**\n\n1. 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.\n3. Ablation tests show that MLP modifications result in slight performance drops, the current design performs best.\n\n|MLP with BatchNorm|MLP w/o Norm|CaDA|\n|-- |-|-|\n|1.77%| 1.75%|1.71%|\n\n> **Q2. Fusion Strategy Design**\n\nThank 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.\n\n|Fusion by CrossAttn|Fusion by Concat|CaDA|\n|-|-|-|\n|1.873%|1.831%|1.714%|\n\n> **Q5. Systematic Interpretation of Attention Patterns**\n\nThe 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.\n\n> **Q6. Sensitivity to k Parameter**\n\nThank 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.\n\n> **Q7. Training Stability**\n\nNo, the training of CaDA is stable. The loss curves for CaDA are shown in Figure 2 of the **PDF**.", "claims_and_evidence": "The claims made in this submission are well-supported by comprehensive evidence, including ablation studies, comparative experiments, and visualization analyses. The authors have addressed potential weaknesses in existing methods and provided convincing validation for their proposed approach.\n\n1. Existing cross-problem NCO methods for VRPs are constraint-unaware and rely solely on global connectivity, limiting their performance. The authors provide a thorough review of existing methods (Section 2) and identify specific limitations in their approach to handling constraints and node relationships. This sets a clear foundation for their proposed improvements.\n\n2. CaDA's constraint prompt and dual-attention mechanism improve cross-problem learning performance. The ablation studies in Section 4.4 demonstrate that removing either component (constraint prompt or sparse attention) results in performance degradation. This directly supports the effectiveness of both mechanisms.\n\n3. CaDA achieves state-of-the-art results across all tested VRPs. The comprehensive experimental results in Section 4 show that CaDA outperforms existing methods on 16 different VRP variants. The results include statistical comparisons and gap percentages relative to traditional solvers.\n\n4. The dual-attention mechanism allows the model to focus on important connections while maintaining global context. The visualization of attention weights in Section 4.5 shows distinct patterns for different VRP variants, indicating that the sparse branch effectively focuses on key connections while the global branch maintains overall context.\n\n5. The constraint prompt effectively provides constraint information to the model. The attention distribution analysis in Section 4.5 demonstrates that CaDA with the constraint prompt exhibits different attention behaviors for different problems, while CaDA without the prompt does not. This directly supports the effectiveness of the constraint prompt.\n\nWhile the evidence is generally strong, there are a few areas where additional support could strengthen the claims:\n\n1. Computational efficiency analysis: The paper focuses primarily on solution quality but could benefit from a more detailed analysis of computational efficiency, especially for larger-scale problems beyond 100 nodes.\n\n2. Generalization to unseen constraints: The zero-shot generalization capability to entirely new constraint combinations (beyond the 5 studied) could be further explored to demonstrate the full potential of the constraint prompt mechanism.", "methods_and_evaluation_criteria": "The proposed methods in this paper, namely the Constraint-Aware Dual-Attention Model (CaDA), make excellent sense for addressing the cross-problem vehicle routing problem (VRP) challenges identified in the paper. The authors have identified key limitations in existing neural combinatorial optimization approaches for VRPs—specifically, the lack of constraint awareness and inefficient representation learning due to global connectivity—and have developed targeted solutions to these problems.\n\nThe dual-attention mechanism, combining global and sparse branches, directly addresses the need for both broad contextual understanding and focused attention on key node relationships in routing problems. This approach seems particularly well-suited to VRPs, where both global structure (like overall route efficiency) and local details (like specific customer sequences) significantly impact solution quality.\n\nThe constraint prompt mechanism effectively incorporates problem-specific information into the model, allowing it to handle diverse VRP variants without requiring separate training for each problem type. This is crucial for developing a generalizable cross-problem solver, as real-world logistics problems often involve varying combinations of constraints.\n\nThe evaluation criteria, including comprehensive testing across 16 VRP variants and comparison against both traditional solvers and state-of-the-art neural methods, provide a robust framework for assessing the model's performance. The use of gap percentage as a performance metric aligns with standard practices in combinatorial optimization and clearly demonstrates the practical significance of the improvements achieved by CaDA.\n\nThe ablation studies further strengthen the evaluation by isolating the contributions of specific model components, providing evidence for the effectiveness of both the constraint prompt and dual-attention mechanisms. These studies help establish that the proposed innovations are indeed responsible for the performance improvements observed.\n\nOverall, the proposed methods and evaluation criteria are well-aligned with the problem objectives and demonstrate a thoughtful approach to advancing neural combinatorial optimization for VRPs.", "theoretical_claims": "The paper primarily focuses on empirical validation of the proposed CaDA model rather than presenting formal theoretical claims with proofs. The claims made are mostly about the effectiveness of the model architecture and its components, supported by experimental results rather than theoretical analysis:\n\n- Comprehensive experimental results across 16 VRP variants\n\n- Ablation studies showing the contribution of each component\n\n- Visualization of attention patterns demonstrating constraint awareness\n\n- Comparison against state-of-the-art methods\n\nWhile the paper does not contain formal theoretical claims with proofs, the empirical evidence provided is substantial and convincing for the claims made. The authors have appropriately focused on empirical validation given the nature of the problem and the proposed solution.", "experimental_designs_or_analyses": "he experimental design and analysis in this paper are robust and valid, providing convincing evidence for the effectiveness of the proposed CaDA model. The comprehensive evaluation across multiple problem variants, appropriate baseline comparisons, and insightful ablation studies all contribute to a strong experimental foundation for the claims made. \n\n1. Experimental Setup and Design\n\nThe experimental design is comprehensive and well-structured. The authors evaluate CaDA across 16 different VRP variants with varying constraints, which demonstrates the model's versatility and generalization capabilities. The use of both 50-node and 100-node instances allows assessment of performance across different problem scales.\n\nThe experimental setup is valid for testing cross-problem learning capabilities. The inclusion of both traditional solvers (PyVRP, OR-Tools) and state-of-the-art neural solvers as baselines provides a robust comparison framework.\n\n2. Selection and Use of Baseline Methods\n\nThe choice of baseline methods is appropriate and comprehensive. The authors compare against both traditional heuristic solvers and multiple neural approaches, including MTPOMO, MVMoE, and various RouteFinder variants.\n\nThe baselines are implemented correctly, with the authors using open-source code where available and following the same training protocols for fair comparison. The time limits for traditional solvers (10s for VRP50, 20s for VRP100) are reasonable and allow meaningful comparison with the neural methods.\n\n3. Performance Metrics and Statistical Analysis\n\nThe primary metric, gap percentage relative to traditional solvers, is appropriate for combinatorial optimization problems. The inclusion of objective function values and running times provides a complete picture of performance.\n\nThe statistical analysis is sound. The results are presented with sufficient detail, allowing readers to assess the significance of performance differences. The use of 1K test instances per VRP variant ensures reliable performance estimates.\n\n4. Ablation Studies\n\nThe ablation studies are well-designed and effectively isolate the contributions of the constraint prompt and dual-attention mechanisms.\nThe ablation studies are valid and provide clear evidence for the effectiveness of each component. The results show consistent performance improvements when both components are included, supporting the claims made.\n\n5. Visualization and Interpretation of Results\n\nThe visualization of attention weights is insightful and supports the claims about constraint awareness.\nThe interpretation of results is appropriate. The authors correctly link the observed attention patterns to the expected behavior for different VRP variants, demonstrating that the model learns meaningful representations.\n\n6. Real-World Validation\n\nThe evaluation on real-world instances from CVRPLib is a valuable addition to the experimental analysis.\nThe real-world validation is appropriately conducted, with results showing that CaDA generalizes well beyond synthetic datasets. The comparison with existing methods on these benchmarks further strengthens the claims.\n\nWhile the experimental design is generally sound, there are a few areas where additional details or analyses could enhance the validity:\n\n1.Statistical Significance Testing: The paper could benefit from explicit statistical significance testing between CaDA and baseline methods to quantify the confidence in performance differences.\n\n2.Computational Efficiency Analysis: A more detailed analysis of computational resources required by CaDA compared to baseline methods would be valuable, especially for larger problem instances.\n\n3. Generalization to Unseen Problems: While CaDA demonstrates strong performance across 16 VRP variants, testing its zero-shot generalization to completely new problem types or constraint combinations would further validate its cross-problem capabilities.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1. Originality:\n\nThe paper demonstrates strong originality through its creative combination of constraint prompts and dual-attention mechanisms specifically tailored for cross-problem VRP solving. This represents a novel adaptation of techniques from natural language processing (prompting) and computer vision (multi-branch architectures) to combinatorial optimization.\n\nThe constraint prompt mechanism is particularly innovative in how it encodes problem-specific information to guide the model's attention, addressing a significant limitation in previous neural VRP solvers that lacked constraint awareness.\n\n2. Significance:\n\nThe work addresses a practically significant problem with direct real-world applications in logistics and transportation. The comprehensive evaluation across 16 VRP variants demonstrates the model's versatility and potential impact across diverse routing scenarios.\n\nThe performance improvements over existing state-of-the-art methods are substantial and practically meaningful, particularly given the computational efficiency advantages of neural solvers compared to traditional heuristic approaches.\n\n3. Clarity:\n\nThe paper is exceptionally well-written and well-structured, making complex concepts accessible to a broad audience. The methodology is clearly explained, with appropriate technical details provided in both the main text and supplementary material.\n\nThe experimental results are presented with transparency, including detailed comparisons with baseline methods, ablation studies, and visualizations that help readers understand the model's behavior.\n\nWeaknesses:\n\n1. Originality:\n\nWhile the combination of techniques is novel, the individual components (prompting, attention mechanisms) have precedents in other domains. The paper could benefit from more extensive discussion of how this specific integration addresses limitations in previous VRP solvers beyond what has been described.\n\n2. Significance:\n\nThe practical impact would be further strengthened by including case studies with logistics companies or real-world deployment scenarios. While the CVRPLib benchmarks are valuable, demonstrating the model's effectiveness in actual operational settings would enhance its perceived significance.\n\nThe computational efficiency analysis is somewhat limited, particularly for very large-scale problems beyond 100 nodes, which might restrict its applicability in certain high-stakes logistics scenarios.\n\n3. Clarity:\n\nSome sections could benefit from additional visualizations or examples to further clarify complex concepts, especially regarding how the constraint prompt interacts with the dual-attention mechanism in practice.\n\nThe paper could provide more detailed explanations of how the attention weights are visualized and interpreted, which might help readers better understand the model's decision-making process.", "other_comments_or_suggestions": "1. Clarification of Prompt Parameters:\n\nIn Section 3.2 (Constraint Prompt), the notation for the prompt generation could be slightly clarified. The dimensions of the learnable parameters Wa, ba, Wb, and bb in Equation 5 should be explicitly stated to help readers understand the computational aspects of the prompt mechanism.\n\n2. Practical Significance of Performance Gaps:\n\nIn Section 4.3 (Main Results), when discussing the performance gaps between CaDA and other methods, a brief discussion about the practical significance of these percentage differences in real-world logistics operations would be valuable. This could help readers better appreciate the real-world impact of the performance improvements.\n\n3. Additional Visualizations for Ablation Study:\n\nFor the ablation study in Section 4.4, consider including additional visualizations comparing the attention patterns of CaDA with and without the sparse attention mechanism. This would provide further insight into how each component contributes to the model's performance and decision-making process.\n\n4. Computational Efficiency Analysis:\n\nA more detailed discussion of computational efficiency, particularly regarding how the dual-attention mechanism affects inference time compared to baseline methods, would strengthen the paper. This could include specific comparisons of runtime for different problem sizes and configurations.\n\n5. Qualitative Analysis of Real-World Solutions:\n\nIn the real-world validation section (Appendix C.4), include a qualitative analysis of the solutions generated by CaDA for specific instances. Highlighting how the model's decisions align with expected behaviors given the constraints would provide additional confidence in its practical applicability.\n\nSome formatting and grammar need to be standardized, for example: Page 3, Section 3.1,Page 5, Section 3.4,Page 7, Section 4.2,Page 9, Figure 5,Page 11, Section 4.5.", "questions_for_authors": "1. Constraint Prompt Design Choices:\n\nThe constraint prompt is implemented as a multi-hot vector processed through an MLP. Why was an MLP chosen instead of other methods for incorporating constraint information (e.g., attention-based mechanisms or simple concatenation)? How sensitive is the model's performance to the specific architecture of the MLP?\n\nIf the MLP was chosen due to empirical testing showing superior performance compared to alternatives, this would strengthen the technical justification for the design. If no alternatives were tested, it might suggest that the prompt mechanism could be further optimized.\n\n2. Dual-Attention Architecture Alternatives:\n\nWere alternative architectures considered for combining the global and sparse attention branches (e.g., different fusion strategies or alternative attention mechanisms)? How did you settle on the current design?\n\nIf multiple alternatives were explored with the current design showing clear advantages, this would demonstrate thorough architectural search. If not, it might indicate potential for further improvement.\n\n3. Zero-Shot Generalization to New Constraints:\n\nSuccessful zero-shot generalization to entirely new constraint combinations would significantly enhance the perceived significance and versatility of the model.\n\nHave you tested CaDA's zero-shot generalization capabilities on problem instances with combinations of constraints not seen during training? How would you expect the model to perform in such scenarios?\n\n4. Inference Time Analysis:\n\nHow does CaDA's inference time compare to traditional solvers and other neural methods, especially for larger problem instances beyond 100 nodes? What is the computational overhead of the dual-attention mechanism compared to standard transformers?\n\nIf CaDA maintains its efficiency advantages at larger scales, this would strengthen its practical relevance. If inference time becomes prohibitive, it might limit real-world applicability.\n\n5. Systematic Interpretation of Attention Patterns:\n\nWhile the attention visualization shows different patterns for different VRP variants, is there a systematic way to interpret these patterns in terms of routing strategies, or are they primarily qualitative illustrations?\n\nIf there's a systematic interpretation method, it would demonstrate deeper understanding of the model's decision-making. If not, it might suggest a need for further interpretability research.\n\n6. Sensitivity to Top-k Parameter:\n\nThe Top-k value is set to N/2 as the standard setting. How sensitive is the model's performance to this parameter? Have you explored a wider range of k values beyond what's shown in Figure 6?\n\nIf performance is robust across a range of k values, it suggests the mechanism is reliable. If performance is highly sensitive, it might indicate the need for careful hyperparameter tuning in practice.\n\n7. Training Stability:\n\nDid you encounter any training stability issues, particularly with the dual-attention mechanism and constraint prompt? How did you address them?\n\nEvidence of stable training would support the practicality of implementing the model. If significant instability was encountered, it might indicate areas where the architecture could be refined.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ce7KA4kaKm", "reviewer": "Reviewer_rF78", "summary": "This paper presents Constraint-Aware Dual-Attention (CaDA), a new neural architecture for solving multi-task vehicle routing problems (VRPs). CaDA integrates a constraint prompt to help the model recognize the specific constraints of the current task, along with a dual-attention architecture that combines a standard attention branch and a top-k sparse attention branch. This architecture ensures that the encoding process is both focused on promising nodes and informed by global context. The model is evaluated on 16 different VRP variants, demonstrating significant improvements over existing neural solvers.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> **W1&Q1. Results on Other Distribution**\n\nThank 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.\n\n| VRP50 | explosion | implosion | rotation | linearprojection | expansion | grid  |\n| ----- | --------- | --------- | -------- | ---------------- | --------- | ----- |\n| MTVRP | 2.65%     | 2.28%     | 2.92%    | 3.45%            | 3.02%     | 2.25% |\n| MVMoE | 2.54%     | 2.18%     | 2.77%    | 3.32%            | 2.89%     | 2.15% |\n| RF-TE | 2.25%     | 1.95%     | 2.39%    | 2.76%            | 2.59%     | 1.91% |\n| CaDA  | 1.88%     | 1.63%     | 1.97%    | 2.31%            | 2.13%     | 1.59% |\n\n> **W2. Code Availability**\n\nThank 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.\n\n\n\n> **C1-C3**: Some symbols are confusing, V in line 163, H_c^{(L)} in line 261.\n\nThank 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.\n\n> **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?\n\nThank 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.\n\n> **Q3. Clarification of Implementation**\n\nIn 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.\n\n> **Q4. Training Settings**\n\nProblem 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.\n\n> **Q5.Explanation of Attention Distributions**\n\nFigure 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. \n\nFor 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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "The methods and evaluation criteria proposed in the paper are effective for addressing the intended problems.", "theoretical_claims": "The paper does not involve theoretical claims.", "experimental_designs_or_analyses": "I have checked all the experiments in the experimental section.", "relation_to_broader_scientific_literature": "It contributes to the community of neural combinatorial optimization. It introduces an efficient constraint prompt mechanism to improve constraint awareness. It introduces the top-k sparse operation to focus on more related node pairs.", "essential_references_not_discussed": "The paper has included the main related works that are crucial for understanding the context and significance of their contributions.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The proposed two-branch structure is interesting.\n2. It achieves SOTA results on cross-problem learning for routing problems.\n\nWeaknesses:\n\nThere is no obvious weakness. However, some experimental results (refer to questions) require further clarification to enhance their interpretability. Additionally, since the code has not been made publicly available, the reproducibility of the experiments cannot be fully verified.", "other_comments_or_suggestions": "1. Some symbols are confusing. For example, the use of $\\boldsymbol{\\tau}$ in line 88 might represent a solution that includes multiple sub-solutions, i.e., it is a set of tuples, and $\\boldsymbol{\\tau}^{i}$ represents the i-th sub-solution. However, $\\boldsymbol{\\tau}$ in line 152 represents a solution as a tuple, and $\\boldsymbol{\\tau}^{i}$ represents the i-th complete feasible solution. \n2. Given that $V$ in line 163 is a vector, it might be clearer to use lowercase letters to represent it.\n3. In line 261, $H_c^{(L)} $ might should be corrected to $ H_c$.", "questions_for_authors": "1. The testing data distribution seems limited. Can CaDA achieve better performance across a broader range of distributions? For example, in [1], it provides instances with various distributions including grid, explosion, implosion, rotation, expansion, etc. It would be beneficial to test the proposed method on these varied distributions to validate its generalization capabilities.\n2. Could you further explain Figure 7? Why does CaDA w/o the prompt show the same attention distribution for CVRP and OVRP?\n3. The experimental setting in the \"Different Sparse Functions\" section (line 400) is confusing. What do you mean by \"Softmax+Top-k\"? Could you further explain how \"a standard Softmax and a representative sparse function α-entmax\" modify parts of CaDA?\n4. Some experimental settings are unclear.  What is the ratio of different VRP variants in the training dataset during the training process?\n5. Figure 8 needs further explanation. Why does Figure 8 appear symmetrical? And when $(i, j)$ is illegal and j will not be the next node of i, i.e., $P_{i,j} < 0$,  why are there still many $A_{ij}$ of CaDA that have large values?  \n[1] Towards omni-generalizable neural methods for vehicle routing problems. ICML, 2023.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3JaJLhaiNv", "reviewer": "Reviewer_KzHG", "summary": "The paper proposes a novel architecture to tackle various variants of vehicle routing problems (VRP). The main idea of this architecture is to encode the different possible constraints in a so-called \"constraint prompt\" and use in conjunction two attention-based encoders of a VRP instance, one global and one sparse (only using top-k attention).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> **E1, Q2. Generalization Capability**\n\nThank you for raising this valuable point. We conduct experiments to evaluate zero-shot and fine-tuning performance on two unseen constraints.\n\n**Unseen Constraints:**\n\n1. Multi-Depot (MD),  vehicles can start from any depot but must return to their respective starting depot. The evaluation includes 16 VRPs.\n2. Mixed Backhaul (MB), linehaul and backhaul customers can be mixed along a route. The evaluation includes 8 VRPs.\n\n**Results**:  \n\n|0-shot|MTPOMO|MVMoE|RF-TE|CaDA|CaDA$\\times$32|\n|-|-|-|-|-|-|\n|MD|42.29%|45.56%|41.93%|39.34%|28.86%|\n|MB|9.28%|8.74%|9.12%|8.46%|7.40%|\n\n|MD\\Epoch|1|5|10|\n|-|-|-|-|\n|MTPOMO|16.70%|11.32%|9.32%|\n|MVMoE|17.88%|11.92%|9.74%|\n|RF-TE|14.11%|7.71%|6.96%|\n|CaDA|11.01%|6.77%|5.90%|\n\n1. 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%).  \n\n2. Fine-Tuning:  After the first epoch, CaDA’s gap reduces by 72% (39.34% $\\to$ 11.01%), outperforming baselines’ improvements of  61–66% .  \n\nWe will add the results and discussion into the revised manucript.\n\n>  **C1,Q1.Training Process Clarification**\n\n1. Mixed Batch Training: Yes, we employ this to stabilize convergence.\n2. Reward Normalization: No reward normalization is applied.  \n\nWe will include these explanations in Section 4 of the revised manuscript.\n\n> **C2. Discussion of Model Sizes**\n\nMvMoE 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.\n\n> **C3. Hyperparameters Clarification**\n\n\nYes, we confirm that for each baseline, the hyperparameters suggested by its authors were used.\n\n> **C4. Ablation Study About Sparse Branch**\n\nWe respectfully clarify that:\n\n- In our paper, CaDA w/o Sparse retains the two-branch structure, but both use global attention.\n\n- The sparse attention consistently improved performance across all 16 VRPs (0.003–0.209\\%, see Figure 4).\n- The sparse attention yields notable gains on variants such as VRPBL (0.209%), OVRP (0.173%), OVRPL (0.163%).\n\n> **C5. Removing the Global Branch**\n\nThank 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.\n\n|Branch|Attention|Gap|\n|:-|-|-|\n|Single|GA|1.92%|\n|Single|SA|1.96%|\n|Dual|GA|1.80%|\n|Dual|SA|1.75%|\n|Dual|GA+SA|1.71%|\n\n> **C6. Comparison of k = N/2 and N/4**\n\nN/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. \n\n> **C7. CaDA$\\times$32 on 16 VRPs**\n\nThank you for this valuable point. Below, we provide the performance results of CaDA $\\times  32$  on the 16 VRPs , which further improves the performance.\n\n|MTPOMO|MVMoE|RF-POMO|RF-MoE|RF-TE|CaDA|CaDA$\\times$32|\n|-|-|-|-|-|-|-|\n|2.45%|2.29%|2.14%|2.16%|1.97%|1.71%|1.35%|\n\n> **R1. References to be Discussed**\n\nThank 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. \n\n> **W1**:  In (1), \\tau_t may be a partial sub-tour.\n>\n> **W3**:  In (14), should it be H_c^{(L)}? W_t should be W_c?\n>\n> **W4**: Below (16), what is the index g of \\pi_g? u should be bolded.\n\nThank you very much for your careful checks. We will correct these notational issues as follows:\n\n- 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.\n- 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.\n- W4: Below (16), the g should be t. We will bold u.\n\n> **W2.  LayerNorm and SwiGLU Design**\n\nThank you for the feedback. Below we clarify these design choices:\n\n- 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.\n- SwiGLU: Following Berto et al. (2024), we use SwiGLU to improve convergence.", "claims_and_evidence": "The authors demonstrate that their trained model can outperform other multi-task neural solvers. To make those results more conclusive, it would have been nice to discuss the following points:\n- The explanation about the training process is a bit too succinct for me, since it simply refers to Berto et al. (2024). I would suggest the authors to explain/recall the training process, at least in the appendix. For instance, do the authors use mixed batch training and/or multi-task reward normalization? \n- A discussion about model sizes of the different methods would help understand where the performance is coming from. \n- An explanation about how the hyperparameters were obtained is missing. I believe that for the baselines, the hyperparameters suggested by their authors were used. It would be nice to confirm this point.\n\nThe authors also conduct an ablation study, which is helpful, although it seems to suggest that the sparse branch has a limited contribution. In addition, I think to make this ablation study complete, it would have been nice to test a version without the global branch.\nAlso, given the closeness of the results for N/2 and N/4, wouldn't it be better to use a smaller k than N/2? N/3 or N/4?\n\nThe performance of the proposed method is also confirmed on CVRPLIB. However, the best method is a bit strange to me. If I understand correctly, it consists in giving to the neural solver all possible combination of constraints to generate the constraint prompt, regardless of the constraints in effect in a solved instance. This would suggest using a similar technique when solving the 16 types of VRP in Table 1, which by construction can only improve the results. In that sense, the constraint prompt seems to encode only loosely a set of constraints.", "methods_and_evaluation_criteria": "The proposed method uses techniques that have been proposed in other contexts (as discussed by the authors in their related work in the appendix for instance) and combine them in a somewhat novel way.", "theoretical_claims": "There is no theoretical claim.", "experimental_designs_or_analyses": "The experiments are mainly conducted according to the experimental setting proposed by Berto et al. (2024). However, in contrast to previous works in multi-task solvers, the authors do not discuss much the generalization capability (e.g., one-shot or few-shot) of their method. I believe this aspect may be important in the multi-task setting.", "relation_to_broader_scientific_literature": "I believe that the authors clearly discuss the related work, notably the recent multi-task solvers and other techniques that inspired or are related to their propositions (e.g., multi-branch, sparse attention).", "essential_references_not_discussed": "Regarding the multi-branch architecture, there are some recent propositions using similar ideas (multi-view) for solving VRP, e.g.,\nGao, C., Shang, H., Xue, K., Li, D., and Qian, C. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. arXiv, 2023\nFang, H., Song, Z., Weng, P., and Ban, Y. Invit: A generalizable routing problem solver with invariant nested view transformer. In Forty-first International Conference on Machine Learning, 2024", "other_strengths_and_weaknesses": "The paper is quite well-written and clear, although there are a few points that could be improved in the exposition, e.g.:\n- In (1), \\tau_t may actually be a partial sub-tour\n- Some of the architectural design decisions could be better explained in the main paper (e.g., LayerNorm in (5), or SwiGLU)\n- In (14), should it be H_c^{(L)}? and W_t should be W_c?\n- Below (16), what is the index g of \\pi_g? Also, in the line below, u should be bolded.", "other_comments_or_suggestions": "None", "questions_for_authors": "1. Could you clarify the training process?\n2. Does the current evaluation consider generalization to new tasks?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YpXakSG9e2", "reviewer": "Reviewer_9jwN", "summary": "This paper targets cross-problem learning for vehicle routing problems. It proposes Constraint-Aware Dual-Attention (CaDA), which introduces a constraint prompt to enhance constraint awareness and employs a dual-attention mechanism consisting of a global branch and a sparse branch. The sparse branch utilizes a top-k attention strategy to focus on key node pairs. Experimental results across 16 VRP variants demonstrate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> **E1. Prompt Ablation Study**\n\nTo 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:\n\n| Prompt on Both Branches | Prompt on Sparse Branch | CaDA  |\n| ----------------------- | ----------------------- | ----- |\n| 1.94%                   | 1.80%                   | 1.71% |\n\n> **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?\n\nThe 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.\n\n> **W2,Q2. Fine-Tune Performance**\n\nThank 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.\n\n> **C1. Clarification on Sparse Branch Data Flow**\n\nThe 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.\n\n> **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.\n\nWe appreciate your careful review. We will revise them accordingly in the revised manuscript.\n\n> **C3. Clarification on Runtime Comparisons**\n\n1)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.\n\n> **C5, C6. Top-k Gap Values and Top-k Parameter Range**\n\nAs 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:\n\n| k=2   | k=6 (N/8) | k=10  | k=12 (N/4) | k=25 (N/2) | k=40  |\n| ----- | --------- | ----- | ---------- | ---------- | ----- |\n| 1.80% | 1.73%     | 1.72% | 1.75%      | 1.71%      | 1.77% |\n\n> **Q3. Explantion about Ablation Study**\n\nThank you for your question. Here we further explain the role of the sparse branch.\n\n- As detailed in our responses to W1 and Q1, sparse attention is beneficial for addressing the limitations of standard attention mechanisms when solving VRPs.\n- Additionally, our visualization (see Figure 4 in [PDF]([Figure.pdf](https://anonymous.4open.science/api/repo/CaDA_illustration-FC5A/file/Figure.pdf?v=13d844ac))) 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.\n\n>**Q4. Paper to be Cited**\n\nThank you for your feedback. We will add this paper (UniCO, ICLR 2025) in the revised manuscript.\n\n> **Q5. Explantion about Ablation Study**\n\nThank 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. \n\nConsequently, 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.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The basic idea of the proposed CaDA is reasonable for the problem at hand, and the evaluation criteria are appropriate.", "theoretical_claims": "No theoretical claims are presented in this paper.", "experimental_designs_or_analyses": "The baselines and benchmark instances are sound. For the ablation experiment concerning the position of the prompt (Figure 5(a)), it would be beneficial to include an experiment that adds the prompt to both branches.", "relation_to_broader_scientific_literature": "The two key contributions of the paper are: it proposes the use of a constraint prompt to enhance task awareness, which has not been emphasized in existing works [1,2,3] for multi-task VRPs. Additionally, it introduces a dual-attention mechanism that incorporates a sparse attention branch to learn from more promising connections, while current methods [1, 2, 3] rely solely on standard attention mechanisms.\n[1] Multi-task vehicle routing solver with mixture-of-experts. In International Conference on Machine Learning (ICML), 2024\n[2] Multi-task learning for routing problem with cross-problem zero-shot generalization. In The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2024). Association for Computing Machinery, 2024.\n[3] Routefinder: Towards foundation models for vehicle routing problems. In ICML 2024 Workshop on Foundation Models in the Wild, 2024.", "essential_references_not_discussed": "All relevant prior works necessary to understand the key contributions of this paper have been cited and discussed.", "other_strengths_and_weaknesses": "Strengths:\n1. This paper demonstrates strong performance across 16 vehicle routing problems and real-world instances.\n2. The paper is well-structured and easy to follow.\n\nWeaknesses:\n1. The motivation and function of the key components, e.g., the sparse branch,need further explaination.\n2. The fine-tune performance is not discussed.", "other_comments_or_suggestions": "1. In Figure 2, the subsequent data flow of the sparse branch is unclear.\n2. The formula in line 270 should probably be written as $\\pi_{\\theta}({\\tau}_{t} = i \\mid \\mathcal{V}, \\boldsymbol{\\tau}\\_{1:t-1})$.\n3. The paper mentions that CaDA significantly reduces the runtime compared to state-of-the-art heuristic solvers. However, the results in Table 1 indicate that the runtime of CaDA is nearly identical to that of RF-TE, and it does not seem to have a significant advantage over other methods. Additionally, why do HGS-PyVRP and OR-Tools have exactly the same runtime?\n4. The explanations for Figures 5(a) and 5(b) are split across two columns and are too close together, which could easily lead to confusion.\n5. Please provide the specific average gap values in Figure 6.\n6. It is recommended to test more data points in the ablation study on 'top-k' to better demonstrate performance variations.\n7. \"Kernel density estimation (KDE)\" appears twice, in lines 394 and 490. It would be better to mention the full term and its abbreviation only once.\n8. In Equation (19) in line 758, a comma should be used instead of a period.", "questions_for_authors": "1. Further explanation about motivation is needed. In the proposed method, the sparse branch is introduced to focus on \"more related node pairs.\" Could you clarify why this is important?\n\n2. How is the fine-tune performance on the VRPs.\n\n3. In Table 2, why does CaDA w/o Sparse perform worse than CaDA? Intuitively, two standard attention branches with higher model complexity should have a stronger representation power than one standard attention branch and one sparse attention branch.\n\n4. Some recent multi-task learning methods for NCO (e.g., [1]) are missing in the related work section.\n\n5. In Figure 4, CaDA w/o Prompt shows a considerable performance drop on OVRPBL compared to other problems. Can the authors provide an explanation for why this happens?\n\n[1] UniCO: On Unified Combinatorial Optimization via Problem Reduction to Matrix-Encoded General TSP. In International Conference on Learning Representations, 2025", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposed a learning based cross-problem solver for different VRP variants. Reviewers acknowledged the technical contributions and promising results, but also pointed out several weaknesses including relatively low novetly since it combines existing techniques and missing experimental details.
Decision: Accept (poster)