Traveling salesman problem is a widely studied NP-hard problem in the field of combinatorial optimization. Many and various heuristics and approximation algorithms have been developed to address the problem. However, few studies were conducted on the multi-solution optimization for traveling salesman problem so far. In this article, we propose a circular Jaccard distance based multi-solution optimization (CJD-MSO) algorithm based on ant colony optimization to find multiple solutions for the traveling salesman problem. The CJD-MSO algorithm incorporates "distancing" niching technique with circular Jaccard distance metric which are both proposed in this paper for the first time. Experimental results verify that the proposed algorithm achieves good performance on both quality and diversity of the optimal solutions.
Keywords: Jaccard distance; metaheuristics; multi-solution optimization; multimodal optimization; traveling salesman problem.