Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: An RL algorithm, TAM, is proposed to solve large-scale VRP problems.  TAM learns how to split the problem into smaller problems and then solve the smaller problems which are instances of TSP by well-performed heuristic algorithms like LKH3. The splitting problem is defined as an RL problem in which the state of the system is the current partial solution which is obtained by the chosen sub-routes of the VRP problem. The action is choosing an unvisited sub-route which is the set of customers/nodes that a vehicle could serve in one round of service. The reward is the minimal distance of the chosen sub-route. To get that, for a given sub-rout, the minimum distance is obtained by using an optimal algorithm or any fast heuristic (here a learned model by RL is used to exploit the power of parallel computation by GPUs). 
The goal is to minimize the total travel length.
To assign the nodes to the sub-routes, the same algorithm as the AM model, proposed by Kool et. al (2019) is used where the masking operator is added to the decoder to assign the nodes into the sub-routes. To use the GPU for solving the TSP problem in the sub-routes, the padding mechanism is used. For each sub-route problem, the trained RL models of sizes 20, 50, and 100 are available and the model which is closest to the size of each sub-route problem is used. 

I really enjoyed reading the paper and the results are impressive to some extent.  

strength_and_weaknesses: Strength
A new RL algorithm is proposed to solve large-scale VRP problems. 

Weakness
The numerical experiments and benchmarks could be improved. 
clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear and well written. 
The algorithm is described well and should be reproducible. 
The idea of the paper is not novelty and it is explored before. But, the overall framework seems working well, which was not the case in previous papers.  
summary_of_the_review: I only have two questions from the authors which upon getting satisfying answer, I'll raise my vote. 

Q1- I did not get "If the capacity of unused vehicles cannot serve the rest demand, then the current vehicle can not visit the depot". I am not sure why the capacity of the rest of the network is considered. If you are choosing a given set of nodes to assign them to a sub-route, then, you can easily check the sum of demand of those nodes. Once the sum of demands of those nodes gets bigger than the capacity of the vehicle, you stop assigning the nodes to the vehicle. Given this, why do you need the new masking operator? This procedure should end with the same result as the suggested masking operator, though it is cheaper and more intuitive. 

Q2- In the presented results in Table 1, I do not see the optimal solution. For some of the presented instances, you can get the optimal solution with the branch & price algorithm presented in [1]. Besides, the main comment on the numerical experiment is on the benchmark set. If you want to show the true value of your algorithm you need to demonstrate the performance of your algorithm on the CVRPLIB problem set (http://vrp.atd-lab.inf.puc-rio.br/index.php/en/) and instance in [3, 4]. The ultimate benchmarking would involve comparing your results with the state-of-the-art algorithm, like [2, 4, 5], which has some of the best results on that problem set. 


[1] Pessoa, Artur, Ruslan Sadykov, Eduardo Uchoa, and François Vanderbeck. "A generic exact solver for vehicle routing and related problems." Mathematical Programming 183, no. 1 (2020): 483-523.

[2] Vidal, Thibaut. "Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood." Computers & Operations Research 140 (2022): 105643.

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

[4] Arnold, F., et al. (2019). Efficiently solving very large scale routing problems. Computers & Operations Research, 107(1), 32–42.

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

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents a framework for learning to solve VRP. The core idea is to first learn a policy that can divide the routes into sub-routes where each sub-route is covered by a single vehicle. The one can use efficient TSP solvers for each of the sub-route, and also solve them in parallel. Experiments show that the proposed approach is able to learn the solving from small-scaled datasets, and generalize the results to large graph with more than 5000 nodes.

strength_and_weaknesses: Strength:

- The problem tackled by the paper is an important combinatorial optimization that is actively used in daily work. 
- The proposed divide-and-conquer paradigm is reasonable and effective. 
- The empirical results show that the paper is able to achieve better results compared to some existing solvers. Also the paper is able to incorporate existing TSP solvers as subroutines and combine the power of both learning and existing human designed heuristics.

Weakness:

- The paper tackles a limited version of the CVRP. In practice the problem might be more complicated that it is hard to first divide the nodes while still obtaining feasible solutions. For example, in practice there would be constraints like 1) a driver could not drive more than certain hours; 2) certain packages should be delivered to a certain location within a given time period. 

- Compared to LKH3 or ORTOOLS the proposed approach obtained comparable or better results with a shorter amount of time. However in practice it is not clear if the proposed approach would further improve with more time. In other words it would be interesting to see the time-solution quality trade-offs of this method and other iteration-based solvers.

clarity,_quality,_novelty_and_reproducibility: This paper is well motivated. The experiments are relatively comprehensive and convincing. The idea is simple but effective, which has practical values. The code is not provided though. As the implementation seems to be nontrivial, the reproducibility might be an issue.

summary_of_the_review: Overall a practical paper for VRP with two-stage approaches. It is a nice combination of learning and existing heuristics. The paper can potentially be improved with more analysis of the results, and directions on handling practical constraints when deploying VRP to real-world problems.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The current study, as a strategy to effectively solve large-scale CVRP, presents a strategy for generating TSP sub-problems by clustering nodes and simultaneously solving the generated TSP problems. In particular, the sequential node selection approach has been used to decompose nodes.
strength_and_weaknesses: The decomposition strategy is a methodology that has been dealt with a lot on the OR side. A literature review of decomposition methods is required. Additionally, more recently, the NCO community has been using a decomposition strategy to deal with large-scale VRP issues. It is difficult to evaluate this paper without including these papers in the literature review and comparing them with these methods.

The current study insists that employing decomposing strategy in a constructive way (i.e., constructive heuristics) is novel in that most decomposing strategies are employed in an iterative manner (i.e., improving heuristics). However, I think it's hard to claim novelty just by suggesting a way to find a solution in a different way. For it to be truly advantageous, it is when the quality of the solution derived by such a process approaches the optimum. From that point of view, I think the strategy of finding a good solution by repeatedly decomposing and solving sub-problems can be more effective.

clarity,_quality,_novelty_and_reproducibility: 
<Methodology>

1. It is understandable that the dimension of the action that selects a cluster is large, so the current study proposes to use a sequence-to-sequence model. However, it is not clearly explained how to reduce the influence on the order. The factorial of the number of nodes generates the same reward. Isn't this redundancy affecting learning? In other words, shouldn't the attribute of permutation invariance be assigned to the learned policy?


2. In general, when decomposing nodes, clustering-based methodologies such as k-means seem to be used a lot. Compared to these methodologies, what are the advantages of decomposing-based methodologies based on sequence to sequence model? Even when the number of clustering increases, is it possible to effectively cluster by reflecting the relationships between nodes?

3. In Equation 4, why is the summation of the product up to n + l? What is n?




<Experiments>

1. Comparison with other decomposing strategies is necessary. Comparing the proposed method with a non-decomposing strategy is not fair. Because the current study proposes an effective decomposing strategy, it should compare with other effective decomposing strategies that can solve the large-scale CVRP. In addition, the performance criterion should be the optimality gap measuring the difference between the produced solution by the proposed method and the true optimum. Because many papers share the best-known solutions for large-scale CVRPs, the study should use this optimal solution as the oracle reference. The current experiment results look like a just ablation study showing the effectiveness of using the decomposing strategy.


2. At what size did AM and POMO learn? Isn't it an unfair comparison to learn them on small size and then solve them on a large size? These models are not intended to achieve transferability over size. If that is the case, wouldn't it be better to compare the performance with other methods designed to achieve size transferability?  

summary_of_the_review: Although the proposed methodology is interesting, it is necessary to quantify how much more effective the proposed decomposition strategy is compared to other decomposition strategies.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a two-stage attention-based method (TAM) to solve large-scale routing problems.

Although existing learning-based solvers suffer from their scalability (e.g., # of nodes is typically less than a thousand), TAM is trained to split the large input instance into small sub-problems with keeping global constraints. Importantly, TAM can be attached to existing solvers to improve solution qualities. The technical contribution is by attention-based problem splitting, and then sub-problems can be efficiently solved by existing heuristics or learned data-driven methods.

Experimental results are reported to support and discuss TAM. Many experimental results support the performance of the proposed approach emperically.
strength_and_weaknesses: [Strength]
- TAM can be attached with any sub-problems solvers (existing heuristics like LKH3 and data-driven methods like AM).
- TAM possibly accelerates existing heuristics (e.g., AM v.s. TAM+AM) by improving their solution qualities.
- Ablation studies for reward and mask functions are meaningful (i.e., designing rewards is an essential step for learning-based methods).

[Weakness]
- Technical contributions are a bit incremental.
clarity,_quality,_novelty_and_reproducibility: - The general idea is well explained at a higher level in Fig.1 and Fig.2. The introduction of MDP beyond the existing AM method (Kool et al. 2019) is given and explained in Eq.1 to Eq.4. Technical contributions on rewards and mask functions a explained in Eq.5 to Eq.7. In my opinion, authors clearly explained the idea. On possible drawback is the training part is almost included only in Appendix, although the authors followed as standard learning framework on RL.

- The quality of the proposed method is reasonable, i.e., it is based on well explained concepts in the paper and standard expreimental evaluations are done.

- The reproducability is now not easily evaluated for me. One reason is the proposed experiments used many related methods (e.g., AM, LKH3, TAM, ...). Another reason is no explict explanations on algorihtms (e.g., pseudo-codes). This could be improved by providing some supplemental materials.
summary_of_the_review: The paper proposes a two-stage attention-based method (TAM) to solve large-scale routing problems. In recent years, simliar problems have been investigated by several researchers, but the proposed paper seems to succeed to solve larger instances. The proposed method seemes to be technically sound, a bit incremental improvement, but a large experimental advantages can be observed by experiments on synthethic and real instance data. Importantly the advantages seems to be large, and the result (i.e., solutions of routing problems) could be much better than existing approaches.

Based on these observations, I feel that the proposed paper is above the baseline.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents a new RL algorithm called TAM for  large-scale Vehicle Routing Problems. The reviewers find this work well written, enjoyable, and impressive in terms of its results. There were some concerns about the need for a thorough literature survey, and corresponding expansion of experimental evaluation. However, I believe these concerns have been sufficiently addressed by the rebuttal.
justification_for_why_not_higher_score: Might be a niche problem setup for the ICLR community.
justification_for_why_not_lower_score: Reviewers have provided strong support for this work.
Decision: Accept: poster