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

Abstract

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