Solving Traveling Salesman Problem with Image-Based Classification
Shoma Miki, Hiroyuki Ebara · 2019
Combinatorial optimization is a problem with various application in the real world, and development of high-quality algorithms for solving it is important. We focus on the traveling salesman problem (TSP) which is one of typical combinatorial optimization problems, and introduce algorithms applying deep learning. One way to apply to combinatorial optimization problems is to make decisions in finding a solution using neural networks. Pixel-mapped Classification Network (PCN) we propose treats a problem as an image by mapping each vertex onto an image, and approximate evaluation of vertices to construct a tour. This can be regarded as a classification that selects the appropriate vertex. We consider construction algorithms of greedy selecting and using beam-search according to the evaluation by PCN. We conduct experiments to examine the performance of these methods, and verify the effectiveness of improving quality of solutions.