Reinforcement Learning for Solving the Vehicle Routing Problem
We present an end-to-end framework for solving the Vehicle Routing Problem (VRP) using reinforcement learning. In this approach, we train a single policy model that finds near-optimal solutions for a broad range of problem instances of similar size, only by observing the reward signals and following feasibility rules. We consider a parameterized stochastic policy, and by applying a policy gradient algorithm to optimize its parameters, the trained model produces the solution as a sequence of consecutive actions in real time, without the need to re-train for every new problem instance. On capacitated VRP, our approach outperforms classical heuristics and Google's OR-Tools on medium-sized instances in solution quality with comparable computation time (after training). We demonstrate how our approach can handle problems with split delivery and explore the effect of such deliveries on the solution quality. Our proposed framework can be applied to other variants of the VRP such as the stochastic VRP, and has the potential to be applied more generally to combinatorial optimization problems.
Updated review: ---------------------- I am happy with the authors response to my two main concerns. I am raising my score to an accept conditional on the additional results being added to the paper.  Original review: --------------------- The reviewed paper presents an application of model-free reinforcement learning to the problem of optimal vehicle routing. The considered application is interesting and potentially of high-impact. It is computationally difficult to solve and finding optimal solutions for large instances is - "in the wild" - currently done with the use of heuristics. The presented appproach marks a significant improvement over said heuristics while being "cheap" to compute.   The paper is well written and easy to follow, the related work background is reasonable, yet it fails to point out connections to graph-networks. The description of problem setting is thorough and easily understandable, making this paper a good reference for future attempts to address similar problems with ML techniques.  The contribution of the paper is purely empirical - which is not necessarily a bad thing. It builds on existing theory and proposes problem specific adjustments. The empirical evaluation is thorough and meaningful, giving useful comparisons to externally implemented SOTA algorithms as well as to simple heuristics.  Arguably such a paper might be better suited for presentation in an operations research conference or journal and not perfectly suited for NIPS. I however refrain from such judgement as I think the paper is interesting enough (modulo my main concerns below) and would suggest that the area chair has a second look.  Overall the paper could well be accepted to NIPS if the two main concerns that I outline below would prove to be unsubstantiated / could be addressed. For now I mark it with a weak reject but I would increase my score to a weak accept/accept if the concerns can be addressed (which would merely require running additional experiments with Pointer networks and adding a short paragraph in the related work).  Main concerns with the paper: 1) Section 3.1 makes it sound as if pointer networks are simply not applicable to the problem. Which is not the case as far as I understand. Sure it will be more expensive to re-evaluate the pointer network once an input has changed but it is technically possible. I fail to see why this cannot be implemented (and in fact just changing the inputs every time step e.g. in tensorflow should automatically generate the required computational graph). In fact you mention in l. 189 that the problem with applying  a simple Pointer Network is mainly a computational one. If this is the case then you should provide a comparison to pointer networks at least on small scale instances and show when and how they break!  2) Your proposed solution in 3.2, to me, reads simply as applying a special case of a graph network (see e.g. [1] and maybe [2-3] for introductions) how is this different than a graph network with a pointer network output ? If it is not then you should discuss/relate to the graph-network line of work in the related work/background section.   Experiments:  - What is the variance of the results wrt. training seeds ? I.e. the plot in Figure 3 seems to show variance accross problem instances for one trained policy, but how does the performance vary wrt. the training itself ? - One appealing property of the method should be that it can handle variable problem sizes yet no attempt is made to quantify this property. Why do you not  try to train on VRP10 to VRP100 and see how well a joint model does ? Would such variability in training sequence size not anyway be required for any practical application ? If so it would also be important to know how the policy compares in these instances to e.g. OR-Tools. Unfortunately does not generalize over problem instances, e.g. more nodes etc.   Specific comments and minor typos: l. 29.: "milestone on the path toward approaching" -> I guess you mean milestone on the path towards solving ? l. 34-36: "Obviously, this approach is not practical in terms of either solution quality or runtime since there should be many trajectories sampled from one MDP to be able to produce a near-optimal solution." -> It is not clear to me what you mean here, I guess you mean that solving an MDP "on-the-fly" every time demands change is too expensive ? What do you mean by many trajectories are needed ? It is not clear that you could not use a model for this to me and what the exact difference is you are trying to point out here. Revise that sentence. l. 52: "which is actually simpler than the Pointer Network approach" -> Remove actually. This sounds as if there was a counter-point to said claim before. Expressing your surprise here is not necessary. l. 54: "Our model" -> it is confusing to call this a model here and before as you are *not* trying to learn a model of the MDP but just use a different parameterization for the policy. Maybe re-write to "policy model" or "actor-critic model" or something like that ?  l. 59: appealing to whom ? I guess you mean it is appealing to practitioners ? l. 64: "inputs change in any way" -> clearly not in any arbitrary way :) try to be a bit more precise, e.g. do you want to say it is robust to noise or to changing rewards of the VRP or ... l. 72: "is ones" -> "is one" l. 78: "and *at* no extra cost" l. 80: reads colloquial better: "[...] we briefly review required notation and relations to existing work" ?  l. 84: "which is almost the same": either substantiate this claim or simply write: "which shared by many of these models" l. 91: "wisely" is inappropriate here -> chang eto "more directly" or "more explicitly" l. 98: "for policy representation" -> "for the policy parameterization" Section 3: as written above the use of the term Model is a bit loose in the paper. Sometimes it referes to the policy, somethimes to the problem formulation itself (the MDP) and sometimes to the combination of both, try to be more specific. l. 226: remove braces this is a full sentence.  [1] Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. Computational capabilities of graph neural networks [2] Li, Y., Tarlow, D., Brockschmidt, M., and Zemel, R. Gated graph sequence neural networks.  [3] Battaglia, P., Pascanu, R., Lai, M., Rezende, D. J., et al. Interaction networks for learning about objects, relations and physics