Active learning in estimating optimal tour length for the travelling salesman problem

Abstract

Travel Salesman Problem is the most popular combinatorial optimization problem. Although numerous heuristics and machine learning approaches were proposed, training a value function for TSP remains a challenging task. In this research, the main focus is shifted from finding a capable model to the wise choice of instances to label using active learning. Two selection criteria based on one-step look-ahead and novelty for choosing the best instance to label are proposed. In addition, a metric to evaluate performance in active learning settings is introduced. The experimental results demonstrate that applying active learning gives a significant advantage over passive learning.