Deep learning

Physics

Vehicle routing problem

Heuristics

Computer network

Mathematics

Reinforcement learning

Algorithm

Optics

Mathematical optimization

Epistemology

Limit (mathematics)

Mathematical analysis

Philosophy

Artificial intelligence

Travelling salesman problem

Set (abstract data type)

Focus (optics)

Programming language

Computer science

Simple (philosophy)

Routing (electronic design automation)

IEEE Transactions on Neural Networks and Learning Systems

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.

Learning Improvement Heuristics for Solving Routing Problems