Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
Authors: Yining Ma
Jingwen Li
Zhiguang Cao
Wen Song
Le Zhang
Zhenghua Chen
Jing Tang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Transformer
positional encoding
learning to optimize
vehicle routing problem
combinatorial optimization

Abstract: Recently, Transformer has become a prevailing deep architecture for solving vehicle routing problems (VRPs). However, it is less effective in learning improvement models for VRP because its positional encoding (PE) method is not suitable in representing VRP solutions. This paper presents a novel Dual-Aspect Collaborative Transformer (DACT) to learn embeddings for the node and positional features separately, instead of fusing them together as done in existing ones, so as to avoid potential noises and incompatible correlations. Moreover, the positional features are embedded through a novel cyclic positional encoding (CPE) method to allow Transformer to effectively capture the circularity and symmetry of VRP solutions (i.e., cyclic sequences). We train DACT using Proximal Policy Optimization and design a curriculum learning strategy for better sample efficiency. We apply DACT to solve the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). Results show that our DACT outperforms existing Transformer based improvement models, and exhibits much better generalization performance across different problem sizes on synthetic and benchmark instances, respectively.

Learning to Ittratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
Yining Ma Jingwen Li', Zhiguang Cao?., Wen Song Le Zhang", Zhenghua Chen², Jing Tang
National University of Singapore
Singapore Institute of Manufacturing Technology, A*STAR
Institute Marine Science and Technology, Shandong University University of Electronic Science and Technology of China Institute for Infocomm Research, A*STAR
The Hong Kong University of Science and Technology fyiningma, 1 [ijiinwen]]at nus edu, zhiguangcaaoooutlokk. com, wensongdemail. sdu. edu. cn, zhangleuestc@gmail chen08320e. ntu. euu.edu.sgg sg, jingtangdust.. .k
Abstract
Recently, Transformer has become a prevailing deep architecture for solving vehicle routing problems (VRPs). However, it is less effective in learning improvement models for VRP because its positional encoding (PE) method is not suitable in representing VRP solutions. This paper presents novel Dual-Aspect Collaborative Transformer (DACT) to learn embeddings for the node and positional features separately, instead of fusing them together done in existing ones, so to avoid potential noises and incompatible correlations. Moreover, the positional fcatures are embedded through novel cyclic positional encoding (CPE) method allow Transformer to effectively capture the circularity and symmetry of VRP solutions (i.e., cyclic sequences). We train DACT using Proximal Policy Optimization and design a curriculum learning strategy for better sample efficiency. We apply DACT to solve the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). Results show that our DACT outperforms existing Transformer based improvement models, and exhibits much better generalization performance across different problem sizes on synthetic and benchmark instances, respectively.
Introduction
Vehicle Routing problems (VRPs), such as the Traveling Salesman Problem (TSP) and the Capacitated
Vehicle Routing Problem (CVRP) which consider finding the optimal route for single or fleet of vehicles to serve a set of customers, have ubiquitous real-world applications [ 22. Despite being intensively studied in the Operations Research (OR) community, VRPs still remain challenging due to their NP-hard nature 3. Recent studies on learning neural heuristics are gathering attention as promising extensions to traditional hand-crafted ones (c.g.. (44)).. where reinforcement learning (RL) [I5] is usually exploited to train a deep neural network as an efficient solver without hand-crafted rules. A salient motivation is that deep neural networks may learn better heuristics by identifying useful patterns in an end-to-end and data-driven fashion.
Solutions to VRPs, i.e., routes, are sequences of nodes (customer and depot locations). Naturally, deep models for Natural Language Processing (NLP), which deal with sequence data as well, are ideal
"Zhiguang Cao and Wen Song are the corresponding authors.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

2- Jowe lume 4
0++ 3- 4
Node Embbedling
PE Vector
Nock
Pretrona
Embealiing (NFB)
Emthesking (PFE)
DAC Encoder
Encoder
XL
Aspect
Aspeet
XL
Eshanced
Ealansed NFF
Ealuneed
Node Libeeding
DAC Decoder
Decoder
Aspect
Aspect 2
de
(a)
(b)
Figure 1: Transformer frameworks for VRPs. (a) et al.
11 (the original one); (b) DACT (ours).
choices for encoding VRP solutions. Given its remarkable performance in NLP tasks, Transformer [16] is standing at the forefront in the learning based methods for VRPs (e.g.. [5 7
17].. The
original Transformer encodes a sentence, i.e., a sequence of words, into a unified set of embeddings by injecting word positional information into its word embeddings through positional encoding (PE). When it comes to VRPs, while is not required in construction models, positional information is critical for deep models that learn improvement heuristics since the input are solutions to be improved.
Although some success has been achieved, learning improvement heuristics for VRPs based on the original Transformer encoder is yet lacking from our perspective. Firstly, directly applying addition operation on PE vectors and the embeddings in absolute PE method (i.e., Figure ( could limit the representation of the model [18] the mixed correlationsfexxitting in the self-attention can bring unreasonable noises and random biases to the encoder (details Appendix (A). Secondly, existing PE methods tend to fuse the node and positional information into one unified representation. NLP tasks such as translation may benefit from this owing to the deterministic and instructive nature of the positional information. However, such design may not be optimal for routing tasks because the positional information therein can be non-deterministic and sometimes even random. This may cause disharmony or disturbance in the encoder and may thus deteriorate the performance. Finally, most VRPs seek the shortest loop of the nodes, making their solutions to be cyclic sequences. However, existing PE methods are only designated to encode linear sequences which may fail to identify such circular input. As will be shown in our experiments, this could severely damage the generalization performance, since the eyclic feature of VRP solutions is not correctly reflected by the encoder.
In this paper, we address the above issues and contribute to the line of using RL to learn neural improvement heuristics for VRPs. We introduce the Dual-Aspect Collaborative Transformer (DACT), where we revisit the solution representations and propose to learn separated groups of embeddings for the node and positional features of VRP solution shown in Figure lb). Our DACT follows the encoder-decoder structure. In the encoder, each set embeddings encodes the solution mainly from its own aspect, and the same time exploits cross-aspect referential attention mechanism for better perceiving the consistence and differentiation with respect to the other aspect. The decoder then collects action distribution proposals from the two aspects and synthesizes them to output the final one. Meanwhile, we design a novel cyclic positional encoding (CPE) method to capture the circularity and symmetry of VRP solutions, which allows Transformer encode cyclic inputs, and also boost the generalization performance for solving VRPs. As the last contribution, we design a simple yet effective curriculum learning strategy to improve the sample efficiency. This further leads to faster and more stable convergence of RL training. Extensive experiments show that our DACT can outperform existing Transformer based improvement models with fewer parameters, and also generalizes well across different sizes of synthetic and benchmark instances, respectively.
'The term correlation refers to the dot product between Query and Key in the self-attention module. The term mixed correlation refers the case where Query and Key are projected from different types of embeddings. 'The relative PE method seems to help, however, it is found to be even worse than the absolute PE method for VRPs in Wu et al. [II. partly due to the disharmony issue caused by learning the unified representation.

---

2 Related work
2.1 Positional encoding (PE) in Transformer.
The original Transformer adopted the absolute PE method to describe the absolute position of elements in the sequence [16], especially for NLP. As formulated in Eq. (T) each generated positional embedding p; E TR& added together with the i-th word embedding x; in the first layer of the encoder,
Abs Via
+ +p) ((2, +p,)WRy
The relative PE method was further proposed in Shaw al. [9 to better capture the relative order information. On the basis of absolute PF, it introduces an inductive bias to the attention as follows,
Rel 1 (1:
Va((e; + pe) + +D)) azz-))
where aj-rER* is learnable parameters for encoding the relative position j- i. To avoid the mixed and noisy correlations between word semanties and positional information in the above two PEs, the Transformer with United Positional Encoding (TUPE) [8] was proposed for NLP which utilizes separated projection metries W₂ and W, for each information follows,
TUPE
(1 W9) (r,
(w,,,)0, by- V2d
1
22d
However, mentioned previously, existing PE methods are less effective for VRPs since they simply fuse the node and positional information into one unified set of embeddings during or after the calculation of the attention correlation ai Meanwhile, they are also unable to properly encode and handle cyclic input sequences as in VRP solutions.
2.2 Deep models for VRP.
Various deep architectures such as Recurrent Neural Network (RNN), Graph Neural Network (GNN), and Transformer have been employed in solving VRPs.
RNN based models. As the pioneering work of neural VRP solvers, Pointer Network adopted RNN and supervised learning to solve TSP [20] (extended RL in Bello al. (2] and CVRP in Nazari et al. (22). While the models in
(20 23 learn construction heuristics, NeuRewriter 4 learns improvement heuristic for CVRP using LSTM to encode the positional information of a solution. In Hottung et al. [13,, the conditional variational autoencoder was adopted to learn continuous and latent search space for VRP, where high-quality solutions were taken as input and encoded by RNNs. However, recurrence structures in RNN are less efficient in both representation and computation [5]
GNN based models. In Dai al. 24]. GNN was combined with Q-learning for solving TSP. Based on supervised learning, Joshi et al. 66 used GNN to Iearn heatmaps that prescribe the probability of each edge appearing in the optimal TSP tour. This idea was extended in Fu al. (25) with additional components such as graph sampling and heatmap merging to enable generalization to larger TSP instances. These models often require post-processin to construct feasible solutions from heatmaps beam
beam search 6 Monte-Care tree search [25] and dynamic programming (26)).
Transformer based models. The Attention Model (AM) by Kool et al. [5] was recognized as the first success of Transformer based models for VRPs. Based on AM, Xin et al. 7 proposed a Multi- Decoder AM that learns multiple diverse policies for better performance. In Kwon al. [8) the RL. algorithm of AM was improved which leaded to a new solver, i.e., POMO (Policy Optimization with Multiple Optima), and achieved the state-of-the-art performance. However, POMO is still lacking in generalization. Besides these construction models, Transformer was also explored to learn improvement heuristics. Hottung and Tierney (27] learned first neural large neighborhood search algorithm for VRPs. Lu et al. [12] proposed the L2I model that learns to select local search operators from pool of traditional ones. Both methods used Transformer style encoder, but the positional information is captured in the node features (information of previous and next nodes) instead of using PE methods. Though 1.11 was shown to outperform LKH3 (28), it is limited to CVRP and the required time is considerably long. Wu et al. [I]] proposed Transformer model which learns to pick node pair each step to perform a pairwise local operator (e.g., 2-opt). However, suffers from the inaccurate representation of positional information given the original Transformer encoder.
3

---

NFTX
Mall-Head DAC-ARI
XTB4
Cocci Projetes
Projetion
Mas Poeiing
Puoiin
Ai Nem
Monee
Maruo
Mazral
Matickaal
Seftzat
Sofouac
Marrel & Sala
Marei Sabb
Faid borverd
Sottes
Unnnng CPt [xx]
DAC Encoder
DAC Decoder
Figure 3: Architecture of policy network, dual- collaborative Transformer (DACT),
3 Problem formulation
We define VRP instance as group of N nodes to visit, where the node feature 2; of node contains 2-dim coordinates and other problem-specifie features (e.g.. customer demand). A solution ó consists of sequence of nodes visited in order where we denote p: to be the position (indices) of node in the solution which is deemed as the positional feature node i. The objective is to minimize the total travel distance (6)) under certain problem-specific constraints.
Starting with an initial yet complete solution, our neural RL policy tries to improve the solution it- eratively. At each step, the policy automatically selects pair of nodes and locally adjusts the solu- tion using a preset pairwise operator such as 2-opr, insert, swap. As illustrated in Figure [ given a node pair (i,j), the 2-opi operator adjusts a solu- tion by reversing the segment between node and node j; the insert operator adjusts a solution by placing node after node j; and the swap operator adjusts a solution by exchanging the position of node and node j. Such operation is repeated until reaching the step limit I' and we model it in the form of Markov Decision Process (MDP) follows.
2
4
Figure 2: Illustration examples of three pairwise operators for routing problems when node pair (i j 1) is specified for operating. From left to right: 2-opt, insert, and swap.
State. For an instance with N nodes, a state describes current solution 6 using its node and positional features of each node, i.e., 8t V (5,) {-f.-.. .... I pÍ. ..... P'N }.-
Action. The action a, = (i.g) specifies a node pair (1-j) for the pairwise operator.
Reward. The reward function is defined as, 7, = (6,)) 10-mmmm min [D(8:41), D(67)] where of is the best incumbent solution found until time t. It refers the immediate reduced cost at each step with respects to the best incumbent solution, which ensures the cumulative reward equal to the total reduced cost over the initial solution. Hence the reward r, >0 if and only if a better solution is found. Policy. The policy Tg is parameterized by the proposed DACT model with parameters f. At each time step, the action (i,j) is obtained by sampling the stochastic policy for both training and inference. Transition. The next state 1 is originated from s; by performing the preset pairwise operator on the given node pair (action). Our state transient is deterministic, in the sense that always accepts the next solution as the next state (infeasible solutions will be masked), regardless of its objective value. With such simple rule, the RL agent is expected automatically learn how combine multiple steps of simple local movements to achieve better solutions, even if some of them may worsen the current solution. Note that the step limit T' can be any user-specified value according the allowed time budget. Hence, our MDP can have infinite horizon and we consider the reward discount factor 7 < 1.
Dual-aspect collaborative Transformer model
We now present the details of our Dual-Aspect Collaborative Transformer (DACT). The concrete architecture of DACT is presented in Figure where we take the TSP with N nodes as illustration

---

PE
CPE (Ours)
PE
CPE (Ours)
PE
(Ours)
45
100
2
2-
15
6
(a)
(h)
(c)
Figure 5: Comparison of our CPE method with absolute PE method on TSP instance with 20 nodes. (a) the embedding vectors, (b) the correlations (dot products) between every two embeddings, and (c)
the top two principal components after PCA (principal component analysis) projection.
example. Our DACT leverages separate aspects of embeddings encode a VRP solution. In the DAC encoder, the self-attention correlations are computed individually for each aspect, and a cross-aspect referential attention mechanism is proposed to enable one aspect to effectively exploit attention correlations from the other aspect as optional references. The DAC decoder then collects action distribution proposals from both aspects and synthesize them to the final one.
4.1 Dual-aspect solution representation
Specifically, we propose to learn two sets of embeddings, i.e., the node feature embeddings (NFEs) for node representation and the positional feature embeddings (PFEs) for positional representation.
NFEs. Following [5] the NEE h2 of node is initialized as the linear projection of its node feature x, with output dimension" dim 64.
tade
PFEs. The PFE of the positional feature ys is initialized as real-valued vector (dim 64)
by applying our cyclic positional encoding (CPE),
Figure 4: An example of cyelic Gray code where digits are used to encode = nodes. The top left shows the base symmetry pattern '1001' in Gray code, and the top right plots its repre- sentation our method.
which is designed based on cyclic Gray codes (29).
As illustrated in Figure 4 the cyclic Gray codes present a eyclic property 11110' in the last column is adjacent to '1111' in the first column) and an ad- jacency similarity property (any codes in adjacent columns only differ in one digit), both of which are desirable for cyclic sequences. To preserve these properties in designing our CPE, follow two observed patterns: 1) each numerical digit contains a periodic cycle with reflectional symmetry, e.g., the '10 in the lowest digit; and 2) the higher the numerical digit, the longer the period. Accordingly. we create similar patterns based on the sinusoidal functions in Eq. (4), where a periodic function with period ia (induced by modulus) is used to generate one base symmetry pattern (the top right in Figure
sin(wa (z(1) mod Am
2x
), if d is even
g:
(d)
my
wy
(4)
cos(wa- (2(1) mod
Am
2x
wa ). if d is odd
We
is to make N nodes linearly spaced in the generated pattern; the angular frequency wa is decreasing along the dimension make the wavelength longer within the range [N [asm/zT .N] (see Appendix B for details). In Figure 5 we visualize the comparison between the absolute PE and our CPE for encoding a TSP instance of 20 nodes. Figure 5 a) demonstrates that our vealev base symmetry pattern has a longer cyclic period as the digit grows. Figure[]lb indicates that our method (blue) is able to correctly reflect the adjacency between the head and tail of the cyclic sequence whereas the PE method (red) fails to do so. Figure 5(c) verifies that our CPE vectors well distributed in space with desired cyclic and adjacency similarity properties.
where =i)
1-1 2m
N+1
N wa
2n/ea
'Different from Wu et al. |. reduce the dimension of the embeddings from 128 to 64.
5

---

4.2
The encoder
The encoder consists of L 3 stacked DAC encoders. In each DAC encoder, we retain relatively independent encoding stream for NFEs and PFEs as in Eq. (5) and Eq. 6 respectively, each of which consists of a shared Qual-Aspece Collaborative Attention (DAC-Att) sub-layer and an independent feed-forward network (FFN) sub-layer. DAC-Att takes both sets of embeddings imput and then outputs their respective enhanced embeddings, i.e., NFEs {h] N and PFEs {g J Each sub-layer followed by skip connection 30 and layer normalization 31 as same as the original Transformer.
( LN h4 + FFN 1 (1A) , -MLLL (11-3) + =.
(11) (LN(A.
(5)
9 LN + + (d.) . LL( (1-1) (e + g.!0)
LN
(6)
DAC-Att. The DAC-Att sub-layer enhances each set of embedding from its own aspect, while leveraging attention correlations from the other aspect to achieve the synergy. Given the two sets of embedding (h, [ and f9, 1 we first compute the self-attention correlation from both aspects,
1 -1 (s:W9) (g)W"")
Vdk (w) (hy
2 = Vdle
(7)
where independent matrices W A W& and W E Rddimxdd are used to calculate queries and keys. The obtained correlations are further normalized to ātt and ai via Softmax. Note that the correlations are computed from their own aspect, which eliminates possible noises and conduces to correctly describe the incompatible node pair relationships in different aspects of VRP solutions.
We then exploit a cross cross-aspect aspect referential attention mechanism, which allows computed correlations to be shared between each other, as additional references for both contradistinetion and collaboration,
out = Concat
Σ a (K, Eai Why
(8)
N Σ
N ati (gj Whrer
out = Concat
a (g3 W)) >at
where WY, WV E didimd, are trainable parameter matrices for formulating values in each aspect; and Vief wher E RRdimxd. are parameter matrices for each aspect to generate referential values. We finally use the multi-head attention to get NFEs h and PFEs as follows,
hr. = DAC-Att (WQ, W WV W WO),
(10)
h4 = Concat head 1, head h i.m Wh 9. Concat [head] 1 head m.m W.
where head,, = out head? 1 = out! A. and W WO E 1R Xdim are trainable parameter matrices. In our model, we adopt m = 4 and d2 d = 16.
FFN. Our FFN sub-layer has only one hidden layer with 64 hidden unites and adopts the ReLU activation function. The parameters of FFN, and FEN, are different for each group embeddings.
4.3
The decoder
(L) N In the DAC decoder, the two sets of embeddings (1(2) y and {g. Ji=1 are first passed through a Max-pooling sub-layer and multi-head compatibility (MHC) sub-layer independently generate diversified node-pare pair selection proposals from their own aspect, which are then aggregated through a feed-forward aggregation (FFA) sub-layer for output.
We omit the encoder index / for better readability.

---

Max-pooling. For each set of embeddings, we adopt the max- max-pooling sub-layer in Wu et al. || to aggregate the global representation of all N embeddings into each respective one
MHC. The compatibility sub-layer computes the attention correlations for each embedding pair, where the obtained correlations with size N N will be deemed as a proposal distribution for node pair selection. Our correlations are computed based on multiple heads for diversity. And we calculate separated attention score matrices Y Y RR x (of head k) from the two aspects independently. Accordingly, the action distribution proposals would be different due to their aspect-specific focus and cognitions of the current solution, which will provide the subsequent FFA layer with rich pool of proposals and allow our model to be more flexible and robust.
FFA. Once all proposals from two aspects are collected, FFN with four layers (dimensions are 2m, 32, 32 and 1, respectively) and ReI.U activation is used to aggregate them,
Y FFA (Y)), Y s.mm 4.j.1 (.j.m)
YA
Y.h
(11)
where m = 4 is the number of heads; and the output Yr, is a scalar indicating the likelihood of selecting node pair (i:j) as an action. Afterwards, we apply Yiz- = C' Tanh(Yy,) with C = 6 to control the entropy, and mask 7 the infeasible node pairs (i', j") Yey- =o0 Lastly, the likelihoods are normalized using Softmax function to obtain the final action distribution P.,.
4.4 Reinforcement learning algorithm
We adopt the proximal policy optimization given in Appendix C. and design a curriculum learning (CL) strategy for better sample efficiency.
32 with n--tep return estimation for training (details
Curriculum learning strategy. The strategy in Wu et al. [I]] sets maximum of Ttrain steps for training and estimates future returns by bootstrapping [33]. However, due to the concern of training cost, Trrain is usually much smaller than actual T for inference (c.g.. 200 v.s. 10k), which may leave the agent a poor chance of observing high-quality solutions (states) during training. Consequently, may cause high variance for bootstrapping because the value function is mostly fitted low-quality solutions and may render it less knowledgeable in estimating long-term future returns accurately. In this paper, tackle this issue by simple yet efficient strategy which gradually prescribes higher-quality solutions as the initial states for training. In doing so, 1) it increases the probability for the agent to observe better solutions and thus reduce the variance of the value function; 2) it increases the difficulty of the learning task (higher-quality solutions are harder to improve) in a gradual manner and achieves better sample efficiency [34). In practice, those higher-quality solutions can be easily achieved by improving the randomly generated ones using the current policy for a few Tinit steps, where Tinst could be slightly increased as the epoch grows.
5 Experiments
We evaluate our DACT model on two representative routing problems, i.e., TSP and CVRP 5 For each problem, we abide by existing conventions to randomly generate instances on the fly for three sizes, i.e., = 20, 50 and 100. Initial experiments with three operators including 2-opt, swap and insert show that 2-opt performs best for both TSP and CVRP (with insert better than swap), hence we use randomly generated
we report results of our method based on 2-opt. Following 44] [ 27] initial solutions for training and the solutions generated by the greedy algorithm for inference. Since each problem has its own constraints and node features, we adjust the input, feasibility masks, and problem-dependent hyperparameters for each problem, the details of which are provided in Appendix Dannd E The DACT is trained and tested on a server equipped with TITAN RTX GPU cards and Intel 19- 10940X CPU at 3.30 GHz. Our code in PyTorch are available here 8
'E.g., for h, h; = 1: (2) ( max
(h.
(4) N ===l
WiGloial, where W/ Wegeal,WGlloo 646464 are parameters.
Besidess, we also mask all the diagonal elements since they are not meaningful to the pair-wise operators. and the node pair selected at the last step to forbid possihle dead loops
DACT
7

---

Table 1: Comparison with various baselines on TSP and CVRP.
N=20
N=50
N=100
Method
Ohj.
Gup
Time
Obj.
Cup
Time
Obj.
Gap
Time
Concorde
3.83
(3m)
5,70
(10m)
7.76
(Ih)
I.KH
3,83
0.00%
(38c)
5,70
0.00%
(5m)
7.76
0.00%
(20m)
OR-Tools
3,86
0.94%
(42s)
5,85
2.87%
(5m)
8,06
3.86%
(23mn)
Neural-2-Opt 23
3.84
0.00%
(15mi)
5.70
0.12%
(29m)
7,83
0.87%
(41m)
Wa (T=5k)
3,83
0.00%
(1h)
5,701
0.20%
(1.5h)
7,87
1.42%
(hh
DACT (T=
3.83
0.04%
(24)
5,70
0.14%
(Imm)(Im)
7.89
1.62%
(4& (44))
TSP
DACT (T=Sk)
3,83
0.00%
[32x] (2m)
5.70
0.02%
(2m (6m)
7,81
0.61%
44m (186 188)
DACT (T=10k)
3.83
0.00%
(1m)(5m)
5.70
0.01%
[3m] 133))
7.79
0.37%
(8m y (40m))
DACTx4 augment
3,83
0.00%
(3mm))0m)
5,70
0.00%
(10m)(h)
7.77
0.09%
(29m (22.5))
GCN-BS [
3.84
0.01%
(12m)
5,70
0.01%
(18m)
7,87
1.39%
(40m)
AM-sampling
3.84-
0.08%
(5m)
5.73
0.52%
(24m)
7,94
2.26%
(Ih)
MDAM-BS
3.84
0.00%
(3m)
5,70
0.03%
(14m)
7.79
0.38%
(44m)
POMO 8
3.83
0.04%
(1s)
5,70
0.21%
(24)
7,80
0.46%
(1ss)
POMOx8 augment
3.83
0.00%
(3s)
5.691
0.03%
(166)
7.78
0.15%
(Im)
DPDP (100k) 26
7,77
0.00%
(3h)
Cpt DE
13
0.00% *
11m
0.02%
22m
0.34%
55m *
LKH
6.14
0.00%
1h
10.38
0.00%
4h
15:68
0.00%%
8h
OR-Tools
6.46
5.68%
2m
11.27
8.61%
13m
17.12
9.54%
NeuRewriter
4
6,15*
6m
10.51
11m
16. 16.10*
17m
NLNS (2
6,19*
6m
10.54
11m
15,99*
16m *
Wa 11 (Tw5k)
6.12
0.39%
(2h)
10.45
0.70%
(4h)
16.031
2.47%
(Sh)
CVRP
DACT (T=lk)
6.15
0.28%
(36s)(33))
10.61
2.13%
(43x
16.17
3.18%
(2m) (5m)
DACT (T=5k)
6,13
40.00%
(mm/33)
10.48
1001%
33 (8m)
15:92
1.55%
(8m) (2m))
DACT (T=10k)
6.13
-0.04%
(2m)(6m)
10.46
0.79%
[6m)
15.85
1.12%
(16m](45m)
DACT augment
6,13
-0.08% %
(lmmm33m)
10:39
0.14%
(32m1(1.5h) Sh)
15.71
0.19%
(1.5h)(4,5h)
AM-sampling S
6.25
1.87%
(6m)
10.62
2.40%
(28m)
16:23
3.72%
(2h)
MDAM-BS
6,14
0.18%
(5m)
10:48
0,98%
(15m)
15.992
2.23%
(1h)
POMO X
6,17
0.82%
(ls)
10.49
1.14%
(4s)
15.83
0.98%
(19)
POMO X8 sugment g
6.14
0.21%
(5s)
10.42
0.45%
(26x)
15.73
0.32%
(2m)
DPDP (100K)
15.69F
0.31%
(6h)
CVAE Opt. DE 13
6.14
21m
10.40
41m
15.75
1.5h*
the obj. values, gaps or time are obtained based on 2,000 instances in their original papers, and not directly comparable to ours.
I the obj. values ohtained by Comcorde I.KI KK may he slightly different from since the 10,000 instances randomlly generated. E. for TSP50, the optimal values according our running of Concorde 5,70, while 5.69 POMO and ea thus focus more on gaps.
5.1 Comparison studies
In Table 1. compare our DACT with, (1) learning based improvement methods, including Wu
et al. III. Neural-2-Opt (23 (TSP only), NeuRewriter 4 (CVRP only). NLNS [27] (CVRP
only), (2) learning based construction methods, including AM-sampling 131. GCN-BS 66 (TSP
only). MDAM-BS 77, POMO 8 (3) conventional optimization algorithms equipped with learning based component(s), including DPDP 26), CVAE-Opt-DE DE [13. and (4) strong conventional solvers including Concorde [35]. LKH 28 36 and OR-Tools (37. Though L21 [12] can outstrip LKH on CVRP, we do not inlude it as a baseline since it requires prohibitively longer inference time than other J All results are averaged over 10,000 randomly generated instances unless specified otherwise (e.g., the ones marked with # only infer 2,000 instances), and we report the metrics of objective values, (optimality) gaps and run time. Regarding baselines, we follow the results reported in their original papers, which may not include all the three metries. For TSP, Concorde is adopted to get the optimal solutions, based on which the optimality gaps of other methods are calculated. CVRP harder to be solved optimally, and the gaps are calculated based on solutions of LKH. Note that even for the baselines which infer 10,000 random instances, their objective values might be slightly different from ours (e.g., the ones marked with t), therefore we focus more on gaps for fair comparison. The run time is also hard to compare due to various factors (e.g., GPU/CPU models, batch sizes, Python v.s. C++). For DACT, we report the time for inferring all 10,000 instances with multiple GPU cards in "O", and a small batch (512 instances) with one single GPU card in "()".
Pertaining to TSP, our DACT with inference step limit of 5,000 (T=5k) outperforms the traditional solver To-lools and all improvement models in terms of optimality gap, including Wu et al. (I] which directly adopted the original Transformer encoder. It also outstrips construction methods
L21 needs 167 days for 10,000 CVRP100 instances, as estimated from 24min/instance in its original paper.
8

---

Table 2: Generalization performance. (a) DACT v.s. baselines on benchmark datasets (up to 200 customers, see Appendix E.4 for detailed results and discussion); (b) PE v.s. CPE on different sizes.
Method
TSPLIB
CVRPLIB
N=20
N=100
Method
OR-Tools
37
3.34%
8.06%
Obj-
Gap
Obj.
Gap
AM-sumpling
22.83%
26.66%
DACT-PE (T=5k)
3.84
0.21%
8.38
7.93%
POMO
8
10.06%
6.10%
DACT-CPE (T=5k)
3.83
0.10%
7.99
2.98 %
Wu al. DACT
M
4.17%
5.20%
Wu ct al. M (T=5k)
3.91
2.14%
9.03
16.37%
2.07%
3,41%
OR- Toolsols 37
3.83
0.00%
8.06
3.87%
(a)
(b)
Table 3: Dual v.s. single aspect representation
Steps
Method
# Params
N=50
N=100
SA-T
0.37M
0.35% (1m)
3.49% (3m)
T=lk
DACT
0.29M
0.14% (Im)
1.62% (4m)
SA-T
0.37M
0.05% (5m)
1.55% (16m)
T=5k
DACT
0.29M
0.02% (6m)
0.61 % (18m)
including AM-sampling and GCN-BS on TSP100. With larger step limit T=10k, our DACT further boosts the solution qualities and outperforms other construction methods including MDAM-BS (beam search), and POMO (the current state-of-the-art). To further reduce the gaps, we also leverage the data augmentation technique in POMO (which considers flipping node coordinates without changing the optimal solution) to solve same instances multiple times in different ways. Although the inference time increases (we run data augmentation in serial on the same GPUs), our DACT with 4 augments not only outstrips POMO with 8 augments but also achieves the lowest objective values and gaps among all purely learning based models. In particular, our method almost optimally solved TSP20 and TSP50 with gap lower than 0.005%, and 0.09% on TSP100, which superior to most of the recent neural solvers. Pertaining to CVRP, our DACT with T=5k produces lower gaps than that of improvement models including NeuRewriter and NLNS. It also performs much better than Wu et al. III except on CVRP50. With T=10k and 6 augments 10 our DACT exhibits even better performance than the highly specialized heuristic solver LKH on CVRP20 and delivers the smallest gap of O. 19% on CVRP100 against other neural solvers including POMO with 8 augments. Besides, our DACT is also competitive to DPDP which leverages learnt heatmap and dynamic programming to search solutions. Though DPDP (100k) can solve TSP100 instances almost optimally, our DACT is more efficient than DPDP on CVRP100. Compared with CVAE-Opt-DE despite that it is averaged over fewer instances and integrated with differential evolution, objective values are still lower.
In terms of the inference time, our DACT is highly competitive against all neural solvers except POMO which learns a construction model by sampling diverse trajectories. However, when it comes to the generalization performance on benchmark datasets, i.c., TSPLIB (38 and CVRPLIB [39] in Table a). DACT produces significantly lower average gaps than the POMO with 8 augments, which indicates that our DACT is more advantageous in practice despite its longer inference time. On the other hand, it is possible to adopt similar diverse rollout strategy for DACT to find better solutions earlier, or explore other model compression techniques such as the knowledge distillation [40] to learn lighter DACT model for faster inference. Since our focus is to ameliorate Transformer for neural improvement solvers, we will investigate these possibilities in the future.
5.2 Ablation studies
Dual-aspect representation. In Table we evaluate the effectiveness of our dual-aspect represen- tation against the single-aspect one (SA- -S-TT on TSP50 and TSPI00, where SA-T mainly follows the Transformer in Wu et al. (TT) but equipped with the CPE, multi-head attentions and CL strategy for fair comparison. We observe that our DACT with fewer parameters consistently outperforms SA-T, which verifies the effectiveness of the dual-aspect representation.
The gap will further decrease 0.09% we adopt 8 augments, with run time of about 7h.

---

TSP20 Policy tested on TSP20 (PE)
TSP20 Policy tested on TSP50 (PE)
TSP20 Policy tested TSP20 (CPE)
TSP20 Policy tested on TSP50 (CPE)
10
20
20 15 10
30
30
50 40
40
10
20
30
40
10
15
20
50
10
20
30
40
50
(a)
(b)
Figure 6: Visualization of the attention scores for the encoder when trained model is used to solve
instances with a larger size. (a) using PE method; (b) using CPE method (ours).
Cyclic positional encoding. Here show that CPE significantly improves the generalization performance across different problem sizes. In Table (b), we record the results of our DACT with PE and CPE, and Wu et al. [1I], when the model trained on TSP50 is di- rectly used to solve instances from TSP20 and TSPI00 with T=5k. We see that even with PE, our DACT out- performs Wu et al. M. Further equipped with CPE, DACT outstrips DACT-PE and OR Tools on TSP100. We continue to compare the two DACT variants by visualizing their attention scores. As depicted in Fig- G a). although the absolute PE is designed for linear sequences, did attempt to capture the circularity of VRP solutions (as highlighted in the green boxes) after training. However, the ability to perceive such properties significantly drops when generalizing over different problem size, which instead engenders random attention scores when generalizing to larger size (see right side of Figure/6 (a)). In contrast, our DACT with CPE is able to capture the circularity as depicted in Figure ((b), which verifies the effectiveness of CPE in representing cyclic sequences (i.e., VRP solutions).
6.6
PPO
PPO+CL
Objective Value
6.5
6.4
6.3
6.2
25
50
100
Epoch
Figure 7: Training curves of PPO with and without CL on CVRP20 (random seeds 1-5).
Curriculum learning (CL) strategy. In Figure we plot the training curves of PPO algorithm with and without our CL strategy, where the results are averaged over 5 independent runs with 90% confidence intervals. shows that our CL strategy significantly improves the sample efficiency while reducing the variance of training, which aligns with our analysis in Section 4.4
6 Conclusions and future work
In this paper, present novel DACT model for routing problems. It learns separate groups of embeddings for the node and positional features, and is equipped with cyclic positional encoding (CPE) to capture the circularity and symmetry of VRP solutions. A curriculum learning (CL.) strategy also exploited to improve the RL training efficiency. Extensive experiments on both synthetic and benchmark datasets justified the effectiveness of DACT in terms of both inference and generalization. potential limitation is that DACT more useful for learning improvement models at present. In the future, we will investigate how extend DACT to construction models, and how speed up the DACT through diverse rollouts or model compression techniques. It is also interesting to apply the proposed CPE to develop Transformer based model for other tasks where the cyclic property is also important, e.g., encoding circular DNA/RNA structures in computational biology [41 42)
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China under Grant 61803104 and Grant 62 62102228, in part by the Young Scholar Future Plan of Shandong University under Grant 624200899641 88, and in part by the * CyberPhysical Production System (CPPS) Towards Contextual and Intelligent Response Research Program, under the RIE2020 IAF-PP Grant A19C1a0018, and Model Factory @ SIMTech.
10

---

References
[1] Paolo Toth and Danicle Vigo. Vehicle routing: problems, methods, and applications. SIAM press, 2014.
[2] Michael Schneider, Andreas Stenger, and Dominik Gocke. The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48(4):500-520, 2014.
[3] Jan Karel Lenstra and AHG Rinnooy Kan. Complexity of vehicle routing and scheduling problems. Networks, 1 112)2221-227, 1981.
[4] Xinyun Chen and Yuandong Tian, Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, pages 628 6281-6292, 2019.
[5] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
[6] Chaitanya K Joshi, Thomas Laurent, Xavier Bresson. efficient graph convolutional network technique for the travelling salesman problem. arxiv preprint arxiv:1906.01222 ArXiV, 2019.
[7] Liang Xin. Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of 35th AAAI Conference on Artificial Intelligence, pages 10422-1249, 2021.
[8] Yeong-Dac Kwon, Jinho Choo, Byoungjip Kim, Iijon Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Newral Information Processing Systems, volume 33, pages 21 1188-1199, 2020.
[9] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Transactions on Industrial Informaties, 17(7):8861 1871, 2020.
[10] Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pages 1621-1632. 2020.
[11] Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. I.F.F Transactions on Neural Networks and Learning Systems, 2021.
[12] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2019.
[13] André Hottung, Bhanu Bhandari, and Kevin Tierney. Learning a latent search space for routing problems using variational autoencoders. In International Conference on Learning Representations, 2021.
[14] Jingwen Li, Yining Ma, Ruize Gao, Zhiguang Cao, Andrew Lim, Wen Song, and Zhang. Deep rein- forcement learning for solving the heterogeneous capacitated vehicle routing problem. IEEE Transactions on Cybernetics, 2021.
[15] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[16] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30, pages 6000-6010, 2017.
[17] Jingwen L.,, Liang Xin, Zhiguang Cao, Andrew Lim, Wen Song, Jie Zhang. Heterogeneous attentions for solving pickup and delivery problem via deep reinforcement learning. IEFE Transactions on Intelligent Transportation Systems, 2021.
[18] Guolin Ke, Di He, and Tie- Yan Liu. Rethinking the positional encoding in language pre-training. In International Conference on Learning Representations, 2020.
[19] Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 464-668, 2018
[20] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, pages 2692-2700, 2015.
[21] 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.

---

[22] Mohammadreza Nazari, Afshin Oroojlooy. Martin Takáč, and Lawrence V Snyder. Reinforeement learning for solving the vehicle routing problem. In Advances Neural Information Processing Systems, pages 9861-9871, 2018.
[23] 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, 2020.
[24] Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms graphs. In Advances in Neural Information Processing Systems, pages 6351-6366 2017.
[25] Zhang-Hure 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.
[26] Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. arXiv preprint arXiv:2102. 11756 2021.
[27] André Hottung and Kevin Tiemney. Neural large neighborhood scarch for the capacitated vehicle routing problem. European Conference on Artificial Intelligence, 2020.
[28] Keld Helsgaun. LKH-3 (version 3.0.6), 2019. URL http:://eebooteef..ruu LKH-3/
[29] Wikipedia. Gray code, 2021. URL: 2020/05/19.
Last visited on
[30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[31] Lei Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization Corr: abs/1607 160706600065 ArXiV, 2016.
[32] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arxiv preprint
ArXiV, 2017.
[33] Fabio Pardo, Arash Tavakoli, Vitaly Levdik, and Petar Kormushev. Time limits in reinforcement learning. In International Conference on Machine Learning, pages 4045-4054, 2018.
[34] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, International Conference on Machine Learning, pages 41 41448, 2009.
Jason Weston, Curriculum learning. In
[35] David L Applegate, Robert E Bixby, Vašck Chvátal, and William J Cook. Concorde TSP Solver, 2020. Utt/htt:://wwwt math. wwaterloo. ca/tap/concorde/
[36]
Keld Helsgaun. LKH (version 2.0.9), 2018. URL LKH/
[37] Laurent Perron and Vincent Furnon. OR-Tools (version 7.2), 2019. URL httphattpe://eveeppprre..oo
com/ ott.ommatiiioo////
[38] Gerhard Reinelt. TSPLIB-A traveling salesman problem library. ORSA journal on computing, 3(4): 376-384, 1991.
[39] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi. Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal Operational Research, 257(3)885--88, 2017.
[40] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint 523.5513 2015.
[41] Chun- Chun-Ying Yu, Tung-Cheng Li, Yi-Ying Wu, Chan-Hsien Yeh, Wei Chiang, Ching Yu Chuang. and Hung-Chih Kuo. The circular maa circbircó participates in the molecular circuitry controlling human pluripotency. Nature communications, 8(1):1-15, 2017.
[42] Chengyu Liu, Yu-Chen Liu, Hsien-De Da Huang, and Wei Wang. Biogenesis mechanisms of circular ma can be categorized through feature extraction of machine learning model. Bioinformatics, 35(23)4487-4870 2019.
[43] Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Firdaus Janoos, Larry Rudolph, and Aleksander Madry. Implementation matters in deep policy gradients: A case study on PPO and TRPO. In International Conference on Learning Representations, 2020.
12


Reviews:
[{"review_id": "GivArsGMGPU", "reviewer": "Reviewer_wmXs", "summary": "The paper proposes a new algorithm for solving the traveling salesman problem and capacitated vehicle routing problem by learning embeddings for the node and positional features separately. The algorithm uses a cyclic positional encoding method (CPE) to characterize the geometric properties of VRP solutions and designs a curriculum learning strategy to improve the sample efficiency. The experiment results show that for TSP and CVRP the proposed algorithm outperforms existing Transformer-based improvement models.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Originality: There are two contributions in this work:\n1) Learning node and position embedding separately to decrease potential noises,\n2) Using the cyclic positional encoding method to handle the circularity and symmetry of VRP solutions,\n\nwhich I think are novel and interesting. \n\nQuality: The paper is solid. Authors provide both synthetic and real data experiments with detailed analysis.\n\nClarity: The paper is clearly written and easy to follow.\n\nSignificance: This paper proposes a new embedding method to efficiently handle the circularity and symmetry of VRP solutions. The experiments show that the proposed algorithm achieves a better objective value than existing Transformer-based improvement models. However, this algorithm still cannot beat LKH and another baseline [1]. Meanwhile, the computational time seems a bit longer compared with [2] as they have almost the same performance. \n\n[1] Lu, Hao, Xingwen Zhang, and Shuang Yang. \"A learning-based iterative method for solving vehicle routing problems.\" International Conference on Learning Representations. 2020.\n\n[2] Kwon, Yeong-Dae, et al. \"POMO: Policy Optimization with Multiple Optima for Reinforcement Learning.\" Advances in Neural Information Processing Systems 33, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Here are some other comments:\n1) The paper shows that CPE captures the cyclic and similarity properties of TSP well (Figure 4). The experiment results demonstrate that the model can also solve the CVRP in relatively good quality. However, we know CVRP has cyclic and symmetric properties within each sub-route. It would be helpful if you can provide some intrinsic illustrations as you did in Figure 4 to show that the structure proposed is also able to deal with the circularity and symmetry of the sub-route for CVRP. If not, do you have any additional ideas to improve the model? \nWhat concerns me is whether the model can be generalized well to more complicated problems such as CVRPTW, which have more geometric properties.\n2) When applying CPE, the dimension of the input becomes rather large. It can adversely impact the computational efficiency of the model. Does it potentially constrain the scalability of the model, especially when we need to deal with large-scale problems?\n3) For CVRP, the pairwise operator does not always result in a feasible solution. How does the model handle such a situation?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "DpI-2oHhdyH", "reviewer": "Reviewer_YbAL", "summary": "This paper introduces a novel architecture for solving the VRP. After illustrating the issues concerning the positional encoding for VRP, this paper introduces an alternative feature representation called CPE which captures the circular dependencies of the VRP. By using this new feature extraction and a specially designed Transformer network to encode the information of nodes and sequences, they show that their method is the best among the baselines and can \"solve\" VRP to close-to-optimality in a short amount of time. I like the main idea of the paper and how all components are designed to work in synergy. It is very clearly written and easy to follow. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This paper includes comprehensive illustrations, ablations studies, and detailed experiments setup discussions, so it does not allow many questions. I do have a few questions/comments to further make this work better:\n\n1) It is not clear what the N nodes demonstrate in this paper in Section 3. While reading the main body, I was thinking that the depot is one of those N nodes, but from line 558 of the Appendix, it appears that the depot is the node with ID N+1. \n\n2) At the algorithm improves the solutions, there might be fewer routes (or vehicles) necessary to satisfy the demands. It is not clear how the algorithm is able to reduce the number of routes. Can you elaborate on this?\n\n3) Another question about the depot. How the location of the depot is going to affect the solution? It looks like that there is no information on the depot is used during the training. This needs to be clarified as it is not obvious how decisions to visit the depot are determined. \n\n4) What will happen in figure 3 if the number of nodes is not a power of two? How we can make sure that the first and last nodes in the gray code are adjacent (different in one digit)? I suggest using the same TSP20 example that you used in Figure 4 to illustrate how this coding works.\n\n5) My next question is about the reward computation. When you defined the reward in Section 3, I was thinking that you have a fixed set of problems (it can be millions of them) and then you have a record of what is the best-observed reward for every specific problem during the training. I thought that is how you get $D(\\delta^*), but based on the explanation in Section 5, you generate sample problems \"on the fly\".  I am wondering how you compute this quantity. \n\n6) There is an argument in line 270 which says \"which are shorter than those reported in [10]\". I have some doubts about this. Since your model is much larger than [10], how can this happen? Do you have any justification? Or, that is simply due to efficient implementation and parallelism?\n\n7) Why L2I is not included in your baselines? Even if it takes some time, it is the SOTA of learning-based methods so far (as far as I know). \n\n8) You have argued that other operators are not as good as 2-opt. It would be informative to have an ablation study on how changing the improvement operator affects the results.\n\n\nOther comments:\n* It needs to be clarified what are the \"preset pairwise operators\" in Line 113.\n* In the description of Figure 1, instead of using vague terms like \"original one\" and \"ours\", you could cite the work that considers (a) and also use the name of your framework (DACT).\n* Do you mean state transition in Line 129 (instead of transient)?\n* In Figure 2, I think matmul (not matmal) is the is a most common way to denote a matrix multiplication. Also, about the operations after softmax (before concat and linear project), are they matrix multiplication or just a scalar times vector? If the latter is correct, you may use \"mul\" instead of \"matmal\".\n* This is very minor, but I am wondering why you report the cumulative time for 10000 problems. It makes more sense to me to know what is the expected time to solve a random problem using a method. \n* Why did you introduce new notation $pe_i$ instead of g_i inf Appendix A?\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "A97XmbXNJ-", "reviewer": "Reviewer_rrox", "summary": "The authors introduce three new ideas for the solution of vehicle routing problems. The first is to separate the positional encodings of nodes (in terms of position in a tour) from other node features, such as customer demand or absolute position. For the positional encoding they introduce a handcrafted feature embedding, which they show exhibits cyclic and reflectional symmetry. The second idea is a “dual-aspect collaborative transformer”, which is a pair of attention modules, acting on the positional encodings and node features separately, where the attention weights from the one module can be applied to the value-embedding of the other and vice versa. The third idea is to use curriculum learning in the training process, so that high-quality solutions are also contained in the training set. \n\nThe results are competitive with SOTA.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "I would like to thank the authors for an interesting read.\n\nMy review is marginally below accept because while the methods seem to be new and are competitive, the paper is very hard to read and it is not very clear how or why the methods work from the text. I look forward to the rebuttal, which will hopefully clear up some of the misunderstanding for me.\n\n- Originality\n\nI found the work to be original for the given context. The innovations were as follows: \n\n1) the introduction of a handcrafted feature\n2) a new kind of attention mechanism (DACT)\n3) the introduction of curriculum learning to the solution of combinatorial optimization problems\n\n- Quality\n\nWhile the results are appealing, and the methods are new in this context, I think the major drawback of this work is the presentation. The motivation of why the positional and node features should be separated is unclear. It appears that the arguments for doing this may even been a bit obscure to the authors. That’s fine, but I would like to see the text contain some clarity as to what appears to be a pure empirical finding.\n\nAblation studies are carried out, which confirm the effectiveness of the dual-aspect representation, cyclic positional encodings, and the curriculum learning. This is nice to see and increases the quality of the work.\n\n- Clarity\n\nI found the manuscript readable, but in certain areas quite difficult to understand, owing to the use of terminology, which had hitherto not been defined. It may be advisable for the authors to have the submission checked for readability and grammar.\n\n- Significance\n\nThe results appear to be good, in comparison to other methods. That said, it appears that one relevant work in missing. “Deep Policy Dynamic Programming for Vehicle Routing Problems” by Kool et al. (2021) (released February) reports 0.004% optimality gap on TSP100 and -0.127% gap on CVRP with respect to LKH. These numbers are better than the submitted paper, which reports 0.09% and 0.19%, respectively. Nonetheless, the reported numbers are highly competitive.\n\nIn terms of ideas, I think the use of curriculum learning is something I have not seen in the context of combinatorial optimization, which makes a lot of sense, thus this is novel. As to the use of the feature embedding and the DACT, these are also novel. The feature embedding is reminiscent of methods from the equivariance literature.\n\n\n- Questions and suggestions for authors:\n\nLine 36: what is meant by “it can bring mixed correlations and induce noisy biases in the self-attention module”. This sentence is vague for me\n\nSection 2, Positional encoding in Transformer: It may be useful to explain to the reader the relative [17] and united [16] PE methods in more detail, perhaps including mathematical descriptions. This would underscore your contribution better, I feel.\n\nLine 140: I would like a concrete explaination/description/definition of an ‘aspect’.\n\nLine 142: What is ‘correlation noise’?\n\nSection 4.1 PFEs: What is the motivation to choose this particular embedding. Are there other positional embeddings, which would also exhibit cyclic/reflection symmetry?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not included limitations of their work. I think they should address issues of scalability (attention scales quadratically in number of cities), speed (it is still slower than some classical commercial tools), and ease of adapting this framework to new versions of routing problems, such as non-Euclidean/asymmetric TSP.", "review_text": "", "extra_scores": {"ethical_concerns": "I see no ethical discussion in the paper, I think the authors should include the impact that solving routing problems has on society.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "5kAHYro_AC", "reviewer": "Reviewer_9zdA", "summary": "Simply, this paper adds the following to an existing paper titled \"Learning improvement heuristics for solving routing problems\" [Ref 10]. \n\n1. Dual aspect representation: a typical neural architecture is converted to a dual. Problem encoding and its solution (the order of routing) encoding are separately done\n2. Cyclic positional encoding\n3. Curriculum learning", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "\nIn Figure2: DAC Decoder output, P_1N is misrepresented by P_11.\n\nOne of the strong points of the paper is that node embedding and positional embedding can be mixed (the Transformer arch.). For a routing problem, the standard benchmark results prove a good performance. Taking a simplistic neural architecture, the authors achieve new state-of-the-art  for the benchmark TSP and CVRP problems. Particularly, for CVRP-20, the proposed approach beats LKH.\n\nCyclic positional encoding is useful for cyclic routing problems, although, for more general routing problems can't be helped as much. \n\n241: in curriculum learning strategy, the authors should elaborate more in \"gradually prescribes higher-quality solutions as the initial states for training.\" (Appendix D has detailed explanations, but the main content should explain the key idea and why. \n\n287: why need to record time for the case of multiple GPU card? Isn't recording single GPU time fair or not?\n\nIn Table 1, an existing approach by Wu et al. [10] and new model performances are compared. Why for using the same 1 GPU the inference time differences are significant? \n\nIf the authors conduct an ablation study and include, the paper will get better.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper focuses on the architecture of neural end-to-end combinatorial optimization methods for routing problems like the TSP and the CVRP. The authors propose two improvement to the encoder of such problems: (1) encoding the node features and position features separately, which results in better behavior of attention scores and (2) using a cyclic positional encoding, that better capture symmetries of VRP solutions. 

The reviews on the paper are mixed. Only one reviewer recommended reject, this reviewer did not react to the author's reply or the other reviewer's arguments. Keeping this in mind, I'd summarize the opinion of the reviewers as follows: 
- Originality: Most of the reviewers found the methods to be novel and interesting, although the core method stays close to the established framework of e.g. [10]. 
- Technical quality: One reviewer mentions the quality is solid. The reviewers seem mostly satisfied about quality, too. One reviewer explicitly mentions the detailed ablations. 
- Significance and Relevance: The topic is relevant to the NeurIPS community. The reviewers characterize the results slightly differently, from 'best among baselines' and 'new state of the art' to 'competitive with baselines'/'doesn't beat baselines convincingly'. However, except from the overall quality, the authors study the generalization of the method to larger problems, which does seem convincingly better than that of competitor methods. Since scaling is a major obstacle for neural combinatorial optimization methods, this is a significant benefit. 

Overall, I consider the paper to close to the borderline, however, I think the generalization results are quite interesting for the NeurIPS audience and as such I would recommend acceptance. 

Decision: Accept (Poster)