Learning Improvement Heuristics for Solving Routing Problems
By Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, Andrew Lim. IEEE Transactions on Neural Networks and Learning Systems, 2019
420 citations recorded by the source corpus.
Recent studies in using deep learning (DL) to solve routing problems focus on construction heuristics, whose solutions are still far from optimality. Improvement heuristics have great potential to narrow this gap by iteratively refining a solution. However, classic improvement heuristics are all guided by handcrafted rules that may limit their performance. In this article, we propose a deep reinforcement learning framework to learn the improvement heuristics for routing problems. We design a self-attention-based deep architecture as the policy network to guide the selection of the next solution. We apply our method to two important routing problems, i.e., the traveling salesman problem (TSP) and the capacitated vehicle routing problem (CVRP). Experiments show that our method outperforms state-of-the-art DL-based approaches. The learned policies are more effective than the traditional handcrafted ones and can be further enhanced by simple diversifying strategies. Moreover, the policies generalize well to different problem sizes, initial solutions, and even real-world data set.
Subfields: Civil and Structural Engineering, Industrial and Manufacturing Engineering
View Paper: https://www.semanticscholar.org/paper/c48fdbbd2c671c8fc9495799c063091eba5e20d6
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Industrial and Manufacturing Engineering
Citations in the corpus
- Reinforcement Learning for Combinatorial Optimization: A Survey (2020, methodology): “The authors use an LSTM encoder, specific to each of the covered problems and train region-picking and rule-picking policies jointly by applying the Q-Actor-Critic algorithm. In the same line of work, [70] has proposed learning improvement heuristics to solve TSP and CVRP using pairwise operators typ”
- POMO: Policy Optimization with Multiple Optima for Reinforcement Learning (2020, background): “The second group of baselines are from deep RL improvement-type approaches found in the literature [9, 11, 12].”
- DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization (2023, background): “These methods have also suffered from the difficulty in scaling up and the latency in inference, partly due to the sparse rewards and sample efficiency issues when learning improvement heuristics in a reinforcement learning (RL) framework (Wu et al., 2021; Ma et al., 2021).”