Rewriting by Generating: Learn Heuristics for Large-scale Vehicle Routing Problems
Authors: Hansen Wang
Zefang Zong
Tong Xia
Shuyu Luo
Meng Zheng
Depeng Jin
Yong Li
Venue:  (2021)
Keywords: vehicle routing problem
reinforcement learning
optimization

Abstract:  The large-scale vehicle routing problems are defined based on the classical VRPs with thousands of customers. It is of great importance to find an efficient and high-quality solution for real-world applications. However, existing algorithms for VRPs including non-learning heuristics and RL-based methods, only perform well on small-scale instances with usually no more than a hundred customers. They are unable to solve large-scale VRPs due to either high computation cost or explosive solution space that results in model divergence. 
Inspired by the classical idea of Divide-and-Conquer, we present a novel Rewriting-by-Generating(RBG) framework with hierarchical RL agents to solve large-scale VRPs. RBG consists of a rewriter agent that refines the customer division globally and an elementary generator to infer regional solutions locally. Extensive experiments demonstrate the effectiveness and efficiency of our proposed RBG framework. It outperforms LKH3, the state-of-the-art method for CVRPs, by $2.43\%$ when customer number $N=2000$ and shortens the inference time by about 100 times.

Published as a conference paper at ICLR 2021
REWRITING BY GENERATING: LEARN TO SOLVE LARGE-SCALE VEHICLE ROUTING PROBLEMS
ABSTRACT
The large-scale vehicle routing problems are defined based on the classical VRPs with thousands of customers. It is of great importance find efficient and high-quality solution for real-world applications. However, existing algorithms for VRPs including non-learning heuristics and RL-based methods, only perform well on small-scale instances with usually no more than hundred customers. They are unable to solve large-scale VRPs due to either high computation cost or explosive solution space that results in model divergence. Inspired by the classical idea of Divide-and-Conquer we present a novel Rewriting-by- -yeeeerrtinnegggeehe (RBB) framework with hierarchical RI. agents to solve large-scale VRPs. RBG consists a rewriter agent that refines the customer division globally and an elementary generator to infer regional solutions locally. Extensive experiments demonstrate the effectiveness and efficiency of our proposed RBG framework. It outperforms LKH3, the state-of off-the-art method for CVRPs, by 2.43% when customer number N 2000 and shortens the inference time by about 100 time!")
INTRODUCTION
The Large-Scale Vehicle Routing Problems (VRPs) is important combinatorial optimization problem defined upon an enormous distribution customer nodes, usually more than a thousand. An efficient and high-quality solution to large-scale VRPs is critical to many real-world applications. Meanwhile, most existing works focus on finding near-optimal solutions with only no more than a hundred customers because of the computational complexity (Laporte 1992] Golden et al. 2008 Brackers et al.] 2016). Originated from the NP-hard nature as a VRPs, the exponential expansion of solution space makes it much more difficult than solving small-scale one. Therefore, providing effective and efficient solutions for large-scale VRPs is a challenging problem (Fukasawa et al. 2006).
Current algorithms proposed for routing problems can be divided into traditional non-lcarning based heuristics and reinforcement learning (RL) based models. Many routing solvers involve heuristics as their core algorithms, for instance, ant colony optimization (Gambardella et al. 1999) and LKH3 (Helsgaun 2017), which can find near optimal solution by greedy exploration. However, they become inefficient when the problem scale extends. Apart from traditional heuristics, RL based VRPs solvers have been widely studied recently to find more efficient and effective solutions (Dai et al. 2017, Nazari al. 2018: Bello et al. 2017 Kool et al., 2019 Chen & Tian| 2019 Lu et al. 2020). Thanks to the learning manner that takes every feedback from learning attempts as signals, RL based methods rely few hand-crafted rules and thus be widely used in different customer distributions without human intervention and expert knowledge. Besides, these RL methods benefit from pre-training process allowing them to infer solutions for new instances much faster than traditional heuristics. However, current RL agents are still insufficient to learn feasible policy and generate solutions directly on large-scale VRPs due the vast solution space, which usually N! for N customers. More specifically, the solution space of large-scale VRPs with 1000 customers 2409 much larger than that of a small-scale one with only 100 customers. Consequently, the complexity makes the agent difficult to fully explore and makes the model hard to learn useful knowledge large-scale VRPs.
To avoid the explosion of solution space in large-scale VRPs, we consider leveraging the classic Londe-and-Conqueer idea to decompose the enormous scale of the original problem. In particularly,
Codes and data will be released at http://ghhaaaooR//i/a////eeeenn

---

Published as a conference paper at ICLR 2021
dividing the large-scale customer distributions into small-scale ones and then generating individual regional solutions to reduce the problem complexity. However, how to obtain a refined region division where the local VRPs can be handled effectively and how to coordinate iterations between global and local optimization efficiently remain two challenges of our VRPs solvers.
To tackle those two challenges above, we propose an RL-based framework, named Rewriting-by- Generating (RBG), to solve large-scale VRPs. The framework adopts a hierarchical RL structure, which consists of a "Generator" and a "Rewriter". Firstly, We divide customers into regions and use an elementary RL-based VRPs solver to solve them locally, known as the "Generation" process, After that, from a global perspective, a special "Rewriting" process is designed based on all regional generations, which rewrites the previous solution with new divisions and the corresponding new regional VRPs results. Within each rewriting step, we select and merge two regions into a hyper- region, and then further divide it into two new sub-regions according to the hyper-regional VRPs solution. By doing this, the problem scale is decomposed into pieces and the problem could be solved efficiently using regional RL-based solvers, and can still preserve the solution quality which is improved by the rewriter continuously.
Extensive experiments demonstrate that our RBG framework achieves significant performance in a much more efficient manner. It has a significant advantage on solution quality to other RL-based methods, and outperforms the state-of-thee size of N = 2000 and could infer solutions about 100 times faster. Moreover, it also has a growing superiority other methods when the problem scale increases.
LKH3 (Helsgaun] 2017). by 2.43% with the problem
Notations: We introduce some fundamental notations of large-scale VRPs, while the complete
formulation presented in the Appendix. Let G(V, E) denote the entire graph of all customers and the depot. Specifically, V = (wo. V1. .... U/. .... UN J. where up denotes the depot, and 1z(1 S S N) denotes the i-th customer with its location (I 34) and its demand d,. The edge ei.j. or E(v,, 02) in another manner represents the traveling distance between Us and Ey. Within the RBG framework, the generated regional VRPs solution T {Uk,0 1 Uk,2, .. NK,N, } of the divided region G3 has a corresponding traveling cost C(TT)) = En E(vu, 11,441). 1. The entire solution of all customers is denoted by æ.
RELATED WORK
We discuss previous works which are related to our research in the following two directions:
Traditional Heuristics. Since the exact methods (Laporte] 1992 Laporte & Nobert 1987 Holland 1992, Baldacci et al. 2010) are almost impossible to solve VRPs within a reasonable time due to the high computation complexity, researchers developed heuristics, i.c., non-exact methods, to find approximation solutions instead. Tabu search is one of the old metaheuristics (Glover) 1990b a
Gendreau et al. 1994 Battiti & Tecchiolli 1994). which keeps searching for new solutions in the neighborhood of the current solution. Instead of focusing
improving merely one solution, genetic algorithms operate in a series of solutions (Goldberg) 1989 Holland 1992). It constructs new struc- tures continuously based on parent structures. Instead of treating objectives be optimized altogether, ant colony optimizations as another widely accepted solver, utilize several ant colonies to optimize different functions: the number of vehicles, the total distance and others Gaaebarllaaa
al.) 1999]
Dorigo et al.) 2006 Dorigo & Di Caro 1999). Meanwhile, recreate search methods keep constructing the current solution and ruining the current ones to build better solutions (Schroiis.SSiiip et al., 2000). This
helps to expand the exploration space to prevent the local optimum. Among these categories, LKH3 is a state-of-the-art heuristic solver that empirically finds optimal solutions (Helsgaun) 2017).
Although these heuristics, compared to exact methods, can improve searching efficiency, they are still much too time-consuming when applied to large-scale VRPs with the acceptable performance required, and may fail to respond to any real-time solution requests.
RL based VRPs Solutions. Since the learning manner of reinforcement learning allows the agent model to directly infer solutions based
pre-trained model with much shorter computation time, RL becomes a compelling direction on solving combinatorial optimizations. It has been successfully applied in VRPs particularly (Bello et al. 2017, 77 Nazari et al.) [018 Kool et al.) 2019). Viiyaals et al.) (2013) was the first to adopt deep learning in combinatorial optimizations by a novel Pointer Network model. Inspired by this, Bello et al. (201)) proposed to use RL to learn model parameters as an
2

---

Published as a conference paper at ICLR 2021
optimal strategy instead of relying ground-truth in supervised learning way, which demonstrates the effectiveness on TSP and the knapsack problem. Nazari et al. (2018) further followed the idea to solve VRPs with attention mechanism as augmentation, and Kool et al. (2019) solved more generalized combinatorial optimization problems. Other than using the idea of Pointer Network k, Dai et al.] (2017) develops their method over graphs via Q-learning (Sutton & Barto 2018), so that the solutions could have better generalization ability. Chen & Tian (2019) proposed a local rewriting rule that keeps rewriting the local components of the current situation via a Q-Actor-Critic training process(Sutton & Barto 2018). [u et al. (2020) further developed a Learn-to-Iterall structure that not only improves the solution exploration but also generates perturbations to avoid local optimum. This is the first machine learning framework that outperforms LKH3 CVRPs (capacitated VRPs), both in computation time and solution quality.
However, these existing RL based methods only achieve promising results without any hand-craft rules and expertise at small scales with usually no more than a hundred customers. The proposed models cannot be trained for mhousand-customer-lee extend exponentially as the number of customers increases, and it will be hard for the model to learn useful route generation policy. In contrast, we propose RL based framework formed upon the classical idea of Divide-and -nddl-----Cenee to solve the large-scale challenge.
VRPs because the state space and action space
SWWRITING-BY-ENERRRE
Figure shows showw the overview structure of our proposed framework, named
Hierarchical Agents
(RBG). Along with the fundamental idea of Divide-and- Cannu-ur to decompose the enormous problem scale dis- cussed previously, we aim at dividing the total customers into separate regions and generate near-optimal solutions individually. To achieve this, we design hierarchical RL structure including two agents which take different functions.
The Total Customers
Rewriting
Divide
Divide
Divide
Divide
Region A
Region
Regian
Generating
Generate
Generate Solution
Generate Solution
Generate
Solution
Solution
First, to refine and obtain more rea- sonable division results, we design the "Rewriting" process which keeps up- dating new divisions by rewriting the previous ones and their corresponding regional solutions. The division quality is critical to the final solution since customers from different regions cannot be scheduled upon the same route. Within each rewriting step, the agent selects and merges two regions based on their generated solutions. A new solution will be generated upon the merged hyper-region in the following step, and the rewriter will further divide the merge hyper-region back to two new regions. Since the exploration on different customer composition is complicated and it is not trivial measure the direct influence to the final performance in terms of traveling distance, an RL-based rewriter is wise choice to learn the selection and merging action. We will show that the model converges and achieves high performance when the rewriter agent learns a stable division result in Section 4.
Figure I: The overview of the Rewriting-by-GGnerating
Second, to reach the global solution from the regional scratches, we employ an elementary VRPs generator that generates solutions to each region, known as the "Generating" process. Considering the time efficiency and the ability to learn solve certain customer distributions when the division updates continuously, also apply an RL agent to learn to generate solutions on these smaller-scale regions.
Overall, we develop a hierarchical RL framework by coordinating the rewriter and the generator in two different scales iteratively. The rewriter updates new division and brings new customer distributions to the generator, while the solutions from the generator formulate key component of the rewriter. From the technical perspective, is worthy to note that the merging- repartionng operation that rewriter conducts is also adopted in previous neta-heuuisticssBaaer & Ayechew
3

---

Published as a conference paper at ICLR 2021
1. Initialice the Partition
4. Merge Two Regions
5. Generating Solutions
Rewriting
2. Generating Solutions
3. Re partitioning
Figure The core idea behind our Rewriting-by-Genreee ber-ber---nnngnnggg framework, where nodes denote customers with color representing regions, and solid lines denote routes.
2003 Bell & McMullen 2004), while we replace the handcrafted heuristic with learning agent. The global RL based rewriter responsible for managing inter-regional exploration while the generator optimizes local results. The combination of Operation Research (OR) heuristics and RL guarantees an effective exploration process as well as achieving high computation efficiency from the prospect of fast solution generation on inference instances.
First, we cluster customers into several initialized hyper-regions. Second, we generate initial regional VRPs solution individual hyper-regions via our elementary VRPs generator. Third, we utilize the rewriter to partition the merged graph to two sub-regions. Then rewriter picks up two sub-regions via the attention mechanism and merges them into one hyper-region, and then generates the hyper-regional solution of the merged hyper-region. After that, we go back to the third step re-partition the hyper-region into sub-regions in loop. Through this process, the partition becomes more reasonable and the solution gets better and better. Finally after enough steps of rewriting are able to reach good solution.
For brevity and clarity, we summary the pipeline as five steps, as shown in Figure 2
3.1 REGION INITIALIZATION
Owning direct intuition that the spatially close customers are more likely to be scheduled within the same route in an optimal solution, an initial division based on the spatial locations is reasonable and benefits later convergence of the model's training. Therefore, we cluster customers according to their locations and divide the entire graph G(V, E) into subgraphs G; the initialization. We adopt K-means in this step for its effectiveness (Wagstaff et al. 200T). To accommodate to generator model below, set K properly Besides, order to make full use both customer locations and the depot location for clustering, set the distance used for K-means polar distance dP, which is calculated using the cosine of the included angle @ in the polar coordinate system, whose center is at the depot and the axis is a fixed line. So the overall distance between customer i, j is dijj d + Bdf In experiments we set / to be 0.1. The detailed intuition analysis and ablation study 9 can also
that the number of customers in each cluster is around 100.
linear combination of the Euclidean distance dE and the
y found in Appendix.
3.2 GENERATING
For small-scale VRPs in merged hyper-regions, we follow the Attention Model (Kool et al., 2019) proposed for routing problems, such as CVRPs, TSPs and other variations. The attention model consists of an encoder to produce embeddings of all customers and a decoder to produce the strategy sequence. When a partial tour has been constructed, canmot be changed, and the remaining problem to find the following path from the last customer. The model benefits from the strong context representation ability of attention and the separate off-line inference stage of RL, and thus could generate high-quality solutions within extremely short period.
4

---

Published as a conference paper at ICLR 2021
Though cannot directly apply it to large-scale problems as it is not trainable at large scale, it is a good choice to use in small-scale local regions to achieve plausible results. To accelerate the training,
the pre- rre-trained model trained on wwo-center-clustendd customer distribution and fine-tune it during training to suit the distribution in hyper-regions. Following Kool et al. (2019), we the solution cost rewards and REINFORCE algorithm (Williams) 1992) for the training of the generator.
with rollout baseline
3.3 REWRITING
The rewriter agent conducts a meraingg--mgiiinneertiiiiiii be detailed, we consistently employ the attention mechanism to select region-pairs and merge them into hyper-regions. According to the newly generated solutions from each hyper-region, we further partition each hyper-region based on the inside routes into two regions.
process to update region divisions. To
We first generate the regional representations for region selection. We obtain local solutions from the generator in each region, in which different routes represented by sequences inside one region are sent as the input to an LSTM based network (Gers et al. 1999) to capture the sequential features. Further, we take the mean value of the outputs from LSTM of each route in a region and process using a fully connected network to generate the d, di.ddimnnioona feature h; for each region G;,
1 N W
h4
LSTM( +b,
where W and b" are shared weights and bias respectively, N; is the number of routes in region G Ti.j = (vo; Ui Ui.j2, Vi.j.m..y? vo) is the j-th route starting and ending the depot to in region Gi. and hú as the representation of each region G; for further process. All regions share the same region encoder and parameters.
With the well represented regional features, we first select region-pairs for further merging and repartition via the attention mechanism. The selection is processed in two steps to generate the oggion-pair... First we compute the selection probability Pi,j
Pij softmaxxeu, hy),
So for each region G., Pi. Pt. sums up one. To ease the training, for each region G, restrict U: to the K nearest regions to G; and set Pi,j = 0 for j g U.. We intuitively set K=5,8,9 for N=500, 1000,2000 cases, respectively, to allow for more neighbors considered as the problem size increases and spatial size of one region becomes smaller. Then we visit every region G, in randomized order and select its pair region G, with probability Ps,, form the region-pair (G,, G2). We drop region-pairs that intersect with previously chosen pairs. After this, we will obtain bunch of region- -aaios with no intersections with each other.
For each selected region-pair (G;,G)) we now merge them together into a hyper-regional subgraph Gmerge = G. + Gj. and regenerate the corresponding hyper-regional VRPs solution o. merrge over the subgraph using the elementary VRPs generator. Since the hyper-regional solution considers the customer information more globally, it is comprehensible that the newly generated solution π "errge is more likely to obtain better quality than of + Tÿ.. the new solution is better than the previous one, we accept the updating on the overall solution of all customers as follows,
o T/ + n "merge"
To maintain the regional-scale consistency and prevent the dilation of any subgraph for further process, we repartition the merged hyper-region Gmerge back to regular sized region Gy and Gyr. Due the same intuition in the initialization that optimal solution is more likely to assign close customer into the same route, we calculate the spatial center of all customers within one route as its representations and use principal component analysis (PCA) to reduce the representations to dimension, and then divide all routes by sides into two new regions Gy and Gj: with similar number customers.
To summarize, the rewriter takes selecting merging-repartinn sions. Such a step is called a rewriting step, or a rollout step. The rewriting is optimized with the performance improvement of the new division to the previous one.
process to update region divi-
5

---

Published as a conference paper at ICLR 2021
3.4 OPTIMIZATION VIA REINFORCE
In the above-mentioned steps, the repartition takes place on the route-level, which does not change the total distance cost. This means the total cost is only influenced by merging and recalculation. Hence we define the reward function for one region-pain (G,, Gy) as follows.
((+)) + C(T)) C(
(4)
describes how the solution improved in each round. Meanwhile, guarantee an effective iteration, if the new generated solution is worse than the previous one, we reject the updated partition and solutions and continue the next rewriting step.
According to the reward, we optimize the model by gradient descent via REINFORCE method (Williams, 1992) with a baseline. To reduce the variance of the gradient propagation, we define the baseline b as the running average of the rewards.
PERFORMANCE EVALUATION
Dataset. CVRP is typical variant of VRP with capacity constrains. Generally, if models can work well on CVRP, it is easy to transfer to VRP by removing the capacity limitation. We follow the similar data generation method as the CVRP evaluation settings from previous works (Nazari et al. 2018: Kool et al.] 2019; Chen & Tian 2019) for consistency and fair comparison. The location of each customer and the depot (x,, y1) is sampled uniformly from a unit square, which means both T; and y sampled uniformly from the interval [0, 1]. The demand d; of each customer is sampled from the discrete set {1, 2, .... 9}, and the capacity of the vehicle is 50. For simplicity, we fix the depot at the central of the area. For random depot cases, we can simply shift and scale the data to make the depot central and customers in [0, 1] x [0. 1], and the result will still be good as shown in experiments below. The traveling distance between two customers or the depot are calculated directly using the inner Euclidean distance.
Evaluation Protocols. We consider three different evaluation settings for large-scale CVRP with customer amount N = 500, 1000, 2000 respectively. During the training process, we use a learning rate of 0.00003 for funetuning the generator and 0.001 for training the rewriter with SGD. At training, we run 10 rollout steps for each sample and randomly rotate the positions of all customers along the depot each step to make training data near-i.i.d. distribution. We train for a total 10000 samples. At evaluation, we run for 100 rollout steps (i.e., rewriting steps) and take the solution at the last step as the final solution. Our method implemented in Python via Pytorch framework, and the experiments are run on 4 Nvidia 2080Ti GPUs.
4.1 PERFORMANCE COMPARISON WITH BASELINES
In Table T first present the performance of Randomly Generated whose routing solution is generated completely randomly as a background performance of the evaluated instances. Then, we compare our proposed RBG framework with other state-of-the-ar baselines, including the heuristics and the RL ones. Ant Colony (Gambardella et al., 1999) and LKH3 (Helsgaun) 2017) are two classic state-of-the-ar heuristics, and OR Tools (Google 2016) is the widely-used combinatorial optimization solver developed by Google. As for the sfate-of-the-art RL baselines, we select the Attention Model (Kool et al. 2019) which generates the solution tour by steps and the ReWriter (Chen) & Tian 2019) that rewrites the previous solutions for improvement. Specifically, we both evaluate the performance of Attention Model trained on only 100 (i.e., original design) and the according amount of customers. The time is computed as the average solution time for one instance.
As shown in Table T. our RBG framework outperforms all other baselines on N 2000, and is only slightly outperformed by LKH3 on N = 500 and N = 1000 with extremely narrow gaps with regards to the total distance, i.e., objection. It is interesting to find that the performance gap from LKH3, the state-of-the-art algorithms compared to both heuristics and RL based methods, keeps decreasing when the size of customers increases. When N = 500, the performance gap is 2.82%, and reduces to 0.99% when N 1000. While RBG eventually outperforms LKH3 by 2.43% when the customer size keeps expanding to 2000. This demonstrates that our RBG framework not only generates high-quality solutions when the problem is a large scale but also has a growing

---

Published as a conference paper at ICLR 2021
Table 1: Overall performance comparison. The objection is the average total route length (less is better). Time is the average time to solve a single instance (less is better). AM_ 100 is the AM model trained on N=100 size, and AM is trained on the corresponding sizes and tested on the same size.
N
500
N = 1000
N 2000
Obj.
Time
Obj.
Time
Obj.
Time
Randomly Generated
273.49
546. 12
1091.35
Ant Colony Gambardella et al. 1999
61,55
20min
112.28
50min
207.56
2h
LKH'S melsgaun 2017
49.83
5min
94.93
18min
185.70
80min
OR Tools (Googic 2016
54.72
20s
100.77
80s
186.95
5min
ReWriter (Chen Tian, 2019
60.67
33s
108.82
37s
198.76
Smin
AM 100-greedy (Kool el al.
201
55,48
50ms
106.60
100ms
218.68
200ms
AM 100-sampling (Kool el al.
2019
55,21
12s
116.41
18s
280.38
39s
AM-greedy (Kool et al. 2019
290.68
50ms
637.17
100ms
998.56
200ms
AM-sampling [Kool et al.
2019
269.31
12s
603.70
18s
954.95
39s
RBG
51.24
7s
95.87
15s
181.19
30s
advantage to other methods when the problem scale grows. This is of great practical value since maintaining solution quality is critical to many realistic industrial applications in which a vast number of customers may occur frequently /Amold et al. (2019).
We can further observe that learning RL-based solvers from scratch on large scale VRP cannot reach acceptable results shown by AM-gready and AM-sampling, the costs of which are close randomly generated, because the training is unable to converge due to large action space and the delayed reward. In contrast, learning iteratively learning to generate (ReWriter and Am-train _asi________ mo0) can improve the performance remarkably. Moreover, our proposed RBG can consistently achieve favourable objection gain compared to those two baselines. This further justifies the superiority of our heuristic RL design.
Apart from the solution quality, RBG also has remarkable inference efficiency. It only costs 30s to obtain the solutions to the instances with N = 2000. Compared to LKH3, the state-of-the art method that has close performance to RBG, our framework works about 100 times faster. A plausible reason is that LKH3 must infer solution for each new problem from scratch, while our RI.-based model can learn policy from the prior instances and generate solution promptly. Consequently, the ability of fast-responding to new instances makes our proposed RBG framework adaptive to situations where instances require real-time responses.
4.2 ANALYSIS OF REWRITING STRATEGY
In our framework, we propose two RL agents to perform different functions. Since previous literature has demonstrated the effectiveness of the generator RL, i.e., the Attention Model (Kool al. 2019) in small scale VRPs, here in this section, we aim at discussing the influence of the rewriting RL.
Firstly, we showcase the importance of rewriter learning the overall performance. To achieve this, we maintain the RBG framework without selecting regions from the RL agent. Instead, we randomly select two adjacent regions at each step directly. The comparison is shown in Figure 3 The y-axis is the ratio to the best performance minus one. We can observe that RL can both improve better and faster than random adjacent selection.
Besides, we analyze the extent and the frequency of repartition along with the performance improve- ment. Figure H(a))shws the reallocation ratio by rollout steps, which is the ratio of customers reallo- cated after a repartition operation. It is calculated as min(G; G, nGg, G, G (GG,GGG,, +G)) Figure (4b) shows the rate of repartition being accepted. Figure [cc) shows the normalized traveling cost ratio along with rollout steps by the minimal cost. We found that the reallocation ratio and the partition update rate decreases significantly as long as the traveling cost decreases. The similar decreasing trend among them demonstrate that the improvement of the solution quality is highly related to the extent and frequency of rewriting. The rewriter finally tends to stop its rewriting operation when the solutions are close to optimal.
In conclusion, Rewriter shows its effectiveness on improving the solution quality during the instance inference.
7

---

Published as a conference paper at ICLR 2021
10-3
10-2
10
10-3
10
10-3
Ratio
Rabio
10-4
10
10"
N=500, Adjacent
10:5
N=1000. N=100o.Adjecent
10"5
N=2000 Adjacend
RL
10
N-1000,AL RL
10-6
N-2000.AL
100
50
100
50 Rollout Steps
100
Rollout Steps
Rollaut Steps
(a) N = 500
(b) N 1000
(c) N 2000
Figure 3: Comparison between RI. and adjacent selection. The "Ratio" metric is the ratio of performance the best performance obtained by these two strategies minus one. In order for clarity, it is plotted in log mode. A rollout step is rewriting step, i.e. we divide-merge--reennenat the solution once. We run 100 rollout steps for each instance at evaluation.
Reallocation Ratio
0.04
500
Partition Update
500
1.03
500
1000
0.3
1000
1000
0.03
2000
2000
Traveling Cost
2000
0.2
1.02
0.02
1.01
0.01
0.00
0.0
1.00
0
50
100
0
50
100
50
100
Rollout Steps
Rollout Steps
Rollout Steps
(a) Reallocation Ratio
(b) Partition Update Rate
(c) Traveling Cost Ratio
Figure 4: Statistics of the rewriter at different rollout steps.
4.3 ANALYSIS OF ROBUSTNESS DATA DISTRIBUTION
We conduct experiments to show- case the robustness of RBG to dif- ferent data distributions. Follow-
Ratio to Performance LKH3
ing the same protocol of data gen-
Random Depot, Random Customer
eration in Fukasawa et al.) (2006).
1.05
Central Depot, Clustered Customer
we test RBG compared to LKH3 in three different scenarios in Fig Random depot, random cluster, in which the depot and the customers
1.04
Central Depot, Random Customer
Depot. Random- Clustered Customer
1.03
LKH3
1.02
are all located randomly, 2) Central depot, clustered customer, whose customers distribute in several clus- ters, and 3) Central depot, random- clustered customer, in which half customers are generated randomly, and the others gather several clus- ters, 4) Central depot, random cus- tomer, which is the same with our training setting. In all these scenarios, the RBG trained on the central depot and random customer data. For comparison, the performance of RBG in each scenario is normalized by the corresponding L.H3 traveling cost.
1.01
1.00
0.99
0.98
10
20
50
Rollout steps
Figure 5: Performance on different data distributions.
We find that our proposed RBG performs well across different data distributions and the decrease trends of the traveling cost are similar. Specifically, RBG outperforms LKH3 at about the 5-th, 10-th and 50-th step in the last three groups. Clustered customer is the only case where RBG is outperformed by LKH3. A plausible reason is that the clustering of the customer distributions make it easier for the LKH3 to find the close customers within the same cluster and assign them to the same route,, and thus the advantage of dividing customers into reasonable regions is weakened. However, RBG still obtains high-qn qugh-qulity solutions with performance loss of no more than 0.1%. Detailed visualization is presented in Appendix.
8

---

Published as a conference paper at ICLR 2021
5 DISCUSSION AND CONCLUSION
In this paper, we propose the problems. The framework generates regional routing solutions within each independent regions, and rewrites its previous performance by merging and repartitioning region pairs via an RL based agent. We demonstrate our framework generates high-quality solutions efficiently, and the performance advantage to other methods even increases when the problem scale expands.
framework for solving large-scale routing
Apart from solving VRPs efficiently as demonstrated by our experiments, our framework provides way of enhancing the learning nature of RL mechanism with hcuristic operations to solve a variety of large-scale scale optimization problem hierarchically.
needs minor effects to adopt our RBG for other problems which existing learning methods are only able to handle at small scale, and the key to replace the generator by corresponding solvers. As the future work, we plan to generalize our framework to large-scale routing problems with different constraints well other NP-hard problems.
REFERENCES
Khaled Alsabti, Sanjay Ranka, and Vineet Singh. An efficient k-means clustering algorithm. 1997.
Florian Amold, Michel Gendreau, and Kenneth Sörensen. Efficiently solving very large-scale routing problems. Computers & Operations Research, 107:32-42, 2019.
Barrie Baker and Ayechew, A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 3065):787-800, 2003.
Roberto Baldacci, Enrico Bartolini, Aristide Mingozzi, and Roberto Roberti. An exact solution framework for broad class of vehicle routing problems. Computational Management Science, 223)2229-268, 2010.
Roberto Battiti and Giampietro Tecchiolli. The reactive tabu search. ORSA journal on computing, 6(2):126-140) 1994.
John Bell Patrick McMullen. Ant colony optimization techniques the vehicle routing problem. Advanced engineering informatics, 18(1):41-45) 2004.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. 2017.
Kris Brackers, Katrien Ramackers, and Inneke Van Nieuwenhuyse. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 09:300-313, 2016.
Xinyun Chen Yuandong Tian. Learning to perform local rewriting combinatorial optimization. In Advonces Neural Information Processing Systems, pp. 6278-6289, 2019.
Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Song. Learning combinatorial optimization algorithms over graphs. pp. 6351-6361, 2017.
Marco Dorigo and Gianni Di Caro. Ant colony optimization: new meta-heuristie. Proceedings the 1999 congress on evolationary compulation-CECC (Cat. No. 99TH8406), volume 2, pp. 1470-1477. IEEE, 1999.
Marco Dorigo, Mauro Birattari, and Thomas Stutzle. Ant colony optimization. IEEE computational intelligence
magazine, 1(4):28-34 39, 2006.
Ricardo Fukasawa, Humberto Longo, Jens Lysgaard, Marcus Poggi De Aragão, Marcelo Reis, Eduardo Uchoa, and Renato Werneck. Robust branch-and-cut-ane -nniii--- for the capacitated vehicle routing problem. Mathematical programming. 106(3):491 511, 2006.
Luca Maria Gambardella, Éric Taillard, and Giovanni Agazzi. Macs-vrptw: multiple colony system for vehicle routing problems with time windows. New Ideas in Optimization, pp. 63-76. MeGraw-Hill 1999.
Michel Gendreau, Alain Hertz, and Gilbert Laporte. tabu search heuristic for the vehiele routing problem. Management science, 40 12610))127--1200 1994.
Felix Gers, Jürgen Schmidhuber, and Fred Cummins. Learning to forget: Continual prediction with Istm. 1999.
Fred Glover. Tabu search- part ii. ORSA Journal computing, 2(1):4-32, 1990a.

---

Published as a conference paper at ICLR 2021
Fred Glover. Tabu search part i. INFORMS Journal Computing, 2:4-32, 01 1990b.
David E Goldberg. Genetic algorithms search. Optimization, and MuchineLearming, 1989.
Bruce I. Golden, Subramanian Raghavan, and Edward A Wasil. The vehicle routing problem: latest advances and new challenges, volume 43. Springer Science & Business Media, 2008
Google. Or-tools. attpss//teeveLpperss.gggg com
2016.
Keld Helsgaun. An extension of the fin-kernighhnn-hessaan tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
J H Holland. Adaptation in Natural and Artificial System. 1992.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! 2019.
K Krishna and M Narasimha Murty. Genetic k-means algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part (Cybernetics), 29(3):433-445) 439, 1999.
Gilbert Laporte. The vehicle routing problem: An overview of exact and approximate algorithms. European journal of operational research, 59(3)345-335, 1992.
Gilbert Laporte and Yves Nobert. Exact algorithms for the vehicle routing problem. In North-Hollandd Mathematics Studies, volume 132, pp. 147-184. Elsevier, 1987.
Hao Lu, Xingwen Zhang, and Shuang Yang. learning-based iterative method solving vehicle routing prohlems. In International Conference on Learning Representations, 2020.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence V Snyder. and Martin Takac. Reinforcement learning for solving the vehicle routing problem. pp. 9861-98777 2018.
Gerhard Schrimpf, Johannes Schneider, Hermann Stamm- Wilbrandt, and Gunter Dueck. Record breaking optimization results using the ruin and recreate principle. Journal of Computational Physics, 159(2): 139 171, 2000. ISSN
doi: https://doi.oor//100/ http:///.........../oo.......... 6413. sciencedi wentt, www. htt.a//sw....eeeeeeeecoooo//////
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in neural information processing systems, pp. 2692-2700, 2015.
Kiri Wagstaff, Claire Cardic, Seth Rogers, Stefan Schrödl, ct al. Constrained k-means clustering with background knowledge. In leml, volume I, pp. 577-584, 2001.
Ronald Williams. Simple statistical cradient-following algorithms for connectionist reinforcement leamning. Machine Learning, 8())229 256, May 1992. ISSN 1573-0565 doi: 10.10077BF00992269. URL [t tps 7/doi mroni.org/100 1000/100.00///8000922200
A APPENDIX
A.1 PRELIMINARY OF VRP
this paper, we evaluate our work on CVRP specifically. present a complete mathematical formulation in this section. CVRP involves one depot and several customers with different demands to need. The task is to determine the routes for vehicles with limited capacity traverse all the customers, and the target is minimize the total traveling cost.
G(V, E') denote the graph consisting depot customers. Specially, [Vo. Vi.... Vi. ... UN ). where vo denotes the depot, and (1 S i S N) denotes the customer with location (z,, yr) and demand d, For each pair of node and j. the edge ei or E(v, Uy) in another manner represents the distance between node i and j. The capacity of the vehicle is denoted by D, is the constraint the maximum of its loaded shipment. Each vehicle also has demand denoted by delivered. We denote solution the subgraph G; as ग. (vx,0, U.. Uk, and the corresponding as C(Txx) Ny F( vk.+ The entire solution of all K subgraphs is denoted by n.
vehicle must return the depot vp reload when all goods
10

---

Published as a conference paper at ICLR 2021
With the above notations, mathematically define VRP follows,
min En=n C(TT))
(5)
s.t. U
Am DAK
(6)
mm An
n, d: Dm, to & mm Vq P.qENPEN
Σ -=p
(8)
where constraint (2) and (3) ensure all customers visited and only visited once with demands satisfied. (4) indicates the capacity constraint.
A.2 ANALYSIS ON DIFFERENT INITIALIZATION STRATEGIES
Due to the intuition that the glosely-distriben customers more likely to appear in the same route in optimal solution, cluster the customers according their locations discussed in Section 3. However, the detailed spatial feature used clustering may vary. Hence we analyze two different ways measure the related distance between two customers and j: 1) Euclidean distance, di,, and 2) the polar distance, df.,,, which is calculated using the cosine of the included angle 9 in the polar coordinate system, whose center is at the depot and the axis is fixed line. The initial partition in Fig shows example of how customers are divided only according their cosine distance.
10025
500
1000
10020
2000
10015
ratio
10010
10005
100000
0.1
0.2
0.5
10
Figure 6: Ablation study on distance factor(beta) for clustering
To measure the influence of the two partition features, we combination of them, df,, 3df to represent the distance between customer and j. where is hyperparameter. The initialization is obtained via the classical K-means algorithm Krishna & Murty 1999 Alsabti et al. 1997) and the results are shown in Fig The traveling costs are normalized by the minimal one. We find that the generated solutions has the best quality when 8 = 0.1. Euclidean distance a straightforward feature to measure the closeness of customers, but the division that relies on it only may generate clusters that far away from the depot. The corresponding route may suffer from great distance cost to travel from the depot the cluster, and then back the depot. While the polar distance can prevent this shortage. appropriate combination of them can benefit the RBG framework to obtain higher performance.
It is also remarkable to point out that the spatial feature combination has a low fluctuation range. The worst performance in every customer scales is no worse than 0.25% than the optimal one. This shows the great robustness of RBG to different initialization strategies.
A.3 VISUALIZATION OF INFERENCE
We present the visualization of the initial and final solutions in all three customer scales, shown in Fig It worthy mention that due the initialization based on spatial features, the initial routes appear to be more gathering in space. Different routes can usually be separated by a clear boundary between them. However, in the final solutions which are rewritten and regenerated for steps by RBG, the routes tend to have more complicated intersections in space. This is because other factors, including the customer demands and the capacity are further considered by RBG and more reasonable divisions and routes undated.
11

---

Published as a conference paper at ICLR 2021
04
04
02
02
80
(a) The initial solutions, N 500, cost=51.97
(b) The final solutions. 500, cost=50.97
04-
04
02
02
00-
(c) The initial solutions, 1000, cost=102.09
(d) final solutions, 1000, cost=99.01
86
04
84
02
(e) The initial solutions, 2000, cost=190.45 (f) final solutions, 2000, cost=184.48
Figure 7: Visualization initial and final solutions of different scales. The big red point at the center represents the depot, and each blue point represents a customer. Routes with the same color are the same region. For clarity in visualization, we omit the line segment from depot the first customer and from the final customer back to depot for each route.
A.4 VISUALIZATION SOLUTION DIFFERENT DATA DISTRIRCTION
A.5 GENERALIZATION ABILITY
Considering that RL based model has generalization ability, that is to train and infer on different instances. we further design experiments to show how RBG performs in this Specially, train model for = 500. 1000, and 2000, and compare travel Table The similar results demonstrate the good generalization ability of our RBG.
12

---

Published as a conference paper at ICLR 2021
10-
88
06-
06
04
-02
90
92
0.4
0.
0.0
1.0
12
-02
0.0
0.4
06
0.0
10
(a) N 2000 instance of random depot data
(b) Solution, cost=274.17
1.0
0.
06
-02
-02
0.0
0.6
1.0
0.0
0.4
1.0
(c) N 2000 instance of clustered customer data
(d) Solution, cost=146.35
10-
08
08-
06
06
-02
-02
0.0
8.
0.4
0.6
1.0
-02
-02
0.0
022
0.4
06
0.8
100
(e) .N 2000 instance of mandom-clustere cus-
(f) Solution, cost=199.71
tomer data
Figure 8: Visualization on graphs and solutions of different data distributions. The big red point represents the depot, and each blue point represents a customer: Routes with the same color are in the same region. For clarity visualization, we omit the line segment from depot to the first customer and from the final customer back to depot for each route.
Table Generalization ability on scales
Test on
500
1000
2000
500
51.24
95.88
181.24
Train on
1000
51.22
95.87
181.28
2000
51.22
95.89
181.19
13


Reviews:
[{"review_id": "vpsSK6ZLU0j", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a learning approach for developing heuristics to solve the capacitated vehicle routing problem (CVRP).  The paper is clearly written and easy to follow.  \n\nMy main concern is related to generalizability of the proposed solutions.  Learning to optimize is an important emerging area. What is missing in this work is what the generalizability of the proposed methods to other combinatorial problems is. Specifically, why did the authors choose VRP?  VRP, though important, is a very specific problem with a lot of very good solutions using simple combinatorial techniques.  The other concern is related to the proposed techniques.  The approaches suggested by the authors, viz., partitioning the input, and rewriting the basic VRP solution by merging regions and recomputing routes, are also adopted by the meta-heuristics developed and used in the commercial OR solvers. \n\nAnother big drawback with the current model is that it does not address many constraints/considerations in real VRP applications that typical solvers address - different costs per vehicle, cost of missed shipment, route limits, dimension limits, alternate visits, etc.  Even the more realistic fixed number of vehicles case is not considered in the proposed solution.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "iYxNLEjJJQU", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "An RL based method, called Rewriting-by Generating (RBG), is proposed to solve large-scale VRPs. It borrows the idea of the hierarchical RL agent, which consists of two parts: \"Generator\" and \"Rewriter\". In the generation process, the graph is divided into several sections and in each section, an RL algorithm runs to get the best route. Then, the rewriter gets the solution of all generators and tries to connect them together with the goal of globalizing them with a smaller route. To this end, the rewriter merges each of two sub-problems together and then divides it into another two sub-problem and solves each again. Doing this helps decrease the route length. This diving and merging is learned by an RL agent (think of the outer agent in the hierarchical RL) so that the rewriter learns when and how to do this. The rewriter uses the attention mechanism to choose two parts of the merged routes, and then get a new solution for each part using the inner-agent. To get the initial sub-problems, K-mean clustering is used to get sub-problems of about 100 nodes. In the evaluations, CVRP of size 500, 1000, and 2000 are considered. The results are compared to LKH3 and google OR-Tools, along with RL algorithms. LKH3 slightly outperforms RGB in terms of the tour length in problems of 500 and 1000 nodes, though it takes a longer time to get the solution.\nQuestion-1: How did you define a route $\\tau_{i,j}$? How many of them can be there? \n\nminor typo:\nThen we then visit", "extra_scores": {}, "extra_text": {}}, {"review_id": "axQ2nQFtpYC", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nThe paper proposes an extended framework for neural combinatorial optimization of the vehicle routing problem.\nWhereas earlier works focused on the optimization of the whole solution at once, this method adds an abstract step to group and rewrite only parts of the route in a \"divide-and-conquer\" manner that allows the neural solver to focus on smaller subproblems and thereby avoid problems when scaling the problem to larger sizes.\nThe neural solver is based on the existing literature and the overall method is trained, as it is common in these papers, via Reinforce.\nThe method is well introduced and an experimental evaluation is performed on CVRP instances from 500-2000 customers, showing good scaling abilities of the presented method.\n\n# Comments\n\nThe interest in solving combinatorial optimization problems using ML/RL is high and the method is a timely advancement in this area, since it addresses one of the main issues in earlier work, which is how to scale to larger instances.\nThe approach to repeatedly solve smaller subproblems of the large instance to achieve local improvements of the global search is an established technique and has been widely applied in the mathematical optimization community and operations research.\nIt is therefore reasonable to transfer the concept.\nThe application is straightforward and the main contribution of the paper is to apply this kind of divide-and-conquer and the selection of the partitions to merge and optimize using a LSTM model rather than a purely heuristic or random selection, which gives some small additional improvement.\nThe results show good improvements for large instances and the framework is general enough to be combined with new neural solvers, which will improve its adoption in the future.\nThe contribution is therefore valuable to the community since it introduces concepts that might not be known, but they are not particularly novel.\nNevertheless, the results are strong and the paper will be of interest to parts of the community.\n\nRegarding the experiments, I'm not entirely clear how the baseline results are achieved.\nAnt Colony Optimization is a surprising choice for a metaheuristic baseline and I'd guess that there should be better alternatives, but I'm not too familiar with the most recent literature here. Finding something more recent or performant would however strengthen the presentation of the results, even though I do not expect it to outperform the presented method.\nIs OR-Tools run with a timeout or is it solved to optimality? Which CVRP model was used there?\nIn general, is there any information about the optimality gap of the found solutions?\n\nIn Sec. 4.2 (Analysis of Rewriting Strategy) I do not completely follow the metric used to compare both selection strategies.\nCould the authors clarify this?\nAlso, the difference between both strategies are mostly small, which indicates that most of the performance benefits stem from the partitioning & rewriting in general and less from the learned selection strategy.\nSince one of the strategies is random, did the authors test to pick a fixed heuristic strategy, e.g. pick the adjacent partition that has not been touched the longest or that had the biggest improvement before (or any other, there are several choices)?\nDid you have a look at the strategy the LSTM converges to?\n\n# Minor Comments\n\nThere are a couple of language problems in the paper and an additional round of proof-reading would be beneficial.\nE.g. the \"problem\" in the title should be plural, the first sentence in the 2. paragraph of page 1 has some extra words (\"those two lines\"), and there are multiple other issues.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_aIBP_iWfJ", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n--------------\nThe paper presents a hierarchical reinforcement learning approach to solve large-scale vehicle routing problems (VRPs). A “rewriting agent” is responsible for dividing the customers into regions while a “generating agent” is responsible for computing the vehicle routes in each region, independently. The rewriting agent learns to score pairs of regions to be merged, using as a reward the reduction of VRP cost gained by the merge. The VRP costs are computed by the generating agent, which is based on the attention model of (Kool et al 2019), that is known to perform well for smaller scale VRPs. \n\nStrong points\n-------------------\n1. The main contribution of the paper is the novel rewriting process that allows to decompose the problem into smaller subproblems, that can then be tackled with state-of-the-art methods.\n2. The numerical experiments show that this approach allows to efficiently solve large problems (2000 nodes).\n\nWeak points\n------------------\n3. Many confusions in the text, in particular regarding the related works (see Feedback to improve the paper)\n4. To validate the hierarchical framework and the rewriting process, it would have been great to apply it to other large scale combinatorial problems. For instance, the multiple vehicle routing problem, where the rewriter would be responsible of assigning the customers to the vehicles.\n5. The authors do not mention whether they will release their code.\n\nRecommendation\n-------------------------\nI would vote for accept. To me the hierarchical framework and the rewriting process are novel in this context and can potentially be applied in other problems. \n\n\nQuestions to authors\n-----------------------------\n6. “large-scale VRP is an *unexplored* and challenging problem”: VRP is one of the most studied problems in Operations Research. Among other aspects, there are of course works that aim at solving large scale problems. What do you mean by unexplored?\n7. In Section 3.3, after the selection and merging phases, the hyper-regions are again split into 2  “regular sized” regions, while maintaining the routes computed in the hyper-region. Is this always guaranteed to be feasible? Say you end up with 3 routes, of 10 customers each, in the hyper-region. How to split them in this case?\n8. “These heuristics usually have a time complexity of O(n 2 log n 2 )” can you share a reference for this claim?\n9. Sec 3.3 “we restrict Gj to the K nearest regions to Gi”. How is K chosen?  \n10. Table 1: The results reported for AM-sampling vs AM-train-on-100 are a bit surprising to me. The paper (Kool et al 2019) reported the best performance when the model was trained and tested on the same size. Do you have an idea of why it’s not the case here? \n11. Regarding AM-train-on-100, was sampling or greedy rollout used?\n12. Table 2: are these results averages over a number of runs? Do you have an intuition about why the values are so close in all cases?\n13. Figure 3: what are the \"rollout steps\" here exactly? Do you have an explanation for the rapid drop of the ratio right before 100?\n14. Figures 7 and 8: Why are the routes not starting and ending at the depot in red?\n\nFeedback to help improve the paper\n---------------------------------------------------\n15. In the introduction, “since pre-defined rules are not suitable for various cases of customer distribution, those methods have poor generalization ability”. It does not make sense to talk about generalization ability for non-learning based methods.\n16. The “exploration space of large-scale VRP” / “exploration complexity” is confusing. I think you mean solution space instead of exploration space.\n17. There are confusions at several points regarding heuristics vs learning algorithms: “....can be divided into heuristics and reinforcement learning (RL)”. RL-based approaches are also computing heuristics to solve the VRP, in the sense that they are not computing exact solution of the problem. So I guess here by heuristics, the authors mean non-learning based heuristics.\n18. The Ant Colony baseline of 1999 does not look competitive at all with the other standard Operations Research heuristics for VRP (here LKH3 and OR Tools) so I don’t see the point in reporting its results (Table 1).\n19. Sec 4.1 “…many realistic industrial applications in which a vast number of customers may occur frequently.” Do you have any reference for that? I would guess that when the number of customers is really large, it’s more likely to resort to the multiple vehicle problem.\n20. Sec 4.3 “…this is the rare case in real-world.” Do you have a reference? Intuitively I tend to disagree, customers are likely to be grouped within cities for instance.\n21. For a variety of VRP instances, you could use CVRPlib: http://vrp.atd-lab.inf.puc-rio.br/index.php/en/\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose an RL-based approach, “Rewriting-by Generating (RBG)”, to solve large-scale capacitated vehicle routing problems (CVRPs): such problems are NP-hard in general and are ubiquitous. The RL agent consists of a "Generator" and "Rewriter". In generation, the graph is sub-divided into several regions and in each region, an RL algorithm runs to get the best (or near-optimal) route. The rewriter then patches these near-optimal sub-solutions together using “hierarchical RL”. 
The paper is generally well-written. 

One main concern is related to generalizability: the authors respond that their approach can work for other NP-hard combinatorial-optimization problems such as knapsack. The authors are encouraged to do a systematic study of several such (related) problems where their approach can work. It was also a concern that the overall approach of partitioning the input instance and rewriting the CVRP solution by merging regions and recomputing routes, is also employed by commercial OR solvers. The authors are encouraged to do a careful comparison (and perhaps melding) with such available solvers, to get a hybrid “OR + ML” improvement. It is also suggested that the authors include several different constraints from real-world VRP (e.g., heterogeneous vehicle costs, costs of missed shipment, route limits, upper-bounded number of vehicles etc.). 

Decision: Reject