Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time
Authors: Qingchun Hou
Jingwei Yang
Yiqiang Su
Xiaoqing Wang
Yuming Deng
Venue: ICLR 2023 poster (2023)
Keywords: Learning
Vehicle Routing Problem
Large-scale Vehicle Routing Problem
Generalization
Combinatorial Optimization
Reinforcement Learning
Attention

Abstract: Large-scale Vehicle Routing Problems (VRPs) are widely used in logistics, transportation, supply chain, and robotic systems. Recently, data-driven VRP heuristics are proposed to generate real-time VRP solutions with up to 100 nodes. Despite this progress, current heuristics for large-scale VRPs still face three major challenges: 1) Difficulty in generalizing the heuristics learned on small-scale VRPs to large-scale VRPs without retraining; 2) Challenge in generating real-time solutions for large-scale VRPs; 3) Difficulty in embedding global constraints into learned heuristics. We contribute in the three directions: We propose a Two-stage Divide Method (TAM) to generate sub-route sequence rather than node sequence for generalizing the heuristics learned on small-scale VRPs to solve large-scale VRPs in real-time. A  two-step reinforcement learning method with new reward and padding techniques is proposed to train our TAM.  A global mask function is proposed to keep the global constraints satisfied when dividing a large-scale VRP into several small-scale Traveling Salesman Problems (TSPs). As result, we can solve the small-scale TSPs in parallel quickly. The experiments on synthetic and real-world large-scale VRPs show our method could generalize the learned heuristics trained on datasets of VRP 100 to solve VRPs with over 5000 nodes in real-time while keeping the solution quality better than data-driven heuristics and competitive with traditional heuristics.

Published as a conference paper at ICLR 2023
GENERALIZE LEARNED HEURISTICS TO SOLVE LARGE-SCALE VEHICLE ROUTING PROBLEMS IN REAL- TIME
Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, Yuming Deng
Alibaba Group
hougingchun. hec@al aati@alibbbll ieababaaiiii -nnc com, 68t org. cn
ABSTRACT
Large-scale Vehicle Routing Problems (VRPs) are widely used logistics, trans- portation, supply chain, and robotic systems. Recently, data-driven VRP heuristics are proposed to generate real-time VRP solutions with up to 100 nodes. Despite this progress, current heuristics for large-scale VRPs still face three major chal- lenges: 1) Difficulty in generalizing the heuristics learned on small-scale VRPs large-scale VRPs without retraining: 2) Challenge in generating real-time lutions for large-scale VRPs; 3) Difficulty in embedding global constraints into learned heuristics. We contribute the three directions: We propose a Two-stage Divide Method (TAM) to generate sub-route sequence rather than node sequence for generalizing the heuristics learned on small-scale VRPs solve large-scale VRPs in real-time. A two-step reinforcement learning method with new reward and padding techniques proposed to train our TAM. global mask function is proposed to keep the global constraints satisfied when dividing a large-scale VRP into several small-scale Traveling Salesman Problems (TSPs). As result, we can solve the small-scale TSPs in parallel quickly. The experiments synthetic and real-world large-scale VRPs show our method could generalize the learned heuristics trained on datasets of VRP 100 to solve VRPs with over 5000 nodes in real-time while keeping the solution quality better than data-driven heuristics and competitive with traditional heuristics.
INTRODUCTION
Vehicle Routing Problems (VRPs) are widely used in logistics, supply chain, transportation, and robotic systems (Toth & Vigol 2002b Golden et al.) 2008 Bullo et al. (01I). For instance, on e-commerce platforms, hundreds and thousands of goods are sold in real-time and then transported to customers with maximum efficiencies, minimum number of vehicles, and shortest distance. Therefore, more large-scale VRPs need to be solved in real-time to improve logistics or transportation efficiency (Dong al. 2021: Duan et al. 2020). Although VRP is of the most well-studied combinatorial optimization problems, the large-scale VRP is still challenging due to its NP-hard characteristic (Golden et al. 2008). Exact methods or solvers (such as branch and bound (Toth & Vigo 2002a). branch and cut (Naddef' & Rinaldi 2002), column generation (Chabrier) 2006). Gurobi, and Cplex) could obtain global optimal solutions on small-scale VRPs with theory guarantee. However, these methods are time-consuming and hard to be extended to large-scale VRPs because permutation number growing exponentially. Traditional heuristics or solvers could solve small-scale VRPs quickly with near-optimal solutions. Some heuristics could be extended to solve large-scale VRPs (Ortools (Perron & Furnon), I.KH3 (Helsgaun) 2017). HGS (Vidal 2022 Vidal et al., (012), and SISRs (Christiaens & Vanden Berghe 2020). However, massive iterations needed to obtain good solutions. The algorithm for solving large-scale VRP in real-time (seconds) still lags behind.
Recently, data-driven methods are proposed learn heuristics for constructing VRP solutions directly (Vinyals et al. 2015). Deep learning methods like Transformer (Vaswani et al., 2017 Kool et al.
2019; Peng et al.) (020)) and Graph neural network (Kipf & Welling, 2016 Khalil et al. 2017 Joshi et al. 2019) are used to extract hidden states of VRPs and TSPs, which is called Encoder. The solution sequences of VRPs are then generated in autoregressive way from the hidden states,

---

Published as a conference paper at ICLR 2023
which is called Decoder. Reinforcement learning techniques are also applied train the encoder- decoder model serqueence-o-seqqeeee model) to improve its accuracy (Nazari et al. 2018). These Ceam-to-construce heuristies outperform or be comparable to traditional VRP heuristics with up to 100 nodes. However, when it comes to large-scale VRPs (over 1000 nodes), the learned heuristics still face three challenges: 1) the training of data-driven large-scale VRP model is time-consuming and computationally expensive. For instance, the computation complexity and memory space of training the Transformer are quadratic to the lengths of the input sequence (nodes number of VRP) (Kool et al., 2019)] Kitaev et al., 2019); 2) the model trained on small-scale VRPs is difficult to be generalized large-scale VRPs because the nodes distribution of large-scale VRPs in test dataset is different from that of the small-scale VRPs in the training dataset; 3) the global constraints like maximum vehicle number are hard to encoded in the encoder-decoder model because global constraints become active only at the end of the sequence.
Although the limitations of traditional and data-driven methods, we ask: Could we generalize the learned heuristics to solve large-scale VRPs in real-time by taking advantages of both data-driven and traditional methods? We try to answer this question from the following perspectives:
1) Although the traditional heuristic methods are time-consuming when solving large-scale VRPs, they can quickly obtain optimal or near-optimal solutions with some theory guarantees when solving small-scale VRPs. We observe that vehicle capacity for real-world large-scale VRPs is limited, and each vehicle serves a few customers. If we know the customers that each vehicle needs to serve, then the original large-scale VRP could be divided into several small-scale TSPs, which could be solved by traditional heuristics quickly and parallelly.
2) The generalization of data-driven heuristics large-scale VRPs is difficult because the sequence- to-sequence model needs to learn the distribution of each node in the long sequence. We observe that if we just model the distribution of sub-routes and ignore the order of nodes inside sub-route, then we could possibly better generalize the model trained on small-scale VRPs to solve large-scale VRPs.
3) Although the global constraints are only active at the end of the sequence, we could design global mask fiunction with theory guarantee to prevent the infeasible solution beforehand. In addition, the global constraints could include some prior information, which helps improve the generalization of the learned heuristics. For instance, we observe that the predefined maximum vehicle number could provide some global information about the possible range of the optimal vehicle number the testing dataset, which could help identify the minimum travel length.
Prior global
Large-seale
information
Learn to divide VRP into sab-TSPs
with global mask fanction
Original subroute
Original subroctte 2
Original subroute N
Padding the original subroute to same longth
Subroute
Subroute
Subroute
Hauriekes
Heurbaies
Hruriates
Optimal Subroute
Optinal Subroute
Optimal Subroute
Combine
Final VRP Roure
Figure 1: Our TAM framework. In the first stage (green), learned model divides large-scale VRP into several small TSPs while satisfying VRP constraints like capacity and maximum vehicle number. Then, the original TSPs are padded to the same number of nodes at the training time. In the second stage (orange), all TSPs or sub-routes with simple constraints are optimized in parallel.
Driven by the above analysis, we present a Two-stage Divide Method (TAM) in Figure I for generalizing the learned heuristies solve large-scale VRPs in real-time with zero-shot way. Our TAM combines the real-time advantages of data-driven methods and the generalization ad advantages of traditional heuristies. It first divides large-scale VRP into several smaller sub-routes by generating
2

---

Published as a conference paper at ICLR 2023
Original VRP-13
Original sogueces ignoting order
(c) Three
(4) VRP-13
TAM jonerates separaze
Pacding the TSPs vaee
Optimitedd TSP
Deput padalng
Figure 2: Illustration of dividing VRP 13 into three TSP-5s, which are optimized in parallel.
350
AM
300
AM
TAM-AM
TAM-AM
000
LKH3
750
TAM-LKH3
TAM-LKHS
Longth
Time(s)
300
1.0
200
100
50
1000
2000
3000
4600
9900
5000
Nico
1600
2000
9000
4000
5000
5000
2000
Size of VRP
Size of VRP
(a)
(b)
Figure 3: The performance of TAM and benchmark methods agaist the size of VRP (a) Route length (b) Solving time. TAM-LKH3; Our TAM with LKH3 as the second- staoe solver; TAM-AM: Our TAM with Attention Model as the second-stage solver; AM: Attention Model; LKH3: LKH3 solver.
sub-route sequence using learned encoder-decoder model. The encoder-decoder model is trained by a two-step Reinforcement Learning (RL) with novel reward that encodes the distribution of sub-route sequence. To accelerate the training process, propose padding technique to pad the original TSPs to the same number nodes at the training time. A global mask function is also proposed encode global constraints like maximum vehicle number in this stage. In the second stage, all small-scale sub-routes could be solved in parallel using traditional heuristics or learned heuristics. To better understand our method, we illustrate the process by splitting a VRP 13 into three smaller TSP-5s and obtaining the final route by combining the three optimized TSPs in Figure 2
Technically, summarize our key contributions as follows:
(1) We propose a new formulation and Two-stage Dividing Method for generalizing the learned heuristics trained on small-scale VRPs solve large-scale VRPs in real-time and zero-shot way.
(2) We propose three techniques to improve the zero-shot generalization ability of our TAM: 1) Propose generating sub-route sequence take advantages of both learned and traditional heuristics; 2) Propose a two-step RL training method with new reward and padding method to accelerate training process and make the TAM invariant to node sequence of sub-route; 3) Propose a global mask function to encode maximum vehicle number constraint with theory guarantee. A proof of the mask function and a generalization analysis of TAM are provided in Section A.4 of Appendix.
(3) We validate our TAM on synthetic and real-world large-scale VRPs. The results show our TAM could generalize the learned heuristics trained on VRP 100 to solve VRPs with over 1000 nodes in real-time while keeping the solution quality competitive with traditional heuristics. For VRP 2000, the solution quality of our TAM is over 50% better than the data-driven Attention Model. Example results of generalizing to VRP 2000 and real-world VRP 1040 shown in Ff Appendix.
(4) Our TAM can scale to VRPs with over 5000 nodes. For VRP 7000, the solution quality of our TAM is about 20% better than LKH3 with only 6.6% solution time. The scalability performance of our TAM (TAM-LKHE and TAM-AM) against the size of VRP is shown in Figure Example results of generalizing to VRP 7000 and 5000 shown in Figure 7 and of Appendix.
3

---

Published as a conference paper at ICLR 2023
2 RELATED WORK
As above mentioned, VRPs are usually solved by exact methods, traditional heuristics, and data- driven methods. The exact methods are time-consuming and incapable of solving large-scale VRPs in a reasonable time. Therefore, we mainly focus on the traditional heuristics and learned methods. In the following part, we summarize the related work about the learned methods. More comprehensive reviews about the traditional heuristics and learned methods could be found in Appendix A.5
Learned methods include learn-to-construet method and learn-to search method. The learn-to- construct method constructs good VRP solutions real-time directly without iterations. Vinyals et al. first proposed using pointer network (PN) to generate TSP solution in real-time (Vinyals et al. 2013). From there, several improvements are witnessed (Nazari et al.
2018 Kool et al. 2019; 2021). The learn-to- conn-tooconstruct ideas also applied in other variant VRPs and get promising results (Delarue jet al. 2020 Peng et al. 2020 Falkner & Schmidt-Thieme 2020 Xin et al., 2020). However, due to the difficulty of training the model large-scale VRPs, generating solutions for VRPs with over 400 nodes is still challenging (Fu et al.) 2021] Joshi et al. 2020 Ma et al. (019). Different from previous works, our TAM generalizes the learned heuristics solve VRPs with over 1000 nodes in real-time by taking the advantages of traditional heuristics, data-driven heuristics, and prior information. To the best of our knowledge, our TAM is the first carm-to-construct method that could solve VRPs with over 5000 nodes in seconds with zero-shot generalization. In contrast, the learn-to-search method mainly used in exact methods (Gasse al. 2019) and traditional heuristics (Lu et al. 2019 Khalil
ee al. 2017: Chen & Tian 2019 Hottung& & Tierney 2019 Xin et al. 2021 Chen et al. 20220) such
as learning better large neighborhood search heuristics (Hottung & Tierney 2019; Chen el al. 2020),
designing better constructors, destructors, and improvement operators (Lu et al. 2019 Khalil et al. 2017) to accelerate the search process. However, the iterative search is still necessary.
Decomposition technique has been used in traditional heuristics (Queiroga et al. 2021 Zhang et al.
2021 Bosman& & Poutré 2006; Ventresca et al.) 2013 Alvim & Taillard [013: Lalla-Ruiz& & Voss
2016 Taillard & Helsgaun 2019). Recently, the decomposition ideas are introduced to data-driven
heuristics for solving TSP and VRP (Fu et al.) (022), such as divide and conquer networks for TSP (Nowak et al.] 2018)) and lear-to-delegate method for VRP(Li al. (02T). They both belong to learn-to-search methods. Different from previous works, our TAM contributes to generalize learn-to-construet heuristics in real-time, which decomposes VRP as independent sub-routes and just call sub-problem solver once in parallel. Besides, our work could easily encode other VRP constraints by changing mask functions, which is more difficult for the learn-to-seard method. In the following sections, we will focus on the learn-to carn-to-construct method.
3 PRELIMINARY WORK
VPR definition VRPs are usually defined as serving all customers' demands from depot with user-defined objectives while considering some constraints. In this paper, we investigate the CVRP (capacitated vehicle routing problem) with maximum vehicle number constraints Im while minimizing travel length. Assuming CVRP with n customers, the inputs are points set Ω = (To. J,,..., J. where To represents depot; T, represents 7th customer. Each customer T, = (x44, Vi, de) contains three features: x-coordinate z,, y-coordinate yt, and demand of customer d, The demand that each vehicle serves is constrained by the vehicle's ' capacity C. The number of available vehicles is limited by 4m- Our objective is to find an optimal permutation π {TT. T....., ) of Ω2 to minimize Euclidean travel length, where Ig is visited times. A detailed model is shown in Appendix A.I
Markov Decision Process Model Previous Ceam-tto-oonsture methods such as Attention Model (AM) (Kool et al. 2019) use RL to train a sequence-to-sequeee policy for solving the VRPs directly. The corresponding MDP (Markov Decision Process) model is as follows: 1) Thate:The current partial solution of VRP. 2) Action: Choose an unvisited customer. The action space is the set of unvisited customers. 3) Reward: The negative value of travel distance.
Therefore, the corresponding stochastic policy p(Te(s:) represents the probability to choose an unvisited customer n, as the next customer, given the current state 8t, which contains the information of the instance and current partial solution. Then, the policy for optimal route π could be modeled as:
n+1
Pa (T|s)) = II Pa (TT()))
(1)
t=1
4

---

Published as a conference paper at ICLR 2023
where is the vehicle number sub-route number, is the parameter of the stochastic policy. In this formulation, the possibility of the next customer should be accurately modeled for each unvisited customer. For large-scale VRPs, generalizing the model to calculate this possibility is much more difficult because of the distribution shift from the training dataset. This is also one of the main reasons behind the generalization failure of current leam-to-construet heuristics.
4
METHOD
4.1
GENERAL FORMULATION OF TAM
For our TAM in Figure global information is learned in the first stage, while local information like nodes' sequence inside each sub-route is handled in the second stage. Therefore, the most challenging part is learning the best global split while considering complex constraints. To this end, we propose generating sub-route sequence rather than node sequence. The MDP model is designed as follows:
State: The current partial solution, composed of the chosen sub-routes of VRP.
2) Action:
Choose an unvisited sub-route. The sub-route for VRP here defined as the set of customers that vehicle could serve. The action space is the of unvisited sub-routes.
3) Reward: The negative value of minimal distance of the chosen sub-route.
Therefore, policy becomes (r (8),, representing the probability choose an unvisited sub-route rs. The optimal sub-route split r could be modeled as:
po(r(s) II po (relse)
where 0 is the parameter of the stochastic split policy. In this formulation, we ignore the visiting order of customers (also called nodes) inside each sub-route rr. This configuration is more beneficial for generalizing the learned model to large-scale VRPs because the distribution of sub-routes could be similar between testing dataset and training dataset, although the number and distribution of nodes are different between the two datasets. After generating the optimal sub-route the optimal route π could be modeled as:
[ (re(se)
4 (in pa (Td/ets (T/(ri m.oo--))
p(T(()
This formulation means we first obtain the optimal sub-route split and then determine the node sequence in each sub-route independently. The is number of node in the route rt. The 3 denotes the parameters of the policy that determines the customer's order inside sub-route. The Tr,0:-1 represents the chosen partial sequence inside sub-route 7, In this paper, we solve the sub-problems using learned or traditional heuristics in parallel. Based on Equation a generalization analysis about why our TAM works is shown Appendix A.4.2
4.2 GENERATING SUB-ROUTE SEQUENCE WITH SEQUENCE-TO-SEQUERN MODEL
Modeling the policy in Equation 2 faces two challenges. First, the action space is much larger and we need to sample all nodes inside a sub-route while ignoring the nodes' order. Second, mask function for constraints is harder to encode without node sequence (Kool et al., 2019 Nazari et al. 2018). To bridge this gap, we propose to transform the policy in Equation 2 into an equivalent soquence-to-sequceee policy (Equation 4) with novel reward to eliminating the effect of nodes' order (Equation We assume the nodes between two depots belong to the same sub-route:
|
x+1
Po
II pa (IT (st)
π ......, x ....... E {Lo}
(4)
{ -1 = Tj mjt1
Er; =i=1,.. 1,...,!
ri O Vi =i=1. 1i=1.... I....,
<< 4m
5

---

Published as a conference paper at ICLR 2023
where n' is the depot visited in 1th time; ry is ith sub-route; Q represents the feasible space of ra- The first line of Equation[Dis a peuueecc-to-sqqeene
policy. The second line shows the times to visit the depot. The third line transforms the sequence of nodes between two depots into the set of nodes (a sub-route problem). The fourth line shows each sub-route should satisfy some local constraints such as capacity constraint. The fifth line shows the global constraint for maximum vehicle number. With this formulation, we could generate sub-route sequence with sequence-to-sequeee model. However, the nodes' order inside sub-route still affects the performance of the policy.
4.3 NEW REWARD
To make the reward of the chosen sub-route r; invariant to the order of nodes inside that sub-route, we propose to use the optimal length of the sub-route as its reward Rg:
R2 = - min (ir:()))))) wi=1.....
(5)
where +() is permutation function; dist() is distance function used to calculate route length. Because the optimal length is invariant to the order of inputs, the reward is then invariant to the order of nodes inside the sub-route. The optimization method could be exact methods, traditional or learned heuristics. The accumulated reward then used to train our policy (details in Section 4.5)
R R
(6)
In doing so, we could find the next route while using mask function satisfy complex constraints.
4.4 GLOBAL MASK FUNCTION
For CVRP, each sub-route should satisfy vehicle capacity constraints (local constraints); the whole route should satisfy the predefined maximum vehicle number constraints (global constraints). The global constraints, however, could only be active at the end of sequence, making it hard to adjust the sequence when the constraints are active and obtain a feasible solution. Therefore, we propose new global mask function for global constraints. According to our formulation in Equation 4 the time of visiting depot is equal to the number of vehicles. Therefore, we could constrain the probability to visit depot py (Te Io (s)) beforchand. If the capacity of unused vehicles cannot serve the rest demand, then the current vehicle can not visit the depot:
tanh
ka. Vdiim
if Eien, di S C' (m (w)
Pa (Ie Iolst) softmax ug), uo
(7)
-00
otherwise.
where q is the context query: kg represents the key of the depot; 22 is the set of unvisited nodes; 4m represents the maximum vehicle number; Lu is the number of used vehicles, including the current vehicle; dim; is the dimension of hidden state. The calculation methods of q and kg are shown in Section A.3.3 Appendix. With Equation 7 could prevent the violation of the maximum vehicle number constraints by making full use of the current vehicle's capacity.
Theorem 1 (Global mask function for maximum vehicle number constraint). Assume that 1) the total capacity of vehicles is larger than the total demand of customers in * C >> Σ; d;; 2) the maximum demand of single customer much less than the capacity of vehicle maxie di < C. Then, the proposed global mask function enforces the satisfaction of the maximum vehicle number constraint 1 I Im..
The theoretical proof and remarks of Theorem 1 are provided in Appendix A.4.1 For local constraints like capacity, we use the mask function in Kool et al. (201)) (see Appendix A.3.4).
AM as dividing model: As above mentioned, we could reformulate our dividing model as a sequence- to-sequence model with new reward and global mask function. In this paper, we modify the Attention Model (Kool et al. 2019) as dividing model. The architecture of the dividing model is shown in Figure 4(a) The input and Encoder are the same as A.M while the Decoder is modified to encode our global mask function in Section 4.4 The output of the autoregressive Decoder is the nodes permutation म, which could divide the VRP into several sub-routes r using Equation 4 The details of AM shown in Section A.3.3 of Appendix. It should be noted that our main contribution is the two-stage dividing formulation and generalization techniques rather than tosenncce----quencee model. Other models like Graph neural network could also be encoded in TAM.

---

Published as a conference paper at ICLR 2023
Enceder
Decoder
aoded
globel
ho
Fin
comstraita
Step Traising stage
Choose aest
Spir
rude
Muiti-Hiad
Updare paliy
Alato Apre
Provide reard
(a)
(b)
Figure 4: (a) Attention-based model for TAM. (b) Two-step training process of TAM.
4.5
TWO-STEP TRAINING ALGORITHM
According to Equation 6 our reward is the sum of the negative optimal length of all sub-routes. However, if we calculate the optimal length of the sub-TSPs with traditional heuristics or exact solvers training our TAM, two problems arise: 1) we cannot use GPU to accelerate
training
process; 2) calculating the optimal solution for each sub-route is relatively time-consuming To this end, we propose a two-step training algorithm in Figure 4(bb for our TAM by using a learned TSP heuristic to approximately calculate optimal reward. The learned TSP heuristics such as AM have been proved to be effective for small-scale TSPs in previous works (Kool et al. 2019 Bello et al.) 2016 Joshi al. 2020).
Algorithm in Appendix A.3. reports the implementation details of our training algorithm. The main training process is follows. Step I: first train TSP solver with A. using generated dataset for small-scale TSPs. Step II: we initialize TAM to split original VRPs in the training dataset into several sub-TSPs. The sub-TSPs are padded the same length by the proposed padding technique. The sub-TSPs are optimized by the well-trained AM in GPU parallelly after padding. The reward is then calculated using Equation 66 to update the parameters of TAM. The process is repeated iteratively until finding an acceptable policy.
The sub-TSPs divided by our TAM have different number of nodes. Therefore, the length of the input vector is different for different sub-TSPs, which cannot be calculated by GPU in parallel. We borrow the idea padding from CNN (LeCun al. (2000) to our TAM. We pad the sub-TSPs to the same length by adding depot nodes in sub-TSP input vectors. In this way, we could compute the reward in parallel using the learned TSP model to accelerate the RL training process while with little impact on the optimal reward.
Padding TSPs to the same length:
4.6 INFERENCE
At inference time, we use the trained TAM to divide the large-scale VRP into several sub-TSPs without padding. Then, the small-scale sub-TSPs could be solved traditional heuristics in CPU parallelly or by learned heuristics (Algorithm 2 and 33. If we use learned TSP heuristics as second- stage solver, train several models datasets of TSP 20, 50, and 100, respectively. At the inference time, we choose the trained TSP model with the closest nodes number to the sub-TSPs as solver. Search strategy in the first stage also matters the inference time. We use three strategies in our TAM: greedy search, sample search, and beam search. The details of the three strategies are described in Appendix A.3.2 In our experiments, we use beam search with beam size as the default strategy.
EXPERIMENTS
5.1 DATA-GENERATION
We set maximum vehicle number Im as following:
Im Eien d;
(8)
We follow the Nazari et al. (2018): Kool et al. (2019) in the dataset generation for CVRP 100, 400, 1000, 2000, 5000, and 7000. We sample the coordinates of depot and nodes with uniform
7

---

Published as a conference paper at ICLR 2023
Table 1: Route length and solving time (second) of CVRP with our TAM and benchmark methods that are trained on CVRPI00 dataset
CVRP
TAM-AM
TAM-LKHB TAM-ORTOOLS
POMO
DPDP
ORTOOLS
T.KH3
LENOTH
74.314
1.42
64.78 1.88 65.12
114.361: 2.15
485,42::0.12
68.471
64,9311.4 188
2000
TIME
2.220.00
5.63+
11.10:0.69
1.87 0.00
4.4240.08
100.01 0.00
20.2940.00 05
LENGTH
50.061:
0.98
46.341
0.84 46.47:1.884
61.421 1.76
160.43:17.21
48.811
46.4410.84
1000
TIME
0.76= 0.00
1.824 0.03 6.0340.01
0.59 0.00
2.27 0.08
00::0::: 0.00
6,15= 0,01
LENGTH
27.03=0.51
25.934
0.46 25 25.9640.47
2.53
29.93+.34
27.01 0.47
24.67=0.46
400
TIME
0.30
1.35.: 0.03
4.83:10.00
0.20.1 0.00
1.80.1.000
30.36.1 0.16
4.10:10.01
LENOTH
19.10.1
06.33-30.3
16.08:10.33
16.42:10.36
15.69:10.26
16.57.1..77
16.681: 0.36
15.58:10.34
100
TIME
0.09=0.00
0.86. 0.01 3.38:0000
0.06 0.00
0.60
0.8:0.011
20.03: 0.01
2.12
distribution from the domain of [0 1]. The demand of each node is normalized by vehicle capacity. We sample 1280000 CVRP100 instances on the fly as training datasets. And then we test our TAM and benchmark algorithms on 100 instances for CVRP 100, 400, 1000, 2000, 5000, and 7000. We trained second-stage TSP model on datasets of TSP 20, 50, 100. More details are shown in Appendix 1.2.
5.2 CONFIGURATION
For fair comparison, all our training hyperparameters are the same AM. We trained TAM for 100 epochs with batch size 512 on the generated dataset. We choose 3 layers transformer in the encoder with heads. The learning rate is constant 1 10-4 All models are trained on single GPU Tesla V100. The rest of the parameters such as dimension of hidden state is listed in Kool et al. (019). We compare our methods (TAM-AM, TAM-LKH3, TAM-Ortools) with three cearn-to-construet benchmarks (AM, POMO, DPDP) and two traditional heuristic benchmarks (LKH3 and Ortools).
AM: data-driven Attention Model (Kool et al., 2019). POMO: Policy Optimization with Multiple
Optima, which is an extension of AM with diverse rollouts (Kwon et al., (020)) DPDP: Deep Policy Dynamic Programming, which generates VRP solutions from a trained heat-map (Kool et al. 2021
LKH3: An open-source VRP solver based on -e---eegaa---elggaa algorithm (Helsgaun 2017 p009). Ortools: An open-source heuristic solver from Google.
TAM-AM: Our TAM with AM as the second stage solver. TAM-LKH3: Our TAM with LKH3 as the second stage solver. TAM-Ortools: Our TAM with Ortools as the second stage solver.
5.3 RESULTS ON CVRP
We first report average testing results on 100 instances in Table The test performance CVRP 400, 1000, and 2000 shows the generalization ability of the method. For our TAM methods, we found that TAM-LKH3 obtains the best performance, while TAM-AM generates solution fastest. Compared with three learn-to-construet methods, our TAM-LKH3 always generates the best solution in less than 6s and outperforms AM and POMO significantly for CVRP with over 400 nodes, while the DPDP method can not generalize to large-scale VPRs directly. For CVRP 2000, our TAM-LKH3 is over 50% better than AM and POMO. We also observe that the gap between our method and AM and POMO is enlarging as the number of nodes increases. Compared with traditional heuristies, we found that our TAM outperforms LKH3 and Ortools in both solution quality and solving time for CVRP 1000 and 2000. Although the LKH3 obtains better solutions for CVRP 400, takes about 4 x computation time than our TAM. These results demonstrate that: 1) our TAM could learn the sub-routes distribution and generalize the learned heuristic to solve large-scale VRP in seconds; 2) the generalization ability of our TAM outperforms the SOTA learn-to-construet methods such as AM, POMO, and DPDP; 3) our TAM is competitive with traditional hcuristics like Ortools and LKH3, while solving time over X faster. The example of CVRP 2000 in Figure 5la) of Appendix shows that good solutions usually have more decoupled sub-routes, which is consistent with our experience. These observations indicate our TAM could find potential patterns for good VRP solutions. More examples such CVRP 1000 are shown in Appendix A.2.6 202266
Scalability study: To validate the scalability performance of our TAM, we further scale our model trained on CVRP100 datasets to CVRP 5000 and 7000. Figure 3 shows the performance of TAM-
8

---

Published as a conference paper at ICLR 2023
Table 2: Route length and solving time (second) of real-world CVRP with TAM and benchmark methods that are trained on CVRPI00 dataset.
CVRP
METRIC
TAM-AM
TAM-LKH3
AM
I.KH3
LENGTH
21.28
20.29
29.35
31,08
1040
TIME
3.43
5.94
3.17
50.00
40.56
1299
TIME
3.72
10.87
3.64
50.33
LENGTH
12.68
12.05
44.34
13.04
963
TIME
3.31
6.74
2.96
50.00
864
LENGTH
24.77
23.33
42.22
39.79
TIME
2.66
50.00
LENGTH
42.32
40.02
58.05
48.45
680
LENGTH
19.26
18.62
34.29
18.46
TIME
2.81
5.34
2.56
100.35
LENGTH
15.87
15.56
26.70
14.99
TIME
2.74
4.69
2.49
100. 22
23.58
27.50
AVERAGE(926)
TIME
3.06
6.58
2.80
61.56
LKH3, TAM-AM, AM. and LKH3 against the size of VRP. Both the route length and solution time are averaged on 100 testing instances. Figure (3a shows that the gap between our TAM-LKH3 and benchmark methods (AM and I.K3)) is enlarging as the size VRP increases. For CVRP 5000 and 7000, both the TAM-AM and TAM-LKH3 are better than LKH3. In particular, the route length of TAM-LKH3 outperforms LKH3 about 18% on CVRP 5000 while the solving time is about 1% of LKH3. For CVRP 7000, the route length of TAM-LKH3 outperforms LKH3 about 20% while the solving time about 6.6% LKH3. Figure (()) shows that the solution time of TAM-LKH3, TAM-AM. and AM are stable while the solution time of the traditional heuristics LKH3 increases quickly. These results show our TAM has much better scalability performance than AM and LKH3. The example results for CVRP 7000 and CVRP 5000 are shown in the 7 and Figure 8 respectively.
Ablation studies about how our three techniques work are shown in Appendix A.2.5 The com- parisons with Learn-to-improve method and HGS shown in Appendix A. and A.2.3 The results on CVRPLIB are shown in Appendix A.2.4 Training time is shown in Appendix A.2.7
5.4 RESULTS ON WORLD CVRPs
For now, investigate the performance of TAM synthetic datasets with uniform distribution of customers. However, the distribution of customers in real world is randomly and irregularly clustered. To this end, we report the generalization of our model on real-world CVRPs. Our TAM has been used for online application. Table Q]n Appendix summarizes the performance of our TAM, AM, and LKH3 on seven real-world cases. On average, both our TAM-AM and TAM-LKH3 significantly outperform AM and LKH3. The solving time of LKH3 is about 10 times of our TAM-LKH3. Figure 5)) in Appendix shows the results a real-world CVRP with 1040 customers. Our TAM-LKH3 finds the best route with length 20.29. The solution time is only about 10% of Ortools and LKH3. Our TAM-AM model finds good route within 3 seconds, whose length is over 30% shorter than AM. These results mean model also has a good generalization
real-world large-scale VRPs. The visualization of solutions on the rest real- worl-world VRPs is shown in Appendix A.2.6
CONCLUSION
In this paper, we propose generating a sub-routes sequence instead of nodes sequence improve the generalization of the learned VRP model. Based on this idea, we propose a two-stage divide model (TAM) to learn how divide the large-seale VRPs into several small-scale TSPs, which could be solved quickly in parallel. We show that our TAM trained on VRP 100 could generalize to solve large-scale VRPs with over 5000 nodes in real-time. The generalization of our TAM outperforms previous Saan-to-construs heuristics on both synthetic and real-world cases. We also encode prior information like maximum vehicle number and expert knowledge like expert-designed heuristics into the data- data-driven model to improve its generalization. In doing so, we have opened up door to generalize the learn-to-oe co-construct heuristics and apply them to solve various real-world cases. More discussions about the main limitations and future works could be found in Appendix A.6

---

Published as a conference paper at ICLR 2023
REFERENCES
Emile Aarts, Emile HL Aarts, and Jan Karel Lenstra. Local search in combinatorial optimization. Princcton University Press, 2003.
Luca Accorsi and Daniele Vigo. fast and scalable heuristic for the solution of large-scale capacitated vehicle routing problems. Transportation Science, 55(4))832-886, 2021.
Adriana CF Alvim and Éric D Taillard. Popmusic for the world location-routing problem. EURO
Journal on Transportation and Logistics, 2(3):231-254 2013.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 161 1.09940, 2016.
Peter AN Bosman and Han La Poutré. Computationally intelligent online dynamic vehicle routing by explicit load prediction in an evolutionary algorithm. In Parallel Problem Solving from Nature- PPSN IX, pp. 312-321. Springer, 2006.
Francesco Bullo, Emilio Frazzoli, Marco Pavone, Ketan Savla, and Stephen L Smith. Dynamic vehicle routing for robotic systems. Proceedings of the IEEE, 1982):1482-18 1504,, 2011.
Alain Chabrier. Vehicle routing problem with elementary shortest path based column generation. Computers & Operations Research, 33(10)2972--990, 2006.
Mingxiang Chen, Lei Gao, Qichang Chen, and Zhixin Liu. Dynamic partial removal: A neural network heuristic for large neighborhood search. arXiv preprint XXXv:2005.09330, 2020.
Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, 2019.
Jan Christiaens and Greet Vanden Berghe. Slack induction by string removals for vehicle routing problems. Transportation Science, 54(2):417-433, 2020.
Jean-Francois Cordeau, Michel Gendreau, Gilbert Laporte, Jean-Yves Potvin, and Frédéric Semet. A guide to vehicle routing heuristics. Journal of the Operational Research society, 53(5):512-522 2002.
Arthur Delarue, Ross Anderson, and Christian Tjandraatmadja. Reinforcement learning with combi- natorial actions: An application to vehicle routing. In Advances in Neural Information Processing Systems, 2020.
Rodolfo Dondo and Jaime Cerdá. A cluster-based optimization approach for the multi-depot het- erogeneous fleet vehicle routing problem with time windows. European journal of operational research, 176(3):448--157, 2007.
Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe, Nikos Parotsidis, Mauricio G. C. Resende, and Quico Spaen. New Instances for Maximum Weight Independent Set From a Vehicle Routing Application. Operations Research Forum, 2(4):48, dec 2021. ISSN 2662-2556. doi: 10.1007/
Marco Dorigo, Mauro Birattari, and Thomas Stutzle. Ant colony optimization. IEEE computational intelligence magazine, 1(4):28-39, 2006.
Lu Duan, Yang Zhan, Haoyuan Hu, Yu Gong, Jiangwen Wei, Xiaodong Zhang, and Yinghui Xu. Efficiently solving the practical vehicle routing problem: A novel joint learning approach. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 3054-3063, 2020.
Jonas K Falkner and Lars Schmidt-Thienee Learning to solve vehicle routing problems with time windows through joint attention. arXiv preprint arXiv:2006.099 0000000000000 2020.
Houming Fan, Yueguang Zhang, Panjun Tian, Yingchun Lv, and Hao Fan. Time-dependent multi- depot green vehicle routing problem with time windows considering temporal-spatial distance. Computers & Operations Research, 129:105211 2021.
10

---

Published as a conference paper at ICLR 2023
Marshall L Fisher and Ramchandran Jaikumar. A generalized assignment heuristic for vehicle routing. Networks, 11(2):109-15 124, 1981.
Zhang-Hur Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 7474-7482, 2021.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combina- torial optimization with graph convolutional neural networks, Advances in Neural Information Processing Systems, 32, 2019.
Bruce L Golden, Subramanian Raghavan, and Edward A Wasil. The vehicle routing problem: latest advances and new challenges, volume 43. Springer Science & Business Media, 2008
Keld Helsgaun. General k-opt submoves for the lin- lin-kennghhn tsp heuristic. Mathematical Program- ming Computation, 19::1119-6,, 2009.
Keld Helsgaun. An Extension of the Kenn-Keniigha--Heeee Salesman and Vehicle Routing Problems. Technical report, 2017.
TSP Solver for Constrained Traveling
André Hottung and Kevin Tiemny. Neural large neighborhood search for the capacitated vehicle routing problem. arXiv preprint arXiv: 1.1000939 2019.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network
technique for the travelling salesman problem. arXiv preprint arXiv:/906.011 2019.
Chaitanya Joshi, Quentin Cappart, Louis-Martin Rousseau, Thomas Laurent, and Xavier Bresson. Learning tsp requires rethinking generalization. arXiv preprini arXiv:2006.0700 2020.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 16Xiv:609.000 (160609990077 2016.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference Learning Representations, 2019.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic program- ming for vehicle routing problems. arXiv preprint arXiv:2102.11756. 2021.
Ycong-Dae -De Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon. Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 188-188221 218-211996 198, 2020.
Eduardo Lalla-Ruiz and Stefan Voss. Popmusic as a matheuristic for the berth allocation problem. Annals of Mathematics and Artificial Intelligence, 76(1) 76(1):173-189, 2016.
Yann LeCun, Koray Kavukcuoglu, and Clément Farabet. Convolutional networks and applications in vision. In Proceedings of 2010 IEEE international symposium on circuits and systems, pp. 253-256. IEEE, 2010.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 34, 2021.
Hao Lu, Xingwen Zhang, and Shuang Yang. learning based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2019.
Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint 0xx.v:1911.04936, 2019.
11

---

Published as a conference paper at ICLR 2023
Juan José Miranda-Bront, Brian Curcio, Isabel Méndez-Diaz, Agustin Montero, Federico Pousa, and Paula Zabala. A cluster- first route-second approach for the swap body vehicle routing problem.
Annals of Operations Research, 253:935-956, 2017.
Denis Naddef and Giovanni Rinaldi. Branch-and algorithms for the capacitated vrp. In The vehicle routing problem, pp. 53-84, SIAM, 2002.
Mohammadreza Nazari, Afshin Oroojlovy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
Alex Nowak, David Folqué, and Joan Bruna. Divide and conquer networks. In International Conference on Learning Representations, 2018.
Bo Peng, Jiahai Wang, and Zizhen Zhang. A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems. In Communications Computer and Information Science, volume 1205 CCIS, pp. 636-650, feb 2020. ISBN 10.1007/978 010079998--8111--577----333
doi:
Laurent Perron and Vincent Furnon. Or-tools. URL
opt intiiiiiiiiin///
David Pisinger and Stefan Ropke. Large neighborhood search. Handbook of metaheuristicx, pp. 399-419. Springer, 2010.
Mingyao Qi, Wei-Hua Lin, Nan Li, and Lixin Miao. A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows. Transportation Research Part E: Logistics and Transportation Review, 48( (8(1):248-257 2012.
Eduardo Queiroga, Ruslan Sadykov, and Eduardo Uchoa. popmusic matheuristic for the capacitated vehicle routing problem. Computers & Operations Research, 136: 10547,, 2021.
Stefan Ropke and David Pisinger. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4):455 2006. ISSN 15265447. doi: 10. 1287/trs... 1050.0135
SN Sivanandam and SN Deepa. Genetic algorithms. In Introduction genetic algorithmss, pp. 15-37. Springer, 2008.
Anand Subramanian, Eduardo Uchoa, and Luiz Satoru Ochi. A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research, 40(10):2519-2555 10019,22211111 2013.
frii D Taillard and Keld Helsgaun. Popmusic for the travelling salesman problem. European Journal of Operational Research, 272(2):420-429, 2019.
Éric D Taillard, Luca M Gambardella, Michel Gendreau, and Jean-vves Potvin. Adaptive memory programming: A unified view of metaheuristics. European Journal of Operational Research, 135 (1):1-16, 2001.
Paolo Toth and Daniele Vigo. Branch-and-boume algorithms for the capacitated vrp. The vehicle routing problem, pp. 29-51. SIAM, 2002a.
Paolo Toth and Daniele Vigo. The vehicle routing problem. SIAM, 2002b.
Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi. Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-855 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
12

---

Published as a conference paper at ICLR 2023
Mario Ventresca, Beatrice Ombuki- Berman, and Andrew Runka. Predicting genetic algorithm performance on the vehicle routing problem using information theoretic landscape measures, In European Conference on Evolutionary Computation in Combinatorial Optimization, pp. 214-225. Springer, 2013.
Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neighbor- hood. Computers & Operations Research, 140:105643, 2022.
Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, Nadia Lahrichi, and Walter Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60 2012.
Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau, and Christian Prins. Heuristics for multi- attribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research, 231 2013.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks, Advances in neural information processing systems, 28, 2015.
Christos Voudouris, Edward Tsang, and Abdullah Alsheddy. Guided local search. In Handbook of metaheuristics, pp. 321-361. Springer, 2010.
Yuan Wang, Linfei Lei, Dongxiang Zhang, and Loo Hay Lee. Towards neighborhood search strategies for integrated delivery optimization of e-commerce and static o2o parcels. Transportation Research Part B: Methodological, 139:38-63, 2020.
Effective
Jianhua Xiao, Tao Zhang, Jingguo Du, and Xingyi Zhang. An evolutionary multiobjective route grouping based heuristic algorithm for large-scale capacitated vehicle routing problems. IEEE Transactions on cybernetics, 51(8):1133-41 2019.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Transactions Industrial Informatics, 17(7):4861-433 1-871111117,, 2020.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with lin-kemiighan-helsgamn heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, 34, 2021.
Yuzhou Zhang, Yi Mei, Shihua Huang, Xin Zheng, and Cuijuan Zhang. route clustering and search heuristic for large-scale multidepot-cappccittee are routing problem. IEEE Transactions on Cybernetics, 2021.
13

---

Published as a conference paper at ICLR 2023
A
APPENDIX
A.1
VRP formulation
14
A.2
More results
16
A.2.1
More details of experiment configuration
16
A.2.2
Comparison with Sear-tooscarce method
16
A.2.3
Comparison with HGS on large-scale VRPs
16
A.2.4
Results on large-scale instances of CVRPLIB
17
A.2.5
Ablation study
17
A.2.6
More CVRP instances
18
A.2.7
Training time comparison between TAM and AM
18
A.3
Details of method
20
A.3.1
Training with reinforcement learning
20
A.3.2
Search strategy
21
A.3.3
Attention Model
22
A.3.4
Local mask functions
23
A.4
Theoretical analysis
23
A.4.1
Proof for global mask function
23
A.4.2
Analysis for generalization performance
24
A.5
Related work
26
A.6
More discussion
27
A.1
VRP FORMULATION
The CVRP (capacitated vehicle routing problem) with maximum vehicle number constraints Lm can be formulated mixed integer programming model:
min
Σ
Cijzij
ien.jennip
Zu = L (0)
(10)
jER
Σ Zi = 1,4j EΩ) (0}
(11)
iE0,i
Uj - 04 d, CC1 22), 10)
(12)
0 05 u < C - d EΩ
(13)
Σ 2,0 =
(14)
JED (0)
Σ 240 =1
(15)
1ED
1 < Im
(16)
Zij E 10, i Q, 0,i
(17)
where equation 9 is objective function, žij is binary decision variable that has value if the are from node to node j is part of the solution and 0 otherwise, Cij is the Fuclidean distance from node
14

---

Published as a conference paper at ICLR 2023
TIVEAM Deg www.g....TTTT.. Ba0-1
Al Eiegle 2AAN Ranr
EAM AM lingl baviaN
TANOOHAR' (eigh
EAItilggo-AAA EarckEs
DONAID LAAA-- Bard
on with 222
(a)
(b)
Figure 5: The example results of generalizing to the synthetic CVRP 2000 (a) and real-world CVRP 1040 (b) with our TAM and benchmark methods that are trained CVRP 100 datasets. The examples show that our TAM significantly outperforms the carn-to-construt method AM with similar solving time while outperforming traditional heuristics (LKH3 and Ortools) on both route length and solving time. The methods are follows: Top left: Data-driven Attention Model (AM). Medium left: Ortools. Bottom left: LKH3. Top right: Our TAM with Attention Model as second-stage solver (TAM-AM). Medium right: Our TAM with Ortools as the second-stage solver (TAM-Ortools). Bottom right: Our TAM with LKH3 as the second-stage stage solver (TAM-LKH3).
15

---

Published as a conference paper at ICLR 2023
Table 3: Route length and solving time (second) of CVRP using TAM-LKH3 and Leam-to-Improox (L2I) that are trained on CVRPI00 dataset.
CVRP
METRIC
L21
TAM-LKH3
LENGTH
138.75
64.78
2000
TIME
25.38
5.63
LENGTH
93.15
46.34
1000
TIME
6.32
1.82
LENGTH
30.67
25.93
400
TIME
3.12
1.35
LENGTH
16.62
16.08
100
TIME
1.01
0.86
to node j; equation 10 and 11 ensure every customer is visited once; equation 11 and define the capacity and connectivity constraints, represents the demand in the vehicle after visiting customer 14 and ensure the maximum vehicle number constraints.
equation 13
A.2
MORE RESULTS
A.2.1
MORE DETAILS OF EXPERIMENT CONFIGURATION
The capacity for synthetic instances of CVRP 100, 400, 1000, 2000, 5000, and 7000 is set to 50, 150, 200, 300, 300, and 300, respectively. At the testing stage, random seed with value of 1234 is utilized to generate the instances. At the training stage, we use the Attention Model trained on TSP 20 dataset default second stage solver. The default search strategy is beam search with beam size 2.
A.2.2 COMPARISON WITH LEARN-TO-SEANE METHOD
As mentioned in related work, the learn-to-search methods could obtain competitive results compared with traditional heuristics such as LKH3 when given enough searching time. In this section, we compare the generalization ability and solving time of method TAM-LKH3 and well knol-nnown learntoo-improve method (L2I, 2019) (Lu et al. (019).. The results are shown in Table We train the 1.21 model on the dataset of CVRP100 with the same parameters Lu al. (209)) and then generalize the 1.21 model to solve CVRP 400, 1000, and 2000 real-time and zero-shot settings. For CVRP 100, we found that our TAM-LKH3 outperforms L2I in real-time. We observe that the solution quality of L2I degrades from 15.57 (Lu et al. 2019) to 16.62 when searching in time. For larger VRP instances, the gap of solution quality between our TAM-LKH3 and L2I enlarges significantly, such 138.75 (L2I) versus 64.78 (TAM-LKH3) for CVRP 2000. These results suggest that: 1) our TAM-LKH3 outperforms L2I on both generalization ability and solving time: 2) the performance of L2I will degrade lot in real-time and zero-shot generalization settings.
In addition, the searching speed of learn-to-search methods and traditional heuristics heavily depends on the quality of initial solution, while our method can generalize to generate large-scale VRP solutions in real-time. Therefore, we could search better solutions for large-scale VRPs by taking advantages of both our TAM and learn-to-search method.
A.2.3 COMPARISON WITH HGS ON LARGE-SCALE VRPS
We have tested our TAM and the open-sourced HGS on 100 instances of CVRP 5000 and 7000 in real-time. Table and 7 report the average route length and solving time of the instances. HGS-160 means the HGS with 60s time-limit. We also implement the TAM-HGS, which uses HGS as the second stage solver of TAM. For real-time application, we found the HGS cannot find a solution in 60 seconds while TAM-HGS could find a good solution in 30.23s and 52.36s for CVRP 5000 and CVRP 7000 respectively. It's also interesting to see that TAM-HGS consumes more time than TAM-LKH3 while finding the nearly same quality solutions.
16

---

Published as a conference paper at ICLR 2023
Table 4: Route length and solving time (second) of CVRP using our TAM-Ortools without reward or without maximum vehicle number mask function that are trained on CVRPI00 dataset.
CVRP
METRIC
TAM-ORTOOLS
W/o NEW REWARD
W/o MASK FUNCTION
LENGTH
65.12 + 1.179
66.27 + 1.222
69.32 + 1.270
2000
TIME
11.10 0.694
11.32 + 0.601
11.32 + 0,572
LENGTH
46.47 + 0.844 0.843
0.881
48.24 + 0.897
1000
TIME
6.03
0.006
6.13 0.006
LENGTH
25.96+0.455
26.10
400
TIME
4.83 = 0.003
4.73 0.009
4.76+ 0.002
LENGTH
16.08 0.330
16.09 + 0.341
16.06 + 0.340
100
TIME
3.38 = 0.002
3.35 = 0.002
3.34 + 0.003
Table 5: Route length and solving time (second) of CVRP using TAM (without second stage solver) and AM that are trained on CVRPI00 dataset.
CVRP
METRIC
AM
TAM
LENGTH
114.36 + 2.148
87.14 + 1.489
2000
TIME
1.87 0.003
1.85 0.002
LENGTH
61.42 + 1.757
57.76 + 1.070
1000
TIME
0.59 0.002
0.58 0.001
LENGTH
29.33 + 0.589
30.77 + 0.580
400
TIME
0.20 + 0.002
0.19 + 0.001
LENGTH
16.42 + 0.360
16.71 + 0.354
100
TIME
0.06 + 0.002
0.05 + 0.000
A.2.4 RESULTS ON LARGE-SCALE INSTANCES OF CVRPLIB
We also test our TAM on all large-scale instances with 500-20000 nodes Uchoa al. (2014) and Arnold, Gendreau and Sörensen (2017) of CVRPLII Uchoa et al. (2017). Table 8 and gap and solving time of the instances. The results show that TAM-LKH3 couldfing signíficantly better results than AM and could find a better solution much faster than LKH3. We also observed that the gap between our TAM and the best solution is about 5-10% when generalizing VRP with about 1000 nodes, and about 15-25% when gneralizing to VRP with over 3000-10000 10000 nodes. This is acceptable for real-time application given that we limit the maximum solving time of our TAM as 60 seconds for instances with less than 10000 nodes and the beam search size as 10 for real-time application. There are two main reasons behind the gap difference: 1) larger-scale VRP much harder to solve; 2) the difference between scale VRP and VRP 100 (used for training TAM) enlarges as the nodes number increases. the optimal solutions are required for non-real-time applications, should significantly improve the sample size of our TAM to find better solution.
the
A.2.5 ABLATION STUDY
To study how the proposed reward and global mask function affect the performance of our TAM, Treport our testing results using three methods, the original TAM-Ortools, the TAM-Ortools trained with standard reward, and the TAM-Ortools trained without the global mask.
1) Our reward vs distance reward: We found that for CVRP 100, the performance gap between TAM-Ortools with and without reward are small because we both train and test on CVRP 100 dataset. As we generalize the learned model to CVRP 400, 1000, and 2000, the gaps are increasing to 0.5%, 1.6%, and 1.8% respectively. The results mean our reward could obviously improve the generalization ability of our TAM to large-scale VRPs and has little impact on its performance on small-scale VRPs.
2) With vs without global mask function: The possible minimal vehicle number for CVRP are 2,, 1(in Equation 8) Therefore, the I, provides prior information for minimal vehicle number.
17

---

Published as a conference paper at ICLR 2023
Table 6: Route length of large-scale synthetic CVRPs using TAM and HGS.
LENGTH
AM
TAM-AM
LKH3
TAM-LKH3
TAM-HGS
HGS-160
CVRP-5000
257.06
172.22
175.66
144.64
142.83
CVRP-7000
354.28
233.44
244.97
196.91
193.64
Table 7: Solving time of large-scale synthetic CVRPs using TAM and HGS.
TIME(S)
AM
TAM-AM
LKH3
TAM-LKH3
TAM-HGS
HGS-T60
CVRP-5000
11.50
11.78
151.64
17.19
30.23
60.00
CVRP-7000
26.13
26.47
501.26
33.21
52.36
60.00
For the results in Table 4 we observe that adding our global mask function could improve results of TAM-Ortools in CVRP 400, 1000, 2000 about 0.3%, 3,8%, 6.8%. respectively. The gaps are increasing the number of nodes increases. This because the generalization-abili of the learned heuristics without the global mask is decreasing the number of nodes increases. Thus, the number of vehicles has larger impact on the total route length for larger VRPs. These results indicate our global mask function could significantly improve the generalization ability of the learned model.
3) TAM vs AM: 3 reports the results of TAM without a second stage solver and AM on CVRP 100, 400, 1000, and 2000. We found that for smaller-scale CVRP 100, and 400, the AM outperforms TAM slightly. This is because the dividing model does not care about order of nodes inside sub-route. However, for large-scale VRPs such CVRP 1000 and 2000, our TAM still outperforms AM significantly even without a second stage solver (23.8% for CVRP 200). These results indicate the superior generalization ability of our TAM.
A.2.6 MORE CVRP INSTANCES
We report synthetic and real-world CVRP instances for comparison and understanding of our method. Figure
8 9 show the results on synthetic CVRP 7000, 5000, 1000 respectively. Figure IT 14 show the results some real-world and large-scale CVRP instances, respectively. Table summrizes the performance of our TAM, AM, and L.H3 on seven real-world cases. The datasets of location, demand, and vehicle capacity are all from real-world cases. For anonymity, we normalized the location and demand using the same method as the synthetic dataset. We found that our TAM-LKH3 could always find good solutions in real-time, while LKH3 fails search for good solutions without enough searching time in some real-world cases (Figure 10 I1 12
12
13). If given enough time for iterations (not -eal-time), traditional heuristics like LKH3 could find good We also found that good solutions for large-scale VRPs are always visually attractive and decoupled for each sub-routes, while bad solutions usually have lots of crossovers among sub-routes. These results indicate the robustness of our TAM on synthetic and real-world cases.
solutions (Figure 14 15
A.2.7 TRAINING TIME COMPARISON BETWEEN TAM AND AM
Because our TAM uses simliar hyperparameters as AM, the only difference that matters for training time is reward calculation. The AM reward is calculated using the distance function directly, while our reward is calculated by a learned TSP solver in GPU. Thus, our training time is a bit larger than AM. The training time of our TAM and AM for 100 epochs shown in Table T0
18

---

Published as a conference paper at ICLR 2023
Table 8: Gap of CVRPLIB instances
LENGTH
No. NODES
AM
TAM-AM
LKH3
TAM-LKH3
X-x502-K39
502
13.97%
6.45%
1.02%
5.75%
X-N513-K21
513
18.13%
11.47%
3.50%
9.41%
X-N524-K153
524
27.57%
16.73%
3.91%
14.34%
X-N536-K96
536
27.67% %
10.32%
19.05%
10.25% %
X-N548-K50
548
28.09%
14.30%
5.38%
13.71 %
X-N561-K42
561
17.85%
10.60%
8.33%
9.36%
X-N573-K30
573
25.79%
10.50%
4.77%
7.56%
X-N586-K159
586
19.40%
8.90%
12.73%
8.89%
X-N599-K92
599
24.02%
9.56%
34.68%
9.37%
X-N613-K62
613
18.20%
11.64%
16.38%
9.69%
X-N627-K43
627
51.64%
10.31%
17.23%
9.61%
X-N641-K35
641
24.62%
8.56%
7.93%
7.39%
X-N655-K131
655
20.55%
7.31%
3.03%
6.66%
X-N670-K130
670
31.18%
19.29%
18.55%
19.01%
X-N685-k75
685
19.80%
11.03%
17.59%
10.40%
X-N701-K44
701
29.56%
7.73%
8.87%
6.81%
X-N716-K35
716
32.90%
12.00%
9.35%
10.05%
X-N733-K150
733
18.74%
8.60%
16.65%
8.51%
X-N749-K98
749
17.06%
10.22%
19.90%
10.03%
X-N766-K71
766
29.50%
9.84%
12.44%
8.82%
X-N783-K48
783
15.60%
12.95%
11.87%
10.23%
X-NS01-K40
801
34.30%
11.91%
5.57%
10.34%
X-N819-K171
819
16.02%
9.70%
28.92%
9.60%
X-N837-K142
837
14.50%
7.58%
11.16%
7.51%
X-N856-K95
856
12.27%
8.99%
8.09%
8.68%
X-N876-K59
876
33.15%
9.37%
9.46%
8.10%
X-N957-K87
957
36.06%
16.94%
10.43%
16.53%
X-N895-K37
895
36.84%
14.32%
29.72%
9.39%
X-N916-K207
916
17.19%
8.91%
10.34%
8.87%
X-N936-K151
936
27.86%
13.92%
22.89%
13.47%
X-N979-K58
979
30.41%
8.23%
15.80%
6.70%
X-N1001-K47
1001
18.36%
12.99%
13.79%
10.64%
LEUVENI-3001
3001
46.93%
20.24%
18.10%
19.30%
LEUVEN2-4001
4001
53.31%
38.57%
22.14%
15.88%
ANTWERP1-6001
6001
39.30%
24.90%
24.20%
24.01%
ANTWERP2-7001
7001
50.32%
33.20%
31.09%
22.55%
AVERAGE
1199
27.18%
13.00 %
14.30%
11.04% %
CHENTI-10001
10001
46.89%
30.20%
29.53%
G 1001
11001
52.20%
33.29%
23.65%
BRUSSELS1-15001
15001
52.37%
43.42%
27.15%
BRUSSELS2-16000
16001
52.44%
39.04%
37.07%
19

---

Published as a conference paper at ICLR 2023
Table 9: Solving time of CVRPLIB instances.
TIME (8)
No. NODES
AM
TAM-AM
LKH3
TAM-LKH3
X-N502-K39
502
0.74
1.01
2.05
1.47
X-N513-K21
513
0.68
0.99
2.10
1.41
X-N524-K1.53
524
0.88
1.00
2.78
1.30
X-N536-K96
536
0.83
0.95
2.37
1.28
X-N548-K50
548
0.78
0.88
2.05
1.18
X-N561-K42
561
0.80
0.93
2.08
1.31
X-N573-K30
573
0.79
0.99
2.05
1.97
X-N586-K155 K159
586
1.00
1.08
3.59
1.58
X-N599-K92
599
1.00
1.13
2.33
1.52
X-N613-K62
613
0.92
1.02
2.34
1.39
X-N627-K43
627
0.98
1.01
2.15
1.71
X-N641-K35
641
1.03
1.53
2.10
2.03
X-N655-K131
655
1.07
1.13
3.63
1.63
X-N670-K136
670
1.09
1.24
4.97
1.64
X-N685-k75
685
1.01
1.16
2.62
1.72
X-N701-K44
701
1.03
1.16
3.04
1.51
X-N716-K35
716
1.05
1.23
3.06
1.92
X-N733-K159
733
1.25
1.36
4.82
1.89
X-N749-K98
749
1.61
1.55
3.42
1.95
X-N766-K71
766
1.16
1.34
4.28
2.01
X-N783-K48
783
1.14
1.35
4.06
2.74
X-N801-K40
801
1.46
1.63
4.12
2.47
819
1.50
1.81
4.65
2.44
X-N837-K142
837
1.37
1.49
5.34
2.06
X-N856-K95
856
1.30
1.40
5.27
2.10
X-N876-K59
876
1.29
1.43
5.20
2.66
X-N957-K87
957
3.42
2.91
4.21
5.01
X-N895-K37
895
2.64
2.58
4.23
3.91
X-N916-K20
916
3.16
3.09
8.93
6.84
X-N936-K151
936
3.94
3.41
9.22
6.05
X-N979-K58
979
3.03
2.95
4.22
5,06
X-N1001-K43
2.93
4.18
4.68
LEUVENI-300
3001
9.73
9,82
68.99
15.59
LEUVEN2-4001
13.45
13.68
73.96
23.73
1NTWERP1-6001
6001
12.81
12.98
596.21
24.91
ANTWERP2-7001
7001
14.96
15.26
479.47
31,90
AVERAGE
1199
2.72
2.82
37.22
4.85
GHENTI-10001
10001
21.41
21.66
37.26
GHENT2-11001
11001
38.55
37.56
55.73
BRUSSELS1-15001
15001
131.39
139.09
166.81
BRUSSELS2-16001
16001
165.94
158.71
187.48
A.3 DETAILS OF METHOD
A.3.1 TRAINING WITH REINFORCEMENT LEARNING
We have defined our stochastic policy (T(T)s) in Equation 4 using an attention- model in Figure 4(a) from which we could determine sub-routes sequence and the number of vehicle by
20

---

Published as a conference paper at ICLR 2023
Table 10: Training time comparison between TAM and AM on CVRP100 dataset.
METHOD TRAINING TIME (H)
EPOCH NUMBER
AM
35.7
100
TAM
78.3
100
Algorithm Training Algorithm for TAM
Input: number of epochs E, batch size B, steps T, trained TSP model AM Initialize 0 = 0, g 0g.
for epoch 1 to E do
for step = to 7 do
Random generate instances Si, Vi E {1..... B}
Sample split π, using policy pa. Vi E (l,.... B) Greedily sample split π., BI using policy PoSl, Vi {I....,B)
Padding all the sub-TSPs of n, and TT the same length, respectively, Vi (1....; B} Calculate the loss L(TT)) L(T:)) using AM according Equation 18 in parallel, respec- tively, Vi E [1....,]]
VC - E == (T,, L(T (1)) Vo log Po (T:)
0 + A0, VC)
end for
if Pe is better than Past then @a. +
end if end for
identifying the locations and number of depots of the sampled sequence To train the model, we define a new loss [(0]s) = (p)((())([((TT)) According to Equation and the cost L(TT) is calculated as:
L(xx) R
Σ min dist(()r:))
(18)
Then, we could optimize the L using REINFORCE algorithm to estimate policy gradient:
VC( (x)() [(L(T) b(s)) V log po(r(s))
(19)
where b(s) is greedy rollout baseline to estimate the value function Kool et al. 2019 If the reward of current split larger than the baseline, should push the parameters 0 of policy network to the direction that is more likely to generate the current split π.
The final training algorithm for TAM is shown in Algorithm
A.3.2 SEARCH STRATEGY
The search strategy in the first stage also matters at the inference time. We use three strategies in our TAM:
Greedy Search: In this strategy, use the most likely split according to our model, and then optimize all sub-routes in parallel. This strategy could generate acceptable solutions with minimum solving time, which could be used in real-time.
In this strategy, we sample kt called beam size, most likely splits according to our model, and optimize each sub-route for all & splits. Then we choose the final VRP route with minimum length. With a larger beam size, this strategy could generate a better split, but also consume more time. We found that increasing the beam size could improve our results obviously first, but will saturate because beam search tends to sample similar splits. Besides, the order nodes inside each sub-route of current split is invariant for the final solution. Therefore, use 10 the beam size.
Beam Search:
21

---

Published as a conference paper at ICLR 2023
Algorithm 2 Inference algorithm for TAM with traditional heuristics second-stage solver
Input:
Learned dividing policy pe. VRP instance
Divide instance into several small scale TSPs {s, 1 1... .I using policy pe with default search strategy
Use a traditional solver such as LKH-3 to solve the small-scale TSPs parallelly in CPU Combine the output of the TSPs as the solution of VRP instance
Algorithm 3
Inference algorithm for TAM with learned heuristics as second-stage solver
Input: Learned dividing policy pa. VRP instance learned TSP solver AM20. AM50, and 10 on dataset of TSP 20, TSP 50, and TSP 100, respectively
Divide instance s into several small scale TSPs {5 " I...I) using policy Pe with default search strategy
Choose the second-stage solver AM, j {20, 30, 50) for s; by minimizing the absolute value between the node number of 8, dep and j. Use the chosen solver to solve the small-scale TSPs parallelly in CPU or GPU
Combine the output of the TSPs as the solution of VRP instance s
Sample Search: In this strategy, we sample k, called sample size, splits randomly according to our model, and optimize each sub-route for all splits. Then choose the final VRP route with minimum length. This strategy could sample totally different splits and could greatly improve the results of our TAM with a large sample number. However, the computation time and memory are also increasing with the sample number. For instance, Figure [6 shows that TAM-LKH3 with sample size 1000 could find the best solution 6.84 among all methods for real-world CVRP 388 instance, while TAM-LKH3 with beam size 10 find solution 6.99. However, the solving time also increases from 3.73s 17.52s.
We report the results of the greedy search of our TAM in Table IT Comparing Table T and Table TT] we found that beam search with beam size 10 outperforms greedy search about 2.6% for our TAM- Ortools, about 3.3% for TAM-AM CVRP 2000. The gap between the beam search and greedy search is larger as the number of nodes increases. Besides, the solving time of beam search is close to that of greedy search. These results mean beam search could effectively improve the generalization of our TAM on solving large-scale VRPs in real-time. should be noted that the beam search could also significantly improve the performance of AM. For CVRP 2000, the route length of AM reduces from 178.31 to 14.36 after using beam search.
A.3.3 ATTENTION MODEL
To learn the policy in Equation I AM uses an attention-based Encoder-Decode model to approximate the policy. The Encoder is a transformer model without positional encoding which transforms each
Table 11: Route length and solving time (second) of CVRP using TAM (greedy search), AM (greedy search), and Ortools.
CVRP
METRIC
AM
TAM-AM
TAM-ORTOOLS
ORTOOLS
LENGTH
178.31 + 27.601
76.87 2.293
66.87 2.096
68.47 0.984
2000
TIME
0.57 + 0.005
0.82 + 0.006
10.864 0.850
100.014 0.001
LENGTH
65.44 + 5.232
50.38 + 1.003
46.49 + 0.842
48.81 + 0.749
1000
TIME
0.26 0.002
0.44 + 0.002
5.71 + 0.004
50.00 0.001
LENGTH
29.38 + 0.504
27.07 0.517
25.97+ 0.473
27.01 = 0.468
400
TIME
0.10 + 0.002
0.27 + 0.001
4.67 + 0.002
30.36+ 0.157
LENGTH
16.71 + 0.383
+.335
16.12 = 0.329
16.68 0.358
100
TIME
0.03 = 0.002
0.15 + 0.002
3.17 + 0.002
20.03 0.014
22

---

Published as a conference paper at ICLR 2023
node input 1, to hidden embedding h, The hy is the global embedding of VRP, by averaging the hidden embeddings of all nodes. Then, the Decoder uses he as context embedding to query hidden states of unvisited nodes to choose the next node to serve (Kool et al. 2019):
he [hg. hist, hpre]
(20)
where hist represents the hidden state of first visited node; hpre is the hidden state of last visited node. The query, key, and value of 7th node for the Decoder are as follows:
= Wh k; = W h,, V, = h:
(21)
Then, could compute the possibility to visit node by attention as following:
= ( L(ss)) = softmax((:)
(22)
tanh
q"k:
if node is unvisited depot otherwise.
U4
vdsmm
(23)
00
where dim& is the dimension of hidden state.
More details about AM could be found in Kool et 2019
A.3.4 LOCAL MASK FUNCTIONS
For local constraints like capacity, we could use the same mask function in Kool et al. (2019) and Bello et al. (2016). If the rest capacity of the current vehicle (C - c) cannot serve the demand of node i (d4), then the current vehicle cannot visit node i:
tanh
K.
if d, S
M4g
(24)
otherwise.
where c is the used capacity of the current vehicle.
For time window constraints, it could be considered in TAM with the following mask function. If the current vehicle cannot arrive the node i in the time window [T. 77", then the current vehicle cannot visit node i:
tanh
if ST+ + +4
01
Vdsmm
(25)
otherwise.
where T' is arrival time of current nodes, 7 is service time of current nodes, f; is the travel time from current nodes to the node
A.4 THEORETICAL ANALYSIS
A.4.1 PROOF FOR GLOBAL MASK FUNCTION
Theorem 1 (Global mask function for maximum vehicle number constraint). Assume that 1) the total capacity of vehicles is larger than the total demand of customers in C C>> Σ, d;: 2) the maximum demand of single customer much less than the capacity of vehicle maxie (1....) n) di e C. Then, the proposed global mask function enforces the satisfaction of the maximum vehicle number constraint I Im-
Note that our global mask enforces the current vehicle cannot return to the depot (cannot use new vehicles) if the capacity of unused vehicles cannot serve the rest demand. In the extreme scenario, our mask function prevents the current vehicle to return to the depot unless it visits as many customers as possible.
Proof.
1) If the total demand E; d, is less than the current vehicle's capacity C, our global mask function enforces using the current vehicle to serve all customers.
2) If the total demand Σ, d; is larger than the current vehicle's capacity C, there always exists a subset of customers 22 that are chosen by our dividing model and eustomer satisfy the following inequality:
Σd d sdsCs
Σ d de ieR
(26)
iE
23

---

Published as a conference paper at ICLR 2023
Dividing C' from above inequality:
Ed/csis
Σ xES2
d d3/C
(27)
iESL
According to Assumption 2, the following inequality holds:
dx/C S max d//C
(28)
iE(L...)
Therefore, there exists subset of customers Ω2 that can be exactly served by one vehicle, which satisfies the following Equation:
C= Σ d
(29)
En
Minus above Equation 29 from Assumption 1, T'Thus,
(m - + Σ d:
d
Σ de
(30)
EE
IES.
Pu is the of unvisited customers. The left side is the remaining capacity. The right side is the remaining demand. Therefore, the rest capacity of vehicles could still serve the rest demand, which satisfies our proposed global mask function. Therefore, the current vehicle could return the depot and use the next vehicle. Repeat the above process, we will always obtain VRP solution while satisfying the maximum vehicle number constraints.
Remark: In terms of Assumption 1, the total capacity of available vehicles is usually large than the total demand of customers for the real-works VRPs with redundancy, because we want to fulfill all the orders and keep the promise to the customers. That's 's one of the reasons why set the maximal vehicle capacity as Equation g terms of Assumption 2, the single demand is usually much less than the capacity of vehicles in the real-world considering a large number of customers. It should be noted that in some rare scenarios, the second Assumption does not hold. To handle this situation, will let the current vehicle visit many customers as possible before returning to the depot. In the early training state, we will add a new vehicle when encountering the situation. the testing state, given the well-trained policy, search strategy, and the redundant vehicle capacity in Equation all solutions of our testing cases are feasible.
A.4.2 ANALYSIS FOR GENERALIZATION PERFORMANCE
The idea behind the sequence-to-sequence model is learning stochastic policy p(T)())), that could determine the next customer m, visit given current state 8t. Then, the optimal route π could be modeled as:
p p(T|s) (T.ss))
(31)
However, TAM aims to find stochastic policy determining the next route r, visit and then the traditional and learned heuristics to optimize the route. The stochastic policy for optimal split is modeled as:
po(r(s) = II pe (re(st)
(32)
[=1
To compare the two policies, we reformulated the Equation 31 as:
ps = ii po (re(st)
(in
4
(mrr., m,o--11)
(33)
This formulation means we first obtain optimal sub-route split and then determine the order of customers in the sub-route. The I is number of node in the route rs. The 3 denotes the parameters of
24

---

Published as a conference paper at ICLR 2023
num 337, length-602
veh num length
0.8
0.6
64
04
0.2
02-
0.0
0.0
(a)
(b)
Figure 6: A generalization case for AM and TAM-LKH3 on the same CVRP 2000 instance with model trained on CVRP 100 datasets. The vehicle number of AM is about 10 times larger than that of TAM. (a) The generalization result using AM. (b) The generalization result using TAM-LKH3.
the policy that determines the customer's order inside sub-route. The 7100:--1 represents the chosen partial sequence inside sub-route Tt-
With the above formulation, argue that all three proposed techniques matter for the generalization of TAM.
Generating sub-route sequence and optimizing in parallel
Comparing Equation 33 and Equation 32 we found that the previous leam-to-construct model must learn not only the sub-route distribution I[ (ry (t), but also the more complex and detailed sequences distribution inside the sub-route II: Il Pa (Ti/re, Ti Tr,0:i11). In contrast, our TAM focus on learning the sub-route distribution. The sequence distribution inside a sub-route is handled by traditional learned heuristics in our TAM. Therefore, focusing on learning sub-route distribution makes our TAM much easy to train and learn; 2) the traditional heuristics could perform well on arbitrary small-scale TSPs and VRPs w.r.t any distributions, which could improve generalization of our TAM to large-scale VRPs distribution-shiifee VRPs.
2) The global mask function technique
According to Equations 33 when generalizing from small-scale VRPs to large-scale VRPs, route number is one of the key variables. However, previous policies without global constraints cannot learn the possible range of optimal vehicle number in large-scale VRPs, which could generate lot of vehicles instead. This also one of the reasons behind the generalization failure of AM. For example, found the AM method could generate 337 vehicles while our TAM with global mask function just generates 34 vehicles, shown Figure 6 This means our global mask function helps encode maximum vehicle number when learning I (r in our TAM. In addition, the pre-defined maximum vehicle number can help estimate the minimum vehicle number beforehand, which could improve the generalization of our TAM, about 5.8% for CVRP 2000.
3) The proposed reward and RL training method As above mentioned, both the proposed generating sub-route technique and the global mask function could help TAM generalize to large- scale VRPs zero-shot way. The third technique, the proposed reward and RL training method, makes training the two-stage dividing model possible. Our RL training method could accelerate the training process by using learned TSP model and parallel computing in GPU. Our reward makes the policy in Equation 4 insensitive the order of nodes inside each sub-route. Using this reward, we achieve generating sub-routes sequence rather than nodes sequence to improve the generalization of our TAM, about 2% for CVRP 2000.
25

---

Published as a conference paper at ICLR 2023
A.5 RELATED WORK
VRPs are usually solved by exact methods, traditional heuristics, and data-driven methods. The exact methods are time-consuming and incapable of solving large-scale VRPs in a reasonable time. Therefore, we mainly focus on the traditional heuristics and data-driven methods.
Traditional methods design heuristics based on domain knowledge to obtain acceptable solutions within a limited search time (Toth & Vigol 2002b). Local search (Aarts et al. [003] Voudouris et al.. 2010). Genetic
& Deepa 2008), Ant colony methods (Dorigo et al. (006). Large neighborhood search (isinner & Ropke 2010p, and Tabu search (Taillard et al.) 2001) are widely used. They usually adopt construction, destruction, and improvement pattern (Golden et al. 2008). They first generate an original feasible solution by constructor, and then destroy the current solution by a destructor, and then improve the current solution by an improvement operator (Ropke & Pisinger 2006). The process is taken iteratively until we obtain an acceptable solution. The pattern is also used in solvers like Ortools (Perron & Furnon), LKH3 (Helsgaun (017), HGS (Vidal 2022
Vidal et al., 2012), FILO (Accorsi & Vigo 2021j. SISRs (Christiaens & Vanden Berghe, Berghe|(2020). and
HILS (Subramanian al., 2013). However, due extremely large search space, the traditional
heuristics need massive iterations to obtain acceptable solutions.
Data-driven methods could construct good VRP solutions directly without iterations (learn-to- construct method). Vinyals et al. first proposed using learned heuristic with pointer network (PN) architecture to solve TSPs in real-time (Vinyals al., 2013). The PN is trained using supervised learning and then generates the TSP solution as a sequence. From there, several improvements are witnessed. Bello et al. replace the supervised learning with policy-based RL to train PN- based heuristic (Bello et al. (016)) Nazari et al. extended RL-based PN to VRPs (Nazari et al., 2018). They use attention layer to replace LSTM the encoder of PN. Kool et al. proposed using Transformer as encoder in PN. Their attention model (AM) is successfully applied in several combinatorial optimization problems, such as TSP, VRP. Orientecring Problem(Kool et al., 2019). Their work obtains close to optimal results for VRP 100. Recently, Kool et al. proposed using dynamic programming to predict the heat-map of edges and then generate VRP solutions from it (Kool et al., 2021). Based on Kool's 's attention model, Kwon et al. observed the symmetry of VRP solutions and proposed POMO to improve the performance of AM. The learn-to-construct ideas are also applied in other variant VRPs and get promising results (Delarue al., 2020 Peng et al. 2020
Falkner& & Schmidt-Thiemee 2020: Xin et al. 2020). However, due to the difficulty of training the model on scage VRPs, generating solutions for VRPs with over 400 nodes are still challenging
(Fu et al. 2021; Joshi et al. 2020; Ma et al. 2019). Some researchers attempted to generalize the learned model on small-scale VRPs to solve large-scale VRPs. For instance, Joshi et al. observed the difficulty to generalize the learned heuristics to larger instances (Joshi et al.) 2020). They investigate how to generalize the learned TSP models to TSP 200 by choosing appropriate architecture and training methods. Their results show commonly used autoregressive decoding and RL could improve the generalization of the learned model, which are also used in our method. Different from previous works, propose novel method by taking the advantages of traditional heuristics, data-driven heuristics, and global information to generalize the learned heuristics to solve VRPs with over 1000 nodes in real-time.
Besides constructing VRPs solutions directly, other works have considered learn-to-searde in exact methods (Gasse et al. 2019) and traditional heuristics (Lu et al., 2019 Khalil al.) 2017 Chen & Tian 2019 Hottung & Tierney 2019 Xin et al., 2021: Chen et al. 2020), such as learning better large neighborhood search heuristies (Hottung& & Tierney 2019 Chen et al. 2020), designing better constructors, destructors, and improvement operators (Lu et al. 2019 Khalil et al. (017]) to accelerate the search process. The results from previous works show the -aan-to-search method could find better solutions for VRPs than traditional heuristics (Lu et al. 2019). However, the iterative search is still necessary.
Decompasition technique has been widely used in traditional heuristics (Queiroga et al., 202 202I\Bosman
Zhang et al.) 20221] Bosman & Poutré, 2006; Ventresca et al., 2013). The technique usually divides original VPRs by clustering method and then solves sub- probprossems in each cluster to obtain the
final solutions (Cordeau et al.] 2002, Vidal et al. 2013) Fisher & Jaikumar, 1981; Miranda- Bront et al. 2017). The based method is applied to solve CVRP (Xiao al.] 2019), PDP (Wang ct al. 2020). VRPTW (Qi et al. 2012). and -elti VRP (Fan et al. 2021: Zhang et al.) 2021 Dondo & Cerdá 2007). However, the cluster-based method has two disadvantages: it is hard to
26

---

Published as a conference paper at ICLR 2023
consider some common constraints and requires effortful human- designed heuristics. It is also hard to determine the optimal clustering number. Therefore, the clustering results could be infeasible or far from optimal solutions. Different from previous works, we propose using the RL-based attention model to split a large-scale VRP into several TSPs while satisfying the complex constraints. Recently, the decomposition ideas are also introduced heuristics) for solving larger instances (Fu et al. p. such as divide and conquer networks for TSP (Nowak al. 2018) and learn-to-delegate method for VRP et al., 2021). The divide and conquer network adopts a dynamic programming strategy to recursively split and merge the partial solutions to improve TSP solution. The Bearn-to-delegate method utilizes traditional solver like LKH3 as sub-problem solver to merge or improve the sub-routes recursively, which is inspired by POPMUSIC Framework(Alvin Taillard 2013] Lalla-Ruiz & Voss, 2016, Taillard & Helsgaun 2019). They both belong to learn-to-search methods. Different from previous works, our TAM contributes to generalize Iearn-to corn-to-constucc heuristics in zero-shot way, which decomposes VRP as independent sub-routes and just call sub-problent solver once in parallel. Besides, our work could easily encode other VRP constraints by changing mask functions, which is more difficult for learn-te sarn-to--earch method. In following sections, we will focus on learn-to-construct method.
data-driven heuristics (especially learn-to-search
A.6 MORE DISCUSSION
Analyzing our results, we found that all three proposed techniques matter for the generalization of TAM. 1) Generating sub-route sequence and optimizing in parallel help us take advantages of both data-driven and traditional heuristics. Comparing TAM-AM in Table I and TAM in Table 5 we found that our two-stage technique could improve TAM's generalization ability significantly, about 15% for CVRP 2000. By dividing the large-scale VRP into several independent small-scale sub-problems, we make solving the large-scale VRP in parallel and real-time possible. It should be noted that the small-scale sub-routes could be part of the routes, rather than complete routes like TSP. In this way, we could extend our TAM to other variants of VRP 2) The proposed reward and training method help the learned first-stage model invariant the order of nodes inside each sub-route. Using this reward, we improve the gencralization of our TAM, about 2% for CVRP 2000 (Table D. This reward also makes our TAM focus on finding good sub-routes split, rather than finding good sequence for each sub- uub-problem. 3) The global mask function technique helps our TAM estimate the minimum vehicle number beforehand. Therefore, TAM could learn to reserve enough capacity for the demands at the end of the sequence for large-scale VRPs, which could improve the generalization of our TAM, about 5.8% for CVRP 2000 (Table 4
Limitations: although our TAM is promising for solving large-scale VRPs in real-time with its generalization ability, still has some limitations: 1) If we want to generalize to even larger VRPs such CVRP 100000, we may need to train our model on larger VRPs directly, such as CVRP 400 and 1000. Due to the Transformer architecture in the Encoder, our TAM consumes a lot of memory and computation resources when training on large-scale VRPs directly. 2) Our TAM outperforms conn-ttt-onsttutt methods and is competitive with some traditional heuristics on large-scale VPRs in real-time and zero-shot generalization settings. However, when it comes to solving large-scale VRP with long searching time (such as days and hours), outperforming the SOTA traditional heuristics such HGS-CVRP is still very challenging.
In the future work, we will focus on the following questions: 1) could we generalize our TAM to other constraints without retraining our model? 2) could we combine the advantages of both our TAM and learn-to-search methods to outperform SOTA heuristics on larger VRPs with a long searching time? 3) could we train our TAM on large-scale VRPs like CVRP 400 and 1000 to generalize on even larger VRPs, such as CVRP 100000? 4) could we embed more abstract forms of local and global constraints our TAM? 5) could we generalize our method to other combinatorial problems?
27

---

Published as a conference paper at ICLR 2023
AM (length-343391 26.0%)
TAM-AM (length-201.96 timem26.44s)
veni pum-118 length $43.91
veh. 117, length=201.00
1.0
0.6
0.
0.4
0.2
0.0
0.0
0.6
0.8
1.0
I.HH (ength-223.38 time-414.211)
TAM- I.KH3(length-122.00 (1m4-33.495)
num-117, length-223.36
veh length=172.01
0.6
0.
Figure 7: Example results on real-world VRP 7000. Top left: Data-driven Attention Model (AM).
Bottom left: LKH3. Top right: Our TAM with Attention Model as the second-stage solver (TAM-
AM). Bottom right: Our TAM with LKH3 as the second-stage solver (TAM-LKH3).
28

---

Published as a conference paper at ICLR 2023
(length-250.29, 11m4-11.484)
TAM-AM (length-154.23, time-11.78s)
veh num=B5, length-250.29
veh, num-=44 length-1544 154.hh-115..22
0.0
52
C4
06
0.8
LKH3 159.th1199.1,, fime=147.256
TAM- LKH 127.64, time=17.64s)
vel num -4, length-159.
Wet pum-84 lengthh1127 127.66
1.0
0.8
0.6
0.6
0.4
0.2
0.2
0.0
0.0
Figure 8: Example results on real-world VRP 5000. Top left: Data-driven Attention Model (AM).
Bottom left: LKH3. Top right: Our TAM with Attention Model as the second-stage solver (TAM- AM). Bottom right: Our TAM with LKH3 as the stcond-stage solver (TAM-LKH3).
29

---

Published as a conference paper at ICLR 2023
AM (length =57, 68, time=0.88)
TAM-AM (length =44.77, time=0.76s)
0.0
0.4
0.6
0.8
1.0
0.0
0.6
0.6
0.
1.0
Ortools (length=45.59) time=50s)
TAM-Ortools (length-41.85, time-5.58s)
1.0
0.0
0.4
0.6
0.8
1.0
0.0
0.7
0.
04
08
LKH3 (2.ngth-42.58. time-8.13s)
TAM-LKH3 (length-41.744 time-2.50s)
4.0
3.0
088
00
06
02
00
0.0
Figure 9: Example results on VRP 1000. Top left: Data-driven Attention Model (AM). Medium left: Ortools. Bottom left: LKH3. Top right: Our TAM with Attention Model the second-stage solver (TAM-AM). Medium right: Our TAM with Ortools as the seeond-stage solver (TAM-Ortools). Bottom right: Our TAM with LKH3 as the second-stage solver (TAM-LKH3).
30

---

Published as a conference paper at ICLR 2023
AM (length-40.56, time-3.64s)
TAM-AM (length-28.85, time-3.72s)
0.8
0.6
0.4
0.4
0.2
8.0
0.0
02
0.4
0.6
0.8
1.0
LKH3 (length=26.69, time=50.33s)
TAM- LKH3(length 22.066 time=10.87s)
4.0
0.8
02-
30
6.2
1.0
Figure 10: Example results on real-world VRP 1299. Top left: Data-driven Attention Model (AM).
Bottom left: LKH3. Top right: Our TAM with Attention Model as the second-stage solver (TAM- AM). Bottom right: Our TAM with LKH3 as the second-stage solver (TAM-LKH3).
31

---

Published as a conference paper at ICLR 2023
AM (1ength=44.34, time=2.96s)
TAM-AM (length-12.68, time=3.31s)
0.2
0.0
0.0
0.0
0.2
0.0
0.0
0.6
LKH3 (1cngth=13.04, time=50s)
TAM- LKH33ength= time=6.74s)
4.7
0.5
0.8
0.4
0.2
0.2
0.0
0.4
0.6
Figure 11: Example results real-world VRP 963. Top left: Data-driven Attention Model (AM). Bottom left: LKH3. Top right: Our TAM with Attention Model as the second-stage solver (TAM- AM). Bottom right: Our TAM with LKH3 as the second-stage solver (TAM-LKH3).
32

---

Published as a conference paper at ICLR 2023
AM Songtt-42.222 time-2.666)
TAM-AM (length-24.77. dime=300ss)
0.
0.-
0.6-
04
0.4
0.2
0.-
0.0
0.5
6.6
1.0
0.0
LKH3 39.79h time=50s)
TAM- (KHgtlength 23.33, time=5.61s)
Figure 12: Example results on worl-world VRP 864. Top left: Data-driven Attention Model (AM).
Bottom left: LKH3. Top right: Our TAM with Attention Model as the second-stage solver (TAM- AM). Bottom right: Our TAM with LKH3 as the secon solver (TAM-LKH3).
33

---

Published as a conference paper at ICLR 2023
AM (180gth=58.05, time=2.09s)
TAM-AM (length=42.32, time=2.389)
0.0
0.4
0.6
0.5
1.0
0.0
0.6
L.KH3 (length-48.455, time-30s)
TAM- L.KH3 40.02, time-6.84s)
0.0
0.0
6.1
0.6
0.6
1.0
0.6
6.6
Figure 13: Example results on real-worke VRP 680. Top left: Data-driven Attention Model (AM). Bottom left: LKH3. Top right: Our TAM with Attention Model as the second-stage solver (TAM- AM), Bottom right: Our TAM with LKH3 as the second-stage solver (TAM-LKH3).
34

---

Published as a conference paper at ICLR 2023
AM (length=34.29, time=2.56s)
TAM-AM (length=19.26. time=2.81s)
0.-
0.4
0.2
0.0
I.KH3 (length-18.44 time- 100.510
TAM- LKH 5,me-),34s)
1.0
0.8
04
0.4
0.2
0.
0.
0.4
0.5
0.8
1.
Figure 14: Example results on real-world VRP 821. Top left: Data-driven Attention Model (AM).
Bottom left: LKH3. Top right: Our TAM with Attention Model as the second-stage solver (TAM- AM). Bottom right: Our TAM with LKH3 as the stage solver (TAM-LKH3).
35

---

Published as a conference paper at ICLR 2023
AM (1ength=26.70, time=2.49s)
TAM-AM (length=15.87, time=2.74s)
0.6
0.4
02
0.0
(length-14.99, time-100.22s)
TAM- 15556 time=4.6%)
1.4
1.0
0.8
0.0-
0.6
0.6.
0.4
0.4
02
02-
0.0
0.0
Figure 15: Example results real-world VRP 817. Top left: Data-driven Attention Model (AM). Bottom left: LKH3. Top right: Our TAM with Attention Model as the second-stage solver (TAM- AM). Bottom right: Our TAM with LKH3 as the second-stage solver (TAM-LKH3).
36

---

Published as a conference paper at ICLR 2023
AM (1ength=9.22,, time=1.64s)
TAM-AM (length=8.29, time=2.36s)
0.0
02
044
0.6
0.0
1.0
30
0.2
0.4
0.6
0.0
1.0
Ortools (length=7,64 time=30s)
TAM-Ortools (length=7.39, time=6.40s)
1.0
3.0
0.-
0.6
0.6
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.6
0.6
0.8
1.
TAM-LKH3-bs10 (length=6.99, time=3.733)
TAM- LKH3-sample 1000( time=17.52s)
0.0
02
0.4
0.6
0.8
1.0
30
0.2 0.6 0.5
0.5
1.0
Figure 16: Example results real-world VRP 388. Top left: Data-driven Attention Model (AM). Medium left: Ortools. Bottom left: TAM (beam size =10) with LKH3 as the second-stage solver (TAM-LKH3), Top right: Our TAM with Attention Model as the second-stage solver (TAM-AM). Medium right: Our TAM with Ortools as the second-stage solver (TAM-Ortools), Bottom right: TAM (sample size = 11000) with LKH3 as the second-stage solver TAM-LKH3-samph. 1000).
37


Reviews:
[{"review_id": "qHPUrF1GTv", "reviewer": "Reviewer_o9TS", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper presents a framework for learning to solve VRP. The core idea is to first learn a policy that can divide the routes into sub-routes where each sub-route is covered by a single vehicle. The one can use efficient TSP solvers for each of the sub-route, and also solve them in parallel. Experiments show that the proposed approach is able to learn the solving from small-scaled datasets, and generalize the results to large graph with more than 5000 nodes.\n", "summary_of_the_review": "Overall a practical paper for VRP with two-stage approaches. It is a nice combination of learning and existing heuristics. The paper can potentially be improved with more analysis of the results, and directions on handling practical constraints when deploying VRP to real-world problems.\n", "strength_and_weaknesses": "Strength:\n\n- The problem tackled by the paper is an important combinatorial optimization that is actively used in daily work. \n- The proposed divide-and-conquer paradigm is reasonable and effective. \n- The empirical results show that the paper is able to achieve better results compared to some existing solvers. Also the paper is able to incorporate existing TSP solvers as subroutines and combine the power of both learning and existing human designed heuristics.\n\nWeakness:\n\n- The paper tackles a limited version of the CVRP. In practice the problem might be more complicated that it is hard to first divide the nodes while still obtaining feasible solutions. For example, in practice there would be constraints like 1) a driver could not drive more than certain hours; 2) certain packages should be delivered to a certain location within a given time period. \n\n- Compared to LKH3 or ORTOOLS the proposed approach obtained comparable or better results with a shorter amount of time. However in practice it is not clear if the proposed approach would further improve with more time. In other words it would be interesting to see the time-solution quality trade-offs of this method and other iteration-based solvers.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QpMIPnBe5V", "reviewer": "Reviewer_7d5S", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The current study, as a strategy to effectively solve large-scale CVRP, presents a strategy for generating TSP sub-problems by clustering nodes and simultaneously solving the generated TSP problems. In particular, the sequential node selection approach has been used to decompose nodes.", "summary_of_the_review": "Although the proposed methodology is interesting, it is necessary to quantify how much more effective the proposed decomposition strategy is compared to other decomposition strategies.", "strength_and_weaknesses": "The decomposition strategy is a methodology that has been dealt with a lot on the OR side. A literature review of decomposition methods is required. Additionally, more recently, the NCO community has been using a decomposition strategy to deal with large-scale VRP issues. It is difficult to evaluate this paper without including these papers in the literature review and comparing them with these methods.\n\nThe current study insists that employing decomposing strategy in a constructive way (i.e., constructive heuristics) is novel in that most decomposing strategies are employed in an iterative manner (i.e., improving heuristics). However, I think it's hard to claim novelty just by suggesting a way to find a solution in a different way. For it to be truly advantageous, it is when the quality of the solution derived by such a process approaches the optimum. From that point of view, I think the strategy of finding a good solution by repeatedly decomposing and solving sub-problems can be more effective.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EKyA5m3mGQ", "reviewer": "Reviewer_6VLJ", "summary": "", "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": "", "summary_of_the_paper": "The paper proposes a two-stage attention-based method (TAM) to solve large-scale routing problems.\n\nAlthough existing learning-based solvers suffer from their scalability (e.g., # of nodes is typically less than a thousand), TAM is trained to split the large input instance into small sub-problems with keeping global constraints. Importantly, TAM can be attached to existing solvers to improve solution qualities. The technical contribution is by attention-based problem splitting, and then sub-problems can be efficiently solved by existing heuristics or learned data-driven methods.\n\nExperimental results are reported to support and discuss TAM. Many experimental results support the performance of the proposed approach emperically.", "summary_of_the_review": "The paper proposes a two-stage attention-based method (TAM) to solve large-scale routing problems. In recent years, simliar problems have been investigated by several researchers, but the proposed paper seems to succeed to solve larger instances. The proposed method seemes to be technically sound, a bit incremental improvement, but a large experimental advantages can be observed by experiments on synthethic and real instance data. Importantly the advantages seems to be large, and the result (i.e., solutions of routing problems) could be much better than existing approaches.\n\nBased on these observations, I feel that the proposed paper is above the baseline.", "strength_and_weaknesses": "[Strength]\n- TAM can be attached with any sub-problems solvers (existing heuristics like LKH3 and data-driven methods like AM).\n- TAM possibly accelerates existing heuristics (e.g., AM v.s. TAM+AM) by improving their solution qualities.\n- Ablation studies for reward and mask functions are meaningful (i.e., designing rewards is an essential step for learning-based methods).\n\n[Weakness]\n- Technical contributions are a bit incremental.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5X3nC-HAFi", "reviewer": "Reviewer_cdJ3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "An RL algorithm, TAM, is proposed to solve large-scale VRP problems.  TAM learns how to split the problem into smaller problems and then solve the smaller problems which are instances of TSP by well-performed heuristic algorithms like LKH3. The splitting problem is defined as an RL problem in which the state of the system is the current partial solution which is obtained by the chosen sub-routes of the VRP problem. The action is choosing an unvisited sub-route which is the set of customers/nodes that a vehicle could serve in one round of service. The reward is the minimal distance of the chosen sub-route. To get that, for a given sub-rout, the minimum distance is obtained by using an optimal algorithm or any fast heuristic (here a learned model by RL is used to exploit the power of parallel computation by GPUs). \nThe goal is to minimize the total travel length.\nTo assign the nodes to the sub-routes, the same algorithm as the AM model, proposed by Kool et. al (2019) is used where the masking operator is added to the decoder to assign the nodes into the sub-routes. To use the GPU for solving the TSP problem in the sub-routes, the padding mechanism is used. For each sub-route problem, the trained RL models of sizes 20, 50, and 100 are available and the model which is closest to the size of each sub-route problem is used. \n\nI really enjoyed reading the paper and the results are impressive to some extent.  \n", "summary_of_the_review": "I only have two questions from the authors which upon getting satisfying answer, I'll raise my vote. \n\nQ1- I did not get \"If the capacity of unused vehicles cannot serve the rest demand, then the current vehicle can not visit the depot\". I am not sure why the capacity of the rest of the network is considered. If you are choosing a given set of nodes to assign them to a sub-route, then, you can easily check the sum of demand of those nodes. Once the sum of demands of those nodes gets bigger than the capacity of the vehicle, you stop assigning the nodes to the vehicle. Given this, why do you need the new masking operator? This procedure should end with the same result as the suggested masking operator, though it is cheaper and more intuitive. \n\nQ2- In the presented results in Table 1, I do not see the optimal solution. For some of the presented instances, you can get the optimal solution with the branch & price algorithm presented in [1]. Besides, the main comment on the numerical experiment is on the benchmark set. If you want to show the true value of your algorithm you need to demonstrate the performance of your algorithm on the CVRPLIB problem set (http://vrp.atd-lab.inf.puc-rio.br/index.php/en/) and instance in [3, 4]. The ultimate benchmarking would involve comparing your results with the state-of-the-art algorithm, like [2, 4, 5], which has some of the best results on that problem set. \n\n\n[1] Pessoa, Artur, Ruslan Sadykov, Eduardo Uchoa, and François Vanderbeck. \"A generic exact solver for vehicle routing and related problems.\" Mathematical Programming 183, no. 1 (2020): 483-523.\n\n[2] Vidal, Thibaut. \"Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood.\" Computers & Operations Research 140 (2022): 105643.\n\n[3] Uchoa, E., et al. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3), 845–858.\n\n[4] Arnold, F., et al. (2019). Efficiently solving very large scale routing problems. Computers & Operations Research, 107(1), 32–42.\n\n[5] Christiaens, J., & Vanden Berghe, G. (2020). Slack induction by string removals for vehicle routing problems. Transportation Science, 54(2), 299–564.\n", "strength_and_weaknesses": "Strength\nA new RL algorithm is proposed to solve large-scale VRP problems. \n\nWeakness\nThe numerical experiments and benchmarks could be improved. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster