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": "ta2_AKgNtB", "reviewer": "Reviewer_25wv", "summary": "This paper proposes an improved Transformer-like architecture to learn an improvement heuristic for the Travelling Salesman Problem (TSP) and Vehicle Routing Problem (VRP). It proposes a special form of positional encoding that represents the cyclic structure of a current solution and proposes to learn separate embeddings for 'node' and 'positional' features (in each layer) which only exchange information through an attention matrix. It uses a PPO algorithm with a curriculum learning strategy. Experiments on TSP and VRP with up to 100 nodes show reasonable performance compared to existing alternatives.\n\nWhile the paper presents an improvement to the results for TSP and VRP, in my opinion it is too incremental to be accepted in its current form, as it largely reuses existing architecture and experimental setup, but with improved positional encodings/embeddings and a simple curriculum learning strategy. It is unclear how the proposed improvements (which share some similarity with United Positional Encoding) can generalize to other problems or how this will affect the ability to solve larger instances, which I think should be the main goal of this line of research, as the current SOTA is not yet competitive with alternative methods. Given the quality of the work I encourage the authors to continue but I think the paper should be improved to show this potential before it can be accepted.", "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": "Originality\n\nThe paper is somewhat incremental as it can be seen as making certain specific improvements to an existing setup (learning to solve routing problems by an improvement heuristic using transformers). Specifically, the improvements made are the 1) using cyclic positional features, 2) separate embeddings for positional and node features (somewhat related to United Positional Encoding) and 3) using PPO with a simple curriculum learning strategy.\n\nClarity\n\nThe paper is quite clear and well written in general, although I find that it should balance the amount of space dedicated to different topics. Much space is used to describe the cyclic positional encoding and equations relating to the 'standard parts' of the transformer architecture (multi-head attention and feed forward layers), whereas to understand the proposed method I would find it much more helpful if the pseudocode in the appendix D was included in the main paper, as well as the description of the '2-opt' operator (reversing the segment between selected nodes i and j), which are crucial details of the used methods.\n\nThe Figures are a bit scary to look at at first sight and could be simplified possibly, but are very helpful in understanding the architecture, positional encoding, etc.\n\nQuality\n\nThe work is technically correct and well-motivated. The experiments are well-conducted and carefully reported to deal reasonably with differences between evaluations of different methods. They support the claim that the architecture outperforms existing improvement models, although this should not be mistaken for 'outperforming VRP' or neural VRP, in which case POMO is a reasonably simple and strong baseline. To give a better picture of where it stands, it would be good to report full performance vs time curves against some of the strongest baselines, which can be easily obtained by running with a different number of iterations.\n\nSignificance\n\nThe results push the boundary for learning improvement based heuristics for VRP which is promising. However, I consider the main contribution the architectural improvement as using PPO with a curriculum learning strategy is rather straightforward. While promising, it is unclear how these generalize to other problems (e.g. when adding time windows, the cyclic property seems to break) or larger instances, which would ultimately be the goal as the method is not yet competitive to VRP. DACT mainly exploits the fact that the input is a (circular) sequence, so I do think it would be good to at least hint at how this could extend to construction heuristics or other problems where solutions are not naturally represented as ordered sequences (e.g. knapsacks).\n\nMinor comments/questions\n\n- Please check spelling (e.g. matmal -> matmul Fig 2.)?\n- Line 288 -> multiple GPU in (.) and single GPU in {.}, I think this should be other way around?\n- Which attention exactly is shown in Fig. 5? Is it averaged over layers?\n- Scrolling past Fig. 5 lags on my PC. If others experience this as well it may be worth saving the images differently for convenience of your e-readers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed in the discussion. I do not see any direct negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "EAy_tPHMQI", "reviewer": "Reviewer_VmAG", "summary": "## Summary\nThe paper proposes an improvement for the Travelling Salesman problem using Transformers to compute positional information. The paper introduces a new architecture to learn separate groups of embeddings for the node and positional features following the encoder-decoder structure; this new architecture is introduced as a Dual Aspect Collaborative Transformer. By separating the node and position embeddings this transformer structure allows for the non deterministic nature of routing tasks. The paper also proposes a cyclic positional encoding method to address the non-linearity of VRPs. The DACT learner is trained using Proximal Policy Optimisation following a curriculum learning strategy in order to address stability issues.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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\nI would classify the originality presented here here in the mid-range. Because even though using transformers for VRPs has been done in the past, this paper splits the information streams, usually encoded together as a key feature for the original use cases, in order to gain flexibility and therefore improving exploration.\n\n## Quality\n* The paper presents clear explanations of any new contributions made; it reads like a complete piece of work but it leaves the reader with a feeling of having expected to see some of the work left for future efforts.\n* I would have liked to see more effort on adding clear introductions about the combination of technologies used and the target problem, aiding readers unfamiliar with them to get setup with constructive knowledge.\n* The paper does have well supported claims.\n\n## Clarity\n* The paper presents the concepts in a clear and well organised manner.\n* More reproducibility details would have been well received by the reader; for instance, a repository containing the code and clear steps for running training and inference.\n* More information needs to be presented on the implementation and training aspects of the PPO learner.\n\n## Significance\nThe results and ideas used here are interesting and valuable. The paper presents an interesting line of work where some more ground can be made to create solutions for TSPs. It's difficult to evaluate if the work presented here advances the state of the art, but it does present a very interesting and novel combination of methods to address a well known and difficult problem.\n\n## References\nA quick google search provided a couple of papers not listed that seem relevant: \n* https://hanalog.polymtl.ca/wp-content/uploads/2018/11/cpaior-learning-heuristics-6.pdf\n* https://arxiv.org/pdf/2010.02068.pdf \\\nIt may be worth scanning for more. \\\nPlease provide details of how this paper relates to those.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "## Limitations\nThe work is clearly focused on a very particular problem. Whether that focus is enough to establish an assertion of its limitations is perhaps a bit subjective.\n\n## Societal impact\nI do not foresee any negative societal impact sourced from this work. It addresses a pretty fundamental problem already present in our daily lives.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "9t9yyhHUBu0", "reviewer": "Reviewer_vqcX", "summary": "This paper addresses the vehicle routing problem. It proposes to learn the embeddings for the nodes and the positional encodings separately, where the positional encoding is learned in a novel cyclic manner. The results show that the proposed dual transformers outperform previous works.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 do not see apparent flaws in this paper. The paper presentation is detailed, the figures are nice, and the results are promising. The ablation studies properly evaluate the contribution of each component.\n\nBuilding on top of [10], this paper makes several solid contributions, yet none of them can be considered groundbreaking.\n\nThere are some minor details not clear to me.\nHow does the proposed model compare to baseline methods in terms of parameters?\nHow does this model generalize to random initial solutions?\nWhat if testing the model with L > 3?\nI believe the g_n^(l) in Figure 2 should be g_N^(l)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see the potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see potential ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "72I9dDo_f3O", "reviewer": "Reviewer_pCD7", "summary": "This paper proposes a few variants to the Transformer model to learn to find solutions for routing problems. There are two main architectural changes: (1) using cyclic Gray codes instead of sinusoidal positional embeddings, and (2) using a two-stream attention function (named Dual-Aspect Collaborative Attention (DAC-Att)) instead of the multihead QKV attention.\n\nThe resulting model is trained with Proximal Policy Optimization (PPO), and is shown to find good solutions to the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP).\n", "questions": "", "limitations": "", "rating": 4, "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 have two main concerns with this paper.\n\nFirst, the contributions seem overly complicated and whether it is necessary to go for such complexity is questionable. For instance, the use of cyclic Gray codes is motivated by the hypothesis that it better encodes the cyclical similarity which is needed when searching for tours, in the case of TSP and CVRP. However, these insights are very specific for these problems. Also, learnable positional embeddings (which is done in many modern Transformer language models), is capable of learning this cyclic behavior as well. If the authors just use learnable positional embeddings, they would not need to introduce the Gray codes. If the authors train with learnable embeddings, and the resulting learned embeddings do not exhibit the cyclic behavior, then maybe the cyclical behavior is not favored in the Transformer. Either way, I feel like the use of Gray codes is not justified.\n\nSecond, while the Dual-aspect Attention (DAC-Att) mechanism is somewhat more justified than the Gray code embeddings, DAC-Att would significantly increase the computational complexity. Perhaps this is the reason why the time stamps in Table 1 for DACT are bad. Other than a slower training and inference time, I think that DACT should compare against methods that have the same computational complexity. If no such method exists (they do), then DACT should still compare to heuristic methods that are allowed to run for more randomized trials in order to account for the complexity differences. Under such circumstances, it is unlikely that DACT will deliver any benefits, which leads to my next point.\n\nThird, the experimental results in the paper are not convincing. In Table 1, DACT lost to many other baselines *under the same time constraint*. Understandably, the authors focus on the gap to optimal solutions, which fafor their method DACT, but the tradeoff for the smallest gaps in DACT is the much longer operating time. Furthermore, all the instances considered in the experiments are relatively small (i.e., with 20, 50, and 100 instances). More convincing experiments on larger situations, preferably the situations where previous methods fail to solve, are needed in order to prove the effectiveness of DACT.\n\nTherefore, while the paper has no obvious flaw, I think the authors will need more work in order to justify the effectiveness of DACT. I recommend rejecting the paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Very limited or none.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on reviews, rebuttal and discussion, I recommend acceptance of this paper. Based on reviews:

* There is no fundamental flaws
* The overall paper is clear
* The experiments are well conducted
* The rebuttal addresses the main concerns

While the significance of the contributions are borderline, it is sufficient to inspire new works in the same direction and is likely to have positive impact on the sub-community.
Decision: Accept (Poster)