Applying Deep Learning and Reinforcement Learning to Traveling Salesman Problem

In this paper, we focus on the traveling salesman problem (TSP), which is one of typical combinatorial optimization problems, and propose algorithms applying deep learning and reinforcement learning. This method is marked by learning the optimal tour as an image using a convolutional neural network, and acquires the Good-Edge Distribution which is the map of edges that could be included in the optimal tour. And it performs neighborhood search by using Good-Edge Value: evaluations of each edge calculated from the distribution. In addition, there are cases where it is not possible to obtain an optimal solution such as large scale instances or other combinatorial optimization problems, so learning by using the best solution instead of the optimal solution is important. Therefore, we also consider learning methods using reinforcement learning. We conduct experiments to examine the performance of these methods, and verify the effectiveness of improving quality of solutions.

I. Introduction

Combinatorial optimization is one of fundamental problems in computer science. And many applications in various fields such as transportation, communication, manufacturing, infrastructure planning, are expected. One of typical combinatorial optimization problems is the traveling salesman problem (TSP): given a graph, finding the tour that have minimum total edge cost and visit all vertices only once. Especially the problem whose vertex is on the 2-dimensional plane and the cost of the edge is defined as the Euclidean distance between vertices is called 2D Euclidean TSP.