Ensemble-based Deep Reinforcement Learning for Vehicle Routing Problems under Distribution Shift
Authors: Yuan Jiang
Zhiguang Cao
Yaoxin Wu
Wen Song
Jie Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: Vehicle Routing Problem
Distribution shift
Deep Reinforcement Learning
Ensemble Learning
TL;DR: An ensemble learning approach to tackle out-of-distribution issue in routing problems, which trains a set of diverse policies with ensemble-based deep reinforcement learning.

Abstract: While performing favourably on the independent and identically distributed (i.i.d.) instances, most of the existing neural methods for vehicle routing problems (VRPs) struggle to generalize in the presence of a distribution shift. To tackle this issue, we propose an ensemble-based deep reinforcement learning method for VRPs, which learns a group of diverse sub-policies to cope with various instance distributions. In particular, to prevent convergence of the parameters to the same one, we enforce diversity across sub-policies by leveraging Bootstrap with random initialization. Moreover, we also explicitly pursue inequality between sub-policies by exploiting regularization terms during training to further enhance diversity. Experimental results show that our method is able to outperform the state-of-the-art neural baselines on randomly generated instances of various distributions, and also generalizes favourably on the benchmark instances from TSPLib and CVRPLib, which confirmed the effectiveness of the whole method and the respective designs.

Ensemble-based Deep Reinforcement Learning for Vehicle Routing Problems under Distribution Shift
Yuan Jiang
Zhiguang Cao
School of Computer Science and Engineering Nanyang Technological University yuan0050e ntu. edu.
School of Computing and Information Systems Singapore Management University zgcao@smu. edu.sg
Yaoxin Wu
Wen Song*
Department of Industrial Engineering & Innovation Sciences Eindhoven University of Technology wu20tue. nl
Marine Science and Technology Shandong University wensongdemail. sdu, edu. cn
Jie Zhang
School of Computer Science and Engineering Nanyang Technological University zhangj eet.eneu.uuee.eeeeeeeeeeee edu.sg
Abstract
While performing favourably on the independent and identically distributed (i.i..)) instances, most the existing neural methods for vehicle routing problems (VRPs) struggle to generalize in the presence of a distribution shift. To tackle this issue, we propose an ensemble-based deep reinforcement learning method for VRPs, which learns group of diverse sub-policies to cope with various instance dis- tributions. particular, to prevent convergence of the parameters to the same one, enforce diversity across sub-policies by leveraging Bootstrap with random initialization. Morcover, we also explicitly pursue incquality between sub-policies by exploiting regularization terms during training to further enhance diversity. Experimental results show that our method able to outperform the state-of-the-ard neural baselines randomly generated instances of various distributions, and also generalizes favourably on the benchmark instances from TSPLib and CVRPLib, which confirmed the effectiienees of the whole method and the respective designs.
Introduction
The vehicle routing problem (VRP) is type of combinatorial optimization problems (COPs) with significant real-world applications, especially in the field of logistics (.. The goal to optimally route a fleet of vehicles, originating at a depot, to serve a set of clients. Given the NP-hard nature, heuristic methods are usually preferred to solve VRPs in practice. However, traditional heuristics always treat each VRP instance independently, resulting in limited computational efficiency or solution quality (2. Hence, there growing interest developing neural heuristics based on deep (reinforcement) learning to exploit the underlying patterns across VRP instances and then generalize to unseen ones
Early neural heuristics for VRPs were primarily supervised 5 whose performance depends heavily on the ground-truth labels, making them less desirable due the expensive computation for
"Coresponning Author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

obtaining optimal solutions. By contrast, deep reinforcement learning (DRL) relies on feedback from the environment rather than the ground truth optimal solution as a reward. allowing neural heuristics to perform favorably in solving VRPs (6] Typically, DRL. can be used to train networks for selecting the next client (or node) to visit in VRPs 7 8 9 I0I which is more capable of generalizing to different problem sizes in comparison with the supervised counterparts
While DRL-based neural heuristics have achieved series of success for VRPs, most of them perform reasonably well only when the underlying deep models are trained and tested on the independent and identically distributed (i.i.d.) instances with respect to the client locations, e.g., the ones generated using the uniform distribution. In the presence of distribution shifts, they struggle to deliver desirable performance, which greatly hinders the applications of neural heuristics into practice. Especially in real-world VRP instances, the client locations may vary dramatically according to weekday or weekend, sunny or rainy weather, etc, leading to various or even unknown distributions. Therefore, how to strengthen the cross-distribution generalization capability is of great importance to the neural heuristics for VRPs. Although number of preliminary studies have been conducted to investigate this issue, including the distributionally robust optimization (DRO, [3), sorriculum-learnng--bee hardness-adaptive generator (HAC, (14), and adaptive multi-distribution knowledge distillation (AMDKD, [5)), they are still far from optimal due to their inferior performance or less practical settings. Hence, it remains challenging to comprehensively and effectively expand the limited generalization capability of the neural heuristics against the distribution shifts for VRPs.
Motivated by the recognition of the limited capability of an inflexible model to learn from multiple distributions [16,, and inspired by the fact that an ensemble of varied models can leverage their respective strengths to collaboratively handle different distributions [1 18 we propose an end- to-end ensemble-based deep reinforcement learning (EL-DRL) to solve VRPs in the presence of distribution shifts, which ensures diverse and complementary learning across different sub-models (or sub-policies), thereby fostering the cross-distribution generalization capability. Specifically, we first extend the REINFORCE algorithm [99] and policy gradient (20] in DRL to the ensemble setting by adaptively training set of sub-policies on instances of mixed distributions to collaboratively solve a VRP instance. Then, to encourage diversity among the sub- bobboooiiies, we harness Bootstrap with random initialization to enforce that each sub-policy is updated according to different loss signals. Additionally, we also exploit different regularization terms to prevent the collapse of sub-policies by explicitly pursuing inequality among them.
Accordingly, our contributions are outlined as follows. (i) We empirically demonstrate that a simple ensemble of similar sub-policies leads to limited performance in solving VRPs with distribution shifts, (ii) We propose an ensemble- based deep reinforcement learning (EL-DRL), and its ensemble-based policy gradient allows multiple sub-policies to learn to collaboratively leverage their strengths on respective distributions. We foster diversity by assigning different loss signals to sub-policies and applying regularization based incquality metrics. (iii) Our EL-DRL adaptively trains sub- sub-policies on instances of various distributions and is flexible without manually specifying instance class or group 3 [5] to train each sub-policy. (iv) We deploy POMO 99| as the sub-mode in EL-DRL for solving the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) on both synthetic and benchmark instances of various distributions. The results verified the superior cross-distribution generalization of our EL-DRL.
2 Related Works
2.1 Deep Learning for Vehicle Routing Problems
In recent years, there has been extensive exploration of the use of deep (reinforcement) learning to solve vehicle routing problems. The Pointer Network (PtrNet) [4], originated from the encoder- decoder-structured
souuence-t--equennee network in natural language processing (NLP), was em- ployed to solve VRPs using supervised learning. To curtail the computational expense of obtaining ground-truth -ruth labels for VRPs, a follow-up study 21 trains the deep architecture using reinforcement learning. Performance was further improved by introducing a self-attention encoder (22) and an attention decoder, leading to the prominent Attention Model (AM). The POMO [9] was constructed upon the Attention Model, which augmented input instances and started inference from multiple cities. Three distinet strategies were presented for integrating active search into POMO in the inference
phase (23), resulting in significantly improved performance. Graph neural networks (GNNs) and their
2

---

variants, such as graph convolutional networks (GCNs) and graph attention networks (GATs), have
been applied to the graphs of VRP instances 24 25 26 27 51. A concurrent line of improvement
10 focuses on refining an initial solution through iterative local rewriting. Neural methods based on deep learning have shown impressive results when training and testing instances share the same or similar distribution with respect to node locations, such as a uniform distribution 19, 32). However, applying the pre-trained models of these methods to instances with non-uniform or complex distributions can result in significant gaps to optimal solutions (33 [4]. To enable the generalization beyond a single uniform distribution during training, group distributionally robust optimization (DRO, [3] has been used to train neural models such POMO and GCN on different distributions, which requires manual labeling of typical and atypical instances and specifying distribution groups. A perriculum-learning based AM (HAC, [14 has also been explored, which is trained on instances of varying hardness produced by an adaptive generator but limited to the mixed- Gaussian distribution. More recently, study (AMDKI,, (15) distills the knowledge from various pre-trained teacher models, which manually assigns specific distribution to train each teacher model. Multi-view graph contrastive learning (MVGCL, (34) is also applied to incorporate generalizable representations in policy learning for better knowledge transferability across distributions.
methods [28 29 30
31
2.2
Deep Ensemble Learning
Deep ensemble learning models combine the strengths of both deep learning and ensemble learning to achieve superior generalization performance [35] 36 Ensemble learning is recognized as a promising solution for adaptation to various tasks [37 35 36). due to the unique advantage that respective sub-models hold in solving different tasks. A few works have (implicitly) borrowed ideas from ensemble learning to solve VRPs [38 29]. For example, MDAM 38 leverages the AM equipped with multiple decoders to solve VRPs, and each decoder corresponds to a sub-model in ensemble learning. However, due to the demanding computation, no mechanism in place to ensure the diversity of constructed solutions beyond the first node. L2I (29] requires manually assigning modification rules to train different policies separately, which also takes prohibitively long runtime to search for better solutions iteratively. In summary, these works focus more on combining multiple models rather than promoting the automatic acquisition of diverse knowledge. On the other hand, diversity crucial in ensemble learning for improving prediction performance and robustness (39 40). Ensemble diversity measures, algorithms for creating diverse ensembles, and ensemble consensus have been investigated to produce high-accuracy ensemble outputs 41 42). Our work differs from existing DRL-based methods for VRPs in that we explicitly consider and enforce diversity among sub-models, allowing them to capture different patterns from various distributions without much manual interference.
3 Methodology
In this section, we present how our ensemble learning paradigm trains set of diverse DRL-based sub-policies, i.e., EL-DRL (see Figure [T. to solve VRP instances of various distributions effectively.
3.1 Preliminary
The traveling salesman problem (TSP) and the capacitated vehicle routing problem (CVRP) are the two most classic VRP variants. The TSP involves finding the optimal route to visit set of N cities (or nodes) {ti, 12,-... , with the objective to minimize the total distance traveled. The CVRP considers a fleet of (homogeneous) vehicles with limited capacity, where the vehicle must only visit a client once and also satisfy its demand. The objective is to minimize the total distance traveled by all vehicles while complying with the capacity constraint.
Our EL-DRL originates from the conjecture that high similarity in parameters of the neural network in the ausemble-based learning paradigm correlates to poor performance, as demonstrated in Section 4.4 Recent studies on ensembles with reinforcement learning 43
4 have primarily focused on utilizing deep Q-learning [46) to play games with a limited number of actions determined by the game controller. However, estimating Q-values for VRPs with hundreds of potential actions (i.c., the next node to visit) is challenging [26] 47), and the performance of these methods is often inferior to that of policy gradient [48). We bridge this gap by designing the ensemble-based DRI. (EL-DRL) to solve VRPs with policy gradient. While we build EL-DRL on top of the policy optimization with multiple optima (POMO) (9) our method is generic and can also be applied to other neural heuristics.
3

---

For clarity, we begin by explaining the process of using a single policy to solve a TSP instance through reinforcement learning. In specific, the policy gradient aims learn policy Ty represented by a neural network and parameterized by 0, which constructs solution for the input instance The (partial) solution тę is defined by the sequence of selected actions (1, a2...... a.. Typically, the neural network employs encoder to embed the input features (e.g. coordinates of nodes) and decoder to sample the next action a [8] [0]. To solve TSP, the decoder autoregressively outputs the probability distribution Te (- Tr) for selecting valid node (action) to visit at each step & E {I,.... N such that Te (T) = II. me (dr+1 8, Tv). Once a complete solution T has been constructed, the negative length of the trajectory can be computed and used as the reward R(T).
3.2 Ensemble- Policy Gradient
Ensemble Learning
Ensemble Inference on various distributions
Red
Solution
Solution
Solution
Pullyyy
Nalk Pudky
SelkPelky
Nabl Pulaa
Sat- Polie
Subliallyy
Sab Pollcy
Mask st.
Unseen Instance
Unseen Instance 2
Instance
Ensemble Models
Sab-Palay
lac Prdie
Instances
Imppeiitty
Solving VRP Disrrbution
VRP Distribtion
Solving Distribution
Figure 1: Illustration of Our EL-DRL. trains sub sub-policies using respective masked reward (rein- forcement loss) signals and inequality regularization to maximize the diversity. During inference, sub-policies synergize by leveraging their strengths on various distributions. Different levels of transparency indicate varied contributions of each sub-policy in deriving the solutions.
Our architecture employs shared attention encoder from AM [8, followed by M respective attention decoders, as illustrated in Figure I Each sub-policy, denoted by Th" with parameters 6m corresponds to unique decoder plus encoder that shares parameters with other sub-policies. In this way, the overall representation an instance is only calculated once through the (computationallyy intensive) encoder. The subsequent lightweight decoders reuse this representation and collaboratively select nodes autoregressively. reducing the computational overhead for the ensemble training.
In our EL-DRL, the action at each step is determined by gathering output from all sub-policies, ie, No (a(++1 s, Tx) 7 Σ1 T& (a++1 s, T.). This is inspired by the real-worke practice where open-source communities combine the strengths of different individuals to achieve various common goals [49]. Similarly, our ensemble policies leverage the strengths of individual sub-models, e.g., some of them may perform well on Uniform distribution, while others excel on Gaussian distribution. Consequently, EL-DRL is dominated by any individual sub-policy. Instead, it averages the probabilities produced by all sub-policies to determine an action at each step.
Using complex RL algorithms may not guarantee significant improvement. A better practice is to tailor learning algorithms for routing problems. We train the sub-policy with the REIN- FORCE algorithm [19] based on the POMO m9del[9]. which samples set of solution trajectories [T',T² ...., NN that start from each all nodes (i E {1, N)), and gather each return R (7') (i.e., the negative of route length). The goal is to maximize the reinforcement learning objective L= E, R (r E,zaag R R(22). (r2)..E,, ..,.NN R (T~) by updating 0 to increase the likelihood of sampling desirable trajectories in the future. We extend this objective multiple sub-policies, which maximizes the expected return LRI with gradients computed as below,
A (
1
VL(0 [18|s)
-b(s) V log TH (rin s): (T(m)
NM
where b(s) is a baseline reduce the gradient variance, ف (T s)) means the probability produced by the m-th sub-policy for the solution Th given the instance s. Our sub-policies synergize to generate single trajectory for each starting node i, thus we have T T' and R(( RR(T') for all m.

---

While it is feasible to train all the sub policies together with Eq. (T.. directly applying it to them may lead to the identical convergence of parameters, because all sub-policies receive the same reward which is used to compute the reinforcement loss signal. To alleviate this issue, we harness the Bootstrap with random initialization [50] for training the ensemble of sub-policies, which fosters diversity across the sub-policies via two mechanisms. Firstly, we initialize all decoders with distinct random parameters, inducing an initial diversity in the ensemble. Secondly, we leverage distinct reinforcement loss signals to train each sub-policy. In particular, for sub-policy Tø" we generate binary masks w from Bernoulli distribution with parameter 3 E (0, 1] and then apply them to the rewards. Integrating those designs into Eq.
we arrive at:
N
M W (R(7') b(s)) V log ng (+)
VLRL
NM
When updating the decoder parameters of sub-policies, we also apply the bootstrap mask to each objective function, similar to the above one in Eq. (2). Additionally, we utilize a shared baseline b(s) averaged from all sampled trajectories:
N
M
b(8) = NM R(T))
N Σ R(T).
1=1 ml
The probabilities of producing the actions of 7$ are reinforced through other N-1 unique trajectories. This shared bascline contributes to reducing gradient variance, and also potentially helps restrain the identical convergence with respect to the sub-policies 9
3.3 Diversity Enhancement via Regularization
To further promote the diversity of the ensemble of sub-policies, we exploit the regularization to encourage explicit diversity across the parameters 0² ..,.. 0M of sub-policies during training. In order to prevent sub-policies from converging to the same parameters or simply duplicating each other, we need to push them away from each other in the parameter space.
This motivates us to measure and pursue the inequality between sub- cub-policies. Therefore, we utilize statistical measurement of inequality within a population (ensembles) in economics. i.c., the Theil index [51]. From the perspective of information theory, it is also a measurement of redundancy, which indicates the difference between the maximum possible entropy of the data and the observed entropy 42). With the Theil index, we could measure whether our ensembles have learned their respective knowledge instead of imitating each other. Concretely, the first regularization term based on the Theil index in our loss function is expressed as Ly = 37 Σ m=
Zm In Em, where En, is the
(2-norm of 6. and μ is the mean of all norms..
Furthermore, since we rely on an ensemble of sub-policies to make the decision, we could also explicitly exert a penalty that discourages all the individual sub-policies from converging toward a common value. This inspires us to utilize the second regularization term from the principles of consensus optimization [52]. where multiple models are independently optimized with their own task-specific parameters. Formally, this regularization term is defined Lp >M where 9 is the mean of the parameters for all sub sub-policies.
pm |
Notice that we intend to minimize the objective function for training our EL-DRL, thereby we integrate the regularization terms with negative signs to maximize the ensemble diversity (inequality). The whole loss function, inclusive of regularization terms with their coefficients (aj and a2)) for our EL-DRL is expressed as:
- VL = -
At last, the parameters of policies are updated using gradient ascent based on Eq. (4). In the inference phase, EL-DRL collaboratively and greedily produces multiple trajectories by augmenting each input instance with rotations (9] and starting the trajectory from each of all nodes. The final solution specified as the best one among all the sampled trajectories (solutions).
5

---

4 Experiments
We propose EL-DRL to train multiple diverse policies for enhancing cross-distribution generalization performance. To evaluate the robustness of our method in handling distribution shifts, EL-DRL and other baselines are tested on synthetic TSP and CVRP instances from various distributions, together with benchmark instances from TSPLib [53] and CVRPLib [54]. Additionally, we perform ablation experiments to demonstrate the importance of diversity and the key designs of our EL-DRL.
Baselines. For TSP experiments, we evaluate against the Concorde exact solver 55 and represen- tative end-to-end neural approaches: Attention Model (AM) (8) Policy Optimization with Multiple Optima (POMO) 19], Multi-Decoder Attention Model (MDAM) 38) Distributionally Robust Op- timization with POMO (DROP) [13], Barrdness-Adattin Curriculum (HAC) [1], and Adaptive Multi-Distribution Knowledge Distillation (AMDKD) [.S. Of these methods, DROP, HAC and AMDKD are recent approaches tackling the cross-distribution generalization issue for solving VRPs. As HAC was initially intended only for TSP, we did not take it into account for our CVRP experiments.
Implementation. EL-DRL employs an architecture similar to AM but with one encoder and four decoders as the backbone. Preliminary experiments showed that the use of four decoders allows for good balance between computational overhead and performance. Each sub-policy was trained using the same hyperparameters as the original POMO [9]. We use Adam optimizer with a learning rate of le-4. The values of a and 02 are tested and set according to testing sets, All the experiments of neural baselines are conducted in parallel on NVIDIA GTX 2080Ti GPUs for both training and inference. The training time for EL-DRL varied with the problem size. Taking CVRP100 as an example, one epoch takes about 5 minutes for EL-DRL. We applied early stopping during training when the reduction in the gap was not significant.
The optimal solution for TSP is calculated using the Concorde solver? For CVRP, as existing solvers difficult to obtain optimal solutions within an acceptable time frame, we employ the strong heuristic HGS [56] as the traditional baseline instead, which has reported better performance [37] reuse their open-sourced code from GitHub. For than LKH3 (58) Regarding neural baselines,
AM-based baselines, we sample 1,280 solutions following [8] for MDAM we set beam search size to 50; for POMO-based baselines, we adopt the greedy rollout with augments following (9, which produces multiple greedy trajectories by rotating each input instance to generate 8x augmented instances with 8 different angles but the same optimal solution. For each generated instance. it starts the trajectory from each of the N nodes. In this way, POMO-basee baselines sample 8 x N solutions in total for each input instance.
Dataset. To ensure the hardness and variety of training distributions and to guarantee that the training instances are not seen during testing, we generate 7.2 million training instances from mixed distributions. Data generation is done by first sampling a uniform instance and then non-repetitively applying three randomly mutation operator of TSPGEN to the same instance. So single training instance is of mixed distributions and does not belong to any single distributions in the testing. During the inference, unlike most existing neural heuristics that are only tested on a uniform distribution, we evaluated all methods on various distributions, including Explosion, Compression, Cluster, Expansion, and Rotation, to assess the generalization performance against distribution shift. These distributions are more diverse in terms of both visual and quantitative measures compared to the uniform distribution [59], making it fairly challenging for neural heuristics to generalize. We test baselines on 10,000 instances in total, with each of the five testing distributions containing 2,000 instances. Therefore, the training instances do not fall into any type of testing distribution and all the test instances are sampled from distribution not seen during training. HAC is trained on instances created by the built-in data generator as its design relies on this process. The training of DROP requires class labels of the input instance and we specify the class of the last applied mutation operation for it. AMDKD requires manually assigning a single distribution for training each teacher model, which is less applicable to setting where each single training instance is of mixed distributions. Thus, we follow its original setting for the best performance, and directly utilize the pre-trained AMDKD solve instances from TSPLib and CVRPLib (Ta
hhups://githubbb "hans//ggthub..om//hhwwwwww hyt.:///hw.cccmm/mmc/////////gge http::/gtthl..ooomsoooooos//spee

---

4.1 Cross-distribution Generalization on TSP
Table Results cross-distribution generalization on TSP50
Distribution
Metric
||
Concorde
AM
POMO
MDAM
HАC
DROP
EL-DRL
Len. Gap
4,74
4,88
4.84
4.87
4.85
4,88
4.83
Explosion
0.00%
2.95%
2.11%
2.74%
2.32%
2.95%
1.90%
Len. Gap
5.22
5.37
5.33
5.36
5.35
5.34
5.32
Compression
0.00%
2.87%
2.11%
2.68%
2.49%
2.30%
1,92%
Len. Gap
5.37
5,56
5.50
5.53
5.52
5.48
Cluster
0.00%
3.54%
2.42%
3.17%
2.98%
2.79%
2.05%
Len.
4.44
4,58
4.55
4.57
4.58
4,60
4.53
Expansion
Gap
0.00%
3.15%
2.48%
2.93%
3.15%
3.60%
2.03%
Len.
4.54
4.69
4.64
4.67
4,66
4.64
4.63
Rotation
Gap
0.00%
3.30%
2.20%
2.86%
2.64%
2.20%
1,98 %
Avg. Inf. Time
0.08
0.07
0.01
0.01
0.02
Table 2: Results of cross-distribution generalization TSP100
Distribution
Metric
||
Concorde
AM
POMO
MDAM
HAC
DROP
EL-DRL
Len. Gap
6.09
6,31
6.22
6.29
6.38
6.27
6,21
Explosion
0.00%
3.61%
2.13%
3.28%
4.76%
2.96%
1.97%
Len. Gap
6.89
7.16
7.06
7.12
7.18
7.12
7.03
Compression
0.00%
3.92%
2.47%
3.34%
4.21%
3.34%
2.03%
Len.
7.26
7.58
7.45
7.53
7.63
7.46
7.41
Cluster
Gap
0.00%
4.41%
2.62%
3.72%
5.10%
2.75%
2.07%
Len.
5.57
5,80
5.72
5.88
5.74
Expansion
Gap
0.00%
4.13%
2.69%
3.77%
5.57%
3.05%
2.15%
Len.
6.02
6,28
6.17
6.24
6.34
6.23
6,14
Rotation
Gap
0.00%
4.32%
2.49%
3.65%
5.32%
3.49%
1.99 %
Avg. Inf. Time
||
0.50
0.22
0.02
0.16
0.23
0.03
0.04
We evaluated the cross-distribution generalization of our EL-DRL on TSP50 and TSP100. Tables [ and gathered the averaged tour length and gaps of all baselines compared to the exact solver Concorde on unseen instances from five different distributions. Although all baselines were trained on mixed distributions, they did not generalize well to other specific distributions (especially for AM), resulting in drastically deteriorated performance (about 2.5% to 4% gaps) compared to the i.i.d testing results they reported in the original paper. For example, POMO reports only 0.03% and 0. 0.14% gaps compared to LKH3 (58) on TSP50 and TSP100, respectively, when trained and tested on uniform distribution in [9] However, its gaps increase up to 2.69% in our cross doot-iiittiittion experiments. This phenomenon implies that these neural baselines are relatively incapable of learning from the underlying common patterns on complex training distributions. In contrast, our EL-DRL significantly improved generalization performance on the five respective testing distributions, achieving the smallest gap among neural heuristic baselines. For example, 2.34% (2.07% vs. 4.32%) compared to AM and achieved a 0.55% (2.07% vs 2.62%) gap reduction on the TSPI00 with Cluster distribution compared to the best neural baseline POMO. Notice that while multiple decoders in MDAM slightly improved its performance compared to AM, it failed to generalize to various distributions with gaps exceeding 3.2% on TSP100. This indicates that simply composing multiple models (even with KL divergence) does not necessarily result in good generalization performance. Meanwhile, EL-DRL also consistently beats the recent generalization- specialized DROP and HAC in terms of both gaps and time efficiency. Especially. DROP exhibits unstable generalization performance and HAC does not generalize well on TSP (4.21-5.32% gaps), possibly due to special data processing requirements for training. which hinder their application to our scenario. In short, our EL-DDRL outperforms these two ofate-of-the-art approaches in generalizing to cross noos-distribution.
EL-DRL reduced the gaps by
7

---

Table 3: Results of cross-distribution generalization CVRP50
Distribution
Metric
HGS
AM
POMO
MDAM
DROP
EI--DRT.
Len.
9.79
10.02
9.92
9.98
9.91
Explosion
Gap
0.00%
2.35%
1.33%
1.94%
1.23%
0.82%
Len. 10.14
10.39
10.28
10.35
10.32
10.24
Compression
Gap
0.00%
2.47%
1.38%
2.07%
1.78%
0.69 %
Len.
10.35
10.60
10.49
10.56
10.49
10.45
Cluster
Gap
0.00%
2.42%
1.35%
2.03%
1.35%
0.87 %
Expansion
Len.
9.53
9.61
9.61
Gap
0.00%
2.55%
1.38%
2.23%
2.23%
0.85 %
Len.
9.43
9.66
9.56
9.62
9.58
9,53
Rotation
Gap
0.00%
2.44%
1.38%
2.01
1.59%
0.74%
Avg. Inf. Time (s)
30
0.22
0.01
0.13
0.01
0.02
Table 4: Results of cross-distribution generalization on CVRP100
Distribution
Metric
HGS
AM
POMO
MDAM
DROP
EL-DRL.
Len.
14.79
14.76
14.70
14.62
Explosion
Gap
0.00%
3.43%
2.45%
3.22%
2.80%
2.24%
Compression
Len. 14.82
15.36
15.21
15.28
15.32
15.18
Gap
0.00%
3.64%
2.63%
3.10%
3.37%
2.43%
Len.
15.44
15.99
15.83
15.91
15.90
15.79
Cluster
Gap
0.00%
3.56%
2.53%
3.04%
2.98%
2.27 %
Len. 13.70
14.18
14.02
14.17
14.19
13.99
Expansion
Gap
0.00%
3.50%
2.34%
3,43%
3.58%
2.12%
Len. Gap
13.97
14.46
14.30
14.40
14.39
14.28
Rotation
0.00%
3.51%
2.36%
3.08%
3.01 %
2.22%
Avg. Inf. Time (s)
30
0.29
0.03
0.17
0.05
0.08
4.2 Cross-distribution Generalization CVRP
Pertaining to CVRP, we present the averaged tour lengths and gaps to the best solutions (obtained from the HGS with a 30s runtime), along with the average time inference on unseen instances of CVRP50 and CVRP100 from five distributions in Tables and 4 respectively. Overall, the HGS solver performs the best regarding tour length, as this heuristic highly specialized for CVRP. Notably, we observe greater advantages of our method against neural baselines on this harder problem than on TSPs. Our EL-DRL achieves superior results on unseen instances of various distributions, with significantly small gaps (0.69-0.87% on CVRP50, and especially outperforms POMO by around 0.7% on Compression distribution. Table 4 shows that for neural baselines, generalizing to various distributions CVRP100 is also challenging, with considerable gaps ranging from 2.36% to 3.64%. In contrast, our method consistently delivers high-quality solutions with shorter lengths and less sensitive distribution shifts, which attains gaps of close to 2% for cross-distribution generalization on CVRP100. This superiority verifies the effectiveness of our idea of leveraging the strength of handling different distributions through cooperation between sub-policies. Regarding efficiency, all neural baselines can solve an instance in less than one second. Owing to our design of lightweight ensemble architecture and parallel inference, EL-DRL does not incur much inference time than the counterparts using a single model while yielding better performance and even exhibiting faster inference than AM and MDAM.
4.3 Real World benchmarks
We continue to evaluate our EL-DRL by taking public benchmark datasets TSPLib [53] and CVRPLib (54 as the testbed, to prove our approach also efficient solving more realistic and varied distributions. TSPLib is a library of TSP instances from various sources and of various types, making desirable yet challenging for assessing generalization. For TSPLib, results are collected from 25 instances which problem sizes ranging from 50 to 300. For CVRPLib, the dataset is XML100, which

---

Table 5: Results on Real-World Benchmarks
Dataset
Metric
Opt.
AM
|POMO MDAM
HAC
DROP/AMDKD EL-DRU
Len.
6.86
8.02
7.44
7.73
8.65
7.45
7.42
TSPLib
Gap
0.00%
10.53%
5.16%
7,82%
16.75%
5.79%
5,30%
4.85 %
Avg. Time (s)
0.48
0.47
0.36
0.48
0.35
0.53
0.95
Len.
16.97
17.82
17.70
17.76
17.84
17.67
17.65
CVRPLib
Gap
0.00%
6.05%
4.51%
4.90%
5..25%
4.32%
4.12%
Avg. Time
0.29
0.03
0.15
0.05
0.03
0.08
contains 10,000 CVRPI00 instances from heterogeneous distributions. We normalize the coordinates in each instance to range of [O, 1] for all neural methods, which also include the neural baseline AMDKD [5]
The upper half of Table 5 illustrates the averaged results on TSPLib instances. These results demonstrate that EL-DRL generalizes well to realistic distributions and varied sizes, in small gap (4.85%), and it is much lower than the gaps of neural heuristics (i.e., around 5%%...%.. ) In particular, the advantage of our EL-DRL over MDAM implies learning similar ensembles may hold back the generalization performance. Compared to the poor results of HAC, which learns only from Gaussian distribution, can conclude that training the models on various heterogeneous distributions could be more beneficial. In comparison to the most recent aameralization-speciaaie brings reduction in the gap by 0.51 %. The lower half of Shols the averaged lengths and gaps on (harder) CVRPLib instances. Our EL-DRL again outperforms the top two baselines, AMDKD and POMO, by margins of 0.20% and 0. 0,40,, respectively. The results on the realistic benchmarks underscore the remarkable capability of our EL-DRL in solving miscellancous instances that were not present during the training phase, highlighting its robustness in coping with distribution shifts.
AMDKD, our EL-DRL
4.4 Ablation Studies
Table 6: Ablation Studies on CVRPI00
Method
POMO
MultiPPOMO
EL-DRL
w/o BRI
w/o Ey
w/o Lp
Avg. Length
14.801
14.784
14.747
14.768
14.752
14.756
Avg. Gap 2.423%
2.311% 1%
2.055 %
2.201% %
2.090%
2.118%
We also carry out ablation studies to demonstrate the effectiveness of key designs in our EL-DRL, by generating 10,000 CVRPI00 instances as an exemplary case and presenting the results in Table 6 To investigate the disadvantage of high similarity between ensemble policies, we deploy single POMO and an ensemble of four POMOs (Multi-POMO), respectively, to compare with our EL-DRL. Additionally,
ablate Bootstrap with Random Initialization (BRI), the Theil index regularization (Cr) and parameter dissimilarity regularization (Lp), then report the averaged results for the 10,000 instances of five distributions on CVRP100. First, the single POMO model relies on its own learning ability, increasing the susceptibility to over-fitting and leading to poor generalization performance. However, simply stacking POMO to multiple copies (Multi-POMO) cannot overcome this limitation and only brings slight improvement compared to the single POMO, which is primarily attributed the larger amount of model parameters and in accordance with the finding in (60]. By contrast, our EL-DRL attains 0.37% reduction of the overall gaps compared to the single POMO by collaboratively solving instances on various distributions. Excluding the Bootstrap with random initialization, sub-policies cannot receive distinct loss signals and converge to similar ones, and thus the gap of the variant without BRI increases significantly 2.201 compared to that of EL-DRL (2.055%). Moreover, removing two regularization terms for maximizing diversity results in redundant parameters for sub-policies and hinders their expressive ability, as evidenced by the drop in generalization performance shown in the last two columns of Table 6 In summary, the designs of our EL-DDRL are largely orthogonal and can be effectively integrated to maintain ensembles of diverse sub- moodmodess, which capable of capturing different aspects of various distributions.

---

Conclusion and Limitation
This paper presents an ensemble-based DRL approach for solving vehicle routing problems, which fosters the capability of existing neural heuristics in generalizing against distribution shifts. By enforcing distinet reinforcement loss signals on each sub-policy and integrating regularization to ensure diversity across sub-policies, our EL-DRL learns to leverage the strengths of individuals in solving different instances with various distributions. In our experiments, we demonstrate that our proposed method delivers high-quality solutions for both synthetic instances of various distributions and heterogeneous instances from real-world benchmarks, confirming the potential of the ensemble idea in contributing to more generalizable and robust neural heuristics.
While it the focus of this paper, our method might be less effective in handling large instances. A major reason is that the scalability of our EL-DRL highly depends on the sub-model, where POMO (the used sub-model) performs inferior on large ones. Moreover, since our EL-DRL follows the ensemble paradigm, the training needs more computational resources than the single one. In the future, we would like to, 1) foster the scalability of our method by exploring decomposition schemes such as the divide-and-conquee [6]], so as to allow it to solve large instances more efficiently; 2) enhance the computational efficiency of our method by introducing sparsity in ensemble learning [62]. so to allow it to train more sub-models while reducing the training overhead; 3) enable the interpretability (63] and further strengthen the collaboration among the sub-models of our method; and 4) extend our method non-routing combinatorial optimization problems.
Acknowledgments and Disclosure of Funding
This research was supported by the National Natural Science Foundation of China under Grant 62102228, the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier grant, and the RIE2025 MTC IAF-PP funding (M2314a0001).
10

---

References
[1] KORTE Bernhard and JENS Vygen. Combinatorial optimization: Theory and algorithms. Springer, 5th Edition., 2012.
[2] Natalia Vesselinova, Rebecca Steinert, Daniel F Perez-Ramirez, and Magnus Boman. Learning combinatorial optimization graphs: A survey with applications to networking. IEEE Access, 8: 1112088-120416, 2020.
[3] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon, European Journal of Operational Research, 29022):055-221, 2021.
[4] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, pages 2692-2700, 2015.
[5] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. In INFORMS Annual Meeting, 2019.
[6] Kai Anulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. A brief survey of deep reinforcement learning. arXiv preprint arXiv: 05866, 2017.
[7] Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combi- natorial optimization with reinforcement learning. In International Conference on Learning Representations, 2017.
[8] Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn solve routing problems! In the 7th International Conference on Learning Reprexentations, 2019.
[9] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, 2020.
[10] Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34, 2021.
[1]] Chaitanya Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, pages 1-29, 2022.
[12] Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Towards omni-generalizann neural methods for vehicle routing problems. In International Conference on Machine Leurning, 2023.
[13] Yuan Jiang. Yaoxin Wu, Zhiguang Cao, and Jie Zhang. Learning to solve routing problems via distributionally robust optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9796-9794, 2022.
[14] Zeyang Zhang, Ziwei Zhang, Xin Wang, and Wenwu Zhu, Learning to solve travelling salesman problem with hardness-adaptivv curriculum. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9136-9144, 2022.
[15] 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 Advances in Neural Information Processing Systems, 2022.
[16] Alan Pham, Eunice Chan, Vikranth Srivatsa, Dhruba Ghosh, Yaoqing Yang, Yaodong Yu, Ruiqi Zhong, Joseph E Gonzalez, and Jacob Steinhardt. The effect of model size worst-group generalization. arXiv preprint arXiv:2112.0400
2021.
[17] Guilherme Perin, Lukasz Chmielewski, and Stjepan Picek. Strength in numbers: Improving generalization with ensembles in machine learning- based profiled side-channel analysis. JACR Transactions Cryptographic Hardware and Embedded Systems, pages 337-364, 2020.
11

---

[18] Jieting Wang, Yuhua Qian, Feijiang Li, Jiye Liang, and Qingfu Zhang. Generalization perfor- mance of pure accuracy and its application selective ensemble learning. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2022.
[19] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3):229-256, 1992.
[20] Jan Peters. Policy gradient methods. Scholarpedia, 5(11))3698, 2010.
[21] Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
[22] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[23] André Hottung, Yeong- Dae Kwon, and Kevin Tiemny. Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
[24] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[25] Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Martin Rousseau. Learning heuristics for the tsp by policy gradient. In International conference on the integration of constraint programming, artificial intelligence, and operations research, pages 170-181. Springer, 2018
[26] Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolu- tional networks and guided tree search. Advances neural information processing systems, 31, 2018.
[27] Zhang-Hur Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7474-7482, 2021.
[28] Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
[29] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2019.
[30] Paulo R d 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 Machine Learning, pages 465-480. PMLR, 2020.
[31] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems.. IEEE transactions neural networks and learning systems, 2021.
[32] Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 19th International Conference, pages 190-213. Springer, 2022.
[33] Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günne- mann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference on Learning Representations, 2022.
[34] Yuan Jiang, Zhiguang Cao, Yaoxin Wu, and Jie Zhang. Multi-view graph contrastive learning for solving vehicle routing problems. In Uncertainty Artificial Intelligence, pages 984-994. PMLR, 2023,
12

---

[35] Mudasir A Ganaie, Minghui Hu, AK Malik, M Tanveer, and PN Suganthan. Ensemble deep learning: A review. Engineering Applications of Artificial Intelligence, 115:105151, 2022.
[36] Yongquan Yang. Haijun Lv, and Ning Chen. survey on ensemble learning under the era of deep learning, Artificial Intelligence Review, 56(6):5545-5555 2023.
[37] Kaiyang Zhou, Yongxin Yang. Yu Qiao, and Tao Xiang. Domain adaptive ensemble learning. IEEE Transactions on Image Processing, 30:8008-8018, 2021.
(38) Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 2021.
[39] E. Ke Tang, Ponnuthurai N Suganthan, and Xin Yao. An analysis of diversity measures. Machine learning, 65:247-271, 2006.
[40] Ammar Mohammed and Rania Kora. A comprehensive review on ensemble deep learning: Opportunities and challenges. Journal of King Saud Cnavvesity-Computee and Information Sciences, 2023.
[41] Ling Liu, Wenqi Wei, Ka-Ho Chow, Margaret Loper, Emre Gursoy, Stacey Truex, and Yanzhao Wu. Deep neural network ensembles against deception: Ensemble diversity, accuracy and robustness. In 2019 IEEE 16th international conference on mobile ad hoc and sensor systems (MASS), pages 274-282. IEFE, 2019.
[42] Hassam Sheikh, Mariano Phielipp, and Ladislau Boloni. Maximizing ensemble diversity in deep reinforcement learning. In International Conference on Learning Representations, 2022.
[43] Richard Y Chen, Szymon Sidor, Pieter Abbeel, and John Schulman. Ucb exploration via q-ensembles. arXiv preprint 17X6v:1706.01500 2017.
[44] Oren Peer, Chen Tessler, Nadav Merlis, and Ron Meir. Ensemble bootstrapping for q-learning. In International Conference on Machine Learning, pages 8454 8463. PMLR, 2021.
[45] Litian Liang, Yaosheng Xu, Stephen McAleer, Dailin Hu, Alexander Ihler, Pieter Abbeel, and Roy Fox. Reducing variance in temporal-differene value estimation via ensemble of deep networks. In International Conference on Machine Learning, pages 12285-13301 PMLR, 2022.
[46] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533 2015.
[47] Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combina- torial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3243-3250 2020.
[48] Bingjie Li, Guohua Wu, Yongming Hc, Mingfeng Fan, and Witold Pedrycz. An overview and experimental study of baaming-based optimization algorithms for the vehicle routing problem. IEEE/CAA Journal of Automatica Sinica, 9(7): 115-1111--1188 2022.
[49] Siobhán O' m'mahony and Fabrizio Ferraro. The emergence of governance in an open source community. Academy of Management Journal, 5065):1099-1166, 2007.
[50] Bradley Efron. The jackknife, the bootstrap and other resampling plans. SIAM, 1982.
[51] J Johnston. H. theil. economics and information theory, 1969.
[52] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, al. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122 2011.
[53] Gerhard Reinelt. Tsplib-a traveling salesman problem library. ORSA journal on computing, 3(4):376-384, 1991.
13

---

[54] Eduardo Queiroga, Ruslan Sadykov, Eduardo Uchoa, and Thibaut Vidal. 10,000 optimal evrp solutions for testing machine learning based heuristics. In AAAI-22 Workshop on Machine Learning for Operations Research (MI4OR), 2021.
[55] David Applegate, Robert Bixby, Vasek Chvatal, and William Cook. Concorde tsp solver. https: h/pp:://wwww.. wwtp://wwwww.tw.w//t///..a. wwaterloo. http:o//...cccccccccceeeeeeeeeee wttpo//att..oooo//////oooooreeee
html 2006.
[56] Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap neighborhood. Computers & Operations Research, 140:105643. 2022.
[57] André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. In Proceedings of the 24th European Conference on Artificial Intelligence (ECAT), 2020.
[58] Keld Helsgaun. An extension of the lin-kemnihhan-helsgarr tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, pages 24-50, 2017.
[59] Jakob Bossek, Pascal Kerschke, Aneta Neumann, Markus Wagner, Frank Neumann, and Heike Trautmann. Evolving diverse tsp instances by means novel and creative mutation operators. In Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, pages 58-71, 2019.
[60] G Brown. Diversity in neural network ensembles.lph. d. thesis]. University of Birmingham, 2004.
[61] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 34, 2021.
[62] Li Zhang and Wei-Da Zhou. Sparse ensembles using weighted combination methods based on linear programming. Pattern Recognition, 44(1):97-106, 2011.
[63] Chia-Hsiu Chen, Kenichi Tanaka, Masaaki Kotera, and Kimito Funatsu. Comparison and improvement of the predictability and interpretability with ensemble learning models in qspr applications. Journal of cheminformatics, 12:1-16, 2020.
14


Reviews:
[{"review_id": "O8y3ktmG3X", "reviewer": "Reviewer_PAi5", "summary": "The paper proposes a deep reinforcement learning approach for vehicle routing problems under distribution shift that trains an ensemble of models. During solution construction, all ensemble models are evaluated at each decision step and the actions are selected based on the combined output probabilities. The ensemble is trained and evaluated on instance sets that contain instances sampled from different distributions. Ideally, the individual models have different strength and weaknesses (e.g., with some performing well on uniform instances, while others are better at Gaussian instances) which could result in an improved generalization performance. In order to improve diversity between the ensemble models, the authors propose 3 different components: 1) Bootstrap with random initialization: All models are initialized with different parameter values and during training each model only sees a subset of the training data. 2) Theil index regularization: Aims at increasing the inequality between sub-policies. 3)  Parameter dissimilarity regularization: Aims at increasing the difference between the model parameters. The results indicate that the proposed ensemble approach performs better than comparable approaches.", "questions": "How many solutions do you generate per test instance?", "limitations": "The authors briefly discuss limitations of their approach.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper addresses an important problem (designing a neural combinatorial optimization approach that generalizes to instances from different distributions).\n- The results show that the method outperforms other methods in the considered generalization setting.\n- The authors perform some ablation experiments to evaluate the effectiveness of the proposed diversity-increasing components.", "weaknesses": "- Overall, I am not fully convinced that the concept of combining outputs of multiple models to create a single solution is ideal for the neural combinatorial optimization setting where we usually generate multiple solutions per instance. In the classical machine learning prediction setting, model outputs are combined because users are interested in a single prediction. In the considered neural combinatorial setting there is no direct need to combine model outputs, instead one solution could be generated per ensemble model.\n- While the authors performed some ablation experiments, I would have wished for even more experiments that provide insights into the method:\n     - Some experiments that directly evaluate how different the policies of the ensemble models are would provide interesting insights. For example, how often do the models disagree on the next actions (if argmax is used to select an action separately for each model).\n    - What is the impact of the weights for the two regularization terms (which are set to 0.5 and 0.5 in the experiments)? A parameter sweep that finds the sweet spot between too much and too little diversity would have been nice.\n    - What is the impact of the ensemble size on the performance?\n- The description of the proposed regularization terms and their theoretical motivation is difficult to understand (or lacking). I do not understand the Theil index regularization and I am skeptical that the parameter dissimilarity regularization meaningfully increases the difference between models. The experimental results do not fully convince me that they work as intended because it is unclear if the reported improvements are statistically significant. The authors should expand the description of the regularization terms, provide a more mathematically-grounded motivation, and more experiments.\n- The experimental setup is a bit unclear. More specifically, the generation of the training instances is not explained in detail and it is unclear from how many different distributions instances are sampled. Furthermore, it is unclear if all test instances are sampled from distribution not seen during training or if there is some overlap.\n- The runtime of the proposed approach is roughly two times slower than that of the POMO model. This makes a direct comparison of the cost difficult. What happens if the number of generated solutions for POMO is increased (e.g., doubled)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reviewing our paper with constructive and valuable feedback. Our detailed responses to the concerns/comments are as follows.\n\nQ1:  How many solutions do you generate per test instance? In the considered neural combinatorial setting there is no direct need to combine model outputs, instead one solution could be generated per ensemble model.\n\nA1: Yes, it is ideal for generating multiple solutions per instance. Our EL-DRL uses the augmentation mechanism of POMO [1] during the inference process. It produces multiple greedy trajectories by rotating each input instance to generate $8 \\times$ instances with different angles but the same optimal solution. For each generated instance, it starts the trajectory from each of the $N$ nodes. Thus, it samples $8 \\times N$ solutions in total for each input instance. For example, EL-DRL samples $8 \\times 100 = 800$ trajectories (solutions) for an instance with 100 nodes. The final solution is the best one among all the sampled trajectories. We will add more details about the augmentations into the revised version of our paper, and refer readers to POMO's augmentation mechanism [1].\n\nQ2: How often do the models disagree on the next actions (argmax)?\n\nA2: Thanks for your question. This experiment will be helpful for examining the effectiveness of our design for diversifying.\n\n| Problem    | TSP100 | CVRP100 |\n|------------|--------|---------|\n| Multi-POMO | 10.29% | 14.83%  |\n| EL-DRL     | 24.57% | 32.95%  |\n\nIn this table, we present the average probabilities of the models that disagree on the next actions. When simply assembling multiple POMOs, these sub-models tend to be similar and cannot produce diverse opinions. In contrast, our mechanisms for enhancing diversity successfully diversify the ensemble and enable sub-models to play their strength in different situations.\n\nQ3: What is the impact of the weights for the two regularization terms? \n\nA3: We swept the weights in grids (i.e. [0.05, 0,5, 1, 2]) for both terms. We find that large diversity (weights are 1 or 2) makes sub-policies favor diversity over higher reward, which hinders the overall ensemble performance. Small diversity (weights are small like 0.05) makes sub-policies produce similar decisions and loses the population benefit. Setting weights to 0.5 for the two regularization terms is a good balance between the objective quality and diversity. Fine-grained tuning for these hyperparameters may improve the results slightly, but it is not the focus of this paper.\n\n\nQ4: What is the impact of the ensemble size on the performance?\n\nA4: We presented an ablation study on the number of sub-policies in Section D (Figure 2) of the original Supplementary Material. The average gaps on CVRP100 with five distributions show that the average gap reduces from 2.048 to 1.960 as the number of sub-policies increases from 3 to 6. However, the gain is the biggest when this number increases from 3 to 4, and then adding more sub-policies only delivers a slight boost (only about 0.002-0.003 gap reduction). Therefore, to achieve a good trade-off between computational overhead and performance, we recommend using 4 sub-policies. However, in the future, we will investigate how to efficiently assemble more sub-policies.\n\nQ5: The authors should expand the description of the regularization terms, provide a more mathematically-grounded motivation, and more experiments.\n\nA5: We will provide more description for these terms. Theil index is a measure of inequality that is based on the concept of entropy in information theory. Entropy measures the amount of uncertainty or randomness in a system. The more distinction the distribution, the higher the Theil index. The Theil index can be interpreted as the average logarithmic distance between the incomes or wealth of individuals and the mean income or wealth of the society. In contrast to conventional approaches, we aim to maximize the ensemble diversity in EL-DRL, thus encouraging inequality within the system.\n\nFor the statistical significance (rliable [14]), the figure in the PDF file of the ‘Author Rebuttal’ demonstrates the significance of our approach with regularization terms over simply using multiple sub-models (Multi-POMO).\n\nQ6:  Explain generation of the training instances and how test instances are sampled.\n\nA6: To ensure the hardness and variety of training distributions and to guarantee that the training instances are not seen during testing, we generate 7.2 million training instances from mixed distributions. Data generation is done by first sampling a uniform instance and then **non-repetitively applying three random mutation operators** of TSPGEN to the same instance. So a single training instance is of **mixed distributions** and it does not belong to any single distributions in the testing.\n\nDuring the inference, we evaluated all methods on five unseen distributions. We test baselines on 10,000 instances in total, with each of the five testing distributions containing 2,000 instances. As stated in the response to Q1, we generate $8 \\times N$ solutions per test instance.\nIn short, the training instances do not fall into any type of testing distribution. All test instances are sampled from distribution not seen during training.\n\nQ7: What happens if the number of generated solutions for POMO is increased (e.g., doubled)?\n\nA7: We modify POMO in this experiment to use sampling for generating multiple solutions:\n\n| Model   | POMO  | POMO x2 | POMO x4 | EL-DRL |\n|---------|-------|---------|---------|--------|\n| CVRP100 | 2.63% | 2.57%   | 2.55%   | 2.12%  |\n\nWe report the average gaps over 5 testing distributions on CVRP100 in the table above. Doubling (POMO x2) or quadrupling (POMO x4) the generated solutions does not add enough diversity and thus it is hard to find diverse solutions with the same model that produces the same probabilities for actions.\n\n*We apologize for the character limit and plese refer to the  ‘author response’ for full reference list.*"}, {"review_id": "blwdcqQzQL", "reviewer": "Reviewer_L9hy", "summary": "In this paper, an ensemble-based deep reinforcement learning algorithm is proposed for vehicle routing problems. The goal of the method introduced in this work is to improve handling of distribution shifts at test time. The approach, EL-DRL, combines multiple ideas: i) and ensemble of sub-policies, ii) distinct losses for each sub-policy, iii) explicit regularization, and iv) distinct random sub-policy weight initialization. The main contribution of the work is a demonstration that sub-policy diversity improves out-of-distribution generalization for ensemble DRL on the VRP. The EL-DRL method is evaluated on a range of TSP and CVRP instances sampled from multiple distributions. It is compared against a significant number of advanced neural baselines and demonstrates improved performance.", "questions": "- How sensitive is the model to hyperparameters---e.g., the learning rate, $\\alpha_1$ and $\\alpha_2$?\n- How does EL-DRL fare against random and Multi-POMO baselines on the other benchmarks beyond CVRP100? \n\n---\n\nUpdate after rebuttal: The authors have made an effort to respond in a satisfactory way to my concerns and questions. Under the assumption that the new experimental results (especially demonstrating the statistical significance of the improvement over baselines) and promised revisions make it into the final version, I have increased my score.", "limitations": "The authors mention two key limitations: EL-DRL inherits limitations of the sub-model, and the increase in computation required to use ensembles of multiple models. They mention that POMO performs inferior on large instances, although I did not see where this is demonstrated in the experiments?", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "#### Originality\n\n- The main contribution of this paper appears to be a demonstration that diversity-enhanced Deep RL [1] can be applied to VRPs. I think this paper can be useful to those working on solving VRPs with Deep RL.\n\n#### Quality\n\n- The experiments are conducted on a wide range of benchmarks and out-of-distribution generalization is evaluation on a large number of synthetic and real VRP distributions.\n- The authors did a good job placing this work in the context of the relevant literature on deep reinforcement learning for VRPs.\n\n#### Clarity\n\n- The paper is written well and easy to follow.\n\n#### Significance\n\n- The proposed approach EL-DRL, appears to achieve state-of-the-art results on a large number of experiments. However, there are some concerns about the interpretation of the results, detailed below.\n\n#### References\n\n[1] Sheikh, Hassam, Mariano Phielipp, and Ladislau Boloni. \"Maximizing ensemble diversity in deep reinforcement learning.\" In International Conference on Learning Representations. 2021.", "weaknesses": "#### Originality\n\n- It is not clear to me that the significance of this work extends beyond the applied research area of Deep RL for VRPs.\n- I would assess the overall theoretical and technical contributions to the machine learning community to be incremental.\n\n#### Soundness\n\n- I struggled to interpret the quantitative results with any amount of confidence. While EL-DRL appears to \"win\" against the other methods (lots of bold), it was not clear to me whether the improvements due to the diversity-enhancing mechanisms are significant or marginal. \n- I would highly recommend using rliable (https://github.com/google-research/rliable) to calculate boostrapped confidence intervals for summary statistics across multiple (5+, ideally) random seeds and to show performance profiles. The Probability of Improvement metric $P( X > Y)$  implemented in `rliable` is a great way to compare these methods against each other. \n- On the majority of the tables in the results, POMO already beats the other baselines, including other advanced strategies for dealing with out-of-distribution generalization. This makes it difficult to interpret comparisons between EL-DRL and the other advanced strategies, as the strength of POMO alone appears to already explain the majority of the performance gains. \n- For many settings, EL-DRL only achieves a slight improvement over POMO. For example, in Table 5 Real-World TSPLib, POMO gets 5.16% gap and EL-DRL gets 4.79% (a length difference of only 7.44 vs. 7.39).\n- Moreover, I believe a random baseline and the Multi-POMO baseline should be included in each Table. A random baseline can help place into context what the difference in gap percentage means. Likewise, Multi-POMO will help provide context, as it has a similar number of parameters to EL-DRL. In Table 6, the Multi-POMO approach does improve over POMO (2.311% vs. 2.423%). \n\n#### A minor issue\n\n- L43-44: The authors write, \"Motivated by the recognition of the limited capability for a single model to learn from multiple distributions, [...], we propose...\" citing [1]. This statement is incorrect and should be revised. It is fairly clear by now that large pre-trained models are certainly capable of learning from multiple distributions. In support of this, the conclusions made in [1] are in fact that \"increasing pre-trained model size consistently improves performance on Waterbirds and MultiNLI. We advise practitioners to use larger pre-trained models when subgroup labels are unknown\".\n\n#### References\n\n[1] Pham, Alan, Eunice Chan, Vikranth Srivatsa, Dhruba Ghosh, Yaoqing Yang, Yaodong Yu, Ruiqi Zhong, Joseph E. Gonzalez, and Jacob Steinhardt. \"The effect of model size on worst-group generalization.\" arXiv preprint arXiv:2112.04094 (2021).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your insightful and helpful feedback on our paper. Please find below our detailed responses to the concerns/comments raised by you.\n\nQ1: Verify whether the improvements due to the diversity-enhancing mechanisms are significant or marginal.\n\nAs suggested, we used Google rliable to compute bootstrapped confidence intervals with 5 runs on TspLib with random seeds. The figure in the PDF file of the ‘Author Rebuttal’  shows the Probability of Improvement metric $P(Y \\gt EL-DRL)$, where Y represents the baselines (including Multi-POMO). Since we aim for smaller values of tour length (higher probability for $Y \\gt EL-DRL$), this metric demonstrates the significance of our EL-DRL in delivering better solutions consistently.\n\nQ2: On the majority of the tables in the results, POMO already beats the other baselines, as the strength of POMO alone appears to already explain the majority of the performance gains.\n\nPOMO is a state-of-the-art neural solver which can serve as a strong baseline.  There are many works on the generalization of VRPs in the literature that use POMO [1] as their basic neural solver, which adds additional modules on top of POMO [6, 8, 13] to facilitate their generalization. Such generalization study is a trend in the research community, with significant value and importance. For example, DROP [6] employs distributional robust optimization to improve the generalization of POMO. AMDKD [8] distills the knowledge to train a POMO model from various pre-trained teacher models. To verify if employing POMO is a guarantee for generalization performance, we compare our model with POMO, DROP and AMDKD in our paper. In Table 5, even though DROP and AMDKD are specially designed for different distributions and built on top of POMO, they do not perform better than POMO or EL-DRL. DROP and AMDKD may excel on certain distributions, but they fall behind the original POMO on some others. This suggests that designing a suitable learning framework for generalizable models is more important than only building on top of POMO. Baselines with POMO usually outperform those without it, but EL-DRL beats all baselines including POMO itself in our experiment. For the analysis of the improvement over POMO, please see the answer of Q3.\n\n\nQ3: For many settings, EL-DRL only achieves a slight improvement over POMO. For example, in Table 5 Real-World TSPLib, POMO gets 5.16% gap and EL-DRL gets 4.79% (a length difference of only 7.44 vs. 7.39).\n\nFirstly, the experiment on TspLib is more difficult than others since we use models trained on $N=100$ and test on $N = 50$ to $N = 250$. In other words, we need to generalize our method for both distributions and scales at the same time.  In our new experiment that trains the model on $N = 50$ and test on $N = 50$ to $N = 500$, EL-DRL surpasses other baselines by a larger margin:\n| Dataset  | Metric    | Opt.  | AM     | POMO  | MDAM   | HAC    | DROP  | AMDKD | EL-DRL |\n|----------|-----------|-------|--------|-------|--------|--------|-------|-------|--------|\n| TSPLib   | Avg. Len. | 7.64  | 8.96   | 8.23  | 8.45   | 9.04   | 8.34  | 8.32  | 8.11   |\n| N~50-500 | AVG. Gap  | 0.00% | 17.28% | 7.72% | 10.60% | 18.32% | 9.16% | 8.90% | 6.15%  |\n\nWe can observe that EL-DRL reduces the gap of POMO by 1.57%.\n\nSecondly, the theory of ‘No Free Lunch’ states that it is very hard to achieve an optimal solution when the testing distribution changes a lot, and nearly impossible to get a very low gap value for models that are assumed to be trained and tested in i.i.d. data. The lower the gaps, the harder it is for new methods to improve. For example, when the gap is large (AM and HAC), newer methods (POMO) can reduce the absolute gap value more easily. But when the gap is close to 5%, it is harder for new methods to achieve a much smaller gap. This phenomenon is common in machine learning research. Hence, our method's improvement to POMO is not marginal.\n\n\nQ4: Moreover, I believe a random baseline and the Multi-POMO baseline should be included in each Table. Likewise, Multi-POMO will help provide context, as it has a similar number of parameters to EL-DRL. \n\nThanks for your advice. We will follow your advice that add a random and the Multi-POMO baseline to each Table. It will be more helpful for understanding how our design outperforms simply employing multiple submodels.\n\n\nQ5: A minor issue L43-44: It is fairly clear by now that large pre-trained models are certainly capable of learning from multiple distributions. \n\nThank you for pointing this out. We agree that enlarging a single model may improve its performance and we will revise these sentences accordingly. \nHowever, only enlarging a single model does not guarantee meaningful improvement. For independent researchers, using a large amount of computational resources to build a huge model is impractical in most cases. Our goal is to improve the generalization performance with similar magnitude of computational resources. Furthermore, many researchers including the creator of PyTorch posted tweets to support the idea that GPT-4 may be a kind of ensemble learning of different smaller models. In other words, most famous artificial general intelligence models may also use the idea of ensembling to enhance their generalization ability on different tasks instead of only enlarging a single model.\n\n*We apologize for the character limit and plese refer to the  ‘author response’ for full reference list.*\n"}, {"review_id": "SuE2u2NaBa", "reviewer": "Reviewer_WvQ5", "summary": "This paper investigated the classical vehicle routing problems and proposed an ensemble-based deep reinforcement learning algorithm. Moreover, two regularization terms (Theil index and L2-dist) were designed to improve the generalization ability of learned policies. The motivation is convincing and the proposed methodology is easy to understand. ", "questions": "Q1: Can the authors explain the relevance between their work and \"MAXIMIZING ENSEMBLE DIVERSITY IN DEEP REINFORCEMENT LEARNING\" published at ICLR2022?\n\nQ2: Is there any comparison between EL-DRL and traditional algorithms like genetic algorithms?\n\nQ3: More detailed literature review of DRL-based methods for VRP is needed.\n\n[1] Reinforcement Learning with Augmented Data\n[2] State Entropy Maximization with Random Encoders for Efficient Exploration", "limitations": "Please see the weakness and question section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1、The classical vehicle routing problem is important to explore and the proposed ensemble-based deep reinforcement learning algorithm has been proven to handle such a critical problem;\n2、The motivation is convincing and the paper writing is easy to understand. ", "weaknesses": "The main concern of mine mainly focuses on the limited discussion and comparison between the existing/previous works and this work:\n(1): Since the authors break down the optimization problem into sub-policies learning, why not just use multi-agent reinforcement learning to solve the problem? I didn't quite understand the necessity of ensemble learning. What is the relationship between ensemble learning and multi-agent policy in RL?\n\n(2): The EL-DRL is built on the top of REINFORCE algorithm that is very old. Can EL-DRL use better baselines like PPO or PPG? Or this setting is indispensable?\n\n(3): Some existing work in RL proposes to use data augmentation (e.g., observation augmentation and intrinsic reward) to improve generalization ability, which is very efficient and cheap [1][2]. Can the authors compare EL-DRL with these approaches?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and support. We also appreciate that the reviewer acknowledges the quality and contribution of the paper.\n\nQ1: Why not just use multi-agent reinforcement learning to solve the problem? What is the relationship between ensemble learning and multi-agent policy in RL?\n\nA1: We can treat our ensemble learning framework as a type of multi-agent system. In RL terms, each sub-policy is an agent and they collaborate to decide the next city to visit. Unlike some other multi-agent RL research, our ensemble mechanism lets our agents work on the same goal synchronously. In many multi-agent systems, agents work asynchronously and face different environments. Sometimes, they may compete with each other. But in our routing problem, the problem is a simple sequence-generation process, where all agents have the same goal: choose the optimal next city until the whole sequence is generated. For routing problems, a complex system that puts each agent in different environments and phases is unnecessary. It may waste resources to maintain the population and not ensure that they seek global rather than local optima. In summary, we aim to devise a simple and efficient collaborative mechanism for agents. Our experiments show that our mechanism outperforms other methods without extra multi-agent techniques.\n\n\nQ2: Can EL-DRL use better baselines like PPO or PPG?\n\nA2: Earlier research [4, 5] uses an extra critic network to predict the baseline in REINFORCE algorithm, also known as A2C but requires extra resources to build another neural network. Plus, the prediction can be unreliable when facing unseen instances. Recent research also uses PPO to train the routing model [3]. But even with more complex RL algorithms, the improvement over [2] that uses a naive REINFORCE algorithm is marginal. Therefore, using a more complex RL algorithm does not guarantee significant improvement. A better practice is to tailor learning algorithms for routing problems. The REINFORCE algorithm we use in this paper is not naive. As stated in Policy Optimization with Multiple Optima (POMO) [1], the agents generate and collect $N$ trajectories that start from $N$ different nodes. The POMO baseline is a shared baseline that averages the reward of $N$ collected trajectories, which reduces variance in policy gradients compared to the greedy-rollout baseline [2]. This baseline can be computed efficiently compared to other baselines. Therefore, using REINFORCE with POMO baseline has been a good practice in DRL-based methods for VRP [6, 7, 8], rather than others like A2C, PPO or PPG.\n\nQ3: Some existing work in RL proposes to use data augmentation. Can the authors compare EL-DRL with these approaches?\n\nA3: We agree that it is very efficient and cheap to improve generalization ability, but the augmentation for images of these works cannot be directly applied to VRPs. Actually, we have already used augmentation during training and inference. As we said above, our backend model POMO starts the trajectory from each node during training. During inference, POMO produces multiple greedy trajectories by rotating each input instance and starting from each node. The final solution is the best one among all sampled trajectories. We will add more details about the augmentations and refer readers to POMO's augmentation mechanism [1].\n\nQ4: Can the authors explain the relevance between their work and \"MAXIMIZING ENSEMBLE DIVERSITY IN DEEP REINFORCEMENT LEARNING\" published at ICLR2022?\n\nA4: Their work (MED) trains models on toy simulation environments and six Atari games with Q-learning algorithms. As we stated in our paper, directly using deep Q-learning to play games with limited actions does not suit our problem, since estimating Q-values for VRPs with hundreds of actions (i.e., the next node to visit) is hard, and these methods perform worse than policy gradient. In contrast, we propose a new Policy Gradient framework that solves routing problems effectively. Both MED and ours use regulation terms from previous works [9, 10] and show their effectiveness in experiments, but their work only shows that regulation terms can improve diversity in ensembles. MED is not for more practical and complex problems like ours. In the Ablation Studies (Table 6), using a single term does not improve much. Our method improves from the careful design of the learning framework with mostly orthogonal components, not from enumerating each regularization term and testing it as MDE did.\n\nQ5: Is there any comparison between EL-DRL and traditional algorithms like genetic algorithms?\n\nA5: Some works compare genetic algorithms (GA) with DRL-based methods directly. However, the naive GA is not specifically tailored for VRPs and its search efficiency drops sharply as the problem size grows. As shown in Table 3 of [11], GA performs worse even with much longer runtime than DRL-based methods. Thus, in the literature, the common practice is to compare with strong traditional algorithms that are customized for VRPs. For example, since optimal solutions for CVRP are hard to obtain in a reasonable time, we use a strong meta-heuristic: Hybrid Genetic Search (HGS) as the baseline in our experiments (Table 3, Table 4 and Table 5). As a traditional algorithm, HGS also uses ideas from GA, but with more adaptations for VRPs. In summary, most existing DRL-based algorithms cannot outperform the strongest traditional algorithms. The advantage of DRL-based algorithms is the inference speed which can produce solutions in seconds. Our work aims to narrow the gap to stronger baselines like HGS than other DRL-based methods.\n\nQ6: More detailed literature review of DRL-based methods for VRP is needed.\n\nA6: Thank you for your suggestion. We will provide more details on the literature review of DRL-based methods for VRP in our revision for clarity.\n\n*We apologize for the character limit and plese refer to the  ‘author response’ for full reference list.*\n"}, {"review_id": "yAutaOiFCH", "reviewer": "Reviewer_eih2", "summary": "This paper suggests a novel method to mitigate the distributional shift of combinatorial optimization problems. The idea is to bootstrap and aggregate multiple diverse policies which are similar to a classical ensemble method called bagging. The idea is simple and effective having promising empirical performances. I clearly vote to accept this paper. \n", "questions": "1.  I'm curious about the robustness of this algorithm on large-scale problems. \n\n2.  There were several pieces of literature to mitigate distributional shift; for example:\n- Sym-NCO (NeurIPS'22) [1]: leveraged symmetricity for better generalization\n- ROCO (ICLR'23) [2]: robustness training of neural combinatorial optimization solver \n- Meta-SAGE (ICML'23) [3]: leveraged meta-learning for better adaptation\nIn my humble opinion, this paper should include the recent rapid progress of related research more carefully. \n\n3. Can this method be applied to non-routing problems?\n\n[1] Kim, Minsu, Junyoung Park, and Jinkyoo Park. \"Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization.\" Advances in Neural Information Processing Systems.\n\n[2] Lu, Han, et al. \"ROCO: A General Framework for Evaluating Robustness of Combinatorial Optimization Solvers on Graphs.\" The Eleventh International Conference on Learning Representations. 2023.\n\n[3] Son, Jiwoo, et al. \"Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization.\" arXiv preprint arXiv:2306.02688 (2023).\n", "limitations": "They already stated their limitation regarding scalability. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "They targeted one of the significant research topics of combinatorial optimization. The idea is simple and straightforward. The empirical results seem to be effective. ", "weaknesses": "One of the other major topics of the distributional shift of combinatorial optimization is scale shift (e.g., trained on $N=50$ and tested on $N=500). This paper did not discuss those topics. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reviewing our paper with positive feedback. We appreciate that the reviewer acknowledges the motivation and significance of our work. Our responses to the comments are as follows.\n\nQ1: One of the other major topics of the distributional shift of combinatorial optimization is scale shift (e.g., trained on $N=50$  and tested on $N=500$). This paper did not discuss those topics. I'm curious about the robustness of this algorithm on large-scale problems.\n\nA1: In this work, we focus on the topic of distribution shift. In our experiments on TSPLib (Table 5), we reused our trained $N=100$ models and tested on instances with problem sizes ranging from $N=50$ to $N=300$. Following your suggestion, we also reuse $N=50$ models and test TSPLib instances with problem sizes ranging from $N=50$ to $N=500$. The result is as below (We also include Sym-NCO):\n| Dataset  | Metric    | Opt.  | AM     | POMO  | MDAM   | HAC    | DROP  | AMDKD | SYM-NCO | EL-DRL |\n|----------|-----------|-------|--------|-------|--------|--------|-------|-------|---------|--------|\n| TSPLib   | Avg. Len. | 7.64  | 8.96   | 8.23  | 8.45   | 9.04   | 8.34  | 8.32  | 8.20    | 8.11   |\n| N~50-500 | AVG. Gap  | 0.00% | 17.28% | 7.72% | 10.60% | 18.32% | 9.16% | 8.90% | 7.33%   | 6.15%  |\n\nAccording to the experiment, our method surpasses other baselines by a larger margin including Sym-NCO regarding robustness on larger scale problems.\n\nQ2: There were several pieces of literature to mitigate distributional shift.\n\nA2: Thank you for these valuable works. For Sym-NCO, the original paper tested on TspLib instances with up to 250 nodes. We showed its results in the above table and our method outperforms this generalization-specific method. ROCO and Meta-SAGE are the most recent works released close to our submission date to NeurIPS 2023. For ROCO, the attacker only modifies the original by ‘choose an edge and half its value’, which does not create distribution shifts as in our scenarios. Meta-SAGE is ‘for improving the scalability of deep reinforcement learning models’ and has special components for larger-scale problems. Although it may not be fair to compare them directly, we are interested in their results on our cross-distribution instances after they share the source code. Also, we think our method can incorporate these scaling techniques when needed for large-scale problems. Since research on generalization for both distribution and scale is scarce, we agree that it is a good future research area. We will add the discussion on these works to our revision.\n\nQ3: Can this method be applied to non-routing problems?\n\nA3: Yes. As you summarized, our work is to propose a new framework for making decisions by multiple diverse policies for combinatorial problems. This idea is also applicable to other problems in which the testing distribution(pattern) is different from train data. For example, since our deep model backend is Attention Model [1, 2], we can reuse the neural net developed for TSP and apply it to solve 0-1 Knapsack Problem (KP) with minor changes like selected items (i.e. visited nodes) as well as items that no longer fit inside the knapsack are masked. Also,  the training reward should be changed to the total value of selected items.\n\n*We apologize for the character limit and plese refer to the  ‘author response’ for full reference list.*\n"}]

Author rebuttal:
We appreciate all reviewers for their thoughtful reviews and constructive comments. In this general response, we provide the reference list, as well as a figure in the PDF file to support our response. Our detailed point-to-point responses can be found below. 

## STATISTICALLY SIGNIFICANT

We used Google rliable Library [14] to compute bootstrapped confidence intervals with 5 runs on TspLib with random seeds. The figure in the PDF file of the ‘Author Rebuttal’ shows the Probability of Improvement metric $P(Y \gt EL-DRL)$, where Y represents the baselines (including Multi-POMO). Since we aim for smaller values of tour length (higher probability for $Y \gt EL-DRL$), this metric demonstrates the significance of our EL-DRL in delivering better solutions consistently.

## REFERENCE

[1] Kwon, Yeong-Dae, et al. "Pomo: Policy optimization with multiple optima for reinforcement learning." Advances in Neural Information Processing Systems 33 (2020): 21188-21198.

[2] Kool, Wouter, Herke van Hoof, and Max Welling. "Attention, Learn to Solve Routing Problems!." International Conference on Learning Representations. 2018.

[3] Wan, Ching Pui, Tung Li, and Jason Min Wang. "RLOR: A Flexible Framework of Deep Reinforcement Learning for Operation Research." arXiv preprint arXiv:2303.13117 (2023).

[4] Nazari, Mohammadreza, et al. "Reinforcement learning for solving the vehicle routing problem." Advances in neural information processing systems 31 (2018).

[5] Bello, Irwan, et al. "Neural Combinatorial Optimization with Reinforcement Learning." International Conference on Learning Representations. 2017.

[6] Jiang, Yuan, et al. "Learning to solve routing problems via distributionally robust optimization." [7] Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 9. 2022.

[7] Hottung, André, Yeong-Dae Kwon, and Kevin Tierney. "Efficient Active Search for Combinatorial Optimization Problems." International Conference on Learning Representations.

[8] Bi, Jieyi, et al. "Learning generalizable models for vehicle routing problems via knowledge distillation." Advances in Neural Information Processing Systems 35 (2022): 31226-31238.

[9] J Johnston. H. theil. economics and information theory, 1969.

[10] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine learning, 3(1):1–122, 2011

[11] Zhang, Zixian, Geqi Qi, and Wei Guan. "Coordinated multi‐agent hierarchical deep reinforcement learning to solve multi‐trip vehicle routing problems with soft time windows." IET Intelligent Transport Systems (2023).

[12] Vidal, Thibaut. "Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood." Computers & Operations Research 140 (2022): 105643.

[13] Hottung, André, Yeong-Dae Kwon, and Kevin Tierney. "Efficient Active Search for Combinatorial Optimization Problems." International Conference on Learning Representations, 2022.

[14] Agarwal, Rishabh, et al. "Deep reinforcement learning at the edge of the statistical precipice." Advances in neural information processing systems 34 (2021): 29304-29320.



Meta-review: This submission received four reviews and all reviewer recommend acceptance, most with low score but consistent. Two reviewers increased their scores (to 5) after the rebuttal. This submission was then discussed in depth between the area and senior area chairs. 

All reviewers find the paper well written and the experiments sufficient. Some extra experiments that study other distribution shift have been suggested and are included in the rebuttal. The main weaknesses that the reviewers point out are similarity to [40] and the specialised topic. However the authors convincingly answered to this in their rebuttal and are expected to revise their document accordingly. 

In summary the paper presents a contribution to a hard and relevant problem and no reviewer recommends rejection. We recommend acceptance of the submission.
Decision: Accept (poster)