This paper is concerned with solving combinatorial optimization problems, in particular, the capacitated vehicle routing problems (CVRP). Classical Operations Research (OR) algorithms such as LKH3 (Helsgaun, 2017) are extremely inefficient (e.g., 13 hours on CVRP of only size 100) and difficult to scale to larger-size problems. Machine learning based approaches have recently shown to be promising, partly because of their efficiency (once trained, they can perform solving within minutes or even seconds). However, there is still a considerable gap between the quality of a machine learned solution and what OR methods can offer (e.g., on CVRP-100, the best result of learned solutions is between 16.10-16.80, significantly worse than LKH3's 15.65). In this paper, we present the first learning based approach for CVRP that is efficient in solving speed and at the same time outperforms OR methods. Starting with a random initial solution, our algorithm learns to iteratively refines the solution with an improvement operator, selected by a reinforcement learning based controller. The improvement operator is selected from a pool of powerful operators that are customized for routing problems. By combining the strengths of the two worlds, our approach achieves the new stateof-the-art results on CVRP, e.g., an average cost of 15.57 on CVRP-100.
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”