Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Using a combination of RL-based solution as a warm start, this paper shows that by adding more improvement and perturbations, the quality of the solutions for capacitated VRP can be further improved. The numerical experiments show that with these extensions, the proposed mechanism is able to perform better than the SOTA LKH3 OR-based method in a shorter amount of time. I find the paper novel and interesting, but I have a few suggestions to further improve it:

1) Most of the mentioned operators are also valid for TSP. To provide a baseline for further research, I am expecting to see the performance of the proposed approach in TSP as well. 
2) I hope that you make your code and saved models publicly available for future researchers since it might not be easy to replicate your numbers.
3) Maybe in future research, the ensemble idea can be tested for making the solution independent of problem size. This is an important possible extension.
4) That would be great if you could add a section for sensitivity analysis. How the model trained for VRP100 is working for say, VRP200, or VRP50?

Minor: 
1) It worths mentioning how e-greedy that is primarily used in value-based methods is incorporated in policy gradient exploration.
2) Page 7, it should be "Figure 3(a), (b), ..."
3) Table 3 and Table 5 overlap. Maybe, it is better to merge them together. 

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: EDIT: I have read the responses and increased my rating to Weak Accept.

The paper proposes an algorithm for the Capacitated Vehicle Routing problem that starts with a random solution and then iteratively improves it by using a learned policy to select an improvement operator to apply to the current solution. Once the solution stops improving for a number of steps, a perturbation is applied to the solution, and the iterations continue by applying improvement operators selected by the learned policy. The problem is posed as a sequential decision problem, and the policy is learned using reinforcement learning. Results on synthetic instances of size 20, 50, and 100 show that the approach is able to achieve better objective value than relevant baselines and faster running time than the LKH algorithm.

Pros:
- Better objective value than baselines and running time than LKH is an impressive result.

- Paper is clearly written and easy to follow. CVRP and other background information is sufficient to fully understand the paper.


Cons:
- The proposed approach has the benefit of using a handcrafted pool of improvement operators that other learning-based approaches don’t have. This makes the comparison to previous learning approaches unfair, and the observed improvements may simply be due to the extra information that the approach gets in the form of the operator pool.

- The evaluation should be expanded to larger instances and existing benchmarks such as CVRPLib (which contains larger instances as well) to understand scalability and generalization to different instance distributions. For example, would the same improvement operator pool suffice for a completely different distribution of instances?


Additional comments:
- Typically when using RL for learning a local search policy, the reward is defined as the change in objective after applying a local move such that the sum of rewards and the initial objective value gives the actual objective value and the policy will be learning to optimize the objective function. In this paper the reward definitions RF1 and RF2 don’t have this property, which suggests that the policy is not being trained to directly optimize the CVRP objective function. Is there an explanation for why it still works?

- It would be useful to explore how well the self-attention network architecture scales to larger problems (e.g., > 1000 customers), and whether using a graph neural network instead results in better or worse results.

- Typo: “significantly worse then”

- Typo: “their would be no discounting”

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper proposes a framework combining RL and OR for solving the capacitated vehicle routing problem (CVRP). The main idea is to train an RL-based controller for choosing the OR operations necessary for improving & reinitializing the solution. Additionally, an ensemble method for diversifying the solution is proposed. The proposed method is shown to empirically outperform the existing OR method LKH3 for solving CVRP. 

Overall, this paper provides a solid contribution by proposing a new learning-based algorithm that beats conventional solver, which is quite hard to achieve. The writing is clear and easy to read. The reference and related works look complete to my knowledge. 

One weakness of the paper is the lack of experiments. Since the paper focuses on the CVRP problems, it would have been nice to compare with the LKH3 on larger graphs, e.g., the case when N > 100. One could also verify the scalability of the algorithm by examining larger-scale benchmarks and compare with heuristics faster than LKH3, e.g., see [1]. I think this is crucial for demonstrating the applicability of the algorithm to real-world problems.

[1] Uchoa et al., New benchmark instances for the Capacitated Vehicle Routing Problem, EJOR 2017
review_title: Official Blind Review #3

Meta-review:    The paper proposed the use of a combination of RL-based iterative improvement operator to refine the solution progressively for the capacitated vehicle routing problem. It has been shown to outperform both classical non-learning based and SOTA learning based methods. The idea is novel and the results are impressive, the presentation is clear. Also the authors addressed the concern of lacking justification on larger tasks by including an appendix of additional experiments. 
Decision: Accept (Poster)