Collaboration! Towards Robust Neural Methods for Routing Problems
Authors: Jianan Zhou
Yaoxin Wu
Zhiguang Cao
Wen Song
Jie Zhang
Zhiqi Shen
Venue: NeurIPS 2024 poster (2024)
Keywords: Combinatorial Optimization
Vehicle Routing Problem
Ensemble
Robustness
Primary area: optimization

Abstract: Despite enjoying desirable efficiency and reduced reliance on domain expertise, existing neural methods for vehicle routing problems (VRPs) suffer from severe robustness issues — their performance significantly deteriorates on clean instances with crafted perturbations. To enhance robustness, we propose an ensemble-based *Collaborative Neural Framework (CNF)* w.r.t. the defense of neural VRP methods, which is crucial yet underexplored in the literature. Given a neural VRP method, we adversarially train multiple models in a collaborative manner to synergistically promote robustness against attacks, while boosting standard generalization on clean instances. A neural router is designed to adeptly distribute training instances among models, enhancing overall load balancing and collaborative efficacy. Extensive experiments verify the effectiveness and versatility of CNF in defending against various attacks across different neural VRP methods. Notably, our approach also achieves impressive out-of-distribution generalization on benchmark instances.

Collaboration! Towards Robust Neural Methods for Routing Problems
Jianan Zhou Nanyang Technological University j jianan0040e ntu. edu. sg
Yaoxin Wu" Eindhoven University of Technology y. wu20tue.
Zhiguang Cao Singapore Management University zgcao8smu. edu. sg
Wen Song
Shandong University
wensongdemail. sdu. edu. cn
Jie Zhang, Zhiqi Shen Nanyang Technological University {zhangj zqshen) @ntu. @ntu.edu..s
Abstract
Despite enjoying desirable efficiency and reduced reliance on domain expertise, existing neural methods for vehicle routing problems (VRPs) suffer from severe robustness issues their performance significantly deteriorates on clean instances with crafted perturbations. enhance robustness, we propose an ensemble-bat based Collaborative Neural Frumework (CNF) w.r.t. the defense of neural VRP methods, which is crucial yet underexplored in the literature. Given a neural VRP method, adversarially train multiple models in collaborative manner synergistically promote robustness against attacks, while boosting standard generalization on clean instances. A neural router is designed to adeptly distribute training instances among models, enhancing overall load balancing and collaborative efficacy. Extensive experiments verify the effectiveness and versatility of CNF in defending against various attacks across different neural VRP methods. Notably, our approach also generalization benchmark instances.
achieves impressive
Introduction
Combinatorial optimization problems (COPs) are crucial yet challenging solve due to the NP- hardness. Neural combinatorial optimization (NCO) aims to leverage machine learning (ML) to automatically learn powerful heuristics for solving COPs, and has attracted considerable attention recently [2]. Among them, a large number of NCO works develop neural methods for vehicle routing of the most classic COPs with broad applications in transportation [54], logistics [35]. planning and scheduling [52], etc. With various training paradigms (e.g.. reinforcement learning (RL)), the neural methods learn construction improvement heuristies, which achieve petitive or even superior performance to the conventional algorithms. However, recent studies show that these neural methods are plagued by severe robustness issues [20], where their performance drops devastatingly on clean instances (sampled from the training distribution) with crafted perturbations.
problems (VRPs)
Although the robustness issue has been investigated in couple of recent works [87, 20, 42), the defensive methods on how to help forge sufficiently robust neural VRP methods are still underexplored.
Yaoxin Wu is the corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

KINO 23.80
CP Sp. Be-dh
Performancee on Instances
(b) Performance on Adversarial Instances
(c) Iusttatiion of
Figure (a-b) Performance of POMO [38] on TSPI00 against the attacker [87]. The value in brackets denotes the number of trained models. We report the average optimality (opt.) gap over 1000 test instances.
(c) Solution visualizations on an adversarial instance. These results reveal the vulnerability of existing neural methods to adversarial attacks, and the existence of undesirable trade-off between standard generalization (a) and adversarial robustness (b) VRPs. Details of the attacker and experimental setups can be found in Appendix B.1 and Section 5, respectively.
In particular, existing endcavours mainly focus on the attack side, where they propose different perturbation models to generate adversarial instances. On the defense side, they simply follow the vanilla adversarial training (AT) [48]. Concretely, treated as a min-max optimization problem, it first generates adversarial instances that maximally degrade the current model performance, and then minimizes the empirical losses of these adversarial variants. However, vanilla AT is known to face an undesirable trade-off [66, 85] between standard generalization (on clean instances) and adversarial robustness (against adversarial instances). As demonstrated in Fig. I, vanilla AT improves adversarial robustness of the neural VRP method at the expense of standard generalization (e.g.. POMO (1) vs. POMO AT (1)). One key reason is that the training model is not sufficiently expressive [20]. We empirically justify this viewpoint by increasing the model capacity through ensembling multiple models, which partially alleviates the trade-off. However, it is still an open question on how to effectively synergize multiple models to achieve favorable overall performance on both clean and adversarial instances within reasonable computational budget.
In this paper, we focus on the defense of neural VRP methods, aiming concurrently enhance both the standard generalization and adversarial robustness. We resort to the ensemble-based AT method achieve this objective. Instead of separately training multiple models, we propose Collaborative Neural Framework (CNF) to exert AT on multiple models a collaborative manner. Specifically, in the inner maximization optimization of CNF, we synergize multiple models to further generate the global adversarial instance for each clean instance by attacking the best- west-performing model, rather than only leveraging each model independently generate their own local adversarial instances. In doing so, the generated adversarial instances are diverse and strong in benefiting the policy exploration and attacking the models, respectively (see Section 4). In the outer minimization optimization of CNF, we train an attention- based neural router to forward instances to models for effective training, which helps achieve satisfactory load balancing and collaborative efficacy.
Our contributions are outlined as follows. 1) In contrast to the recent endeavors on the attack side, concentrate on the defense of neural VRP methods, which is crucial yet underexplored in the literature. We empirically observe that the defense through vanilla AT may lead to the undesirable trade-off between standard generalization and adversarial robustness in VRPs. sieemble-based collaborative neural framework to concurrently enhance the performance on both clean and adversarial instances. Specifically, we propose to further generate global adversarial instances, and design an attention-base effective training. 3) We evaluate the effectiveness and versatility of our method against various attacks on different VRPs, such as the symmetric and asymmetric traveling salesman problem (TSP, ATSP) and capacitated vehicle routing problem (CVRP). Results show that our framework can greatly improve the adversarial robustness of neural methods while even boosting the standard generalization. Beyond the expectation, we also observe the improved nut-of-distributiin (OOD) generalization on both synthetic and benchmark instances, which may suggest the favorable potential of our method in promoting various types of generalization of neural VRP methods.
We propose an
neural router to distribute instances to each model for
Note that in CO, there may not be an intentional attacker seeking to compromise the model in practice. In this paper, "attacker" refers to method of generating instances where the current model underperforms.

---

2 Related Work
Neural VRP Methods. Most neural VRP methods learn construction heuristics, which are mainly divided into two categories, i.e., autoregressive and non-autoregressive ones. Autoregressive methods sequentially construct the solution by adding one feasible node each step. [71] proposes the Pointer Network (Ptr-Net) to solve TSP with supervised learning. Subsequent works train Ptr-Net with RL to solve TSP [1] and CVRP [51]. [37] introduces the attention model (AM) based on the Transformer architecture [69] to solve a wide range of COPs including TSP and CVRP. [38] further proposes the policy optimization with multiple optima (POMO), which improves upon AM by exploiting solution symmetries. Further advancements [39, 34, 3, 24, 13, 44, 27, 45, 21, 12] are often developed on top of AM and POMO. Regarding non-autoregressive methods. the solution is typically constructed in a one-shot manner without iterative forward passing through the model. [31] leverages the graph convolutional network to predict the probability of each edge appearing on the optimal tour (i.e.. heat-map) using supervised learning. Recent works [17, 36, 56, 64, 49, 82, 33, 77] further improve its performance and scalability by using advanced models, training paradigms, and search strategies. We refer to [40, 28, 83, 88] for scalability studies, to [30, 5, 90, 18, 41, 16, 89, 4] for generalization studies, and to [11, 59, 84, 61] for other COP studies. On the other hand, some neural methods learn improvement heuristics to refine initial feasible solution iteratively, until a termination condition is satisfied. In this line of research, the classic local search methods and specialized heuristic solvers for VRPs are usually exploited [8. 43, 10, 76, 47, 78, 46]. In general, the improvement heuristies can achieve better performance than the construction ones, but at the expense of much longer inference time. In this paper, we focused autoregressive construction methods.
Robustness of Neural VRP Methods. There a recent research trend on the robustness of neural methods for COPs [68, 20, 42], with only a few works on VRPs [87, 20, 42]. In general, they primarily focus on attacking neural construction heuristics by introducing effective perturbation models to generate adversarial instances that are underperformed by the current model. Following the AT paradigm, [87] perturbs node coordinates of TSP instances by solving an inner maximization problem (similar to the fast gradient sign method [22]), and trains the model with a hardness-aware loss function. [20] proposes an efficient and sound perturbation model, which ensures the optimal solution to the perturbed TSP instance can be directly derived. It adversarially inserts several nodes into the clean instance by maximizing the cross-entropy over the edges, so that the predicted route is maximally different from the derived optimal one. [42] leverages a no- worse optimal cost guarantee (i.e., by lowering the cost of a partial problem) to generate adversarial instances for asymmetric TSP. However, existing methods mainly follow vanilla AT [48] to deploy the defense, leaving a considerable gap to further consolidate robustness.
restance-reweighee
Robustness in Other Domains. Deep neural networks are vulnerable to adversarial examples [22], spurring the development of numerous attack and defensive methods to mitigate the arisen security issue across various domains. 1) Vision: Early research adversarial robustness mainly focus on the continuous image domain (e.g.. at the granularity of pixels). The vanilla AT, as formulated by [48] through min-max optimization, has inspired significant advancements in the field [65, 60, 85, 7, 86]. 2) Language: This domain investigates how malicious inputs (c.g., characters and words) can deceive (large) language models into making incorrect decisions producing unintended outcomes [14, 72, 50, 91. 74]. Challenges include the discrete nature of natural languages and the complexity of linguistic structures, necessitating sophisticated techniques for generating and defending against adversarial attacks. 3) Graph: Graph neural networks are also susceptible to adversarial perturbations in the underlying graph structures [92], prompting research enhance their robustness (29, 15, 19, 23, 63). Similar to the language domain, challenges stem from the discrete nature of graphs and the interconnected nature of graph data. Although various defensive methods have been proposed for these specific domains, most are not adaptable to the VRP (or COP) domain due their needs for ground-truth labels, reliance on the imperceptible perturbation model, and unique challenges inherent in combinatorial optimization.
Preliminaries
3.1 Neural VRP Methods
Problem Definition. Without loss of generality, we define a VRP instance e over graph g = (V, g}. where V = (wx 1/ represents the node set, and (vi, By)) E E represents the edge set with 14 # e/.
3

---

The solution r to a VRP instance is tour, i.e., a sequence of nodes in V. The cost function e(-) computes the total length of a given tour. The objective to seek an optimal tour r" with the minimal cost: r² = arg min,ee c(7lz), where Φ is the set of all feasible tours which obey the problem-specific constraints. For example, a feasible tour in TSP should visit each node exactly once, and return to the starting node in the end. For CVRP, each customer node in V is associated with a demand 6, and a depot node vO is additionally added into V with 60 = O. Given the capacity Q for each vehicle, tour in CVRP consists of multiple sub-tours, each of which represents vehicle starting from vo. visiting a subset of nodes in and returning to vo. It is feasible if each customer node in V is visited exactly once, and the total demand in each sub-tour is upper bounded by Q. The optimality gap <(r)-o(r") x 100% is used to measure how far solution is from the optimal solution.
d(T))
Autoregressive Construction Methods. Popular neural methods [37, 38] construct a solution to a VRP instance following Markov Decision Process (MDP), where the policy is parameterized by a neural network with parameters 0. The policy takes the states as inputs, which are instantiated by features of the instance and the partially constructed solution. Then, it outputs the probability distribution of valid nodes to be visited next, from which an action is taken by either greedy rollout or sampling. After a complete tour is constructed, the probability of the tour can be factorized via the chain rule (T( I (x mh 2)), where za and Th represent the selected node and the partial solution at the 8th step, and S is the number of total steps. Typically, the reward is defined the negative length of tour -c(r(xr). The policy network is commonly trained with REINFORCE [75]. With a baseline function b(.) to reduce the gradient variance and stabilize the training. it estimates the gradient of the expected reward as:
vo[(0 = Epo(ria)((((T) Vo
3.2 Adversarial Training
Adversarial training is one of the most effective and practical techniques to equip deep learning models with adversarial robustness against crafted perturbations on the clean instance. In the supervised fashion, where the clean instance x and ground truth (GT) label y are given, AT is commonly formulated as min-max optimization problem:
min R (ev (((y, (+)),, with ā = arg max e.N fe(G.)))
(2)
where D is the data distribution; l is the loss function; fo(.) is the model prediction with parameters 0: No [xr] is the neighborhood around v, with its size constrained by the attack budget e. The solution
to the inner maximization is typically approximated by projected gradient descent:
((41) [[xG1=(==)) + signiign 2ce Ely, ())
(3)
where a is the step size; II is the projection operator that projects the adversarial instance back to the neighborhood No [x]; (f)) is the adversarial instance found at step t; and the sign operator used to take the gradient direction and carefully control the attack budget. Typically, (x))) is initialized by the clean instance or randomly perturbed instance with small Gaussian or Uniform noises. The adversarial instance is updated iteratively towards loss maximization until a stop criterion is satisfied.
AT for VRPs. Most ML research on adversarial robustness focuses on the continuous image domain [22, 48). We would like highlight two main differences in the context of discrete VRPs (or COPs). 1) Imperceptible perturbation: The adversarial instance ã is typically generated within a small neighborhood of the clean instance xr that the adversarial perturbation is imperceptible to human eyes. For example, the adversarial instance in image related tasks is typically bounded by M[[=]: : || - ق E|p S e under the lp norm threat model. When the attack budget is small enough, retains the GT label of x. However, it is not the case for VRPs due to the nature of discreteness. The optimal solution can be significantly changed even if only a small part of the instance modified. Therefore, the subjective imperceptible perturbation is not a realistic goal in VRPs, and we do not exert such an explicit imperceptible constraint on the perturbation model (see Appendix A for further discussions). In this paper, we set the attack budget within a reasonable range based on the attack methods. 2) Accuracy-rouustness trade-off: The standard generalization and adversarial robustness seem to be conflicting goals in image related tasks. With increasing adversarial robustness the standard generalization tends to decrease, and a number of works intend to mitigate such a trade-off in the image domain [66, 85, 73, 57, 80]. By contrast, recent work [20] claims the existence of
4

---

Instanee Set X
Locp
Logii Matris
Local Attuck
Naural Rosser
DJ
85 1.5
Opcimize
Global
Altack
Inner Maximization
Outer Minimization
The overview of CNF. Suppose we train M = 3 models (e = {01 82. 83}) on a batch (B = 3) of clean instances. The inner maximization generates local (Ø) and global (क) adversarial instances within T steps. In the outer minimization, neural router 6, is jointly trained to distribute instances the M models for training. Specifically, based on the logit matrix P predicted by the neural router, each model selects the instances with TopxC-largest logits (e.g., red ones). The neural router is optimized maximize the improvement of collaborative performance after each training step of θ. For simplicity, we omit the superscripts of instances in the outer minimization.
Figure 2:
neural solvers with high accuracy and robustness in COPs. They state that sufficiently expressive model does not suffer from the trade-off given the problem-specifte efficient and sound perturbation model, which guarantees the correct GT label of the perturbed instance. However, by following the vanilla AT, we empirically observe that the undesirable trade-off may still exist in VRPs (as shown in Fig. 1), which is mainly due the insufficient model capacity under the specific perturbation model. Furthermore, similar to combinatorial optimization, although the language and graph domains are also discrete, their methods cannot be trivially adapted VRPs (see Appendix A).
4 Collaborative Neural Framework
In this section, we first present the motivation and overview of the proposed framework, and then introduce the technical details. Overall, we propose a collaborative neural framework to synergistically promote adversarial robustness among multiple models, while boosting standard generalization. Since conducting AT for deep learning models from scratch is computationally expensive due to the extra inner maximization steps, we use the model pretrained on clean instances as a warm-start for subsequent AT steps. An overview of the proposed method is illustrated in Fig. 2.
Motivation. Motivated by the empirical observations that 1) existing neural VRP methods suffer from severe adversarial robustness issue; 2) undesirable trade-off between adversarial robustness and standard generalization may exist when following the vanilla AT, we propose to adversarially train multiple models in collaborative manner to mitigate the above- mentiondd issues within reasonable computational budget. It then raises the research question on how to effectively and efficiently train multiple models under the AT framework, involving a pair of inner maximization and outer minimization, which will detailed the following parts. Note that despite the accuracy-robustig trade-off being well-known research problem in the literature of adversarial ML. most works focus on the image domain. Due to the needs for GT labels or the dependence on the imperceptible perturbation model, their methods (c.g., TRADES [85]. Robust Self-Training with AT [57]) cannot be directly leveraged to solve this trade-off in VRPs. We refer to Appendix A for further discussions.
Overview. Given pretrained model Op. CNF deploys the AT its M copies (i.e., !!))
1 + fp) in collaborative manner. Concretely, at each training step, it first solves the inner maximization optimization to synergistically generate the local (ø) and global (σ) adversarial instances, on which the current models underperform. Then, in the outer minimization optimization, we jointly train an attention-based neural router 0, with all models by RL an end-to-end manner. By adaptively distributing instances to different models for training, the neural router can reasonably exploit the overall capacity of models and thus achieve satisfactory load balancing and collaborative efficacy. During inference, discard the neural router 0, and use the trained models θ to solve each
5

---

Algorithm 1 Collaborative Neural Framework for VRPs
Input: training steps: E, number of models: M, attack steps: T, batch size: B, pretrained model: Op:
Output: robust model set ( = {0(8))11
I: Initialize ( = =010)
0/7 0p, 0
2: for 1, ................................ E do
3: [0i] Sample a batch of clean instances
4: Initialize #1 1 5:() zs, vi [I, B) VjE
5: for = I..... d'do
D Inner Maximization
6:
[(() + Approximate solutions max { D; :0 ; vi E e BI, Vj [1, M]
7:
0
(/--1) -- Choose best-perforiing model for ai (((11) from e(e-2) Vi E [1.
8:
+ Approximate solutions to max f(x! 1) (00 vi E
9:
end for
10:
X'
8ig 1 [ Vi [1, B), Vj E [1
Outer Minimization
11:
R + Evaluate X' on O ((-1)
12:
P Softmax (-- of (X,
13:
( < Train 0/- E o on TPp) instances, Vj E M1]
14:
R' Evaluate X' on (e))
15:
0 Update neural router g with the gradient V of ((e-1) L using Eq. (6)
16:
end for
instance. The best solution among them is returned to reflect the final collaborative performance. We present the pseudocode of CNF Algorithm I, and elaborate each part the following subsections.
4.1 Inner Maximization
The inner maximization aims to generate adversarial instances for the training in the outer mini- mization, which should be 1) effective in attacking the framework; 2) diverse to benefit the policy exploration for VRPs. Typically, an iterative attack method generates local adversarial instances for each model only based on its own parameter (e.g., the same 0 in Eq. (3) is repetitively used throughout the generation). Such local attack (line 6) only focuses on degrading each individual model, failing to consider the ensemble effect of multiple models. Due the existence multiple models in CNF, we are motivated to further develop general form of local attack - global attack (line 7-8), where each adversarial instance can be generated using different model parameters within T generation steps. Concretely, given each clean instance x, we generate the global adversarial instance by attacking the corresponding rest-performing model in each iteration of the inner maximization. In doing so, compared with the sole local attack, the generated adversarial instances are more diverse to successfully attack the models (see Appendix for further discussions). Without loss of generality, we take the attacker from [87] as example, which directly maximizes the variant of the reinforcement loss as follows:
E(:; 0) c(T)
log pa (T|x),
b(x))
where b(-) is the baseline function (as shown in Eq. (1)). On top of it, we generate the global adversarial instance F such that:
((++)) = (x a V (0;
0% = arg minges (T(=(();))
(5)
where z(1) is the global adversarial instance and f/.) is the best best-performing model (w.r.t. x(!) at step t. If a(() is out of the range, would be projected back to the valid domain A by II, such as the min-max normalization for continuous variables (e.g., node coordinates) or the rounding operation for discrete variables (e.g.. node demands). We discard the sign operator in Eq. (3) to relax the imperceptible constraint. More details are presented in Appendix B.I.
In summary, the local attack is a special case of the global attack, where the same model chosen as 0g in each iteration. While the local attack aims to degrade a single model 0, the global attack can viewed as explicitly attacking the collaborative performance of all models O which takes into consideration the ensemble effect by attacking 0s. In CNF, we involve adversarial instances that

---

are generated by both the local and global attacks to pursue better adversarial robustness, while also including clean instances to preserve standard generalization.
4.2 Outer Minimization
After the adversarial instances are generated by the inner maximization, collect set of instances X' with X N, which includes clean instances x. local adversarial instances ī and global adversarial instances J. train M models. Here key problem is that how are the instances distributed models for their training, so as to achieve satisfactory load balancing (Iraining efficiency) and collaborative performance ( To solve this, we design an attention- based neural router, and jointly train it with all models θ to maximize the improvement of collaborative performance.
Concretely, we first evaluate each model on X' obtain cost matrix R E IR NMM, The attention- based neural router 8, takes as inputs the instances and R, and outputs a logit matrix (X. R) P E R M where f is the decision function. Then, apply Smax function along the first dimension of P to obtain the probability matrix P, where the entity Pij represents the probability of the deh instance being selected for the outer minimization of the jth model. For each model, the neural router distributes the instances with TopAC-largest predicted probabilities training (line 10-13). In doing so, all models have the same amount (AC) of training instances, which explicitly ensures the load balancing (see Appendix A). We also discuss other strategies of instance distributing, such as sampling, instance-based choice, etc. More details can be found in Section 5.2.
batch for its
After all models O are trained with the distributed instances, we further evaluate each model on X. obtaining a new cost matrix R' E R M. To pursue desirable collaborative performance, is expected that the neural router 8, can reasonably exploit the overall capacity of models. Since the action space of f, is huge and the models are changing throughout the training, we resort to the reinforcement learning (based on trial-and-error) 14-15). Specifically, we set (min R - min R') as the reward signal, and update 6, by gradient ascent to maximize the expected return with the following approximation:
optimize parameters of the neural router 0, (line
Vo, ((,,(()))) = E Me [min R - min R'), Vo, log Pigl.
(6)
where the min operator is applied along the last dimension of R and R', since we would like to maximize the improvement of collaborative performance after training with the selected instances. Intuitively, if an entity in (min R min R') is positive, it means that, after training with the selected instances, the collaborative performance of all models on the corresponding instance is increased. Thus, the corresponding action taken by the neural router should be reinforced, and vice versa. For example, in Fig. 2, if the reward entity for the first instance 21 is positive, the probability of this action (i.e., the red one in the first row of P) will be reinforced after optimization. Note that the unselected (e.g., black ones) will be masked out in Eq. (6). In doing so, the neural router learns effectively distribute instances and reasonably exploit the overall model capacity, such that the collaborative performance of all models can be enhanced after optimization. Further details on the neural router structure and the in-depth analysis of the learned routing policy are presented in Appendix C.
5 Experiments
In this section, we empirically verify the effectiveness and versatility of CNF against attacks spe- cialized for VRPs, and conduct further analyses to provide the underlying insights. Specifically, our experiments focus on two attack methods [87, 42), since the accuracy-robustnes trade-off exists when conducting vanilla AT to defend against them. We conduct the main experiments on POMO [38] with the attacker in [87]. and further demonstrate the versatility of the proposed framework MatNet [39] with the attacker in [42]. More details on the experimental setups, data generation and additional large-scale instances) are presented in Appendix D. All experi- ments are conducted on a machine with NVIDIA V100S- -PIOE cards and Intel Xeon Gold 6226 CPU at 2.70GHz. The source code is available https: /tt///gittt gitbttt..u..... com/ wwwm/oommaa...ee htte//ooyalll/eeeeaeee /ooutiig///onng---eeeoe CNF.
empirical results (e.g., evaluation
Baselines. 1) Traditional methods: we solve TSP instances by Concorde and LKH3 [25], and CVRP instances by hybrid genetic search (HGS) [70] and LKH3. 2) Neural methods: we compare our method with the pretrained base model POMO (~1MM parameters), and its variants training with various defensive methods, such as the vanilla adversarial training (POMO (DM, the defensive method
7

---

Table 1: Performance evaluation over 1K test instances. The bracket includes the number of models.
Uniform (100)
Fixed Adv.
(100)
Adv. (100)
Uniform (200)
Fixed Adv.
(200)
Adv. (200)
Gup
Gsa
Cap
Time
Crip
Gap
Time
Concorde LKH3
0.000%
0.3m
0.000%
0.3m
0.0001%
0.6m
0.000%
0.6m
0.000%
1.3m
0.002%
2.1m
0,000%
3.9m
0.005%
5.8m
POMO (1)
0.144%
0.1m
35 8035%
0.1m
35.8035%
0.1m
0.736%
0.5m
63.477%
0.5m
63.477%
0, 0.5m
POMO AT ())
0.365%
0.1m
0.390%
0.1m
0.330%
0.1m
2.151%
0.5m
1.248%
0.5m
1.154%
0.5m
ROVD AT (3)
0.255%
0 3m
0.2055%
3.3m
0.2455
01.mm
1.8844%
1.5m
1,0905
1.5m
1.011%
1.5m
0.3m
0.344%
0.3m
0.3166
1.5m
1.5m
POMO DivTrain (3)
0.255%
0.3m
0.297%
0.3m
0.254%
0.5m
1.875%
1.5m
1.093%
1.5m
1.026%
1.5m
ONE Gready (3)
0.187%
0.3m
0.314%
0.3m
0. 1.00%
0.3m
0.868%
1.5m
1.10%%
1.5m
1.066%
1.5m
CNF
0.118%
0.3m
0.236%
0.3m
0.217%
0.3m
0.614%
1.5m
0.954%
1.5m
0.952%
1.5m
HGS I.KA
0.000%
6. 6.6m
0.000%
14.6m
0.000%
0.4h
0.000%
1.2h
0.538%
18.1m
0.344
23.0m
1,116%
0.5h
0.7615
0.6h
POMO (I)
1.209%
0.1m
3.983%
0. 0.1m
3.983%
0.1m
2.122%
0.6m
16.173%
0.8m
16. 173%
0.8mn
POMD AT (1)
1.45%
0. 6.1m
0.882%%
0. m.1m
0.938%
0.1m
3.2491%
0.6m
1845%
0.6m
1.455%
0.6m
POMO AT (3)
1.2566
0 1.3m
0.767%
0.3m
0.8099
0.3m
2.919%%
1.8m
1.2536
1.8m
1.296%
1.8m
POMO DivTrain (3)
1J888%
0.3m
0.829%
0.8485
1.9714%
1.8m
1.367%
1.8m
1.254%
0.3m
0.754%
0.3m
0.809%
2.9466
1.8m
1.220%
1.8m
1.302%
1.8m
ONE Gready (3)
1.112%
0.3m
0.785%
0.3m
0.821%
0.3m
1.969%
1.8m
1.316%
1.383%
1.8m
CNF(3)
1.073%
0.3m
0.7.0%
0.3m
0.769 %
2.0315%
1.8m
1.193%
1.198%
1.8m
For traditional methods, Adh. not shown since the test adversaiial dataset differrett for each neural method.
proposed by the attacker [87] (POMO (HA), and the diversity training [32] from the literature of Specifically, POMO adversarially trains the models by first generating local adversarial instances in the inner maximization, and then minimizing their empirical risks the outer minimization. POMO HAC further improves the outer minimization instance-reweighted loss function on a mixed dataset, including
ensemble-based adversarial ML CYOMODivTranne
by optimizing a hardness- both clean and local adversarial instances. POMO DivTrain improves the ensemble diversity by minimizing the cosine similarity between the gradients of models w.r.t. the input. Furthermore, we also compare our method with CNF_Greedt by replacing the neural router with a heuristic greedy selection method, and another advanced ensemble-based AT method TRS [81] (see Appendix D.6). More implementation details of baselines are provided in Appendix D.
Training Setups. CNF starts with a pretrained model, and then adversarially trains its M copies in a collaborative way. We consider two scales of training instances n E {100, 2003. For the pretraining stage, the model is trained on clean instances following the uniform distribution. We use the open-source pretrained POMO for n 100, and retrain the model for n 200. Following the original training setups from [38], Adam optimizer is used with the learning rate of 1e - 4, the weight decay of 1e - 6 and the batch size of B = 64. To achieve full convergence, we pretrain the model on 300M and 100M clean instances for TSP200 and CVRP200, respectively. After obtaining the pretrained model, we use to initialize M models, and further adversarially train them on 5M and 2.5M instances for n = 100 and n 200, respectively. To save the GPU memory, we reduce the batch size to = 32 for n = 200. The optimizer setting is the same as the one employed in the pretraining stage, except that the learning rate is decayed by 10 for the last 40% training instances. For the mixed data collection, we collect clean instances, M local adversarial instances and B global adversarial instances in each training step.
Inference Setups. For neural methods, we use the greedy rollout with x8 instance augmentations following [38]. We report the average gap over the test dataset containing 1K instances. Concretely, the gap is computed w.r.t. the traditional VRP solvers (i.e., Concorde for TSP, and HGS for CVRP). If multiple models exist, we report the collaborative performance, where the best gap among all models is recorded for each instance. The reported time is the total time to solve the entire dataset. We consider three evaluation metrics: 1) Uniform (standard generalization): the performance on clean instances whose distributions are the same as the pretraining ones; 2) Fixed Adv. (udversarial robustness): the performance on adversarial instances generated by attacking the pretrained model. It mimics the black-bor box setting, where the attacker generates adversarial instances using a surrogate model due to the inaccessibility to the current model and the transferability of adversarial instances; 3) Adv. (adversarial robustness): the performance on adversarial instances generated by attacking the current model. For neural method with multiple (M) models, it generates MK adversarial instances, from which we randomly sample 1K instances to construct the test dataset. It is the conventional white-box metric used to evaluate adversarial robustness in the literature of AT.
5.1 Performance Evaluation
The results are shown in Table 1. We have conducted t-test with the threshold of 5% to verify the statistical significance. For all neural methods, we report the inference time single GPU, More-
8

---

0.09
Ciaan
0.00
625
Ad
AW
gos
gaae
8 ai5
8 6.5
616
0.0
6.0
600
Velned
Nothod
Hathes
(a) Ablation study on Components
(b) Ablation study on Hyperperamcters
(c) Ablation study on Routing Stratogics
Figure 3: Ablation studies on TSP100. The metrics of Uniform and Fixed Adv. are reported.
over, for neural methods with multiple (M) models (e.g., CNF (3)), we develop implementation of parallel evaluation on multiple GPUs, which can further reduce their inference time by almost M times. From the results, we observe that traditional VRP methods are relatively more robust than neural methods against crafted perturbations, demonstrating the importance and necessity of improving adversarial robustness for neural methods; 2) the evaluation metrics of Fixed Adv. and Adv. are almost consistent in the context of VRPs; 3) our method consistently outperforms baselines, and achieves high standard generalization and adversarial robustness concurrently. For CNF, we show the performance of each model on TSPI00 in Fig. 5. Although not all models excel well on both clean and adversarial instances, the collaborative performance quite good, demonstrating diverse expertise of models and the capability of CNF in reasonably exploiting the overall model capacity.
5.2 Ablation Study
We conduct extensive ablation studies on TSP100 to demonstrate the effectiveness and sensitivity of our method. Note that the setups are slightly different from the training ones (c.g., half training instances). The detailed results and setups are presented in Fig. and Appendix D.I, respectively.
Ablation on Components. We investigate the role each component in CNF by removing them separately. As demonstrated in Fig. 3(a), despite both components contribute the collaborative performance, the neural router exhibits a bigger effect due to its favorable potentials to elegantly exploit training instances and model capacity, especially in the presence of multiple models.
Ablation on Hyperparameters. We investigate the effect of the number of trained models, which key hyperparameter of our method, on the collaborative performance. The results are shown in Fig. 3(b), where we observe that increasing the number of models can further improve the collaborative performance. However, use M = 3 in the main experiments due to the trade-off between empirical performance and computational complexity. We refer to Appendix D.4 for more results.
Ablation on Routing Strategies. We further discuss different routing strategies, including neural and heuristic ones. Specifically, given the logit matrix P predicted by the neural router, there are various ways to distribute instances: 1) Model choice with TopK. (M- :) each model chooses potential instances with ToplC-largest logits, which the default strategy (K B) in CNF; 2) Model choice with sampling (M-Sample): each model chooses potential instances by sampling from the probability distribution (i.e., scaled logits); 3-4) Instance choice with TopK/sampling (1-TopK//-SSue /Saappll--/ee in contrast to the model choice, each instance chooses potential model(s) either by Topı or sampling. The probability matrix P is obtained by taking Softmar along the first and last dimension of P for model choice and instance choice, respectively. Unlike the model choice, instance choice cannot guarantee load balancing. For example, the majority of instances may choose dominant model (if exists), leaving the remaining models underfitting and therefore weakening the ensemble effect and collaborative performance; 5) Random: instances randomly distributed to each model; 6) Self-training: each model trained on adversarial instances generated by itself without instance distributing. The results in Fig. 3(c) show that M- performs the best.
5.3 Out-of-Distribution Generalization
In contrast to other domains (e.g., vision), the set of valid problems not just a low-dimensional manifold in high-dimensional space, and hence the manifold hypothesis [62] does not apply to VRPs (or COPs). Therefore, is critical for neural methods to perform well on adversarial instances when striving for broader -isto--disttibbrionn (OOD) generalization in VRPs. In this section,

---

Table 2: Generalization evaluation synthetic TSP datasets. Models are only trained on 100.
Crocs Distribution
Cruur-Siz
Cross Size & Distribution
Rotation
(100)
Explosion
(100) Time
Uniform
(50)
Uniform
(200)
Rotation (200)
Explosioo (200)
Gap
Time
Gap
Gap
Time
Gap
Time
Gap
Time
Gap
Time
Concorde LKH3
0.000%%
0.3m
0.000%
0.3m
0.000%
0.2m
0.000%
0.6m
0.000%
0.6m
0.000%
0.6m
0.000%
1.2m
0.000%
1.2m
0.000%
0.4m
0.000%
0.000%
3.3m
0.000%
3.5m
POMO (1)
0.471%
0.1m
0.238
0.1m
0.064%
0.1m
1.688%
0.5m
2.936%
0.5m
2.587%
0.5m
POMO AT ())
0.640%
0.1m
0.364%
0.1m
0.151%
0.1m
2.667%
0.5m
3.462%
0.5m
2. 2.989%
0.5m
POMO (3)
0.508%:
0.3m
0.263%
0.3m
0,085%
0.1m
2.362%
1.5m
3.176%
1.5m
2.688%
1.5m
(3)
0.2044
0.107%
0.038%
0.1m
1.414%
1.718%
POMO DivTTTann Train (3)
0.502'%
0.3m
0.255%
0.3m
0.078%
0.1m
2.356%
1.5m
3.176%
1.5m
2.707%
1.5m
CNF (3)
0.193%
0.3m
0.084%
0.3m
0,036 %
0.1m
1.383
1.5m
2.055%
1.5m
1.672%
1.5m
further evaluate the OOD generalization performance on unseen instances from both synthetic and benchmark datasets. The empirical results demonstrate that raising robustness against attacks through CNF can favorably promotes various forms of generalization, indicating the potential existence of neural VRP solvers with high generalization and robustness concurrently. The data generation and comprehensive results can be found in Appendix D.
Synthetic Datasets. We consider three generalization settings, i.e., cross-distribution, cross-size and cross-size & distribution. The results are shown in Table 2, from which we observe that simply conducting the vanilla AT somewhat hurts the OOD generalization, while CNF can significantly improve it. Since adversarial robustness is known as a kind of local generalization property [22, 48], the improvements in OOD generalization can be viewed as byproduct of defending against adversarial attacks and balancing the accuracy-robustnes trade-off.
Benchmark Datasets. We further evaluate all neural methods on the real-world benchmark datasets, such as TSPLIB [58] and CVRPLIB [67]. We choose representative instances within the range of [100, 1002]. The results, presented in Tables 9 and 10, demonstrate that our method performs well across most instances. Note that all neural methods are only trained on 7 = 100.
5.4 Versatility Study
To demonstrate the versatility of CNE, we extend its application to MatNet [39] to defend against another attacker in [42]. Specifically, it constructs the adversarial instance by lowering the cost of a partial clean asymmetric TSP (ATSP) instance. When adhering to the vanilla AT, the undesirable trade-off also observed in the empirical results [42]. In contrast, our method enables models to achieve both high standard generalization and adversarial robustness. The detailed attack method, training setups, and empirical results are presented in Appendix B.3, D.I and D.3, respectively.
6 Conclusion
This paper studies the crucial yet underexplored adversarial defense of neural VRP methods, filling the gap in the current literature on this topic. We propose an ensemble-based collaborative neural framework to concurrently enhance performance on clean and adversarial instances. Extensive experiments demonstrate the effectiveness and versatility of our method, highlighting its potential to defend against attacks while promoting various forms of generalization of neural VRP methods. Additionally, our work can be viewed as ad advancing the generalization of neural methods through the lens of adversarial robustness, shedding light on the possibility of building more robust and generalizable neural VRP methods in practice.
The limitation of this work the increased computational complexity due to the need synergistically train multiple models. Fortunately, based on experimental results, CNF with just three models has already achieved commendable performance. It even surpasses vanilla AT trained with nine models, demonstrating better trade-off between empirical performance and computational complexity.
Interesting future research directions may include: 1) designing efficient and effective attack or defense methods for other COPs; 2) pursuing better robustness with fewer computation, such as through conditional computation and parameter sharing; 3) theoretically analyzing the robustness of neural VRP methods, such as certified robustness: 4) investigating the potential of large language models to robustly approximate optimal solutions to COP instances.
10

---

Acknowledgments and Disclosure of Funding
This research supported by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No: AISG3-RP-2022-031) It is also partially supported by Alibaba Group through Alibaba-NTU Singapore Joint Research Institute (JRI), Nanyang Technological University, Singapore. We would like to thank the anonymous reviewers and (S)ACs of NeurlPS 2024 for their constructive comments and dedicated service the community.
References
[1] Irwan Bello, Hieu Pham. Quoe V. Le, Mohammad Norouzi, Samy Bengio. Neural combinatorial optimization with reinforeement learning. ICLR Workshop Track, 2017.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2):00--21,, 2021.
[3] Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma. Fanchen Bu, Jiarui Wang. Haoran Ye, Minsu Kim, Sanghyeok Choi, Nayeli Gast Zepeda, André Hottung, Jianan Zhou, Jieyi Bi, Yu Hu, Fei Liu, Hyeonah Kim, Jíwoo Son, Haeyeon Kim, Davide Angioni, Wouter Kool, Zhiguang Cao, Jie Zhang, Kijung Shin, Cathy Wu, Sungsoo Ahn, Guojie Song. Changhyun Kwon, Lin Xie, and Jinkyoo Park. RI4co: an extensive reinforcement learning for combinatorial optimization benchmark. arXiv preprint arXiv:2306. 17 17100, 2023.
[4] Federico Berto, Chuanbo Hua, Nayeli Gast Zepeda, André Hottung, Niels Wouda, Lcon Lan, Kevin Tierney, and Jinkyoo Park. Routefinder: Towards foundation models for vehicle routing problems. arXiv preprint arXiv:2406. 15007, 2024.
[5] Jieyi Bi. Yining Ma. Jiahai Wang. Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. In NeurlPS, volume 35, pages 31226-31238 2022.
[6] Jakob Bossek, Pascal Kerschke, Aneta Neumann, Markus Wagner, Frank Neumann, and Heike Trautmann. Evolving diverse tsp instances by means of novel and creative mutation operators. In Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithmss, pages 58-71. 2019.
[7] Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitting may be mitigated by properly learned smoothening. In ICLR, 2021.
[8] Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. In NewrIPS, volume 32, 2019.
[9] M Cutler. Efficient special case algorithms for the n-line planar traveling salesman problem. Nenworks, 10(3):183-195, 1980.
[10] Paulo R O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning. pages 465-480. PMLR, 2020.
[11] Hanjun Dai, Elias B. Khalil, Zuang Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In NeurlPS, volume 30, 2017.
[12] Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. GOAL: A generalist combinatorial optimization agent learner. arXiv preprint arXiv:2406. 15779, 2024.
[13] Darko Drakulic, Sofia Michel, Florian Mai, Amaud Sors, and Jean-Mare Andreoli. BQ-NCO: Bisimulation quotienting for efficient neural combinatorial optimization. In NeurlPS, volume 36, 2023.
[14] Javid Ebrahimi, Anyi Rao, Daniel Lowd, and Dejing Dou. Hotflip: White-hox adversarial examples for text classification. In ACI. pages 31-36, 2018.
[15] Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. WSDM, pages 169-177 177, 2020.
[16] Han Fang, Zhihao Song, Paul Weng, and Yutong Ban. INVIT: A generalizable routing problem solver with invariant nested view transformer. In JCML, 2024.
[17] Zhang Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In AAAI, volume 35, pages 7474-7483 2021.

---

[18] Chengrui Gao. Haopu Shang. Ke Xue. Dong Li, and Chao Qian. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In /JCAI, 2024.
[19] Simon Geisler, Tobias Schmidt, Hakan Sirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Gün- nemann. Robustness of graph neural networks at scale. In NeurIPS, volume 34, pages 7637-7649, 2021.
[20] Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. ICLR, 2022.
[21] Yong Liang Goh, Zhiguang Cao, Yining Ma, Yanfei Dong. Mohammed Haroon Dupty, and Wee Sun Lee. Hierarchical neural constructive solver for world tsp scenarios. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 884-895, 2024.
[22] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
[23] Lukas Gosch, Daniel Sturm. Simon Geisler, and Stephan Günnemann. Revisiting robustness graph machine learning. In ICLR, 2023.
[24] Nathan Grinsztajn, Daniel Furelos- Blanco, Shikha Surana, Clément Bonnet, and Tom Barrett, Winner takes all: Training performant rl populations for combinatorial optimization. In NeurlPS, volume 36, pages
2023.
[25] Keld Helsgaun. An extension of the iin-kerighann-helsaan tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, pages 24-50, 2017.
[26] André Hottung, Ycong- Dac Kwon, and Kevin Tierney. Efficient active search for combinatorial optimization problems. In ICLR, 2022.
[27] André Hottung, Mridul Mahajan, and Kevin Tiemey. PolyNet: Learning diverse solution strategies for neural combinatorial optimization. arXiv preprint arXiv:2402. 14048, 2024.
[28] Qingehun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In ICLR, 2023.
[29] Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, and Jiliang Tang. Adversarial attacks and defenses on graphs: A review and empirical study, arXiv preprint 30060,,00,, 2020.
[30] Chaitanya K Joshi, Quentin Cappart, quires rethinking generalization. In International Conference on Principles and Practice of Constraint Programming, 1021.
Rousseau, and Thomas Laurent. Learning tsp re-
[31] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 0/227, 2019.
[32] Sanjay Kariyappa and Moinuddin K Qureshi. Improving adversarial robustness of ensembles with diversity training. arXiv preprint arXiv: /tt:::9900.0999 2019.
[33] Minsu Kim, Sanghycok Choi, Jiwoo Son, Hyconah Kim, Jinkyoo Park, and Yoshua Bengio. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arXiv:2403.0704 2024.
[34] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging symmetricity for neural combinato- rial optimization. In NeurIPS, 2022.
[35] Grigorios D Konstantakopoulos, Sotiris P Gayialis, and Evripidis P Kechagias. Vehicle routing problem and related algorithms for logistics distribution: literature review and classification. Operational research, pages 1-30, 2022.
[36] Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. In International conference on integration of constraint programming. artificial intelligence, and operations research, pages -93-213.662 Springer, 2022.
[37] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In ICLR, 2018.
[38] Yeong-Dac -De Kwon, Jinho Choo, Byoungjip Kim, I1joo Yoon, Youngjune Gwon, and Scungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In NewrIPS, volume 33, pages 21188 2119,2 2020.
12

---

[39] Yeong- Dae Kwon, Jinho Choo, IIjoo Yoon, Minah Park, Duwon Park. and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In NeurlPS, volume 34, pages 5138-5149, 2021.
[40] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. In Neur!PS, volume 34, pages 26198-26211, 2021.
[41] Fei Liu, Xi Lin, Qingfu Zhang, Xialiang Tong, and Mingxuan Yuan. Multi-task learning for routing problem with cross-problem zero-shot generalization. In 202.
2024.
[42] Han Lu, Zenan Li, Runzhong Wang, Qibing Ren, Xijun Li, Mingxuan Yuan, Jia Zeng, Xiaokang Yang. and Junchi Yan. ROCO: A general framework for evaluating robustness of combinatorial optimization solvers on graphs. In ICLR, 2023.
[43] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-basee based iterative method for solving vehicle routing problems. In ICI.R, 2020.
[44] Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In NeurlPS, volume 36, pages 8845-8864, 2023.
[45] Luo, Xi Lin, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Self- self-improved learning for scalable neural combinatorial optimization. arXiv preprint arXiv:2403. 19561, 2024.
[46] Yining Ma. Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In NewrIPS, volume 36, 2023.
[47] Yining Ma, Jingwen Li. Zhiguang Cao, Wen Song. Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In NeurlPS, volume 34, pages 10006-11107, 2021.
[48] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
[49] Yimeng Min. Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. In NeurlPS, volume 36, 2023.
[50] John Moriis, Eli Lifland, Jin Yong Yoo, Jake Grigsby, Di Jin, and Yanjun Qi. Textattack: A framework for adversarial attacks, data augmentation, and adversarial training in nlp. In EMNLP, pages 119-126, 2020.
[51] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáe. Reinforcement learning for solving the vehicle routing problem. In NeurIPS, volume 31, 2018.
[52] Silvia Padrón, Daniel Guimarans, Juan José Ramos, and Salma Fitouii-Trabeks A bi-objective approach for scheduling ground-handling vehicles in airports. Computers Operations Research, 71:34-53, 2016.
[53] Tianyu Pang, Kun Xu. Chao Du Ning Chen, and Jun Zhu, Improving adversarial robustness via promoting ensemble diversity. In ICML, pages 4970-4979, PMLR, 2019.
[54] Victor Pillac, Michel Gendreau, Christelle Guéret, and Andrés L Medaglia. A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1):1-11, 2013.
[55] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Cupta. Robust adversarial reinforcement learning. In ICMI., pages 2817-2826. PMIRR, 2017.
[56] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In NeurlPS, volume 35, pages 25531-25544 2022.
[57] Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang. Understanding and mitigating the tradeoff between robustness and accuracy. In ICMI, pages 7909-7919. PMLR, 2020.
[58] Gerhard Reinelt. Tsplib traveling salesman problem library. ORSA journal on computing, 3(4):376-38, 1991.
[59] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learning a sat solver from single-bit supervision. In ICLR, 2019.
[60] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In ICLR, 2018
13

---

[61] Igor G Smit, Jianan Zhou, Robbert Reijnen, Yaoxin Wu, Jian Chen, Cong Zhang, Zaharah Bukhsh, Wim Nuijten, and Yinggian Zhang. Graph neural networks for job shop scheduling problems: A survey. arXiv preprint arXiv:2406. 14096, 2024.
[62] David Stutz. Matthias Hein, and Bernt Schiele. Disentangling adversarial robustness and generalization. In CVPR, pages 1976-6987. 2019.
[63] Youchen Sun, Zhu Sun, Yingpeng Du, Jie Zhang, and Yew Soon Ong. Self-supervised denoising through independent cascade graph augmentation for robust social recommendation. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2806 2817, 2024.
[64] Zhiqing Sun and Yiming Yang. DIFUSCO: Graph- based diffusion solvers for combinatorial optimization. In NeurlPS, volume 36, pages 1706-3731. 2023.
[65] Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. Ensemble adversarial training: Attacks and defenses. In ICLR, 2018.
[66] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry, Robust- ness may be at odds with accuracy. In ICLR, 2019.
[67] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257 858. 2017.
[68] Nithin Varma and Yuichi Yoshida. Average sensitivity of graph algorithms. In Proceedings of the 2021 ACM-SIAM Symposium Discrete Algorithms (SODA). pages 684-703. STAM, 2021.
[69] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkorcit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NewrIPS, volume 30, 2017.
[70] Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neighborhood. Computers & Operations Research, 140: 105643, 2022.
[71] Oriol Vinyals, Meire Fortunato, and Navdeop Jaitly. Pointer networks. In NeurlPS, volume 28, 2015.
[72] Eric Wallace, Shi Feng. Nikhil Kandpal, Matt Gardner, and Sameer Singh. Universal adversarial triggers for attacking and analyzing nlp. In EMNLP-IJCNLPP pages 2153-2162, 2019.
[73] Haotao Wang. Tianlong Chen, Shupeng Gui, TingKuei Hu, Ji Liu, and Zhangyang Wang. Once-for-all adversarial training: In-situ tradeoff between robustness and accuracy for free. NeurlPS, 33:7449- 2020.
[74] Alexander Wei, Nika Haghtalab, and Jacob Steinhardt. Jailbroken: How does LLM safcty training fail? In Thirty-seventh Conference Neural Information Processing Systems, 2023.
[75] Ronald J Williams. Simple statistical gradient- algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-25) 256. 1992.
[76] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE transactions on neural networks and learning systems, 2021.
[77] Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post-hoc search-based neural approaches for solving large-scale traveling salesman problems. In ICML, 2024.
[78] Liang Xin. Wen Song, Zhiguang Cao, and Jie Zhang. NeuroLKH: Combining deep learning model with seeemighann-elsgaaae heuristic for solving the traveling salesman problem. NewrIPS, volume 34, pages 7472-7483 2021.
[79] Huanrui Yang, Jingyang Zhang, Hongliang Dong, Nathan Inkawhich, Andrew Gardner, Andrew Touchet, Wesley Wilkes, Heath Berry, and Hai Li. DVERGE: diversifying vulnerabilities for enhanced robust generation of ensembles. In NeurIPS, volume 33, pages 5505 5515, 2020.
[80] Yao- Yuan Yang, Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaudhuri. A closer look at accuracy vs. robustness. In NewrIPS, volume 33, pages 8588-8601, 2020.
[81] Zhuolin Yang, Linyi Li, Xiaojun Xu, Shiliang Zuo, Qian Chen, Pan Zhou, Benjamin Rubinstein, Ce Zhang. and Bo Li. TRS: Transferability reduced ensemble via promoting gradient diversity and model smoothness. In NewrIPS, volume 34, pages 17642 -7655, 2021.
14

---

[82] Haoran Ye, Jiarui Wang, Zhiguang Cao. Helan Liang, and Yong Li. DeepACO: Neural-enhanced ant systems for combinatorial optimization. In NeurIPS, volume 36, 2023.
[83] Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. GLOPP: Learning global partition and local construction for solving large-scale routing problems in real-time. In AAAI, volume 38, pages 20284-20292, 2024.
[84] Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning dispatch for job shop scheduling via deep reinforcement learning. NeurIPS, volume 33, pages 1621 1022- 2020.
[85] Hongyang Zhang, Yaodong Yu. Jiantao Jiao, Eric Xing. Laurent El Ghaoui, and Michael Jordan. The- oretically principled trade-off between robustness and accuracy. ICML, pages 7472-7482. PMLR. 2019.
[86] Jingfeng Zhang, Jianing Zhu, Gang Niu, Han, Masashi Sugiyama, and Mohan Kankanhalli. Geometry- aware instance-rewenn restihee-reweightedd adversarial training. In ICLR, 2021.
[87] Zeyang Zhang. Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning to solve travelling salesman problem with aarptivs-ddaative curriculum. In AAAI, volume 36, pages 9136-9144, 2022.
[88] Zhi Zheng, Changliang Zhou, Tong Xialiang, Mingxuan Yuan, and Zhenkun Wang. UDC: A unified neural divide-and- congurr framework for large-scale combinatorial optimization problems. arXiv preprint vrXiv:2407.00312 2024.
[89] Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Xu Chi. MVMoE: Multi-task vehicle routing solver with mixture-of-ette expertss... In ICML, 2024.
[90] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards onni-generalizable neural methods for vehicle routing problems. In ICML, pages 27769427787 PMLR, 2023.
[91] Andy Zou, Zifan Wang. Zico Kolter, and Matt Fredrikson. Universal and transferable adversarial attacks aligned language models. arXiv preprint arXiv:2307.15043, 2023.
[92] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann, Adversarial attacks on neural networks for graph data. In KDD, pages 2847-2856, 2018.
15

---

Collaboration! Towards Robust Neural Methods for Routing Problems (Appendix)
A Frequently Asked Questions
Load Balancing, In this paper, load balancing refers to distributing each model with a similar or the same number of training instances from the instance set X, in each outer minimization step. It can avoid the appearance of dominant model or biased performance. The proposed neural router with the TopıC operator explicitly ensures such load balancing since each model is assigned exactly IC instances based on the probability matrix predicted by the neural router.
Why does CNF Work? Instead of simply training multiple models, the effectiveness of the proposed collaboration mechanism in CNF can be attributed to its diverse adversarial data generation and the reasonable exploit of overall model capacity. As shown in the ablation study (Fig. 3())), the diverse adversarial data generation is helpful in further improving the adversarial robustness (see results of CNF vs. W/O Global Attack). Mcanwhile, the neural router has a bigger effect in mitigating the trade-off (see results of CNF vs. W/O Router). Intuitively, by distributing instances to suitable submodels for training, each submodel might be stimulated have its own expertise. Accordingly, the overlap of their vulnerability areas may be decreased, which could promote the collaborative performance of CNF. As shown in Fig. 5, not all models perform well on each kind of instance. The expertise of Og lies primarily in handling clean instances, whereas 0, specializes in dealing with adversarial instances. Such diversity in submodels contributes to the collaborative efficacy of O and the mitigation of the undesirable trade-off between standard generalization and adversarial robustness, thereby significantly outperforming vanilla AT with multiple models.
Why using Best- Best-performing Model for Global Attack? The collaborative performance of our framework depends on the best-performing model 0, w.r.t. each instance, since its solution will be chosen as the final solution during inference. The goal of inner maximization is to construct the adversarial instance that can successfully fool the framework. Intuitively, if we choose to attack other models (rather than 0,), the constructed adversarial instances may not successfully fool the best-performing model 0,, and therefore the final solution to the adversarial instance could still be good, which contradicts the goal of inner maximization. Therefore, to increase the success rate of attacking the framework and generate more diverse adversarial instances, for each instance, we choose the corresponding best-performing model O, the global model in each attack iteration.
Divergence of Same Initial Models. We take POMO [38] as an example. During training, in each step of solution construction, the decoder of the neural solver selects the valid node to be visited by sampling from the probability distribution, rather than using the argmax operation. Even though we initialize all models using the same pretrained model, given the same attack hyperparameters (e.g., attack iterations), the adversarial instances generated by different models are generally not the same at the beginning of the training. Therefore, the same initial models can diverge to different models due to the training on different (adversarial) instances.
Larger Model. In addition to training multiple models, increasing the number of parameters for single model another way of enhancing the overall model capacity. However, technically, 1) larger model needs more GPU memory, which puts more requirements on a single GPU device. It is also more sophisticated enable parallel training on multiple GPUs compared the counterpart with multiple models; 2) currently, our method conducts AT upon the pretrained model, but there does not exist a larger pretrained model (e.g., larger POMO) in the literature. Despite the technical issues, we try to pretrain larger POMO (i.e., 18 encoder layers with 3.64M parameters in total) on the uniform distributed data, and further conduct the vanilla AT. The performance is around 0.335% and 0.406% on clean and adversarial instances, respectively, which is inferior to the counterpart with multiple models (i.e., POMO_A _A (3)). The superiority of multiple models may be attributed to its ensemble effect and the capacity in learning multiple diverse policies.
16

---

Advanced AT Methods in Other Domains. In this paper, we mainly focus on the vanilla AT [48]. More advanced AT techniques, such as TRADES [85], AT in RL [55], and ansemble-based AT [65, 32, 53, 79, 81] can be further considered. However, some of them may not be applicable to the VRP domain due to their needs for ground-truth labels or the dependence on the imperceptible perturbation model. 1) TRADES is empirically effective for trading adversarial robustness off against standard generalization on the image classification task. Its loss function is formulated as C (x)( 2) + (f f(ā),, where CE is cross-entropy. KL is KL-divergence; z is clean instance; 7 is an adversarial instance; f(xx) is the logit predicted by the model; y is the ground-truth label; 33 is a hyperparameter. By explicitly making the outputs of the network (logits) similar for and ă. it can mitigate the accuracy accuracy-robustnee robustness trade-off. However, the above statement is contingent upon the imperceptible perturbation model, where the ground truth labels of x and ö are kept the same. As we discussed in Section 3.2, in the discrete VRPs, the perturbation model does not have such imperceptible constraint, and the optimal solutions to x and &. are not the same in the general case. Therefore, it does not make sense to make the outputs of the model similar for x and ø. 2) Another interesting direction is AT in RL, where the focus is the attack side rather than the defense side (e.g., most of the design in [55] focuses on the adversarial agent). Specifically, it jointly trains impede the first agent, to generate
another agent (i.e., the attacker adversary). whose objective hard trajectories in a two-player zero-sum way. Its goal is to learn a policy that is robust to modeling errors in simulation or mismatch between training and test scenarios. In contrast, our work focuses on the defense side and aims to mitigate the trade-off between standard generalization and adversarial robustness. Moreover, this method is specific to RL while our framework has the potential to work with the supervised learning setting. Overall, it is non-trivial to directly apply this method to address our research problem (e.g.. the trade-off). But it is an interesting future research direction to design attack methods specific to RI. (e.g., by training another adversarial agent or attacking each step of MDP). 3) Similar to the proposed CNF, ensemble-based AT also leverages multiple models, but with different motivation (e.g.. reducing the adversarial transferability between models to defend against black-box adversarial attacks [79). Concretely, ADP [53] needs the ground-truu labels to calculate the ensemble diversity. DVERGE [79] depends on the misalignment of the distilled feature between the visual similarity and the classification result, and hence on the imperceptible perturbation model. Therefore, it is non-trivial to directly adapt them to the discrete VRP domain. DivTrain [32] proposes to decrease the gradient similarity loss to reduce the overall adversarial transferability between models, and TRS [81] further uses model smoothness loss to improve the ensemble robustness. Technically, their methods are computational expensive due to the needs to keep the computational graph before taking optimization step. We show their empirical results in Table 7. Compared with others, their empirical results are not superior in VRPs. For example, for TSP100, POMO TRS (3), which is adapted from [81], achieves 0.098% and 0.528% on the metrics of Uniform and Fixed Adv., respectively, failing to mitigate the undesirable trade-off. We leave the discussion on defensive methods from other domains (e.g.. language and graph) to Section 2.
Attack Budget. As discussed in Section 3.2, we do not exert the imperceptible constraint on the perturbation model in VRPs. We further explain it from two perspectives: 1) different from other domains, there is no theoretical guarantee to ensure the invariance of the optimal solution (or ground- truth label), given an imperceptible perturbation. A small change on even one node's 's attribute may induce a totally different optimal solution. Therefore, we do not see the benefit of constraining the very small (i.e., imperceptible) range in VRP tasks. Moreover, even with the absence of the imperceptible constraint on the perturbation model, unlike the graph learning setting, do not observe significant degradation on clean performance. It reveals that we don't need explicit imperceptible perturbation to restrain the changes on (clean) objective values in VRPs. In our experiments, we set the attack budget within reasonable range following the applied attack method (c.g., a E [1. 100] for [87]) Our experimental results show that the proposed CNF is able to achieve a favorable balance, given different attack methods and their attack budgets; 2) in VRPs (or COPs), all generated adversarial instances are valid problem instances regardless of how much they differ from the clean instances [20]. In this sense, the attack budget models the severity of a potential distribution shift between training data and test data. This highlights the differences to other domains (e.g., vision), where unconstrained perturbations may lead to non-realistic or invalid data. Technically, the various attack budgets can help to generate diverse adversarial instances for training. Considering the above aspects, we believe our adversarial setting, including diverse but valid problem instances, may benefit the VRP community in developing more general and robust neural solver.
attack budget
17

---

With that said, this paper can also be viewed as attempt to improve the generalization of neural VRP solvers from the perspective of adversarial robustness.
Attack Scenarios and Practical Significance. Actually, there may not be a person or attacker to deliherately invade the VRP model in practice. However, the developers in logistics enterprise should consider the adversarial robustness of neural solvers as a sanity check before deploying them in the real world. The adversarial attack can be viewed as a way of measuring the worst-case performance of neural solvers within the neighborhood of inputs. Without considering adversarial robustness, the neural solver may perform very poorly (see Fig. I(c)) when the testing instance pattern in the real world is 1) different from the training one, and 2) similar to the adversarial one. For example, considering an enterprise like Amazon, when some new customers need to be added the current configuration or instance, especially when their locations coincidentally lead to the adversarial instance of the current solver (i.e., the node insertion attack presented in Appendix B.2), the model without considering adversarial robustness may output very bad solution, and thus resulting in unpleasant user experience and financial losses. Furthermore, one may argue that this robustness issue can be ameliorated by using other solvers, i.e. NCO alongside traditional heuristics. We would like to note that traditional solvers may be non-robust as well, as discussed a recent work [42]. The availability of traditional solvers cannot be guaranteed for novel problems as well.
The Selection Basis of Attackers. There are three attackers in the current VRP literature [87, 20, 42]. We select the attacker based on its generality. Specifically, 1) [20] is an early work that explicitly investigates the adversarial robustness in COPs. Their perturbation model needs to be sound and efficient, which means, given clean instance and its optimal solution, the optimal solution to the adversarial instance can be directly derived without running solver. However, this direct derivation requires unique properties and theorems of certain problems (e.g.. the intersection theorem [9] for Euclidean-based TSP), and hence is non-trivial to generalize to more complicated VRPs (e.g.. CVRP). Moreover, their perturbation model is limited to attack the supervised neural solver (i.e., ConvTSP [31]), since it needs to construct the adversarial instance by maximizing the loss function so that the model prediction is maximally different from the derived optimal solution. While in VRPs, RL-based methods [37, 38] are more appealing since they can gain comparable performance without the need for optimal solutions. 2) [42] requires that the optimal solution to the adversarial instance is no worse than that to the clean instance in theory, which may limit the search space of adversarial instances. It focuses on the graph-based COPs (e.g., asymmetric TSP) and satisfies the requirement by lowering the cost of edges. Similar to [20]. their method is not easy to design for VRPs with more constraints. Moreover, they resort the black-box adversarial attack method by training reinforcement learning based attacker, which may lead to higher computational complexity and relatively low success rate of attacking. Therefore, for better generality, we choose [87] as the attacker in the main paper, which can be applied to different VRP variants and popular VRP solvers [37, 38). Moreover, we also evaluate the versatility of CNF against [42] as presented in Appendix D.3.
Training Efficiency. As mentioned in Section 6, the limitation of the proposed CNF is the increased computational complexity due to the need to synergistically train multiple models. Concretely, we empirically observe that CNF requires more training time than the vanilla AT variants on TSP100 (e.g., POMO_AY AT (3) 32 hrs vs. CNF (3) 85 hrs). However, simply further training them cannot significantly increase their performance since the training process has nearly converged. For example, given roughly the same training time, POMO_AY achieves 0.246% and 0.278% while CNF achieves 0.1 181 and 0.236% on the metrics of Uniform and Fixed Adv., respectively. On the other hand, our training time is less than that of advanced AT methods (e.g.. POMO TRS (3) [81] needs around 94 hrs). The above comparison indicates that CNF can achieve a better trade-off to deliver superior results within a reasonable computational budget. Moreover, we find that the global attack generation consumes much more training time than the neural router (~~0.05 million parameters). During inference, the computational complexity of CNF only depends on the number of models, since the neural router is only activated during training, and is discarded afterwards. Therefore, all methods with the same number of trained models have the same inference time.
Relationship between OOD Generalization and Adversarial Robustness in VRPs. Generally, the adversarial robustness measures the generalization capability of model over the perturbed instance T in the proximity of the clean instance x. In the context of VRPs (or COPs), adversarial instances are neither anomalous nor statistical defects since they are valid problem instances regardless of how much they differ from the clean instance x [20]. In contrast to other domains (c.g.. vision). 1) the attack budget models the severity of a potential distribution shift between training data and test
18

---

data; 2) the set of valid problems is not just a low-dimensional manifold in high- digensiien space, and hence the manifold hypothesis [62] does not apply to combinatorial optimization. Therefore. it is critical for neural VRP solvers to perform well on adversarial instances when striving for broader OOD generalization. Based on experimental results, we empirically demonstrate that raising robustness against attacks through CNF favorably promotes various forms of generalization of neural VRP solvers (as shown in Section 5.3), indicating the potential existence of neural VRP solvers with high generalization and robustness concurrently.
Robustness of Test-time Adaptation Methods. Test-time adaptation methods [26, 56, 82] are relatively robust. This degree of "robustness" primarily comes from 1) traditional local search heuristics and metaheuristics, which can effectively handle perturbations but bring much post- processing runtime, or 2) the costly fine-tuning that incurs more inference time on each test instance. Our CNF can also be combined with them to pursue better performance. Furthermore, we conduct experiments on DIMES [56] and DeepACO [82]. The results are shown in Tables 3 and 4, where we observe that 1) CNF outperforms them in most cases (e.g., w/o advanced search) with much shorter runtime, and 2) test-time adaptation methods (i.e., the purple columns) improve robustness by adopting much post-search effort and consuming hours runtime. According to the results, we note that 1) directly comparing CNF with these methods with advanced searches (e.g., MCTS, NLS) is somewhat unfair, since the additional post- processsnn search makes the analysis of model robustness difficult. For example, recent work finds that MCTS strong that using an almost all-zero heatmap can achieve good solutions [77], raising doubts about the real robustness of learned models; 2) the post-processing searches are typically time-consuming and coablem-specfffc. making them non- non-trivial to be adapted to other COPs. Finally, we highlight that studies on robustness in COPs are still rare, and most work focused on investigating the robustness of neural solvers themselves, due their advantages in generality on more complex COPs and inference speed. However, attacking test-time adaption methods is potential research direction, which will leave future work.
Table 3:
Robustness study of DIMES [56] on 1000 TSP100 instances. G, S. MCTS, and AS denote greedy, sample, Monte Carlo tree search, and active search, respectively.
DIMES (G)
DIMES (AS+G)
DIMES (S)
DIMES (AS+S)
DIMES (MCTS)
DIMES (AS-MCTS)
Gap
Time
Gap
Time
Gap
Time
Gap
Time
Gap
Time
Gap
Time
Clean Fixed Adv.
14.65%
1.3m
5.21%
13.50%
1.40m
5.11%
2.44h
0.05%
2.50m
0.03%
2,4h
19.29%
1.32m
12.12%
2.45h
18.24%
1.42m
11.87%
2.45h
0.19%
2.50m
0.16%
2.49h
Table Robustness study of DeepACO [82] on 1000 TSPI00 instances. Note that only DeepACO (NLS) uses local search. We use 100 ants and T (0, 50, 100) ACO iterations. The total inference time of each method with T 100 is reported.
ACO
1.7h
DeepACO- - -.7h
DecpACO (NLS) 5.6h
Tw1
Tw10
Tw50
T=100
Tw1
T-10
T=50
Tw100
Tw1
T=10
Tw50
T=100
Clean
98. 65.6%%
46.15%
25.47%
20.31%
13.65% 25.50%
7.21% 14.60%
5,54% 10.75%
5.08%
0.46%
0.08%
0.03%
0.02%
Fixed Adv.
40.87%
19.09%
12.61%
10.92%
9.71%
0.31%
0.08%
0.00%
0.00%
19

---

B Attack Methods
In this section, we first give formal definition of adversarial instance in VRPs, and then present details of existing attack methods for neural VRP solvers, including perturbing input attributes [87], inserting new nodes [20], and lowering the cost of a partial problem instance ensure no-worse theoretical optimum [42]. They can generate instances that are underperformed by the current model.
We define an adversarial instance as the instance that 1) is obtained by the perturbation model within the neighborhood of the clean instance, and 2) is underperformed by the current model. Formally, given a clean VRP instance x {Ie, d. J. where ze Ne is the continuous variable (e.g., node coordinates) within the valid range Nc; E Na is the discrete variable (e.g., node demand) within the valid range Na; perturbation model G around the clean instance z, which the current model may be vulnerable. Technically, the adversarial instance can be constructed by adding crafted perturbations to the corresponding attribute of the clean instance, and then project them back to the valid domain, e.g.. J. =Iw; (Ie + a )r.), where denotes the projection operator (e.g.. min-mas max normalization); ar denotes the attack budget. The crafted perturbations can be obtained by various perturbation models, such as the one in Eq. (7), Ye. = v. (2; 0), where is the model parameters; & is the loss function. We omit the attack step for notation simplicity. An illustration of generated adversarial instances is shown in Fig. 4. Below, we follow the notations from the main paper, and detail each attack method.
the constraint, the adversarial instance
{āc: Td. Ø} is found by the
(a)
(b)
(c)
Figure 4: An illustration of generated adversarial instances (i.e., the grey ones). (a) An adversarial instance generated by [87] on CVRP, where the triangle represents the depot node. A deeper color denotes heavier node demand; (b) An adversarial instance generated by [20] on TSP, where the red nodes represent the newly inserted adversarial nodes; (c) An adversarial instance generated by [42] on asymmetric TSP, where the cost of edge is in half.
B.1 Attribute Perturbation
The attack generator from [87] is applied to attention-based models [37, 38] by perturbing attributes of input instances. As introduced in Section 4, generates adversarial instances by directly maximizing the reinforeement loss variant (so called the hardness measure in [87]). We take the perturbation
the node coordinate an example. Suppose given the clean instance (i.e., .()) = 2) and model parameter 0, the solution the inner maximization can be approximated as follows:
((+1) NT (a((0) Vaco ((()),
where (+)) the (local) adversarial instances and g(*) is the model parameters, at step Here use No to represent the valid domain of node coordinates (i.e., unit square (00 1)) for simplicity. After each iteration, it checks whether (()) = (t) + a- gaen (((();
(ae(0);;)) 0(t) ) is within the valid domain No or not. it is out of Nc. the projection operator (i.e., min- max normalization) is applied as follows:
((() min (())
II: (x)) max (+) min (t) (max N. min
(8)
Note that it originally only focuses TSP, where the node coordinates are perturbed. We further adapt it to CVRP by perturbing both the node coordinates and node demands. The implementation is straightforward, except that we set the valid domain of node demands as Nç {1.... 9). For the perturbations on node demands, the projection operator applies another round operation as follows:
a(() min (t)
IL (2(t))
max (t) min (+) (max Na. min Na)
20

---

B.2 Node Insertion
An efficient and sound perturbation model is proposed by [20], which, given the optimal solution y to the clean instance z sampled from the data distribution D, guarantees to directly derive the optimal solution ÿ to the adversarial instance i without running a solver. The attack is applied to the GCN [31], which is a non-autoregressive construction method for TSP. It learns the probability of each edge occurring in the optimal solution (i.e., heat-map) with supervised learning. Following the AT framework, the objective function can be written as follows:
min E (a. max ((fo Ø), with 2 E G(z, v) A U = h(2,z,y).
(10)
where l is the cross-entropy loss; G is the perturbation model that describes the possible perturbed instances i around the clean instance æ;; and h is used to derive the optimal solution ÿ based on (ž, z, y) without running a solver. In the inner maximization, the adversarial instance 전 is generated by inserting several new nodes into x (below we take inserting one new node as an example), which adheres to below proposition and proof (by contradiction) borrowed from [20]:
Proposition 1. Let Z & V be an additional node to be inserted, w(E) is an edge weight, and P, are any two neighbouring nodes in the original optimal solution y. Then, the new optimal solution ğ (including Z) is obtained from y through inserting Z between P and Q *f,
E A[(P, Q)}
with A f B s.l. wo( A, 2) + w B, Z) (A,, B) S wo(P, 2)
(Q, + 2) - (P,
Proof. Let (R, S) E \ () to be two neighboring nodes of Z on ÿ. Assume P. 2) + w(Q, 2) - w(P. Q) < w wR, 2) + w(, 2) w R, S) and the edges (P, Z) and (Q, Z) are not
contained in ÿ (i.e., Z is inserted between R and S rather than P and Q).
Below inequalities hold by the optimality of y and g:
<(ū) w/ wIt, 2) wSS Z) + w [R, 8) 2 c(v).
(11)
<(y) + wP,, P, Z) + (Q, w(P. P. Q) 2 20())
(12)
Therefore, we have
c(y) + w(P, + (Q, w(P, Q) c(ā) cly) + w (R, Z) + -w,,) (13)
which leads to a contradiction against the assumption (i.e., w( (P, Z) + w(Q, 2) - w(P, Q) < w(R 2) + ws, Z) w(R,S)). The proof is completed.
They use a stricter condition #(A, B) E E ((P.Q) with A * B s.t. ((A,)) + w(B Z) B) S w(P, Z) + w(2 Z) w/ (P, in the proposition, since it is unknown which nodes can be R and S in ÿ. Moreover, for the metric TSP, whose node coordinate system obeys the triangle inequality (e.g., euclidean distance), it is sufficient if the condition of Proposition holds for (A, E 3 \ (((P.Q)) U H) with A + B where H denotes the pairs of nodes both on the Convex Hull H E CE) that are not line segment of the Convex Hull. It is due the fact that the optimal route ÿ must be a simple polygon (i.e., no crossings are allowed) in the metric space. This conclusion was first stated for the euclidean space as "the intersection theorem" by [9] and is direct consequence of the triangle inequality.
Based on the above- mentioned proposition, the optimization of inner maximization involves: 1) obtaining the coordinates of additional node Z by gradient ascending (c.g., maximizing / such that the model prediction is maximally different from the derived optimal solution û): 2) penalizing if Z violates the constraint in Proposition 1. Unfortunately, the constraint is non-convex and hard to find a relaxation. Instead of optimizing the Lagrangian (which requires extra computation for evaluating fo), the vanilla gradient descent is leveraged with the constraint as the objective:
Z - V 2 (w Z) + u (Q, 2) w(P, Q)
(min w/ (A, Z) + w(B, - w)), (14) A.B
where 1) is the step size. After we find Z satisfying the constraint, the adversarial instance ă and the corresponding optimal solution ğ can be constructed directly. Finally, the outer minimization takes (ž. f7) as inputs to train the robust neural solvers. This attack method can be easily adopted by our proposed framework, where is replaced by the best model O, when maximizing the cross-entropy loss (i.e., max; E(fo, (7), 5)) in the inner maximization optimization. However, due to the efficiency and soundness of the perturbation model, it does not suffer from the undesirable trade-off following the vanilla AT [20]. Therefore, we mainly focus other attack methods [87, 42].
21

---

B.3 No-Worse Theoretical Optimum
The attack method specialized for graph- COPs is proposed by [42]. resorts to the black-box adversarial attack method by training a reinforcement learning based attacker, and thus can be used to generate adversarial instances for both differentiable (e.g., learning- based) and non-differentiable (e.g.. heuristic exact) solvers. In this paper, we only consider the learning-basee neural solvers for VRPs. Specifically, it generates the adversarial instance I by modifying the clean instance I (e.g., lowering the cost of partial instance) under the no worse optimum condition, which requires c(ū) S c(y) if we are solving minimization optimization problem. The attack successful (w.r.t the neural solver 0) if the output solution to E is worse than the one to (i.e., c(7|zž; 0) c[T|2; 0) 2 c(v) 2 c(T)). The training of the attacker is hence formulated as follows:
max. c( 0) c(T|2;; 0),
(15)
S.L. T= G(,,Tz c(t) S c(y).
where Gax, T: represents the deployment of the attacker G trained on the given model (or solver) 0 to conduct T modifications on the clean instance It is trained with the objective as in Eq. (15) using the RL algorithm (i.e., Proximal Policy Optimization (PPO)). Specifically, the attack process is modelled as a MDP, where, at step t. the state is the current instance ;(t;; the action is to select an edge whose weight is going to be half; and the reward is the increase of the objective: ((+(1+) ((++))) ()- - (())))(()); 0). This process is iterative until 7 edges are modified. We use ROCO represent this attack method in the remaining of this paper.
ROCO has been applied to attack MatNet [39] on asymmetric TSP (ATSP). As shown in the empirical results of [42], conducting the vanilla AT may suffer from the trade-off between standard generalization and adversarial robustness. To solve the problem, we further apply our method to defend against it. However, it is not straightforward to adapt ROCO to the inner maximization of CNF, since ROCO belongs to the black-box adversarial attack method, which does not directly rely on the parameters (or gradients) of the current model to generate adversarial instances. Concretely, we first train an attacker Gj using RL for each model fj. obtaining M attackers for M models (O = {0,} M-1) in CNF. For the local attack, we simply use Gj to generate local adversarial instances for 0j by Gz(æ, Tz For the global attack, we decompose the generation process (i.e., modifying T edges) of global adversarial instance F as follows:
T (++1)
66 (t) (I()) 11 0% arg minnge
(16)
where z(()) is the global adversarial instance; 8/0) is the best- test-performing model (w.rt. ((1)); and G/
is the attacker corresponding to 0((), at step t E [0, T - 1]. Since the model f, is updated throughout the optimization, to save the computation, we fix the attacker Gj and only update (by retraining) it every E epochs using the latest model. More details and results can be found in Appendix D.3.
C Neural Router
C.1 Model Structure
Without loss of generality, we take TSP as an example, where an instance consists of coordinates of n nodes. The attention-based neural router takes as inputs N instances X E R xxx2 and cost matrix R E R xM, where M is the number of models in CNF. The neural router first embeds the raw inputs into h-dimensional (i.e., 128) features as follows:
F1 Mean (W,X X + b1), FR W2R b2,
(17)
where F, E Nxh and Fn R Nxh are features of instances and cost matrices, respectively; W1, W are weight matrices; by, by are biases. The Mean operator is taken along the second dimension of inputs. Then, a single-head attention layer (i.e., glimpse [1]) is applied:
Q WF( Fr)), K = WK (Emb(M))
(18)
where - is the horizontal concatenation operator, Q R Nxh is the query matrix; K E Mxh is the key matrix; Wo, Wx are the weight matrices; Emb (M) E Mxh is a learnable embedding layer
22

---

gos
go4
goa
30
12
Model
Figure 5: Left panel: Performance of each model 0 E θ in CNF (M = 3), and the overall collaboration performance of O. Right panel: A demonstration (i.e., attention map) of the learned routing policy for 0g- The horizontal axis is the index of the training instance. Concretely, 0-2: clean instances æ; 3-11: local adversarial instances म; 12-14: global adversarial instances ã. The vertical axis the epoch of the checkpoint. A deeper color represents higher probability to be selected.
representing the features of M models. The logit matrix P E NRN is calculated as follows:
QKT
P= C tanh(
(19)
Vh
where the result is clipped by the tanh function with C = 10 following [1]. When the neural router applied to CVRP, we only slightly modify Q by further concatenating with the features of the depot and node demands, while keeping others the same.
C.2 Learned Routing Policy
attempt to briefly interpret the learned routing policy. We first show the performance of each model 0,- E θ in CNF in the left panel of Fig. 5, which is trained on TSPI00 following the training setups presented in Section 5. Although not all models perform well on both clean and adversarial instances, the collaborative performance of θ is quite good, demonstrating the diverse expertise of each model and the capability of CNF in reasonably exploiting the overall model capacity. We further give demonstration (i.e., attention map) of the learned routing policy in the right panel of Fig. 5. We take the first model Og as an example, whose expertise lies in clean instances. For simplicity and readability of the results, the batch size is the neural router is 15. The neural router then distributes B = instances to each model (if using model choice routing strategies). Note that the instances for different epochs are the same, while the types remain the same (c.g., instances with ids 0-2 are clean instances). From the results, we observe that 1) the learned policy tends distribute all types of instances each model in balanced way at the beginning of training, when the model is vulnerable to adversarial instances; 2) clean instances are more likely be selected the end of training, when the model relatively robust to adversarial instances while trying to mitigate the sccuracy-robustness trade-off.
B = 3. and thus the number of input instances X' for
D Experiments
D.1 Extra Setups
Setups for Baselines. We compare method with several strong traditional and neural VRP methods. Following the conventional setups in the community [37, 38, 26), for specialized heuristic solvers such as Concorde, LKH3 and HGS, we run them on 32 CPU cores for solving TSP and CVRP instances in parallel, while running neural methods on one GPU card. Below, we provide the implementation details of baselines. Concorde: We Concorde Version 03.12.19 with the default setting, to solve TSP instances. 2) LKH3 [25]: We use LKH3 Version 3.0.8 to solve TSP and CVRP instances. For each instance, we run LKH3 with 10000 trails and run. HGS [70]: We run HGS with the default hyperparameters to solve CVRP instances. The maximum number of iterations without improvement is set to 20000. 4) For POMO [38], beyond the open-source pretrained model, we further train it using the vanilla AT framework (POMO_AV (T). Specifically, following the training setups presented in Section 5, we use the pretrained model initialize M models, and train them individually using local adversarial instances generated by themselves. 5) POMO HAC [87] further
23

---

improves upon the vanilla AT. It constructs a mixed dataset with both clean instances and local adversarial instances for training afterwards. In the outer minimization, optimizes an instance- reweighted loss function based on the instance hardness. Following their setups, the weight for each instance Z2 is defined as: wi = exp((F((((:)))T))) (xp(F(((2))))T)) where F is the transformation function (i.e., tanh): is the temperature controlling the weight distribution. It starts from 20 and decreases linearly as the epoch increasing. The hardness H. is computed following Eq. (4). 6) POMO POMO_DivTraie DivTrain is adapted from the diversity training [32], which studies the ensemble- based adversarial robustness in the image domain by proposing a novel method to train an ensemble of models with uncorrelated loss functions. Specifically, it improves the ensemble diversity by minimizing the cosine similarity between the gradients of (sub-)model) w.r.t. the input. Its loss function is formulated as: L = é + À log(Z) Ligeees exp( <V.le.v<bb)) [V,6.IVv.t. )), where E is the original loss function; M is the number of models; Vzla is the gradient of the loss function (on the oth model) w.r.t. the input x; X = 0.5 is hyperparameter controlling the importance of gradient aligmment during training. 7) CNF Greedy: the neural router is simply replaced by the heuristic method, where each model selects I. hardest instances. We use [87] as the attack method in Section 5. For training efficiency, we set T in the main experiments. The step size a is randomly sampled from 100.
Setups for Ablation Study. We conduct extensive ablation studies on components, hyperparameters and routing strategies as shown in Section 5. For simplicity, we slightly modified the training setups. We train all methods using 2.5M TSP100 instances. The learning rate is decayed by 10 for the last 20% training instances. For the ablation on components (Fig. 3(a)), we the attack steps T = 2, and remove each component separately to demonstrate the effectiveness of each component in our proposed framework. For the ablation on hyperparameters (Fig. 3(b),, we train multiple models with M E {2. 3, 4, 5}. For the ablation on routing strategies (Fig. 3(C)), we set K. = B for M- M-TopK,, where B= 64 is the batch size, and K. 1 for I-TopK. The other training setups remain the same.
Setups for Versatility Study. For the pretraining stage, we train MatNet [39] on 5M ATSP20 instances following the original setup from [39]. We further train perturbation model by attacking it using reinforcement learning. Concretely, we use the dataset from [42], consisting of 50 "tmat" class ATSP training instances that obey the triangle inequality, to train the perturbation model for 500 epochs. Adam optimizer is used with the learning rate of le - 3. The maximum number of actions taken by the perturbation model is T = 10. A ffter the pretraining stage, we use the pretrained model to initialize M = 3 models, and further adversarially train them. We fix the perturbation model and only update it using the latest model every E' 10 epochs (as discussed in Appendix B.3). After the 10th epoch, there would be M perturbation models corresponding to M models. Following [42], we use the fixed IK clean instances for training. In the inner maximization, we generate MK local adversarial instances and 1K global adversarial instances using the perturbation models. However, since the perturbation model is not efficient (i.e., it needs conduct beam search to find edges to be modified). we generate adversarial instances in advance and reuse them later. Then, in the outer minimization, we load all instances and distribute them to each model using the jointly trained neural router. The models are then adversarially trained for 20 epochs using the Adam optimizer with the learning rate of - 5, the weight decay of Te 6, and the batch size of B 100.
D.2 Data Generation
We follow the instructions from [37] to generate synthetic instances. Concretely, 1) Uniform Distribution: The node coordinate of each node is uniformly sampled from the unit square (O, 1). as shown in Fig. 6(a). 2) Rotation Distribution: Following [6], we mutate the nodes, which originally follow the uniform distribution, by rotating a subset of them (anchored in the origin of the Fuclidean plane) as shown in Fig. 6(b). The coordinates of selected nodes are transformed by
cos(pp)
sin(p)]
multiplying them with a matrix
cos(p)) where & ~ [0, 2T]] is the rotation angle. 3)
sin(()
Explosion Distribution: Following [6]. mutate the nodes, which originally follow the uniform
distribution, by simulating a random explosion. Specifically, we first randomly select the center of explosion ve (i.e., the hole shown in Fig. 6(c)). All nodes i within the explosion radius R = 0.3 is moved away from the center of explosion with the form of v. Ue + (R + +)
P.-n, TT.- where
Exp(A À 1/10) is a random value drawn from an exponential distribution.
In this paper, we mainly consider the distribution of node coordinates. For CVRP instances, the coordinate of the depot node uo is uniformly sampled from the unit square (0, 1). The demand
24

---

(a)
(b)
(c)
Figure 6: The generated TSP instances following the (a) Uniform distribution; (b) Rotation distribu-
tion; (c) Explosion distribution.
of each node & is randomly sampled from a discrete uniform distribution ,1....,9,. The capacity of each vehicle is set to Q |3 + T where is the size of CVRP instance. The demand and capacity are further normalized to 8 5/Q and I, respectively.
Table 5: Performance evaluation against ROCO [42] over 1K ATSP instances.
Fixed
(xl) Gap
Time
(x16) Gap
Time
(x1) Gap
Time
(x16) Gap
Time
LKII3 Nearest Neighhour
0.000%
1s
0.000%
0.000%
0.000S
1s
30.481%
30.481%
31.595%
31.595%
Insertion
3.967%
MatNet
0.784%
0.5g
0.056%
0.931%
0.5s
0.053%
MaiNeLAF (1)
0.817%
0.5%
0.072%
0.827%
0.5s
0.046%
Ss
MatNet, AT (3)
0.299%
1.5%
0.028%
15x
0.319%
1.5s
0.023%
15s
CNF (3)
0.246
1.5s
0.022%
0.278
1.5s
0.015%
15s
D.3 Versatility Study
We demonstrate the versatility of CNF by applying it to MatNet [39] to defend against another attack [42]. The results are shown in Table 5, where we evaluate all methods on 1K ATSP instances. For neural methods, we use the sampling with x1 and x16 instance augmentations following [39, 42]. The gaps are computed w.r.t. LKH3. Based on the results, we observe that 1) CNF is effective in mitigating the undesirable accuracy- robbstey- trade-off; 2) together with the main results in Section CNF is versatile defend against various attacks among different neural VRP methods.
Table 6: Sensitivity Analyses on hyperparameters.
Remark
Optimizer
Batch Size
Normalization
LR
Uniform (100)
Fixed Adv. (100)
Default
Adam
Instance
le-4
0.111%
0.255%
SGD
64
Instance
le-4
0.146%
3.316%
Adam
32
Instance
le-4
0.122%
0.262%
Adam
128
Instance
lc-4
0.088 %
0.311%
Adam
Batch
1c-4
0. 141%
0.247
Adam
Instance
1c-3
0.183%
0.282%
Adam
64
Instance
le-5
0.101%
0.616%
D.4 Sensitivity Analyses
In addition to the ablation study on the key hyperparameter (i.e., the number of models M), we further conduct sensitivity analyses on others, such as the optimizer E [Adam, SGD), batch size [32, 64, 128), normalization layer E [batch, instance), and learning rate (LR) E [le-3, le-4, le- The experiments are conducted on TSP100 following the setups of the ablation study as presented in Appendix D.I. The results are shown in Table 6, where we observe that the performance of our method can be further boosted by carefully tuning hyperparameters.
25

---

D.5
Ablation Study on CVRP
16
Gean
We further conduct the ablation study on CVRP. For simplicity, here only consider investigating the role of each component CNF by removing them separately. The experiments are conducted on CVRPI00, and the setups are kept the same the ones presented in Appendix D.1. The results are shown in Fig. 7. which still verifies the effectiveness of the global attack and neural router in CNF.
12
11
Method
Figure 7: Ablation study on Components.
D.6 Advanced Ensemble-based AT
Here, we consider several advanced ensemble-based AT methods, such as ADP [53], DVERGE [79], TRS [81]. However,
discussed in Appendix A, it is non-trivial to adapt ADP and DVERGE to the VRP domain due their needs for ground -trtt labels the dependence on the imperceptible perturbation model. Therefore, we compare our method with TRS [81], which improves upon Div- Train [32]. Concretely, proposes to use the gradient similarity loss and another model smoothness loss to improve ensemble robustness. We follow the experimental setups presented in Section 5, and show the results of TSP100 Table We observe that TRS achieves better standard generalization but much worse adversarial robustness, and hence fail to achieve satisfactory trade-off in our setting. Morcover, TRS is more computationally expensive than CNF in terms of memory consumption, since it needs to keep the computational graph for all submodels before taking an optimization step.
Table 7: Comparison with advanced ensemble-based AT on TSP100.
POMO (1)
POMO_AT(3)
POMO_HACOS
POMO DOMO_DivTrain (3)
POMO _RROTTRSSTT (3)
CNF (3)
Uniform (100)
0.144%
0.255%
0.135% 0.344%
0.255 0.297%
0.098%
0.118%
Fixed Adv. (100)
35.803%
0.295
0.528%
0.236%
D.7 Visualization of Adversarial Instances
The distribution of generated adversarial instances depends on the attack method and its strength. Here, we take the attacker from [87] an example. We visualize clean instances and their corresponding adversarial instances in Fig. 8, where we show distribution shifts of node coordinates and node demands on CVRP100, respectively.
E Broader Impacts
Recent works have highlighted the vulnerability of neural VRP methods adversarial perturbations, with most research focusing on the generation of adversarial instances (i.e., attacking). contrast, this paper delves into the adversarial defense of neural VRP methods, filling the gap in the current literature on this topic. Our goal is to enhance model robustness and mitigate the undesirable accuracy-robustness trade-off, which is a commonly observed phenomenon adversarial ML. We propose an ensemble-bart a collaborative manner, achieving high generalization and robustness concurrently. Our work sheds light on the possibility of building more robust and generalizable neural VRP methods in practice. However, since our approach introduces extra operations upon the vanilla AT, such as the global attack in the inner maximization and the neural router in the outer minimization, the computation cost may not be friendly to our environment. Therefore, exploring more efficient and scalable attack or defense methods for VRPs (or COPs) is worthwhile endeavor for future research.
collaborative neural framework to adversarially train multiple models in
26

---

CURPL00
CURP100
1.
1.0
0.
3.5
0.8
0.4
0.0
0.2
0.2
0.2
0.2
(a) Clean Instances
(b) Adversarial Instances (Weak)
(c) Adversarial Instances (Strong)
20.5
Parcertage Rreeuency PN
15.4
Perconage
26.2
Node Demand
Mode Demand
(d)
Adversarial Instances (Weak)
(e)
Adversarial Instances (Strong)
Figure 8: Visualization of clean instances and corresponding adversarial instances generated by weak and strong attack [87]. (a-c) shows the spatial distribution of node locations, and (d-e) shows the percentage frequency distribution of node demands over the entire CVRPI00 test dataset.
F
Licenses
Table 8: List of licenses for code and datasets used in this work.
Resource
Type
Link
License
Concorde
Code
Available for academic research use
LKH3 (25)
Code
http://wechhcccH..ed.dd// www.://wwww.....oooooocccccacka.
Available for academic research use
HGS [70]
Code
https//gichuh http:://ww..iiicda///scc---aaaa.
MIT License
POMO (38)
Code
/
MIT License
MaNNet
Code
http://giccuu..com http::///siubb.ccooo////////aaaa
MIT
DIMES [56]
Code
http:://gihuhh..om///MMMMM
MIT License
De<pACO (82)
Code
https//gghhua..com//eemyyyyyyy/
MIT License
HAC (87)
Code
No License
ROCO [42)
Code
No License
Code
https///ithhbbboo com http://gttt....omm./.cccee//tttn www.rittty---uudd-S-S----ooeeeee -moooth-Ensnmbebeee
Lieense
TSPLIB [58]
Dataset
http://comott..iiiooo und hww.eeeeweerr..e.aaoseeee.......
Available for any non commercial use
CVRPLIB [67]
Dataset
http://rpp gol gos inf pac-rio brf.deeeedeeeppppp
Available for academic research
27

---

Table 9: Results TSPLIB [58] instances. Models are only trained 100.
POMO
POMO_A A
POMO_HA
POMO_Div DivTrrin
CNF
Instance
Opt.
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Cap
Obj.
Gap
kroA100
21282
21420
0.65%
21347
0.31%
21308
0.12%
21370
0.41%
21308
0.12%
kroB 100
22141
22200
0.27%
22211
0.32%
22200
0.27%
22199
0.26
22216
0.34%
kroC100
20749
20799
0.24%
20768
0.09%
20753
0.02%
20768
0.09%
20758
0.04%
kroD100
21294
21446
0.71%
21391
0.46%
21407
0.53%
21435
0.66%
21353
0.28%
kroE100
22068
22259
0.87%
22288
1.00%
22167
0.45%
22213
0.66%
22121
0.24%
629
630
0.16%
0.16%
629
0.00%
0.32%
0.16%
lin105
14379
14477
0.68%
14426
0.33%
14408
0.20%
14402
0.16%
14403
0.17%
pr107
44303
44678
0.85%
47819
7.94%
44596
0.66%
46285
4.47%
44719
0.94%
pr124
59030
59389
0.61%
59257
0.38%
59385
0.60%
59558
0.89%
59076
0.08% %
bier127
118282
133042
12.48
118606
0.27%
118608
0.28%
118137
0.05%
118841
0.47%
ch130
6110
0.15%
0.33%
0.08%
0.25%
0.02%
pr]36
96772
97983
1.55%
100225
3.57%
97617
0.87%
100145
3.49%
97567
0.82%
pr144
58537
58935
0.68%
59544
1.72%
58913
0.64%
59265
1.24%
58868
0.57%
ch150
6528
6554
0.40%
6582
0.83%
6556
0.43%
6578
0.77%
6550
0.34%
kroA155
26524
26755
0.87%
26898
141%
26736
0.80%
26813
109%
26722
0.75%
kroB150
26130
26405
1.05%
26506
1.4%
26379
0.95%
26467
1.99%
26494
1.39%
pr152
73682
74249
0.77%
77537
5.23%
75291
2.18%
77127
4.68%
74876
1.62%
1a:195
2323
2486
7.02%
2500
7.62%
2461
5.94%
2467
6.20 20%
2449
5.42%
kroA200
29368
29992
2.12%
30222
2.91%
29771
1.37%
2.64%
29756
1.32%
kroB200
29437
30298
2.92%
30157
2.45%
29890
1.54%
30267
2.82%
29862
1.44%
Is225
126643
134609
6.29%
135801
7.23%
128085
1,14%
134569
6.26%
128436
1.42%
tsp225
3916
4035
3.04%
4031
2.94%
4004
2.25%
4025
2.78%
4001
2.17%
pr226
80369
83470
3.86 %
89455
11.31%
85466
6.34%
90347
12.42%
84914
5.66%
pr264
49135
55157
12.26%
60390
22.91%
53894
9.69%
60957
24.06%
53763
9.42%
a280
2579
2740
6.24%
2741
6.28%
2690
4.30%
2760
7.02%
2701
4.73%
pr299
48191
50785
5.38%
50812
5.44%
50487
4.76%
50535
4.86%
50408
4.60%
42029
3.13%
4.23%
42860
1.98%
4.31%
2.45%
rd400
15281
15775
3.23%
16221
6.15%
15755
3.10%
16135
5.59%
15778
3.25%
R417
11861
133588
17.68
15240
28.49'
14544
22.62%
15637
31.84%
14317
20.71%
pr439
107217
123357
15.05%
120548
12.43%
1179663
10.02%
120212
12.12%
117632
9.71 %
pcb442
50778
54087
6.52%
54686
7.70%
53165
4.70%
55125
8.56%
53281
4.93%
d493
35002
64215
83.46%
38356
9.58%
37685
7.67% %
38168
9.05%
38051
8.71%
uS74
36905
41456
12.33
42045
13.93%
40804
10.57%
41990
13.78%
40737
10.38 %
1M1555
6773
7828
15.58%
7774
14.78%
7658
13.07%
7791
15.03%
7635
12.73
p654
34643
46094
33.05%
51915
49.86%
45447
31.19%
52837
52.52%
46425
34.01%
d657
48912
59082
20.79%
56232
14.97%
55580
13.63%
56635
15.79%
55066
12.58%
u724
41910
49171
17.33%
50583
20.69%
48818
16.48%
50679
20.92%
48692
16.18%
ra1783
8806
10819
22.86%
10769
22.29%
10512
19.37%
10767
22.27%
10473
18.93%
pr0002
259045
325734
25.74%
328459
26.80%
322276
24.41%
335954
29.69%
320624
23.77%
Table 10: Results on CVRPLIB [67] instances. Models are only trained on n = 100.
POMO
POMO_AY
POMO_HA _HCC
POMO DivTrain
CNF
Instance
Opt.
Obj-
Gap
Obj.
Gap
Obj.
Gap
Ohj.
Gap
Ohj.
Gap
X-n101-k25
27591
29282
6.13%
28919
4.81%
29176
5.74%
29019
5.18%
28911
4.78%
X-a106-k14
26362
2.27%
26608
0
1.62%S
26679
1.20%
26672
1.18%
1-1110-k13
14971
15154
1.22%
15298
2.18%
15305
2.23%
15125
103%
15127
1.04%.
X-n120-k6
13332
14574
9.32%
13762
3 333
13734
3.02%
13801
3.52%
13652
2.40%
X-n134-k13
10916
11315
3.66%
11189
2.50%
11250
3 3.06%
11259
3.14%
11248
3,04%
X-n145-k7
15700
16382
4.34%
16233
3.39%
16019
2.03%
16192
3.13%
15980
1.78%
X-n148-ka k46
434488
47613
9.59%
46546
7.13%
46433
6.87%
46504
7.03%
45694
5.17%
X-n162-k11
14138
14986
6.00%
14923
5.55%
14827
4.87%
14942
5.69%
14794
4.64%
X-n181-k23
25569
26969
5.48%
26282
2.79%
26299
2.80%
26211
2.51%
26213
2.52%
X-n195-k51
44225
50296
13%7
50228
13.57%
48987
10.77%
51367
16.1
48823
10.40%
X-n214-k11
10856
11752
8.25%
11868
9.32%
11570
6.58%
11760
8.33%
11587
6.73%
1-233-116
19230
217
9.76%
21054
9.49%
9.55%
9.10%
X-a251-228
38684
41355
6.90%
41313
6. 6.80%
41193
6.49%
41212
6.54%
40992
5.97%
X-n270-K35
35291
39952
13.21%
38837
10.05%
38376
8.74 %
38511
9.12%
38411
8.84%
X-6289-600
95151
105343
10.71
104923
10.27%
104236
9.55%
104786
10.13%
104261
9.57%
k50
47161
53937
14.37%
53772
14.02%
52876
12.12%
53789
14.05%
$2699
11.74%
X-n313-k71
94043
105470
15%
105647
12.34%
104179
10.78%
104375
10.99%
103326
10.30%
X-n331-k15
31102
42292
35.98%
39293
26.34%
36957
18.83%
37047
19.115
36194
16.37%
X-1376-194
147713
162224
9.82%
157156
6.39%
158410
7.24%
158168
7.08%
157880
6.88%
K52
65928
76139
15.49%
76527
16.08%
76080
15. 15.40%
78141
18.52%
74878
13.58%
X-4499-37
36391
46077
26.62%
48372
32.92%
49018
34.70%
46614
28.09%
45219
24.26
X-1469-k188
221824
252278
13.73%
264366
19.18%
258635
16.59%
263698
18.88%
258751
16.65%
X-a502-k39
69226
85692
23.79%
83326
20.37%
83702
20.91%
80082
15.68%
79373
14.66%
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Main contributions and scope are accurately reflect in Abstract and Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in see Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]

---

Justification:
The paper does not include new theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The detailed experimental setups are presented in Section 5 and Appendix D. The source code is uploaded to the supplementary material.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
30

---

Answer: [Yes]
Justification: The source code, test datasets, and detailed instructions are uploaded to the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https:
httpps.ccppublic//ee / ssi ssionooiccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
The experimental setting are presented in Section and Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: T-test is conducted to verify the statistical significance of experimental results, with the threshold of 5%. Please see Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
31

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Experiments compute resources are indicated in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:/:///uurrs...ee https//ccccccccccccccccccccaece csGuidel ines?
Answer: [Yes]
Justification:
This paper respects the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please Appendix E.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Please Appendix F.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "gQpglgLAyQ", "reviewer": "Reviewer_DziC", "summary": "The paper proposes a Collaborative Neural Framework (CNF) to improve the robustness of neural methods for vehicle routing problems (VRPs) against adversarial attacks. CNF introduces two key innovations: first, a global attack strategy that generates diverse adversarial instances by attacking the best-performing model, in addition to the local attacks on individual models. Second, an attention-based neural router that effectively distributes instances to different models for training, achieving satisfactory load balancing and collaborative performance. Extensive experiments show the effectiveness and generalization ability of the proposed method against different attacks.", "questions": "Please see the weakness part.", "limitations": "Yes, the authors discuss the limitations in the conclusion section.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper tackles the crucial yet underexplored problem of adversarial defense for neural VRP methods. \n- The paper is well-structured, with clear problem formulation, technical details, and comprehensive experimental evaluations.", "weaknesses": "- The paper is primarily focused on the empirical evaluation of the proposed framework, without providing any theoretical analysis or guarantees on the robustness or generalization properties of the approach", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer for spending valuable time reviewing our paper and providing positive comments. Here are our detailed responses to your comments, where `W` denotes Weakness.\n\n**W: Theoretical analysis or guarantees.**\n\nThanks for your comment. The majority of the work within the \"learning for solving VRP\" literature focused on the empirical side. They prioritized closing the gap between neural solvers and traditional solvers, lacking theoretical proof of the improvement. In this situation, it’s challenging for us to provide a solid theoretical analysis within the tight rebuttal period. We will try to add further analysis in the final draft. Here, we would like to give some intuition and empirical proof for the effectiveness and soundness of the proposed method:\n\n* *The global attack makes CNF diverse to benefit policy exploration, and it is stronger than the local attack in terms of attacking the ensemble of models.* 1) Diverseness: The global attack is a generalization of the local attack, which means the local attack could be viewed as a kind of global attack when the same model is repeatedly used to generate adversarial examples in each attack iteration. Therefore, by leveraging different model parameters during the attack, the adversarial instances generated by global adversaries can be more diverse than those only generated by local adversaries. 2) Strongness: The collaborative performance of CNF depends on the best-performing model $θ_b$ (w.r.t. each instance) since its solution will be chosen as the final solution during inference. In CNF, the goal of inner maximization is to construct adversarial instances that can successfully fool the entire framework. Intuitively, if we choose to attack other models rather than $θ_b$, the constructed adversarial instances may not successfully fool $θ_b$, and therefore the final solution to the adversarial instance could still be good, which contradicts the goal of the inner maximization. Therefore, to increase the success rate of attacking the CNF framework, for each clean instance, we propose the global adversary and choose the corresponding best-performing model $θ_b$ to be attacked in each iteration of the inner maximization. To empirically justify it, we record the training dynamics of CNF (3) at the middle stage of training on TSP100. We observe that the global adversary could maximally degrade the model performance by increasing the optimality gap to 0.52% while the local adversary could only degrade the model to 0.37%. Please note that a smaller optimality gap denotes a weaker attack.\n\n* *The neural router empowers CNF to reasonably exploit the overall model capacity.* Intuitively, by distributing instances to suitable models for training, each model might be stimulated to have its own expert area. Accordingly, the overlap of their vulnerability areas may be decreased, which could promote the collaborative performance of CNF. As shown in Fig. 5, not all models perform well on each kind of instance. Such diversity in model expertise contributes to the mitigation of the trade-off between standard generalization and adversarial robustness, thereby significantly outperforming vanilla AT with multiple models.\n\nIn summary, instead of independently training multiple models, the effectiveness of the proposed collaboration mechanism in CNF can be attributed to its diverse adversarial data generation and the reasonable exploit of overall model capacity. As shown in the ablation study (Fig. 3(a)), the diverse adversarial data generation is helpful in further improving the adversarial robustness (see results of `CNF vs. W/O Global Attack`). Meanwhile, the neural router has a bigger effect in mitigating the trade-off (see results of `CNF vs. W/O Router`). Both components contribute to the power of CNF, thereby significantly outperforming other baselines.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "OCKNWZdFvf", "reviewer": "Reviewer_AuRq", "summary": "This paper develops a ensemble-based method CNF for adversarial training to enhance the robustness of NCO solvers. CNF demonstrates outstanding performance compared to all current adversarial training frameworks.", "questions": "1. For CVRP, Is it possible to perform adversarial training on the demand values as well?\n2. What's the setting of ablation models in the part Ablation on Components?\n3. For TSP, is CNF equally effective in different network architectures (such as ELG [1])?\n4. Can the neural router used to assign the testing datas to facilitate inference?\n5. Minor questions: \nLine 82 should be 100% instead of 100. \nThe notation $\\tilde{x}$ and $\\bar{x}$ is quite similar which may cause misunderstanding.\nSection 2.2 should include more references, e.g., [2].\n\\theta{r} should be included as input in Algorithm 1.\nWhat's the formula of b(x) in Eq. (4)?\n﻿\n[1] Gao, Chengrui, et al. \"\"Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy.\"\" arXiv preprint arXiv:2308.14104 (2023).\n[2] Goodfellow, Ian, et al. \"\"Generative adversarial nets.\"\" Advances in neural information processing systems 27 (2014).", "limitations": "The discussion in article is comprehensive enough.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The effectiveness of CNF is outstanding.\n2. The motivation, statement, and objective notation in the article are relatively complete.\n3. The paper is well-written.", "weaknesses": "1. The trade-off between generalization (on clean instances) and transitional robustness demonstrated in Figure is not clear.\n2. Compared to the textual illustration of the proposed CNF, Figures 2 and Algorithm 1 are not intuitive enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's time and effort in reviewing our paper and providing constructive comments. Here are our detailed responses to your review, where `W` denotes Weakness and `Q` denotes Question (Q1-Q5).\n\n**W: The trade-off demonstrated in Figure is not clear; Figures 2 and Algorithm 1 are not intuitive enough.**\n\nThanks for your comments. We will polish them to be clearer. Based on the results from Fig. 1 (a-b), conducting vanilla adversarial training (i.e., POMO_AT (1)) can significantly improve the adversarial robustness of the base model (POMO (1)), i.e., ~35% -> ~0.4%, but at the sacrifice of standard generalization, i.e., ~0.15% -> ~0.36%. This demonstrates the existence of an undesirable trade-off between standard generalization and adversarial robustness in VRPs. We further give a detailed explanation regarding Fig. 1, which will be included in the final draft. Please see our response to `Reviewer xLJf Q1`.\n\n**Q1: For CVRP, Is it possible to perform adversarial training on the demand values as well?**\n\nYes, a round operation can be used to project perturbed demands into the discrete valid domain. Please see the detailed formulation (i.e., Eq. (7)(9)) in Appendix C.1. We further show the percentage frequency distribution shift of node demands if perturbing node demands of CVRP instances. Please see Fig. 1 (d-e) of the [uploaded PDF](https://openreview.net/attachment?id=drriUYPVZV&name=pdf) for details.\n\n**Q2: What's the setting of ablation models in the part Ablation on Components?**\n\nThe detailed training setups of ablation studies can be found in lines 969-976 of Appendix E.1. We consider the case of $M=3$ models, and remove each component separately to demonstrate the effectiveness of each component in our proposed CNF. Concretely, our CNF is equivalent to the base model, augmented by the global attack and neural router (i.e., `CNF = POMO_AT + Global Attack + Router`). 1) If we remove the global attack (i.e., `W/O Global Attack`), then only the local adversarial instances are generated in the inner maximization. They are then distributed by the neural router in the outer minimization. 2) If we remove the neural router (i.e., `W/O Router`), then the global and local adversarial instances are generated in the inner maximization. In the outer minimization, the local adversarial instances are distributed to the corresponding model that generates them, while the global adversarial instances are randomly distributed to models for training. 3) If we remove both components, then it is the vanilla adversarial training (i.e., `POMO_AT`), where there is no interaction or collaboration among models.\n\n**Q3: For TSP, is CNF equally effective in different network architectures?**\n\nYes, the proposed CNF can be naturally adapted to other construction solvers, such as ELG [1] and LEHD[2]. In this paper, we mainly consider POMO and MatNet to demonstrate the versatility of CNF to defend against various attacks on different VRPs. Following the reviewer's suggestion, we further conduct an experiment of ELG with a simplified training setup (i.e., half the training instances) due to the tight rebuttal period. The pretrained ELG achieves 0.23% and 15.24% on the clean instances and adversarial instances of TSP100, respectively. Collaboratively training three ELG models through CNF significantly improves the standard generalization and adversarial robustness concurrently (i.e., clean: 0.11%; adv.: 0.25%). This demonstrates the generality of CNF in improving the robustness of neural VRP solvers. \n\n**Q4: Can the neural router be used to assign the testing data to facilitate inference?**\n\nYes, the neural router can be used during inference. The positive side is that it can save inference time if the number of models M is extremely large. However, the neural router cannot fully guarantee to select the corresponding best-performing model w.r.t. each test instance. It may also suffer from the generalization issue if facing OOD instances. With that said, its performance is generally inferior to our default inference strategy. So this is a trade-off between computation and performance. Based on the experiments, we find that $M=3$ models are sufficient for CNF, so we decided to deactivate the neural router to maximize performance during inference.\n\n**Q5: About minor questions.**\n\nWe thank the reviewer for the careful review and for bringing these issues to our attention! We will fix them and add the references in the final draft. The formulation of the POMO baseline in Eq. (4) is $b(x)=\\frac{1}{N}\\sum_{i=1}^Nc(\\tau_i)$, where $N$ is the number of start nodes, $c(\\cdot)$ is the cost function, and $\\tau$ is the constructed solution (or tour) for the input instance $x$.\n\n```\n[1] Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy. In IJCAI 2024.\n[2] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. In NeurIPS 2023.\n```", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "5AsuRvEiZf", "reviewer": "Reviewer_xLJf", "summary": "This paper presents an ensemble-based Collaborative Neural Framework for for vehicle routing problems to improve robustness. Multiple models are adversarially trained for better robustness against attacks and improve generalization, and a neural router routes instances to models for better load balancing and efficacy.", "questions": "1. Figure 1 is not clearly explained and not referred in the paper.\n2. During inference, \"The best solution among them is returned\", how can you tell which is the best solution?\n3. What is \"collaborative manner\" exactly?\n4. What distribution will the generated adversarial instances follow?\n5. Does this paper focus on solving combinatorial optimization problems? How?\n6. As an important part of evaluation, there is no discussion on Table 7 or 8.", "limitations": "Adequate.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Not clear.", "weaknesses": "1. The paper is not organized or written  well.\n2. This paper is not technically sound.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for dedicating your precious time to review our paper and offer feedback. Here are our detailed responses to your comments, where `W` denotes Weakness and `Q` denotes Question (Q1-Q6).\n\n**W: The paper is not organized or written well; This paper is not technically sound.** \n\nDue to the space limit, please see the [General Response](https://openreview.net/forum?id=YfQA78gEFA&noteId=drriUYPVZV). We will further polish our paper.\n\n**Q1: Figure 1 is not clearly explained and not referred.**\n\nFig. 1 is referred in line 34 of Section 1. The motivation of Fig. 1 is to show the robustness issue of existing neural combinatorial solvers and the effectiveness of our CNF compared to vanilla adversarial training (AT). The empirical observations of Fig. 1 can be summarized as follows:\n\n* Based on Fig. 1 (b-c): Recent neural combinatorial solvers (e.g., POMO) suffer from severe robustness issues - their performance significantly deteriorates on adversarial instances (e.g., >> 10% optimality gap on TSP100).\n* Based on Fig. 1 (a-b): Vanilla AT (i.e., POMO_AT (1)) can significantly improve the adversarial robustness of the base model (i.e., (b): ~35.80% -> ~0.39%), but at the sacrifice of standard generalization (i.e., (a): 0.14% -> 0.37%). This is the so-called trade-off between standard generalization and adversarial robustness.\n* Based on Fig. 1 (a-b): Simply increasing the model capacity by naive ensembling multiple models through AT cannot efficiently mitigate this trade-off (e.g., POMO_AT (9) ensembles 9 models, but the standard generalization is still worse than POMO (1)). In contrast, our CNF can effectively mitigate this trade-off by only using 3 models.\n\n**Q2: During inference, how can you tell which is the best solution?**\n\nDifferent from Bayesian optimization, evaluating the solution quality is simple and efficient in routing problems. After constructing multiple solutions, the solution with the minimal objective value (i.e., tour length) is the best one.\n\n**Q3: What is collaborative manner exactly?**\n\nNote that previous baselines (e.g., POMO_AT ($M$)) are **independent**, which means $M$ models are independently trained, and output the best solution found by them. With that said, there is no interaction among $M$ models during training. In contrast, our CNF leverages the **collaboration** mechanism, which can be explained from the below perspectives: \n\n* *Adversarial instance generation in the inner maximization:* we propose the global attack for synergizing multiple models to generate the global adversarial instance by attacking the best-performing model in each iteration, rather than only leveraging each model to independently generate their own local adversarial instances. Suppose we have $M=3$ models ($\\Theta=\\{\\theta_1, \\theta_2, \\theta_3\\}$), the traditional local adversarial instance $\\tilde{x}^{(T)}$ for $\\theta_1$ is generated through $T$ iterations, and $\\theta_1$ is repeatedly used in each iteration. In contrast, our global adversarial instance $\\bar{x}^{(T)}$ can be generated by: $\\bar{x}^{(0)} \\xrightarrow{\\theta_3} \\bar{x}^{(1)} \\xrightarrow{\\theta_1} ... \\xrightarrow{\\theta_2} \\bar{x}^{(T)}$ (i.e., $\\theta_3$ performs the best for $\\bar{x}^{(0)}$; $\\theta_1$ performs the best for $\\bar{x}^{(1)}$; ...). Therefore, there is a collaboration among models for instance generation in CNF.\n* *Policy optimization in the outer minimization:* for baselines, each model is solely trained on the local adversarial instance generated by itself. We design a neural router, intending to maximize the improvement of ensemble performance, to adaptively forward training instances to different models for effective training. In this way, we empirically observe that each model tends to have its own expert area (as shown in Fig. 5), and the total model capacity can be reasonably exploited, which is also a kind of collaboration.\n\nIn summary, CNF facilitates the interaction (or collaboration) among models, facilitating diverse instance generation and making better use of the limited model capacity, hence significantly outperforming baselines.\n\n**Q4: What distribution will the generated adversarial instances follow?**\n\nIt depends on the attack method and its strength. We have provided an illustration in Fig. 4 of the paper. We further visualize the generated adversarial instances in Fig. 1 of the [uploaded PDF](https://openreview.net/attachment?id=drriUYPVZV&name=pdf), where we show distribution shifts of node coordinates and node demands on CVRP100, respectively.\n\n**Q5: Does this paper focus on solving COPs? How?**\n\nNot exactly. This paper focuses on *improving the robustness and generalization of recent neural combinatorial solvers through AT*. Most of these neural solvers leverage the attention mechanism and the variant of Transformer to solve VRPs (see Section 2.1 regarding how they solve VRPs). Nevertheless, their performance greatly degrades on adversarial instances. Therefore, this paper proposes *a new training framework* to adversarially train these neural solvers in a collaborative way, aiming to enhance their robustness and generalization for solving VRPs.\n\n**Q6: There is no discussion on Table 7 or 8.**\n\nWe summarize the results in lines 326-329. Concretely, the results of Tables 7 and 8 show that our method outperforms baselines on most benchmark instances, which has two implications: 1) raising robustness against attacks through CNF can favorably promote various forms of generalization (e.g., cross-size and cross-distribution); 2) there may exist a neural solver with high generalization and robustness concurrently in the COP domain. With that said, the generalization and robustness may not be conflicting goals in COPs [1], which is different from other domains such as image-based tasks. We will add the above discussion in the final draft.\n\n```\n[1] Generalization of neural combinatorial solvers through the lens of adversarial robustness. In ICLR 2022.\n```", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "UXzMu3VtgS", "reviewer": "Reviewer_d2Cb", "summary": "This paper focuses on the robustness of neural combinatorial optimization and proposes a new framework to robustify neural models for routing problems. The core idea is to train a set of models and to let them collectively make the best predictions. The authors have conducted experiments to benchmark the proposed method against various baselines for TSP and CVRP.", "questions": "Q1: How robust are test-time adaptation methods such as meta-learning [58] and neural-guided local search [89]? Since such methods do not solely rely on the pretrained model, they may be inherently robust. Hence, it might be better if this paper also compare with such test-time adaptation methods. \n- [58] Qiu et al. DIMES: A differentiable meta solver for combinatorial optimization problems. NeurIPS, 2022.\n- [89] Ye et al. DeepACO: Neural-enhanced ant systems for combinatorial optimization. NeurIPS, 2023.\n\nQ2 (regarding the limitation): Since it is observed that the proposed method takes more time to converge, is it possible to employ better training schemes to speed up the convergence of the proposed method? For example, [58] found that meta-learning can significantly speed up convergence (see their Figure 1).", "limitations": "The authors have clearly discussed the main limitation in Section 5. Although using multiple models potentially increases the computational burden in both training and inference phases, the authors found that three models typically suffice to achieve good performance. Thus, this does not seem to be a severe limitation. See also Q2.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: The approach to emsembling multiple models in this paper seems novel and interesting. I believe that the idea will be interesting even for more general combinatorial optimization problems.\n\nS2: The empirical performance of the method is impressive. The proposed method consistently outperforms all baselines on TSP and CVRP. Besides that, the experiments section is well written. Sections E.2 (data generation) and 4.3 (discussion on OOD generalization) are particularly interesting.\n\nS3: The authors have provided code and detailed description of experimental settings (Section E.1) to facilitate reproducibility.", "weaknesses": "W1: The proposed method is collaborative AT. Hence, a missing ablation study is *independent* AT, i.e., using AT to train $M$ models independently (say, under different seeds) and outputting the best solutions found by the $M$ models. \n\nW2: This paper did not describe the threat model considered in this work. There should be no guarantee of performance if arbitrary perturbations are allowed. Thus, it might be better if the authors can clearly state what types of perturbations the proposed method is robust against.\n\nW3: This paper describes mainly the training procedure but barely the inference procedure. It might be better if the paper can elaborate more on the detailed inference procedure.\n\nMinor issue: While the authors (as well as prior work) use \"attack\" throughout the paper, I personally do not think this is a precise term. The setting in this paper seems more like OOD than attacking because I am unable to come up with a real-world scenario where an attacker wants to perturb the instance only in order to make the model produce a worse solution for the *perturbed* instance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We genuinely appreciate the effort the reviewer dedicated to evaluating our paper and providing insightful feedback! Here are our detailed responses to your comments, where `W` denotes Weakness (W1-W4) and `Q` denotes Question (Q1-Q2).\n\n**W1: An experiment on independent AT.**\n\nActually, the baseline method POMO_AT (3) in Table 1 refers to the independent AT, where 3 models are adversarially trained separately, and output the best solution. The results of training more (yet independent) AT models can be found in Fig. 1, showing that our method achieves a better trade-off between computation and performance.\n\n**W2: This paper did not describe the considered threat model.** \n\nSpecifically, we consider the threat model of [1] in the main paper, which means that our trained model is robust against the perturbation of input attributes (e.g., node coordinates). To demonstrate the versatility of our method, we consider another threat model of [2] in Appendix E.3, which can be viewed as the perturbation of constraints. Due to the page limit, we present the details of each threat model in Appendix C (e.g., C.1 for [1]; C.3 for [2]). Please kindly refer to them.\n\n**W3: Elaboration on the inference procedure.** \n\nGenerally, given a single trained model, we construct the solution using the greedy rollout with x8 augmentations following POMO [3]. Given multiple ($M)$ models, we construct one solution per model following the above procedure, obtain $M$ solutions for each test instance, and report the best one. The clean performance is evaluated on the test dataset whose distribution is the same as the training one. The adversarial performance is evaluated on the adversarial dataset, which is generated by attacking the pretrained or current model. If we use the threat model of [1], adversarial instances are generated by Eqs. (7-8) as shown in Appendix C.1, and $θ^{(t)}$ in Eq. (7) is then adjusted for different methods and evaluation metrics (e.g., $θ^{(t)}$ is set to the parameters of the pretrained model $θ_p$ if the metric of `Fixed Adv.` is evaluated). Please see lines 256-269 for inference setups. We will include more inference details in the final draft.\n\n**W4: Minor issue: The \"attack\" term, and the real-world scenario.**\n\nWe understand the reviewer's concern. This term is from the general ML and thus we keep it for consistency in this paper. Generally, the attack procedure can be viewed as a way of generating instances on which the current model underperforms. We discuss the potential attack scenarios and practical significance in Appendix A (lines 686-700). We will clarify this terminology and highlight its difference in the COP domain in the introduction section. Please let us know if you have any better recommendations.\n\n**Q1: How robust are test-time adaptation methods such as meta-learning and neural-guided local search?**\n\nThanks for the interesting question. Yes, these test-time adaptation methods [4-6] are relatively robust. This degree of \"robustness\" primarily comes from 1) traditional local search heuristics and metaheuristics, which can effectively handle perturbations but bring much post-processing runtime, or 2) the costly fine-tuning that incurs more inference time on each test instance. Our CNF can also be combined with them to pursue better performance. For example, we further combine CNF with EAS [6] and deliver better TSPLIB results as shown in Table 1 of the [uploaded PDF](https://openreview.net/attachment?id=drriUYPVZV&name=pdf).\n\nFurthermore, following the reviewer's suggestion, we conduct experiments on DIMES [4] and DeepACO [5]. The results are shown in Tables 2 and 3 of the [uploaded PDF](https://openreview.net/attachment?id=drriUYPVZV&name=pdf), where we observe that 1) CNF (clean: 0.12%; adv: 0.24%) outperforms them in most cases (e.g., w/o advanced search) with a much shorter runtime, and 2) test-time adaptation methods (i.e., the purple columns) improve robustness by adopting much post-search effort and consuming hours of runtime. According to the results, we note that 1) directly comparing CNF with these methods with advanced searches (e.g., MCTS, NLS) is somewhat unfair, since the additional post-processing search makes the analysis of model robustness difficult. For example, recent work finds that MCTS is so strong that using an almost all-zero heatmap can achieve good solutions [7], raising doubts about the real robustness of learned models; 2) the post-processing searches are typically time-consuming and problem-specific, making them non-trivial to be adapted to other COPs.\n\nFinally, we highlight that studies on robustness in COPs are still rare, and most work focused on investigating the robustness of neural solvers themselves, due to their advantages in generality on more complex COPs and inference speed. However, inspired by the reviewer's question, attacking test-time adaption methods is a potential research direction, which we will leave to future work.\n\n**Q2: Is it possible to employ meta-learning to speed up the convergence?**\n\nRL-based AM/POMO is known for its slow convergence due to the autoregressive decoding and sparse reward problem. DIMES [4] designs a compact continuous parameterization space of the underlying distribution of candidate solutions (i.e., heatmap) to efficiently search for high-quality solutions. Therefore, DIMES shows a faster convergence (due to its novel paradigm and lightweight network) in their Fig. 1. Furthermore, meta-learning is typically leveraged to help the model generalize across tasks (e.g., problem instances in DIMES). The second-order meta-learning (e.g., MAML [8]) is computationally expensive for training POMO. Therefore, we experiment with FOMAML [8], a first-order meta-learning method. We set the inner update step as 1, and follow our original training setups. Unfortunately, we do not observe an improved training efficiency or convergence. However, we will further explore this inspiring idea in the future.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
## **General Response**

We extend our heartfelt gratitude to all reviewers for their valuable comments. We are pleased to see that the reviewers have recognized our research topic is **crucial** (`DziC`), our method is **novel** (`d2Cb`) and **effective** (`AuRq, d2Cb`), our paper is **well-written** (`DziC, AuRq, d2Cb`), and our experiments are **detailed** and **comprehensive** (`DziC, d2Cb`). We have carefully considered all reviewers' comments by providing detailed **[clarifications and answers]** to the raised concerns and questions, and conducting **[extra experiments]**:

* adapting CNF to ELG to demonstrate the generality;
* showing the distribution of generated adversarial instances;
* checking the robustness of test-time adaptation methods, and comparing CNF with them;
* training CNF with meta-learning to investigate whether it could speed up the convergence.

We will include the above content in the final draft. Furthermore, for the convenience of reviewers and AC to understand and evaluate our paper, **especially in response to the weaknesses raised by `Reviewer xLJf`**, we provide a comprehensive overview of our paper below.

----

**[Paper Organization]:** Section 1 introduces the motivation of the research topic and methodology, and summarizes our contributions. Section 2 elaborates on the background of VRPs and AT. Section 3 details our method, including the overview, technical details, and its soundness. Section 4 presents experimental settings, empirical results, insights, and analyses. The conclusion, limitations, and future work are finally stated in Section 5. The related work is reviewed in the Appendix due to the page limit.

**[Motivation of Research Topic]:** The study on robustness in combinatorial optimization problems (COPs) is critical. It is highly related to the practicality and reliability of neural combinatorial solvers. Recent works observe that the performance of existing neural combinatorial solvers would significantly degrade on adversarial instances (i.e., clean instances with crafted perturbations), and thus start paying more attention to robustness. Most of them only investigate the attack methods, leaving the exploration of effective defense underexplored. In this paper, we focus on not only effectively defending against various attacks but also largely improving the performance on clean instances. Such a study may benefit the development of versatile neural solvers in real-world scenarios. 

**[Motivation of Methodology]:** Previous works simply use vanilla adversarial training (AT) from the adversarial ML literature to deploy defense, which causes an undesirable trade-off between standard generalization (on clean instances) and adversarial robustness (on adversarial instances). This issue is also a well-known research problem in adversarial ML, and an effective solution is to increase the model capacity (e.g., ensembling multiple models). However, according to our experiments in Fig. 1, independently training multiple models and then ensembling them cannot efficiently achieve a favorable trade-off. Therefore, it further motivates us to develop an ensemble-based *Collaborative Neural Framework (CNF)*, a more elegant AT framework facilitating collaboration among models, to achieve a better trade-off.

 **[Technical Soundness / Why CNF Works]:** Instead of independently training multiple models, the effectiveness of CNF can be attributed to the collaboration mechanism inherent in its *diverse adversarial data generation (i.e., global attack)* and *reasonable exploitation of overall model capacity (i.e., neural router)*. As shown in the ablation study (Fig. 3(a)), the diverse adversarial data generation is helpful in further improving the adversarial robustness (see results of `CNF vs. W/O Global Attack`). Meanwhile, the neural router has a bigger effect in mitigating the trade-off (see results of `CNF vs. W/O Router`). We refer to our response to `Reviewer DziC` for the intuition and empirical proof of the effectiveness and soundness of these two components.

Briefly, the global attack makes CNF diverse and strong in benefiting policy exploration and attacking the ensemble of models. The neural router empowers CNF to reasonably exploit the overall model capacity, stimulating each model to have its own expert area. Such diversity in data generation and model expertise contributes to the mitigation of the trade-off between standard generalization and adversarial robustness, thereby significantly outperforming previous baselines.

**[Insight and Significance]:** *Conceptually*, we present insights into the differences in AT between the continuous image domain and the discrete COP domain in Section 2.2. *Technically*, we present insights into how AT could be leveraged to improve the robustness and generalization of neural combinatorial solvers concurrently. *Empirically*, we present insights about 1) the effectiveness of AT as a way of improving the robustness and generalization of neural combinatorial solvers. Raising robustness against attacks through CNF can favorably promote various forms of generalization (e.g., cross-size and cross-distribution); 2) the existence of neural combinatorial solvers with both high generalization and robustness. This implies that generalization and robustness may not be conflict goals in the COP domain.

In summary, our paper presents an early attempt to study the adversarial robustness of neural combinatorial solvers in the context of VRPs. It is also the first work to effectively improve the standard generalization and adversarial robustness concurrently, taking a step towards a more robust and generalizable neural combinatorial solver. We believe our insights can significantly benefit the robustness study in the NCO community, and serve as a solid avenue for future work.

----

We hope our responses can address all reviewers' concerns, and we welcome further discussions if any point is unclear.

The Authors

Meta-review: After the rebuttal, reviewers think that their concerns have been mostly mitigated and they all agree that the paper has benefits. In particular, reviewers think that the paper tackles an important open problem of adversarial defense for routing problems and the effectiveness is outstanding. Therefore, AC will follow the reviewers' vote to accept the paper.

However, note that reviewers also mention some remaining issues that should be addressed in the revised version to further improve the paper. These include:

1. The paper lacks theoretical analysis and guarantee: please provide theoretical evidence for the following two arguments as authors mentioned in the rebuttal: "The global attack makes CNF diverse to benefit policy exploration, and it is stronger than the local attack in terms of attacking the ensemble of models" "The neural router empowers CNF to reasonably exploit the overall model capacity."

2. Please polish your description about the trade-off between generalization and transitional robustness as well as the intuition behind Figures 2 and Algorithm 1.

3. Please clarify the threat models and inference details in the main body.

Please take the above-mentioned comments into consideration in the next version of the paper.
Decision: Accept (poster)