Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper considers the problem of capacitated vehicle routing which is a famous combinatorial optimization problem that is known to be NP-hard. This paper takes the approach of solving instances of this problem using RL. The goal is this problem is to minimize the maximum time (or makespan objective) for multiple vehicles to complete various tasks subject to fuel constraint. The paper trains a graph embedding from random instances and then show that it solves new instances of this problem with reasonable accuracy. Moreover, they also show that the embedding can be transferred to other related objectives.

The strengths of this paper are as follows.

- Contributions to the literature of RL for combinatorial optimization which has become a recent growing paradigm. In this paradigm, we seek to obtain statistical algorithms (based on RL for instance) to NP-hard problems where the average instance tends to be computationally easy while the hard instances are not abundant. It is important to identify the set of combinatorial optimization problems for which we can surpass computational hardness and this paper adds to this literature.
- Extensive experimentation: The second strength of this paper is that the paper does a good job of extensively evaluating their method on a variety of instances and also other related problems/objectives.

Having said that, the paper has a number of weakness in my opinion.

- I find this paper to be rather incremental since this is not the first paper to study RL algorithms for this problem. The paper does not make a good case for why (yet) another RL based algorithm is useful for this problem and along what dimensions is this algorithm having the most novel improvements? The paper gives two reasons, but I do not find it convincing enough. In particular, it does not really show empirically why prior methods do not extend to this setting and why a new algorithm needs to be proposed.
- I found very little generalizable learnings from this paper that could be useful for the machine learning community. The paper should make a better case for why the results from this paper are important to the ICLR community. It seems like this paper is more suitable for an appropriate operations research journal such as OR/INFORMS. I would like the authors to expand/justify more along these lines. May be the paper brings to light some hard application that could lead to new algorithmic developments? 


Overall, I think the paper is scientifically sound. My ratings stem from the fact that it may not be a good fit for ICLR. As I state above, I do not find generalizable results that can appeal to a broad (or even narrow) machine learning audience and will be a better fit for more domain specific venues.
review_title: scientifically sound, perhaps not a good fit

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
An end-to-end RL algorithm, Graph-centric RL-based Transferable Scheduler (GRLTS) is proposed to solve the capacitated multi-vehicle VRP problem. 
The fuel capacity of vehicles is considered and vehicles can visit charging stations in the middle of their routes toward the customers, and if their charge is about to finish, they get a reward as good as visiting a customer. 
The goal is to minimize the makespan (completion time), which is the time between starting and finishing visiting all customers. 
The state of each vehicle includes the current fuel level, the number of customers served up to now, the allocated node to visit. The state of customers involves its location and a visit indicator flag. And, the state of each charging station is its location. The action for each vehicle is the next node to visit, and the reward consists of two parts: (i) the number of visited customers, (ii) a reward to refuel the vehicle worth visiting a customer node when the battery is almost empty, otherwise a small value. 

To use the proposed states, node and edge embedding are done by following GNN, a graph attention network that learns the attention weight over the neighbor nodes/edges to build the representation of each node. The edge values are considered a message that the source node sends to the target node. Also, in the GNN only the neighbor nodes/edges are considered.


Major comment:
Q1- By just reading the main body of the paper, it is not clear what RL model you have used, and what does it mean to obtain a softmax operator over the Q-values in equation (7). If it is a regular actor-critic model, you do not need the critic for decision making, and the critic is only involved in the training. I am not sure why the critic is involved in decision making in equation (7). Can you please clarify?

Q2- GRLTS does not perform better than the benchmarks in CVRP and TSP. What is the point of having those results in the main body of the paper? 
To me, the current paper does not give any idea about your training algorithm and just provides the MDP definition and the result. I would suggest moving them to the appendix and explain some details of your training algorithms in the main body instead of the appendix. 

Q3- Why Table 6 and Table 7 does not involve other RL and heuristic algorithms? It looks like a cherry-picking among the benchmark algorithms is performs. 

review_title: An RL algorithm for mCVRP problem is proposed 

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary
--------------
The paper presents a reinforcement learning approach to learn a routing policy for a family of Vehicle Routing Problems (VRPs). More precisely, the authors train a model for the min-max capacitated multi vehicle routing problem (mCVRP), then use it to solve variants of the problem that correspond to various VRP problems (with a single vehicle, no capacity constraints, no fueling stations, etc). They use a GNN to represent the states and the PPO algorithm to learn the policy. They validate their approach on both random instances and literature benchmarks.

Strong points
-------------------
1. The goal of using a single policy to solve a variety of routing problems
2. First RL-based approach to tackle the multiple vehicle setting of VRPs
3. Extensive numerical experiments on both randomly generated and benchmark instances


Weak points
-----------------
4. There are a lot of imprecisions/typos/lack of definitions/mathematical imprecisions (see Feedback to improve the paper)                                                        
5. According to the definition of the rewards, the expected return of the policy would be: $\sum_v \sum_t (r^v_{visit} + r^v_{refuel})$. It is important to note that this does not correspond to the objective function of the mCRVP problem. This choice of reward does not look natural to me and it would be useful to better motivate it.
6. Sec 3.3: “When an vehicle node i reaches the assigned customer node, an event occurs and the vehicle node i computes its node embedding and selects one of its feasible action…”. This is crucial but not clear to me. At a step t, some vehicles might still be in between two cities. How is that taken into account in the state s_t? With the definition of the transition function, I understand that when an action is taken at t, the vehicle arrives at destination at t+1. Does it mean that you sequentially assign only one vehicle to a city and then “wait for it to arrive” before computing the next assignment? In that case what are the events about?
7. Tables 1, 2, 3: to be relevant the results should averages over a number of random instances. Maybe it’s already the case but it is not mentioned.
8. Sec 3.4 about the training should be more precise. It was difficult for me to find the relevant information because it was scattered at different places in the (10 pages) appendix.
9. The authors do not mention whether they will share their code.

Recommendation
-------------------------
I would vote for reject. Although the problem addressed is interesting, the paper is not well-written and there are too many typos and missing explanations to understand the method.
 
Arguments for recommendation: 
----------------------------------------------
see weak points


Questions to authors
-----------------------------
10. What prevents a vehicle from getting to a customer and then not having enough fuel to go back to a refuelling station?
11. Table 1: are the results averaged over a number of random instances?
12. To improve the results on TSP and VRP, have you tried including instances with only 1 vehicle during training?
	


Feedback to help improve the paper
---------------------------------------------------
13. In the formal definition of the mCRVP (Section 2.1), there is no mention that the customers should all be visited. As it is presented, the problem is solved trivially by all vehicles doing nothing.
14. In the state definition, in the vehicle state “x_v^t is the allocated node that vehicle v to sist”. This is important and not clear. I think the authors mean that it’s the node where the vehicle v is currently located. But then in customer state, x_c^t is a location. V^c should depend on t. 
15. Action a_t in {V_c union V_R} is not mathematically correct with the definition of V_C and V_R. The update of the v_t^c variable is missing (although in definition there was no dependence on t)
16. In the definition of the refuelling rewards (section 2.2.3)
(a) the index t is missing in q^v. The rewards should also be dependent on t.
(b) What values for \alpha? If F_v < 1 then the reward is negative or might be undefined if F_v =1
17. Section 2.3: TSP is a special case of mCRVP. The fact that there is no fuel constraint is missing
18. Equation (2) what is R_C. How is it chosen?
19. Equation (3) R_R = F^v for which v?
20. Right after equation (5),\alpha_ij is defined as softmax(e_ij) but then e_ij is defined as a function of \alpha
21. Equation 7, I believe the sum should be over N_C(i) \union N_R(i)



review_title: RL approach to solve various VRPs

Meta-review: This paper looks at a natural application of robust learning for vehicle routing. The paper introduces some new ideas for this RL problem; although the problem has been considered before.  The paper gives a nice algorithm with extensive experimental contributions.  

The paper has some shortcomings. The reviewers found there to be a lack of clarity in the mathematical definitions.  Moreover, there were modeling choices that the reviewers felt needed more thorough explanation.   For these reasons, this paper falls below the bar.  The authors are encouraged to revise the manuscript taking these concerns into consideration.


Decision: Reject