Wu Yaoxin, Song Wen, Cao Zhiguang, Zhang Jie, Lim Andrew
IEEE Trans Neural Netw Learn Syst. 2022 Sep;33(9):5057-5069. doi: 10.1109/TNNLS.2021.3068828. Epub 2022 Aug 31.
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.
最近利用深度学习（DL）解决路由问题的研究集中在构造启发式算法上，其解决方案仍远未达到最优。改进启发式算法有很大潜力通过迭代优化解决方案来缩小这一差距。然而，经典的改进启发式算法均由手工制定的规则引导，这可能会限制其性能。在本文中，我们提出了一个深度强化学习框架来学习路由问题的改进启发式算法。我们设计了一种基于自注意力的深度架构作为策略网络，以指导下一个解决方案的选择。我们将我们的方法应用于两个重要的路由问题，即旅行商问题（TSP）和容量受限车辆路径问题（CVRP）。实验表明，我们的方法优于基于DL的现有方法。所学习到的策略比传统手工制定的策略更有效，并且可以通过简单的多样化策略进一步增强。此外，这些策略能很好地推广到不同的问题规模、初始解决方案，甚至是真实世界的数据集。
