Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning

Abstract

Recent works using deep learning to solve the Traveling Salesman Problem (TSP) have focused on learning construction heuristics. Such approaches find TSP solutions of good quality but require additional procedures such as beam search and sampling to improve solutions and achieve state-of-the-art performance. However, few studies have focused on improvement heuristics, where a given solution is improved until reaching a near-optimal one. In this work, we propose to learn a local search heuristic based on 2-opt operators via deep reinforcement learning. We propose a policy gradient algorithm to learn a stochastic policy that selects 2-opt operations given a current solution. Moreover, we introduce a policy neural network that leverages a pointing attention mechanism, which unlike previous works, can be easily extended to more general k-opt moves. Our results show that the learned policies can improve even over random initial solutions and approach near-optimal solutions at a faster rate than previous state-of-the-art deep learning methods.

To appear in Proceedings Machine Learning Research - ACML 2020

References in corpus (7)

• Adam: A Method for Stochastic Optimization
• Learning Combinatorial Optimization Algorithms over Graphs
• Highly Scalable Deep Learning Training System with Mixed-Precision: Training ImageNet in Four Minutes
• Neural Combinatorial Optimization with Reinforcement Learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Attention, Learn to Solve Routing Problems!
• Learning Improvement Heuristics for Solving Routing Problems

Cited by in corpus (7)

• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
• Solving the Order Batching and Sequencing Problem using Deep Reinforcement Learning
• Matrix Encoding Networks for Neural Combinatorial Optimization
• Learning for routing: A guided review of recent developments and future directions
• Graph Neural Network Guided Local Search for the Traveling Salesperson Problem
• Learning Enhanced Optimisation for Routing Problems
• A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem