Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
Question-1: How did you define a route $\tau_{i,j}$? How many of them can be there? 

minor typo:
Then we then visit
review_title: It proposes a hierarchical RL algorithm to solve large-scale VRP problems.  

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.  

My 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. 

Another 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.

review_title: Learning heuristics for CVRP, though important, is a very niche problem.  The proposed solution is very similar to what is already adopted by many of the meta-heuristics used by the OR solvers.

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary
--------------
The 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. 

Strong points
-------------------
1. 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.
2. The numerical experiments show that this approach allows to efficiently solve large problems (2000 nodes).

Weak points
------------------
3. Many confusions in the text, in particular regarding the related works (see Feedback to improve the paper)
4. 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.
5. The authors do not mention whether they will release their code.

Recommendation
-------------------------
I 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. 


Questions to authors
-----------------------------
6. “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?
7. 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?
8. “These heuristics usually have a time complexity of O(n 2 log n 2 )” can you share a reference for this claim?
9. Sec 3.3 “we restrict Gj to the K nearest regions to Gi”. How is K chosen?  
10. 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? 
11. Regarding AM-train-on-100, was sampling or greedy rollout used?
12. 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?
13. Figure 3: what are the "rollout steps" here exactly? Do you have an explanation for the rapid drop of the ratio right before 100?
14. Figures 7 and 8: Why are the routes not starting and ending at the depot in red?

Feedback to help improve the paper
---------------------------------------------------
15. 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.
16. The “exploration space of large-scale VRP” / “exploration complexity” is confusing. I think you mean solution space instead of exploration space.
17. 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.
18. 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).
19. 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.
20. 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.
21. For a variety of VRP instances, you could use CVRPlib: http://vrp.atd-lab.inf.puc-rio.br/index.php/en/



review_title: Interesting hierarchical RL framework for large-scale VRPs

final_score: rating: 6: Marginally above acceptance threshold
review_content: # Summary

The paper proposes an extended framework for neural combinatorial optimization of the vehicle routing problem.
Whereas 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.
The neural solver is based on the existing literature and the overall method is trained, as it is common in these papers, via Reinforce.
The 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.

# Comments

The 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.
The 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.
It is therefore reasonable to transfer the concept.
The 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.
The 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.
The contribution is therefore valuable to the community since it introduces concepts that might not be known, but they are not particularly novel.
Nevertheless, the results are strong and the paper will be of interest to parts of the community.

Regarding the experiments, I'm not entirely clear how the baseline results are achieved.
Ant 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.
Is OR-Tools run with a timeout or is it solved to optimality? Which CVRP model was used there?
In general, is there any information about the optimality gap of the found solutions?

In Sec. 4.2 (Analysis of Rewriting Strategy) I do not completely follow the metric used to compare both selection strategies.
Could the authors clarify this?
Also, 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.
Since 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)?
Did you have a look at the strategy the LSTM converges to?

# Minor Comments

There are a couple of language problems in the paper and an additional round of proof-reading would be beneficial.
E.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.
review_title: Improving neural VRP solving by improving smaller subproblems

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