Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation
Authors: Jieyi Bi
Yining Ma
Jiahai Wang
Zhiguang Cao
Jinbiao Chen
Yuan Sun
Yeow Meng Chee
Venue: NeurIPS 2022 Accept (2022)
Keywords: learning to optimize
vehicle routing problem
knowledge distillation
generalization
combinatorial optimization

Abstract: Recent neural methods for vehicle routing problems always train and test the deep models on the same instance distribution (i.e., uniform). To tackle the consequent cross-distribution generalization concerns, we bring the knowledge distillation to this field and propose an Adaptive Multi-Distribution Knowledge Distillation (AMDKD) scheme for learning more generalizable deep models. Particularly, our AMDKD leverages various knowledge from multiple teachers trained on exemplar distributions to yield a light-weight yet generalist student model. Meanwhile, we equip AMDKD with an adaptive strategy that allows the student to concentrate on difficult distributions, so as to absorb hard-to-master knowledge more effectively. Extensive experimental results show that, compared with the baseline neural methods, our AMDKD is able to achieve competitive results on both unseen in-distribution and out-of-distribution instances, which are either randomly synthesized or adopted from benchmark datasets (i.e., TSPLIB and CVRPLIB). Notably, our AMDKD is generic, and consumes less computational resources for inference.

Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation
Jieyi Bil.t, Yining Ma Jiahai Wang Zhiguang Cao ,Jinbiao Chen',
Yuan Sun and Yeow Meng Chee² School of Computer Science and Engineering, Sun Yat-sen University National University of Singapore
Singapore Institute of Manufacturing Technology, A*STAR
Univeesstty of Melbourne
bi bi.jy60mai12.. sysu. edu. cn, yiningma@u. nus edu
wangj banggiahh@ail.ssyaa sysu. edu. cn, zhiguangcao@outlook com chenjb69@mail2. sysu. edu. en, yuan. sun@unimelb edu au, ymcheeθnus. edu.sg
Abstract
Recent neural methods for vehicle routing problems always train and test the deep models on the same instance distribution (i.e., uniform). To tackle the consequent cross-distribution generalization concerns, we bring the knowledge distillation to this field and propose an Adaptive Dillii-Dittribttion Knowledge Distillation (AMDKD) scheme for learning AMDKD leverages various knowledge from multiple teachers trained on exemplar distributions to yield light-weight yet generalist student model. Mcanwhile, we equip AMDKD with an adaptive strategy that allows the student to concen- trate difficult distributions, effectively. Extensive experimental results show that, compared with the baseline neural methods, our AMDKD is able to achieve competitive results on both unseen in-distribution and out- -iitr---istiittionn instances, which are either randomly synthe- sized adopted from benchmark datasets (i.e.. TSPLIB and CVRPLIB). Notably, our AMDKD is generic, and consumes less computational resources for inference.
generalizable deep models. Particularly,
to absorb hard-to-maser knowledge more
Introduction
The Vehicle Routing Problem (VRP) is a class of NP-hard combinatorial optimization problems with wide variety of practical applications, such freight delivery [1], last-mile logistics [2] and ride- hailing [3]. For decades, the problem has been studied intensively in computer science and operations research, with numerous exact and (approximate) heuristic algorithms proposed [4-7]. Although the heuristic algorithms are usually preferred in practice given their relatively higher computational efficiency, they heavily rely hand-crafted rules and domain knowledge, which may still leave room for improvement. As a promising alternative, deep (reinforcement) learning could be used to automatically learn heuristic (or policy) for VRPs in end-to-end fashion, which has aroused widespread attention in recent years [8-16]. Compared to the traditional ones, the learned heuristics based on deep models could further reduce computational costs while ensuring desirable solutions.
However, existing deep models suffer from inferior generalization with respect to distributions of node coordinates. To be concrete, they often train and test neural networks instances of the same
Equally contributed.
Jiahai Wang and Zhiguang Cao are the corresponding authors.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

distribution, mostly the uniform distribution, where deep models are able to achieve competitive results more efficiently than the traditional heuristics (e.g.. [12]). Nevertheless, when the learned policy is applied to infer the out-of-distribution (OoD) instances, the solution quality is usually low. This cross-distribution generalization issue inevitably hinders the applications of deep models, especially because the real-world VRP instances may follow various and even unknown distributions.
number of preliminary attempts have been made to tackle this generalization issue for VRPs, which mainly leverage (automatic) data augmentation [17-20] and distributionally robust optimization [21], respectively. However, they are not optimal in our view, as the former always starts with specified single distribution which may limit the resulted performance, while the latter needs to manually define major and minor instances. Different from them, in this paper, we aim to enhance the cross- distribution generalization by transferring various policies learned from respective distributions into one, where we exploit knowledge distillation to learn more generalizable models for VRPs.
Specifically, we propose a generic Adaptive Multi- Dulti-Distribution Knowledge Distillation (AMDKD) scheme for training a light-weight model with favorable coss-distribution generalization performance. To impart broad yet specialized knowledge, we exploit multiple teacher models that are (pre-) -trineed on respective exemplar distributions. Our AMDKD then leverages those teachers to train shared student model in turns, inspired by the learning paradigm of human-beings. Meanwhile, we also equip the AMDKD with an adaptive strategy to track the real-time learning performance of the student model on every exemplar distribution, which allows the student to concentrate on absorbing those hard-to- to-tetter knowledge, so as to strengthen the effectiveness of the learning.
Accordingly, our contributions are summarized as follows: (1) We bring the knowledge distillation to the field of neural combinatorial optimization and aim at improving the cross pross-distribution gen- eralization for solving VRPs, which offers a promising perspective to transfer knowledge/policy learned from multiple models into one: (2) We propose the Adaptive Multi-Distribution Knowledge Distillation (AMDKD) scheme, where we distill diverse knowledge from multiple teachers trained on exemplar distributions to yield light-weight yet generalist student model, and also present an adaptive strategy for the student to better assimilate hard-to til--tt-mmteer knowledge from difficult distributions; (3) We apply our generic AMDKD to two representative deep models, i.e., AM [10] and POMO [12]. respectively. Results show that, while consuming less computational resources for inference, our AMDKD performs favorably against the backbone models as well as other existing gen- eralization methods for deep models, especially on the benchmark dataset CVRPLIB [22]. By further coupling with the efficient active search (EAS) [23], our AMDKD achieves the new state-of-thh-aat performance. We also conduct series of analysis to verify our designs.
2 Related work
Recently, neural methods based on deep models for VRPs have aroused widespread interest. These methods are categorized as neural construction models and neural improvement models in general.
Neural construction models. They exploit deep (reinforcement) learning to autoregressively con- struct the solution in an end-to-end fashion. Vinyals et al. [8] introduced the first RNN-based Pointer Network (Ptr-Net) to solve TSP based on supervised learning. Bello et al. [24] then exploited rein- forcement learning to train the Ptr-Net for TSP. In [9], the Ptr-Net was then extended to solve CVRP. Different from the above RNN-based methods, Kool al. [10] proposed the well-known Attention Model (AM) based on the Transformer architecture [25]. Subsequently, many studies extended AM for routing problems, such as [12, 13, 26-30]. As representative, Kwon et al. [12] proposed the POMO (Policy Optimization with Multiple Optima) and achieved significantly better performance. In a recent work, POMO was adapted to an efficient active search (EAS) framework to further boost the performance during inference [23]. Besides, graph neural networks (GNNs) are also utilized to effectively learn and identify the graph-structured features of the problem instance [1, 11, 31-33J.
Neural improvement models. They iteratively improve the initial solution by exploiting deep (reinforcement) learning to assist or control the local search. Chen and Tian [34] proposed the NeuRewriter that learned a policy to partially rewrite the current solution. Hottung and Tiemny [35, 36] leveraged deep networks to learn to perform the large neighborhood search. Wu et al. [37] and Costa et al. [38] proposed to control the 2-opt operation [6]. Ma et al. [14] further upgraded the deep model of Wu et al. [37] to dual-aspect collaborative Transformer (DACT) with much superior performance. The DACT method was further enhanced in [39] in order to learn a ruin-and and-repair

---

operation for pickup and delivery problems. Generally, improvement methods consume much longer inference time than construction ones to achieve higher solution quality.
cross-distribution generalization. The above neural methods for VRPs often train and test the deep models on the same instance distribution. Although the state-of-the-art deep models perform close to or even surpass the strong traditional heuristics, they are incapable to generalize the learned policy to other distributions, which seriously impairs their practical applications. Therefore, the cross-distribution issue has gradually gained more attention [17-21]. Among the early attempts in this line of research, Xin et al. [18] proposed generative adversarial network (GAN) based framework to generate hard-to-solve instances for training the model. Wang et al. [20] leveraged the game theory and proposed the Policy Space Response Oracle (PSRO) framework simultaneously learn a trainable solver and an instance generator. Zhang et al. [17] designed hardness bardnesss-ddaptive TSP instance generator and adopted curriculum learning to train the model. These methods primarily emphasized on data augmentation or are limited to TSP. Different from them, Jiang et al. [21] adopted CNN to acquire distribution-awann features and exploited group DRO (Distributionally Robust Optimization) to enhance model robustness against distributions. However, this method needs to manually define major and minor instances. Note that we acknowledge that the generalization to different problem scales (or sizes) is also important, which we leave as the future research direction.
3
Preliminaries and notations
We first present the formulation of the studied VRPs and classic distributions. Then we introduce how deep models are used solve them, followed by the basic rationale of knowledge distillation.
3.1 VRPs and their distributions
We define VRPs over a complete graph G = ( E}, where o E V represents the (customer) node, e(e; v2) E E represents the edge between two nodes, and Cle(t,, v5)] represents the cost (we use length in this paper) of the edge. By referring tour T (a.k.a. solution) to a permutation of nodes in V. the objective is usually to find the optimal tour r" with the least total cost(lengthh over finite search space containing all possible tours, which could be formulated as Eq. (1) in general,
arg min L(7'lg) arg min EES
Σ e(H.,55)T
C Cle(u,, uy)l
r'ES
For different VRP variants, such objective may be subject to different problem-specine constraints [40, 41], where multiple sub-tours may exist in a valid tour r. Following the recent literature [10, 12, 23]. we focus on two representative VRPs, i.e., TSP and CVRP, respectively. A feasible tour for TSP considers a vehicle visiting each node in once and only once. As an extension from a vehicle to a fleet, CVRP considers an extra depot node to and capacity limit Q for any given vehicle, where each customer node ei = I..... n.) is associated with a demand request 6,. A feasible tour for CVRP consists of multiple sub-tours, each of which represents vehicle in the fleet departing from the depot, serving a subset of nodes, and finally returning to the depot. The total demand of each sub-tour must not exceed the capacity Q, and all nodes except for the depot must be visited once and only once.
In Figure 1, we visualize a number of VRP instances following various distributions from the literature [10, 21, 43], including the TSPLIB [42] and CVRPLIB [22] benchmark datasets. As can be observed, the node coordinates of a VRP instance may follow complicated and even unknown distribution, which considerably intensifies the hardness for solving. While the recent neural methods report superior performance to the traditional heuristics on some fixed distributions, it is unfortunate that they are more sensitive to distribution shift. It is thus of great importance and interest to develop powerful deep models that can simultancously handle as many diverse distributions as possible.
3.2 Tour construction by deep models
We focus on neural construction methods for VRPs, which usually exploit deep neural networks to sequentially construct the tour. light of this, the solving procedure is mostly modelled as a Markov Decision Process (MDP), where the Transformer styled [10] architectures following the encoder-decoder structure are often adopted as the policy network. Typically, the encoders project the nodes of the instance into node embeddings for feature extraction. Afterwards, the decoder builds the
3

---

(a)
(b)
(c)
(d)
(c)
(h)
(i)
i (k)
(m)
(n)
Figure 1: VRP instances following various distributions from the literature: (a) gr (b) lin 105, (c) att532,, (d) pr136, (e) X-n125-k30, (f) bierl 27, (g) Tai 150, (h) Uniform, (i) Cluster, (i) Mixed, (k)
Expansion, (I) Implosion, (m) Explosion, (n) Grid, where instances (a)-(g) are from TSPLIB [42] and CVRPLIB [22]. this paper, we consider instances following distributions (h)-()) for training and other unseen distributions (k)-(n), as well as unseen benchmark datasets for testing.
tour T based on learned node embeddings and the partial tour d1:--1 constructed previously. At time step I. the MDP, the decoder picks an unvisited node as the action a, where invalid ones are masked for feasibility. The procedure is repeated until the whole tour is completed, which is factorized as,
(o(
II po (1:1-1, 9), 1=1
where pa is the policy parameterized by 0, and denotes the final time step in MDP. For TSP, & - n for CVRP, 2 n since the depot can be visited more than once'. The total reward defined as negative of the tour length, i.e., - -(r(g) This is essentially consistent with the objective in Eq. (1).
3.3 Knowledge distillation
Knowledge distillation [44] is a kind of teacher-student training paradigm that aims transferring knowledge from a (group of) complex teacher model(s) 8T, to succinct student model Ø5, The recent research findings reveal that knowledge distillation is not only able to effectively learn lighter student network from larger teacher network(s) [45, 46), but also has potential to improve the generalization [47, 48] even over its teacher(s) [49-51]. Typically, the teacher models are pre-trained, and the student model compares the output of teacher model(s) with its own and considers it as supervisory signal. Formally, the student network is trained with the goal of minimizing a weighted combination of the distillation loss CKD and the original task loss Trakk as follows,
[ = aaCakkk + (1 LKD,
where a E [0, 1]. The LLD with respect to one or more teachers 2N is generally formulated as,
Nr
LKD = -ΣΣ
1
Φ Pot (o)
(4)
NT
TE
where x is the training data from X' and Φ(.) measures the statistical distance between the teacher and the student, such as the Kullback-Leibler divergence KI- (p = E; Per (log log
Methodology
Consider what happens in classroom when students study multiple modules. Typically, they (students) learn only one module (exemplar distribution) at time from professional teacher, and then go the next one until all modules are mastered. When students do poorly quiz after class (validation dataset), they will be required to study that module more frequently in order to
'The sub-tours for CVRP are constructed sequentially, At each step, the agent selects an unvisited node whose demand is smaller than the remaining capacity returns the depot for full replenishment.

---

Generatic Indomnos E
Nortrae (0)
J (pm-tralned)
Tencher Betwork
esising
Texter
Impet Xhurper
Updas
Cwy
Satipl Ditiiutiond
Teacher artion dbarttuttinn
Adapiive Probehiity
Uniifrm
Valldadion ditiavel
Truising
Student network (trainable)
By
Seftnow
Tour 2
Cluster
Unifuerm
Cip on
Pool [R)
Sumple
6
Clusser
Cup
Tour
Exemplar Distributions
Mised
Ex
Misoe
Dap on
Mixell
distribation
Ulscce
Teacher Pre-trainiin
Student Training
Inference
Framework of our AMDKD scheme. From left to right: teacher pre-training, student training and inference. The Uniform is selected as the current exemplar distribution for an example.
Figure 2:
become generalists. Motivated by this, we propose the Adaptive Multi- cullii-Distribution Knowledge Distillation (AMDKD) scheme that could efficiently learn more generalizable models for VRPs.
Previously, deep models were trained on a single distribution, e.g., the Uniform in [12-14]. More recently, attempts have been made to expand the training data by augmenting atypical (minor) [21] or hard instances [17, 18]. Differently, AMDKD allows expert knowledge for tackling distinct distributions be transferred into single yet generalist model via distillation. With light network and high inference speed, the resulted model is supposed to perform favorably against existing methods. Moreover, AMDKD is generic, and could be used to boost various deep models for VRPs.
4.1 Overall structure and teacher (pre)-training
The overview framework of our AMDKD is illustrated in Figure 2. Given an existing deep model (e.g.. AM [10]), AMDKD first performs teacher training (or directly use pre-trained ones) to obtain teacher model for each distribution listed a set exemplar ones. Then each knowledge transfer epoch, AMDKD picks specific distribution d and its teacher 0, to train student network. To facilitate effective learning, the likelihood of picking each distribution is adaptively updated according to the current performance of the student distillation, allowing the student network g to sample RL trajectories (i.c., tours {Tys }) for training, and calculates the two losses (i.e., KD loss and Task loss) for update.
validation dataset. Finally, AMDKD performs on-policy
We consider Uniform, Cluster, and Mixed (mixture of uniform and cluster) as exemplar distributions to train teacher networks in this paper. Consequently, set of well-trained teachers with parameters 0t = [OO OE, (M) are attained for each distribution. Despite only limited distributions are exploited throughout training, the learned student network is expected to absorb generic and robust knowledge from teachers that may effectively generalize to unseen distributions such as Expansion, Implosion, Explosion, and Grid (visualization in Figure 1). Our motivation here is that each teacher only needs to master a specific distribution, and by working together via our distilling scheme, they can educate generalist student. Note that the exemplar distributions used here could also be substituted with others (see Section 5.3). Furthermore, since our designed distillation scheme is model-agnostic, the teacher network follow most of existing architectures. In this paper, we assess scheme by applying to two representative construction methods, i.e., AM [10] and POMO [12), respectively.
4.2 Adaptive multi-distribution student training
Given the well-trained teachers on exemplar distributions, our AMDKD student selects one teacher and one distribution in each knowledge transfer epoch and gradually learns to make appropriate decisions. Note that there is another line of works that argue for the simultaneous use of multiple teachers the distillation process [52, 53]. In their strategy, all teachers are engaged to provide weighted loss to train the student as aforementioned in Section 3.3. However, such design may require teachers to be trained on a homogeneous task primarily with supervised learning, which does not suit our heterogeneous distributions with reinforcement learning (see Appendix C for results).
5

---

Algorithm 1 Adaptive Multi-Distriutionn Knowledge Distillation (AMDKD)
Input: A backbone model M (e.g., AM), exemplar distributions D (e.g., D = (U, MJ)
1: Randomly initialize teacher networks 02 (vd E (D) and student network 0$ according to M:
2: Perform teacher training or leverage pre-train ones (if any) to attain well-learned 03 (Vd E D);
3: for epoch = 1, 2, .... E do
4: Pick distribution d and its teacher 6J with an adaptive probability according to Eq. (5);
5: for step 1, 2....... T do
6:
Let student 0 sample tours Ty's for each {Gi according to its own policy p&s:
7:
Get V Trakk by estimating Eq. (6) as per the original design of M:
8:
Get LKD by computing the gradients of Eq. (7);
9: @ <- 0 + L.VL where VL t- aV Taak + (1 a) VLDD
10: end for
11: end for
Student network. We stipulate that the student shares similar architecture with its teachers, but can reduce its network parameters as needed to speed up the inference. Nevertheless, we find in Section 5.3 that larger student model usually leads to a better performance. Therefore, there is trade-off between solution quality and computational cost. In this paper, we consider reducing the dimension of the node embeddings from 128 (teacher) 64 (student), resulting in a reduction of 61.8% and 59.2% in the model parameters for the adaption with AM and POMO, respectively. We also considered lowering the number of encoder layers, but the results were below the expectation.
The adaptive disti-distii distilling strategy. In each epoch, AMDKD selects one distribution and its corresponding teacher model. At the beginning, it selects each distribution with an equal probability. After epoch E' (a hyper-parameter), the probability would be adaptively adjusted according to the performance of the student on the given validation datasets Zu, Zc, ZM (each with 1,000 instances) for each exemplar distribution. The likelihood pullative of selecting distribution d E {U, C, 3 is proportional to the exponent value of the gaps to the LKH solver [4] as follows,
padupiiv (d) { Softmax (AvgGap (o Hzz (Troverr Hzal), if > E'
(5)
otherwise
DD
where [D] is the number of exemplar distributions; {Tos and {Trolvee refer to the tour set generated by the student 0$ and the LKK solver on dataset 2g, respectively. The validation sets are fixed, hence the LKH solver only needs to run once to attain {Tsolver)l for d {U, C, M }. Meanwhile, we note that piulaptive may converge during distillation (see Appendix C), which means that it possible to stop such evaluation early and reuse the stabilized one for an even faster training.
Loss function. Following Eq. (3), we leverage the task loss (Crusk) and the KD loss (Ckd) to jointly train the student with =0.5. Pertaining to Lrask, we define the task loss follows,
Lrak [ (d) -E (119) [[(]]]]], (=())]((()))
(6)
where the training instances G are sampled following the selected distribution d, and the tours constructed via the student network g³ according to Eq. (2). In AM and POMO, the REINFORCE algorithm [54] is used to estimate the gradients for the above loss function and we follow exactly the same way as per their original designs. Pertaining to LKD. it is defined to encourage the student to imitate how a teacher network sequentially selects the nodes. Specifically, given the instance G sampled from distribution d and a tour Tys constructed by the student ØS following its own policy, our AMDKD leverages Pøy (Tx (9) suggested by the teacher network 0f, compute LKD that measures the similarity of the probability distributions between teacher and student using the KL divergence,
LKD
1 B
Σ
Σ TT
Pog(a,(si) (10g Pot (ag19i) 1aallii--ooo llo))=logpp--0 Dog (agl()))
We summarize our AMDKD in Algorithm Note that our AMDKD follows the on on-policy scheme where the tours Tys are output by the student that currently performs learning. As an alternative, such tours can also be output by the teacher (i.e., off-policy scheme). However, performs inferior to our on-policy one (see Section 5.3). Finally, we note that the student learned by our AMDKD could also be coupled with the efficient active search (EASS [23] during inference to further boost the performance. Accordingly, the resulting AMDKD+EAS achieves a new ofte--o--theaat performance.

---

Table I: Distillation effectiveness of AMDKD on three exemplar distributions.
Size
m 20
50
100
Model
(M)
Ght
Avg.
Gc
Gy
Avg.
Gu
Gc
Gy
Avg.
AM(U)
0.68
0.09%
0.26%
0.19%
0.18%
0.59%
2.24%
1.36%
1.39%
2.10%
7.49%
4.06%
4.55%
AM(C)
0.68
0.17%
0.10%
0.27%
0.18%
1.11%
0.80%
2.14%
1.45%
3.76%
6.97%
4.39%
5.04%
AM(M)
0.68
0.15%
0.16%
0.13%
0.15%
1.19%
1.21%
0.87%
1.26%
3.08%
5.65%
2.55%
3.76%
AMDKD-AM
0.26
0.02%
0.06%
0.05%
0.04%
0.25%
1.64%
0.86%
0.91%
1.21%
5.63%
3.55%
3.46%
TSP
POMOIU)
1.20
0.00%
0.01%
0.01%
0.01%
0.04%
0.42%
0.21%
0.229
0.17%
1.97%
0.92%
1.02%
POMOIC)
1.20
0,00%
0.00%
0.01%
0.00%
0.09%
0.07%
0.21%
0.12%
0.41%
0.29%
0.83%
0.51%
POMO(M)
0.00%
0.01%
0.00%
0.00%
0.08%
0.17%
0.08%
0.11%
0.77%
1.17%
0.34%
0.76%
AMDKD-PPMMO
0.49
0.00%%
0.00%
0.00%%
0.00%
0.05%
0.05%
0.09%
0.06%
0.34%
0,35%
0.41%
0.37%
AM(U)
0.68
1.98%
1.99%
1.98%
1.98%
2.53%
4,33%
2.98%
3.28%
3.10%
9.87%
4.57%
5.85%
1.74%
3.08%
2.75%
3.35%
3.06%
3.89%
4.36%
AM(M)
0.68
2.09%
2.19%
2,05%
2.11%%
2.74%
3.17%
2.31%
2.74%
3.95%
6.26%
3.41%
4.54%
CVRP
AMDKD-AM
0.26
0.53%
0.59%
0.64%
0,59%
1.61%
2,66%
1.92%
2.07%
2.08%
5,06%
3.01%
3.38%
POMOIU)
0.49%
0.51%
0.45%
1.53%
1.07%
1.13%
2.34%
POMOIC)
1.20
0.41%
0.40%
0,54%
0.45%
1.16%
0.93%%
1 1,07%
1.05%
0.93%
1.28%
1.21%
1.14%
POMOIM)
1,20
0.36%
0.51%
0.10%
0.41%%
1.22%
1.34%
0.85%
1.14%
1.89%
2.07%
0.96%
1.64%
AMDKID-POMO
0.49
0.35%
0.40%
0.41%
0.39%
0.81%
0.97%
0.89%
0.89%
1.00%
1.36%
0.99%
1.13%
Note: Unless ocheriise stated, the gaps are compoted wit. the strong traditional solvers Gurobi [5] (for TSP) and I.KH (4] (for CVRP).
5 Experiments
We conduct experiments on TSP and CVRP with n 20, 50, and 100 nodes similar to [12, 14). As aforementioned, we adopt Uniform, Cluster and Mixed (mixture of uniform and cluster) as exemplar distributions for training: Expansion, Implosion, Explosion, and Grid as the unseen distributions for testing. For the above 7 distributions, we follow [10, 21, 43] to generate the respective instances (details are presented in Appendix A). All experiments are conducted on a machine with NVIDIA RTX 3090 GPU cards and Intel Xeon Silver 4216 CPU at 10GZz. Our implementation in PyTorch are publicly available?. Some additional analysis and discussions can be found in Appendix C.
Training and hyper- parameters. We apply our AMDKD to two representative deep models, i.c., AM [10] and POMO [12], termed as AMDKD-AN and AMDKD-POMO respectively. For the teacher (pre)-training phase, we directly follow the RL algorithm, network architecture, and other hyper-parameten as suggested in the original backbone method. For the student distillation phase, we use batch size B = 512", and task-specific hyper-parameters T 250, F = 500 for AMDKD-AM and respectively. By default, the dimension of the node embeddings
T 20, E" = for in our student networks AMDKD-AM and AMDKD-POMO is reduced from 128 (teacher) to 64 (student) to enjoy a faster inference speed. The total numbers of needed training epochs vary with the problem size. Regarding AMDKD-AM, we use 2.000, 5,000, 10,000 for problem sizes 20, 50, 100, respectively (both TSP and CVRP); regarding AMDKD-POMI (CVRP-20, TSP-50, TSP-100) and 30,000 (CVRP-50, CVRP- 100). The Adam optimizer is used with learning rate 1c-4. Training time also varies with the problem size. Taking CVRP-100 as an example, one epoch takes about 4 minutes for AMDKD-AM and 1.4 minutes for A.DDKIDPPOMO.
we use 5,000 (TSP-20), 10,000
Inference. For AMDKD-AM, it samples 1,280 solutions following AM [10]; and for AMDKD- POMO, we adopt the greedy rollout with x8 augments following POMO [12]. All experiments are conducted on test datasets containing 10,000 instances per distribution. Unless otherwise stated, the gaps are computed w.r.t. the strong traditional solvers Gurobi [5] (for TSP) and LKH [4] (for CVRP).
5.1 Effectiveness analysis of AMDKD
We first study the effectiveness of our AMDKD when applied to backbone model AM and POMO for TSP and CVRP, respectively. In Table 1, we display the gaps of the learned student and their respective teachers on unseen instances following three exemplar distributions (denoted as Gu, Gc. and Gm) and also report the parameter sizes of each model. We can see that when the teacher model is trained on a specific distribution, it does not generalize well on the other ones (especially for AM), resulting in poor overall performance (if referring to the average gaps). In contrast, our AMDKD could alleviate this issue effectively. While the learned student model by AMDKD reduces the size of
For training AMDKD- POMO TSP100 and CVRP100, B = 128 due to GPU memory constraint.
7

---

Table 2: Generalization on unseen in-distribution (ID) and out-of-distribution (OoD) instances.
Size (M)
20
50
100
Model
Guo
GoaD
Time'
Gm
GoLD
Time'
GD
GooD
Time'
Gurobi
0.01s (78)
0.08s (51s)
0.7s (7.6m)
HACP
0.68
0.11%
0.07%
(48s)
1.05%
0.09s (4m)
4.68%
2.97%
0.19% (16m)
LCP
2.03
0.11%
0.03%
1.2s (43m)
6.70%
0.99%
1.5s (2.5h)
32.70%
8.24%
2.4% (6.4h)
DACT(T-1,280)**
0.27
0.118
0.08%
12x (2. Im)
0.31%
0.34%
(7.2m)
2.37%
3.13%
28s (23m)
AM (128)
0.68
0.18%
0.10%
0.03 (48s)
1.48%
0.74%
0.09s (4em)
4,15%
2.84%
0.19 (16m)
T5P
AM (64)
0.26
0.21%
0.115
0.03s (35s)
1.74%
0.83%
0.08s (2.8m)
5.93%
3.85%
(11m)((1m)
AMDKD-AM (64)
0.26
0,04%
0.02%
0.03s (35%)
0.91 %
0,37%
0.08s (2.8m)
3.46%
1.87% %
0.178 (11m)
POMO* (128)
1,30
0.00%
0.00%
0.03s
0.07%
0.05%
0.0%% (16s)
0.30%
0.28%
0.13s (1.
POMOR (64)
0.49
0.02%
0.01%
0.02s (16)
0.18%
0.16%
0.04s (11s)
0.69%
0.59%
0.12s (50s)
HIDKD-POMO (64)
0.49
0.00%
0.00%
0.02x (46)
0.06%
0.05%
0.04s (11s)
0.37%
0.41%
0.12s
AMDKD+EAS
0.49
0.00%
0.00%
Ss (4.5m)
0.01 %
0.01 %
12s (28m)
0.11%
0.10%
28s (2.3h)
LKHB
7.7%
31s (5.36)
S6s (9.6h)
11C2(T-1,280)**
0.27
0.09%
0.05%
28s (4.3m)
1.59%
1.59%
(54m)
5.56%
5.55%
1.5m (34m)
AM (128)
0.68
2,00%
1.98%
0.05s
3.39%
2.66%
0.12s (5m)
5.42%
3.75%
0.26s (
CVRP
AM (64)
0.26
2,02%
2,022%
0.05: (49x)
3.62%
2.63%
1.1 (3.6m)
6,83%
4. 5.56%
0.23s (13m)
AMDKD-AM (64)
0.26
0.59%
0.55%
0.05s (19%)
2,07%
169%
0.1 (3.6m)
3,38%
2.44%
0.23s (13m)
POMO* (128)
1.20
0.42%
0.39%
0.05s (7.8s)
0.92%
0.94%
0.10s (18s)
1.14%
1.21%
0.19 (1.3m)
POMO
0.49
0.55%
0.51%
0.05% (6. ls)
1.19%
1.21%
0.08s (15s)
1.43%
1.50%
0.18s (1.1m)
AMDKD-POMO (64)
0.49
0.39%
0.36 %
0.05s (s)
0.89 %
0.90%
0.08s (15s)
1.13%
1.21% %
0.18s (1. (1.1m)
AMDKD+EAS!
0.49
-0.04%
-0.06%
96 (7.8m)
0.07%
0.04%
20s (37m)
-0.03%
-0.04%
40s (3.3k)
We report the average time to solve one insiance, and the total time to solve 10,000 instances in (-) with butch parallelism allowed (one GPU). The corresponding model is trained on a mixed training dataset that contains instances from all the three exemplar distributions. For EAS, adopt EAS-lay version (T=100) for demonstaaion purpose.
the teacher model from 0.68 to 0.26 M (a 61.8% reduction) for AM and from 1.20 0.49 M (a 59.2%
reduction) for POMO, it still exhibits improved overall performance for both TSP and CVRP on all the three sizes. Pertaining to AMDKD-AM, our AMDKD student not only significantly outperforms its three teachers for both TSP and CVRP, but also exhibits even lower gaps on the distribution where the teacher was previously trained in most cases. Pertaining to AMDKD-POMO, although POMO itself presents a better generalization, our AMDKD can still boost its overall performance with a much lighter student network for both TSP and CVRP. The above results validate that our AMDKID does not overfit to single distribution, and successfully learns lightweight yet generalist student model under the guidance of multiple teachers with expertise in different exemplar distributions.
5.2 Generalization analysis of AMDKD
We now assess the cross-distribution generalization of our AMDKD. In addition to the two backbone models, we also compare with the following methods, i.e., 1) other deep models including- L.a) DACT [14], a neural improvement model that learns to perform local search; 1.b) LCP [13] (TSP only), hybrid two-stage method that combines improvement and construction strategy; and 2) other methods specialized for generalization including- 2.a) HAC [17] (TSP only), a fine-tuning framework for AM by leveraging instances with different hardness; 2.b) DROP [21], a distributionally robust optimization based method enhance POMO; 2.c) GANCO [18), framework that enhances AM by learning generative adversarial network to produce hard-to-solve training instances; and 2.d) PSRO (a.k.a. LIH) [20], an improvement method with a game theory based policy space response oracle framework. More implementation details of them are provided in Appendix B. Note that for DROP, GANCO, and PSRO, we only compare the results on several benchmark instances reported in their original papers (see Table 3), since their codes (for re-training) are not publicly available.
Distribution mixture augmentation. Given that baselines AM, POMO, DACT, and LCP were originally trained on the uniform distribution only (resulting in poor generalization), we re-train the above models (with #) on a mixed dataset containing instances from the three exemplar distributions, to ensure fair comparison. We also apply this mixed dataset as the initial training instances for HAC (with #). Though such distribution mixture augmentation improves the generalization of construction methods POMO and AM on larger instances, we notice that it does not always happen so, especially for the methods that have an improvement component (e.g., DACT and LCP). We present detailed results and discussions regarding this finding in Appendix B. Meanwhile, for AM# and POMO# we report their performance with network dimensions of both 128 and 64 (same size as our AMDKD student) for more comprehensive comparison. We assess the following metrics, 1) parameter size; 2)
8

---

Table Generalization performance on selected instances (100 from benchmark datasets.
PSRD
AM (128)
GANCO
HMC
AMURD-AM (64)
PUMO (128)
DRUP
PUMUP"(12)
AMDKD-POMO (64)
AMDKIHEAS
1SPLIB CVRPLIB
4,4%%
42,558
4,57%
6.004
17.005
3.53% 7.43%
29755 14.10%
10.795 8.78%
9,87% 6.80%
1
8.4%
29.36'
13.89%
4,38%
1.25%
average gap on unseen in-distribution instances, i.e. GID: 3) average gap on unseen out-o--distribution instances, i... GooD; 4) average time for solving an individual instance and total time for solving 10,000 instances with batch parallelism allowed (one GPU)*.
As can be observed in Table 2, our AMDKD is able to achieve competitive results on both un- seen in-distribution and out-of outtof-distribution instances, and performs favourably against all baselines. Pertaining to TSP, our AMDKD AM (64) significantly outperforms the baseline AM (128) and AM# (64) all sizes in terms of both GID and GOOD with fewer parameters and higher inference speed. Meanwhile, it also consistently beats the recent baseline HAC# (designed to boost the gener- alization of AM) on all sizes in terms of both two gaps and the time efficiency. For the backbone model POMO, which suffers from less generalization concern, the baseline POMO# (128) can already attain near-optimal solutions to TSP instances with desirable generalization performance. However, our AMDKD (64) is able to achieve competitive generalization results with nearly half of the model size and higher inference speed. When we reduce the network dimension of POMO# # to 64 (as our AMDKD), POMO (64) performs much inferior to our AMDKD-POMO (64). Pertaining to CVRP, similar patterns can be observed, where our AMDKD AM (64) and AMDKD-POMS (64) consistently deliver favourable generalization performance against all the compared baselines. Besides, both our AMDKD-AM (64) and AMDKD-POMO (64) exhibit significantly faster inference than improvement methods ICP and DACT while achieving similar or even lower gaps.
Furthermore, show that by coupling our AMDKD-POMO (64) model with the recent efficient active search (EAS) [23], the resulting AMDKD+EAS (T=100) attains considerably superior per- formance that even surpasses LKH3 on CVRP-100 with much shorter time. Given the advances of active search for a particular instance to be inferred, AMDKD+EAS allows the model learned by our AMDKD with strong generalization to continuously improve its performance during inference (longer T will yield even better performance), which leads to new state-of ootte-of-ie of-the-art hybrid solver.
We now evaluate the generalization of our AMDKD the benchmark, i.e., TSPLIB and CVRPLIB, which contain various instances of unknown distributions and larger size. As shown in Table 3, our AMDKI-AM (64) significantly boosts the generalization of AM (128) and also outperforms the baseline AM# (128) as well as other generalization methods that take AM (128) as the backbone model (GANCO and HAC). Similarly, our AMDKD-POMO (64) also significantly beats the other baseline methods, except for POMO# (128) on TSPLIB. Nevertheless, regarding the harder CVRP instances from CVRPLIB, our AMDKD-POMO (64) could yield significantly better performance. Finally, we note that the AMDKD+EAS achieves the smallest gaps for both TSP and CVRP among all baselines. We refer to Appendix D for full results and discussions.
5.3 Further analysis of AMDKD
Effects of different components. We conduct ablation studies on CVRP-50 and TSP-50 to verify the designs of our AMDKD, where we consider removing the proposed adaptive strategy, the KD loss LKD. and the task loss Lrssk, respectively. As displayed in Table 4, the use of adaptive strategy further enhances the learning effectiveness, and the two losses play prominent role in the phase of gradient update. We also verify that when compared with our on-policy scheme, the off-policy variant (as mentioned in Section 4.2) saliently impairs the distillation performance.
Effects of student network architectures. In Figure 3, we exhibit the boxplots of the averaged gaps when using different student network architectures (different dimensions of the entire network and different number of layers in its encoder) of AMDKD-POMO for solving CVRP-50. As revealed, the larger the model, the better its performance. Hence, we acknowledge that our AMDKD can be further boosted when the student (64) shares the same architecture with its teachers (128). Specifically. for CVRP-50, our AMDKD-POMO (128) exhibits an average optimality gap of 0.81 %. which is
'Even so, we note that the time of traditional solvers and deep models might be still difficult to be fairly compared due to different implementations (C vs Python) and computing devices (CPU vs GPU).

---

1.25
1.25
Table 4: Ablation studies of AMDKD designs.
1.00
1.00
0.75
Components
CVRP-50
TSP-50
Iay ar2 layerd layer6
dim32 dim64dim128
Model
ExD
Lua
1ye
Avg. Gap
Avg. Gap
who adaptive
0.94%
0.69%
(a)
(b)
who Cun
1.06%
0.66f%a
CTal
4
0.69%
Figure 3: Effects of student network architec-
off policy
4
v
10.42%
0.80%
tures. (a) different numbers of encoder layers,
AMDKD
0.90%
0.63%
(b) different node embedding dimensions.
Table 5: Performance of AMDKD on CVRP-50 trained with different exemplar distributions.
Expansion Ong
Implasion Gap
Hxplosaen
Model
(M)
Cup
Dlg
Goop
Ohj
Clap
Clap
Cihj.
Gaop
Chjj
Clop
Avg. Cup
LKH
10.40
5:13
1.20
8.22
0.90%
10.36
0.96%
5.82
0.94%
10.50
0.95%
10.47
0.94%
5.19
1.14%
9.51
0.90%
0.97%
1.20
8:25
0.96%%
10:34
0.805
5.81
01824
10.48
0.77%
10.46
0.78%
5.21
1.505
9:52
1.008
0:95%
POMoiEsplesio)
1.20
8.23
0.95%
10:35
0.83%
8.81
0.80%
10.49
0.82%
10.47
0.87%
5.20
1.27%
9.51
1.02%
0.94%
POMUXCad)
1.20
8.23
0.97%
10.34
0.79%
8.81
0.82%
10.48
0.76%
10.46
0.77%
5.21
1.57%
9.52
1.00%
0.97%
AMDKD-POMO*
0.49
8.23
0.96%
10:35
0.898
8.82
0.80%
10,49
0.88%
10.47
0.88%
5.18
1.08%
9.50
0.92%
0.92%
lower than the 0.90% of AMDKD-POMO (64). However, this improvement comes at the expense of
increased computational costs three aspects: 1) more training time SHIDKD-POMO (128) needs almost 1.7 times (12 days vs 7 days) more training time; 2) more parameters AMDKD POMMO (128) has about 2.4 times (1.20 M vs 0.49 M) more parameters; 3) slower inference time- AMDKD-POME (128) infers about 1.2 times (1.3 min vs 1.1 min) slower than AMDKD POMO (64). Hence, we note that there a trade-off between solution quality and computational cost.
Effects of different exemplar distributions. We now vary the distributions which were used as the exemplar ones validate that AMDKD could still be effective. We take the POMO and CVRP-50 as an example. To distinguish from the original version (AMDKD-POMO) we term the model taking Expansion, Implosion, Explosion, and Grid as the exemplar distributions as AMDKD-POMO gathered the results in Table 5. It shows that the overall performance of AMDKD-POMO is still better than POMO trained on these four distributions respectively. Hence, our AMDKD able to consistently improve the cross cros-distribution generalization with different exemplar distributions.
and
6 Conclusions and future work
In this paper, we propose an Adaptive Multi-Distribution Knowledge Distillation (AMDKD) scheme to alleviate the -ioss-distriuution generalization issue of deep models for VRPs. Different from the existing generalization methods, aim enhance the distribution generalization by transferring various policies learned from exemplar distributions into one via an efficient knowledge distillation scheme. To facilitate effective learning, we design adaptive strategy to train single yet generalist student network by leveraging multiple teachers in turns. The experiment results exhibit competitive performance of our AMDKD in generalizing other unseen cuttoo-distributiin instances (randomly generated or from benchmarks), which also consumes less computational resources. While our AMDKD is generic, a potential limitation is that its boost is not guaranteed be always significant across all unseen distributions for all backbone models. For future work, we will investigate, 1) generalizing AMDKD for different/larger problem sizes; 2) considering the improvement models like DACT [14] as the backbone; 3) performing online distillation to jointly and efficiently train the teachers and the student models [55]; 4) assessing the impact of the quality of the validation dataset on the distillation; and 5) enhancing the interpretability of AMDKD [56].
Acknowledgments and Disclosure of Funding
This work is supported in part by the National Key R&D Program of China (2018AAA0101203), the National Natural Science Foundation of China (62072483), and the Guangdong Basic and Applied Basic Research Foundation (2022A15 151A011500 1690, 2021A 0021A151500 551501229);; in part by the Agency for Sci- ence Technology and Research Career Development Fund (C22281 (222), and the IEO Decentralised GAP project of Continuous Last-Mile Logistics (CLML) at SIMTech
10

---

References
[1] Lu Duan. Yang Zhan, Haoyuan Hu, Yu Gong, Jiangwen Wei, Xiaodong Zhang. and Yinghui Xu. Efficienlly solving the practical vehicle routing problem: A novel joint learning approach. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3054-3063, 2020.
[2] Grigorios D Konstantakopoulos, Sotiris P Gayialis, and Evripidis P Kechagias, Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Operational Research, pages 1-30, 2020.
[3] Zhiwei Qin, Xiaocheng Tang. Yan Jiao, Fan Zhang, Zhe Xu, Hongtu Zhu, and Jieping Ye. Ride-hailing order dispatching at DiDi via reinforcement learning. INFORMS Journal on Applied Analytics, 50(5): 272-286, 2020.
[4] Keld Helsgaun. LKH-3 (version 3.0.7), 2017. URL http::p//wwbboeee....../o////o// LKH-3/.
[5] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https://www.guroht
[6] G. A. Croes. A method for solving raaeling-salesman problems. Operations Research, 6:791-812, 1958.
[7] Paul Shaw. A new local search algorithm providing high quality solutions to vehicle routing problems. 1997.
[8] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, pages 1692-2700. 2015.
[9] Mohammadreza Nazari, Afshin Oroojlooy. Martin Takáč, and Lawrence Snyder. Reinforcement learning for solving the vehicle routing problem. In Advances Neural Information Processing Systems, pages 9861 11719 2018.
[10] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018
[11] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arxiv preprint arxiv:1906.01222 ArXiV, 2019.
[12] 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, volume 33, pages 21 2188--11998 2020.
[13] Minsu Kim, Jinkyoo Park, and joungho kim. Learning collaborative policies to solve np- ap-hard routing problems. In Advances in Neural Information Processing Systems, volume 34, pages 10418- 10430, 2021.
[14] Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang. .earning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neural Information Processing Systems, volume 34, pages 11096-11
1009-11107, 11077, 2021.
[15] Liang Xin, Wen Song. Zhiguang Cao, and Jie Zhang. NeuroLKH: Combining deep learning model with San--ernighan-Hekeee
heuristic for solving the traveling salesman problem. In Advances in Neural Information Processing Systems, volume 34, pages
2021.
[16] Rongkai Zhang, Cong Zhang, Zhiguang Cao. Wen Song. Puay Siew Tan. Jie Zhang, Bihan Wen, and Justin Dauwels. Learnigg to solve multiple-TSP with time window and rejections via deep reinforcement lcarning. IEEE Transactions on Intelligent Transportation Systems, pages 1-12, 2022. doi: 10.1109/TTTS. 2022.3207011.
[17] Zeyang Zhang, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning solve travelling salesman problem with hardness-adaptive curriculum. In AAAI Conference on Artificial Intelligence, 2022.
[18] Liang Xin, Wen Song. Zhiguang Cao, and Jie Zhang. Generative adversarial training for neural combinato- rial optimization models, 2022. URL https: / http:////ee//eeeee//eeee wtt.eeeeeeeoomm//////tttreee
[19] Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference on Learning Representations, 2022.
11

---

[20] Chenguang Wang, Yaodong Yang, Congying Han. Tiande Guo, Haifeng Zhang, and Jun Wang. A game- theoretic approach for improving generalization ability of TSP solvers, 2022. URL https:://ppenreriier net//forunidd77Aasailiiy
[21] Yuan Jiang, Yaoxin Wu, Zhiguang Cao, and Jie Zhang. Learning to solve routing problems via distribu- tionally robust optimization. In AAAI Conference on Artificial Intelligence, 2022.
[22] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehiele routing problem. Europeon Journal of Operational Research, 257(3):845-858, 2017.
[23] André Hottung, Yeong- Dae Kwon, and Kevin Tiemney Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
[24] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Machine Learning (Workshop), 2017.
[25] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances Neural Information Processing Systems, volume 30, pages 6000 00100,60022200000000000 2017.
[26] Bo Peng. Jiahai Wang. and Zizhen Zhang. A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. In International Symposium on Intelligence Computation and Applications, pages 636-6566 653,650,220 2019.
[27] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In AAAI Conference on Artificial Intelligence, pages 10042-12049 2021.
[28] Jingwen Li, Yining Ma. Ruize Gao, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Deep rein- forcement learning for solving the heterogeneous capacitated vehicle routing problem. IEEE Transactions Cybernetics, 2021.
[29] Yeong-Dae Kwon, Jinho Chao, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 34, 2021.
[30] Zizhen Zhang, Zhiyuan Wu, Hang Zhang, and Jiahai Wang. Meta-lcarming-based deep reinforcement learning for multiobjective optimization problems. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[31] Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in Neural Information Processing Systems, pages 6351-6361, 2017.
[32] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large TSP instances. In AAAI Conference on Artificial Intelligence, 2021.
[33] Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. arxiv preprint arxiv:2102.1 1 1756, ArXiV, 2021.
[34] Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, pages 6281 1-292, 2019.
[35] André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. In European Conference on Artificial Intelligence, 2020.
[36] André Hottung and Kevin Tierney. Neural large neighborhood search for routing problems. Artificial Intelligence, page 103786, 2022.
[37] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristies for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 305))50577-506, 2021.
[38] Paulo da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Eren Akçay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, pages 485-480, 2020.
12

---

[39] Yining Ma, Jingwen Li. Zhiguang Cao, Wen Song, Hongliang Guo, Yuejiao Gong, and Yeow Meng Chee. Efficient neural neighborhood search for pickup and delivery problems. In Proceedings of the Thirty-Firt International Joint Conference on Artificial Intelligence, pages 4776-4784, 2022.
[40] Jinbiao Chen, Huanhuan Huang, Zizhen Zhang. and Jiahai Wang. Deep reinforcement learning with two- stage training strategy for practical electric vehicle routing problem with time windows. In International Conference on Purallel Problem Solving from Nature, pages 356-370. Springer. 2022.
[41] Zizhen Zhang, Hong Liu, MengChu Zhou, and Jiahai Wang. Solving dynamic traveling salesman problems with deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[42] Gerhard Reinelt. TSPLIB-A traveling salesman problem library. ORSA journal on computing. 3(4): 376-384, 1991.
[43] 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.
[44] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arxiv preprint arxiv:1503.008 02531,, ArXiv, 2015.
[45] Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. TinyBERT: Distilling BERT for natural language understanding. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 111444444, 2020.
[46] Weijie Liu, Peng Zhou, Zhiruo Wang, Zhe Zhao. Haotang Deng, and Qi Ju. FastBERT: self- dist-disti BERT with adaptive inference time. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 6035-6044, 2020.
[47] Samuel Stanton, Pavel Izmailov, Polina Kirichenko, Alexander A Alemi, and Andrew G Wilson. Does knowledge distillation really work? In Advances in Neural Information Processing Systems, volume 34, pages 6906 6919, 2021.
[48] Hossein Mobahi. Mehrdad Farajtabar, and Peter Bartlett. Self-distillation amplifies regularization in hilbert space. In Advances in Neural Information Processing Systems, volume 33, pages 3351-3361, 2020.
[49] Minghao Hu, Yuxing Peng. Furu Wei, Zhen Huang, Dongsheng Li, Nan Yang, and Ming Zhou. Attention- guided answer distillation for machine reading comprehension. In EMNLP, 2018
[50] Tommaso Furlanello, Zachary Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar, Born again neural networks. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1607-1616, 10-15 15 Jul 2018.
[51] Glen Berseth, Cheng Xie, Paul Cernek, and Michiel Van de Panne. Progressive reinforcement learning with distillation for multi-skilled motion control. In International Conference on Learning Representations, 2018.
[52] Andrei A Rusu, Sergio Gomez Colmenarejo, Çaglar Gülçehre, Guillaume Desjardins, James Kirkpatrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell. Policy distillation. In ICLR (Poster), 2016.
[53] Chuhan Wu, Fangzhao Wu, and Yongfeng Huang. One teacher is enough? pre-trained language model distillation from multiple teachers. In Findings of the Association for Computational Linguisties: ACL- IJCNLP 2021, pages 4408-4413, 2021.
[54] Ronald J. Williams. Simple statistical gradient-foloowngg algorithms for connectionist reinforcement learning. Machine Learning, 8:229-256, 2004.
[55] Qiushan Guo, Xinjiang Wang, Yichao Wu, Zhipeng Yu, Ding Liang. Xiaolin Hu, and Ping Luo. Online knowledge distillation via collaborative learning. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 11000-1002, 2020.
[56] Quanshi Zhang, Xu Cheng, Yilan Chen, and Zhefan Rao. Quantifying the knowledge in a DNN to explain knowledge distillation for classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
13


Reviews:
[{"review_id": "u5Ee-kYWtEg", "reviewer": "Reviewer_6JzK", "summary": "This paper proposes a knowledge distillation framework named Adaptive Multi-Distribution Knowledge Distillation (AMDKD) for transferring various knowledge from multiple expert teachers to a generalist lightweight student model.  Firstly, AMDKD performs teacher pre-training to obtain expert teachers for different distributions.  Then in each epoch of the knowledge distillation process, AMDKD selects a specific distribution and its teacher with an equal probability. The probability of each distribution being selected is computed according to the performance of the student model on this distribution.  With the selected teacher model, AMDKD performs a general single-teacher knowledge distillation and updates the student model. Several experiments on TSPLIB and CVRPLIB datasets are conducted and AMDKD shows competitive results compared with state-of-the-art methods.", "questions": "See the weaknesses.", "limitations": "See the weaknesses.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths：\n1.\tBenefitting from a concise description of the overall framework, the motivation and training process is clear and easy to read.\n2.\tThe idea of selecting a specific teacher model on the weakness of the student model is interesting, which converts a multi-teacher knowledge distillation to a single-teacher knowledge distillation in each epoch, avoiding the profitless influence of averaging the outputs from multiple teacher models.\n3.\tSufficient experiments are conducted to prove the effectiveness and the generalization of AMDKD, especially the experiments on the unseen in-distribution and out-of-distribution instances.\n\nWeaknesses:\n1.\tThe probability of selecting specific distribution and its teacher is updated with each epoch, which will take a lot of computation cost to evaluate the performance of the student model. \n2.\tThe selection of teachers is decided by the performances on the validation datasets, which makes the experimental results rely on the quality of the validation datasets\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kYJoECqxXb", "reviewer": "Reviewer_kcQQ", "summary": "This paper proposes a knowledge distillation (KD) approach for learning generalizable models for vehicle route planning (VRP). One key challenge in VRP is identified, that is, cross-distribution generalization. The proposed KD approach (a.k.a. AMDKD) leverages multiple specialized teacher models from different distributions to distill a generalist student model that can handle multiple distributions at the same time and generalizes well to OOD instances. Overall, the paper is well-written, the proposed method is clearly explained, and the experiments demonstrate promising results of the hybrid distillation scheme for VRP.\n", "questions": "1. Table 2 shows the time* of AMDKD+EAS methods is much slower than existing methods, but the authors claimed that the proposed approach can help attain a more efficient student model. Why is that?\n2. Maybe add more understanding of why AMDKD is better than # models. Why training on mixed data is not as good as training separately then distilling? Any deeper understanding in the context of VRP?\n3.  Why do the three distributions (Figure 1c-1e) generalize better to other distributions? Given a real-world application scenario where generalization needs to be improved, is there a strategy for including more distributions with AMDKD in addition to the existing distribution?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": " Strengths:\n1. This paper presents a novel exploration of KD or multi-teacher KD for VRP;\n2. The proposed AMDKD approach is simple but effective and could be easily applied to help improve the generalizability of existing models by training and distilling on multiple distributions;\n3. The paper is very well written and easy to read.\n\nWeaknesses:\n1. There is some confusion about the time analysis.\n2. Could provide more understanding of AMDKD.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VaKuKLc4rW", "reviewer": "Reviewer_RL4k", "summary": "The paper focuses on a class of NP-hard combinatorial optimization problems called Vehicle Routing Problems (VRP) which is of wide practical interest. In the deep learning community there is a wide interest in replacing the domain and expert dependent heuristics with data-driven methods like reinforcement learning. However, as the paper notes, most current approaches focus on one particular distribution of problem rather than trying to generalize across distributions, which limits their practical applicability. The paper builds on the ideas of knowledge distillation widely applied in practical deep learning applications to train a light-weight student model to learn from this variety of individual distributions focused methods. This allows demonstration of competitive results on both unseen in-distribution as well as OOD instances while requiring cheaper compute resources.", "questions": "Would be useful to understand the computational tradeoff for the larger student models as well. What's their resulting size and time taken? ", "limitations": "The paper adequately mentions its limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nA simple and widely used idea of knowledge distillation is demonstrated useful in a new domain with wide practical applications. Given the simplicity the method is likely simple to implement and generalize to real world problems. The shown improvements are fairly consistent along a variety of different axes of comparisons and are compared against a fair number of strong baselines. They also confirm that their method can improve further with more compute resources for their student model.\n\n### Weaknesses\n\nMain weakness as the authors acknowledge as future work is generalizing across different/larger problem sizes. The idea of knowledge distillation is straightforward and not necessarily novel, but this will likely be a strong baseline for the community to build upon.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4CpmjA4o5KE", "reviewer": "Reviewer_iBvW", "summary": "This paper aims to enhance the cross-distribution generalizability of deep learning models for the vehicle routing problem. It proposes a novel method that is based on knowledge distillation and uses several teacher networks to guide learning a student network that is both light-weight and of strong generalizability. Moreover, it proposes an adaptive strategy to select the teacher models that are more informative. Experiments on two datasets verify the effectiveness of the proposed method by adding it on two existing methods and achieves performance gains. ", "questions": "See the weakness above. ", "limitations": "Limitations are well addressed. ", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1) The proposed method is technically sound. \n2) Experiments on two datasets verify the effectiveness of the proposed method by comparing with existing methods. \n3) The proposed method is overall well presented.\n\n\nWeaknesses:\n1) From the implementation details, it seems that the proposed method has quite a few task-specific designs, e.g., training policies, architectures, hyper-parameters, etc. It is thus doubtful if the proposed method is generalizable enough when applied in practice. \n\n2) In Table 1, there are many 0.00%, especially for methods LKH and Gurobi, all their result numbers are 0.00%. I am not sure if it has some special implications. If it is, there should be some explanations about it; otherwise, it could be presented in a better way, or maybe just leave it unfilled. \n\n3) What is the performance variance with respect to the hyper-parameters.   ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept