Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes new ways to learn good decomposition steps in a heuristic search algorithm for the capacitated vehicle routing problem. The learning algorithm can select good seed points for the decomposition, often permitting significant speed-ups (1.5x) over other baseline decomposition algorithms (random and other simple variations). Additional experiments are conducted to evaluate the impact of the client distribution on the performance of the proposed approach.
main_review: The paper is well written and generally easy to follow. The application is interesting and the experimental results will be noteworthy for both the machine learning (ML) and operations research (OR) communities.

I suggest being careful of some affirmations and statements, which can be quite misleading. The authors have a tendency to "oversell" the contribution. The CVRP literature already contains many decomposition algorithms based on geographic partitions (see, e.g., [1] for a review). Therefore it is incorrect to mention the decomposition or "the use of spatial locality" as a novelty in the contribution statement. Instead, the contribution should be focused on the learning part, the algorithm designed for it, and the numerical experiments. Similarly, the sentence "We hypothesize that in such situations, the larger problem can be efficiently approximately solved as a sequence of smaller subproblems, which can be delegated to efficient sub-solvers." is misleading: this is a well-known fact, not an author's hypothesis.

The main contribution of the paper is the design of a learning algorithm that can select seed points during decomposition steps. However, this component is only very succinctly discussed. The authors employ a very heavy hammer (a transformer network with a dense multi-head attention mechanism) but do not provide experiments supporting the choice of this architecture. I am missing an ablation study and sensitivity analysis to deconstruct the design of this method, and a comparison with simpler regression models for this learning task.

The choice of the algorithm for the subproblems and for the experimental comparisons is not properly justified. The LKH-3 solver has never been (or even pretended to be) a state-of-the-art (SOTA) algorithm for the CVRP. The use of this method as well as OR-Tools in earlier papers on the CVRP in the ML domain (around 2017) was possibly a question of ease of integration and some herd effect (subsequent papers reproducing choices made in earlier works). Papers published at NeurIPS should follow rigorous experimental standards, and this includes i) accurately representing the application domain (the CVRP has been the subject of numerous studies in the OR domain over the last 60 years) and ii) drawing experimental comparisons with algorithms that are truly SOTA. As discussed in [1] and in a long stream of subsequent comparisons, ILS [2], HGS [3,4] and SISR [5] stand out as the current state-of-the-art for CVRP in terms of solution quality. Most notably, these methods can solve instances with around 100 customers to near-optimality within seconds. Therefore, we would expect to see experimental analyses or comparisons being built on these algorithms, especially given that source code is available for some of them.

In connection with my previous comment, the authors have used [6,7] as a principled way to generate training and test data, but they did neither report experimental results on the original instances, nor comparisons with SOTA algorithms on them. This seems necessary in such a study about new heuristic results for the CVRP. The CVRPLib website (http://vrp.atd-lab.inf.puc-rio.br/index.php/en/) gathers a lot of information on these instances, and it also includes regular updates of the best-known solutions. If the authors have found new best results during these studies, they could likewise report them.

The learning algorithm is focused on the choice of the seed points, but the number of routes $k$ is kept constant through each step of the decomposition. Yet, the number of clients per route heavily depends on the instance and application (e.g., long-haul transportation may involve only a few deliveries in each route, whereas parcel-delivery applications may involve up to 100-150 deliveries per route). Consequently, using a fixed number of routes in the decomposition may give sometimes small subproblems that are too trivial, or large subproblems that are solved inefficiently in other cases. In view of this, the parameter $k$ (or any parameter that determines the size of the subproblem, e.g., a maximum number of customers) appears to be an even more important choice than the seed point used for each decomposition. Given this critical importance, why not learning this parameter instead of expecting the user to do an extensive hyperparameter calibration to select it? This would also permit better transfer between different application contexts.

Minor comment: "exorbitant amount of a time" => Quite excessive (and dependent on the termination criterion)

Overall, this paper covers important research questions and reports very interesting experiments, but the issues related to baseline comparisons are a clear weak point that leads me to recommend a weak rejection at this stage. As suggested in this report, a more thorough experimental analysis and a better positioning in relation to the current SOTA algorithms could lead me to revise my evaluation.

[1] Laporte, G., et al.  (2014). Heuristics for the vehicle routing problem. In P. Toth & D. Vigo (Eds.), Vehicle Routing: Problems, Methods, and Applications (pp. 87-116). Society for Industrial and Applied Mathematics.

[2] Subramanian, A., Uchoa, E., & Ochi, L. S. (2013). A hybrid algorithm for a class of vehicle routing problems. Computers & Operations Research, 40(10), 2519-2531.

|3] Vidal, T., et al. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611-624. 

[4] Vidal, T. (2020). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. arXiv:2012.10384 

[5] Christiaens, J., & Vanden Berghe, G. (2020). Slack induction by string removals for vehicle routing problems. Transportation Science, 54(2), 299-564.

[6] Uchoa, E., et al. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3), 845-858.

[7] Arnold, F., Gendreau, M., & Sörensen, K. (2019). Efficiently solving very large scale routing problems. Computers & Operations Research, 107(1), 32-42.

=================================
           After author's responses
=================================

The authors have carefully considered my comments and conducted extensive numerical analyses, providing (i) new ablation experiments and (ii) tests with a SOTA algorithm for the CVRP. The results provide useful information and permit to fill the gaps and weaknesses mentioned in my previous review. Considering these changes, I am pleased to revise my score and recommend accepting the revised paper at NeurIPS.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a decomposition method for large-scale vehicle routing problems (VRPs) that leverage supervised learning. Specifically, the proposed methodology uses regression to identify a smaller, more tractable subproblem from a given initial solution, which is then addressed by another solver and incorporated into a full solution. Numerical results compare different state-of-the-art heuristics (e.g., LKH-3) and exact approaches (e.g., OR Tool) on different variations of the VRP with up to 3,000 nodes.

main_review: **Originality**

I did find the specific setup novel and interesting. There are, however, several related routing methods that incorporate learning when decide which cities to group together to solve them separately, which is a classical idea for large-scale VRPs. For example,

Poullet, Julie. Leveraging machine learning to solve The vehicle Routing Problem with Time Windows. Diss. Massachusetts Institute of Technology, 2020.

and references therein. Perhaps the key difference is that existing methods formulate the problem as either as a more traditional classification task or as a unsupervised learning problem, while in this paper the authors use a regression/classification to learn how to "break" an existing solution, which I found quite interesting. My suggestion is for authors to better relate with that associated VRP literature, as there are strong parallels between approaches.

**Quality**

The numerical study is very thorough to the best of my analysis. All the parameters are explained and detailed clearly. I believe some details could be moved from the Appendix to the main text, or at least expanded, in particular those concerning the  training details and some comments concerning the ablation study.

My main questions are:

(a) What is the impact of the initial solution to the overall approach? It seems that the initial routes could greatly modify the possible subproblems one uses both for training as well as for the actual runs. Furthermore, are the final gaps/times obtained robust with respect to the quality of the initial solution provided?

(b) The number of subproblems is quite small. What are the gains if we relax or restrict the distance thresholds? That is, how one could determine the numbers to use? Any insights here would be extremely helpful, such as a sensitivity analysis on the solution time/quality impact. Moreover, is there a way to avoid enumerating all subproblems, possibly as a future work?

**Clarity**

The paper is very well written and easy to follow. The source code is also provided and the supplemental material is excellent. 

**Significance**

In my view, the paper presents simple but effective ideas for large-scale VRPs that improve upon the state of the art heuristics under certain settings. The numerical study is thorough and insightful. I believe the technique can be of interest to a larger audience beyond routing as it is applicable to other large-scale combinatorial problems that are amenable to constructive approaches, such as the maximum stable set. I have some small concerns about the impact of the initial solution and the requirement to enumerate subproblems, but I believe they are easy to be clarified.
limitations_and_societal_impact: No specific concerns.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes an iterative framework to solve large-scale Vehicle Routing Problems. At each iteration, given the current feasible solution, a learned component selects subroutes that form a VRP subproblem. Then the subproblem is solved using a standard VRP solver (LKH-3) and the subsolution is used to update the current solution. The subproblem selector uses a Transformer encoder and predicts the subsolution cost; it is trained in a supervised way. Experimental results show that the method is able to reach the performance of the VRP solver LKH with significantly shorter computation times.

main_review: Originality
---------------

The idea of this work is to decompose a large-scale VRP into a series of smaller subproblems that can be solved efficiently. This is a standard approach in Mixed Integer Linear Programming in general and for VRPs in particular (e.g. references [30] and [31] cited in the paper). The originality comes from learning the heuristic that is responsible for the subproblem definition. 

The learning component itself is based on a standard Transformer encoder architecture. Using spatial information to guide the subproblems definition is also standard in decomposition techniques for the VRP (see e.g. [a, b]).

I believe the general strategy and the components are not novel. However their combination here gives good experimental results. 

[a] É. Taillard, 1993, Parallel iterative search methods for vehicle routing problems.  
[b] Santini et al, 2021, Decomposition strategies for vehicle routing heuristics.   


Quality
----------
The paper is of good quality. I have a couple of concerns regarding the experimental validation:

In general to give a more precise sense of the improvements, I think it’s important to look at and report the optimality gaps (average and standard deviation) w.r.t the best found solution i.e. (Method cost - Best sol cost)/best sol cost. It would also be useful to indicate the size of the test set in the main text. 

Since this paper proposes a decomposition framework for VRPS, I think it would be relevant to compare to other decomposition heuristics such as the cited POPMUSIC framework (or e.g. [c], the heuristics cited in [b]) that specifically target large-scale problems. 
While LKH-3 is known to be an efficient heuristic to solve a variety of TSP and VRP problems, I am not sure it is the state-of-the-art solver for large scale VRPs. Do the authors have a reference that claims that?

Also the authors observe that the random problem-selector baseline achieves a similar performance within the same computation time in the uniform distribution case and with more time in the clustered mixed datasets. Do the authors have an explanation/interpretation of this observation?

In Table 1, the AM greedy gives a lower cost than the AM sampling. This is surprising as it contradicts the results reported in the original paper (admittedly for smaller problems). Do the authors have an idea of why it’s the case? What was the sample size? Since the computation time is significantly shorter than all other methods, have the authors tried increasing the sample size?

Finally, I wonder how the size of the subproblems is controlled. If the demands are very small w.r.t the vehicle capacity, the initial solution may contain only say 2 routes. Then there is only one subproblem that is the entire problem. Can this happen?

[c] Vidal, 2020, Hybrid genetic search for the cvrp: Open-source implementation and swap* neighborhood.  


Clarity
---------

The paper is clear and well-written.  
A suggestion: I did not get much from figures 6 and 7 whereas I would have liked to see more details in the main paper about how the proposed method was adapted to other variants of the VRP (Section 6.5).

Some typos/details:  
L49-52: this is more of a description of a heuristic solution of the VRP rather than the problem itself. The vehicle capacity may return to he depot before  exhausting its capacity if it leads to a better cost.   
L61: Subproblem: the depot node… —> Subproblem: CVRP in the depot node….  
L14: *The* vehicle routing problem  
L54: *the* depot 0. 
L242: begets —> gets.  


Significance
-----------------

The paper focuses on solving large-scale vehicle routing problems, using a decomposition strategy. I feel like the contribution is quite specific to VRPs. For example it's not clear how this can be adapted to the Traveling Salesman Problem (even though it is a closely related problem). 

The usefulness to VRP practitioners depends on how the results of this method compare to strong decomposition heuristics for large-scale VRPs (see above Quality section).

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper introduces a local search technique for vehicle routing problems (VRP) that decomposes the general problem and delegates smaller subproblems to a subsolver, e.g. an exact VRP solver.
How to decompose the problem is learned from a generated training set using a transformer model and is the main contribution of the paper.
Experiments results with a comparison to recent works in the area show the effectiveness of the proposed method.

main_review: It is noticed that a VRP can be decomposed into smaller subproblems that are aware of spatial locality, i.e. that a locally optimal (or at least good) subroute in an area of the overall problem is commonly part of the overall optimal (or near-optimal) route.
How to pick a good region to make improvements and find locally good routes is the main question of this research and the proposed solution is to learn a model that identifies the subproblems.

Decomposition is an important aspect for solving large combinatorial problems (such as VRP) and it is a common technique, e.g., in operations research for problem modeling. Identifying appropriate subproblems takes away a huge burden and is therefore a timely contribution in the area.
My concern is related to the generality of the method, since selecting locally connected areas in the VRP problem space is relatively easy compared to other combinatorial problems.

For the experiments presented in VRP, the same criticisms are for most (if not all) neural combinatorial optimization problems apply: The shift in training + testing effort vs. the exact solvers that only have testing effort (and there take longer), but can provide guarantees. I don't think that this problem has to be solved in this paper, but it will be a constant struggle for the time being.

My conclusion is that the presented method, when only limited to VRP, is good and interesting, but I'm missing the connection to the larger area of combinatorial optimization and solving NP-hard problems.

Questions:
- OR-Tools is selected as a baseline. It is written "We set 15 min as the time-out [..], which converges in all settings.". What is meant by converging? It is clear that OR-Tools (an exact solver) does not find the optimal solution in that time and is limited by the timeout, as shown in the table. Does converge only mean that it finds _any_ solution?
- Given my earlier criticism on generalization, what is your expectation how well other subsolvers would work in this or other problems?

Update: I read the author responses and raise my score.
limitations_and_societal_impact: Limitations and societal impact are adequately addressed.
review_title: null

Meta-review: This paper proposes and analyzes a learning augmented local search algorithm to solve large-scale VRPs. Overall, all reviewers found novelty and merit in the work that was presented, but a number of questions and potential concerns of the work were posed. In their rebuttal, the author(s) were very thorough and convincing in answering these questions/concerns, and in many cases additional experiments were performed to provide additional insights in response to specific reviewer questions.

As a result of these interactions, the unanimous decision of the reviewers was to accept the paper (with multiple reviewers raising their final scores), continent on the the author(s) commitment to revise the paper to incorporate the following: (1) the revised statement of contributions they provided in the rebuttal, (2) an expanded discussion of other related learning-based approaches to this problem, (3) the additional comparative results produced relative to HGS, which was suggested as a better SOTA approach to compare against than LKH-3 and (4)  the results of new ablation experiments that were performed in response to specific reviewer queries that further enhance the paper's conclusions. In response to a direct question regarding how the authors would accomplish all revisions during the rebuttal phase, the author(s) explicitly agreed to this set of changes, and we are taking them at their word.
Decision: Accept (Spotlight)